:::

[圖資]作業系統 922期中考 -2

4月 17, 2006 0 Comments Edit Post

九十二學年度第二學期
作業系統 期中考 之二


一、解釋名詞

1. Working set (工作集合)

工作集合(working set)是指在一定的時間中,某個行程(process)所參照(reference)到的分頁數量(pages),其時間同等於參照分頁的次數(a fixed number of page references)。假如在約5個參照分頁次數的時間中,該行程參照到了1 2 2 1 3這幾個分頁。那麼其工作集合為3個分頁,各別為1 2 3。

工作集合是用來預測該行程接下來要使用的需求欄位數量(demand frames),作業系統(OS)依照各個行程的工作集合來分配他們的欄位數量,以避免輾轉現象發生。

2. Thrashing (輾轉現象)

輾轉現象(thrashing)是指行程(process)分頁替換的頻率相當高,於是系統的時間相耗費在輸入輸出(I/O)的動作,CPU的使用率(utilization)低落,作業系統會認為需要增加多工的程度(the degree of multiprogramming),而又將行程加入系統中,每個行程所分配到的實體記憶體又更少,因而惡性循環。當各行程的總需求欄位空間(total demand frames)超過實體記憶體的欄位空間時,便會發生輾轉現象。

3. Dynamic linking (動態連結)

  1. 直到需要執行的時候,才會進行連結動作。當程式要用到系統程式庫(libraries)時,在需要參照(reference)的地方做記號(stub)
  2. 記號stub是用來找尋需要使用的程式庫(libraries),stup將會被取代為該程式庫的記憶體位置,並且執行該程式。作業系統需要確認該程式庫是否在實體記憶體當中。
  3. 有用到的程式資料庫在記憶體裡只會存在一份,而不必每次參照的時候都得複製,因此不會重複。鏈結(linking)的工作只需進行一次
  4. 動態連結特別適合程式庫(libraries)

二、試解釋內部斷裂(Internal fragmentation)與外部斷裂(external fragmentation)的差異。

  1. 斷裂(fragmentation)發生在行程(process)載入記憶體(memory)時,空間分配時發生的問題。
  2. 外部斷裂(external fragmentation)是指記憶體總和剩餘空間雖然足以載入整個行程,但因為剩餘空間被其他行程切割而不連續,所以無法載入行程,浪費記憶體空間。浪費的記憶體多寡,與記憶體選擇配置的演算法相關,也和記憶體空間總量以及行程的平均大小有關。
  3. 有時行程雖然小於記憶體某段連續的剩餘空間(坑洞),但在配置給該行程時,仍將整段空間都要走,以減少記憶體「小碎塊」的情況發生。這種行程額外要求了自己不需要的空間,稱之為內部斷裂(internal fragmentation)。
  4. 外部斷裂是指記憶體空間不連續,而無法配置給行程;內部斷裂是指被額外配置給行程,但實際並未被使用的記憶體空間。兩者相同的地方在於,都有不會被使用,而形同浪費的記憶體空間。

三、請略述處理分頁錯誤的步驟(最好畫圖表示,若以文字描述請將步驟標示清楚)

六個步驟

  1. 檢查TBL裡面需要的分頁的有效‧無效位元是否為1 (0代表尚未載入記憶體、1代表已經載入記憶體)→為0,發生分頁錯誤
  2. 發生分頁錯誤之後,暫停該行程的執行,進入監督模式,交由作業系統操作
  3. 作業系統到硬碟(second storage)去尋找程式(program,尚未在記憶體中執行的程式)所需的該段分頁
  4. 取出該分頁至實體記憶體的可用欄位。如果實體記憶體已經沒有可用欄位,則須先執行分頁替換的動作
  5. 所需分頁寫入實體記憶體之後,再修改分業表當中的有效‧無效位元,將它改成1(有效)
  6. 重新啟動行程,讓他再執行一次分頁要求,因為分頁已經載入,就不會發生分頁錯誤了

四、 以下列分頁參考串列為例︰

1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6

試問對下列分頁替換法而言,將分別產生多少次分頁錯誤?假設分配頁框數為4個頁框

1. LRU:共10次分頁錯誤

 

1

2

3

4

2

1

5

6

2

1

2

3

7

6

3

2

1

2

3

6

分頁表

1

1

1

1

1

1

1

1

1

1

1

1

1

6

6

6

6

6

6

6

 

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

 

 

3

3

3

3

5

5

5

5

5

3

3

3

3

3

3

3

3

3

 

 

 

4

4

4

4

6

6

6

6

6

7

7

7

7

1

1

1

1

未被使用時間

0

1

2

3

4

0

1

2

3

0

1

2

3

0

1

2

3

4

5

0

 

0

1

2

0

1

2

3

0

1

0

1

2

3

4

0

1

0

1

2

 

 

0

1

2

3

0

1

2

3

4

0

1

2

0

1

2

3

0

1

 

 

 

0

1

2

3

0

1

2

3

4

0

1

2

3

0

1

2

3

步驟

  1. 先檢查分頁表當中,是否有與待載入的分頁相同編號的分頁
    →如果有,將之未被使用時間設為0,停止檢查
    →如果沒有,繼續檢查
  2. 檢查未被使用時間最長的分頁,將之替換為待載入分頁,未被使用時間設為0
  3. 其他未檢查的分頁,未被使用時間各自加1

分頁錯誤,載入的分頁 (上一階段當中,未被使用時間最長的一個分頁)

  • 分頁表:替換成被載入的分頁
  • 未被使用時間:歸零

檢查到已經有載入的分頁

  • 分頁表:不變
  • 未被使用時間:不變

2. FIFO:共14次分頁錯誤

 

1

2

3

4

2

1

5

6

2

1

2

3

7

6

3

2

1

2

3

6

分頁表

1

1

1

1

1

1

5

5

5

5

5

3

3

3

3

3

1

1

1

1

 

2

2

2

2

2

2

6

6

6

6

6

7

7

7

7

7

7

3

3

 

 

3

3

3

3

3

3

2

2

2

2

2

6

6

6

6

6

6

6

 

 

 

4

4

4

4

4

4

1

1

1

1

1

1

2

2

2

2

2

載入時間

0

1

2

3

4

5

0

1

2

3

4

0

1

2

3

4

0

1

2

3

 

0

1

2

3

4

5

0

1

2

3

4

0

1

2

3

4

5

0

1

 

 

0

1

2

3

4

5

0

1

2

3

4

0

1

2

3

4

5

6

 

 

 

0

1

2

3

3

4

0

1

2

3

4

5

0

1

2

3

4

步驟

  1. 先檢查分頁表當中,是否有與待載入的分頁相同編號的分頁
    →如果有,停止檢查
    →如果沒有,繼續檢查
  2. 檢查載入時間最長的分頁,將之替換為待載入分頁,載入時間設為0
  3. 其他未檢查的分頁,載入時間各自加1

分頁錯誤,載入的分頁 (上一階段當中,載入時間最長的一個分頁)

  • 分頁表:替換成被載入的分頁
  • 載入時間:歸零

檢查到已經有載入的分頁

  • 分頁表:不變
  • 載入時間:不變

Second=Chance Algorithm:共10次分頁錯誤

 

1

2

3

4

2

1

5

6

2

1

2

3

7

6

3

2

1

2

3

6

分頁表

1

1

1

1

1

1

1

1

1

1

1

1

1

6

6

6

6

6

6

6

 

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

 

 

3

3

3

3

5

5

5

5

5

3

3

3

3

3

3

3

3

3

 

 

 

4

4

4

4

6

6

6

6

6

7

7

7

7

1

1

1

1

載入時間

0

1

2

3

4

5

0

1

2

3

4

0

1

0

1

2

3

4

5

6

 

0

1

2

3

4

0

1

2

3

4

0

1

2

3

4

0

1

2

3

 

 

0

1

2

3

0

1

2

3

4

0

1

2

3

4

0

1

2

3

 

 

 

0

1

2

3

0

1

2

3

4

0

1

2

3

0

1

2

3

參考位元

0

0

0

0

0

1

0

0

0

1

1

0

0

0

0

0

0

0

0

1

 

0

0

0

1

1

0

0

1

1

1

0

0

0

0

1

0

1

1

1

 

 

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

0

1

1

 

 

 

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

步驟

  1. 先檢查分頁表當中,是否有與待載入的分頁相同編號的分頁
    →如果有,則將該分頁的參考位元設為1,停止檢查
    →如果沒有,繼續檢查
  2. 檢查載入時間最長的分頁
  3. 如果載入時間相同,則用FIFO依照載入先後排序
  4. 檢查的分頁的參考位元如果是1,將之設為0,載入時間設為0,繼續檢查下一個
  5. 檢查的分頁的參考位元如果是0,將之分頁替換成待載入的分頁,參考位元設為0,載入時間設為0,停止檢查
  6. 其他尚未被檢查到的分頁,其載入時間增加1

分頁錯誤,載入的分頁

  • 分頁表:替換成被載入的分頁
  • 載入時間:歸零
  • 參考位元:設為0

檢查到已經有載入的分頁

  • 分頁表:不變
  • 載入時間:不變
  • 參考位元:設為1

受檢查,給予第二次機會的分頁

  • 分頁表:不變
  • 載入時間:歸零
  • 參考位元:歸零

五、略述記憶體管理中需求分頁(Demand Paging)的做法

  • 需求分頁的基本道理是:「直到需要執行的時候,才將分頁載入記憶體」。
  • 在分頁的作法中,程式(program,當程式在執行狀態的時候,稱為行程或程序(process))會被分割成大小相等的分頁,這時程式是被擺置在次儲存裝置(second storage),如硬碟當中。當程序(process)執行時遇到須要使用的部份分頁,才去載入分頁。
  • 需求分頁使用了分頁表來記錄該分頁是否已經載入記憶體。分頁表基本上有三個欄位:分頁編號、分頁實體記憶體位置、分頁已載入的有效-無效位元(valid-invalid bit),其中有效-無效位元是用來紀錄分頁是否已經載入記憶體。如果未載入為0,表示該分頁上在磁碟當中;已經載入為1,表示已經存在於記憶體當中。
  • 程序的需求分頁動作會先檢查分頁表的有效-無效位元,如果為1,則正常執行;如果為0,則發生分頁錯誤。分頁錯誤時的處理,可以參考第三題。

六、下列程式設計技巧和結構中,哪些對需求分頁的環境有利,哪些則相對的顯得不利?並請簡單敘述你的理由。

  • 堆疊(stack)
  • 循序搜尋法(sequence search)
  • 純程式碼(pure code)
  • 向量運算(vector operations)
  • 間接定址(indirection)

首先,需求分頁的特色在於將程序執行時所需要的記憶體空間降至最低,因為只載入需要的分頁。但是當記憶體空間不足時,則需要執行花費時間的分頁替換動作(page replacement)。減少分頁替換的情況發生,也就是程序執行時,重覆使用同一個分頁;其次是按照順序地執行分頁,這些都是有利於需求分頁環境的結構。相對的,不按照順序、跳來跳去的程式結構,將會時常需要載入位置差異大的分頁,而不利於需求分頁的環境。

  • 堆疊(stack):堆疊是一種先進後出的資料結構。例如有A B C D這四個資料依順序進入堆疊,則接下來出來的則是D C B A。從執行順序來看,會變成A B C D D C B A。其中存取A的兩個時間差距遠,表示時常要載入位置差異大的分頁,因此不利於需求分頁的環境。
  • 循序搜尋法 (sequence search):這是一種用於搜尋的演算法。例如要在A B C D當中檢查D的位置,則程式會從A B C D一個一個依序地檢查。其使用的分頁是有順序性的,因此利於需求分頁環境。
  • 純程式碼 (pure code):程式碼不可被其他程式修改,而用來重複執行的程式碼稱之,又稱為共同程式碼。因為該段程式碼(等於分頁)重複使用,因此有利於需求分頁環境。
  • 向量運算 (vector operations):向量是指具有方向的量單位,如往北走20公里,此為向量的表示。在電腦運算中,單向、平面或立體圖形的向量通常用一維、二維或三維矩陣表示,而向量的運算便是矩陣之間的運算。程式中常使用陣列的方式來表示矩陣,而程式語言對陣列的Column-major(欄優先)還是Row-major(列優先)分配分頁的方式,與程式中先執行列還是執行欄的差別,便會影響到分頁錯誤的發生頻率。當分配分頁方式與執行順序相同時,會利於需求分頁的環境;反之,則是不利於需求分頁。

0 意見:

留言工具: