1 背景

同步互斥回顧:

并發問題: 競爭條件(競態條件)

• 多程序并發存在大量問題

同步

• 多線程共享公共數據的協調執行
• 包括互斥與條件同步
• 互斥: 在同一時間只有一個線程可以執行臨界區

確保線程同步

• 需要高層次的編程抽象(如: 鎖)
• 從底層硬件支持編譯

2 信號量

信號量是抽象數據類型

• 信號量用一個整形(sem)表示, 具有兩個原子操作
• P(): sem減1, 如果sem < 0, 等待, 否則繼續
• V(): sem加1, 如果sem <= 0, 喚醒一個等待的P

3 信號量使用

3.1 信號量的一些屬性

• 信號量是整數(有符號)
• 信號量是被保護的變量

• 初始化完成后, 唯一改變一個信號量的值的辦法是通過P()和V()
• 操作必須是原子

• P()能夠阻塞, V()不會阻塞
• 我們限定信號量是"公平的"

• 沒有線程被阻塞在P()仍然阻塞如果V()被無限頻繁調用(在同一個信號量)
• 在實踐中, FIFO(先阻塞先被喚醒)經常被使用(如果只能喚醒一個進程)(忙等的鎖沒有這種先等先喚醒機制)

?3.2 信號量的實現簡介

信號量實現一般有兩種:

• 二進制信號量: 可以是0或1
• 一般/計數信號量: 可取任何非負值
• 兩者互相表現(給定一個可以實現另一個)

信號量可以用在兩個方面:

• 互斥
• 條件同步(調度約束 -- 一個線程等待另一個線程的事情發生)

用二值信號量實現互斥功能:

mutex = new Semaphore(1); //初始化一個值為1的信號量作為一個鎖mutex->P(); //信號量減1 //執行臨界區代碼, 此時如果有其他線程要進入臨界區, 也需要mutex->P(), 也就會讓信號量的值為-1, //也就會被阻塞 mutex->V(); //信號量加1

用二值信號量實現同步:

condition = new Semaphore(0);// Thread A condition->P() //A線程等待condition->V()// Thread B condition->V() //B線程喚醒, 也就是同步

用計數信號量還可以實現生產者 - 消費者問題:

有界緩沖區(buffer)的生產者 - 消費者問題, 有以下性質:

• 一個或多個生產者產生數據將數據放在一個緩沖區(buffer)里
• 單個消費者每次從緩沖區取出數據
• 在任何一個時間只有一個生產者或消費者可以訪問該buffer

這個問題用互斥(鎖機制)是不夠的.

而且具有正確性要求:

• 在任何一個時間只能有一個線程操作buffer(互斥)
• 當buffer為空, 消費者必須等待生產者(調度/同步約束)
• 當緩存區滿, 生產者必須等待消費者(調度同步約束)

根據以上要求和性質:

如果每個約束用一個單獨的信號量, 有以下信號量設計:

• 二進制信號量互斥
• 一般信號量fullBuffers
• 一般信號量emptyBuffers?

代碼設計:

class BoundedBuffer{mutex = new Semaphore(1);fullBuffers = new Semaphore(0);emptyBuffers = new Semaphore(n); }BoundedBuffer::Deposit(c) {emptyBuffers->P(); //需保證buffer還有空閑, 如果無空閑, 則等待mutex->P(); //要保證對buffer的操作的互斥性Add c to the buffer;mutex->V();fullBuffers->V(); //有數據進入 }BoundedBuffer::Remove(c) {fullBuffers->P(); //需保證buffer有數據, 如果無數據, 則等待mutex->P(); //要保證對buffer的操作的互斥性Remove c from buffer;mutex->V();emptyBuffers->V(); //取出數據 }

4 信號量實現

針對信號量的P()和V()操作的實現, 需要使用硬件原語:

• 禁用中斷
• 原子指令(Test - And - Set)

具體實現:

class Semaphore{int sem;WaitQueue q; }Semaphore::P(){sem --;if (sem < 0) {Add this thread t to q;block(p);} }Semaphore::V(){sem ++;if (sem <= 0) {Remove a thread t from q;wakeup(t);} }

實現中需要注意的細節:

• 信號量的雙用途

• 互斥和條件同步
• 但等待條件是獨立的互斥

• 讀/開發代碼比較困難

• ?程序員必須非常精通信號量

• 容易出錯

• 使用的信號量已經被另一個線程占用
• 忘記釋放信號量?

• 不能夠處理死鎖問題

5 管程

管程的目的:

分離互斥和條件同步的關注

什么是管程:

• 一個鎖: 指定臨界區
• 0或者多個條件變量: 等待/通知信號量用于管理并發訪問的共享數據

一般方法:

• 收集在對象/模塊中的相關共享數據
• 定義方法來訪問共享數據

簡單步驟:

獲取進入管程的鎖從而進入管程

管程中對共享資源進行操作

當需要等待時候, 信號量調用wait自身睡眠并把進入管程的鎖進行釋放

當資源得到滿足, 信號量會調用signal從而喚醒正在這個信號量睡眠的線程

條件變量的實現:

class Condition{int numWaiting = 0;WaitingQueue q; }Condition::Waiting(lock){numWaiting ++;Add this thread to q;release(lock);schedule(); //need mutex, 選擇下一個線程去執行require(lock) }Condition::Signal(){if (numWaiting > 0) {Remove a thread t from q;wakeup(t); //need mutex, 把該線程置為ready狀態numWaiting --;} }

管程實現生產者 - 消費者問題:

• 需要維持每個條件隊列
• 線程等待的條件等待signal()

class BoundedBuffer{Lock lock;int count = 0;Condition notFull, notEmpty; }BoundedBffer::Deposit(c){lock->Acquire();while(count == n)notFull.Wait(&lock);Add c to the buffer;count ++;notEmpty.Signal();lock->Release(); }BoundedBuffer::Remove(c){lock->Acquire();while(count == 0)notEmpty.Wait(&lock);Remove c from buffer;count --;notFull.Signal();lock->Release(); }

6 經典同步問題

6.1 讀者 - 寫者問題

問題動機:

共享數據的訪問

兩種類型的使用者:

• 讀者: 不需要修改數據
• 寫者: 讀取和修改數據

問題的約束:

• 允許同一時間有多個讀者, 但在任何時候只有一個寫者
• 當沒有寫者時讀者才能訪問數據
• 當沒有讀者和寫者時寫者才能訪問數據
• 在任何時候只能有一個線程可以操作共享變量

設計思路:

• 需要有以下共享數據:

• 數據集, 也就是要進行讀或者寫的數據
• 信號量CountMutex初始化為1
• 信號量WriteMutex初始化為1
• 整數Rcount初始化為0(正在執行讀操作的數量)

?6.1.1 讀者優先

基于讀者優先策略的方法: 只要有一個讀者處于活動狀態, 后來的讀者都會被接納. 如果讀者源源不斷出現的話, 那么寫者就始終處于阻塞狀態.

• 寫操作: Writer

sem_wait(WriteMutex); //相當于WriteMutex->P(), 保證只有一個線程在執行寫操作, 以及在寫操作過程中沒有讀操作write;sem_post(WriteMutex); //相當于WriteMutex->V()

• 讀操作: Reader

sem_wait(CountMutex); //保證對Rcount操作的互斥性 if(Rcount == 0)sem_wait(WriteMutex); //說明此時沒有讀操作, 是有可能有寫操作的, 所以需要等待寫操作結束 ++ Rcount; sem_post(CountMutex);read;sem_wait(CountMutex); -- Rcount;if (Rcount == 0)sem_post(WriteMutex);sem_post(CountMutex);

6.1.2 寫者優先

基于寫者優先策略的方法: 一旦寫者就緒, 那么寫者會盡可能快地執行寫操作. 如果寫者源源不斷地出現的話, 那么讀者就始終處于阻塞狀態.

需要的變量:

• AR = 0? ? ? ? ? ? ? ? ? ? ? ? //active readers正在執行讀操作的線程個數
• AW = 0? ? ? ? ? ? ? ? ? ? ? ? //active writers正在執行寫操作的線程個數
• WR = 0? ? ? ? ? ? ? ? ? ? ? ? //waiting readers正在等待讀操作的線程個數
• WW = 0? ? ? ? ? ? ? ? ? ? ? ? //waiting writers正在等待寫操作的線程個數
• Condition okToRead
• Condition okToWrite
• Lock lock

讀操作:

Read(){//wait until no writersstartRead();read database;//check out - wake up waiting writers;doneRead(); }startRead(){lock.Acquire();while ((AW + WW) > 0) { //如果有寫者, 寫者優先WR ++;okToRead.wait(&lock);WR --;}AR ++;lock.release(); }doneRead(){lock.Acquire();AR --;if (WW > 0 && AR == 0) { //需要喚醒等待的寫者okToWrite.signal();}lock.Release(); }

寫操作:

Write() {//Wait until no readers/writersstartWrite();write database;//check out - wake up waiting readers/writers;doneWrite(); }startWrite(){lock.Acquire();while((AR + AW) > 0) { //需要等待正在寫或者讀的操作結束后WW ++;okToWrite.wait(&lock);WW --;}lock.Release(); }doneWrite() {lock.Acquire();AW --;if (WW > 0) {okToWrite.signal();} else if (WR > 0) {okTORead.broadcast();}lock.Acquire(); }

• 6.2 哲學家就餐問題

問題描述(1965年由Di jkstra首先踢出并解決):

5個哲學家圍繞一張圓桌而坐, 桌子上放著5支叉子, 每兩個哲學家之間放一支; 哲學家的動作包括思考和進餐, 進餐時需要同時拿起他左邊和右邊的兩支叉子, 思考時則同時將兩支叉子放回原處. 如何保證哲學家們的動作有序進行? 如: 不會出現有人永遠拿不到叉子.

共享數據:

• bowl of rice(data set)
• Semaphore fork[5] initialized to 1

思路:

• 必須有數據結構, 來描述每個哲學家的當前狀態

#define N 5 //哲學家個數 #define LEFT i //第i個哲學家的左鄰居 #define RIGHT (i + 1) % N //第i個哲學家的右鄰居 #define THINKING 0 //思考狀態 #define HUNGRY 1 //饑餓狀態 #define EATING 2 //進餐狀態 int state[N]; //記錄每個人的狀態

• 該狀態是一個臨界資源, 每個哲學家對它的訪問應該互斥地進行 -- 進程互斥

semaphore mutex; //互斥信號量, 初值1

• 一個哲學家吃飽后, 可能要喚醒它的左鄰右舍, 兩者之間存在著同步關系 -- 進程同步

semaphore s{N}; //同步信號量, 初值0

• 函數philosopher定義(哲學家流程定義)

void philosopher(int i){ //i的取值: 0到N - 1, 代表著第幾個哲學家while(true){ //封閉式循環think();take_forks(i); //拿到兩把叉子或被阻塞eat();put_forks(i); //把兩把叉子放回原處} }

• 函數take_forks的定義

void take_forks(int i){ //i的取值: 0到N - 1P(mutex); //進入臨界區state[i] = HUNGRY;test_take_left_right_forks(i); //試圖拿兩把叉子V(mutex); //退出臨界區P(s[i]); //沒有叉子便被阻塞 }void test_take_left_right_forks(int i) {if (state[i] == HUNGRY &&state[LEFT] != EATING &&state[RIGHT] != EATING) {state[i] = EATING;V(s[i]); //通知第i個人可以拿起左右叉子吃飯了} }

• 函數put_forks定義

//功能: 把兩把叉子放回原處, 并在需要的時候, //去喚醒左鄰右舍 void put_forks(int i){P(mutex);state[i] = THINKING; //交出兩把叉子//提醒左右鄰居其相鄰狀態有改變, 讓其從阻塞態恢復, 重新執行循環檢查test_take_left_right_forks(LEFT);test_take_left_right_forks(RIGHT);V(mutex); }

總結

以上是生活随笔為你收集整理的操作系统信号量和管程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。