OS02进程同步2014-2015-2

1、操作系统操作系统Operating Systems2.4 进进 程程 同同 步步 进程同步的基本概念进程同步的基本概念 两种形式的制约关系两种形式的制约关系 间接相互制约关系。间接相互制约关系。p间接相互制约源于资源共享间接相互制约源于资源共享共享打印机共享打印机 直接相互制约关系。直接相互制约关系。 p主要源于进程间的合作。主要源于进程间的合作。进程的同步与互斥进程的同步与互斥 进程的两大关系：进程的两大关系： 互斥（间接制约关系）：互斥（间接制约关系）：各进程竞争使用同一临界资源各进程竞争使用同一临界资源p临界资源：临界资源：一段时间内只允许一个进程使用的系统资源一段时间内只允许一个进程使

2、用的系统资源 进程同步（直接制约关系）：进程同步（直接制约关系）：根据一定的根据一定的时序关系时序关系合作完成一项任务合作完成一项任务为完成共同任务的并发进程基于为完成共同任务的并发进程基于某个条件某个条件来协调其活来协调其活动动讨论讨论 进程之间存在哪几种制约关系？各是什么原因引起的？以进程之间存在哪几种制约关系？各是什么原因引起的？以下活动各属于哪种制约关系？下活动各属于哪种制约关系？（1）若干学生去图书馆借书。）若干学生去图书馆借书。（2）两队进行篮球比赛。）两队进行篮球比赛。（3）流水线生产的各道工序。）流水线生产的各道工序。（4）商品生产和社会消费。）商品生产和社会消费。生产者生产者

3、-消费者问题消费者问题 生产者生产者-消费者消费者(producer-consumer)问题是一个著名的问题是一个著名的进程同步问题。进程同步问题。123 . nPC生产者生产者-消费者问题消费者问题producer: repeat produce an item in nextp; while counter=n do no-op; bufferin:=nextp; in:=(in+1) mod n; counter:=counter+1; until falseconsumer: repeat while counter=0 do no-op; nextc:=bufferout; out:

4、=(out+1) mod n; counter:=counter-1; consumer the item in nextc; until false; 生产者生产者-消费者问题消费者问题counter:=counter+1： register1:=counter；register1:=register1+1；counter:=register1； counter:=counter-1：register2:=counter；register2:=register2-1；counter:=register2； 生产者生产者-消费者问题消费者问题生产者进程生产者进程:/ counter初始值初始值

5、=5 register1:=counter； register1:=register1+1； counter:=register1； 消费者进程消费者进程 register2:=counter; register2:=register2-1 ; counter:=register2； ;程序的执行已经失去了再现性。程序的执行已经失去了再现性。解决此问题的关键是应把变量解决此问题的关键是应把变量counter作为临界资源处理，作为临界资源处理，令生产者进程和消费者进程互斥地访问变量令生产者进程和消费者进程互斥地访问变量counter。5 5register1register15 5registe

6、r2register24 46 65 5counter4 46 6临界区临界区 把在每个进程中访问把在每个进程中访问临界资源临界资源的那段代码称为临界区的那段代码称为临界区 若能保证诸进程互斥地进入自己的临界区，便可实现诸进若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。程对临界资源的互斥访问。 repeatentry section（进入区）（进入区）critical section；exit section（退出区）（退出区）remainder section； until false； 临界区临界区同步机制应遵循的规则同步机制应遵循的规则1. 空闲让进。空闲让进

7、。2. 忙则等待。忙则等待。 3. 有限等待。有限等待。 4. 让权等待。让权等待。 互斥：解决方法互斥：解决方法 软件解决软件解决 （参见教参附录（参见教参附录A） 由并发执行的进程承担这个责任由并发执行的进程承担这个责任 不需要程序设计语言或操作系统提供任何支持不需要程序设计语言或操作系统提供任何支持 增加开销增加开销 硬件支持硬件支持 很难成为一种通用的解决方案很难成为一种通用的解决方案 在操作系统或程序设计语言中提供某种级别的支持在操作系统或程序设计语言中提供某种级别的支持 信号量、管程信号量、管程2.4.2 硬件同步机制硬件同步机制 在单处理机机器中，并发进程只能交替执行。在单处理机

8、机器中，并发进程只能交替执行。 一个进程将一直运行，直到它调用一个系统服务或被中断一个进程将一直运行，直到它调用一个系统服务或被中断 关中断：保证互斥关中断：保证互斥 repeatentry section（进入区：关中断）（进入区：关中断）critical section；exit section（退出区：打开中断）（退出区：打开中断）remainder section； until false； 关中断关中断 关中断关中断缺点缺点 滥用关中断权利可能导致严重后果滥用关中断权利可能导致严重后果 影响系统效率，限制处理机交叉执行程序的能力影响系统效率，限制处理机交叉执行程序的能力 不适合多处理

9、机系统不适合多处理机系统利用利用Test and Set指令指令 boolean TS (boolean *lock) Boolean old; old = * lock; *lock = TRUE; return old； 原语原语do . while TS(&lock); 临界区临界区 lock :=false; remainder section； 利用对利用对 原语，原语，void SWAP ( boolean *a, boolean *b ) boolean temp; temp = *a; *a = *b; *b = temp;利用对利用对do key = TRUE; do SWA

10、P(&lock, &key); while(key!=FALSE); 临界区操作；临界区操作； lock:=FALSE;while(TRUE)硬件指令方法缺点硬件指令方法缺点2.4.3信号量机制信号量机制1 整型信号量整型信号量 定义为一个用于表示定义为一个用于表示资源数资源数目的目的整型整型量量S 仅能通过两个标准的仅能通过两个标准的原子操作原子操作P操作操作(wait)和和V操作操作(signal)来访问。来访问。wait(S)： while Svalue-； if (S-valuelist)；每次每次wait操作，意味着进操作，意味着进程请求一个单位的该类资程请求一个单位的该类资源，源，

11、signal(semaphore *S) S-value+； if S-valuelist)； 每次每次signal操作，表示执操作，表示执行进程释放一个单位资源行进程释放一个单位资源原子操作原子操作记录型信号量记录型信号量 若信号量若信号量s-value为正值为正值 则则s-value所代表的实际还可以使用的物理资源数所代表的实际还可以使用的物理资源数. 若信号量若信号量s-value为负值：为负值： 则其绝对值等于登记排列在该信号量则其绝对值等于登记排列在该信号量s队列之中等待的队列之中等待的进程个数进程个数 s-value的初值为的初值为1时：时： 表示只允许一个进程访问临界资源，此时的

12、信号量转化表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。为互斥信号量，用于进程互斥。信号量的值信号量的值 value 信号量队列指针信号量队列指针AA issues semWait, later times outB issues semWaitD issues semSignals = 1Ready queueProcessorD BC12Fig ure 5.5 Example of Semaphore MechanismBlocked queueDD issues semSignal, later times outs = 0Ready queueProces

13、sorA CB4Blocked queueBs = 0Ready queueProcessorC DABlocked queueC issues semWait5Cs = 0Ready queueProcessorB ADBlocked queue3Ds = 1Ready queueProcessorA CBlocked queueBD issues semSignal7Ds = 2Ready queueProcessorCBlocked queueA BD issues semSignal6Ds = 3Ready queueProcessorBlocked queueC A B A and

14、B run and are blocked on the semaphore 上述的进程互斥问题，是针对各进程之间只共享一个临界上述的进程互斥问题，是针对各进程之间只共享一个临界资源而言的。资源而言的。process A:process B:wait(Dmutex)；wait(Emutex)；wait(Emutex)；wait(Dmutex)； 若进程若进程A和和B按下述次序交替执行按下述次序交替执行wait操作：操作：process A: wait(Dmutex)； 于是于是Dmutex=0process B: wait(Emutex)； 于是于是Emutex=0process A: wai

15、t(Emutex)； 于是于是Emutex=-1 A阻塞阻塞process B: wait(Dmutex)； 于是于是Dmutex=-1 B阻塞阻塞 3 AND型信号量型信号量 采取原子操作方式：采取原子操作方式： 要么把它所请求的资源全部分配到进程要么把它所请求的资源全部分配到进程 要么一个也不分配。要么一个也不分配。 可避免上述死锁情况的发生。可避免上述死锁情况的发生。 在在wait操作中，增加了一个操作中，增加了一个“AND”条件条件 AND同步，或称为同时同步，或称为同时wait操作操作 Swait(Simultaneous wait)Swait(S1，S2，Sn)if S1=1 an

16、d and Sn=1 thenfor i:=1 to n do Si:=Si-1；endforelse 当发现第一个当发现第一个 Sivalue-； if S-valuelist)； S0 P2NULL-1实现前趋关系实现前趋关系 设有两并发进程设有两并发进程P1P1和和P2P2。 P1P1中有语句中有语句S1S1； P2P2中有语句中有语句S2S2。semaphore S = 0; P1()P1() S1S1； signal(S)signal(S) S1S2P2()P2() wait(S)wait(S)；S2S2； signal(semaphore S) S-value+； if S-val

17、uelist)； S0 P2NULL-1用信号量机制实现进程同步用信号量机制实现进程同步 P1,P2,P3为一组合作进程，其进程流图如下所示，试用为一组合作进程，其进程流图如下所示，试用信号量实现这三个进程的同步。信号量实现这三个进程的同步。 设以下同步信号量设以下同步信号量 ： S1表示表示P1发给发给P2的能开始执行的消息，的能开始执行的消息， 其初值为其初值为0； S2表示表示P1发给发给P3的能开始执行消息，的能开始执行消息， 其初值为其初值为0。P1P3P2process P1begin V(S1); V(S2);endprocess P3Begin P(S2); end Proce

18、ss P2begin P(S1); endP1P3P2 前趋图举例前趋图举例 Semaphore a,b,c,d,e,f,g;a.value=b.value=c.value=0；d.value=e.value=f.value=0;P1() S1; signal(a); signal(b); ;P2()wait(a); S2; signal(c); signal(d);P3()wait(b); S3; signal(e); P4()wait(c); S4; signal(f);P5()wait(d); S5; signal(g);P6()wait(e); wait(f); wait(g); S6

19、;abcdgef用信号量解题的关键用信号量解题的关键步骤：步骤：1.信号量的设置；信号量的设置；2. 给信号量赋初值；给信号量赋初值；3. P、V操作安排的位置（其中，操作安排的位置（其中，P的顺序不能颠倒，的顺序不能颠倒，V的顺的顺序任意）序任意）信号量讨论信号量讨论11、设有、设有3个进程共享同一程序段个进程共享同一程序段,若最多允许有若最多允许有2个进程进入个进程进入程序段程序段,则所采用的信号量的初值为则所采用的信号量的初值为( )。2 2P1wait(mutex);程序段程序段；signal(mutex);P2wait(mutex);程序段；程序段；signal(mutex);P3w

20、ait(mutex);程序段；程序段；signal(mutex);mutex21 P3NULL0 -1信号量讨论信号量讨论22、有、有3个进程共享同一程序段个进程共享同一程序段,而每次最多允许两个进程进而每次最多允许两个进程进入该程序段入该程序段,若用若用P、V操作作同步机制操作作同步机制,则记录型信号量则记录型信号量S的取值范围为的取值范围为()。 3、若记录型信号量、若记录型信号量S的初值为的初值为2,当前值为当前值为-1,则表示有则表示有( )等待进程。等待进程。 A.0个个B.1个个C.2个个D.3个个2,1,0,-1(2,1,0,-1(或或2,-1)2,-1)B信号量讨论信号量讨论3

21、4、购物问题。某超级市场、购物问题。某超级市场,可容纳可容纳100人同时购物人同时购物,入口处备有入口处备有篮子篮子,每个购物者可持一个篮子入内购物每个购物者可持一个篮子入内购物,出口处结帐出口处结帐,并归还并归还篮子篮子(出口出口/入口仅容纳一人通过入口仅容纳一人通过),请用请用P、V操作完成购物同操作完成购物同步算法。步算法。 答答:semaphore S,mutex1,mutex2;S.value=100; /可容纳可容纳100人同时购物人同时购物,mutex1.value=1;/入口仅容纳一人通过入口仅容纳一人通过mutex2.value=1; /出口仅容纳一人通过出口仅容纳一人通过

22、cobeginPi () /是否到是否到100人？人？P(mutex1);进入口处进入口处,取一只篮子取一只篮子;V(mutex1);选购商品选购商品;P(mutex2);结帐结帐,并归还篮子并归还篮子;V(mutex2);V(S); coend;P(S); 2.4.5 2.4.5 管程机制管程机制 管程引入管程引入 把分散在各进程中的临界区集中起来进行管理把分散在各进程中的临界区集中起来进行管理 ； 防止进程有意或无意的违法同步操作防止进程有意或无意的违法同步操作 可利用可利用共享数据结构共享数据结构抽象地表示共享资源，把对共享数据抽象地表示共享资源，把对共享数据结构实施的操作定义为结构实施

23、的操作定义为一组过程一组过程 进程对共享资源的操作，都是通过这组过程对共享数进程对共享资源的操作，都是通过这组过程对共享数据结构的操作来实现的据结构的操作来实现的 确保每次仅有一个进程使用共享资源确保每次仅有一个进程使用共享资源管程的定义管程的定义 一个管程定义了一个一个管程定义了一个数据结构数据结构和能为并发进程所执行和能为并发进程所执行( (在在该数据结构上该数据结构上) )的的一组操作一组操作，这组操作能，这组操作能同步同步进程和改变进程和改变管程中的数据。管程中的数据。 管程的组成管程的组成1.1.名称；名称；2.2.局部于管程内部的共享数据结构说明；局部于管程内部的共享数据结构说明；

24、3.3.对该数据结构进行操作的一组过程；对该数据结构进行操作的一组过程；4.4.对局部于管程内部的共享数据设置初始值语句。对局部于管程内部的共享数据设置初始值语句。管程的示意图管程的示意图 condition c1condition c1wait(c1)wait(c1)condition condition c cn n wait( wait(c cn n) ) 局部数据局部数据 条件变量条件变量 过程过程/ /函数函数1 1 过程过程/ /函数函数k k出口出口 初始化代码初始化代码入口入口管程管程等待调用过程等待调用过程的进程队列的进程队列管程等待区管程等待区入口等待队列入口等待队列 管程

25、是管程是互斥互斥进入的进入的 当一个进程试图进入一个巳被占用的管程时，它应当当一个进程试图进入一个巳被占用的管程时，它应当在管程的入口处等待在管程的入口处等待 在管程的入口处应当有一个进程在管程的入口处应当有一个进程等待队列等待队列（入口等待（入口等待队列）。队列）。管程的条件变量管程的条件变量 条件变量条件变量 出现在管程内的一种数据结构出现在管程内的一种数据结构Condition Condition x x，y;y; 只有在管程中才能被访问只有在管程中才能被访问 它对管程内的所有过程是全局的它对管程内的所有过程是全局的 只能通过两个原语操作只能通过两个原语操作waitwait和和signa

26、lsignal来控制它。来控制它。cwaitcwait 正在调用管程的进程因正在调用管程的进程因x x条件需要被阻塞或挂起时调用条件需要被阻塞或挂起时调用cwait(x)cwait(x)： 将自己插入到将自己插入到x x条件的等待队列上并释放管程，条件的等待队列上并释放管程， 直到直到x x条件变化。条件变化。 此时其它进程可以使用该管程。此时其它进程可以使用该管程。csignalcsignal 正在调用管程的进程发现正在调用管程的进程发现x x条件发生了变化，条件发生了变化，则调用则调用csignal(x)csignal(x)重新启动一个因重新启动一个因x x条件而阻塞或挂起的进程。条件而阻

27、塞或挂起的进程。 这与信号量机制中的这与信号量机制中的signalsignal操作不同。操作不同。管程中的多个进程进入管程中的多个进程进入 若进程若进程Q Q因因x x条件阻塞，而正在调用管程的进程条件阻塞，而正在调用管程的进程P P执行执行 csignal(x)csignal(x)操作操作后，后，Q Q被重新启动，可采用下述方式之一被重新启动，可采用下述方式之一进行处理：进行处理： P P等待，直至等待，直至Q Q离开管程或等待另一条件。离开管程或等待另一条件。 Q Q等待，直至等待，直至P P离开管程或等待另一离开管程或等待另一条件。条件。 规定唤醒为管程中最后一个可执行的操作规定唤醒为管

28、程中最后一个可执行的操作(P离开管程离开管程,Q被唤醒被唤醒)；进程进程Q进程进程Pcwait(x)Csignal(x)管程主要特性管程主要特性 模块化模块化 基本程序单位，可以单独编译；基本程序单位，可以单独编译； 抽象数据类型抽象数据类型 包含数据和操作；包含数据和操作； 信息隐蔽信息隐蔽 从外部看不到内部信息；从外部看不到内部信息； 每次只允许一个进程进入管程，执行管程内的过程每次只允许一个进程进入管程，执行管程内的过程 实现互斥实现互斥管程和进程不同管程和进程不同 管程定义的是公共数据结构；管程定义的是公共数据结构； 管程管程把共享变量上的同步操作集中起来把共享变量上的同步操作集中起来

29、 进程进程通过调用管程中的过程对共享数据结构通过调用管程中的过程对共享数据结构实行操作实行操作 管程的设置则是解决共享资源的互斥使用问题管程的设置则是解决共享资源的互斥使用问题 管程管程不能与其调用者并发不能与其调用者并发 管程管程是操作系统中的一个资源管理模块，供进程调用。是操作系统中的一个资源管理模块，供进程调用。 进程具有动态性，由进程具有动态性，由“创建创建”而诞生，由而诞生，由“撤销撤销”而而消亡消亡生产者生产者消费者问题消费者问题 生产者生产者消费者问题消费者问题 生产者生产者消费者问题是相互合作的进程关系的一种抽象消费者问题是相互合作的进程关系的一种抽象 制约关系：制约关系： 只

30、要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未满，生产者便可将消息送入缓冲池； 只要缓冲池未空，消费者便可从缓冲池中取走一个消息只要缓冲池未空，消费者便可从缓冲池中取走一个消息 互斥互斥123 . nPC利用管程解决生产者利用管程解决生产者-消费者问题消费者问题 Monitor ProducerConsumer item bufferN; int in, out; /缓冲区指针缓冲区指针 int count; /缓冲中数据项个数缓冲中数据项个数 condition notfull ,notempty; /条件变量条件变量 public : int=0;out=0;count=0 /缓冲区初始化缓冲区初始化 void put (item x) if (count = N) cwait(notfull) ; /缓冲区满缓冲区满 bufferin : = x ; in = (in+1) % N ; count = count + 1 ; csignal(not