# Operating System #6_2

## Deadlock

* 一個或多個process無止境地等待某個在waiting中的process。
* 彼此等候，沒有任務實際在工作。
* 

## Starvation

* 低優先度的process不斷被高優先度的搶去工作機會，永遠無法被執行。

## Priority Inversion

* 當任務排程沒有做好時，可能讓低優先度的process佔有高優先度的資源，進而導致執行順序反過來的情況。

## Bounded-Buffer Problem

* 問題：請設計一個大小`N`的Buffer存放Processes的鎖，也就是說一次最多只有`N`個Processes可以工作的結構。

//Producer 
do { // produce an item in nextp
    wait (empty);
    wait (mutex);
    // add the item to the buffer
    signal (mutex);
    signal (full);
} while (TRUE);

//Consumer
do {
    wait (full);
    wait (mutex);
// remove an item from buffer to nextc
    signal (mutex);
    signal (empty);
// consume the item in nextc
} while (TRUE);

* full預設為`0`、empty預設為`N`、mutex預設為`1`。

## Readers-Writers Problem

* 問題：我們需要設計一個用於讀寫的鎖，讀取可以一次一個或多個一起讀，而寫入一次只能有一個寫入；當然，不可以同時讀取和寫入。
* 

## Dining-Philosophers Problem

* 問題：在圓桌上的五人，左右兩邊都各有一枝筷子。他們都必須同時拿到左右的筷子才能吃飯。吃完後他們會將筷子放回去並開始思考，等候下一次吃飯。請模擬出這樣的鎖。

While (TRUE) {
wait (chopstick[i]);
wait (chopstick[(i+1)%5]);
// eat
signal (chopstick[i]);
signal (chopstick[(i+1)%5]);
// think
}

* 如果五人都同時拿起了右邊/左邊的筷子，就會造成死結。
* 為了避免這種狀況，簡單的解決方法就是不同的位置拿不同邊，奇數拿右邊、偶數拿左邊等等。

## Monitor

* Monitor是一種高階程式語言的結構，利用Private變數來保護需要共享的資源。
* Monitor一樣擁有Mutual exclusion的特性，一次只有一個process在Monitor裡面。
* 在裡面有`condition variable`，並有兩個methods可以去使用它：
* x.wait(): 使用的process會被掛起(暫停？)。
* x.signal(): 回復一個被wait()的process。
* 在程序`P`使用signal()叫醒`Q`之後，有兩種選擇：
* Signal and wait: `Q`立刻搶占Monitor，`P`去某個地方等待。
* Signal and continue: `P`繼續做直到它完成，`Q`則去某個地方等待。
* 程序在Monitor中，可能會處於以下四種狀態：
* Active: 執行中
* Entering: 被Monitor擋住
* Waiting: 等候condition variable
* Inactive: 等候執行的程序完成

## Semaphore VS monitor

* monitor就像一個公共廁所，一次只能有一個人在裡面處理事情，藉由鎖保護裡面，裡面有人的時候其他人無法進入。
* 而Semaphore像是一個Ubike停車場，大家都可以去，如果有車你就可以使用，沒有的話你就得等待他人用完還車。

###### tags: `note`