第二章进程管理3.docx
《第二章进程管理3.docx》由会员分享，可在线阅读，更多相关《第二章进程管理3.docx（46页珍藏版）》请在冰点文库上搜索。
第二章进程管理3
2.8进程的同步
2.8.1进程同步的基本概念
一．进程同步的任务
1.引例------反映“不可再现性”“与时间有关的错误”示例
2.1的例3．
VarN:
Integer
Begin
N:
=0;
Parbegin
ProgramA:
ProgramB:
BeginBegin
repeatrepeat
┆┆
a1:
N:
=N+1;b1：
Print（N）
untilfalse┆
┆b2：
N:
=0；
Enduntilfalse
End
Parend
End
进程A,B执行时共享变量N，若执行顺序为:
a1b1b2或b1b2a1执行结果不同，有可能使数据出错
也就是进程并发运行呈现出“不可再现性”即，产生“与时间有关的错误”。
2．进程同步的任务
（1）使多个进程并发运行具有可再现性
（2）使多个进程可以进行通信（IPC）
。
多个进程合作一个任务（多个进程并发运行以提高速度），但每个进程只能访问本进程的内存空间，多个进程如何进行通信？
例
问题:
。
一个进程如何向另一进程传送信息（数据）
。
如何保证两个或多个进程在共享资源时不会彼此影响
。
如何为存在依赖关系的进程进行适当地定序
二、同步和互斥的概念
1．间接制约（资源共享引起）——互斥使用临界资源，如两个或多个进程互斥使用打印机。
2．直接制约（互相合作关系）——同步
A，B进程共享缓冲区，它们不是一种简单地互斥使用缓冲区的关系:
A，B进程在执行次序上应该协调，它们互相之间制约关系为：
·当缓冲区放满数据时，A进程不能再向缓冲区放数据
·当缓冲区数据已全部取走（缓冲区空），B进程不能再打印
“同步”是指进程在执行次序上有互相的制约关系，互斥是同步的特例。
三、临界区
·临界资源：
一次仅允许一个进程使用的资源
·临界区：
进程中访问临界资源的那段代码（注:
临界区是代码，不是数据区）
并发执行示例
用Parbegin和Parend把并发执行的程序括起来
Begin
VarN:
integer——临界资源
N:
=0；
Parbegin
ProgramA：
Begin
Repeat
·
al:
N:
=N+1——临界区
·
untilfalse
End
Parend
ProgramB:
Begin
Repeat·
bl:
Print（N）;
b2:
N:
=0;临界区
·
untilfalse
End
End
例：
两个进程共享一个变量count，执行顺序不同结果不同
Begin
Varcount:
integer:
=0临界资源
Parbegin
P1:
begin
┆
a1:
R1=count;
a2:
R1:
=R1+1;临界区
a3:
count:
=R1;
┆
end
P2:
begin
┆
b1:
R2:
=count;
b2:
R2:
=R2-1;临界区
b3:
count:
=R2
┆
endparend
end
若count当前值为5，按如下几种不同运行顺序，结果不同：
①a1,a2,a3,b1,b2,b3或b1,b2b3,a1,a2,a3,count的值为5
②a1,a2,b1b2,a3,b3,结果为4
③a1,b1,a2,b2,a3,b3:
count的值为4
OS应提供同步机制以避免出现上述现象,使得进程P1使用临界资源期间（在临界区中运行），进程P2不能使用临界资源
2.8.2进程的同步机制要求
一、进入区和退出区的设置
为了保证对临界资源的正确使用，将程序对临界资源的访问过程分成三个部分：
程序P1:
┋
检查是否可进入临界区，并设置“正在访问”标志，使其它进程不可以进入临界区
临界区
将“正在访问”标志清除，使其它进程可以进入临界区
其它代码
二、同步机制的准则（P64）
1．空闲让进
2．忙则等待
3．有限等待
4．让权（CPU运行权）等待
2.8.3用软件方法解决互斥问题
用户在程序中设置逻辑变量，用于要进入临界区进程的测试，OS不提供任何支持
方法一、设置“令牌”,输流进入临界区
用变量turn指示被允许进入的进程编号，初值为i表示允许Pi进程进入临界区
改错P65第5行应为turn=i
Pi:
repeat
Whileturn≠idono-op——进入区（测试）
turn:
=j，——退出区
其它代码
untilefalse
Pj:
repeat
Whileturn≠jdono-op
turn:
=i;
其它代码
untilefalse
分析：
·turn相当“令牌”,输流使用――不会同时进入临界区,不会同时都不能进入，符合“空闲让进”“忙则等待”
·Pi和Pj必须输流进入临界区
缺点:
Pi退出后（turn:
=j），若因某种原因Pj不能进入临区，那么Pi也不能再进入临区――
方法二、每个进程设置自己是否在临界区的标志flag
flag[0,1…n]ofboolean；n个进程标志，初值为false——不在临界区
每个进程Pi在进入临界区前先检查其它一进程是否在临界区，如不在，表示则Pi可进入，并在进入前首先修改本进程标志flag[i]:
=true,表示“本进程在临界区，其它进程不能进入临界区”――忙则等待
varflag[0,1…n]ofboolean
Pirepeat
a1:
whileflag[j]dono-op—检查其它进程是否在临界区
flag[i]:
=true——修改标志，表示Pi要进入临区
临界区
flay[i]:
＝false
其它代码
untilfalse
Pj:
repat
b1:
whileflay[i]dono-op
b2:
flay[j]:
=true
临界区
flay[j]:
=false
其他代码
untilfalse
若判断和设置标志的动作连续完成，则可顺利实现“互斥进入”。
·若Pi,Pj几乎同时要求进入临界区，如顺序为：
a1,b1则测试条件都满足（都不在临区）
则Pi,Pj同时进入临区（不能互斥）——违背“忙则等待”。
方法三、先设置标志（表示要进入临区），再测试
Pi:
repeat
a1:
flay[i]:
=true
a2:
whileflay[j]dono-op
临界区
flay[i]:
=false
其它代码
untilfalse
Pj:
repeat
b1:
flay[j]:
=true;
b2:
whileflay[i]dono-op
临界区
flay[j]:
=false
其它代码
untilfalse
若顺序为:
a1,b1,a2,b2,则Pi,Pj都进不了临区，违背“有空让进”
2.8.4用硬件方法解决同步问题
软件方法解决互斥的缺点
程序中在进入临区之前用两条语句分别进行测试和锁住，如果测试和锁住两条语句不能连续执行（例如上述进程Pi,Pj几种特殊切换）,就会产生不符合同步机制准则的结果。
下面用硬件方法解决同步问题。
一、Test-and-Set指令（TS指令）
锁Lock=false可进入临界区（锁开着）
Lock=true不可进入临界区（锁关着）
设置硬件测试锁的指令TestandSet，把测试和关锁两个操作结合在一条指令中，不会被打断，保证互斥进入临界区，该指令功能如下：
FunctionTS（VarLock:
boolean）:
Boolean
Begin
TS:
=Lock
Lock:
=true;
End
二、利用TS实现进程互斥
repeat
WhileTS（Lock）doskip;---反复测试，直至TS为false（等待CPU运行其它进程，其它进程把Lock=false）
临界区
lock:
=false;
其它代码
untilfalse
缺点:
WhileTs（Lock）doskip当TS=true时需要反复测试（违背让权（CPU运行权）等待）
三、Swap指令（类似TS指令）P68自学
思考用Swap指令为什么可实现互斥
2.6.5信号量机制
一条硬件指令执行时不会被打断，原语也是“不会被打断”的操作
一、整型信号量的原语操作
整型信号量S:
>0可以进入临界区
≤0不可进入临界区
Wait（S）:
/*也称P操作*/
WhileS≤0dono-op
S:
=S–1
Wait原语类似于Test-and-Set指令，把测试和设置（S:
=S–1）两个操作在一条原语中实现
SignaL（S）:
/*也称V操作*/
S:
=S+1;
SignaL原语相当于Lock=false（开锁）
可利用整型信号量实现互斥，程序如下：
Varmutex:
semaphone:
=1/*信号量置初值*/
Begin
Parbegin
Process1:
begin
Repeat
Wait（mutex）;
临界区
signal（mutex）;
其它代码
untilfalse;
end
Process2:
begin
Repeat
Wait（mutex）;
临界区
Signal（mutex）;
其它代码
untilfalse;
end
parend
end
缺点:
Wait（S）:
WhileS≤0dono-op当S≤0时需要反复测试（违背让权（CPU运行权）等待）
二、记录型信号量机制
Typesemaphone=record
value:
integer;/*信号量的整型值*/
L:
listofprocess;/*设置等待该信号量的进程阻塞队列*/
End
相应地，Wait（S）和Signal（S）操作可描述为：
Procedurewait（S）-----P操作
VarS:
semaphone;
Begin
S.value:
=S.value-1;
ifS.value<0thenblock（S.L）
End
block（S.L）为阻塞原语,若S.value<0则调用Wait（S）的进程自我阻塞（等待其它进程用signal（S）唤醒）
注意。
此处用if测试而不是While测试，这样不必“忙等”。
Proceduresignal（S）-----V操作
VarS:
semaphone;
Begin
S.value:
=S.value+1;
ifS.value≤0thenwakeup（S.L）;
End
wakeup（S.L）为唤醒原语
三、整型信号量和记录型信号量的不同
整型记录型
①While测试①用if测试（不必反复测试）
②wait（S）中先WhileS≤0②wait（S）中先S.value:
=S.value-1
后S:
=S–1后ifS.value<0thenblock（S.L）
③不涉及进程阻塞队列③测试条件不通过进程进入阻塞队列
④Signal只释放资源④Signal操作释放资源还负责唤醒进程
四、信号量整型值的变化范围
·信号量整数值可作为同类可用资源计数：
S.value>0时，S.value的值为该类资源当前可用的数量
S.Value<0时，其绝对值为请求使用该资源（要想进入临区对资源操作）的进程数（在阻塞队列中等待该信号量的进程数）。
例：
五个进程共享3台打印机
S.value初值为3
若五个进程几乎同时申请进入临区使用打印机，那么：
第一个进程申请进入：
S.value:
3-1=2
第二个进程申请进入：
S.value:
2-1=1申请成功进入临区
第三个进程申请进入：
S.value:
1-1=0
上述三个进程在临区使用打印机未结束，第四,第五个进程也申请进入临区使用打印机，则：
第四个进程申请进入：
S.value:
0-1=-1——阻塞
第五个进程申请进入：
S.value:
-1-1=-2——阻塞
该信号量整型值S.Value的变化范围为3-2
五、利用信号量实现互斥
Varmutex:
semaphone:
=1
Begin
Parbegin
Process1:
begin
Repeat
Wait（mutex）;
临界区
signal（mutex）;
其它代码
untilfalse;
end
Process2:
begin
Repeat
Wait（mutex）;
临界区
signal（mutex）;
其它代码
untilfalse;
end
Parend
End
注。
阻塞进程被唤醒后不需再用Wait测试，直接进入临区
六、利用信号量同步
例一、生产者——消费者问题
1.单缓冲区，单生产者、单消费者
CPIOP
·同步问题：
生产者将产品一件（批）一次放入缓冲区，消费者从缓冲区取出一件（批）产品。
·同步要求：
当缓冲区有产品时，生产者不能再放产品到缓冲区，当缓冲区为空时，消费者进程不能从缓冲区取产品。
·信号量设置：
①empty:
初值为1（为空），表示有1个缓冲区，用来表示缓冲区是否为空
当生产者进程向缓冲区放产品之前，用Wait操作,测试empty的值是否≥1,若是，则可放产品。
当消费者进程从缓冲区取产品后，用Signal（empty）操作释放缓冲区（表示缓冲区已空）
②full：
初值为0，表示缓冲区是否为满（有产品），初值0表示没有产品。
当消费者进程从缓冲区取产品之前，用Wait操作测试full的值是否≥1，若是，可取产品。
当生产者进程向缓冲区放产品时，用signal（full）操作释放full表示缓冲区已满。
程序如下：
varempty,full:
semaphore:
=1,0
begin
Parbegin
producer:
consumer:
beginbegin
repeatrepeat
┆┆
生产产品
wait（empty）;wait（full）;
把产品放入缓冲区从缓冲区取出产品
signal（full）;signal（empty）;
┆┆
untilfalseuntilfalse
Parend
end
注意。
此处对信号量empty,full的wait,signal操作设置的位置
思考题：
如果用一个互斥信号量mutex,一个条件变量可以实现吗？
2.多缓冲区、单生产者、单消费者
多缓冲区可使生产者、消费者进程不是必须输流使用缓冲区
50
41
32
·同步要求：
缓冲池满了，生产者不能再放产品
缓冲池空了，消费者不能再取产品
·缓冲池中各缓冲区编号，0，1，…，n-1（n个缓冲区）,缓冲区循环编号，例：
6=（5+1）mod6=0
缓冲池用buffer数组表示下标从0到n-1
·信号量empty初值为n，（表示有n个空缓冲区）
信号量full初值为0，（表示缓冲区都空）
·生产者放产品时必须指定缓冲区编号，用in表示，初值为0
消费者取产品时用out指定缓冲区编号，初值为0
程序如下：
varempty,fullsemaphore:
=n,0;
buffer:
array[0,…n-1]ofitem;
in,out:
=0,0;
begin
parbegin
producer:
consumer:
beginrepeatbeginrepeat
┆┆
生产产品
wait（empty）;wait（full）;
buffer[in]:
=产品产品：
=buffer（out）
in:
=（in+1）modnout:
=（out+1）modn
signal（full）;signal（empty）;
untilfalse;untilfalse
parend
end
思考题：
（1）in和out值的变化范围？
（2）当in和out的值为多少的表示缓冲池放满了产品。
当in和out的值为多少时表示缓冲池没有产品。
3．多个缓冲区，多个生产者，多个消费者
与上述（2.）不同点：
·多个生产者共享缓冲池指针in，必须互斥使用in
·多个消费者共享缓冲池指针out，必须互斥使用out
·简单方法：
设置一互斥信号量mutec，使得无论生产者还是消费者，只能有一个
进程进入缓冲池
程序如下，P73
Varmutex,empty,full:
semaphone:
=1,n,0;
Buffer:
array[0,…,n-1]ofitem;
in,out:
integer:
=0,0;
Begin
Parbegin
Producer:
consumer:
beginbegin
repeatrepeat
produceraniteminnextpwait（full）;
wait（empty）;wait（mutex）;
wait（mutex）;nextc:
=buffer（out）;
buffer（in）:
=nextp;out:
=（out+1）modn;
in:
=（in+1）modn;signal（mutex）;
signal（mutex）;signal（empty）;
signa（full）;consumetheiteminnextc;
untilfalse;untilfalse;
endend
parend
end
讨论1．多个wait操作的不同顺序问题
（1）正确顺序
Producer:
consumer:
………………
a1:
wait（empty）;b1:
wait（full）
a2:
wait（mutex）;b2:
wait（mutex）;
………………
若缓冲已满，生产者进程阻塞，未执行wait（mutex），消费者进程可以运行
（2）错误顺序
如果将上述多个wait操作顺序颠倒如下：
-------
a1:
wait（mutex）;b1:
wait（mutex）;
a2:
wait（empty）;b2:
wait（full）
若缓冲已满，生产者进程运行：
先执行wait（mutex），通过，再执行wait（empty），生产者进程阻塞（等待empty），但不释放互斥信号量mutex，轮到消费者进程运行：
阻塞（等待mutex），这样两个进程都阻塞
结论：
一般先对资源同步信号量作wait操作，再执行对互斥信号量的wait操作
2．对互斥信号量mutex的wait操作和signal操作在同一个进程中必须成对出现。
3．对资源同步信号量的wait和signal操作分别处子不同的进程中
P：
wait（empty）;c:
wait（full）
Signal（full）signal（empty）
例2：
利用信号量控制程序（或语句）的执行顺序
程序前驱图程序前驱图中的信号量设置
ab
cd
e
fg
Vara,b,c,d,e,f,g:
semaphore:
0,0,0,0,0,0,0
Begin
Parbegin
S1begins1;sighal（a）;signal（b）;end;
S2beginwait（a）;s2;signal（c）;signal（d）end;
S3beginwait（b）;s3;signal（e）end;
S4beginwait（c）;s4;signal（f）;end;
S5beginwait（d）;wait（e）;s5;signal（g）;end;
S6beginwait（f）;wait（g）;s6；end;
Parend
End
思考：
是否可以用一个信号量代替a,b两个信号量,，程序改为:
S1begins1;signal（a）end;
S2beginwait（a）;s2;――――
S3beginwait（a）;s3;――――
例3：
读者——写者问题
多个读者进程可以同时读文件,但排斥写者进程；写者进程写文件时排斥其它任何进程
同步要求：
①读者可以同时读，不需互斥
②读者与写者之间互斥
③写者与读者，写者互斥
信号量设计：
·:
互斥信号量wmutex，用于：
①第一个读者与写者互斥②写者与其它读写者互斥
对wmutex的操作：
·第一个读者进入临区时，用wait（wmutex）测试并排斥其它写者。
·最后一个读者退出临区时，用signal（wmutex）释放资源
·设置读者计数器readcount，初值为0，用于对读者序号的统计，以确定“第一”和“最后一个”在临区的读者。
·设置信号量rmutex，以使读者互斥使用计数器（注意：
不是互斥使用要读的文件）
利用记录型信号量解决读者-写者问题程序：
varrmutex,wmutex;semaphone:
=1,1;
readcount:
integer:
=0;
begin
parbegin
Reader:
Begin
Repeat
Wait（rmutex）;——互斥使用readcount计数器
Ifreadcount=othenwait（wmutex）;——第一个读者负责测试可否进入临区
readcount:
=readcount+1;
Signal（rmutex）;——释放计数器
执行读操作
……
wait（rmutex）;
readcount:
=readcount-1;
ifreadcount=0thensignal（wmutex）;―――――最后一个出临区的读者负责释放资源。
Signal（rmutex）;
Untilfalse;
End
Writer:
写者进程只需用wmutex信号量互斥使用临区
Begin
Repeat
Wait（wmutxe）;
Performwriteoperation;——临界区
Signal（wmutex）;
Untilfalse;
End
Parend
End
思考题：
（1）在读者进程中对rmutex的互斥操作做了两次，是否可以改为一次，结果有何不同。
信号量应用小结：
1．互斥信号的初值为同类可用资源的个数。
例定义时置，mutex:
=1表示有1个资源
若varmutex:
semaphore:
=5表示有5个同类资源，最多允许5个进程同时使用
2．对互斥信号量的操作，在同一程序中测试（wait）和释放（signal）：
wait（mutex）
临界区
signal（mutex）
3．资源信号量（用作同步），初值为同类
升级会员 