## 完整講義簡報

講義作者的完整簡報可以在這裡下載
https://www.os-book.com/OS10/slide-dir/index.html

# 第五章

## Two level scheduling


## Processor Affinity
A process has an affinity for the processor on which it is currently running

* Soft affinity
* When an OS has a policy of attempting to keep a process running on the same processor but not guaranteeing that it will do so
* The OS will try to make the process run on the same processor, but it will not force it.
* Hard affinity
* process可以指定在特定的processor上執行
* Allowing a process to specify a subset of processors on which it may run
* NUMA (Non-Uniform Memory Access)
* A CPU has faster access to its local memory than to memory local to another CPU


### 考古題


> a, b, d

## Real time CPU scheduling)(計算)

### Priority Based Scheduling

* Has processing time t, deadline d, period p
* 0 ≤ t ≤ d ≤ p
* Rate of periodic task is 1/p

### Rate Monotonic Scheduling

* Shorter periods = higher priority;
* Longer periods = lower priority
* period: P1 = 50, P2 = 100
* process time P1 = 20, P2 = 37?


### Earliest Deadline First Scheduling

* The earlier the deadline, the higher the priority
* The later the deadline, the lower the priority
* process time: P1 = 25, P2 = 35



### 考古題

:::info
其實我不知道要做幾次
:::


### 參考答案


## Algorithm Evaluation

透過計算以下指標決定要使用哪個排程演算法
* CPU utilization
* Response time
* Throughput
* Turnaround time

### Deterministic Modeling

Little’s law
* 用於計算 utilization，以利系統評估
* n = λ x W
* n = average queue length
* W = average waiting time in queue
* λ = average arrival rate into queue

### 考古題


# 第六、七章

## Race condition

* Race condition
* Several processes access and manipulate the same data **concurrently** and the outcome of the execution depends on the particular **order** in which the access takes place
* Process **synchronization** and **coordination** among cooperating processes

## The Critical Section Problem

A solution to the critical section problem must satisfy three requirements
* Mutual exclusion
* Progress
* Bounded waiting

Two general approaches are used to handle critical sections in OS
* Preemptive kernels
* Non-preemptive kernels

## piterson solution

* 只能用於解決2個process
* process共用flag[2]和turn變數

process Pi:

while (true) { 
	flag[i] = true; 
	turn = j; 
	while (flag[j] && turn == j);
	    /* critical section (進程中存取共享資源)*/
	flag[i] = false;
        /* remainder section (進程中不需要存取共享資源)*/
 }


## Hardware solution(填充)

### Memory barriers

Memory barriers用於**強制** CPU 和編譯器**按照特定順序執行記憶體操作**，從而避免資料不一致。

**Memory model**
* Strongly ordered
* 硬體或編譯器**不會改變**讀寫**指令的順序**
* Weakly ordered
* 處理器和編譯器**可以自由地重新排序記憶體操作**，只要這些操作不違反程式執行結果

### Atomic variables

Atomic variables是一種變數類型，保證在多執行緒環境中對該變數的操作是不可分割的（atomic），不會再分給其他的thread，可以避免data race(不同的thread同時讀寫共享變數)


### 考古題


### test_and_set(Atomic operation)

類似Atomic variables的概念，Atomic operation不會被其他thread打斷，用於保證多線程環境中的同步。

**test_and_set**
* 用途
* 表示lock是否已經被佔用
* 回傳值
* 返回變數的原始值，並將其設置為新值


### compare_and_swap CAS(Atomic operation)

* 用途
* 用於實現無鎖(lock-free)操作，**實現比較並交換**的操作
* compare_and_swap()不會被其他線程打斷，因此在不使用lock的情況下保證操作的正確性。
* 回傳值
* 返回變數的原始值，並指示操作是否成功
* lock初始值為0


### Bounded-waiting with CAS

while ((j != i) && !waiting[j]) j = (j + 1) % n;

* 退出臨界區後，選擇下一個等待進程
* 如果process waiting[j] == true，表示它在等待進入臨界區(Critical Section)。
* 如果從`j`迴圈到`i`並且沒有其他process在等待，則表示沒有其他process需要進入臨界區。


### 考古題1


### 考古題2


## Semaphores(選擇)

busy waiting problem
* process一直檢查condition是否為true

### semaphore種類
* Counting semaphore
* 用於多個process
* Binary semaphore
* 只有0, 1，適用於2個porcess(Mutex lock)

### wait(), signal()

實作了 **wait()** 和 **signal()**，並把process分成**waiting, ready state(queue)**

* ready state(queue)
* 接著要被執行的process
* waiting state(queue)
* 等待中的process
* wait()
* **嘗試獲取資源**。如果資源可用，則信號量值減 1(Decrementing)；如果資源不可用（信號量值 ≤ 0），則進程進入等待狀態，直到資源釋放。
* 確保只有一個process可以修改該資料
* **sleep**
* 將process放至waiting queue
* signal()
* **釋放資源**，將信號量值加 1(incrementing)。如果有進程因等待資源而被阻塞，則喚醒其中的一個進程。
* **wakeup**
* 將一個process從waiting queue放至ready queue


## Monitor

* Monitor會將要共享資源和訪問這些資源的方法封裝在一個對象(ADT)中，實作上可**以使用Semaphores搭配Condition variables實現Monitor**
* 每次**只有一個process**可以訪問Monitor內部的資源
* 條件變量 Condition Variable(老師說很重要)
* Monitor常配合條件變量使用，允許process在等待某個條件時進入waiting queue。

### 使用Semaphores實現Condition Variable


### 使用Semaphores和Condition實現Monitor

這裡實作了一個Montior用於單一資源的管理，架構類似Mutex Lock


## Bounded buffer

Bounded Buffer Problem，描述了在多個進程（通常是生產者與消費者）之間如何安全地共享一個有限大小的緩衝區，同時確保數據的一致性與正確性。

* 一次只能有一個process放入或移出資料
* producer
* 如果buffer還有空間，則producer放入資料
* 如果為full，則等待
* consumer
* 如果buffer還有資料，則consumer移出資料
* 如果為empty，則等待


### 考古題


## Readers-Writers

* 允許多個process讀取資料，但是一次只允許一個process修改資料
* Readers
* 只會讀取資料
* 避免writer在修改資料時有reader讀取(檢查rw_mutex)
* Writers
* 可以讀取跟修改資料
* writer必須等到所有reader讀取完後才能write(檢查rw_mutex)
* 如果reader_count=0代表沒有reader需要讀取，則釋放 rw_mutex


考古題


## Dining-Philosophers

### 問題描述
有 5 位哲學家 坐在一張圓桌周圍，分別編號為 P1, P2, P3, P4, P5。
每位哲學家交替進行兩件事：思考（Thinking） 和 吃飯（Eating）。
在桌上，哲學家中間放著一個餐盤和一根筷子，因此有 5 根筷子。

規則是：
* 哲學家需要同時拿到左邊和右邊的筷子才能吃飯。
* 吃飯完畢後，哲學家會放下筷子，繼續思考。

### 問題的核心
哲學家問題的核心在於如何安全且高效地讓哲學家進行「吃飯」而不會出現以下問題：

死鎖（Deadlock）：
* 如果每個哲學家同時拿起左邊的筷子，所有人都會等待右邊的筷子，導致整個系統卡住。

飢餓（Starvation）：
* 如果某些哲學家長時間無法取得兩根筷子，會導致飢餓問題。

競爭條件（Race Condition）：
* 哲學家同時試圖拿取筷子時，可能導致不一致的狀態。

### 使用Semaphore解決
* 為每根筷子設置一個信號量，表示筷子是否可用（1 表示可用，0 表示被占用）。
* 哲學家要吃飯時，先執行 wait() 嘗試獲取兩根筷子，吃飯後執行 signal() 釋放筷子。

while (true){ 
    wait(chopstick[i] );
    wait(chopStick[ (i + 1) % 5] );	
    /* eat for awhile */
    signal(chopstick[i] );
    signal(chopstick[ (i + 1) % 5] );
    /* think for awhile */
}

### 使用monitor解決

* `pickup()` 拿起筷子
* 將自身狀態設為 HUNGRY，表示嘗試吃飯。
* 調用 test(i)，檢查哲學家是否可以進入「吃飯」狀態。
* 如果狀態不是 EATING，則進入等待，直到被喚醒。
* `putdeown()` 放下筷子
* 將自身狀態設為 THINKING，表示已經完成吃飯。
* 測試左右鄰居是否可以進入「吃飯」狀態：
* test((i + 4) % 5) 測試左邊的哲學家。
* test((i + 1) % 5) 測試右邊的哲學家。
* test() 檢查是否可以吃飯
* 左鄰居不在吃飯(EATING)。
* 哲學家本身處於 HUNGRY 狀態。
* 右鄰居不在吃飯(EATING)。
* 如果滿足條件，將狀態設為 EATING，並喚醒（signal）哲學家i。

monitor DiningPhilosophers{ 
    enum {THINKING; HUNGRY, EATING} state [5];
    condition self [5];

    void pickup (int i) { 
        state[i] = HUNGRY;
        test(i);
        if(state[i] != EATING) self[i].wait;
    }
	
    void putdown (int i) { 
        state[i] = THINKING;
        // test left and right neighbors
        test((i + 4) % 5);
        test((i + 1) % 5);
    }

    void test (int i) { 
        if ( (state[(i + 4) % 5] != EATING) &&
        (state[i] == HUNGRY) &&
        (state[(i + 1) % 5] != EATING) ){ 
            state[i] = EATING ;
            self[i].signal () ;
        }
   }

    initialization_code() { 
        for(int i = 0; i < 5; i++) state[i] = THINKING;
    }
}

# 第八章

## Deadlock

### Deadlock產生條件
* A deadlock can arise when four conditions hold simultaneously
* Mutual exclusion
* Hold and wait
* No preemption
* Circular wait

### Handling deadlock

Deal with the deadlock problem in one of three way
* **Ignore** the problem
* Use a protocol to **prevent** or **avoid** deadlocks, ensuring that the system will never enter a deadlock state
* Allow the system to enter a deadlock state, **detect** it, and **recover**

## Deadlock prevention

針對deadlock產生的原因去解決

* Mutual exclusion
* 標注哪些是Sharable resources, Non-sharable resources
* Hold and wait
* porcess在要(request)資源時自己不能拿(hold)資源
* No preemption
* 當一個拿著(holding)資源的process要(request)不到資源時，則釋放(release)所有資源
* Circular wait
* 規定process必須按照順序請求資源

### 考古題


## banker(Deadlock Avoidance)

### 名詞解釋

* $P_n$
* process編號
* A, B, C
* process的各種資源
* instances
* 系統擁有的資源上限
* Max
* 執行該process所需的總資源(A, B, C)
* Allocation
* 系統在當時$t_n$所擁有的空閒資源
* Available
* 系統目前擁有的空閒資源
* Need(Safety Algorithm)
* 系統還需要多少資源
* Need = Max - Allocation
* Request(Resource-Request Algorithm)
* 系統會立即分配資源給該process，並檢查該行為是否導致unsafe state
* Available = Available - Request
* Allocation = Allocation + Request


考古題


### (a)

使用Banker's Algorithm Safety Algorithm 來檢測是否safe


### Safety Algorithm 步驟

**步驟1:**

$P_0$時 Need=(7,5,3)-(0,1,0)=(7,4,3)，而Need > Available(3,3,2)因此無法完成$P_1$

$P_1$時 Need=(3,2,2)-(2,0,0)=(1,2,2)，而Available(3,3,2) >= need因此可以完成$P_1$

得順序($P_1$->...)

而$P_1$完成時可以將多餘的資源收回，因此Available=(5,3,2)

**步驟2:**

$P_3$時Need=(2,2,2)-(2,1,1)=(0,1,1)，而Available(5,3,2) >= need因此可以完成$P_3$

得順序($P_1$->$P_3$)

而$P_3$完成時可以將多餘的資源收回，因此Available=(7,4,3)

**步驟3:**

$P_4$時Need=(4,3,3)-(0,0,2)=(4,3,1)，而Available(7,4,3) >= need因此可以完成$P_4$

得順序($P_1$->$P_3$->$P_4$)，Available = (7,4,5)

**步驟4:**

$P_0$時Need=(7,5,3)-(0,1,0)=(7,4,3)，而Available(7,4,5) >= need因此可以完成$P_0$

得順序($P_1$->$P_3$->$P_4$->$P_0$)，Available = (7,5,5)

**步驟5:**

$P_2$時Need=(9,0,2)-(3,0,2)=(6,0,0)，而Available(7,5,5) >= need因此可以完成$P_2$

得順序($P_1$->$P_3$->$P_4$->$P_0$->$P_2$)，Available = (10,5,7)

**結論:**

而由於所有process都可以被執行，因此state為safe

### (b), \(c\)

使用Banker's Algorithm Resource-Request Algorithm
* 1,2 步驟基本上是一樣的，可以跳過1


### Resource-Request Algorithm 流程圖


### Resource-Request Algorithm 計算過程

**$P_1$ request(1,0,2)**

Available(3,3,2) >= Request(1,0,2)
Available = (3,3,2) - (1,0,2) = (2,3,0)
$P_1$ Allocation = (2,0,0) + (1,0,2) = (3,0,2)

測試是否為safety

**步驟1:**

:::info
為($P_1$)可跳過，因為之前($P_1$->$P_3$->$P_4$->$P_0$->$P_2$)已算過

**範例:**
$P_1$時 Need=(3,2,2)-(3,0,2)=(0,2,0)，而Available(2,3,0) >= need因此可以完成$P_1$
:::

由於後面的process之前測試過了，可知道順序($P_1$->$P_3$->$P_4$->$P_0$->$P_2$)，執行結果為safey

> A: $P_1$ request granted

**$P_0$ request(0,2,0)**

Available(3,3,2) >= Request(0,2,0)
Available = (3,3,2) - (0,2,0) = (3,1,2)
$P_0$ Allocation = (0,1,0) + (0,2,0) = (0,3,0)

測試是否為safety:

**步驟1:**

$P_3$時Need=(2,2,2)-(2,1,1)=(0,1,1)，而Available(3,1,2) >= need因此可以完成$P_3$

得順序($P_3$->...)，Available=(5,2,3)

**步驟2:**

$P_1$時 Need=(3,2,2)-(2,0,0)=(1,2,2)，而Available(5,2,3) >= need因此可以完成$P_1$

得順序($P_3$->$P_1$)，Available=(7,2,3)

**步驟3:**

:::info
為($P_4$)可跳過，因為之前(...->$P_4$->$P_0$->$P_2$)已算過
:::

由於後面的process之前測試過了，可知道順序($P_3$->$P_1$->$P_4$->$P_0$->$P_2$)，執行結果為safey

> A: $P_0$ request granted

## Deadlock Dection

### Detection Algorithm

:::info
其實跟上面的演算法概念一樣，也是看他是不是safe，不是的話則有deadlock
:::


### 課本範例


### 考古題


### (a)

$P_0$ Available > Need，Available = (0,1,0)，Finish[0]=true
$P_2$ Available > Need，Available = (3,1,3)，Finish[2]=true
$P_3$ Available > Need，Available = (5,2,4)，Finish[3]=true
$P_4$ Available > Need，Available = (5,2,6)，Finish[4]=true
$P_1$ Available > Need，Available = (7,2,6)，Finish[1]=true
> 順序($P_0$->$P_2$->$P_3$->$P_4$->$P_1$)，all Finish[i]=true

### (b)

先算Request:

$P_2$ request (0,0,1), $P_2$ Request(Max) => (0,0,1)

檢查是否有deadlock

$P_0$ Available > Need，Available = (0,1,0)，Finish[0]=true

## Recovery from Deadlock

* Rollback(重做)
* **選擇影響最小**的進行重做，如果同一個process**一直被選中則稱為Starvatio**n
* return to some safe state, restart the thread for that state

# 第九章

## Address Binding

* Compile time
* Load time
* Execution time

### 考古題


## Memory-Management Unit (MMU)

* Logical address
* generated by the CPU; also referred to as virtual address
* Physical address
* address seen by the memory unit
* MMU
* Hardware device that at run time maps virtual to physical address


### relocation register

* relocation register紀錄著程式的base address(又稱base register)


## Memory Allocation

### Main memory

Main memory分成兩部分
* operating system
* 通常放在low memory
* User process
* 放在high memory
* 每個process都有一個連續的記憶體空間可以使用(Contiguous memory allocation)

### Variable Partition

* Hole
* 可以使用的記憶體空間區段(block)
* Variable-partition
* 一種記憶體管理策略，為每個進程分配不同大小的記憶體量
* Variable-partition策略
* First-fit
* 找到第一個可以放的block就放
* Best-fit
* 查看全部記憶體後，找到最小且可以放得下的block
* Worst-fit
* 查看全部記憶體後，找最大的block放


## Paging Hardware

* Memory Protection
* Valid-invalid
* 紀錄page table的entry是否存有資料
* valid 有資料
* invalid 無資料
* Shared Pages
* 將page table複製，並開放(read-only)讓其他process讀取

### 考古題

### (a)

* CPU會尋找page table上儲存的frame，再透過frame + offest的方式找到physical memory的位置


### (b)

* logical address = 32(page) x (1024 x 4)(offset, word = 4Bytes) = 2^17
* 記憶體是以Bytes為單位，一個word為4 Bytes
* physical address = 16(frame) x (1024 x 4)(offest) = 2^16

## Effective Accese Time
* 計算


## Inverted page table
:::info
page table共有Hierarchical, Hashed, Inverted三種，其他的我就沒列進來了
:::
* 所有process共用一個page table
* 上述的方法每個process都會有自己的page table，而Inverted所有process共用一個page table，這樣可以較省空間但也導致搜尋時間較長
* 透過pid和page number去page table尋找該資料的位置，位置i就是physical address的frame，就可以直接透過frame和offest去拿資料