[圖資] 作業系統942期末考 (附參考說明)

6月 15, 2006 輔大圖資 18 Comments Edit Copy Download

92.6.16 第二學期
作業系統期末考 (附參考說明)

以下多為依照自己的記憶寫的參考用解答，希望能夠幫助同學釐清概念。(當然，也是會有幫倒忙的時候)

一、磁碟陣列排班法則 1. FCFS　2. SSTF　3. SCAN　4. C-SCAN　5. LOOK　6. C-LOOK　中

[1] 略述SCAN與C-LOOK兩個法則的作法？

SCAN排班表是從開始磁區往同一方向掃描到磁區尾端，改變方向一路掃回開頭，掃到開頭再折回去。

C-LOOK則是從頭到尾就遵照一個方向掃描，從頭到最靠近尾端的一個要求磁區，然後再返回最近靠開頭的一個要求磁區開始，往尾端掃描

[2] 哪一個法則有可能會造成飢餓的問題？(請簡單說明)

SSTF最可能造成飢餓(starvation)。飢餓是指要求的指令永遠無法執行，必須無止盡等待的情況。SSTF無視順序地只先服務最近靠近的要求，因此太遠的要求磁區會很難有機會可以執行到，可能造成肌餓。

[3] 哪一個演算法最適合我們平常所搭乘的電梯使用？(請簡單說明)

電梯的演算法是LOOK，就這樣。

不考電梯，但應該會有同樣類型的應用題型出現。推測較可能會考的有：SSTF(25%，最短路徑，可能會發生飢餓)、SCAN(20%，掃到底)、C-SCAN(10%，掃到底，單方向圓圈循環)、LOOK(35%，掃到最靠近底)、C-LOOK(10%，掃到最靠近底，單方向圓圈循環)

以上推測可能出題的%來自於實際應用最可能的情況，也就是說，LOOK排程最容易套用在現實生活的情境；其次是SSTF的最短路徑；SCAN則是LOOK改良的前身，適用於必須強迫走到底的狀況；而其他C-的演算法，因為必須為圓圈循環的模式，所以比較難以看到應用在現實生活；相對的，如果有圓圈循環的特徵出現，那麼極可能是C-的兩種演算法之一喔！

以上是無責任推測，只要搞懂這幾種排班表，遇上問題時，便可以很快地想到應用的方法囉。

[4] 假設某磁碟共有200個磁柱(注意，編號是從0到199)，若有連續之讀寫要求 60, 100, 190, 20, 180, 40, 50，請問上述各法則中讀寫臂移動距離最多的是哪一個法則？
(假設開始是位於50，方向為由小到大，兩者距離相等的時候，以移動方向為準←這些考試的時候都要舉手問老師喔！)

(不用算都知道是FCFS...)

各排班移動距離排序：FCFS(620) > C-LOOK(430) > LOOK(410) > C-SCAN(390) > SCAN(330) > SSTF(200)

二、試解釋為什麼SSTF法則似乎對中間磁柱較有興趣，而對極內或極外圈的磁柱較為不便？

SSTF會優先移動到距離現在最接近的要求磁柱。在要求磁柱呈現均勻分配，極內、中間、極外磁柱皆有的情況下，中間磁柱便類似統計學上的中位數，他與所有要求的磁柱與中位數的距離為最短，因此在SSTF的規則下，中間磁柱會有較高的機會被執行，感覺上會偏中間磁柱。

三、在磁碟可用空間管理的方法中，試比較位元向量(bit vertor)與鏈接串列(linked list)的優劣？

位元向量是把磁碟可用(free)的空間以一連串的0或1表示。優點是簡單且可以快速找到開始或一段連續的可用區段。因為需要時常存取的關係，擺在記憶體當中才能發揮效率，不過這牽扯到磁碟大小影響位元向量的長度，大型磁碟的位元向量會佔用記憶體太多位置。

鏈結串列是將所有可用磁區以指標的方式連結在一起，而將這整串的開頭磁區儲存在特別區域並且擺置在記憶體當中快取。然而，這樣是很難去追溯完整的清單，系統必須執行長時間的I/O (輸入輸出)動作來找尋每一個鏈結的磁區。不過還好，大多時候作業系統只會需要一個可用磁區，就是那個快取中的開頭磁區。鏈結串列可以搭配FAT一起運作，他們都是儲存檔案串列資訊的特殊資料。

四、在磁碟檔案配置中何謂索引區段(index block)？

索引區段是索引配置(indexed allocation)裡面使用的特別磁區。在索引配置中，每個檔案都有一個索引區段，記錄著這個檔案各個部份的指標位置。即使只有紀錄小型檔案，索引區段依然得佔用一整個磁區，因此發展出縮小磁區大小以避免浪費索引區段的方法，這又得考慮到當檔案過大、必須存放的指標數量超過單一磁區大小時的問題。解決的方法有三種：

1. 索引磁區連結索引磁區(Linked Scheme)：一個索引磁區擺不下，那就連到下一個索引磁區繼續擺
2. 多層次索引(Multilevel index)：將指標分層存放。開始的索引磁區包含著下一層的數個索引磁區，在這數個索引磁區存放指標。
3. 綜合兩種方法(Combined scheme)：索引磁區中，前12個指標指到資料本身，後3個則指到單層、雙層、三層索引磁區

五、實作磁碟檔案目錄的資料結構採用雜亂表格(hash table，又稱雜湊表格)有何優點？

雜湊表格是指儲存檔案目錄的資料結構是採用「陣列(array)」，也就是一個固定長度、分成很多格子，每個格子都儲存資料的結構。雜湊的意思是，當資料要儲存或讀取時，都會經過一個特殊的函數(function)，以算出一個位置。因為函數計算的時間是固定的，不像普通的搜尋方法會隨著檔案大小而影響搜尋時間。所以雜湊演算法具有時間固定、簡單的優點。

缺點是需要考慮到碰撞(collision，多對一函數的結果，兩個不同的輸入卻有相同的輸出)的處理。

六、RAM磁碟與磁碟快取間的差異？(13.4.3)

七、何謂檔案控制區段(File Control Block)

在邏輯邏輯系統管理當中，檔案結構是由檔案控制區段來維護。檔案結構區段包含著檔案的資訊，包括擁有者、擁有群組、權限，以及檔案內容的位置。

八、試比較RAID 0、RAID 1與RAID 2三種磁碟陣列規格的差異與優劣？
→ 比較RAID 0、RAID 1、RAID 2與RAID 0+1

n為磁碟個數

※注意，RAID 2不是漢明碼、不是CRC，而是記憶體類型錯誤偵錯碼組織(memory-style error-correcting-code(ECC) organization