第八章进程调度和时间 UNX是分时多进程操作系统，进程间的运行调度是整个 系统运行控制的最根本内容。 进程调度的基本方式： 把每一次硬件时钟中断称为一个时钟“滴答”，由若干 个时钟滴答构成一个时间片。 核心给每一个用户进程分配一个时间片，当该进程的时间 片用完后，核心抢先该进程并调度另外一个进程运行。一段 时间以后，核心又会重新调度该进程继续运行下去。以此方 式，核心让各个进程轮流运行。 核心进程的运行：或者运行在不可被抢先的状态下；或者 睡眠在某个中断级别上。 1
第八章 进程调度和时间 UNIX是分时多进程操作系统，进程间的运行调度是整个 系统运行控制的最根本内容。 进程调度的基本方式： 把每一次硬件时钟中断称为一个时钟“滴答”，由若干 个时钟滴答构成一个时间片。 核心给每一个用户进程分配一个时间片，当该进程的时间 片用完后，核心抢先该进程并调度另外一个进程运行。一段 时间以后，核心又会重新调度该进程继续运行下去。以此方 式，核心让各个进程轮流运行。 核心进程的运行：或者运行在不可被抢先的状态下；或者 睡眠在某个中断级别上。 1
8.1多级反馈循环调度算法 1、算法思想 核心给进程分配一个CPU时间片，抢先一个超过其时间片的 进程，并把它反馈到若干优先级队列中的某一个队列上。 当进程的上下文切换结束时，核心执行schedule_process 算法来调度一个进程，即从处于“在内存中就绪（状态3）”和 “被抢先（状态7）”状态的进程中，选取优先权最高的就绪进 程。 如果若干个进程都具有相同的最高优先权，则核心选择在“ 就绪”状态时间最长的进程。 如果没有可运行的合格进程，核心则休闲等待，直到下次中 断，下次中断最迟发生在下一个时钟滴答时。 2
8.1 多级反馈循环调度算法 1、算法思想 核心给进程分配一个CPU时间片，抢先一个超过其时间片的 进程，并把它反馈到若干优先级队列中的某一个队列上。 当进程的上下文切换结束时，核心执行schedule_process 算法来调度一个进程，即从处于“在内存中就绪（状态3）”和 “被抢先（状态7）”状态的进程中，选取优先权最高的就绪进 程。 如果若干个进程都具有相同的最高优先权，则核心选择在“ 就绪”状态时间最长的进程。 如果没有可运行的合格进程，核心则休闲等待，直到下次中 断，下次中断最迟发生在下一个时钟滴答时。 2
算法schedule_process 输入：无 输出：无 { while(没有能被选取运行的进程) for(就绪队列中的每个进程) 取已装入内存的、优先级最高的进程； f(没有合格运行的进程) 机器休闲；*下次时钟中断使机器脱离休闲状态，重新开始循环*/ } 将选取的进程从就绪队列中移出； 切换到被选取进程的上下文，恢复其执行； } 3
算法 schedule_process 输入：无 输出：无 { while (没有能被选取运行的进程) { for (就绪队列中的每个进程) 取已装入内存的、优先级最高的进程； if (没有合格运行的进程) 机器休闲； /* 下次时钟中断使机器脱离休闲状态，重新开始循环 */ } 将选取的进程从就绪队列中移出； 切换到被选取进程的上下文，恢复其执行； } 3
2、调度参数 核心态优先权 优先级 进程 进程对换 等待磁盘VO 中断 等待缓冲区 等待索引节点 等待tty输入 中断 等待tty输出 等待子进程退出 优先权阈值 用户级0 用户级1 :: 用户态优先权 用户级n 4
2、调度参数 4 核心态优先权 优先级 优先权阈值 用户态优先权 不可中断可中断 进程 进程对换 等待磁盘I/O 等待缓冲区 等待索引节点 等待tty输入 等待tty输出 等待子进程退出 用户级 0 用户级 1 用户级 n ……
核心在三种情况下计算进程的优先权： ①、核心给一个即将进入睡眠态的进程赋予一个特定的优先权。 越是等待系统紧俏资源的进程，获得的优先权越高。 ② 核心调整从核心态返回到用户态的进程的优先权。 一进程在核心态下运行时拥有的较高优先权，必须在返回 用户态时降低为用户级优先权。此外，该进程刚占用了宝贵的 CPU时间，为公平起见也需降低本进程的优先权。 ③、时钟中断处理程序每隔一个“时钟滴答”调整所有用户态进 程的优先权。 一核心运行调度算法，防止某个进程垄断CPU的使用。 5
核心在三种情况下计算进程的优先权： ①、核心给一个即将进入睡眠态的进程赋予一个特定的优先权。 —— 越是等待系统紧俏资源的进程，获得的优先权越高。 ②、核心调整从核心态返回到用户态的进程的优先权。 —— 进程在核心态下运行时拥有的较高优先权，必须在返回 用户态时降低为用户级优先权。此外，该进程刚占用了宝贵的 CPU时间，为公平起见也需降低本进程的优先权。 ③、时钟中断处理程序每隔一个“时钟滴答”调整所有用户态进 程的优先权。 —— 核心运行调度算法，防止某个进程垄断CPU的使用。 5
在一个进程的时间片中，时钟可能要使它中断若干次 遇到多次“时钟滴答”，每次中断时，时钟中断处理程序都要重 新计算所有进程（包括运行进程和等待进程）的CPU使用量，并 由此调整各就绪进程的优先权值。 CPU使用量=decay(CPU)=CPU/2 其中的CPU是进程占用处理器的时间（时钟滴答数)。 进程优先数(priority)=(CPU使用量2)+（初始用户优先数） 其中的“初始用户优先数”就是优先权初始值。 优先数越大，则优先级越低；优先数越小，则优先级越高一 一运行进程的运行时间越长，优先数越高，优先级降低；就绪进 程等待的时间越长，优先数越低，优先级升高。 用户级优先权进程不能跨越阈值获得核心级优先权。 6
在一个进程的时间片中，时钟可能要使它中断若干次 —— 遇到多次“时钟滴答”，每次中断时，时钟中断处理程序都要重 新计算所有进程（包括运行进程和等待进程）的CPU使用量，并 由此调整各就绪进程的优先权值。 CPU使用量=decay(CPU) = CPU/2 其中的CPU是进程占用处理器的时间（时钟滴答数）。 进程优先数(priority)=(CPU使用量/2) + (初始用户优先数) 其中的“初始用户优先数”就是优先权初始值。 优先数越大，则优先级越低；优先数越小，则优先级越高— —运行进程的运行时间越长，优先数越高，优先级降低；就绪进 程等待的时间越长，优先数越低，优先级升高。 用户级优先权进程不能跨越阈值获得核心级优先权。 6
核心态优先权 优先级 进程 进程对换 等待磁盘/O 可 等待缓冲区 等待索引节点 等待tty输入 可中断 等待tty输出 等待子进程退出 优先权阈值 用户级0 用户级1 :: 用户态优先权 用户级n 进程在优先级队列中移动 7
7 核心态优先权 优先级 优先权阈值 用户态优先权 不可中断可中断 进程 进程对换 等待磁盘I/O 等待缓冲区 等待索引节点 等待tty输入 等待tty输出 等待子进程退出 用户级 0 用户级 1 用户级 n …… 进程在优先级队列中移动
说明： 1、如果进程正在执行一段临界区代码时收到时钟中断，它先“ 记住”此事，并继续运行，直到当前处理机执行级别降低之后 的下一次时钟中断时，再重新计算进程优先权。 2、提高系统实时性（响应速度)的方法： 缩短时间片 提高衰减函数的衰减速度 一使进程轮转的频率更快，但系统开销更高。 8
说明： 1、如果进程正在执行一段临界区代码时收到时钟中断，它先“ 记住”此事 ，并继续运行，直到当前处理机执行级别降低之后 的下一次时钟中断时，再重新计算进程优先权。 2、提高系统实时性（响应速度）的方法： 缩短时间片 提高衰减函数的衰减速度 —— 使进程轮转的频率更快，但系统开销更高。 8
3、进程调度实例： 假设系统中有A、B、C三个同时建立的进程，具有相同的 初始优先数60。系统中没有其它进程，这三个进程也没有做任何 系统调用。时间片大小为一秒钟，每一秒钟产生60个时钟“滴答 ”，每个时间片到时，调用衰减函数重新计算每个进程的CPU使 用量，必要的话就做上下文切换： CPU使用量=decay(时钟滴答数)=时钟滴答数2 则进程的优先数为： priority=(CPU使用量/2)+60 60为初始优先数。假设A进程先运行，下图为调度的顺序： 9
3、进程调度实例： 假设系统中有A、B、C三个同时建立的进程，具有相同的 初始优先数60。系统中没有其它进程，这三个进程也没有做任何 系统调用。时间片大小为一秒钟，每一秒钟产生60个时钟“滴答 ”，每个时间片到时，调用衰减函数重新计算每个进程的CPU使 用量，必要的话就做上下文切换： CPU使用量 = decay(时钟滴答数) = 时钟滴答数/2 则进程的优先数为： priority = (CPU使用量/2) + 60 60为初始优先数。假设A进程先运行，下图为调度的顺序： 9
时间 进程A 进程B 进程C : 优先数 CPU计数 优先数 CPU计数 优先数 CPU计数 0 60 0 60 0 60 0 1 时间片到，重新 计算优先数 2. 0=0/2 60 75 30 60 0 60 1 75=30/2+60 30=60/2 2 60=0/2+60 67 15 88 2 75 60 0 1 2. 60 63 7 67 15 75 3 8 9.. 67 76 33 63 7 67 15 8 9 68 9999999999999999999999 76 8 63 7 10
10 时间 进程A 进程B 进程C 0 1 2 3 4 5 60 75 67 63 76 68 0 1 2 . . . 60 30 60 60 75 67 63 76 60 60 60 75 67 63 0 1 2 . . . 60 30 0 1 2 . . . 60 30 优先数 CPU计数 优先数 CPU计数 优先数 CPU计数 0 0 0 15 15 15 7 7 8 9 . . . 67 33 7 8 9 . . . 67 33 时间片到，重新 计算优先数 75=30/2+60 30=60/2 0=0/2 60=0/2+60