【2】章2进程控制与同步-3课件

上次问题描述OS进行进程创建、终止、阻塞、挂起等的过程；什么是同步；使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性控制同步的关键在哪里。不被打断的进行标志值的判断和修改同步原则空闲让进，忙则等待，有限等待，让权等待7/19/20231山东农业大学计算机系第2章进程管理2.1进程基本概念2.2进程控制

2.3进程同步（信号量） 2.4经典进程同步问题2.5进程通信2.6线程7/19/20232山东农业大学计算机系2.信号量机制荷兰科学家Dijkstra(狄克斯特拉)提出的一种卓有成效的进程同步机制。Edsger

Wybe

Dijkstra

(1930.5~2002.8)7/19/20233山东农业大学计算机系1）

整型信号量信号量定义为一个整型量；根据初始情况赋相应的值；仅能通过两个原子操作来访问。P操作wait(S): WhileS<=0dono-op;S:=S-1;V操作signal(S): S:=S+1;对比软件解决法7/19/20234山东农业大学计算机系例：对临界资源的互斥使用程序1:wait(s)使用Rsignal(s)程序2:wait(s)使用Rsignal(s)S=1给共享变量R设置一个信号量swait(){WhileS<=0dono-op;S:=S-1;}signal(){s=s+1}S=0S=1S=0S=17/19/20235山东农业大学计算机系2）记录型信号量整型信号量符合“有限等待”原则signal释放资源后，当CPU被分配给等待进程后，等待进程仍可继续执行，可以符合“有限等待”。但整型信号量不符合“让权等待”原则整型信号量的wait操作，当s≤0时，当前进程会占着CPU不断测试；信号量原语不能被打断，这个占有CPU的进程会一直不断的占据CPU循环下去，陷入忙等。7/19/20236山东农业大学计算机系改进：条件不符时应能够主动放弃CPU新问题：放弃CPU的进程进入阻塞队列：因等待某信号量而放弃CPU的等待进程会有“若干”个，需将它们组织管理起来，并在合适的时候唤醒。7/19/20237山东农业大学计算机系*信号量结构信息发生变化不仅要有值的处理，还有队列的处理。此时形成记录型数据结构，包括两部分：整型变量value(代表资源数目)进程链表L(链接所有等待进程)：代码描述：typeSemaphore=record value：integer; L：listofPCB;end;

操作：S.Value，S.L7/19/20238山东农业大学计算机系指针●数值（-3）●PCB1●PCB20PCB3记录型信号量Value>0，表示当前可用资源的数量；Value≤0，其绝对值表示等待使用该资源的进程数，即在该信号量队列上排队的PCB的个数。7/19/20239山东农业大学计算机系*P、V操作也有所变化不仅修改资源数，还要处理进程的阻塞、唤醒等操作。先修改资源数，再判断处理。P操作wait():

S.value=S.value-1;ifS.value<0thenblock(S,L)V操作signal()：

S.value=S.value+1;ifS.value<=0thenwakeup(S,L)7/19/202310山东农业大学计算机系定义信号量semaphore代表可用资源实体的数量。又叫信号灯。当≥0，代表可供并发进程使用的资源实体数当<0，表示正在等待使用该资源的进程数。建立一个信号量必须经过说明，包括信号量所代表的意义赋初值建立相应的数据结构，以便指向等待使用临界区的进程。除初值外，信号量的值仅能由标准原子操作P、V操作来改变。

PV操作是荷兰语通过和释放的意思。7/19/202311山东农业大学计算机系3）信号量的基本应用实现进程互斥实现进程间的前趋关系（有序）7/19/202312山东农业大学计算机系实现多个进程互斥设置一互斥信号量mutex，初值为1。进程i：V(mutex);criticalsection操作共享资源RremaindersectionP(mutex);

S.value=S.value-1;ifS.value<0thenblock(S,L)

S.value=S.value+1;ifS.value<=0thenwakeup(S,L)7/19/202313山东农业大学计算机系互斥信号量注意点：互斥信号量mutex初值为1；每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语（在同一进程中），不能次序错误、重复或遗漏：遗漏P原语则不能保证互斥访问遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；7/19/202314山东农业大学计算机系实现有序前趋关系:

并发执行的进程P1和P2中，分别有代码C1和C2，要求C1要在C2开始前完成；为每对前趋关系设置一个同步信号量S12，并赋初值为0。则只有V操作所在进程获得cpu时能运行P1：C1；signal(S)；P2：wait(S)；C2；7/19/202315山东农业大学计算机系控制同步顺序的注意点信号量值为0的点是限制的关键所在；成对使用P和V原语（在有先后关系的两个进程中），不能次序错误、重复或遗漏，否则同步顺序出错。7/19/202316山东农业大学计算机系一个简单同步举例例：设有一供者和一用者，如何用信号量来控制二者对缓冲区的同步使用。注意思考： 信号量是针对资源设置的，分析本问题各对象关心的资源，想想需要设置几个信号量，初值又如何？缓冲区供者用者7/19/202317山东农业大学计算机系V(s2);将数据送入缓冲区；…P(s1);V(s1);从缓冲区取数来用；P(s2);供者：用者：………注意：需要两个信号量s1表示空缓冲的个数，初值为1；s2表示满缓冲的个数，初值为0；初值决定了执行的初始状态，值得思考7/19/202318山东农业大学计算机系练习：1）如何利用互斥信号量解决上次课两个加法进程对共享变量操作的问题？A：R1=x；R1=R1+1；x=R1B：R2=x；R2=R2+1；x=R2Var

mutex:semaphore:=1;x:integer;processA:beginrepeat

P(mutex); R1=x; R1=R1+1; x=R1;

V(mutex);untilfalse;7/19/202319山东农业大学计算机系2）民航售票系统问题n个售票处。每个售票处通过终端访问系统的公用数据区假定公用数据区中分别用Ri表示某时间i次航班的现存票数。Pi表示某售票处的处理进程，试用信号量实现进程间的互斥关系。7/19/202320山东农业大学计算机系Vars:semaphore:=1;begin

parbeginprocessPi:begin end

parendendrepeatP(s);按旅客定票要求找到RiIFRi

>=1then

Ri

=Ri

-1;

输出一张票；EndifV(s);输出“票已售完”；untilfalse;7/19/202321山东农业大学计算机系3）用信号量实现司机和售票员的同步。司机：RepeatP(s1);

离站；行车；到站；

V(s2);Untilfalse;售票员：Repeat

关车门；

V(s1);

售票；

P(s2);

开车门；乘客上下车；Untilfalse;初值如何？同步信号量成对出现在不同进程中7/19/202322山东农业大学计算机系4）AND型信号量出现原因：一些应用往往需要两个或多个共享资源，而不是前述的一个资源。进程同时要求的共享资源越多，发生死锁可能性越大。解决思想： 一次性分配给进程所需资源，用完一起释放。Wait操作时对它所有需要的资源都要判断，有AND条件，故称“AND同步”、“同时wait”。ProcessA：

wait(Dmutex);

wait(Emutex);ProcessB：

wait(Emutex);

wait(Dmutex);7/19/202323山东农业大学计算机系Swait(S1,S2,…,Sn)if（S1>=1and…andSn>=1）thenfori:=1tondoSi:=Si-1;

endforelse

将进程阻塞在第一个不能满足资源信号量的队列中。

endifSsignal(S1,S2,…,Sn)fori:=1tondoSi:=Si+1;

唤醒所以与si相关的阻塞进程

endfor

7/19/202324山东农业大学计算机系5）信号量集引入原因：每次只能获得或释放一个单位的资源，低效；某些时候资源分配有下限的限制；修改：在大于可分配设置的下界值t前提下，每次可分配d个。7/19/202325山东农业大学计算机系Swait(S1,t1,d1,…,Sn,tn,dn)ifS1>=t1and…andSn>=tnthenfori:=1tondoSi:=Si-di;

endforelse…

endifSsignal(S1,d1,…,Sn,dn)fori:=1tondoSi:=Si+di;….

endforAND信号量机制上加以扩充，每种资源参数有三：

S为信号量（现有值）；

t为下限值（现有不能少于该条件）；d为需求值；7/19/202326山东农业大学计算机系信号量集的一个特例只有一个信号量S的几种特殊情况：

Swait(S,d,d)，，允许每次申请d个资源，若现有资源数少于d，不予分配。

Swait(S,1,1)，蜕化为一般的记录型信号量，一次申请一个，至多分配一个(S>1时可计数，或S=1时可控制互斥)。

Swait(S,1,0)，当S>=1时，允许多个进程进入某特定区，当S变为0后，阻止任何进程进入特定区，相当于可控开关。并不对S资源的数量产生影响。7/19/202327山东农业大学计算机系*体验Swait(S,1,0)的开关作用(选看)给车库位数定义资源信号量S=5通行证p=0车库入口进程P_in：Repeat

Swait(S,1,0)

发通行证 signal（p）Untilfalse车辆进程P_car：repeat wait（p）

wait(S)

停车

…shopping

取车

signal（S）Untilfalse需求为0，可见不改变车库资源数，主要进行判断7/19/202328山东农业大学计算机系*信号量题目做题一般方法：分析问题，找出同步、互斥关系根据资源设置信号量变量写出代码过程，并注意P、V操作的位置检查代码，模拟机器运行，体验信号量的变化和程序运行过程是否正确。7/19/202329山东农业大学计算机系名词解释同步、临界资源、临界区、让权等待默写记录型信号量的wait，signal原语。它与整型信号量的区别是什么？AND信号量机制可解决什么问题？用基本记录型信号量解决如下同步关系，并回答问题：四人有什么同步关系，应设置几个信号量，初值为多少？程序虽然无序请求，但在信号量控制下，是在合理的同步运行，请给出所有错误的无序请求下信号量起控制作用的过程分析。作业一空盘放一水果父放梨，母放橘儿取梨，