在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。下面举一个简单的例子来帮大家理解这个概念。例如，让系统计算1+2×3，假设系统产生两个进程：一个是加法进程，一个是乘法进程。要让计算结果是正确的，一定要让加法进程发生在乘法进程之后，但实际上操作系统具有异步性，若不加以制约，加法进程发生在乘法进程之前是绝对有可能的，因此要制定一定的机制去约束加法进程，让它在乘法进程完成之后才发生，而这种机制就是本节要讨论的内容。
虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所用，我们将一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。
对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可把临界资源的访问过程分成4个部分：
do { entry section; //进入区 critical section; //临界区 exit section; //退出区 remainder section; //剩余区} while(true)同步亦称直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系源于它们之间的相互合作。
例如，输入进程A通过单缓冲向进程B提供数据。当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据送入缓冲区，进程B就被唤醒。反之，当缓冲区满时，进程A被阻塞，仅当进程B取走缓冲数据时，才唤醒进程A。
互斥也称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。
例如，在仅有一台打印机的系统中，有两个进程A和进程B，若进程A需要打印时，系统已将打印机分配给进程B，则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程A唤醒，并将其由阻塞态变为就绪态。
为禁止两个进程同时进入临界区，同步机制应遵循以下准则：
在进入区设置并检查一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。
该算法设置一个公用整型变量 turn，用于指示被允许进入临界区的进程编号，即若 turn=0，则允许
若 turn=1 一直成立，
xxxxxxxxxx//P0进程: //P1进程:while(turn != 0); while(turn != 1); //进入区critical section; critical section; //临界区turn=l; turn=0; //退出区remainder section; remainder section; //剩余区该算法的基本思想是在每个进程访问临界区资源之前，先查看临界资源是否正被访问，若正被访问，该进程需等待：否则，进程才进入自已的临界区。为此，设置一个布尔型数组 flag[]，如第 i 个元素 flag[i] 为 FALSE，表示 TRUE，表示
xxxxxxxxxx//Pi进程 //Pj进程while(flag[j]); 1 while(flag[i]); 2 //进入区flag[i] = TRUE; 3 flag[j] = TRUE; 4 //进入区critical section; critical section; //临界区flag[i] = FALSE; flag[j] = FALSE; //退出区remainder section; remainder section; //剩余区优点：不用交替进入，可连续使用：
缺点：
算法二先检测对方的进程状态标志，再置自已的标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后同时进入临界区。为此，算法三先将自己的标志设置为TRUE，再检测对方的状态标志，若对方标志为TRUE，则进程等待：否则进入临界区。
xxxxxxxxxx// Pi 进程: // Pj 进程flag[i] = TRUE; flag[j] = TRUE; //进入区while(flag[j]); while(flag[i]); //进入区critical section; critical section; //临界区flag[i] = FALSE; flag[j] = FALSE; //退出区remainder section; remainder section;//剩余区两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区时，双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。
为了防止两个进程为进入临界区而无限期等待，又设置了变量turn，每个进程在先设置自己的标志后再设置turm标志。这时，再同时检测另一个进程状态标志和允许进入标志，以便保证两个进程同时要求进入临界区时，只允许一个进程进入临界区。
xxxxxxxxxx//Pi 进程 //Pj 进程：flag[i] = TRUE; turn = j; flag[j] = TRUE; turn = i; //进入区while(flag[j] && turn == j); while(flag[i] && turn == i); //进入区critical section; critical section; //临界区flag[i] = FALSE; flag[j] = FALSE; //退出区remainder section; remainder section; //剩余区具体如下：考虑进程P，一旦设置 flag[i] = true ，就表示它想要进入临界区，同时 turn=j ,此时若进程 flag[j]=false，循环条件不符合，则
理解 Peterson's Algorithm 的最好方法就是手动模拟。
理解本节介绍的硬件实现，对学习后面的信号量很有帮助。计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或对两个字的内容进行交换等。通过硬件支持实现临界段问题的方法称为低级方法，或称元方法。
当一个进程正在执行它的临界区代码时，防止其他进程进入其临界区的最简方法是关中断。因为CPU只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完，进而保证互斥的正确实现，然后执行开中断。其典型模式为
xxxxxxxxxx...关中断;临界区;开中断;...
这种方法限制了处理机交替执行程序的能力，因此执行的效率会明显降低。对内核来说，在它执行更新变量或列表的几条指令期间，关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断后不再开中断，则系统可能会因此终止。
TestAndSet 指令：这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。指令的功能描述如下：
xxxxxxxxxxboolean TestAndSet(boolean *lock) { boolean old; old = *lock; *lock = true; return old;}可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用，初值为false。进程在进入临界区之前，利用TestAndSet检查标志lock，若无进程在临界区，则其值为false，可以进入，关闭临界资源，把lock置为true，使任何进程都不能进入临界区；若有进程在临界区，则循环检查，直到进程退出。利用该指令实现互斥的过程描述如下：
xxxxxxxxxxwhile TestAndSet(&lock);进程的临界区代码段;lock = false;进程的其他代码;Swap指令：该指令的功能是交换两个字（字节）的内容。其功能描述如下：
xxxxxxxxxxSwap(boolean *a, boolean *b){ boolean temp; temp = *a; *a = *b; *b = temp;}注意：以上对 TestAndSet 和 Swap 指令的描述仅是功能实现，而并非软件实现的定义。事实上，它们是由硬件逻辑直接实现的，不会被中断。
用 Swap 指令可以简单有效地实现互斥，为每个临界资源设置一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。在进入临界区前，先利用Swap指令交换lock与key的内容，然后检查key的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。其处理过程描述如下：
xxxxxxxxxxkey = true;while(key != false) Swap(&lock, &key);进程的临界区代码段;lock = false;进程的其他代码;硬件方法的优点：适用于任意数目的进程，而不管是单处理机还是多处理机；简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。
硬件方法的缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。
无论是软件实现方法还是硬件实现方法，读者只需理解它的执行过程即可，关键是软件实现方法。实际练习和考试中很少让读者写出某种软件和硬件实现方法，因此读者并不需要默写或记忆。以上的代码实现与我们平时在编译器上写的代码意义不同，以上的代码实现是为了表述进程实现同步和互斥的过程，并不是说计算机内部实现同步互斥的就是这些代码。
解决临界区最简单的工具就是互斥锁（mutex lock）。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数 acquire() 获得锁，而函数 release() 释放锁。
每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用 acquire() 会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。
xxxxxxxxxxacquire(){ while(!available) //忙等待 available = false; //获得锁}release() { available = true; //释放锁}acquire() 或 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。
互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire() 。当多个进程共享同一个CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。本节后面，将会研究如何使用互斥锁解决经典同步问题。
信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的原语 wait(S) 和 signal(S) 访问，也可记为“P操作”和“V操作”
原语是指完成某种功能且不被分割、不被中断执行的操作序列，通常可由硬件来实现。例如，前述的Test-and-Set和Swap指令就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机上可由软件通过屏蔽中断方法实现。原语之所以不能被中断执行，是因为原语对变量的操作过程若被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。
整型信号量被定义为一个用于表示资源数目的整型量 S，wait 和 signal 操作可描述为
xxxxxxxxxxwait(S) { while(S <= 0); S--;}signal(S) { S++;}在整型信号量机制中的wait操作，只要信号量
记录型信号量机制是一种不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量 value 外，再增加一个进程链表 L，用于链接所有等待该资源的进程。记录型信号量得名于采用了记录型的数据结构。记录型信号量可描述为
xxxxxxxxxxtypedef struct{ int value; struct process *L;}semaphore;相应的 wait(S) 和 signal(S) 的操作如下：
xxxxxxxxxxvoid wait(semaphore S) {//相当于申请资源 S.value--; if(S.value < 0) { add this process to S.L; block(S.L); }}wait操作，S.value--表 示进程请求一个该类资源，当 S.value<0 时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入该类资源的等待队列 S.L，可见该机制遵循了“让权等待”的准则。
xxxxxxxxxxvoid signal(semaphore S){//相当于释放资源 S.value++; if(S.value<=0){ remove a process P from S.L; wakeup(P); }}signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增1，因此有 S.value++。
若加 1 后仍是 S.value <= 0，则表示在 S.L 中仍有等待该资源的进程被阻塞，因此还应调用 wakeup 原语，将 S.L中的第一个等待进程唤醒。
信号量机制能用于解决进程间的各种同步问题。设 S 为实现进程
xxxxxxxxxxsemaphore S=0;//初始化信号量P1() { x; //语句x V(S); //告诉进程P2，语句x已经完成 ...}P2() { ... P(S); //检查语句x是否运行完成 y; //检查无误，运行y语句 ...}若 P(S) 时，S为0，执行P操作会把进程
信号量机制也能很方便地解决进程互斥问题。设S为实现进程P，P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数为1）。只需把临界区置于P（S）和V（S）之间，即可实现两个进程对临界资源的互斥访问。其算法如下：
semaphore S=1;//初始化信号量P1(）（P(S);//准备开始访问临界资源，加锁进程P1的临界区；V(S);//访问结束，解锁P2(){P(S);//准备开始访问临界资源，加锁进程P2的临界区；V(S);//访问结束，解锁...当没有进程在临界区时，任意一个进程要进入临界区，就要执行P操作，把S的值减为0，然后进入临界区；当有进程存在于临界区时，S的值为0，再有进程要进入临界区，执行P操作时将会被阻塞，直至在临界区中的进程退出，这样便实现了临界区的互斥。直互斥是不同进程对同一信号量进行P，V操作实现的，一个进程成功对信号量执行了P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作，表示当前没有进程进入临界区，可以让其他进程进入。
0922024年操作系统考研复习指导下面简单总结一下PV操作在同步互斥中的应用：在同步问题中，若某个行为要用到某种资源，则在这个行为前面P这种资源一下；若某个行为会提供某种资源，则在这个行为后面V这种S资源一下。在互斥问题中，P，V操作要紧夹使用互斥资源的那个行为，中间不能有其他余代码。5.利用信号量实现前驱关系信号量也可用来描述程序之间或语句之间的前驱关系。图2.10给出了一个前驱图，其中S，S2,S3,·,S是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干初始值为“0”的S6信号量。例如，为保证S→S2,S→S的前驱关系，应分别设置信号图2.10前驱图举例量al,a2。同样，为保证S2→S4,S2→Ss,S→S6,S4→S6,S→S6，应设置信号量b1,b2,c,d,e。实现算法如下：semaphoreal=a2=b1=b2=c=d=e=0；//初始化信号量S1(){V(a1);V(a2）;//S1已经运行完成S2()P(al);//检查S1是否运行完成....V(b1);V(b2);//S2已经运行完成S3(){P（a2);//检查S1是否已经运行完成V(c);//S3已经运行完成S4()tP(bl);//检查S2是否已经运行完成....v(d);//S4已经运行完成S5(){P(b2);//检查S2是否已经运行完成v(e);//S5已经运行完成S6()P(C);//检查S3是否已经运行完成P(d);//检查S4是否已经运行完成P(e);//检查S5是否已经运行完成....6。分析进程同步和互斥问题的方法步骤1）关系分析。找出问题中的进程数，并分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。2）整理思路。找出解决问题的关键点，并根据做过的题目找出求解的思路。根据进程的操作流程确定P操作、V操作的大致顺序。3）设置信号量。根据上面的两步，设置需要的信号量，确定初值，完善整理。
第2章进程与线程093这是一个比较直观的同步问题，以S2为例，它是S的后继，所以要用到S的资源，在前面的简单总结中我们说过，在同步问题中，要用到某种资源，就要在行为（题中统一抽象成L）前面P这种资源一下。S2是S4，Ss的前驱，给S4，Ss提供资源，所以要在L行为后面V由S4和Ss代表的资源一下。
在信号量机制中，每个要访问临界资源的进程都必须自备同步的PV操作，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当而导致系统死锁。于是，便产生了一种新的进程同步工具一一管程。管程的特性保证了进程互斥，无须程序员自己实现互斥，从而降低了死锁发生的可能性。同时管程提供了条件变量，可以让程序员灵活地实现进程同步。1。管程的定义系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请、释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程（monitor）。管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。由上述定义可知，管程由4部分组成：①管程的名称；②局部于管程内部的共享数据结构说明；③对该数据结构进行操作的一组过程（或函数）；④对局部于管程内部的共享数据设置初始值的语句。管程的定义描述举例如下：7/②定义共享数据结构，对应系统中的某种共享资源共享数据结构s;1/④对共享数据结构初始化的语句init_code(){S=5;//初始资源数等于51/③过程1：申请一个资源take_away()(对共享数据结构x的一系列处理；S--://可用资源数-1·//③过程2：归还一个资源give_back()(对共享数据结构×的一系列处理；S++;//可用资源数+1
024年操作系统考研复习指导熟悉面向对象程序设计的读者看到管程的组成后，会立即联想到管程很像一个类（class）。1）管程把对共享资源的操作封装起来，管程内的共享数据结构只能被管程内的过程所访问。一个进程只有通过调用管程内的过程才能进入管程访问共享资源。对于上例，外部进程只能通过调用take_awayO过程来申请一个资源；归还资源也一样。2）每次仅允许一个进程进入管程，从而实现进程互斥。若多个进程同时调用take_awayO，give_backO，则只有某个进程运行完它调用的过程后，下个进程才能开始运行它调用的过程。也就是说，各个进程只能串行执行管程内的过程，这一特性保证了进程“互斥”访问共享数据结构S。2.条件变量当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程。为此，将阻塞原因定义为条件变量condition。通常，一个进程被阻塞的原因可以有多个，因此在管程中设置了多个条件变量。每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程，对条件变量只能进行两种操作，即wait和signal。x.wait：当x对应的条件不满足时，正在调用管程的进程调用x.wait将自已插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程。x.signal：x对应的条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞的进程。下面给出条件变量的定义和使用：monitor Demo共享数据结构S;condition x;//定义一个条件变量xinit_code()(...)take_awayO0OV10: if(s<=0) x.wait();//资源不够，在条件变量×上阻塞等待资源足够，分配资源，做一系列相应处理：give back()归还资源，做一系列相应处理；if（有进程在等待）x.signal（）;//唤醒一个阻塞进程条件变量和信号量的比较：相似点：条件变量的wait/signal操作类似于信号量的P/V操作，可以实现进程的阻塞/唤醒。不同点：条件变量是“没有值”的，仅实现了“排队等待”功能；而信号量是“有值”的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。
1.生产者一消费者问题问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。问题分析：1）关系分析。生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一
第2章进程与线程095个相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。2）整理思路。这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。3）信号量设置。信号量mutex作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为1；信号量full用于记录当前缓冲池中的“满”缓冲区数，初值为0。信号量empty用于记录当前缓冲池中的“空”缓冲区数，初值为n。我们对同步互斥问题的介绍是一个循序渐进的过程。上面介绍了一个同步问题的例子和一个互斥问题的例子，下面来看生产者一消费者问题的例子是什么样的。生产者一消费者进程的描述如下：semaphore mutex=1;//临界区互斤信号量semaphore empty=n;//空闲缓冲区semaphore full=0;//缓冲区初始化为空producer() (7/生产者进程while(1)(produce an item in nextp;/生产数据P（empty）；（要用什么，P一下）//获取空缓冲区单元P（mutex）；（互斥夹紧）//进入临界区add nextpto buffer;（行为)//将数据放入缓冲区V（mutex）；（互斥夹紧）//离开临界区，释放互斥信号量V（ful1）；（提供什么，V一下）//满缓冲区数加1consumer()1/消费者进程while(1){P(full);//获取满缓冲区单元P(mutex);//进入临界区remove an item from buffer;1/从缓冲区中取出数据V(mutex);7/离开临界区，释放互斥信号量V(empty);//空缓冲区数加1consume the item;//消费数据该类问题要注意对缓冲区大小为n的处理，当缓冲区中有空时，便可对empty变量执行P操作，一旦取走一个产品便要执行V操作以释放空闲区。对empty和full变量的P操作必须放在对然后执行P(full)，这样可不可以？答案是否定的。设想生产者进程已将缓冲区放满，消费者进程并没有取产品，即empty=0，当下次仍然是生产者进程运行时，它先执行P（mutex）封锁信号量，再执行P(empty)时将被阻塞，希望消费者取出产品后将其唤醒。轮到消费者进程运行时，它先执行P（mutex），然而由于生产者进程已经封锁mutex信号量，消费者进程也会被阻塞，这样一来生产者、消费者进程都将阻塞，都指望对方唤醒自己，因此陷入了无休止的等待。同理，若消费者进程已将缓冲区取空，即full=0，下次若还是消费者先运行，也会出现类似的死锁。不过生产者释放信号量时，mutex,full先释放哪一个无所谓，消费者先释放mutex或empty都可以。根据对同步互斥问题的简单总结，我们发现，其实生产者一消费者问题只是一个同步互斥问题的综合而已。下面再看一个较为复杂的生产者-消费者问题。
0962024年操作系统考研复习指导问题描述：桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。爸爸放苹果妈妈放橘子出问题分析：此处必须1）关系分析。这里的关系要稍复杂一些。由每次只能向其连续执行中放入一只水果可知，爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连女儿吃苹果儿子吃橘子起来，儿子和女儿之间没有互斥和同步关系，因为他们图2.11进程之间的关系是选择条件执行，不可能并发，如图2.11所示。2）整理思路。这里有4个进程，实际上可抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。3）信号量设置。首先将信号量plate设置互斥信号量，表示是否允许向盘子放入水果，初值为1表示允许放入，且只允许放入一个。信号量apple表示盘子中是否有苹果，初值为0表示盘子为空，不许取，apple=1表示可以取。信号量orange表示盘子中是否有橘子，初值为0表示盘子为空，不许取，orange=1表示可以取。解决该问题的代码如下：semaphore plate=1, apple=0, orange=0;dad(）{//父亲进程while(l)fprepare an apple;P(plate);//互斥向盘中取、放水果put the apple on the plate;//向盘中放苹果v(apple);//允许取苹果1/母亲进程while（1)prepare an orange;P(plate);//互斥向盘中取、放水果put the orange on the plate;//向盘中放橘子V(orange);7/允许取橘子son(){//儿子进程while(l)(P(orange);//互斥向盘中取橘子take an orange from the plate;V(plate);1/允许向盘中取、放水果eat the orange;daughter(){//女儿进程while(l)(P(apple);//互斥向盘中取苹果take an apple from the plate;V(plate);//允许向盘中取、放水果
第2章进程与线程097eat the apple;进程间的关系如图2.11所示。dad0和daughterO、momO和sonO必须连续执行，正因为如此，也只能在女儿拿走苹果后或儿子拿走橘子后才能释放盘子，即V(plate）操作。2。读者一写者问题问题描述：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任意一个写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。问题分析：1）关系分析。由题目分析读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题。2）整理思路。两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的P操作、V操作即可解决。读者的问题比较复杂，它必须在实现与写者互斥的同时，实现与其他读者的同步，因此简单的一对P操作、V操作是无法解决问题的。这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者时，写者是无法写文件的，此时读者会一直占用文件，当没有读者时，写者才可以写文件。同时，这里不同读者对计数器的访问也应该是互斥的。3）信号量设置。首先设置信号量count为计数器，用于记录当前读者的数量，初值为0；设置mutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw，用于保证读者和写者的互斥访问。代码如下：int count=0;//用于记录当前的读者数量semaphore mutex=1;//用于保护更新count变量时的互斥semaphore rw=1;//用于保证读者和写者互斥地访问文件writer()//写者进程while(1)(P(rw);//互斥访问共享文件writing;//写入V(rw);//释放共享文件reader(){//读者进程while(l)(P(mutex);//互斥访问count变量if(count0)1/当第一个读进程读共享文件时P(rw);//阻止写进程写count++;//读者计数器加1V(mutex);//释放互斥变量countreading://读取P(mutex);//互斤访问count变量count--;//读者计数器减1if(count0)//当最后一个读进程读完共享文件V(rw);//允许写进程写
0982024年操作系统考研复习指导V(mutex);//释放互斥变量count在上面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式会导致写进程可能长时间等待，且存在写进程“饿死”的情况。若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的writerO和readerO函数中各增加一对PV操作，就可以得到写进程优先的解决程序。int count=0;//用于记录当前的读者数量semaphore mutex=l;//用于保护更新count变量时的互斥semaphore rw=l;//用于保证读者和写者互斥地访问文件semaphore w=1;//用于实现“写优先”writer()l//写者进程while(1)1P(W);//在无写进程请求时进入P(rw)://互斥访问共享文件writing;//写入V(rw);//释放共享文件V(w);//恢复对共享文件的访问reader(){7/读者进程while(l)P（W);//在无写进程请求时进入P(mutex);//互斥访问count变量if (count0)//当第一个读进程读共享文件时P(rw);//阻止写进程写count++;//读者计数器加1V(mutex);//释放互斥变量countV(w)://恢复对共享文件的访问reading;//读取P(mutex);//互斥访问count变量count--,//读者计数器减1if (count0)//当最后一个读进程读完共享文件V(rw);//允许写进程写V(mutex);//释放互斥变量count这里的写进程优先是相对而言的，有些书上把这个算法称为读写公平法，即读写进程具有一样的优先级。当一个写进程访问文件时，若先有一些读进程要求访问文件，后有另一个写进程要求访问文件，则当前访问文件的进程结束对文件的写操作时，会是一个读进程而不是一个写进程占用文件（在信号量w的阻塞队列上，因为读进程先来，因此排在阻塞队列队首，而V操作唤醒进程时唤醒的是队首进程），所以说这里的写优先是相对的，想要了解如何做到真正写者优先，可参考其他相关资料。读者-写者问题有一个关键的特征，即有一个互斥访问的计数器count，因此遇到一个不太好
第2章进程与线程099解决的同步互斥问题时，要想一想用互斥访问的计数器count能否解决问题。3。哲学家进餐问题问题描述：一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭，如图2.12所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手让，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。问题分析：1）关系分析。5名哲学家与左右邻居对其中间筷子的访问是互斥关系。2）整理思路。显然，这里有5个进程。本题的关键是如何让一图2.125名哲学家进餐名哲学家拿到左右两根筷子而不造成死锁或饥饿现象。解决方法有两个：一是让他们同时拿两根筷子；二是对每名哲学家的动作制定规则，避免饥饿或死锁现象的发生。3）信号量设置。定义互斥信号量数组chopstick[5]={1，1,1，1,1}，用于对5个筷子的互斥访问。哲学家按顺序编号为0~4，哲学家i左边筷子的编号为i，哲学家右边筷子的编号为（i+1)%5semaphore chopstiek[5]=(1，1，1，1，1）;//定义信号量数组chopstick[51，并初始化PiO（//i号哲学家的进程dofP(chopstick[il);//取左边筷子P(chopstick[(i+l)%5]);//取右边筷子eat;//进餐V(chopstick[i]);//放回左边筷子V(chopstick[（i+i)&51);//放回右边筷子think;1/思考)while(1);该算法存在以下问题：当5名哲学家都想要进餐并分别拿起左边的筷子时（都恰好执行完wait（chopstick[i])）;）筷子已被拿光，等到他们再想拿右边的筷子时（执行wait（chopstick[(i+1)%5]);；）就全被阻塞，因此出现了死锁。为防止死锁发生，可对哲学家进程施加一些限制条件，比如至多允许4名哲学家同时进餐；仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子；对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后拿右边的筷子，而偶数号哲学家刚好相反。制定的正确规则如下：假设采用第二种方法，当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子。semaphorechopstick[5]={1,1,1,1,1);/ /初始化信号量semaphore mutex=1;//设置取筷子的信号量Pi()//i号哲学家的进程dolP(mutex);//在取筷子前获得互斥量P(chopstick[i]);//取左边筷子P（chopstick[(i+1)%5]);1/取右边筷子V(mutex);//释放取筷子的信号量eat://进餐
1002024年操作系统考研复习指导V(chopstick[i]);//放回左边筷子V(chopstick[(i+1)%5]);//放回右边筷子think;//思考)while(l);此外，还可采用AND型信号量机制来解决哲学家进餐问题，有兴趣的读者可以查阅相关资料，自行思考。熟悉ACM或有过相关训练的读者都应知道贪心算法，哲学家进餐问题的思想其实与贪心算法的思想截然相反，贪心算法强调争取眼前认为最好的，而不考虑后续会有什么后果。若哲学家进餐问题用贪心算法来解决，即只要眼前有筷子能拿起就拿起的话，就会出现死锁。然而，若不仅考虑眼前的一步，而且考虑下一步，即不因为有筷子能拿起就拿起，而考虑能不能一次拿起两根筷子才做决定的话，就会避免死锁问题，这就是哲学家进餐问题的思维精髓。大部分练习题和真题用消费者一生产者模型或读者-写者问题就能解决，但对于哲学家进餐问题和吸烟者问题仍然要熟悉。考研复习的关键在于反复多次和全面，“偷工减料”是要吃亏的。4.吸烟者问题问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上，如此重复（让三个抽烟者轮流地抽烟）。问题分析：1）关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或以上的抽烟者，三个抽烟者对抽烟这个动作互斥（或由三个抽烟者轮流抽烟得知）。2）整理思路。显然这里有4个进程。供应者作为生产者向三个抽烟者提供材料。3）信号量设置。信号量offerl，offer2，offer3分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。代码如下：int num=0;7/存储随机数semaphore offerl=0;//定义信号量对应烟草和纸组合的资源semaphore offer2=0;//定义信号量对应烟草和胶水组合的资源semaphore offer3=0;//定义信号量对应纸和胶水组合的资源semaphore finish=0;//定义信号量表示抽烟是否完成process P1(){//供应者while(l)fnum++;num=num号3；if(num0)V(offerl);//提供烟草和纸else if(num1)V(offer2);//提供烟草和胶水elseV(offer3);//提供纸和胶水任意两种材料放在桌子上：P(finish);
第2章进程与线程101process P2() (//拥有烟草者while(l)P(offer3);拿纸和胶水，卷成烟，抽掉；V(finish);process P3() t//拥有纸者whiie(l)（P(offer2);拿烟草和胶水，卷成烟，抽掉；V(finish);process P4()(//拥有胶水者while(1)(P(offerl);拿烟草和纸，卷成烟，抽掉；V(finish);
在学习本节时，请读者思考以下问题：1）为什么会产生死锁？产生死锁有什么条件？2）有什么办法可以解决死锁问题？学完本节，读者应了解死锁的由来、产生条件及基本解决方法，区分避免死锁和预防死锁。
1。死领的定义在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而，多个进程的并发执行也带来了新的问题一死锁。所谓死锁，是指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。下面通过一些实例来说明死锁现象。先看生活中的一个实例。在一条河上有一座桥，桥面很窄，只能容纳一辆汽车通行。若有两辆汽车分别从桥的左右两端驶上该桥，则会出现下述冲突情况：此时，左边的汽车占有桥面左边的一段，要想过桥还需等待右边的汽车让出桥面右边的一段；右边的汽车占有桥面右边的一段，要想过桥还需等待左边的汽车让出桥面左边的一段。此时，若左右两边的汽车都只能向前行驶，则两辆汽车都无法过桥。进程 P正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程 P2所占用，而P2在未释放打印机之前，又提出请求使用正被P占用的输入设备。这样，两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。2。死锁产生的原因（1）系统资源的竞争通常系统中拥有的不可剥夺资源，其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局，如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产
生死锁，对可剥夺资源的竞争是不会引起死锁的。（2）进程推进顺序非法进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁。例如，并发进程P，P2分别保持了资源 R,R2，而进程P, 申请资源 R2、进程 P2申请资源R,时，两者都会因为所需资源被占用而阻塞，于是导致死锁。信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息，也会使得这些进程间无法继续向前推进。例如，进程A等待进程B发的消息，进程B又在等待进程A发的消息，可以看出进程A和B不是因为竞争同一资源，而是在等待对方的资源导致死锁。3。 死锁产生的必要条件产生死锁必须同时满足以下4个条件，只要其中任意一个条件不成立，死锁就不会发生。（1）互斥条件程所占有。此时若有其他进程请求该资源，则请求进程只能等待。（2）不剥夺条件自己来释放（只能是主动释放）。（3）请求并保持条件时请求进程被阻塞，但对自己已获得的资源保持不放。（4）循环等待条件··存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待态的进程集合{P,P2,.·,P}，其中 P;等待的资源被 P（i=0,1,.·,n-1）占有，P,等待的资源被Po占有，如图2.13所示。直观上看，循环等待条件似乎和死锁的定义一样，其实不然。按死锁定义构成等待环所要求的条件更严，它要求P;等待的资源必须由P；i来满足，而循环等待条件则无此限制。例如，系统中有两台输出设备，Po占有一台，Pk占有另一台，且K不属于集合{0，1，‘，n}。P,等待一台输但Pk不在圈内，若Pk释放了输出设备，则可打破循环等待，如图2.14所示。因此循环等待只是死锁的必要条件。图2.13循环等待图2.14满足条件但无死锁资源分配图含圈而系统又不一定有死锁的原因是，同类资源数大于1。但若系统中每类资源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。要注意区分不剥夺条件与请求并保持条件。下面用一个简单的例子进行说明：若你手上拿着
第2章进程与线程135一个苹果（即便你不打算吃），别人不能把你手上的苹果拿走，则这就是不剥夺条件；若你左手拿着一一个苹果，允许你右手再去拿一个苹果，则这就是请求并保持条件。4。死锁的处理策略为使系统不发生死锁，必须设法破坏产生死锁的4个必要条件之一，或允许死锁产生，但当死锁发生时能检测出死锁，并有能力实现恢复。1）死锁预防。设置某些限制条件，破坏产生死锁的4个必要条件中的一个或几个。．2）避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态。3）死锁的检测及解除。无须采取任何限制性措施，允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。预防死锁和避免死锁都属于事先预防策略，预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低；避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。死锁的几种处理策略的比较见表2.4。表 2.4死锁处理策略的比较资源分配策略各种可能模式主要优点主要缺点效率低，进程初始化时死锁一次请求所有资源，资源剥适用于突发式处理的进保守，宁可资源闲置间延长；剥夺次数过多;预防夺，资源按序分配程，不必进行剥夺不便灵活申请新资源必须知道将来的资源需是“预防”和“检浏”的折死锁中（在运行时判断是否可能寻找可能的安全允许顾序不必进行剥夺求；进程不能被长时间避免阻塞死锁）不延长进程初始化时间，通过剥夺解除死锁，造死锁宽松，只要允许就分配资源定期检查死锁是否已经发生检测允许对死锁进行现场处理成损失
防止死锁的发生只需破坏死锁产生的4个必要条件之一即可。1。 破坏互斥条件若允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。2。破坏不剥夺条件当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺，或从而破坏了不剥夺条件。该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。3. 破坏请求并保持条件采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行，这些资源就一直归它所有，不再提出其他资源请求，这
1362024年操作系统考研复习指导样就可以保证系统不会发生死锁。这种方式实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。4。破坏循环等待条件为了破坏循环等待条件，可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源R，则该进程在以后的资源申请中就只能申请编号大于R;的资源。这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。
是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可以获得较好的系统性能。1。 系统安全状态避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待。所谓安全状态，是指系统能按某种进程推进顺序（P,P2,·,P,）为每个进程P;分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称P，P2,"·，P,为安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态。假设系统中有三个进程 P1，P2和 P3，共有 12 台磁带机。进程 P,共需要 10 台磁带机，P2和P分别需要 4 台和 9 台。假设在 T时刻，进程P，P2和表 2.5资源分配P已分别获得5台、2台和2台，尚有3台未分配，见进程最大需求已分配可用表2.5。P1053在 T时刻是安全的，因为存在一个安全序列P2,P1,P242P3，只要系统按此进程序列分配资源，那么每个进程都P3392能顺利完成。也就是说，当前可用磁带机为3台，先把3 台磁带机分配给P2以满足其最大需求，P2结束并归还资源后，系统有5台磁带机可用；接下来给P,分配5台磁带机以满足其最大需求，P结束并归还资源后，剩余10台磁带机可用；最后分配7台磁带机给P3，这样P也能顺利完成。若在 T时刻后，系统分配1台磁带机给 P3，系统剩余可用资源数为 2，此时系统进入不安全状态，因为此时已无法再找到一个安全序列。当系统进入不安全状态后，便可能导致死锁。例如，把剩下的 2 台磁带机分配给 P2，这样，P2完成后只能释放 4台磁带机，既不能满足 P又不能满足P3，致使它们都无法推进到完成，彼此都在等待对方释放资源，陷入僵局，即导致死锁。并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。
第2章进程与线程1372。 银行家算法银行家算法是最著名的死锁避免算法，其思想是：把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。（1）数据结构描述可利用资源向量Available：含有m个元素的数组，其中每个元素代表一类可用的资源数目。Available[]=K表示系统中现有Ry类资源K个。最大需求矩阵 Max：nxm 矩阵，定义系统中 n个进程中的每个进程对m类资源的最大需求。简单来说，一行代表一个进程，一列代表一类资源。Max[i,]=K表示进程i需要 R,类资源的最大数目为K。Allocation[i,J=K表示进程i当前己分得Ry类资源的数目为K。初学者容易混淆Available向量和Allocation 矩阵，在此特别提醒。需求矩阵Need：nxm矩阵，表示每个进程接下来最多还需要多少资源。Need[i,j]=K表示进程i还需要R,类资源的数目为K。上述三个矩阵间存在下述关系：Need = Max- Allocation一般情况下，在银行家算法的题目中，Max矩阵和Allocation矩阵是已知条件，而求出Need矩阵是解题的第一步。（2）银行家算法描述设 Request;是进程 P;的请求向量，Request;[]=K表示进程 P;需要j类资源 K 个。当 P;发出资源请求后，系统按下述步骤进行检查：·①若Request;[]≤Need[i,小，则转向步骤②；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。②若Request[]≤Available[]，则转向步骤③；否则，表示尚无足够资源，P;须等待。③系统试探着把资源分配给进程P，并修改下面数据结构中的数值：Available = Available-- Request,;:Allocation[i, j] = Allocation[i, j]+ Request,[/];Need[i, J] = Need[i, j]- Request,[/];④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程P；，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程P;等待。（3）安全性算法始时， Work = Available。①初始时安全序列为空。，②从Need矩阵中找出符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于或等于Work向量，找到后，把对应的进程加入安全序列；若找不到，则执行步骤④。
1382024年操作系统考研复习指导③进程P;进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，因此应执行Work=Work+Allocation[]，其中 Allocation[i]表示进程 P;代表的在 Allocation 矩阵中对应的行，返回步骤②。④若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态。，看完上面对银行家算法的过程描述后，可能会有眼花缭乱的感觉，现在通过举例来加深理解。3.安全性算法举例假定系统中有5个进程{Po,P，P2,P3,P4}和三类资源{A,B,C}，各种资源的数量分别为 10,5,7，在T时刻的资源分配情况见表2.6。T。时刻的安全性。利用安全性算法对T时刻的资源分配进行分析。表 2.6T。时刻的资源分配表资源情况MarAllocationAvailable进程ABCABCABCPo753010P322200332(3 0 2)(2 3 0)P29.0.2302222211P433002①从题目中我们可以提取Max矩阵和Allocation 矩阵，这两个矩阵相减可得到 Need矩阵：7 537o 1 074"322 0 2 0226022110.[o 0. 2]4331441MaxAllocationNeed②然后，将 Work 向量与 Need 矩阵的各行进行比较，找出比 Work 矩阵小的行。例如，在初始时，(3,3,2) >(1,2,2)(3,3,2) > (0,1,1)对应的两个进程分别为P,和 P3，这里我们选择P，（也可以选择P）暂时加入安全序列。③释放 P,所占的资源，即把 P, 进程对应的Allocation 矩阵中的一行与Work 向量相加:(3 3 2)+(2 0 0)=(5 3 2)=-Work此时需求矩阵更新为（去掉了P,对应的一行)：P[7 43]P|6 0 0lP[0 1 1P[4 3 1]再用更新的 Work 向量和 Need 矩阵重复步骤②。利用安全性算法分析 T时刻的资源分配情况如表 2.7所示，最后得到一个安全序列{P,P3,P4,P2,Po}。
第2章进程与线程139表 2.7T。 时刻的安全序列的分析资源情况WorkNeedAllocationWork+Allocation进程ABABA.AcBcB0.5P:32220312231P321175130AP443310075P2456003107471074300101.4.银行家算法举例安全性算法是银行家算法的核心，在银行家算法的题目中，一般会有某个进程的一个资源请求向量，读者只要执行上面所介绍的银行家算法的前三步，马上就会得到更新的 Allocation 矩阵和Need矩阵，再按照上例的安全性算法判断，就能知道系统能否满足进程提出的资源请求。假设当前系统中资源的分配和剩余情况如表2.6所示。（1）P,请求资源：P,发出请求向量Request(1,0,2)，系统按银行家算法进行检查：Request;(1, 0, 2)≤Need;(1, 2, 2)Request;(1, 0, 2)≤Available;(3, 3, 2)系统先假定可为P，分配资源，并修改Available = Available - Request, = (2, 3, 0) ·Allocation; = Allocation, + Request; = (3, 0, 2)Need, = Need, -- Request = (0, 2, 0)由此形成的资源变化情况如表 2.6 中的圆括号所示。令 Work=Available=(2,3,0)，再利用安全性算法检查此时系统是否安全，如表 2.8所示。表 2.8 P,申请资源时的安全性检查资源情况WorkNeedAllocationWork+Allocation进程BABAC.ABcABCcP130.232532.2P50111743P47434310027457307Po>105P275560。302105√由所进行的安全性检查得知，可找到一个安全序列{P,P3,P4,Po,P2)。因此，系统是安全的，可以立即将 P所申请的资源分配给它。分配后系统中的资源情况如表 2.9所示。表2.9为 P,分配资源后的有关资源数据资源情况AllocationNeedAvailable进程BCBCBAAAc01743230P13020206P230:20211P31P4002
1402024年操作系统考研复习指导(2）P4请求资源：P4发出请求向量Request4(3,3,0)，系统按银行家算法进行检查：Request(3, 3, 0)≤Need4(4, 3, 1);Request4(3, 3, 0) > Available(2, 3, 0), 让 P4 等待。(3）Po请求资源：Po发出请求向量 Requsto(0,2,0)，系统按银行家算法进行检查:Requesto(0, 2, 0)≤Needo(7, 4, 3);Requesto(0, 2, 0)≤Available(2, 3, 0)系统暂时先假定可为Po分配资源，并修改有关数据：Available = Available - Requesto = (2, 1, 0)Allocationo = Allocationo + Requesto = (0, 3, 0)Needo= Needo-Requesto =(7, 2,3)，结果如表 2.10 所示。表 2.10为 P。分配资源后的有关资源数据资源情况 AllocationNeedAvaflable进程ABCABBcPo030723210P302020P230200P32101<P4024进行安全性检查：可用资源Available(2,1,0)已不能满足任何进程的需要，因此系统进入不安全状态，因此拒绝Po的请求，让 Po等待，并将Available,Allocationo,Needo恢复为之前的值。
前面介绍的死锁预防和避免算法，都是在为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不采取任何措施，则应该提供死锁检测和解除的手段。1。 资源分配围系统死锁可利用资源分配图来描述。如图2.15所示，用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，因此用框中的一个圆代表一类资源中的一个资源。从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程。在图 2.15 所示的资源分配图中，进程P,已经分得了两个 R资源，并又请求一个 R2资源；进程P2分得了一个 R,资源和一个图 2.15资源分配示例R2资源，并又请求一个 R,资源。2. 死锁定理简化资源分配图可检测系统状态S是否为死锁状态。简化方法如下：1）在资源分配图中，找出既不阻塞又不孤点的进程P：（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于或等于系统中已有的空闲资源数量，如在图 2.15 中，R没有空闲资源，R2有一个空闲资源。若所有连接该进程的边均满足上述条件，则这个进
第 2 章 进程与线程141程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。在图 2.16(a)中，P,是满足这一条件的进程结点，将 P的所有边消去，便得到图 2.16(b)所示的情况。这里要注意一个问题，判断某种资源是否有空闲，应该用它的资源数量减去它在资源分配图中的出度，例如在图 2.15 中，R, 的资源数为 3，而出度也为 3，所以 R,没有空闲资源，R2的资源数为2，出度为1，所以 R2有一个空闲资源。2）进程P;所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在图 2.15 中，进程 P2就满足这样的条件。根据 1）中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的，如图2.16(c)所示。( P,P0.000oooo微信公众号：edjky66(a)(b)图 2.16 资源分配图的化简S 为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。3.死锁解除一旦检测出死锁，就应立即采取相应的措施来解除死锁。死锁解除的主要方法有：1）资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源乏的状态。2）撤销进程法。强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。3）进程回退法。让一（或多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺。要求系统保持进程的历史信息，设置还原点。
灰大专防机芯1。进程与程序的区别与联系1）进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。进程的运行实体是程序，离开程序的进程没有存在的意义。从静态角度看，进程是由程序、数据和进程控制块（PCB）三部分组成的。而程序是一组有序的指令集合，是一种静态的概念。2）进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定的生命周期，是暂时
存在的；而程序则是一组代码的集合，是永久存在的，可长期保存。3）一个进程可以执行一个或几个程序，一个程序也可构成多个进程。进程可创建进程，而程序不可能形成新的程序。‘4）进程与程序的组成不同。进程的组成包括程序、数据和PCB。2.死皱与饥饿一组进程处于死锁状态是指组内的每个进程都在等待一个事件，而该事件只可能由组内的另一个进程产生。这里所关心的主要是事件是资源的获取和释放。与死锁相关的另一个问题是无限期阻塞（Indefinite Blocking）或饥饿（Starvation），即进程在信号量内无穷等待的情况。产生饥饿的主要原因是：在一个动态系统中，对于每类系统资源，操作系统需要确定一个分配策略，当多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序。有时资源分配策略可能是不公平的，即不能保证等待时间上界的存在。在这种情况下，即使系统没有发生死锁，某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时，称发生了进程“饥饿”，当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时，称该进程被“饿死”：例如，当有多个进程需要打印文件时，若系统分配打印机的策略是最短文件优“饿死”。“饥饿”并不表示系统一定会死锁，但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别如下：1）进入“饥饿”状态的进程可以只有一个，而因循环等待条件而进入死锁状态的进程却必须大于或等于两个。2）发生“饥饿”的进程的状态可能是就绪态（长期得不到处理机)，也可能是阻塞态·（如长期得不到所需的IO设备），而发生死锁的进程的状态则必定是阻塞态。3.银行家算法的工作原理银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，若有则先进行试分配，并对分配后的新状态进行安全性检查。若新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免了死锁现象的发生。4。 进程同步、互斥的区别和联系并发进程的执行会产生相互制约的关系：一种是进程之间竞争使用临界资源，只能让它们逐个使用，这种现象称为互斥，是一种竞争关系；另一种是进程之间协同完成任务，在关键点上等待另一个进程发来的消息，以便协同一致，是一种协作关系。