【操作系統】經典的同步問題(生產者消費者問題, 哲學家進餐問題, 讀寫問題)

用專業術語來說, 進程是程式的一次動態執行.說簡單點, 就是進程是系統中的某個任務.操作系統中有多個任務需要執行, 那麼怎樣執行才能使它們同步呢? 即如何讓任務併發執行互不影響呢? 這就引出了進程同步中的經典問題: 生產者消費者問題, 哲學家進餐問題, 讀寫問題生產者-消費者問題有一群生產者進程 ...

用專業術語來說, 進程是程式的一次動態執行.說簡單點, 就是進程是系統中的某個任務.操作系統中有多個任務需要執行, 那麼怎樣執行才能使它們同步呢? 即如何讓任務併發執行互不影響呢? 這就引出了進程同步中的經典問題: 生產者消費者問題, 哲學家進餐問題, 讀寫問題

生產者-消費者問題

有一群生產者進程在生產產品, 並將這些產品提供給消費者進程取消費. 為使生產者進程與消費者進程能併發進行, 在兩者間設置了一個具有n個緩衝區的緩衝池, 生產者進程將其所生產的產品翻入緩衝區中, 消費者進程可從一個緩衝區中取走產品取消費.生產者消費者進程都以非同步方式進行, 但它們之間必須保持同步, 不允許消費者進程到空緩衝區去取產品, 也不允許生產者進程向已滿的緩衝區投放產品.

一個緩衝池中有n個緩衝區, 只要緩衝池未滿, 生產者便可以投放產品; 緩衝池為空, 消費者便可以消費產品

法一:記錄型信號量

//生產者消費者問題
//記錄型信號量
//緩衝池中有n個緩衝區, 互斥信號量mutex, 
//信號量empty表示空緩衝區數量, full表示滿緩衝區的數量
int in = out = 0;
item buffer[n];
semaphore mutex = 1, empty = n, full = 0;
void producer() {
    do {
        producer an item nextp;
        wait(empty);
        wait(mutex);
        buffer[in] = nextp;
        in = (in + 1) % n;
        signal(mutex);
        signal(full);
    } while(true);
}
void consumer() {
    do {
        wait(full);
        wait(mutex);
        nextc = buffer[out];
        out = (out + 1) % n;
        signal(mutex);
        signal(empty);
        consumer the item in nextc;
    } while(true);
}
void main() {
    cobegin
        producer();
        consumer();
    coend
}

註意: 對信號量的wait()和signal()操作必定是成對出現的.

法二:AND型信號量

//AND型信號量
//Swait(empty, mutex)代替wait(empty)和wait(mutex)
//Ssignal(mutex,full)代替signal(mutext)和signal(full)
//Swait(full, mutex)代替wait(full)和wait(mutex)
//Ssignal(mutex, empty)代替signal(mutex)和signal(empty)
int in = out = 0;
item buffer[n];
semaphore mutex = 1, empty = n, full = 0;
void producer() {
    do {
        producer an item nextp;
        Swait(empty, mutex);
        buffer[in] = nextp;
        in = (in + 1) % n;
        Ssignal(mutex, full);
    } while(true);
}
void consumer() {
    do {
        Swait(full, mutex);
        nextc = buffer[out];
        out = (out + 1) % n;
        Ssignal(mutex, empty);
        consumer the item in nextc;
    } while(true);
}
void main() {
    cobegin
        producer();
        consumer();
    coend
}

法三: 管程

//管程
//建立管程producerconsumer,PC
/*
put(x), 生產者利用該過程將自己生產的產品投放到緩衝池中, 並用整型變數count表示緩衝池中已有的產品數目,當
count>=N時, 表示緩衝池已滿,生產者需等待.
get(x), 消費者利用該過程從緩衝池中取出一個產品, 當count<=0時, 表示緩衝池已無可用的產品, 消費者需等待
condition 為notfull和notempty
cwait(condition), 當管程被一個進程占用時, 其他進程調用該進程時阻塞, 並掛在條件condition的隊列上
csignal(condition), 喚醒在cwait執行後阻塞在條件condition隊列上的進程, 如果這樣的進程不止一個, 則選擇其中一個
實施喚醒操作, 如果隊列為空, 則無操作而返回.
*/
Monitor producerconsumer {
    item buffer[N];
    int in, out;
    condition notfull, notempty;
    int count;
    public:
        void put(item x) {
            if (count >= N) cwait(notfull);
            buffer[in] = x;
            in = (in + 1) % N;
            count++;
            ssignal(notempty);
        }
        void get(item x) {
            if (count <= 0) cwait(notempty);
            x = buffer[out];
            out = (out + 1) % N;
            count--;
            csignal(notfull);
        }
        {
            in = 0;
            out = 0;
            count = 0;
        }
}PC;

void producer() {
    item x;
    while (true) {
        producer an item in nextp;
        PC.put(x);
    }
}
void consumer() {
    item x;
    while (true) {
        PC.get(x);
        consumer the item in nextc;
    }
}
void main() {
    cobegin
        producer();
        consumer();
    coend
}

哲學家進餐問題

五個哲學家公用一張圓桌, 分別坐在周圍的五張桌子上, 在圓桌上有五個碗和五隻筷子交叉排列, 它們的生活方式是交替的進行思考和進餐. 哲學家進行思考時不用筷子, 饑餓時取一隻他兩邊的任意一隻筷子(預設取左邊的筷子, 沒有時取右邊的, 都沒有時就取不了), 當他有兩隻筷子時就能進餐. 進餐後, 放下筷子繼續思考.若只有一隻筷子, 不放棄該筷子並等待擁有另一隻筷子時再進餐.

用一個信號量表示一隻筷子, 共五個信號量 semaphore chopsitck[5] = {1, 1, 1, 1, 1}; , 為 1 表示筷子未拿起, 為0表示筷子被拿起.那麼第i為科學家的進餐活動就可以描述為

法一:記錄型信號量

do {
    wait(chopstick[i]);
    wait(chopstick[(i + 1) % 5]);
    //eat
    signal(chopstick[i]);
    signal(chopstick[(i + 1) % 5]);
    //think
} while (true);

假設五位哲學家都要拿筷子(都拿左手邊), 那麼將沒有人可以用餐, 就會陷入死鎖狀態.則哲學家進餐的解決方法:

1.至多允許四位哲學家拿同一邊的筷子, 則可讓至少一位哲學家先用餐, 用餐完後釋放筷子進而讓其他哲學家有機會用餐.

2.五位哲學家先競爭奇數(偶數)好筷子, 在競爭偶數(奇數)號筷子, 總會有一位哲學家能進餐.

法二: AND型信號量

//AND型信號量
semaphore chopstick[5] = {1, 1, 1, 1, 1};
do {
    //think
    Swait(chopsitck[(i + 1) % 5], chopsitck[i]);
    //eat
    Ssignal(chopsitck[(i + 1) % 5], chopsitck[i]);
} while (true);

讀者-寫者問題

一個數據文件或記錄可被多個進程所共用, 則我們稱這個文件或記錄為共用對象.讀文件的進程稱為Reader進程, 寫文件的進程稱為Writer進程.共用對象可以被多個Reader進程, 因為讀進程並不會破壞數據, 但是Writer進程在任何時刻只能有一個, 且須與其他對象互斥的訪問共用對象, 否則多個寫進程會造成衝突. 讀寫者問題即一個Writer進程必須與其他進程互斥的訪問共用對象.

設置寫互斥信號量wmutex

設置讀互斥信號量rmutex

整型變數readcount表示正在讀的進程數目(Reader)

當readcount!=0時, 表示有Reader進程,此時不能進行Writer進程.

法一:

//記錄型信號量
semaphore rmutext = 1, wmutext = 1;
int readcount = 0;
void Reader() {
    do {
        wait(rmutex);
        if (readcount == 0) {
            wait(wmutex);
        }
        readcount++;
        signal(rmutex);
        
        perform read operation;
        
        wait(rmutex);
        readcount--;
        if (readcount == 0) {
            signal(wmutext);
        }
        signal(rmutex);
    } while (true);
}

void Writer() {
    do {
        wait(wmutex);
        perform write operation;
        signal(wmutex);
    } while (true);
}
void main() {
    cobegin
        Reader();
        Writer();
    coend
}

法二:

引入RN, 表示最多允許RN個Reader進程同時讀

信號量L初始為RN

//信號量集
int RN;
semaphore L = RN, mx = 1;
void Reader() {
    do {
        Swait(L, 1, 1);
        Swait(mx, 1, 0);
        
        perform read operation;
        
        Ssignal(L, 1);
    } while (true);
}
void Writer() {
    do {
        Swait(mx, 1, 1; L, RN, 0);
        perform write operation;
        Ssignal(mx, 1);
    } while (true);
}

void main() {
    cobegin
        Reader();
        Writer();
    coend
}