中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall 第五讲 进程同步和通信（part II） 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall.

Presentation on theme: "中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall 第五讲 进程同步和通信（part II） 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall."— Presentation transcript:

1 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall
第五讲 进程同步和通信（part II） 中国科学技术大学计算机系 陈香兰 2013Fall

2 管程 进程间通信 内容提要 进程同步问题的来由和进程同步的主要任务 临界资源和临界区 2任务的进程互斥问题的解决方案
信号量Semaphores 死锁和饿死现象 经典同步问题 管程 进程间通信

3 管程 进程间通信 内容提要 进程同步问题的来由和进程同步的主要任务 临界资源和临界区 2任务的进程互斥问题的解决方案
信号量Semaphores 死锁和饿死现象 经典同步问题 管程 进程间通信

4 信号量机制 Semaphore Reading 计算机操作系统，汤子瀛，3.2节
Operating System Concepts，7th edition，section6.5 P200

5 信号量机制 整型信号量 记录型信号量 信号量集

6 整型信号量 The real situation may be more complex
Semaphore S – integer variable Can only be accessed via two indivisible (atomic) operations: Proberen & Verhogen (Dutch) P(S): while S 0 do no-op; S--; V(S): S++; P：又称为wait操作 V：又称为signal操作

7 Counting & binary semaphore
Counting semaphore (资源信号量） Used to control access to a given resource consisting of only a finite number 0,…,n Binary semaphore (二进制信号量或互斥信号量，mutex) 0 or 1 Used to control access to the CS

8 Generally using counting semaphore
Shared semaphore semaphore resources; /* initially resources = n */ Pi: do { P( resources ); Critical section; V( resources ); Remainder section; } while(1);

9 Generally using binary semaphore
Shared semaphore semaphore mutex; /* initially mutex = 1 */ Pi: //利用信号量实现互斥 do { P( mutex ); Critical section; V( mutex ); Remainder section; } while(1); What is the different between these two?

10 Another common example
E.g.: Pi has code segment A Pj has code segment B A must be executed before B Solution Using semaphore semaphore finish; // Initialize finish = 0 利用信号量进行同步； 可以描述前驱关系 Pi Pj A V(flag) P(flag) B

11 同步举例（前驱举例） semaphore a,b,c,d,e,f,g = 0,0,0,0,0,0,0 begin parbegin begin S1;signal(a);signal(b);end; begin wait(a);S2;signal(c);signal(d);end; begin wait(b);S3;signal(g);end; begin wait(c);S4;signal(e);end; begin wait(d);S5;signal(f);end; begin wait(e);wait(f);wait(g);S6;end; parend end S1 S2 S3 S4 S5 S6 a b c d g e f

12 忙等问题 Busy-Waiting Solution:
So far, all solutions have this common problem Entry section, always loop if … Wastes CPU cycle Still in ready state and participate in scheduling These kind of semaphore is also called a spinlock Spinlock, is useful in some cases Solution: Instead of busy-waiting (loop), it just blocks itself, when must wait

13 Record semaphore记录型信号量
Define semaphore as a record typedef struct { int value; struct process *L; //等待队列 } semaphore; Use two system call: block The state of the process is switched to the waiting state, and then the control  CPU scheduler; wakeup Changes the process from the waiting state to the ready state, and places it to ready queue

14 汤子瀛，2版 & 汤小丹，3版 Type semaphore＝record value: integer; L: List of process; end; procedure signal(S) var S: semaphore begin S.value:=S.value+1; if(S.value≤0) then wakeup(S.L); end procedure wait(S) var S: semaphore; begin S.value:=S.value-1; if S.value<0 then block(S.L); end

15 分析S.value 对于wait操作， 开始时： 结束时： 对于signal操作， 开始时，同wait结束时
value<0，说明有等待者，此时L上有等待进程；此时，value的绝对值表示等待进程的个数 对于signal操作， 开始时，同wait结束时 value ≥0，说明没有等待者，不必唤醒，只需要加1 value<0，说明有等待者；加1，并唤醒1个进程

16 Operating system concepts, 7th
P(S) S.value--; If (S.value<0){ add the caller to S.L; block(); } S.value >0: number of remaining resources S.value <0: number of waiting processes V(S) S.value++; If (S.value<=0){ remove a process P from S.L; wakeup(P); } S.value P V After “--” After “++” >0 >=0 GOT! L=NULL =0 <0 Failed! <=0 L!=NULL

17 Implementation of semaphore
临界区问题: No two processes can execute P/V operation on the same semaphore at the same time Two ways Uniprocessor Disable interrupt during P/V Multiprocessor Software solutions Hardware instructions

18 Misuse of semaphore E.g.: Process P0, & P1
Semaphore S & Q, both initially = 1; P0 P1 P(S) P(Q) . V(S) V(Q) block block

19 AND型信号量 AND型信号量的基本思路： 即资源分配具有原子性，要么全分配；要么一个都不分配 Swait和Ssignal操作
将进程在整个运行过程中需要的所有资源，一次性全部的分配该进程，待进程使用完后再一起释放。 即资源分配具有原子性，要么全分配；要么一个都不分配 Swait和Ssignal操作

20 Swait(S1,S2,…,Sn) if(S1≥1 and S2≥1 and … and Sn≥1 ) then for i:=1 to n do Si:=Si－1; endfor else 将进程加入第一个条件不满足的Si的等待队列上，并且修改程序指针到Swait操作的开始部分 endif Ssignal(S1,S2,…,Sn) for i:=1 to n do Si:=Si＋1; 若Si有等待进程，则唤醒 endfor

21 信号量集 目标：更一般化 例如，一次申请多个单位的资源； 又如，当资源数低于某一下限值时，就不予分配 Swait(S1, t1, d1,S2, t2, d2,…,Sn,tn,dn) if(S1≥t1 and S2≥t2 and … and Sn≥ tn )then for i:=1 to n do Si:=Si－di; endfor else 将进程加入第一个条件不满足的Si的等待队列上，并且修改程序指针到Swait操作的开始部分 endif t: 需求值 d: 下限

22 Ssignal(S1, d1,S2, d2,…,Sn,dn) for i:=1 to n do Si:=Si＋di; 若Si有等待进程，则唤醒 endfor
信号量集的几种特殊情况： Swait(S,d,d)：多单位 Swait(S,1,1)：一般记录型信号量 Swait(S,1,0)：s≥1时，允许多个进入临界区；s＝0后，阻止一切

23 内容提要 进程同步问题的来由和进程同步的主要任务 临界资源和临界区 2任务的进程互斥问题的解决方案 信号量Semaphores 死锁和饿死现象 经典同步问题 管程 进程间通信

24 Deadlock & starvation 死锁和饿死现象
Two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes Starvation 饿死 Indefinite blocking A process may never be removed from the semaphore queue in which it is blocked If LIFO queue (stack mode)

25 管程 进程间通信 内容提要 进程同步问题的来由和进程同步的主要任务 临界资源和临界区 2任务的进程互斥问题的解决方案
信号量Semaphores 死锁和饿死现象 经典同步问题 管程 进程间通信

26 Classical Problems of Synchronization
Bounded-Buffer Problem 生产者-消费者问题 Readers and Writers Problem 读者与写者问题 Dining-Philosophers Problem 哲学家就餐问题

27 Bounded-buffer problem
Producer-Consumer problem Producer process produces information, & that is consumed by a consumer process Use buffer to share information The access to buffer must be synchronized Bounded-buffer Fixed buffer size Both need to wait in some conditions

28 使用记录型信号量解决PC问题 Shared semaphore Other shared variable
semaphore full, empty, mutex; Initially: full = 0; /* counting full items */ empty = N; /* counting empty items */ mutex = 1; /* binary semaphore, control access to CS */ Other shared variable item buf[BufSize]; int in=0; int out = 0;

29 P&C Producer Consumer do{ /* * produce an item * in nextp */ P(empty);
P(mutex); /* add nextp to buffer*/ buf[in]=nextp; in=(in+1) mod n; V(mutex); V(full); }while(1); P(full); /* remove a item to nextc*/ nextc=buf[out]; out=(out+1) mod n; V(empty); * consume the item * in nextc

30 Readers-Writers problem读者－写者问题
A data object can be shared among several concurrent process/threads. Readers读者: those only want to read the data object Writers写者: others want to update (r/w) the data object 读者与写者之间的冲突 R||R W/R W/W

31 Readers-Writers problem (cont’d)
写者对共享数据具有独占性 读者-写者问题的变形: The first R/W problem Reader has the higher priority Writer may starve The second R/W problem Writer has the higher priority Reader may starve

32 R/W problem: a solution
Shared variable int readcount = 0; Shared semaphore semaphore Wmutex=1; semaphore Rmutex = 1; Writer do{ P(Wmutex); /* perform write operation */ V(Wmute); }while(1); Reader do{ P(Rmutex); if (readcount==0) P(Wmutex); readcount++; V(Rmutex); /* perform read operation */ readcount--; V(Wmutex); }while(1);

33 利用信号量集解决读者-写者问题 假定最多只允许RN个读者 使用信号量L控制读者的数量
var RN integer; L, mx:semaphore:=RN,1; reader: begin repeat Swait(L,1,1); Swait(mx,1,0); … read … Ssignal(L,1); until false; end writer: begin repeat Swait(mx,1,1; L,RN,0); …write… Ssignal(mx,1) end

34 Dining-Philosophers Problem哲学家就餐问题
Thinking or eating Only 5 chopsticks Left & right One at a time At most 2 philosophers can eat at a time semaphore chopstick[5] ={1,1,1,1,1};

35 Dining-philosophers problem (cont.)
A possible solution Philosopher i Possible deadlock When 5 philosophers each grabs the left chopstick, … Solutions: Philosophers <=4 Only if both chopsticks are available, … Odd, first left then right; even, first right then left do{ P(chopstick[i]); // left P(chopstick[(i+1)%5]; // right /* eating */ V(chopstick[i]; V(chopstick[(i+1)%5]; /* thinking */ }while(1);

36 利用AND信号量解决哲学家就餐问题 var chopstick array of semaphore:=(1,1,1,1,1) process i repeat think; Swait(chopstick[(i+1)mod5], chopstick[i]); eat; Ssignal(chopstick[(i+1)mod5], chopstick[i]); until false;

37 Timing errors Only happen when some particular execution sequences take place For example: counter++; counter--; Difficult to detect Do not always occur

38 Misuse of semaphore  timing errors
Semaphore is just a convenient and effective mechanism for process synchronization. If be used incorrect, timing errors will happen. Example 1: The given solution to Dining-philosophers problem Only if 5 philosophers each grabs the left chopstick simultaneously An honest programming error or an uncooperative programmer also results in timing errors. For example:

39 Example 2 Example 2.1: If the order of P/V is interchanged
V(mutex); CS section; P(mutex); irreproducible, violating the mutual-exclusion requirement Example 2.2: If replaces V(mutex) with P(mutex) always deadlock

40 Example 2.3: If P or V or both be omitted
Example 2 (cont’d) Example 2.3: If P or V or both be omitted P(mutex); CS section; // starving (deadlock) or CS section; V(mutex); // mutual exclusion is violated CS section; // mutual exclusion is violated

41 管程 内容提要 进程同步问题的来由和进程同步的主要任务 临界资源和临界区 2任务的进程互斥问题的解决方案 信号量Semaphores
死锁和饿死现象 经典同步问题 管程 进程间通信

42 The solution: Monitor 管程
引入管程的原因：方便性 管程将对共享资源（数据）的同步操作加以封装 Hansan关于管程的定义： 一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据

43 高级语言结构：管程类型 管程的组成： 管程的名称 局部于管程内部的共享数据说明 对该数据结构进行操作的一组过程
对局部于管程内部的共享数据设置初始值的语句

44 type monitor-name = monitor variable declarations procedure entry P1(…) begin … end; procedure entry P2(…) begin … end; … procedure entry Pn(…) begin … end; begin initilization code; end

45 Synchronization of monitor
The monitor construct prohibits concurrent access to all procedures defined within the monitor. Only one process may be active within the monitor at a time. The synchronization is built into the monitor type, the programmer does not need to code it explicitly.

46 Condition Variables条件变量
To allow a process to wait within the monitor, a condition variable must be declared, as condition x, y; //分别表示不同的等待原因 条件变量只能通过 wait 和 signal来操作 x.wait The process invoking this operation is blocked until another thread invokes x.signal x.signal Resumes exactly one thread. If no thread is blocked, then it’s no effect

47 具有条件变量的管程

48 Something about signal
E.g.: P invokes x.signal, and Q is blocked on condition x. Which one will execute then? Make sure: only one process can be active! Two possibilities: Signal-&-Wait Signal-&-continue

49 Monitor for PC problem type PC＝monitor var in,out,count: integer; buffer: array[0,…,n-1] of item; notfull, notempty: condition; procedure entry put(item) begin if (count≥n) then notfull.wait; //满，则等待非满 buffer[in] := nextp; in := (in+1)mod n count:=count+1; if notempty.queue then notempty.signal; end

50 procedure entry get(item) begin if count≤0 then notempty
procedure entry get(item) begin if count≤0 then notempty.wait; //空，则等待非空 nextc:=buffer[out]; out:=(out+1)mod n; count:=count-1; if notfull.queue then notfull.signal; end begin in:=out:=0; count:=0; end producer begin repeat produce item… PC.put(item) until false end consumer: begin repeat PC.get(item); consume item… until false end

51 利用管程解决哲学家同步问题 type DP＝monitor var state: array[0,…,4] of (thinking, hungry, eating); var self: array[0,…,4] of condition; procedure entry pickup(i:0…4) begin state[i]:=hungry; test(i); if state[i] ≠eating then self[i].wait; end procedure entry putdown(i:0…4) begin state[i] :=thinking; test(i+4 mod 5); test(i+1 mod 5); end

52 procedure test(k:0…4) begin if state[k+4 mod 5] ≠eating and state[k]=hungry and state[k+1 mod 5] ≠eating then begin state[k]:=eating; self[k].signal; end end begin //初始化 for i:=0 to do state[i]:=thinking; end 哲学家i： repeat hungry… DP.pickup(i); eating… DP.putdown(i); thinking; until false;

53 管程 进程间通信 内容提要 进程同步问题的来由和进程同步的主要任务 临界资源和临界区 2任务的进程互斥问题的解决方案
信号量Semaphores 死锁和饿死现象 经典同步问题 管程 进程间通信

54 进程间通信的类型 进程通信是进程之间的信息交换。 低级通信：用于进程的同步和互斥，如信号量 高级通信 通信效率低；对用户不透明 共享内存
消息传递系统 管道通信系统

55 共享存储器 1）基于共享数据结构的通信方式 2）基于共享内存区的通信方式 如生产者消费者问题中的缓冲区
缺点：低效；需要用户考虑数据结构并进行同步互斥 比较低级 2）基于共享内存区的通信方式

56 消息传递系统 以消息为单位 提供一组通信原语，如send，receive等 两种实现方式： 直接通信方式：使用进程的消息缓冲队列
间接通信方式：使用中间介质，称为信箱

57 管道通信 管道： UNIX 管道机制必须提供的协调能力：
是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称为pipe文件 UNIX 管道机制必须提供的协调能力： 互斥：不能同时读写 同步：满写和空读的等待 判断对方是否存在。双方都存在时，才能通信

58 管程 进程间通信 内容提要 进程同步问题的来由和进程同步的主要任务 临界资源和临界区 2任务的进程互斥问题的解决方案
信号量Semaphores 死锁和饿死现象 经典同步问题 管程 进程间通信

59 作业 什么是临界资源？什么是临界区？ 同步机制应该遵循的规则有哪几个？ 信号量有几种分类方式？每种分类方式中包含几种信号量？
死锁和饿死有什么异同？ 高级通信机制主要有哪几种？

60 参考上机作业，不必做 利用Linux或者Windows提供的信号量机制，解决生产者消费者问题。