# midterm 3 Chp 6~8
###### tags: `EXAM`
## 107
### 1.必考
* Any solution to solve a critical section problem must satisfy three requirements.Please explain the three requirements.(%) Explain how does Peterson solution satisfy the three requirements.(%)
* Ans.
[Ch6. P.11](https://hackmd.io/n2EJ6aRJSLO1Qdup1jTBgQ#P.11)
1. **Mutual Exclusion**
- 任一時間點，只允許一個 process 進入他自已的 critical section 內活動。
2. **Progress**
- 選擇進入critical section的程序不能永久被推遲
- 必須在有限的時間從想進入 critical section 的 process 中，挑選其中一個 process 進入 critical section，隱含**No Deadlock**。
3. **Bounded Waiting**
- 自 process 提出進入 critical section 的申請到獲准進入 critical section 的等待時間是有限的。
- 若有 n 個 processes 想進入，則任一 process 至多等待 n-1 次即可進入
- **避免starvation**
* 參考答案
### 2.
Please insert acquire lock and release lock into the functions producer() and
consumer() to protect critical sections with the best performance.
``` c
void producer(){
while(1){
while(counter == BUFFER_SIZE);
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
acquire();//add here
counter++;
release();//add here
}
}
void consummer(){
while(1){
while(counter == 0) ;
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
acquire();//add here
counter--;
release();//add here
}
```
### 3.
The OS TAs wrote a simple code to simulate the Dining philosophers problem with pthread. The following code is their code. Please check if TAs used mutex lock correctly or not. (10%) And explain if the output is reasonable or not. (Why Philosopher 4 was the first one to think and eat? Could Philosopher 4 and Philosopher 1 eat at the same time?)(10%)
Ans.
* 兩種答案:
* 正確: mutex 放置的位置正確或程式邏輯正確，程式可以運行
* 錯誤: deadlock 或其他可能出現的問題(當 5 個 thread 取得左手邊筷子的時間極為接近時)
* 1、4可以同時吃飯
### 4.
a. Please complete the Need matrix.
Need(Max-allocation)
0000
0750
1002
0050
0642
b. Is the system in a safe state?
Yes
## 106.
### 5.
Please explain the following terms:
(以下都是官方版本的敘述)
* (A) **Race condition** (5%)
Several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place.
* (B) **Deadlock** (5%)
Two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.
* (C ) **Priority inversion** (5%)
Scheduling problem when lower-priority process olds a **lock** needed by higher-priority process.
* (D) **Busy waiting** (5%)
Busy-waiting, busy-looping or spinning is a technique in which a process repeatedly checks to see if a condition is true
順便加上我們這次小考考的:
* **Starvation**:
A process may never be removed from the semaphore queue in which it is suspended.
### 6.
Which of the following statements are true? If false, why? (15%)
(A) Hardware support synchronization implements lock mechanism with atomic instructions which are interruptible.
(B) There is only one process can be active within a monitor.
(C ) Mutex lock can be implemented with binary semaphore.
(D) Semaphore can be implemented without busy waiting.
(E) Monitor handles synchronization issues with condition variables containing two operations: wait and signal, which are also used in semaphore.
Ans.
(B)(C )(D)
(A) Atomic instructions are not interruptible.
(E) Wait and signal in semaphore act as lock with resource counter, which are not related to condition variables at all.
### 7.
Please describe Dining-Philosophers Problem. (5%) And complete the test function of the monitor below to solve this problem. (10%)
* 
* 
* Ans.
* 
* 若干個哲學家坐在圓桌一起用餐，若其中一人想要進食，就必須同時持有左右兩邊的筷子才行，若在場所有哲學家都持有左手邊的筷子遲遲不放，痴痴地等待右手邊的筷子釋出，便會發生大家都在等待(deadlock)，因此要約定只在左右兩邊的筷子都可用時才能進食
```java
void test(int i){
if ((state[(i+4)%5]!=EATING)&&
(state[(i+1)%5]!=EATING)&&
(state[i] == HUNGRY)){
state[i] = EATING;
self[i].signal();
}
}
```
### 8.
Please determine whether the following RAGs are deadlocked or not.
AD
### 9.
Describe the difference between deadlock prevention and deadlock avoidance.
Deadlock prevention: ensure that at least one of the necessary conditions mentioned above cannot hold
## 105.
### 7.
Q : What is the main disadvantage of Mutex Locks? Simply describe it.
A : Requires **busy waiting**, any other process that tries to enter its critical section must call acquire() continuously.
lock therefore called a spinlock.
### 8. 必考deadlock定義
[deadlock定義](https://hackmd.io/i31OZkWOTACybwRIFdwCmA)
* Consider the traffic deadlock depicted
a. Show that the four necessary conditions for deadlock indeed hold in this example. (15%)
b. State a simple rule for avoiding deadlocks in this system. (10%)
Ans.
* (1) mutual exclusion:
* The mutual exclusion condition holds as only one car can occupy a space in the roadway.
* (2) hold-and-wait
* A car holds onto their place in the roadway while they wait to advance in the roadway.
* (3) no preemption
* A car cannot be removed (i.e. preempted) from its position in the roadway.
* (4) circular wait
* There is indeed a circular wait as each car is waiting for a subsequent car to advance.
* A car may not advance into an intersection
### 9.
* Describe the possible methods used to recover a system from deadlock.
* Ans.
* (1) Process termination:
Abort all deadlocked processes
Abort one process at a time until the deadlock cycle is eliminated
* (2) Resource preemption:
Selecting a victim – minimize cost
Rollback
### 10.
Answer the following questions using the banker’s algorithm:
a. What is the content of the matrix Need? (10%)
b. Is the system in a safe state? (10%)
c. If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately? (10%)
Ans.
a. Need: max-allocation
$P_0$: (0, 0, 0, 0)
$P_1$: (0, 7, 5, 0)
$P_2$: (1, 0, 0, 2)
$P_3$: (0, 0, 2, 0)
$P_4$: (0, 6, 4, 2).
b. Yes.With Available being equal to (1, 5, 2, 0), either process $P_0$ or $P_3$ could run.
Once process P3 runs, it releases its resources which allow all other existing processes to run.
c. Yes it can. This results in the value of Available being (1, 1, 0, 0).One ordering of processes that can finish is P0, P2, P3, P1, and P4.
執行順序:
available
1 5 2 0
P0 1 5 3 2
P2 2 8 8 6
P3 2 14 11 8
P4 2 14 12 12
P1 3 14 12 12
Sign in with Wallet
Connect another wallet