:::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)



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**


**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


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

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


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


## 每年必考的填空

compiler&linker&loader位置(填空)


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**


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**)


> 引用自: [作業系統 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[必考]


## 考古有出現過的

### three virtual machines(畫圖)


### Data and task parallelism(畫圖)


### 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