---

※ 本文轉錄自 abc1231qa 看板

---

聽首歌提提神

---

> 11/19

> 1. What is fragmentation?
-Internal fragmentation:
Page切得太大塊,而Process占的空間沒這麼大,
留下無法讓其他process用的記憶體碎片(Page"內部"的碎片)
-External fragmentation:
使用Segmentation的狀態下, 某些Process執行完後留下大小不一的記憶體碎片


> 2. Dynamic linking的好處?
-Dynamic Loading:當副程式被叫用到時，程式才載入到記憶體中；
 運作方式：一開始只有主程式被載入，當副程式被呼叫時，系統檢查程式是否已在記憶
 體中，若不在，則利用可重新定位linker來將此副程式載入，然後將控制權交給這個
 副程式。
-Dynamic Linking：Dynamic loading是執行時才「載入」，Dynamic Linking是執行時才
「連結」。

載入跟連結的差異是，載入是指該段程式還不在記憶體中，而連結則是已在記憶體中

> 3. What is Address binding?
Address binding when :
-Compile time
 如果此時知道程式要擺在那裡，就產生absolute code，否則就產生relocatable code
 例如.com檔是absolute（絕對）的，而.exe可以是relocatable
-Load time
 程式編譯要產生重定碼，在載入的時間才會有位址
-Execution time
 如果執行的時候會被移動到記憶體另外的地方那就要再執行的時候才載入

Logical(virtual) address and Physical address:
 通常前兩種bind的邏輯位址和實體位址是一樣的，第三種則不同。由MMU（Memory
 management unit）管理


> 11/26

> 1. How paging works?
實際記憶體被分成許多固定大小的區塊 (Frames)
邏輯記憶也被分成許多「同樣大小」的區塊 (Pages)
                                Physical Addr.
 Logical Addr. -> Translation -----------------> Page Table -> Physical Memory
  (virtual)

要執行一個程式只要找到足夠的frames即可.


> 2. Segmantation v.s. Paging 各別優缺點是?
-Segmentation
優點: 1) 沒有internal fragmentation
      2) 可設定Segment為Read only，Segment protection較容易作
缺點: 1) 可能有external fragmentation  (見最上面第一題)

-Paging
優點: 1) 沒有external fragmentation
      2) 可run-time binding
缺點: 1) 可能有internal fragmentation (最後一個page未必會跟frame一樣大)
      2) logical -> physical太花時間  (解法: TLB)

> 3. Page fault如何處理?
當所有可用的frame都滿了, 還有新的程式(page)要進來怎辦 - 把舊的frame替換掉
Page replacement solutions:

-FIFO:
 First in, first out

-Optimal:
 要置換frame時,選擇會在最久之後才被用到的frame為victim
 實作上有困難, 因為無法預知未來

-LRU(Least Recently Used)
 把最久沒被用到的frame換掉
 實作: 1) counter 2) stack

-LFU(Least Frequently Used)
 把最少被用到的frame換掉
 實作: counter (但剛進的frame , counter數字會很低, 可用aging解決, 就是每過一段
                時間把counter shift 1 bit)

-MFU(Most Frequently Used)
 同上, 把最常被用到的換掉

-Second Chance        (這個我看不太懂)
 新增一個reference bit, 代表這個frame是否有被參考到
 以FIFO為基礎，選擇一個FIFO頁面後，檢查reference bit，如果為0，就替換這個頁面
，若為1，則修改為0，但這次不做替換。
 如果某個頁面經常被使用到，參考位元就會一直保持在1。
 改進：用一個circular queue。

-Enhanced Second Chance (Not used Recently)
 同上, 再新增一個modify bit, 代表這個frame是否有被修改過
 (reference bit , modify bit)
 (0,0)沒用，沒改
 (0,1)沒用，有改
 (1,0)有用，沒改
 (1,1)有用，有改
 替換的優先順序為上列四項由上而下

-Random
 隨便亂換


> 12/3

> 1. Second chance algorithm如何運作?
 看上面

> 2. What is thrashing? 為何會發生Thrashing? 如何處理?

-一個Process如果page replacement用的時間比執行時間還多,就表示它正處於Thrashing
 狀態.

-Thrashing 原因
 1)在multiprogramming的環境下，採用global page replacement algorithm(即不管替
   換的frame屬於那個process，都一律可以替換)
 2)執行中的process需要載入未載入的page，因此發生page fault，但frame都滿了，所
   以要執行page replacement
 3)輪到下一個process執行，恰好它要用的page被換掉了，於是發生page fault，然後進
   行page replacement
 4)由於process都花時間在page fault、page replacement上，所以CPU的使用率會降低
   ，於是CPU提高multiprogramming的degree，執行更多process
 5)page fault、page replacement更嚴重→Thrashing現象

(Degree of multiprogramming: 同時能執行的Process數目)

-Handling Thrashing:
 1) 局部替換演算法:
    如果process正發生thrashing，則此process不能再從別的process取得frame，在做
    page replacement時，能對自已使用到的page做置換。
    這樣可以把Thrashing限制在局部的範圍內。
    (這條老師好像沒講)
 2) Working Set Model:
    很難文字解釋, 有空再找圖
 3) OS設定page fault 比例的上、下限，若process的page fault 比例過高，OS就多分
    一點frame給process；若太低，則搶走一些，
    須配合global allocation跟 avaiable frame pool

> 12/10

> 1. What is file?

> 2. 為甚麼使用檔案之前要先"open" ?
前兩題不知該如何回答

> 3. Directory Structure有哪些? 各別的優缺點是?
1)可將一個磁碟分割成兩種目錄系統(Partition)，也可將兩個磁碟合併成為一個目錄系
  統(Volume)
2)Single level Directory：只有一層
3)Two Level Directory：每個使用者擁有自己的檔案目錄
4)Tree Structure Directory
5)Acyclic Graph：
  提供共用目錄及檔案的能力，共用有兩種實作方法
　a.Link實作
　b.Duplicate directory entries ：把相同的目錄複製，不易維持一致性。

--
Open-file-table:
系統的表格，紀錄所有開啟檔案的資訊而，每一個Process有自己的per-process table，
其中有一個指向Open-file table的指標，
此外表中對每一個檔案通常會有一個open count，刪除時-1開啟時+1，當刪除=0時才把它
從table中移去。


--
 ◤◥ Origin:  東華資工˙雲蹤月湖  bbs.csie.ndhu.edu.tw
 ◣◢ Author: silveriii 從 114-44-211-1.dynamic.hinet.net 發表
 ▂█ Modify: silveriii 於 2010/01/13 Wed 19:54:02 修改
→ silveriii 推：順便徵你不要的正規課本                               10/01/13
→ TZUKI 推：DoG神                                                    10/01/13

--
※ 來源: DISP BBS (http://disp.twbbs.org)
※ 作者: abc1231qa  來自: 134.208.40.177  時間: 2010-01-13 21:57:02
※ 編輯: abc1231qa  來自: 134.208.40.177  時間: 2010-01-13 21:58:43

--
※ 來源: DISP BBS (http://disp.twbbs.org)
※ 作者: uefangsmith  來自: 123.110.129.39  時間: 2010-01-14 00:49:15
※ 編輯: uefangsmith  來自: 123.110.129.39  時間: 2010-01-14 00:50:23