---
title = 'shiwulo os final'
writer = 'Zekk Liu'
---
*** Shiwulo os final ***
如果有寫錯，請留言告訴我，謝謝 !

# Summary
[TOC]

Ch5 Synchronization
===
> Note: gdb可能會自動優化程式碼(-O3)，導致平行化處理失敗。

Critical section
---
CS成立條件
> #### 1. mutual exclusion
> >一次只能有一個人進入
> #### 2. progress
> >沒有人在CS的話，則要讓想進入CS的人進去
> #### 3. bounding waiting
> > 不能讓某個人等太久(或是無窮等待)

Peterson's solution: 禮讓對方先進去

atomic_thread_fence()
> fence上下的程式碼不能隨意交換

lfence
> 只限制load的fence

sfence
> 只限制store的fence

Semaphore & mutex
---
Mutex/semaphore
> = spinlock + sleep + wakeup
>
> 
>
> 
> * 引用自 https://hackmd.io/@hui0705/CCU-Shiwulo-OS#OS-%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1-CH5---CH9

semaphore若lock失敗，則會造成ctx-sw。所以要使用這個方法通常都是用在要等比較久的情況。

spinlock若lock失敗，會進入loop等待unlock，所以會一直測試而浪費CPU time。

> 結論: 等很久(與ctx-sw比較)用semaphore，等一下下用spinlock。
> 而spinlock效能較高，但可能會出現無意義的等待。

semaphore實作

wait(S){
  	value--;
	if(value<0){
		block();
	}
}

signal(S){
	value++;
	if(value<=0){
		wakeup(P);
	}
}

恐龍書對mutex定義: 01-semaphore

特色
> ##### 1. 判斷誰鎖住mutex(owner概念)
> ##### 2. 可能有有先權繼承
> ##### 3. 可能有槽狀鎖定
> ##### 4. 可能支援自適應鎖(adaptive mutex)

adaptive mutex (Sun Solaris)

* 引用自 https://hackmd.io/@hui0705/CCU-Shiwulo-OS#OS-%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1-CH5---CH9

> 簡單來說adaptive mutex就是
> > p發現q在執行 => spinlock (q在執行表示應該很快就會離開CS)
> >
> > p發現q沒在執行(可能在讀資料啥的) => mutex (不要浪費CPU)

Futex
---


* 引用自 https://hackmd.io/@hui0705/CCU-Shiwulo-OS#OS-%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1-CH5---CH9

Producer Consumer problem
---
> Note: in & out請參考circular queue

* 引用自 https://hackmd.io/@hui0705/CCU-Shiwulo-OS#OS-%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1-CH5---CH9

### 一對一的producer consumer
> 共享in & out這兩個變數就可以解決。(一次只會有一個人write)

volatile int in = 0, out = 0;
void put(){
	static int item = 1;
	while(((in + 1) % bufsize) == out)
		; // do nothing / no free buffers / busy waiting
	buffer[in] = item++;
	in = (in + 1) % budsize;
}
void get(){
	int tmpItem;
	while(in == out)
		; // do nothing / busy waiting
	tmpItem = buffer[out];
	out = (out + 1) % bufsize;
}

> 因為只有一個producer-consumer，不會發生race condition，所以不需要lock。

### 多個Producer consumer

#### 做法
> ##### 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);

Reader-writer problem
---
定義
> reader只能讀，可以有很多個
> writer可以讀寫，只能有一個

Test_n_set
---

CPU上的指令，內容為"讀+修改+寫入"(read-modify-write)

#### test_n_set(int *lock)
> 回傳舊的lock值，set lock value to 1

#### atomic_swap(int *a, int *b)
> 類似test_n_set

新方式使用test+test_n_set
> 就是C11的atomic_compare_exchange()

Ticket lock
---
> Note: 具有FIFO的spinlock，overhead跟spinlock差不多。

概念:
> #### 1. 進入CS前先抽號碼牌
> #### 2. 等待叫號，如果叫到自己則進入CS
> #### 3. 離開CS就做"叫號"的動作

struct ticketlock_t(){
	volatile atomic_int next_ticket;
	volatile int now_serving;
};
void ticketLock_acquire(volatile atomic_int* next_ticket, volatile int* now_serving){
	int my_ticket;
	// 抽號碼牌，利用atomic operation避免race condition
	my_ticket = atomic_fetch_add(mext_ticket, 1);
	while(*now_serving != my_ticket)
		; //busy waiting
}
void ticketLock_release(volatile int *now_serving){
	++*now_serving;
	// 離開前叫下一個號碼
}

Sequential lock (seq lock)
---
> Note: reader付出成本的reader writer solution

概念:
> 共享一個變數version，當version是奇數則表示writer還在執行，所以redo。若是偶數表示資料就是正確的。
>
> 可用在更新時間的資料。

void seq_wrt_lock(){
	atomic_fetch_add(&g_version, 1);
}
void seq_wrt_unlock(){
	atomic_fetch_add(&g_version, 1);
}
void rd_thread(void* para){
	while(1){ // reader的main loop
		while(1){ // 讀取資料，如果writer正在更新資料(在CS當中)的話就重讀(redo)
			int local_version;
			if((locak_version = atomic_load(&g_version)) % 2 == 1) continue; // writer in CS，redo
			for(int i=0; i<100; i++)
				; // 模擬讀取資料
			if(local_version == atomic_load(&g_version))
				break; // 資料正確，結束
			else
				continue; // 資料不同，redo
		}
	}
}

rw-spinlock
---
> Note: reader太多的話，writer可能會starvation

概念:
> writer進入CS一次拿大量的票(e.g. 1000，包場的概念)，確保其他人不能進入CS。
>
> reader一次拿一張，且最大門票不能太多，不然做減法後可能會underflow。

void init_rwspinlock(){
	atomic_store(&nTicket, maxTicker);
}
void wrt_lock(){
	while(1){
		atomic_fetch_sub(&nTicket, maxTicket); // 避免發生race condition
		
		int ret = atomic_load(&nTicket);
		if(ret == 0) return; // 表示沒有人在CS
		else atomic_fetch_add(&nTicket, maxTicket); // lock失敗表示有人在CS，把門票家回去
	}
}
void rd_lock(){
	while(1){
		atomic_fetch_sub(&nTicket, 1); // 拿一張門票
		int ret = atomic_load(&nTicket);
		if(ret > 0) return; // 表示可能有reader在CS，或是根本沒有人
		else atomic_fetch_add(&nTicket, 1); // 表示有writer在CS
	}
}
void rd_unlock(){
	atomic_fetch_add(&nTicket, 1);
}
void wrt_unlock(){
	atomic_fetch_add(&nTicket, maxTicket);
}

在所有lock中的測試迴圈可以加入asm("pause")，避免造成CPU的負擔。

Cache coherence
---
#### Snoop
> 利用廣播(broadcast)的方式，當一個CPU修改了cache line之後，就會發送通知到Bus，而其他CPU會利用snooper不斷的監聽Bus來得知Cache目前的狀況。
>
> 重點: 空間成本低，利用broadcast，無法點到點傳輸
>
#### dictionary
> 點對點傳送資料，當一個CPU修改了cache line之後，他會利用Dictionary跟其他Cache有相同資料的CPU發送通知，也就代表所有CPU的cache line的信息，都被記錄在這個directory裡。
>
> 重點: 空間成本高(要記最新版本在哪)，可以點到點傳輸

目前最好的做法是snoop跟dictionary一起實作。

#### DMA & Cache coherency

if有新資料:
> 1. 在cache
> > flush到記憶體
> 2. 在網路卡(NIC)
> > 直接寫入記憶體

Memory Order
---
在stdatomic.h有以下這些memory order
1. relax // 最弱
> 指令可以上下隨意搬移
2. consume
> 相關指令不可以往上搬
3. acquire
> 不論相不相關都不可以往上搬
4. release
> 不論相不相關都不可以往下搬
5. acq_rel
> 在lock成功之前都不能執行，直到其他thread unlock(或是自己lock成功)後才執行。如果要對變數做read-modify-write，可以考慮使用acq_rel
6. seq_cst(sequence consistance) // 最強
> 具有acq_rel的所有特性，且所有宣告的acq_rel都要按照某個順序執行，不能同時執行
> 需要滿足以下條件:
> ##### 1. Program order
> ##### 2. Write atomicity

Deadlock
---
定義
> 一群task彼此等待

#### livelock
> 彼此不斷改變狀態禮讓對方進入CS，而導致沒人進入CS

#### starvation
> 按照優先權分配資源，優先權最低的task可能永遠拿不到資源

發生Deadlock的四個必需條件
> #### 1. Mutual exclusive
> > 資源無法共用
> #### 2. Hold and wait or resource holding
> > 握有資源然後在等待其他資源，但會造成資源使用率降低
> #### 3. No preemption
> > OS無法重新分配已分配出的資源，可以用重跑的方式解決，但可能造成某些程式不斷重跑
> #### 4. Circular wait
> > resource allocation graph中至少有一個等待迴圈，解決方式可以依照特定順序做lock。(這種解決方式與程式碼的撰寫方式有關)

#### deadlock avoidance

> 不讓系統進入可能造成deadlock的狀態

#### 著名方法
> #### 1. priority celling protocol (PCP)
> > 高優先權最多等低優先權"一次"
> > real-time OS常用的方法，要搭配rate-monotonic(RM)排程演算法使用
> > RM是real-time system最常見的排程演算法
> #### 2. stack resource policy (SRP)
> > 與PCP相似
> > 可以搭配earliest deadline first(EDF)排程演算法使用

#### deadlock prevention
> 不讓系統進入circular wait的狀態

解決系統進入deadlock
> 1. rollback後釋放出資源
> 2. kill某些task(e.g.選擇占用特別多資源的task)

Linux kernel的Semaphore
---

主要函數
> ##### down(semaphore *sem)
> > count>0表示lock成功，成功進入CS。否則進入wait_list並呼叫schedule()
> >
> 新版down function
> > ###### down_interruptible()
> > > 發生signal時喚醒task
> > >
> > ###### down_killable()
> > > fatal signal以外的不會喚醒，直到想處理的事件處理完。
> >
> ##### up(semaphore *sem)
> > 如果wait_list()是empty，那count++，否則找出放到wait_list最前面的task，將其移除並呼叫wake_up_process將task放到run-queue

Ch7 Main Memory
===

記憶體配置
> ##### 1. OS找出程式所需要的記憶體
> ##### 2. OS將執行檔複製到記憶體
> ##### 3. OS將未初始化的部分給"0"

MMU
---

#### External fragmentation
> free space夠多，但無法滿足目前的記憶體需求

#### Internal fragmentation
> 因為配置演算法，多分配了記憶體給原本沒需要那麼多的app

#### 解決fragmentation
> 搬動記憶體位置 => 定址方式必須是相對定址。需要更改base reg. file的stack、data、code。
> 預防程式碼出錯，會設定lim的大小以防出錯(觸發segmentation fault)，而程式之間不會互相干擾。
> ctx-sw要切換gemeral reg.以外，也要切換base reg. file

50 percent rule
---
系統中不可以用的記憶體數量是可用記憶體的一半(50%)，也就是說系統中有1/3的記憶體因為external fragmentation而無法使用。

Page
---
記憶體最小管理單位為page，且不需要連續分配。每個page都要設定用途的屬性。
CPU透過vertual address查找page table後，找出對應的physical address

#### 區段(segmentation)管理機制 v.s. 分頁(paging)管理機制
> 分頁較有彈性，只要找夠多的page即可。而每個page size是固定的，演算法叫好寫
> 一個區段包含很多page，導致映射表格很大，而造成硬體在映射時速度變慢。

#### fragmentation 討論
> (segmentation problem)
> segmentation會出現free space不連續，導致external fragmentation
>
> paging因為每個page大小一致，而透過映射的方式連接不連續的page，所以沒有external fragmentation。
> 但paging只能給恰好一個page倍數大小的記憶體，所以很多情況下都只能多給，而造成internal fragmentation。

Page的硬體管理機制
---
一般來說1 page = 4kb，而且page的起始位置必須是4kb的倍數。
huge page大小可以是2M or 1G

MMU可以說是一個(平行)搜尋表格，而查找的表格mappingTBL改名成translation lookaside buffer(TLB)
TLB的數量限制程式大小 => 透過增加TLB數量 or 動態載入TLB

#### TLB miss
> 無法在TLB找到對應的page number的entry

##### 硬體解決方式
> 對page table進行分層。

> PTE: page table entry
>
> 整個32bit可以分成前面20bits的page number以及後面12bits的page屬性。
>
> virtual address在查找TLB(translation lookaside buffer)的時候，如果出現TLB miss，就把page number切成10bits的LV1 PTE以及10bits的LV2 PTE。

#### PTBR - page table base register
> 在intel中為CR3(control register 3)，把PTE對應到的page的前20bits拿出來，接著把後面12bits補0，就是下一個page的位置。然後在查找LV2 pte就可以知道frame number(physical number)了(又或是invalid，在後面章節會提到)。
>
> PTBR暫存器指向第一層(LV1)的page table，而CR3所存放的是第一層page table的physical address。

Buddy system
---
buddy - 好兄弟
> 同一個parent才可以合併

Slab
---
類別
> ##### 1. slab full
> ##### 2. slab partial
> ##### 3. slab free

特色
> 配置後很難進行壓縮，因為很難回收，原因是不知道有沒有人還在用。
> 除非變成slab free才有辦法回收。

Malloc
---
> 從"heap"中找"閒置"的記憶體

heap
> 連續配置的記憶體空間，大小是4k的倍數
> 資料結構: ptmalloc

Ch8 Virtual Memory
===

Page fault
---
> OS還未將page載入DRAM(重新載入就解決)，或是有讓不同process"隱形共用"內容相同的page。

virtual memory 組成要件
> ##### 1. 硬體定義表格
> > page table
> ##### 2. 純軟體表格
> > 定義堆疊或是程式碼之類的區段，檢查記憶體是否正確。
> ##### 3. 處理page fault
> > 要有page fault handler(interrupt service routine)

virtual memory 常見功能
---
### 1. shared page
> ##### 1. 應用程式使用相同函數庫 e.g. libs
> ##### 2. 透過shared memory共享資料 e.g. mmap
> ##### 3. Linux kernel可能會將內容一樣的page做"隱含共享" (KSM) e.g. 桌布&登入畫面
>
> How???
> > 允許process的page table中的某些PTE指向同一個data page。
> >
> > 對於thread，因為共享所有記憶體內容，所以不用切換memory context。(所以也不用切換PTBR的數值)
### 2. demand paging
> 定義: OS不會立刻把所有要用到的記憶體都配置給應用程式。發生page fault時會載入該記憶體資料。
> #### 優點
> > ##### 1. Less I/O needed
> > ##### 2. Less memory needed
> > ##### 3. Faster response
> > ##### 4. More users / programs
> #### 缺點
> > 導致大量的random access(random access很慢 大概<1M)
> > 執行期間可能會引發延遲(lag)，因為要載入page。
>
> 做法:
> > OS收到page fault，去查詢記憶體配置表格(mm_struct)看是否valid。valid就修改page table，invalid就是segmentation fault。

> #### Pure demand paging
> > Linux在執行新的檔案時，沒有配置任何page給task，稱為pure demand paging

> #### Effective Access Time (EAT)
> > EAT = (1-p) x memory access
> > \+ p x (page fault overhead + swap page out + swap page in + restart overhead)
> >
> > swap page out: page不夠
> > swap page in: 如果page不在page cache
### 3. copy on write (COW)
> 有人嘗試做寫入時(通常是fork()後)，因為共用導致write的屬性被取消(r--)，違反read-only而產生page fault。
>
> 複製一份檔案(rw-)給parent跟child。
>
> 需要R/W屬性
### 4. zero-out page
> 避免資料外洩
### 5. same page merging
> Kernel virtual machine (KVM)透過將相同的page設定成共用記憶體，節省記憶體使用。

x86的PTE屬性(12 bits)
---
##### Avali
> Avaliable for system programmer's use
##### G
> Global page
##### PAT
> Page table attribute index
##### D
> Dirty 最近write過?
##### A
> Accessed 存取過?
##### PCD
> Cache Disabled
##### PWT
> Write-Through
##### U/S
> User/Supervisor
##### R/W
> Read/Write
##### P
> Present

valid-invalid bit
> 通常在PTE的最右邊(present)，表示存不存在往下指的page。

Page Replacement
---
找出最近不會用的page，並且將其從記憶體移除。

Note: Linux kernel是non-swappable的，必要時OS還會殺掉一些task。
(OOM killer - out-of-memory killer)

### page replacement algorithm
#### 1. FIFO
越早進來的page越早剔除
#### 2. Optimal algorithm
未來最久沒有用到的page剔除
最佳演算法，但是無法預測未來
#### 3. Least recently used (LRU)
最近最沒用到的page剔除。
因為要記錄page上次的存取時間，成本太高。
可以用reference bit實作，相當於用一個bit當作時間戳記。
#### 4. Second chance (Clock)
當page被visit兩次之後就會被剔除
類似LRU演算法。
#### 5. Least frequently used (LFU)
用最少的page剔除。
#### 6. Most frequently used (MFU)
用最多的page剔除。
#### 7. Linux's page replacement
使用兩個LRU排序(active & inactive pages)。
移除page的方式是使用second chance

好處?
> 只讀過一次的page就大概率只會留在inactive，且垃圾桶的機制只花一點點記憶體便獲得容錯的機制。

##### 8. ARC (Adaptive Replacement Cache)

ARC是一種由 IBM 所提出的自動調整式快取置換策略，結合了 LRU 和 LFU 的優點。
ARC快取策略會根據近期存取模式調整自己的行為，自動選擇 LRU 或 LFU 策略來最小化快取未命中的次數。

> ARC 演算法主要會同時維護LRU與LFU兩種快取，並且紀錄這2種演算法哪些快取被置換掉。
> 也就是上圖中 Ghost list B1與Ghost list B2，這2個list都是只存快取索引，不存快取資料。如果近期的快取要求都是打中Ghost list B1，那麼演算法就會調整成使用LRU策略的快取資料比較多，使用 LFU 策略的快取資料會變少，也就是T1的部分會長大，T2的部分會變小，反之亦然。

#### Belady's anomaly
給定一個reference string，在"n+1"的frame所容納的page效能沒有比"n"個page高。

Thrashing
---
> Thrashing現象會發生在page分配到的frame不夠多時，會很頻繁的發生page fault，會使CPU的使用效率突然急速下降。
> 在paging花的時間比instructions還多。

原因
> 低CPU使用率
> 呼叫更多process(提升multiprogramming degree)，導致新的process搶走舊process的Frame
> 發生更多page fault，更多的等待I/O
> 造成CPU使用率更低

#### 解決方法
Working-set model
請自行到下方連結閱讀
https://ithelp.ithome.com.tw/articles/10208889

Ch9 Block-stroage
===

Hard disk
---

一個sector大小 = 一個page = 4kb

Flash memory
---
不支援in-place update
> 先將有用(新)的資料搬出，然後erase整個flash memory，再將資料搬入。

解決out-of-place problem: Flash translation layer (FTL)

disk scheduling
---
* 研究所常考SCAN，SCAN-EDF

NCQ: native command queue。NCQ硬碟可以透過改變讀寫次序而增加效率。
>優點: 硬碟控制器可以同時對rotational delay&seek time做優化。OS只要把commands丟到NCQ就可以讓硬碟自行排程。
>
>缺點: 不知道command的重要性(優先級)

Linux I/O Scheduling
---

目錄 & 檔案
---
#### LBA (logical block number)
目錄是一個命名系統(naming system)
路徑+檔名可以找到檔案

extents
> 連續分配位置可以獲得較高效率，但會有fragmentation problem

linked allocation
> data block前面存資料，後面存指標指向下一個
>
#### FAT (file allocation table)
> 將指標放到最前面，甚至可以將指標table放到主記憶體內。

index allocation
> 每個檔案都配置一個index block，紀錄檔案的data block在storage的哪些位置。

inode
---
> Note: shiwulo很常考一題

free space management
---
方法
> ##### 1. bit vector
> > 快速找連續記憶體空間，但要將全部都放到主記憶體 不然效率不高
> ##### 2. link list
> > 很難找到連續的記憶體空間，可能造成storage效能低落
> ##### 3. btrfs
> > 紀錄哪些block已經使用，不在btree的就是free space

目錄檔案
---
包含:
1. name
2. type
3. i-node number

RAID
---
> Note: 基本上都會考一題，應該啦

容錯式磁碟陣列 (RAID, Redundant Array of Independent Disks)，簡稱磁碟陣列。
> RAID把多個硬碟組合成為一個邏輯硬碟，因此，作業系統只會把它當作一個實體硬碟。RAID常被用在伺服器電腦上，並且常使用完全相同的硬碟作為組合。

## 主要級別
### RAID 0
> 硬碟需求: 至少2顆
> 容錯性: 0(一個壞掉就全毀)
> 特色: 將兩個以上的硬碟串聯起來，分段後分散儲存。因為可以並列處理，所以是所有級別中最快的。
### RAID 1
> 硬碟需求: 至少2顆
> 容錯性: 1(互相備份(mirror))
> 特色: 資料寫入時會同時寫到兩個以上的硬碟，安全性最好，但是磁碟使用率最低。此外，如果出現同一筆資料不同硬碟data不同，系統會不知道要讀哪個檔案。
### RAID 5
> 硬碟需求: 至少3顆
> 容錯性: 1
> 特色: 兼顧安全及儲存成本，假設為3顆硬碟RAID5時，即為可使用兩顆硬碟的容量，最後一顆硬碟做另外兩顆硬碟資料的奇偶校驗碼，只要其中有一顆不幸損壞了，當安裝上新的硬碟後，RAID可以經由另外兩顆硬碟的奇偶校驗碼及資料去算出第三顆所儲存的資料或是奇偶校驗碼。
### RAID 10/01
> 硬碟需求: 至少4顆(需要偶數增加)
> 容錯性: 2
> 特色: 兼具RAID0的讀寫速度與RAID1的備援安全性
> > RAID 10時，即為兩顆兩顆硬碟互相做RAID1，在拿這兩組做RAID0。
> >
> > RAID 01時，即為兩顆兩顆硬碟互相做RAID0，在拿這兩組做RAID1。
> >
> RAID10優於RAID01: 原因是因為RAID01只要有一顆硬碟壞掉，就完全剩下另外一組硬碟可以支援，浪費了一顆硬碟，所以通常伺服器挑選時會做RAID10。

* Question: RAID0和RAID1(mirror)何者比較適合多媒體伺服器?
> 考慮到讀取效能及價格的情況下，RAID0會比較適合，因為需要大量I/O情況下，RAID0速度優於RAID1(mirror)，並且不需考慮備份，所以不會選擇安全性較高的RAID1。