---
# System prepended metadata

title: 作業系統期中考前
tags: [學業共筆]

---

:::warning
註: 老師112年的期中考跟113年題目差很多，須注意!!!
:::

## 必考懶人包 checklist
畫圖&計算
* Scheduling Algorithms(畫圖+計算average waiting time)
* CPU-scheduling(有可能出成選擇) & Process state diagram(要會畫)
* User mode& kernel mode(要會畫)
* switch from process to process(要會畫)

選擇
* Operating System Structure
* Threading Issues
* Operations on Processes
* Scheduler
* IPC
* IPC in Message-Passing Systems
* Storage-device

填空

* compiler&linker&loader位置(填空)
* socket組成
* Mechanisms and Policies

## 必考題

### Scheduling Algorithms(畫圖+計算average waiting time)

![image](https://hackmd.io/_uploads/BJ7DDe9eJe.png)

![image](https://hackmd.io/_uploads/rk1iDzcgyl.png)

waiting time 計算:
* SJB&FCFS: process開始被執行時的時間
* 計算process第一次執行與process最後一次執行前總共被分幾次quantum做運算
* Waiting time = Last start time - arrival time - (preemption * quantum)
    * 以上題為例: 第一次執行為10，最後一次被執行完成時是51，在最後一次之前總共先運算了兩次
    * p2: 51 - (10)第一次 - 2\*10 = 21


### CPU-scheduling(有可能出成選擇) & Process state diagram(要會畫)

**Process state diagram**

![image](https://hackmd.io/_uploads/rkq9hG9e1l.png)

**CPU-scheduling** decisions may take place under the following circumstances
* When a process switches from the running state to the waiting state
* When a process switches from the running state to the ready state
* When a process switches from the waiting state to the ready state
* When a process terminates

![image](https://hackmd.io/_uploads/SJq5sN9xJx.png)

### User mode& kernel mode(要會畫)

防止使用者的程式對系統有惡意行為

![2024-09-24_10.55](https://hackmd.io/_uploads/ryB5g7cgkl.jpg)


### switch from process to process(要會畫)

![image](https://hackmd.io/_uploads/B1nyxrceJx.png)

## 每年必考的填空 

compiler&linker&loader位置(填空)

![image](https://hackmd.io/_uploads/Bk2KVXceye.png)

IPC in Message-Passing Systems
* Blocking (synchronous) 
    * Blocking send
    * Non-blocking receive

Communications in Client-Server Systems
* A socket is identified by an **IP address** concatenated with a **port number**

Mechanisms and Policies
* Mechanisms (determine how to do something)
* Policies (determine what will be done)

## 會拿來當選擇題的題目

### 老師的出題規則

:::info
根據我的觀察，老師選擇題的選項會直接把簡報上面的敘述複製下來，並改掉某個關鍵字讓你做多選
:::

### Operating System Structure[必考]

Monolithic structure
* Place all of the functionality of the kernel into a **single, static** binary file that runs in a single address space

Layer Approach
* The layers are selected such that each uses functions (operations) and services of only **lower-level** layers

Microkernel
* Removing all **nonessential** components from the kernel and implementing them as **system** and **user-level programs**
* **Benefits**
    * Easier to extend
    * Easier to port
    * More secure
    * More reliable
* Disadvantage
    * Performance can suffer from due to increased **system-function overhead**

Loadable kernel modules
* The kernel has a set of core components and links in additional services via modules,either at **boot time** or **during run time** (Linking services dynamically)

### Threading Issues[必考]

Signal
* To **notify** a process that a particular event has occurred
* The pattern
    * Generated
    * Delivered
    * Handled

Thread Cancellation
* Involves terminating a thread **before it has completed**
* Two different scenarios
    * Asynchronous cancellation
    * Deferred cancellation

Lightweight process (LWP)
* A **virtual processor** on which the applications can **schedule a user thread** to run
* Each LWP is **attached to a kernel thread**

### Operations on Processes[必考]

When a process creates a new process, two possibilities for execution
* The parent continues to **execute concurrently** with its children
* The parent **waits until** some or all of its children have **terminated**

The parent may **terminate the execution** of the child
* The child has **exceeded its usage** of some of the resources that it has been allocated
* The task assigned to the child is **no longer required**
* If **parent is exiting**, and the OS does not allow a child to continue if its parent terminates


### Scheduler[必考]

Long-Term Scheduler
* 控制在記憶體中 Process 的數量 (**degree of multi-programming**)
* 當 degree 太低時， CPU 有很多的時間在 idle
* 當 degree 太高時，會發生 Thrashing，有太多的 Process 在爭搶有限的 memory，導致 Process 一直在 memory 跟 disk 之間 swap，不斷的做 I/O

Short-Term Scheduler (CPU Scheduler)
* 執行頻率很高，大約 100ms 執行一次(**invoke frequently**)
* 由演算法來縮短每個 Process 的等待時間
* choose what to **excute next**
* brought process to **ready queue**

![image](https://i.imgur.com/Ec849XW.png)

Medium-Term Schduler
因現代 memory 空間的增長以及虛擬記憶體的觀念引入，過往由 Long-Term Schduler 處理的動作多改由 Medium-Term Schduler 執行

swap out : 將 Process 由 memory 搬到 disk 中
swap in : 將 Process 由 disk 搬到 memory 中
propose : 改善 Process mix / 減少記憶體中的 Process 數量，**降低 degree**釋放記憶體空間(**reduce degree**)

![image](https://hackmd.io/_uploads/rkfQPHclyx.png)

> 引用自: [作業系統 CH3 Process](https://hackmd.io/@Chang-Chia-Chi/OS-CH3)

### IPC (Interprocess Communication)[必考]
Independent
* A process **cannot affec**t or to be affected by the other processes executing in the system 

Cooperating
* A process **can affect** or to be affected by the other processes executing in the system

The reasons to cooperate
* Information sharing
* Computation speedup
* Modularity

Two models of IPC
* Shared memory
* Message passing

### IPC in Message-Passing Systems[必考]

:::info
考試推常會問有process之間有多少link，需不需要name
:::

**Direct communication**

* Properties
    * A links is established automatically between every pair of processes that want to communicate. The processes need to know only each other’s identity to communicate.
    * **A link** is associated with **exactly two processes** 
    * Between each pair of processes, there exists exactly one link

Symmetry
* **Both** the sender and the receiver **must name** the other to communicate
    * send (P, message)
    * receive(Q, message)

Asymmetry
* Only the **sender names the recipient**, the recipient is not required to name the sender
    * send (P, message)
    * receive(id, message)
    
**Indirect communication**
* The messages are sent to and received from mailboxes or ports
    * send (A, message)
    * receive(A, message)
* Properties:
    * A links is established between a pair of processes only if both members of the pair **have a shared mailbox** .
    * A link may be **associated with more than two** processes
    * Between each pair of communicating processes, a number of **different links may exist**, with each link corresponding to one mailbox.

### Storage-device[必考]

![image](https://hackmd.io/_uploads/Skh6e5ceye.png)


## 考古有出現過的

### three virtual machines(畫圖)

![image](https://hackmd.io/_uploads/Sy_GG95eye.png)


### Data and task parallelism(畫圖)

![image](https://hackmd.io/_uploads/rkBd-q9xye.png)


### DMA(Direct Memory Access)(選擇)

* The **device controller** transfers an entire **block** of data directly to or from its **own buffer** storage to **memory**
* With no intervention by the CPU
* One interrupt is generated per block