Operating system

架構:

• PC OS提供以下功能:

1. Processing management
2. Memory management
3. File system
4. Networking
5. Security
6. User interface
7. Device driver

• 常見OS:

1. Multiprogramming System: 允許多個process同時執行, 提高CPU utilization
   Multiprogramming Degree: 等待執行的process數
   ref: https://ithelp.ithome.com.tw/articles/10205080
2. Time Sharing System: Multiprogramming System的一種, 資源共享.
3. Distributed System: 須符合兩個條件，硬體上每台電腦都是自主的，軟體上用戶將整個系統看做是一臺電腦
   ex: 閒置電腦提供計算, 透過網路傳輸資料
4. Real Time System:
   Hard: 工作必須在時間內完成, 否則就失效
   Soft: 高優先權的Process必須先於所有低優先權的Process完成
5. Clustered System: 共享store device, 集結CPU並透過LAN完成工作

ref:

OS - Ch1 作業系統簡介 與 常見系統類型

• Interrupt:

1. Stop process & save context
2. CPU根據interrupt ID -> look up interrupt vector -> get Interrupt Service Routine(ISR) address
3. Execute ISR
4. restore context
5. restart process

Interrupt flow

• Interrupt種類:

1. External: CPU外部周邊元件, ex: I/O complete, I/O device error
2. Internal: CPU內部, ex: debug, divide by 0, overflow
3. Software: 使用者程式需要OS提供服務 -> system call -> 對應ISR -> 回傳結果給使用者程式

Note: Trap = internal + software

• I/O

電腦架構:

電腦架構

1. 不同controller服務特定的裝置
2. CPU, I/O 可同時執行, 競爭記憶體, controller通常有buffer
3. Interrupt driven

• 運作方式:

1. Polling: I/O controller將data放在status register, CPU 週期性拿到data, 得知需要服務的裝置
2. Interrupt driven: I/O需要服務 -> interrupt 通知CPU
3. DMA(direct memory access): controller 可以直接在memory 傳輸data, 不需要CPU
   cycle stealing — DMA 向 CPU 竊用機器週期，而直接向記憶體存取資料
   note: DMA和CPU access同樣memory, DMA > CPU, 執行消耗小的先執行

• Synchronous vs Asynchronous

1. Synchronous: 一段時間只能有1個 I/O request
2. Asynchronous: 一段時間可以不只1個 I/O request, 要有一張表紀錄I/O 位址和使用狀況

• Privileged Instruction:

保護重要的資源，需要 Kernel mode 才能執行。Dual-Mode 需要硬體的額外支援，用一個 Mode Bit 記錄.
ex: I/O, modify memory related register, timer setting, 系統停止…

• System call:

via API rather than direct system call use(because of portability and simplicity issue)

Three most common APIs:

1. Win32 API for Windows
2. POSIX API for POSIX-based system(Linux, UNIX, Mac OS)
3. Java API for Java Virtual Machine(JVM)

System Call的參數如何傳遞給OS: 用一張表記在memory中, register 儲存這張表的位址

• Instruction type:

1. Privilege instruction：會進 trap 的指令
2. Sensitive instruction：修改到硬體的指令
3. Innocuous Instruction: Those that are not control or behavior sensitive

• Virtual machine:

優點: 方便測試, 可以同時跑好幾個OS

缺點: VM間溝通困難, 效率不佳

ref:

OS - Ch2 中斷、I/O、系統呼叫、OS 結構設計 和 虛擬機

• Process: progarm載入memory
• State

1. new
2. ready
3. running
4. waiting: 亦稱blocked, ex: wait I/O complete
5. terminated: finish

process state transition

Each process has an unique PID:

• memory 配置:

1. Stack: parameter of function, local var, caller’s return address. 遵守FILO
2. Heap: 動態配置
3. BSS: 未初始化的static var
4. Data: 初始化的static/global var
5. Text/code: binary image of process, 常數字串

• Context switch:

發生於多個processes分享同一個CPU資源, save old context, load new context
ex: 多工, 中斷…

1. Process control block(PCB): 紀錄process information的資料結構, 切換process時, 未做完的process資訊會存在PCB.
   OS 在 Process Scheduling Queue 中維護所有的 PCB

PCB

Process scheduling queue

1. Job queue: keep all processes in the system.
2. Ready queue: in main memory. Ready and wait to execute.
3. Devices queue: waiting for I/O device

• Scheduler

1. Long term scheduler(job scheduler): new -> ready
   a. 從job queue挑選適合的載入記憶體準備執行
   b. 可調控multi programming degree
2. Short term scheduler(CPU scheduler): ready -> running
   a. 從ready queue挑選priority最高的執行
   b. 執行頻率最高
3. Medium term scheduler: virtual memory
   a.當記憶體不足 + 其他process要載入記憶體執行
   scheduler挑選process swap out到磁碟 -> 記憶體夠 -> process swap in
   b.減少 Multiprogramming Degree

Note: I/O bound vs CPU bound
I/O bound: spend more time doing I/O, ex:等待輸入的程式
CPU bound: spend more time doing compute, ex: 壓縮程式

• 與process相關的system call:

1. fork(): 建立child process, code/date section內容均來自parent copy, 與parent占用不同memory.
2. exit(): 中止process
   return 0: 正常
   return -1: 不正常
3. execlp(): 載入特定的binary file讓process執行, process的code section為此binary code content
4. wait(): 暫停process

parent 等 child回傳後繼續

• Process termination:

1. child執行完, 結果回傳parent, 要求OS刪除自己(exit), OS回收resource
2. parent abort child process
3. parent比child先結束, child可能也終止或是由OS/ancestor 提供resource而存活

Note:

1. orphan: parent死了
2. zombie: parent睡了, child執行完了
3. fork vs vfork vs clone:
   fork(): 利用copy-on-write, 要有MMU, parent 和 child concurrent執行
   vfork(): child的call, stack, data都是parent的, parent和child不能concurrent執行
   vfork -> parent wait -> child exec() or exit() -> parent
   clone(參數): 按指定條件創建子行程，可決定哪些父子資源要共享，哪些要額外複製一份。

ref:

fork()、vfork()、clone()系統呼叫差異

• Inter process communication(IPC):

share memory & passing message

1. share memory: ring buffer
   問題: synchronize a producer and a consumer

2. passing message

a. Direct communication: 指出名子, send(P, msg), receive(Q, msg)
b. Indirect communication: 不是直接寄給其他 process 而是寄到他家信箱 (also referred to as ports)，每個 mailbox 有一個特殊 id，一次可以連多個 process 但只能寄給一個 process，系統會自動選一個寄，然後告訴寄件者收件者是誰

ref:

OS - Ch3 行程 Process

• Thread: 被包含在process內, 是OS能夠進行CPU運算的最小單位

Thread: OS分配CPU時間
Process: OS分配resource

Thread的內容: thread ID, thread state, program counter, register set, stack
Process內的thread共享:
1. code section: instruction
2. data section: global variable
3. OS resource: open files, signals

Code section + Data section = memory space, Address space, Heap memory ???

process有multi-thread的好處:
1. Responsiveness: even某個thread blocked, 其他thread還是可以執行

2. Resource sharing: code/data section, OS resource

3. Economy: thread is light-weight process(context switch速度: thread比process快5倍, 建立速度: thread比process快13倍)

4. Scalability: 可用多處理器架構

• Multi-thread:

1. User thread: user mode下, OS不知道有這些thread, OS不管理

優點: 產生、管理成本較低
缺點: 如果process thread發出鎖定system call + kernel是single thread則整個process被綁住 ???

常見user thread:
Pthread(POSIX thread)
Win32 thread
Java thread

2. Kernel thread: kernel mode下, OS管理
常見kernel thread:
Window XP/2000
Linux
Solaris
Tru64 UNIX

[Multi-threads 例題]
有兩個 Process P_A 與 P_B，P_A 三 條thread、P_B 兩條thread，若 OS 採平均分配原則來分配 CPU Time，則 P_A 與 P_B 各分多少 % 之 CPU Time？

1. User thread
2. Kernel thread

Ans :

1. Kernel 不知道有 user thread，只知道有 P_A 與 P_B 兩個 process。P_A 與 P_B 各分到 50% 的 CPU Time。
2. 有 5 條 thread 欲分配，每條可分到 20% 的 CPU time。
   P_A 分到 3×20% = 60% 的 CPU time。
   P_B 分到 2×20% = 40% 的 CPU time 。

• Multi-threading model:

1. Many to one:
   1.1 容易被single thread卡死
   1.2 沒有平行化
   1.3 可攜性好

2. One to one:
2.1 成本高
2.2 kernel thread會對程式執行產生負擔???, 所以限制數量

3. Many to many:
3.1 不會被single thread卡死
3.2 比one to one經濟
3.3 I/O bound thread 要有 kernel thread 對應，但是不會讓執行的核心忙碌??? 想讓執行的核心忙碌要再加等量的 kernel thread ?? why let CPU busy

Note: When you write multithreaded programs, It should not be assumed that which model is adopted by the thread library! 不該預期是哪種model

• Issue:

1. Semantics of fork() and exec(): ***再讀
   undefined: 有可能
   1.1 fork this thread
   1.2 fork this process
2. Signal handle:
   2.1 synchronous signal
   2.2 asynchronous signal

Note:
interrupt: process or device 通知 kernel
signal: kernel 通知 process

3. Thread cancellation
3.1 asynchronous cancellation : 立刻取消
3.2 deferred cancellation : 一個時間周期到才會取消
3.3 actual cancellation : 根據thread狀態取消

4. Thread pools

5. Thread local storage(TLS)
Thread布置TLS讓外面可以觀測

6. Light weight process (LWP)
介於 user-level thread 和 kernel-level thread 的資料結構，用來提供一個 virtual process 讓應用程式 thread 做排程，支援多個 User-level Thread 對應到一個 kernel thread，屬於 kernel-level thread。

7. Thread libraries : pthreads
Pthreads (POSIX threads) 是依據 ieee 1003.1c 標準定義的 thread 標準，定義了創建和操縱 thread 的一套 API，可用在 user-level 和 kernel-level，常用在一般 Unix 作業系統。

8. Implicit threading methods

ref:

OS - Ch4 多執行緒 Multithread Programming

Scheduling:

CPU scheduling: 從ready queue挑一個process 進running(CPU 執行)

以下狀況, CPU scheduling 選擇的 process會改變:

1. running -> waiting
2. waiting -> ready
3. running -> ready
   ex: time sharing下, time out回到ready
4. terminate

• Preemptive vs Cooperative:

Preemptive scheduling(主流):

• Higher responsiveness
• Hard to share resources race conditions
• Higher overheads ???

Cooperative scheduling:

• Simpler in design
• Poor responsiveness
• Potential hazards

Dispatcher

dispatcher 負責將 CPU 控制權交給經由 Short-term scheduler 所挑選出的 process。

下列情況Dispatcher須執行：

• context switch
• switching to user mode
• jumping to the proper location in the user program to restart that program

Scheduling Criteria

• CPU utilization：CPU process exec. / CPU total time，CPU 使用的時間
• Throughput：單位時間內完成的工作數目
• Turnaround time：完成時間 (完成-到達)，進去process到出來花的時間
• Waiting time：waiting in the ready queue
• Response time：自使用者命令交付到系統產生第一個回應所需的時間 (time-sharing system, user-interactive App 特別重視)

演算法:

1. FCFS: first come first server

Convoy Effect: 很多 process 均在等待一個需要很長 CPU Time 來完成工作 process，造成平均等待時間大幅增加的不良現象。對 I/O-bound process 有極糟糕的影響，會造成低 I/O 利用度。

2. SJF: short job first

優點：short waiting time.

缺點：Not fair, starvation issue (low priority processes may never execute)
solution: 隨時間增加, 加大priority

RR (Round Robin) 排程

• 優點：

1. No process waits more than (n-1)q time units.

2. better response (Users feel that processes run “smoothly slow”)

Multi-level queue:

Ready queue is partitioned into separate queues. Each queue has its own scheduling algorithm. e.g.

• foreground (interactive) — RR
• background (batch) — FCFS

Multi-level feedback queue:

A process can move between the various queues. Aging can be implemented this way.

OS - Ch5 排程 CPU Scheduling

Synchronization:

Critical Section: the section of the program shared across processes

The Critical Section Problem：提供對共享變數之存取的互斥控制，確保資料的正確性。

Solution:

1. Mutual exclusion(Mutex):
   任一時間點，只允許一個 process 進入他自已的 critical section 內活動。
2. Progress：必須同時滿足下面2個要件
   a. 不想進入 critical section 的 process 不可以阻礙其它 process 進入 critical section
   b. 必須在有限的時間從想進入 critical section 的 process 中，挑選其中一個 process 進入 critical section，隱含No Deadlock。
   有空位時讓「想進的人」「馬上」進入
3. Bound waiting:
   自 process 提出進入 critical section 的申請到獲准進入 critical section 的等待時間是有限的。即若有 n 個 processes 想進入，則任一 process 至多等待 n-1 次即可進入，隱含 No starvation。

• Peterson’s solution — software solution
  Two process solution. Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted.
• Disable interrupt — hardware instructions support

ref 感覺有問題?
https://mropengate.blogspot.com/2015/01/operating-system-ch6-synchronization.html

• Semaphore: includes waiting list of process, counter and also supports two different type of atomic operations i.e. wait and signal.

1. Binary Semaphore: implement the solution of critical section problems with multiple processes.
   value: 0~1, initialize value: 1
2. Counting Semaphore: control access to a resource that has multiple instances.
   value: 0 ~ unrestricted

P(): wait, s-1
V(): signal, s+1

ref:

Semaphores in Process Synchronization - GeeksforGeeks

• Mutex vs semaphore:

Mutex:
1. 只能由上鎖的 thread 解鎖
2. 只能讓一個 thread 進入 critical section
3. 可以避免priority inversion(透過mutex傳priority)

Semaphore:
1. 可以由原本的 thread 或是另外一個 thread 解開 (跟jesrv寫的不同??)
2. 可以設定要讓幾個 thread 進入
3. binary semaphore 無法避免priority inversion
4. 用signal 的 up 與 down，讓 Semaphore 可以變成是一種 notification 的作用，例如 A thread 執行到某個地方時 B thread 才能繼續下去，就可以使用 Semaphore 來達成這樣的作用。

ref:

Mutex, Semaphore, the difference, and Linux kernel | louie_lu's blog

• priority inversion: priority低的process反而先執行

Task H, task L share resources, Task H must wait Task L finish
Task L run -> Task M becomes ready to run, preempting Task L -> Task M run

ref:

Introduction to Priority Inversion

• semaphore vs spinlock:

semaphore: wait()失敗 -> context switch進到sleep -> 排入waiting queue -> 直到resource釋放 -> 排入run queue

spinlock: 用test and set(atomic)這個指令看有沒有辦法取得lock, 不會sleep, 不會context switch, busy waiting, 適用多核

mutex: 拿不到lock也會sleep, context switch, 適用單核

ref:

Work Note-semaphore/mutex/spinlock

Linux 核心設計: 淺談同步機制 - HackMD

• Parallel vs Concurrent:

Parallel:

1. 同時做很多事 do a lot of things at once

2. 需要multiple core

code:

scenario

concurrency is about dealing with lot of things at once 一次處理很多事

1. share resources need to access/update
2. multiple task need to coordinate ???

CPU只有1 core也會發生

Code:

scenario:

理想:

非理想:

multiple core 也會發生

solution:

1. lock & unlock

lock & unlock protect share resources

2. Atomic:

• Deadlock:
  發生在multi-processes, 互相等待對方所擁有的資源的情況，造成所有的 process 無法往下執行

• 滿足4個條件:

1. Mutex: 如果Resource在任何時間點，最多只允許一個process持有(使用)。ex: CPU, Memory, I/O Device
2. Hold & Wait: Process持有部分Resource且等待其他process有的Resource。
3. No Preemption: Process不可任意搶奪其他process持有的Resource，必須等待對方自願釋放後才有機會取得。
4. Circular Waiting

• Deadlock vs starvation:

• Deadlock solution:

1. Prevention:
   1.1 Mutex: 無解
   1.2 Hold & Wait: 可行。規定只有可以一次拿到所有需要的Resource才可以擁有；要申請其他Resource前，要先放棄手中Resource。
   1.3 No Preemption: 可行。改為Preemptive即可，依優先權決定誰可以搶Resource。
   1.4 Circular Waiting: 可行。賦予Resource ID，必須依照ID順序持有。??

2. Avoidance:

3. Detection & Recovery:

4. Ignore:

ref:

OS - Ch7 死結 Deadlock

Memory Management

較好懂的教學

Memory management on Linux:

memory management on Linux

Binding: 決定程式記憶體位置, 分compile/load/run time

binding

How to refer memory in a program — Address Binding

1. Compile Time

程式中的資料、參數等必須要有對應的記憶體位置，早期的作法是在編譯期間，就決定要放在哪裡，送進 CPU 時 CPU 就知道該去哪裡存取資料

• Compiler 會將組合語言轉換成實際的記憶體位置(absolute code)
• 若起始地址變更(可能該地址被其他 process 占住)，則需要重新編譯 (recompile)，等於要關閉並重新執行

ex: MS-DOS .COM format

2. Load Time

• Compiler 不會決定實際的記憶體地址，而是會留一個變數(Base Register)，給出相對位置。程式讀取後(loader，loader 一般假設程式是重新執行，因此會執行非常多動作，如 process 的 control block、記憶體初始化、data structure 的創建等，也就是 program 變成 process 的過程)，才透過該變數決定真正的地址(relocatable code)
• 若 run time 起始地址變更，則需要重新讀取 (reload)

3. Execution Time

• Compiler 將組合語言轉換成 logical-address(i.e. virtual-address)
• 雖然看似 compile time 決定實際地址，但這其實是個虛擬的地址。
• CPU 以為記憶體地址就是 compiler 轉換的位置，但送要求去記憶體存取資料時，中間還有一個硬體單元 MMU(i.e. Memory-Management-Unit, MMU)，會做記憶體地址的轉換，導向正確的實際地址
• MMU 將虛擬地址 map 為實際地址

由 logical-address 加上 relocation register 產生實際地址

MMU 可以看成 OS 的一部分，但因為使用頻率非常高，所以一般用硬體來實作

多數 general-purpose 的作業系統使用這個方法

Logical vs. Physical Address

• Logical address 為 CPU 送出的地址，也就是 virtual address
• Physical address 為記憶體看到的真實地址
• Compile time & Load time address binding 的方式，logical address = physical address
• Execution-time address binding 的方式，logical address != physical
• User program(Programming, Compiling…etc) 只管 logical address，永遠不會看到 physical address

How to load a program into memory — static/dynamic loading and linking

1. Dynamic Loading

• 不會將整個程式 load 到記憶體，子程式在 function call 的時候才 load
• 這樣做有更好的記憶體空間使用
• 未用到 routine 不會被載入記憶體
• 在大量程式碼使用率較低時(如 error handling code)特別有用
• OS 提供功能，但不會決定 routine 是 dynamic 或 static loading，而是由使用者決定(library, API)
• 在 C 語言中使用 Dynamic Loading 的範例，當呼叫 printf("%f\n", (*cosine)(2.0)) 時，cosine 才會讀到記憶體中。現在 programmer 使用 Dynamic Loading 常常是希望在 run time 決定該使用哪個函式。

2. Static Linking

• 函式庫透過 loader 被結合進 program 的 image 當中，compile 的時候，將函式庫加入程式碼
• 每一個用到函式庫的 program 都有一份，浪費記憶體資源，但執行比較快
• 即便改用 Static Linking 加上 Dynamic Loading，因為函式庫仍然需要，因此無法解決程式碼重複複製的問題

3. Dynamic Linking

• Dynamic Linking 在 run time 才去找連結
• 因此只需要一份 library 在記憶體當中
• OS 在 program 中加入 stub，call stub 的時候會向 OS 確認 library 是否在記憶體中
• stub call → 找 referred lib 是否在 memory 中，沒有的話則 Load 進來 → 將其位址替換掉，之後就不用經過 stub(relocation)
• 因為在 run time 時期才找函式庫，執行速度較慢
• 在 windows 中為了系統效能，是編譯成 DLL(Dynamic link library)

Swapping: process暫時放到外部記憶體(ex: disk), 之後再load回來繼續執行(priority-based scheduling algorithms), mid-term scheduler.

考慮swap transfer time:
Consider that the disk transfer rate is 40MB/s, and the average disk seek overhead is 8 ms. To swap out a 10-MB process and then to swap in a 10-MB process require

10,000KB/40,000KB = 250ms (250ms+8)*2=0.516s (mid-term scheduler)

Note: The time quantum of a typical time-sharing system is 10ms; (short-term scheduler)

Contiguous Memory Allocation:
OS 依據 Process 的大小找一塊夠大的連續可用的記憶體，配置給該 process 使用；OS 用 Link List 管理 Free Blocks，稱為 Available list

1. Relocation-register 有base, limit資訊, 限制每個process的memory

2. 找連續可用空間:

• First-Fit：從 AV list head 找，第一個 free block size >= n 就配置。
• Next-Fit：從上次配置後的下一個 Block 開始搜尋，改善 First-Fit 易在 AV-list 前端附近產生許多非常小的可用空間的問題。
• Best-Fit：找所有 free block，比 n 大且最接近 n。
• 長期而言會剩下很大的洞跟很小的洞。
• Worst-Fit：找所有 free block，比 n 大且（size — n）值最大者。
  長期結果每個洞大小差不多。
• Buddy System：16,8,4,2,1的二元樹，每一層有 list 可以搜尋有無空間。

不同fit的結果

缺點:

1. 均有外部碎裂(External Fragmentation)問題：所有可用空間總和大於某個 process 所需要，但因為此空間不連續所以無法配給該 process 使用，造成 memory 空間閒置。

2. 配置完所剩的極小 Free Blocks 仍會保存在 AV-list 中，徒增 Search Time 與記錄成本。

Fragmentation: memory空著沒法用

• External fragmentation:可用空間總和大於某個 process 所需要，但因為這些空間不連續所以無法配給該 process 使用

solution:
1. Compaction: 類似磁碟重組, 移動執行中的 process，使不連續的 free blocks 得以聚集成一塊夠大的連續可用空間.
a. 很難在短時間內決定一個最佳的壓縮策略。
b. process 必須是 dynamic binding 才可以支援

2. Page memory management

• Internal fragmentation: 配置給 process 的 memory 空間大於 process 真正所需的空間(ex: process 14kb, 配16kb, 浪費2kb)

solution: 減小page的size

Paging: OS 將 disk切成pages, page是disk和memory傳輸的最小單位

• Physical memory: frames, each frame大小相等
• Logical memory: process用的, pages, page大小 = frame大小

process 有一個 page table, page table 儲存在記憶體中，執行時用 page table 的資訊來把 logical address 轉成 physical address。

logical address to physical address

優點：

• 解決 external fragmentation問題
• 可以支援記憶體的共享(Sharing)：不同 page 對應相同的 frame。
• 可以支援記憶體的保護(Protection)：在分頁表上多加一個 protection bit 欄位
• R : 表示Read only
• RW : 表示Read/Write皆可
• 支援 Dynamic Loading 及 Virtual Memory 的製作

缺點：

• 會有 internal fragmentation 問題 (page size 愈大愈嚴重)
• memory 有效存取時間較長 (logical address 轉 physical address)
• 需要額外的硬體支援
• page table implementation (每個 Process 皆有 1 個 page table)
• logic address -> physical address (用到搜尋器、加法器)

Page table製作:

1. register 保存分頁表每個項目的內容

優點 : 速度快

缺點 : 僅適用於 page table 大小較小的情況，太大的 page table 則不適用。 ???

2. page table 保存在 memory 中
Page table base register(PTBR) 紀錄起始位置
Page table length register(PTLR) 紀錄table大小

優點 : 適用於 page table size 較大之情況 ??

缺點 : 速度慢。因為需要存取兩次 memory。(一次用於存取 page table、一次用於真正的資料存取)

3. 用Transaction Lookaside Buffer(TLB, full associate cache)保存常用page table, 完整的page table保存在memory
flow:
lookup TLB(find page no.) -> find, output frame address, 只access 1次
-> miss, 在memory查page table, access 2次

[例題] TLB 的 Effective Access Time (EAT) 計算

Let the TLB hit ratio= 98 %, 20ns to lookup the TLB, 100 ns to access memory.

• TLB hit time = 20+100
• TLB miss time = 20 + 100 (page table) + 100 (target address)
• EAT = 0.98*120 + 0.02*220 = 122 ns

Page Table型態

目的：page table size 太大太稀疏的解決方法

1. Multilevel paging:
   透過 paging page table，只抓所需的 page table 進 memory

2. Hashing Page Table:

a. 將 logical address 中的 p(page#) 經由 hashing function 計算取得 hashing table (page table) 的 bucket address。

b. 而在每個 bucket 中，皆以 linked list 串連具相同 hashing address 的 page number 及對應的 frame number。

c. 去 linked list 中搜尋符合的 page number 之節點。取得 f，然後與 d 相加得出 physical address。

3. Invert Page Table:

a. 以 physical memory 為對象，建立一個 global page table 給所有 process (若有 m 個frames，table entry 有 m 格)

b. 每個 entry 記錄此頁框被哪個 process 的哪個 page 所佔用以 <Process id, Page No>

優點：大幅降低 page table size

缺點：

1. searching invert page table 耗時，可用 hash 增加搜尋速度

2. 無法支援 memory sharing

Segmentation

使得記憶體的 logical 配置的看法與使用者一致。配置方式為單一段之間連續配置。OS 會替每個 process 準備 segment table :

1. 用 Segment-table length register (STLR) 記錄各段的大小(Limit)。

2. 用 Segment-table base register (STBR) 紀錄各段載入記憶體的起始位址(Base)。

優點 :

1. 無 internal fragmentation。

2. 支援 memory sharing 和 protection，且比 paging 容易實施(有的Page可能會涵蓋到不同需求的程式片段)。

3. 可支援 dynamic loading 及 virtual memory 的製作。

4. segmentation 和 page 為兩獨立觀念，可同時使用

缺點 :

1. external fragmentation (但 segments 很少 allocated/de-allocated 所以還好)

2. 記憶體存取時間較長。

3. 需要額外硬體的支援。

paging vs segment

Paged Segment Memory Management(先分段、再分頁)

每個 process 會有一個 segment table，而每個段會有一個 page table。

優點:

1. 與User對Memory看法一致(segment)

2. Sharing/Protection易實作之優點(segment)

3. 避免 external fragmentation (paging)

缺點:

1. 仍有internal fragmentation(最終是paging)
2. table多, 占memory, access time長

ref:

作業系統 CH8 Memory Management - HackMD

OS - Ch8 記憶體管理 Memory Management

Virtual memory

讓程式以為有連續可用的記憶體, 實際上通常是 切成多個片段的physical memory + disk memory

優點:
1. process 需求的memory > physical memory, 可以執行

2. OS負擔, programmer無負擔(???)

3. physical memory各個小空間都可利用, 提升使用率

4. 提高 multiprogramming degree，提昇 CPU 使用度 (有足夠的page for process ???

5. I/O transfer timer下降, 不用將all page載入 ???

Note: 64 bit Virtual address vs Physical address:

• virtual address:

不需要2^64(太大, 增加複雜), 幾種implement: 48 bits, 57 bits

ex: 48 bits, 分成canonical higher/lower half
可用空間 4G*64K = 256 TB

搭配Page table structure: 好幾層page-mapped table用 ?? 好處是??

• Physical address: AMD64 processor support 256 TB, 但是主機板還沒support 256 TB

x86-64 - Wikipedia

Implement

1. Demand paging:

以 paging 為基礎，採用 lazy swapper 技巧
process初期不將all pages 載入 physical memory, OS負責處理page fault

a. 多加一個 Valid/Invalid Bit 欄位，用以指示 page 是否在 memory 中。

b. Effective Access Time (EAT) = (1 — p) x memory access + p (page fault overhead + swap page out + swap page in + restart overhead)

2. Copy on write:

一種最佳化, 同時多個callers同時要求相同資源（physical memory or external memory）, callers拿到一樣的pointer 指向資源, 直到某個caller要改變data -> copy副本 for this caller, 其他callers用原本的資源

應用: parent process fork child process, 只有child要改變資料才會copy(frame), 大部情況child 不會改變資料, 增加效率.

a. fork()使用copy on write:
parent, child concurrent執行, CPU要有MMU硬體支援

b. vfork()不使用copy on write:
(1) parent, child除了stack其他都共享
(2) 通常用於沒有MMU硬體支援, parent要等child執行完(exec(),exit())

Page replacement algorithm:

當 page fault 發生且 memory 無可用 page 時, OS必須執行page replacement: chose victim page swap out to disk, swap in the lost page到frame.

a. swap out/swap in是disk I/O(慢)

b. 不一定需要swap out, 看victim page有沒有修改(dirty bit), 沒有修改就不用swap out; swap in是必須的

方法:
1. FIFO: 最先的page = victim page
可能有Belady 異常現象：當Process分配到較多的Frame數目其Page Fault Ratio不降反升.

4個frame錯10個 vs 3個frame錯9個

ref: Bélády’s anomaly

2. Optimal page replacement(OPT):
最佳, 沒有Belady’s anomaly, 無法實現(看不到未來)

3. Least Recently Used (LRU):
沒有Belady’s anomaly, 需要大量硬體支援(counter or stack)

• 因為LRU成本太高, 延伸近似法:

a. Second change: FIFO + reference bit
每個 page 的初始值 reference bit 值設為 1，每次被指到的 page 其 reference bit 值就改為 0，然後指下一個 page，如果下一個被指到的 page 其 reference bit 值為 0 的話，則替換該 page。

b. Enhanced second change: 多 modification bit
(0,0)：最近沒被用到過也沒被修改過。
(0,1)：最近沒被用到過，但是有被修改過。
(1,0)：最近有被用到過，但是沒被修改過。
(1,1)：最近有被用到過，也有被修改過。
越上面, 越容易成為victim

c. Pre-paging: 猜那些page會用到, process初期就載入這些pages

4. Least Frequently Used(LFU):
Need time to warm up and cool down (aging) a page

Performance Issue

1. frame 的分配多寡對 page fault ratio 之影響:
一般來說，Process所分配到的 frame 愈多，則 page fault ratio 愈低。 process 所分配的頁框數目有最少數目與最大數目的限制，此兩類數目限制均取決於硬體因素。

• 最大數目的限制：由 physical memory size 決定
• 最少數目的限制：由機器指令結構決定，必須能讓任何一個機器指令順利執行完成，即機器指令執行過程中，Memory Access可能之最多次數。

e.g. IF — ID — EX — MEM — WB 中，IF 必有記憶體存取，MEM、WB可能有必有記憶體存取，因此最少的 frame 數目為 3。

2. page size 對 page fault ratio 之影響 (TLB reach)
3. page structure/algorithm 對 page fault ratio 之影響
4. I/O interlock

Thrashing

如果一個 process 沒有足夠的 frames，代表 process 在記憶體中的 frames 數量不足以支撐 process 執行，導致 page fault 一直在發生 (且 page fault 是 instruction level，無法 overlap)，等於 CPU 要一直等待 I/O，造成 CPU 使用率反而下降的情況

當一個 process 花在 paging 的時間比執行時間更高時，稱為 thrashing

• Performance problem:
  process因page falut而等I/O -> CPU utilization下降 -> OS因CPU utilization下降, 增加degree of multiprogramming -> new process搶old process的frame 導致更多page fault -> CPU utilization持續下降
• Solution:

1. Working set model:

a. 從 Locality 的角度思考, 計算一段時間process所需的frame數量, assign給process

b. process的frame需求是動態變化, OS必須持續追蹤
(1) program structure, ex: subroutine, loop, stack
(2) data structure, ex: array
(3) working set window: 觀察的時間

每一個 process 的 working set size WSSi, frames 的總需求數 D=∑WSSi
D > m (available frames) ，則有 thrashing 發生
如果 D << m，增加 degree of multiprogramming
如果 D > m，把整個 process suspend (mid-term scheduler)，free 該 process 所有的 frames

優點:
1. 在最大化 multiprogramming 的情況下，同時防止 trashing 的發生
2. 可以最大化 CPU 使用率

缺點: tracking 的成本很高

2. Page fault frequency scheme:
監控每個process fault rate, 控制fault rate在一定範圍, 防止thrashing

為每一個 process 建立 upper 跟 lower bounds
如果 page fault rate > upper limit, increase frames
如果 page fault rate < lower limit, reduce frames

Memory-mapped file

一段virtual memory對應1 file，將file I/O 視為經常性的記憶體，而非一般的 open(), read(), write() 標準系統存取
程式設計師可以藉由撰寫記憶體映射檔案相關的函式庫程式 (如 c 的 mmap, java 的 java.nio package) 直接從virtual memory讀取檔案內容，加速 I/O 效能

特性:
1. 高速檔案存取 (主要目的)
a. 比直接讀寫檔案快幾個數量級
b. 傳統檔案每次被讀取時需要一次系統呼叫+ 一次磁碟存取

2. 將大檔案載入到記憶體。
a. 導致內部碎片空間浪費 (對齊頁，通常為 4 KB) ???
b. 對映檔案區域的能力取決於於記憶體定址的大小：在 32 bit 機器中，不能超過 4GB。
c. 多個程式共享記憶體，直接對記憶體進行讀取和寫入來修改檔案。
d. 使程式動態載入ex: Linux dynamic loading 實作方式。

ref:

OS - Ch9 虛擬記憶體 Virtual Memory

作業系統CH9 Virtual Memory Management - HackMD