【教学课件】第二章进程管理.ppt

《【教学课件】第二章进程管理.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章进程管理.ppt（153页珍藏版）》请在三一办公上搜索。

1、1,2023/8/7,第二章 进程管理,2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与线程,2,2023/8/7,2.1 进程的基本概念,2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图,3,2023/8/7,前趋图举例,=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P5,P7),(P6,P7)PiPj称Pi是Pj的直接前趋，Pj是Pi的直接后继,4,2023/8/7,前趋图中必须不存在循环

2、,图例中存在前趋关系S2S3和S3 S2，显然，这种前趋关系是无法满足的。,5,2023/8/7,2.1 进程的基本概念,2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图,6,2023/8/7,程序顺序执行,程序执行过程中通常存在顺序执行问题构成程序的若干个程序段之间组成程序段的多条语句之间,S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;,7,2023/8/7,程序顺序执行时的特征,顺序性处理机的操作，严格按照规定顺序执行封闭性封闭环境下运行，程序独占全机资源只有当前运行程序才能改变资源状态

3、程序执行结果不受外界因素的影响可再现性只要程序执行时的环境和初始条件相同，程序重复执行结果相同,8,2023/8/7,程序顺序执行时的特性，将为程序员检测和校正程序的错误，带来极大的方便,9,2023/8/7,2.1 进程的基本概念,2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图,10,2023/8/7,程序并发执行例1,程序段语句间并发执行S1:a:=x+2 S2:b:=y+4S3:c:=a+b S4:d:=c+6,11,2023/8/7,程序并发执行例2,一批程序IiCi Pi并发执行IiIi+1

4、CiCi+1 PiPi+1,12,2023/8/7,程序并发执行时的特征,间断性“执行暂停执行执行”的活动规律失去封闭性系统资源共享及资源状态改变的多样性，致使程序运行失去封闭性，程序运行必然会受到其它程序的影响不可再现性并发执行的程序，计算结果与其执行速度及时间有关,13,2023/8/7,程序并发执行不可再现性举例,共享初值为0的变量N的两程序段A、BA:N:=N+1B:Print(N);N:=0执行结果分析先A:1,1,0中A:0,1,0后A:0,0,1,14,2023/8/7,2.1 进程的基本概念,2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.

5、4 进程的特征和定义2.1.5 进程状态及状态转换图,15,2023/8/7,进程的引入,并发、共享及多道程序环境基于程序的概念已不能完整、有效地描述并发程序在内存中的运行状态必须建立并发程序的新的描述和控制机制基于程序段、数据段和进程控制块而引入进程的概念以对应程序的运行过程进程控制块存放了进程标识符、进程运行的当前状态、程序和数据的地址以及关于该程序运行时的CPU环境信息,16,2023/8/7,进程的定义,进程是可并发执行的程序在一个数据集合上的运行过程，亦即进程实体的运行过程进程实体由程序段、数据段及进程控制块三部分构成进程是系统进行资源分配和调度的一个独立单位,17,2023/8/7

6、,进程的特征与程序的区别与联系,结构特征程序段、数据段及进程控制块动态性生命周期及“执行”本质并发性共存于内存、宏观同时运行独立性调度、资源分配、运行异步性推进相互独立、速度不可预知,18,2023/8/7,2.1 进程的基本概念,2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图,19,2023/8/7,进程的基本状态及状态转换,20,2023/8/7,引入挂起状态的可能原因,终端用户的请求程序运行期间发现可疑问题暂停进程父进程的请求考察、修改或协调子进程操作系统的需要运行中资源使用情况的检查和记账负载调

7、节的需要负荷调节和保证实时系统正常运行,21,2023/8/7,具有挂起状态的进程状态图,22,2023/8/7,2.1 进程的基本概念,2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图,23,2023/8/7,作业题,2.1 比较程序的顺序执行和并发执行。2.2 比较程序和进程。2.3 试对进程的状态及状态转换进行总结，注意状态转换的物理含义及转化条件。,24,2023/8/7,第二章 进程管理,2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与

8、线程,25,2023/8/7,2.2 进程控制,2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制,26,2023/8/7,进程控制块,进程实体的一部分，拥有描述进程情况及控制进程运行所需的全部信息的记录性数据结构使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程操作系统控制和管理并发执行进程的依据进程存在的惟一标志常驻内存并存放于操作系统专门开辟的PCB区,？,27,2023/8/7,进程控制块中的信息,进程标识符内/外部、父/子进程、用户标识符处理器状

9、态信息通用、PC、PSW、用户栈指针寄存器进程调度信息进程状态、进程优先级、事件及其它进程控制信息程序和数据地址、进程同步通信机制资源清单、链接指针,28,2023/8/7,进程控制块的组织方式1链接方式,29,2023/8/7,进程控制块的组织方式2索引方式,执行指针,就绪表指针,阻塞表指针,就绪索引表,阻塞索引表,30,2023/8/7,2.2 进程控制,2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制,31,2023/8/7,进程图（进程树）,描述进程家族关系的有向树结点/有向边父/子进程祖父进程/

10、祖先,有什么用？,32,2023/8/7,2.2 进程控制,2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制,33,2023/8/7,引起创建/终止进程的事件,用户登录分时系统中，验证为合法的终端用户登录作业调度批处理系统中作业调度程序调度到某作业提供服务运行中的用户程序提出某种请求应用请求基于应用进程的需要由其自身创建新进程,正常结束批处理系统中Halt，分时系统中LogsOff异常结束越界错误、保护错特权指令错非法指令错运行超时、等待超时算术运算错、I/O故障外界干预操作员或操作系统干预父进程请求/终

11、止,34,2023/8/7,进程创建/终止过程,Create()原语1、分配标识符，并申请空白进程控制块2、为新进程的程序和数据及用户栈分配必要的内存空间所需内存大小问题3、初始化进程控制块自身/父进程标识符处理机状态/调度信息4、将新进程插入到就绪进程队列,Terminate()原语1、检索被终止进程PCB，读取进程状态2、若其正处于执行状态，应立即中止执行并设置调度标志为真，以指示调度新进程3、终止子孙进程4、资源归还5、移出被终止进程PCB，等待其它程序利用,35,2023/8/7,2.2 进程控制,2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2

12、.2.5 进程的挂起与激活 UNIX进程描述与控制,36,2023/8/7,引起进程阻塞/唤醒的事件,请求系统服务但不能立即满足启动某种操作且必须在该操作完成之后才能继续执行新数据尚未到达相互合作进程的一方需首先获得另一进程数据才能继续无新工作可做特定功能系统进程当完成任务且暂无任务,系统服务满足操作完成数据到达新任务出现,37,2023/8/7,进程阻塞/唤醒过程,Block()原语1、先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将它插入到对应的阻塞队列中2、转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换,Wakeup()原语首先把被阻塞进程从等待该事件的阻

13、塞进程队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该进程插入到就绪队列中,？,原语配对！,38,2023/8/7,2.2 进程控制,2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制,39,2023/8/7,进程挂起/激活过程,Suspend()原语1、检查被挂进程现行状态并修改和插队2、复制PCB到指定区域3、若被挂进程正在执行则转向调度程序重新调度,Activate()原语1、检查进程现行状态并修改和插队2、若有新进程进入就绪队列且采用了抢占式调度策略，则检查和决定是否重新调度,？,？,4

14、0,2023/8/7,2.2 进程控制,2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制,41,2023/8/7,UNIX进程控制用数据结构,进程表,本进程区表,内存,CODE,DATA,STACK,系统区表,进程U区,42,2023/8/7,UNIX进程状态转换图,43,2023/8/7,进程映像,进程是进程映像的执行过程，进程映像则是正在运行进程的实体用户级上下文用户程序（正文区、数据区）、用户栈区、共享存储区寄存器上下文PC、PSW、栈指针、通用寄存器系统级上下文进程表项、U区、本进程区表、系统区表

15、项、页表核心栈、若干层寄存器上下文,44,2023/8/7,进程控制,fork系统调用创建新进程0号（对换）进程=1号（始祖）进程exit系统调用实现进程自我终止exec系统调用改变进程原有代码（更新用户级上下文）wait系统调用阻塞主调进程并等待子进程终止,45,2023/8/7,进程调度与切换,引起进程调度的原因时钟中断、核心态执行返回、放弃处理机调用算法动态优先数轮转调度算法进程优先级分类内核优先级（可/不可中断）、用户优先级优先数计算基本用户优先数、进程本次CPU使用时间进程切换,46,2023/8/7,2.2 进程控制,2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2

16、.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制,47,2023/8/7,作业题,2.4 试根据你自己的理解，采用类C语言设计和描述操作系统关于进程控制块的数据结构、组织方式及管理机制。在此基础上，给出进程的创建、终止、阻塞、唤醒、挂起与激活等函数原型及函数代码。注意，对于过于复杂的功能或你无法解决的细节可采用指定功能的函数模块来替代。如处理机调度scheduler(),48,2023/8/7,第二章 进程管理,2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与线程,49,2023/8/7,2.3 进程同步,2

17、.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础,50,2023/8/7,并发进程间制约关系,资源共享关系间接制约多个进程彼此无关，完全不知道或只能间接感知其它进程的存在系统须保证诸进程能互斥地访问临界资源系统资源应统一分配，而不允许用户进程直接使用相互合作关系直接制约系统应保证相互合作的诸进程在执行次序上的协调和防止与时间有关的差错,51,2023/8/7,2.3 进程同步,2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础,52,202

18、3/8/7,临界资源,一段时间内只允许一个进程访问的资源许多物理设备、变量及表格举例两个进程A、B共享变量N(初值为5)A:N:=N+1;B:N:=N-1计算操作的系统实现过程剖析 A:R1:=N B:R2:=N R1:=R1+1 R2:=R2-1 N:=R1 N:=R2,53,2023/8/7,临界区,每个进程中访问临界资源的那段代码称为临界区保证诸进程互斥地进入自己的临界区是实现它们对临界资源的互斥访问的充要条件,54,2023/8/7,访问临界资源的循环进程描述,进程Pibeginrepeat 进入区 临界区 退出区 until false;end,主程序描述框架begin parbeg

19、in Pi;Pj;parendend,55,2023/8/7,2.3 进程同步,2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础,56,2023/8/7,进程同步机制基本准则,空闲让进当无进程处于临界区时，可允许一个请求进入临界区的进程立即进入自己的临界区忙则等待当已有进程进入自己的临界区时，所有企图进入临界区的进程必须等待有限等待对要求访问临界资源的进程，应保证该进程能在有限时间内进入自己的临界区让权等待当进程不能进入自己的临界区时，应释放处理机,57,2023/8/7,2.3 进程同步,2.3.1 并发进程间制

20、约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础,58,2023/8/7,整型信号量,整型信号量s除初始化外，仅能被两个标准的原子操作wait(s)和signal(s)亦即P/V操作来访问。wait(s):while s0 do no_op;s:=s-1;signal(s):s:=s+1;,有何弊端？,59,2023/8/7,记录型信号量机制 信号量类型声明,type semphore=record value:integer;L:list of process;end,物理意义？,60,2023/8/7,记录型信号量机制 wait(s)

21、操作描述,procedure wait(s)Var s:semphore;begin s.value:=s.value-1;if s.value0 then block(s.L);end,61,2023/8/7,记录型信号量机制 signal(s)操作描述,procedure signal(s)Var s:semphore;begin s.value:=s.value+1;if s.value0 then wakeup(s.L);end,62,2023/8/7,AND型信号量集机制的引入,对于多个进程要共享两个以上的资源的情况，上述机制则可能导致发生死锁例两个进程A、B要求同时访问共享数据C、

22、D process A:process B:wait(Dmutex);wait(Cmutex);wait(Cmutex);wait(Dmutex);对策：若干个临界资源的分配采取原子操作方式,63,2023/8/7,Swait(s1,s2,sn)操作,procedure Swait(s1,s2,sn)Var s1,s2,sn:semphore;begin if s1 1 and and sn 1 then for i:=1 to n do si:=si-1;else blockProcessAndResetPC(sfirstless);end,？,for i:=1 to n do if(sin

23、)for i:=1 to n do si:=si 1;,64,2023/8/7,Ssignal(s1,s2,sn)操作,procedure Ssignal(s1,s2,sn)Var s1,s2,sn:semphore;begin for i:=1 to n do si:=si+1;wakeupAllProcesses(si);endfor;end,？,65,2023/8/7,一般信号量集机制的引入,记录型信号量集机制中，wait(s)和signal(s)操作仅能对信号量施以增1和减1的操作，即每次只能获得或释放一个单位的临界资源。当一次需d个某类临界资源时，便需要进行d次wait(s)操作，这

24、显然是低效的。此外，在有些情况下，要求当资源数量低于某一下限值时，便不予分配。故在每次分配之前，都必须测试该资源的数量是否不小于测试值t。基于以上两点可以对AND信号量机制进行扩充，形成一般化的“信号量集”机制。,66,2023/8/7,Swait(s1,t1,d1,sn,tn,dn)操作,procedure Swait(s1,t1,d1,sn,tn,dn)Var s1,s2,sn:semphore;t1,t2,tn,d1,d2,dn:integer;begin if s1 t1 and and sn tn then for i:=1 to n do si:=si-di;else blockP

25、rocessAndResetPC(sfirstless);end,for i:=1 to n do if(sin)for i:=1 to n do si:=sidi;,67,2023/8/7,Ssignal(s1,d1,sn,dn)操作,procedure Ssignal(s1,d1,sn,dn)Var s1,s2,sn:semphore;d1,d2,dn:integer;begin for i:=1 to n do si:=si+di;wakeupAllProcesses(si);endfor;end,68,2023/8/7,一般信号量集的几种特殊情况,Swait(s,d,d)信号量集中只有

26、一个信号量，但它允许每次申请d个资源；当现有资源少于d个时，便不予分配Swait(s,1,1)此时的信号量集已退化为一般的记录型信号量Swait(s,1,0)一种特殊且很有用的信号量，相当于可控开关当s1时，允许多个进程进入某特定区；当s变为0后，将阻止任何进程进入该特定区,69,2023/8/7,2.3 进程同步,2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础,70,2023/8/7,利用信号量实现互斥主程序,Var mutex:semphore:=1;begin parbegin process1;proce

27、ss2;parendend,71,2023/8/7,利用信号量实现互斥子程序,process1:begin repeat wait(mutex);临界区 signal(mutex);until false;end,process2:begin repeat wait(mutex);临界区 signal(mutex);until false;end,72,2023/8/7,信号量要描述的前趋关系示例,S1,S2,S3,S4,S5,S6,a,b,c,d,e,f,g,73,2023/8/7,利用信号量来描述前趋关系,Var a,b,c,d,e,f,g:semphore:=0,0,0,0,0,0,0;

28、begin parbegin begin S1;signal(a);signal(b);end;begin wait(a);S2;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g);S6;end;parendend,74,2023/8/7,2.3 进程同步,2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2

29、.3.5 信号量机制应用基础,75,2023/8/7,作业题,2.5 什么是临界资源和临界区？试举例说明。并谈谈你对进程同步机制准则的理解。2.6 试阐述你对整型信号量机制与记录型信号量机制的完整理解以及AND型信号量机制与一般信号量集机制的基本思想。,76,2023/8/7,第二章 进程管理,2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与线程,77,2023/8/7,2.4 经典进程同步问题,2.4.1 生产者消费者问题2.4.2 哲学家进餐问题 读者写者问题,78,2023/8/7,生产者消费者问题背景,生产者消费者问题是相互合

30、作进程关系的一种抽象输入时的输入进程与计算进程输出时的计算进程与输出进程生产者消费者问题具有很大的代表性和实用价值计算机系统IPO系统,79,2023/8/7,生产者消费者问题描述,生产者进程在生产数据，并将此数据提供给消费者进程消费为使二者可以并发执行，在它们之间设置了一个具有n个缓冲区的循环缓冲，生产者进程可以将它所生产的数据放入一个缓冲区中，消费者进程可以从一个缓冲区中取得一个数据消费异步运行方式及彼此必须保持同步,80,2023/8/7,空缓冲区与满缓冲区空缓冲区是指未投放数据或虽曾投放数据但对应数据已被取走的缓冲区满缓冲区则指已投放数据且对应数据尚未被取走的缓冲区进程同步当生产者进程

31、要把所生产的数据送入循环缓冲时，首先应检查是否有空缓冲区存在，若有，则可向对应空缓冲区中投放数据，同时通知消费者进程；否则只有等待。当消费者进程要从循环缓冲中提取数据时，首先应检查是否有满缓冲区存在，若有，则从对应满缓冲区中提取数据，并通知生产者进程，否则只有等待。进程互斥循环缓冲是一个临界资源：单/多个生产者/消费者进程,生产者消费者问题剖析,81,2023/8/7,生产者消费者问题临界资源剖析,消费者1消费者2消费者3 消费者X,生产者1生产者2生产者3 生产者Y,82,2023/8/7,生产者消费者程序变量设计,循环缓冲表示机制一维数组buffer:array 0.n-1 of item

32、;输入指针in指示下一个可以投放数据的缓冲区初始值为0；变化方式：in(in+1)mod n输出指针out指示下一个可以获取数据的缓冲区初始值为0；变化方式：out(out+1)mod nnextp/nextc暂存每次要生产或消费的数据,83,2023/8/7,生产者消费者程序信号量设计,循环缓冲的互斥使用互斥信号量mutex，初始值为1资源信号量empty 表示循环缓冲中的空缓冲区的数量，其初始值为nfull 表示循环缓冲中的满缓冲区的数量，其初始值为0,84,2023/8/7,生产者消费者主程序设计,Var buffer:array 0.n-1 of item;in,out:integer

33、 0,0;mutex,empty,full:semphore 1,n,0;begin parbegin producer1;produceri;producerY;consumer1;consumerj;consumerX;parendend,85,2023/8/7,生产者子程序设计,produceri:Var nextp:item;begin repeat produce an item in nextp;wait(empty);wait(mutex);bufferin nextp;in(in+1)mod n;signal(mutex);signal(full);until false;en

34、d,86,2023/8/7,消费者子程序设计,consumerj:Var nextc:item;begin repeat wait(full);wait(mutex);nextcbufferout;out(out+1)mod n;signal(mutex);signal(empty);consume the item in nextc;until false;end,87,2023/8/7,同步问题程序设计要领,每个并发子程序关于互斥信号量的wait与signal操作必须在同一子程序中成对出现关于资源信号量的wait与signal操作同样需成对出现，但可以分别处于不同的并发子程序中每个并发子程

35、序中的多个wait操作的顺序不能颠倒，即资源信号量wait操作执行在前而互斥信号量wait操作执行在后，否则可能引起死锁每个并发子程序中的多个signal 操作的执行顺序无关紧要非临界资源访问操作无需放到临界区中,88,2023/8/7,基于AND信号量的生产/消费者子程序设计,produceri:begin repeat produce an item in nextp;Swait(empty,mutex);bufferin nextp;in(in+1)mod n;Ssignal(mutex,full);until false;end,consumerj:begin repeat Swait

36、(full,mutex);nextcbufferout;out(out+1)mod n;Ssignal(mutex,empty);consume the item in nextc;until false;end,89,2023/8/7,2.4 经典进程同步问题,2.4.1 生产者消费者问题2.4.2 哲学家进餐问题2.4.3 读者写者问题,90,2023/8/7,哲学家进餐问题描述,哲学家进餐问题是典型的同步问题五个哲学家共用一张圆桌，分别坐在环桌均匀摆放的五张椅子上，并全部执行同为交替地进行思考和进餐的生活方式圆桌上放有五支筷子，均匀排放在哲学家之间的位置上哲学家饥饿时便试图去取用圆桌上最

37、靠近他左右两端的两支筷子，且只有在同时拿到两支筷子时方可进餐，进餐完毕则把筷子放回原处，并继续进行思考,91,2023/8/7,哲学家进餐问题剖析(待续),筷子是临界资源信号量数组chopstick0.4，初始值均为1第i个哲学家活动wait(chopsticki);wait(chopstick(i+1)mod 5);Eat;signal(chopsticki);signal(chopstick(i+1)mod 5);Think;,92,2023/8/7,哲学家进餐问题剖析(续),上述解决方案在五个哲学家同时饥饿且各自拿起左边筷子的情况下会引起死锁避免死锁的三种方法 至多允许四个哲学家同时进餐

38、，以保证至少有一个哲学家可以同时拿到两支筷子而进餐 仅当哲学家左右两支筷子均可使用时，才允许他拿筷进餐 奇数号哲学家先拿左筷后拿右筷；而偶数号哲学家则相反,93,2023/8/7,哲学家进餐主程序设计,Var chopstick:array0.4 of semphore(1,1,1,1,1);begin parbegin philosophy0;philosophyi;philosophy4;parendend,94,2023/8/7,基于AND信号量机制的 哲学家进餐子程序设计,philosophyi:begin repeat Think;Swait(chopstick(i+1)mod 5,

39、chopsticki);Eat;Ssignal(chopstick(i+1)mod 5,chopsticki);until false;end,95,2023/8/7,2.4 经典进程同步问题,2.4.1 生产者消费者问题2.4.2 哲学家进餐问题2.4.3 读者写者问题,96,2023/8/7,读者写者问题描述,读者写者问题是指保证一个写者进程必须与其它进程互斥地访问共享数据对象（数据文件或记录）的同步问题。存在多个进程共享一个数据对象只要求读的进程称为读者进程拥有写或修改要求的进程称为写者进程允许多个读者进程同时执行读操作任何写者进程的执行具有排它性读者写者问题常用于测试新同步原语,97,

40、2023/8/7,读者写者程序信号量及变量设计,写者进程与其它进程的互斥执行写互斥信号量wmutex，初始值为1读者进程之间的并发执行读者进程计数变量readercount，表示正在执行的读者进程数量，其初始值为0读者进程计数变量的互斥访问readercount对于多个读者进程而言是临界资源，应为之设置读互斥信号量rmutex，其初始值为1,98,2023/8/7,读者写者主程序设计,Var readercount:integer 0;rmutex,wmutex:semphore 1,1;begin parbegin reader1;readeri;readerm;writer1;writer

41、j;writern;parendend,99,2023/8/7,读者子程序设计,readeri:begin repeat wait(rmutex);if readercount=0 then wait(wmutex);readercount readercount+1;signal(rmutex);Perform read operation;wait(rmutex);readercount readercount-1;if readercount=0 then signal(wmutex);signal(rmutex);until false;end,100,2023/8/7,写者子程序设计

42、,writerj:begin repeat wait(wmutex);Perform write operation;signal(wmutex);until false;end,101,2023/8/7,读者写者问题解决方案反思,如果读者到来无读者读、无写者写，则新读者可读无读者读、有写者写，则新读者等待有读者读（无论写者等），则新读者可读如果写者到来无读者读且无写者写，则新写者可写有读者读或有写者写，则新写者等待,读者优先的原则,102,2023/8/7,写者优先的读者写者问题,一旦有写者到达，则后续的读者必须等待（无论当时是否有读者在读）-如果读者到来无写者写且无写者等，则新读者可读有写

43、者写或有写者等，则新读者等待如果写者到来无读者读且无写者写，则新写者可写有读者读或有写者写，则新写者等待,课后作业,103,2023/8/7,读者数限定的读者写者问题,保持读者写者基本要求最多允许RN个读者同时读引入信号量rMax，并赋以初值RN；同时借助于Swait(rMax,1,1)来控制读者数量读者与写者之间的互斥引入互斥信号量wmutex读者执行Swait(wmutex,1,0)保证无写者写者检查Swait(wmutex,1,1,rMax,RN,0)保证既无写者在写又无读者在读,104,2023/8/7,读者数限定的读者写者主程序设计,Var RN:integer:=10;rMax,w

44、mutex:semphore RN,1;begin parbegin reader1;readeri;readerm;writer1;writerj;writern;parendend,105,2023/8/7,读者数限定的读者子程序设计,readeri:begin repeat Swait(rMax,1,1);Swait(wmutex,1,0);Perform read operation;Ssignal(rMax,1);until false;end,106,2023/8/7,读者数限定的写者子程序设计,writerj:begin repeat Swait(wmutex,1,1,rMax,

45、RN,0);Perform write operation;Ssignal(wmutex,1);until false;end,107,2023/8/7,2.4 经典进程同步问题,2.4.1 生产者消费者问题2.4.2 哲学家进餐问题 读者写者问题,108,2023/8/7,作业题,课本作业23、24、25、26、27、282.13 给出基于记录型信号量机制的写者优先的读者-写者问题的同步解决方案。,109,2023/8/7,操作系统实践实验3,利用Windows下的VC+或者Linux下的C或C+编程模拟解决各种进程同步问题：生产者-消费者问题；读者优先的读者-写者问题；写者优先的读者-写者

46、问题；读者数限定的读者-写者问题；哲学家就餐问题撰写实验报告，阐述实验目的、实验目标、实验步骤、技术难点及解决方案、关键数据结构和算法流程、测试方案与过程及运行效果、结论与体会等。,110,2023/8/7,第二章 进程管理,2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与线程,111,2023/8/7,2.5 进程通信,2.5.1 进程通信概念及分类2.5.2 消息传递通信实现方式2.5.3 消息传递系统实现若干问题2.5.4 消息缓冲队列通信机制,112,2023/8/7,进程通信概念与实现机制,进程通信概念 指进程之间的信息交换

47、实现机制低级进程通信：效率低，操作系统仅提供共享存储器，通信对用户不透明和不方便高级进程通信：能传送大量数据，效率高，进程通信实现细节由操作系统提供，整个通信过程对用户透明，通信程序编制简单,113,2023/8/7,进程通信的类型,共享存储器系统基于共享数据结构的通信方式基于共享存储区的通信方式消息传递系统直接/间接通信方式管道通信管道概念协调机制：互斥、同步、通信前提,114,2023/8/7,2.5 进程通信,2.5.1 进程通信概念及分类2.5.2 消息传递通信实现方式2.5.3 消息传递系统实现若干问题2.5.4 消息缓冲队列通信机制,115,2023/8/7,直接通信方式,通信原语

48、 Send(Receiver,message)Receive(Sender,message)一个接收进程可与多个发送进程通信打印进程Sender无法事先指定基于进程直接通信原语的应用生产者-消费者通信过程,116,2023/8/7,基于通信原语的生产者子程序设计,producer:Var nextp:item;begin repeat produce an item in nextp;wait(empty);wait(mutex);bufferin nextp;in(in+1)mod n;signal(mutex);signal(full);until false;end,Send(consu

49、mer,nextp);,117,2023/8/7,基于通信原语的消费者子程序设计,consumer:Var nextc:item;begin repeat wait(full);wait(mutex);nextcbufferout;out(out+1)mod n;signal(mutex);signal(empty);consume the item in nextc;until false;end,Receive(producer,nextc);,118,2023/8/7,间接通信方式,信箱进程间通信有关共享数据结构的中间实体由操作系统或用户进程创建私有/公有/共享信箱可实现实时/非实时通信

50、通信原语信箱的创建和撤销、消息的发送和接收发送/接收进程间存在的四种关系一对一、多对一、一对多、多对多,119,2023/8/7,2.5 进程通信,2.5.1 进程通信概念及分类2.5.2 消息传递通信实现方式2.5.3 消息传递系统实现若干问题2.5.4 消息缓冲队列通信机制,120,2023/8/7,消息传递系统中的几个问题,通信链路 显式/隐式建立（计算机网络/单机）点-点或多点连接通信链路单向/双向通信链路无容量/有容量通信链路（缓冲区）消息格式有消息头和消息正文构成，分定/变长两种进程同步方式发送/接收进程阻塞与否（三种情况）,121,2023/8/7,2.5 进程通信,2.5.1