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

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

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

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

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

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

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

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

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

错误示例程序 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;

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 */

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 */

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

推进顺序不合理时 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

临界资源（ 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 ）定义： 在一段时间内只允许一个进程访问的资源

如果有：原子操作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

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

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

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

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

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

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时，会出现同时进入临界区的现象，即不满足“互斥”

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后，两者都进不了临界区（永远），同时违背“空闲让进”和“有限等待”

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

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

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

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

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)

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)