程序間的通信

程序間的通信
- 程序間的通信
- 競争條件
- 臨界區
- 忙等待的互斥
  - 屏蔽中斷
  - 鎖變量
  - 嚴格輪換法
  - Dekker算法與Peterson算法
  - TSL指令
- 優先級反轉
- 睡眠與喚醒
- 信号量
- 管程
- 消息傳遞
- 屏障

1. 程序間的通信

需要關注的問題：

一個程序如何把消息傳遞給另一個
確定兩個或更多程序在關鍵活動中不會出現交叉
確定兩個程序的輸出為正确的順序

後兩個問題同樣适用于線程間的通信，而第一個問題對于線程來說很容易，因為同一個程序中的線程共享一個位址空間。

2. 競争條件

兩個或多個程序讀寫某些共享資料，而最後的結果取決于程序運作的精确時序。

在一些作業系統中，協作的程序可能共享一些彼此都能讀寫的共用存儲區。例如，列印程式。當一個程序需要列印一個檔案，它将檔案名放在一個目錄中。列印機存在一個程序周期性的檢查是否有檔案需要列印。假設目錄中有很多位置，不同的位置由數字0，1，2，…，來差別，每個位置放一個檔案名。同時假設有兩個共享變量：out，指向下一個要列印的檔案；in，指向目錄中下一個空閑位置。在某一時刻，0至3号位置為空（即檔案列印完畢），而4到6号位置被占用（有排等待列印的檔案）。幾乎在同一時刻，程序A,B都決定要列印一個檔案。此時A讀到in的值為7，将7存在A的局部變量中。此時時鐘中斷，CPU認為程序A運作了足夠的時間切換到程序B。程序B讀取in，值也為7，B也将7存在自己的局部變量中。此時A，B都想要把檔案防止在位置7列印。是以會存在覆寫動作，而哪個檔案會被列印，則取決于A，B接下來的運作順序。

3. 臨界區

想要避免競争條件，使用互斥可以達到這個目的。

互斥：以某種手段確定當一個程序在使用一個共享變量或檔案時，其他程序不能做同樣的操作。

我們把對共享記憶體進行通路的程式片段稱為臨界區。而通過互斥，我們可以使兩個程序不能同時處在臨界區中，以此來避免競争條件。它需要滿足以下4個條件：

任何兩個程序不能同時處于其臨界區。
不應對CPU的速度和數量做任何建設。
臨界區外運作的程序不得阻塞其他程序。
不得使程序無限期等待進入臨界區。

4. 忙等待的互斥

1. 屏蔽中斷：

在單處理器系統中，最簡單的方法就是使每個程序在剛剛進入臨界區後立即屏蔽所有中斷，并在就要離開之前在打開中斷。但此方法存在很多問題：

把屏蔽中斷的權利交給使用者程序不明智，有可能再也不打開中斷，則系統會是以中止。
屏蔽中斷僅僅對執行disable（屏蔽中斷）指令的那個CPU有效，對于多處理器系統，其它CPU會繼續運作，依然存在同時通路共享記憶體。

2. 鎖變量：

設定一個共享鎖變量，其初始值為0。當一個程序想要進入臨界區時，首先測試這把鎖。如果該鎖值為0，則該程序将其設定為1并進入臨界區。如果這把鎖的值已經為1，則該程序将等待直到值變為0。于是。0表示臨界區内沒有程序，1表示已經有程序進入臨界區。

type Lock_Tokern is mod ;  
Lock: Lock_Tokern := ;

task body P is
begin   
  loop
    -- non_critical_section --
    loop exit when Lock = ; end loop;
    Lock := Lock + ;
    -- critical_section --
  end loop;
end P;

但是這個方法并不能解決問題，試想當A程序檢查鎖變量為0時結束循環，而恰在此時程序B将A打斷，同時檢查到此時鎖值依然為0，則B也可以跳出循環，這樣兩個程序就可以同時進入臨界區。

3. 嚴格輪換法：

設定一個整型變量turn，初始值為0，用于記錄哪個程序進入臨界區，并檢查或更新共享記憶體。當turn為0時，程序0可以進入臨界區并将turn值置為1，當turn值為1時，程序1可以進入臨界區并将turn值置為0。

type Turn_Token is mod ;
Turn : Turn_Token := ;

task body P0 is
begin
  loop
    -- non_critical_section --
    loop exit when Turn = ; end loop;
    -- critical_section --
    Turn := Turn + ;
  end loop;
end P0;

task body P1 is
begin
  loop
    -- non_critical_section --
    loop exit when Turn = ; end loop;
    -- critical_section --
    Turn := Turn + ;
  end loop;
end P1;

存在的問題是，程序連續測試一個變量直到某個值出現為止，這被稱為忙等待(busy waiting)。這種方式非常浪費CPU。用于忙等待的鎖，稱為自旋鎖。而且這個方法違反了上文提到的條件2，即程序被臨界區之外的程序阻塞(loop)。

4. Dekker算法與Peterson算法

參見：并發問題-互斥（Dekker算法和Peterson算法）

5. TSL指令

TSL即為Test and Lock。需要硬體支援。讀寫操作被保證為不可分割，即該指令結束前其他處理器均不允許通路該記憶體字。執行TSL指令的CPU将鎖住記憶體總線，以禁止其他CPU在本指令結束之前通路記憶體(不等于屏蔽中斷,屏蔽中斷對其他CPU無效)。

type Flag is Natural range ;
C : Flag := ;

task body Pi is 
L : Flag;
begin
  loop
    loop
      [L := C; C:= ];
      exit when L = ;
    end loop;
    -- critical_section --
    C := ;
  end loop;
end Pi; 

task body Pj is 
L : Flag;
begin
  loop
    loop
      [L := C; C:= ];
      exit when L = ;
    end loop;
    -- critical_section --
    C := ;
  end loop;
end Pj;

中括号中的操作為原子操作。

一種相似的方法是用原子交換操作，替代原子指派操作。

type Flag is Natural range ;
C : Flag := ;

task body Pi is 
L : Flag ：= ；
begin
  loop
    loop
      [Temp := L; L := C; C := Temp];
      exit when L = ;
    end loop;
    -- critical_section --
    L := ; C := ;
  end loop;
end Pi; 

task body Pj is 
L : Flag;
begin
  loop
    loop
      [Temp := L; L := C; C := Temp];
      exit when L = ;
    end loop;
    -- critical_section --
    L := ; C := ;
  end loop;
end Pj;

這兩個方法都有忙等待的缺點。

5. 優先級反轉

當使用需要忙等待的方法時，如果程序間存在優先級關系，如H享有高優先級，L享有低優先級，當L在臨界區中運作時，H就緒并準備進入臨界區，開始忙等待，由于H優先級過高，L不會被排程，永遠無法離開臨界區，是以H将永遠忙等待下去

6. 睡眠與喚醒

使用程序間通信原語，他們在無法進入臨界區時将被阻塞，而不是忙等待。

sleep：是一個将引起調用程序阻塞的系統調用，即被挂起，直到被另外一個程序喚醒。

wakeup：調用要被喚醒的程序。

7. 信号量

一個可以取值為0或者正數的值。并有兩種操作，P和V，且檢查數值、修改變量值、以及可能發生的睡眠操作均為一個單一的，不可分割的原子操作。進而保證了當一個信号量開始操作時，其他程序無法修改信号量。主要是要保證不可分割的方式實作它，因為操作信号量時間很短是以屏蔽所有中斷是可行的

一般信号量用于保持在0至指定最大值之間的一個計數值。當線程完成一次對該semaphore對象的等待(wait)時，該計數值減一；當線程完成一次對semaphore對象的釋放(release)時，計數值加一。當計數值為0，則線程等待該semaphore對象不再能成功直至該semaphore對象變成signaled狀态。semaphore對象的計數值大于0，為signaled狀态；計數值等于0，為non-signaled狀态.

計數信号量具備兩種操作動作，之前稱為 V(稱signal())與 P(又稱wait())。V操作會增加信号量 S的數值，P操作會減少它。

運作方式：

初始化，給與它一個非負數的整數值。
運作 P(又稱wait())，信号量S的值将被減少。企圖進入臨界區塊的程序，需要先運作 P(wait())。當信号量S減為負值時，程序會被擋住，不能繼續；當信号量S不為負值時，程序可以獲準進入臨界區塊。
運作 V(又稱signal(()，信号量S的值會被增加。結束離開臨界區塊的程序，将會運作 V(signal())。當信号量S不為負值時，先前被擋住的其他程序，将可獲準進入臨界區塊。

var mutex : semaphore := ;

Process P1;
  statement X;
  wait(mutex);
    statement Y;
  signal(mutex);
  statement Z;
end P1; 

Process P2;
  statement A;
  wait(mutex);
    statement B;
  signal(mutex);
  statement C
end P2;

A->B->C; X->Y->Z; [X,Z|A,B,C]; [A,C|X,Y,Z]; ![B|Y] 以上表達式可以解釋為
    1. A，B，C 三個操作按順序執行。
    2. X，Y，Z 三個操作按順序執行。
    3. X，Z 操作可以與A，B，C操作并發執行。
    4. A，C 操作可以與X，Y，Z操作并發執行。
    5. B，Y操作永遠不可能并發執行。

互斥量：隻有兩種狀态的信号量。（加鎖，解鎖）。在使用者線程中，沒有時鐘停止的情況下，也可以使用。因為不存在忙等待。取鎖失敗時，就放棄CPU給另一個線程。下次運作時，重新對鎖進行測試

以上方法對于線程是沒問題的，因為他們享有公共位址空間。但對于程序可以有兩種方法解決

1）将一些共享資料結構，如信号量，存放在核心中，并且隻能通過系統調用通路

2）讓程序與其他程序共享部分位址空間，如果沒有共享途徑，則使用共享檔案

條件變量經常與互斥量一起使用。被阻塞的線程常常是在等待發信号的線程做某些工作，釋放某些資源而隻有滿足條件變量後，被阻塞的線程才可以繼續運作。條件變量允許這種等待與阻塞原子性地進行。條件變量不會存在記憶體中。如果将一個信号量傳遞給一個沒有線程在等待的條件變量，這個信号會丢失。

8. 管程

管程是一個由過程，變量及資料結構等組成的一個集合，他們組成一個特殊的子產品或軟體包。程序可以在任何需要的時候調用管程中的過程，但它們不能再管程之外聲明的過程中直接通路管程内的資料結構。任一時刻管程中隻能有一個活躍程序，是以可以優先完成互斥。管程是語言概念，即程式設計語言的組成部分，編譯器知道它們的特殊性。當一個程序調用管程時，先檢查在管程中是否有其他活躍程序，如果有，調用程序将被挂起。進入管程的互斥是由編譯器負責的。

引入條件變量使得程序在無法繼續運作時被阻塞。當一個管程過程發現它無法繼續運作時則在某個條件變量上執行wait操作。該操作導緻調用程序自身阻塞。并且将另一個以前等在管程之外的程序調入管程。如果要喚醒正在睡眠的程序，則使用signal指令，為保證互斥，使用完signal語句的程序需要立即退出管程，是以signal語句隻可能作為一個管程過程的最後一條語句。wait操作必須在signal之前，因為條件變量無法累計。

詳見：信号标與管程

9. 消息傳遞

以上這些機制都是用來解決通路公共記憶體的一個或多個CPU上的互斥問題的。如果一個分布式系統具有多個CPU并且每個CPU有自己的私有記憶體，那麼這些機制将失敗。

為了解決這個問題，可以使用消息傳遞這種方法，在這種方法中可以使用兩種原語send和receive

send(destination, &message)，向一個指定目标發送一條消息

receive(source, &message)從一個給定源接收一條消息。如果沒有消息可用，則接收者可能被阻塞，直到一條消息到達，或者傳回一個錯誤。

可以用這種方法解決生産者-消費者問題。消費者首先将N條空消息發送給生産者。當生産者向消費者傳遞一個資料項時，取走一個空消息，并送回一條填充了内容的消息。為避免生産者産生資訊速度過快被阻塞，可以引入一種資料結構，來對消息進行緩沖。目的是容納那些已經發送但尚未被接收的資訊。

#define N 100                      //緩沖區中的槽數目

void producer(void){
  int item;
  message m;                      //消息緩沖區

  while(TRUE){
    item = produce.item();        //産生放入緩沖區的資料
    receive(consumer, &m);        //等待消費者發送空緩沖區
    build_message(&m, item);      //建立一個待發送的消息
    send(consumer, &m)            //發送資料給消費者
  }
}

void consumer(void){
  int item, i;
  message m;

  for(i = ;i < N;i++)
    send(producer, &m);           //發送N個空緩沖區

  while(True){
    receive(producer, &m);        //接收包含資料項的消息
    item = extract_item(&m);      //将資料項從消息中提取出來
    send(producer, &m);           //将空緩沖區發送回生産者
    consume_item(item);           //處理資料項
  }
}

10. 屏障

在某些應用中劃分了若幹階段，除非所有程序都就緒才可以進行下一階段否則任何程序都不可以進入下一階段。要實作這個目的，可以再每個階段結尾安置屏障。當一個程序到達屏障時會被阻攔，直到所有程序到達屏障為止。

參考書目：現代作業系統第三版，分布式系統原理與範型第二版

[作業系統] 程序間的通信程序間的通信

程序間的通信

1. 程序間的通信

2. 競争條件

3. 臨界區

4. 忙等待的互斥

1. 屏蔽中斷：

2. 鎖變量：

3. 嚴格輪換法：

4. Dekker算法與Peterson算法

5. TSL指令

5. 優先級反轉

6. 睡眠與喚醒

7. 信号量

8. 管程

9. 消息傳遞

10. 屏障

繼續閱讀

WIN10下指令行禁用編輯模式

Linux指令行下載下傳檔案和安裝RAR

使用 Windows 指令行删除結果

Win10系統怎麼開啟Linux Bash指令行？

Linux指令行通配符

windows和linux下使用指令行執行jmeter

sip presence , subscribe 和 notify 中文

終端環境之tmux

【Tomcat】Tomcat參數調優:連接配接數和并發數

[Linux] diff 查找檔案的異同

作業系統（python）多程序學習

ACS基本配置-權限等級管理

傳說FreeBSD等比Linux更穩定，更“健壯”

無人機--飛控科普

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins