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

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

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

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

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

4 进程同步问题的来由 The processes are cooperating with each other directly or indirectly. Concurrent access to shared data may result in data inconsistency. 举例： 打印机 共享变量、表格、链表

5 细分进程之间的相互制约关系 进程同步的主要任务是： 间接相互制约关系 来源于进程间的资源共享关系，例如打印机
直接相互制约关系 来源于进程间的合作，例如利用缓冲区传递信息 进程同步的主要任务是： 对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可在现性

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

7 临界资源和临界区 举例：生产者－消费者问题（P－C问题）

8 Example: producer-consumer problem
PC问题是经典的同步问题 一群生产者进程（Producer）生产产品（信息）提供给消费者进程消费 它们使用具有n个缓冲区的缓冲池来传递（共享）产品 生产者每次将一个产品放入一个缓冲区 消费者每次从一个缓冲区中取走一个产品

9 生产者进程与消费者进程并发异步的运行，它们之间必须同步：
不允许生产者向一个满的缓冲区投放产品 不允许消费者从一个空的缓冲区去取产品

10 错误示例程序 var n: integer; //缓冲池大小 type item=…;
var buffer: array [0,1,…,n-1] of item; //缓冲池 in, out : 0,1,…,n-1; //下一个可投和可取，初始0 counter: 0,1,…,n; //当前产品个数 producer: repeat … produce an item in nextp … while counter = n do no-op buffer[in] := nextp; in:=in+1 mod n counter:=counter+1; until false; consumer: repeat while counter =0 do no-op; nextc:=buffer[out]; out:=(out+1) mod n; counter:=counter-1; … consumer the item in nextc; … until false;

11 C语言的表示（1） Shared data #define BufSize 10 typedef struct { … } item;
item buf[BufSize]; int in=0; int out = 0; int count =0; Producer item newProduced; While (1) { /*produce an new item;*/ while (count==BufSize) ; /* do nothing */ ++count; buf[in] = newProduced; in = (in+1) %BufSize; } Consumer item nextConsumed; While(1) { while (count==0); /* do nothing */ --count; nextConsumed = buf[out]; out = (out+1) %BufSize; /* consume */

12 C语言的表示（2），判断空和满的方法不同 Shared data #define BufSize 10 typedef struct { …
} item; item buf[BufSize]; int in=0; int out = 0; The shared buffer is implemented as a circular array in points to the next free position in the buffer out points to the first full positions in the buffer, except … They are blocked when … Solution is correct, but can only fill up ?? buffer Producer item newProduced; While (1) { /*produce an new item;*/ while (((in+1)%BufSize)==out) ; /* do nothing */ buf[in] = newProduced; in = (in+1) %BufSize; } Consumer item nextConsumed; While(1) { while (in==out) nextConsumed = buf[out]; out = (out+1) %BufSize; /* consume */

13 错误示例程序分析 考虑counter这个变量 设counter当前值为5 当上述两个代码段顺序执行时，无论谁先谁后，都正确 但
register1 = count; register1 = register1+1; count = register1 ; 对于counter:=counter-1语句： register2 = count; register2 = register2-1; count = register2 ;

14 推进顺序不合理时 The value of count may be either 4 or 6, where the correct result should be 5 P register1 = count; register1 = 5 register1 = register1+1; register1 = 6 C register2 = count; register2 = 5 register2 = register2-1; register2 = 4 count = register1; count = 6 count = register2; count = 4

15 临界资源（ Critical-resource ）定义： 在一段时间内只允许一个进程访问的资源
Race condition竞争条件 Race condition The situation where several processes access and manipulate shared data concurrently, & the final value of the shared data depends on the particular order in which the access takes place To prevent race conditions, concurrent processes must be synchronized E.g.: either producer or consumer can manipulate the variable count at a time. 临界资源（ Critical-resource ）定义： 在一段时间内只允许一个进程访问的资源

16 如果有：原子操作Atomic operation
To avoid interleaving … The statements ++count; & --count; must be performed atomically Atomic operation means an operation that completes in its entirety without interruption

17 临界区 临界区（Critical Section）定义： 进程中，访问临界资源的那段代码称为临界区 必须规范对临界区的访问
General structure of process P do { entry section（进入区） critical section exit section（退出区） remainder section } while(1)

18 同步机制应遵循的规则 空闲让进：Progress 忙则等待：Mutual Exclusion (互斥)
有限等待： Bounded Waiting，避免饿死 让权等待：不忙等，让出处理器 Nonzero speed, but no assumption

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

20 Two-Tasks solutions Only 2 tasks, T1 & T2 4 algorithms, software based

21 Algorithm 1 Let the two threads share a common integer value turn Ti
volatile int turn=0; // initially turn = 0 turn =i  Ti can enter its CS Ti Do { while (turn!=i); // do nothing critical section; turn = j; remainder section; } while(1); 分析：Satisfies mutual execution, but not progress reason? 1

22 Algorithm 2 Replace the shared variable turn with a shared array: Ti
volatile boolean flag[2]; Initially flag[0] = flag[1] = false; flag[i] = true  Ti want to enter its CS Ti do { While (flag[j]); flag[i] = true; Critical section; Flag[i]=flase; Remainder section; } while(1); 分析：满足空闲让进，但当flag几乎同时从false转为true时，会出现同时进入临界区的现象，即不满足“互斥”

23 Algorithm 3 flag[i] = true  Ti is hoping to enter its CS Ti
do { flag[i] = true; While (flag[j]) do no-op; Critical section; Flag[i]=flase; Remainder section; } while(1); 分析：当几乎同时将flag设为true后，两者都进不了临界区（永远），同时违背“空闲让进”和“有限等待”

24 Algorithm 4, peterson’s solution
Combining the key ideas of algorithm 1 & 2 Ti: do{ flag[i]=true; turn = j; while (flag[j] && turn==j); critical section; flag[i] = false; remainder section; } while(1); Meets all requirements; solves the CS problem for 2-Tasks

25 利用硬件方法解决互斥问题 Hardware instruction Test-&-Set instruction
Swap instruction

26 Test-&-Set instruction
TS instruction /* return original value & set it to ture*/ boolean TS( boolean variable) { boolean return_value = variable; variable = true; return return_value; } Truth table 真值表 variable TS before after F T

27 Using Test-&-Set intruction
Shared variable: boolean lock=false; //资源状态空闲 Pj: do { while( TS(lock)); // 操作前lock？操作后lock？ critical section; lock = false; remainder section; } while (1);

28 Swap instruction The instruction /* swap the value of 2 variable */
void swap ( boolean &v1, boolean &v2){ boolean temp = v1; v1 = v2; v2 = temp; } Truth-table 真值表 (v1,v2) Before after (T, T) (T, F) (F, T) (F, F)

29 Using swap instruction
Shared variable: boolean lock = false; Local variable: boolean key = false; Pi: do { key = true; while (key==true) swap(lock, key); critical section; lock = false; remainder section; } while(1); Truth-table: (lock,key) Before after (T, T) (T, F) (F, T) (F, F)