计算机操作系统课件第二章课件.ppt

第二章 进程管理2.1 为什么要引入进程的概念2.1.1 程序顺序执行程序一般可分成三个部分：输入部分:以I表示;计算部分:以C表示;输出部分:以P表示。程序顺序执行的示意图为：I1C1P1I2C2P2InCnPn对于一个程序段中的多条语句来说，也有一个执行顺序问题。例：三条语句的程序段：S1：a:=x+yS2：b:=a-5S3：c:=b+1S2必须在a被赋值后才能执行;同样S3也只有在b程序被赋值后才能执行。程序顺序执行的特点：顺序性、封闭性、可再现性。封闭性指程序一旦开始执行其结果只取决于程序本身。2.1.2 程序并行执行 程序的I、C、P三者之间存在IiCiPi这样的前趋关系，对一个作业的输入、计算、打印三个操作，必须顺序执行，但并不存在Pi Ii+1关系，因而在对一批程序处理时，可使它们并发执行。程序并发执行的前趋图：I1I2I3I4C1C2C3C4P1P2P3P4(输入设备)(CPU)(输出设备)并发执行是指两个程序的执行在时间上是重叠的。例1：有两个循环程序A和B，共享一个变量N。程序A每执行一次做：N:=N+1程序B每执行一次做：print(N)，然后置N:=0程序A和B独立地并行工作,可能出现三种情况(假定某时刻N的值为n)：N:=N+1在print(N)和N:=0之前,得到N的值分别为:n+1,n+1,0。N:=N+1在print(N)和N:=0之后,得到N的值分别为:n,0,1。N:=N+1在print(N)和N:=0之间,得到N的值分别为:n,n+1,0。并发程序已与程序的执行顺序有关，失去了封闭性和可再现性。程序是指令的有序集合,是静态的概念。机器执行程序的活动称为”计算”,”计算”是动态的概念。当一个并发程序可为多个用户作业调用,而使该程序处于多个“执行”中,从而形成多个“计算”。所以程序与“计算”不再一一对应。例2：有下述四条语句的程序段：S1：a:=x+2S2：b:=y+4S3：c:=a+bS4：d:=c+6 可见，S3必须在a和b被赋值后才能执行；S4必须在S3之后执行，但S1和S2可以并发执行，因为它们彼此互不依赖。(相互制约性)S1S2S3S4 并发执行的特点：相互制约性、失去封闭性、不可再现性。直接制约关系通常是在彼此之间有逻辑关系的两个并发执行的程序之间发生。间接方式发生制约关系是由竞争使用同一资源引起的,得到资源的程序可继续执行,得不到资源的程序只好暂停等待。程序或程序段并发执行的条件：若两个程序段p1、p2能满足下述条件，它们便能并发执行，具有可再现性。该条件称为Bernstein条件。R（p1）W（p2）R（p2）W（p1）W（p1）W（p2）=R（p1）p1的读集、W（p2）p2的写集、“与”运算、“和”运算 空集。例：S1：a:=x+y R（S1）=x，y，W（S1）=a S2：b:=z+1 R（S2）=z，W（S2）=b S3：c:=a-b R（S3）=a，b，W（S3）=c S4：w:=c+1 R（S4）=c，W（S4）=w S1和S2可以并发执行，S1和S3、S2和S3、S3和S4均不能并发执行。2.1.3 进程概念的引入一、引入进程的目的：在多道程序的环境下,程序的并发执行代替了程序的顺序执行,它破坏了程序的封闭性和再现性,使得程序和计算不再一一对应,而且由于资源共享和程序的并发执行导致在各个程序活动之间可能存在相互制约的关系。程序活动不再处于一个封闭系统中,出现了许多新的特征即独立性、并发性、动态性及相互制约性。在这种情况下，程序这个静态概念已经不能如实反映程序活动的这些特征，所以引入了进程这一概念。为了使程序在多道程序环境下能并发执行，并能对并发执行的程序进行控制和描述，而专门为之配置了一个称为“进程控制块”的数据结构。二、进程的定义：进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。三、进程的特征：动态性：进程从产生到执行,再到消亡,是有生命的、动态的。并发性：程序不能并发执行。独立性：进程实体是一个能独立运行的单位,同时也是系统中能独立获得资源和独立调度的基本单位。异步性：进程按各自独立的不可预知的速度向前推进。四、进程和程序的区别 1）进程是一个动态概念,程序是静态概念,程序是指令的有序集合,无执行含义,进 程则强调执行的过程。2）进程具有并行特征(独立性、异步性),程序则没有。3）不同的进程可以包含同一个程序，同一程序在执行中也可以产生多个进程。2.2 进程的表示和调度状态2.2.1 进程的表示1.进程的组成进程通常由程序、数据集和进程控制块(Process Control Black,记为PCB)组成。进程的程序部分描述了进程所要完成的功能。数据集部分包括程序在执行时所需的数据和工作区。程序和数据集是进程存在的物质基础,即进程的实体。进程控制块包含进程的描述信息和控制信息，是进程的动态特性的集中反映。2.进程控制块为描述进程的动态变化，便于系统对进程进行有效的控制和管理，系统中为每一进程设置一个进程控制块。进程控制块是进程存在的惟一标志。当系统创建一个进程时，系统为其创建一个PCB，当进程被撤消时，系统收回它的PCB，该进程就消亡了。不同的操作系统其PCB的格式和所含的信息不同。一般PCB含如下的信息：进程标识名或标识号:系统中每个进程由唯一的表示符,以便系统识别。位置信息:进程的程序和数据部分在内存或外存中的物理位置。状态信息:进程当前所处的状态(执行、就绪、阻塞等)。进程的优先级:进程现场保护区:当进程暂时不在CPU上运行时各状态保护起来，以便再次进入CPU时恢复现场。资源清单:指出资源需求、分配和控制信息。队列指针或链接字:用于将处于同一状态的进程链接成一个队列,在该单元中存放下一进程的PCB首址。其它信息：视系统而定。2.2.2 进程的调度状态在多处理系统中,用进程调度来确定哪个进程将得到CPU的控制。调度分为3个阶段：长期、中期和短期。长期调度也叫做作业调度，确定哪些作业或进程可以竞争系统资源。通常一旦作业调度程序使某作业成为活动的，那么这个作业会一直保持活动状态直到作业完成为止。作业调度程序的主要目标是给中期调度程序提供适当数量的作业。如果作业数量太少，当所有作业都被阻塞时CPU会闲置。如果作业过多，存储管理系统可能过载从而降低系统效率。中期调度程序也叫交换程序，把进程调入调出内存。支持多处理的存储管理系统都可以使用交换机制，这样在内存中可以有超出物理容量的更多进程数以共享系统。页面调度这样的存储管理系统甚至通过将整个进程换出内存限制竞争内存的进程数。短期调度程序也就是调度程序，把CPU分配给已装入主存准备运行的进程。通常调度程序按固定的最大时间片分配CPU。进程用完分配给它的时间片后必须释放CPU，回到进程池，调度程序从进程池中挑选执行的进程。在多线程系统中，短期调度有多种调度方式。短期调度程序用线程调度而不是进程调度。然而短期调度也可以是两级调度，就是进程调度中还有线程调度。由于一个进程中的线程共享内存和其他资源，所以进程中的线程切换比“重进程”(或不同进程的线程)之间切换的开销要小得多。1.进程的基本调度状态 运行状态(running)。进程在CPU中运行时的状态。就绪状态(ready)。进程在等待CPU的状态。阻塞状态(blocked)。正在CPU上运行的进程因某种原因而暂停运行并等待其他的资源被释放时的状态。进程的基本调度状态及其转换就绪执行:由进程调度程序调度。运行阻塞:在CPU中的进程请求其他服务。一般由运行进程自己主动提出。例如:进程在运行过程中需要某一条件而不能满足时，就自己主动放弃CPU进入阻塞。运行就绪:时间片到或另一个优先权高的进程来抢占。阻塞就绪:I/O服务完成。总是由外界事件引起的,而不是由该事件自己引起的。阻塞 运行:必须经过“就绪”。因为该进程阻塞解除时,系统中可能有多个进程都处于逻辑上可执行状态。系统必须根据一定的算法选择一个就绪进程占用CPU。这种选择过程称为进程调度。2.细分进程的调度状态 细分方法A就绪状态可细分为低优先级就绪、中优先级就绪和高优先级就绪。阻塞状态细分为因等待盘、带的I/O而阻塞，因等待终端的I/O而阻塞和因等待页面的I/O而阻塞。细分的进程状态转换图 细分方法B将基本调度状态的就绪和阻塞细分为活跃的和静止的两部分。这是因为有时需要人为的把正在运行或没有运行的进程挂起(suspend),使其处于静止状态(正在运行的进程停止运行,没有运行的进程不再运行)。系统的三种基本调度状态演变为五种调度状态:运行、活跃就绪、活跃阻塞、静止就绪和静止阻塞。具有挂起操作的进程状态转换图2.3 进程的控制2.3.1 进程的控制结构OS采用层次化的模块结构，一般将与硬件紧密相关的模块安排在同一个软件层次中，并使它们常驻内存(以便提高OS的运行效率，并对它们加以特殊的保护),通常把这一部分称为OS的内核。内核不是进程。中断处理 支撑部分 时钟管理 原语操作 OS内核 进程管理 资源管理部分 存储管理 设备管理原语：一段紧凑不可分割(不可被中断)的指令组。内核中包含的原语主要有进程控制原语、进程通信原语、资源管理原语和其它方面的原语。属于进程控制方面的原语有进程创建原语、进程撤消原语、进程挂起原语、进程激活原语、进程阻塞原语和进程唤醒原语。2.3.2 进程控制原语1.进程的建立建立进程的两种方法：在系统生成时建立起一些系统进程。利用创建原语来创建一个新进程。一个进程必须由其父进程来创建，而父进程由其祖先进程创建。即父进程创建子进程，子进程创建孙进程。形成进程树。树型结构系统的主要优点是:资源分配严格。子进程仅能分配到父进程所拥有的资源,用完立即归还。进程控制灵活。给进程不同的控制权。进程可建立子进程分担子任务，且可并发地执行。进程层次清晰，关系明确。进程创建原语(CREAT()步骤：进程的树型结构2.状态转换原语挂起原语。当需要把某个进程挂起时调用此原语。对于树型结构系统，被挂起的进程只能是它的子孙或其自身。若进程状态为：“运行”：把CPU状态保存在PCB中，停止运行该进程,并把其状态改为静止就绪。并从活跃就绪进程队列中选一进程投入运行。“活跃阻塞”：改为静止阻塞。“活跃就绪”：改为静止就绪。激活原语。把静止就绪改为活跃就绪或静止阻塞改为活跃阻塞。激活原语只能激活某进程自己的子孙。阻塞原语和唤醒原语。由“运行”“活跃阻塞”“活跃就绪”通常是在资源管理原语“请求”和“释放”的作用下完成。但有的系统使用阻塞原语和唤醒原语完成上述转换。当一进程所期待的某一事件尚未出现时，该进程调用阻塞原语把自己阻塞起来。当某进程所期待的事件出现时，由“发现者”进程调用唤醒原语。发现者进程可能与被唤醒进程不直接相干，但通常与唤醒进程是合作的并发进程。阻塞原语(BLACK()步骤：唤醒原语(WAKEUP()步骤：提出者：进程自己 执行者：其它进程(“发现者”进程)3.进程的撤消当一个进程完成其任务后，应予以撤消，以便及时释放它所占用的资源。撤消原语(KILL()步骤：2.4 进程调度2.4.1 交通控制程序和进程调度程序1.交通控制程序在操作系统中，交通控制程序的主要职能是管理进程状态之间的转变和协调进程间的通讯。2.进程调度程序该程序实现进程从就绪运行状态的转变。进程调度程序所要完成的是把一台物理的CPU转变为多台虚拟的CPU或多台逻辑的CPU。3.进程调度程序的功能记住系统中所有进程的状态、优先数和资源需求情况。确定调度算法，决定把处理机分配给哪个进程和分配多长时间。分配处理机给进程。进程调度程序是操作系统的真正核心。2.4.2 进程调度算法的设计1.引起进程调度的时机现运行进程运行结束或因任务完成而正常结束,或因出错而异常结束。现运行进程因某种原因从运行进入阻塞状态。现运行进程因执行某种原语进入阻塞状态。一个具有更高优先级的进程要求使用处理机。分配给该进程运行的时间片已用完。2.进程调度方式 非剥夺方式(非抢占式)。原来运行的进程继续运行直至该进程完成或发出某事件而进入完成或阻塞状态时才主动放弃自己的处理机。剥夺方式(抢占式)。现运行进程在运行过程中，如有更高优先级的进程到达，则现运行进程被迫放弃处理机，处理机立即分配给新进程。3.进程调度算法的选择进程调度算法基本分为两大类：优先级法和时间片轮转法。4.进程队列的组织链接表或进程队列方式可使PCB的数目不受限制，可动态申请或释放。由于各队列分开，因此管理方便。缺点是动态分配PCB所占内存的算法比较复杂，指针占用额外存储空间，费时。2.4.3 常用的进程调度算法1.静态优先级法如果在进程创建时就确定了优先级，且在运行过程中不再动态改变，这种优先级法称为静态优先级法。优先级的确定方法:按进程类型确定。系统类型(优先级高)、用户类型。按作业的资源要求确定。如要求CPU时间和内存空间少的进程优先(短进程优先算法SPF Shortest Process First)。按作业到达的时间确定。先来先服务算法(FCFS First-Come First-Served)按用户类型和要求确定。用户可购买作业优先权数，以高代价取得系统照顾。作业 情况调度算法进程名ABCDE平均到达时间01234服务(执行)时间43524 FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8 SPF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.1周转时间T:指进程提交给系统开始,到进程完成为止的时间间隔。T进程等待时间+进程执行时间完成时间提交(到达)时间。带权周转时间W:W=进程周转时间/进程执行时间。W越小越好 进程等待时间P:P=进程周转时间-进程执行时间。SPF 平均周转时间 0)s.count=s.count-1;elses.queue.Insert();/Block this processvoid V(semaphore s)if(s.queue.empty()s.count=s.count+1;elses.queue.Remove();/Schedule a process,if any,blocked on s 信号量是非负的整数变量。信号量操作有时也称为Down和Up,或Wait和Signal。2.利用信号量实现进程的互斥设S为两进程互斥的公用信号量,初值为1,表明该临界资源末被占用。只需把临界区的程序段置于P(S)和V(S)之间,即可实现两进程互斥。进程P1进程P2P(S)P(S)S1 /(临界区)S2 /(临界区)V(S)V(S)例：有一单向行驶的公路桥,每次只允许一辆汽车通过。当汽车到达桥头时,若桥上无车便可上桥;否则,需等待,直到桥上的汽车下桥为止。若每一辆汽车为一个进程,请用P,V操作编程实现。解：公路桥是1个临界资源,由于它每次只允许一辆汽车通过,故可为它设置一个初值为1的临界资源mutex。汽车过公路桥的动作可描述为：Semaphore mutex=1;CrossBridge()begin行驶到桥头;P(mutex);上桥行驶,从另一头下桥;V(mutex);end;beginS:semaphore；S:=1;cobeginPROCESS Pi /(i=1,2,n)begin按旅客要求找到Xj;P(S);Ri :=Xj；If Ri=thenbegin Ri:=Ri 1;Xj:=Ri；V(S);输出一张票;end elsebegin V(S);输出“票已售完”;end；end；coend；end;例:设一民航航班售票系统有n个售票处,每个售票处通过终端访问系统的公共数据区,假定公共数据区中一些单元X(j1,2,3)分别存放月日次航班的现存票数。用P1,P2,Pn表示各售票处为旅客服务时的处理进程,R1,R2Rn为各进程执行时所用到的工作单元(变量)。当售票处有旅客买票时，进程如下工作：3.利用信号量实现进程间的同步设S为两进程的信号量,初值为0。进程P1受进程P2制约。进程P1进程P2L1:P(S)L2:V(S)例:用信号量实现司机和售票员的同步。设S1和S2分别为司机和售票员的私用信号量，初值均为0。合作进程的执行次序：例：PA、PB、PC为一组合作进程，其前驱图如右：要求PA执行结束后，PB、PC才能执行。设两个信号量SB、SC分别表示进程PB、PC能否开始执行，初值为SB=0、SC=0。PA：PB：PC：P（SB）P（SC）V（SB）V（SC）共享单缓冲区的两个进程的同步问题：例：设一计算进程IC和一打印进程OP共用一个单缓冲，如图所示。IC进程负责不断地计算数据并输入缓冲区T中，OP进程负责从缓冲区T中取出数据去打印。同步约束：OP进程只有在IC进程将数据输入缓冲区后，才能取出打印。IC进程只有在OP进程将数据取出打印后，才能送入下一个计算数据。SA=0；/SA信号量表示缓冲区中有无信息（初始无数据）SB=1；/SB信号量表示缓冲区中有无空位（初始有空位）4.生产者消费者问题生产者消费者问题是很多并发进程间存在的内在关系的一种抽象。假定这些生产者和消费者是互相等效的,只要缓冲区未满,生产者就可把产品送入缓冲;类似地,只要缓冲区未空,消费者便可从缓冲区取走产品并消耗它。仅当缓冲区满时生产者被阻塞;类似地,缓冲区空时消费者被阻塞。问题：生产者、消费者同步问题生产者之间(或消费者之间)都会选中同一共享资源:缓冲单元互斥问题。设：公用信号量S初值为1,表示没有进程进入临界区,用于实现进程互斥。私有信号量S0,表示产品数量,初值为0。私有信号量Sn,表示可用缓冲区数,初值为n。begin B:array0.n-1 of integer;/int Bn;p,r:integer;/存、取产品的位置 S,Sn,S0:semaphore;p:=r:=0;S:=1;Sn:=n;S0:=0;cobeginprocess produceri(i=1,2,m)begin L1:produce a product;P(Sn);P(S);Bp:=product;p:=(p+1)mod n;V(S0);V(S);goto L1;endprocess consumerj(j=1,2,k)begin L2:P(S0);P(S);take a product from Br;r:=(r+1)mod n;V(Sn);V(S);consume;goto L2;end coend;End;begin S,Sr:semaphore；/(分别为对共享资源file和rc的信号量)rc:integer;/(在读文件的人数,计数器,是共享变量)S:=1;Sr:=1;rc:=0;cobegin PROCESS Readeri(i=1,2,)begin P(Sr);rc:=rc+1;if rc=then P(S);/第一个读者对写加锁 V(Sr);read file F;P(Sr);rc:=rc -1;if rc=0 then V(S);/最后一个读者对写解锁 V(Sr);end;5.读者与写者问题 一个文件F供多个进程读写,要求:写时需独占;读时可共享。PROCESS Writerj(j=1,2,)begin P(S);write file F；V(S);end；coend;end;说明:该程序的问题:当有进程在读而使一个写进程阻塞时,如果仍有进程不断地请求读,则写进程将被长期地推迟运行。而实际情况是希望写者优先。即有进程在读时，如有进程请求写，那么新的读者被拒绝。begin S,Sn:semaphore；/(S用于互斥,Sn=n表示最多有n个进程可同时读操作)S:=1;Sn:=n;cobegin PROCESS Readeri(i=1,2,)begin P(S);P(Sn);V(S);read file F;V(Sn);end;PROCESS Writerj(j=1,2,)begin P(S);for i:=1 to n do P(Sn);/如果写P操作成功,则对所有读进行P操作,只有P操作成功才能进行写操作,/因此只有在写操作前进行的读操作可执行完成,以后的读必须等写完成后才能执行。write file F；for i:=1 to n do V(Sn);V(S);end；coend;end;2.5.3 高级通讯原语低级通讯：交换的数据量少(P,V操作)。目的是控制进程执行速度。高级通讯：交换的数据量大。目的是交换信息。消息缓冲方式和信箱通讯方式。1.消息缓冲通讯发送进程直接将消息挂在接受进程的消息队列上。(1)message数据结构（缓冲区的几个域）：发送消息的进程标识：sender;消息的长度：size;消息正文：text;指向下一消息缓冲区的指针：next;(2)PCB中相应的数据项：消息队列队首指针：mq;消息队列互斥信号量：mutex;/进入临界区时P(mutex)操作,离开时V(mutex)操作消息队列资源信号量：sm;/放消息时V(sm)操作，取消息时P(sm)操作(3)发送原语send(receiver,addr);receiver:接收进程的标识符,addr:发送区始址。发送区包括:发送进程标识，消息长度和消息正文。(4)接收原语receive(addr);addr:接收区始址。接收区包括:发送进程标识，消息长度和消息正文。消息缓冲通讯 若消息队列容量N，发送进程申请不到缓冲区，发送进程阻塞。若消息队列的消息为0，接收进程接收不到消息，接收进程阻塞。2.信箱通讯信箱用于存放信件，而信件是一进程发送给另一进程的消息。(1)信箱通讯过程 发送进程将消息发到一中间实体(称为信箱)，接收进程从中获取。发信的进程主要把预处理的信笺投入信箱，而不必过问是谁来接收及处理。同样，接收进程只关心取信笺处理，也不必知道是谁发来的。每个信箱有一个唯一的标识符。(2)信箱的数据结构 信箱由信箱头和信箱体组成。信箱的拥有者为接收进程，信箱名、信箱大小在创建信箱时确定。mesnum是接收进程的私有信号量，初值为0。fromnum是发送进程的私有信号量，初值为boxsize。mutex是该邮箱的互斥信号量,初值为1。(3)发送原语和接收原语 send(boxname,msg);receive(boxname,msg);(4)原语的实现信箱名：boxname信箱大小：boxsize已存信件数：mesnum空格子数：fromnum满信件满信件满信件空格子空格子send(boxname,msg)beginlocal X;根据boxname找到信箱;P(fromnum);P(mutex);选择标志为空不格子;把消息msg放入空的格子X中;置格子X为满标志;V(mutex);V(mesnum);endreceive(boxname,msg)beginlocal X;根据boxname找到信箱;P(mesnum);P(mutex);选择标志为满的格子X;将格子X中的信件取出放入msg中;置格子X的标志空;V(mutex);V(fromnum);end2.6 死锁 当某一进程提出资源的使用要求后,使得系统中一些进程处于无休止的阻塞状态,在无外力的作用下,这些进程永远也不能继续前进,这种现象称死锁。2.6.1 死锁的起因和产生死锁的必要条件 1.死锁的起因临界资源：Y1,Y2进程Pa 进程Pb P(SY1)占用Y1 P(SY2)占用Y2 P(SY2)要用Y2 P(SY1)要用Y1 V(SY2)V(SY1)V(SY1)V(SY2)进程Pa,Pb无法继续前进,出现死锁。进程Pa 进程Pb P(SY1)占用Y1 P(SY1)占用Y1 P(SY2)要用Y2 P(SY2)要用Y2 V(SY2)V(SY2)V(SY1)V(SY1)当进程争夺资源时,有可能产生死锁,但不一定就会死锁,这取决于各进程推进的速度和对资源请求的顺序,因此,死锁是一种与时间有关的错误。2.产生死锁的必要条件1971年Coffman提出了可逐次再使用资源产生死锁的必要条件是：互斥控制进程对其所要求的资源进行排它控制，一个资源仅能被一个进程独占。非剥夺控制进程所获得的资源在未释放之前,不能被其它进程强行剥夺,只能有该进程自己释放。逐次请求进程以随意的零星方式逐次取得资源,而不是集中性的一次请求,这有利于提高资源的利用率。环路条件在发生死锁时，其有向图必构成环路，即前一进程保持着后一进程所要求的资源。只要破坏上述四个条件之一，即可预防死锁的发生。2.6.2 死锁举例P、V操作引起的死锁进程A进程B启动读卡机P(S1)卡片送入缓冲区 从缓冲区取卡片信息P(S2)V(S2)V(S1)加工卡片信息初始时S1=0;S2=0;存储器共享的死锁假定系统中有m个单位的存储器，它为n个进程所共享。若每个进程都要求i个存储单位，当 mn*i 时就可能发生死锁。加锁法引起的死锁进程P1进程P2LOCK(W)LOCK(W)若P1,P2优先级不同，S1S2 也可能发生死锁。UNLOCK(W)UNLOCK(W)哲学家吃通心面问题(Dining Philosophers Problem)有五个哲学家围坐在一圆桌旁,桌中央有一盘通心面,每人面前有一只空盘子,每两人之间放一根筷子。每个哲学家思考、饥饿,然后吃通心面。但是每个哲学家必须获得两根筷子(只能从自己左边和右边取筷子)才能吃到通心面。P0.4对应五个哲学家，r0-r4对应五根筷子，S0 S4对应取五根筷子的互斥信号量，初值为1。对于第i个哲学家可取左边(i)和右边(i+1)的筷子。设i+1的操作为i=(i+1)mod 5;begin S:array0.4 of semaphore;S0:=S1:=S2:=S3:=S4:=1;cobegin process Pi(i=04)begin Li:thinking;hungry;P(Si);pickup riP(Si+1);pickup ri+1eating;putdown riputdown ri+1;V(Si);V(Si+1);goto Li;end;coend;end;此算法采用先取左边的筷子,再取右边的筷子,可能会出现每人都取到左边的筷子而取不到右边的,从而形成死锁。2.6.3 死锁的预防只要打破互斥控制、非剥夺控制、逐次请求和环路条件之一，即可预防死锁。对于后两种条件可采用如下两种方法解决：资源静态分配法 进程在运行之前一次申请它所需的全部资源。优点：简单、安全。缺点：资源利用率低。资源顺序分配法 对系统的全部资源加以全局编号。使用时，所有进程对资源的申请必须严格按资源的序号递增的次序提出。例如：在哲学家吃通心面问题中，五根筷子编号为r0,r1,r2,r3,r4。对于P0-P3必须先申请ri,然后申请ri+1,对于P4必须先申请r0,然后申请r4,就可防止死锁。2.6.4 死锁的避免 只要系统在分配资源时自始至终地作出正确的选择就能避免死锁。银行家算法：银行家占有有限资金，不可能满足所有借款人的最大需求量的总和，但可以满足一部分借款人的借款要求。待这些人的借款归还后又可把这笔资金借给他人。当有人提出借款要求时，银行家就要计算，以决定是否借给他，看是否会造成银行家的资金被借光而使资金无法周转。例程客户已贷款额最大贷款额A06B05C04D07客户已贷款额最大贷款额A16B25C24D47客户已贷款额最大贷款额A16B15C24D47设银行家有金额为10。余额为2,安全余额为1,不安全检查状态是否安全:看是否有足够的资源满足一个距最大需求最近的客户。银行家算法中的数据结构:进程运行标志Finish1.n:表示系统是否有足够的资源分配给进程。有足够的资源时:Finishi=1。算法开始时：Finishi=0各资源总数W1.m:每一个元素表示一类可分配资源总数。最大需求数Max1.n1.m:n个进程中的每一个进程对m类资源的最大需求。已分配资源R1.n1.m:每一类资源当前已分配给每一进程的资源数。尚需资源Q1.n1.m:每一个进程尚需的各类资源数。可用资源S1.m:表示系统可供进程继续分配的各类资源数目。例：假设系统中有五个进程P0，P1，P2，P3，P4和三种资源A，B，C，每一种资源的数量分别为W(10，5，7)。在T0时刻的资源分配情况如下：Max R Q S(3,3,2)Finish()A,B,C A,B,C A,B,C P0 7 5 3 0 1 0 7 4 3 P1 3 2 2 2 0 0 1 2 2P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1判断T0时刻是否安全？S R Q S+Ri Finish()A,B,C A,B,C A,B,C A,B,C P1 3 3 2 2 0 0 1 2 2 5 3 2 1P3 5 3 2 2 1 1 0 1 1 7 4 3 1P0 7 4 3 0 1 0 7 4 3 7 5 3 1P2 7 5 3 3 0 2 6 0 0 10 5 5 1P4 10 5 5 0 0 2 4 3 1 10 5 7 1_系统在T0时刻安全，有一个可能的安全序列P1，P3，P0，P2，P4 此时假如P1提出请求向量Req=(1,0,2),系统能分配给它吗？Max R Q S(2,3,0)Finish()A,B,C A,B,C A,B,C P0 7 5 3 0 1 0 7 4 3 P1 3 2 2 3 0 2 0 2 0P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1判断此时刻是否安全？S R Q S+Ri Finish()A,B,C A,B,C A,B,C A,B,C P1 2 3 0 3 0 2 0 2 0 5 3 2 1P3 5 3 2 2 1 1 0 1 1 7 4 3 1P0 7 4 3 0 1 0 7 4 3 7 5 3 1P2 7 5 3 3 0 2 6 0 0 10 5 5 1P4 10 5 5 0 0 2 4 3 1 10 5 7 1_系统在此时刻安全，有一个可能的安全序列P1，P3，P0，P2，P4 此时假如P0提出请求向量Req=(0,2,0),系统能分配给它吗?Max R Q S(2,1,0)Finish()A,B,C A,B,C A,B,C P0 7 5 3 0 3 0 7 2 3 P1 3 2 2 3 0 2 0 2 0P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1判断此时刻是否安全?因为此时系统可用资源数S(2,1,0)已不能满足任何进程的需求,故可得知系统进入不安全状态,此时系统不能进行分配,即系统不能满足P0提出的请求向量(0,2,0)。_系统在此时刻不安全。2.6.5 死锁的检测系统设置：资源分配表S进程等待表D资源号占用进程12IKIK进程号请求资源号KIJI检测方法：系统每分配一个资源,就在S表中登录一次。当资源使用完毕,相应内容在S表中删除。例：若K进程请求I资源得到满足，在S表中登录IK。若J进程请求I资源得不到满足，在D表中登录JI。查原因(查S表)得I已被进程K占用。查K进程是否在等待分配资源：否其他原因、是有可能死锁 查D表，K进程在等待I资源。再查S表得I资源被K占用，若J=K 则构成 IKIJI的环路条件。所以J、K进程死锁。2.7 线程2.7.1 线程概念的引入操作系统中引入进程概念的目的在于提高系统效率，提高系统资源利用率。进程的两个基本属性：进程是一个可拥有资源(如：内存区域、外存单元)的独立单位。进程同时又是可以独立调度和分派的基本单位。由于属性，在进程的创建、撤消和切换中，系统必须为之付出较大的时空开销(CPU为OS服务的时间、内存为OS服务的空间)，所以进程管理中，进程数目不宜过多，进程切换的频率也不宜过高。这样就限制了并发程度的进一步提高。解决方法：将上述属性分开,引入线程只作为独立调度和分派的基本单位(如：使用相同资源的程序合并为一个进程，其中的一个功能作为一个线程)。结果：轻装前进。对拥有资源的基本单位(进程)又不频繁地切换(此时，频繁切换的是线程)。2.7.2 什么是线程 1.线程的定义线程是进程中的一个实体,是被系统独立调度和分派的基本单位。说明：线程自己基本上不拥有资源，只拥有一点在运行过程中必不可少的资源。如程序计数器、一组寄存器和栈。但它可与同属一个进程的其他线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程，同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中也呈现出间断性，所以线程有“就绪”、“执行”、“阻塞”三个状态。2.进程和线程的关系3.线程是进程的一个组成部分。每个4.进程创建时通常只有一个线程。5.进程的多线程都在进程的地址空间活动。6.资源是分给进程的而不是分给线程的。7.处理机调度的基本单位是线程，线程之间8.竞争处理机，真正在处理机上运行的是线程。#define N5/哲学家人数#define LEFT(i+N-1)%N/i的左邻编号#define RIGHT(i+1)%N/i的右邻编号#define THINKING0#define HUNGRY1/试图拿起筷子#define EATING 2intstateN;/跟踪记录每位哲学家的状态Semaphore mutex=1;/临界区信号Semaphore sN;/每个哲学家一个信号量void philosopher(int i)/i:哲学家编号 while(TRUE)thinking();take_forks(i);eating();put_forks(i);void take_forks(int i)down(&mutex);/进入临界区 statei=HUNGRY;/记录哲学家i处于饥饿状态 test(i);/尝试取2根筷子 up(&mutex);/离开临界区 down(&si);/如果得不到需要的筷子则阻塞void put_forks(int i)down(&mutex);/进入临界区 statei=THINKING;/哲学家已用餐完毕 test(LEFT);/检查左边邻居现在可吃吗 test(RIGHT);/检查右边邻居现在可吃吗 up(&mutex);/离开临界区void test(int i)if(statei=HUNGRY&stateLEFT!=EATING&stateRIGHT!=EATING)statei=EATING;up(&si);每个进程将过程philosopher()作为主代码运行,take_forks(),put_forks()和test()只是普通过程,而非单独的进程。返回