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

6月 14, 2006 輔大圖資 5 Comments Edit Copy Download

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顆磁碟：

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

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

位元向量就是使用一連串的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移動距離最長。

[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

權限說明：