[优选文档]哈工大张英涛操作系统视频对应全PPT.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,哈工大张英涛操作系统视频对应课件全,进程通信分类,低级通信：进程的互斥和同步,高级通信：指用户可直接利用,os,提供的一组通信命令，高效地传送大量数据的一种通信方式。对用户透明。,高级通信分类,共享存储器系统,消息传递系统,管道通信,共享存储器系统,(1),共享数据结构的通信方式 进程之间通过某种数据结构，如缓冲池进行通信属于低级通信方式；,(2),共享存储区通信方式 为了传送大量信息，在存储器中划出一块共享存储区，进程可通过对共享存储区进行读或写来实现通信，属于高级通信方式。,消息传递系统,信息交换的单位是消息或报文，分成两种：,1,直接通信方式,2,间接通信方式,计算机网络中将消息称为报文。,直接通信方式,发送进程直接把消息发送给目标进程,发送进程和接收进程都以显式方式分别提供对方的标识符。,系统提供两条通信原语,Send(Receiver,message);,Receive(Send,message);,例如,:Send(P2,m1);,Receive(P1,m1);,解决生产者一消费者问题,repeat ,produce an item in nextp;,Send(consumer,nextp);,until false;,repeat,Receive(producer,nextp);,Consumer the item in nextc;,until false;,间接通信方式,进程之间的通信需要通过某种中间实体，该实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发送给自己的消息。,这种中间实体称为信箱。,消息在信箱中可以安全地保存只允许核准的目标用户随时读取，故可实现非实时通信。,信箱的创建和撤消,进程用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性,(,公用、私用或共享,),；对于共享信箱，还应给出共享者的名字。,用信箱撤消原语来撤消。,消息的发送与接收,Send(mailbox,message),：将一个消息发送到指定信箱；,Receive(mailbox,message),从指定信箱中接收一个消息,信箱分类,私用信箱。,公用信箱。,共享信箱。,私用信箱,用户进程建立，作为该进程的一部分。,拥有者有权读消息其他用户只能发送。,采用单向通信链路。,进程结束时信箱也消失。,公用信箱,它由,OS,创建,提供给系统中的所有核准进程使用。,进程既发送也可取出。,采用双向通信链路的信箱来实现。,系统运行期间始终存在。,共享信箱,由某进程创建，创建时提供共享进程,(,用户,),的名字。,信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。,信箱通信时发送进程和接收进程的关系：,一对一关系。建立一条专用的通信链路。,多对一关系。服务进程与多个用户进程之间进行交互，又称客户服务器交互。,一对多关系。一个发送进程与多个接进程进行交互，使发送进程可用广播形式，向接收者发送消息。,多对多关系。建立一个公用信箱，多个进程投递并取走自己的消息。,管道通信,管道通信方式建立在文件系统的基础上，利用共享文件来连接两个相互通信的进程，此共享文件称为管道,(Pipe),。,管道是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件,写进程,读进程,管道,管道通信必需的协调能力,(1),互斥 当一个进程正在对管道进行读写操作时，另一进程必须等待。,(2),同步 当写,(,输入,),进程把一定量的数据,(,如,4K),写入管道后，便去睡眠等待，直到读,(,输出,),进程取走数据后再把它唤醒。当读进程发现管道空时也应睡眠等待，直至写进程将消息写入管道后，才将它唤醒,(3),判别对方是否存在只有确定了对方存在时方能进行通信。,谢 谢 收 看,操作系统 第,11,讲,哈尔滨工业大学 张英涛,操 作 系 统,第,12,讲,主讲人：张英涛,哈尔滨工业大学远程教育课程,线程,进程,:,使多个程序能并发执行，以提高资源利用率和系统吞吐量,引入线程，是为了减少程序在并发执行时所付出的时空开销，使,OS,具有更好的并发性,引入线程目的,进程是可拥有资源的独立单位和可独立调度和分派的基本单位。,创建、撤消和切换中，系统必须为之付出较大的时空开销。故进程，其数目不宜过多，进程切换的频率也不宜过高。,进程不应同时作为拥有资源的单位和可独立调度和分派的基本单位，应该“轻装上阵”；,线程的属性,（,1,）轻型实体。线程中的实体基本上不拥有系统资源,（,2,）独立调度和分派的基本单位。线程的切换非常迅速、开销小。,（,3,）可并发执行。,（,4,）共享进程资源。,课 堂 练 习,1,操作系统是,控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的系统软件,(,或程序集合,),是用户与计算机之间的接口。,操作系统的基本职能是（）,A.,控制和管理系统内各种资源，有效地组织多道程序的运行,B.,提供用户界面，方便用户使用,C.,提供方便的可视化编辑程序,D.,提供功能强大的网络管理工具,A,操作系统的基本特征是,、,和,_,、,。,并发,共享,异步性,虚拟,操作系统中引入“进程”概念,的主要目的是（）。,A.,改善用户编程环境,B.,描述程序动态执行过程的性质,C.,使程序与计算过程一一对应,D.,提高程序的运行速度,B,某进程由于需要从磁盘上读入数据而处于阻塞状态。当系统完成了所需的读盘操作后，此时该进程的状态将（）,A.,从就绪变为运行,B,从运行变为就绪,C,从运行变为阻塞,D,从阻塞变为就绪,D,进程控制块（,PCB,）是专为用户进程设置的私有数据结构，每个进程仅有一个,PCB,。,（）,判断对错并改正,所有,简单地说，进程是程序的执行过程。因而，进程和程序是一一对应的。（）,判断对错并改正,不是,进程间相互合作的关系是,_,关系，而对资源争用的关系是,_,关系。若干进程使用同一临界资源时必须,_,执行。,同步,互斥,互斥,对信号量,S,每执行一次,P,操作，则信号量,S,的值就,。当,S,的值,_,时，执行,P,操作的进程的状态就置为阻塞态，把相应的,PCB,连入该信号量队列的,，并且该进程,处理机。,减,1,小于,0,末尾,放弃,进程和程序的主要区别是什么？,解答题,答：进程是动态的，程序是静态的；进程具有并发性，而程序具有顺序性；进程具有独立性，是资源分配和调度的基本单位，而程序无此特性；进程和程序间没有一一对应关系；进程异步运行，会相互制约，程序不具备此特性。,有两个用户进程,A,和,B,，在运行过程中都要使用系统中的一台打印机输出计算结果。,（,1,）说明,A,、,B,进程之间存在什么样的制约关系？,（,2,）为保证这两个进程能正确地打印出各自的结果，请用信号量和,P,、,V,操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。,解：,(1)A,、,B,两个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。,解：,（,2,）,mutex,：用于互斥的信号量，初值为,1,。,各进程代码如下：,进程,A,：,.,P,（,mutex,）,申请打印机,使用打印机,V,（,mutex,）,.,进程,B,：,.,P,（,mutex,）,申请打印机,使用打印机,V,（,mutex,）,.,谢 谢 收 看,操作系统 第,12,讲,哈尔滨工业大学 张英涛,操 作 系 统,第,13,讲,主讲人：张英涛,哈尔滨工业大学远程教育课程,第三章,处理机调度,与死锁,一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历的三级调度,:,高级调度,低级调度,中级调度,高级调度,又称作业调度、长程调度、接纳调度,作用：把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配资源、排在就绪队列上，准备执行。,分时系统、实时系统，通常不需要作业调度。,各进程代码如下：,produce an item in nextp;,哈尔滨工业大学 张英涛,用户进程建立，作为该进程的一部分。,这是由用户进程的紧迫程度及所付费多少来确定。,完成后，便把它挂在轮转队列的末尾，等待下次调度运行，这次调度程序在选择下一个（队首）任务运行。,只有一个主处理器，有多个从处理器。,高响应比优先调度算法,4 9 6 13,在执行期间，只要又出现优先权更高的进程，就重新将处理机分配给新到的优先权最高的进程。,作业较小，只要使作业（进程）在第一队列所规定的时间片内完成，便可令用户满意。,对称MPS,与单机进程调度方式相同。,2 动态分配方式,（1）就绪队列的形式。,Receive(producer,nextp);,设置某些限制条件，破坏四个必要条件中的一个或几个条件。,A B C D E,低级调度,也称为进程调度、短程调度。,作用：决定就绪队列中的哪个进程应获得处理机，然后由分派程序执行把处理机分配给该进程的具体操作。,在,OS,中都必须配置。,进程调度的两种调度方式,非抢占方式,抢占方式,非抢占方式,一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或阻塞时，才再把处理机分配给其他进程。,1,进程执行完毕，或因发生某事件而不能在继续执行；,2,执行中的进程因提出,I/O,请求而暂停执行,3,在进程通信或同步过程中执行了某种原语操作，如,P,操作（,WAIT,操作）、,BLOCK,原语、,WAKEUP,原语等。,非抢占方式引起进程调度的因素,抢占方式,允许暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。,抢占原则,（,1,）优先权原则。优先权高的进程抢占处理机。,（,2,）短作业优先原则。短作业（进程）抢占当前较长作业（进程）的处理机。,（,3,）时间片原则。各进程按时间片运行，当一个时间片用完后重新调度。,中级调度,又称中程调度。,目的：提高内存利用率和系统吞吐率,作用：使暂时不能运行的进程从内存调至外存，进入就绪驻外存状态或挂起状态。把外存上又具备运行条件的就绪进程，重新调入内存，并修改为就绪状态，挂在就绪队列上。,又称对换,调度队列模型,仅有进程调度的调度队列模型,有高级和低级调度的调度队列模型,同时有三级调度的调度队列模型,通常，把就绪进程组织成,FIFO,队列，每当创建新进程时排在就绪队列的末尾，按时间片轮转方式运行,仅有进程调度的调度队列模型,进程在执行时，出现三种情况：,1,任务在时间片内完成，进程便在释放处理机后进入完成状态；,2,任务在时间片内未完成，,OS,便将该任务再放入就绪队列的末尾；,3,在执行期间，进程因为某事件而被阻塞后，被,OS,放入阻塞队列。,就绪队列,阻塞队列,cpu,进程调度,等待事件,时间片完,进程完成,用户,事件出现,有高级和低级调度的调度队列模型,与前一模型的差别：,（,1,）就绪队列的形式。批处理系统中最常用的是优先权队列。也可采用无序链表方式。,（,2,）设置多个阻塞队列。,就绪队列,阻塞队列,cpu,进程调度,等待事件,时间片完,进程完成,作业调度,后备队列,有三级调度的调度队列模型,调出时，可使进程状态由内存就绪转变为外存就绪，由内存阻塞转变为外存阻塞；,在中级调度使外存就绪转变为内存就绪。,谢 谢 收 看,操作系统 第,13,讲,哈尔滨工业大学 张英涛,操 作 系 统,第,14,讲,主讲人：张英涛,哈尔滨工业大学远程教育课程,选择调度方式和调度算法的准则,面向用户的准则,面向系统的准则,周转时间短,响应时间快,截止时间的保证,优先权准则,系统吞吐量高,处理机利用率好,资源的平衡利用,周转时间,从作业被提交给系统开始，到作业完成为止的这段时间间隔称为作业周转时间。包括四部分时间：,在外存后备队列上等待调度的时间,进程在就绪队列上等待调度的时间,进程在,CPU,上执行的时间,进程等待,I/O,操作完成的时间,平均周期时间：,T=1/n T,i,i=1,n,带权周转时间,:,W=T/T,s,T,：作业的周期时间,T,s,：,系统为提供为它提,供服务的时间（真正,运行时间）。,平均带权周转时间：,W=1/n Ti/T,si,i=1,n,作业,提交时间,/,时,运行时间,/h,1,10.00,2,2,10.10,1,3,10.25,0.25,例,:,有如下三道作业。系统为它们服务的顺序,是：,1,、,2,、,3,。求平均周转时间和平均,带权周转时间。,作业,提交时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,1,10.00,2,2,10.10,1,3,10.25,0.25,解：,作业,提交时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,1,10.00,2,10,12.00,2,2/2,2,10.10,1,12,13.00,2.9,2.9/1,3,10.25,0.25,13,13.25,3,3/0.25,平均周转时间：,T=(2+2.9+3)/3=2.63h,平均带权周转时间：,W=(2+2.9+12)/3=5.3h,。,响应时间,响应时间是从用户通过键盘提交一个请求开始直至系统首次产生响应为止的时间间隔。它包括三部分时间：,从键盘输入的请求信息传送到处理机的时间,处理机对请求信息进行处理的时间,将响应信息回送到终端显示器的时间。,是分时系统中的重要原则,。,截止时间是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。,对于严格的实时系统，其调度方式和调度算法必须能保证这一点。,吞吐量,吞吐量指单位时间内系统所完成的作业数。,评价批处理系统性能的重要指标。,与作业的平均长度有关。对于大型作业，一般吞吐量约为每小时一道作业对于中、小型作业，其吞吐量则可达到数十道作业。,谢 谢 收 看,操作系统 第,14,讲,哈尔滨工业大学 张英涛,操 作 系 统,第,15,讲,主讲人：张英涛,哈尔滨工业大学远程教育课程,调度算法,调度算法是指：根据系统的资源分配策略所规定的资源分配算法。,不同的系统和系统目标，通常采用不同的调度算法,先来先服务调度算法,作业调度中每次从后备作业队列中，选择一个或多个最先进入该队列的作业调入内存，为它们分配资源、创建进程，然后放入就绪队列。,进程调度时每次从就绪队列中，选择一个最先进入该队列的进程分配处理机使之运行。直到完成或阻塞后，才放弃处理机。,先来先服务调度算法,是一种最简单的调度算法既可用于作业调度也可用于进程调度。,FCFS(first come first serve),算法,有利长作业（进程），而不利于短作业（进程）。,有利,CPU,繁忙型作业，而不利于,I/O,繁忙型作业。,进程,到达时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,A,0,1,0,B,1,100,1,C,2,1,101,D,3,100,102,决定服务顺序,进程,到达时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,A,0,1,0,B,1,100,1,C,2,1,101,D,3,100,102,开始,+,运行,进程,到达时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,A,0,1,0,1,B,1,100,1,101,C,2,1,101,102,D,3,100,102,202,开始,+,运行,进程,到达时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,A,0,1,0,1,B,1,100,1,101,C,2,1,101,102,D,3,100,102,202,完成,-,到达,进程,到达时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,A,0,1,0,1,1,B,1,100,1,101,100,C,2,1,101,102,100,D,3,100,102,202,199,周转,/,运行,进程,到达时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,A,0,1,0,1,1,1/1,B,1,100,1,101,100,100/100,C,2,1,101,102,100,100/1,D,3,100,102,202,199,199/100,进程,到达时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,A,0,1,0,1,1,1/1,B,1,100,1,101,100,100/100,C,2,1,101,102,100,100/1,D,3,100,102,202,199,199/100,短作业（进程）优先法,短作业优先（,SJF,）法：从后备队列中选择一个或若干个估计运行时间最短的作业调入内存运行。,短进程优先（,SPF,）调度算法：从就绪队列中选出一估计运行时间最短的进程，分配处理机使它立即执行直到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。,进程名,A B C D E,平均,到达时间,0 1 2 3 4,服务时间,4 3 5 2 4,FCFS,完成时间,周转时间,带权周转时间,SJF,完成时间,周转时间,带权周转时间,作业,算法,进程名,A B C D E,平均,到达时间,0 1 2 3 4,服务时间,4 3 5 2 4,FCFS,完成时间,4 7 12 14 18,周转时间,4 6 10 11 14,9,带权周转时间,1 2 2 5.5 3.5,2.8,SJF,完成时间,周转时间,带权周转时间,作业,算法,进程名,A B C D E,平均,到达时间,0 1 2 3 4,服务时间,4 3 5 2 4,FCFS,完成时间,4 7 12 14 18,周转时间,4 6 10 11 14,9,带权周转时间,1 2 2 5.5 3.5,2.8,SJF,完成时间,4,周转时间,4,带权周转时间,作业,算法,进程名,A B C D E,平均,到达时间,0 1 2 3 4,服务时间,4 3 5 2 4,FCFS,完成时间,4 7 12 14 18,周转时间,4 6 10 11 14,9,带权周转时间,1 2 2 5.5 3.5,2.8,SJF,完成时间,4 6,周转时间,4 3,带权周转时间,作业,算法,进程名,A B C D E,平均,到达时间,0 1 2 3 4,服务时间,4 3 5 2 4,FCFS,完成时间,4 7 12 14 18,周转时间,4 6 10 11 14,9,带权周转时间,1 2 2 5.5 3.5,2.8,SJF,完成时间,4 9 6,周转时间,4 8 3,带权周转时间,作业,算法,进程名,A B C D E,平均,到达时间,0 1 2 3 4,服务时间,4 3 5 2 4,FCFS,完成时间,4 7 12 14 18,周转时间,4 6 10 11 14,9,带权周转时间,1 2 2 5.5 3.5,2.8,SJF,完成时间,4 9 6 13,周转时间,4 8 3 9,带权周转时间,作业,算法,进程名,A B C D E,平均,到达时间,0 1 2 3 4,服务时间,4 3 5 2 4,FCFS,完成时间,4 7 12 14 18,周转时间,4 6 10 11 14,9,带权周转时间,1 2 2 5.5 3.5,2.8,SJF,完成时间,4 9 18 6 13,周转时间,4 8 16 3 9,带权周转时间,作业,算法,进程名,A B C D E,平均,到达时间,0 1 2 3 4,服务时间,4 3 5 2 4,FCFS,完成时间,4 7 12 14 18,周转时间,4 6 10 11 14,9,带权周转时间,1 2 2 5.5 3.5,2.8,SJF,完成时间,4 9 18 6 13,周转时间,4 8 16 3 9,8,带权周转时间,1 2.673.1 1.5 2.25,2.1,作业,算法,进程名,A B C D E,平均,到达时间,0 1 2 3 4,服务时间,4 3 5 2 4,FCFS,完成时间,4 7 12 14 18,周转时间,4 6 10 11 14,9,带权周转时间,1 2 2 5.5 3.5,2.8,SJF,完成时间,4 9 18 6 13,周转时间,4 8 16 3 9,8,带权周转时间,1 2.673.1 1.5 2.25,2.1,作业,算法,SJ（P）F法缺点,（,1,）对长作业不利。如果有一长作业进入系统的后备队列，由于总是优先调度那些短作业（进程），将导致长作业长期不被调度。,（,2,）完全未考虑作业的紧迫程度，不能保证紧迫性作业（进程）会被及时处理。,（,3,）作业（进程）的长短根据用户所提供的估计执行时间而定的不一定能真正做到短作业优先调度。,高优先权优先调度算法,1,优先权调度算法的类型,2,优先权的类型,3.,高响应比优先调度算法,谢 谢 收 看,操作系统 第,15,讲,哈尔滨工业大学 张英涛,操 作 系 统,第,16,讲,主讲人：张英涛,哈尔滨工业大学远程教育课程,优先权调度算法类型,1,）非抢占式优先权算法,2,）抢占式优先权调度算法,非抢占式优先权算法,把处理机分配给就绪队列中优先权最高的进程后便一直执行下去直至完成；或发生某事件使该进程放弃处理机时，可再将处理机重新分配给另一优先权最高的进程。,用于批处理系统和某些对实时性要求不严的实时系统中。,抢占式优先权调度算法,把处理机分配给优先权最高的进程，使之执行。在执行期间，只要又出现优先权更高的进程，就重新将处理机分配给新到的优先权最高的进程。,能更好地满足紧迫作业的要求，常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。,优先权的类型,静态优先权,动态优先权,静态优先权,在创建进程时确定,在进程的整个运行期间保持不变。,一般地，用某一范围内的一个整数来表示的，例如，,07,或,0255,中的某一整数，又把该整数称为优先数。,确定优先权依据：,（,1,）进程类型：系统进程高于用户进程,（,2,）进程对资源的要求：要求少的进程应赋予较高优先权。,（,3,）用户要求。这是由用户进程的紧迫程度及所付费多少来确定。,静态优先权法优缺点,简单，系统开销小,不精确，仅在要求不高的系统中使用,动态优先权,优先权随进程推进或随其等待时间的增加而改变的，以便获得更好的调度性能。,高响应比优先调度算法,引入动态优先权，并使作业优先级随着等待时间的增加而以速率,a,提高。,该优先权的变化规律为：,优先权,=,（等待时间,+,要求服务时间）,/,要求服务时间,优先权,=R,P,=,响应时间,/,要求服务时间,R,P,：响应比,分析,作业等待时间相同，则有利于短作业。,要求服务时间相同，实现的是先来先服务。,长作业也可获得处理机。,优点：兼顾长短作业。,缺点：由于做相应比计算故增加了系,统开销,时间片轮转法,分时系统中多采用,时间片轮转法,把就绪进程组织成,FIFO,队列，,把,CPU,分配给队首进程，,规定它执行一个时间片。,时间片完时排在就绪队列的末尾，重新把处理机分配给就绪队列中新的队首进程，也执行一个时间片。,就绪队列中的所有进程在一给定时间内，均可获得一个时间片的,CPU,时间,.,多级反馈队列调度算法,（,1,）为多个就绪队列赋不同的优先级。,第一个队列的优先级最高其余逐个降低。,各队列中进程执行时间片的也不同，优先权愈高的队列中时间片愈小。,多级反馈队列调度算法,（,2,）新进程进入内存后，首先放入第一队列的末尾，按,FCFS,原则排队等待调度。到该进程执行时，如果能在该时间片内完成，便准备撤离系统；如果未完成，转入第二队列的末尾，再同样地按,FCFS,原则等待调度执行；如此下去，当一个长作业从第一队列依次降到第,N,队列后，在第,N,队列中便采取按时间片轮转的方式运行。,（,3,）仅当第,1,（,i1,）队列均空时，才会调度第,i,队列中的进程运行。如果处理机正在第,i,队列中为某进程服务时，又有新进程进入优先权较高的队列，则新进程将抢占处理机，即由调度程序把正在运行的进程放回到第,i,队列的末尾，把处理机分配给新到的高优先权进程。,多级反馈队列调度算法,多级反馈队列调度算法的性能,（,1,）终端型作业用户。作业较小，只要使作业（进程）在第一队列所规定的时间片内完成，便可令用户满意。,（,2,）短批处理作业用户。其周转时间短。,（,3,）长批处理作业用户。不必担心作业长 期得不到处理。,谢 谢 收 看,操作系统 第,16,讲,哈尔滨工业大学 张英涛,操 作 系 统,第,17,讲,主讲人：张英涛,哈尔滨工业大学远程教育课程,实时调度基本条件,提供必要的信息,系统处理能力强,采用抢占式调度机制,具有快速切换机制,必要信息,就绪时间。,开始截止时间和完成截止时间。,处理时间。,资源要求。,优先级。,假定系统中有有,M,个周期性的硬实时任务，它们的处理时间可表示为,C,i,，周期时间间表示为,P,i,，,N,为系统中的处理机数。则必须满足下面的限制条件：,C,i,/,P,i,N,系统才是可调度的。,i=1,m,例,:,单处理机系统中有,6,个硬实时任务，它们的周期时间都是,50MS,，而每次的处理时间为,10MS,，则,C,i,/,P,i,=6/5,1,所以系统是不可调度的,i=1,6,快速切换机制,对外部中断的快速响应能力。响应禁止中断的时间间隔尽量短,快速的任务分派能力。,实时调度算法分类,按任务性质,硬实时调度算法,软实时调度算法,实时调度算法分类,按调度方式,非抢占调度算法,抢占调度算法,实时调度算法分类,按调度时间,静态调度算法,动态调度算法,非抢占式调度算法,算法简单，用在小型实时系统或要求不严的实时控制系统中。,分两种：,（,1,）非抢占式轮转调度算法,（,2,）非抢占式优先调度算法,非抢占式轮转调度算法,用于工业群控系统中,由一台计算机控制若干个相同的（或类似的）对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。,调度程序每次选择队列中的第一个任务运行。完成后，便把它挂在轮转队列的末尾，等待下次调度运行，这次调度程序在选择下一个（队首）任务运行。,可获得数秒至数十秒的响应时间,非抢占式优先调度算法,针对有一定要求的系统,为实时要求高的任务赋予较高的优先级。优先安排在就绪对列队首，待当前任务结束后，被调度执行。,响应时间为数秒至数百毫秒,抢占式调度算法,应用于响应时间在数十毫秒以下的系统。,根据抢占发生时间不同分类：,（,1,）基于时钟中断的抢占式优先权调度算法。,（,2,）立即抢占的优先权调度算法。,基于时钟中断的抢占式优先权调度算法,高优先级的实时任务到达后不立即抢占，等到时钟中断到来时再重新分配处理机。,立即抢占的优先权调度算法,高优先级的实时任务到达后，只要当前任务未处于临界区就立即把处理机分配给它。,进程,1,进程,2,进程,n,实时进程,实时进程要求调度,实时进程运行,非抢占轮转调度算法,调度时间,当前进程,实时进程,实时进程要求调度,当前进程完成,非抢占优先权调度算法,调度时间,当前进程,实时进程,实时进程要求调度,时钟中断到来,基于时钟中断的抢占式优先权调度算法,调度时间,当前进程,实时进程,实时进程要求调度,抢占并立即执行,立即抢占的优先权调度算法,调度时间,常用的实时调度算法,最早截止时间优先算法即,EDF,算法,（,EARLIEST DEADLINE FIRST,）,最低松弛优先算法即,LLF,算法,（,LEAST LAXITY FIRST,）,谢 谢 收 看,操作系统 第,17,讲,哈尔滨工业大学 张英涛,操 作 系 统,第,18,讲,主讲人：张英涛,哈尔滨工业大学远程教育课程,EDF,算法,根据任务的开始截止时间确定优先级，截止时间越早优先级越高。,系统中保持一个实时任务优先级就绪队列，调度程序选择对首任务分配处理机。,可采取抢占式和非抢占式调度。,任务执行,任务到达,开始截止时间,1,2,3,4,1,2,3,4,1,2,4,3,LLF,算法,根据任务的紧急程度确定优先级，紧急程度越高优先级越高。,系统中保持一个实时任务优先级就绪队列，调度程序选择对首任务分配处理机。,可采取抢占式和非抢占式调度。,多处理器系统（,MPS,）,提高系统性能的主要途径有两条：,一,.,提高元器件的运行速度，特别是处理器芯片的速度,二,.,改进计算机系统的体系结构，特别是在系统中引入多个处理器或多台计算机。,功能较强的主机系统和服务器都采用了多处理器系统,处理器的数目可为两个至数千。,多处理机系统,类型,1,从,多处理机之间耦合的紧密程度上，可分为：,紧密耦合,MPS,松弛耦合,MPS,2,根据系统中处理器的相同与否可分为：,对称,MPS,非对称,MPS,紧密耦合,MPS,通常通过高速总线或高速交叉开关实现多个处理器互连。,它们共享主存和,I/O,设备，并要求将主存划分为若干个能独立访问的存储器模块，以便多个处理器能同时对主存进行访问。,系统中的所有资源和进程，都由操作系统实施统一的控制和管理。,松弛耦合（,MPS,）,通常通过通道或通信线路实现多台计算机之间互连。,每台计算机都有自己的存储器和,I/O,设备，并配置了,OS,来管理本地资源和在本地运行的进程。,每台计算机都能独立工作，必要时可通过通信线路与其它计算机交换信息。,对称多处理器系统,系统中的处理器单元在功能和结构上都相同,例如，,IBM,公司的,SR/6000 MODEL F50:,利用,4,片,POWER PC,处理器构成的。,非对称多处理器系统,系统中有多种类型的处理单元，它们的功能和结构各不相同,只有一个主处理器，有多个从处理器。,进程分配方式,多处理器系统中进程的调度与系统结构有关。,同构系统中进程可以分配到任一处理器上,非对称系统中进程只能分配到某一合适运行的处理器上。,对称多处理器系统的进程分配,把所有处理器作为一个处理器池,由调度程序或基于处理器的请求，将任何一个进程分配给池中的任何一个处理器。采用两种方式：,1,静态分配方式,2,动态分配方式,静态分配方式,特点：进程被固定分配到一个处理器上；与单机进程调度方式相同。,优点：开销小,缺点：各处理机忙闲不均,动态分配方式,设置一个公共就绪队列，进程可被分配到任一处理器上,优点：消除了忙闲不均的现象。,非对称,MPS,中的进程分配方式,多采用主,从式,OS,，即,OS,的核心部分驻留在一台主机上，从机上只是用户程序，进程调度只由主机执行。,优点：系统处理简单，因为进程分配由主机独自处理，使进程间的同步问题得以简化。,谢 谢 收 看,操作系统 第,18,讲,哈尔滨工业大学 张英涛,操 作 系 统,第,1 9,讲,主讲人：张英涛,哈尔滨工业大学远程教育课程,进程（线程）调度方式,自调度方式,成组调度方式,专用处理机分配方式,自调度方式,自调度机制,自调度方式的优点,自调度方式的缺点,自调度机制,是最简单的一种调度方式，是直接由单处理机环境下的调度方式演变而来的。,单处理机环境下的,FCFS,、,FPF,和抢占式,FPF,调度算法都可用。,FCFS,算法是一种好的调度算法。,自调度机制,整个系统中只设置一个就绪队列，供多个处理器共享，这些处理器必须互斥地访问该队列。,自调度方式优点,容易将单处理机环境下的调度机制移植到多处理机系统中。,处理器的利用率高。因为只要公共就绪队列不空，就不会出现处理机空闲的情况，也不会发生处理器忙闲不均的现象。,自调度方式缺点,（,1,）瓶颈问题。一个就绪队列，供多个处理器共享，这些处理器必须互斥地访问该队列。处理器数目在数十个乃至数百个时，会产生严重的瓶颈问题。,（,2,）低效性。线程在整个生命周期中，可能要多次更换处理器，使高速缓存的使用效率很低。,（,3,）线程切换频繁。多个相互合作型的线程很难同时获得处理器，将会使某些线程阻塞，被切换下来。,成组调度方式,是指将一个进程中的一组线程，分配一组处理器上去执行。,可用两种方式为应用程序分配处理器时间：,（,1,）面向所有应用程序平均分配处理器时间,（,2,）面向所有线程平均分配处理器时间,面向所有应用程序平均分配处理器时间,假定系统中有,N,个处理机和,M,个应用程序，每个应用程序至多含有,1/M,的时间去占有,N,个处理机。,4 7 12 14 18,然后，采取适当措施，从系统中将已发生的死锁清除掉。,哈尔滨工业大学远程教育课程,哈尔滨工业大学 张英涛,立即抢占的优先权调度算法,描述程序动态执行过程的性质,为实时要求高的任务赋予较高的优先级。,它们共享主存和I/O设备，并要求将主存划分为若干个能独立访问的存储器模块，以便多个处理器能同时对主存进行访问。,提高系统性能的主要途径有两条：,与作业的平均长度有关。,设置某些限制条件，破坏四个必要条件中的一个或几个条件。,提高系统性能的主要途径有两条：,调度程序每次选择队列中的第一个任务运行。,进程具有独立性，是资源分配和调度的基本单位，而程序无此特性；,4 3 5 2 4,操作系统的基本特征是 、和_、。,例,:,有,4,个处理机和,2,个应用程序，应用程序,A,含有,4,个线程，应用程序,A,含有,4,个线程。求处理机分配方式及时间利用率。,应用程序,A,应用程序,B,处理器,1,处理器,2,处理器,3,处理器,4,1/2,1/2,应用程序,A,应用程序,B,处理器,1,处理器,2,处理器,3,处理器,4,线程,1,线程,1,线程,2,线程,3,线程,4,1/2,1/2,浪费,3/8,应用程序,A,应用程序,B,处理器,1,处理器,2,处理器,3,处理器,4,线程,1,线程,1,线程,2,线程,3,线程,4,4/5,1/5,浪费,1/5*3/4=3/20,面向所有线程平均分配,成组调度方式优点,减少线程切换,优于自调度,专用处理机分配方式,指在一个应用程序的执行期间，专门为该应用程序分配一组处理器，每一个线程一个处理器，供应用程序专用直至该应用程序完成。,专用处理机分配方式缺点,可造成单个处理机的浪费,专用处理机分配方式引入原因,多处理机系统中单个处理机的利用率不很重要,在一个应用程序的运行中完全避免了进程或线程的切换，大大加速运行。,死 锁,多个进程在运行过程中因竞争资源而造成的一种僵局。,各并发进程彼此等待对方拥有的资源，且在得到对方资源前不释放自己的资源。,死锁,小区,A,小区,B,例如：,系统中共有,5,台打印机，进程,A,需要,3,台，进程,B,需要,4,台，进程,A,、,B,并发执行时进程,A,已经占,3,台，进程,B,已经占,2,台。则此时陷入死锁状态。,产生死锁的原因,（,1,）竞争资源。资源（打印机、公用队列）数目不能满足进程的需要时,（,2,）进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。,谢 谢 收 看,操作系统 第,19,讲,哈尔滨工业大学 张英涛,操 作 系 统,第,20,讲,主讲人：张英涛,哈尔滨工业大学远程教育课程,竞争资源引起死锁,1,）可剥夺和非剥夺性资源,2,）竞争非剥夺性资源,3,）竞争临时性资源,可剥夺和非剥夺性资源,资源分成两类：,可剥夺性资源：指某进程在获得这类资源后，该资源可以在被其他进程