系统进程同步处理与管程

韩都衣舍淘宝店

/

潮州新闻网

韩都衣舍童装时尚女装

/

网购韩都衣舍首选麦考林

/

韩都衣舍官方旗舰店

/

金彩

/1系统进程同步处理与管程背景临界区域问题同步硬件信号量经典同步问题临界区域管程2背景有限缓冲问题的共享内存解决方案（自学，增加计数变量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=R2-1……R2=4counter=R1……c=6counter=R2……c=43竞争条件（racecondition）：多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关防止竞争条件：确保一段时间内只有一个进程能操作共享变量——进程同步（processsynchronization）补充：并发与并行并发（concurrency）：多个事件在同一时间间隔内发生并行（parallel）：多个事件在同一时刻发生单CPU系统中，程序在宏观上并发，微观上串行执行多CPU系统中，程序在宏观上并发，微观上并行执行4临界区域问题临界区（criticalsection）：进程的代码段临界区问题：设计一个进程用来协作的协议进入区（entrysection）退出区（exitsection）剩余区（remaindersection）临界区问题的解答必须满足三项要求互斥有空让进（前进要求）有限等待典型进程Pi的通用结构do{

临界区剩余区}while(1)进入区退出区51、两进程解法算法1算法2do{

临界区剩余区}while(1)flag[i]=true;while(flag[j]);flag[i]=false;do{

临界区剩余区}while(1)while(turn!=i);turn=j;分析：满足互斥要求不满足前进要求（严格交替）分析：满足互斥要求不满足前进要求（精确时序）6do{

临界区剩余区}while(1)flag[i]=true;turn=j;while(flag[j]&&turn==j);flag[i]=false;

算法3分析：满足互斥要求满足前进要求满足有限等待要求72、多进程解法面包店算法思想：小号码客户先得到服务，相同号码取名称小者数据结构booleanchoosing[n];(初值为false)intnumber[n];(初值为0)约定符号若a<c或a==c&&b<d则记为(a,b)<(c,d)max(a0,…,an-1)是数k，表示k>=ai对i=0,…,n-1成立8面包店算法中进程Pi的结构do{

临界区剩余区}while(1)choosing[i]=true;number[i]=max(number[0],number[1],…,number[n-1])+1;choosing[i]=false;for(j=0;j<n;j++){while(choosing[j]);while((number[j]!=0)&&(number[j],j)<(number[i],i));}number[i]=0;上述四种算法都要忙等待（循环测试）！9同步硬件（简单了解）单处理器环境在修改共享变量时禁止中断出现多处理器环境使用特殊硬件指令，提供原子操作TestAndSetSwap10信号量信号量（semaphore，S）整数变量，除了初始化，只能由wait和signal访问wait的经典定义signal的经典定义对信号量整数值的修改必须不可分的执行——原子操作wait(S){while(s<=0);//no-opS--;}signal(S){S++;}111、用法解决n个进程的临界区问题——互斥设n个进程共享一个信号量mutex，初始化为1进程Pi的组织结构如下do{

临界区剩余区}while(1)wait(mutex);signal(mutex);使用信号量解决各种同步问题——同步122、实现自旋锁（spinlock）－忙等待克服忙等，重新定义信号量和wati、signal操作信号量定义typedefstruct{intvalue;structprocess*L;}semaphore;整数值进程链表13wait操作signal操作voidwait(semaphoreS){S.value--;if(S.value<0){addthisprocesstoS.L;block();}}voidsignal(semaphoreS){S.value++;if(S.value<=0){removeaprocessfromS.L;wakeup(P);}}若S.value<0，则其绝对值是等待信号量S的进程个数信号量原子执行143、死锁与饥饿（了解概念）死锁（deadlocked）两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生饥饿（starvation）或无限期阻塞（indefiniteblocking）进程在信号量内无穷等待157.5经典同步问题1、有限缓冲问题（生产者－消费者问题）数据结构semaphoremutex,empty,fullmutex：提供对缓冲池访问的互斥要求，初值1empty：空缓冲项，初值nfull：满缓冲项，初值016do{…produceaniteminnextp;…wait(empty);wait(mutex);…addnextptobuffer…signal(mutex);signal(full);}while(1);do{wait(full);wait(mutex);…removeanitemfrombuffertonextc;…signal(mutex);signal(empty);…consumetheiteminnextc…}while(1);生产者进程结构消费者进程结构172、读者－作者问题第一读者－作者问题（V）：读者不需等待第二读者－作者问题：若有作者等待，新读者需等待数据结构semaphoremutex,wrt;intreadcount;mutex：确保在更新变量readcount时的互斥，初值1wrt：供写者及第一个进入临界区和最后一个离开临界区的读者使用，初值1readcount：用来跟踪有多少进程正在读对象18作者进程结构读者进程结构wait(wrt);…writingisperformed…signal(wrt);wait(mutex);readcount++;If(readcount==1)wait(wrt);signal(mutex);…readingisperformed…wait(mutex);readcount--;if(readcount==0)signal(wrt);signal(mutex);第一个进入临界区的读者最后一个离开临界区的读者193、哲学家就餐问题数据结构semaphorechopstick[5];chopstick[i]：第i个哲学家身边的筷子，初值1食物20哲学家i的结构do{wait(chopstick[i]);wait(chopstick[(i+1)%5]);…eat…signal(chopstick[i]);signal(chopstick[(i+1)%5]);…think…}while(1);分析：确保没有两个相邻哲学家同时进餐可能会导致死锁（例如5个哲学家同时拿起左边的筷子）21解决死锁问题的方案最多只允许4个哲学家同时坐在桌子上只有两只筷子都可用时才允许一个哲学家拿起它们使用非对称解决，即奇数哲学家先拿起他左边的筷子，接着拿他右边的筷子，而偶数哲学家先拿起他右边的筷子，接着拿起他左边的筷子饿死问题无法确保22临界区域（简单了解）信号量使用时可能出现一些错误若交换了wait和signal的执行顺序，多个进程可能在临界区内同时执行，违反互斥要求若wait替代了signal，会发生死锁若省略了wait或signal或两者，可能会死锁或违反互斥针对上述问题－高级语言构造临界区域（条件临界区域）管程（monitor）23临界区域需要定义的数据结构v：类型为T的共享数据（v:sharedT）B：布尔逻辑表达式S：与v关联的执行语句regionvwhen(B)S;当语句S在执行时，没有其他进程能访问变量v当进程试图进入临界区时，先计算布尔逻辑表达式B，若为真，执行语句S；否则，进程放弃互斥并延迟到B为真，并且没有其他进程位于与v相关联的区域内24管程（monitor）管程的语法monitormonitor-name{sharedvariabledeclarationsprocedurebodyp1(…){…}procedurebodyp2(…){…}…procedurebodypn(…){…}{initializationcode}}管程：由程序员定义的一组操作符，管程构造确保一次只有一个进程能在管程内活动条件变量conditionx,y;x.wait();调用操作的进程会暂停直到另一进程调用x.signal();重新启动一个悬挂的进程251、管程－哲学家就餐问题的无死锁解答数据结构enum{thinking,hungry,eating}state[5];conditionself[5];管程dp控制筷子的分布哲学家i的操作dp.pickup(i);…eat…dp.putdown(i);26哲学家就餐问题的管程解法monitordp{enum{thinking,hungry,eating}state[5];conditionself[5];voidpickup(inti){state[i]=hungry;test(i);if(state[i]!=eating)self[i].wait();}voidputdown(inti){state[i]=thinking;test((i+4)%5);test((I+1)%5);}27voidtest(inti){if(state[(i+4)%5]!=eating)&&(state[i]==hungry)&&(state[(i+1)%5]!=eating){state[i]=eating;self[i].signal();}}voidinit(){for(inti=0;i<5;i++)state[i]=thinking;}}282、用信号量实现管程数据结构semaphoremutex,next;intnext_count;mutex：互斥，初值1next：供信号进程挂起自己，初值0next_count：对挂起在next上的进程数量计数wait(mutex);…bodyofF…if(next_count>0)signal(next);elsesignal(mutex);外部程序293、条件变量的实现semaphorex_sem;//初值为0intx_count;//初值为0x.waitx.signalx_count++;if(next_count>0)signal(next);elsesignal(mutex);wait(x-sem);x_count--;if(x_count>0){next_count++;signal(x_sem);wait(next);signal(mutex);next_count--;}30总结补充信号量小结wait、signal操作小结前驱关系的信号量解答针对信号量问题的补充练习311、信号量小结一个信号量可用于n个进程的同步互斥；且只能由wait、signal操作修改。用于互斥时，S初值为1，取值为1~-(n-1)（相当于临界区的通行证，实际上也是资源个数）

S=1：临界区可用

S=0：已有一进程进入临界区

S<0：临界区已被占用，|S|个进程正等待进入用于同步时，S初值>=0

S>=0:表示可用资源个数

S<0:表示该资源的等待队列长度322、wait、signal操作小结wait(S)：请求分配一个资源。

signal(S)：释放一个资源。

wait、signal操作必须成对出现。用于互斥时，位于同一进程内；用于同步时，交错出现于两个合作进程内。多个wait操作的次序不能颠倒，否则可能导致死锁。多个signal操作的次序可任意。333、补充例题（前驱关系）如图所示的优先图，要求用信号量实现S1S3S4S5S6S7S234Semaphorea,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);S7}}35补充题目练习S1S3S4S5S6S236Semaphorea,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、针对信号量问题的补充练习桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃盘中的香蕉，而女儿专等吃盘中的苹果。分析：生产者－消费者问题的一种变形，生产者、消费者以及放入缓冲区的产品都有两类，但每类消费者只消费其中固定的一种产品。数据结构：semaphoredish，apple，banana;dish：表示盘子是否为空，初值为1apple：表示盘中是否有苹果，初值为0banana：表示盘中是否有香蕉，初值为038father:do{wait(dish);

将苹果放到盘中；signal(apple);}while(1);mother:do{wait(dish);

将香蕉放到盘中；signal(banana);}while(1);son:do{wai