contents
讀物
現在恐龍書不知道第幾版了，而且中文翻譯有點慘。看英文原文又太慢的情況，剛好查到聯合大學陳士杰教授寫的 ppt。繁體中文的說明，採用恐龍書第七版的內容。
下附章節簡報和課後習題解答。
稍微看過每一章的內容後，就可以著手看習題解答。
CH 1
CH 2
CH 3
CH 4
CH 5
CH 6
CH 7
CH 8
CH 9
CH 10
恐龍書課後習題解答 感謝大大的提供
之前也有好幾次參照教授寫的中文簡報，相當有助益。
可能遭遇的問題
個人拙見，請自行過濾
Round-Robin Scheduling
- 這個問題在寫考題的時候，略顯著的疑惑。
- 對於 Round-Robin Scheduling 的部分詳見代碼後，由於超過時限後，還要將變數存起來，所以丟入 queue 的時間會晚一點，也就是說在同一時刻會慢於新抵達的 process。之後的程序就按照 queue 的順序去運行。12345678910queue Qwhile(true) {w = Q.front()w = work(w)if(hasProcess())Q.push(nextPorcess())if(w != null)Q.push(w)time++}
考古題(課本後習題)
(=ﾟωﾟ)= 下附解答僅個人拙見，請勿隨意採信，請發揮您的善心，救救笨蛋
95 期中考
What is multiprogramming ? what is time-sharing ?(10%)
Multiprogramming(多重程式)：
- 定義：
內存有多個 processs 同時執行，一般電腦的運行方式。透過 CPU scheduling 將發生中斷 (eg. wait for I/O complete, resource not available, etc.) 的行程切換給可執行的運作。 - 特色：
可以避免 CPU idle，提高 CPU utilization(使用率) - 其他：
- Multiprogramming Degree：系統內存在執行的 process 數目
- 通常 Multiprogramming Degree 越高，則 CPU utilization 越高(p.s. ch7 Thrashing 除外)
- 多個 process 同時執行，mode 有兩種 Concurrent(並行)、Parallel(平行)
- 定義：
Time-sharing:
- 定義：
Multiprogramming 的一種，在 CPU 排班法則方面，其使用 RR(Round-Robin) 法則。
// RR 法則－CPU time quantum，若 process 在取得 CPU 後，未能於 quantum
// 內完成工作，則必須被迫放棄 CPU，等待下一次輪迴。 - 特色：
對每個 user 皆是公平的，適用在 user interactive 且 response time (反應時間)要求較短的系統環境，透過 resource sharing 技術(eg. CPU scheduling, memory sharing, spooling 達到 I/O Device 共享)，使得每個user皆認為有專屬的系統存在。
- 定義：
Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems ?
In Distributed System - Multiprocessor - Tightly-Coupled System(different from Loosely-Coupled Distributed System)- Symmetric Multiprocessors (SMP) 對稱式多處理器
- 定義：
每個 processor 的能力皆相同，即可負責的功能完全一樣。萬一某個 processor 壞了，其上工作可由其他processor 接手，系統不會整個 crash，只是整體效能下降而已。 - 特色：
Reliability (可靠性)大幅提升，強調 load balancing (負載平衡)(每個CPU的工作負擔相同)
- 定義：
- Asymmetric Multiprocessors (ASMP) 非對稱式多處理器
- 定義：
不同(群)顆的 processor，其負擔的功能不盡相同，在此架構下，通常含有一個Master CPU，負責工作的分派與協調，其他 CPUs 稱為 Slave CPU (稱為 Master-Slave Architecture) - 特色：
效能通常較SMP高，但可靠度較差
- 定義：
- Symmetric Multiprocessors (SMP) 對稱式多處理器
- What are the differences between a trap and an interrupt? What is the use of each function ?
- Trap:
軟體產生 system call
an exception in a user process.
ex. system call (software divide-by-zero) - Interrupt:
硬體產生 signal
something generated by the hardware.
ex. IO-complete interrupt (hardware generated) - 兩者相同之處
從 User Mode 切換到 Kernel Mode。
兩者都算是 interrupt 中斷指令。
- Trap:
- What is the purpose of system calls?
System calls allow user-level processes to request services of the operating system.
System calls 提供 使用者級別 的程序來請求作業系統給的服務。
// process control, file Management, device management, information maintenance, communication - Describe the differences among short-term, medium-term, and long-term scheduling.
- short-term (CPU scheduler) —
CPU 工作排程
selects from jobs in memory those jobs that are ready to execute and allocates the CPU to them. - medium-term —
常用於分時系統的排程器。當記憶體不夠的時候，需要暫時將部分的執行程序搬出，將新來的程序載入，置換機制被建置用來移除部份在記憶體執行中及恢復那些被暫時移除的程式。
used especially with time-sharing systems as an intermediate scheduling level. A swapping scheme is implemented to remove partially run programs from memory and reinstate them later to continue where they left off. - long-term (job scheduler) —
將 job 變成 process 的工作排程，將工作從硬碟載入到主記憶體中。
determines which jobs are brought into memory for processing.
- short-term (CPU scheduler) —
- Can a multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a single-processor system? Why?
- A multithreaded system comprising of multiple user-level threads cannot make use of the different processors in a multiprocessor system simultaneously. The operating system sees only a single process and will not schedule the different threads of the process on separate processors. Consequently, there is no performance benefit associated with executing multiple user-level threads on a multiprocessor system.
- 以 user-level hreads 實現 multithread 的程式，在多處理器系統中不能比在單處理機系統中有更好的效率， 因在多處理機系統中之作業系統不會將多個 CPU 同時分配給該 user-level multithread 程式。
Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:
Process Burst Time Priority P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2The processes are assumed to have arrived in the order P1,P2,P3,P4,P5, all at time 0.
- (a) Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a nonpreempitive priority(a small priority number implies a higher priority), and RR(quantum = 1) scheduling.(5%)
- (b) What is the turnaround time of each process for each of the scheduling algorithms in part(a).(5%)
- (c) What is the waiting time of each process for each of the scheduling algorithms in part(a).(5%)
(d) Which of the schedules in part (a) results in the minimal average waiting time(over all processes)? (5%)
請參照上附的習題解法。
96 期中考
FCFS, SJF, Priority, Round-Robin and Multilevel Queue
Which can be preemptive ? (5%)- preemptive 可搶先
SRTF (剩餘最短優先)、Priority (優先權優先)、Multilevel Queue (多層佇列)、RR - non-preemptive 不可搶先
FCFS (先到先服務)、SJF (最短工作優先)、Priority (優先權優先) - Priority (優先權優先) 屬於可搶先跟不可搶先。
- 可搶先的定義為非自願性被踢出 CPU。
- preemptive 可搶先
What are the four main purposes of an operating system ? (10%)
- Managing programs
- Managing Memory
- Handling input and output
- User Interface
Please give a detail description on the differences among the terms multiprocessing, multitasking and multithreading. (15%)
- multiprocessing
具有多個處理器，在同一時間可以在各自處理器上運行程序。 - multitasking
執行單一使用者的多個行程，利用排程器讓每一個行程都在平均時間內解決。 - multithreading
可以將程序切成好幾個執行緒，若硬體可以同時執行多個執行緒，效率將會上升，如果不能，由於速度夠快看起來也很像多個執行緒同時運行。
- multiprocessing
What are the differences between a trap and an interrupt ? What is the use if each function ? (20%)
- Trap:
軟體產生 system call
an exception in a user process.
ex. system call (software divide-by-zero) - Interrupt:
硬體產生 signal
something generated by the hardware.
ex. IO-complete interrupt (hardware generated) - 兩者相同之處
從 User Mode 切換到 Kernel Mode。
兩者都算是 interrupt 中斷指令。
- Trap:
What is the purpose of system calls, Please describe three general methods that be used to pass parameters to the operating system. (10%).
- System call 由作業系統提供 API interface 給 user program，可以藉由 system call 向作業系統請求服務，作業系統接收到請求後，執行完報告結果給 user program。
- [方法1] Registers
利用Registers ( 暫存器 )儲存這些參數
優：速度快
(∵不用作記憶體的存取 )
缺：不適用於參數個數多的情況 - [方法2] Memory
將參數利用 Table 或 Block 的方式儲存在 Memory 中，同時利用一個 Register 記錄此 Table 或 Block 的起始位址，並傳給O.S.
優：適用於參數個數較多的情況
缺：速度慢 - [方法3] Stack
利用System Stack (堆疊 )。要存放參數時，將之Push 到Stack Stack， 再由O.S.從Stack中Pop 取出參數 。
Stack在系統中比Register多一些(可用Mem. 或其它硬體(如：Register)來實作此Stack)
What is a process ? Draw the diagram of Process State. And describe every state. (15%)
What are the differences between thread and process ? Why do threads have much shorter context switching times ? (10%)
| Thread | Process | |---------------------------------|---------------------------| | Light Weight Process | Heavy Weight Process | | | | | 同一個Task (或 Process ) 內的 | 不同的Process之間無共享的| | Threads可以共享 Code Section, | Address Space，互為獨立。| | Data Section, 及O.S. Resources | | | | | Context Switching 負擔輕 | 負擔重 | | | Thread的管理(Management)成本低 | 成本高 | (管理項目： Creation, | | Scheduling, Context, Switching | | Switching…etc.) | | | | 一個Task內有多條Threads存在 | 一個Task內只有一條Thread | Process (Task) 內的某 Thread | | 被 Block，則可切到其它Thread | | 執行。此時，若 Process 內只要還有 | Thread 在執行，則 Process 不會被 BlockWhat is Multilevel Feedback-Queue scheduling ? (5%)
定義： 與Multilevel Queue的定義相似，差別在於允許 Process 在各佇列之間移動 ，以避免Starvation 的情況。 * 採取類似 “Aging” 技術，毎隔一段時間就將 Process 往上提升到上一層 Queue 中。∴在經過有限時間後，在 Lower Priority Queue 中的 Process 會被置於 Highest Priority Queue 中。故無 Starvation。 * 亦可配合降級之動作。當上層 Queue 中的 Process 取得 CPU 後，若未能在 Quantum 內完成工作，則此 Process 在放棄 CPU 後，會被置於較下層的 Queue 中。Please draw the Gantt charts for the following processes for the problems shown below.
(a) Round-Robinm time quantum = 1 (5%)
(b) Shortest-remaining-time-first (Preemptive SJF) (5%)Arrival Time Brust Time P1 0 4 P2 1 2 P3 2 3 P4 5 4 P5 6 3 (a) Time : 0 Queue: P1 0 1 +---+ P1 先丟入 P2, P1 因為超時丟入，此時執行 P2 Time : 1 Queue: P2, P1 0 1 2 +---+---+ P1 P2 丟入 P3, P2 因為超時丟入，此時執行 P1 Time : 2 Queue: P1, P3, P2 0 1 2 3 +---+---+---+ P1 P2 P1 P1 因為超時丟入，此時執行 P3 Time : 3 Queue: P3, P2, P1 0 1 2 3 4 +---+---+---+---+ P1 P2 P1 P3 P3 因為超時丟入，此時執行 P2 Time : 4 Queue: P2, P1, P3 0 1 2 3 4 5 +---+---+---+---+---+ P1 P2 P1 P3 P2 P2 完成，P4 抵達丟入，此時執行 P1 Time : 5 Queue: P1, P3, P4 0 1 2 3 4 5 6 +---+---+---+---+---+---+ P1 P2 P1 P3 P2 P1 P5 抵達丟入，P1 超時丟入，此時執行 P3 Time : 6 Queue: P3, P4, P5, P1 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+ P1 P2 P1 P3 P2 P1 P3 P3 超時丟入，此時執行 P4 Time : 7 Queue: P4, P5, P1, P3 0 1 2 3 4 5 6 7 8 +---+---+---+---+---+---+---+---+ P1 P2 P1 P3 P2 P1 P3 P4 P4 超時丟入，此時執行 P5 Time : 8 Queue: P5, P1, P3, P4 0 1 2 3 4 5 6 7 8 9 +---+---+---+---+---+---+---+---+---+ P1 P2 P1 P3 P2 P1 P3 P4 P5 P5 超時丟入，此時執行 P1 Time : 6 Queue: P1, P3, P4, P5 0 1 2 3 4 5 6 7 8 9 10 +---+---+---+---+---+---+---+---+---+---+ P1 P2 P1 P3 P2 P1 P3 P4 P5 P1 P1 完成，此時執行 P3 Time : 10 Queue: P3, P4, P5 0 1 2 3 4 5 6 7 8 9 10 11 +---+---+---+---+---+---+---+---+---+---+---+ P1 P2 P1 P3 P2 P1 P3 P4 P5 P1 P3 P3 完成，此時執行 P4 Time : 11 Queue: P4, P5 0 1 2 3 4 5 6 7 8 9 10 11 12 +---+---+---+---+---+---+---+---+---+---+---+---+ P1 P2 P1 P3 P2 P1 P3 P4 P5 P1 P3 P4 ... 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ P1 P2 P1 P3 P2 P1 P3 P4 P5 P1 P3 P4 P5 P4 P5 P4
課本習題快取區
ch 5
- 5.9 Why is it important for the scheduler to distinguish I/O-bound programs
from CPU-bound programs?
為什麼排程器需要需分 IO 密集程式 和 CPU 綁定程式 ?
Answer: I/O-bound programs have the property of performing only a small amount of computation before performing I/O. Such programs typically do not use up their entire CPU quantum. CPU-bound programs, on the other hand, use their entire quantum without performing any blocking I/O operations. Consequently, one could make better use of the computer’s resouces by giving higher priority to I/O-bound programs and allow them to execute ahead of the CPU-bound programs.
IO 密集程式占用 CPU 的時間比較少，大部分時間等在等待 IO。相反地 CPU 綁定程式則會大幅度占用 CPU 的時候，因為沒有 IO 操作的堵塞。而 CPU bound 的程序因此而得到了很多調度機會並且每次都能把CPU run完。故在這樣的系統裡要給 I/O bound 的程序更高的優先級使其能被調度得更多些。
- 5.10 Discuss how the following pairs of scheduling criteria conflict in certain
settings.
a. CPU utilization and response time // CPU 使用率 和 回應時間 的比較
b. Average turnaround time and maximum waiting time // 平均運轉時間 和 最大等待時間 的比較
c. I/O device utilization and CPU utilization // IO 裝置使用率 和 CPU 使用率 的比較
Answer:
a. CPU utilization and response time: CPU utilization is increased if the overheads associatedwith context switching isminimized. The context switching overheads could be lowered by performing context switches infrequently. This could, however, result in increasing
the response time for processes.
CPU 的使用率(utilization)上升時，切換工作的次數(context-switches)就會少，由於切換次數少，則回應時間(response time)就會上升。b. Average turnaround time and maximum waiting time: Average turnaround time is minimized by executing the shortest tasks first. Such a scheduling policy could, however, starve long-running tasks and thereby increase their waiting time.
平均運作時間(average turnaround time) 的最小化可以藉由最短工作優先的方式，但是這將會使得長工作飢餓，如此會增加最大等待時間。c. I/O device utilization and CPU utilization: CPU utilization is maximized by running long-running CPU-bound tasks without performing context switches. I/O device utilization is maximized by scheduling I/O-bound jobs as soon as they become ready to run, thereby incurring the overheads of context switches.
CPU 使用率的上升盡可能讓 CPU 密集工作長時間運行 (減少 IO 或者其他的中斷所引發的上下文切換)，IO 裝置使用率的上升靠的是讓排入的 IO 密集工作立即地運行，但這會增加上下文切換的開銷。
- 5.11 Consider the exponential average formula used to predict the length of the next CPU burst.What are the implications of assigning the following values to the parameters used by the algorithm?
使用指數平均公式去預測下一次的 CPU burst。 t0 預估時間。
a. a = 0 and t0 = 100 milliseconds
b. a = 0.99 and t0 = 10 milliseconds
Answer: When a = 0 and t0 = 100 milliseconds, the formula always makes a prediction of 100 milliseconds for the next CPU burst. When a = 0.99 and t0 = 10 milliseconds, themost recent behavior of the process is given much higher weight than the past history associated with the process. Consequently, the scheduling algorithm is almost memoryless, and simply predicts the length of the previous burst for the next quantum of CPU execution.
當 a = 0 時，預測的時間總會是 100 milliseconds，而當 a = 0.99 時，將會高度依賴近期幾次的結果，而對於歷史關聯只有較輕的權重。
// t(n+1) = a * 上一次實際時間 + (1 - a) * t(n)