簡答題

#

🍜1. 解決critical section方法的三個條件?

#

1. 互斥 (Mutual Exclusion)
   • 定義：如果行程 \(P_i\) 正在它的 Critical Section 裡面執行，那麼其他所有的行程都不准進入它們的 Critical Section。
   • 白話文：一次只能有一個人進廁所。門鎖起來了，別人就不能進來。
2. 進行 (Progress)
   • 定義：如果目前沒有人在 Critical Section 裡面，而且有人想進去，那麼：
     1. 只有那些「想進去的行程」可以參與決策（決定誰能進去）。
     2. 這個決定不能無限期地被拖延。
   • 白話文：
     • 有空位就要讓人用：廁所沒人，我想上，你不能莫名其妙擋著不讓我進去。
     • 閒雜人等勿擾：正在外面吃飯（Remainder Section）、不想上廁所的人，不能跑過來投票決定誰可以上廁所，也不能卡住門口。
3. 有限等待 (Bounded Waiting)
   • 定義：從一個行程「提出進入申請」開始，到它「真正被允許進入」為止，這段期間內，其他行程搶先進入 Critical Section 的次數必須要有上限 (Bound)。
   • 白話文：
     • 不能被插隊插到死：我去排隊買票，前面最多只能讓 3 個人插隊。不能因為我運氣不好，就讓其他人一直插隊，害我排到天荒地老都進不去。

🍜2. 造成deadlock的四個條件?

#

1. Mutual Exclusion (互斥)
   • 定義：系統中至少有一個資源是 不可共享的 (Non-shareable)。也就是說，該資源一次只能給一個行程使用。
2. Hold and Wait (持有並等待 / 佔用並等待)
   • 定義：一個行程目前 至少持有 (Hold) 了一個資源，且正在 等待 (Wait) 其他行程持有的資源。
3. No Preemption (不可搶佔 / 不可剝奪)
   • 定義：資源不能被強制從行程手中搶走，必須由持有的行程在使用完畢後自願釋放 (Voluntarily release)。
4. Circular Wait (循環等待)
   • 定義：系統中存在一組行程
     • \(\{P_0, P_1, \dots, P_n\}\)，形成一個頭尾相接的等待圓圈。
     • \(P_0\) 正在等 \(P_1\) 手上的資源\(P_1\) 正在等 \(P_2\) 手上的資源
     • …
     • \(P_n\) 正在等 \(P_0\) 手上的資源

🍜3. Consider the following snapshot of a system:

#

        Allocation  	Max 		Available
        A B C D   		A B C D 	A B C D
    P1 	1 1 2 5  		1 7 6 7 	2 6 3 1
    P2	2 5 4 3 		2 9 5 3
    P3 	2 4 6 5  		2 4 6 7
    P4  2 1 1 1  		2 8 6 1

⭐ Allocation -> 已佔有 ; Max -> 最大需求 ; Available -> 目前可用

🦢a. What is the content of the matrix Need?

#

Need 的公式 : \(Need[i,j] = Max[i,j] - Allocation[i,j]\)

• P1: \((1,7,6,7) - (1,1,2,5) = (0, 6, 4, 2)\)
• P2: \((2,9,5,3) - (2,5,4,3) = (0, 4, 1, 0)\)
• P3: \((2,4,6,7) - (2,4,6,5) = (0, 0, 0, 2)\)
• P4: \((2,8,6,1) - (2,1,1,1) = (0, 7, 5, 0)\)

答案 :

      A B C D
P1    0 6 4 2
P2    0 4 1 0
P3    0 0 0 2
P4    0 7 5 0

🦢b. Is the system in a safe state? Why?

#

我們需要找到一個 Safe Sequence (安全序列)，讓所有行程都能依序執行完畢。

初始 Work (可用資源) = Available = (2, 6, 3, 1)

1. 第一輪檢查：

   • P1 Need (0, 6, 4, 2) \(\le\) Work (2, 6, 3, 1) ? \(\rightarrow\) No ( C資源 4>3, D資源 2>1 )
   • P2 Need (0, 4, 1, 0) \(\le\) Work (2, 6, 3, 1) ? \(\rightarrow\) Yes ✅
     • 假設 P2 執行完畢，釋放資源：
     • Work = Work + Allocation_P2 = (2, 6, 3, 1) + (2, 5, 4, 3) = (4, 11, 7, 4)

2. 第二輪檢查(目前 Work = 4, 11, 7, 4)：

   • P3 Need (0, 0, 0, 2) \(\le\) Work? \(\rightarrow\) Yes ✅
     • 假設 P3 執行完畢，釋放資源：
     • Work = (4, 11, 7, 4) + (2, 4, 6, 5) = (6, 15, 13, 9)

3. 第三輪檢查(目前 Work = 6, 15, 13, 9)：

   • P1 Need (0, 6, 4, 2) \(\le\) Work? \(\rightarrow\) Yes ✅
     • 假設 P1 執行完畢，釋放資源：
     • Work = (6, 15, 13, 9) + (1, 1, 2, 5) = (7, 16, 15, 14)

4. 第四輪檢查(目前 Work = 7, 16, 15, 14)：

   • P4 Need (0, 7, 5, 0) \(\le\) Work? \(\rightarrow\) Yes ✅
     • 假設 P4 執行完畢

答案 : 可以，安全序列 : <P2, P3, P1, P4>

🦢c. If a request from process P1 arrives for (1,5,3,1) can the request be granted immediately? Why?

#

(如果 P1 提出資源請求 (1, 5, 3, 1)，可以立即准許嗎？為什麼？)

因為資源請求 (1, 5, 3, 1) > P1_Need ( 0, 6, 4, 2 )

所以不行，會超出 \(P_1\) 的 Need

🍜4. Given memory partitions of 100KB, 500KB, 200KB, 300KB, 600KB(in order), how would each of the first-fit, best-fit and worst-fit algorithms place processes of 212KB, 417KB, 112KB, and 426KB(in order)? Which algorithm makes the most efficient use of memory?

#

初始狀態

Memory Partitions:

1. 100 KB
2. 500 KB
3. 200 KB
4. 300 KB
5. 600 KB

Processes: 212 KB, 417 KB, 112 KB, 426 KB

1. First-Fit

#

原則：從頭開始掃描，找到第一個夠大的洞就塞進去。

• Process 212 KB:

  • 檢查 100 (太小) \( \rightarrow \) 檢查 500 (夠大！)。
  • 結果：放入 Partition 2 (500 KB)。剩餘 \( 500 - 212 = 288 \text{ KB} \)。

• Process 417 KB:

  • 檢查 100 (太小) \( \rightarrow \) 檢查 288 (太小) \( \rightarrow \) 檢查 200 (太小) \( \rightarrow \) 檢查 300 (太小) \( \rightarrow \) 檢查 600 (夠大！)。
  • 結果：放入 Partition 5 (600 KB)。剩餘 \( 600 - 417 = 183 \text{ KB} \)。

• Process 112 KB:

  • 檢查 100 (太小) \( \rightarrow \) 檢查 288 (夠大！)。
  • 結果：放入 Partition 2 (剩餘的 288 KB)。剩餘 \( 288 - 112 = 176 \text{ KB} \)。

• Process 426 KB:

  • 檢查 100, 176, 200, 300, 183… 全部都太小。

First-Fit 結論：Process 426 KB 無法配置。

2. Best-Fit

#

原則：掃描全部，找到最小且足夠的洞（留下最小的剩餘空間）。

• Process 212 KB:

  • 候選名單：500, 300, 600。
  • 最佳選擇：Partition 4 (300 KB) (因為 \( 300-212=88 \)，最貼近)。
  • 結果：放入 Partition 4。剩餘 88 KB。

• Process 417 KB:候選名單：500, 600。

  • 最佳選擇：Partition 2 (500 KB) (因為 \( 500-417=83 \))。
  • 結果：放入 Partition 2。剩餘 83 KB。

• Process 112 KB:

  • 候選名單：200, 600。
  • 最佳選擇：Partition 3 (200 KB) (因為 \( 200-112=88 \))。
  • 結果：放入 Partition 3。剩餘 88 KB。

• Process 426 KB:

  • 候選名單：600。
  • 最佳選擇：Partition 5 (600 KB)。
  • 結果：放入 Partition 5。剩餘 \( 600 - 426 = 174 \text{ KB} \)。

Best-Fit 結論：所有行程都成功配置

3. Worst-Fit (最差配適)

#

原則：掃描全部，找到最大的洞（留下最大的剩餘空間）。

• Process 212 KB:

  • 最大洞：600。
  • 結果：放入 Partition 5 (600 KB)。剩餘 \( 600 - 212 = 388 \text{ KB} \)。

• Process 417 KB:

  • 最大洞：500。
  • 結果：放入 Partition 2 (500 KB)。剩餘 \( 500 - 417 = 83 \text{ KB} \)。

• Process 112 KB:

  • 最大洞：Partition 5 剩下的 388 KB。
  • 結果：放入 Partition 5 (剩餘的 388 KB)。剩餘 \( 388 - 112 = 276 \text{ KB} \)。

• Process 426 KB:

  • 剩下的洞：100, 83, 200, 300, 276。最大才 300。

Worst-Fit 結論：Process 426 KB 無法配置。

哪一個比較有效率 ?

#

答案 : Best-Fit，因為他是唯一最大化利用空間的方法

🍜5. 考慮下面的參考頁號碼, 而記憶體配置的欄數為4, 請用FIFO, Optimal, LRU 三個頁置換演算法, 請計算各自的頁失誤次數? 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

#

1. FIFO (First-In, First-Out) 先進先出

#

原則：最先進入記憶體的頁面，最先被置換出去。

• 詳細過程：
  • 前4個 (1,2,3,4) 填滿記憶體 (Faults: 4)。
  • 接著 1, 2 都在裡面 (Hits)。
  • 來了 5：踢掉最早來的 1 \( \rightarrow \) 放入 5。
  • 來了 1：踢掉最早來的 2 \( \rightarrow \) 放入 1。
  • 來了 2：踢掉最早來的 3 \( \rightarrow \) 放入 2。
  • 來了 3：踢掉最早來的 4 \( \rightarrow \) 放入 3。
  • 來了 4：踢掉最早來的 5 \( \rightarrow \) 放入 4。
  • 來了 5：踢掉最早來的 1 \( \rightarrow \) 放入 5。
  • 放入 5。🔴 FIFO Page Faults = 10 次

2. Optimal (最佳化)

#

原則：置換掉「未來最長時間內不會被用到」的頁面。 (由現在往未來/右邊看)

值得注意的是，只要是有在裡面的 (H) 就直接跳過不看

Page Faults = 7 次 ( 開頭塞 4 個進來記得也要算上 )

3. LRU (Least Recently Used) 最近最少使用

#

原則：置換掉「過去最久沒被使用」的頁面。 (由現在往過去/左邊看)

🍜6. 考慮一個對於在磁柱0到199上的區塊有許多 I/O 要求，如在磁碟佇列之中的以下排列：98、183、37、122、14、124、65、67, 如果磁碟讀寫頭的起始位址為磁柱 53,而前一個讀寫頭是小於53的位址, 如果採用FCFS, SCAN, C-SCAN三個磁碟排班演算法, 請計算各自讀寫頭所移動的距離?

#

為了方便計算，先把磁碟佇列由小排到大 : 14, 37, 65, 67, 98, 122, 124, 183

1. FCFS (First-Come, First-Served) 先來先服務

#

規則： 完全依照佇列進來的順序跑，不管遠近。 路徑：53 \( \rightarrow \) 98 \( \rightarrow \) 183 \( \rightarrow \) 37 \( \rightarrow \) 122 \( \rightarrow \) 14 \( \rightarrow \) 124 \( \rightarrow \) 65 \( \rightarrow \) 67

示意圖 :

計算移動距離：

• |53 - 98| = 45
• |98 - 183| = 85
• |183 - 37| = 146
• |37 - 122| = 85
• |122 - 14| = 108
• |14 - 124| = 110
• |124 - 65| = 59
• |65 - 67| = 2

總移動距離： \( 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = \) 640 磁柱

2. SCAN (電梯演算法)

#

規則： 讀寫頭像電梯一樣，先往一個方向走到底（碰到邊界），處理沿途的要求，然後折返往回走。 方向：目前向右（往 199 方向）。

• 路徑：

1. 從 53 開始往右，依序經過：65, 67, 98, 122, 124, 183

2. 碰到邊界 199 (注意：標準 SCAN 演算法會碰到邊界才折返)

3. 折返向左，依序經過：37, 14

示意圖 :

計算移動距離 (簡化法)：

• 第一段 (向右到底)： 從 53 走到 199\( |199 - 53| = 146 \)
• 第二段 (折返向左)： 從 199 走到最左邊剩下的要求 (14)\( |199 - 14| = 185 \) 總移動距離：\( 146 + 185 = \) 331 磁柱

3. C-SCAN (Circular SCAN) 循環掃描

#

規則： 類似 SCAN，但是只做單向服務。當讀寫頭碰到終點 (199) 時，它會直接甩回起點 (0)，中間不服務任何要求，回到起點後再重新往右掃描。 方向：永遠向右（往 199 方向）。

路徑：

1. 從 53 開始往右：65, 67, 98, 122, 124, 183
2. 碰到邊界 199
3. 直接跳回起點 0 (這段距離要算，且中間不服務)
4. 從 0 開始往右：14, 37 (結束)

計算移動距離：

• 第一段 (向右到底)：從 53 走到 199
  • \( |199 - 53| = 146 \)
• 第二段 (甩回起點)：從 199 飛回 0
  • \( |199 - 0| = 199 \)第三段 (重新掃描)：從 0 走到剩下的最後一個要求 (37)
    • \( |37 - 0| = 37 \)

總移動距離：\( 146 + 199 + 37 = \) 382 磁柱

🍜7. Please use the following data structure to write down the programs for the producer and consumer in thebounded-buffer shared memory scheme for process communications.

#

#define BUFFER SIzE 10
typedef struct{
    ...
}item;                          // The data which producer and consumer need to handle
item buffer[BUFFER_SIZE]:       //shared memory
int in = 0;                      // buffer index for producer
int out = 0;                    // buffer index for consumer
int counter = 0;                 // indicate the count of items in buffer

1. Producer (生產者)： 負責製造資料放進緩衝區。
2. Consumer (消費者)： 負責從緩衝區把資料拿出來。

Producer

#

item next_produced; // 準備要生產的項目

while (true) {
    /* 1. 生產一個項目 */
    // produce an item in next_produced
    
    /* 2. 檢查緩衝區是否已滿 (Full?) */
    while (counter == BUFFER_SIZE)
        ; /* do nothing, just wait */

    /* 3. 放入緩衝區 */
    buffer[in] = next_produced;
    
    /* 4. 移動 in 指標 (環形移動) */
    in = (in + 1) % BUFFER_SIZE;
    
    /* 5. 增加計數器 */
    counter++;
}

Consumer

#

item next_consumed; // 準備存放拿出來的項目

while (true) {
    /* 1. 檢查緩衝區是否為空 (Empty?) */
    while (counter == 0)
        ; /* do nothing, just wait */

    /* 2. 從緩衝區取出 */
    next_consumed = buffer[out];

    /* 3. 移動 out 指標 (環形移動) */
    out = (out + 1) % BUFFER_SIZE;

    /* 4. 減少計數器 */
    counter--;

    /* 5. 消費項目 */
    // consume the item in next_consumed
}

🍜8. Following the previous problem and your solution above, we will face a problem called race condition of processsynchronization between producer and consumer in real implementation. Please give an example of race conditionwhile producer and consumer in process synchronization. (Hint: Usually the problem can be found in theassembly codes for producer and consumer while their execution sequences interfered by interrupts)

#

生產者與消費者的 counter ++ 和 counter -- 會出現問題，因為這幾行程式實際在底層會分為

1. 載入 counter 暫存器
2. 修改 counter
3. 儲存 counter 回去

這部分如果未經處理會出現覆蓋掉彼此運算結果的情況

🍜9. which one in the following two program segments has better performance if each program has only a single frame inmemory to store the integer array C? A single frame can store 512 int elements. Show your performance evaluationby number of page faults in each program and give a brief description about your evaluations.

#

int C[][]=new int[256][256];
Program segment I: for (i = 0; i < C.length; i++)
                        for (j = 0;j< C.length;j++){
                            c[i,j]= 0;
                        }

Program segment 2: for (j = 0; j < C.length; j++)
                        for (i = 0; i < C.length; i++){
                            c[i,j] =  0;
                        }

• 因為一列有 256 個 int，所以 一個 Frame 可以塞進剛好 2 列 (Rows) (\( 512 \div 256 = 2 \))。

所以 segment I 的 Page Fault 有 128 次

segment 2 則是 256 * 128 次。