# *NCNU OS Note*
::: danger
*目前沒有公開打算
請勿外流！！！*
:::
:::info
- Author: ***小鄧 kevin***
- 本筆記依照課本排序，清大開放課程為參考
:::
## Reference
- [全英文筆記](https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/)
- [師大筆記 舊版恐龍](http://www.csie.ntnu.edu.tw/~swanky/os/index.htm)
::: warning
請一起食用！！！
:::
<!-- ch1 -->
# Ch.1 Computer System
- 4 component
- **User**
- ex. 人、電腦、機器
- **Application**
- 解決 user's computer Program 的方法統稱
- **Operation**
- Hardware resource 的==控制、合作==
- **Hardware**
- computer resource
- I/O
- CPU
- Memory
- 
## Computer-System Organization
- through ==common bus== to ==shared memory==
- cpu 經由 bus 來控制 device driver 來去判斷使用哪個 device (shared memory)
- Goal
- concurrent CPUs and device driver
- **local buffer**
- 正在ing的東西
- 類似暫存器 ==但不是==（儲存暫存器的東西）
- **device driver** 別名 device controller（原文書上，這兩個東西是分開的，基本上每一個 controller 都有一個 driver，所以應該可以把他們視為一體）
- 處理 I/O（或者說是管理 device)
- 從 buffer 丟到 memory （應該是 bus 做的事）
- 
## Structure
### Storage Structure
- 
- organized by
1. speed
2. cost
3. Volatility (揮發性)
- ==Main memory==
- 速度較快
- CPU 可直接讀取
- Volatile
- e.g. Ramdom Access Memory(RAM)、Dymanic Ramdom Access Memory(DRAM)
- ==Cache (快取)==
- 將資料暫時從下層複製到上層，目的是增加 access 的速度。
- 
- 所有資料最終都儲存在空間最大但速度最慢的磁碟。
- 為了快一點，就會把資料往上層 copy。
- ==Secondary storage==
- 速度較慢
- CPU 不可直接讀，要讀要先搬進 main memory
- non-Volatile
- e.g. hrad-disk drivens(HDDS)、non-volatile memory(NVM)
### I/O Structure
- Typical operation involves I/O requests, direct memory access ( DMA ), and interrupt handling.
- 
### I/O 運作
### 1. Busy waiting (課本沒說)
### 2. Interrupt
- I/O需要的時候，Interrupt 請求cpu做I/O
- Interrupt 產生時的OS處理流程：
- 1. 暫停目前 process 執行並保存此 process 當時執行狀況
- 2. OS 根據 Interrupt ID 查尋 Interrupt vector 並取得 ISR (Interrupt Service Routine) 起始位址(address)
- 3. interrupt 執行 (ISR 執行)
- 4. 執行完成，恢復先前 process 執行狀況
- 5. 回到原先中斷前的執行
- 
- 在monitor area內會存放interrupt vector及各種ISR
- Interrupt種類
- *Hardware Interrupt*
- **外部中斷（External Interrupt）**: CPU 外的週邊元件所引起的。（I/O Complete Interrupt, I/O Device error）
- **內部中斷（Internal Interrupt）**: 不合法(error)的用法所引起的，CPU 本身所引發。（Debug、Divide-by-zero、overflow）
- *Software Interrupt*
- **軟體中斷（Software Interrupt）**：使用者程式在執行時，若需要 OS 提供服務時，會藉由 System Call 來呼叫 OS 執行對應的 ISR，完成服務請求後，再將結果傳回給使用者程式。
- ==Singal or Interrupt → Hardware==
- ==Trap → Software==
### 3. Direct Memory Accexs (DMA)
- ++目的++: 負責 I/O 與 Memory 的溝通
- ==不需要 CPU 監督==
- 優
- CPU 有更多執行時間
- interrupt frequence(頻率)更少
- 缺
- 硬體設計複雜化
- DMA 與 CPU 採 Interleaving (交替) 使用 memory resource，一般稱為 "cycle stealing" 技術
#### 機器指令週期
- 機器指令週期：
- IF：Instruction Fetch(must mem access)
- DE：Decode (解碼)
- FO：Fetch Operands (運算元)
- EX：ALU Execute
- WM：Write result to Memory
::: danger
- 萬一 CPU 與 DMA 對 memory 存取發生conflict (衝突)，則給 DMA 較高的優先權(執行消耗小的先執行)
:::
## Hardware Protection
## Operations
### Dual-Mode Operation
- 對Hardware重要的resources實施protection，把可能引起危害的一些機器指令，設為priveleged instruction
- ++目的++：**防止user program直接使用這些priveleged instruction**
- Dual-Mode 需要硬體的額外支援，用一個 Mode Bit 記錄權限。
- Mode Bit 透過 interrupt來控制，且主要是靠Hardware支援
- User Mode (bit = 1)：一般模式
- Kernel Mode (bit = 0)：在此模式下才有權利執行特權指令
- 
### Privileged instructions
- Executed only in monitor(監視) mode
- Requested by users (system calls)
- 種類
- I/O instruction
- 關於memory management所用之Register修改指令(base、limit register)
- Timer設定指令
- Enable, Disable Interrupt指令
- Halt指令 (OS 開、關機)
- change user mode to moniter mode指令
- 
### I/O Protection
- ++目的++: **防止 user program 對 I/O Device 不正常之使用**
- ==All I/O instructions== are privileged instructions
### Memory Protection
- ++目的++：**保護 monitor 所在的區域不被 user program 更改**
- *Base register*
- holds the smallest legal physical memory address
- *Limit register*
- contains the size of the range
- ==利用 base register 及 limit register 記錄 user program 的起始位址及大小==
- 
### CPU Protection (Timer)
- ++目的++：**防止user process無限期佔用CPU而不釋放**
- Timer—interrupts
- decremented(遞減) every clock tick
- When timer reaches the value 0, an interrupt occurs
- ==Load-timer== is a privileged instruction
## System type
::: danger
- 一堆、周志遠沒教、克寧也沒教
- 操!
:::
<!-- ch2 -->
# Ch.2 OS Service
- 主要由 Command Interpreter (命令解譯器)及 System Call 所組成
### User interface
- **CLI (Command Line Interface)**
- 常見的Command Line
- 其實是透過一支 program: ==shell== 去執行
- ex. bash、cshell ...
- 流程
1. 接收 user commands
2. 判斷 command 正確與否
3. 若正確，則呼叫對應的 Service routine (command routine) 完成工作
4. 結果回傳給 user
- **GUI (Graphic User Interface)**
- 常見有接滑鼠、鍵盤、螢幕
- icons represent files, programs, actions, etc
- *Most systems have both CLI and GUI*
#### Communication Models
- **Message passing**
- Memory Copy
- 其實有點慢，too many copy 的動作
- ==從 kernel memory (OS Memory) 複製==
- **Shared memory**
- 透過 System call 去 create 需要 share memory的區塊
||Message passing|Shared memory|
|-----|--------|-------- |
|mailbox link|O |X |
|速度 |慢 |快|
|安全疑慮 |X |O|
## System calls
- user program 執行時與 OS 之間的溝通介面，當 user program 需要 OS 提供服務時，藉由呼叫 system call (伴隨==trap== to monitor mode)通知 OS
- OS 可依據 system call ID 查表，啟動 service routine 執行，得到結果，再傳回給 user program，完成服務請求
- Via software interrupt
- Generally assembly language
- System Call種類 (課本page.71)：
- Process Control
- File Management
- Device Management
- Information Maintenance
- Communication
- Protection
- 三種方法：
- *registers*
- **利用 registers 儲存參數**
- 優：快速
- 缺：不適用於參數多時。
- ∵ register 數目有限，參數不能太多
- *table in memory*
- **將參數存在 memory 中的某個表格或 Block**
- 優：適用於參數多時
- ∵ 可存參數較多
- 缺：速度較慢
- ∵不限制參數的數目與長度
- *stack*
- **利用 stack 保存參數**
- Push (保存) 參數
- OS 利用 POP 取出參數
- ∵不限制參數的數目及長度
### Application Programmming interface (API)
- 簡單來說就是API裡面有可能包含多個System call
- Language libraries,
- e.g., C Library
- API call could involve ==zero or multiple== system call
- Why use API?
- ++Simplicity++ (方便)
- ++Portability++ (可移植性)
- 不用經過interface
- ++Efficiency++ (效率)
## System calls vs. Application Programmming interface (API)
## System design Structure
- Goals
- **User goals**
- easy to use、learn
- **System goals**
- easy to design、implement(實行)、maintain(維持)
### OS Architecture
#### *Simple structure*
- 早期的structure
- e.g. MS-DOS
- Pros : simple
- cons : poorly structured. No protection.
- 
#### *Monolith*
- 開始分 kernel mode 和 user mode
- e.g. UNIX
- Pros : efficient
- Cons : not scalable
#### *Layered*
- 概念好但不存在，因為完全分層設計困難
- Pros : more structured, easy to debug and to scale
- Cons : difficult to comply with, very hard to define layers
- 
#### *Modules*
- Most modern operating systems implement kernel modules
- e.g. linux.
- Overall, similar to layers but with more flexible.
#### *Microkernel*
- 核心功能能省則省，把很多功能都放到核外
- e.g. Mach (Mac OS X)
- Pros : Robustness(堅固性), Scalability, and Security
- Cons : inefficient. Because of message passing.
#### *Hybrid Systems* *(混合系統)*
- Most OSes today do not strictly adhere to one architecture, but are hybrids of several.
- e.g. iOS, Android
## Virtual Machine (emulator仿真器)
- ==Multiple different== OSes running simultaneously on the same physical hardware
- Cloud computing (雲端計算)
- Protection of system resources
- Solve system compatibility problems
- e.g. VMware, Java Virtual Machine
- 
<!-- ch3-->
# Ch.3 Process
### Process
- A Program in exection
#### Process vs. Program
:::success
*Process*
- **active** entity: a program in execution in memory
:::
:::warning
*Program*
- **passive** entity: a file stored in disk
:::
- Process includes:
- **Text section**
- Code segment
- **Data section**
- global variables
- **Stack**
- temporary local variables and functions
- **Heap**
- dynamic allocated variables or classes(ex. pointer,malloc...)
- 
## Process state (State Transition Diagram)
- Five state
- *New*
- create process
- *Ready*
- Process load into memory
- put in Ready **queue**
- *Running*
- cpu get process and running
- *waiting*
- put into wait **queue** ==(not Ready queue)==
- e.g. I/O-complete
- *Terminated* *(已終止)*
- 正常 or 不正常 結束工作
- 
- ==Only one process== is running on any processor at any instant
- 反之 many processes may be ready or waiting
## Process Control Block
- OS 管理 Process，會把這個 ==Block== 丟到 kernel memory area (wait or ready queue)
- **Process number (ID)**
- unique
- **Process state**
- 行為
- **Program counter**
- address (位址)
- **CPU registers**
- value
- **CPU scheduling information**
- e.g. 優先權值, 在ready queue中的PCB指標
- **Memory-management information**
- e.g. Base/limit registers (很後面會說)
- **I/O status information**
- 未完成的I/O request，在I/O queue中的等待編號
- **Accounting information**
- e.g. 用了多少CPU time, 使用CPU的Max time, Quantum
### Threads (ch.4)
- 暫略
## Process Scheduling
### Scheduling Queue
- Job queue (**New State**)
- set of all processes in the system
- Ready queue (**Ready State**)
- set of all processes residing in main memory, ready and waiting to execute
- Device queue (**Wait State**)
- set of processes waiting for an I/O device
- 
### Schedulers
- *short-term scheduler*
- must very quickly swap one process out of the CPU
- <font color="#f00">Ready state → Run state</font>
- 可以想成決定CPU要執行哪個process的scheduler(cpu side)
- *long-term scheduler*
- 從 job queue 挑出 job，load 到 memory (ready queue)
- 決定哪個或多少process要被放進memory裡(user side)
- <font color="#f00">New state → Ready state</font>
- *medium-term scheduler*
- improve process mix, free up memory
- 常用於 timer-share system (VM)
- 所有 system 都有這個 Scheduler
- 決定哪個process要被swap近disk或者從disk swap出memory
- <font color="#f00">Ready state → Wait state</font>
|Name |short-term|long-term |medium-term|
|-----|--------|-------- |--------|
|頻率|高 |低 |中|
|multiprogramming 控制 |X |O|O|
|CPU & I/O 比例控制 |X |O|O|
### Context Switch
- 當 CPU 要從執行中的 process 切換到 另一個 process 時，kernel 必須保存 process status (state-save)，並且要 load new process status，做完之後再 ==state-restore (狀態恢復)==
- 
- How to improve speed *Context Switch*?
- 提高 memory speed
- add number registers
- special instructions to save/load register
- ==multiple sets of registers==
::: info
- user process and system are different set
- 只要改變 pointer
:::
## Operations on Processes
### Process Creation
- 過程中會產生 Parent and Child
- Parent vs. Child
- execution
- concurrently (同時)
- Parent ==waits until children terminate==
- address space
- Child duplicate (複製) of parent (相同)
- Child has a program loaded into it (不同)
### *fork*
- ++目的++: Create a new (child) process
- 2種情況
- 失敗 (大部份因資源不足)
- return value < 0 to parent and system
- 成功
- value = 0 to child process
- value > 0 to parent process (this value is child process ID)
### 補充指令
#### *execlp*
- ++目的++: Load a new binary file and destroying the old code
#### *wait*
- ++目的++: waits for one of its child processes to complete
### Process Termination
- exit() is called
- All resources of process are ==deallocated== (釋放)
### 補充指令
#### *abort*
- ++目的++: terminate execution of PID
::: danger
- killing (exiting) parent >> killing (exiting) all its children
:::
## Interprocess Communication
- a set of methods for the exchange of data
- Purposes
- information sharing
- computation speedup (not always true...)
- modularity
### Methods
### Shared-Memory
- To synchronize a producer and a consumer via shared memory
- Use memory address to access data
- Buffer as a circular array
- next free
- *in*
- first available
- *out*
- empty
- *in = out*
- full
- *(in+1) % B = out*
- 不 +1 的話，full 也會是 in = out
```
/*producer*/
while (1) {
while (((in + 1) % BUFFER_SIZE) == out)
; //wait if buffer is full
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
/*consumer*/
while (1) {
while (in == out); //wait if buffer is empty
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}
```
### Message passing
- communication link must be established
- send and receive
- three problem to solve
- Direct or indirect communication ( naming ) (直接問題)
- direct communication
- one-to-one link
- Indirect communication
- Multiple processes can share the same mailbox
- Only one process can read any given message in a mailbox
- Synchronous or asynchronous communication (同步問題)
- Blocking send
- sender is blocked until the message is received by receiver or by the mailbox
- Nonblocking send
- sender sends the message and resumes operation
- Blocking receive
- receiver is blocked until the message is available
- Nonblocking receive
- receiver receives a valid message or a null
- Automatic or explicit buffering. (緩衝問題)
- Zero capacity
- blocking send/receive
- Bounded capacity
- if full, sender will be block
- Unbounded capacity
- never block
- 
## Communication in Client-Server Systems
### Sockets
- A socket is identified by a concatenation of IP address and port number
- Communication consists between a pair of sockets
- 
### Remote Procedure Calls (RPC)
- 遠端上的 procedure
- Implementation involves ==stubs== on either end of the connection
- 
<!-- ch4-->
# Ch.4 Thread
### Thread
- Process 是 Thread 的容器
- CPU 初始化時產生
- thread ID
- program counter
- a stack
- a set of registers
#### Process vs. Thread
1. 一個 Process 會同時存在多個 Thread。
2. 一個 Process 底下的 Thread 共享資源，如記憶體、全域變數 (Global Variable) 等，不同的 Process 則否。
3. 同一個 Process 內的 Thread 使用相同的 Memory Space，==但這些 Thread 各自擁有其 Stack==。換句話說，Thread 能透過 reference 存取到相同的 Object，但是 local variable 各自獨立。
4. 作業系統 (OS) 會根據 Thread 的優先權以及使用過的 CPU 時間，在不同的 Thread 作切換，讓各個 Thread 都有執行的機會。
### Motivation
- web browser
- web server
- RPC server
- 
### Benefits of Multithreading
- ***Responsiveness***
- 當一個 thread 執行的時候，其他 thread 會放慢或是 block
- ***Resource sharing***
- performed simultaneously in a single address space.
- ***Economy***
- Creating and managing threads ( and context switches between them ) is much faster than performing the same tasks for processes.
- ***Scalability (Utilization of multiprocessor architectures)*** (可擴展性)
- A single threaded process can only run on one CPU, no matter how many may be available, whereas the execution of a multi-threaded application may be split amongst available processors.
## Multicore Programming
- 多核心
- pressure on system designers (設計困難)
- ***Identifying tasks (dividing activity)***
- 分配、分工
- ***Balance***
- 不在瑣碎的任務上浪費時間
::: warning
- Amdahl's law
- $N: processing\ core$
- $S: portion\ of\ the\ application$
- speedup $\leq$ $\frac{1}{S\ +\ \frac{1\ -\ S}{N}}$
- maximum speed up = $\frac{1}{S}$ ps.*(感覺會考)*
:::
- ***Data splitting***
- 防止 Thread 相互干擾
- ***Data dependency***
- 同步以確保資料正確
- ***Testing and debugging***
## Model
### User Model vs. KernelModel
- User Model
- done by user-level threads library ==without kernel support==
- e.g. POSIC, Win32, Java
- OS Model
- supported by the kernel (OS)
- e.g. Linux, Windows 2000, Java
## Multithreading Model
### Many-to-One (多對一)
- 優
- it is efficient
- do by user
- 缺
- will block if a thread makes a blocking system call
- multiple threads are unable to run in parallel on multiprocessors
- 
### One-to-One (ㄧ對一)
- 優
- More concurrency
- 缺
- Creating a thread requires creating the corresponding kernel thread
- 
### Many-to-Many (多對一)
- 優
- can run in parallel on a multiprocessor
- When a thread performs a blocking call, the kernel can ==<font color="#f00">schedule</font>== another thread for execution.
- 
## Thread libraries
- 屬於 Shared-Memory Programming
### Pthread (可以理解為一個 標準化的 API)
- POSIX (<font color="#f00">P</font>otable <font color="#f00">O</font>perating <font color="#f00">S</font>ystem <font color="#f00">I</font>nterface)
- ==standard== is specified for portability across Unix-like systems
- Pthread is the implementation of POSIX standard for thread
#### window Thread
- Similar to Pthreads
#### java Thread
- ALL Java programs use Threads
- single-threaded ones.
## Implicit Threading
### Thread Pool
- for await work (不用每次都 create 一個 Thread)
- faster to service a request
- ==need control resource size==
## Thread Issue
### fork() and exec() system calls
- If the new process execs right away, there is no need to copy all the other threads. Overwise, If it doesn't, then the entire process should be copied.
- OS provide ==multiple versions of the fork== call for this purpose.
### Signal Handling
- There are four major options:
- Deliver the signal to the thread to which the ==signal applies.==
- Deliver the signal to ==every thread== in the process.
- Deliver the signal to ==certain threads== in the process.
- Assign a specific thread to ==receive all signals== in a process.
### Thread Cancellation
- Asynchronous Cancellation (非同步)
- 立即 Cancel thread (有可能還在run)
- 可能造成資料不同步的問題
- Deferred Cancellation (延遲)
- default 預設選項
- Check at Cancellation points to cancel
### Thread-Local Storage
- 大部份的 Thread 都是共享 data
### Scheduler Activations
- Many implementations of threads provide a ==virtual processor== as an interface between the user thread and the kernel thread
- 這個 virtual processor 稱為 Lightweight Process (LWP) (~~懶挖屁~~)
- 
::: danger
- The kernel communicates to the user-level thread library when certain events occur ( such as a thread about to block ) via an **upcall**, which is handled in the thread library by an **upcall handler**.
- The upcall also provides a new LWP for the upcall handler to run on, which it can then use to reschedule the user thread that is about to become blocked. The OS will also issue upcalls when a thread becomes unblocked, so the thread library can make appropriate adjustments.
:::
<!-- ch5-->
# Ch.5 CPU scheduling
## Basic Concepts
- CPU-I/O burst cycle: Process execution consists of a cycle of CPU execution and I/O wait
- Generally, there is a large number of short CPU bursts, and a small number of long CPU bursts
- I/O-bound program
- many short CPU bursts
- CPU-bound
- few long CPU bursts
### CPU Scheduler
- Selects from ready queue to execute (i.e. allocates a CPU for the selected process)
### Preemptive vs. Non-preemptive
- CPU scheduling decisions may take place when a process:
- ==Switches from running to waiting state==
- Switches from running to ready state
- Switches from waiting to ready
- ==Terminates==
- *<font color="#f00">Non-preemptive</font> scheduling*(不會打斷CPU burst):
- Scheduling under 1 and 4 (no choice in terms of scheduling)
- The process keeps the CPU until it is terminated or switched to the waiting state
- *<font color="#f00">Preemptive</font> scheduling*(會打斷CPU burst):
- Scheduling under all cases
### Preemptive Issues
- Inconsistent state of shared data
- Require process synchronization (Chap6)
- incurs a cost associated with access to shared data
### Dispatcher (調度)
- <font color="#f00">Dispatcher</font> module gives control of the CPU to the process selected by scheduler
- switching context
- switching to user mode
- jumping to the proper location in the selected program
- <font color="#f00">Dispatch latency</font> – time it takes for the dispatcher to stop one process and start another running
- Scheduling time
- Interrupt re-enabling time
- Context switch time
## Scheduling Algorithms
### Scheduling Criteria
- *CPU utilization* (使用率)
- 讓CPU盡量保持忙碌
- *Throughput* (平均完成量->效能)
- 在單位時間之內能夠完成的工作量
- *Turnaround time* (single job執行完所需的時間)
- 對每一個process，從他進入到完成所需要花費的時間。越短越好
- *Waiting time* (所有burst執行完後，有多少時間是在waiting)
- 被Scheduing load裡面準備要用 **ready queue** 得時間開始算，到執行結束的時間。越短越好
- *Response time* (submit 到第一個burst執行的時間)
- 在time sharing的環境中，有一個request過來，等多少時間可以Response回去的間隔。
### Algorithms
#### FCFS Scheduling
- ***First in First out***
- Process (Burst Time) in arriving order:
P2 (3), P3 (3), P1 (24)
- The Gantt Chart of the schedule
- Waitingtime:P1=6, P2=0, P3=3
- Average Waiting Time (AWT): (6+0+3) / 3 = 3
#### Shortest-Job-First (SJF) Scheduling
- Associate with each process the length of its next CPU burst
- <font color="#f00">A process with shortest burst length gets the CPU first</font>
- <font color="#f00">SJF provides the minimum average waiting time (optimal!)</font>
- Two schemes
- <font color="#f00">Non-preemptive</font>
- once CPU given to a process, it cannot be preempted until its completion
- <font color="#f00">Preemptive</font>
- if a new process arrives with shorter burst
length, preemption happens
- 
- 
- ==Approximate Shortest-Job-First (SJF)==
- $\tau_{n+1} = \alpha*t_n+(1-\alpha)*\tau_n$
- $\alpha$ 任意
- 課本舉例 $\alpha = \frac{1}{2}$
#### Priority Scheduling
- The CPU is allocated to the highest priority process
- issue: starvation
- low priority processes never execute
- Solution: aging
- as time progresses increase the priority of processes (隔一段時間增加 priority)
#### Round-Robin (RR) Scheduling
- Each process gets a small unit of CPU time ==(time quantum, TQ)==
- After TQ elapsed, process is preempted and added to the end of the ready queue
#### Multilevel Queue Scheduling
- 不同的 Queue run 不同的 Scheduling Algorithms
- ==cannot switch from queue to queue==
- 
#### Multilevel Feedback Queue Scheduling
- A process can move between the various queues; <font color="#f00">aging</font> can be implemented
## Multi-Processor Scheduling
### Asymmetric multiprocessing
- 只有一個處理器存取系統data架構，能緩解共享data的需要。
### Symmetric multiprocessing (SMP)
- 每個處理器由自己做scheduling，且所有行程在共同的ready queue內，或每個ready queue有自己的private queue。
### <font color="blue">Problem 1:</font> Processor affinity
- process 想儘量長時間運行在某個指定的CPU上 ，且不被轉移至其他CPU 的傾向性。
- soft affinity:
- possible to migrate between processors
- hard affinity:
- not to migrate to other processor
### <font color="blue">Problem 2:</font> Load-balancing
- 讓工作量保持平均分配
- Push migration (推工作):
- move (push) processes from overloaded to idle or less-busy processor
- Pull migration (拉工作):
- idle processor pulls a waiting task from a busy processor
- <font color="red">Load balancing often 抵銷 the benefits of processor affinity</font>
### NUMA
- 把系統切成數個節點 (node)，每個 CPU 及 memory 就位在某一個節點上，當處理器存取同一個節點的記憶體時，可以有較高的存取速度；而存取其他節點的記憶體時，就需要透過節點間的資料傳遞，會耗費較多時間
### Multicore Processors
- 在同一個物理晶片上，放置多個處理器內核，這是目前的一種趨勢
- 更快速而且低耗能
- 當memory被取回時，利用memory停滯時間，取得其他行程中的progress
<!-- ch6-->
# Ch.6 Process Synchronization
## Background
- ==同時access shared data== 可能導致data的不一致性
- 維持data的一致性，需要有機制去確保==合作的process的執行的順序==
### Race Condition
- 多個process同時access和manipulate（操作）shared data
- 最後shared data的值會由最後一個執行的process所決定
- 通常被形容是==critical section problem==
#### 預防
- concurrent processes需要被同步化
- 在single-processor machine, 我們可以disable interrupt或使用non-preemptive CPU scheduling
<!-- - Disable Interrupt
- Def： 為確保共享變數之存取敘述執行時不受任何中斷干擾，可以automically executed，可以採序如下方式
```
Disable Interrupt
執行敘述
Enable Interrupt
```
- 優點：simple，易於實施，適用於uniprocessor(單一CPU)環境
- 缺點：不適用於Multiprocessors環境，因為效益很差
- 說明：process需發出Disable Interrupt請求給各其它CPUs，並且必須等到所有其它CPUs回覆"Interrupt已Disable"之回應訊息，才可以執行敘述同時，完成後，再發訊息通知其它CPUs Enable Interrupt
- Critical Section Design
- 目的：提供對共享變數之存取的互斥控制，確保資料的正確性 -->
## Critical Section
### The Critical-Section Problem
- Purpose: 一個protocol以讓processes去合作
- Problem description:
- <font color="red">N processes</font> are competing to use some <font color="red">shared data</font>
- 每個process有一個==code segment==，稱為==critical section==，在這裡shared data被存取
- 需要確保當有一個行程正在執行他的critical section，其他的行程不允許執行他自己的CS —> ==<font color="red">mutually exclusive</font>==
```c++
do {
/*entry section*/ // get entry permission
critical section // modify shared data
/*exit section*/ // release entry permission
remainder section
} while (1);
```
### Critical Section Requirements
- <font color="blue">Mutual Exclusion:</font> 有process在執行CS時，其他process不能執行CS
- <font color="blue">Progress:</font> 沒有其他process在執行CS時，要執行的process的CS不能被擋住
- <font color="blue">Bounded Waiting:</font> process的執行時間必須有限制，不能讓一個process一直占用CS
### Peterson’s Solution for Two Processes
- Shared variables
- int <font color="red">turn</font>; //initially turn = 0
- <font color="red">turn = i ⇒ Pi can enter its critical section</font>(當 turn = i，Pi可以進入critical section)
- boolean <font color="red">flag</font>[2]; //initially flag [0] = flag [1] = false
- <font color="red">flag [i] = true ⇒ Pi ready to enter its critical section</font> (確認Pi想要進critical section)
:::info
- Critical Section 要怎麼包?
1. 越小越好 (全部都包進去可能會導致process被lock)
2. 不要包到不會出現Race condition的程式碼 (包太多效率降低)
:::
### Bakery Algorithm (n processes)
- 每個行程在進入他的CS之前，會收到一個號碼（抽號碼牌）
- 有最小號碼的行程先執行他的CS
- 產生號碼的方法會產生non-decreasing order的序列
- 如果兩個行程的號碼一樣，比較pid，pid小的先
## Pthread Lock/Mutex Routines(課本講很少 不知道要不要考 要考之後補)
## Hardware Support
- Atomic TestAndSet()
- 不會被中斷
``` C++
boolean TestAndSet ( bool &lock) {
bool value = lock ;
lock = TRUE ;
return value ;
}
```
### solution code:
```C++
do { // P0
while (TestAndSet (lock) ) ;
critical section
lock = FALSE;
remainder section
} while (1) ;
do { // P1
while (TestAndSet (lock) ) ;
critical section
lock = FALSE;
remainder section
} while (1) ;
```
- lock是共享的變數，當執行test_and_set(&lock)，會將lock變數記憶體的位置傳入test_and_set()這時會被上鎖(lock = TRUE)，等執行完後lock才會被解鎖
- Atomic compare_and_swap()
- 不可被中斷
- def:
```C++
int compare_and_swap(int *value,int expected, int new_value)
{
int temp = *value;
if(*value == expexted)
*value = new_value;
return temp;
}
```
### solution code:
```C++
do{
while (compare_and_swap(&lock, 0, 1) != 0);
critical section
lock = 0;
remainder section
}while(true)
```
- lock是共享變數，初始值為0 (0代表不能進去，1代表可以進去)，當執行compare_and_swap(&lock , 0 , 1)，會去比對lock跟expected的值，如果相同就會把值做交換
## Mutex Locks (Spinlock)
- OS的設計者會建立software tools去解決CS的問題。
- software tools包含mutex lock跟spinlock。
- 最簡單的方法是mutex lock。
- 會使用兩種方法來取得與釋放lock：
- acquire()：取得lock
```C++
acquire ()
{
while(!available)
/*busy wait*/
available = false
}
```
- release()：釋放lock
```C++
release ()
{
available = true
}
```
- acquire()與release()必須是atomic，且透過硬體指令執行。
* busy waiting：如果以上兩種方法沒有取到lock的話，將會處於一種「busy waiting」的狀態，一直在等待，直到可以進入CS並完成後，會release lock，所以此lock會被稱作為「Spinlock」，由busy waiting的方式進行。
### solution of CS using Mutex Locks (Spinlock)
```C++
while (true)
{
/*acquire lock*/
Critical section
/*release lock*/
Remainder section
}
```
## Semaphores
### Semaphores
- A <font color ="blue">tool</font> to generalize the synchronization problem
- a record of <font color ="red">how many units</font> of a particular resource are available(<font color ="blue">Semphores</font>是一個介於0到指定最大值的整數變數，代表某樣resource的數量)
- If #record = 1 -> <font color ="red">binary semaphore, mutex lock</font>
- If #record > 1 -> <font color ="red">counting semaphore</font>
- accessed only through 2 atomic ops: <font color ="red">wait</font> & <font color ="red">signal</font>
- wait()：需要一個resource
- signal()：執行完了，free一個resource
- 當執行完wait()則減1，而執行完signal()則加1。當變數等於0時，就要等到執行完signal()才能再執行wait()。
- n-Process Critical Section Problem
### Non-busy waiting Implementation
- Semaphore is <font color ="red">data struct with a queue</font> (Semphore 變成一個queue而不是一個變數)
- may use any queuing strategy (FIFO, FILO, etc)
- wait() and signal()
- use system calls: <font color ="red">sleep() and wakeup()</font>
- must be executed <font color ="red">atomically</font>
- 不會浪費CPU資源，但是因為call system calls，因此執行速度會變很慢
### Semaphore with Critical Section
- 因為S.value可能有race condition，所以須結合critical section
:::danger
sleep() & wakeup() 不能被包進critical section
:::
### Deadlocks & Starvation
- <font color="blue">Deadlocks</font>: 兩個process在互相等待被對方占住的資源。
- <font color="blue">Starvation</font>: 無限期的blocking；有一個行程可能永遠不會從semaphore wating queue中移出來。
- <font color="blue">Priority Inversion</font>：是一個排程問題，也就是低優先權的process佔住了高優先權process的資源，如果想要解決這個問題的話，就要透過==priority-inheritance protocol==解決。
## Monitors
- 提供方便且有效率的機制給process synchronization使用。
- 有些系統不支持。
- ==**確保只能有一個process可以在monitor內執行**==。
- 不能解決所有的synchronization問題，但這已經是較為複雜的方法。
### Condition Variables
- condition x, y;
- 有兩種operations允許condition variables：
- x.wait()：一個process要invoke一個operation時，要一直等到x.singal()可以使用，不然就是suspended。
- x.signal()：如果任何的x.wait()被invoked的話，其中一個process就會重新開始。
- 但如果沒有任何x.wait()的話，對variable就不會有任何影響。
### Condition Variables Choices
- 如果process P invokes x.wait()且process Q在x.wait()內暫停的話：
- Ｐ和Ｑ不可以同時平行執行。如果Ｑ重新開始的話，Ｐ就必須要等待。
- operation 包含：
- ==Signal and wait==：Ｐ必須等待Ｑ，直到Ｑ離開monitor或是等待其他condition。
- ==Signal and continue==：Ｑ必須等待Ｐ，直到Ｐ離開monitor或是等待其他的condition。
<!-- ch7-->
# Ch.7 Classical Problems of Synchronization
## Bounded-Buffer (Producer-Consumer) Problem
- 有一個pool，其有n個buffer，每個buffer可以hold一個item
- Producer
- 取一個空的buffer
- 放置一個item進buffer
- 如果沒有空的buffer，則等待
- Consumer
- 取一個buffer並拿出item
- 將buffer放到free pool
- 如果所有的buffers都空的，則等待
## Reader-Writers Problem
- 一組shared的data objects
- A group of processes
- reader processes (read shared objects)
- writer processes (update shared objects)
- a writer process has ==exclusive access== to a shared object
### Problem
- first RW problem
- 在writer做更新時(exclusive access)，不能有其他reader在read
- second RW problem
- 當writer準備好了，只要shared data一被釋放，他馬上就可以access
- writer的==priority==高過於reader
- 因此當writer ready，就沒有reader可以開始讀
- ==不能preemtive==，保證資料完整性
```C++
/* writer */
Writer(){
while(TRUE){
wait(wrt);
/* Writer Code */
signal(wrt);
}
}
/* reader */
Reader(){
while(TRUE){
wait(mutex);
readcount++;
if(readcount == 1) //第一個read
wait(wrt);
signal(mutex);
. . .
/* Reader Code */
. . .
wait(mutex);
readcount--;
if(readcount == 0)
signal(wrt);
signal(mutex);
}
}
```
- Writer可能會有==starvation problem==
- 如果有一個reader在讀，後來又來一個reader看到已經有人在讀，所以又進去了，所以writer一直等
## Dining-Philosopher Problem
- 五個人坐在五張椅子上，有五隻筷子
- 一個人不是在thinking就是在eating
- thinking: 與其他四人沒有互動
- eating: 需要兩隻筷子在手上
一次只拿一隻筷子
- done eating: 放下兩隻筷子
- deadlock problem
- one chopstick as one semaphore
- 需要好幾個資源才能做一件事
- starvation problem
### Dining Philosophers Example
#### monitor type
```C++
monitor dp {
enum {thinking, hungry, eating} state[5]; //current state
condition self[5]; //delay eating if can’t obtain chopsticks
void pickup(int i) {
state[i] = hungry;
test(i); // try to eat
if (state[i] != eating)
// 放到自己的waiting queue
// wait to eat
self[i].wait();
}
void putdown(int i) {
state[i] = thinking;
// check if neighbors are waiting to eat
test((i+4) % 5);
test((i+1) % 5);
}
void test(int i) {
if ( (state[(i + 4) % 5] != eating) && (state[(i + 1) % 5] != eating)
&& (state[i] == hungry) ) {
//No neighbors are eating and Pi is hungry
state[i] = eating;
self[i].signal(); // If Pi is suspended, resume it
// If Pi is not suspended, no effect
}
}
void init() {
for (int i = 0; i < 5; i++)
state[i] = thinking;
}
}
```
### Pthread Lock/Mutex Routines
#### use mutex
- declare：pthread_mutex_t
- initialize：pthread_mutex_init()
- destroy：pthread_mutex_destory()
- CS be protected：pthread_mutex_lock() and pthread_mutex_unlock()
```c
#include “pthread.h”
pthread_mutex mutex;
pthread_mutex_init(&mutex, NULL);
pthread_mutex_lock(&mutex); // enter critical section
/* Critical Section; */
pthread_mutex_unlock(&mutex);// leave critical section
pthread_mutex_destory(&mutex);
```
### Condition Variables (CV)
- CV代表一些條件讓thread可以
- 等待直到條件發生
- 通知其他正在等待的thread，條件已經發生了
- operations on condition variables
- wait()
- Block直到另一個thread calls signal() or broadcast() on the CV
- signal()
- Wake up one thread waiting on the CV
- broadcast()
- Wake up all threads waiting on the CV
```c
pthread_cond_t // data type
pthread_cond_init ()// initialize
pthread_cond_wait (&theCV, &somelock)
pthread_cond_signal (&theCV)
pthread_cond_broadcast (&theCV)
```
### Synchronization in java (別人做的)
### Synchronization Examples
- Solaris
- Windows (p.318 or 7.2.1)
- Linux (p.320 or 7.2.2)
- Pthreads
<!-- ch8-->
# Ch.8 Deadlock
<!-- ch9-->
# Ch.9 Memory
## background
- ==主記憶體==和==暫存器==為CPU唯一能直接存取的地方
- process在disk等待被載入進memory和被執行
- 多支program被讀到memory能增進資源使用率和反應時間
- 一個process能在執行期間在disk與memory之間移動
## Base and Limit Registers(Hardware Support)
- 一個logic address space是由base和limit register所限定的。
- **Base：process的==起始位置==。**
- **Limit register：process的==尾端位置==。**
- CPU會負責以每個process ID來檢查每個process是否有在自己的位置上。
## Address Binding
### Compile time
- **symbolic code** 轉成 **absolute code（絕對地址）**
- 如果已經知道記憶體的位置，便產生==absolute code==，但有更改位置的話，code也需要==recompile==。
### Load time
- **symbolic code** 轉成 **relocatable code**
- compile time還不知道，只給個==變數（BASE）==，load time才給實際的值，其他是==相對BASE的地址==
- 如果記憶體並不知道位置的話，就產生relocatable code。
### Executin time (Run time)
- compiler將symbolic code轉成==logical-address （i.e. virtual-address） code==
- 使用這種方式需要特別的硬體（ex: MMU）
- 如果process在執行時，記憶體segment被搬移到另一個segment的話，連接就會延遲到這時才開始。
:::danger
**Memory-Management Unit (MMU)**
- 虛擬位址對應到實體位址的硬體device
- 每個由user process產生的logical-addr.加上relocation register產生實體地址
:::
## Logical vs. Physical Address Space
- Logical (virtual) addr.==由CPU產生==
- Physical addr
- 被memory module看見
- compile-time & load-time address binding
- logical addr = physical addr
- Execution-time address binding
- logical addr ≠ physical addr
- user program永遠使用logical addr
- **不會看見physical addr**
## loading and linking
### Static linking(靜態連接)
- compile的時候將library加入程式碼，libraries被loader結合進program在memory的image。
- 浪費記憶體、執行比較快
### Dynamic linking(動態連接)
- linking推遲至execution time才做
- 只會有一份==lib code==，能被共享
- A ==stub== is included in the program in-memory image for each lib reference
- stub call --> 找referred lib是否在memory，沒有的話，Load進來 --> 將其位址替換掉，之後就不用經過stub (relocation)
- 需要OS support
- loader載入user program時，將有使用到系統函式庫的位置以stub標記。當行程執行到系統函式庫，判斷該函式在不在記憶體，不在的話，將函式載入，並且將形成呼叫處改成函式位址。
## Contiguous(連續) Memory Allocation
### fixed-partition allocation
- 每個process載入one partition of fixed-size
- ==multi-programming==的程度被partition的數量所限
### Variable-size partition（Multiple Partition）
- Hole : 一塊連續記憶體
- 多個不同大小的hole分散在記憶體
- 當一個process抵達，他會被分配在大小足夠容納他的hole中
- OS維護in-use, free hole的資訊
- 一個被釋放的hole能與其他的hole做合併，形成更大的hole
### Dynamic Storage Allocation Problem
- 問題：如何從一個list的hole滿足要求size n?
- 解法：
- **First-fit**：分配在第一個合適的hole
- **Best-fit**：分配在最小且合適的hole（必須整個list都尋找過）
- **Worst-fit**：分配在最大的hole（必須整個list都尋找過）
- First-fit和Best-fit比Worst-fit在速度與資源的使用好
## Fragmentation（碎裂）
### External fragmentation
- 被分配的記憶體比請求的記憶體要稍微再大一些而發生fragmentation
- 發生在variable-size allocation
- 解法：
- ==compaction（聚集）==
- Shuffle memory將空閒的hole聚集在一起合併(at execution time)
- 透過改變base register
- paging or segmentation變成不連續
### Internal fragmentation
- 由於memory的partition大小已經被事先切好，所以可能會造成原先留的空間，沒有被使用到的部分被閒置
- 發生在fixed-partition allocation
## Non-Contiguous Memory Allocation — Paging
1. 將physical memory分成==fixed-size==的blocks稱為==frame==
2. 將logical address space分成==一樣size==稱==page==
3. 為了要run一個有N個pages的program，需要找N個free frames和載入program
4. keep track of free frames
5. 建立page table將logical轉換成physical addresses
### 優缺
1. 允許physical-address space of a process可以不連續
2. 避免external fragmentation
3. 無法避免internal fragmentation
4. 提供 共享 memory/pages
:::info
**Page table**
- 每個entry存在physical memory的base address of a page
- 每一個process都會有一個page table由OS所維護
- 只會包含process擁有的page
- program不能access不是他的空間
:::
### Address Translation Scheme
#### Logical address被分成兩部分
- page number（p）
- page table的index
- n bits表示一個process能allocate至多$2^N$個pages
(所需$2^N * pagesize$的memory大小)
- page table的index
- 與base address結合定義physical memory address
- n bits表示page size為$2^N$
### logical addr = page * pagesize + page offset
### Physical addr = frame * pagesize + page offset
#### example
- page的數量決定於一個process的logical memory大小
- frame的數量決定於physical memory的大小
#### Page / Frame Size
- page（frame） size是由硬體所決定
- 越大的page size越容易造成Internal fragmentation
- 增加的好處
- memory, process, dataset能變更大
- 更好的I/O（during page fault）
- page table變小
## Implementation of Page Table
- 方法 1
- 使用 register 保存分頁表每個項目的內容
- 優點 : 速度快
- 缺點 : 僅適用於 page table 大小較小的情況，太大的 page table 則不適用。
- 方法 2：
- page table 保存在 memory 中，OS 利用 ==PTBR(Page Table Base Register)== 記錄起始位址，==PRLR(Page-table length register)== 紀錄 page table 的大小
- 優點 : 適用於 page table size 較大之情況
- 缺點 : 速度慢。因為需要存取兩次 memory。(一次用於存取 page table、一次用於真正的資料存取)
- 方法 3：
- 使用 ==TLB(Transaction Lookaside Buffer)== 來保存部份常用的 page table
- :::warning
Translation Look-aside Buffer（TLB）
- 用==Associative Memory==所組成，是硬體，能同時access，且entry數是有限的
- 一些TLBs在每個TLB entry中，儲存==address-space identifies(ASIDs)==，且每個process都有獨特的識別碼去提供address-space保護process。
:::
- 流程如下：
1. 首先，到 TLB 查詢有無對應的 Page Number 存在。
2. 若 Hit，則輸出 Frame 的起始位址，只存取記憶體 1 次。
3. 若 Miss，則到記憶體中取出 page table 查詢，存取記憶體 2 次。
#### 簡單例題
### Memory Protection
- 每個page都有一個==protection bit==表示"唯讀" 或 “可讀寫”
- valid-invalid bit
- valid：表page存在physical memory、page屬於該process記憶體中
- invalid：禁止process存取
- 隱藏問題：
- 沒有使用到的entry（浪費）
- 解決辦法：page table length register（PTLR）
- 為valid但是illegal
- 解決辦法：memory limit register限制存取的空間
### Shared Pages
- 允許多個process共享相同的Reentrant code（read only）, e.g：text editors, compilers, web servers
- 只有一份copy
- 多份virtual addr.對應到physical addr.
- Shared code在每一個process中必須保持在同一個logical address
## Structure of the Page Table
### Hierarchical Paging
- 將logical address space 化成多層 page tables（n-level page table）
### Hashed Page Table
- 適用於>32bit addr.
- virtual page number經過hash func.歸到某個entry
- 越大的hashed table，每個entry會有smaller chain
- entry包含 Virtual Page Number, Frame Number, Next
### Inverted Page Table
- 不會為每個process維護page table
- 維護frame table（entry：pid + page number）
- 減少存page table的memory，但增加access的時間，每次的access都要找table全部一遍
- 難支援shared memory / page
## Swapping
- 將process從memory ==swap out==至==backing store (disk)==，稍後又swap in memory繼續執行（不同於***context switch***）
- Backing store，獨立於file system，提供memory image直接的存取
- swap的目的：
- 釋放memory
- Roll out, roll in: 將低優先權的換出，換一個優先權高的進來
# Ch.10 Virtual memory
- 將user logical memory從physical memory分開出來
- 使應用程式==認為它擁有連續的可用的記憶體==
- 實際上，它被分隔成多個==實體記憶體碎片==，還有部分暫時儲存在==外部磁碟記憶體==上，在需要時進行資料交換
- ==logical addr. space==能大過於physical memory
- ==增加CPU的使用率==，有限的physical memory多塞點program，multi-programming的degree上升
- ==簡單programming==的工作，programmer不用管memory的限制
- 對於swap, load可有==更少的I/O負擔==，因為不用將整個program load進來
## Demand Paging
1. 一個page，當有需要的時候，才load到memory裏頭
- 減少I/O
- 減少對memory的需求，能有更多的user
2. 一個page被需要時機為，當有reference指到它
- invalid reference -> abort
- not in memory -> page fault
3. pure demand paging
- Start a process with no page
- 只有被需要才送到memory
4. prepaging
- 預測哪些page將被使用，將他們置換進來
- 避免pure demand paging一開始大量的page fault
#### 相關名詞
:::success
- **Swapper**（midterm scheduler）管理整個process
- **Pager**管理一個process中的各個page
- **Page Table**：valid-invalid bit （in or not in memory）
- **Secondary memory**（swap space, backing store）：==disk==
:::
## Page Fault
- page fault OS造成的；
- segmentation fault user造成的
### STEP
1. OS查看PCB所指到的page table
- Invalid reference -> abort
- not in memory -> continue
2. 找一個空的frame
3. 將page從disk swap進frame
4. 重設page table，valid bit = 1
5. 重新執行指令
## Demand Paging Performance
### Effective Access Time (EAT) = (1 – p) x ma + p x pft
- Parameter
- *p*：page fault rate
- *ma*：mem. access time
- *pft*：page fault time
- 存取時間會正比於page fault time（因為page fault time所花時間大）
- program通常都是locality的reference（access在附近的memory） —> 一個page fault會帶進4KB的memory content，降低page fault發生的機會
- page fault time的組成
- page-fault interrupt
- **read page from disk最耗時**
- restart process
## Copy-on-Write
- 最佳化demand paging
- 提高process creation的效率
1. parent和child process在記憶體能共用一個page
2. 只有在child要寫入資料時，才會複製一個page出來，放到free page
3. 提供一個pool來存放free page，如果需要free page時，按照==zero-fill-on-demand==分配。
## Page Replacement
- 發生page fault，但是沒有free frame時，需要置換
### 方法
1. swap out a process，清空所有它所佔有的frame
2. page replacement，找一個沒有在使用的frame，free掉它
（利用dirty bit減少transfer的負擔，只寫回有被更改過的frame）
:::warning
**解決page demand的問題**
- ==frame-allocation algorithm==：為每個process決定配給他多少個frame做使用
- ==page-replacement algorithm==：選擇哪個frame要被換掉
:::
### STEP
1. 在disk中找到需要的page
2. 找到free frame
- 有free frame，直接使用
- 沒有free frame，利用page replacement algorithm選一個victim frame (用dirty bit找)
3. 將需要的page讀進frame（swap in），並更新page/frame table
4. restart process
## Algorithms
### FIFO algorithm
- ==最舊的page==越先被換掉
- 
- Belady’s Anomaly：更大的allocated空間，page fault的次數卻沒有減少
### Optimal algorithm
- 選將來最久不會被使用的page換掉，需要future的資訊
- 實際上我們沒有future的資訊 (無法預測未來)
- 算是Stack Algorithm(First In, Last Out)
### LRU algorithm（Least Recently Used）
- 與optimal algorithm相近，但LRU是往前看
- 選最近最久沒被使用到的page換掉
#### 實作
1. Counter implementation
- page referenced：time stamp被複製到counter
- replacement：移除最老的counter
- 問題：counter可能overflow、移除的時候需要linear time
2. Stack implementation
- page referenced：被移到doubled-linked-list的top
- replacement：移除在bottom的page
- 
#### Second-Chance Algorithm
- 又稱為clock algorithm
- 以FIFO為基礎
- 如果在找 victim 時，找到的reference bit為1，會將reference bit改為0，給他一次機會，下次再找到他時，就會被交換掉。
- 
#### Enhanced Second-Chance Algorithm
- 加強版的演算法，多增加一個dirty bit來判斷。
- 以下有四種模式，越上方的越會先被交換掉：
- (reference bit , dirty bit)
(0,0) ->最近沒有被使用也沒有被修改
(0,1) ->最近沒有被使用，但有被修改
(1,0) ->最近有被使用，但沒被修改
(1,1) ->最近有被使用而且也有修改
### Counting Algorithms：
- 這種演算法很少用，他是計算被用到的次數來決定
1. LFU（least frequently used）：
- 將最少運用到的page交換掉
2. MFU（most frequently used）：
- 運用次數少的page可能才剛交換近來，所以交換已經運用次數多的，因為可能不會再用到它。
### Page-Buffering Algorithms：
- 當page被修改過後，一段時間未被使用，則將被修改的page移入磁碟內，dirty bit重設為0。然後使用一個free frame記錄是哪些page被修改過，當需要再用到時，可以直接取出重新使用。
## Frame Allocation
- 每個process需要最小的frame數目
### Fixed allocation
1. Equal allocation：
- 每個proces配到的frame數目一樣
2. Proportional allocation：
- 配置數目依據process的大小做成長
### Priority allocation
- dynamic
- 利用Proportional allocation基於優先權，而不是size
- 從優先權低的process拿走它的frame做替換
### Local allocation
- Process找frame替換時，只能找自己的frame。
### Global allocation
- process從全部的frame挑選做替換
- eg. 允許高優先權的process拿走低優先權的process的frame
- 好的performance，普遍使用
- 每個process的一個最小的frame數目應該被維護以避免Thrashing
## Trashing
- Trashing產生：
1. Frame不夠，頻繁發生page fault
2. Page replacement發生
3. 很快的frame又不夠用，又需要Page replacement (2 3之間會產生很多page fault)
4. 導致CPU使用效率低，因為process都在忙著swap in/out，CPU就空閒下來，這時CPU就會想提高程度，抓更多process進來工作。
### 解決方法
### Working-Set Model
- 預估各 process 在不同執行時期所需的 frame 數目，並依此提供足夠的 frame 以防止thrashing。
- 緣由：process 執行時對於 memory 的存取區域具 locality 性質。
- Temporal locality：Process目前所存取的記憶體區域過不久後會再度被存取，e.g. loop, subroutine, counter, stack.
- Spatial locality：process 目前所存取的記憶體區域其鄰近區域極有可能也會被存取，e.g. array, sequential code execution, global data area.
::: info
方法
- OS 設定一個 working set window size t，以 t 次記憶體存取中，所存取到的不同Page 之集合，此一集合稱為 working set。
- working set 中的 process 個數，稱為 ==working set size ($WSS_i$)==。
- 
:::
#### 狀況
1. D > m (thrashing) —> 中止process —> free掉所有他佔用的frame
2. D << m —> 提升degree of multiprogramming
## Page-fault frequency
- 直接測量與控制page fault rate以避免thrashing
- 為每個process建立upper bound與lower bound在一個理想的page fault rate
- 若page fault超過upper bound —>
- 配額外的frame給這個process
- 若沒有free frame，立即暫停process，free掉他占用的frame
- 若page fault低於lower bound —>
- 從該process移除frame（表不需要這麼多frame）
- launch新的process
### Memory Compression 不想做= =
Sign in with Wallet
Connect another wallet