《第2章进程管理2说课讲解》由会员分享，可在线阅读，更多相关《第2章进程管理2说课讲解（116页珍藏版）》请在金锄头文库上搜索。
1、2.3 进程的同步与通信,进程间的联系 进程的同步机制信号量及wait-signal操作（解决进程同步互斥问题）旧称P-V操作,2.3.1 进程同步的基本概念,1. 进程之间的两种相互制约关系 进程的并发执行虽然提高了资源利用率, 但由于进程的异步性, 会给系统造成混乱。为了使并发执行的各进程都能正确执行, 使它们之间能有效地共享资源和相互合作, 必须研究并发执行的各进程之间的相互制约关系, 采取一定的措施使系统中诸进程有条不紊的同步向前推进。进程之间有两种相互制约关系： 间接相互制约关系(资源共享关系) 直接相互制约关系(功能合作关系),1) 间接相互制约关系(资源共享关系、互斥关系) 由于
2、共享资源, 使得系统中本来没有逻辑关系的进程, 因相互竞争资源而产生了制约关系。 例如: 进程 P1和P2在运行中都要使用打印机, 为了保证各进程输出的完整, 打印机必须互斥访问 (独占使用)。这样, 一旦系统将打印机分配给进程 P1, 进程P2就必须等待, 直到P1用完打印机并释放后, P2才能使用。 这种因共享资源而使并发执行的各进程之间产生的关系, 叫做间接制约关系, 又叫做互斥 (mutual exclusion)关系。 这种关系可用“进程-资源-进程”来描述。,2)直接制约关系(相互功能合作关系、同步关系) 通常, 一个用户作业要涉及一组并发进程(输入、计算和输出进程), 这些进程必
3、须相互协作共同完成这项任务。 具体说, 在运行过程中, 某进程可能要在某些同步点上等待另一伙伴(协作进程)为它提供消息, 在未获得消息之前, 该进程处于等待状态, 获得消息后被唤醒进入就绪态, 此后, 才能继续运行。进程间的这种制约关系叫做直接制约关系, 又叫同步(synchronism)关系。 这种关系可用“进程-进程”来描述。,2. 临界资源和临界区,进程的互斥是由于共享资源而引起的, 为描述这类情况, 引入临界资源和临界区的概念。 临界资源(互斥资源)：critical resource 系统中一次只允许一个进程访问的资源; 这些资源既包括I/O设备, 如打印机等资源, 也包括软件资源,
4、 如共享变量、共享文件等。 临界区(互斥区): critical section 并发执行的进程中, 访问临界资源的必须互斥执行的程序段叫临界区。 临界区分散在每个要并发执行的进程中, 它们都对某个共享的数据结构(共享资源)进行访问,P1 :,P2 :,变量a是临界资源 C1、C2、C3是临界区 对a应互斥访问,P3 :,C3 ),C1 ),C2 ), a := a +1 print (a) , a := a +1 print (a) , if a 0 then a := a +1 else a:= a-1 ,Solution Requirements,Mutual Exclusion Onl
5、y one process can be in the critical section at any time Progress Decision on who enters CS cannot be indefinitely postponed No deadlock Bounded Waiting Bound on #times others can enter CS, while I am waiting No livelock Also efficient (no extra resources), fair, simple, ,3.同步机制应遵循的原则(进入临界区的原则) 空闲让进
6、：当无进程在临界区时，任何一个有权 使用临界区的进程可进入。 (多中择一):当没有进程在临界区，而同时有多个 进程要求进入临界区，只能让其中之一进入 忙则等待：当有进程在临界区时，其它试图进入 临界区的进程必须等待，即不许两个以上的 进程同时进入临界区 有限等待：任何进入临界区的要求应在有限的时 间内得到满足 让权等待：处于等待状态的进程应放弃占用CPU 以免进程陷入“忙等”。,硬件 硬件指令(原语不可中断)和屏蔽中断两种办法。 软件 编程解决: 进入临界区之前附加一段检查的代码(进入区), 以保证互斥进入, 在临界区后各附加程序(退出区)恢复标志, 表明已从临界区退出, 其它进程可进入。 缺
7、点: 需要高的编程技巧,忙等待 。,2.3.2 如何解决互斥问题,软件解法 (1)var free:boolean; true:临界区空(初值) false:非空 proc p(n); 每个并发进程 L: if free then begin free:= false; critical section end else goto L; free:=true; ,问题: 当p(i)测试free为true, 还未将free改为false时, 此时恰好p(j)也测试free, 其值仍然是true, 使两个进程都进入临界区违反了忙则等待的原则。,begin 主程序 Parbegin p(1)；p(2
8、)；p(n)； parend end；,软件解法 (2) var turn: boolean; 当turn=true时P可进入临界区,否则Q可进入临界区 P) Q) repeat until turn; repeat until not turn; critical section critical section turn:=flase; turn:=true; ,问题: 解决了解法 (1) 的问题,不会使两个进程都进入临界区,但P和Q必须轮流进入临界区,当P退出临界区后 turn=flase, 此时临界区空闲, 但 P不能再进入临界区, 违反了空闲让进的原则。,软件解法：(3) var p
9、turn,qturn: boolean;初值为false P进入临界区的条件: pturn qturn:=false . .,问题: 似乎解决了解法 (2)的问题, P和Q不必轮流进入临界区, 但当P和Q同时执行 pturn=true; qturn=true;时, 临界区空闲, 而P和Q都不能进入临界区, 仍然违反空闲让进的原则。,软件解法(4) : 在解法(3)基础上引入turn枚举类型(初值任意) var turn: (p,q) pturn,qturn: boolean;初值为false P等待的条件: qturn qturn:=false . . 可见软件法需要很高的编程技巧,而且“忙等
10、”效率低 。,var k:boolean; 全局变量k=true表示资源已被占用 func Lock(var target:boolean):boolean; TestandSet begin 加锁原语或测试并设置原语不可中断 Lock :=target; target:=true end; proc p(n); 每个并发进程 while Lock(k) do ; critical section k:=false; 开锁 ,硬件解法 (1) 用硬件指令“测试并设置”,begin 主程序 k:=false ; 初值表示资源可用 parbegin p(1)；p(2)；p(n)； parend e
11、nd；,var lock:boolean; 每组共享定义一个全局变量 function swap(var a,b:boolean); 交换指令不可中断 var temp:boolean; begin temp:=a; a:=b; b:=temp end; proc p; 每个并发进程 var key:boolean; 定义一个局部变量 key:=true; repeat swap(lock, key) until key=false; critical section 局部变量key存储lock的原值 lock:=false; ,硬件解法(2)用硬件指令“交换”指令,硬件解法(3)“开关中断”
12、指令,CPU从某进程转接到另一进程是由于时钟中断(时间片到) 或其它中断引起的。当一个进程进入临界区前, 关闭所有的中断, 其它进程就不可能进入临界区。当进程退出临界区后, 再开中断。此后要进入临界区的进程就可进入。描述如下： 关中断(disable) critical section 开中断(enable) 开、关中断可以保证各进程互斥地进入临界区。这种方法简单, 但系统要付出较高代价。缺点是：限制了处理机交叉执行程序的能力。,2.3.3 信号量机制,同步机制： 信号量及wait-signal操作；管程；条件临界域；路径表达式等（用于集中式系统中） 会合；通信顺序进程；分布进程；远程过程调用
13、等（适用于分布式系统中）,同步机制应满足的基本要求： 描述能力、可以实现、 效率高、 使用方便 信号量(Semaphores)共享资源的使用信号的量: 1965年荷兰学者Dijkstra提出信号量机制，现已被广泛用于解决各种互斥和同步问题。,1. 整型信号量： 管理控制铁路交通的重要工具是信号灯。利用信号灯的状态(颜色)控制火车的通行。单段铁路任何时刻只允许一列火车通行(相当于临界区), 遇红灯(表示路段被占用)应等待, 遇绿灯可进入 (同时红灯亮禁止其它火车进入), 驶出后绿灯亮,信号灯标志路段资源的占用情况。 为了管理各并发进程对共享资源的使用, 引入表示共享资源的使用信号的量信号量的概念
14、; 它被定义为一个整型量 S; S0 表示资源可用 (无进程在临界区相当于绿灯亮); 某进程企图进入临界区时, 若S0允许进入; 信号量 S 只能通过两个标准原子操作(不可中断) wait(S)和signal(S)来访问。过去它们被称为P-V操作, 可描述为：,wait(S)：while S=0 do ; 有进程在临界区空循环 S:=S-1; signal(S)： S:=S+1;,进入区执行wait(S)操作,退出区执行signal(S),例如: var s:integer; s:=1; parbegin p1: begin p2: begin wait(s); wait(s); 临界区代码
15、临界区代码 signal(s); signal(s); end; end; parend wait(S)操作中, 当S=0时会使进程处于“忙等”状态。,2. 记录型信号量 为了消除“忙等”现象, 若资源被占用应自我阻塞, 记录型信号量用记录结构, 增加等待队列头指针域： type semaphore = record value:integer; L:list of process； end； s: semaphore; S.value的初值表示系统中该类资源的数目(又称资源信号量)。运行中S.value0表示该资源可用的数目, S.value0 的绝对值表示在该资源的等待链表中已阻塞进程的数目, S.L则为该链队列头指针。若S.value初值为1则转化为互斥信号量。 相应的 wait(S) signal(S)操作可描述为：,procedure wait(s:semaphore); begin s.value:=s.value-1; 先减1再判断 if s.value0 then block(s.L) end; 其中: block(s.L)原语是将该进程自我阻塞, 置为等待状 态, 并将它的PCB插到信号量队列s.L的末尾。 将来被唤醒后, 运行应从wai
