經典的程序同步問題

文章目錄

• 程序同步
• • 1、是什麼，主要任務，解決方式，基本概念
  • 2、兩種機制
  • 3、經典問題
  • • 3.1、生産者——消費者問題
    • • 3.1.1、問題描述
      • 3.1.2、設計
      • 3.1.3、實作
    • 3.2、哲學家進餐
    • • 3.2.1、問題描述
      • 3.2.2、設計
      • 3.2.3、實作
    • 3.3、讀者——寫者
    • • 3.3.1、問題描述
      • 3.3.2、設計
      • 3.3.3、實作

程序同步

1、是什麼，主要任務，解決方式，基本概念

是什麼： 在多道程式環境下，程序是并發執行的，不同程序之間存在着不同的互相制約關系。

主要任務： 對多個相關程序在執行次序上進行協調，使并發執行諸程序之間按照一定的規則（或時序）共享系統資源，并能很好地互相合作，進而使得程式的執行具有可再現性。

解決方式：

1. 保證多個程序采用互斥的方式通路臨界資源
2. 其次要協調互相合作的各個程序的執行次序

基本概念：

1. 同步和互斥：
   • 同步：指為了完成某個任務，建立多個程序，這些程序在合作的過程中而産生的互相制約的關系
   • 互斥：指某個程序對一臨界資源通路，其它程序等待的一種互相制約關系
2. 兩種制約關系：
   • 間接互相制約關系：由于共享系統資源，而導緻這些并發執行的成宿之間形成的制約的關系
   • 直接互相制約關系：由于多個程序之間的合作，而形成的制約關系
3. 臨界資源（臨界區）：隻一次隻允許一個程序使用的共享的資源稱之為臨界資源，把在每個程序通路臨界資源的那段代碼稱之為臨界區

2、兩種機制

信号量機制：

• 整型信号量
• 記錄型信号量
• 信号量集

管程機制： 管程是由局部于自己的若幹公共變量及其說明和所有通路這些公共變量的過程所組成的軟體子產品。

3、經典問題

3.1、生産者——消費者問題

3.1.1、問題描述

系統中有兩個程序，一個程序用于生産資源，一個程序用于消費資源。這兩個程序共享一塊大小确定的存放資源的區域（緩沖池）。

• 當區域内的資源沒有裝滿時，生産程序可以往裡面放資源；當區域内的資源滿時，生産程序需等待
• 當區域内的資源不為空時，消費程序可以從裡面取出資源；當區域内的資源為空時，消費程序需等待

3.1.2、設計

1、因為兩個程序之間的通路，不能同時進行，即生産程序放入資源時，消費程序不能取資源；消費程序取資源時，生産程序不能放入資源， 是以需要一個互斥信号量：mutex，初始值為1，表示程序能直接執行

2、生産程序需要判斷緩沖池是不是滿的，是以需要一個空緩沖區，empty，初始值為n,當空緩沖區為0時表示已經滿了

3、消費程序需要判斷緩沖池是不是空的，是以需要一個滿緩沖區，full，初始值為0，當滿緩沖區為0時，表示緩沖池中沒資料

3.1.3、實作

semaphore mutex=1,empty=n,full=0;
void producer(){
	do{
		wait(empty);		//如果empty<=0，等待；否則empty--
		wait(mutex);		//如果mutex<=0,等待；否則mutex--
		//生産
		signel(mutex);		//mutex++
		signel(full);		//full++
	}while(TRUE);
}

void consumer(){
	do{
		wait(full);			//如果full<=0，等待；否則full--
		wait(mutex);		//如果mutex<=0,等待；否則mutex--
		//生産
		signel(mutex);		//mutex++
		signel(empty);		//empty++
	}while(TRUE);
}

void main(){
	cobegin
		producer();consumer();
	coend
}
           

3.2、哲學家進餐

3.2.1、問題描述

一張圓桌上坐着五名哲學家，每兩名哲學家之間擺一根筷子，一共五根筷子，一個哲學家隻有左手右手都拿到一隻筷子才能進餐。進餐完畢，筷子放回原處。

3.2.2、設計

因為有五隻筷子，是以筷子為臨界資源，即chopstick[5]={1,1,1,1,1}；如代碼1。

問題： 假如五個哲學家，同時去拿左邊的筷子時，五個信号量将都會變為0，将永遠拿不到右邊的筷子，産生死鎖

改進：

1. 至多運作有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能進餐，可以增加一個信号量mutex，初始值為4
2. 僅當哲學家左右兩隻筷子都能用時，才允許他那契筷子進餐
3. 奇數哲學家先拿左邊的，偶數哲學家先拿右邊的

3.2.3、實作

代碼1（有可能引起死鎖）：

semaphore chopstick[5]={1,1,1,1,1};
void get(){
	do{
		wait(chopstick[i]);		
		wait(chopstick[(i+1)%5]);		
		//eat
		signel(chopstick[i]);		
		signel(chopstick[(i+1)%5]);		
	}while(TRUE);
}
           

代碼2：

semaphore chopstick[5]={1,1,1,1,1};
void get(){
	do{
		wait(mutex);
		wait(chopstick[i]);		
		wait(chopstick[(i+1)%5]);		
		//eat
		signel(chopstick[i]);		
		signel(chopstick[(i+1)%5]);	
		signel(mutex);	
	}while(TRUE);
}
           

3.3、讀者——寫者

3.3.1、問題描述

一個檔案可以被讀和被寫，多個程序操作這一個共享對象

• 因為讀操作不會引起檔案混亂，是以可以同時有多個程序讀
• 寫操作會引起檔案混亂，是以寫操作不允許和其他讀操作或者寫操作同時通路對象

3.3.2、設計

1. 因為可以有多個程序讀，是以寫入的時候，需要判斷目前是否還有程序在讀，如果有，則不能寫，等待，如果沒有，則可以寫入，是以需要一個讀緩沖池，readcount，初始值為0
2. 因為readcount是可以被一個或多個程序通路的臨界資源，是以針對以readcount應該設定一個互斥信号量rmutex，初始值為1
3. 因為寫入的時候，不允許其他操作，是以需要一個寫的互斥信号量wmutex，初始值為1

3.3.3、實作

semaphore rmutex=1,wmutex2=1;
int readcount=0;
void reader(){
	do{
		wait(rmutex);
		if(readcount==0)wait(wmutex);
		readcount++;
		signal(rmutex);
		//讀
		wait(rmutex);
		readcount--;
		if(readcount==0)signal(wmutex);
		signal(rmutex);
	}while(TRUE);
}

void writer(){
	do{
		wait(wmutex);
		//寫
		signal(wmutex);
	}while(TRUE);
}
void main(){
	cobegin
		reader();writer();
	coend
}