《处理器管理》PPT课件.ppt

第2章 处理器管理,主讲：周文强 课程：操作系统,本章内容：,2.4 进程同步机制2.5 进程通信2.6 处理机调度,2.4 进程同步机制,操作系统中引入进程后，虽然改善了资源的利用率，提高了系统的吞吐量。但是，由于进程的异步性，也会给系统造成混乱。因此，必须有效地协调各个并发进程间的关系，从而使它们能正确的执行。本节主要介绍进程的同步与互斥的实现机制。,2.4.1 进程的并发性,在并发运行的系统中，若干个作业可以同时运行，而每个作业又需要有多个进程协作完成。在这些同时存在的进程间具有并发性，称之为“并发进程”。进程间的关系可以分为：1、资源共享关系2、相互合作关系,1、资源共享关系,系统中的某些进程需要访问共同的资源，即当一个进程访问共享资源时，访问该共享资源的其他进程必须等待，当这个进程使用完后，其他进程才能使用。这时要求进程应互斥地访问共享资源。,2、相互合作关系,系统中的某些进程之间存在相互合作的关系，即一个进程执行完后，另一个进程才能开始。否则，另一个进程不能开始，这时就要保证相互合作的进程在执行次序上要同步。,1、临界资源,通常一次仅允许一个进程使用的资源称为临界资源，同时，也将一个进程访问的这种临界资源的那段程序代码称为临界区。操作系统中的进程就绪队列就是一种在一个时刻只能允许一个进程访问的临界资源。所以，进程的互斥就是两个进程不能同时进入访问同一临界资源的临界区。,2、临界区(critical section),临界区是进程执行程序中的对临界资源访问的那一段程序，这段程序的进入执行，需要有一定的原则来协调。例如：1、有若干进程都欲进入临界区，它们不能互相阻塞，使得谁也进不了临界区，应当在有限时间内让一个进程进入临界区。2、每次至多有一个进程进入临界区，并且在临界区中只能停留有限的时间。,3、进程同步,多个相关进程在执行次序上的协调，这些进程相互合作，在一些关键点上需要相互等待或相互通信。通过临界区可以协调进程间相互合作的关系，这就是进程同步,4、进程互斥,当一个进程进入临界区使用临界资源时，另一个进程必须等待。当占用临界资源的进程退出临界区后，另一个进程才被允许使用临界资源。通过临界区协调进程间资源共享的关系，就是进程互斥。,2.4.3 进程同步机制应遵循的原则,(1)空闲让进。当无进程处于临界区时，允许一个进程进入。(2)忙则等待。当有进程在临界区中，其他欲进入临界区的进程必须等待。(3)有限等待。对要求进入临界区的进程，应在有限时间内让其进入，避免“死等”。(4)让权等待。临界区让出，必须立即释放处理器，让等待进程进入，避免“忙等”。,12,锁操作：1.测试锁位的值；lock/unlock2.若原来的值是为“0”，将锁位置为“1”（占用该资源）；3.若原来值是为“1”，（该资源已被别人占用），则转到1。开锁操作：进程使用完资源后，将锁位置为“0”，称为开锁操作。,2.4.4 进程同步机制锁,13,PAA:lock(keyS)unlock(keyS)Goto A可能导致不公平现象,PBB:lock(keyS)unlock(keyS)Goto B,锁操作的缺点,14,1、循环测定锁定位，将损耗较多的CPU时间。2、影响系统可靠性和执行效率，并可能导致不公平现象。,2.4.5 进程同步机制-信号量,信号量是一种特殊变量，他用来表示系统中资源的使用情况。而整型信号量就是一个整型变量。当值大于0时，表示系统中对应可用资源的数目；当值小于0时，其绝对值表示因该类资源而被等待的进程数目；当值等于0时，表示系统中对应资源已经用完，并且没有因该类资源而被等待的进程。,P,V原语,信号量的初值只能由P,V原语操做P:passeren V:verhoogP操作：申请资源操作sem减1若sem减1后仍大于1或等于零，则P返回，进程继续；若sem减1后小于零，则该进程阻塞转等待队列中。,V操作：释放资源操作,sem加1若sem加1后结果大于1，则V停止操作，该进程返回调用处，继续执行；若sem加1后小于或等于零，则该进程转就绪队列，同时进程调试选取一个等待队列中的进程转运行。P,V操作必须用原语实现。,18,用信号量实现两并发进程PA，PB互斥的描述如下：设sem为互斥信号量，其取值范围为(1,0,-1)其中sem=1表示进程PA和PB都未进入S的临界区，sem=0表示进程PA或PB已进入S的临界区，sem=-1进程PA和PB中，一个进程已进入临界区，另一进程等待进入。描述:PA:PB:P(sem)P(sem)V(sem)V(sem),2.4.6 用P,V原语实现进程互斥,sem=1,进程A想使用临界区,进程A执行P操作,sem=0,进程B执行P操作,进程B想使用临界区,sem=-1,进程B被阻塞,进程A使用临界区完,进程A执行V操作,sem=0,进程B转入阻塞队列中,20,PAA:P(sem)V(sem)Goto A会导致不公平现象吗？,PBB:P(sem)V(sem)Goto B,放水果问题,有一个水果盘，只能放入1个水果。父亲每次放1个苹果供儿子吃，或者放1个橘子供女儿吃。给出父亲、儿子、女儿的算法描述。,放水果问题,需要三个信号量s1,s2,s3分别代表需要盘子是否为空，是否可以有苹果，是否橘子。,父亲进程：A:P（s1）if 放苹果 then V(s2)else V(s3)goto A,s1=1，s2=0，s2=0,放水果问题,儿子进程：B:P(s2)取走苹果V（s1）goto B,女儿进程C:P(s3)取走苹果V（s1）goto C,用P,V原语操作实现进程同步的方法：为各并发进程设置私用信号量为私用信号量赋初值利用P,V原语和私用信号量规定各进程的执行顺序。,2.4.7 用P,V原语操作实现同步,PA,Pp,buffer,deposit(data),remove(data),例 进程PA和PB共享缓冲队列发送和接收数据。,26,在PA至少送一块数据入一个缓冲区之前，PB不可能从缓冲区中取出数据(假定数据块长等于缓冲区长度)；PA往缓冲队列发送数据时，至少有一个缓冲区是空的；由PA发送的数据块在缓冲队列中按先进先出方式排列。,解：设bufempty为进程PA的私用信号量，buffull为进程PB的私用信号量；令bufempty的初始值为n(n为缓冲队列的缓冲区个数)，buffull的初值为0；,PA:deposit(data):begin local xP(bufempty);按FIFO选空缓冲区buf(x)；buf(x)databuf(x)置满标记V(buffull)end,PB:remove(data):begin local xP(buffull);按FIFO选装满数据缓冲区buf(x)；data buf(x)buf(x)置空标记V(bufempty)end,2.4.8 利用信号量实现进程同步与互斥,生产者-消费问题消费者：系统中使用某一类资源的进程称为该资源的消费者。生产者：释放同类资源的进程称为该资源的生产者。,它们之间满足：消费者想接收数据时，有界缓冲区中至少有一个单元是满的；生产者想发送数据时，有界缓冲区中至少有一个单元是空的。生产者-消费者问题是同步关系,当有进程在写数据时（如生产者进程）则同时不允许对该缓冲区进行读操作（如消费者进程）。故有界缓冲区是临界资源，进程必须互斥访问。生产者-消费者问题同时也具有互斥关系,设信号量mutex：用于访问缓冲区时的互斥，初值是1 avail：生产者进程的私用信号量，表示有界缓冲区中的空单元数，初值为n；full：为消费者进程的私用信号量，表示缓冲区中非空单元数，初值为0。avail+full=n,consumer(data):beginP(full)P(mutex)取缓冲区某单元数据V(avail)V(mutex)end,producer(data):beginP(avail)P(mutex)送数据入缓冲区某单元V(full)V(mutex)end,每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁！,分析：P操作的顺序-很重要,P操作的顺序不当会产生死锁。例：假定执行顺序如下,分析：当full=0,mutex=1时，执行顺序：Consumer.P(mutex);Consumer.P(full);/C阻塞，等待Producer 发出的full信号 Producer.P(avail);Producer.P(mutex);/P 阻塞，等待Consumer发出的avail信号思考：还有其他的执行序列可以产生死锁吗？,发生死锁,2.4.9 利用信号量实现进程同步的方法,1、使用PV操作的规则（1）分清哪些是互斥问题，哪些是同步问题（2）对于互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，互斥信号量的个数只与临界资源的种类有关（3）对于同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关（4）在每个进程中由于实现互斥的PV操作必须成对出现；用于实现同步的PV操作也必须成对出现。必须先执行对同步信号量的P操作，再执行对互斥信号量的P操作。,2、同步互斥问题的解题步骤,（1）确定进程。包括进程的数量、进程的工作内容，可以用流程图描述（2）确定同步互斥关系。根据使用的是临界资源，还是处理的前后关系，来确定互斥与同步，然后确定信号的个数、含义，以及对信号量的PV操作（3）用C语言描述同步或互斥算法,2.5 进程通信,进程通信是指进程间的信息交换。进程通信所交换的信息量少则一个数值或状态，多则成千上万个字节。根据通信的机制不同将进程通信分为低级通信和高级通信。,低级通信-进程的同步和互斥,进程的同步和互斥称为低级通信。缺点：1、效率低，一次发送的信息量比较少。2、信号量机制主要依靠进程来控制，用户使用不方便。,高级通信,高级通信是指用户直接利用操作系统提供的一组通信命令，高效地传送大量数据的一种通信方式。高级通信机制分为3大类：1、共享存储器系统2、消息传递系统3、管道通信系统,2.5.1 共享存储器系统,在共享存储器系统中，相互通信的进程共享某些数据结构或存储区，进程之间能够通过它们进程通信。共享存储器系统分为2种方式：1、共享数据结构方式2、共享存储区方式,1、共享数据结构方式,在这种通信方式下，相互通信的进程共用某些数据结构，并通过这些数据结构交换信息。这种方式与信号量机制相比，并没有发生太大的变化，比较低效、复杂，只适合于传送少量的数据。,2、共享存储区方式,这种通信方式是在存储器中划出一块共享存储区，相互通信的进程可以通过对共享存储区中的数据进行读或写来实现通信。这种方式效率高，可以传送较多的数据。,2.5.2 消息传递系统,在消息传递信息中，进程间的数据交换是以消息为单位进行的。用户直接利用系统中提供的一组通信命令（原语）进程通信。消息传递系统成为最常用的高级通信方式。优点：1、工作效率提高2、简化了程序编制的复杂性，方便用户的使用。,1、直接通信方式,发送进程使用发送原语直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接收接收进程使用接收原语从消息缓冲队列中读取消息。通常系统提供两条通信原语。发送原语：Send（Receiver，message）；接收原语：Receive（Sender，message）；例如原语Send（P2，M）表示将消息M发送给接收进程P2；而原语Receive（P1，M）则是表示接收由进程P1发送来的消息M。,2、间接通信方式,发送进程与接收进程通过中间实体信箱来完成通信，既可以实现实时通信，有可以实现非实时通信。接收进程使用接收原语从信箱中取出消息。,（1）信箱通信的操作,系统为信箱通信提供了若干条操作原语，包括创建信箱原语、撤销信箱原语、发送原语、接收原语等。1、信箱的创建与撤销。进程可以利用信箱创建原语来建立一个新信箱。创建进程应给出信箱的名字、信箱属性等。当信箱所属进程不再需要该信箱时，可用信箱撤销原语来撤销信箱。,2、消息的发送与接收。相互通信的进程利用系统提供的下述通信原语来实现消息的发送与接收。Send（mailbox，message）：将一个消息发送到指定信箱Receive（mailbox，message）：从指定信箱中接收一个消息,（2）消息的分类,消息可以由操作系统创建，也可以由用户创建。创建者是信箱的拥有者，信箱可以分为3类：1、私用信箱。用户进程可以为自己建立一个新信箱，并作为进程的一部分信箱的拥有者有权从信箱中读取信息，其他用户只能将自己的消息发送到该信箱中。当拥有该信箱的进程终止时，信箱也随之消失。,2、公用信箱。它由操作系统创建，并提供给系统中所有核准的用户进程使用。核准的进程既可以把消息发送到该信箱，有可以从信箱中取出发送给本人的消息。通常，公用信箱在系统运行期间始终存在。,3、共享信箱。它实际上是某种进程创建的私有信箱。在创建时或创建后，又指明它是可以共享的，同时指出共享进程（用户）的名字，此时就成为共享信箱。信箱的拥有者和共享者，都有权从信箱中取走发送给本人的消息。,（3）通信进程间的关系,当利用信箱通信时，发送进程与接收进程存在下列关系：1、一对一关系。在一个发送进程和一个接收进程之间建立一条专用的通信通道，使它们之间的通信不受其他进程的影响。2、多对一关系。允许提供服务的一个接收进程与多个用户发送进程之间进行通信，也称为客户/服务器方式。3、一对多关系，允许一个发送进程与多个接收进程进行通信，使发送进程可以用广播形式，向一组或全部接收者发送消息。4、多对多关系。允许建立一个公用信箱，让多个进程既可以把消息发送到该信箱，又可以从信箱中取出发送给本人的消息。,2.5.3 管道通信系统,管道是指连接读进程和写进程的，用于实现它们之间通信的共享文件。向管道提供输入的发送进程（写进程），以字符流的形式间大量数据送入管道，而接收管道输出的接收进程（读进程），可以从管道中接收数据。由于发送进程和接收进程是利用管道进行通信的，故称为管道通信方式。,2.6 处理机调度,一个作业从提交开始直到完成，往往要经历三级调度，即作业调度（高级调度）、进程调度（低级调度）和中级调度。1、作业调度是从后备作业队列中选择出若干个作业，为它们分配必要的资源，将它们调入主存，为它们建立进程，使之成为就绪进程。2、进程调度是从主存就绪队列上选择哪个进程获得处理器资源，让进程运行。,56,功 能：按照一定调度算法从就绪队列中选择一个新的进程投入运行。入口信息：可省,进程调度,2.6.1 进程调度算法的选取原则,选择调度算法的原则有面向用户的，也有面向系统的。1、面向用户的原则（1）周转时间短（2）相应时间快（3）截止时间有保证（4）优先权原则,计算公式,周转时间=完成时间-到达时间平均周转时间=每个进程的周转时间之和/进程个数带权周转时间=进程的周转时间/系统为进程提供的实际服务时间平均带权周转时间=所有进程的带权周转世间之和/进程个数,2、面向系统的原则,（1）系统吞吐量高（2）处理器利用率高（3）各类资源的平衡利用,2.6.2 常用的进程调度算法,算法选择的合理性，将决定进程调度的优劣，它要解决两个问题：第一选择哪个进程执行进程调度；第二个选中某个进程，如何给它分配处理器，该进程能占用处理器多久。第一个问题是选择进程调度算法，第二个问题是选择进程的调度方式。,1先来先服务调度算法,FCFS按照进程进入就绪队列的先后顺序选择可以占用处理器的进程。这是一种不可抢占方式的调度算法。优点：实现简单，缺点：后来的进程等待CPU的时间较长。,2短执行进程优先算法,SPF就是从就绪队列中选择一个CPU执行时间预期最短的进程，将处理器分配给它。优点：较公平 缺点：实现难度较大，因为要准确预定下一个进程的CPU执行周期是很困难的。,3.最短剩余时间优先调度算法,SRT是将CPU分配给需要最少时间来完成的进程。SRT充分照顾了剩余运行时间短的进程。,4时间片轮转法,RR让每个进程在就绪队列中的等待时间与享受服务的时间成比例。在RR中，需要将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但又未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。,5优先权调度算法,HPF的核心是确定进程的优先级。确定优先级的方法可分为静态法和动态法。静态法根据进程的静态特性，在进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改变。动态法把进程的静态特性和动态特性结合起来确定进程的优先级，随着进程的执行过程，其优先级不断变化。,基于静态优先级的调度算法,优点：实现简单，系统开销小 缺点：静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较低，调度性能不高。现在的操作系统中，大多采用动态优先级的调度策略。,基于动态优先级的调度算法,(1)根据进程占有CPU时间的长短来决定。一个进程占有处理机的时间愈长，则在被阻塞之后再次获得调度的优先级就越低。反之，其获得调度的可能性就会越大。(2)根据就绪进程等待CPU的时间长短来决定。一个就绪进程在就绪队列中等待的时间越长，则它获得调度选中的优先级就越高。,2.6.3 作业调度,作业是指用户在一次计算过程或者事务处理过程中，要求计算机系统所作工作的集合。作业调度是从后备作业队列中选择若干个作业，为它们分配必要的资源，将它们调入主存，为它们建立进程，使它们成为就绪进程的过程。这涉及到作业所处的状态、作业调度以及调度算法。,1、作业调度采用的数据结构,为了管理和调度作业，系统为每个作业设置一个作业控制块（JCB）。JCB 是在作业进入系统时由SPOOLING系统为其建立的。其内容由作业控制卡（说明书）中得到的。JCB是作业存在系统的标志，作业进入系统时，则为之建立JCB，当作业退出时，则其JCB也被撤销。,作业名,资源要求,资源使用情况,类型级别,优 先 级,状 态,要求的运行时间、使用语言最迟完成时间、要求的主存量要求外设类型、台数要求的文件量和输出量,进入系统时间开始运行时间已运行时间主存地址外设台号,控制方式 作业类型,优先数,作业控制表JCB,SPOOLING系统,SPOOLING又称为外围设备同时联机操作。在SPOOLING系统中，多台外围设备通过通道或DMA器件和主机与外存连接起来。在硬盘中开辟一块输入/输出井，并将多个用户作业随机的存储提取，各用户间互不干扰。系统中的输入程序包含两个独立的过程，一个过程负责从外部设备把信息读入缓冲区；另一个是写过程，负责把缓冲区的信息送到外存输入井中。,2、作业调度与进程调度的关系,作业调度与进程调度的关系,3、常用的作业调度算法,作业调度程序要完成以下工作：(1)按照某种调度算法从后备作业队列中挑选作业(2)为选中的作业分配主存和外设资源。(3)为选中的作业建立相应的进程。(4)构造和填写作业运行时所需的有关表格。(5)作业结束时完成该作业的善后处理工作，如收回资源，输出必要的信息，撤消该作业的全部进程(PCB)和作业控制块 JCB。,调度原则：公平，合理，使用户满意提高系统资源利用率，如提高系统吞吐量 作业调度算法的评价因素作业吞吐量：运行尽可能多的作业；充分利用资源：CPU忙、I/O设备忙；对各作业公平、合理，使用户满意：执行时间长短、等待时间等；,（1）选择作业调度算法应考虑的因素,（2）常用的作业调度算法,FCFS按作业到达系统的先后次序进行调度。该算法优先考虑在系统中等待时间最长的作业，而不考虑作业运行时间的长短。,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 总是从作业的后备队列中挑选运行时间最短的作业，作为下个调度运行的对象。,短作业优先调度算法,由此：此作业流的平均周转时间为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存在的问题,先来先服务调度算法只考虑了作业的等待时间，而忽略了作业的运行时间，对短作业不利；短作业优先调度算法只考虑了作业运行时间的长短，而忽略了作业的等待时间，对运行时间长的作业不利，因为如果始终有短作业进入系统，则较长作业会长时间得不到调度。,3.响应比高者优先调度算法,HRRN是在每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高者投入运行。HRRN既考虑了作业的等待时间又考虑了作业的运行时间的调度算法，,响应比高者优先调度算法,R作业的响应时间作业的运行时间 作业的响应时间作业的等待时间作业的运行时间 作业的响应比为：R1作业的等待时间作业的运行时间。一个作业的响应比随着等待时间的增加而提高。在相同等待时间的情况下，短作业优先，而对于相同运行时间的作业，等待时间长的作业优先运行。,响应比高者优先调度算法,由于作业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运行完毕，计算后备队列中作业2，4的响应比，计算如下：作业2:R=(72+30)/30=3.4作业4:R=(36+24)/24=2.5显然，这次应该选择作业2，故表2-3中作业2的开始时间为作业3的完成时间，即7:12，最后运行作业4。故作业运行的次序为：1，3，2，4。,由此：此作业流的平均周转时间为T(2.0+1.7+0.7+1.5)/4=1.475h，此作业流的平均周转时间为W(1.0+3.4+3.5+3.75)/4=2.9125注：通过以上分析，这种算法既考虑了作业的等待时间，也考虑了作业的运行时间，是一种比较理想的调度算法。但这种算法复杂，而且需要动态计算某一作业完成时刻后备队列中每个作业的响应比，增加了系统的开销。,4.优先权调度算法,根据作业的优先数调度作业进入系统运行。为每个作业确定一个优先数，资源能满足且优先数高的作业优先被选中，当几个作业有相同的优先数时，对这些具有相同优先数的作业再按照先来先服务原则进行调度。,实例解析,【例】系统中有四个作业同时到达，它们的运行时间和优先数如表2-9所示，若使用优先权调度算法时，作业的平均周转时间为多少？分析：优先权调度算法中规定作业的优先数越高，则该作业在运行的次序中越靠前，所以本例四个作业的运行次序为1，3，4，2。,实例解析,解：由表2-9作业的优先数得作业运行次序为1，3，4，2，故该批作业的平均周转时间为：T(3)+(3+7)+(3+7+2)+(3+7+2+5)/4=42/4=10.5,5.均衡调度算法,这种调度算法根据作业对资源的要求进行分类，作业调度从各类作业中挑选，尽可能地使使用不同资源的作业同时执行。这样不仅可以使系统中的不同类型的资源都在被使用，而且可以减少作业等待使用相同资源的时间，从而加快作业的执行。有的系统还对每一类中的各作业确定优先数，作业调度时在每类作业中再按优先数高者优先的调度原则选择作业。这样，既能使各类作业都得到照顾，又能照顾同类作业中的紧迫作业。,