一些概念:

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

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

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

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

軟、硬件方法解決進(jìn)程互斥問題:

1.軟件解法：

（1）.Dekker算法：

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

//進(jìn)程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 // 進(jìn)程的個(gè)數(shù)
int turn; // 輪到誰？ 
int interested[N];// 興趣數(shù)組，初始值均為FALSE

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

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

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

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

2.硬件解法：

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

同步機(jī)制其一：信號(hào)量及P、V操作:

（1）.信號(hào)量：一個(gè)整數(shù)值，用于進(jìn)程間傳遞信息。

struc semaphore
{
  int count;
  queueType queue;
}

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

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

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

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

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

用信號(hào)量解決問題:

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

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

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

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

2.讀者——寫者問題：

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

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

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

當(dāng)有其他讀者在讀時(shí)；

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

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

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

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

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

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

讀寫互斥

寫寫互斥

允許多個(gè)讀進(jìn)程同時(shí)訪問

采用記錄型信號(hào)量機(jī)制解決

較常見的寫法：

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);
    }
}

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

為了解決以上問題，需要提高寫進(jìn)程的優(yōu)先級(jí)。這里另增加一個(gè)排隊(duì)信號(hào)量：queue。讀寫進(jìn)程訪問文件前都要在此信號(hào)量上排隊(duì)，通過區(qū)別對待讀寫進(jìn)程便可達(dá)到提高寫進(jìn)程優(yōu)先級(jí)的目的。另外再增加一個(gè) writecount 以記錄提出寫訪問申請和正在寫的進(jìn)程總數(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);
    }
}

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

通過類似思想即可實(shí)現(xiàn)讀寫進(jì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);
    }
}

讀進(jìn)程沒變，寫進(jìn)程變成在每次寫操作前都要等待 queue 信號(hào)量。

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

同步機(jī)制其二：管程機(jī)制:

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

2.管程兩個(gè)重要特性：

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

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

3.分類：

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

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

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

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

4.Hoare管程簡介：

?

因?yàn)楣艹淌腔コ膺M(jìn)入的，所以當(dāng)一個(gè)進(jìn)程試圖進(jìn)入一個(gè)已被占用的管程時(shí)，應(yīng)當(dāng)在管程的入口處等待，為此，管程的入口處設(shè)置一個(gè)進(jìn)程等待隊(duì)列，稱作入口等待隊(duì)列。

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

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

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

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

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

?