操作系统第二章 课件.

1、第二章第二章 进程管理进程管理n进程的基本概念进程的基本概念n进程与程序的区别进程与程序的区别n进程控制进程控制n进程同步进程同步n进程通信进程通信n线程线程临沂师范学院信息学院2.1进程的基本概念进程的基本概念n程序在并发环境中的执行过程程序在并发环境中的执行过程n资源分配和独立运行的基本单位资源分配和独立运行的基本单位临沂师范学院信息学院程序的顺序执行程序的顺序执行n一个有四条语句的程序段：一个有四条语句的程序段：S1：a:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;临沂师范学院信息学院程序的顺序执行程序的顺序执行临沂师范学院信息学院S1S2S3S4程序顺序执行的

2、特征程序顺序执行的特征n顺序性顺序性n封闭性封闭性n可再现性可再现性临沂师范学院信息学院n顺序性：顺序性：处理机处理机的操作严格按照程序所规的操作严格按照程序所规定的顺序执行，即每一个操作必须在下一定的顺序执行，即每一个操作必须在下一操作之前结束。操作之前结束。n封闭性：程序在封闭环境下执行，结果不封闭性：程序在封闭环境下执行，结果不受外界因素影响。受外界因素影响。n可再现性：只要环境和初始条件相同，程可再现性：只要环境和初始条件相同，程序重复执行时总得到相同结果。序重复执行时总得到相同结果。临沂师范学院信息学院程序并发执行程序并发执行n一个有四条语句的程序段：一个有四条语句的程序段：S1：a

3、:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;临沂师范学院信息学院程序的并发执行程序的并发执行临沂师范学院信息学院S1S2S3S4程序并发执行的特征程序并发执行的特征n间断性间断性 共享、合作、制约导致：共享、合作、制约导致： 执行执行-暂停暂停-执行执行n失去封闭性失去封闭性 资源状态由多程序改变资源状态由多程序改变n不可再现性不可再现性 相同环境和初始条件，重复执相同环境和初始条件，重复执行结果不同行结果不同临沂师范学院信息学院程序程序A 程序程序BL1： L2： N：=N+1 PRINT (N)；goto L1 N：=0； goto L2设共享变量设共享变量N初

4、值为初值为5，则会产生，则会产生3种执行结果：种执行结果：6，6，05，0，15，6，0临沂师范学院信息学院进程的特征进程的特征n结构特征结构特征n动态性动态性n并发性并发性n独立性独立性n异步性异步性临沂师范学院信息学院进程的结构特征进程的结构特征n进程结构进程结构临沂师范学院信息学院PCB进程控制块程序段数据段动态特征的集中反映描述要完成的功能操作对象及工作区进程的动态性进程的动态性n进程最基本的特征是动态性进程最基本的特征是动态性n进程的生命周期：进程由创建而产生，由进程的生命周期：进程由创建而产生，由调度而执行，由撤消而消亡的过程。调度而执行，由撤消而消亡的过程。临沂师范学院信息学院n

5、并发性：多个进程同在内存中，且能在一并发性：多个进程同在内存中，且能在一段时间内同时运行。段时间内同时运行。n独立性：进程是一个能独立运行、独立分独立性：进程是一个能独立运行、独立分配资源、独立接受调度的基本单位。配资源、独立接受调度的基本单位。n异步性：进程按各自独立的、不可预知的异步性：进程按各自独立的、不可预知的速度向前推进。速度向前推进。临沂师范学院信息学院进程定义进程定义n进程是进程实体的运行过程，是系统进行进程是进程实体的运行过程，是系统进行资源分配和调度的基本单位。资源分配和调度的基本单位。临沂师范学院信息学院进程和程序的关系进程和程序的关系n进程是一个动态概念，程序是一个静态概

6、进程是一个动态概念，程序是一个静态概念念n进程具有并行特征，程序没有进程具有并行特征，程序没有n进程是竞争资源的基本单位进程是竞争资源的基本单位n一个程序对应多个进程，一个进程为多个一个程序对应多个进程，一个进程为多个程序服务程序服务临沂师范学院信息学院进程的三种基本状态进程的三种基本状态n就绪状态就绪状态n执行状态执行状态n阻塞状态阻塞状态临沂师范学院信息学院就绪态就绪态n进程已经分配了除处理机以外的所有必要进程已经分配了除处理机以外的所有必要资源，只要再获得处理机就能够执行的状资源，只要再获得处理机就能够执行的状态。态。n这样的进程可能有多个，通常排成一个队这样的进程可能有多个，通常排成一

7、个队列，称就绪队列。列，称就绪队列。临沂师范学院信息学院执行态执行态n已经获得已经获得CPU，正在运行。，正在运行。n在单处理机系统只有一个进程处于执行状在单处理机系统只有一个进程处于执行状态。多处理机系统则有多个进程处于执行态。多处理机系统则有多个进程处于执行状态。状态。临沂师范学院信息学院阻塞态阻塞态n正在执行的进程由于发生某事件而暂时无正在执行的进程由于发生某事件而暂时无法继续执行时，放弃处理机而进入的状态，法继续执行时，放弃处理机而进入的状态，又称等待状态。又称等待状态。n引起阻塞的事件：请求引起阻塞的事件：请求I/O，申请缓存。，申请缓存。临沂师范学院信息学院进程的基本状态转换进程的

8、基本状态转换临沂师范学院信息学院就绪堵塞执行进程调度进程调度进程调度I/O完成I/O请求时间片完挂起状态挂起状态n引入原因：引入原因：(1)终端用户请求终端用户请求(2)父进程请求父进程请求(3)负荷调节需要负荷调节需要(4)操作系统的需要操作系统的需要临沂师范学院信息学院挂起引起的状态转换挂起引起的状态转换静止状态静止状态 挂起状态挂起状态 非挂起状态非挂起状态临沂师范学院信息学院活动状态活动状态有挂起状态的进程状态图有挂起状态的进程状态图临沂师范学院信息学院执行执行活动就绪活动就绪静止堵塞静止堵塞活动堵塞活动堵塞静止就绪静止就绪挂起挂起激活激活调度调度挂起挂起I/OI/O请求请求激活激活挂

9、起挂起释放释放释放释放进程控制块进程控制块n进程结构进程结构临沂师范学院信息学院PCB进程控制块程序段数据段进程控制块进程控制块nPCB是是OS中最重要的记录型结构。中最重要的记录型结构。nOS用用PCB对并发进程进行管理和控制。对并发进程进行管理和控制。nPCB是进程存在的唯一标志。是进程存在的唯一标志。nPCB常驻内存。常驻内存。nOS专门开辟专门开辟PCB区将所有的区将所有的PCB组织成若组织成若干个链表或队列。干个链表或队列。临沂师范学院信息学院PCB的结构：结构体的结构：结构体nFor example:定义一个学生的自然信息：定义一个学生的自然信息：临沂师范学院信息学院姓名 性别班级

10、专业出生年 月 日结构体结构体(structure)定义一个结构：定义一个结构：struct Student char name20; char sex12; DATE birthday; char speciality20; char class10; ; typedef struct Student STUDENT;临沂师范学院信息学院PCB中的信息中的信息(1)进程标识符进程标识符(2)处理机状态处理机状态(3)进程调度信息进程调度信息(4)进程控制信息进程控制信息临沂师范学院信息学院PCB中的信息之一中的信息之一n进程标识符进程标识符(1)内部标识符内部标识符 进程唯一的数字编号，给进

11、程唯一的数字编号，给OS使用。使用。(2)外部标识符外部标识符 由字母、数字组成，给用户使用。由字母、数字组成，给用户使用。临沂师范学院信息学院PCB中的信息之二中的信息之二n处理机状态处理机状态处理机中主要的寄存器：处理机中主要的寄存器：(1)通用寄存器通用寄存器 8-32个，暂存信息用个，暂存信息用(2)指令计数器指令计数器 要访问的下一条指令地址要访问的下一条指令地址(3)程序状态字程序状态字PSW 条件码、执行方式、中断屏蔽条件码、执行方式、中断屏蔽标志标志(4)用户栈指针用户栈指针 用户进程拥有的系统栈，存放过程和用户进程拥有的系统栈，存放过程和系统调用参数及调用地址系统调用参数及调

12、用地址临沂师范学院信息学院PCB中的信息之三中的信息之三n进程调度信息进程调度信息（1）进程状态）进程状态（2）进程优先级）进程优先级（3）与调度算法有关信息）与调度算法有关信息（4）事件）事件 如：阻塞原因如：阻塞原因临沂师范学院信息学院PCB中的信息之四中的信息之四n进程控制信息进程控制信息（1）程序和数据地址）程序和数据地址（2）进程同步和通信机制）进程同步和通信机制（3）资源清单：除）资源清单：除CPU之外的所需资源与已之外的所需资源与已经分配资源清单经分配资源清单（4）链接指针：本进程）链接指针：本进程PCB所在队列的下一所在队列的下一个地址。个地址。临沂师范学院信息学院知道了知道了

13、PCB中的信息之后要思考中的信息之后要思考n为什么程序并发执行有不可再现性的缺点？而进为什么程序并发执行有不可再现性的缺点？而进程有可再现性？程有可再现性？程序并发执行时，多个程序共享系统中的各种资源，程序并发执行时，多个程序共享系统中的各种资源，因而这些因而这些资源的状态将由多个程序改变资源的状态将由多个程序改变，致使程序的，致使程序的运行已失去了封闭性，某个程序的运行必然受到其他运行已失去了封闭性，某个程序的运行必然受到其他程序的影响。由于失去了封闭性，也将导致不再现性。程序的影响。由于失去了封闭性，也将导致不再现性。进程在并发执行方式下，它的运行呈现进程在并发执行方式下，它的运行呈现“走

14、走停停走走停停”的规律，当它停下来时，要求有一个数据结构的规律，当它停下来时，要求有一个数据结构PCB来来记录进程的当前状态记录进程的当前状态（及时保护它的运行现场，以保（及时保护它的运行现场，以保证在其恢复运行时可以证在其恢复运行时可以正确的正确的接着向下执行）接着向下执行）临沂师范学院信息学院CPU Switch From Process to ProcessPCB的组织方式的组织方式（1）链接方式）链接方式把统一状态的把统一状态的PCB，用其中的链接字链接成，用其中的链接字链接成一个队列。如：就绪队列、阻塞队列（根一个队列。如：就绪队列、阻塞队列（根据不同阻塞原因）、空白队列。据不同阻塞

15、原因）、空白队列。（2）索引方式）索引方式建立就绪索引表、阻塞索引表等。把索引表建立就绪索引表、阻塞索引表等。把索引表在内存的首地址放在内存的专用单元中。在内存的首地址放在内存的专用单元中。临沂师范学院信息学院链接方式链接方式临沂师范学院信息学院空闲队列指针阻塞队列指针就绪队列指针执行指针PCB1 4PCB2 3PCB3 0PCB4 8PCB5PCB6 7PCB7 9PCB8 0PCB9 11索引方式索引方式临沂师范学院信息学院执行指针就绪表指针阻塞表指针PCB1PCB2PCB3PCB4PCB5PCB6PCB72.2进程控制进程控制n进程管理最基本功能是进程管理最基本功能是进程控制进程控制n进

16、程控制任务：进程控制任务：进程的创建、终止、进程状态的转变等进程的创建、终止、进程状态的转变等n进程控制一般由进程控制一般由OS内核内核来实现。来实现。临沂师范学院信息学院进程图进程图临沂师范学院信息学院ACBEFHGD进程的创建进程的创建n原语原语CREAT（）按下述步骤创建一个新进程：（）按下述步骤创建一个新进程：原语：是由若干条指令构成，完成一个特定功能的一原语：是由若干条指令构成，完成一个特定功能的一个过程。个过程。原语：原语是一种规模相当小的程序，被定义在原语：原语是一种规模相当小的程序，被定义在OS的的底层，它的运行过程不可分隔。底层，它的运行过程不可分隔。（1）申请空白）申请空白

17、PCB（2）为新进程分配资源）为新进程分配资源（3）初始化进程控制块）初始化进程控制块（4）将新进程插入就绪队列）将新进程插入就绪队列临沂师范学院信息学院临沂师范学院信息学院引起进程终止的事件引起进程终止的事件n正常结束正常结束n异常结束异常结束越界错误、保护错、非法指令越界错误、保护错、非法指令n外界干预外界干预操作员或操作员或OS干预、被父进程终止、父进程终干预、被父进程终止、父进程终止止临沂师范学院信息学院进程的终止过程进程的终止过程n从从PCB集合中检索出该进程的集合中检索出该进程的PCB，从中，从中读出该进程的状态。读出该进程的状态。n若处于执行状态，终止该进程的执行，并若处于执行状

18、态，终止该进程的执行，并置调度标志为真，重新调度。置调度标志为真，重新调度。n若有子孙进程，将所有子孙进程终止。若有子孙进程，将所有子孙进程终止。n将进程全部资源归还其父进程或系统。将进程全部资源归还其父进程或系统。n将其将其PCB从所在队列（或链表）中移出从所在队列（或链表）中移出临沂师范学院信息学院临沂师范学院信息学院进程阻塞过程进程阻塞过程n由阻塞原语由阻塞原语BLOCK完成完成临沂师范学院信息学院入口保存当前进程的CPU现场置该进程状态进入等待队列转进程调度临沂师范学院信息学院进程唤醒过程进程唤醒过程n由唤醒原语由唤醒原语WAKEUP来完成来完成临沂师范学院信息学院入口从等待队列中摘下

19、被唤醒进程置该进程为就绪态进入就绪队列转进程调度或返回临沂师范学院信息学院注意注意nBLOCK和和WAKEUP是一对作用相反的原是一对作用相反的原语。语。n如果在某进程中调用了如果在某进程中调用了阻塞原语阻塞原语，则必须，则必须在与之相合作的另一进程中或其他相关的在与之相合作的另一进程中或其他相关的进程中，安排进程中，安排唤醒原语唤醒原语，以能唤醒阻塞进，以能唤醒阻塞进程；否则，被阻塞进程将会因不能被唤醒程；否则，被阻塞进程将会因不能被唤醒而长久地处于阻塞状态，从而再无机会继而长久地处于阻塞状态，从而再无机会继续运行。续运行。临沂师范学院信息学院进程的挂起与激活进程的挂起与激活n挂起原语：挂起

20、原语：SUSPEND()n激活原话：激活原话：ACTIVE()临沂师范学院信息学院临沂师范学院信息学院2.3进程同步进程同步n进程的两种制约关系进程的两种制约关系间接制约：进程间由于共享某种系统资源，而间接制约：进程间由于共享某种系统资源，而形成的相互制约。形成的相互制约。直接制约：进程间由于合作而形成的相互制约直接制约：进程间由于合作而形成的相互制约关系。关系。临沂师范学院信息学院进程A进程B进程A进程B资源资源进程的两大关系进程的两大关系n互斥互斥n同步同步临沂师范学院信息学院互斥（间接作用）：互斥（间接作用）：mutual exclusionn由于各进程要求共享资源，而有些资源需由于各进

21、程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。资源，进程的这种关系为进程的互斥。临沂师范学院信息学院临界资源：临界资源：critical resourcen系统中某些资源一次只允许一个进程使用，系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源。称这样的资源为临界资源或互斥资源。临沂师范学院信息学院同步（直接作用）同步（直接作用）:synchronismn指系统中多个进程中发生的事件存在某种指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项时序关系，需要相互合作，共

22、同完成一项任务。任务。具体说，一个进程运行到某一点时具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态。得消息之前，该进程处于等待状态。临沂师范学院信息学院临沂师范学院信息学院与时间有关的错误与时间有关的错误n例例1：民航售票：民航售票票数：票数：XA进程进程: B进程：进程：if x0 thenif x0 thenx:=x-1 x:=x-1临沂师范学院信息学院与时间有关的错误与时间有关的错误n例例2：交通流量统计：交通流量统计车辆数：车辆数：SL1 中断处理程序：中断处理程序：s:=0;s:=s+1Delay(

23、600);Write(s);Goto L1临沂师范学院信息学院临界区（临界段）临界区（临界段）n在每个进程中访问临界资源的那段程序在每个进程中访问临界资源的那段程序总结总结：只要进程当中有访问临界资源的语句，：只要进程当中有访问临界资源的语句，那么这些语句就是临界区那么这些语句就是临界区n进程必须互斥进入临界区进程必须互斥进入临界区临沂师范学院信息学院访问临界区的循环进程描述访问临界区的循环进程描述repeatuntil false;临沂师范学院信息学院进入区临界区退出区剩余区检查临界资源是否能访问将临界区标志设为未访问同步机制遵循的原则同步机制遵循的原则n空闲让进空闲让进n忙则等待忙则等待n

24、有限等待有限等待n让权等待让权等待如何在如何在OS内实现这些同步原则？内实现这些同步原则？临沂师范学院信息学院信号量机制信号量机制n信号量（信号量（Semaphore：旗语）：旗语）n是一种数据结构是一种数据结构n信号量的值与相应资源的使用情况有关信号量的值与相应资源的使用情况有关n信号量的值仅由信号量的值仅由P、V操作改变操作改变是荷兰文字中是荷兰文字中“使用资源使用资源” 和和“归还资源归还资源”的的首字母首字母临沂师范学院信息学院整型信号量整型信号量n整型数整型数P操作（操作（wait）原语）原语V操作（操作（signal）原语）原语临沂师范学院信息学院SnP(s): while s=0

25、 do no-op s:=s-1;nV(s): s:=s+1;临沂师范学院信息学院整型信号量机制执行过程整型信号量机制执行过程临沂师范学院信息学院临界区临界区P1P(S)V(S)整型信号量的特点整型信号量的特点nwait(S)和和signal(s)是原子操作是原子操作n只要信号量只要信号量S=0，就不断测试，不满足，就不断测试，不满足“同步机制规则同步机制规则”中的让权等待中的让权等待临沂师范学院信息学院记录型信号量记录型信号量n记录型结构，包含两个数据项：记录型结构，包含两个数据项：type semaphore=record value:integer; L:list of process;

26、 end临沂师范学院信息学院Value S L ns.value为资源信号量其初值：某类资源的数目为资源信号量其初值：某类资源的数目nwait操作：申请一个单位资源操作：申请一个单位资源Procedure wait(S)Var S:semaphore;beginS.value:=S.value-1;If S.value0 then block(s,L)end临沂师范学院信息学院临沂师范学院信息学院临界区临界区P4wait(S)临界区临界区P3wait(S)临界区临界区P2wait(S)临界区临界区P1wait(S)假设：系统中有三台打印机，那么假设：系统中有三台打印机，那么S.value=3，

27、有，有四个并发的打印进程四个并发的打印进程.s.value:=3-1If s.value0Then block(s,L)end.s.value:=2-1If s.value0Then block(s,L)end.s.value:=1-1If s.value0Then block(s,L)end.s.value:=0-1If s.value0Then block(s,L)endnSignal操作：释放一个单位资源操作：释放一个单位资源Procedure signal(S)Var S:semaphore;beginS.value:=S.value+1;If S.value=0:表示系统中可用的资源

28、数量表示系统中可用的资源数量nS.value=1 and sn=1 then for i:=1 to n do si:=si-1; endfor else当发现第一个当发现第一个si1就把该进程放入等待队列并将其就把该进程放入等待队列并将其程序计数器置于程序计数器置于Swait操作的开始位置操作的开始位置 endif临沂师范学院信息学院Ssignal(s1,s2,sn) for i:=1 to n do si:=si+1;将所有等待将所有等待Si的进程由等待队列取出放入到的进程由等待队列取出放入到就绪队列就绪队列endfor;临沂师范学院信息学院一般信号量集一般信号量集n一般信号量集是指同时需

29、要多种资源、每一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。在一个临界值时的信号量处理。n一般信号量集的基本思路就是在一般信号量集的基本思路就是在AND型信型信号量集的基础上进行扩充，在一次原语操号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。作中完成所有的资源申请。临沂师范学院信息学院临沂师范学院信息学院临沂师范学院信息学院用信号量实现互斥用信号量实现互斥Var mutex:semaphore:=1Begin Parbegin Process1:begin repeat wait(mutex

30、); critical section signal(mutex); remainder section until false; end;临沂师范学院信息学院Process2:begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end;parend临沂师范学院信息学院n在实现互斥时应注意在实现互斥时应注意nwait(mutex)和和signal(mutex)必须成对地必须成对地出现出现n缺缺wait(mutex)将会引起系统混乱，不能保将会引起系统混乱，不能保证对临界

31、资源的互斥访问证对临界资源的互斥访问n缺缺signal(mutex)将会使该临界资源永久不将会使该临界资源永久不被释放被释放临沂师范学院信息学院图例：初始状态图例：初始状态临沂师范学院信息学院初始状态初始状态mutex:=1没有并发进程使用临界区没有并发进程使用临界区临界资源临界资源互斥的进程互斥的进程一个进程申请临界资源一个进程申请临界资源临沂师范学院信息学院mutex:=1没有并发进程使用临界区没有并发进程使用临界区申请成功，进程使用临界资源申请成功，进程使用临界资源临沂师范学院信息学院mutex:=0另一个进程也使用临界区另一个进程也使用临界区临沂师范学院信息学院mutex:=0申请失败

32、申请失败临沂师范学院信息学院mutex:=阻塞队列阻塞队列-1释放资源释放资源临沂师范学院信息学院mutex:=阻塞队列阻塞队列02.4经典进程的同步问题经典进程的同步问题n生产者消费者问题生产者消费者问题n哲学家进餐问题哲学家进餐问题n读者写者问题读者写者问题临沂师范学院信息学院经典的生产者消费者问题经典的生产者消费者问题临沂师范学院信息学院生产者生产者消费者消费者放产品放产品取产品取产品一次只可放一个产品一次只可放一个产品生产者消费者问题生产者消费者问题n同步问题：同步问题：P进程不能往进程不能往“满满”的缓冲区中放产品，设置的缓冲区中放产品，设置信号量为信号量为emptyC进程不能从进程

33、不能从“空空”的缓冲区中取产品，设置的缓冲区中取产品，设置信息号为信息号为full临沂师范学院信息学院消费者：消费者：Repeat P(full); 从缓冲区取产品从缓冲区取产品; V(empty)； 消费产品消费产品;Until false临沂师范学院信息学院生产者：生产者：Repeat 生产一个产品生产一个产品; P(empty); 送产品到缓冲区；送产品到缓冲区； V(full);Until falseempty初值为初值为1，full初值为初值为0临沂师范学院信息学院多个缓冲区的生产者和消费者多个缓冲区的生产者和消费者临沂师范学院信息学院生产者：生产者：Repeat 生产一个产品生产一

34、个产品; P(empty); 往往Buffer(in)里面放产品里面放产品; in:=(in+1) mod n; V(full);Until false多个缓冲区的生产者和消费者多个缓冲区的生产者和消费者临沂师范学院信息学院消费者：消费者：Repeat P(full); 从从buffer(out)里面取产品里面取产品; out:=(out+1) mod n; V(empty)； 消费产品消费产品;Until false思考：要不要对缓冲池（临界资源）进行互思考：要不要对缓冲池（临界资源）进行互斥操作？斥操作？临沂师范学院信息学院Producer:begin repeat生产产品生产产品;P(e

35、mpty); P(mutex); Buffer(in):=nextp; in:=(in+1) mod n; V(mutex); V(full); until false; end;临沂师范学院信息学院Consumer:begin repeat P(full); P(mutex); nextc:=Buffer(out); out:=(out+1) mod n; P(mutex); P(empty); 消费产品消费产品; until false; end;临沂师范学院信息学院注意注意n每个程序中的每个程序中的P操作顺序不能颠倒。应先执操作顺序不能颠倒。应先执行对资源信号量的行对资源信号量的P操作，

36、然后再执行对互操作，然后再执行对互斥信号量的斥信号量的P操作，否则可能引起进程死锁。操作，否则可能引起进程死锁。临沂师范学院信息学院经典的哲学家进餐问题经典的哲学家进餐问题n有五个哲学家，他们的生活方式是交替地有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有分别坐在周围的五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能他的筷子，只有在他拿到两支

37、筷子时才能进餐。进餐完毕，放下筷子又继续思考。进餐。进餐完毕，放下筷子又继续思考。临沂师范学院信息学院临沂师范学院信息学院分析分析n筷子是临界资源，在一段时间内只允许一筷子是临界资源，在一段时间内只允许一个哲学家使用个哲学家使用n用一个信号量表示一支筷子，由这五个信用一个信号量表示一支筷子，由这五个信号量构成信号量组号量构成信号量组 Var chopstick:array04 of semaphoren所有信号量被初始化为所有信号量被初始化为1临沂师范学院信息学院用记录型信号量解决哲学家进餐问题用记录型信号量解决哲学家进餐问题第第i个哲学家的活动可描述为个哲学家的活动可描述为Repeat wa

38、it(chopsticki); wait(chopstick(i+1)mod 5); eat signal(chopsticki); signal(chopstick(i+1)mod 5); think;Until false临沂师范学院信息学院问题问题n假如五个哲学家同时饥饿而各自拿起左边假如五个哲学家同时饥饿而各自拿起左边的筷子，会使五个信号量均为的筷子，会使五个信号量均为0，当他们再，当他们再试图拿起右边筷子时，都将无限期地等待。试图拿起右边筷子时，都将无限期地等待。临沂师范学院信息学院解决方法解决方法n至多四个人同时拿左的筷子，保证至少有至多四个人同时拿左的筷子，保证至少有一个人可以进

39、餐，最终释放筷子使更多的一个人可以进餐，最终释放筷子使更多的人进餐人进餐n仅当哲学家的左右两支筷子均可用时，才仅当哲学家的左右两支筷子均可用时，才允许他拿起筷子进餐允许他拿起筷子进餐n给所有哲学家编号，奇数号的哲学家先拿给所有哲学家编号，奇数号的哲学家先拿左边的筷子，偶数号的哲学家则反之左边的筷子，偶数号的哲学家则反之临沂师范学院信息学院用用AND型信号量解决哲学家进餐问题型信号量解决哲学家进餐问题Var chopstick:Array04 of semaphore:=(1,1,1,1,1)临沂师范学院信息学院第第i个哲学家的活动个哲学家的活动Repeat think; Swait(chops

40、tick(i+1)mod 5,chopsticki); eat Ssignal(chopstick(i+1) mod 5,chopsticki); think;Until false;临沂师范学院信息学院读者写者问题读者写者问题n有两组并发进程：有两组并发进程：读者和写者，共享一组数据区读者和写者，共享一组数据区n要求：要求：允许多个读者同时执行读操作允许多个读者同时执行读操作不允许读者、写者同时操作不允许读者、写者同时操作不允许多个写者同时操作不允许多个写者同时操作临沂师范学院信息学院n如果读者来：如果读者来：无读者、写者，新读者可以读无读者、写者，新读者可以读有写者等，但有其它读者正在读，

41、则新读者也有写者等，但有其它读者正在读，则新读者也可以读可以读有写者写，新读者等有写者写，新读者等n如果写者来：如果写者来：无读者，新写者可以写无读者，新写者可以写有读者，新写者等待有读者，新写者等待有其它写者，新写者等待有其它写者，新写者等待临沂师范学院信息学院Var rmutex,wmutex:semaphore:=1,1; readcount:integer:=0; begin parbegin 读者：读者：begin repeat P(rmutex); if readcount=0 then P(wmutex); readcount:=readcount+1; V(rmutex); 执

42、行读操作执行读操作; P(rmutex); readcount:=readcount-1; if readcount=0 then V(wmutex); V(rmutex); until false; end临沂师范学院信息学院写者：写者：begin repeatP(wmutex); 执行写操作执行写操作;V(wmutex); until false; end临沂师范学院信息学院2.6进程通信进程通信n进程通信是指进程之间的信息交换进程通信是指进程之间的信息交换n交换的信息量：交换的信息量：一个状态或数值一个状态或数值上千个字节上千个字节临沂师范学院信息学院进程通信分类进程通信分类1.低级通信

43、：进程的互斥和同步低级通信：进程的互斥和同步2.高级通信：指用户可直接利用高级通信：指用户可直接利用OS提供的提供的一组一组通信命令通信命令，高效地传送大量数据的一，高效地传送大量数据的一种通信方式。对用户透明。种通信方式。对用户透明。临沂师范学院信息学院高级通信分类高级通信分类n共享存储器系统共享存储器系统n消息传递系统消息传递系统n管道通信管道通信临沂师范学院信息学院共享存储器系统共享存储器系统1.共享数据结构的通信方式，进程之间通过共享数据结构的通信方式，进程之间通过某种数据结构，如缓冲池进行通信属于低某种数据结构，如缓冲池进行通信属于低级通信方式；级通信方式；2.共享存储区通信方式，为

44、了传送大量信息，共享存储区通信方式，为了传送大量信息，在存储器中划出一块共享存储区，进程可在存储器中划出一块共享存储区，进程可通过对共享存储区进行读或写来实现通信，通过对共享存储区进行读或写来实现通信，属于高级通信方式。属于高级通信方式。临沂师范学院信息学院消息传递系统消息传递系统信息交换的单位是消息或报文，分成两种：信息交换的单位是消息或报文，分成两种：1.直接通信方式直接通信方式2.间接通信方式间接通信方式计算机网络中将消息称为计算机网络中将消息称为报文报文临沂师范学院信息学院直接通信方式直接通信方式n发送进程直接把消息发送给目标进程发送进程直接把消息发送给目标进程n发送进程和接收进程都以

45、显式方式分别提发送进程和接收进程都以显式方式分别提供对方的标识符供对方的标识符n系统提供两条通信原语系统提供两条通信原语Send(Receiver,message); Receive(Sender,message);临沂师范学院信息学院例如：例如：Send(P2,m1); Receive(P1,m1);临沂师范学院信息学院解决生产者消费者问题解决生产者消费者问题repeat . produce an item in nextp; . Send(consumer,nextp);Until false;Repeat Receive(producer,nextp); . Consumer the i

46、tem in nextc;Until false;临沂师范学院信息学院间接通信方式间接通信方式n进程之间的通信需要通过某种中间实体，进程之间的通信需要通过某种中间实体，该实体用来暂存发送进程发送给目标进程该实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方的消息；接收进程则从该实体中取出对方发送给自己的消息。发送给自己的消息。n这种中间实体称为信箱。这种中间实体称为信箱。n消息在信箱中可以安全地保存，只允许核消息在信箱中可以安全地保存，只允许核准的目标用户随时读取，故可实现非实时准的目标用户随时读取，故可实现非实时通信。通信。临沂师范学院信息学院信箱的创建和撤消信箱的创建和

47、撤消n进程用信箱创建原语来建立一个新信箱。进程用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性创建者进程应给出信箱名字、信箱属性（公用、私用或共享）；对于共享信箱，（公用、私用或共享）；对于共享信箱，还应给出共享者的名字。还应给出共享者的名字。n用信箱撤消原语来撤消用信箱撤消原语来撤消临沂师范学院信息学院消息的发送与接收消息的发送与接收nSend(mailbox,message)将一个消息发送到指定信箱将一个消息发送到指定信箱nReceive(mailbox,message) 从指定信箱中接收一个消息从指定信箱中接收一个消息临沂师范学院信息学院信箱分类信箱分类n私用信箱私用信

48、箱n公用信箱公用信箱n共享信箱共享信箱临沂师范学院信息学院私用信箱私用信箱n用户进程建立，作为该进程的一部分。用户进程建立，作为该进程的一部分。n拥有者有权读消息，其他用户只能发送。拥有者有权读消息，其他用户只能发送。n采用单向通信链路。采用单向通信链路。n进程结束时信箱也消失。进程结束时信箱也消失。临沂师范学院信息学院公用信箱公用信箱n它由它由OS创建创建n提供给系统中的所有核准进程使用。提供给系统中的所有核准进程使用。n进程既可发送也可取出进程既可发送也可取出n采用双向通信链路的信箱来实现采用双向通信链路的信箱来实现n系统运行期间始终存在系统运行期间始终存在临沂师范学院信息学院共享信箱共享

49、信箱n由某进程创建，创建时提供共享进程（用由某进程创建，创建时提供共享进程（用户）的名字户）的名字n信箱的拥有者和共享者，都有权从信箱中信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息取走发送给自己的消息临沂师范学院信息学院信箱通信时发送和接收进程的关系信箱通信时发送和接收进程的关系n一对一关系一对一关系。建立一条专用的通信链路。建立一条专用的通信链路。n多对一关系多对一关系。多个用户进程与服务进程之间进行。多个用户进程与服务进程之间进行交互，又称客户交互，又称客户/服务器交互。服务器交互。n一对多关系一对多关系。一个发送进程与多个接收进程进行。一个发送进程与多个接收进程进行交互，使发

50、送进程可用广播形式，向接收者发送交互，使发送进程可用广播形式，向接收者发送消息。消息。n多对多关系多对多关系。建立一个公用信箱，多个进程投递。建立一个公用信箱，多个进程投递并取走自己的消息。并取走自己的消息。临沂师范学院信息学院管道通信管道通信n管道通信方式建立在文件系统的基础上，管道通信方式建立在文件系统的基础上，利用共享文件来连接两个相互通信的进程，利用共享文件来连接两个相互通信的进程，此共享文件称为管道此共享文件称为管道(Pipe)。n管道管道是指用于连接一个读进程和一个写进是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件。程，以实现它们之间通信的共享文件。临沂师范学院信

51、息学院临沂师范学院信息学院写进程写进程管道管道读进程读进程管道通信必需的协调能力管道通信必需的协调能力1.互斥当一个进程正在对管道进行读互斥当一个进程正在对管道进行读/写操作时，写操作时，另一进程必须等待。另一进程必须等待。2.同步当写（输入）进程把一定量的数据（如同步当写（输入）进程把一定量的数据（如4K）写入管道后，便去睡眠等待，直到读（输）写入管道后，便去睡眠等待，直到读（输出）进程取走数据后再把它唤醒。当读进程发现出）进程取走数据后再把它唤醒。当读进程发现管道空时也应睡眠等待，直至写进程将消息写入管道空时也应睡眠等待，直至写进程将消息写入管道后，才将它唤醒。管道后，才将它唤醒。3.判别对方是否存在，只有确定了对方存在时方能判别对方是否存在，只有确定了对方存在时方能进行通信。进行通信。临沂师范学院信息学院2.7线程线程n线程的引入线程的引入n线程与进程的对比线程与进程的对比临沂师范学院信息学院线程的引入线程的引入n进程的两个基本属性进程的两个基本属性1.资源的拥有者资源的拥有者：给每个进程分配一虚拟地址空间，保存进程给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件、映像，控制一些资源（文件、I/O设备），有设备），有状态、优先级、调度状态、优先级、调度2.调度单位：调度单位：进程是一个执行轨迹进程是一个执行轨迹n以上两个属性构成了进程并发执行的基础以上