iT邦幫忙

0

【小黑馬作業系統教室】(20) (Ch12) Mass-Storage Structure (大量儲存裝置結構)

嗨嗨,大家好,我是心原一馬,
這章節最重要的兩個概念大概是
「磁碟排程演算法」(Disk Scheduling Algorithm)及「RAID」了,
話不多說,進正文吧。

基礎概念-光碟

使用光碟來儲存資料,
大概在十年前還很流行,
譬如說以前有DVD player,
CD player之類的,可以用來看電視劇或是聽音樂。
電腦也有個光碟機,
以前單機遊戲流行的年代,
也可以買遊戲光碟來玩。

不過,現代網路發展的速度非常快,
網際網路的連線遊戲也漸漸取代了單機遊戲光碟,
現代也有youtube可以很方便的看影集或聽音樂,
感覺光碟愈來愈少見了,
估計有一天這個章節會從作業系統課本進入歷史課本中。

https://ithelp.ithome.com.tw/upload/images/20200105/20117114iyjSaVukXY.png

圖示中,Track是光碟的一圈,
Sector,track的一小段。
據老師所說,
光碟圓盤轉動相當快,每秒可以達到3600~7200轉,
真正極慢的是磁頭在內圈與外圈之間的移動。

disk scheduling

由於磁頭在內圈與外圈之間的移動是很慢的,
因此磁頭所移動的距離也就大概與讀取資料所需的時間成正比。
disk scheduling講的就是說給你一串資料的位置,
希望儘可能設計出一種策略,
讓磁頭所移動的距離愈小愈好。
(這個問題其實跟「搭電梯演算法」很像)

譬如說程式要讀取的資料位置依序分別為: 98, 183, 37, 122, 14, 124, 65, 67(位置範圍0-199),
磁頭初始位置(Head pointer)在 53的位置。

你可以跟搭電梯問題聯想在一起,
假設在一棟有0~199層的大樓,
電梯依序被按了98, 183, 37, 122, 14, 124, 65, 67樓的按鈕,
那麼電梯該如何走較有效率呢?

常見的有以下六種方法:

一、FCFS (First-Come-Frist-Served)

這個策略非常的單純,
就是先發出的請求會先處理,
但有可能效率不佳。
以此問題為例: 拜訪順序依序為98, 183, 37, 122, 14, 124, 65, 67,
走過的距離是640。
https://ithelp.ithome.com.tw/upload/images/20200105/201171149Ney2V3SYn.png

二、SSTF (Shortest-Seek-Time-First)

此方法為優先讀取當前最短距離的資料,
以下是本例的執行結果:
https://ithelp.ithome.com.tw/upload/images/20200105/20117114KlkBwfeuB8.png

但SSTF有個缺點,就是可能會產生starvation(有些請求一直沒被處理到)。
以電梯問題來想,好比說電梯本來在三樓,
住在一樓跟二樓的居民一直不斷按電梯,
那麼因為距離較近的關係,電梯就會不斷在一樓跟二樓之間跑,
那住在99樓的居民可能就會一直等不到電梯。

三、SCAN Scheduling

電梯會來回在0樓~199樓之間移動,
據說電梯就是用這種演算法,
避免有人一直等不到電梯。
https://ithelp.ithome.com.tw/upload/images/20200105/20117114GRQdDP7d6V.png

四、C-SCAN Scheduling

方法前面加「C-」(circular)表示只有單向的意思,
磁頭只往單個方向移動,
好比說電梯只有往上走,
當電梯到199樓的時候,
可以瞬間回到0樓往上走了。
https://ithelp.ithome.com.tw/upload/images/20200105/20117114lYyOPzemfK.png

五、LOOK and C-LOOK Scheduling

其實LOOK 和 C-LOOK排程法跟SCAN 和 C-SCAN非常相似,
差別在於SCAN 和 C-SCAN總是會走到底,
而LOOK 和 C-LOOK走到最後一個請求時即折返,
譬如以下是以C-LOOK算法處理98, 183, 37, 122, 14, 124, 65, 67的結果:
(到183樓時瞬間返回14樓)

https://ithelp.ithome.com.tw/upload/images/20200105/20117114W0bStMd96W.png

RAID(Redundant Arrays of Inexpensive Disks)

RAID是本章的第二個重點,
一般來說可以是「Redundant Array of Independent Disks」(獨立磁碟備援陣列)
或「Redundant Array of Inexpensive Drives」(低價硬碟備援陣列),
兩種說法都有人用,
簡單來說,RAID就是把多個硬碟組成一個硬碟來使用,
以帶來比單獨使用一個硬碟更多的「容量、速度、及安全性」。
目前有RAID0~RAID6,六種架構,
RAID0~RAID6並不代表等級高低,只是代表幾種不同的需求。

RAID0: striping

實作: 單純將資料切割存放到多個硬碟中(不重複存放)
優點: 沒有空間浪費,效能極高
缺點: 沒有安全性,若硬碟一部分壞了,整個硬碟便無法讀取。

RAID1: mirroring

實作: 使用兩個硬碟,將資料備份兩份一模一樣至兩個硬碟中
優點: 安全性高,任何一個硬碟壞掉都救的回來,適用於完全不能出錯的資料備份
缺點: 空間浪費50%

RAID2, 3, 4

據說這幾種RAID一直都不太流行就是了…
RAID2是以一種叫「Hamming code」的方式修正資料,
由於方法較複雜較少人做。
RAID3, 4以「Parity bit」修正資料。

RAID5: Distributed Parity bit

RAID 5 是一種儲存效能、資料安全和儲存成本兼顧的儲存解決方案,
成為較普及的RAID,
與RAID4相比,
將Parity bit分散儲存在n個硬碟中,
可以有較好的效能。

RAID6

與RAID5相比,多儲存了一些資訊,
可容許兩個硬碟同時壞掉。

自己對RAID的理解不是很深,
稍微照著自己學到的內容寫個簡介,
就整理到這邊吧。


尚未有邦友留言

立即登入留言