系统进程同步处理及管程

1、韩都衣舍淘宝店 http:/ 潮州新闻网 http:/ 韩都衣舍童装时尚女装 http:/ 网购韩都衣舍首选麦考林 http:/ 韩都衣舍官方旗舰店 http:/ 金彩 http:/ 有限缓冲问题的共享内存解决方案（自学，增加计数变量有限缓冲问题的共享内存解决方案（自学，增加计数变量count） 设设count当前值为当前值为5，则：，则：R1=counter R1=5R1=R1+1 R1=6counter=R1 c=6R2=counter R2=6R2=R2-1 R2=5counter=R2 c=5R1=counter R1=5R1=R1+1 R1=6 R2=counter R2=5R2=R

2、2-1 R2=4counter=R1 c=6counter=R2 c=43 竞争条件竞争条件（race condition）：）：多个进程并发访问和操作多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关同一数据且执行结果与访问发生的特定顺序有关 防止竞争条件防止竞争条件：确保一段时间内只有一个进程能操作共享：确保一段时间内只有一个进程能操作共享变量变量进程同步进程同步（process synchronization）补充：并发与并行补充：并发与并行 并发（并发（concurrency）：）：多个事件在同一时间间隔内发生多个事件在同一时间间隔内发生 并行（并行（parallel）：

3、）：多个事件在同一时刻发生多个事件在同一时刻发生 单单CPUCPU系统中，程序在宏观上并发，微观上串行执行系统中，程序在宏观上并发，微观上串行执行 多多CPUCPU系统中，程序在宏观上并发，微观上并行执行系统中，程序在宏观上并发，微观上并行执行4临界区域问题临界区域问题临界区（临界区（critical section）：）：进程的代码段进程的代码段临界区问题：设计一个进程用来协作的协议临界区问题：设计一个进程用来协作的协议 进入区（进入区（entry section） 退出区（退出区（exit section） 剩余区（剩余区（remainder section）临界区问题的解答必须满足三项要

4、求临界区问题的解答必须满足三项要求0互斥互斥0有空让进（前进要求）有空让进（前进要求）0有限等待有限等待1) 典型进程典型进程Pi的通用结构的通用结构do 临界区临界区 剩余区剩余区 while(1)进入区进入区退出区退出区51、两进程解法、两进程解法 算法算法1 算法算法2do 临界区临界区 剩余区剩余区 while(1)flagi=true; while(flagj);flagi=false;do 临界区临界区 剩余区剩余区 while(1)while(turn!=i);turn=j;分析：分析：满足互斥要求满足互斥要求不满足前进要求（严格交替）不满足前进要求（严格交替）分析：分析：满足互

5、斥要求满足互斥要求不满足前进要求（精确时序）不满足前进要求（精确时序）6do 临界区临界区 剩余区剩余区 while(1)flagi=true;turn=j;while(flagj&turn=j);flagi=false; 算法算法3分析：分析：满足互斥要求满足互斥要求满足前进要求满足前进要求满足有限等待要求满足有限等待要求72、多进程解法、多进程解法v 面包店算法面包店算法 思想：小号码客户先得到服务，相同号码取名称小者思想：小号码客户先得到服务，相同号码取名称小者 数据结构数据结构boolean choosingn; (初值为初值为false)int numbern; (初值为初值

6、为0) 约定符号约定符号若若 ac或或a=c&bd 则记为则记为 (a,b)=ai 对对i=0,n-1成立成立8面包店算法中进程面包店算法中进程Pi的结构的结构do 临界区临界区 剩余区剩余区 while(1)choosingi=true;numberi=max(number0,number1,numbern-1)+1;choosingi=false;for(j=0;jn;j+) while(choosingj); while(numberj!=0)&(numberj,j)(numberi,i);numberi=0;上述四种算法都要忙等待（循环测试）！上述四种算法都要忙等待（循

7、环测试）！9同步硬件同步硬件（简单了解）（简单了解） 单处理器环境单处理器环境0在修改共享变量时禁止中断出现在修改共享变量时禁止中断出现 多处理器环境多处理器环境0使用特殊硬件指令，提供原子操作使用特殊硬件指令，提供原子操作xTestAndSetxSwap10信号量信号量 信号量（信号量（semaphore，S）0整数变量，除了初始化，只能由整数变量，除了初始化，只能由wait和和signal访问访问 wait的经典定义的经典定义 signal的经典定义的经典定义 对信号量整数值的修改必须不可分的执行对信号量整数值的修改必须不可分的执行原子操作原子操作wait(S) while(s=0) ;/

8、no-op S-;signal(S) S+;111、用法、用法解决解决n个进程的临界区问题个进程的临界区问题互斥互斥0 设设n个进程共享一个信号量个进程共享一个信号量mutex，初始化为初始化为10 进程进程Pi的组织结构如下的组织结构如下do 临界区临界区 剩余区剩余区 while(1)wait(mutex);signal(mutex);使用信号量解决各种同步问题使用信号量解决各种同步问题同步同步122、实现、实现 自旋锁（自旋锁（spinlock）忙等待忙等待 克服忙等，重新定义信号量和克服忙等，重新定义信号量和wati、signal操作操作 信号量定义信号量定义typedef struc

9、t int value; struct process *L; semaphore;整数值整数值进程进程链表链表13 wait操作操作 signal操作操作void wait(semaphore S) S.value - -; if (S. value0) add this process to S.L; block( ); void signal(semaphore S) S.value + +; if (S. value=0) remove a process from S.L; wakeup( P); 若若S.value0，则其绝对值是等待信号量则其绝对值是等待信号量S的进程个数的进程个

10、数 信号量原子执行信号量原子执行143、死锁与饥饿（、死锁与饥饿（了解概念了解概念） 死锁（死锁（deadlocked）0两个或多个进程无限地等待一个事件，而该事件只能由两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生这些等待进程之一来产生 饥饿（饥饿（starvation）或无限期阻塞（或无限期阻塞（indefinite blocking）0进程在信号量内无穷等待进程在信号量内无穷等待157.5 经典同步问题经典同步问题1、有限缓冲问题（生产者消费者问题）、有限缓冲问题（生产者消费者问题） 数据结构数据结构 semaphore mutex,empty,fullxmute

11、x：提供对缓冲池访问的互斥要求，初值提供对缓冲池访问的互斥要求，初值1xempty：空缓冲项，初值空缓冲项，初值nxfull：满缓冲项，初值满缓冲项，初值016do produce an item in nextp; wait(empty); wait(mutex); add nextp to buffer signal(mutex); signal(full); while(1);do wait(full); wait(mutex); remove an item from buffer to nextc; signal(mutex); signal(empty); consume the

12、item in nextc while(1);生产者进程结构生产者进程结构消费者进程结构消费者进程结构172、读者作者问题、读者作者问题第一读者作者问题（第一读者作者问题（V）：）：读者不需等待读者不需等待第二读者作者问题：若有作者等待，新读者需等待第二读者作者问题：若有作者等待，新读者需等待数据结构数据结构0 semaphore mutex,wrt;0 int readcount;xmutex：确保在更新变量确保在更新变量readcount时的互斥，初值时的互斥，初值1xwrt：供写者及第一个进入临界区和最后一个离开临界供写者及第一个进入临界区和最后一个离开临界区的读者使用，初值区的读者使用

13、，初值11) readcount：用来跟踪有多少进程正在读对象用来跟踪有多少进程正在读对象18 作者进程结构作者进程结构读者进程结构读者进程结构 wait(wrt); writing is performed signal(wrt); wait(mutex); readcount+ +; If(readcount=1) wait(wrt); signal(mutex); reading is performed wait(mutex); readcount- -; if(readcount=0) signal(wrt); signal(mutex); 第一个进第一个进入临界区入临界区的读者的读

14、者最后一个最后一个离开临界离开临界区的读者区的读者193、哲学家就餐问题、哲学家就餐问题 数据结构数据结构0semaphore chopstick5;xchopsticki：第第i个哲学家身边的筷子，初值个哲学家身边的筷子，初值1食物食物20哲学家哲学家i的结构的结构do wait(chopsticki); wait(chopstick(i+1)%5 ); eat signal(chopsticki); signal(chopstick (i+1)%5 ); think while(1);分析：分析：确保没有两个相邻哲确保没有两个相邻哲学家同时进餐学家同时进餐可能会导致死锁（例可能会导致死锁（

15、例如如5个哲学家同时拿个哲学家同时拿起左边的筷子）起左边的筷子）21解决死锁问题的方案解决死锁问题的方案最多只允许最多只允许4个哲学家同时坐在桌子上个哲学家同时坐在桌子上只有两只筷子都可用时才允许一个哲学家拿起它们只有两只筷子都可用时才允许一个哲学家拿起它们使用非对称解决，即奇数哲学家先拿起他左边的筷使用非对称解决，即奇数哲学家先拿起他左边的筷子，接着拿他右边的筷子，而偶数哲学家先拿起他子，接着拿他右边的筷子，而偶数哲学家先拿起他右边的筷子，接着拿起他左边的筷子右边的筷子，接着拿起他左边的筷子饿死问题无法确保饿死问题无法确保22临界区域临界区域（简单了解）（简单了解） 信号量使用时可能出现一些

16、错误信号量使用时可能出现一些错误0若交换了若交换了wait和和signal的执行顺序，多个进程可能在的执行顺序，多个进程可能在临界区内同时执行，违反互斥要求临界区内同时执行，违反互斥要求0若若wait替代了替代了signal，会发生死锁会发生死锁0若省略了若省略了wait或或signal或两者，可能会死锁或违反互或两者，可能会死锁或违反互斥斥 针对上述问题高级语言构造针对上述问题高级语言构造0临界区域（条件临界区域）临界区域（条件临界区域）0管程（管程（monitor）23临界区域临界区域 需要定义的数据结构需要定义的数据结构0v：类型为类型为T的共享数据（的共享数据（v: shared T）

17、0B：布尔逻辑表达式布尔逻辑表达式0S：与与v关联的执行语句关联的执行语句 region v when(B) S;0当语句当语句S在执行时，没有其他进程能访问变量在执行时，没有其他进程能访问变量v 当进程试图进入临界区时，先计算布尔逻辑表达式当进程试图进入临界区时，先计算布尔逻辑表达式B，若若为真，执行语句为真，执行语句S；否则，进程放弃互斥并延迟到否则，进程放弃互斥并延迟到B为真为真，并且没有其他进程位于与，并且没有其他进程位于与v相关联的区域内相关联的区域内24管程（管程（monitor） 管程的语法管程的语法monitor monitor-name shared variable dec

18、larations procedure body p1() procedure body p2() procedure body pn() initialization code 管程：由程序员定义的一管程：由程序员定义的一组操作符，管程构造确保一组操作符，管程构造确保一次只有一个进程能在管程内次只有一个进程能在管程内活动活动 条件变量条件变量 condition x, y;x.wait();调用操作的进程会暂停直到调用操作的进程会暂停直到另一进程调用另一进程调用x.signal();重新启动一个悬挂的进程重新启动一个悬挂的进程251、管程哲学家就餐问题的无死锁解答、管程哲学家就餐问题的无死锁

19、解答 数据结构数据结构0enum thinking, hungry, eating state5;0condition self5;0管程管程dp控制筷子的分布控制筷子的分布 哲学家哲学家i的操作的操作dp.pickup(i); eat dp.putdown(i);26哲学家就餐问题的管程解法哲学家就餐问题的管程解法monitor dp enum thinking, hungry, eating state5; condition self5; void pickup(int i) statei=hungry; test(i); if(statei!= eating) selfi.wait()

20、; void putdown(int i) statei=thinking; test(i+4)%5); test(I+1)%5); 27void test (int i) if (state(i+4)%5!=eating)&(statei=hungry) &(state(i+1)%5!=eating) statei=eating; selfi.signal(); void init () for(int i=0;i0) signal(next);else signal(mutex);外部程序外部程序293、条件变量的实现、条件变量的实现 semaphore x_sem; /初

21、值为初值为0 int x_count; /初值为初值为0 x.waitx.signalx_count+ +;if (next_count0) signal(next);else signal(mutex);wait(x-sem);x_count- -;if (x_count0) next_count+ +; signal(x_sem); wait(next); signal(mutex); next_count- -;30总结补充总结补充 信号量小结信号量小结 wait、signal操作小结操作小结 前驱关系的信号量解答前驱关系的信号量解答 针对信号量问题的补充练习针对信号量问题的补充练习31

22、1、信号量小结、信号量小结v 一个信号量可用于一个信号量可用于n n个进程的同步互斥；且只能由个进程的同步互斥；且只能由waitwait、signalsignal操作修改。操作修改。用于互斥时，用于互斥时，S S初值为初值为1 1，取值为，取值为1 - (1 - (n-1) n-1) （相当于临界区的通行证，实际上也是资源个数）相当于临界区的通行证，实际上也是资源个数） S=1S=1：临界区可用：临界区可用 S=0S=0：已有一进程进入临界区：已有一进程进入临界区 S0S=0=0 S=0:S=0:表示可用资源个数表示可用资源个数 S0: S0: 表示该资源的等待队列长度表示该资源的等待队列长度

23、322 2、waitwait、signalsignal操作小结操作小结 wait(S)wait(S)：请求分配一个资源。请求分配一个资源。 signal(S)signal(S)：释放一个资源。释放一个资源。 waitwait、signalsignal操作必须成对出现。操作必须成对出现。 用于互斥时，位于同一进程内；用于互斥时，位于同一进程内； 用于同步时，交错出现于两个合作进程内。用于同步时，交错出现于两个合作进程内。 多个多个waitwait操作的次序不能颠倒，否则可能导致死锁。操作的次序不能颠倒，否则可能导致死锁。 多个多个signalsignal操作的次序可任意。操作的次序可任意。333

24、、补充例题（前驱关系）、补充例题（前驱关系） 如图所示的优先图，要求用信号量实现如图所示的优先图，要求用信号量实现S1S3S4S5S6S7S234Semaphore a,b,c,d,e,f,g; /初值为初值为0 S1;signal(a);signal(b); wait(a);S2;S4;signal (c);signal(d); wait(b);S3;signal(e); wait (c);wait(e);S5;signal(f); wait(d);S6;signal(g); wait(f);wait(g);S735补充题目练习补充题目练习S1S3S4S5S6S236Semaphore a,

25、b,c,d,e,f,g; /初值为初值为0 S1;signal(a);signal(b); wait(a);S2; signal(c);signal(d); wait (b); S3;signal(e); wait(c);S4;signal(f); wait(d);S5;signal(g); wait(e);wait(f);wait(g);S6;374、针对信号量问题的补充练习、针对信号量问题的补充练习桌子上有一个盘子，可以存放一个水果。父亲总是放苹桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃盘

26、中的香蕉，而女儿专等吃盘中的苹果。盘中的香蕉，而女儿专等吃盘中的苹果。 分析：生产者消费者问题的一种变形，生产者、消费分析：生产者消费者问题的一种变形，生产者、消费者以及放入缓冲区的产品都有两类，但每类消费者只消者以及放入缓冲区的产品都有两类，但每类消费者只消费其中固定的一种产品。费其中固定的一种产品。 数据结构：数据结构：semaphore dish， apple ， banana ; dish：表示盘子是否为空，初值为表示盘子是否为空，初值为1 apple：表示盘中是否有苹果，初值为表示盘中是否有苹果，初值为0 banana：表示盘中是否有香蕉，初值为表示盘中是否有香蕉，初值为038father:do wait(dish); 将苹果放到盘中；将苹果放到盘中； signal(apple);while(1);mother:do wait(dish); 将香蕉放到盘中；将香蕉放到盘中； signal(banana);while(1);son:do wait(banana); 从盘