CSIE - Operating System

CSIE - Operating System

LAVI
  2022-05-11 2022-05-11 Created   2024-09-11 2024-09-11 Updated    

Chapter 5

  • Real-Time CPU Scheduling
    • soft real-time system
      • 沒有保證 real-time process 何時被排班
    • hard real-time systems
      • 任務必須在期限內被服務
    • interrupt latency
      • 從 interrupt 到達到他開始被服務的時間
    • dispatch latency
      • 停止當前行程並啟動另一個行程的時間
      • conflict phase
        • 任何在 kernel 的行程都可搶先
        • 低優先權的行程釋放資源給高優先權
  • Priority-based Scheduling
    • periodic
      • 在固定的間隔週期要求 CPU
  • Rate-Monotonic Scheduling
    • 優先權是週期的倒數
    • ex:
      • p1 = 50, p2 = 100
      • t1 = 20, t2 = 35
      • CPU utilization = time/period = 20/50 + 35/100 = 75%

        不合，因為 p1 過了 deadline

        符合，使用 Rate-Monotonic Scheduling，看優先權

    • Rate-Monotonic Scheduling 被視為最佳，不能用它做的別人也做不了
  • Earliest-Deadline-First (EDF) Scheduling
    • 優先權看 deadline，越早越高
      • deadline，一開始 d=p，完成 t 後 d += p
    • ex:
      • p1 = 50, p2 = 100
      • t1 = 20, t2 = 35
      • CPU utilization = time/period = 25/50 + 35/100 = 75%

        第二輪週期時，d1 = 100, d2 = 160
        所以 p2 在 t=100 時被 p1 搶先，因為 p1 優先權高

  • Proportional Share Scheduling
    • 配置 T 個分享，單位時間能接收 N 次分享，每個 process 收到 N/T 的處理時間
    • ex:
      • T = 100
      • N: A = 50，B = 15，C = 20
      • A 有總處理器時間的 50/100 = 50%，B 有 15%，C 有 20%
  • Little’s Formula
    • n = average queue length
    • W = average waiting time in queue
    • λ = average arrival rate into queue
      • n = λ x W
      • ex:
      • 已知每秒平均有 7 個 process 到達(λ)，並且通常有 14 個 process 在佇列中(n)，就可以求出每個 process 的平均等待時間為 2 秒鐘(W)
  • Simulations
    • Trace tape
      • 監督實際系統，紀錄實際事件順序

Chapter 6

  • Race Condition
    • 數個行程同時存取和處理相同資料的情況，執行的結果取決於存取時的特定順序
    • ex: count = 5
      • T0: producer execute register1 = counter {register1 = 5}
      • T1: producer execute register1 = register1 + 1 {register1 = 6}
      • T2: consumer execute register2 = counter {register2 = 5}
      • T3: consumer execute register2 = register2 – 1 {register2 = 4}
      • T4: producer execute counter = register1 {counter = 6 }
      • T5: consumer execute counter = register2 {counter = 4}

        不正常的狀態，count == 4，紀錄有 4 個緩衝區，但實際上有 5 個

  • Critical Section Problem
    • Each process has critical section segment of code
      • 當一個行程在他的 critical section執行，不允許其他行程在此 critical section 執行
    • 每個 process 必須要求允許，才能進入臨界區間
      • entry section -> critical section -> exit section -> remainder section
    • Solution to Critical-Section Problem
      1. mutual exclusion:
        • 如果行程 pi 正在 critical section 內執行，則其他的行程不能在其 critical section 內執行
      2. progress:
        • 如果沒有行程在 critical section 內執行，同時某一行程想要進入其 critical section，那他就會立即的可以進入 critical section
      3. bounded waiting:
        • 在一個行程已經要求進入其 critical section，而此要求尚未被答應之前，允許其他行程進入其 critical section 的次數有一個限制
    • Preemptive kernel
      • 讓一個行程在核心模式中執行時可以被搶先
    • Non-preemptive kernel
      • 直到離開 kernel mod、block、自動交出 CPU 控制前，都不可
  • Peterson’s Solution
    • solve Critical-Section Problem
      • int turn
        • 輪到誰進入 critical section
      • boolean flag[2]
        • 表示一個行程是否準備進入 critical section
    • 為了證明解答是對的，需要證明:
      1. mutual exclusion 存在
        • flag[j] = false or turn = i
      2. progress 要求都能被滿足
      3. bounded waiting 要求可以符合
  • Memory Barriers
    • strongly ordered
      • 修改 memory 位址時，馬上立即可知
    • weakly ordered
      • 修改 memory 位址時，不會立即可知
    • memory barriers/memory fences
      • 可以強制將 memory 的任何修改傳遞給其他 processor 的指令
  • Hardware Instructions
    • Atomic = non-interruptible
    • test_and_set()
      • test memory word and set value
      1. 不可中斷的執行
      2. Returns the original value of passed parameter
      3. Set the new value of passed parameter to “TRUE”
    • compare_and_swap()
      • swap contents of two words
      1. 不可中斷的執行
      2. Returns the original value of passed parameter “value”
      3. 只有當 if(value == expected) == true 時，value 才會設置成 new_value
    • 只有第一個行程可以進入 critical section
    • Atomic Variables
      • compare_and_swap() 用作建立解決 Critical-Section Problem 的工具
  • Mutex Locks
    • 保護 critical section，進入 critical section 前須 call acquire()、離開後須 call release()，兩者不可分割
    • 會造成 busy waiting，因此也被稱 spinlock
      • 再進入前會在 acquire() 不斷執行(旋轉)
    • Contended lock
      • a thread blocks while trying to acquire the lock
    • Uncontended lock
      • a lock is available when a thread attempts to acquire it
    • short duration
      • less than 2 context switches (one to wait and one to restore)
  • Semaphore
    • 只能經由 wait() 和 signal() 兩個不可分割的方式執行
    • counting semaphore
      • integer value 不受限制
    • Binary semaphore
      • 可以是 0 或 1，類似 mutex lock
    • sleep()
      • 當 semaphore 不為正，在 waiting queue 裡 invoke wait()
    • wakeup()
      • 當 process 執行 signal()，把一個在 waiting queue 裡的 process 移到 ready queue
  • Monitors
    • 一種高階、抽象的資料結構，提供便利且有效率的 process 同步機制
    • 只能存取在 monitor 內部的變數或參數
    • 同一時間內只有一個 process 在 monitor 內活動
    • x.wait()
      • 執行這個運作的行程，必須先暫時等待，直到另一個行程執行 x.signal()
    • x.signal()
      • 每次只能恢復一個 invoke x.wait() 的 process
  • Liveness
    • 系統必須遵循的特性，以確保 process 讓 progress make progress during their execution life cycle
    • liveness failure
      • Infinite loop
      • Busy wait presents the possibility of starvation
      • Deadlock
      • Priority inversion
  • Deadlock
    • 多個 process 無限期的等待只能由在 waiting 的 process 發出的事件
  • Priority Inversion
    • 排班問題，低優先權持有高優先權所需的 lock
    • 解決: 使用 priority-inheritance protocol
      • priority: L < M < H
      • 讓低優先權 L 暫時繼承高優先權 H，以阻止被 M 搶先，避免 H 要等 M
      • 執行完後再放棄繼承到的優先權

Chapter 7

  • Bounded-Buffer Problem
    • n buffers, each can hold one item
    • Semaphore mutex initialized to the value 1
    • Semaphore full initialized to the value 0
    • Semaphore empty initialized to the value n
      • producer
        • produce -> wait(empty) -> wait(mutex) -> add -> signal(mutex) -> signal(full)
      • consumer
        • wait(full) -> wait(mutex) -> remove -> signal(mutex) -> signal(empty)
  • Readers-Writers Problem
    • reader
      • only read the data set，do not perform any update
    • writer
      • both read and writer
    • problem
      • 有 writer 和其他 reader/writer 同時存取共用資料
    • 解決:
      • Semaphore rw_mutex initialized to 1
        • 確保 writer/第一個 reader/最後一個 reader 是 mutual exclusion
      • Semaphore mutex initialized to 1
        • 確保 reader 是 mutual exclusion，配合計算 readcount
      • Integer read_count initialized to 0
        • 有幾個正在讀取 reader
    • 變形:
      1. first
        • reader 只會等待 writer，不用等待 reader
        • writer 可能會 starve
      2. second
        • 只要有一個 writer 在等待，就沒有 reader 可以讀取資料
        • reader 可能會 starve
  • Dining-Philosophers Problem
    • 哲學家搶筷子吃飯問題
      • solution
        • semaphore
          • 利用 semaphore chopstick[5];
          • 可能產生 deadlock，解決方法:
            1. 最多允許 4 個哲學家同時坐在桌旁
            2. 允許一個哲學家只有當左右兩側的筷子都可用時才拿筷子
            3. 讓奇數/偶數位子的哲學家先拿左邊的筷子，再拿右邊的筷子
          • 解決 deadlock 但還是可能會 starvation
        • monitor
          • 哲學家只有當左右兩側的筷子都可用時才拿筷子
          • 哲學家只有當左右兩側的鄰居都不在吃飯時才可以吃飯
            • enum {THINKING, HUNGRY, EATING} state[5];
            • state[(i+4) % 5] != EATING and state[(i+1) % 5] != EATING
          • 雖然很餓，但無法取得兩側筷子時，必須先 delay
            • condition self[5];
  • Transactional Memory
    • 不可中斷的一連串 read/writer 操作
    • 當 transaction 都被執行完畢，交付 memory transaction；否則，操作將被終止並撤回
      • 確保不可中斷性
      • 辨識哪些 block 可以一次被完成，哪些可以平行被執行

Chapter 8

  • Deadlock Characterization

    同時出現 4 項就會 deadlock

    1. Mutual exclusion
      • 一次只有一個 process 可以使用此資源，如果有別人想用，就要等待此資源被釋放
    2. hold and wait
      • 一個 process 拿著至少一項資源，但正在等待其他已被其他 process 占用的資源
    3. no preemption
      • 資源不能被搶先
    4. circular wait
      • 如果 T0 所等待的資源已被 T1 占用，而 T1 等待的資源被 T2 占用，Tn 的資源又被 T0 占用
  • Resource-Allocation Graph (RAG)
    • 說明 deadlock 現象
    • ex:
      • process 狀態:
        • T1 占用 R2 的一個 instance，並正在等待 R1 的一個 instance
        • T2 占用 R1 和 R2 的各一個 instance，並正在等待 R3 的一個 instance
        • T3 占用 R3 的一個 instance
    • 如果 RAG 有環，每個 R 只有一個 instance 時，必 deadlock
      • 沒有還，沒有 deadlock；有環但有多個 instance，可能 deadlock
  • Deadlock Prevention
    1. mutual exclusion
      • 不要要求可共享的資源
      • 占用不可分享資源
    2. hold and wait
      • 必須確保 thread 在不占用其他資源時，才可以要求資源
        • 在每個 thread 執行前先要求並取得所需資源
        • thread 只有在未占用資源時可以要求資源
        • 缺點: resource utlization 低、可能 starvation
    3. non preemptive
      • 如果一個 process 占用著某些資源，但還要求無法立即被取得的資源，則他目前持有的資源可以被他人 preemptive，他要釋放那些資源
      • 這些 preempted 的資源會被加到 process 正在等候的 waiting list
      • 當 thread 重新或的原有的資源和正要求的資源後，才會重新開始
    4. circular wait
      • 對所有的資源形式強迫安排一個線性的順序，thread 要求資源時必須按照數字大小、遞增的提出要求
  • Deadlock Avoidance
    • 取得關於資源的前置資訊
      • 每個 thread 聲明其所需的每種資源的最大數量
      • 動態檢查資源數量，確保不會 circular wait
      • resource-allocation state
    • safe state
      • 如果系統能以某種順序將其資源分配給各 thread，而且能避免死結，就稱為 safe state

        safe state: T1、T0、T2

  • Resource-Allocation Graph 方案
    • Single instances
    • Claim edge: Ti → Rj 表示出 thread Tj 可能在未來需要資源 Rj，以虛線表示
      • Claim edge 轉換成 request edge，當 thread 要求資源時；Request edge 轉換成 assignment edge，當資源被分配給 thread；assignment edge 轉換成 claim edge 當 thread 釋放資源後
      • 當 Request edge 轉換成 assignment edge 不會產生環時，才會被允許
  • Banker’s Algorithm
    • Multiple instances
      - 𝑁𝑒𝑒𝑑[𝑖][𝑗] = 𝑀𝑎𝑥[𝑖][𝑗] − 𝐴𝑙𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛[𝑖][𝑗]
    • safety algorithm

      整張都是重點

    • ex:
      • 5 thread T0 到 T4
      • 3 resource types: A (10 instances), B (5instances), and C (7 instances)
      • 設定在時間 t0 時，狀態如下

        safety state: T1、T3、T0、T2、T4


      • T1 再要求 (1, 0, 2)
        • 先確認 (1, 0, 2) 是否 <= available (3, 3, 2)
          • available = available - request
          • allocation = allocation + request
          • need = need - request
      • T4 再要求 (3, 3, 0) -> No
      • T0 再要求 (0, 2, 0) -> No
  • Deadlock Detection
    • wait-for graph
      • Single Instance of Each Resource Type
        • Resource-Allocation Graph 的變形
    • Detection Algorith
      • Several Instances of a Resource Type

        似乎和 safety algorithm 只差在第四步檢查的東西不同
        還有第二步，是 request 和 work 做比較，不用 need

    • ex:
      • 5 threads T0 到 T4
      • Three resource types: A (7 instances), B (2 instances), and C (6 instances)
      • 在 t0 時有下列資源分配狀態:

        sequence: T0、T2、T3、T1、T4，使 all finish[i] = ture

      • if T2 requests an additional instance of type C
        • 會 deadlock
  • Recovery from Deadlock
    • 取消所有死結中的行程
      • 代價大
    • 一次取消一個行程直到死結循環被消除為止
      • 超額費用
      • 如何決定取消誰:
        1. Priority of the process
        2. 此行程已運作多久，在完成指定工作前還需要多少時間
        3. process 已經使用的資源
        4. 行程還需要多少資源，才能完成此行程
        5. 有多少行程須被終止
    • Resource Preemption
      • 逐步搶先行程的某先資源，直到死結被消除
        1. Selecting a victim
        2. Rollback
          • 必須將其撤回某一安全狀態，在從此狀態重新開始
        3. Starvation
          • 某些行程可能總是被選為犧牲者，使得他永遠無法執行完他的工作，所以要設定被選為犧牲者的次數

Chapter 9

  • cache 在 CPU 和主記憶體之間，用來配合速度差異的記憶體緩衝器
  • Base and Limit Registers
    • 定義一個 logical address space
  • Address Binding
    • first user process physical address always at 0000addresses 在下述方式的任何步驟中完成:
      • compile time:
        • 如果已確知程式在記憶體中的位址，absolute code 即可產生；在過一段時間後，因為起始位址已改變，所以需要重新編譯
      • load time:
        • 程式在 compile time 若不能確定在記憶體中的位址，則編譯器必須產生 relocatable code
      • execution time:
        • 如果行程在執行時能被由原來的記憶段落移到另一段落位址，則連 binding 的動作就會被延遲到執行時間才發生；need base and limit registers
  • Logical vs. Physical Address Space
    • logical address
      • CPU 所產生的位址，也可以稱為虛擬位址 virtual address
    • physical address
      • memory unit 所看到的位址
    • logical address space
      • 一個程式所產生的所有 logical address 集合
    • physical address space
      • 一個程式所產生的所有 physical address 集合
  • Memory-Management Unit (MMU)
    • 硬體執行 virtual address map to 到 physical address 的工作
    • relocation register
      • 當行程產生的位址被送往記憶體時，就加上 relocation register 的數值
    • user program 只會處理 logical addresses，永遠無法看到 physical addresses
  • Dynamic Loading
    • static linking
      • 系統程式將可藉由 loader 將 system libraries and program code 併入二進制程式內
    • dynamic linking
      • 連結被推遲直到執行時才發生
    • stub
      • used to 定位合適的 memory-resident library routine
      • 將自己替換成 routine 的位址，並執行 routine
    • dynamic linked library DLL
      • 被執行時連結到使用者程式系統的程式庫，也稱為共享程式庫 shared libraries
  • Memory Protection
    • Relocation registers 存放著最小的 physical address
    • Limit register 存放著 logical addresses
  • Memory Allocation
    • Hole
      • 還未劃分的記憶體區間
  • Dynamic Storage-Allocation Problem
    • 如何從可用區間 free holes 去滿足 n 個大小
      • First-fit
        • 配置第一個足夠大的 hole
      • Best-fit:
        • 在所有容量夠大的區間中，將最小的一個區間分配給行程，除非區間串列依照容量大小的順序排序，否則需要搜尋整個串列才能符合這項策略
        • 會找出最小的剩餘區間
      • Worst-fit:
        • 將最大的區間配給行程，一樣除非區間串列依照容量大小的順序排序，否則需要搜尋整個串列才能符合這項策略
        • 會找出最大的剩餘區間
  • Fragmentation
    • External Fragmentation 外部斷裂
      • 有足夠的總記憶體空間得以滿足需求，但這些可用空間非連續
      • reduce external fragementation: compaction
        • 收集記憶體內零散的可用空間，使成一大空間
    • Internal Fragmentation 內部斷裂
      • 配置給一個行程的記憶體可能比實際需要多一點，要不然需要額外的功夫去記住剩下的小空間，而這些小部分沒有被使用到的記憶體就是 Internal Fragmentation
    • 50-percent rule
      • first-fit 分析顯示，給予 N 個配置區間，由於斷裂現象所以將遺失其 0.5 N，則 1/3 的記憶體可能沒有使用到
  • Paging
    • 允許行程的 Physical address space 是不連續的
    • frame
      • 將 physical memory 打散為許多固定大小區塊的欄 frame
    • page
      • 將 logical memory 打散為大小相同區塊的頁 page
    • page table
      • 設置 page table 轉換 logical addresses 成 physical addresses
    • 頁數 page number, p & 頁偏移量 Page offset, d
      • 任何由 CPU 產生的位址都分為此兩個部分
      • page number
        • 被當作指向 page table 的索引，在 page table 中存在每一 page 的 physical memory 的 base address
      • page offset
        • 承上，此 base address 再和 page offset 結合，定義送往 memory unit 的 physical memory address
    • Logical Address Translation to Physical Address step by MMU:
      1. 提取 page number p，並將其當作 page offset 的索引
      2. 從 page offset 中提取相對應的 frame number f
      3. 將 logical address 中的 p 替換為 f
    • 計算內部斷裂
      • 如果 Page size = 2,048 bytes
      • Process size = 72,766 bytes
      • 需要 35 pages + 1,086 bytes
      • 造成 Internal fragmentation of 2,048 - 1,086 = 962 bytes 位元組的內部斷裂
  • Hardware Support
    • Page-table base register (PTBR)
      - 指向 page table
  • translation look-aside buffers (TLB)
    • TLB works as follows:
      • 當有一 logical memory 由 CPU 產生後，MMU 會先檢查他的 page number 是否出現在 TLB，如果找到了，他的 frame 就立即有效且被用來存取記憶體，如果沒有，則稱為 TLB miss
        • Needs address translation
        • 需要從記憶體中找到 page table
        • 把 page 和 frame 加到 TLB 中
        • 如果 TLB 已經存滿了，作業系統需要找一項做置換
    • TLB 在每個 TLB 項目中儲存 address-space identifiers (ASIDs)
      • ASID 可以識別該行程，並用來提供行程的位址空間保護
    • Hit ratio
      • 在 TLB 中找一個 page number 所花時間的百分比率
    • Effective Access Time (EAT)
      • 計算 expectation of memory-access time
    • ex: Consider the following setting
      • Hit ratio 80%
      • Memory access time: 10ns
      • EAT: 0.80 × 10 (hit ratio * 10 所花的時間) + 0.20 × 20 (沒找到 page number 的比例 * 要花兩倍時間重找) = 12 ns
  • Protection
    • 在 page table 中的每一項都會加上另一個額外的位元: 有效-無效位元 Valid-invalid bit
      • 當這個位元被設定為有效時，表示這一頁是在此行程的邏輯位址空間內，因此是一個合法的頁
      • 如果被設定為無效，表示這一頁不在此行程的邏輯位址空間內
  • Structure of the Page Table
    • 階層式分頁 Hierarchical Paging
      • forward-mapped page table

        p1 是指向外層 page table 的索引值
        p2 是內層 page table 所指的 page table 之 page offset

      • two-level paging
        • 避免一個如此巨大的表格的解法是，將外層分頁表分為兩個較小的片段
    • Hashed Page Tables
      • The virtual page number is hashed into a page table
        • This page table contains a chain of elements hashing to the same location
        • 每個 elements 由三個欄位組成
          1. the virtual page number
          2. the value of the mapped page frame
          3. the pointer to the next element
        • Virtual page numbers 與此 chain 的欄 1 做比較
          • 如果兩者相同，相關分頁欄被用來形成所需要的 physical address
          • 如果不同，就會搜尋接下來的 chain 以找出符合的數值
    • Inverted Page Table
      • 對於 memory 的每一 page 都有一個進入點
      • 每一項中包含儲存在此 page 的 real memory location 所對應的 virtual address，以擁有該 page 的 process
      • 使用 hash table 幫助限制只搜尋一項或最多幾項
        • TLB 可以加速搜尋
  • Swapping
    • 一個行程可能被置換出記憶體到 backing store，然後再回到記憶體被繼續執行
    • backing store
      • 一個足夠大的 disk，可以容納 copies of all memory images
    • Roll out, roll in
      • 低優先權的 process 被置換，讓高優先權的 process 可以被 loaded 並執行

Chapter 10

  • Demand Paging
    • 只載入 process 所需的分頁；使用 demand paging 的記憶體，page 只有在程式有需要時才載入
    • 就像使用 swapping 的分頁系統
      • Page is needed -> reference to it
      • invalid reference -> abort 中止
      • not-in-memory -> bring to memory
  • Page Fault
    • 如果程式想要使用一分頁尚未被載入記憶體的資料時，存取會標示為無效的分頁，造成 page fault
    • 處理分頁錯誤的流程:
      1. 檢查行程的內部表格，決定是屬於有效還是無效的記憶體存取，如果是無效的 -> 中止，如果是有效的，那就是我們還沒將該頁載入，現在載入
      2. find free frame
      3. 排定 disk 去將那 page swap into 新找到的 frame
      4. 修改 tables，指出該頁目前已在記憶體中，Set validation bit = v
      5. 重新啟動因 page fault 而被中斷的指令
  • Performance of Demand Paging
    • Based on the effective access time (EAT)
      • EAT = (1−p) × ma + p × pf
      • p: 分頁錯誤出現的機率 (0 ≤ p ≤ 1)
      • ma: memory-access time
      • pf: page fault time
    • 分頁錯誤會引起下列一連串事情發生:
      1. 對作業系統發出 trap
      2. 保存 user register 與行程的狀態
      3. 認定該 interrupt 是 page fault
      4. 核對其對某頁參考是合規定的，並且決定該頁在 disk 上的位置
      5. 產生一次由 disk 讀取可用 free frame 的讀取動作
        a. 在 queue 等待，直到讀出的要求被完成
        b. 等待該裝置的搜尋及/或潛伏時間
        c. 開始將該頁轉移至一個 free frame 內
      6. 在等待的時候，可以把 CPU 分配給其他的使用者 (CPU 排班)
      7. 接收從儲存 I/O 子系統來的中斷信號 (I/O 做完了)
      8. 將 process stage 與 user register 保存起來
      9. 確認 interrupt 來自 disk
      10. 更正 page table 與 tables，以表示所要的某頁已在記憶體中
      11. 等待 CPU 再次分配給這個行程
      12. 重新存入 user register、process state、page table，然後恢復中斷指令
    • ex:
      • Memory access time = 200 nanoseconds
      • Average page-fault service time = 8 milliseconds
      • EAT = (1 – p) x 200 + p (8 milliseconds)
        = 1 – p x 200 + p x 8,000,000
        = 200 + p x 7,999,800
  • First-In-First-Out (FIFO) Algorithm
    • Reference string:
      • 當需要替換一頁時，去找最老的一頁
      • 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
      • 3 frames (3 pages can be in memory at a time per process)
      • 15 次 page fault
      • 畢雷地異常 Belady’s Anomaly:
        • 增加更多的欄可能會造成更多的分頁錯誤
        • ex 四個欄(10) 比三個欄(9) 多
  • Optimal page-replacement algorithm OPT
    • replace 往未來看，最久沒被用的 page
      • 9 次 page fault
  • Least Recently Used (LRU) Algorithm
    • replace 往過去看，最久未被使用的那一頁
      • 12 次 page fault
    • Counter implementation:
      • 令每一 page 有一個 counter，page 每被 reference 一次後 counter 就 ++
      • 如果當需要替換分頁時，就尋找 counter 中最小的值
    • 堆疊 Stack implementation
      • 保存一個由 page number 組成的堆疊來執行
      • 當某一頁被參考後:
        • 將他從 stack 中移出並放在頂端
      • 每次更新都花費許多時間，但在做替換工作時不需搜尋
    • LRU 和 OPT 一樣，都不會受 Belady’s Anomaly 影響，這種稱為堆疊演算法 stack algorithms
  • Second-chance algorithm
    • 是一種 FIFO + 會檢視 Reference bit
      • reference bit
        • initially = 0；set to 1，代表被使用過
    • Clock replacement，環狀的去取代，以一個指標標示著下一個被替換掉的頁
      • Reference bit = 0 -> replace it
      • reference bit = 1 then:
        • set reference bit 0, leave page in memory
        • 找下一個被置換的頁，用相同方法
  • 加強第二次機會演算法 Enhanced Second-Chance Algorithm
    • 藉由把參考位元 reference bit 和修改位元 modify bit 視為一組
      • Take ordered pair (reference, modify)
        1. (0, 0) 表示從未使用過也未被修改過 -> 最佳替換分頁
        2. (0, 1) 代表近來未被使用過但曾被修改過 -> 沒那麼好，因為此頁需要被寫出，才可以被替換
        3. (1, 0) 表示近來被使用但未被修改過 -> 可能很快會被再使用到
        4. (1, 1) 表示曾被使用過且被修改過 -> 可能會再被用到，再替換掉此頁之前，必須把它寫出輔助儲存體
  • Fixed Allocation
    • 比例分配 Proportional allocation
      • 可用記憶體根據每個行程的大小分配
        • 行程 pi 的大小: si
        • 定義 s = sigma si
        • 可用的總欄數是 m，分配 ai 個欄給 pi
          • ai = si/s * m
  • Thrashing
    • 如果行程沒有足夠的 frame，過程中將快速出現 page fault
      • Page fault to get page，替換接下來的 demand page
      • 但因為很快的又出現錯誤，所以又要替換並帶回分頁
      • 會導致:
        • Low CPU utilization
        • Operating system thinking that it needs to increase the degree of multiprogramming
        • Another process added to the system
      • 輾轉現象 Thrashing
        • 一個行程花費在分頁時間比執行時間還多

Reference

榮佐老師的課程簡報

On this page
CSIE - Operating System
  1. Chapter 5
  2. Chapter 6
  3. Chapter 7
  4. Chapter 8
  5. Chapter 9
  6. Chapter 10
  7. Reference