操作系統(tǒng)課件pv講評forumf

PV操作習(xí)題講解推廣的消息緩沖問題（1）消息緩沖區(qū)為k個，有m個發(fā)送進(jìn)程，n個接收進(jìn)程，每個接收進(jìn)程對發(fā)送來的消息都必須接收一次。用PV操作組織正確的發(fā)送和接收操作分析假設(shè)發(fā)送者和接收者都是采用環(huán)狀遞增方式使用緩沖區(qū)任意一個發(fā)送者：或等待在第x緩沖區(qū)（條件是緩沖區(qū)x未被清空）

或發(fā)送到x，發(fā)送完后需要通知（喚醒）所有接收進(jìn)程任意一個接收者不停的輪詢緩沖區(qū),如果緩沖區(qū)有內(nèi)容，則收取，并把此緩沖區(qū)的未接收數(shù)減一，如果減至0，則置緩沖區(qū)為空

推廣的消息緩沖問題（2）任意一個緩沖區(qū)或同時被若干個接受者讀取或只被一個發(fā)送者寫入數(shù)據(jù)方案任意一個緩沖區(qū)分為2種互斥的狀態(tài)：空——可被某個發(fā)送者寫入滿——可被所有尚未收取該消息的接收者讀用信號量empty互斥多個發(fā)送者間的寫操作用信號量full和empty同步發(fā)送者和接受者間的先寫后讀操作每個緩沖區(qū)需要記錄已經(jīng)取走當(dāng)前消息的接受者數(shù)目這個變量所有接收者都可以更改，需要用信號量mut同步所有發(fā)送者共享一個消息緩沖隊列，采用環(huán)狀遞增的使用方式共享消息緩沖隊列的指針s，用全局變量mutex互斥對其的訪問typedefstruct{MessageTypemsg;intcount;//記錄未接收的進(jìn)程數(shù)目semaphoremut;//初值為1semaphoreempty;//初值為1semaphorefull[n];}BufferType;BufferTypebuff[m];Sender_i(inti)//i為發(fā)送進(jìn)程號{ints_i;intj;while(true){

P(mutex);s_i=s;s=(s+1)%m;

V(mutex);

P(buff[s_i].empty);

向緩沖區(qū)buff[s_i]中寫入消息；

P(buff[s_i].mut)；

buff[s_i].count=n;

V(buff[s_i].mut);for(j=0;j<n;j++)

V(buff[s_i].full[j]);}}Recerver_i(inti)//i為接收進(jìn)程號{intj;

While(true){for(j=0;j<k;j=(j+1)%k){

P(buff[j].full[i]);

從buff[j]中讀出消息；

P(buff[j].mut);buff[j].count--;if(buff[j].count==0)

V(buff[j].empty);

V(buff[j].mut);}}}第2類讀者寫者問題（1）第2類讀者寫者問題（1）分析設(shè)立全局變量boolwriting標(biāo)志當(dāng)前有寫者在寫intrc計數(shù)當(dāng)前正在讀的讀者數(shù)目intrq計數(shù)當(dāng)前正在等候讀的讀者數(shù)目intwq計數(shù)當(dāng)前正在等待寫的寫者數(shù)目凡是對全局變量的訪問或者修改都必須用信號量互斥設(shè)立全局信號量mutex用信號量read&write互斥讀寫操作Proc_writer(){P(mutex);if(writing||rc>0){wq=wq+1;V(mutex);P(write);}else{writing=true;V(mutex);}Write();P(mutex);if(wq>0){wq=wq-1;V(mutex);V(write);}else{if(rq>0){while(rq>0){rq=rq-1;V(read);}writing=false;V(mutex);}}}Proc_reader(){P(mutex);if(writing||wq!=0){rq=rq+1; V(mutex); P(read);}elseV(mutex);P(mutex);rc=rc+1;V(mutex);Read();P(mutex);rc=rc-1;if(rc==0&&wq>0){writing=true;wq=wq-1;V(mutex);V(write);}elseV(mutex);}另類PV操作（1）有一個系統(tǒng)定義P、V操作如下：另類PV操作（2）另類PV操作（3）解答：（1）不合理：先進(jìn)后出；可能“無限等待”（2）思路：令等待隊列中始終只有一個進(jìn)程。將“?！弊兂伞瓣犃小盨emaphoreS[n-1];//S[i]的初值為i+1Procedure_i(){inti;DO_PRE_JOB();for(i=n-2;i>=0;i--)P(S[i]);DO_JOB_IN_CRITICAL_SECTION;for(i=0;i<n－1;i++)V(S[i]);……}另類PV操作（4）(3)上述解法每次都需要做2(n-1)次P/V操作，性能低下。采用二叉樹的思想，改進(jìn)如下：假設(shè)共有2N個進(jìn)程爭用臨界區(qū)；時間復(fù)雜性：2*(2N-1)vs2log2N；空間復(fù)雜性：2N-1vs2N-1另類PV操作（5）

設(shè)有4個進(jìn)程P1、P2、P3、P4，信號量S1、S2、S3的初值為1P_1()//P2與此同{inti;DO_PRE_JOB();P(S1);P(S3);DO_JOB_IN_CRITICAL_SECTION;V(S3);V(S1);……}P_3()//P4與此同{inti;DO_PRE_JOB();P(S2);P(S3);DO_JOB_IN_CRITICAL_SECTION;V(S3);V(S2);……}睡眠理發(fā)師問題（1）睡眠理發(fā)師問題（2）semaphoresn;//初值為n，代表理發(fā)店位子數(shù)目semaphores;//初值為1，入座理發(fā)椅semaphorebarbering;//初值為0，理發(fā)

custom