:::

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

6月 15, 2006 11 Comments Edit Post

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
磁區 60 100 190 20 180 40 50
移動 10 40 90 170 160 140 10
累加 10 50 140 310 470 610 620
SSTF
磁區 50 60 40 20 100 180 190
移動 0 10 20 20 80 80 10
累加 0 10 30 50 130 210 220
SCAN
磁區 50 60 100 180 190 (199) 40 20
移動 0 10 40 80 10 9 159 20
累加 0 10 50 130 140 149 308 328
C-SCAN
磁區 50 60 100 180 190 (199) (0) 20 40
移動 0 10 40 80 10 9 199 20 20
累加 0 10 50 130 140 149 348 368 388
LOOK
磁區 50 60 100 180 190 40 20
移動 0 10 40 80 10 150 20
累加 0 10 50 130 140 390 410
C-LOOK
磁區 50 60 100 180 190 20 20
移動 0 10 40 80 10 170 20
累加 0 10 50 130 140 410 430

各排班移動距離排序: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一起運作,他們都是儲存檔案串列資訊的特殊資料。

  位元向量
bit vertor
鏈結串列
linked list
儲存方式 0,1字元陣列 指標(pointer)
複雜度 簡單 複雜
找到可用空間 快,且任意位置都可以找尋 只有開頭磁區快速,其他的得慢慢尋找、鏈結
額外空間 隨著磁碟大小等比例增加 只需要一個地方來儲存開頭磁區的位置,其他的鏈結則存在各個可用磁區裡面
快取 檔案過大便難以快取 可快取加快速度,且可與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 0 RAID 1 RAID 2 RAID 0+1
目的 - 快速 備份 錯誤修正 快速+備份
寫入消耗時間 1 1 / n 1 1 + 同位元計算時間 1 / n (同RAID 0)
安全度 - 1 / n (其中一顆硬碟損壞,檔案就全毀) 2倍 (有第二顆可以隨時備用) 用記憶體偵錯碼(ECC)來修正或重建 2倍 (同RAID 1)
額外空間
(overhead)
→成本
0 0 與儲存資料的空間相同 比RAID 1還少 是儲存資料空間的三倍

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

 

總共11 則留言, (我要發問)

  1. To 2樓匿名,

    咦,不會是SCAN,是LOOK吧
    SCAN會走到底再回頭,可是LOOK不需要走到底就可以回頭的啊

    回覆刪除
  2. 第四題的 look及c-look 再加總的地方,有計算錯誤,以上提醒

    回覆刪除
  3. 大家發現了錯誤在哪裡了嗎?
    答出來的有加分喔!

    回覆刪除
    回覆
    1. 網誌管理員已經移除這則留言。

      刪除
  4. 也太多錯誤了吧
    這樣會誤導很多人!
    請改善

    回覆刪除
  5. To 王鈞禾,

    留給大家找錯誤的喔。

    回覆刪除
    回覆
    1. 請問Fcfs累加答案是610還是620呢

      刪除
    2. 請問Fcfs累加答案是610還是620呢

      刪除
  6. To 王鈞禾,

    我想應該是620。

    回覆刪除
  7. To 王鈞禾,

    我想應該是620。

    回覆刪除

留言工具: