4.1 進程間的相互作用
4.1.1 進程間的聯系
資源共享關系
相互合作關系
臨界資源應互斥訪問。
臨界區：不論是硬件臨界資源，還是軟件臨界資源，多個進程必須互斥地對它們進行訪問。
把在每個進程中訪問臨界資源的那段代碼稱為臨界資源區。
顯然，若能保證諸進程互斥地進入自己的臨界區，便可實現它們對臨界資源的互斥訪問。
為此，每個進程在進入臨界區之前，應先對欲訪問的臨界資源進行檢查，看其是否正在被訪問。
如果沒被訪問，則進入臨界區，且設置正訪問標志；如果正被訪問，則不進入臨界區。
同步機制應遵循的標準：
1、空閑讓進
2、忙則等待
3、有限等待 ? ?對要求訪問臨界資源的進程，應保證該進程能在有效的時間進入自己的臨界區，以免陷入“死等”狀態
4、讓權等待 ? ?當進程不能進入自己的臨界區時，應立即釋放處理機，以免進程陷入“忙等”狀態
—————————————————————————————————————————————————————————————————
4.1.2 利用軟件方法解決進程互斥問題
全局共享變量，適用于兩個進程，非重點，用于說明遇到的情況。現在很少采用。
算法1：
設置一個公用整形變量turn，用于指示被允許進入臨界區的編號，即若turn=1，表示允許p1進入臨界區。
main()
{
? ? cobegin{
? ? ? ? p1;
? ? ? ? p2;
? ? }
}
對p1：
while (1)
{
? ? while (turn != 1) no-op;
? ? critical section;
? ? turn = 2;
}
該算法可以確保每次只允許一個進程進入臨界區。但是強制兩個進程輪流進入臨界區，資源利用不充分。
如p1退出臨界區后將turn置2，如果此時p2不進入臨界區，且p1又想再次訪問臨界區，違背“空閑讓進”原則。
算法2：
算法1的問題在于：它采取了強制的方法讓p1和p2輪流訪問臨界資源，完全不考慮它們的實際需要。
算法2的思想是對兩個線程置兩個標志位flag1和flag2。若flag1=1，表示p1正在執行；若flag2=1，表示p2正在執行。
int flag1=0;
int flag2=0;
對p1：
while (1)
{
? ? while (flag2 != 0) no-op;
? ? flag1=1;
? ? critical section;
? ? flag1=0;
}
如果兩個進程在開始時幾乎同時進入臨界區，因而同時發現對方的訪問標志是0，于是兩個進程都先后進入臨界區，此時違背了“忙則等待”原則。
算法3：
使要進入臨界區的進程先設置其要求進入的標志，然后再去查看其它進程的標志。
對p1：
while (1)
{
? ??flag1=1;
? ? while (flag2 != 0) no-op;
? ? critical section;
? ? flag1=0;
}
算法4：
組合了算法1和算法3的概念。
p1將flag1置1代表希望進入臨界區，并將turn置2代表允許p2進入臨界區；判斷flag2 && turn=2為真，等待，否則，進入。
對p1：
while (1)
{
flag1=1;
turn=2;
while (flag2 && turn==2) no-op;
critical section;
flag1=0;
}
此算法即保證了“空閑讓進”，又保證了“忙則等待”。
上述4種算法均為忙式等待，不滿足“讓權等待”。
—————————————————————————————————————————————————————————————————
4.1.3 利用硬件方法解決進程互斥問題
安全利用軟件方法來解決諸進程互斥進入臨界區的問題有一定難度且有很大局限性，因而現在已很少采用。
現在許多計算機已提供了一些特殊的硬件指令，這些指令允許對一個字中的內容進行檢測和修正，或交換兩個字的內容。
1、利用Test-and-Set指令實現互斥
int TS(static int lock)
{
? ? int TS=lock;
? ? lock=1;
? ? return(TS);
}
lock=0表示資源空閑。
為了實現諸進程對臨界資源的互斥訪問，可為每個臨界資源設置一個全局變量lock并賦初值0，表示資源空閑。
用TS指令記錄變量lock的狀態，并將1賦予lock，這等效于關閉了臨界區。
while (1)
{
? ? while(TS(lock)) ?no-op;
? ? critical section;
? ? lock=0;
}
2、利用Swap指令實現進程互斥
Swap指令稱為交換指令。在微機中該指令又稱為XCHG指令，用于交換兩個字的內容。
void Swap(static int a,b)
{
? ? int temp;
? ? temp=a;
? ? a=b;
? ? b=temp;
}
可為臨界資源設置一個全局變量lock。其初值為0，在每個進程中再利用一個局部變量key。
while (1)
{
? ? key=1;
? ? do{
? ? ? ? swap(lock, key);
? ? } while (key);
? ? critical section;
? ? lock=0;
}
利用硬件指令能有效實現進程互斥，但卻不能滿足“讓權等待”準則，造成處理機時間的浪費，而且也很難將其用于解決較復雜的進程同步問題。
—————————————————————————————————————————————————————————————————
4.1.4 信號量機制
應用廣泛：單處理機系統、多處理機系統、計算機網絡
信號量的類型
·信號量分為： 互斥信號量 和 資源信號量
·互斥信號量用于申請或釋放資源的使用權，常初始化為1
·資源信號量用于申請或歸還資源，可以初始化為大于1的正整數，表示系統中某類資源的可用個數。
·wait操作用于申請資源（或使用權），進程執行wait原語時，可能會阻塞自己。
·signal操作用于釋放資源（或歸還資源使用權），進程執行signal原語時，有責任喚醒一個阻塞進程。
?
信號量的意義
·互斥信號量：申請/釋放使用權，常被初始化為1
·資源信號量：申請歸還資源，資源信號量可以初始化為一個正整數，表示系統中某類資源的可用個數。 S.count的意義為
>S.count >= 0 表示還可執行wait(S)而不會阻塞的進程數（可用資源）
>S.count < 0 表示S.queue隊列中阻塞進程的個數（被阻塞進程數）
?
S.count的取值范圍
·當僅有兩個并發進程共享臨界資源時，互斥信號量僅能取值 -1 0 1
其中S.count=1，表示無進程進入臨界區
S.count=0,表示已有一個進程進入臨界區
S.count=-1,表示已有一個進程正在等待進入臨界區
·當用S來實現n個進程互斥時，S.count的取值范圍為 ?1 ?-(n-1)
·操作系統內核以系統調用形式提供wait 和 signal原語，應用程序通過系統調用實現進程間的互斥。
P(S)=wait(S)
V(S)=signal(S)
·工程實踐證明，利用信號量方法實現進程互斥是高效的，一直被廣泛采用。
1、記錄型信號量機制
typedef struct{
? ? int value; ? ?//整型值，代表資源數目
? ? list of process *L; ?//鏈表，鏈接所有等待該信號量代表資源的進程
}semaphore;
兩個標準原子操作：wait(s)和signal(s) ? ?這兩個操作長期以來被稱為P、V操作。
原子性：執行過程不可中斷，即當一個進程在修改某信號量時，沒有其他進程可同時對該信號量進行修改。
void wait(static semaphore s)
{
? ? s.value--;
? ? if (s.value < 0) ?block(s.L);
}
void signal(static semaphore s)
{
? ? s.value++;
? ? if (s.value <= 0) ?wakeup(s.L);
}
s.value的初值表示系統中某類資源的數目，因為又稱為資源信號量。
每次wait操作意味著請求一個單位的資源，描述為s.value--；當s.value<0時，表示資源已分配完畢，用block原語進行自我阻塞，放棄處理機并插入到信號量鏈表s.L中。遵循“讓權等待”原則。此時，s.value的絕對值數代表在該信號量鏈表中。
每次signal操作，表示執行進程釋放一個單位資源，故s.value++；加1后若s.value<=0，則表示在該信號量鏈表中仍有等待該資源的進程被阻塞，故還應調用wakeup原語，喚醒進程訪問臨界資源。
信號量實現互斥
semaphore mutex=1;
void procedure1()
{
while(1)
{
wait(mutex);
critical section;
signal(mutex);
}
}
void procedure2()
{
while(1)
{
wait(mutex);
critical section;
signal(mutex);
}
}
main()
{
cobegin{
procedure1();
procedure2();
}
}
注意：wait(mutex)和signal(mutex)必須成對出現。
缺少wait(mutex)將導致系統混亂，不能保證對臨界資源的互斥訪問；
缺少signal(mutex)將會使臨界資源永遠不被釋放。
還可用信號量來描述程序或語句之間的前驅關系。
信號量初值為0
可利用信號量，按照語句的前趨關系，寫出一個可并發執行的程序。
main(){
semaphore a=b=c=d=e=f=g=0;
cobegin{
{T1; ?signal(a); ? ?signal(b);}
{wait(a); ?T2; ?signal(c); ?signal(d)}
{wait(b); ?T3; ?signal(e)}
{wait(c); ?T(4); ?signal(f)}
{wait(d); ?T(5); ?signal(g)}
{wait(e); ?wait(f); ?wait(g); ?T6}
}
2、信號量集機制
（1）AND型信號量集機制
上述互斥針對進程之間要共享一個臨界資源而言的。
在有些應用場合，一個進程需要先獲得兩個或更多的共享資源后方能執行任務。
process P:
wait(Amutex);
wait(Bmutex);
process Q:
wait(Bmutex);
wait(Amutex);
此種情況可能引起死鎖。
AND同步機制的基本思想是，將所需的所有臨界資源一次性全部分配給進程，該進程用完后一次性全部釋放。
對若干臨界資源的分配采取原子操作方式，要么全部分配，要么一個都不分配。
void Swait(s1, s2, ..., sn)
{
? ? if(s1>=1 && s2>=1 && ... && sn>=1)
? ? ? ? for(i=1; i<=n; ++i) ? ?
? ? ? ? ? ? si.value--;
? ? else
? ? ? ? Place the process in the awaiting queue associated with the si found with si<1,and set the program count of this count of this process to the beinning of Swait operation.
}
void Ssignal(s1, s2, ..., sn)
{
for(i=1; i<=n; ++i)
{
si.value++;
Remove all the process waiting in the queue associated with si into the ready queue;
}
(2)一般信號量集
上述信號量機制，只能對信號量進行加一減一操作。
擴充：
可以加n減n；
在小于某個值時，不分配。
void Swait(s1, t1, d1, s2, t2, d2, ..., sn, tn, dn)
{
if(s1>=t1 && s2>=t2 && ... && sn>=tn)
for(i=1; i<=n; ++i) ? ?
si.value-di;
else
Place the process in the awaiting queue associated with the si found with si<ti,and set the program count of this count of this process to the beinning of Swait operation.
}
void?Ssignal(s1, t1, d1, s2, t2, d2, ..., sn, tn, dn)
{
for(i=1; i<=n; ++i)
{
si.value+=di;
Remove all the process waiting in the queue associated with si into the ready queue;
}
幾種一般“信號量集”的特殊情況：
Swait(s,d,d)。信號量集中只有一個信號量，允許每次申請d個資源，當資源數少于d時，不予分配。
Swait(s,1,1)。退化為一般信號量（s>1）或互斥信號量(s==1)。
Swait(s,1,0)。開關型信號量。
———————————————————————————————————————————————————
4.1.5 管程機制
信號量機制對于每個要訪問臨界資源的進程都必須自備同步操作wait(s)和signal(s)，這使得大量的同步操作分散在各個進程中。這不僅給系統的管理帶來麻煩，還會因為同步操作的使用不當而導致死鎖。
把所有進程對某一種臨界資源的同步操作都集中起來，構成一個所謂的“秘書”進程。
凡要訪問該臨界資源的進程，都需要先報告“秘書”，有秘書來實現諸進程的同步。
把并發進程間的同步操作分別集中于相應的管程中。
系統中的各種硬件資源和軟件資源，均可用數據結構加以抽象描述，即用少量信息和對該資源所執行的操作來表征該資源，而忽略了它們的內部結構和實現細節。
當共享資源用共享數據結構表示時，資源管理程序可用對該數據結構進行操作的一組過程來表示，如資源的請求和釋放過程request和release。把這樣一組相關的數據結構和過程一并稱為管程。
一個管程定義了一個數據結構和能為并發進程所執行（在該數據結構上）的一組操作，這組操作能同步進程和改變管程中的數據。
管程分3部分：
1、局部于管程的共享變量說明；
2、對該數據結構進行操作的一組過程；
3、對局部于管程數據的數據設置初值的語句。
語法描述：
monitor monitor-name{
variable declarations
{ initialization code}
entry p1(...){...}
entry p2(...){...}
... ...
entry pn(...){...}
}
局部于管程的數據，僅能被局部于管程的過程所訪問，局部于管程的過程也僅能訪問管程內的數據結構。
管程相當于圍墻，每次只允許一個進程進入管程，從而實現進程互斥。
在利用管程實現同步時，必須設置兩個同步操作原語wait和signal。
當某進程通過管程請求臨界資源而未能滿足時，管程便調用wait原語使該進程等待，并將其排在等待隊列上。
僅當另一進程訪問完并釋放之后，管程調用signal原語喚醒等待隊列中的隊首進程。
管程中對每個條件變量都需予以說明，其形式為：“condition x,y;”，該變量應置于wait和signal之前，可表示為x.wait和x.signal。
x.signal操作的作用是重新啟動一個被阻塞的進程，但如果沒有進程被阻塞，則x.signal操作不產生任何后果，這與信號量機制中的signal操作不同。
——————————————————————————————————————————————————
1、生產者-消費者問題（producer-consumer）
有一群生產者進程在生產產品，并將此產品提供給消費者進程去消費。
并發進行，設置一個n個緩沖區的緩沖池。
不允許消費者到空緩沖區去取產品，也不允許生產者進程向一個已有產品，尚未取走的緩沖區投放產品。
in指示下一個可投放產品的緩沖區，生產者生產一個產品后，輸入指針加1，即in=(in+1)mod n；
out指示下一個可獲取產品的緩沖區，消費者消費一個產品后，輸出指針加1，即out=(out+1)mod n。
(in+1)mod n == out 時表示緩沖池滿；
in == out 時表示緩沖池空。
還引入了一個整型變量counter，初始值為0。生產者投放產品后，counter+1；消費者消費產品后，counter-1.
(1)利用記錄型信號量解決生產者-消費者問題
互斥信號量mutex實現諸進程對緩沖池的互斥使用
資源信號量empty表示空緩沖區的數量
資源信號量full表示滿緩沖區的數量
semaphore mutex=1, empty=n, full=0
item buffer[n];
int in=out=0;
void producer()
{
? ? while(1)
? ? {
? ? ? ? produce an item in nextp; //nextp代表產品
? ? ? ? wait(empty);
? ? ? ? wait(mutex);
? ? ? ? buffer[in]=nextp;
? ? ? ? in=(in+1)mod n;
? ? ? ? signal(mutex);
? ? ? ? signal(full);
? ? }
}
void consumer()
{
? ? while(1)
? ? {
? ? ? ? wait(full);
? ? ? ? wait(mutex);
? ? ? ? nextc=buffer[out];
? ? ? ? out=(out+1)mod n;
? ? ? ? signal(mutex);
? ? ? ? signal(empty);
? ? ? ? consume the item in nextc;
? ? }
}
main()
{
? ? cobegin{
? ? ? ? producer();
? ? ? ? consumer();
? ? }
}
注意以下幾點：
1、在每個程序中實現互斥的wait(mutex)和signal(mutex)應該成對出現；
2、對資源信號量empty和full的wait和signal操作，同樣需要成對出現，但它們分別處于不同的進程；
3、在每個進程中的wait操作不能顛倒。應先執行對資源信號量的wait操作，然后再執行對互斥信號量的wait操作，否則引起死鎖。
生產者放產品和消費者取產品無需互斥進行。
semaphore mutex1=1, mutex2=1, empty=n, full=0
item buffer[n];
int in=out=0;
void producer()
{
? ? while(1)
? ? {
? ? ? ? produce an item in nextp; //nextp代表產品
? ? ? ? wait(empty);
? ? ? ? wait(mutex1);
? ? ? ? buffer[in]=nextp;
? ? ? ? in=(in+1)mod n;
? ? ? ? signal(mutex1);
? ? ? ? signal(full);
? ? }
}
void consumer()
{
? ? while(1)
? ? {
? ? ? ? wait(full);
? ? ? ? wait(mutex2);
? ? ? ? nextc=buffer[out];
? ? ? ? out=(out+1)mod n;
? ? ? ? signal(mutex2);
? ? ? ? signal(empty);
? ? ? ? consume the item in nextc;
? ? }
}
main()
{
? ? cobegin{
? ? ? ? producer();
? ? ? ? consumer();
? ? }
}
(2)利用AND信號量解決生產者-消費者問題
semaphore mutex1=1, mutex2=1, empty=n, full=0
item buffer[n];
int in=out=0;
void producer()
{
? ? while(1)
? ? {
? ? ? ? produce an item in nextp; //nextp代表產品
? ? ? ? Swait(empty, mutex1);
? ? ? ? wait(mutex1);
? ? ? ? buffer[in]=nextp;
? ? ? ? in=(in+1)mod n;
? ? ? ? Ssignal(mutex1, full);
? ? }
}
void consumer()
{
? ? while(1)
? ? {
? ? ? ? Swait(full, mutex2);
? ? ? ? nextc=buffer[out];
? ? ? ? out=(out+1)mod n;
? ? ? ? Ssignal(mutex2,empty);
? ? ? ? consume the item in nextc;
? ? }
}
main()
{
? ? cobegin{
? ? ? ? producer();
? ? ? ? consumer();
? ? }
}
(3)利用管程解決生產者-消費者問題
monitor producer-consumer
{
? ? int in,out,count;
? ? item buffer[n];
? ? condition notfull, notempty;
? ? {in=out=0; count=0;}
? ? entry put(item)
? ? {
? ? ? ? if(count>=n) ?notfull.wait;
? ? ? ? buffer[in]=nextp;
? ? ? ? in=(in+1)mod n;
? ? ? ? count++;
? ? ? ? notempty.signal;
? ? }
? ? entry put(item)
? ? {
? ? ? ? if(count<=0)??notempty.wait;
? ? ? ? nextc=buffer[out];
? ? ? ? out=(out+1)mode n;
? ? ? ? count--;
? ? ? ? notfull.signal;
? ? }
}
void producer()
{
? ? while(1)
? ? {
? ? ? ? produce an item in nextp;
? ? ? ? producer-consumer.put(item);
? ? }
}
void consumer()
{
? ? while(1)
? ? {
? ? ? ? producer-consumer.get(item);
? ? ? ? consume the item in nextc;
? ? }
}
main()
{
? ? cobegin{
? ? ? ? producer();
? ? ? ? consumer();
? ? }
}
2、讀者寫者問題
對于數據對象
允許多個讀者進程同時訪問；只允許一個寫者進程互斥訪問。
即要么有多個讀者，要么只有一個寫者。
對于讀者寫者不同的優先權，可以有兩種變形：
第一類讀者寫者問題，讀者優先——讀者在讀，后續來的讀者可直接進入。可能導致寫者餓死。
第二類讀者寫者問題，寫者優先——寫者欲讀，所有后續讀者均等待。可能導致讀者餓死。
（1）利用記錄型信號量解決第一類讀者-寫者問題
semaphore rmutex=mutex=1;
int readcount=0;
void reader(int i)
{
? ? while(1)
? ? {
? ? ? ? wait(rmutex)
? ? ? ? if(readcount==0)
? ? ? ? ? ? wait(mutex);
? ? ? ? readcount++;
? ? ? ? signal(rmutex);
? ? ? ? perform read operation;
? ? ? ??
? ? ? ? wait(rmutex);
? ? ? ? readcount--;
? ? ? ? if(readcount==0)
? ? ? ? ? ? signal(mutex);
? ? ? ? signal(rmutex);
? ? }
}
void writer(int j)
{
? ? while(1)
? ? {
? ? ? ? wait(mutex);
? ? ? ? perform write operation;
? ? ? ? signal(mutex);
? ? }
}
mian()
{
? ? cobegin{
? ? ? ? reader(1);
? ? ? ? ...
? ? ? ? reader(n);
? ? ? ? writer(1);
? ? ? ? ...
? ? ? ? writer(n);
}
（2）利用記錄型信號量集機制解決第一類讀者-寫者問題
增加一條限制，最多允許RN個讀者同時讀。
#define RN
semaphore L=RN, mx=1;
void reader(int i)
{
? ? ? ? while(1)
? ? ? ? {
? ? ? ? ? ? ? ? Swait(L,1,1)
? ? ? ? ? ? ? ? Swait(mx,1,0); //起開關作用，只要無寫者進入（mx==1），讀者就可進入。
? ? ? ? ? ? ? ? perform read operation;
? ? ? ? ? ? ? ? signal(L,1);
? ? ? ? }
}
void writer(int j)
{
? ? while(1)
? ? {
? ? ? ? Swait(mx,1,1,L,RN,0; //僅當無寫者進程（mx==1），又無讀者進程（L=RN）時，寫者才進入?
? ? ? ? perform write operation;
? ? ? ? Signal(mx,1);
? ? }
}
mian()
{
cobegin{
reader(1);
...
reader(n);
writer(1);
...
writer(n);
}
（3）利用管程方法解決第二類讀者-寫者問題
monnitor reader-writer{
int rc, wc; //記錄讀進程和寫進程數
condition R,W;
{ rc=wc=0}
entry start_read
{
if wc>0 R.wait;
rc++;
R.signal;
}
entry end_read
{
rc--;
if rc=0 ? ?W.signal;
}
entry start_write
{
wc++;
if( rc>0 || wc>1) W.wait;
}
entry end_write
{
wc--;
if(wc>0) ? ?W.signal;
else ? R.signal;
}
}
Reader(int i)
{
? ? while(1)
? ? {
? ? ? ? reader_writer.start_read;
? ? ? ? reading;
? ? ? ? reader_writer.end_read;
? ? }
}
Writer(int j)
{
? ? while(1)
? ? {
? ? ? ? reader_writer.start_write;
? ? ? ? reading;
? ? ? ? reader_writer.end_write;
? ? }
}
mian()
{
cobegin{
reader(1);
...
reader(n);
writer(1);
...
writer(n);
}
3、哲學家進餐問題
5位哲學家，交替思考和進餐。
一張圓桌，桌上有5支筷子。
平時思考，饑餓時同時拿起左右兩只筷子即可進餐。
進餐完畢，放下筷子繼續思考。
semophore chopstick[5]={1,1,1,1,1};
wodi process(int i)
{
while(1)
{
wait(chopstick[i]);
wait(chopstick[(i+1)mod 5]);
eat;
signal(chopstick[i]);
signal(chopstick[(i+1)mod 5]);
think;
}
}
上述過程可能引起死鎖。
幾種解決方案：
1、最多允許4位哲學家同時進餐；
2、僅當兩支筷子都可用時，才允許拿起筷子進餐；
3、規定奇數哲學家先拿左邊筷子，偶數哲學家先拿右邊筷子。最后總有一個哲學家能獲得兩支筷子而進餐。
利用AND信號量機制解決哲學家進餐問題
semaphore chopstick[5]={1,1,1,1,1}
void process(int i)
{
while(1)
{
Swait(chopstick[(i+1)mod 5], chopstick[i]);
eat;
Ssignal(chopstic[(i+1)mod 5], chopstick[i]);
think;
}
}
main()
{
cobegin{
process(0);
process(1);
process(2);
process(3);
process(4);
process(5);
}
}
—————————————————————————————————————————————————————————
4.2 進程通信
進程通信是指進程之間的信息交換。少則是一個狀態或數值，多則是成千上萬個字節。
進程的互斥和同步時低級通信。
高級通信是指用戶可直接利用操作系統所提供的一組通信命令高效地傳送大量數據。
在高級通信方式中，操作系統隱藏了進程通信的實現細節，或者說通信過程對用戶是透明的。
4.2.1 進程通信的類型
三大類：共享存儲器系統、消息傳遞系統、管道通信系統
1、共享存儲器系統
相互通信的進程共享某些數據結構或共享存儲區。
（1）基于共享數據結構的通信方式。程序員負責公用數據結構設置和同步處理，低效，適合少量數據。
（2）基于共享存儲區的通信方式。高級通信，進程在通信前，向系統申請共享存儲區中的一個分區，并指定該分區的關鍵字；若系統已經給其它進程分配了這樣的分區，則將該分區的描述符返回給申請者。接著申請者把獲得的共享存儲分區連接到本進程上。此后，便可像讀、寫普通存儲器一樣地讀寫公用存儲區。
2、消息傳遞系統
進程間的數據交換以消息為單位。
直接利用系統提供的通信命令（原語）來實現通信。
操作系統隱藏了通信的實現細節，大大簡化了通信程序編制的復雜性，因而應用廣泛。
高級通信方式
（1）直接通信方式：
發送進程直接將消息發送給接受進程并將它掛在接受進程的消息緩沖隊列上，接受進程從消息緩沖隊列中取得消息。
（2）間接通信方式：
發送進程將消息發送到某種中間實體中，接受進程從中取得消息。這種中間實體稱為信箱。這種通信方式稱為信箱通信方式。
3、管道通信
管道是用于連接一個讀進程和一個寫進程以實現它們之間通信的共享文件，又稱為pipe文件。
寫進程以字符流的形式將大量的數據寫入管道，讀進程從管道讀取信息。
管道通信機制必須提供以下3方面的協調能力。
互斥、同步、判斷對方是否存在。
4.2.2 直接通信和間接通信
1、直接通信方式
直接通信方式是指發送進程利用操作系統所提供的發送命令直接把消息發送給目標進程。
此時，要求發送進程和接收進程都以顯示的方式提供對方的標識符。
通常系統提供下述兩條通信原語：
send(receiver, message);
receive(sender, message);
利用直接通信原語來解決生產者-消費者問題：
void producer()
{
while(1)
{
produce an item in nextp;
send(consumer, nextp);
}
}
void consumer()
{
? ? while(1)
? ? {
? ? ? ? receive(producer,nextc);
? ? ? ? consume the item in nextc;
? ? }
}
main(){
? ? producer();
? ? consumer();
}
2、間接通信方式
進程之間的通信需要通過作為某種共享數據結構的實體，該實體用來暫存發送進程發給目標進程的消息；接收進程從該實體中取出對方發送給自己的消息。通常把這種中間實體稱為信箱。
在邏輯上，信箱由信箱頭和包括若干信格的信箱體所組成，每個信箱必須有自己的唯一標識符。
利用信箱進行通信，用戶可以不必寫出接受進程標識符就可以向不知名的進程發送消息，且信息可以安全的保存在信箱中，允許目標用戶隨時讀取。
這種通信方式被廣泛地用于多機系統和計算機網絡中。
系統為信箱通信提供了若干條原語，用于信箱的創建、撤銷和消息的發送、接受。
信箱可由操作系統創建，也可由用戶進程創建。
分三類：私有信箱、公用信箱、共享信箱
發送進程和接收進程的四種關系：
一對一
多對一：客戶/服務器交互
一對多：廣播
多對多
4.2.3 消息緩沖隊列通信機制
send原語
receive原語
消息緩沖區：
struct message_buffer{
? ? sender; ?//發送者進程標識符
? ? size; ?//消息長度
? ? text; ?//消息正文
? ? next; ?//指向下一個緩沖區的指針
};
PCB中有關通信的數據項
struct processcontrol_block{
? ? mq; //消息隊列首指針
? ? mutex; ?//消息隊列互斥信號量
? ? sm; ?//消息隊列資源信號量
}
發送原語：
發送進程在利用發送原語發送消息之前應首先在自己的內存空間設置一發送區a，把待發送的消息正文、發送進程標識符、消息長度等信息傳入其中，然后調用發送原語，把消息發送給接收進程。
發送原語首先根據發送區a中所設置的消息長度a.size來申請一個緩沖區i，接著把發送區a的信息復制到消息緩沖區i中。
為了能將i掛在接收進程的消息隊列mq，上，應先獲得接收進程的內部標識符j，然后將i掛在j.mq上。
由于該隊列屬于臨界資源，故在執行insert操作的前后要分別執行wait和signal操作。
void send(receiver, a)
{
? ? getbuf(a.size, i); //根據a.size申請緩沖區
? ? i.sender=a.sender; ?//將a中的信息復制到緩沖區i中
? ? i.size=a.size;
? ? i.text=a.text;
? ? i.next=0;
? ? getid(PCB set, receiver, j); //獲得接收進程內部標識符j
? ? wait(j.mutex);
? ? insert(j.mq,i); ?//將消息緩沖區插入消息隊列
? ? singal(j.mutex);
? ? signal(j.sm);
}
接收原語：
接收原語進程調用接收原語receive(b)從自己的消息緩沖隊列mq中摘下第一個消息緩沖區i，并將其中的數據復制到以b為首地址的指定消息接收區內。
void receive(b)
{
? ? j=inernal.name; //j為接收進程的內部標識符
? ? wait(j.sm);
? ? wait(j.mmutex);
? ? remove(j.mq, i); ?//將消息隊列中第一個消息移出
? ? signal(j.mutex);
? ? b.sender=i.sender; ?//把消息緩沖區i中的信息復制到接收區b
? ? b.size=i.size;
? ? b.next=i.next;
}
————————————————————————————————————————————————————————
Massage Passing
·Enforce mutual exclusion
·Exchange information
send(destination, message)
receive(source, message)
?
?
Synchronization
·Sender and receiver may or may not be blocked( waiting for message)
·Blocking send, blocking receive
---Both sender and receiver are blocked until message is delivered.
---Called a rendezvous(緊密同步，匯合)
·Non-blocking send, blocking receive
---Sender continues processing such as sending messages as quickly as possible.
---Receive is blocked until the requested message arrives.
·Non-blocking send, non-blocking receive
---Neither part is required to wait.
?
Addressing 尋址
·Direct addressing
---Send primitive includes a specific identifier of the destination process.
---Receive primitive could know ahead of time which process a message is expected.
---Receive primitive could use source parameter to return a value when the receive operation has been performed.
?
·Indirect addressing
---Messages are sent to a shared data structure consisting of queues.
---Queues are called mailboxes.
---One process sends a message to the mailbox and the other process picks up the message from the mailbox.
Message Format
Header ? ? ? ? ? ? ? ? ? ? ? ??Body >Message Contents
>Message Type ? ?
>Destination ID
>Source ID
>Message Length
>Control Information
Mutual Exclusion
·若采用Non-blocking send, blocking receive
·多個進程共享mailbox mutex
若進程申請進入臨界區，首先申請從mutex郵箱中接受一條消息。
若郵箱空，則進程阻塞；若進程收到郵箱中的消息，則進入臨界區，執行完畢退出，并將該消息放回郵箱mutex。
該消息as a token(令牌)在進程間傳遞。
Massage Passing: Producer/Consumer Problem
·解決有限buffer ?Problem/Consumer Problem
·設兩個郵箱：
---May_consume：Producer存放數據，供Consumer取走（即buffer數據區）
---May_produce：存放空消息的buffer空間
?
