# 2021期末考古試寫
###### tags: `作業系統`, `109-2`
:::warning
 **此條目需要補充更多來源。** (2021年6月30日)
請協助補充多方面可靠來源以改善這篇條目，無法查證的內容可能會因為異議提出而移除。
:::
[TOC]
## Q1 Multithread Models
**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.
:::success
**Ans. II, III, V**
I. Many-to-One
IV. Many-to-many
:::
## Q2 Scheduling Periodic Task
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?
:::success
**Ans. 75ms**
$10/50 + 25/100 + 15/150 + 40/200 + C/300 <= 1$
$C <= 75$
:::
## Q3 FORK
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”)
}
```
:::success
**Ans: ACDBD**
A
(*fork*)
C (forkpid == 0)
D (forkpid == 0)
B (forkpid != 0)
D (forkpid != 0)
:::
## Q4 Disk (Transfer Rate)
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?
:::success
**Ans: 48**
- 7200rpm = 120rps
- 一圈有 400 個 sector，每個 sector 有 1KB 的資料 => 每圈 400KB = 0.4MB
- 120/s * 0.4MB = 48 MB/s
:::
## Q5 Process Synchronization (Semaphores, Crictical Section and Spinlocks)
**Which of the following statement is true?**
A. Wait and signal of a counting semaphore cannot be implemented with multiple binary semaphores.
B. Critical sections cannot be preserved by disabling kernel preemption.
C. Spinlocks are not appropriate for multi-core systems.
D. All of the above are incorrect.
E. More than one process can be active within a monitor.
:::success
**Ans: D**
A. counting semaphore 可利用 binary semaphore 制定
B.
C. not appropriate for single-core systems (see [here at 5.4](https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/5-web.pdf))
E. Only one
:::
## Q6
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 interrupt disabling to synchronize processes P1 and P3.
D. Using spin locks to synchronize processes P1 and P3.
:::success
**Ans: C**
From 共編:
- 如果 multiprocessor system 採用 interrupt disabling，則需要將所有的CPU核心關掉，而這相當的耗時
- 但只關掉一顆CPU核心依然會產生錯誤，因此 interrupt disabling 不適合用在multiprocessor system，只適合用在多核心上，
- 單核心則使用 spin locks 較為合適
:::
## Q7
Which of the following statements is **false**?
A. Working set theory can be used to control the level of multiprogramming.
B. The technology of virtual memory system may fail for some specific CPU instruction sets.
C. System calls are only executed with privileged instructions which are not supposed to be used by user programs.
D. The memory hierarchy does not always guarantee efficiency in information retrieval.
E. In practice, the SJF scheduling algorithm may not be optimal in average waiting time.
:::success
**Ans: C**
C: (false) user: system call to have privileged instructions executed
B: Thrashing issue
E: may starve
:::
## Q8 Requirements of Critical Section
Which of the requirements for a solution to the critical-section problem are not satisfied for the following program?
```c=
//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>
}
}
```
:::success
**Ans. Bounded Waiting**
搶 Lock 以執行 CS
:::
## Q9 Banker's Algorithm
Consider the following snapshot of a system and use banker’s algorithm to following questions.
(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?
:::success
**Ans: Yes, Yes**
要求量都小於 Available，獲得後也小於各自的 max
:::
## Q10 Banker's Algorithm (Complexity)
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?
:::success
**Ans: $mn^2$**
:::
## Q11 Deadlock Requirements
Which of the following is not a necessary condition for the happening of a deadlock?
A. Circular waiting in the resource allocation graph
B. Resource allocation without preemption
C. Resources not released by a terminated process
D. Resource hold and wait by processes
E. Mutual exclusion to resources
:::success
**Ans: C**
**Necessary conditions [4x]** **((p)7 / 8.6)**
1. **Mutual exclusion** 在一個時間內，只能有一個 Process 使用資源
2. **Hold & Wait** 一個行程正掌握著某些資源，且正在等待其他資源
3. **No preemption** 資源只能由 Process 自願放棄，不能被要求放棄/徵收
4. **Circular wait** Process P1 在等 P0，P2 在等 P1， ...，Pn 在等 Pn-1，但是 P0 也排到隊伍內等 Pn
:::
## Q12 Q13 Pages
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?
- How much space is occupied in memory by the page tables for the specific process?
:::success
**Ans: $2^{14}$**
[1]
- Offset: 32 - 10 - 10 = 12 (bits)
- Page Size = 2^12 (bytes)
- 64MB / 2^12B = 2^14
[2]
:::
## Q14 Pages
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. There are 16 entries in the page table.
B. The frame number has 4 bits
C. The page number has 6 bits
D. The page table requires 320 bits, including the valid-invalid bits.
E. A page-table entry stores a frame number
:::success
**Ans: A**
16KB = 2^14 bits
1KB = 2^10 bits
Frame: 16KB / 1KB = 16 => 4-bit (B)
Page: 16bits - 10bits = 6-bits (C)
PTE: 2^6 = 64 (A!)
PTE Size: 64 * (4+1)bits = 320 bits (D)
:::
## Q15 Deadlock
Which are correct for deadlocks?
A. If a resource-allocation graph has a cycle, then the system must be in a deadlocked state.
B. None of the above.
C. For the deadlock-avoidance scheme, if a process requests a resource that is currently available, it should be allocated to the process.
D. In general, we cannot prevent deadlocks by denying the mutual-exclusion condition.
E. 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.
:::success
**Ans: DE**
A. not must
C. this is Deadlock *Prevention*, not *Avoidance*
D. 只要有一條件無法成立，deadlock 便無法發生
:::
## Q16 Deadlock
Which of the following statements on the concept of deadlocks is **not** correct?
A. 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.
B. If there is a cycle of resource allocation graph for a system with single instance resource, it will be in a deadlock state.
C. If a deadlock situation arises, the four conditions of mutual exclusion, hold and wait, no preemption, and circular wait must hold simultaneously.
D. If a system is in the safe state, it will not be in a deadlock state.
E. 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.
:::success
**Ans: A**
A. not must
:::
## Q17 Page Fault
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 100 μs, the page fault ratio must be less than 0.15%.
B. None of the above.
C. The effective access time is 1500170 ns.
D. If we want the effective memory time is less than 50 μs, the page fault ratio must be less than 0.60%.
E. The effective access time is 1500180 ns.
:::success
**Ans: C**
$10$ms = $10^7$ns
EAT: $200\times85\% + 10^7\times15\% = 1500170$ ns (C, E)
A: <1%
D: <0.5%
:::
## Q18
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. The critical-section problem could be solved by disabling interrupts while accessing a shared variable in a uni-processor environment.
D. Spinlocks are appropriate for uni-processor systems.
E. A nonpreemptive kernel is free from race conditions on kernel data structures.
:::success
**Ans: CE**
A: 曾經是，現在不是了
B: It can't. (But it solves "Priority Inversion" problem)
C: 如此可以輪流進入CS，並不被打斷
D: 比較適合使用 Preemptation 來控制
E: nonpreemptive 相當於一次只有一個行程在kernel中有動作，因此不會有 racing
:::
## Q19 Replacement Policy
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. LRU outperforms FIFO
B. FIFO outperforms LRU
C. FIFO, LRU and OPT have the same number of page faults
D. LRU causes more page faults with a larger number of here frames
E. Implementing OPT in real operating systems
:::success
**Ans: ABC**
ABC: 依測資而定，都有可能 (除非有選項說有演算法勝過 OPT：你不能超越神)
D: LRU 跟 OPT 一樣免疫 Belady’s Anomaly
E: if u can predict future, why u still be here
:::
## Q20 Deadlock
20
Which of the following statements are correct?
A. Preemptive kernel design cannot prevent the deadlock problem with kernel data structures from occurring in the kernel.
B. 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.
C. Deadlock condition refers to the situation where several processes are currently blocked waiting for some resources to be released by some of them.
D. None of the above.
E. The “hold and wait” and “circular wait” requirement conditions are redundant and thus one of them can be removed.
:::success
**Ans: ABC**
E: 四大訴求 缺一不可
:::
## Q21 Pages
Which of the following statements are correct?
A. None of the above.
B. Page-table length register (PTLR) indicates size of the page table.
C. Page-table base register (PTBR) points to the page table.
D. Page number is used as an index into a page table which contains base address of each page in virtual memory.
E. Page offset is combined with base address to define the virtual memory address that is sent to the memory unit.
:::success
**Ans: BC**
DE: in Physical memory, not VM (Process 認為 Page 都會在 physical，只有 OS 會知道被他藏到 VM 的 Page)
:::
## Q22 Process Synchronization
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. 14
C. None of the above
D. 12
E. 10
:::success
**Ans: BDE**
B: P1->P2 = `5 -> +2 -> *2`
D: P2->P1 = `5 -> *2 -> +2`
E: P1覆蓋P2 = `5 -> *2`
:::
## Q23 Contiguous Memory Management
Which of the following statements are correct about contiguous memory management?
A. Best-fit is better than worst-fit in terms of speed utilization.
B. Best-fit is better than first-fit in terms of storage utilization.
C. None of the above.
D. First-fit is better than best-fit in terms of speed utilization.
E. All of three ways for contiguous allocation have the internal fragmentation problem.
:::success
**Ans: BD**
A: 兩個都對整條要進行搜尋
D: 因為不用找整條
E: first 跟 best 是產生 external frag
:::
## Q24 Virtual Memory Technique
Which of the following statements are correct about the virtual memory technique.
A. Decrease the CPU utilization.
B. Increase the Multiprogramming degree.
C. None of the above.
D. Increase the memory utilization.
E. Decrease the I/O frequency.
:::success
**Ans: BD**
ABD: 讓電腦認為能塞更多Page，提升更多效能
E: 跟 IO 沒關係
:::
## Q25 Banker's (沒選項，略)
## Q26 Page Replacement
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 FIFO (First-In-First-Out) algorithm, the number of page faults is 16.
B. If it uses the LRU (Least Recently Used) algorithm, the number of page faults is 17.
C. If it uses the optimal algorithm, the number of page faults is 10.
D. None of the above.
E. If it uses the second-chance algorithm, the number of page faults is 15.
:::success
**Ans: D**
LRU: 16
FIFO: 14
SecondChace: 14
OPT: 11
:::
## Q27 Page
Which of the following statements are correct? The less page size is,
A. The less internal fragmentation there is.
B. The more page fault ratio is.
C. The more I/O frequency is.
D. The less page table size is
E. None of the above.
:::success
**Ans: ABC**
A: page size 越小，page 內部的剩餘空間就越小
B: 存的資料也越小
C: Fault 提升，I/O次數也會提升
D: PT 的大小是看 PTE
:::
## Q28 Virtual Memory Technique
Which of the following statements are correct?
A. More programs can run concurrently with the virtual memory technique.
B. Virtual memory is separation of user physical memory from logical memory.
C. Only part of the program needs to be in memory for execution with the virtual memory technique.
D. None of the above.
E. Virtual address space is a logical view of how process is stored in memory.
:::success
**Ans: ACE**
B: physical 跟 logical 反了
:::
## Q29
Which of the following statements are correct?
A. The copy-on-write technique increase the time of the process creation.
B. The modify bit in demand paging is modified by the operating system.
C. It uses dirty bit to reduce overhead of page replacement in the operating system.
D. None of the above.
E. The loop structure in a program affects the number of page faults.
:::success
**Ans: ACE**
B: by Hardware
E:
:::
## Q30
Which of the following statements are correct?
A. Dynamic loading must needs a support from the operating system.
B. A mutex is used to protect a critical section of code. It cannot protect a shared variable.
C. 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.
D. Dynamic linking must needs a support from the operating system.
E. None of the above.
:::success
**Ans: D**
D: 4*104 = 416
:::
## Q31
Which of the following statements are correct?
A. If Banker’s algorithm returns an unsafe, it means the resource request must make the system in deadlock.
B. All of deadlock necessary conditions (i.e. mutual exclusion, hold and wait, no preemptive and circular waiting) exist, the system must be in deadlock.
C. The resources allocation graph has a cycle, the system must be in deadlock.
D. The resources allocation graph has no cycle, the system must not be in deadlock.
E. None of the above.
:::success
**Ans: D**
DEADLOCK 四大訴求 缺一不可
:::
## Q32
Which statements regarding process synchronization are true?
(多選題)
A. Semaphores are typically more difficult to use than monitor.
B. Monitor is typically supported as OS system calls.
C. Monitor can do some synchronization which is impossible to be done by semaphores.
D. When a semaphore blocks a process, the process is moved to ready state.
E. Semaphore is busy waiting while monitor is not.
:::success
**Ans: A**
AB: Monitor 是 programming language，更高階，更好用
C: 都能
D: 是 waiting state (ready 是要你重跑ni)
E:
:::
## Q33
Which of the following scheduling algorithms could result in starvation?
A. Priority
B. Multilevel Queue
C. First-come, first-served
D. Shortest job first
E. Round robin
:::success
**Ans ABD**
扯到階級制度 (Priority)、分類的概念，就會有貧富分配不均的問題
> 我還沒吃早餐，我也好餓
> [name=JCxYIS][time=Wed, Jun 30, 2021 11:49 AM]
:::
## Q34
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. To allocate contiguous memory from free boles, the best-fit algorithm is the optimum solution in memory utilization.
C. None of the above is correct.
D. For first-in-first-out page replacement, the page-fault rate will definitely not increase as the number of frames increases.
E. Pure segmentation suffers from internal fragmentation.
:::success
**Ans: C**
A: 不是exe time... 看圖： 
B: 不一定
D: FIFO 有 Belady’s anomaly 存在
E: 看到 segmentation 就會是 external，不可能 internal
:::
## Q35 Q36
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.
- What percentage of CPU time will process P1 get if the threads of the P1 and P2 are kernel threads entirely?
- What percentage of CPU time will process P2 get if the threads of the P1 and P2 are user threads entirely?
:::success
**Ans: 60%, 50%**
- Kernal Thread：依照 thread 數分配 => P1: 3/(3+2) = 60%
- User Thread: 依照 Process ㄈ配 => 1/(1+1) = 50%
:::
## Q37 Q38 Q39 Q40
Consider the following processes:
| | Process | Arrival Time | Burst Time |
|:---:|:-------:|:------------:|:----------:|
| A | P1 | 0 | 6 |
| B | P2 | 2 | 4 |
| C | P3 | 3 | 2 |
| D | P4 | 5 | 8 |
- Suppose we are using a non-preemptive Shortest-Job-First scheduler. Write the execution order of these processes.
- Suppose we are using a non-preemptive Shortest-Job-First scheduler. What is the average waiting time?
- Now suppose we are using a preemptive Round-Robbin scheduler with a time quantum of 4 units. Write the execution order of these processes.
- Now suppose we are using a preemptive Round-Robbin scheduler with a time quantum of 4 units. What is the average waiting time?
:::success
**Ans: ACBD, 4, ABCAD, 5**
- SJF
```
01234567890123456789
A <====> WAIT=0
B ......<==> WAIT=6
C ...<> WAIT=3
D .......<======> WAIT=7
------
Total WAIT=16
Av.WAIT=4
```
- RR
```
01234567890123456789
A <==>......<> WAIT=6
B ..<==> WAIT=2
C .....<> WAIT=5
D .......<======> WAIT=7
------
Total WAIT=20
Av.WAIT=5
```
:::
Sign in with Wallet
Connect another wallet