學校課程/作業系統

作業系統 筆記 (2)

contents

  1. 1. Page-replacement algorithm
  2. 2. Thrashing(振盪)
    1. 2.1. 解決方法
  3. 3. Page
  4. 4. Fragmentation
  5. 5. Deadlock(死結)
    1. 5.1. 解決方法
  6. 6. 小問題

精簡

Page-replacement algorithm

  • FIFO Algorithm
    最先載入的 Page (即：Loading Time最小者)，優先視為 Victim Page。
  • Optimal Algorithm(OPT)
    以 “將來長期不會使用的 Page Page” 視為Victim Page。
  • Least Recently Used Algorithm (LRU)
    以 “最近不常使用的 Page Page” 視為Victim Page。
    • 緣由：LRU製作成本過高
    • 作法：
      • Second econd Chance ( 二次機會法則 )
      • Enhance nhance Second Chance ( 加強式二次機會法則 )
    • 有可能退化成 FIFO FIFO，會遇到 Belady 異常情況
  • Second Chance (二次機會法則)
    以 FIFO 法則為基礎，搭配 Reference Bit 使用，參照過兩次以上的 page 將不會被置換出去，除非全部都是參照兩次以上，將會退化成 FIFO。
  • Enhance Second Chance (加強式二次機會法則)
    使用(Reference Bit Bit, Modification Bit Bit) 配對值作為挑選 Victim Page 的依據。對於沒有沒修改的 page 優先被置換，減少置換的成本。
  • Belady’s anomaly 當 Process 分配到較多的 Frame 數量，有時其 Page Fault Ratio 卻不降反升。
Rank Algorithm Suffer from Belady’s anomaly
1 Optimal no
2 LRU no
3 Second-chance yes
4 FIFO yes

Thrashing(振盪)

當 CPU 效能低時，系統會想引入更多的 process 讓 CPU 盡可能地工作。但當存有太多 process 時，大部分的工作將會花費在 page fault 造成的 Page Replacement，致使 CPU 效率下降，最後造成 CPU 的效能越來越低。

解決方法

  • [方法 1]
    降低 Multiprogramming Degree。
  • [方法 2]
    利用 Page Fault Frequency (Ratio) 控制來防止 Thrashing。
  • [方法 3]
    利用 Working Set Model “預估 ” 各 Process 在不同執行時期所需的頁框數，並依此提供足夠的頁框數，以防止 Thrashing。
    • 作法
      OS 設定一個Working Set Window (工作集視窗；Δ) 大小，以Δ 次記憶體存取中，所存取到的不同Page之集合，此一集合稱為 Working Set 。而Working Set中的Process個數，稱為 Working Set Size ( 工作集大小； WSS) 。

Page

  • Page Size 愈小
    • 缺點
      • Page fault ratio愈高
      • Page Table Size愈大
      • I/O Time (執行整個Process的I/O Time) 愈大
    • 優點
      • 內部碎裂愈小
      • Total I/O Time (單一Page的Transfer Time) 愈小
      • Locality愈集中

Fragmentation

分成外部和內部碎裂 External & Internal Fragmentation

Deadlock(死結)

  • 成因
    1. mutual exclusion 資源互斥
      一個資源只能分配給一個 process，不能同時分配給多個 process 同時使用。
    2. hold-and-wait 擁有並等待
      擁有部分請求的資源，同時等待別的 process 所擁有資源
    3. no preemption 不可搶先
      不可搶奪別的 process 已經擁有的資源
    4. circular wait 循環等待
      存有循環等待的情況

解決方法

  • Dead Lock Prevention
    不會存有死結成因四條中的任何一條。
  • Dead Lock Avoidance
    對運行的情況做模擬，找一個簡單的算法查看是否有解死結，但這算法可能會導致可解的情況，歸屬在不可解的情況。
    • Use a. to get: $\sum Need + \sum Allocation < m + n$
    • Use c. to get: $\sum Need_{i} + m < m + n$
    • Rewrite to get: $\sum Need_{i} < n$
  • Dead Lock Detection & Recovery
    Recovery 成本太高

小問題

  • Propose two approaches to protect files in a file system.
    檔案系統如何保護檔案？請提供兩種方式。

    對檔案做加密動作，或者將檔案藏起－不可讀取。

  • The system will enter deadlock if you cannot find a safe sequence for
    it, YES or NO? Please draw a diagram to explain your answer.
    如果找不到一個安全序列，是否就代表系統進入死結？

    不會，因為找尋安全序列的方式通常是精心設計的通則，也就是說每個程序要求資源的方式都是可預期的運作，但實際上並不是如此，而且順序和運作都是各自獨立且不可預期，有可能途中就會釋放資源。

  • spinlock mutex semaphore 三者的區分？

    spinlock(自旋鎖)是一種佔有 CPU 效能的一種 busy waiting，而 mutex 和 semaphore 是一種根據一個資料物件來達到互斥的效果。

    就以 spinlock 來說，比較適合鎖較短的指令。相反地，mutex 和 semaphore 用於鎖住區域 (critical section) 的指令代碼。

    回過頭看 mutex 和 semaphore，mutex 只能限制單一程序進入 critical section，而 semaphore 可以自訂有多少程序可以進度 critical section，就以 binary semaphore 來說，其功能效應等同於 mutex。