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

第二章第二章 进程管理进程管理2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与线程1/9/202312.1 进程的基本概念2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图1/9/20232前趋图举例q=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P5,P7),(P6,P7)qPiPj称Pi是Pj的直接前趋，Pj是Pi的直接后继P1P2P3P4P5P6P71/9/20233前趋图中必须不存在循环q图例中存在前趋关系S2S3和S3 S2，显然，这种前趋关系是无法满足的。S1S2S31/9/202342.1 进程的基本概念2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图1/9/20235程序顺序执行q程序执行过程中通常存在顺序执行问题构成程序的若干个程序段之间组成程序段的多条语句之间IiCiPiS1:a:=x+y;S2:b:=a-5;S3:c:=b+1;1/9/20236程序顺序执行时的特征q顺序性处理机的操作，严格按照规定顺序执行q封闭性封闭环境下运行，程序独占全机资源只有当前运行程序才能改变资源状态程序执行结果不受外界因素的影响q可再现性只要程序执行时的环境和初始条件相同，程序重复执行结果相同1/9/20237程序顺序执行时的特性，将为程序员检测和校正程序的错误，带来极大的方便1/9/202382.1 进程的基本概念2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图1/9/20239程序并发执行例1q程序段语句间并发执行S1:a:=x+2 S2:b:=y+4S3:c:=a+b S4:d:=c+6S1S3S4S21/9/202310程序并发执行例2q一批程序IiCi Pi并发执行IiIi+1 CiCi+1 PiPi+1I1I2I3I4C1C2C3C4P1P2P3P41/9/202311程序并发执行时的特征q间断性“执行暂停执行执行”的活动规律q失去封闭性系统资源共享及资源状态改变的多样性，致使程序运行失去封闭性，程序运行必然会受到其它程序的影响q不可再现性并发执行的程序，计算结果与其执行速度及时间有关1/9/202312程序并发执行不可再现性举例q共享初值为0的变量N的两程序段A、BA:N:=N+1B:Print(N);N:=0q执行结果分析先A:1,1,0中A:0,1,0后A:0,0,11/9/2023132.1 进程的基本概念2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图1/9/202314进程的引入q并发、共享及多道程序环境q基于程序的概念已不能完整、有效地描述并发程序在内存中的运行状态q必须建立并发程序的新的描述和控制机制q基于程序段、数据段和进程控制块而引入进程的概念以对应程序的运行过程q进程控制块存放了进程标识符、进程运行的当前状态、程序和数据的地址以及关于该程序运行时的CPU环境信息1/9/202315进程的定义q进程是可并发执行的程序在一个数据集合上的运行过程，亦即进程实体的运行过程进程实体由程序段、数据段及进程控制块三部分构成q进程是系统进行资源分配和调度的一个独立单位1/9/202316进程的特征与程序的区别与联系q结构特征程序段、数据段及进程控制块q动态性生命周期及“执行”本质q并发性共存于内存、宏观同时运行q独立性调度、资源分配、运行q异步性推进相互独立、速度不可预知1/9/2023172.1 进程的基本概念2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图1/9/202318进程的基本状态及状态转换1/9/202319引入挂起状态的可能原因q终端用户的请求程序运行期间发现可疑问题暂停进程q父进程的请求考察、修改或协调子进程q操作系统的需要运行中资源使用情况的检查和记账q负载调节的需要负荷调节和保证实时系统正常运行1/9/202320具有挂起状态的进程状态图1/9/2023212.1 进程的基本概念2.1.1 前趋图2.1.2 程序顺序执行及特征2.1.3 程序并发执行及特征2.1.4 进程的特征和定义2.1.5 进程状态及状态转换图1/9/202322作业题作业题q2.1 比较程序的顺序执行和并发执行。q2.2 比较程序和进程。q2.3 试对进程的状态及状态转换进行总结，注意状态转换的物理含义及转化条件。1/9/202323第二章第二章 进程管理进程管理2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与线程1/9/2023242.2 进程控制2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制1/9/202325进程控制块q进程实体的一部分，拥有描述进程情况及控制进程运行所需的全部信息的记录性数据结构q使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程q操作系统控制和管理并发执行进程的依据q进程存在的惟一标志q常驻内存并存放于操作系统专门开辟的PCB区？1/9/202326进程控制块中的信息q进程标识符进程标识符内/外部、父/子进程、用户标识符q处理器状态信息处理器状态信息通用、PC、PSW、用户栈指针寄存器q进程调度信息进程调度信息进程状态、进程优先级、事件及其它q进程控制信息进程控制信息程序和数据地址、进程同步通信机制资源清单、链接指针1/9/202327进程控制块的组织方式1链接方式PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8.空闲队列指针空闲队列指针执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针6751081/9/202328进程控制块的组织方式2索引方式PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8.执行指针执行指针就绪表指针就绪表指针阻塞表指针阻塞表指针就绪索引表就绪索引表阻塞索引表阻塞索引表1/9/2023292.2 进程控制2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制1/9/202330进程图（进程树）q描述进程家族关系的有向树描述进程家族关系的有向树结点/有向边父/子进程祖父进程/祖先ABCDEHLMIJFGK有什么用有什么用？1/9/2023312.2 进程控制2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制1/9/202332引起创建/终止进程的事件q用户登录用户登录分时系统中，验证为合法的终端用户登录q作业调度作业调度批处理系统中作业调度程序调度到某作业q提供服务提供服务运行中的用户程序提出某种请求q应用请求应用请求基于应用进程的需要由其自身创建新进程q正常结束正常结束批处理系统中Halt，分时系统中LogsOffq异常结束异常结束越界错误、保护错特权指令错非法指令错运行超时、等待超时算术运算错、I/O故障q外界干预外界干预操作员或操作系统干预父进程请求/终止1/9/202333进程创建/终止过程Create()Create()原语原语1 1、分配标识符，并申、分配标识符，并申请空白进程控制块请空白进程控制块2 2、为新进程的程序和、为新进程的程序和数据及用户栈分配必数据及用户栈分配必要的内存空间要的内存空间所需内存大小问题3 3、初始化进程控制块、初始化进程控制块自身/父进程标识符处理机状态/调度信息4 4、将新进程插入到就、将新进程插入到就绪进程队列绪进程队列Terminate()Terminate()原语原语1 1、检索被终止进程、检索被终止进程PCBPCB，读取进程状态读取进程状态2 2、若其正处于执行状态，、若其正处于执行状态，应立即中止执行并设置应立即中止执行并设置调度标志为真，以指示调度标志为真，以指示调度新进程调度新进程3 3、终止子孙进程、终止子孙进程4 4、资源归还、资源归还5 5、移出被终止进程、移出被终止进程PCBPCB，等待其它程序利用等待其它程序利用1/9/2023342.2 进程控制2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制1/9/202335引起进程阻塞/唤醒的事件q请求系统服务请求系统服务但不能立即满足q启动某种操作启动某种操作且必须在该操作完成之后才能继续执行q新数据尚未到达新数据尚未到达相互合作进程的一方需首先获得另一进程数据才能继续q无新工作可做无新工作可做特定功能系统进程当完成任务且暂无任务q系统服务满足系统服务满足q操作完成操作完成q数据到达数据到达q新任务出现新任务出现1/9/202336进程阻塞/唤醒过程Block()Block()原语原语1 1、先立即停止执行，、先立即停止执行，把进程控制块中的现把进程控制块中的现行状态由行状态由“执行执行”改改为阻塞，并将它插入为阻塞，并将它插入到对应的阻塞队列中到对应的阻塞队列中2 2、转调度程序进行重、转调度程序进行重新调度，将处理机分新调度，将处理机分配给另一就绪进程，配给另一就绪进程，并进行并进行切换切换Wakeup()Wakeup()原语原语首先把被阻塞进程从等首先把被阻塞进程从等待该事件的阻塞进程待该事件的阻塞进程队列中移出，将其队列中移出，将其PCBPCB中的现行状态由阻塞中的现行状态由阻塞改为就绪，然后再将改为就绪，然后再将该进程插入到就绪队该进程插入到就绪队列中列中？原语配对原语配对！1/9/2023372.2 进程控制2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制1/9/202338进程挂起/激活过程Suspend()Suspend()原语原语1 1、检查被挂进程现行、检查被挂进程现行状态并修改和插队状态并修改和插队2 2、复制、复制PCBPCB到指定区域到指定区域3 3、若被挂进程正在执、若被挂进程正在执行则转向调度程序重行则转向调度程序重新调度新调度Activate()Activate()原语原语1 1、检查进程现行状态并、检查进程现行状态并修改和插队修改和插队2 2、若有新进程进入就绪、若有新进程进入就绪队列且采用了抢占式队列且采用了抢占式调度策略，则检查和调度策略，则检查和决定是否重新调度决定是否重新调度？1/9/2023392.2 进程控制2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制1/9/202340UNIX进程控制用数据结构进程控制用数据结构进程表本进程区表内存CODEDATASTACK正文区数据区栈区系统区表CODEDATASTACK进程U区1/9/202341UNIX进程状态转换图fork用户态执行挂起就绪挂起阻塞内存中就绪内存中阻塞新状态核心态执行僵死状态被抢占状态exit内存足内存不足换出换入换出唤醒唤醒调度阻塞抢占系统调用中断中断返回中断返回调度1/9/202342进程映像v进程是进程映像的执行过程，进程映像则是正在运行进程的实体q用户级上下文用户程序（正文区、数据区）用户程序（正文区、数据区）、用户栈区、共享存储区、用户栈区、共享存储区q寄存器上下文PC、PSW、栈指针、通用寄存器q系统级上下文进程表项、U区、本进程区表、系统区表项、页表核心栈、若干层寄存器上下文1/9/202343进程控制qfork系统调用创建新进程0号（对换）进程=1号（始祖）进程qexit系统调用实现进程自我终止qexec系统调用改变进程原有代码（更新用户级上下文）qwait系统调用阻塞主调进程并等待子进程终止1/9/202344进程调度与切换q引起进程调度的原因时钟中断、核心态执行返回、放弃处理机q调用算法动态优先数轮转调度算法q进程优先级分类内核优先级（可/不可中断）、用户优先级q优先数计算基本用户优先数、进程本次CPU使用时间q进程切换1/9/2023452.2 进程控制2.2.1 进程控制块 进程图2.2.3 进程的创建与终止2.2.4 进程的阻塞与唤醒2.2.5 进程的挂起与激活 UNIX进程描述与控制1/9/202346作业题作业题q2.4 试根据你自己的理解，采用类C语言设计和描述操作系统关于进程控制块的数据结构、组织方式及管理机制。在此基础上，给出进程的创建、终止、阻塞、唤醒、挂起与激活等函数原型及函数代码。注意，对于过于复杂的功能或你无法解决的细节可采用指定功能的函数模块来替代。如处理机调度scheduler()1/9/202347第二章第二章 进程管理进程管理2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与线程1/9/2023482.3 进程同步2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础1/9/202349并发进程间制约关系q资源共享关系间接制约多个进程彼此无关，完全不知道或只能间接感知其它进程的存在系统须保证诸进程能互斥地访问临界资源系统资源应统一分配，而不允许用户进程直接使用q相互合作关系直接制约系统应保证相互合作的诸进程在执行次序上的协调和防止与时间有关的差错1/9/2023502.3 进程同步2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础1/9/202351临界资源q一段时间内只允许一个进程访问的资源许多物理设备、变量及表格q举例两个进程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:=R21/9/202352临界区q每个进程中访问临界资源的那段代码称为临界区q保证诸进程互斥地进入自己的临界区是实现它们对临界资源的互斥访问的充要条件 1/9/202353访问临界资源的循环进程描述进程进程进程进程P Pi ibeginrepeat 进入区进入区 临界区临界区 退出区退出区 until false;end主程序描述框架begin parbegin Pi;Pj;parendend1/9/2023542.3 进程同步2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础1/9/202355进程同步机制基本准则q空闲让进当无进程处于临界区时，可允许一个请求进入临界区的进程立即进入自己的临界区q忙则等待当已有进程进入自己的临界区时，所有企图进入临界区的进程必须等待q有限等待对要求访问临界资源的进程，应保证该进程能在有限时间内进入自己的临界区q让权等待当进程不能进入自己的临界区时，应释放处理机1/9/2023562.3 进程同步2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础1/9/202357整型信号量q整型信号量s除初始化外，仅能被两个标准的原子操作wait(s)和signal(s)亦即P/V操作来访问。qwait(s):while s 0 do no_op;s:=s-1;qsignal(s):s:=s+1;有何弊端有何弊端？1/9/202358记录型信号量机制 信号量类型声明type semphore=record value:integer;L:list of process;end物理意义物理意义？1/9/202359记录型信号量机制 wait(s)操作描述procedure wait(s)Var s:semphore;begin s.value:=s.value-1;if s.value0 then block(s.L);end1/9/202360记录型信号量机制 signal(s)操作描述procedure signal(s)Var s:semphore;begin s.value:=s.value+1;if s.value0 then wakeup(s.L);end1/9/202361AND型信号量集机制的引入q对于多个进程要共享两个以上的资源的情况，上述机制则可能导致发生死锁q例两个进程A、B要求同时访问共享数据C、D process A:process B:wait(Dmutex);wait(Cmutex);wait(Cmutex);wait(Dmutex);q对策：若干个临界资源的分配采取原子操作方式1/9/202362Swait(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)for i:=1 to n do si:=si 1;1/9/202363Ssignal(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？1/9/202364一般信号量集机制的引入q记录型信号量集机制中，wait(s)和signal(s)操作仅能对信号量施以增1和减1的操作，即每次只能获得或释放一个单位的临界资源。当一次需d个某类临界资源时，便需要进行d次wait(s)操作，这显然是低效的。q此外，在有些情况下，要求当资源数量低于某一下限值时，便不予分配。故在每次分配之前，都必须测试该资源的数量是否不小于测试值t。q基于以上两点可以对AND信号量机制进行扩充，形成一般化的“信号量集”机制。1/9/202365Swait(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 blockProcessAndResetPC(sfirstless);endfor i:=1 to n do if(sin)for i:=1 to n do si:=sidi;1/9/202366Ssignal(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;end1/9/202367一般信号量集的几种特殊情况qSwait(s,d,d)信号量集中只有一个信号量，但它允许每次申请d个资源；当现有资源少于d个时，便不予分配qSwait(s,1,1)此时的信号量集已退化为一般的记录型信号量qSwait(s,1,0)一种特殊且很有用的信号量，相当于可控开关当s1时，允许多个进程进入某特定区；当s变为0后，将阻止任何进程进入该特定区1/9/2023682.3 进程同步2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础1/9/202369利用信号量实现互斥主程序Var mutex:semphore:=1;begin parbegin process1;process2;parendend1/9/202370利用信号量实现互斥子程序process1:begin repeat wait(mutex);临界区临界区 signal(mutex);until false;endprocess2:begin repeat wait(mutex);临界区临界区 signal(mutex);until false;end1/9/202371信号量要描述的前趋关系示例S1S2S3S4S5S6abcdefg1/9/202372利用信号量来描述前趋关系Var a,b,c,d,e,f,g:semphore:=0,0,0,0,0,0,0;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;parendend1/9/2023732.3 进程同步2.3.1 并发进程间制约关系2.3.2 临界资源与临界区 进程同步机制准则2.3.4 信号量机制2.3.5 信号量机制应用基础1/9/202374作业题作业题q2.5 什么是临界资源和临界区？试举例说明。并谈谈你对进程同步机制准则的理解。q2.6 试阐述你对整型信号量机制与记录型信号量机制的完整理解以及AND型信号量机制与一般信号量集机制的基本思想。1/9/202375第二章第二章 进程管理进程管理2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与线程1/9/2023762.4 经典进程同步问题2.4.1 生产者消费者问题2.4.2 哲学家进餐问题 读者写者问题1/9/202377生产者消费者问题背景q生产者消费者问题是相互合作进程关系的一种抽象输入时的输入进程与计算进程输出时的计算进程与输出进程q生产者消费者问题具有很大的代表性和实用价值计算机系统IPO系统1/9/202378生产者消费者问题描述q生产者进程在生产数据，并将此数据提供给消费者进程消费q为使二者可以并发执行，在它们之间设置了一个具有n个缓冲区的循环缓冲，生产者进程可以将它所生产的数据放入一个缓冲区中，消费者进程可以从一个缓冲区中取得一个数据消费q异步运行方式及彼此必须保持同步彼此必须保持同步1/9/202379q空缓冲区与满缓冲区空缓冲区与满缓冲区空缓冲区是指未投放数据或虽曾投放数据但对应数据已被取走的缓冲区满缓冲区则指已投放数据且对应数据尚未被取走的缓冲区q进程同步进程同步当生产者进程要把所生产的数据送入循环缓冲时，首先应检查是否有空缓冲区存在，若有，则可向对应空缓冲区中投放数据，同时通知消费者进程；否则只有等待。当消费者进程要从循环缓冲中提取数据时，首先应检查是否有满缓冲区存在，若有，则从对应满缓冲区中提取数据，并通知生产者进程，否则只有等待。q进程互斥进程互斥循环缓冲是一个临界资源：单/多个生产者/消费者进程生产者消费者问题剖析生产者消费者问题剖析1/9/202380生产者消费者问题临界资源剖析0n-3n-2n-1123指针移动方向输出指针out输入指针in消费者1消费者2消费者3 消费者X生产者1生产者2生产者3 生产者Y1/9/202381生产者消费者程序变量设计q循环缓冲表示机制一维数组buffer:array 0.n-1 of item;q输入指针in指示下一个可以投放数据的缓冲区初始值为0；变化方式：in (in+1)mod nq输出指针out指示下一个可以获取数据的缓冲区初始值为0；变化方式：out(out+1)mod nqnextp/nextc暂存每次要生产或消费的数据1/9/202382生产者消费者程序信号量设计q循环缓冲的互斥使用互斥信号量mutex，初始值为1q资源信号量empty 表示循环缓冲中的空缓冲区的数量，其初始值为nfull 表示循环缓冲中的满缓冲区的数量，其初始值为01/9/202383生产者消费者主程序设计生产者消费者主程序设计Var buffer:array 0.n-1 of item;in,out:integer 0,0;mutex,empty,full:semphore 1,n,0;begin parbegin producer1;produceri;producerY;consumer1;consumerj;consumerX;parendend1/9/202384生产者子程序设计生产者子程序设计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;end1/9/202385消费者子程序设计消费者子程序设计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;end1/9/202386同步问题程序设计要领同步问题程序设计要领q每个并发子程序关于互斥信号量的wait与signal操作必须在同一子程序中成对出现q关于资源信号量的wait与signal操作同样需成对出现，但可以分别处于不同的并发子程序中q每个并发子程序中的多个wait操作的顺序不能颠倒，即资源信号量wait操作执行在前而互斥信号量wait操作执行在后，否则可能引起死锁q每个并发子程序中的多个signal 操作的执行顺序无关紧要q非临界资源访问操作无需放到临界区中1/9/202387基于基于AND信号量的生产信号量的生产/消费者子程序设计消费者子程序设计produceri:begin repeat produce an item in nextp;Swait(empty,mutex);bufferin nextp;in (in+1)mod n;Ssignal(mutex,full);until false;endconsumerj:begin repeat Swait(full,mutex);nextcbufferout;out (out+1)mod n;Ssignal(mutex,empty);consume the item in nextc;until false;end1/9/2023882.4 经典进程同步问题2.4.1 生产者消费者问题2.4.2 哲学家进餐问题2.4.3 读者写者问题1/9/202389哲学家进餐问题描述q哲学家进餐问题是典型的同步问题五个哲学家共用一张圆桌，分别坐在环桌均匀摆放的五张椅子上，并全部执行同为交替地进行思考和进餐的生活方式圆桌上放有五支筷子，均匀排放在哲学家之间的位置上哲学家饥饿时便试图去取用圆桌上最靠近他左右两端的两支筷子，且只有在同时拿到两支筷子时方可进餐，进餐完毕则把筷子放回原处，并继续进行思考1/9/202390哲学家进餐问题剖析(待续)q筷子是临界资源信号量数组chopstick0.4，初始值均为1q第i个哲学家活动wait(chopsticki);wait(chopstick(i+1)mod 5);Eat;signal(chopsticki);signal(chopstick(i+1)mod 5);Think;03214043211/9/202391哲学家进餐问题剖析(续)q上述解决方案在五个哲学家同时饥饿且各自拿起左边筷子的情况下会引起死锁q避免死锁的三种方法 至多允许四个哲学家同时进餐，以保证至少有一个哲学家可以同时拿到两支筷子而进餐 仅当哲学家左右两支筷子均可仅当哲学家左右两支筷子均可使用时，才允许他拿筷进餐使用时，才允许他拿筷进餐 奇数号哲学家先拿左筷后拿右筷；而偶数号哲学家则相反03214043211/9/202392哲学家进餐主程序设计哲学家进餐主程序设计Var chopstick:array0.4 of semphore(1,1,1,1,1);begin parbegin philosophy0;philosophyi;philosophy4;parendend1/9/202393基于基于AND信号量机制的信号量机制的 哲学家进餐子程序设计哲学家进餐子程序设计philosophyi:begin repeat Think;Swait(chopstick(i+1)mod 5,chopsticki);Eat;Ssignal(chopstick(i+1)mod 5,chopsticki);until false;end1/9/2023942.4 经典进程同步问题2.4.1 生产者消费者问题2.4.2 哲学家进餐问题2.4.3 读者写者问题1/9/202395读者写者问题描述q读者写者问题是指保证一个写者进程必须与其它进程互斥地访问共享数据对象（数据文件或记录）的同步问题。存在多个进程共享一个数据对象只要求读的进程称为读者进程拥有写或修改要求的进程称为写者进程允许多个读者进程同时执行读操作任何写者进程的执行具有排它性q读者写者问题常用于测试新同步原语1/9/202396读者写者程序信号量及变量设计q写者进程与其它进程的互斥执行写互斥信号量wmutex，初始值为1q读者进程之间的并发执行读者进程计数变量readercount，表示正在执行的读者进程数量，其初始值为0q读者进程计数变量的互斥访问readercount对于多个读者进程而言是临界资源，应为之设置读互斥信号量rmutex，其初始值为11/9/202397读者写者主程序设计读者写者主程序设计Var readercount:integer 0;rmutex,wmutex:semphore 1,1;begin parbegin reader1;readeri ;readerm;writer1;writerj ;writern;parendend1/9/202398读者子程序设计读者子程序设计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;end1/9/202399写者子程序设计写者子程序设计writerj:begin repeat wait(wmutex);Perform write operation;signal(wmutex);until false;end1/9/2023100读者写者问题解决方案反思q如果读者到来无读者读、无写者写，则新读者可读无读者读、有写者写，则新读者等待有读者读（无论写者等），则新读者可读q如果写者到来无读者读且无写者写，则新写者可写有读者读或有写者写，则新写者等待读者优先的原则读者优先的原则1/9/2023101写者优先的读者写者问题q一旦有写者到达，则后续的读者必须等待（无论当时是否有读者在读）-q如果读者到来无写者写且无写者等，则新读者可读有写者写或有写者等，则新读者等待q如果写者到来无读者读且无写者写，则新写者可写有读者读或有写者写，则新写者等待课后作业课后作业1/9/2023102读者数限定的读者写者问题q保持读者写者基本要求q最多允许RN个读者同时读引入信号量rMax，并赋以初值RN；同时借助于Swait(rMax,1,1)来控制读者数量q读者与写者之间的互斥引入互斥信号量wmutex读者执行Swait(wmutex,1,0)保证无写者写者检查Swait(wmutex,1,1,rMax,RN,0)保证既无写者在写又无读者在读1/9/2023103读者数限定的读者数限定的读者写者主程序设计读者写者主程序设计Var RN:integer:=10;rMax,wmutex:semphore RN,1;begin parbegin reader1;readeri ;readerm;writer1;writerj ;writern;parendend1/9/2023104读者数限定的读者数限定的读者子程序设计读者子程序设计readeri:begin repeat Swait(rMax,1,1);Swait(wmutex,1,0);Perform read operation;Ssignal(rMax,1);until false;end1/9/2023105读者数限定的读者数限定的写者子程序设计写者子程序设计writerj:begin repeat Swait(wmutex,1,1,rMax,RN,0);Perform write operation;Ssignal(wmutex,1);until false;end1/9/20231062.4 经典进程同步问题2.4.1 生产者消费者问题2.4.2 哲学家进餐问题 读者写者问题1/9/2023107作业题作业题 课本作业23、24、25、26、27、28q2.13 给出基于记录型信号量机制的写者优先的读者-写者问题的同步解决方案。1/9/2023108操作系统实践实验3q利用Windows下的VC+或者Linux下的C或C+编程模拟解决各种进程同步问题：I.生产者-消费者问题；读者优先的读者-写者问题；写者优先的读者-写者问题；读者数限定的读者-写者问题；哲学家就餐问题II.撰写实验报告，阐述实验目的、实验目标、实验步骤、技术难点及解决方案、关键数据结构和算法流程、测试方案与过程及运行效果、结论与体会等。1/9/2023109第二章第二章 进程管理进程管理2.1 进程的基本概念2.2 进程控制2.3 进程同步2.4 经典进程同步问题2.5 进程通信2.6 管程与线程1/9/20231102.5 进程通信2.5.1 进程通信概念及分类2.5.2 消息传递通信实现方式2.5.3 消息传递系统实现若干问题2.5.4 消息缓冲队列通信机制1/9/2023111进程通信概念与实现机制进程通信概念与实现机制q进程通信概念 指进程之间的信息交换q实现机制低级进程通信：效率低，操作系统仅提供共享存储器，通信对用户不透明和不方便高级进程通信：能传送大量数据，效率高，进程通信实现细节由操作系统提供，整个通信过程对用户透明，通信程序编制简单 1/9/2023112进程通信的类型进程通信的类型q共享存储器系统基于共享数据结构的通信方式基于共享存储区的通信方式q消息传递系统消息传递系统直接/间接通信方式q管道通信管道概念协调机制：互斥、同步、通信前提1/9/20231132.5 进程通信2.5.1 进程通信概念及分类2.5.2 消