軟、硬件方法解決進程互斥問題

一些概念:

1.臨界資源(critical resource)：系統(tǒng)中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源（或互斥資源）。

2.臨界區(qū)(互斥區(qū))(critical section(region))：各個進程中對某個臨界資源（互斥資源）實施操作的程序片段。

3.進程互斥（mutual exclusive）：由于各進程要求使用共享資源（變量、文件等），而這些資源需要排他性使用，因此各進程之間競爭使用這些資源，這一關(guān)系稱為進程互斥。

4.進程同步（synchronization）：指系統(tǒng)中多個進程中發(fā)生的事件存在某種時序關(guān)系，需要相互合作，共同完成一項任務(wù)。具體地說，一個進程運行到某一點時，要求另一伙伴進程為它提供消息，在未獲得消息之前，該進程進入阻塞態(tài)，獲得消息后被喚醒進入就緒態(tài)。

軟、硬件方法解決進程互斥問題:

1.軟件解法：

（1）.Dekker算法：

//進程P:
//...
pturn = true;
{
  if (turn == 2) 
  {
    pturn = false;
    while (turn == 2);
    pturn = true;
  } 
}
/*...
臨界區(qū)
...*/
turn = 2;
pturn = false;
//...

//進程Q:
//...
qturn = true;
while (pturn) 
{
  if (turn == 1) 
  {
    qturn = false;
    while (turn == 1);
    qturn = true;
  } 
}
/*...
臨界區(qū)
...*/
turn = 1;
qturn = false;
//...

（2）.Peterson算法：

#define FALSE 0
#define TRUE 1
#define N 2 // 進程的個數(shù)
int turn; // 輪到誰？ 
int interested[N];// 興趣數(shù)組，初始值均為FALSE

void enter_region ( int process)// process = 0 或 1 
{ 
  int other;// 另外一個進程的進程號 
  other = 1 - process; 
  interested[process] = TRUE;// 表明本進程感興趣 
  turn = process;// 設(shè)置標志位 
  while( turn == process && interested[other] == TRUE); //循環(huán)
}

void leave_region ( int process) 
{ 
  interested[process] = FALSE;// 本進程已離開臨界區(qū) 
}

//進程i：
//...
enter_region ( i );
/*...
臨界區(qū)
...*/
leave_region ( i );
//...

（雖然自選鎖在一定程度上會白白浪費CPU時間片，但是在多CPU的環(huán)境中，對持有鎖較短的程序來說，使用自旋鎖代替一般的互斥鎖往往能夠提高程序的性能。）

2.硬件解法：

有中斷屏蔽方法、“測試并加鎖”指令、“交換指令”等方法。

同步機制其一：信號量及P、V操作:

（1）.信號量：一個整數(shù)值，用于進程間傳遞信息。

struc semaphore
{
  int count;
  queueType queue;
}

對信號量可以施加的操作只有三種：初始化、P和V。

（2）.P、V操作：均為原語操作

semaphore s = 1；
//一種實現(xiàn)方式
P(s) //P操作，又叫down或semWait操作
{
  s.count --;
  if (s.count < 0)
  {
    /*  
    該進程狀態(tài)置為阻塞狀態(tài)；
    將該進程插入相應(yīng)的等待隊列s.queue末尾；
    重新調(diào)度；
    */
  }
}

V(s)//V操作，又叫up或semSignal操作
{
  s.count ++;
  if (s.count < = 0)
  {
    /*
    喚醒相應(yīng)等待隊列s.queue中等待的一個進程；
    改變其狀態(tài)為就緒態(tài)，并將其插入就緒隊列；
    */
  }
}

最初提出的是二元信號量（解決互斥），之后推廣到一般信號量（多值）或計數(shù)信號量（解決同步）。

用信號量解決問題:

1.生產(chǎn)者——消費者問題：

#define N 100 //緩沖區(qū)個數(shù)
typedef int semaphore; //信號量是一種特殊的整型數(shù)據(jù)
semaphore mutex =1; //互斥信號量：控制對臨界區(qū)的訪問
semaphore empty =N;  //空緩沖區(qū)個數(shù)
semaphore full = 0; //滿緩沖區(qū)個數(shù) 

void producer(void) //生產(chǎn)者進程
{ 
  int item; 
  while(TRUE) 
  { 
    item=produce_item(); 
    P(&empty); 
    P(&mutex); 
    insert_item(item); //臨界區(qū)
    V(&mutex) 
    V(&full); 
  } 
}

void consumer(void) //消費者進程
{ 
  int item;
  while(TRUE) 
  {
    P(&full);
    P(&mutex);
    item=remove_item();//臨界區(qū)
    V(&mutex);
    V(&empty);
    consume_item(item);
  }
}
//兩個P操作的順序不能顛倒，會引起死鎖，
//V操作的順序可以顛倒，但是會引起臨界區(qū)擴大等問題。

2.讀者——寫者問題：

問題概述：多個進程共享一個數(shù)據(jù)區(qū)，這些進程分為兩組：讀者進程——只讀數(shù)據(jù)區(qū)中的數(shù)據(jù)，寫者進程——只往數(shù)據(jù)區(qū)寫數(shù)據(jù)。允許多個讀者同時執(zhí)行讀操作；不允許多個寫者同時操作；不允許讀者、寫者同時操作。

第一類——讀者優(yōu)先：

讀者執(zhí)行：當無其他讀、寫者時；

當有其他讀者在讀時；

寫者執(zhí)行：當無其他讀、寫者時；

typedef int semaphore;
int rc = 0; //reader counter,共享變量
semaphore rw_mutex = 1;//讀寫臨界區(qū)保護鎖
semaphore rc_mutex = 1;//有多個讀者時，rc是我們?nèi)藶橐M的一個
                       //臨界區(qū)資源，也需要提供鎖保護
//讀者進程：
void reader(void)
{
  while (TRUE) 
  {
    P(rc_mutex);//對rc上鎖
    rc = rc + 1;
    if (rc == 1) //如果是第一個讀者
      P(rw_mutex);//對讀寫臨界區(qū)上鎖
    V(rc_mutex);//對rc操作完畢，解鎖
    read();//讀寫臨界區(qū)，讀操作
    P(rc_mutex);
    rc = rc - 1;
    if (rc == 0) //如果是最后一個讀者
      V(rw_mutex);//釋放讀寫臨界區(qū)
    V(rc_mutex);
}

void writer(void)
{
  while (TRUE) 
  {
    P(rw_mutex);
    write();
    V(rw_mutex);
  }
}

另外兩類——寫者優(yōu)先、公平競爭：

多進程對共享資源互斥訪問及進程同步的經(jīng)典問題

設(shè)有一文件F，多個并發(fā)讀進程和寫進程都要訪問，要求：

讀寫互斥

寫寫互斥

允許多個讀進程同時訪問

采用記錄型信號量機制解決

較常見的寫法：

semaphore fmutex=1, rdcntmutex=1;
//fmutex --> access to file; rdcntmutex --> access to readcount
int readcount = 0;
void reader(){
    while(1){
        wait(rdcntmutex);
        if(0 == readcount)wait(fmutex);
        readcount = readcount + 1;
        signal(rdcntmutex);
        //Do read operation ...
        wait(rdcntmutex);
        readcount = readcount - 1;
        if(0 == readcount)signal(fmutex);
        signal(rdcntmutex);
    }
}
void writer(){
    while(1){
        wait(fmutex);
        //Do write operation ...
        signal(fmutex);
    }
}

讀進程只要看到有其他讀進程正在訪問文件，就可以繼續(xù)作讀訪問；寫進程必須等待所有讀進程都不訪問時才能寫文件，即使寫進程可能比一些讀進程更早提出申請。所以以上解法實際是 讀者優(yōu)先 的解法。如果在讀訪問非常頻繁的場合，有可能造成寫進程一直無法訪問文件的局面....

為了解決以上問題，需要提高寫進程的優(yōu)先級。這里另增加一個排隊信號量：queue。讀寫進程訪問文件前都要在此信號量上排隊，通過區(qū)別對待讀寫進程便可達到提高寫進程優(yōu)先級的目的。另外再增加一個 writecount 以記錄提出寫訪問申請和正在寫的進程總數(shù)：

semaphore fmutex=1, rdcntmutex=1, wtcntmutex=1, queue=1;
//fmutex --> access to file; rdcntmutex --> access to readcount
//wtcntmutex --> access to writecount
int readcount = 0, writecount = 0;
void reader(){
    while(1){
        wait(queue);
        wait(rdcntmutex);
        if(0 == readcount)wait(fmutex);
        readcount = readcount + 1;
        signal(rdcntmutex);
        signal(queue);
        //Do read operation ...
        wait(rdcntmutex);
        readcount = readcount - 1;
        if(0 == readcount)signal(fmutex);
        signal(rdcntmutex);
    }
}
void writer(){
    while(1){
        wait(wtcntmutex);
        if(0 == writecount)wait(queue);
        writecount = writecount + 1;
        signal(wtcntmutex);
        wait(fmutex);
        //Do write operation ...
        signal(fmutex);
        wait(wtcntmutex);
        writecount = writecount - 1;
        if(0 == writecount)signal(queue);
        signal(wtcntmutex);
    }
}

每個讀進程最開始都要申請一下 queue 信號量，之后在真正做讀操作前即讓出(使得寫進程可以隨時申請到 queue)。而只有第一個寫進程需要申請 queue，之后就一直占著不放了，直到所有寫進程都完成后才讓出。等于只要有寫進程提出申請就禁止讀進程排隊，變相提高了寫進程的優(yōu)先級。

通過類似思想即可實現(xiàn)讀寫進程的公平競爭：

semaphore fmutex=1, rdcntmutex=1, queue=1;
//fmutex --> access to file; rdcntmutex --> access to readcount
int readcount = 0;
void reader(){
    while(1){
        wait(queue);
        wait(rdcntmutex);
        if(0 == readcount)wait(fmutex);
        readcount = readcount + 1;
        signal(rdcntmutex);
        signal(queue);
        //Do read operation ...
        wait(rdcntmutex);
        readcount = readcount - 1;
        if(0 == readcount)signal(fmutex);
        signal(rdcntmutex);
    }
}
void writer(){
    while(1){
        wait(queue);
        wait(fmutex);
        signal(queue);
        //Do write operation ...
        signal(fmutex);
    }
}

讀進程沒變，寫進程變成在每次寫操作前都要等待 queue 信號量。

課本上一般只會寫第一種解法吧?？戳撕髢煞N方法即可發(fā)現(xiàn)，在第一個解法中，fmutex 信號量實際是雙重身份，首先實現(xiàn)對文件的互斥訪問，其次起到了和后面排隊信號量 queue 相同的作用，只不過在那種排序下只能是讀者優(yōu)先。如果直接看過后兩種解法，應(yīng)該會有更清楚的理解吧。

同步機制其二：管程機制:

1.管程：由關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及在其上操作的一組過程組成（進程只能通過調(diào)用管程中的過程來間接地訪問管程中的數(shù)據(jù)結(jié)構(gòu)），是一種高級同步機制。

2.管程兩個重要特性：

管程是互斥進入的：為了保證管程中數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)完整性，管程的互斥性是由編譯器負責保證的。

管程中設(shè)置條件變量及等待/喚醒操作（wait/signal）：可以讓一個進程或線程在條件變量上等待（此時，應(yīng)先釋放管程的使用權(quán)），也可以通過發(fā)送信號將等待在條件變量上的進程或線程喚醒

3.分類：

P進入管程，執(zhí)行等待操作并釋放管程互斥權(quán)，此時Q進入管程，喚醒P進程，管程中就有了兩個活動進程，根據(jù)對這種情況的處理，分為：

Hoare管程：Q（喚醒者）等待，P（被喚醒者）執(zhí)行；

MESA管程：P等待Q繼續(xù)執(zhí)行；

Hansen管程：規(guī)定喚醒操作為管程中最后一個可執(zhí)行操作。

4.Hoare管程簡介：

?

因為管程是互斥進入的，所以當一個進程試圖進入一個已被占用的管程時，應(yīng)當在管程的入口處等待，為此，管程的入口處設(shè)置一個進程等待隊列，稱作入口等待隊列。

如果進程P喚醒進程Q，則P等待Q執(zhí)行；如果進程Q執(zhí)行中又喚醒進程R，則Q等待R執(zhí)行；……，如此，在管程內(nèi)部可能會出現(xiàn)多個等待進程，在管程內(nèi)需要設(shè)置一個進程等待隊列，稱為緊急等待隊列，緊急等待隊列的優(yōu)先級高于入口等待隊列的優(yōu)先級。

條件變量——在管程內(nèi)部說明和使用的一種特殊類型的變量（定義一個條件變量c，var c:condition;）。

對于條件變量，可以執(zhí)行wait和signal操作：

wait(c)： 如果緊急等待隊列非空，則喚醒第一個等待者；否則釋放管程的互斥權(quán)，執(zhí)行此操作的進程進入c鏈末尾。

signal(c)： 如果c鏈為空，則相當于空操作，執(zhí)行此操作的進程繼續(xù)執(zhí)行；否則喚醒第一個等待者，執(zhí)行此操作的進程進入緊急等待隊列的末尾。

?