[圖資] 作業系統942期末考2 (附參考說明)
[圖資] 作業系統942期末考2 (附參考說明)
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)卻得佔用一整個磁區。
為減少索引磁區浪費的空間,可以藉由縮小磁區空間來解決,但是磁區過小恐怕難以容納大檔案所需要的指標空間,因此有幾個改善的方法。
- 索引磁區連結索引磁區(Linked Scheme):一個索引磁區擺不下,那就連到下一個索引磁區繼續擺
- 多層次索引(Multilevel index):將指標分層存放。開始的索引磁區包含著下一層的數個索引磁區,在這數個索引磁區存放指標。
- 綜合兩種方法(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 | - | 紀錄該檔案的屬性: -:普通檔案 |
2~4 | rw- | 擁有者(owner)的權限 |
5~7 | r-- | 擁有群組(group)的權限 |
8~10 | r-- | 其他人(universe)的權限 |
權限說明:
類型 | 意義 |
---|---|
r | 可讀取 |
w | 可寫入 |
x | 可執行 |
- | 權限被封閉 |
(more...)
Comments