一、解釋名詞
 (1) 臨界區間(Critical Section)
 (2) 行程控制表(process control table或process control block)
 (3) Medium-term scheduler(中程排班程式)
二、何謂本文切換(Context Switch)?並請討論其與時間量(time quantum, 或稱時間片段time slice)間的關連性
三、考慮以下一組行程，其中CPU分割時間長度是以毫秒為單位：

┌──┬────┬───────────┐
│行程│到達時間│所需的CPU執行週期時間 │
├──┼────┼───────────┤
│ P1 │   0    │           8          │
├──┼────┼───────────┤
│ P2 │   5    │           2          │
├──┼────┼───────────┤
│ P3 │   3    │           4          │
├──┼────┼───────────┤
│ P4 │   1    │           3          │           
├──┼────┼───────────┤
│ P5 │   5    │           2          │
├──┼────┼───────────┤
│ P6 │   2    │           5          │
└──┴────┴───────────┘

Gantt Chart畫法請一下列方式繪製：

FCFS
      ┌───┬───┬────────┬──┐
      │Pi    │Pj    │     ......     │Pn  │
      └───┴───┴────────┴──┘
時間軸 0      5       7     ........    20    24


假設這些行程依上表所列時間到達，及所需CPU執行週期時間(若條件相同時，以process id較小者優先)，請問：

(a) 畫出這些行程以(1)先到先做(FCFS)、(2)不可搶先最短的工作先做(nonpreemptive SJF)、(3)可搶先最短的工作先做(preemptive SJF)和(4)依序循環(Round-Robin)(quantum=3)排班演算法執行的甘特圖(Gantt Chard)。【請依序寫】
(b) 在上述的每一個排班演算法中，每一個行程的回復時間(turnaround time)是多少？(最後請以表格匯整依序作答)
(c)上述的各演算法之中，每一個行程的等待時間(waiting time)是多少？(最後請以表格匯整依序作答)

四、何謂號誌(semaphores)？其優點為何？
五、[1]請說明臨界區間問題必須滿足的三個要求
    [2]依序解釋下列演算法是否為何滿足或步滿足上列的三項要求

[1 ] do {
[2 ]  waiting[i] = true;
[3 ]  key = true;
[4 ]  while(waiting[i] and key)
   key := TestAndSet(lock);
[5 ]  waiting[i] := false;
 
[6 ]    Critical Section (C.S.)
 
[7 ]  j:=(i+1)%n;
[8 ]  while (j!=i)and !(waiting[j])
   j:=(j+1)%n;
[9 ]  if (j==i)
   lock:=false;
  else
  waiting[j]:=false;

[10]   remainder section 
[11] } while (1);