同步问题分析

3.2 信号量机制
一、记录型信号量机制
描述进程前趋关系： 实例： a
p2 p1 Var a,b,c,d,e:semaphore:=0,0,0,0,0; begin parbegin process p1: begin L ; V(a); V(b); end; process p2: begin P(a); L ; V(c); end; process p3: begin P(b); L ; V(d); end; process p4: begin P(c); P(d); L ; V(e); end; process p5: begin P(e); L ; end; parend end
是算法1和3的组合，既实现了“空闲让进”，又保证了 “忙则等待”。
3.1 进程同步的基本概念
三、利用软件方法解决进程互斥问题
缺点： 四种算法全部属于“忙等待”方式。 现在已很少使用。
3.1 进程同步的基本概念
四、利用硬件方法解决进程互斥问题
利用Test-and-Set指令 1.Test-and-Set 指令 function TS(var lock:boolean):boolean begin TS:=lock; lock:=true; end 结果 TS(lock)=lock lock=true
b
p3
c
p4
d e
p5
3.2 信号量机制
一、记录型信号量机制
描述进程前趋关系： 模型： 与进程同步类似；不同点： 1.信号量s的初值=0； 2.若等信号，则在开始处执行P(s)； 3.若发信号，则在最后处执行V(s)；
3.2 信号量机制
一、记录型信号量机制
物理含义： 信号量的值s.value： 表示系统中某类可用资源的数目。s.value>0，表示还有 此类资源可供分配；s.value≤0，表示资源已分配完毕， 其绝对值表示s.L链表中阻塞进程的数目。 P(s)：请求一个单位的资源。 V(s)：释放一个单位的资源。
Process P0 : repeat while turn≠0 do no-op; critical section turn:=1; remainder section until false; Process P1 : repeat while turn≠1 do no-op; critical section turn:=0; remainder section until false;
3.1 进程同步的基本概念
四、利用硬件方法解决进程互斥问题
2. 利用TS指令实现进程互斥的模型
repeat while TS(lock) do skip;----进入区 critical section; --------临界区 lock:=false; -----------------退出区 remainder section until false;
3.2 信号量机制
一、记录型信号量机制
实现进程同步： 模型：一类资源⇔一个公用信号量s（初值=0..n） 请求资源的进程中：P(s); 释放资源的进程中：V(s); 实例：进程A和B合作。 A B M M 取数据； M 计算数据； 送据； M M
3.2 信号量机制
一、记录型信号量机制
var s:semaphore:=0; parbegin processA:begin M P(s); 取数据； 计算数据; M end processB:begin M 送数据； V(s); M end parend 执行时两种可能性： 1. 在进程B还没有送数据之前，进程 A先执行了P(s)，结果会怎样？ 2. 进程B的V(s)操作已经完成，进程A 才执行了P(s)，结果会怎样？ 1.进程A执行P(s)，会使自己进入阻 塞状态，直至进程B送数据后执行 V(s) ，才能将它唤醒。 2. 若进程B的V(s)操作已经完成，进 程A才执行了P(s)，则进程A不会 阻塞。它可以顺利地取到数据，完 成下面的操作。
硬件指令的缺点： 1.虽可有效实现互斥，但属于“忙等待”方式，违背了 “让权等待”原则。 2.很难用它解决复杂的同步问题。
3.2 信号量机制
一、记录型信号量机制 二、AND型信号量集机制
1965年，荷兰科学家Dijkstra在THE系统上提出。 一个信号量S是一个整型量，除对其初始化外，它只能 由两个原子操作P和V来访问。 P和V的名称来源于荷兰文proberen（测试）和verhogen （增量），它们的执行具有不可中断性。 本书中将P、V操作称做 wait 和 signal 操作。
3.1 进程同步的基本概念
一、临界资源
临界资源：一段时间内只允许一个进程访问的资源。 要求：共享临界资源的诸进程必须互斥访问临界资源。 原因： 例：生产者--消费者问题（P62） 生产者（producer） M 放产品； counter:=counter+1; M 消费者（consumer） M 取产品； counter:=counter-1; M
缺点：解决了“空闲让进”，但又违背了“忙则等待”。
3.1 进程同步的基本概念
三、利用软件方法解决进程互斥问题
算法3 var flag:array[0..1] of boolean;
Process P0 : repeat flag[0]:=true; while flag[1] do no-op; critical section flag[0]:=false; remainder section until false; Process P1 : repeat flag[1]:=true; while flag[0] do no-op; critical section flag[1]:=false; remainder section until false;
彼此有关
具体表现为： 1）进程之间由于共享资源而产生的间接制约关系。 2）进程之间由于相互合作而产生的直接制约关系。
进程同步
解决1）的方法是：保证诸进程互斥访问临界资源。 解决2）的方法是：协调相互合作的诸进程的执行次序。--狭义的同步
3.1 进程同步的基本概念
一、临界资源 二、临界区 三、利用软件方法解决进程互斥问题 四、利用硬件方法解决进程互斥问题
缺点：强制两进程轮流进入临界区；不能保证“空闲让进”。
3.1 进程同步的基本概念
三、利用软件方法解决进程互斥问题
算法2 var flag:array[0..1] of boolean; （flag[i]=true，Pi在临界区）
Process P0 : repeat while flag[1] do no-op; flag[0]:=true; critical section flag[0]:=false; remainder section until false; Process P1 : repeat while flag[0] do no-op; flag[1]:=true; critical section flag[1]:=false; remainder section until false;
3.2 信号量机制
一、记录型信号量机制
实现进程互斥： 模型：一个临界资源⇔一个互斥信号量mutex（初值=1） 需互斥访问该临界 P(mutex);----进入区 资源的每个进程中 CS; V(mutex);----退出区 实例：三个进程执行中要共享变量count。 分析：count属于临界资源，对其应互斥访问。
3.1 进程同步的基本概念
一、临界资源
机器语言形式为：
生产者 counter:=counter+1; ⇓ 1 register1:=counter; 2 register1:= register1+1; 3 counter:= register1; 可能性 CPU执行顺序 counter的值 （初值为5） A 123456 5 正确 消费者 counter:=counter-1; ⇓ 4 register2:=counter; 5 register2:= register2-1; 6 counter:= register2; B 456123 5 正确 C 124536 4 不正确 D 451263 6 不正确 不是A、B M M 不正确
由于生产者和消费者并发运行，且共享变量 counter ，造成：
3.1 进程同步的基本概念
一、临界资源
结论： counter是临界资源，生产者和消费者应互斥访问。 即：虽然生产者、消费者并发执行，但在执行counter的 加1、减1的语句时，只能顺序进行。 即：只能按可能性中A或B的顺序进行，绝不能交替进行。 临界资源实例： 硬件中的打印机、磁带机等，软件中的变量、队列、缓 冲区等。
思路： false 可以进入CS a)每个临界资源⇔一个lock（初值=false） true 不能进入CS b)在进入区测试是否 不能 (lock=true):忙等待 可以进入临界区CS 可以 (lock=false) 进入CS执行 退出CS
3.1 进程同步的基本概念
四、利用硬件方法解决进程互斥问题
缺点：解决了“忙则等待”，但又违背了“空闲让进”和 “有限等待”。
3.1 进程同步的基本概念
三、利用软件方法解决进程互斥问题
算法4
Process P0 : repeat flag[0]:=true; turn:=j; while (flag[1] and turn=j) do no-op; critical section flag[0]:=false; remainder section until false;
3.1 进程同步的基本概念
二、临界区（Critical Section）
临界区（CS）：每个进程中访问临界资源的那段代码。 例： 生产者（producer）
M 放产品； counter:=counter+1; ---CS M 消费者（consumer） M 取产品； counter:=counter-1; ---CS M