第二章进程管理3.docx
- 文档编号:16533920
- 上传时间:2023-07-14
- 格式:DOCX
- 页数:46
- 大小:139.67KB
第二章进程管理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.资源信号量(用作同步),初值为同类
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 进程 管理