进程管理.doc

第三章 进程管理一、 进程的基本概念(一) 进程概念的引入多道程序在执行时，需要共享系统资源，从而导致各程序在执行过程中出现相互制约的关系，程序的执行表现出间断性的特征。这些特征都是在程序的执行过程中发生的，是动态的过程，而传统的程序本身是一组指令的集合，是一个静态的概念，无法描述程序在内存中的执行情况，即我们无法从程序的字面上看出它何时执行，何时停顿，也无法看出它与其它执行程序的关系，因此，程序这个静态概念已不能如实反映程序并发执行过程的特征。为了深刻描述程序动态执行过程的性质，人们引入“进程（Process）”概念。从理论角度看，是对正在运行的程序过程的抽象；从实现角度看，是一种数据结构，目的在于清晰地刻划动态系统的内在规律，有效管理和调度进入计算机系统主存储器运行的程序。(二) 进程的概念1. 解释进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源，是一个动态的概念，是一个活动的实体。它不只是程序的代码，还包括当前的活动，通过程序计数器的值和处理寄存器的内容来表示。主要有两点：第一，进程是一个实体。每一个进程都有它自己的地址空间，一般情况下，包括文本区域（text region）、数据区域（data region）和堆栈（stack region）。文本区域存储处理器执行的代码；数据区域存储变量和进程执行期间使用的动态分配的内存；堆栈区域存储着活动过程调用的指令和本地变量。第二，进程是一个“执行中的程序”。程序是一个没有生命的实体，只有处理器赋予程序生命时，它才能成为一个活动的实体，我们称其为进程。进程是操作系统中最基本、重要的概念。是多道程序系统出现后，为了刻画系统内部出现的动态情况，描述系统内部各道程序的活动规律引进的一个概念,所有多道程序设计操作系统都建立在进程的基础上。2. 进程的特征动态性：进程的实质是程序的一次执行过程，进程是动态产生，动态消亡的；并发性：任何进程都可以同其他进程一起并发执行；独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位；异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进；结构特征：进程由程序、数据和进程控制块三部分组成。3. 进程与程序的区别1、程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。2、程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的。3、进程更能真实地描述并发，而程序不能；4、进程是由进程控制块、程序段、数据段三部分组成;5、进程具有创建其他进程的功能，而程序没有。6、同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程。 7、在传统的操作系统中，程序并不能独立运行，作为资源分配和独立运行的基本单元都是进程。4. 进程实体(1) 基本组成1、程序：描述该进程所要完成的功能。如果一个程序被多个进程共享，那么该进程代码在执行过程中不应该被修改，即程序代码是可重入的。2、数据集合：进程执行时的操作对象和场所。3、进程控制块（PCB）：进程存在的唯一标识：记录进程生命周期内状态变化的重要数据结构，是进程管理的依据。(2) 进程控制块包含的信息系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。在不同的操作系统中对进程的控制和管理机制不同，PCB中的信息多少也不一样，通常PCB应包含如下一些信息。1、进程标识符：每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。2、进程当前状态：说明进程当前所处的状态。为了管理的方便，系统设计时会将相同的状态的进程组成一个队列，如就绪进程队列，等待进程则要根据等待的事件组成多个等待队列，如等待打印机队列、等待磁盘I/O完成队列等等。3、存储指针：进程相应的程序和数据地址，以便把PCB与其程序和数据联系起来。4、占用资源表：列出所拥有的除CPU外的资源记录，如拥有的I/O设备，打开的文件列表等。5、进程优先级：进程的优先级反映进程的紧迫程度，通常由用户指定和系统设置。6、现场保护区：当进程因某种原因不能继续占用CPU时（如等待打印机），释放CPU，这时就要将CPU的各种状态信息保护起来，为将来再次得到处理机恢复CPU的各种状态，继续运行。7、通信信息：用于实现进程间互斥、同步和通信所需的信号量等。8、进程所在队列PCB的链接字：根据进程所处的现行状态，进程相应的PCB参加到不同队列中。PCB链接字指出该进程所在队列中下一个进程PCB的首地址。9、族系关系：记录本进程的父进程（创建该进程的进程）和子进程（该进程创建的进程）的进程标识符。10、与进程有关的其他信息。 如进程记账信息，进程占用CPU的时间等。(3) 进程控制块的组织方式1、线性表方式：不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。2、索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。3、链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列等。5. 进程切换进行进程切换就是从正在运行的进程中收回处理器，然后再使待运行进程来占用处理器。这里所说的从某个进程收回处理器，实质上就是把进程存放在处理器的寄存器中的中间数据找个地方存起来，从而把处理器的寄存器腾出来让其他进程使用。那么被中止运行进程的中问数据存在何处好呢？当然这个地方应该是进程的私有堆栈。让进程来占用处理器，实质上是把某个进程存放在私有堆栈中寄存器的数据（前一次本进程被中止时的中间数据）再恢复到处理器的寄存器中去，并把待运行进程的断点送入处理器的程序指针PC，于是待运行进程就开始被处理器运行了，也就是这个进程已经占有处理器的使用权了。这就像多个同学要分时使用同一张课桌一样班主任说是要收回正在使用课桌的同学的课桌使用权，实质上就是让他把属于他的东西拿走，而赋予某个同学课桌使用权，只不过就是让他把他的东西放到课桌上罢了。在切换时，一个进程存储在处理器各寄存器中的中间数据叫做进程的上下文，所以进程的切换实质上就是被中止运行进程与待运行进程上下文的切换。在进程未占用处理器时，进程的上下文是存储在进程的私有堆栈中的。(三) 进程状态1. 进程状态进程的基本状态只有三种：运行态、就绪态和阻塞态。运行态表示进程已经获得CPU资源，相关程序正在运行。就绪态是指该进程已经做好一切准备，进入了就绪队列，而阻塞态是程序因为某种原因退出运行转而阻塞，等待条件得到满足时进入就绪态，也就是程序不具备运行条件，常见的有I/O事件：程序等待用户输入的数据。这种状态又称为等待或者睡眠。运行态等待态：往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的。等待态就绪态：则是等待的条件已满足，只需分配到处理器后就能运行。运行态就绪态：不是由于自身原因，而是由外界原因使运行状态的进程让出处理器，这时候就变成就绪态。例如时间片用完，或有更高优先级的进程来抢占处理器等。就绪态运行态：系统按某种策略选中就绪队列中的一个进程占用处理器，此时就变成了运行态。进程在运行期间不断地从一个状态转换到另一个状态，进程的各种调度状态依据一定的条件而发生变化，它可以多次处于就绪状态和执行状态，也可多次处于阻塞状态，但可能排在不同的阻塞队列。2. 并发执行的条件设：读集R(pi)=a1,a2,a3,.am：表示程序pi在执行期间所需参考的所有变量的集合，写集W（pi）=b1,b2,b3,.bn：表示程序pi在执行期间要改变的所有变量的集合。当两个程序p1和p2具有如下条件时便能并发执行，且具有可再现性：R(p1)W(p2) R(p2) W(p1) W(p1) W(p2)=。该条件也称为Bernstein条件。3. 进程的挂起状态(1) 挂起状态的引入“挂起”的实质是使进程不能继续运行，即使挂起后的进程处于就绪状态，它也不能参与对CPU的竞争。因此，称被挂起的进程处于静止状态，相反，没被挂起的进程则处于活动状态。而且，处于静止状态的进程，只有通过“激活”动作，才能转换成活动状态。1终端用户的需要：终端用户在自己的程序运行期间，发现有可疑问题时，希望暂停自己的程序。2父进程的需要：父进程希望考察或修改子进程、或者协调子进程间的活动时，要挂起子进程。3OS的需要：OS有时需要挂起某些进程，检查运行中资源的使用情况，以便改善系统运行的性能。4对换的需要：为了缓和内存紧张，将内存中处于阻塞态的进程换至外存上，即该进程处于挂起阻塞。5负荷调节的作用：当系统中的工作负荷太重，可由系统把一些不重要或不紧迫的进程挂起，以保证系统仍然能够正常运行。(2) 进程状态的转换1、活动就绪静止就绪：当进程处于未挂起的就绪时，称此为活动就绪状态，表示为Readya。当用挂起原语Suspend将该进程挂起后，该进程变为静止就绪状态，表示Readys，处于Readys状态的进程，不再被调度执行。2、活动阻塞静止阻塞：当进程处于未被挂起的阻塞状态时，称为它处于活动阻塞状态，表示为Blocked。当用Suspend原语将它挂起后，进程便转变为静止阻塞状态，表示为Blockeds,处于该状态的进程，在其所期待的事件出现后，它将从静止阻塞变为静止就绪。3、静止就绪活动就绪：处于Readys状态的进程，若用激活原语Active激活后，该进程将转换为Readya状态。4、静止阻塞活动阻塞：处于Blockeds状态的进程，若用激活原语Active激活后，该进程将转换为Blockeda状态。静止这一词语有的地方称为挂起，相应的静止就绪称为挂起就绪。这里都作为一样的理解，不区分静止与挂起。二、 进程控制进程控制是指系统使用一些具有特定功能的程序创建或者撤销进程、实现进程状态转换，从而使多个进程在某一时间段内并发执行，实现系统资源共享，提高程序运行效率和资源利用率，进程控制的主要任务是创建和撤消进程以及实现进程的状态转换。进程控制一般由操作系统的内核来实现。(一) 进程调度1. 概念与功能无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。主要功能是：记录系统中各个进程的执行情况；根据一定的算法，运行一个就绪进程；执行CPU的分配操作，恢复中断时保存的现场。2. 进程四个基本属性31.多态性：从诞生、运行，直至消灭。2.多个不同的进程可以包括相同的程序3.三种基本状态之间可进行转换4.并发性：并发执行的进程轮流占用处理器3. 进程调度发生的条件1、正在运行的进程结束或者因为某一事件不能继续运行2、进程提出I/O请求后自行阻塞3、进程执行过程中执行了原语操作，需要重新调度4、优先级更高的进程进入就绪队列引起调度4. 进程调度的分级高级、中级和低级调度作业从提交开始直到完成，往往要经历下述三级调度：高级调度：(High-Level Scheduling)又称为作业调度，它决定把后备作业调入内存运行；低级调度：(Low-Level Scheduling)又称为进程调度，它决定把就绪队列的某进程获得CPU；中级调度：(Intermediate-Level Scheduling)又称为在虚拟存储器中引入，在内、外存对换区进行进程对换。5. 进程调度方式(1) 非剥夺方式分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。这种方式简单，系统开销小。(2) 剥夺方式当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。(二) 进程调度的算法1. 优先数法优先数也称为优先级，优先数法根据进程的优先数高低来确定选择次序，优先级高的进程获得CPU资源。(1) 静态优先数法进程创建时确定的优先数在进程的整个生命周期内保持不变，优先数的分配原则是：系统进程（系统启动时启动的进程，不是由用户启动的）的优先数比用户进程（用户启动的进程）高；资源要求低的进程的优先数比资源要求低的进程的优先数高；按照用户的要求指定。静态优先数法实现简单，但是呆板。(2) 动态优先数法系统基于某种原则（算法），在进程的生命周期内经常修改个进程的优先数，一般有以下几个原则：进程上次占用的CPU时间越长，优先数越低；就绪态进程等待时间越长，优先数越高。有一个公式可以表示：2. 时间片轮转法所有进程按照就是时间先后顺序排队，调度程序每次都从队头选择一个进程，使其运行，并从队头将其删除（上次第二的进程就排第一）。时间片一到，CPU自动制定调度程序，选择下一个即将投入运行的进程。原来没有执行就得进程根据需要可以进入就绪队列队尾或者阻塞队列队尾。这样决定系统效率的关键是时间片的长度。系统中唯有运行态绝对不存在运行队列。(三) 原语在系统态（系统权限）下完成进程控制等特定功能的程序或者程序段称为原语。为保证操作的正确性，原语在执行过程中不允许中断（即屏蔽中断）。用于进程控制的原语有：创建原语、撤消原语、挂起原语、解挂（解除挂起）原语。进程图：用于描述进程家族关系的有向树。（父进程、子进程的概念）；引起进程创建的事件：用户登陆、作业调度、提供服务、应用请求。1. 创建原语cteate()申请空白的PCB、为新进程分配资源、初始化PCB、将新进程插入就绪队列。Procedure create(n, S0,K0,M0,R0, acc) i=getinternal name(n) i.id=n i.priority= K0 i.CPU state=R0 i.status:=readys j=EP i.parent=j geny=null geny=i i.sdata=RQ insert(RQ,i) continueend Procedure参数说明：被创建进程的外部标识符n、初始CPU状态S0（包括CPU的工作方式、进程起始地址以及屏蔽码等）、进程优先数K0、初始内存M0以及所需资源的清单R0等、某进程运行的中间结果acc.创建过程：首先，从PCB集合种索取一个空白PCB，并获得该PCB的内部标识符i;然后，把调用者提供的参数，以及从执行过程EP中获得的调用者内部标识j ，填入该PCB，设置记帐数据，置新进程为“静止就绪”状态；最后，把此PCB分别插入就绪队列RQ和进程家族中。2. 撤销原语destroy( )(1) 引起进程终止的事件正常结束：运行完成异常结束：越界错误、保护错、特权指令错、非法指令错、运行超时、等待超时、算术运算错、I/O故障。外界干预：操作员或操作系统干预、父进程干预、父进程终止。(2) 进程的终止过程根据被终止进程的标识符，从PCB集合中检测出该进程的PCB，并读出进程的状态。若被终止的进程正处于执行态，应立即终止执行，并设调度标志为真，选择新进程，把处理机分配给它。若还有子孙进程，则中指所有子孙进程。将该进程所有的资源，归还给父进程或系统。将被终止进程从他所在的队列中移出，等待其他进程来搜集信息。(3) 撤销原语在撤销指定进程的同时也应该撤销所以的子孙进程, kill()由于撤销子孙进程，描述如下:Procedure destroy(n) Sched=false; i=getinternal name(n) kill(i) if sched then scheduler else continue;end Procedureprocedure kill(i) if i.sdata(i)=”executing” then stop(i) sched=true end if remove (i.sdata,i) for all Sgeny do kill(s) for all r(i.main store i.resources) do if owned(r) then insert (r.semaphore,r.sdata) for all created resources(i) do remove descriptor (R) remove process control block (i);end procedure3. 进程的阻塞与唤醒(1) 引起进程阻塞与唤醒的事件请求系统服务动某种操作新数据尚未到达无新工作可做(2) 进程阻塞过程（是进程本身的一种主动行为）当由于某个事件，使进程无法继续执行，便可调用阻塞原语BLOCK把自己阻塞。若进程处于执行态，则停止执行，把PCB中的现行状态改为：执行-阻塞，并将它插入阻塞队列。转调度程序重新调度，将处理机分配给另一就绪进程，并进行切换（即保留阻塞进程的CPU现场）(3) 进程唤醒过程当被阻塞进程等待的事件出现后（I/O操作完成、等待数据到达），调用唤醒原语来唤醒阻塞进程：被阻塞进程移出阻塞队列；将其PCB的现行状态改为：就绪；将该进程插入就绪队列。(4) 唤醒原语 wakeup()Procedure wakeup(n) i=getinternal name(n) remove (WQ(r),i); i.status=”ready” i.sdata=RQ insert(RQ,i) continueend Procedure注：semaphore是一个记录形信号量，其定义如下：Type semaphore / record dim Value as integer dim L() as new process/ L: list of process;End Type(5) 阻塞原语 blockProcedure block i:=EP; stor(i); i.status=”blockdea” i.sdata=WQ(r); insert(WQ(r),i); schedulerend Procedure4. 进程的挂起与激活当出现了引起进程挂起的事件时，系统就利用挂起原语suspend()将指定进程的进程挂起。当发生激活进程的事件时，系统将利用激活原语active()将指定进程激活。(1) 激活原语active( )Procedure active(n) i=getinternal name(n) i.status=（i.status=”readys”）？ readya”： blockeda if i.status=”readya” then scheduler else continue end if end Procedure(2) 挂起原语suspend( )Procedure suspend(n,a) i=getinternal name(n); s=i.status(四) 进程同步与互斥的基本概念1. 进程的两种关系一是资源共享关系。此时，进程同步的主要任务是保证诸进程能互斥地访问临界资源；二是相互合作关系。此时进程同步的主要任务是保证相互合作的诸进程在执行次序上的协调，不会出现与时间有关的差错。2. 临界资源在计算机中有许多资源一次只能允许一个进程使用，如果多个进程同时使用这些资源，则有可能造成系统的混乱，这些资源被称作临界资源。如打印机和一些共享变量。进程互斥是指为完成各自的目的而竞争同一资源，进程同步是指为完成某一目标而相互协作。3. 各种区域进入区（entry section）：在临界区之前新增一段代码，用于在访问临界区之前进行资源检查。临界区（critical section）：访问临界资源的代码退出区（exit section）：用于将临界区正被访问的标志恢复为未被访问的标志。剩余区（remainder section）：临界区及退出区之外的部分称为。临界资源（critical section）：一次仅允许一个进程使用的资源。4. 进程同步与互斥进程同步是指只有与它协作完成某一任务的进程发来可以进入临界区的消息到来之后才继续运行的现象，属于让权等待；进程互斥与上面类似，但是信号是调度程序发送的，不是退出的进程发送的，这样的两个进程之间不存在合作关系。进程的关系根据实际需要而确定，相互之间是随机的。5. 同步机制应遵循的准则为实现进程互斥，所有的同步机制都应遵循下述四条准则：(1) 空闲让进当无进程处于临界区时，相应的临界资源处于空闲状态。因而可允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。(2) 忙则等待。当已有进程进入自己的临界区时，意味着相应的临界资源正被访问，因而所有其它试图进入临界区的进程必须等待，以保证诸进程互斥地访问临界资源。(3) 有限等待对要求访问临界资源的进程，应保证该进程能在有效时间内进入自己的临界区，以免陷入“死等”状态。(4) 让权等待当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。(五) 锁系统用来实现进程同步或者互斥的机构称为同步机构。这些机构大都采用一个物理实体和相应的原语实现进程的调度。常用的有锁和信号量。系统通过这些原语实现对临街资源的有序访问，实现进程的同步或者互斥。加锁与开锁原语是一种最简单的同步机构，其方法是为每个临界区设置一个布尔变量，例如用变量S表示临界资源的状态，真表示资源可用，家表示资源正被使用。那么S又被称为锁或者锁位。1. 加锁原语与开锁原语(1) 加锁原语 lock(S)1、测试S是否为真；2、若为真，则将S设为假3、若为假则返回到1(2) 开锁原语 unlock(S)将S设为真2. 实现方法(1) 第一种方法测试当前临界资源的状态，一旦为真则立刻进入。进程进入时加锁，禁止其它进程进入。然后执行自己的操作。操作完毕，开锁后退出。如下面所示：:lock(S);Si;unlock(S);:这个方法实现简单，但是不断测试临界资源的状态占用大量的CPU资源，使得这种方法导致系统效率极低，耗费大量的处理器时间。改进算法如下：Lock(S):if !S block n; insert(SL,n); scheduler;else S=0;unlock(S):if SLremove(SL,n);status(q)=readyinsert(RL,q);S=1;说明：当进程不能进入临界区时，不再循环测试锁位S的值，而是插入锁位S 的等待队列SL中，正在使用临界区的进程退出时不仅要恢复锁位S，还要检查锁位S锁位等待队列SL是否为空。若不为空，则将SL队头的进程置为就绪状态并且移到就绪队列RL中。(六) 信号量信号量表示自愿的物理数量，是一个与整形队列有关的整形变量。有多种表示方法。除初始化外，仅能通过两个标准的原子操作V操作（即wait(s)，等待）和P操作（即signal(s)，发信号）来访问。呈现进程同步的两个进程之间发送的信号称为同步信号量，否则称为互斥信号量。1. 信号量表示机制(1) 整型信号量机制整型信号量是一个整型量。PV操作可描述为：wait(s): while (s0) do no-op;s-; signal(s): s+;整型信号量的主要问题是，只要s0，wait操作就会不断地测试，因而，没能做到“让权等待”。(2) 记录型信号量机制在记录信号量中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。typedef struct int value; list of process *L;semaphore;相应的wait和signal操作可描述为：void wait(static semaphore s) s.value-; if (s.value0) block(s.L);void signal(static semaphore s) s.value+; if (s.value0) wackup(s.L);(3) AND型信号量集机制AND同步机制的基本思想是，将进程在整个运行过程中所需要的所有临界资源一次性全部分配给进程，待该进程使用完后再一起释放。只要尚有一个资源未能分配给该进程，其他所有可能为之分配的资源也不分配给它。同样，对若干个临界资源的分配采取原子操作方式，要么全部分配到进程，要么一个也不分配。避免死锁的发生。为此，在wait操作中增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait（Simultaneous Wait）。其定义如下：Swait(S1,S2,Sn) if (S11&Sn1) for (i=1;i=n;i+) Si-; else Place the process in the waiting queue associated with the Si found with Si1, and set the program count of this process to the beginning of Swait operation.Ssignal(S1,S2,Sn) for (i=1;i=n;i+) Si+; Remove all the process waiting in the queue associated with Si into the ready queue.(4) 信号量集在记录型信号量机制中，wait(s)或signal(s)操作仅能对信号量施以增1或减1的操作，即每次只能获得或释放一个单位的临界资源。当一次需要n个某类资源时，便需要进行n次wait(s)操作，显然这是低效的。此外，在某些情况下，当资源数量低于某一下限值时便不予分配。因而，在每次分配之前都必须测试该资源的数量是否大于测试值t。基于上述两点可以对AND信号量机制进行扩充，形成一般化的“信号量集”机制。Swait操作可描述如下：Swait(S1,t1,d1；S2,t2,d2,Sn,tn,dn) if (S1t1&Sntn) for (i=1;i=n;i+) Si=Si-di; else Place the process in the waiting queue associated with the Si found with Siti, and set the program count of this process to the beginning of Swait operation.Ssignal(S1,t1,d1,S2,t2,d2,Sn,tn,dn) for (i=1;i1）或互斥信号量（S=1时）。Swait(S,1,1)。这是一种很特殊很有用的信号量。当S=1时，允许多个进程进入某特区，当S变为0后，将阻止任何进程进入特定区，换言之，它相当于一个可控开关。3. 信号量的应用(1) 利用信号量实现前趋关系信号量可用来描述程序或语句之间的前趋关系。若Pi是Pj的直接前趋，则可设置一个初值为0的公用信号量S，并将signal（S）操作放在Pi后，而在Pj前插入wait（S）操作，以保证Pi在Pj开始执行前完成，实现Pi和Pj的前趋关系。(2) 利用信号量实现互斥为使多个进程能互斥地访问某个临界资源，只需为该资源设置一个互斥信号量mutex,并将其初值置为1，然后将访问该资源的临界区置于wait（mutex）和signal（mutex）之间。下面的算法描述了如何利用信号量实现进程P1和P2的互斥，其中信号量mutex的初值为1。P1进程 wait(mutex);critical section; signal(mutex); P2进程wait(mutex);critical section;signal(mutex)4. 经典进程同步问题(1) 生产者-消费者问题（Producer-Consumer）：有一群生产者进程在生产产品，并将此产品提供给消费者进程去消费。为使生产者进程和消费者进程能并发执行，在它们之间设置一个公用缓冲池，生产者进程可将它所生产的产品放入一个缓冲区中，消费者进程可从一个缓冲区取得一个产品消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装有消息且尚未被取走产品的缓冲区中投放产品。假定，在生产者和消费者之间的公用缓冲池中有n个缓冲区，可利用互斥信号量mutexP使生产者进程实现对缓冲池的互斥使用；利用互斥信号量mutexC使消费者进程实现对缓冲池的互斥使用；利用资源信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将产品送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个产品。生产者-消费者问题可描述如下：semaphore mutexP=1,mutexC=1,empty=n,full=0;item buffern;int in=out=0;void producer() while (1) produce an item in nextp; . wait(empty); wait(mutexP); bufferin=nextp; in=(in+1) mod n; signal(mutexP); signal(full); void consumer()while (1) . wait(full); wait(mutexC); nextc=bufferout; out=(out+1) mod n; signal(mutexC); signal(empty); . consume the item in nextc; main()cobegin producer();consumer();(2) 哲学家进餐问题有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子继续思考。1、利用记录型信号量解决哲学家进餐问题分析：筷子是临界资源，在一段时间内只允许一个哲学家使用。因此，可以用一个信号量表示一支筷子。故需要信号量数组。描述如下：var chopstick:array0,.4 of semaphore;(初值为1)repeatwait(chopsticki);wait(chopstick(i+1) mod 5)；eat;signal(chopsticki);signal(chopstick(i+1) mod 5);think;until false;注意：如果五个哲学家同时进餐，可能会导致死锁现象。解决死锁的方法：（1）至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。（2）仅当哲学家的左右两支筷子都可用时，才允许它拿起筷子进餐。（3）规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五个哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。2、利用AND信号量机制解决哲学家进餐问题每个哲学家先获得两个临界资源后才能进餐，这实质是AND信号量机制同步问题。var chopstick:array0,.4 of semaphore=（1，1，1，1，1)；process irepeatthink;wait(chopsticki);Swait(chopstick(i+1) mod 5, chopsticki)；eat;signal(chopstick(i+1) mod 5, chopsticki);until false;(3) 读者-写者问题1、问题的描述（1）Reader进程：只要求读的进程称为Reader。（2）Writer进程：要求对数据对象今年系写或修改的进程称为Writer。注意：允许多个Reader进程同时读一个共享对象；但绝对不允许一个write进程和其他reader进程或writer进程同时访问共享对象。（违反Bernstein条件，从而引起混乱。）读者-写者问题：指保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。2、解决方法（1）利用记录型信号量解决读者写者问题设：互斥信号量wmutex，rmutex；整形变量readcount正在读的进程数目；只要有一个reader进程在读，便不允许write进程去写，因此，仅当readcount=0表示尚无reader进程在读，reader进程才需要执行wait(wmutex)操作，若wait(wmutex)操作成功，reader进程便可去读。此时,readcount+1。相应地，仅当reader进程在执行了readcount 减1操作后，其值为0时，才需执行signal(wmutex)操作。以便让write进程去写。又因为readcount 是一个可被多个reader进程访问的临界资源，因此，应为它设置一互斥信号量rmutex。Var rmutex,wmutex:semaphore:=1,1;Readcount:integer:=0;BeginParbegin;Reader:begin;RepeatWait(rmutex)If readcunt=0 then wait(wmutex);Readcount;=readcount+1;Signal(rmutex);Perform read operation;Wait(rmutex);Readcount:=readcount-1;If readcount=0 then signal(wmutex)Sinai(rmutex);Until false;EndWriter:beginRepeatWait(wmutex);Perform write operation;Signal(wmute);Until false;EndParendEnd（2）利用信号量集机制解决读者一写者问题这里的读者一写者问题，与前面的略有不同，它增加了一条限制，即最多只允许RN个读者同时读。为此，又引入了一个信号量L，并赋予其初值为RN，通过执行wait（L，1，1）操作，来控制读者的数目，每当有一个读者进入时，都要先执行wait(L,1,1)操作，使L的值减1。当有RN个进入读后，L便减为0，第RN+1个读者进入读时，必然会因wait(L,1,1)操作失败而阻塞。利用信号量集来解决读者一写者问题的描述如下：var RN integer; L,mx:semaphore:=RN,1;BeginParbeginReader:beginRepeatSwait (L,1,1);Swait (mx,1,0);Perform read operationSsignai (L,1);Until false;EndWriter:begin RepeatSwait (mx,1,1;L,RN,0);Perform write operationSsignal (mx,1);Until false;EndParend End其中，Swait(mx,1,0)语句起着开关作用。只要无writer进程进入写mx=1,reader 进程就都可以进入读。但只要一旦有writer进入写时，其mx=0,则任何reader进程就都无法进入读。Swait(mx,1,1,L,RN,0)语句表示仅当即无writer进程在写（mx=1），又无reader进程在读（L=RN）时,writer进程才能进入临界区写。(七) 管程虽然信号量机制是一种既方便又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作wait(s)和signal(s)。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的同步工具管程。1. 管程的基本概念(1) 管程的定义一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据”。由定义可知，管程由三部分组成：局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初值的语句。此外，还需为该管程赋予一个名字。管程的语法为：monitor monitor-name variable declarations entry p1(.) . entry p2(.) . . entry pn(.) . initialization code ;(2) 管程具有以下特点：（1）局部于管程的数据结构，仅能被局部与管程的过程所访问，任何管程外的过程都不能访问；反之，局部于管程的过程也仅能访问管程内的数据结构。（2）任何进程只能通过调用管程提供的过程入口进入管程。（3）任一时刻，最多只能有一个进程在管程中执行。2. 条件变量在利用管程实现进程同步时，必须设置两个同步操作原语wait和signal。当某进程通过管程请求临界资源而未能满足时，管程便调用wait原语使该进程等待，并将它排在等待队列上。仅当另一进程访问完并释放之后，管程又调用signal原语唤醒等待队列中的队首进程。通常，等待的原因可有多个，为了区别它们，又引入了条件变量co