一、 是非題
1. ○ 內文切換是不具生產力的，所以應該越短越好。
2. ╳ 執行緒又稱為輕量級行程，它會跟同一行程的其他執行緒共享程式計數器及暫存器。（共享相同的記憶體位址空間、程式區段、資料區段，和一些系統資源）
3. ○ 一般來說，大多數的行程通常都是具有大量極短的CPU暴衝，而較長的CPU暴衝則少得多。
4. ╳ SJF排程偏愛CPU暴衝較長（短）的行程。
5. ╳ FCFS（SJF）排程法可能會導致飢餓現象。
6. ○ SJF排程法也可以視為是優先權排程的一個特例。
7. ╳ 老化機制可以用來解決護送（飢餓）現象。
8. ○ 在多層佇列排程中，各行程無法在佇列間動態移動。
二、 問答題
1. 請說明行程與程式的差異。
答：
1.行程：行程是主動的個體，程式是被動的個體。程式是存放在儲存裝置中的檔案，可搬移與拷貝；行程包含程式計數器來指示下一個要執行的執令，及一組相關資源。
2.行程是暫時的，程式是長存的。行程於執行結束後就不存在，程式如未刪除，會一直存在儲存裝置中。
3.行程與程式的組成內容不同：行程中包含程式、資料與行程控制資訊。
2. 在圖2-3中，為什麼當分派程式執行時，行程Ａ、Ｂ都處於「非執行中」？
答：因為CPU一次只能執行一個工作，而當分派程式執行時，它便佔用了CPU。所以此時行程Ａ、Ｂ都處於「非執行中」的狀態。
3. 請述描各種排程器的主要功能與不同點。
答：
長期排程器(long-term scheduler)：又稱任務排程(job scheduling)，用來決定哪些行程可以參與系統的競爭；通常長期排程器決定讓某行程加入後，就會讓它保持作用到結束為止，常見於批次系統中，缺點是會發生護送現象。
短期排程器(short-term scheduler)：也稱分派程式，負責將CPU分配給已經進入記憶體，並且已就緒可以執行的行程使用。多工作業系統中，每個行程至少有一部分放在記憶體中，由短期排程器負責排程。缺點是可能因行程過多，使得每個行程回應速率過慢或執行時間過長。
中期排程器(mid-term scheduler)：又稱置換程式(swapper)，會將一些行程從記憶體中暫時移出到輔助記憶體（通常是磁碟），以釋放出部分記憶體空間。
4. 請說明行程通常有那些狀態？
答：
建立(NEW)：行程剛產生時的狀態。
就緒(ready)：行程已準備好，隨時可執行。
懸置(blocked)：行程正等待某事件發生，通常是在等待I/O運算完成。
執行(running)：行程正在執行，佔用CPU。
終止(terminated)：行程已結束，但有些資訊還留在系統中。
中期排程則還會多出２個狀態
置換／就緒(swapped/ready)：行程可被執行，但目前置換於輔助記憶體中。
置換／懸置(swapped/blocked)：行程正等待某事件發生，並被置換到輔助記憶體中。
5. 請說明在那些情況下行程會離開執行的狀態。
答：
執行→懸置：因進行I/O運算、與其他行程間的通訊、或是某些系統條件（非行程本身所控制）。
執行→就緒：執行中的行程會分配到固定的CPU使用時間，如果時間內未發生需等待的事件，當時間到了時，系統計時器會產生中斷，將控制器交回作業系統。
執行→終止：可能因執行到某些不合法的動作而被終止，也可能正常完成任務而結束。
6. 請說明在哪些情況下會產生新行程。
答：
◎使用者登入
◎使用者執行某個程式
◎請求系統提供服務
◎由現有行程產生
7. 請說明行程結束的可能原因。
答：
◎ 任務完成
◎ 保護錯誤
◎ 運算錯誤
◎ I/O失敗
◎ 外力終止
◎ 父行程終止
◎ 父行程要求
8. 請說明在行程控制區段中通常儲存了行程的哪些資訊。
答：行程控制區段（PCB, Process Control Block）中，包含下列資訊
◎ 行程狀態與排程資訊
◎ 記憶體管理
◎ 硬體狀態
◎ 輸入／輸出狀態資訊
◎ 其他：行程本身的識別資訊(行程識別碼，Process ID)、父行程的行程識別碼、存取權限、起始時間(start time)等。
9. 請簡述作業系統中常見的佇列，並說明其用途。
答：
◎ 工作佇列：當一個行程被允許\進入系統時，就會被放置於工作佇列。工作佇列記錄著系統中所有的行程。
◎ 就緒佇緒：當一個行程準備要執行時，就會被移到就緒佇列。同一時間內會有很多的行程被放在就緒佇列中，每個行程都有一個對應的 PCB，每個 PCB 再用鏈結串列串在一起。
◎ 磁碟裝置佇列：當一個行程等待 I/O 裝置動作完成時，就會被移到裝置佇列，而且每個裝置都擁有自己的裝置佇列。
◎ 行程等待佇列：一個行程在執行期間可能需要等待某些事件完成後才能執行，如 I/O 的要求等，這時行程會被移到等待佇列。
10. 請說明何謂內文切換？
答：當CPU的使用權由一個行程轉到另一個行程時，須將上一個行程的相關資訊儲存起來，並且把即將要使用CPU的行程之相關資訊載入系統中，這個動作稱之為內文切換。
11. 內文切換對系統而言是額外的負擔，請問有那些因素會影響內文切換所花的時間。
答：取決於所需拷貝的暫存器數目、記憶體速度、硬體是否提供特殊指令（如一次載入所有暫存器的單一指令）等。
12. 當一個執行緒被建立時，需要使用到什麼資源？與建立一個行程有什不同？
答：
◎ 執行緒建立時會擁有自己的程式計數器、暫存器與堆疊空間，但和同一行程中的其他執行緒共享相同的記憶體空間、程式區段、資料區段和一些系統資源。
◎ 執行緒與行程的差異：
位址空間：行程間位址空間是相互獨立；同一行程的執行緒共享相同的位址空間。
通訊方式：行程間通訊須利用作業系統所提供之機制進行；執行緒因共享相同位址，可直接讀寫其全域資料進行溝通。
內文切換：同一行程間執行緒間進行內文切換的時間小於行程間內文切換。
13. 為什麼執行緒的內文切換會比行程的內文切換快?
答：執行緒的內文切換只需儲存程式計數器、一組暫存器和堆疊空間，比行程的內文切換除了上述項目外，還需儲存行程狀態與排程資訊、記憶體管理、硬體狀態、輸入／輸出狀態資訊及其他包括行程本身資訊等，所以執行緒內文切換會比行程內文切換快的多。
14. 請說明為什麼排程是影響作業系統效能的重要因素。
答：對一個單CPU的系統來說，任何時間都只能有一個行程在執行，因此當行程在等待某個事件或I/O運算時，因未使用到CPU，所以可將CPU讓出給其他需要執行的行程使用，因此排程的好壞便會嚴重影響到作業系統的效能。
15. 請解釋CPU暴衝、I/O暴衝與CPU為主、I/O為主行程之間的關係。
答：
CPU暴衝（CPU burst）：行程執行時持續地使用CPU。
CPU為主（CPU bound）:當程式需大量CPU運算時，暴衝統計會包含較長的CPU暴衝，行程就較長時間佔用CPU。
I/O暴衝（I/O burst）：行程執行時專注在I/O運算上。
I/O為主（I/O bound）：程式通常會有很多很短CPU暴衝，因專注在I/O暴衝，所以CPU暴衝較多且較短，不需大量計算。行程切換較為頻繁且週期短。
要判斷一個行程是屬於CPU為主還是I/O為主時，評估的標準是根據CPU暴衝。
16. 請定義可搶先的和不可搶先的排程法，並舉例在那些情況下必須使用可搶先的排程法。
答：
可搶先式排程法：排班程式可以在行程進入等待或結束之前就先將行程趕出CPU，以便將CPU配置給另一個行程。
不可搶先式排程法：只有當執行中的行程進入懸置狀態或終止的時候，其他行程才有可能取得CPU的控制權。
為避免其他使用者或應用程式等待過久或是有時間限制的工作，就必須使用可搶先式的排程法，如土石流監測警報、核能電廠的幅射監視系統、高速公路車流監控系統等，就必需使用可搶先式的排程法，以免造成時機延誤。
17. 請說明實作SJF排程法的困難。
答：因為很難知道行程下一個 CPU 暴衝時間的確實長度，最多只能使用預估的方法來求得近似的值。
18. 請問有那些方法可以用來避免行程發生飢餓現象？
答：
老化機制：給每個行程一個年齡，代表行程在就緒佇例中等待的時間；當年齡增加到一定程度時，就將行程優先權提高。另外也可以使用多層反饋佇列排程法，將在低優先權的佇列中等待過久的行程，移至優先權較高的佇列，這樣就能避免飢餓的現象發生。
19. 請問在RR排程法中，時間切片太長或太短各會造成什麼影響？
答：如果切片時間太短，會造成內文切換頻率過高，影響系統效能；如果切片時間太長，則會近似FCFS排程效果，造成護航現象。
20. 請問在多層佇列排程法中，如果不同的佇列有不同的時間切片，會有什麼優點？
答：多層佇列排程法中，每個佇列所得到的時間切片長度可因優先權的高低而不同，優先權較高的佇列可得到較長的時間切片，而優先權較低的佇列得到的時間切片就比較短。當然不見得優先權較高的行程就需要較長的時間切片，譬如說互動式的前景程式也許只要很短的時間切片，所以並沒有一定的規則能規範佇列之間的時間切片長度，而是時間切片的長度應以應用行程的特性決定。
21. 假設一個排程法對最近時間內使用最少CPU時間的行程有利。為什麼這種排程法有利於I/O為主的行程？
答：I/O為主（I/O bound）：程式通常會有很多很短CPU暴衝，因使用CPU的時間很短，所以I/O為主的行程容易被優先執行。
22. 評估排程的方法有哪幾種？
答：
◎ CPU使用率：CPU真正在執行行程的時間比例。
◎ 產量（throughput）：系統在單位時間內所能完成的行程數目。
◎ 回覆時間（turnaround time）：單一行程執行完畢平均所需的時間。
◎ 等待時間：行程花費在等待的平均時間。
◎ 反應時間（response time）：在互動式系統中，當使用者輸入後，系統開始做出回應所需的平均時間。
◎ 可預測性（predictability）：用來評做系統回應的一致程度。
◎ 公平性：所有行程具有相同執行機會的程度。
三、 計算題。
1. 有一組行程如下：
行程 | CPU暴衝時間（毫秒） |
Ｐ１ | １５ |
Ｐ２ | ７ |
Ｐ３ | ４ |
Ｐ４ | １０ |
到達時間皆為0，順序為Ｐ１、Ｐ２、Ｐ３、Ｐ４。
請分別使用FCFS與不可搶先的SJF排程法，求出平均等待時間。
答：
FCFS排程法
0 15 22 26 36
平均等待時間為(0+15+22+26)/4=15.75毫秒
不可搶先的SFJ排程法
0 4 11 21 36
平均等待時間為(0+4+11+21)/4=9毫秒
2. 假設有四個行程Ｐ１、Ｐ２、Ｐ３、Ｐ４，都在時間0到達，順序為Ｐ１、Ｐ２、Ｐ３、Ｐ４，其CPU暴衝時間如下：
行程 | CPU暴衝時間（毫秒） | 優先權 |
Ｐ１ | 6 | 2 |
Ｐ２ | 5 | 0 |
Ｐ３ | 7 | 3 |
Ｐ４ | 4 | 1 |
a. 當使用FCFS、SJF、不可搶先的優先權(數字愈小，優先權愈高)和RR(時間切片=3)排程法時，行程的執行順序為何，請畫出與課文類似的圖。
b. 所有行程的平均等待時間為何？
c. 每個行程的回覆時間各為何？
答：
a.
FCFS排程：
0 6 11 18 22
SJF排程：
0 4 9 15 22
不可搶先的優先權排程：
0 5 9 15 22
RR排程：
0 3 6 9 12 15 17 20 21 22
Ｐ１ | Ｐ２ | Ｐ３ | Ｐ４ | Ｐ１ | Ｐ２ | Ｐ３ | Ｐ４ | Ｐ１ |
b.
FCFS平均等待時間：
（0+6+11+18）/4=8.75毫秒
SJF的平均等待時間：
（0+4+9+15）/4 =7毫秒
不可搶先的優先權平均等待時間：
（0+5+9+15）/4=7.25毫秒
RR的平均等待時間：
（0+(12-3)+3+(15-6)+6+(17-9)+(21-20)+9+(20-12)）/4=13.25毫秒
c. 各行程回覆時間
| FCFS | SJF | 不可搶先
的優先權 | RR |
P1 | 6 | 15 | 15 | 15 |
P2 | 11 | 9 | 5 | 17 |
P3 | 18 | 22 | 22 | 22 |
P4 | 22 | 4 | 9 | 21 |
3. 假設有四個行程Ｐ１、Ｐ２、Ｐ３、Ｐ４和Ｐ５，都在時間0到達，順序為Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５，其CPU暴衝時間如下：
行程 | CPU暴衝時間（毫秒） | 優先權 |
Ｐ１ | 10 | 3 |
Ｐ２ | 3 | 1 |
Ｐ３ | 2 | 3 |
Ｐ４ | 1 | 4 |
Ｐ５ | 5 | 2 |
a. 當使用FCFS、SJF、不可搶先的優先權(數字愈小，優先權愈高)和RR(時間切片=3，依照抵達順序執行)排程法時，行程的執行順序為何，請畫出與課文類似的圖。
b. 在上述各種演算中，各行程的平均等待時間為何？哪個演算法的平均等待時間最短？
c. 如果希望讓RR的效能表現最好，根據經驗法則，在上例的執行情況下，它的時間切片最少應該是多少？
答：
a.
FCFS排程：
0 10 13 15 16 21
SJF排程
0 1 3 6 11 21
不可搶先的優先權排程
0 3 8 18 20 21
RR排程：
0 3 6 8 9 12 15 17 21
b.
FCFS平均等待時間：
（0+10+13+15+16）/5=10.8毫秒
SJF的平均等待時間：
（0+1+3+6+11）/5 =4.2毫秒
不可搶先的優先權平均等待時間：
（0+3+8+18+20）/4=9.8毫秒
RR的平均等待時間：
（0+(12-3)+(17-6)+3+6+8+9+(15-3)）/5=11.6毫秒
由以上計算數據得知，SJF排程法的平均等待時間4.2毫秒是最短的。
c. 一般的經驗法則是80%的CPU暴衝時間應該要小於一個時間切片的長度。由此得知此題的適當時間切片長度應為等於5。
四、 進階題
5.請說明當行程發生哪一些狀態轉換的時候，作業系統會重新排程。
答：有 4 種行程的執行狀態轉換時需要進行重新排程：
(1)由執行狀態切換到就緒狀態（如發生中斷）。
(2)由執行狀態切換到等待狀態（如產生I/O的要求或是等待某些事件的發生）。
(3)由執行狀態切換到結束狀態。
(4)由等待狀態切換到就緒狀態（如完成 I/O）。
6.請舉例說明，在哪一些系統中產量會比回覆時間來的重要，而哪一些系統中回覆時間會比反應時間來得重要。
答：網路書店的圖書查詢系統對於需服務大量讀者查詢的情況下，要求單位時間內系統完成的行程個數會比各個行程執行完成後的總共執行時間來的重要。即時系統必須保證關鍵任務在一定的時間內能夠完成，否則對系統會有負面的影響，所以即時系統的回覆時間會比回應使用者送出要求後的反應時間來得重要。
7.一個排程法決定了行程的執行順序，假設系統中有ｎ個不可搶先的行程需要排程，可能產生哪幾種不同的執行順序？請用ｎ寫出一個公式
答：ｎ！＝ｎ＊（ｎ－１）＊（ｎ－２）...＊２＊１
8.很多排程法都需要設定一些參數，如RR排程法需要設定時間切片的長度，多層佇列排程法需要設定佇例的個數與每個佇列的排程法等。而這些排程法可能隱含了另一個排程法（如當RR排程法的時間切片為無限大時，就如同FCFS排程法）。請問下列各組排程方法之間，是否有存在某些關係？如果有的話，是什麼樣的關係？
a. 優先權，SJF
b. MFQ，FCFS
c. 優先權，FCFS
d. RR，SJF
答：
a. 優先權，SJF：當最短的行程擁有最高的優先權時，就如同 SJF 排程法。
b. MFQ，FCFS：多層反饋佇列的最低佇列，就如同 FCFS 排程法。
c. 優先權，FCFS：等待時間最長的行程擁有最高的優先權，就如同 FCFS 排程法。
d. RR，SJF：RR與SJF 並不存在關係。
