---
tags: shiwulo OS
---
# OS 作業系統 CH1 - CH5(Peterson's solution)

> 2020 期中筆試：https://pse.is/4mx46x

## CH1 introduction

### Dual mode operation (雙模式執行)
#### 意思為CPU具有二種以上的權限
>* Kernel mode & User mode
>* Privileged mode & normal mode

- #### Kernel mode
- OS掌控系統的控制權，於kernel mode可以對硬體做任何的變更。
- #### User mode
- 一般模式，不能執行特權指令，否則會導致中斷，OS會強迫中止process。

| 可否存取 | Kernel space | User space | Privileged Instruction |
|:-----------:|:------------:|:----------:|:----------------------:|
| Kernel mode | ✔️ | ✔️ | ✔️ |
| User mode | | ✔️ | |

> Privileged Instruction：可能造成系統重大危害的指令

#### Mode Change 模式切換
- User mode -> Kernel mode
- **syscall**
- Kernel mode -> User mode
- **sysret**
> system call handler：進入Kernel mode時，當會將大部分暫存器的值到PCB(CH3會介紹)，以便之後返回User mode時還可以繼續正常執行。
>

#### :question: 為什麼需要dual mode?
> 使用dual mode讓使用者只能透過system call呼叫kernel操作週邊裝置或者執行特權指令。目的是把可能造成危害的機器指令設為特權指令，就可避免一般user program使用，避免這些指令對系統或其它user造成危害。[color=#4a8aa1]

#### :question: CPU只能跑在一其中一種mode上，那如果Kernel跟User都有要執行的process會撞在一起嗎?
> 在一個CPU上，同一個時間只有一個應用程式在跑，因此core會不斷的在不同應用程式間快速切換，讓大家以為這些應用程式同時在跑。[color=#4a8aa1]

### Context switch
#### 從task A切換到task B，且一定發生在Kernel。
> system call的overhead小於context switch
> Context-switch的主要負擔是「記憶體的切換」
#### :question: context-switch和mode change的差別?
> cotext-switch是指從一個task切換到另一個task
> Mode change是指不同權限模式的切換，例如：從user mode切換到kernel mode
> Overhead：
> context-switch可能會造成大量的cache miss，尤其是process之間的context-switch
> Mode change通常只是觸發CPU執行模式的改變，overhead較小[color=#4a8aa1]

### main memory (主記憶體)
* #### RAM (Random Access Memory)
在斷電以後儲存在上面的資料會自動消失，因此需要定期寫到第二層儲存裝置(disk、SSD)
* Cache memory
* Buffer memory
* Program memory

* #### ROM (Read Only Memory)
儲存了資料就無法再被改寫或刪除，但其儲存過的內容也不會因為電源關閉而丟失，因此會用來儲存開機資訊。

* #### 啟動作業系統
要啟動作業系統，我們需要讀取disk上的boot sector來啟動GRUB(OS載入器)。
而在沒有軟體驅動的情況下，CPU無法直接讀取disk。
我們知道CPU能直接控制DRAM和ROM，因此我們在ROM中擺入「BIOS」，BIOS的最重要目的就是讀取disk上的boot sector。

> boot sector : 負責booting「存放在disk的其他部份的程式」的機器碼。

### I/O子系統
介於記憶體及硬體中間，負責作為溝通橋梁
* #### 輸入輸出
* MMIO (Memory mapped I/O)
* 佔用CPU的物理地址空間
* 將周邊控制設備的暫存器及記憶體mmap到CPU的記憶體映射空間
* MOV指令
* PIO (Port I/O)
* 不佔用CPU的物理地址空間
* IN, OUT指令
* 透過指令，將資料透過port傳到與CPU的記憶體映射空間**不同的空間**

* #### 資料傳輸
* DMA (direct memory access)
可以直接存取記憶體，不需CPU介入處理，是一種快速的資料傳送方式。
* DMA and Cache coherency problems
* 原因：
> 因為CPU會將更新的資料寫進cache，但cache還沒flush到記憶體上時，AMD從RAM中獲取資料，因此就有可能拿到舊的資料。
* 💡解決方法：
> DEV -> CPU 使用硬體解決，如果該段記憶體也存在cache中，硬體自動會將DMA的資料更新到cache
> CPU -> DEV 藉由設定，讓CPU在該記憶體區段進行寫入時，直接寫穿（write through，或noncacheable），直達裝置上的記憶體

* #### 通知狀態
通知OS工作已完成
* polling 輪詢
> 一個一個詢問做完了沒
> 主動的，可以視負載情況調整頻率
> 適合滑鼠、鍵盤等的低速裝置以及會在短時間做出大量變更的裝置
* interrupt 中斷
> 被動的，適合需要立即做讀寫的高速裝置，如硬碟、網卡
* polling + interrupt

### Interrupt 中斷

* #### 內部中斷
稱作異常，不能被遮蔽。

* #### 外部中斷
* 可遮蔽中斷 INTR
> I/O 裝置產生的IRQ(Interrupt ReQuirement中斷請求)
* 不可遮蔽中斷 NMI
> 緊急的事件（如硬體故障）引起的故障

* #### 中斷向量表
對應到該中斷的ISR(Interrupt Service Routine)
* 0 ~ 31 的向量對應於異常和非遮蔽中斷。
* 32~ 47 的向量（即由I/O裝置引起的中斷）分配給遮蔽中斷。

* #### interrupt handler
* Top half
* 儲存裝置相關資料
> 確保處理中斷以後，還可以繼續原本的工作
發生中斷後，硬體會自動將所有中斷disable，並切換到Kernel mode之後再呼叫ISR
ISR中首先儲存CPU的狀態尤其是PC暫存器必須立即存下來（這部份需要硬體實現)
ISR必須儲存足夠多的CPU狀態，讓ISR執行完畢後「將來」可以繼續中斷前的CPU工作（scheduler會決定接下來要執行誰）
* 將 bottom half 排程後結束執行。
* Bottom half
* 執行時，interrupt是開啟的，因此CPU仍然可以接受中斷請求，不需等待。
* 運作機制
* softirq
* tasklet
* workqueue

## CH2 OS structure

### System Call
Kernel對外開放的API
> API : application programming interface
* #### System Call Overhead
1. CPU從user mode切換到kernel mode，CPU同時數個指令在執行，進行切換時需要flush所有執行到一半的指令
2. Kernel將user space的所有暫存器存在kernel stack中（每一個task，於kernel中有自己的stack，請注意，不是user mode stack）
3. 檢查權限
4. 依照kernel內部的calling convention，呼叫實現該system call的function

* #### vDSO (Virtual Dynamic Shared Object)
快速系統呼叫機制。
假如程式需要一直讀取系統的time，而每次想從系統取得資訊都必須要呼叫syscall，這樣就會花很多時間，因此我們可以把Kernel中部分沒有機密性的資訊放在User space，讓程式以function call的方式取得。
* 會時常變動，但又沒有機密性的資訊
> __vdso_clock_gettime
> __vdso_getcpu
> __vdso_gettimeofday
> __vdso_time
* 不會變動，又沒有機密性的資訊
> 如果system call不會牽扯到安全性，可以將部分資訊寫在user space，讓程式能夠以function call的方式取得。
> 第一次，產生syscall，libc 紀錄 function 的值
第二次，libc直接回傳

### OS struct
* #### Layered approach
> 將系統分成n層
> 第n層只能用第n-1層所提供的functions

### inline assembly
#### :question: 什麼樣的情況決定要inline assembly或者完整的組合語言？
> * inline assembly : 通常我們只對少數幾行程式碼要優化或者特殊運作的情況下。
> * 完整的組合語言 : 由CPU直接呼叫的程式碼 [color=#4a8aa1]

## CH3 Process and Thread

### process
* Load到memory的program(正在執行的program)
* Process ≈ Task ≈ Job

### Process memory
* 表示一個行程最多能夠存取多少記憶體，實體記憶體（也就是插槽上的RAM）通常遠小於行程的定址空間
* 每個process都有自己完整的地址空間(虛擬空間，映射到 kernel 中的實體記憶體)
* 以32位元為例： $2^{32} × 64\ bits\ =\ 4,294,967,296\ bits\ ×\ 8\ Bytes\ =\ 512M\ bytes\ ×\ 8\ Bytes\ =\ 4G\ Bytes$
* 通常將行程的定址空間分為二個部分，上半部分為OS kernel，下半部分為行程真正可用的定址空間
* 示意圖，上半部為kernel space，下半部為process於user space的記憶體分布狀況

### ASLR (Address space layout randomization)
* 一種針對緩衝區溢出的全保護技術，通過線性區佈局的隨機化，增加攻擊者預測目的地址的難度，防止攻擊者直接定位攻擊代碼位置。
* 作業系統會隨機的產生每個section的address
* :question:為什麼要有ASLR？
> 如果沒有ASLR，libc裡面的system()函數會被放在固定地方，所以駭客只需要透過stack overflow改掉return address，並且將system所需要的參數透過stack overflow寫入到堆疊。那麼就可以透過retrun to libc執行任意的指令。
* ASLR會造成效能上的損失
> 如果不使用ASLR，那麼可以將常用的函數固定在同一個地方，因此在做context switch的時候就不需要切換常用函數庫的部分
* :question:ASLR 的 random 是怎麼做到的?
> * 應用程式使用IP相對定址，因此應用程式可以放在任何記憶體位址
> * 函數庫（libc等）放到任意位址，loader可以正確定位
> * mmap及brk(sbrk)分配記憶體本來就可以隨機

### Process flow
![](https://i.imgur.com/dLOUzBg.png "Process flow" =600x)
> Ready queue：排班中，等待CPU。
> running：正在執行。
> 可中斷：可被signal中斷，中斷完必須重新執行
> 不可中斷：不可被signal中斷，但是還是可以中斷 ex.kill(9)。

### Process Concrol Block (PCB)
作業系統核心中一種資料結構，當context switch發生時，Kernel會把未做完的process相關資訊記錄在PCB裡。
* 包含內容：
* Process state
> 例如 : runnable, waiting
* 相關CPU資訊
> 如果行程不在CPU執行，OS會將該process的狀態儲存於此
* Schedule的相關資訊
> 使用者設定的nice為多少
* 記憶體相關資訊
> 程式碼區段、資料區段等等
* 使用了多少資源
> 程死掉以後，parent可以使用wait()取得相關資訊
* 正在等待的I/O
* 這個行程開啟的檔案

### 行程分類
系統中同時存在I/O-bound process和CPU-bound process可以讓系統的效率極大化
CPU是電腦的總指揮，我們通常希望CPU趕快發出命令，讓I/O開始動作，因此通常讓I/O-bound process的優先權比較高
* I/O-bound process
> 當I/O變更快時，這個process會運行得更快，那麼它就是I/O-bound process，也就是指process做I/O的時間遠高於CPU，如ftp server。
* CPU-bound process
> 當CPU變更快時，這個process會運行得更快，那麼它就是CPU-bound process，也就是指process做CPU運算的時間遠高於I/O，如image processing。

#### :question: 為什麼I/O-bound的task要提高優先權
> CPU先趕快要I/O去處理事情，就可以處理自己的事了。
>
> 💡例如：有二類學生
>> * 詢問人生哲學問題（CPU-bound）
>> * 詢問接下來要去打掃哪（I/O-bound）
>
> Q : 請問本廢宅要先回答哪一類的學生？
> A : 打掃的，因為先叫他去打掃就可以接著處理人生哲學問題，如果先回答問題，則要等問題回答完了才會叫他去打掃，效率較差。

### Interprocess Communication (IPC)
多個process/thread內部的溝通，都統稱叫做IPC
* Process 之間為什麼需要溝通？
* 傳遞資訊
> copy-paste
> Information sharing
* 同步
> 平行計算
> master thread可以收到所有worker thread的訊息以後，繼續往下做、計算加速
* 模組化設計
> master thread收request，發包給worker
* 方便性
> 像web server，一個user對一個process，就可以很容易去管理這些connection
* Communication Methods
* shared memory
> 如果有兩個或以上的process同時想write這塊空間的時候，則會產生 synchronization 的問題
* message passing
* 直接傳送 (signal)
* 間接傳送 (FIFO)

### Thread
process和thread都是task，如果二個task共用記憶體空間，稱之為thread
在同一組thread間做contest switch，只需要切換暫存器，不需要切換memory address space

* :question: Thread比process的context switch有效率，其主要原因為何？
> context switch的overhead主要是在cache memory的更新上，而thread間共享記憶體，因此context switch時所造成的cache miss較少。

* #### Thread可劃分為
* **User-level thread**
> 使用 User-level library 管理 Thread，包括處理 Thread Context Switch，也因此 OS 是察覺不到 Thread 存在的，因為只有在 User-level 中運行，所以不會使用到 System Call。
* **Kernel-level thread**
> 由 OS 管理 Thread，因此 OS 是察覺的到 Thread 存在，所以也有 Thread Context Switch 的發生，但是比 Process Context Switch 成本低，因為不需要切換 address space(記憶體空間)，專門處理 System Call 。
* #### **User-level thread** 和 **Kernel-level thread** 的對應模式
* Many-to-One
> 
* One-to-One
> 
* Many-to-Many
* Many-to-many model
> 
* two-tier model
> 

## CH4 CPU Scheduling

### Preemptive and Non-Preemptive Scheduling
* preemptive OS 可搶奪型
> 不論正在執行的Task是否可繼續執行，必要時CPU使用權可能被搶奪
* preemptive kernel
> * Context switch可能會發生在Task執行在kernel mode時
> * 所有存取到共用變數的程式碼都必須使用lock-unlock保護
* non-preemptive kernel
> * 當一個Task執行於kernel mode時，其優先權無限大
> * Context switch只會發生在Task由kernel mode切換到user mode時
> ※ 等到Task A在kernel內的工作完成後，才會開始執行Task B
* non-preemptive OS 不可搶奪型
> * 又稱為cooperative multitasking 合作式排程
> * 一個Process除非自行放棄CPU的使用權，否則其他Task不能奪取其CPU使用權

:question:**Preemptive OS** 和 **Preemptive kernel** 的差別?
> * Preemptive OS
> 能確保應用程式執行於user mode時，如果time quantum用完或者優先權不夠高時，可以立即切換task。
> * Preemptive kernel
> 即使task執行於kernel mode也可以立即的切換task [color=#4a8aa1]

:question:當 **non-preemptive kernel** 遇到 signal 會如何處理?
> 設定「need to reschedule」等到 kernel space 準備切回 user space 時，呼叫 scheduler，決定切回哪個 user mode app [color=#4a8aa1]

:question: 在什麼樣的情況下**non-preemptive OS**的效能比較好?
> 所有的程式都沒有bug，程式使用完CPU都把CPU釋放出來，使用過久自覺性的釋放CPU。
> 例如 : netware [color=#4a8aa1]

### Scheduling Criteria
* CPU utilization
> 讓CPU維持在高使用率
>> 如下圖，有兩個task，橘色部分為共享資源
>> 

>
>> 我們讓第一個task跑快一點，讓橘色的部分錯開，白色部分為CPU閒置時間
> 

>
>> 我們換成讓第二個task跑快一點，可以發現CPU閒置的時間變少了
> 

* Throughput
> 每單位時間可以完成的工作的數量。例如：讓I/Obound的行程優先執行
* Turnaround time
> 從交付工作，到完成的時間。與scheduler及程式本身的執行長度相關
* Waiting time
> 在ready queue的時間。通常高優先權的task在readyqueue的時間較短
* Response time
> 回應時間
> * 假設系統中有10個task，這10個行程連接到10個user，如果要讓使用感覺執行流暢的話有下列做法：
> * 單向互動
> > 假如這10個行程是「播放影片」，那麼只要安插適當的buffer，將解碼過的影片放在buffer內，供使用者的task拿取，只要buffer夠大，即使每10秒才輪到一次執行，使用者也不會感覺lag
> * 雙向互動
> > 假如這10個行程是「語音通話」，必須在150ms內輪到執行一次，否則使用者會覺得通話品質不好。換句話說，每個task每一回合只能執行15ms

### 簡單 Scheduler
決定接下來要執行哪一個task
* **FCFS Scheduling**
First Come First Serve 依抵達順序執行，先來的先執行
> 假設有3個task
>
> | task | CPU time | 抵達順序 |
> | :--: | :------: | :------: |
> | P1 | 24 | 1 |
> | P2 | 3 | 2 |
> | P3 | 3 | 3 |
>
> ![](https://img-blog.csdn.net/20150612111213709 "FCFS" =360x)
>
> 等待時間：P1 = 0, P2 = 24, P3 = 27
> 平均等待時間：17
> ※ 優先底抵達的task的執行時間比較久，那麼平均等待時間會變得很長
* **SJF Scheduling**
Shortest Job First 工作時間最短的task優先執行
> * non-preemptive SJF
> 如果只是寫「SJF」通常代表non-preemptable
> 當一個行程拿到 CPU，不會被搶佔直到他完成
> ![](https://i.imgur.com/wQBZGsP.png "non-preemptive SJF" =500x)
>
> * preemptive SJF
> 又稱之為SRTF (Shortest Remaining Time First)
> 當有新的行程且他的 CPU burst 的長度比較小，搶佔發生
> ![](https://i.imgur.com/XV0JkpF.png "preemptive SJF" =500x)

> 在average waiting time方面，SJF及SRTF分別是non-preemptive scheduling和preemptive scheduling的最佳演算法

* :question: 工作還沒執行，怎麼知道執行時間?
> 依照task以前的執行時間，預測這次使用這次使用CPU的時間：
> $𝜏_{n+1}\ =\ αt_n\ +\ (1\ -\ α)\ ⨉\ 𝜏_n$
>> $𝜏_𝑥$ 是預測的第 x 次的CPU時間
>> $𝑡_𝑛$ 是上一次的CPU時間
>> Linux 的 $α$ 預設為 ${1 \over 2}$

* **Round-Robin(RR) Scheduling**
類似於FCFS排程，但是增加了preemptive以切換程序，定義一個較小的時間單元，稱為time slice，在一群task中輪流執行，為每個程序分配不超過time slice的CPU。
> 假設有3個task，time slice = 4
>
> | task | CPU time | 抵達順序 |
> | :--: | :------: | :------: |
> | P1 | 24 | 1 |
> | P2 | 3 | 2 |
> | P3 | 3 | 3 |
>
> 
>
> 等待時間：P1 = 6, P2 = 4, P3 = 7
> 平均等待時間：5.66

* :question: time slice要設定為多久?
> * Too Large -> 應用程式的回應時間變差
> * Too small -> context switch的overhead太大
> * 設定為：大多數的task都可以在一回合的時間內從CPU變為Waitting
> ![](https://i.imgur.com/tjuraEf.png "burst duration" =500x)
> 將time slice設定為8可以讓大部分的task從CPU變為Waitting

### Linux 2.4 Scheduler
Linux 2.4 Scheduler 支持 SMP（Symmetric Multi-Processing），為non-preemptive kernel，且是利用Round-robin來Scheduling。
但由於只用一個global runqueue，各個core需要競爭同一個runqueue裡面的任務，所以效率很低，時間複雜度是 $O(N)$
* #### goodness
同時表示CPU time和優先權
goodness為上一回合殘餘的goodness＋該nice的基本goodness
簡單來說 goodness就是 time slice的剩餘 + nice value

* #### epoch
* 將執行時間分成無數個epoch
* 當沒有task可以執行時就換到下一個epoch
> 此時可能有些task的time slice還沒用完，但些task正在Waitting
> 2.4假設Waitting就是在等待I/O
* 為了避免CPU idle，當切換到下一個epoch時，補充所有task的time slice
> 如果是I/O-bound task因為上一個epoch還有一些time slice還未用完，因此補充過後，這些task的time slice比較多
>> ※ $time\ slice_{new}\ =\ {time\ slice_{old} \over 2}\ +\ nice$
>> $time\ slice_{old}$ 需要除2的原因是為了避免要waitting很久的task拿到很多time slice

![](https://i.imgur.com/OebSLtu.png "epoch" =600x)

:question: 2.4 scheduler如何提升 I/O bound的優先權?
> 因為下一回合的goodness為上一回合殘餘的goodness ＋ 該nice的基本goodness。
> 會殘餘goodness的task就是I/O bound，而且goodness越大優先權越高。
> 因此2.4可以讓I/O bound task的優先權變高。 [color=#4a8aa1]

* #### 2.4 scheduler缺點
* 計算goodness太耗費時間，就算某一個task的goodness一直沒變，每次還是要重算
* 所有CPU共用一個run queue，這個run queue變成系統的效能瓶頸
* waitting不一定是等I/O，例如：執行sleep()

### Linux 2.6 Scheduler
每個CPU有自己的runqueue，一個task一但被指定到某顆CPU上執行，除非特殊狀況，否則該task不會輕易的離開該CPU。
* #### fully preemptable kernel
2.6 kernel以後，Linux中每一個task執行於kernel mode時，都有一個變數「preempt_count」用以記載該task是否可以被preempt

* 每當lock一個資源時，preempt_count++，變成1
* 每當unlock一個資源時，preempt_count--，變回0
<BR>
* 當preempt_count為0時，kernel可以做行程切換。
>Kernel需要做行程切換主要是因為interrupt。
>例如：一個高優先權的task正在等這個interrupt。
* 如果preempt_count由1變0，那麼OS kernel需要檢查一下，是否需要context switch

### Linux 2.6 O(1) Scheduler
每個CPU有自己的run queue，每個run queue由二個array組合而成
* active array
> 存放time slice還沒用完的task
* expired array
> 存放time slice用完的task

當一個task耗盡time slice之後，就會被插入expired array，並計算出下一回合的dynamic priority
當active array為空時，只需要把active array和expired array對調即可。
時間複雜度為 $O(1)$

* #### 2.6 O(1)Scheduler缺點
* 與2.4一樣使用epoch的概念區分I/O-bound和CPU-bound，因此每一個task使用完CPU time以後，要經過一個epoch的時間才能補充time slice

### Linux 2.6 CFS
Complete Fair Scheduling 完全公平排程器
每次的工作排程時，CFS選取目前獲得CPU執行時間最少的工作來做排程，並使用rb-tree實現，紅黑樹插入節點的時間複雜度為 $O(log\ n)$

* #### 核心概念
* 希望將一顆「實體處理器」依照目前正在執行的task的數量虛擬成n顆虛擬處理器
* 假如這些task的優先權都一樣高的話，那麼每一個虛擬處理器的效能為實體處理器的1/n

* #### 虛擬執行時間 vruntime
vruntime 代表的意義就是 virtual runtime，顧名思義就是行程到目前為止所運行的虛擬時間，所以對CFS而言，為了公平起見，讓大家都能夠享有公平的運行時間，CFS會挑出vruntime最小的行程執行。

* #### 舉例
有3個要執行的task，藍色的優先權最高
> 

每一個task執行1個time slice的時間，然後換下一個task跑(vruntime最小的)
※ 當藍色執行1個time slice的時間，其vruntime增加2
※ 當灰色及黃色執行1個time slice的時間，其vruntime增加4
因為藍色(高優先權的task)每次增加的vruntime的比例較小，vruntime很快的就又變成最小的，執行頻率高
> 

:question: 為什麼CFS方法中，提高優先權為什麼可以改善該task的response time?
> 高優先權的task每次增加的vruntime的比例較小，因此高優先權的task的vruntime很快的就又變成最小的，因此執行頻率較高，有比較好的response time。 [color=#4a8aa1]

:question: 假設現在系統的min_vruntime為6450000，當一個新的task進入OS以後，新的task的vruntime設為何者比較合理?
> 6450000。因為新抵達的task應該要有全新的time slice，因此新進的task的vruntime，應該與目前正在執行的task的vruntime（即：min_vruntime）相等才比較合理。這樣的設定相當於這個task從未被執行過。 [color=#4a8aa1]

:bulb:Linux中的priority（nice）和真正的priority的不同
> Linux 優先權分成140個等級（0~140）
> * (0~99) real-time priority
> * (100~139) nice value
>
>使用者可以設定 nice value （-20~+19）
>這個nice value會被OS參考，考量核心、mult-thread、bound、省電、效能的特性，最後得出的 dynamic priority 才是真正的 priority。 [color=#4a8aa1]

## CH5 syncronization
多個task同時存取「記憶體」會發生彼此複寫的問題

### race condition
兩個以上的行程共用一個資源時，在進行存取時因為順序不同，導致結果不一致
* 解法
* 使用critical section的概念
> 臨界區段（Critical section）指的是一個存取共用資源的程式片段，而這些共用資源有無法同時被多個執行緒存取的特性。
> 需要滿足三個條件：
> * mutual exclusion(互斥執行)：如果有一個task在critical condition，其他的不能進去
> * progress：如果當下沒有task在critical section，則讓想進去的task進去
> * bounded waitong：如果有task想進去critical section，不能讓他等太多次。不能只有只有特定的task進入critical section。

### Peterson’s solution
完全解決race condition的「純軟體」演算法，這個演算法假設只有P0、P1二個task
對於硬體有一些重要的基本：假設「load」和「store」是atomic operations、共享記憶體的系統

bool flag[2] = {false, false}; /*分別代表P0及P1是否想進入CS*/
int turn; /*turn = 1或0，代表這一回合誰的「進入權」比較高*/

* P0

    while(1) { /*代表P0週而復始地想進入CS*/
        flag[0] = true;     /*告訴大家，P0想進入CS*/
        turn = 1;           /*如果P1也想進入CS，讓P1先進去*/
        while(flag[1] == true AND turn ==1) /*P1進入權比較高，且P1想進入CS*/
            ;//用while loop實作出wait
        
        /*critical section，可以於此更新共享資料結構*/
        
        flag[0] = false;    /*離開CS，因此將flag[0]設定為false。
                            /*表示P0目前不需要待在CS了*/
    }

* P1

    while(1) { /*代表P1週而復始地想進入CS*/
        flag[1] = true;     /*告訴大家，P1想進入CS*/
        turn = 0;           /*如果P0也想進入CS，讓P0先進去*/
        while(flag[0] == true AND turn ==0) /*P0進入權比較高，且P0想進入CS*/
            ;//用while loop實作出wait
        
        /*critical section，可以於此更新共享資料結構*/
        
        flag[1] = false;    /*離開CS，因此將flag[1]設定為false。
                            /*表示P1目前不需要待在CS了*/
    }

:::danger
:exclamation: C11版本以前，不支援autoic operation，記憶體優化時可能會把程式碼位置對調
:::
#### 證明Peterson’s sol. 滿足critical section的三個條件
* mutual exclusion的證明：
* P0和P1同時執行，這二個task都可能設定turn變數，因此turn可能等於0要不然就是1
> * 這是因為store是atomic operation，並且是共享記憶體系統，因此turn只可能等於0或者是1
> * 如果store不是atomic operation，那麼有可能P0看到的turn是1，而P1看到的turn是0
* progress的證明：
* 假設P0想進入CS，P1不想進入CS
> * flag [0] == 1; flag[1] == 0;
> * turn == 1; /* 因為P0執行了「禮讓」程式碼 */

> 雖然turn==1，但由於P1不想進入CS，因此flag[1] == false，下列程式碼的條件不成立，P0可以進入CS。
> * while(flag[1] == true AND turn == 1)

> 因此我們證明了，當CS裡面沒有task正在執行時（在本例中P1不想進入CS），P0可以進入CS，滿足progress的定義

* 假設P0想進入CS，P1想進入CS但P1只執行到flag[1] = true;
> * flag [0] == 1; flag[1] == 1;
> * turn == 1; /* 因為P0執行了「禮讓」程式碼 */

> 因為turn == 1，對P0而言，下列程式碼的條件不成立，P0不可以進入CS。
> * while(flag[1] == true AND turn == 1)

> 但根據程式碼，當P1執行到flag[1]=true以後，隨後會執行turn=0，之後P0就可以進入CS

* 假設P0、P1都想進入CS
> 那麼如同mutual exclusion的證明，P0或P1當中有一個人可以進入CS
* bounded waiting的證明：
* 證明方向：第一次是P0進去的話，下次一定是P1進去
> 第3行，禮讓

<br><br>

---

# OS 作業系統 CH5 - CH9

> 2020 期末筆試：https://drive.google.com/file/d/18s6foChr2IIxvw7wuKNRJb6Vwumxu8Q4/view?usp=sharing

## CH5 syncronization

### Semaphore & Mutex

* #### Spinlock
如果執行緒沒有獲取鎖，則會進入迴圈直到獲得上鎖的資格，因此叫做自旋鎖。
* 效能較高
* Busy waiting
> 一直不斷的詢問是否可以訪問，在lock不成功時，會使用一個loop等待。
* 無意義的等待
> 在semaphore、mutex中，因為「等待的task」都被scheduler換出了，因此不會「無意義的等待」

:::info
要等很久 ➜ 使用Semaphore
等一下子 ➜ 使用Spinlock (資料庫系統等大型軟體)
:::

* #### Semaphore
是一個同步物件，用於保持在 0 至指定最大值之間的一個計數值。
* 當執行緒完成一次對該 semaphore 物件等待時，該計數值減一。
* 當執行緒完成一次對semaphore 物件釋放時，該計數值加一。
* semaphore物件的計數值大於0，為signaled狀態；計數值等於0，為nonsignaled狀態。

> **可以設定同時被 Acquire 的次數**
> **可以保證 Task 的執行順序**

* #### Mutex
透過一個變數或物件確保 Critical Section 內的資料同一時間內只會有單一存取。

> 與Semaphore最大的差異在於:
> 1. Mutex 只能由上鎖的 thread 解鎖，而 Semaphore 沒有這個限制，可以由原本的 thread 或是另外一個 thread 解開。
> 2. Semaphore 可以設定同時被 Acquire 的次數，而 Mutex 則無法。所以若 Critical Section 允許被兩個以上的執行緒執行的話，通常我們會採用 Semaphore。

* #### adaptive mutex
自適應鎖，Solaris中的一種鎖機制，提供了一種更靈活高效的訪問同步資源的方法。

$p$ 和 $q$ 競爭mutex， $p$ 想要這個 mutex，討論 $p$ 的情況：
* 如果 mutex 未上鎖， $p$ 獲得鎖
* 如果上鎖：
* **$q$ 在另外一顆處理器，且 $q$ 在 OS 的 waiting queue**（例如：正在讀資料），則 $p$ 進入 sleep 的狀態等待 mutex（即context-switch）
* **$q$ 在另外一顆處理器，且 $q$ 不在 waiting queue**（表示 $q$ 正在運算），則 $p$ 採用 busy waiting 的方式等待mutex（因為覺得應該快結束了）
* **$q$ 和 $p$ 在同一顆處理器上**，則 $p$ 進入 sleep 的狀態等待 mutex（即context-switch）
> 如果不曉得到底該用spinlock或mutex，那麼就用adaptive mutex

* #### futex
fast user-space locking，用來實現Mutex以及Semaphore。

### Producer-consumer problem
也稱有限緩衝問題（Bounded-buffer problem），是一個多進程同步問題的經典案例。該問題描述了共享固定大小緩衝區的兩個進程「**Producer**」和「**Consumer**」在實際運行時會發生的問題。
Producer 的主要作用是生成一定量的數據放到緩衝區中，然後重複此過程。與此同時， Consumer 也在緩衝區消耗這些數據。
該問題的關鍵就是要保證**Producer不會在緩衝區滿時加入數據**，**Consumer也不會在緩衝區中空時消耗數據**。

* ### Solution
* buffer的長度為N
* Semaphore mutex initialized to the value 1
* 可以到buffer裡面存取嗎，請先將mutex當成semaphore，其初始值為1
* Semaphore full initialized to the value 0
* 意義是：buffer裡面還有東西嗎？
* Semaphore empty initialized to the value N.
* 意義是：buffer裡面還有空位嗎？

**Producer**

    do {//produce an item in nextp
        wait (empty);
        wait (mutex);
        //add the item to the buffer
        signal (mutex);
        signal (full);
    } while (TRUE);

**Consumer**

    do {
        //produce an item in nextp
        wait (full);
        wait (mutex);
        //remove the item from the buffer
        signal (mutex);
        signal (empty);
    } while (TRUE);

### Cache coherence problem
CPU必須使用一些特別的方法保證所有core看到的資料是一樣的，否則「共享記憶體」的假設就不成立，不同core擁有不同的cache，因此core可能看到「新舊不一」的值。
* Snoop
利用廣播(broadcast)的方式，當一個CPU修改了cache line之後，就會發送通知到Bus，而其他CPU會利用snooper不斷的監聽Bus來得知Cache目前的狀況。
> * 空間成本較低
> * 無法實現點對點傳輸

* Dictionary
點對點傳送資料，當一個CPU修改了cache line之後，他會利用Dictionary跟其他Cache有相同資料的CPU發送通知，也就代表所有CPU的cache line的信息，都被記錄在這個directory裡。
> * 空間成本較高（要記住最新版本在哪邊）
* Snoop + Dictionary
* 目前較好的CPU通常使用混合式做法

### Atomic operation

我看不到重點QQ

## CH7 main memory

### BIOS
Basic Input/Output System 基本輸入輸出系統，亦稱為ROM BIOS。
* BIOS的資料不需要電力就可以保存
* BIOS的速度通常較DRAM要來慢

## 後面ㄉ東西沒時間整理ㄌ:P