《处理器管理》

1、.第第2章章 处理器管理处理器管理 主讲：周文强主讲：周文强 课程：操作系统课程：操作系统.本章内容：本章内容：2.4 进程同步机制进程同步机制2.5 进程通信进程通信2.6 处理机调度处理机调度.2.4 进程同步机制 操作系统中引入操作系统中引入进程进程后，虽然改善了资源后，虽然改善了资源的利用率，提高了系统的吞吐量。的利用率，提高了系统的吞吐量。 但是，由于进程的但是，由于进程的异步性异步性，也会给系统造，也会给系统造成混乱。因此，必须有效地成混乱。因此，必须有效地协调协调各个各个并发并发进程间的关系进程间的关系，从而使它们能正确的执行。，从而使它们能正确的执行。 本节主要介绍进程的同步与

2、互斥的实现机本节主要介绍进程的同步与互斥的实现机制。制。.2.4.1 进程的并发性 在并发运行的系统中，在并发运行的系统中，若干个作业若干个作业可以同可以同时运行，而时运行，而每个作业每个作业又需要有又需要有多个进程多个进程协协作完成。在这些同时存在的进程间具有作完成。在这些同时存在的进程间具有并并发性发性，称之为，称之为“并发进程并发进程”。 进程间的关系可以分为：进程间的关系可以分为：1、资源共享关系、资源共享关系2、相互合作关系、相互合作关系.1、资源共享关系 系统中的系统中的某些进程某些进程需要访问需要访问共同的资源共同的资源，即当即当一个进程一个进程访问共享资源时，访问该共访问共享资

3、源时，访问该共享资源的享资源的其他进程其他进程必须等待，当这个进程必须等待，当这个进程使用完后，其他进程才能使用。这时要求使用完后，其他进程才能使用。这时要求进程应进程应互斥地互斥地访问共享资源。访问共享资源。.2、相互合作关系 系统中的系统中的某些进程某些进程之间存在之间存在相互合作的关相互合作的关系系，即，即一个进程一个进程执行完后，执行完后，另一个进程另一个进程才才能开始。否则，另一个进程不能开始，这能开始。否则，另一个进程不能开始，这时就要保证相互合作的进程在执行次序上时就要保证相互合作的进程在执行次序上要同步。要同步。.1、临界资源 通常一次通常一次仅仅允许允许一个进程一个进程使用的

4、资源使用的资源称为称为临界资源临界资源，同时，也将一个进程，同时，也将一个进程访问的这种临界资源的那段访问的这种临界资源的那段程序代码程序代码称为称为临界区临界区。 操作系统中的操作系统中的进程就绪队列进程就绪队列就是一种就是一种在一个时刻只能允许一个进程访问的在一个时刻只能允许一个进程访问的临界资源临界资源。所以，进程的互斥就是两。所以，进程的互斥就是两个进程不能同时进入访问同一临界资个进程不能同时进入访问同一临界资源的临界区。源的临界区。.2、临界区(critical section) 临界区是进程执行程序中的对临界区是进程执行程序中的对临界资源临界资源访访问的那问的那一段程序一段程序，这

5、段程序的进入执行，这段程序的进入执行，需要有一定的原则来协调。需要有一定的原则来协调。 例如：例如： 1、有若干进程都欲进入临界区，它们不能、有若干进程都欲进入临界区，它们不能互相阻塞，使得谁也进不了临界区，应当互相阻塞，使得谁也进不了临界区，应当在在有限时间内有限时间内让一个进程进入临界区。让一个进程进入临界区。 2、每次、每次至多有一个进程至多有一个进程进入临界区，并且进入临界区，并且在临界区中只能停留在临界区中只能停留有限的时间有限的时间。.3、进程同步、进程同步 多个相关进程多个相关进程在执行次序上的协调，这些进在执行次序上的协调，这些进程相互合作，在一些程相互合作，在一些关键点关键点

6、上需要上需要相互等待相互等待或或相互通信相互通信。 通过通过临界区临界区可以协调进程间相互合作的关系，可以协调进程间相互合作的关系，这就是进程同步这就是进程同步.4、进程互斥、进程互斥 当当一个进程一个进程进入进入临界区临界区使用临界资源时，使用临界资源时，另一个进程另一个进程必须等待。当占用临界资源的必须等待。当占用临界资源的进程退出临界区后，另一个进程才被允许进程退出临界区后，另一个进程才被允许使用临界资源。使用临界资源。 通过通过临界区临界区协调进程间资源共享的关系，协调进程间资源共享的关系，就是进程互斥。就是进程互斥。.2.4.3 进程同步机制应遵循的原则进程同步机制应遵循的原则 (1

7、)空闲让进空闲让进。当无进程处于临界区时，。当无进程处于临界区时，允许一个进程进入。允许一个进程进入。 (2)忙则等待忙则等待。当有进程在临界区中，。当有进程在临界区中，其他欲进入临界区的进程必须等待。其他欲进入临界区的进程必须等待。 (3)有限等待有限等待。对要求进入临界区的进。对要求进入临界区的进程，应在有限时间内让其进入，避免程，应在有限时间内让其进入，避免“死等死等”。 (4)让权等待让权等待。临界区让出，必须立即。临界区让出，必须立即释放处理器，让等待进程进入，避免释放处理器，让等待进程进入，避免“忙等忙等”。.12n锁操作：锁操作：1.测试锁位的值；测试锁位的值；lock/unlo

8、ck2.若原来的值是为若原来的值是为“0”，将锁位置为，将锁位置为“1”（占用该（占用该资源）；资源）；3.若原来值是为若原来值是为“1”，（该资源已被别人占用），（该资源已被别人占用），则转到则转到1。n开锁操作：开锁操作：进程使用完资源后，将锁位置为进程使用完资源后，将锁位置为“0”，称为开锁操，称为开锁操作作。2.4.4 进程同步机制锁.13.锁操作的缺点14.18.20.放水果问题有一个水果盘，只能放入1个水果。父亲每次放1个苹果供儿子吃，或者放1个橘子供女儿吃。给出父亲、儿子、女儿的算法描述。.放水果问题需要三个信号量s1,s2,s3分别代表需要盘子是否为空，是否可以有苹果，是否橘子

9、。父亲进程：父亲进程：A:P（s1 ）if 放苹果放苹果 then V(s2)else V(s3) goto As1 = 1， s2 = 0， s2 = 0.放水果问题儿子进程：B:P(s2) 取走苹果V（s1）goto B女儿进程女儿进程C:P(s3) 取走苹果取走苹果V（s1）goto C.PAPpbufferdeposit(data)remove(data)例例 进程进程PA和和PB共享缓冲队列发送和接收共享缓冲队列发送和接收数据。数据。.26在在PA至少送一块数据入一个缓冲区之前，至少送一块数据入一个缓冲区之前，PB不可能从缓冲区中取出数据不可能从缓冲区中取出数据(假定数据块假定数据块

10、长等于缓冲区长度长等于缓冲区长度)；PA往缓冲队列发送数据时，至少有一个缓往缓冲队列发送数据时，至少有一个缓冲区是空的；冲区是空的；由由PA发送的数据块在缓冲队列中按先进先发送的数据块在缓冲队列中按先进先出方式排列。出方式排列。.2.4.8 利用信号量实现进程同步与互斥利用信号量实现进程同步与互斥. 每个进程中各个每个进程中各个P操作的次序是重要的操作的次序是重要的：先检查资源数目，再：先检查资源数目，再检查是否互斥检查是否互斥否则可能死锁！否则可能死锁！.Consumer：Producer：P(avail);P(mutex); one unit-buf;V(mutex);V(full);P(

11、full);P(mutex);/进入区进入区 one unit-buf;V(mutex);V(avail);/退出区退出区分析：分析：当当full=0, mutex = 1时，执行顺序：时，执行顺序： / C阻塞，等待阻塞，等待Producer 发出的发出的full信号信号 / P 阻塞，等待阻塞，等待Consumer发出的发出的avail信号信号.2.4.9 利用信号量实现进程同步的方法1、使用、使用PV操作的规则操作的规则（1）分清哪些是互斥问题，哪些是同步问题）分清哪些是互斥问题，哪些是同步问题（2）对于互斥问题要设置互斥信号量，不管有互）对于互斥问题要设置互斥信号量，不管有互斥关系的进

12、程有几个或几类，互斥信号量的个数斥关系的进程有几个或几类，互斥信号量的个数只与临界资源的种类有关只与临界资源的种类有关（3）对于同步问题要设置同步信号量，通常同步）对于同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关信号量的个数与参与同步的进程种类有关（4）在每个进程中由于实现互斥的）在每个进程中由于实现互斥的PV操作必须成操作必须成对出现；用于实现同步的对出现；用于实现同步的PV操作也必须成对出现操作也必须成对出现。必须先执行对同步信号量的。必须先执行对同步信号量的P操作，再执行对操作，再执行对互斥信号量的互斥信号量的P操作。操作。.2、同步互斥问题的解题步骤（1）确定

13、进程。包括进程的数量、进程的工）确定进程。包括进程的数量、进程的工作内容，可以用流程图描述作内容，可以用流程图描述（2）确定同步互斥关系。根据使用的是临界）确定同步互斥关系。根据使用的是临界资源，还是处理的前后关系，来确定互斥资源，还是处理的前后关系，来确定互斥与同步，然后确定信号的个数、含义，以与同步，然后确定信号的个数、含义，以及对信号量的及对信号量的PV操作操作（3）用）用C语言描述同步或互斥算法语言描述同步或互斥算法.2.5 进程通信 进程通信是指进程通信是指进程间进程间的信息交换。进程通的信息交换。进程通信所交换的信息量少则一个数值或状态，信所交换的信息量少则一个数值或状态，多则成千

14、上万个字节。多则成千上万个字节。 根据通信的机制不同将进程通信分为根据通信的机制不同将进程通信分为低级低级通信通信和和高级通信高级通信。.低级通信-进程的同步和互斥进程的同步和互斥称为低级通信。进程的同步和互斥称为低级通信。缺点：缺点：1、效率低，一次发送的信息量比较少。、效率低，一次发送的信息量比较少。2、信号量机制主要依靠进程来控制，用户使、信号量机制主要依靠进程来控制，用户使用不方便。用不方便。.高级通信 高级通信是指用户直接利用操作系统提供高级通信是指用户直接利用操作系统提供的一组通信命令，高效地传送大量数据的的一组通信命令，高效地传送大量数据的一种通信方式。一种通信方式。高级通信机制

15、分为高级通信机制分为3大类：大类：1、共享存储器系统、共享存储器系统2、消息传递系统、消息传递系统3、管道通信系统、管道通信系统.2.5.1 共享存储器系统 在共享存储器系统中，相互通信的进程共在共享存储器系统中，相互通信的进程共享某些数据结构或存储区，进程之间能够享某些数据结构或存储区，进程之间能够通过它们进程通信。通过它们进程通信。共享存储器系统分为共享存储器系统分为2种方式：种方式：1、共享数据结构方式、共享数据结构方式2、共享存储区方式、共享存储区方式.1、共享数据结构方式 在这种通信方式下，相互通信的进程共用某在这种通信方式下，相互通信的进程共用某些数据结构，并通过这些数据结构交换信

16、息。些数据结构，并通过这些数据结构交换信息。这种方式与信号量机制相比，并没有发生太这种方式与信号量机制相比，并没有发生太大的变化，比较低效、复杂，只适合于传送大的变化，比较低效、复杂，只适合于传送少量的数据。少量的数据。.2、共享存储区方式 这种通信方式是在存储器中划出一块共享存这种通信方式是在存储器中划出一块共享存储区，相互通信的进程可以通过对共享存储储区，相互通信的进程可以通过对共享存储区中的数据进行读或写来实现通信。这种方区中的数据进行读或写来实现通信。这种方式效率高，可以传送较多的数据。式效率高，可以传送较多的数据。.2.5.2 消息传递系统 在消息传递信息中，进程间的数据交换是以在消

17、息传递信息中，进程间的数据交换是以消息为单位进行的。用户直接利用系统中提消息为单位进行的。用户直接利用系统中提供的一组通信命令（原语）进程通信。消息供的一组通信命令（原语）进程通信。消息传递系统成为最常用的高级通信方式。传递系统成为最常用的高级通信方式。优点：优点：1、工作效率提高、工作效率提高2、简化了程序编制的复杂性，方便用户的使、简化了程序编制的复杂性，方便用户的使用。用。.1、直接通信方式 发送进程使用发送原语直接将消息发送给接收进发送进程使用发送原语直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接程，并将它挂在接收进程的消息缓冲队列上。接收接收进程使用接收原语从消息缓

18、冲队列中读取收接收进程使用接收原语从消息缓冲队列中读取消息。通常系统提供两条通信原语。消息。通常系统提供两条通信原语。发送原语：发送原语：Send（Receiver，message）；）；接收原语：接收原语：Receive（Sender，message）；）；例如原语例如原语Send（P2，M）表示将消息）表示将消息M发送给接收发送给接收进程进程P2；而原语；而原语Receive（P1，M）则是表示接）则是表示接收由进程收由进程P1发送来的消息发送来的消息M。.2、间接通信方式 发送进程与接收进程通过中间实体发送进程与接收进程通过中间实体信箱信箱来完成通信，既可以实现实时通信，有可来完成通信，

19、既可以实现实时通信，有可以实现非实时通信。以实现非实时通信。 接收进程使用接收原语从信箱中取出消息。接收进程使用接收原语从信箱中取出消息。.（1）信箱通信的操作 系统为信箱通信提供了若干条操作原语，系统为信箱通信提供了若干条操作原语，包括创建信箱原语、撤销信箱原语、发送包括创建信箱原语、撤销信箱原语、发送原语、接收原语等。原语、接收原语等。 1、信箱的创建与撤销。、信箱的创建与撤销。 进程可以利用信箱创建原语来建立一个新进程可以利用信箱创建原语来建立一个新信箱。创建进程应给出信箱的名字、信箱信箱。创建进程应给出信箱的名字、信箱属性等。当信箱所属进程不再需要该信箱属性等。当信箱所属进程不再需要该

20、信箱时，可用信箱撤销原语来撤销信箱。时，可用信箱撤销原语来撤销信箱。.2、消息的发送与接收。相互通信的进程利用、消息的发送与接收。相互通信的进程利用系统提供的下述通信原语来实现消息的发系统提供的下述通信原语来实现消息的发送与接收。送与接收。Send（mailbox，message）：将一个消息）：将一个消息发送到指定信箱发送到指定信箱Receive（mailbox，message）：从指定）：从指定信箱中接收一个消息信箱中接收一个消息.（2）消息的分类 消息可以由操作系统创建，也可以由用户消息可以由操作系统创建，也可以由用户创建。创建者是信箱的拥有者，信箱可以创建。创建者是信箱的拥有者，信箱可

21、以分为分为3类：类： 1、私用信箱。用户进程可以为自己建立一、私用信箱。用户进程可以为自己建立一个新信箱，并作为进程的一部分信箱的拥个新信箱，并作为进程的一部分信箱的拥有者有权从信箱中读取信息，其他用户只有者有权从信箱中读取信息，其他用户只能将自己的消息发送到该信箱中。当拥有能将自己的消息发送到该信箱中。当拥有该信箱的进程终止时，信箱也随之消失。该信箱的进程终止时，信箱也随之消失。. 2、公用信箱。它由操作系统创建，并提供、公用信箱。它由操作系统创建，并提供给系统中所有核准的用户进程使用。核准给系统中所有核准的用户进程使用。核准的进程既可以把消息发送到该信箱，有可的进程既可以把消息发送到该信箱

22、，有可以从信箱中取出发送给本人的消息。通常，以从信箱中取出发送给本人的消息。通常，公用信箱在系统运行期间始终存在。公用信箱在系统运行期间始终存在。. 3、共享信箱。它实际上是某种进程创建的、共享信箱。它实际上是某种进程创建的私有信箱。在创建时或创建后，又指明它私有信箱。在创建时或创建后，又指明它是可以共享的，同时指出共享进程（用户）是可以共享的，同时指出共享进程（用户）的名字，此时就成为共享信箱。信箱的拥的名字，此时就成为共享信箱。信箱的拥有者和共享者，都有权从信箱中取走发送有者和共享者，都有权从信箱中取走发送给本人的消息。给本人的消息。.（3）通信进程间的关系 当利用信箱通信时，发送进程与接

23、收进程存在下列关系：当利用信箱通信时，发送进程与接收进程存在下列关系： 1、一对一关系。在一个发送进程和一个接收进程之间建、一对一关系。在一个发送进程和一个接收进程之间建立一条专用的通信通道，使它们之间的通信不受其他进立一条专用的通信通道，使它们之间的通信不受其他进程的影响。程的影响。 2、多对一关系。允许提供服务的一个接收进程与多个用、多对一关系。允许提供服务的一个接收进程与多个用户发送进程之间进行通信，也称为客户户发送进程之间进行通信，也称为客户/服务器方式。服务器方式。 3、一对多关系，允许一个发送进程与多个接收进程进行、一对多关系，允许一个发送进程与多个接收进程进行通信，使发送进程可以

24、用广播形式，向一组或全部接收通信，使发送进程可以用广播形式，向一组或全部接收者发送消息。者发送消息。 4、多对多关系。允许建立一个公用信箱，让多个进程既、多对多关系。允许建立一个公用信箱，让多个进程既可以把消息发送到该信箱，又可以从信箱中取出发送给可以把消息发送到该信箱，又可以从信箱中取出发送给本人的消息。本人的消息。.2.5.3 管道通信系统管道通信系统 管道管道是指连接读进程和写进程的，用于实是指连接读进程和写进程的，用于实现它们之间通信的共享文件。向管道提供现它们之间通信的共享文件。向管道提供输入的输入的发送进程发送进程（写进程写进程），以字符流的），以字符流的形式间大量数据送入管道，而

25、接收管道输形式间大量数据送入管道，而接收管道输出的出的接收进程接收进程（读进程读进程），可以从管道中），可以从管道中接收数据。由于发送进程和接收进程是利接收数据。由于发送进程和接收进程是利用管道进行通信的，故称为用管道进行通信的，故称为管道通信方式管道通信方式。.2.6 处理机调度处理机调度 一个作业从提交开始直到完成，往往要经历一个作业从提交开始直到完成，往往要经历三级调度，即三级调度，即作业调度作业调度（高级调度）、（高级调度）、进程进程调度调度（低级调度）和（低级调度）和中级调度中级调度。1、作业调度作业调度是从后备作业队列中选择出若干是从后备作业队列中选择出若干个作业，为它们分配必要的

26、资源，将它们调个作业，为它们分配必要的资源，将它们调入主存，为它们建立进程，使之成为就绪进入主存，为它们建立进程，使之成为就绪进程。程。2、进程调度进程调度是从主存就绪队列上选择哪个进是从主存就绪队列上选择哪个进程获得处理器资源，让进程运行。程获得处理器资源，让进程运行。.56功功 能：能：按照一定按照一定调度算法从就绪调度算法从就绪队列中选择一个队列中选择一个新的进程投入运新的进程投入运行。行。入口信息：入口信息：可省可省 入口（就绪队列指针） 调度算法选择 将选中进程从就绪队列取出 运行 修改选中进程的 PCB： 状态=运行态 就绪队列 就绪队列 运行态 进程调度进程调度.2.6.1 进程

27、调度算法的选取原则进程调度算法的选取原则 选择调度算法的原则有面向用户的，也有选择调度算法的原则有面向用户的，也有面向系统的。面向系统的。1、面向用户的原则、面向用户的原则（1）周转时间短）周转时间短（2）相应时间快）相应时间快（3）截止时间有保证）截止时间有保证（4）优先权原则）优先权原则.计算公式计算公式周转时间周转时间=完成时间完成时间-到达时间到达时间平均周转时间平均周转时间=每个进程的周转时间之和每个进程的周转时间之和/进进程个数程个数带权周转时间带权周转时间=进程的周转时间进程的周转时间/系统为进程系统为进程提供的实际服务时间提供的实际服务时间平均带权周转时间平均带权周转时间=所有

28、进程的带权周转世所有进程的带权周转世间之和间之和/进程个数进程个数.2、面向系统的原则、面向系统的原则（1）系统吞吐量高）系统吞吐量高（2）处理器利用率高）处理器利用率高（3）各类资源的平衡利用）各类资源的平衡利用.2.6.2 常用的进程调度算法常用的进程调度算法 算法选择的合理性，将决定进程调度的优劣算法选择的合理性，将决定进程调度的优劣，它要解决两个问题：，它要解决两个问题： 第一第一选择哪个进程执行进程调度；选择哪个进程执行进程调度； 第二第二个选中某个进程，如何给它分配处理器个选中某个进程，如何给它分配处理器，该进程能占用处理器多久。，该进程能占用处理器多久。 第一个问题是选择第一个问

29、题是选择进程调度算法进程调度算法，第二个问，第二个问题是选择题是选择进程的调度方式进程的调度方式。.1先来先服务调度算法先来先服务调度算法 FCFS按照进程进入就绪队列的先后顺序按照进程进入就绪队列的先后顺序选择可以占用处理器的进程。这是一种不选择可以占用处理器的进程。这是一种不可抢占方式的调度算法。可抢占方式的调度算法。 优点：实现简单，优点：实现简单， 缺点：后来的进程等待缺点：后来的进程等待CPU的时间较长。的时间较长。.2短执行进程优先算法短执行进程优先算法 SPF就是从就是从就绪队列就绪队列中选择一个中选择一个CPU执行执行时间预期最短的进程，将处理器分配给它时间预期最短的进程，将处

30、理器分配给它。 优点：较公平优点：较公平 缺点：实现难度较大，因为要准确预定下缺点：实现难度较大，因为要准确预定下一个进程的一个进程的CPU执行周期是很困难的。执行周期是很困难的。.3.最短剩余时间优先调度算法 SRT是将是将CPU分配给分配给需要最少时间需要最少时间来来完成的进程。完成的进程。SRT充分照顾了剩余运行时充分照顾了剩余运行时间短的进程。间短的进程。 .4时间片轮转法时间片轮转法 RR让每个进程在让每个进程在就绪队列就绪队列中的中的等待时间等待时间与与享受享受服务的时间服务的时间成比例。成比例。 在在RR中，需要将中，需要将CPU的处理时间分成固定大的处理时间分成固定大小的时间片

31、。如果小的时间片。如果一个进程一个进程在被调度选中之后在被调度选中之后用完了用完了系统规定的时间片，但又系统规定的时间片，但又未完成未完成要求的要求的任务，则它自行释放自己所占有的任务，则它自行释放自己所占有的CPU而排到而排到就绪队列的末尾，等待下一次调度。就绪队列的末尾，等待下一次调度。 同时，进程调度程序又去调度当前就绪队列中同时，进程调度程序又去调度当前就绪队列中的第一个进程。的第一个进程。.5优先权调度算法优先权调度算法 HPF的核心是确定进程的优先级。的核心是确定进程的优先级。 确定优先级的方法可分为静态法和动态法。确定优先级的方法可分为静态法和动态法。静态法静态法根据进程的静态特

32、性，在进程开始执根据进程的静态特性，在进程开始执行之前就确定它们的优先级，一旦开始执行行之前就确定它们的优先级，一旦开始执行之后就不能改变。之后就不能改变。 动态法动态法把进程的静态特性和动态特性结合起把进程的静态特性和动态特性结合起来确定进程的优先级，随着进程的执行过程来确定进程的优先级，随着进程的执行过程，其优先级不断变化。，其优先级不断变化。 .基于基于静态优先级静态优先级的调度算法的调度算法 优点：优点：实现简单，系统开销小实现简单，系统开销小 缺点：静态优先级一旦确定之后，直缺点：静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系到执行结束为止始终保持不变，从而系统效率较低

33、，调度性能不高。统效率较低，调度性能不高。 现在的操作系统中，大多采用动态优现在的操作系统中，大多采用动态优先级的调度策略。先级的调度策略。.基于基于动态优先级动态优先级的调度算法的调度算法 (1)根据根据进程占有进程占有CPU时间的长短时间的长短来决来决定。一个进程定。一个进程占有处理机的时间愈长占有处理机的时间愈长，则在被阻塞之后再次获得调度的优，则在被阻塞之后再次获得调度的优先级就越低。反之，其获得调度的可先级就越低。反之，其获得调度的可能性就会越大。能性就会越大。 (2)根据根据就绪进程等待就绪进程等待CPU的时间长短的时间长短来决定。一个来决定。一个就绪进程在就绪队列中就绪进程在就绪

34、队列中等待的时间越长等待的时间越长，则它获得调度选中，则它获得调度选中的优先级就越高。的优先级就越高。.2.6.3 作业调度作业调度 作业作业是指用户在一次计算过程或者事务处理是指用户在一次计算过程或者事务处理过程中，要求计算机系统所作工作的集合。过程中，要求计算机系统所作工作的集合。 作业调度作业调度是从是从后备作业队列后备作业队列中选择若干个中选择若干个作作业业，为它们分配必要的资源，将它们调入，为它们分配必要的资源，将它们调入主主存存，为它们，为它们建立进程建立进程，使它们成为，使它们成为就绪进程就绪进程的过程。这涉及到作业所处的的过程。这涉及到作业所处的状态状态、作业调作业调度度以及以

35、及调度算法调度算法。.1、作业调度采用的数据结构、作业调度采用的数据结构 为了管理和调度作业，系统为每个作业设为了管理和调度作业，系统为每个作业设置一个置一个作业控制块（作业控制块（JCB）。）。 JCB 是在作业进入系统时由是在作业进入系统时由SPOOLING系系统统为其建立的。其内容由为其建立的。其内容由作业控制卡作业控制卡（说（说明书）中得到的。明书）中得到的。JCB是作业存在系统的是作业存在系统的标志，作业进入系统时，则为之标志，作业进入系统时，则为之建立建立JCB，当作业退出时，则其，当作业退出时，则其JCB也被撤销也被撤销。.作业名资源要求资源使用情况类型级别优 先 级状 态要求的

36、运行时间、使用语言最迟完成时间、要求的主存量要求外设类型、台数要求的文件量和输出量进入系统时间开始运行时间已运行时间主存地址外设台号控制方式 作业类型优先数作业控制表作业控制表JCB.SPOOLING系统系统 SPOOLING又称为又称为外围设备同时联机操作外围设备同时联机操作。在在SPOOLING系统中，多台系统中，多台外围设备外围设备通过通过通通道道或或DMA器件器件和和主机与外存主机与外存连接起来。在硬连接起来。在硬盘中开辟一块输入盘中开辟一块输入/输出井，并将多个用户作输出井，并将多个用户作业随机的存储提取，各用户间互不干扰。业随机的存储提取，各用户间互不干扰。 系统中的输入程序包含两

37、个独立的过程，一系统中的输入程序包含两个独立的过程，一个过程负责从外部设备把信息个过程负责从外部设备把信息读入缓冲区读入缓冲区；另一个是另一个是写过程写过程，负责把缓冲区的信息送到，负责把缓冲区的信息送到外存输入井外存输入井中。中。.2、作业调度与进程调度的关系、作业调度与进程调度的关系作业调度与进程调度的关系作业调度与进程调度的关系用户作业录入提交收容完成运行就绪阻塞等待I/OI/O完成进程调度作业调度执行作业调度.3、常用的作业调度算法、常用的作业调度算法 作业调度程序要完成以下工作：作业调度程序要完成以下工作：(1) 按照某种调度算法从后备作业队列中挑选作业按照某种调度算法从后备作业队列

38、中挑选作业(2) 为选中的作业分配主存和外设资源。为选中的作业分配主存和外设资源。(3) 为选中的作业建立相应的进程。为选中的作业建立相应的进程。(4) 构造和填写作业运行时所需的有关表格。构造和填写作业运行时所需的有关表格。(5) 作业结束时完成该作业的善后处理工作，如收作业结束时完成该作业的善后处理工作，如收回资源，输出必要的信息，撤消该作业的全部进回资源，输出必要的信息，撤消该作业的全部进程程 (PCB) 和作业控制块和作业控制块 JCB。. 调度原则：调度原则：公平，合理，使用户满意公平，合理，使用户满意提高系统资源利用率，如提高系统吞吐量提高系统资源利用率，如提高系统吞吐量 作业调度

39、算法的评价因素作业调度算法的评价因素作业作业吞吐量吞吐量：运行尽可能多的作业；：运行尽可能多的作业；充分充分利用资源利用资源：CPU忙、忙、I/O设备忙；设备忙；对各作业对各作业公平、合理公平、合理，使用户，使用户满意满意：执行时间长短、：执行时间长短、等待时间等；等待时间等；（1）选择作业调度算法应考虑的因素）选择作业调度算法应考虑的因素.（2）常用的作业调度算法）常用的作业调度算法 FCFS按作业到达系统的先后次序进按作业到达系统的先后次序进行调度。该算法优先考虑在系统中等行调度。该算法优先考虑在系统中等待时间最长的作业，而不考虑作业运待时间最长的作业，而不考虑作业运行时间的长短。行时间的

40、长短。 1.先来先服务调度算法先来先服务调度算法 .先来先服务调度算法先来先服务调度算法由此：此作业流的平均周转时间为由此：此作业流的平均周转时间为T (2.0+1.5+1.2+1.5)/4=1.55h，此作业流的平均周转时间为此作业流的平均周转时间为W (1.0+3.0+6.0+3.75)/4=3.4375h注：通过以上分析，显然，这种算法容易实现，但效率很注：通过以上分析，显然，这种算法容易实现，但效率很低。低。 .2.短作业优先调度算法短作业优先调度算法 SJF 总是从作业的后备队列中挑选运总是从作业的后备队列中挑选运行时间最短的作业，作为下行时间最短的作业，作为下个调度个调度运行的对象

41、。运行的对象。.短作业优先调度算法短作业优先调度算法由此：此作业流的平均周转时间为由此：此作业流的平均周转时间为T (2.0+2.1+0.7+1.0)/4=1.45h，此作业流的平均周转时间为此作业流的平均周转时间为W (1.0+4.2+3.5+2.5)/4=2.8h注：通过以上分析，虽然这种算法易于实现，且效率也注：通过以上分析，虽然这种算法易于实现，且效率也比较高，但未考虑长作业的利益。比较高，但未考虑长作业的利益。.FCFS和SPF存在的问题 先来先服务调度算法只考虑了作业的等待先来先服务调度算法只考虑了作业的等待时间，而忽略了作业的运行时间，对短作时间，而忽略了作业的运行时间，对短作业

42、不利；业不利； 短作业优先调度算法只考虑了作业运行时短作业优先调度算法只考虑了作业运行时间的长短，而忽略了作业的等待时间，对间的长短，而忽略了作业的等待时间，对运行时间长的作业不利，因为如果始终有运行时间长的作业不利，因为如果始终有短作业进入系统，则较长作业会长时间得短作业进入系统，则较长作业会长时间得不到调度。不到调度。.3.响应比高者优先调度算法响应比高者优先调度算法 HRRN是在每次调度作业运行时，先计是在每次调度作业运行时，先计算后备作业队列中每个作业的算后备作业队列中每个作业的响应比响应比，然后挑选响应比最高者投入运行。然后挑选响应比最高者投入运行。 HRRN既考虑了作业的等待时间又

43、考既考虑了作业的等待时间又考虑了作业的运行时间的调度算法，虑了作业的运行时间的调度算法， .响应比高者优先调度算法响应比高者优先调度算法 R作业的响应时间作业的响应时间作业的运行时间作业的运行时间 作业的响应时间作业的响应时间作业的等待时间作业作业的等待时间作业的运行时间的运行时间 作业的响应比为作业的响应比为：R1作业的等待时间作业的等待时间作业的运行时间。作业的运行时间。 一个作业的响应比随着一个作业的响应比随着等待时间等待时间的增加而的增加而提高。在提高。在相同等待时间相同等待时间的情况下，的情况下，短作业短作业优先优先，而对于，而对于相同运行时间相同运行时间的作业，的作业，等待等待时间

44、长的作业优先运行时间长的作业优先运行。.响应比高者优先调度算法响应比高者优先调度算法. 由于作业由于作业1的开始时间是的开始时间是5：00，而其余作，而其余作业均未到达，故先运行作业业均未到达，故先运行作业1。当作业。当作业1运运行完毕，计算后备队列中作业行完毕，计算后备队列中作业2，3，4的响的响应比。按照以上的定义和计算公式，计算应比。按照以上的定义和计算公式，计算如下：如下： 作业作业2:R=(60+30)/30=3 作业作业3:R=(30+12)/12=3.5 作业作业4:R=(24+24)/24=2. 可见，作业可见，作业3的响应比最高，选择作业的响应比最高，选择作业3运行，故运行，故表表2-3中作业中作业3的开始时间为作业的开始时间为作业1的完成时间，的完成时间，即即7:00，当作业，当作业3运行完毕，计算后备队列