操作系统课件：Chapter-02进程管理

进程管理第二章2.1什么是进程2.2进程控制2.3进程同步2.4经典IPC问题2.5管程2.6进程高级通信2.7线程1什么是进程（1）为了提高计算机系统中各种资源的利用率，现代操作系统广泛采用多道程序技术（multi-programming），使多个程序同时在系统中存在并运行。Whyprocesses?2什么是进程（2）3什么是进程（3）在多道程序系统中，各个程序之间是并发执行的，共享系统资源。CPU需要在各个运行的程序之间来回地切换，这样的话，要想描述这些多道的并发活动过程就变得很困难。MIT的MULTICS系统中首先引入了“进程”(Process)概念。4什么是进程（4）一个进程应该包括：程序的代码；程序的数据；PC中的值，用来指示下一条将运行的指令；一组通用的寄存器的当前值，堆、栈；一组系统资源（如打开的文件）Aprocess＝aprograminexecution5什么是进程（5）程序是文本，是语句的描述（静态）进程是运行中的程序，含有上下文信息（动态）Process≠Programmain()

{…..}A()

{…..}

PROCESSmain()

{…..}A()

{…..}

PROGRAMheap

StackAMainRegisters,PC6什么是进程（6）一位有手好厨艺的计算机科学家正在为他的女儿烘制生日蛋糕。他有做生日蛋糕的食谱，厨房里有所需的原料：面粉、鸡蛋、糖、香草汁等。食谱＝程序；科学家＝CPU；

原料＝数据；进程＝做蛋糕；7什么是进程（7）现在假设计算机科学家的儿子哭着跑了进来，说他被一只蜜蜂蜇了。计算机科学家就记录下食谱做到哪儿了（保存进程的当前状态），然而拿出一本急救手册，按照其中的指示处理蜇伤。CPU从一个进程（做蛋糕）切换到另一个进程（医疗救护）。8什么是进程（8）进程特征结构特征：程序段、相关的数据段、PCB构成了进程实体动态性：进程是进程实体的一次执行，进程的状态总是在变化，PCB的内容总是在变化并发性：多个进程实体，同存于内存中，能在一段时间内同时运行（宏观上）9什么是进程（9）进程特征独立性：独立运行和资源调度的基本单位。每个进程都有“自己”的PC和内部状态，运行时独立于其他的进程（逻辑PC和物理PC）异步性：以各自独立的、不可预知的速度向前推进10什么是进程（10）4个进程并发执行11什么是进程（11）进程与程序的区别：程序是静态的被动的，进程是动态的，主动的。程序在外存上存储，进程在内存中实现；程序没有PCB，无法并发执行，无法被调度，而进程相反。一个程序多次执行可以产生多个进程，一个进程可以执行多个程序。12什么是进程（12）进程的三种基本状态1)就绪(Ready)状态：进程一旦获得CPU就可以投入运行的状态2)执行状态：进程获得CPU正在运行的状态3)阻塞状态：进程由于等待资源或某个事件的发生而暂停执行的状态13什么是进程（13）可能的进程状态运行阻塞就绪状态间的转化14什么是进程（14）运行

阻塞等待I/O的结果等待某一进程提供输入运行

就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态就绪

运行调度程序选择一个新的进程运行阻塞就绪当所等待的事件发生时15什么是进程（15）在某些系统中，由于一些特殊的原因（比如说考察进程情况或者调节系统负荷），进程被从内存中调出进驻外存，不再接受调度。这种新的状态被称为挂起状态。16什么是进程（16）ReadyaRunningBlockedaBlockedsReadyswakeup(唤醒)事件发生挂起suspend时间片完被调度schoduler解挂

active挂起

suspend解挂

active挂起

suspend等待事件

sleep事件发生wakeup(唤醒)17什么是进程（17）描述进程的数据结构：进程控制块（ProcessControlBlock，PCB）。进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构，PCB中记录了操作系统所需要的，用于描述进程情况及控制进程运行所需的全部信息。OS是根据PCB来对并发执行的进程进行控制和管理的。进程控制块（PCB）18什么是进程（18）PCB的内容19什么是进程（19）系统用PCB来描述进程的基本情况以及运行变化的过程，PCB是进程存在的唯一标志。进程的创建：为该进程生成一个PCB；进程的终止：回收它的PCB；进程的组织管理：通过对PCB的组织管理来实现；进程的状态转换：……？20什么是进程（20）两个进程的状态转换21什么是进程（21）将CPU切换到另一进程需要保存原来进程的状态并装入新进程的保存状态，这被称为上下文切换。上下文切换时间是额外开销，因为切换时系统并不能做什么有用的工作。上下文切换时间与硬件支持密切相关。上下文切换22什么是进程（22）PCB的组织-链接23什么是进程（23）PCB的组织-索引24什么是进程（24）就绪队列和各种I/O设备队列25进程控制（1）引起进程创建的四个主要事件系统初始化时；在一个正在运行的进程当中，执行了创建进程的系统调用；用户请求创建一个新进程；初始化一个批处理作业。进程创建26进程控制（2）从技术上来说，只有一种创建进程的方法，即在一个已经存在的进程（用户进程或系统进程）当中，通过系统调用来创建一个新的进程。Unix：fork函数；Windows：CreateProcess函数;进程创建27进程控制（3）进程的创建(CreationofProgress)步骤(1)申请空白PCB(2)为新进程分配资源(3)初始化进程控制块(4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列进程创建28进程控制（4）在以下四种情形下，进程终止：正常退出（自愿的）；错误退出（自愿的）；致命错误（强制性的）；被其他进程所杀（强制性的），

Unix：kill，

Windows：TerminateProcess。进程终止29进程控制（5）进程的终止步骤(1)读出该进程的状态。(2)终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3)将其所有子孙进程予以终止(4)将被终止进程所拥有的全部资源归还给其父进程或者系统。(5)将被终止进程的PCB从所在队列(或链表)中移出。进程终止30进程控制（6）引起进程阻塞和唤醒的事件(1)请求系统服务(2)启动某种操作(3)新数据尚未到达(4)无新工作可做进程阻塞与唤醒31进程控制（7）进程阻塞过程(1)调用阻塞原语block把自己阻塞(2)将PCB插入阻塞队列(3)最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。

进程阻塞与唤醒32进程控制（8）进程唤醒过程(1)首先把被阻塞的进程从等待该事件的阻塞队列中移出(2)将其PCB中的现行状态由阻塞改为就绪(3)然后再将该PCB插入到就绪队列中。进程阻塞与唤醒33进程控制（9）进程的挂起过程修改进程状态PCB复制到某指定的内存区域如有必要转调度程序进程的激活过程进程调入内存修改进程状态如抢占调度考虑是否执行进程的挂起与激活34进程同步（1）进程间通信（InterProcess

Communi-

cation，IPC）：进程之间的信息交流与协调。如果两个并发运行的进程之间没有任何关联关系（直接的或间接的），那么无须通信；如果两个并发运行的进程之间存在着某种关联关系（直接的或间接的），那么可能需要通信。例

如：两个进程使用相同的一个共享文件。35进程同步（2）进程间如何来通信呢，如何来相互传递信息呢？当两个或多个进程在进行一些关键性的临界活动时（如对共享资源的访问），如何确保它们不会相互妨碍——进程互斥问题；当进程之间存在着某种依存关系时，如何来调整它们的运行次序——进程同步问题。36进程同步（3）进程的互斥spoolerdirectory:假脱机目录，装着要打印的内容，进程A和B同时要求打印，out指向下一个要打印的文件，in指向下一个空闲槽位。37进程同步（4）...next_free_slot=in;write"file_a"toitemnext_free_slot++;updatein;...processAprocessB...next_free_slot=in;write"file_b"toitemnext_free_slot++;updatein;...next_free_slot=in;//7next_free_slot=in;//7write"file_b"toitemfile_bnext_free_slot++;//8updatein;//8write"file_a"toitemfile_anext_free_slot++//8;updatein;//838进程同步（5）竞争条件（racecondition）：两个或多个进程对同一共享数据同时进行读写操作，而最后的结果是不可预测的，它取决于各个进程具体运行情况。解决之道：在同一时刻，只允许一个进程访问该共享数据，即如果当前已有一个进程正在使用该数据，那么其他进程暂时不能访问。这就是互斥的概念。39进程同步（6）进程在运行过程中所做的工作分为两类：内部计算（不会导致竞争条件）对共享内存或共享文件的访问（可能导致竞争条件）我们把完成第二类工作的程序称为“临界区”，把需要互斥访问的共享资源称为“临界资源”。如果我们能设计出某种方法，使得任何两个进程都不会同时出现在临界区中，就可以避免竞争条件的出现。临界资源和临界区的引入40进程同步（7）Repeat

entrysection

criticalsection

exitsectionremaindersectionUntilfalse对含有临界区进程的描述41进程同步（8）任何两个进程都不能同时进入临界区；不能事先假定CPU的个数和运行速度；当一个进程运行在它的临界区外面时，不能妨碍其他的进程进入临界区；任何一个进程进入临界区的要求应该在有限时间内得到满足。实现互斥访问的四个条件42进程同步（9）使用临界区的互斥43进程同步（10）信号量机制

1965年，由荷兰学者Dijkstra

提出了信号量机制提出goto有害论最短路径算法的创造者Algol60编译器的设计者和实现者THE操作系统的设计者和开发者提出信号量机制解决了有趣的“哲学家聚餐”问题44进程同步（11）整形信号量最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(AtomicOperation)wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。wait(S):whileS≤0dono-opS:=S-1;signal(S):S:=S+1;45进程同步（12）整形信号量whileS≤0dono-opS:=S-1;临界区S:=S+1;whileS≤0dono-opS:=S-1;临界区S:=S+1;process0process1S：1whileS≤0dono-opS:=S-1;0临界区whileS≤0dono-op执行阻塞就绪P0P1时间片还没完，我再歇会......S:=S+1;S:=S-1;临界区S:=S+1;46进程同步（13）记录型信号量信号量被描述为一个记录（或者结构）。

typesemaphore=recordvalue:integer;L:listofprocess;endvalueL47进程同步（14）P原语操作的定义：procedurewait(S)

varS:semaphore;begin

S.value:=S.value-1;ifS.value＜0then block(S,L)end48进程同步（15）V原语操作的定义：proceduresignal(S)

varS:semaphore;begin

S.value:=S.value+1;ifS.value≤0then wakeup(S,L);end49进程同步（16）在记录型信号量机制中，S.value的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value:=S.value-1；当S.value＜0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。信号量值的意义50进程同步（17）当n个进程互斥的使用某个临界资源时，我们可以为此临界资源设置一个用于互斥访问的信号量mutex，并初始化为1。每个进程的组织结构如下：

利用信号量实现进程互斥wait(mutex)临界区signal(mutex)剩余区51进程同步（18）实例：有3个客户在某天的日常生活中使用了某个ATM自动取款机。假设他们对ATM的使用顺序是a到来，a进入，b到来，c到来，a离开，b进入，b离开，c进入，c离开。52进程同步（19）P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)53进程同步（20）执行阻塞就绪1^0^-1Pcb_b-2Pcb_bPcb_c-1Pcb_c0^1^信号量变化54进程同步（21）某阅览室，最多可容纳100名读者同时阅览，当阅览室中少于100名读者时，阅览室外等候的读者可以立即进入，否则需要在外面等待。每个读者可看成一个进程。互斥例题55进程同步（22）semaphoreseats；seats.value=100;while(阅览时间){wait(seats);进入阅览室；阅读；离开阅览室；signal(seats);}56进程同步（23）互斥中可能出现的死锁processA:……wait(Dmutex);

wait(Emutex);……signal(Dmutex);signal(Emutex);……

processB:……wait(Dmutex); wait(Emutex);……signal(Dmutex);signal(Emutex);……

57进程同步（24）AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。这样就可避免上述死锁情况的发生。AND型信号量58进程同步（25）Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1thenfori:=1tondo

Si:=Si-1;

endforelse

将进程放入第一个Si

<1的信号量阻塞队列，设置进程pc到swait操作的开始处endif59进程同步（26）Ssignal(S1,S2,…,Sn)fori∶=1tondo

Si=Si+1;

将所有si信号量阻塞队列中的进程转入就绪队列endfor;60进程同步（27）一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理（一次需要N个某类临界资源时，就要进行N次wait操作－－低效又可能死锁）一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请信号量集61进程同步（28）进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si>=ti；即当资源数量低于ti时，便不予分配）；占用值为di（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);信号量集62进程同步（29）Swait(S1,t1,d1,…,Sn,tn,dn)ifSi≥t1and…and

Sn≥tnthenfori∶=1tondo

Si∶=Si-di;

endforelse将进程放入第一个Si＜ti的信号量阻塞队列，设置进程pc到swait操作的开始处

endif63进程同步（30）signal(S1,d1,…,Sn,dn)fori∶=1tondo

Si∶=Si+di;将所有si信号量阻塞队列中的进程转入就绪队列

endfor;64进程同步（31）一般“信号量集”的几种特殊情况：(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S＞1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。65进程同步（32）进程间的同步是指多个进程中发生的事件存在某种时序关系，因此在各个进程之间必须协同合作，相互配合，使各个进程按一定的速度执行，以共同完成某一项任务。进程的互斥实质上也是一种同步关系，进程互斥可以看作是一种特殊的进程同步。为便于区分，把进程同步特指为对执行顺序严格要求的同步问题。同步：合作。 互斥：竞争。利用信号量实现进程同步66进程同步（33）【例子1】司机与售票员while(上班时间){

发动汽车；正常运行；到站停车；}while(上班时间){

关闭车门；售票；打开车门；}只有关闭车门以后，才能启动汽车；只有停车以

后，才能打开车门。67进程同步（34）【例子2】三个并发进程的读写get进程负责从输入序列f中读取字符，送到缓冲区s中；copy进程把缓冲区s中的数据复制到缓冲区t；put进程从缓冲区t中取出数据打印。68进程同步（35）【例子1】司机与售票员while(上班时间){

P(S_Door);

发动汽车；正常运行；到站停车；

V(S_Stop);}公车司机while(上班时间){

关闭车门；

V(S_Door);

售票；

P(S_Stop);

打开车门；}售票员semaphoreS_Door；//初始化为0semaphoreS_Stop; //初始化为0先关门

后开车先停车

后开门69进程同步（36）【例子1】司机与售票员while(上班时间){

P(S_Door);

发动汽车；正常运行；到站停车；

V(S_Stop);}公车司机while(上班时间){

P(S_Stop);打开车门；关闭车门；

V(S_Door);

售票；

}售票员semaphoreS_Door；//初始化为1semaphoreS_Stop; //初始化为0先关门

后开车先停车

后开门70进程同步（37）【例子2】三个并发进程的读写设有一个缓冲区buffer，大小为一个字节。Compute进程不断产生字符，送buffer，Print进程从buffer中取出字符打印。如不加控制，会出现多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有Compute和Print进程的运行刚好匹配的一种是正确的，其它均为错误。bufferComputePrint71进程同步（38）解题步骤：分析问题，弄清楚同步关系；设置信号量，说明其含义和初值；写出程序描述。问题分析：要保证打印结果的正确，Compute和Print进程必须遵循以下同步规则：当Compute把数据送入buffer后，Print才能从

buffer中取，否则它必须等待（先存后取）；当Print从buffer取走数据后，Compute才能将

新数据送buffer，否则也须等待（先取后存）72进程同步（39）while(计算未完成){

P(S_Empty);

Write_Data()；

V(S_Full);}

Computewhile(打印未完成){

P(S_Full)；

Print_Data()；

V(S_Empty);}PrintsemaphoreS_Empty； //缓冲区是否为空，初值为1semaphoreS_Full; //是否有数据写入，初值为073进程同步（40）【例子2】三个并发进程的读写get进程负责从输入序列f中读取字符，送到缓冲区s中；copy进程把缓冲区s中的数据复制到缓冲区t；put进程从缓冲区t中取出数据打印。74进程同步（41）while(…){

P(S_Empty);

Get_Data(f,s)；

V(S_Full);}

Getwhile(…){

P(S_Full)；

P(T_Empty);

Copy_Data(s,t);

V(S_Empty);

V(T_Full);}Copywhile(…){

P(T_Full);

Put_Data(t,g)；

V(T_Empty);}

Put75进程同步（42）信号量解决互斥问题while(……){

P(S);

临界区；

V(S);}while(……){

P(S);

临界区；

V(S);}while(……){

P(S);

临界区；

V(S);}while(……){

P(S);

临界区；

V(S);}while(……){

P(S);

临界区；

V(S);}while(……){

P(S);

临界区；

V(S);}while(……){

P(S);

临界区；

V(S);}while(……){

P(S);

临界区；

V(S);}while(……){

P(S);

临界区；

V(S);}76进程同步（43）信号量解决同步问题while(……){

P(S1);

……

V(S2);}while(……){

P(S2);

……V(S1);}互相合作的两个进程只有一个可以先执行；信号量S1和S2的初值，一个为1，一个为077进程同步（44）有一个仓库，可以存放A和B两种产品。要求：1)每次只能存入一种产品(A或B)；2)-N<A产品数量-B产品数量<M。试用PV操作描述产品A与产品B的入库过程。同步与互斥的混合问题78进程同步（45）同步与互斥的混合问题while(……){

P(Sa);

P(mutex);

将产品入库；

V(mutex);

V(Sb);}semaphoremutex；//初始化为1semaphoresa;//初始化为m-1semaphoresb;//初始化为n-1while(……){

P(Sb);

P(mutex);

将产品入库；

V(mutex);

V(Sa);}79经典IPC问题（1）生产者-消费者问题哲学家就餐问题读者-写者问题用信号量来解决，主要问题：如何选择信号量，如何安排P、V原语的顺序。80经典IPC问题（2）两个进程（生产者和消费者）共享一个公有的、固定大小的缓冲区，生产者不断地制造产品，并把它放入缓冲区，而消费者不断地把产品取出来，并且使用它。要求两个进程都能正确地工作。 生产者-消费者问题描述81经典IPC问题（3）12345678生产者生产—消费者问题消费方向生产方向消费者82经典IPC问题（4）对于生产者进程：制造一个产品，当要送入缓冲区时，要检查缓冲区是否已满，若未满，才可将产品送入缓冲区，并在必要时通知消费者；否则等待；对于消费者进程：当它去取产品时，先要检查缓冲区中是否有产品可取，若有，则取走一个，并在必要时通知生产者；否则等待。这种相互等待，并互通信息就是典型的进程同步。同时，缓冲区是个临界资源，因此，各个进程在使用缓冲区的时候，还有一个互斥的问题。生产者-消费者问题解析83经典IPC问题（5）semaphoreS_Buffer_Num; //空闲的缓冲区个数，初值为NsemaphoreS_Product_Num; //缓冲区当中的产品个数，初值为0semaphoreS_Mutex; //用于互斥访问的信号量，初值为184经典IPC问题（6）voidproducer(void)

{

intitem;

while(TRUE){

item=produce_item(); //制造一个产品

P(S_Buffer_Num); //是否有空闲缓冲区

P(S_Mutex); //进入临界区

insert_item(item); //产品放入缓冲区

V(S_Mutex); //离开临界区

V(S_Product_Num); //新增了一个产品

}}85经典IPC问题（7）voidconsumer(void)

{

intitem;

while(TRUE){

P(S_Product_Num); //缓冲区中有无产品

P(S_Mutex); //进入临界区

item=remove_item() //从缓冲区取产品

V(S_Mutex); //离开临界区

V(S_Buffer_Num); //新增一个空闲缓冲区

consume_item(item); //使用该产品

}}86经典IPC问题（8）五个哲学家围坐在一张圆桌旁，每个哲学家面前都摆着一大盘意大利面条，面条非常滑，所以每个哲学家都需要两把叉子才能进餐，在相邻两个盘子之间，只有一把叉子。桌面的布局见右图。哲学家就餐问题描述本图摘自“ModernOperatingSystems”012340123487经典IPC问题（9）哲学家就餐问题描述每个哲学家的动作只有两种：进餐和思考。当一个哲学家感到饥饿时，他试图去获得他左边和右边的两把叉子（一次取一把，顺序无关），然后才能开始进餐。吃完以后，他需要把两把叉子放回原处，然后继续思考。问题是：如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐，也不出现有人永远拿不到叉子。88经典IPC问题（10）#defineN5 //哲学家个数

voidphilosopher(inti)//哲学家编号：0－4

{

while(TRUE)

{

think(); //哲学家在思考

take_fork(i); //去拿左边的叉子

take_fork((i+1)%N); //去拿右边的叉子

eat(); //吃面条中….

put_fork(i); //放下左边的叉子

put_fork((i+1)%N); //放下右边的叉子

}}方案1：有可能死锁89经典IPC问题（11）方案2：改进版，仍有饥饿(starvation)可能while(1) //去拿两把叉子

{

take_fork(i); //去拿左边的叉子

if(fork((i+1)%N)){ //右边叉子还在吗

take_fork((i+1)%N);//去拿右边的叉子

break; //两把叉子均到手

}

else{ //右边叉子已不在

put_fork(i); //放下左边的叉子

wait_some_time(); //等待一会儿

}

}如果哲学家同时开始算法......90经典IPC问题（12）方案3：继续改进版，可以工作，但不佳while(1) //去拿两把叉子

{

take_fork(i); //去拿左边的叉子

if(fork((i+1)%N)){ //右边叉子还在吗

take_fork((i+1)%N);//去拿右边的叉子

break; //两把叉子均到手

}

else{ //右边叉子已不在

put_fork(i); //放下左边的叉子

wait_random_time(); //等待随机长时间

}

}91经典IPC问题（13）方案4：独吃大餐版，可以工作semaphoremutex //互斥信号量，初值1

voidphilosopher(inti)//哲学家编号i：0－4

{

while(TRUE){

think(); //哲学家在思考

P(mutex); //进入临界区

take_fork(i); //去拿左边的叉子

take_fork((i+1)%N); //去拿右边的叉子

eat(); //吃面条中….

put_fork(i); //放下左边的叉子

put_fork((i+1)%N); //放下右边的叉子

V(mutex); //退出临界区

}}其实mutex可以最大到4......92经典IPC问题（14）S1思考中…

S2进入饥饿状态；

S3如果左邻居或右邻居正在进餐，进入阻塞状态；

否则转S4

S4

拿起两把叉子；

S5吃面条…

S6放下左边的叉子，看看左邻居现在能否进餐

（饥饿状态、两把叉子都在），若能则唤醒之；

S7放下右边的叉子，看看右邻居现在能否进餐，

若能，唤醒之；

S8转S1一种比较好的思路93经典IPC问题（15）必须有一个数据结构，来描述每个哲学家的当前状态；该数据结构是一个临界资源，各个哲学家对它的访问应该互斥地进行——进程互斥；一个哲学家吃饱后，可能要唤醒它的左邻右舍，两者之间存在着同步关系——进程同步；解题关键问题94经典IPC问题（15）数据结构定义#defineN 5 //哲学家个数

#defineLEFT (i+N-1)%N //第i个哲学家的左邻居

#defineRIGHT (i+1)%N //第i个哲学家的右邻居

#defineTHINKING 0 //思考状态

#defineHUNGRY 1 //饥饿状态

#defineEATING 2 //进餐状态

int

state[N]; //记录每个人的状态

semaphoremutex; //互斥信号量，初值1

semaphores[N]; //每人一个信号量，095经典IPC问题（16）函数philosopher的定义voidphilosopher(inti)//i的取值：0到N－1

{

while(TRUE)

{

think(); //思考中…

take_forks(i); //拿到两把叉子或被阻塞

eat(); //吃面条中…

put_forks(i); //把两把叉子放回原处

}

}S1S2–S4S5S6–S796经典IPC问题（17）函数take_forks的定义//功能：要么拿到两把叉子，要么被阻塞起来。

voidtake_forks(inti)//i的取值：0到N－1

{

P(mutex); //进入临界区

state[i]=HUNGRY; //我饿了！

test(i); //试图拿两把叉子

V(mutex); //退出临界区

P(s[i]); //没有叉子便阻塞

}97经典IPC问题（18）函数test的定义voidtest(inti) //i的取值：0到N－1

{

if(state[i]==HUNGRY&&

state[LEFT]!=EATING&&

state[RIGHT]!=EATING)

{

state[i]=EATING; //两把叉子到手

V(s[i]); //第i人可以吃饭了

}

}98经典IPC问题（19）函数put_forks的定义//功能：把两把叉子放回原处，并在需要的时候，

//去唤醒左邻右舍。

voidput_forks(inti) //i的取值：0到N－1

{

P(mutex); //进入临界区

state[i]=THINKING; //交出两把叉子

test(LEFT); //看左邻居能否进餐

test(RIGHT); //看右邻居能否进餐

V(mutex); //退出临界区

}99经典IPC问题（20）读者-写者问题描述一个数据文件或记录，可被多个进程共享，只要求读文件的进程称为“Reader进程”，其他进程称为“Writer进程”。规则是：允许多个进程同时读，但不允许同时读写，或多个进程同时写。100经典IPC问题（21）读者-写者问题解析任何时候“写者”最多只允许一个，而“读者”可以有多个：“读—写”是互斥的；“写—写”是互斥的；“读—读”是允许的；101经典IPC问题（22）基于读者优先的解法假设读者来：1）若有其它读者在读，则不论是否有写者在等，新读者都可以读（读者优先）；2）若无读者、写者，则新读者也可以读；3）若无读者，且有写者在写，则新读者等待；假设写者来：1）若有读者，则新写者等待；2）若有其它写者，则新写者等待；3）若无读者和写者，则新写者可以写；102经典IPC问题（23）解题关键需要设置一个计数器rc，用来记录并发运行的读者个数；对于各个读者而言，该计数器是一个临界资源，对它的访问必须互斥进行，因此设置一个互斥信号量S_mutex；对于各个写者而言、写者与所有的读者而言，数据库是一个临界资源，对它的访问必须互斥地进行，因此设置一个互斥信号量S_db。103经典IPC问题（24）基于读者优先的解答int

rc=0; //并发读者的个数

semaphoreS_mutex; //对rc的互斥信号量，初值1

semaphoreS_db; //对数据库的信号量，初值1voidwriter(void)

{

while(TRUE){

think_up_data(); //生成数据，非临界区

P(S_db); //希望访问数据库

write_data_base(); //更新数据库

V(S_db); //退出临界区

}

}104经典IPC问题（25）voidreader(void)

{

while(TRUE){

P(S_mutex); //互斥地访问计数器rc

rc++; //新增了一个读者

if(rc==1)P(S_db);//如果是第一个读者…

V(S_mutex); //退出对rc的访问

read_data_base(); //读取数据库的内容

P(S_mutex); //互斥地访问计数器rc

rc--; //减少一个读者

if(rc==0)V(S_db);//如果是最后一个读者

V(S_mutex); //退出对rc的访问

use_data_read(); //使用数据，非临界区

}

}105南开天大之路（1）在南开大学和天津大学之间有一条弯曲的小路，其中从S到T（或T到S）一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M(同时允许两辆自行车停留)，可供两辆自行车已从两端进入小路情况下错车使用，如图所示。试设计一个算法使来往的自行车均可顺利通过。106南开天大之路（2）107南开天大之路（3）任何一段路不允许两辆车行驶。所以一个方向上只允许有一辆车。安全岛允许两辆车存在。所以安全岛不用设置同步机制。因为整条路最多只有两辆车。两个方向上的两辆车在两个支路只允许一辆车行驶。此题只有互斥没有同步。题目分析108南开天大之路（4）任何一段路不允许两辆车行驶。所以一个方向上只允许有一辆车。S到T的整条路对于南开的车是临界资源。T到S的整条路对于天大的车是临界资源。两个方向上的两辆车在两个支路只允许一辆车行驶。SK路段和LT路段对南开和天大的车都是临界资源。题目分析109南开天大之路（5）semaphoreST_mutex,TS_mutex,SK_mutex,LT_mutex;//初值1voidnankai(void){

P(ST_mutex)；

P(SK_mutex)；通过SK路段；进入安全岛M；

V(SK_mutex)；

P(LT_mutex)；通过LT路段：

V(LT_mutex)；

V(ST_mutex)；}voidtianda(void){

P(TS_mutex)；

P(LT_mutex)；通过LT路段；进入安全岛M；

V(LT_mutex)；

P(SK_mutex)；通过SK路段：

V(SK_mutex)；

V(TS_mutex)；}110和尚喝水（1）某寺庙，有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为3个(老和尚和小和尚共同使用）。每次入水、取水仅为一桶，且不可同时进行。试给出有关取水、入水的算法描述。111和尚喝水（2）很显然这个问题包含了互斥和同步。在使用到井(well)，缸(urn)，桶(bucket)时，必须互斥的使用。对于入水和取水来说则是生产者和消费者问题。题目分析112和尚喝水（3）取水时要查看水缸是否有“full资源”，没有则阻塞。取水后，释放一个“empty资源”，如果必要唤醒一个入水的进程。入水时要查看水缸是否有“empty资源”，没有则阻塞。入水后，释放一个“full资源”，如果必要唤醒一个取水的进程。题目分析113和尚喝水（4）测试full资源;取来水桶；缸中取水；将水倒入饮水容器；还回水桶；释放empty资源;喝水；测试empty资源;取来水桶；井边打水；入水进缸；还回水桶；释放full资源;取水入水Semaphorewell,urn,bucket,empty,full;//初值1,1,3,10,0114和尚喝水（5）while(取水时间){p(full);p(bucket);取来水桶；p(urn);缸中取水；v(urn);将水倒入饮水容器；还回水桶；v(bucket);v(empty);喝水；}while(入水时间){p(empty);p(bucket);取来水桶；p(well);井边打水；v(well);p(urn);入水进缸；v(urn);还回水桶；v(bucket);v(full);}115管程（1）使用困难：各并发进程间的逻辑关系比较复杂，在使用信号量时，必须小心谨慎，稍有不当（如P、V操作的次序错误、重复或遗漏）就会出错；出错后果严重：如竞争状态、死锁和各种无法预料的、不可重现的错误现象；可读性差：信号量的控制分布在整个程序中，其正确性分析很困难；维护困难：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局。信号量方法的缺点116管程（2）为了更容易地编写出正确的程序，Hoare(1974)和Hansen(1975)提出了管程(monitor)的概念。其基本思想是：将共享变量以及对共享变量所进行的操作封装在一个模块中。管程的引入117管程（3）管程是由一组变量、数据结构和函数所构成的一种特殊的软件模块。monitor

example

integer

i;

condition

c;

procedure

producer();

…

end;

procedure

consumer();

…

end;

endmonitor;118管程（4）封装性：进程可以调用管程当中的函数，但是不能直接访问管程的内部数据结构；互斥性：在任何时候，只允许一个进程在管程中活动（即调用管程的函数）；语言相关性：管程属于编程语言的范畴，由编译器来识别并实现对管程内函数的互斥访问。管程的特性119管程（5）互斥：把共享数据封装在管程内，把各个进程的临界区变成管程当中的函数。这样就能够保证任何两个进程都不会同时进入它们的临界区；同步：在管程内部，应当具有某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时应使其等待。因此在管程内部可以声明和使用一种特殊类型的变量----条件变量（conditionvariables）。基于管程的进程同步与互斥120管程（6）管程的结构conditionc1wait(c1)…conditioncn

wait(cn)

局部数据条件变量过程1过程k出口初始化代码入口管程等待调用的进程队列管程等待区域…121管程（7）条件变量：用来描述等待的原因。每个条件变量表示一种等待的原因，它不取具体的数值。对条件变量的操作：wait和signal；当一个管程函数发现它不能继续执行下去时，使用wait操作，使得调用它的进程进入阻塞状态，同时允许其他的进程进入管程；而signal操作的作用是唤醒某个正在等待的进程；条件变量122管程（8）通过wait和signal操作即可实现进程间同步关系；

wait操作和signal操作有点类似于P、V原语，但条件变量不取具体的数值，不进行信号的累加，因此在signal操作发出信号前，必须有wait操作在等待，否则该信号就丢失了。条件变量123管程（9）问题：当一个进程P用signal操作唤醒另外一个进程Q时，如何避免两个进程同时位于管程当中呢？P等待，Q先执行，直到它退出管程或者再次被阻塞；P继续执行，等它退出管程后Q再执行；P在执行signal操作后立即退出管程，即把signal作为管程函数的最后一条语句。124管程（10）125进程高级通信（1）低级通信：只能传递状态和整数值（控制信息），包括用来实现进程同步和互斥的信号量和管程机制。优点是速度快。缺点是：传送信息量小：每次通信传递的信息量固定，若需要传递较多信息，就得进行多次通信。编程复杂：用户需要直接去实现通信的细节，编程复杂，容易出错。高级通信：能够传送任意数量的数据，包括三类：共享内存、管道、消息。低级通信与高级通信126进程高级通信（2）绝大多数现代的操作系统都提供了相应的方法，来让各个进程共享它们地址空间当中的某些部分，即共享内存。在共享内存中，可以任意读写和使用任意的数据结构（缓冲区）。一组进程向共享内存中写，另一组进程从共享内存中读，通过这种方式实现两组进程间的信息交换。类似于生产者－消费者问题中的缓冲区，需要进程的同步和互斥机制来确保数据的一致性。共享内存127进程高级通信（3）管道通信由UNIX首创，由于其有效性，后来的一些系统相继引入了管道技术；管道通信以文件系统为基础，所谓管道即连接两个进程之间的一个打开的共享文件，专用于进程之间的数