作業系統面試—程序同步

本文是基于作業系統概念（第七版）第六章的學習總結，不足之處歡迎批評指正。

一、什麼是臨界區問題？

臨界區是指在該區域中，程序可能改變共同變量、更新一個表、寫一個檔案等。如果多個程序進入臨界區進行修改，那麼将會引起混亂。

典型程序的通用結構：

do{

進入區；

   臨界區；

退出區；

  剩餘區；

}while(true)；

臨界區問題的解答必須滿足下面三個要求：

1、互斥。一個程序在臨界區執行，那麼其他程序是不允許進入的。

2、前進。若臨界區沒有程序執行，那麼其他想進入的程序可以進行選擇。

3、有限等待。

二、處理作業系統的臨界區問題：

1、搶占核心——适合實時程式設計，搶占核心的響應更快。

2、非搶占核心——從根本上來說不會引起競争。

三、peterson算法（這是一種基于軟體的臨界區問題的解答）

flag——表示哪個程序想要進入臨界區。

turn——表示哪個程序可以進入臨界區。

下面是程序pi的結構：

do{

flag[i]=true;

turn=j;

while(flag[i]&&turn==j);

臨界區；

flag[i]=false;

剩餘區； 

}while(true);

說明：當i想進入臨界區但是不允許進入臨界區，那麼程式就一直進行while循環，進入不了臨界區。如果此時turn==i，即i可以進入臨界區了，那麼程序i進入臨界區，但是此時程序j是進入不了臨界區的。執行完畢後，重新設定程序i，含義為此時i不想進入臨界區了。peterson算法的關鍵在于借助了turn這個變量，大家慢慢體會。

四、硬體同步

采用鎖的臨界區問題的解答

do{

請求鎖；

 臨界區；

釋放鎖；

 剩餘區；

}

這裡我們将用簡單硬體指令來解決臨界區問題。

單處理系統——在修改共享變量是禁止中斷出現即可。

多處理系統——上面的方法不可行，因為要将消息傳遞給多處理器，費時。

幸運的是，現代計算機系統大多數提供了特殊硬體指令以原子地檢查和修改字的内容或者交換兩個字的内容。

什麼是原子地？

原子操作即不可中斷。

第一個指令testandset（）——指令的作用是傳回lock的bool值，并設定其為true。是以如果原來為true,則隻是簡單傳回，否則要設定從false->true。

bool testandset(bool *lock){

  bool temp=*lock;

  *lock=true;

  return temp;

}

那麼如何利用testandset()來實作互斥呢？

初始化一個全局變量lock，初始化為false；需要說明的lock為false，代表沒有上鎖，是以資源可用。

為什麼需要将lock設定為true呢，是以如果程序進入了，那麼需要上鎖，進而使得其他程序進入不了臨界區。

do{

while(testandset(&lock));

臨界區；

lock=false;

剩餘區；

}while(true);

第二個指令——swap()

void swap(bool* a, bool *b){

   bool temp;

   temp=*a;

   *a=*b;

    *b=temp;

}

那麼如何利用swap()來實作互斥呢？

聲明一個全局變量lock，初始化為false，并且每個程序中有一個局部bool變量key。

do{

key=true;

while(key==true) swap(&lock,&key);

臨界區；

lock=false;

}while(true);

首先lock為false，資源可用，執行swap指令之後，lock=true,資源上鎖，key=false；這裡我覺得若key一直為false，那麼程序會一直執行臨界區，是以在剩餘去肯定會對key進行重新設定。

但是上面兩個操作雖然解決互斥問題，但并未解決有限等待問題，可能一個程序會一直運作許多次，而另一個等待程序一直在等待。是以可對testandset指令進行改進，

首先引入兩個全局變量：

bool waiting[n];

bool lock;

waiting[i]=false變量代表級程序無需等待，可以進入臨界區，waiting[i]=true，則表示需要等待。每一次隻有一個waiting被設定為false，以滿足互斥要求。key的作用是實作無限循環。

隻有第一個程序進入時才會發現key==false（testandset的作用），之後lock被設定為true，是以其他程序都必須等待。當程序進入臨界區執行完之後，會查找其他是否有其他程序想進入臨界區，若沒有，則直接釋放鎖，否則将找到的程序waiting設定為false,這樣這個程序就可以進入臨界區了。是以任何等待臨界區的程序最多隻需要等待n-1次，因為是循環等待。

do{

waiting[i]=true;

key=true;

while(waiting[i]&&key)

    key=testandset(&lock);

waiting[i]=true;

臨界區；

j=(i+1)%n;

while(j!=i&&!waiting[j]) j=(j+1)%n;

if(j==i)

lock=false;

esle

waiting[j]=false;

剩餘區；

}while(true);

五、信号量

信号量的引入原因：由于基于硬體的臨界區問題的解決方案對于程式員而言，使用比較複雜。

信号量s是個整數變量，除了初始化外，隻能通過兩個原子操作來通路，wait()和signal(),即P,V操作。

wait操作的定義：

s可以了解為現可用資源的數量，s<=0代表沒有資源可以使用。wait（）——擷取資源，signal（）——釋放資源。

wait(s){

while(s<=0);

s--;

}

signal(s){

s++;

}

通常os區分計算信号量和二進制信号量，計數信号量不受值域限制，二進制信号量的值隻能為0或者1。

二進制信号量又稱為互斥鎖。下面程式就可以使用二進制信号量實作n個程序的臨界區問題。

do{

wait(mutex);

臨界區；

signal(mutex);

剩餘區；

}while(true);

六、信号量的實作

上述信号量的主要缺點：忙等待，即任何想進入臨界區的程序必須在進入代碼中進行連續循環。這種類型的信号量也成為自旋鎖，這是因為程序在等待鎖是還在運作。

為了克服忙等待，那麼如何做呢？

程序不是忙等待，而是阻塞自己，阻塞操作将一個程序放入信号量相關的等待隊列中，并将該程序的狀态切換成等待狀态，這樣就是忙等待了。

修改原來原來wait和signal的定義：

typedef struct{

int value;

struct process* list;

}semaphore;

每個信号量都有一個整型值和一個程序連結清單，signal會從等待程序連結清單中取一個喚醒。

wait(semaphore* s){

s->value--;

if(s->value<0){

将該程序插入等待程序連結清單中，

block()；——挂起程序。

}

}

signal(semaphore* s){

s->value++;

if(s->value<=0){

從等待程序連結清單中移除程序p;

wakeup(p)；——喚起程序p到就緒隊列中。

}

}

死鎖和饑餓現象：

死鎖：兩個或多個程序無限地等待一個事件，而這個事件又是由這些等待程序中的一個産生，是一種互相等待的現象。具體死鎖問題和算法将在下一篇博文中介紹。