:::

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

6月 14, 2006 5 Comments Edit Post

92.6.13 第二學期
作業系統期末考

以下解答除了參考課本、網站與自己的記憶之外,也要感謝一些同學的協助。有些從同學那邊看到的錯誤觀念,都已經在下面修正了,有空的話,請務必好好讀一讀吧。

不在這次考試範圍內的東西,或是與老師上課講的範圍有些差別的東西,我則是修改題目或是跳過不作答。

再強調一次,以下的說明僅作為參考,可能(或許、絕對、一定)會有錯誤,請大家斟酌使用。


6/15 10:20 修正RAID 1的安全度

6/15 9:39 修正電梯演算法,補完權限說明


一、解釋名詞

[1] 置換空間(swapping space)
(這次有可能會考)→置換空間(swap-space)

置換空間管理是另一種作業系統中的一個低階工作(屬於硬體方面的操作)。虛擬記憶體把磁碟空間當做主記憶體的延伸。因為磁碟存取速度遠不及於記憶體存取,使用置換空間其實會降低系統的效能,拖垮存取的效率。置換空間主要是為了提供虛擬記憶體系統的大量存取。置換空間在不同作業系統當中會有不同的表現方式,取決於記憶體管理演算法。置換空間一般是大於實體記憶體的兩倍,以允許做到雙重緩衝(double buffer)的功能。

(管理方法...上課似乎沒有講的很多,我有印象的就是這些。)

[2] 記憶體應對I/O (memory-mapping I/O) (13.2)

[3] 週期偷取 (cycle stealing) (13.2.3,之前也有講過)


(必考)二、(12.4)

[1] 檔案系統使用哪三種方式來配置磁碟空間?試比較三者的優缺點?

1. 連續配置(contiguous allocation):

連結配置是將檔案位址以線性的方式一個接著一個存放。連續配置檔案是依據磁碟位址(adress)與長度(length),而目錄就是指示檔案的開始磁區(block)位置與長度。

連續配置的優點是簡單易處理,也可以做到直接存取。缺點是無法解決外部斷裂(external fragmentation,剩餘空間被切斷,而無法有效利用)。因為無法預測新增時的檔案大小,因此得考慮外部斷裂的問題。隨著檔案的新增與刪除,也會將剩餘空間切離的支離破碎。為了解決外部斷裂的問題,可以使用磁碟重組程式(repacking routine),但是代價是時間的花費。

2. 串列配置(linked allocation):

串列配置解決了連續配置的問題,每個檔案都只是到下一個磁區的連結,而各個磁區可以分散在磁碟當中任何地方。目錄只要指到開始的磁區,便能從該磁區找到下一個磁區,最後湊齊完整的檔案。

串列配置的缺點在於,只能循序存取(sequential-access)檔案。他必須從第一個磁區一個一個串連到最後一個磁區,而每次磁碟讀取與磁頭搜尋都要花費時間。串列配置不支援直接存取檔案,不能從檔案中間開始讀取。

另一個缺點在於指標的佔用空間造成檔案額外的負擔(overhead)。

串列配置的方式也不安全,當其中一個磁區壞掉的時候,就無法找到他完整的檔案。可以使用雙重連結表(double linked list)來改善,在每個磁區裡面儲存檔名與相關的磁區編號,但是這會造成更多的額外負擔。

串列配置最重要的是使用了檔案配置表(file-allocation table,FAT),取代把指標分散在各個磁區的作法,FAT是獨立一個表格,存放著各磁區的編號與指標。FAT改善了讀取的速度,也可以藉由快取(cache)加速,但FAT也成為整個磁碟最大的弱點所在。

3. 索引配置(indexed allocation):

索引配置的方式,是在檔案的索引磁區(index block)記錄著該檔案所有磁區的位置。

索引配置可以支援直接存取(direct access,從檔案任意地方開始讀取),而且可以解決外部斷裂。但是問題在於浪費空間(wasted space),索引磁區只包含少量的指標(pointer)卻得佔用一整個磁區。

為減少索引磁區浪費的空間,可以藉由縮小磁區空間來解決,但是磁區過小恐怕難以容納大檔案所需要的指標空間,因此有幾個改善的方法。

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

索引配置會遇到跟串列配置一樣的效能問題,雖然索引磁區可以用快取加速,但檔案依然是分散在磁碟的各部份,為了湊齊完整檔案,必須花費時間移動讀寫頭到磁柱各個地方湊齊檔案。

[2] 檔案較大且須隨機存取,最好用哪一個方式?

連續配置會有外部斷裂的問題,因此不適合存放較大的檔案。隨機存取(direct access)必須能夠從檔案中間開始存取,串列配置也不適合。因此能夠避免外部斷裂且可由索引區段從中間存取檔案的索引配置(indexed allocation)較為適合。


三、試解釋遮罩中斷 (maskable interrupt) 與非遮罩中斷(non-maskable interrupt),他們的用途又各為何?(13.2.2)


四、何謂磁碟陣列?試比較RAID 0與RAID 1二種磁碟陣列規格的優劣。

RAID(Redundant Arrays of Inexpensive Disks,不昂貴磁碟的過剩陣列)是一種改進資料傳輸速度與安全性的方法。藉由將檔案分割並行(parallel)寫入多顆磁碟,因此各個磁碟的存取時間將會平分並縮短,這是RAID 0的原理。此外,也有將相同的資料複製存入多顆磁碟,以增加資料儲存安全性的作法,這是RAID 1的原理。以下以表格比較RAID 0與RAID 1的規格優劣,假設這兩個RAID都使用了n顆磁碟:

  一般磁碟 RAID 0 RAID 1
速度 1 1/n (寫入的資料平分而減少)
1 (寫入的資料都一樣多)
磁碟損壞 1 1/n (壞掉一個磁碟就檔案全毀) 2倍 (有第二顆磁碟可以取代)
偵錯與修正 (RAID 2)以上才能做到偵錯與修正
最低磁碟數量 1 2 2

 


五、請簡單說明在磁碟可用空間管理的方法中,如何利用位元向量的方法進行管理。

(沒有印象老師有講...)

位元向量就是使用一連串的0與1的陣列,紀錄每一個磁區可用或是不可用。1表示可以使用(free),0表示使用中(allocated)。舉例來說,如果編號2、4、5、8的磁區是可以使用的,那麼陣列的表示法就是:(注意,第一個磁區編號是0)

001011001......

優點是簡單且可以快速找到開始或一段連續的可用區段,但是因為位元向量需要頻繁存取,所以只有在記億體當中才會有效率。


六、記憶體磁碟(Ram disk)和快取(cache)都使用了系統的主記憶體,試述這兩種方法的差異。(13.4.3)
(老師只有提到Ram disk的構造,並沒有特別去說明cache)→請問記憶體磁碟(Ram disk)的特色?

記憶體磁碟其目的是藉由記憶體遠遠超越硬碟的高速存取能力,加快電腦的運作效率,但是缺點是記憶體磁碟沒有電的時候資料就會消失(揮發性),而且記憶體成本較高。

記憶體磁碟有兩種方式:

第一種方式是從主記憶體當中切割一部份作為磁碟使用,當主記憶體夠大的時候,可以透過軟體來切割模擬成一顆硬碟,以存放需要存取頻繁的檔案,曾經聽過有人拿來作為BT(bittorrent)的儲存區,以避免早期BT對硬碟傷害大的弱點。不過這種方式切割出來的可用空間不會很大,因此較不實用。

另一種則是使用記憶體磁碟卡(RAM disk card),他是一張可以安裝數條記憶體的電路板,藉由PCI或其他介面連結電腦,可以模擬成一顆具有高速存取能力的磁碟。現在也有內建鋰電池的記憶體磁碟卡,即使關機之後資料也不會馬上消失。


(必考)七、磁碟排班法則 1. FCFS、2. SSTF、3. SCAN、4. C-SCAN、5. LOOK、6. C-LOOK中

[1] 假設某磁碟共有200個磁柱,若有連續之讀寫要求 110, 60, 120, 130,70, 110, 130,請問上述各法則中讀寫臂移動距離最多的是哪一個法則?(磁頭開始於第50軌,預設方向為增加的方向)

FCFS
磁區 50 110 60 120 130 70 110 130
移動 0 60 50 60 10 60 40 20
累加 0 60 110 170 180 240 280 300
SSTF
磁區 50 60 70 110 110 120 130 130
移動 0 10 10 40 0 10 10 0
累加 0 10 20 60 60 70 80 80
SCAN
磁區 50 60 70 110 110 120 130 130
移動 0 10 10 40 0 10 10 0
累加 0 10 20 60 60 70 80 80
C-SCAN
磁區 50 60 70 110 110 120 130 130
移動 0 10 10 40 0 10 10 0
累加 0 10 20 60 60 70 80 80
LOOK
磁區 50 60 70 110 110 120 130 130
移動 0 10 10 40 0 10 10 0
累加 0 10 20 60 60 70 80 80
C-LOOK
磁區 50 60 70 110 110 120 130 130
移動 0 10 10 40 0 10 10 0
累加 0 10 20 60 60 70 80 80

可知FCFS移動距離最長。

[2] 請簡單說明哪一個演算法最適合我們平常所搭乘的電梯使用的理由?

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

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

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

[3] 當作業系統對於系統讀取均勻分布於各磁軌時,試分析LOOK與C-LOOK排程法的性能?

LOOK在磁區頭尾來回走,移動順序為:頭→中→尾→中→頭→中→...的現象,可以看出中間磁區讀取頻繁。

而C-LOOK則一直往同一方向讀取,移動順序為:頭→中→尾→頭→中→尾→...,各磁區平均讀取。

因此在需要均勻地來回各磁軌時,C-LOOK會有較好的效能。


八、請清楚解釋及說明個別屬性的意思與操作指令

-rw-r--r-- 1 lyvia music 196 Jul 11 2000 test.txt

權限:本人可以讀寫、不能執行。同群組及其他人只能讀,不能寫入及執行

擁有者:lyvia/所屬群組:music

檔案大小:196 byte

創造時間:2000年6月11日

檔名:test.txt

[1] lyvia music 這兩個檔案屬性代表何意?若要更改檔案屬性各需用哪一個指令?

各代表該檔案所屬的ID以及所屬的群組名稱。改變擁有者指令為chown (change owner),改變群組使用chgrp (change group)

[2] -rw-r--r-- 請解釋該檔案屬性的意思,若要更改屬性需用哪一個指令?

擁有者可讀寫,其他人只能讀。更改屬性用chmod

位置 範例 說明
1 -

紀錄該檔案的屬性:

-:普通檔案
d:目錄
l:連結

2~4 rw- 擁有者(owner)的權限
5~7 r-- 擁有群組(group)的權限
8~10 r-- 其他人(universe)的權限

權限說明:

類型 意義
r 可讀取
w 可寫入
x 可執行
- 權限被封閉

 

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

  1. 你知道嗎,我看到這篇的時候差點感動到噴淚...Q_Q

    請讓我叫你一聲神 <0>

    回覆刪除
  2. 太感人了~布丁大人會不會太強
    辛苦你啦
    一直追著你問OS
    好心會有好報的!!!
    "恭喜大三陳勇汀同學通過國科會計畫申請案"
    看到系上公告就為你開心呀

    回覆刪除
  3. 感謝布丁大 拜謝m(_ _)m

    恭喜布丁大 通過國科會的研究申請案喔

    可喜可樂 可喜可樂

    回覆刪除
  4. 布丁...圖資系有你真好!!

    回覆刪除