ch10处理机调度

制作者：凤羽翚操作系统OperatingSystem网址：联系作者：[e-mail]第10章处理机调度Chapter10ProcessorScheduling制作者：凤羽翚10-2操作系统OperatingSystem教学要求•本章目标：–本章介绍进程调度的概念及其就是按照某种算法动态地将处理机分配给合适的就绪进程，使之执行。常见的进程调度算法有：先来先服务调度算法，优先级调度算法，时间片轮转算法，最短进程优先调度算法，多级反馈队列调度算法等等。介绍–在同一个计算机系统中安装多个处理机，使它们协调工作，以完成用户规定的任务，这种的系统称为多处理机系统及其。尽管多处理机系统出现了新的特点，但多处理机操作系统与单机操作系统基本相似。较常见的多处理机的调度模式有：自调度模式，专用处理机调度模式，群调度模式，多模式调度，主从式调度模式等。同时还介绍了–Linux操作系统的三种中进程调度算法有三种：基于优先级的时间片轮转（RR）调度算法，基于优先级的先来先服务（FIFO）调度算法，可抢占的动态优先级调度算法。•教学目标：–进程调度的作用，进程调度的算法，多处理机系统及其特点，多处理机调度的策略；Linux系统进程调度的实现方法。•重点与难点：–进程调度，上下文切换，进程调度算法，多处理机系统及其特点，多处理机调度，Linux系统中的进程调度。•专业术语：–地址映射、页表、段表、虚拟存储、快表、抖动、工作集制作者：凤羽翚10-3操作系统OperatingSystemAgenda•10.1概念•10.2处理机调度的类型•10.3进程调度算法•10.4多处理机调度•10.5Linux的进程调度制作者：凤羽翚10-4操作系统OperatingSystem10.1概念10.1.1进程调度的概念–系统能够按照某种算法动态地将处理机分配给合适的就绪进程，使之执行，这一过程称为进程调度，实现进程调度的程序称为进程调度程序。10.1.2进程调度的功能–记住系统中所有进程的状态和执行情况–根据调度算法，决定把处理机分配给哪个就绪进程，分配多长时间–分配处理机–回收处理机处理机调度制作者：凤羽翚10-5操作系统OperatingSystem10.1概念10.1.3引起进程调度的原因–正在运行的进程顺利地完成任务而正常结束。–正在运行的进程因出现错误或故障而异常结束。–进程提出了IO请求，或需要等待某事件的发生。–进程为实现与其它进程的同步而执行了某些原语，如P操作、阻塞原语block导致自己阻塞而离开处理机，或执行V操作、唤醒原语wakeup，唤醒了等待队列中的就绪进程。–分时系统中，分配给进程的时间片已用完。–在一些系统中，就绪进程的高优先级高于运行中的进程时，它可以抢占处理机，从而引起新的进程调度（这与调度方式有关）。处理机调度制作者：凤羽翚10-6操作系统OperatingSystem10.1概念10.1.4选择进程调度算法的因素–系统的设计目标或系统的类型–进程的类型–系统资源的均衡使用及其利用率–对用户的公平程度10.1.5进程调度的性能评价–处理机的利用率–系统吞吐量。指单位时间内处理机所完成的进程数。–轮转时间（turnaround）–响应时间–可靠性、进程在就绪队列中的等待时间与执行时间的比值也是一个重要的评价指标。处理机调度制作者：凤羽翚10-7操作系统OperatingSystem10.2处理机调度的类型10.2.1按运行的进度分•长程调度–长程调度，又叫作业调度，或高级调度，其主要功能是按照某种算法，从存放在系统外存中的作业队列中选择作业进入内存，为它们创建进程、分配必要的资源，并将进程送入就绪队列，做好执行前的准备。•中程调度–中程调度，又叫交换调度，或中级调度，它能在短期内调整系统的负荷，提高内存的利用率和系统吞吐量。它提供“挂起”和“解除挂起”等功能，将那些暂时不能运行的进程从宝贵的内存调到外存上去等待，以减缓内存的紧张。在内存有空闭时，按照一定的算法，将那些在外存上等待并已获得了运行条件的进程重新从外存调入内存，并置为就绪状态，挂入就绪队列上等待调度。。•短程调度–短程调度，又叫进程调度，或低级调度，其主要功能是按照某种算法，从就绪队列中选择进程，然后将处理机分配给该进程，使之处于运行中。处理机调度制作者：凤羽翚10-8操作系统OperatingSystem10.2处理机调度的类型10.2.2按占有处理机的能力分–剥夺方式•所谓剥夺方式，又称为可抢占方式，是指当一个进程正在处理机上运行时，如果出现了更高优先级即更为重要紧迫的就绪进程，系统就立即暂停当前进程，强行将处理机分配给更重要紧迫的进程。–非剥夺方式•非剥夺方式，又称为不可抢占方式，是指当系统把处理机分配给一个进程后，就让这个进程在处理机上一直运行下去时，直到进程运行完毕或阻塞，或时间片用完，决不允许优先级更高的、更重要紧迫的就绪进程强行占用处理机。处理机调度制作者：凤羽翚10-9操作系统OperatingSystem10.3进程调度算法10.3.1先来先服务调度算法–先来先服务（Firstcomefirstserved,FCFS）调度算法是最为简单的一种进程调度算法，它根据进程进入就绪队列的先后次序来分配处理机，实现的是非剥夺调度方式。当一个进程获得处理机并运行后，它将一直占用处理机，直到该进程完成其任务，或因等待某个事件或资源而不能继续运行时才释放处理机。–先来先服务算法简单，容易实现，但效率较低，因为它实际上只考虑作业在系统中等待时间的长短，不考虑作业要求运行时间的长短，可能会造成新来的短作业需要长时间地等待长作业的运行，平均周转时间较大。处理机调度制作者：凤羽翚10-10操作系统OperatingSystem10.3进程调度算法10.3.2优先级调度（priorityscheduling）算法–总是把处理机分配给优先级最高的就绪进程。优先级反映了进程执行任务的轻重缓急，一般用优先数来表示。–优先级的类型•静态优先级。指进程的优先级（数）是在进程创建时就确定，此后在进程的整个生命期中就固定不变。确定进程优先级的依据包括：进程的类型、进程对资源的需求情况、用户的要求。•动态优先级。指进程在创建时根据进程的特点和系统资源的使用情况就确定了一个初始优先级（数），在进程的生命期中系统可以根据进程的执行情况和外界因素的变化而重新调整。进程优先级（数）的调整依据主要有：进程占有处理机时间的长短、进程等待处理机时间的长短、进程对资源的使用要求。处理机调度制作者：凤羽翚10-11操作系统OperatingSystem10.3进程调度算法10.3.2优先级调度算法–调度的方式•非抢占的优先级调度算法。一旦处理机分配给当时优先级最高的一个就绪进程后，该进程一直运行下去，直到自身的原因（如任务已完成，或等待某事件）而让出处理机。在进程的执行期间，即使出现了更高优先级的进程，即不能从运行中的进程处抢走处理机。•可抢占的优先级调度算法。任何时候都严格按进程的优先级分配处理机，它要求在处理机上运行的进程必须是当时系统中优先级最高的可执行进程。在一个高优先级的进程被分配到处理机并执行时，如果出现一个更高优先级的进程，如刚创建的、或刚唤醒的，进程调度程序立即停止原最高优先级的进程运行，迫使它把处理机让给新出现的最高优先级的就绪进程。。处理机调度制作者：凤羽翚10-12操作系统OperatingSystem10.3进程调度算法10.3.3时间片轮转调度算法–采用轮转法（RoundRobin,RR）调度算法的系统，将所有就绪进程按到达时间的先后顺序排成一个就绪队列，进程调度程序总是把处理机分配给就绪队列中的第一个进程执行，但进程只能运行一个时间片。如果进程在这个时间片内还不能执行完毕，则系统将该进程移入到就绪队列的尾部等候再次调度，而将处理机分配给下一个就绪进程（排在当前队首的进程）。处理机调度制作者：凤羽翚10-13操作系统OperatingSystem10.3进程调度算法10.3.3时间片轮转调度算法–采用轮转法（RoundRobin,RR）调度算法的系统，将所有就绪进程按到达时间的先后顺序排成一个就绪队列，进程调度程序总是把处理机分配给就绪队列中的第一个进程执行，但进程只能运行一个时间片。如果进程在这个时间片内还不能执行完毕，则系统将该进程移入到就绪队列的尾部等候再次调度，而将处理机分配给下一个就绪进程（排在当前队首的进程）。10.3.4最短进程优先调度算法–最短进程优先（ShortestJobFirst）调度算法，就是从就绪队列中挑选出那些所需运行时间最短的进程，并把处理机分配给该进程，使之执行。这是一种非抢占的调度策略，有利于减少平均等待时间，提高系统的吞吐量。处理机调度制作者：凤羽翚10-14操作系统OperatingSystem10.3进程调度算法10.3.5多级反馈队列调度算法–多级反馈队列（Multipl-levelQueue）调度算法实际上是一种可变时间片的轮转调度算法。处理机调度制作者：凤羽翚10-15操作系统OperatingSystem10.3进程调度算法–它的实施过程如下所述。•（1）在系统中设置多个就绪进程队列，每个队列对应一个调度级别或优先级，第一个队列的优先级最高，以下各个队列的优先级逐次降低。•（2）赋予各个就绪队列中的进程以不同的时间片。优先级越高的就绪队列中的进程所分得的时间片越小，优先级越低的进程所分得的时间片越大，通常优先级每低一级，队列中进程所分得的时间片就增加一倍，如第k+1队列中的进程所分得的时间片是第k队列中进程的两倍。所以，进程的优先级降低了，但其获得的时间片却增加了。•（3）每个队列按先来先服务的原则排序。•（4）当一个新进程进入内存后，首先将它排在第一个队列的尾部等候调度。该队列中的进程按先来先服务的原则分配处理机，并在规定的时间片内运行。如一个进程被调度、并在规定的时间片内执行完毕，该进程就可准备撤离系统；如该进程尚未执行完毕，但需要等待某事件的发生而主动让出处理机，则该进程移入相应的等待队列；如进程用完给定的时间片后仍未执行完毕，则进程调度程序将该进程移入下一级队列的尾部去等待，而将处理机分配给同队列中的下一个就绪进程。•（5）只有当第一个就绪队列为空时，调度程序才去调度第二个队列中的就绪进程，依次类推，只有当第1队列到第k队列为空时，调度程序才去调度第k+1队列中的就绪进程。•（6）当第k队列中的一个进程正在运行时，如果出现了一个优先级更高的就绪进程，则调度程序将暂停正在运行的进程，并将它移入到第k队列的尾部去等待，同时把处理机分配给新出现的更高优先级的进程去运行。处理机调度制作者：凤羽翚10-16操作系统OperatingSystem10.4多处理机调度•10.4.1多处理机系统简介–多处理机系统的定义•在同一个计算机系统中安装多个处理机，使它们协调工作，以完成用户规定的任务。这样的计算机系统就叫多处理机系统。–多机系统的优点•高可靠性。即使其中一个处理机发生故障，其余的处理机仍能够继续工作，较好地完成用户规定的任务。•高度并行性。在单处理机系统中，我们利用多道程序设计技术来实现多个进程或线程的并发运行，各个进程或线程实际上只能分时地使用处理机。而在多处理机系统中，实际存在多个物理处理机，并发中的进程或线程可以在物理上就并行地运行，大大提高系统的处理能力。•提高系统的处理能力和吞吐量处理机调度制作者：凤羽翚10-17操作系统OperatingSystem10.4多处理机调度•10.4.1多处理机系统简介–多处理机系统的分类•按共享内存的耦合度分类–紧耦合系统。多个处理机具有共享公共存储器的系统，在这样的系统中，处理机之间通过公用存储器进行通信。–松耦合系统。每个处理机具有自己专用的存储器的系统，在这种系统中，处理机之间的通信往往通过专用线路或网络进行的。目前应用较广的SMP对称多处理器系统采用的就是一个统一的共享内存空间，属于紧耦合系统。•按处理机在系统中