2021期末考題

--- title: 2021期末考題 tags: 作業系統 --- [作業系統期末考題共編](https://docs.google.com/document/d/1mr1tn2gGtzGRGe7hwdqZH0YFfFwRJNKG9n1L7nuMlVM/edit) # 中央大學 2021 作業系統期末(線上考試) ## 單選題 :::info 1. Which of the following descriptions regarding the multithread models are correct? I. In One-to-One model, only one thread can access the kernel at a time on multiprocessors. II. In Many-to-One model, the entire process will block if a thread makes a blocking system call. III. In Many-to-Many model, the number of kernel threads can be specific to either a particular application or a particular machine. IV. In One-to-One model, developers can create as many user threads as necessary. V. The two-level model is a variation of the Many-to-Many model. ::: I. In ~~One-to-One~~ Many-to-One model, only one thread can access the kernel at a time on multiprocessors. In One-to-One model, it supports multiple threads to execute in parallel on microprocessors. ![](https://i.imgur.com/niCrlfH.png) ![](https://i.imgur.com/lfD1zao.png) IV. In ~~One-to-One~~ Many-to-Many model, developers can create as many user threads as necessary. In One-to-One model, creating user thread requires the corresponding Kernel thread. ![](https://i.imgur.com/12XV1zg.png) ![](https://i.imgur.com/7sG2KDo.png) [參考網站](https://www.tutorialspoint.com/operating_system/os_multi_threading.htm) *** :::info 2. One soft real-time system has five periodic tasks, with periods of 50, 100, 150, 200 and 300 ms each. Assume these tasks require 10, 25, 15, 40 and C ms of CPU time, respectively.What is the largest value of C for the system to be schedulable? ::: 10/50+25/100+15/150+40/200+c/300<=1 (225+c)/300<=1 c<=75 *** :::info 3. After executing the program shown below, what is the output on the screen? ```c= main(){ int status; printf(“A”); if(fork()!=0){ waitpid(-1,&status,0); printf(“B”); }else{ printf(“C”); } printf(“D”) } ``` ::: 1. 執行到printA 2. fork()產生父行程與子行程，父行程在waitpid()等待子行程結束 3. 子行程的fork=0，因此進入else進行printC，再來printD，子行程結束 4. 父行程繼續執行，printB，接著printD 故順序為ACDBD *** :::info 4. You have a 7200-rpm disk with a track-to-track seek time of 1 ms. The disk has 400 sectors on each track. Each sector has 1KB. What is the maximum date transfer rate in MB/sec? ::: 7200rpm = 7200轉/分鐘 = 120轉/秒一圈有400個sector，又每個sector有1KB的資料 =>每圈400KB 120*400 = 48,000KB/sec(每秒可以有這麼多資料) 轉成MB = 48MB/sec 7200-rpm/60 x 400 x 1KB = 48 MB/sec *** :::info 5. Which of the following statement is true? A. Spinlocks are not appropriate for multi-core systems. B.Critical sections cannot be preserved by disabling kernel preemption. C.More than one process can be active within a monitor. D.Wait and signal of a counting semaphore cannot be implemented with multiple binary semaphores. E.All of the above are incorrect. ::: A.Spinlocks are not appropriate for ~~multi-core~~ single-processor systems. Because the condition that would break a process out of the spinlock can be obtained only by executing a different process. B.Critical sections ~~cannot~~ can be preserved by disabling kernel preemption. C.~~More than~~ Only one process can be active within a monitor. D.Wait and signal of a counting semaphore ~~cannot~~ can be implemented with multiple binary semaphores. 參考網址：https://tinyl.io/4LSy 選 E 以上皆非 *** :::info 6. Consider a two-processor system running three processes P1, P2 and P3. The processes P1 and P2 run on the first CPU, while the process P3 runs on the second CPU. All these three processes share one mutually exclusive resource. Suppose that processes never migrate form a CPU to the other one. In terms of CPU utilization and hardware cost, which one of the following design options is improper? A.None of the above. B.Using interrupt disabling to synchronize processes P1 and P2. C.Using spin locks to synchronize processes P1 and P3. D.Using interrupt disabling to synchronize processes P1 and P3. ::: 因為如果 multiprocessor system採用 interrupt disabling，則需要將所有的CPU核心關掉，而這相當的耗時，但只關掉一顆CPU核心依然會產生錯誤，因此 interrupt disabling 不適合用在 multiprocessor system，只適合用在單核心上，而多核心則使用 spin locks 較為合適。 選 D *** :::info 7. Which of the following statements is false? A. The technology of virtual memory system may fail for some specific CPU instruction sets. B. The memory hierarchy does not always guarantee efficiency in information retrieval. C. In practice, the SJF scheduling algorithm may not be optimal in average waiting time. D. Working set theory can be used to control the level of multiprogramming. E. System calls are only executed with privileged instructions which are not supposed to be used by user programs. ::: E. System calls are ==only== executed with privileged instructions which are not supposed to be used by user programs. 但 System calls 也可以 used by user programs 因此選 E *** :::info 8. Which of the requirements for a solution to the critical-section problem are not satisfied for the following program? ```cpp //lock is a shared data and initialized to 0 while(1){ key=1; while(key){ atomic_swap(lock,key); <Critical Section> Lock=0; <Remainder Section> } } ``` A.Progress B.Mutual Exclusion C.Bounded Waiting D.No preemption ::: atomic_swap() -> 滿足 No preemption(不可被打斷)、Mutual Exclusion 但主要是因為此程式沒有設定等待 critical-section 的時間的界值(A bound must exist on the number of times) 故選 C ![](https://i.imgur.com/J2zR35a.png) 網站：https://www.geeksforgeeks.org/introduction-of-process-synchronization/ ![](https://i.imgur.com/IJA7VW2.png) 網站：https://sls.weco.net/node/21326 *** :::info 9. Consider the following snapshot of a system and use banker’s algorithm to following questions. ![](https://i.imgur.com/5ibvYQX.png) 1.If a request from process P1 arrives for (1, 1, 0, 0), can the request be granted immediately? 2.If a request from process p4 arrives for (0, 0, 2, 0), can the request be granted immediately? ::: 算出Need = Max-Allocation | | A | B | C | D | | -------- | -------- | -------- | -------- | -------- | | P0 | 2 | 2 | 1 | 1 | | P1 | 2 | 1 | 3 | 1 | | P2 | 0 | 2 | 1 | 3 | | P3 | 0 | 1 | 1 | 2 | | P4 | 2 | 2 | 3 | 3 | 1. P1要求(1,1,0,0) < Available(3,3,2,1) 如果立刻同意，P1的Allocate=(4,2,2,1)，P1的Need=(1,0,3,1)，Available=(2,2,2,1) 可以找到safe sequence： P0：P0's need(2,2,1,1)<Available(2,2,2,1) => if P0 done => Available(4,2,2,2) P3：P3’s need(0,1,1,2)<Available(4,2,2,2) => if P3 done => Available(5,5,3,4) 因Available(5,5,3,4)已超越所有Need，故一定存在safe sequence [圖解](https://drive.google.com/file/d/1NL9Vo7ie9kxR0IgfMAW8JZkPpGUfcQuu/view) 2. P4要求(0,0,2,0) < Available(3,3,2,1) 如果立刻同意，P4的Allocate=(1,4,5,2)，P4的Need=(2,2,1,3)，Available=(3,3,0,1) 因大家都要C，沒C不能做，所以找不到safe sequence ![](https://i.imgur.com/9i8vULF.png) 答案為 1 是 YES，2 是 NO *** :::info 10. The banker’s algorithm is used for deadlock-avoidance. For a system with n processes and m types of resources, what is the order of complexity of this algorithm? ::: The time complexity of the Banker's algorithm as a function of the number n of processes and m of resources is o(n\*n\*m) *** :::info 11. Which of the following is not a necessary condition for the happening of a deadlock? A.Resources not released by a terminated process B.Circular waiting in the resource allocation graph C.Mutual exclusion to resources D.Resource hold and wait by processes E.Resource allocation without preemption ::: ![](https://i.imgur.com/mSTYM3l.png) 故選 A 中文參考網站：https://mropengate.blogspot.com/2015/01/operating-system-ch7-deadlock.html 英文參考網站：https://afteracademy.com/blog/what-is-deadlock-and-what-are-its-four-necessary-conditions *** :::info 12. Suppose that there is a machine with 32-bit addresses and a two-level page table. Note that the first 10 bits of an address is an index into the first level page table and the next 10 bits are an index into a second level page table. The page tables are stored in memory and each entry in the page tables is 4 bytes. Suppose the space allocated to a specific process is 64 Mbytes. How many pages are occupied by this process? ::: 32bit addr -10 first level -10 second level = 12bits ( page offset ) 12bits 用來做 page offset，故 page size = 2^12bytes = 4KB 最後再用64MB = 2^26 bytes，2^26 / 2^12 = 2^14 pages *** :::info 13. (Continued from the previous question.) How much space is occupied in memory by the page tables for the specific process? A.4 kbytes B.None of the above C.68 kbytes D.64 kbytes E.16 kbytes ::: page table = PT outer PT size = outer PT 的 entrys 數量 \* entry size 因此 outer PT size = 2^10 \* 4 Bytes = 4KB 需要 2^14 (總共需要的pages數) / 2^10 (一個 inner PT 的 entry 數) = 2^4 個 inner page 因此需要的 inner PT size = 16 \* 4KB = 64KB 64KB + 4KB = 68 KB *** :::info 14. Consider a tiny paging system that has 16 KB physical memory, and the frame size is 1 KB. Let the logical address have 16 bits. The page table uses single-level direct index. Which one of the following is not correct? A.The page table requires 320 bits, including the valid-invalid bits. B.The frame number has 4 bits C.There are 16 entries in the page table. D.A page-table entry stores a frame number E.The page number has 6 bits ::: frame number = 16K(memory) / 1K(frame size)= 16 (總共有多少個frame) = 2^4 → 4bits ( B ) page number = 16 - 10(1K = 2^10) = 6bits ( E ) page table entry = 2^6 = 64 ( C ) for each table entry: 4bits(frame#)+1bit(valid-invalid bit)=5bits 64 entries * 5bits = 320 bits ( A ) 選 C ## 多選題 *** :::info 15. Which are correct for deadlocks? (多選題) A.For the deadlock-avoidance scheme, if a process requests a resource that is currently available, it should be allocated to the process. B.If a resource-allocation graph has a cycle, then the system must be in a deadlocked state. C.To ensure that the hold-and-wait condition never occurs, the protocol requiring each process to request and be allocated all its resources before it begins execution can work. D.None of the above. E.In general, we cannot prevent deadlocks by denying the mutual-exclusion condition. ::: A. deadlock avoidance在分配資源前會動態偵測，以確保處於安全狀態(safe state)。某些資源可能不能被立即分配，行程必須等候以免產生deadlock B. 就算RAG圖中有cycle，也不一定會產生deadlock (如下圖) ![](https://i.imgur.com/wzUYyfN.png) 網頁參照：https://ithelp.ithome.com.tw/articles/10206155 選 C、E *** :::info 16. Which of the following statements on the concept of deadlocks is not correct? (多選題) A. If there is a cycle of resource allocation graph for a system with single instance resource, it will be in a deadlock state. B. If there is a cycle of resource allocation graph for a system with resource of multiple instances, it may not be in a deadlock state. C. If we use banker’s algorithm to control the resource request and allocation, and when we find the system is unsafe, and still grant the resource request, the system will enter the deadlock state. D. If a system is in the safe state, it will not be in a deadlock state. E. If a deadlock situation arises, the four conditions of mutual exclusion, hold and wait, no preemption, and circular wait must hold simultaneously. ::: A. ![](https://i.imgur.com/nIG33Yh.png) B. ![](https://i.imgur.com/sxa0RCs.png) C. 只是有可能而已(若最壞情形會進)，不一定 D. ![](https://i.imgur.com/d3kUquC.png) E. ![](https://i.imgur.com/tt4QWbD.png) 中文參考網站：https://mropengate.blogspot.com/2015/01/operating-system-ch7-deadlock.html 英文參考網站：https://afteracademy.com/blog/what-is-deadlock-and-what-are-its-four-necessary-conditions 選 C *** :::info 17. Assume that the memory access time is 200 ns, the average page-fault service time including page-fault time and twice memory access time is 10 ms, and the page fault ratio is 15%. (多選題) A.If we want the effective memory time is less than 50 μs, the page fault ratio must be less than 0.60%. B.None of the above. C.The effective access time is 1500170 ns. D.The effective access time is 1500180 ns. E.If we want the effective memory time is less than 100 μs, the page fault ratio must be less than 0.15%. ::: 沒有page fault ：200 ns、85% 有page fault：10 ms、15% CD：Effective access time：200\*85% + 10\*10^6\*15% = 1500170ns A：0.2(1-x)+10000x < 50、x 約 < 0.5% E : 0.2(1-x)+10000x < 100、x 約 < 1% 選 C *** :::info 18. Which of the following statements are correct? (多選題) A.The current Linux kernel is a nonpreemptive kernel and a process running in a kernel mode could not be preempted. B.Priority inheritance protocols can resolve race conditions in real time systems. C.Spinlocks are appropriate for uni-processor systems. D.A nonpreemptive kernel is free from race conditions on kernel data structures. E.The critical-section problem could be solved by disabling interrupts while accessing a shared variable in a uni-processor environment. ::: A. 現在的Linux版本是可以被搶先的。 B. Priority inheritance protocols can resolve Priority Inversion C. Spinlocks are appropriate for ~~uni-processor~~ multi-processor systems. D. True，因為 nonpreemptive 不允許被搶先，因此在kernel中一次只會有一個程序被執行，所以沒有 race conditions 的問題 選 D E *** :::info 19. Consider the page replacement algorithms FIFO (first-in first-out), LRU (least-recently used), and OPT (optimal). Which of the following cases are possible? (多選題) A. Implementing OPT in real operating systems B. LRU causes more page faults with a larger number of here frames C. FIFO outperforms LRU D. LRU outperforms FIFO E. FIFO, LRU and OPT have the same number of page faults ::: A. OPT 是理想狀態最佳演算法，要預測未來，很難在現實中實現 B. LRU和OPT都是stack algorithm，不會發生Belady’s Anomaly(=cause more page faults with larger frame) (會發生Belady's Anomaly：FIFO、Second Chance、Random) C/D. 我們只能知道OPT是最佳的其餘都有可能 E 有可能發生中文參考網站：https://ithelp.ithome.com.tw/articles/10208354 選 CDE *** :::info 20. Which of the following statements are correct? (多選題) A. For the banker’s algorithm to work correctly, when a new process enters the system, it must declare the maximum number of instances of each resource type that it may need; otherwise, this algorithm will fail. B. Preemptive kernel design cannot prevent the deadlock problem with kernel data structures from occurring in the kernel. C. The “hold and wait” and “circular wait” requirement conditions are redundant and thus one of them can be removed. D. None of the above. E. Deadlock condition refers to the situation where several processes are currently blocked waiting for some resources to be released by some of them. ::: B. https://www.ptt.cc/bbs/Grad-ProbAsk/M.1359386486.A.778.html C. Deadlock condition必須同時滿足mutual exclusion、==hold and wait==、no preemption、==circulate wait== 缺一不可 ![](https://i.imgur.com/tt4QWbD.png) 中文參考網站：https://mropengate.blogspot.com/2015/01/operating-system-ch7-deadlock.html 英文參考網站：https://afteracademy.com/blog/what-is-deadlock-and-what-are-its-four-necessary-conditions 選 ABE *** :::info 21. Which of the following statements are correct? (多選題) A. Page-table length register (PTLR) indicates size of the page table. B. None of the above. C. Page-table base register (PTBR) points to the page table. D. Page offset is combined with base address to define the virtual memory address that is sent to the memory unit. E. Page number is used as an index into a page table which contains base address of each page in virtual memory. ::: D. Page offset is combined with base address to define the ~~virtual~~ physical memory address that is sent to rhe memory unit. E. Page number is used as an index to page table which contains base assress of each page in ~~virtual~~ physical physical memory. 選 AC *** :::info 22. We have two process P1 and P2 which share a variable “c”. The variable “c” initializes to 5. There is an only statement which is "c=c+2" in P1. There is an only statement which is "c=c×2" in P2. When P1 and P2 run once at the same time respectively, please choose possible values for “c” in the end of two processes. (多選題) A. 8 B. 10 C. 12 D. 14 E. None of the above ::: share variable “c” = 5 將這些算式轉成機器碼： P1 ： c = c+2 ==1== register1 = c ==2== register1 = register1 + 2 ==3== c = register1 P2 ： c = c*2 ==4== register2 = c ==5== register2 = register2 * 2 ==6== c = register2 交換一下執行順序： 123456 => c=14 456123 => c=12 142536 => c=10 142563 => c=7 故選 BCD *** :::info 23. Which of the following statements are correct about contiguous memory management? (多選題) A. First-fit is better than best-fit in terms of speed utilization. B. Best-fit is better than first-fit in terms of storage utilization. C. All of three ways for contiguous allocation have the internal fragmentation problem. D. None of the above. E. Best-fit is better than worst-fit in terms of speed utilization. ::: ![](https://i.imgur.com/j9ijV0k.png) 參考網站：https://ithelp.ithome.com.tw/articles/10226191 A. True，因為 First-fit 找到第一個合適的就放進去了，而 Best-fit 需要掃描過整個記憶體區，因此 First-fit speed 較快。 B. True，因為 Best-fit 會找到最剛好的空間去放 C. All of three ways for contiguous allocation have the ~~internal~~ external fragmentation problem. ![](https://i.imgur.com/CVXPixE.png) ![](https://i.imgur.com/hNNqKvi.png) ![](https://i.imgur.com/4UbSU2X.png) 參考網站：https://mropengate.blogspot.com/2015/01/operating-system-ch8-memory-management.html E. Best-fit 和 Worst-fits 都需要掃描過整個記憶體區，因此速度相同 選 AB *** :::info 24. Which of the following statements are correct about the virtual memory technique. (多選題) A. Increase the memory utilization. B. Decrease the CPU utilization. C. Increase the Multiprogramming degree. D. None of the above. E. Decrease the I/O frequency. ::: ![](https://i.imgur.com/fFs0lga.png) AC. True B. ~~Decrease~~Increase the CPU utilization. E. VM 是可以提高I/O的效能，但與 frequency 無關 選 AC *** :::info 25. Consider a system with five processes P0~P4 and four resource type A, B, C and D. Suppose at time T0, the resource allocation state is: ![](https://i.imgur.com/R5f9KQf.png) Which one is correct? (多選題) ::: Need = | | A | B | C | D | 是否 < Available | | -------- | -------- | -------- | -------- | -------- | -------- | | P0 | 1 | 0 | 2 | 3 | 否 | P1 | 3 | 1 | 0 | 0 | 否 | P2 | 0 | 0 | 4 | 0 | 否 | P3 | 2 | 0 | 0 | 0 | 否 | P4 | 0 | 1 | 0 | 0 | 是 1. (1,1,2,0) 給 P4，之後回收 P4 的 Allocation -> (2,1,2,2) 2. (2,1,2,2) 給 P3，之後回收 P3 的 Allocation -> (2,2,4,2) 3. (2,2,4,2) 給 P2，之後回收 P2 的 Allocation -> (3,2,4,5) 4. (3,2,4,5) 給 P1，之後回收 P1 的 Allocation -> (3,3,5,7) 5. (3,3,5,7) 給 P0，之後回收 P0 的 Allocation -> (5,4,6,7) 由上列可知先給 P4 的話，可以順利跑完。 因此 P4 is a safe sequence. *** :::info 26. Assume that the reference string of referenced page numbers is 5,0,1,3,2,1,1,5,4,2,4,0,5,1,2,3,2,4,1,5. There are 3 page frames in the system. Which of the following statements are correct? (多選題) A. If it uses the optimal algorithm, the number of page faults is 10. B. If it uses the LRU (Least Recently Used) algorithm, the number of page faults is 17. C. None of the above. D. If it uses the second-chance algorithm, the number of page faults is 15. E. If it uses the FIFO (First-In-First-Out) algorithm, the number of page faults is 16. ::: A：page faults is 11 ![](https://i.imgur.com/CYJZJ8W.png) B：False，16 ![](https://i.imgur.com/4A1orni.png) D：second chance : False，14 ![](https://i.imgur.com/iztIxar.png) E：FIFO page faults is 14 ![](https://i.imgur.com/2uk9Gnq.png) 參考中文網頁：https://ithelp.ithome.com.tw/articles/10208354 選 C *** :::info 27. Which of the following statements are correct? The less page size is, (多選題) A. The more I/O frequency is. B. The more page fault ratio is. C. The less internal fragmentation there is. D. None of the above. E. The less page table size is ::: A：True，page fault ratio 上升 -> 做更多的IO B：True，page size 愈小，page fault ratio 愈多 C：True，page size越小，page 內部的剩餘空間就越小 E： The ~~less~~ more page table size is，page table size = page table entries 數 * each PTE’s size, page table entries數上升 選 ABC *** :::info 28. Which of the following statements are correct? (多選題) A. None of the above. B. More programs can run concurrently with the virtual memory technique. C. Virtual memory is separation of user physical memory from logical memory. D. Virtual address space is a logical view of how process is stored in memory. E. Only part of the program needs to be in memory for execution with the virtual memory technique. ::: C：Virtual memory is separation of user ~~physical~~ logical memory from ~~logical~~ physical memory. 選 BDE *** :::info 29. Which of the following statements are correct? (多選題) A. The modify bit in demand paging is modified by the operating system. B. It uses dirty bit to reduce overhead of page replacement in the operating system. C. The copy-on-write technique increase the time of the process creation. D. The loop structure in a program affects the number of page faults. E. None of the above. ::: A：Dirty(modify) bit: one bit for each page frame, set by hardware whenever the page is modified. If a dirty page is replaced, it must be written to disk before its page frame is reused. C: correct, increase the time of the process creation(增加進程創建的時間) -> 但答案是對，所以題目想說的應該是減少process create 的時間(increase efficiency)，因為只有被修改的page才要真的複製，助教確認是題目有問題 選 BD *** :::info 30. Which of the following statements are correct? (多選題) A. A mutex is used to protect a critical section of code. It cannot protect a shared variable. B. None of the above. C. Dynamic linking must needs a support from the operating system. D. Dynamic loading must needs a support from the operating system. E. There is a hashing page table which of hashing function is "H(p)=p mod 104" in the system. Each entry in page table needs 4 bytes. So, the hashing page table size is 412 bytes. ::: A. mutex lock就是要避免race condition，當然可以保護share variable C. True，動態連結器 (Dynamic Linker)需要 OS 協助檢查 library 是否已讀取 D. ![](https://i.imgur.com/9u66v4Q.png) E. There is a hashing page table which of hashing function is "H(p)=p mod 104" in the system. Each entry in page table needs 4 bytes. So, the hashing page table size is ~~412~~416 bytes. 中文參考網頁：https://mropengate.blogspot.com/2015/01/operating-system-ch9-virtual-memory.html 選 C *** :::info 31. Which of the following statements are correct? (多選題) A. All of deadlock necessary conditions (i.e. mutual exclusion, hold and wait, no preemptive and circular waiting) exist, the system must be in deadlock. B. The resources allocation graph has no cycle, the system must not be in deadlock. C. The resources allocation graph has a cycle, the system must be in deadlock. D. None of the above. E. If Banker’s algorithm returns an unsafe, it means the resource request must make the system in deadlock. ::: A. mutual exclusion, hold and wait, no preemptive and circular waiting 是 deadlock 發生的必要條件，但如果都符合也不一定會產生 deadlock C. 就算RAG圖中有cycle，也不一定會產生deadlock (如下圖) ![](https://i.imgur.com/wzUYyfN.png) 網頁參照：https://ithelp.ithome.com.tw/articles/10206155 E. 不一定，只是有可能產生 選 B *** :::info 32. Which statements regarding process synchronization are true? (多選題) A. When a semaphore blocks a process, the process is moved to ready state. B. Monitor is typically supported as OS system calls. C. Monitor can do some synchronization which is impossible to be done by semaphores. D. Semaphore is busy waiting while monitor is not. E. Semaphores are typically more difficult to use than monitor. ::: A. When a semaphore blocks a process, the process is moved to ~~ready state~~ waiting state. ![](https://i.imgur.com/6knskqt.png) B. Monitor 是 programming language，不是system call C. ~~Monitor~~Semaphores can do some synchronization which is impossible to be done by ~~semaphores~~monitor. D. semaphore也能是not busy waiting ![](https://i.imgur.com/IDS5PcY.png) 選 E *** :::info 33. Which of the following scheduling algorithms could result in starvation? (多選題) A. Round robin B. Multilevel Queue C. First-come, first-served D. Shortest job first E. Priority ::: A： round robin 為輪流，故每個人都有機會輪到 B： Multilevel Queue，仍然有Priority存在，故有可能starvation C： FCFS，先來先做，故只要排隊就能做到 D： SJF，要花很多時間完成的，永遠排不到 E： Priority低的，永遠無法做到另外：注意Multilevel Feedback Queue，與Multilevel Queue的差別，Multilevel Feedback Queue有機制可以預防starvation 選 BDE *** :::info 34. Which of the following statements about memory management is correct? (多選題) A. A system can detect thrashing by using a figure, in which CPU utilization is plotted against the execution time. B. For first-in-first-out page replacement, the page-fault rate will definitely not increase as the number of frames increases. C. To allocate contiguous memory from free boles, the best-fit algorithm is the optimum solution in memory utilization. D. None of the above is correct. E. Pure segmentation suffers from internal fragmentation. ::: A. A system can detect thrashing by using a figure, in which CPU utilization is plotted against the ~~execution time~~ degree of multiprogramming. ![](https://i.imgur.com/g3Yc4XP.png) B. FIFO 有可能出現 Belady’s anomaly，frame 越大越容易有 page-fault C. 比較多人使用 first-fit E. Pure segmentation ~~suffers from~~is free of internal fragmentation. 選 D --- ## 題組 ### 題組一 :::success Suppose that two long running processes, P1 and P2, are running in a system for different users, and there are no other processes in the system Process P1 consists of three threads and process P2 consists of two threads. Assume that the threads never block and that the processes are entirely resident in primary memory. ::: :::info 35. What percentage of CPU time will process P1 get if the threads of the P1 and P2 are kernel threads entirely? A. 70% B. 40% C. 50% D. 60% ::: P1：3 threads P2：2 threads If the threads are kernel threads, they are independently scheduled and each of the five threads will get a share of the CPU. Thus, the 3 threads of P1 will get 3/5 of the CPU time. That is, P1 will get 60% of the CPU. 選 D *** :::info 36. What percentage of CPU time will process P2 get if the threads of the P1 and P2 are user threads entirely? A. 60% B. 70% C. 50% D. 40% ::: If the threads are user threads, the threads of each process map to one kernel thread, so each process will get a share of the CPU. The kernel is unaware that P1 has three threads. Thus, P1 will get 50% of the CPU. 選 C 參考資料：https://student.cs.uwaterloo.ca/~cs350/S06/midSol.pdf --- ### 題組二 :::success Consider the following processes: ![](https://i.imgur.com/ar458hZ.png) ::: :::info 37. Suppose we are using a non-preemptive Shortest-Job-First scheduler. Write the execution order of these processes. A. ADBC B. ACBD C. ABDC D. ABCD ::: 時間越短越優先 選 B --- :::info 38. Suppose we are using a non-preemptive Shortest-Job-First scheduler. What is the average waiting time? A. 4 B. 6 C. 3 D. 5 ::: (3+6+7)/4 = 4 選 A --- :::info 39. Now suppose we are using a preemptive Round-Robbin scheduler with a time quantum of 4 units. Write the execution order of these processes. A. ACDB B. ACBDB C. ABCAD D. ABCD ::: 選 C --- :::info 40. Now suppose we are using a preemptive Round-Robbin scheduler with a time quantum of 4 units. What is the average waiting time? A. 3 B. 5 C. 4 D. 6 :::