《计算机操作系统-进程调度》课件

计算机操作系统——进程调度摘要基础：进程调度策略：进程调度实现：互斥与同步-避免：死锁与饥饿-解决：几个经典问题（如生产者-消费者）-了解：进程通信单道程序与多道程序的执行单道程序执行的过程多道程序执行的过程课堂思考与练习设时刻0，在内存中有三个程序A、B、C，占用CPU的优先权为A最高，C最低；它们的计算和I/O操作时间如表所示。试画出单道运行和多道运行的时间关系图。ABC计算306020I/O403040计算101020什么叫进程？为什么要引入“进程”这一概念？为了提高系统资源的利用率，出现了多道程序设计技术，但多道程序的并发执行和资源共享带来了新的问题，破坏了程序的封闭性和可再现性，程序和机器执行程序的活动不再一一对应，并发程序之间有可能存在相互制约关系。并发程序的独立性、并发性、动态性和相互制约反映了并发程序的本质，而程序的概念已不能反映程序并发执行的实质，因此，人们引入了进程的概念来描述并发程序的执行过程。进程：一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。这里，程序指一组操作序列，而数据集则是接受程序规定操作的一组存储单元的内容。进程=程序的执行？进程和程序的区别和关系？进程和程序是两个既有联系又有区别的概念，它们的区别和关系可简述如下：(1)进程是一个动态概念，而程序则是一个静态概念。程序是指令的有序集合，没有任何执行的含义。而进程则强调执行过程，它动态地被创建，并被调度执行后消亡。(2)进程具有并行特征，而程序没有。由进程的定义可知，进程具有并行特征的两个方面，即独立性和异步性。也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，执行速度是异步的。显然，由于程序不反映执行过程，所以不具有并行特征。(3)进程是竞争计算机系统资源的基本单位，从而其并行性受到系统自己的制约。这里，制约就是对进程独立性和异步性的限制。(4)不同的进程可以包含同一程序，只要该程序所对应的数据集不同。如何监控程序的执行？用各种数据结构来记录多个进程（PCB）用状态的变迁来跟踪多个进程用进程调度来选择控制多个进程用并发控制来同步、协调多个进程进程的静态描述进程=程序+数据+进程控制块PCB程序描述进程所要完成的功能数据是对其进行操作的数据结构集，程序在执行时必不可少的工作区和操作对象。进程控制块包含了有关进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映。进程状态及转换进程控制进程控制，就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。1.进程创建2.进程撤销3.进程阻塞4.进程唤醒5.进程切换：在某一时刻，一运行的进程被迫中断，让出CPU给指定进程。一般在进行进程上下文切换时，不保留被切换的进程上下文的正文，但保留进程执行时所使用的寄存器。程序执行过程①单进程单一进程②多进程独立进程彼此独立③多进程协作进程彼此依赖在并发环境下不存在完全独立的进程！程序执行过程④多进程竞争进程共享互斥共享资源⑤多进程通信进程相互通信程序执行过程中的问题①②不存在资源竞争，只存在CPU调度③④⑤多个进程相互依赖、彼此竞争资源，既存在CPU调度，又存在同步协调，从而引入并发控制。并发控制的实施•策略：临界资源与临界区•机制：标志、信号量•方法：加锁、P、V原语•实现：互斥和同步进程互斥（1）临界资源：一次仅允许一个进程使用的共享资源。每次只准许一个进程进入临界区，进入后不允许其他进程进入。对于临界资源，多个进程必须互斥地对它进行访问。临界区：每个进程中访问临界资源的那段代码。临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的。间接制约：由共享公有资源而造成的对并发进程执行速度的间接制约。即把这种由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象。进程互斥（2）互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。进程互斥：一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。当占用临界资源的进程退出临界区，才允许另一进程区访问此临界资源。为了禁止两个进程同时进入临界区，需采用一定的方法来协调它们。无论方法是什么都应遵循下述准则：1.空闲让出2.忙则等待3.让权等待4.有限等待进程互斥（3）互斥的加锁实现对临界区加锁以实现互斥：当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区。进程互斥（4）设临界区的类名为Ｓ。为了保证每一次临界区中只能有一个程序段被执行，又设锁定位key［Ｓ］。key［Ｓ］表示该锁定位属于类名为Ｓ的临界区。加锁后的临界区程序描述如下：lock(key［Ｓ］)〈临界区〉unlock(key［Ｓ］)设key［Ｓ］=1时表示类名为Ｓ的临界区可用，key［Ｓ］=0时表示类名为Ｓ的临界区不可用。进程互斥（5）一种简便的实现方法是：lock(x)=beginlocalvrepeatv←xuntilv=1x←0end因为当同时有几个进程调用lock(key［Ｓ］)时，在x←0语句执行之前，可能已有两个以上的多个进程由于key［Ｓ］=1而进入临界区。为解决这个问题有些机器在硬件中设置了“测试与设置指令，保证第一步和第二步执行不可分离。注意：在系统实现时锁定位key［Ｓ］总是设置在公有资源所对应的数据结构中的。进程互斥（6）试考虑以下进程PA和PB反复使用临界区的情况：PAA：lock(key［Ｓ］)〈Ｓ〉unlock(key［Ｓ］)GotoAPBB：lock(key［Ｓ］)＜Ｓ＞unlock(key［Ｓ］)GotoB设进程ＰA已通过lock(key［Ｓ］)过程而进入临界区。显然，在进程PA执行unlock(key［Ｓ］)过程之前，key［Ｓ］=0且进程PB没有进入临界区的机会。然而，当进程PA执行完unlock(key［Ｓ］)过程之后，由于紧接着是一转向语句，进程PA将又立即去执行lock(key［Ｓ］)过程。此时，由于unlock(key［Ｓ］)过程已将key［Ｓ］的值置为1，也就是开锁状态，从而进程PA又可进入临界区Ｓ。只有在进程PA执行完unlock(key［Ｓ］)过程之后、执行GotoA语句之前的瞬间发生进程调度，使进程PA把处理机转让给进程PB，进程PB才有可能得到执行。然而遗憾的是，这种可能性是非常小的。因此，进程PB将处于永久饥饿状态（starvation）。使用加锁法实现进程间互斥时，还将导致在某些情况下出现不公平现象。进程互斥（7）这正如某个学生想使用某个人人都可借用、且不规定使用时间的教室时一样，他必须首先申请获得使用该教室的权利，然后再到教室看看该教室是不是被锁上了。如果该教室被锁上了，他只好下次再来观察，看该教室的门是否已被打开。这种反复将持续到他进门后为止。从这个例子中，可以得到解决加锁法所带来的问题的方法。一种最直观的办法是，设置一个教室管理员。从而，如果有学生申请使用教室而未能如愿时，教室管理员记下他的名字，并等到教室门一打开则通知该学生进入。这样，既减少了学生多次来去教室检查门是否被打开的时间，又减少了因为学生自发地检查造成的不公平现象。在操作系统中，这个管理员就是信号量。信号量管理相应临界区的公有资源，它代表可用资源实体。进程互斥（8）信号量信号量的概念和下面所述的Ｐ、Ｖ原语是荷兰科学家E.W.Dijkstra提出来的。信号是铁路交通管理中的一种常用设备，交通管理人员利用信号颜色的变化来实现交通管理。在操作系统中，信号量sem是一整数。在sem大于等于零时代表可供并发进程使用的资源实体数，但sem小于零时则表示正在等待使用临界区的进程数。显然，用于互斥的信号量sem的初值应该大于零，而建立一个信号量必须经过说明所建信号量所代表的意义，和赋初值以及建立相应的数据结构以便指向那些等待使用该临界区的进程。进程互斥（9）Ｐ，Ｖ原语信号量的数值仅能由Ｐ，Ｖ原语操作改变(Ｐ和Ｖ分别是荷兰语Passeren和Verhoog的头一个字母，相当于英文的pass和increment的意思)。采用Ｐ，Ｖ原语，可以把类名为Ｓ的临界区描述为WhenＳdoＰ(sem)临界区Ｖ(sem)od。这里，sem是与临界区内所使用的公用资源有关的信号量。一次Ｐ原语操作使得信号量sem减1，而一次Ｖ原语操作将使得信号量sem加1。必须强调的一点是，当某个进程正在临界区内执行时，其他进程如果执行了Ｐ原语操作，则该进程并不像调用lock时那样因进不了临界区而返回到lock的起点，等以后重新执行测试，而是在等待队列中等待有其他进程做Ｖ原语操作释放资源后，进入临界区，这时，Ｐ原语的执行才算真正结束。另外，当有好几个进程执行Ｐ原语未通过而进入等待状态之后，如有某进程作了Ｖ原语操作，则等待进程中的一个可以进入临界区，但其他进程必须等待。进程互斥（10）Ｐ原语操作的主要动作是：(1)sem减1；(2)若sem减1后仍大于或等于零，则进程继续执行；(3)若sem减1后小于零，则该进程被阻塞后与该信号相对应的队列中，然后转进程调度。进程互斥（11）Ｖ原语的操作主要动作是：(1)sem加1；(2)若相加结果大于零，进程继续执行；(3)若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。用Ｐ，Ｖ原语实现进程互斥利用Ｐ，Ｖ原语和信号量，可以方便地解决并发进程的互斥问题，而且不会产生使用加锁法解决互斥问题时所出现的问题。设信号量sem是用于互斥的信号量，且其初值为1表示没有并发进程使用该临界区。显然，由上面几节的讨论可知，只要把临界区置于Ｐ(sem)和Ｖ(sem)之间，即可实现进程间的互斥。当一个进程想要进入临界区时，它必须先执行Ｐ原语操作以将信号量sem减1。在一个进程完成对临界区的操作之后，它必须执行Ｖ原语操作以释放它所占用的临界区。由于信号量初始值为1，所以，任一进程在执行Ｐ原语操作之后将sem的值变为0，表示该进程可以进入临界区。用信号量实现互斥时值的变化wait(s)p1s10-1-2-101criticalsignal(s)wait(s)criticalsignal(s)p2wait(s)criticalsignal(s)p3semaphoreWait操作信号量非负，P1进入临界区Wait操作信号量为负，P2阻塞Wait操作信号量为负，P3阻塞Signal操作后信号量非正，从等待队列中唤醒一个进程Signal操作后信号量非正，从等待队列中唤醒一个进程Signal操作后信号量为正，表示已无进程在临界区用信号量实现两并发进程PA，PB互斥的描述如下：1)设sem为互斥信号量，其取值范围为(1,0,-1)。其中sem=1表示进程PA和PB都未进入类名为Ｓ的临界区，sem=0表示进程PA或PB已进入类名为Ｓ的临界区，sem=-1表示进程PA和PB中，一个进程已进入临界区，而另一个进程等待进入临界区。2）描述：PA：Ｐ（sem）〈Ｓ〉Ｖ（sem）：：：PB：Ｐ（sem）〈Ｓ〉Ｖ（sem）∷：：练习与思考一试用P、V操作实现飞机联网售票系统中各地N个终端的终端售票进程发售同月同日同一次航班机票的过程。例：设余票单元为count，有N个售票进程正确并发执行的算法ProcessPi(i=1,2,…n)Beginbegincount:integer;s:semaphore;VarXi:integer;s:=1;按旅客要求找到count;cobeginP(s);P1;Xi:=count;P2;IfXi=1then……beginPn;Xi:=Xi-1;coendXi:=count;end.V(s);输出一张票;EndElse输出“