## L7 Classical Problems of Synchronization

1. **Bounded-Buffer Problem**

這個問題描述了有兩個並行進程——生產者(producer)和消費者(consumer)共享一個有界緩衝區(bounded buffer)。生產者的工作是產生數據，並將數據放入緩衝區中;消費者的工作是從緩衝區中取出數據進行消費。

問題的關鍵是:
- 緩衝區容量有限,因此生產者在緩衝區滿時需要等待,直到有空間。
- 當緩衝區為空時,消費者需要等待,直到有新數據可消費。

需要設計合適的同步機制來協調生產者和消費者的操作,防止競態條件(race conditions)、死鎖(deadlocks)等問題的發生。

2. **Readers and Writers Problem**

這個問題描述了多個讀者(reader)和寫者(writer)進程同時訪問一個共享數據對象或文件。讀者只需讀取數據,但寫者需要修改數據。

問題的關鍵是:
- 當有寫者在寫入數據時,不允許其他進程訪問共享數據。
- 任意多個讀者可以同時讀取共享數據。
- 寫者優先權高於讀者,即當有寫者請求訪問時,新的讀者必須等待。

需要設計合適的同步機制,既要確保讀者和寫者之間的互斥訪問,又要避免不必要的等待,提高並行度和數據吞吐量。

3. **Dining-Philosophers Problem**

這個問題通過形象比喻描述了線程之間競爭資源分配和死鎖問題。有5位哲學家環坐在一張圓桌邊,每兩名哲學家之間放有一根筷子,每個哲學家最多只能同時拿到兩根相鄰的筷子。哲學家們在思考和進餐之間交替。

問題的關鍵是:
- 每個哲學家必須同時獲得左右兩根筷子才能進餐。
- 如果哲學家們都採用相同的獲取筷子順序,就可能會發生死鎖。

這個問題需要設計合理的資源分配策略和同步機制,既要避免死鎖、也要確保哲學家們能夠公平地獲得資源而不會產生飢餓(starvation)等問題。

# L8 Deadlock
- Resource-Allocation Graph
- 有迴路表示可能(非一定)有deadlock發生
- 
- 反例
- 

### DEADLOCK 條件
1. **互斥（Mutual Exclusion）**：
- **定义**：一次只能有一个进程可以使用一个资源。如果一个资源被一个进程占用，其他进程不能同时使用这个资源。
2. **保持和等待（Hold and Wait）**：
- **定义**：一个进程已经持有至少一个资源，同时还在等待额外的资源，这些资源被其他进程持有。
- **例子**：假设进程A已经占用了打印机，现在需要扫描仪来完成任务。然而，扫描仪此时被进程B占用，进程A必须等待进程B释放扫描仪。
3. **不可剥夺（No Preemption）**：
- **定义**：资源不能被强制性地从进程中剥夺，必须由持有资源的进程自行释放。当进程完成任务后，才会释放资源。
4. **循环等待（Circular Wait）**：
### Deadlock Handling
- 確保系統不進入deadlock state
- prevention
- 破壞四必要條件任一
- avoidance
- single instance：resource allocation graph
- multiple instance：Banker's Algorithm
- 允許進入deadlock然後復原
- 直接忽略，就讓它死
### Deadlock recover
* Process Termination
* 中止所有deadlocked threads
* 一次中止一個process直到deadlock cycle被消除
* Resource Preemption
* 挑選一個受害者：挑選代價最小的
* Rollback：回到safe state，並重啟thread
* Starvation：相同的thread可能會一直被挑選成為受害者，將roll back次數納入cost考量
# L9
- protection
- base registers
- limit registers
- 不能寫在自己process能用的記憶體外
- 
## Address Binding
* input queue：含有從磁碟準備進入記憶體的程式
* address在不程式生命週期的不同階段有不同表示法
* Source code address：通常有象徵性
* Compiled code address：綁定到某address的相對距離
* linker or loader會把相對距離綁定到實際位址

## Binding of Instructions and Data to Memory
- 指令和資料到記憶體位址的binding可能發生在以下三個不同的階段
* compile time：事先知道記憶體位址，產生absolute code
* 如果起始位置發生變化，必須重新編譯程式碼
* load time：
* 在compile time時不知道記憶體位址，產生relocatable code
* execution time：
* 若process在執行時可以在記憶體中被移動
* Binding delayed until run time
* 需要hardware support
## logic/physical address
- Logical(virtual)
- ==generated by the CPU==
- user program只處理這個
- Physical
- seen by the memory unit

## Memory-Management Unit (MMU)
- MMU用來把邏輯地址轉為實際地址
- 
- 用戶程序從不直接接觸或處理物理地址，而是以虛擬地址取代
- base register=relocation register
## Dynamic Loading
- 只有當需要某個模塊或函數時，才會加載它，這樣可以節省內存。
- 不需要OS支持
## Dynamic Linking
- 共享庫：動態連結通常使用共享庫（shared libraries），這些庫可以被多個程序同時使用，從而節省內存和磁盤空間。
- 程序內會加個stub表示要使用共享程式庫
- 需要OS支持
- 延後到執行時才linking
## memory allocation
### 連續分配（Contiguous Allocation）
- 同個程式放在同個區段內
- 主記憶體通常被分為兩個partition
* os通常跟interrupt vector一起被放在low memory
* user process被放在high memory
* 每個process被放在記憶體中的一個contiguous section
#### fixed allocation
- 是一種早期方法：
- 主要記憶體劃分
- 駐留操作系統（Resident Operating System）：通常位於低位記憶體區域，並且包含中斷向量。
- 用戶進程（User Processes）：被放置在高位記憶體區域。
- Relocation registers用於保護使用者進程免受彼此影響以及作業系統程式碼和資料的更改
- Base register contains smallest physical address
- Limit register contains range of logical addresses
#### varible size allocation
- 可變分區是一種內存管理技術，其中內存被劃分為不同大小的分區
- 由於分區大小是可變的，系統可以更有效地利用內存，減少內存碎片
- 當進程退出時，釋放的內存形成==Hole==能被其他進程使用
- 填external hole策略
- first fit
- 第一個符合大小的洞
- best fit
- 最接近程序大小的洞
- worst fit
- 最大的洞
#### 解決external hole
- compaction
- 不連續分配(paging)
### 不連續分配
- 同個程式可以放在不同區段內
#### page table 特性
- Page table is kept in main memory
- Page-table base register (PTBR) points to the ==page table==
- Page-table length register (PTLR) indicates ==size of== the page table
#### TLB
- store address-space identifiers (ASIDs)
- 用來辨別每個process擁有的page
#### paging
- 碎片化
- 外部碎片 (External Fragmentation)
- 內部碎片 (Internal Fragmentation)
- paging
- 避免外部碎片，但還是有內部碎片
- Divide physical memory into fixed-sized blocks called **frames**
- Size is power of 2, between 512 bytes and 16 Mbytes
- Divide logical memory into blocks of same size called **pages**
- **page table** 轉邏輯內存為物理內存
- 
- memory protection
- 設定read/write only
- in/valid bit
- share memory
- paging/segment可
- 連續分配不行
- Effective Access Time (EAT)
- If we find the desired page in TLB then a mapped-memory access take 10 ns
- Otherwise we need two memory access so it is 20 ns
- EAT=0.99 x 10 + 0.01 x 20
- valid/invalidbit
- page not in the process logical address space
#### swapping
- Backing store
- SSD?
- Roll out, roll in
- 較低優先權的進程被換出，以便可以載入和執行較高優先權的進程
- 系統維護一個準備運行進程的就緒隊列，這些進程在磁碟上有記憶體映像
- double buffering
- 增加開銷
- 將 I/O 傳輸到核心空間，然後傳輸到 I/O 設備
# 第十章：虛擬內存
- 虛擬內存
- 能夠跑很大的程式
- disk很大
- 增加CPU利用率
- 能放入更多process
- higher multiprogramming degree
- 簡化程式設計師工作
- 不須程式設計師親自限制內存
- 程式執行更快
- 不用一次load完
- 因demand paging

* 補充：找空位demand paging o(1)較demand segment o(n)快
- Demand Paging
- 它與傳統的預先加載所有程式或頁面到內存中的方式不同，而是僅在需要時才將頁面加載到內存中
- Lazy swapper
- never swaps a page into memory unless page will be needed
- pager
- 負責處理頁面（pages）的交換（swapping）工作的組件通常被稱為。
- 效能
- EAT(存取時間)=(1 – 頁錯) x 內存存取時間 + 頁錯 (頁錯處理時間)
- 虛擬內存對效能影響不大，因為locality(一次搬一個page)
- page fault
- 當location在程式範圍內，但Valid-Invalid Bit為Invalid時觸發
- 
- OS判斷
- Invalid reference=>abort
- Just not in memory
- free-frame list
- a **pool** of free frames
- 用于跟踪可用物理内存框架的数据结构。
- zero-fill-on-demand
- 要被分配前清0
- Copy-on-Write
- 当多个进程共享相同内存资源时，只有在其中一个进程尝试修改资源时才会进行克隆
- 在有虛擬內存時能幫助fork()更有效率
- Page Replacement
- 使用dirty bit減少頁面傳輸的開銷，僅將修改的頁面寫入磁盤
- 若無free frame可分配時，呼叫Page and Frame Replacement Algorithms
### Page and Frame Replacement Algorithms
#### 目標
- lowest page-fault rate
#### FIFO
- 不是很好
- Belady's Anomaly：增加frame數量可能產生更多page fault
#### stack algorithm
- [增加frame後不會導致Belady's Anomaly](https://youtu.be/TXcPJuccafA?list=PLS0SUwlYe8czigQPzgJTH2rJtwm0LXvDX&t=959)
- Optimal(Belady)
- replace掉將來最晚用到的frame
- 無法實作：無法預知未來輸入
- LRU(Least Recently Used)
- 理論來源：locality
- 之前最早access的被踢掉
- 
- 用hasing map使得尋找只需O(1)
#### count algorithm
- 用個計數器紀錄當前每個frame出現次數(已經不在frame內的不需要記)
- 
- 花費較LRU昂貴，效果也不一定更好
- LFU(Lease Frequently Used)
- 驅逐最少用的frame
- MFU(Most Frequently Used)
- 驅逐最常用的frame
### allocation
- Fixed allocation &local allocation
- 只能用自己程序的free frame
- Priority allocation&global allocation
- 能用的任意的free frame
- priority高的能一直搶priority低的frame

### thrashing
- 定義
- paging spending more time than execute
- >OS增加degree of multiprogramming增加效能>每個程式沒有足夠frame>需一直swap>降低效能>loop
- 
- 解方1 Working set(少用 overhead高)
- 
- 觀察一個時間內需要的frame數量，較精準的分類
- 若需要的frame>可用的frame，則發生thrashing，此時中止程序
- 若需要的frame<可用的frame，則可以增加degree of multiprogramming
- 解方2 page fault freqency scheme
- 監視每個程序的page fault rate
- 若某程序的page fault rate>限制，則多給他一些frame
- 若某程序的page fault rate<限制，則把他的frame給其他人
### kernel memory allocate?
#### Buddy System:
- Buddy System是一種基於==binary tree==的動態內存分配算法,通過將空閒內存塊以2的指數大小進行切分和合併,以應對不同大小的內存請求。
- 

#### Slab Allocator
- Slab Allocator是一種用於管理系統中內核級緩存的內存分配器,它將內存分成多個slab,每個slab僅包含特定類型對象的快取,以期提高內存分配和釋放的效率。
# L11
### Access Latency
- Average access time = average seek time + average latency
### 名詞
- Mass Storage Structure
- hdd
- Nonvolatile Memory Devices
- ssd
- usb
- Volatile Memory
- DRAM
- RAM disk
- Disk Attachment
- ATA
- SATA
- USB(most common)
- pci(connecting directly to PCI bus)
#### HDD Disk Scheduling
- FCFS
- 
- SSTF(Shortest Seek Time First)
- 
- SCAN
- 
- Circular-SCAN
- 
- NVM Scheduling
- random I/O
- Throughput can be similar
### Error detect
- 錯誤檢測
- 奇偶校驗（Parity Bit）：一種校驗和形式，使用模數運算來計算、存儲和比較固定長度的數值。
- 循環冗餘檢查（CRC）：常用於網絡，利用hash function來檢測多比特錯誤。
- 錯誤校正：
- 錯誤校正碼（ECC）：不僅能檢測錯誤，還能校正某些錯誤。
- 軟錯誤：可校正的錯誤。
- 硬錯誤：能檢測但無法校正的錯誤。
- 應用領域：
- 內存、網絡和存儲中廣泛使用錯誤檢測與校正技術，以確保數據完整性和系統可靠性。
### 磁碟的低階格式化和高階格式化
- 低階格式化 (Low-level formatting)：
- 也稱為物理格式化 (physical formatting)。
- 將磁碟劃分為扇區，這些扇區可以被磁碟控制器讀寫。
- 每個扇區包含標頭信息、數據和錯誤校正碼 (ECC)。
- 通常每個扇區可以容納 512 字節的數據，但這個大小是可選的。
- 磁碟用於存儲文件的準備：
- 作業系統需要在磁碟上記錄自己的數據結構。
- 將磁碟劃分為一個或多個圓柱組，每個圓柱組被視為邏輯磁碟。
- 邏輯格式化 (Logical formatting)：
- 也稱為「建立文件系統 (making a file system)」。
- 為提高效率，大多數文件系統將塊 (blocks) 組合成群集 (clusters)。
- 磁碟 I/O 是以塊為單位進行的。
- 文件 I/O 是以群集為單位進行的。
### Storage Device Management
- 根分區(root partition)：主要包含操作系統的分區。
- 啟動塊(boot block)：包含指向啟動卷或啟動加載器的代碼，以便正確加載操作系統內核。
- raw disk access：允許應用程式直接管理磁碟塊，如數據庫。
- 引導程序(Bootstrap loader)：存儲在啟動塊中，負責加載操作系統。
- 壞塊處理：使用技術如扇區備援(sector sparing)來處理磁碟上的壞塊，確保數據完整性。
### Swap-Space Management
- Secondary storage slower than DRAM, so important to optimize performance
- 通常可以有多個交換空間，以減少任何單個設備的 I/O 負載。
- 最好是有專用設備(dedicated devices)來存儲交換空間。
### RAID
- 
- C=copy
- P,Q=parity bit
# Q
- valid/invalid：那格有沒有資料
- dirty 快取被改過，標記後寫回ram