作業系統-3——并發：互斥和同步

一、基本概念

• 原子操作：一個函數（原語）或動作的指令序列不可分割，要麼作為一個整體執行（不可中斷），要麼都不執行。
• 臨界資源：一次僅允許一個程序獨自占有使用的不可剝奪資源。
• 臨界區：程序通路臨界資源的那一段代碼。
• 互斥：當一個程序正在臨界區中通路臨界資源時，其他程序不能進入臨界區。
• 同步：合作的并發程序需要按先後次序執行。例如：一個程序的執行依賴于合作程序的消息或信号。當一個程序沒有得到來自合作程序的消息或信号時需阻塞等待，直到消息或信号到達才喚醒。
• 死鎖：多個程序全部阻塞，形成等待資源的循環鍊。
• 饑餓：一個就緒程序被排程程式長期忽視、不被排程執行。
• 信号量：用于程序間傳遞信号的一個整數。在信号兩上隻可以進行三種操作，即初始化，遞增，遞減。這三種操作分别都是原子操作。遞減作用于阻塞一個程序，遞增作用于解除一個程序的阻塞。信号量也稱為計數信号量或一般信号量。

二、互斥

1、互斥的要求

• 強制互斥（忙則等待）：一次隻允許一個程序進入臨界區。有程序正在臨界區執行時，其他請求程序等待；等待程序退出後，從多個請求程序中選擇一個進入臨界區。
• 有限等待：請求程序應在有限的等待時間内進入臨界區，不能造成程序死鎖或饑餓。
• 有空讓進：當臨界區空閑時，請求程序可立即進入。
• 讓權等待：程序不能進入臨界區時，應釋放處理器，避免忙等。

？#一個正在通路臨界資源的程序由于申請等待I/O操作而被中斷時，它可以允許其他程序搶占處理器，但是不能進入相關臨界區。

2、用硬體實作中斷

• 中斷禁用
• 專用機器指令

3.信号量（☆☆☆☆☆）

• 信号量：不要求忙等的同步互斥工具。
• 一種信号量表示一種資源。信号量的值表示可用資源的個數。
• 當資源不可用時，程序将阻塞（避免忙等）（加入阻塞隊列），直到另一程序釋放資源時才被喚醒。
• 信号量s隻能被下面的兩個原語通路：

            #semWait(s)                也稱作P(s)操作，wait(s)            ——本程序請求配置設定一個資源

            #semSignal(s)              也稱作V(s)操作，signal(s)         ——本程序釋放一個資源

        ·semWaits(s)、semSignal(s)操作必須成對出現。

        ·用于互斥時，位于同一程序内，臨界區前後。

        ·用于同步時，交錯出現于兩個合作程序内。

        ·多個semWait()的次數不能颠倒，否則可能導緻死鎖。用于同步的semWait(s1)應出現在用于互斥的semWait(s2)之前。

        ·多個semSignal()操作的次序可任意。

struct	semaphore {
	
	int count;
	queueType queue;
};

void semWait(semaphore s){
	s.count--;
	if(s.count < 0){
		/*把目前程序插入隊列*/
		/*阻塞目前程序*/
	}
}

void semSignal(semaphore s){
	s.count++;
	if(s.count <= 0){
		/*把程序p從隊列中移除*/
		/*把程序p插入就緒隊列*/
	}
	
}
           

#用于互斥時，s的初值為1，取指為1~-(n-1)。

•     s=1時：有一個臨界資源可用，一個程序可進入臨界區。
•     s=0時：臨界資源已配置設定，一個程序已進入臨界區。
•     s<0時：臨界區已被占用，|s|個阻塞程序正在等待進入。

#用于同步時，s初值将>=0

•     s>=0：可用資源個數（或可進入臨界區的程序個數）。
•     s<0    :  該資源的等待隊列長度（阻塞程序個數）。

#強信号量：喚醒一個阻塞程序并移出阻塞隊列時，采用FIFO移出政策的信号量。

#弱信号量：喚醒一個阻塞程序并移出阻塞隊列時，采用随機選擇移出政策的信号量。

#用信号量實作互斥：

const int n = /*程序數 */;
semaphore s =1;/*s的初值=1*/
void P(int i){	/*程序Pi*/
	while(true){
		semWait(s);
		/*臨界區*/
		semSignal(s);
		/*其他部分*/
	}
}
void main(){/*n個程序并發*/
	parbegin(P(1),P(2),...,P(n));
}
           

#用信号量實作同步：

semaphore s =0;/*s的初值=0*/
Process	P1:
do{
	......
	代碼段A；
	semSignal(s);
}
Process P2:
do{
	semWait(s)
	代碼段B；
	......
}
           

4.生産者/消費者問題

• 一組生産者程序和一組消費者程序共用一個有sizeofbuffer個緩沖區的緩沖池來交換資料（有限緩沖）。
• 資源，限制條件及信号量的設定

        #緩沖池一次隻能讓一個程序通路。（互斥）

            設一信号量s，初值為1。

        #生産者需要空緩沖來發送資料。（同步）

            設一信号量empty，初值為sizeofbuffer。

        #消費者需要滿緩沖來擷取資料。（同步）

            設一信号量full，初值為0。

void producter(){
	while(true){
		semWait(empty);
		semWait(s);
		/*把資料送到緩沖區*/
		semSignal(s);
		semSignal(full);
	}
}

void consumer(){
	while(true){
		semWait(full);
		semWait(s);
		/*從緩沖區取出資料*/
		semSignal(s);
		semSignal(empty);
	}
}
           

5.讀者/寫者問題

有一個共享的資料對象：

• 允許多個讀者程序同時讀；
• 一次隻允許一個寫者程序寫；當一個寫者正在寫時，不允許其他任何讀者或寫者同時通路該共享對象。

1.讀者優先

• 當至少已有一個讀者正在讀時，随後的讀者直接進入，開始讀資料對象，但寫者将等待。
• 但一個寫者正在寫時，随後到來的讀者和寫者都等待。
• 信号量的設定：

#一次隻能讓一個寫者或一頓讀者通路資料。

    設一互斥信号量wsem，初值為1。

#正在讀資料的讀者數目由全局變量readcount表示（初值=0），它被多個讀者互斥通路。

（第1個讀者需對資料加鎖，最後1個讀者對資料解鎖）

           為readcount設一互斥信号量x，初值為1。

void reader(){
	while(true){
		semWait(x);
		readcount++;
		if(readcount == 1)
			semWait(wsem);
		semSignal(x);
		/*讀資料對象*/
		semWait(x);
		readcount--;
		if(readcount == 0)
			semSignal(wsem);
		semSignal(x);
	}
}

void  writer(){
	while(true){
		semWait(wsem);
		/*寫資料對象*/
		semSignal(wsem);
	}
}
           

2.寫者優先

當一個寫者聲明想寫時，不允許新的讀者進入資料對象，隻需要等到已有的讀者讀完即可開始寫。可以避免寫者饑餓。

（具體實作略，有時間再補充）

6.管程

管程是由一個或多個過程、一個初始過程、一個初始化序列和局部資料組成的軟體子產品。主要特點如下：

• 局部資料變量隻能被管程的過程通路，任何外部過程都不能通路。
• 一個程序通過調用管程的一個過程進入管程。
• 在任何時候，隻能有一個程序在管程中執行，調用管程的任何其他程序都被阻塞，以等待管程可用。

（個人了解：管程就是将semWait()和semSignal()和共享資料封裝起來，使得隻能通過調用管程裡的相應函數才能實作其功能。這樣子做好處在于避免了程序有意/無意的互斥/同步錯誤。）

• 條件變量（condition variable）

    #表示程序正在等待的資源或原因。隻用于維護等待隊列，但沒有相關聯的值。

• 有兩個函數可以操作條件變量：

    #cwait(c):條件不滿足時，調用cwait(c)的程序被放在條件變量c的等待隊列中阻塞。

    #csignal(c):喚醒一個條件變量為c的阻塞程序。

管程實作互斥/同步

7.消息

略（有時間再補充）