磁盘调度算法
上文介绍了磁盘的结构，本文介绍磁盘的调度算法相关的内容。
本文内容
寻找时间（寻道时间） T s ：在读/写数据前，需要将磁头移动到指定磁道所花费的时间。
寻道时间分两步：
则寻道时间 T s = s + m * n。
磁头移动到指定的磁道，但是不一定正好在所需要读/写的扇区，所以需要通过磁盘旋转使磁头定位到目标扇区。
延迟时间T R ：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则 平均所需延迟时间T R = (1/2)*(1/r) = 1/2r。
传输时间T R ：从磁盘读出或向磁盘中写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N，则传输时间 T R = (b/N) * (1/r) = b/(rN)。
总的平均时间 T a = T s + 1/2r + b/(rN) ，由于延迟时间和传输时间都是与磁盘转速有关的，且是线性相关。而转速又是磁盘的固有属性，因此无法通过操作系统优化延迟时间和传输时间。所以只能优化寻找时间。
算法思想： 根据进程请求访问磁盘的先后顺序进行调度。
假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。
按照先来先服务算法规则，按照请求到达的顺序，磁头需要一次移动到55、58、39、18、90、160、150、38、184号磁道。
磁头共移动了 45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498个磁道。响应一个请求平均需要移动498 / 9 = 55.3个磁道（平均寻找长度）。
优点： 公平；如果请求访问的磁道比较集中的话，算法性能还算可以 。
缺点： 如果大量进程竞争使用磁盘，请求访问的磁道很分散，FCFS在性能上很差，寻道时间长 。
算法思想： 优先处理的磁道是与当前磁头最近的磁道。可以保证每次寻道时间最短，但是不能保证总的寻道时间最短 。（其实是贪心算法的思想，只是选择眼前最优，但是总体未必最优）。
假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。
磁头总共移动了（100 -18）+ （184 -18） = 248个磁道。响应一个请求平均需要移动248 / 9 = 27.5个磁道（平均寻找长度）。
缺点： 可能产生饥饿现象 。
本例中，如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求又来了一个18号磁道访问请求。如果有源源不断的18号、38号磁道访问请求，那么150、160、184号磁道请求的访问就永远得不到满足，从而产生饥饿现象。这里产生饥饿的原因是 磁头在一小块区域来回移动。
SSTF算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动。为了防止这个问题，可以规定： 磁头只有移动到请求最外侧磁道或最内侧磁道才可以反向移动，如果在磁头移动的方向上已经没有请求，就可以立即改变磁头移动，不必移动到最内/外侧的磁道。 这就是扫描算法的思想。由于磁头移动的方式很像电梯，因此也叫 电梯算法 。
假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的访问55、58、39、18、90、160、150、38、184号磁道。
磁头共移动了（184 - 100）+ （184 -18） = 250个磁道。响应一个请求平均需要移动 250 / 9 = 27.5个磁道（平均寻找长度）。
优点： 性能较好，寻道时间较短，不会产生饥饿现象。
缺点： SCAN算法对于各个位置磁道的响应频率不平均 。（假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等待低头移动很长一段距离；而响应了184号磁道的请求之后，很快又可以再次响应184号磁道请求了。）
SCAN算法对各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而 返回时直接快速移动至最靠边缘的并且需要访问的磁道上而不处理任何请求。
通俗理解就是SCAN算在改变磁头方向时不处理磁盘访问请求而是直接移动到另一端最靠边的磁盘访问请求的磁道上。
假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的访问55、58、39、18、90、160、150、38、184号磁道。
磁头共移动了（184 -100）+ （184 - 18）+（90 - 18）=322个磁道。响应一个请求平均需要移动322 / 9 = 35.8个磁道（平均寻找长度）。
优点： 相比于SCAN算法，对于各个位置磁道响应频率很平均。
缺点： 相比于SCAN算法，平均寻道时间更长。
绛旓細銆愮瓟妗堛戯細C 鏈鐭閬撴椂闂翠紭鍏绠楁硶瑕佹眰璁块棶鐨勭閬撲笌褰撳墠纾佸ご鎵鍦ㄧ殑纾侀亾璺濈鏈杩戯紝浠ヤ娇姣忔鐨勫閬撴椂闂存渶鐭紝杩欏鏄撲娇寰楃澶翠竴鐩村湪鏌愪釜纾佺洏鍖哄煙鏉ュ洖绉诲姩锛岃岃繙绂昏鍖哄煙鐨勮繘绋嬶紝鍏惰姹傚彲鑳介暱鏈熷緱涓嶅埌婊¤冻銆
绛旓細FCFS绠楁硶鏍规嵁杩涚▼璇锋眰璁块棶纾佺洏鐨勫厛鍚庨『搴忚繘琛岃皟搴︼紝杩欐槸涓绉嶆渶绠鍗曠殑璋冨害绠楁硶銆傝绠楁硶鐨勪紭鐐规槸鍏锋湁鍏钩鎬с傚鏋滃彧鏈夊皯閲忚繘绋嬮渶瑕佽闂紝涓斿ぇ閮ㄥ垎璇锋眰閮芥槸璁块棶绨囪仛鐨勬枃浠舵墖鍖猴紝鍒欐湁鏈涜揪鍒拌緝濂界殑鎬ц兘锛涗絾濡傛灉鏈夊ぇ閲忚繘绋嬬珵浜変娇鐢ㄧ鐩橈紝閭ｄ箞杩欑绠楁硶鍦ㄦц兘涓婂線寰鎺ヨ繎浜庨殢鏈鸿皟搴︺傛墍浠ワ紝瀹為檯纾佺洏璋冨害涓冭檻涓浜涙洿涓...
绛旓細瀵婚亾鏃堕棿鏄‖鐩樻ц兘鐨勫叧閿寚鏍囷紝鍖呮嫭鍚姩纾佸ご鑷傛椂闂村拰纾佸ご绉诲姩鏃堕棿锛屽欢杩熸椂闂村垯涓庣‖鐩樿浆閫熺揣瀵嗙浉鍏炽傝繖閲岋紝鎴戜滑鍏虫敞鍑犵纾佺洏璋冨害绠楁硶锛欶CFS锛堝厛鏉ュ厛鏈嶅姟锛夊敖绠″叕骞筹紝浣嗗鐞嗗垎鏁ｈ姹傛晥鐜囦笉楂橈紝骞冲潎瀵婚亾鏁颁负55.3锛汼STF锛堟渶鐭閬撴椂闂达級杩芥眰閫熷害锛屼絾鍙兘瀵艰嚧鏌愪簺纾侀亾鈥滈ゥ楗库濈幇璞★紝濡18/38纾侀亾鎸佺画璇锋眰銆傜鐩...
绛旓細纾佺洏璋冨害鍦ㄥ閬撶▼搴忚璁＄殑璁＄畻鏈虹郴缁熶腑锛屽悇涓繘绋嬪彲鑳戒細涓嶆柇鎻愬嚭涓嶅悓鐨勫纾佺洏杩涜璇/鍐欐搷浣滅殑璇锋眰銆備负浜嗗敖蹇殑鍝嶅簲杩涚▼鐨勭鐩樿姹傦紝浜轰滑璁捐浜纾佺洏璋冨害绠楁硶銆備富瑕佹湁鍥涚纾佺洏璋冨害绠楁硶銆傚厛鏉ュ厛鏈嶅姟绠楁硶锛團CFS锛夛紝鏈鐭閬撴椂闂翠紭鍏堢畻娉曪紙SSTF锛夛紝鎵弿绠楁硶锛圫CAN锛夛紝寰幆鎵弿绠楁硶锛圕SCAN锛夈傝繍鐢ㄦ渶鐭閬撲紭鍏...
绛旓細鍑℃槸鏈夐槦鍒楃殑鍦版柟灏辫鑰冭檻璋冨害銆傚亣瀹:褰撳墠鏈9涓纾佺洏璇诲啓璇锋眰;杩9涓鐩樿鍐欒姹傝璁块棶鐨勭閬撳彿鎸夌収鍚勪釜纾佺洏璇诲啓璇锋眰鍒拌揪鐨勬搴忎緷娆′负:55銆58銆39銆18銆90銆160銆150銆38銆184銆傛澶栵紝纾佸ご褰撳墠浣嶄簬100鍙风閬撲笂銆傚鏋滅郴缁熶娇鐢⊿CAN绠楁硶鎴朇-SCAN绠楁硶锛岄偅涔堟垜浠繕鍋囧畾纾佸ご褰撳墠鐨勭Щ鍔ㄦ柟鍚戜负纾侀亾鍙峰闀跨殑鏂瑰悜銆
绛旓細纾佺洏璋冨害涓垎鍒秹鍙婂鎵炬椂闂村拰寤惰繜鏃堕棿銆傜鐩橀┍鍔ㄨ皟搴﹀寘鎷Щ鑷傝皟搴﹀拰鏃嬭浆璋冨害锛岀鐩樿皟搴﹀湪澶氶亾绋嬪簭璁捐鐨勮绠楁満绯荤粺涓紝鍚勪釜杩涚▼鍙兘浼氫笉鏂彁鍑轰笉鍚岀殑瀵圭鐩樿繘琛岃/鍐欐搷浣滅殑璇锋眰銆傜敱浜庢湁鏃跺欒繖浜涜繘绋嬬殑鍙戦佽姹傜殑閫熷害姣旂鐩樺搷搴旂殑杩樿蹇紝鍥犳鎴戜滑鏈夊繀瑕佷负姣忎釜纾佺洏璁惧寤虹珛涓涓瓑寰呴槦鍒楋紝甯哥敤鐨纾佺洏璋冨害绠楁硶鏈...
绛旓細鍏堟潵鍏堟湇鍔绠楁硶锛氳繖涓畻娉曞疄闄呬笂涓嶈冭檻璁块棶鑰呰姹傝闂殑鐗╃悊浣嶇疆锛岃屽彧鏄冭檻璁块棶鑰呮彁鍑鸿闂姹傜殑鍏堝悗娆″簭銆傛渶鐭閬撴椂闂翠紭鍏堢畻娉曪細瑕佹眰璁块棶鐨勭閬擄紝涓庡綋鍓嶇澶存墍鍦ㄧ殑纾侀亾璺濈鏈杩戯紝浠ヤ娇姣忔鐨勫閬撴椂闂存渶鐭傛壂鎻忕畻娉曪細鈥滅數姊璋冨害鈥濇槸娌跨潃鑷傜殑绉诲姩鏂瑰悜鍘婚夋嫨绂诲綋鍓嶈鍐欒瘝澶存渶杩戠殑鍝釜纾侀亾鐨勮闂呫.寰幆...
绛旓細路涓烘枃浠跺垎閰嶅繀瑕佺殑瀛樺偍绌洪棿锛浡锋彁楂樼鐩樺瓨鍌ㄧ┖闂寸殑鍒╃敤鐜囷紱路鎻愰珮瀵圭鐩樼殑I锛廜閫熷害锛屼互鏀瑰杽鏂囦欢绯荤粺鐨勬ц兘锛浡烽噰鍙栧繀瑕佺殑鍐椾綑鎺柦锛屾潵纭繚鏂囦欢绯荤粺鐨勫彲闈犳с1锛纾佺洏璋冨害绠楁硶 纾佺洏鏄彲琚涓繘绋嬪叡浜殑璁惧銆傚綋鏈夊涓繘绋嬮兘璇锋眰璁块棶纾佺洏鏃讹紝搴旈噰鐢ㄤ竴绉嶉傚綋鐨勮皟搴︾畻娉曪紝浠ヤ娇鍚勮繘绋嬪纾佺洏鐨勫钩鍧囪闂(涓昏鏄...
绛旓細锛1锛夊厛鏉ュ厛鏈嶅姟璋冨害绠楁硶 鐢变簬璇ョ畻娉曞氨鏄寜鐓х閬撹姹傚簭鍒楃殑鍏堝悗娆″簭渚濇璁块棶纾侀亾鐨勶紝鍥犳纾侀亾鐨勮闂簭鍒楋紙鏈嶅姟椤哄簭锛夊氨鏄細110銆180銆32銆115銆15銆120銆60銆70銆傚綋鍓嶇澶村湪50鍙风閬撱傛晠纾佸ご绉诲姩閬撴暟涓猴細锛110-50锛+锛180-110锛+锛180-32锛+锛115-32锛+锛115-15锛+锛120-15锛+锛120-60锛+...
绛旓細Java鐗堢殑纾佺洏璋冨害绠楁硶锛屽叾涓畻娉曞寘鍚 1 鍏堟潵鍏堟湇鍔 2 鏈鐭椂闂翠紭鍏 3 鏈鐭椂闂翠紭鍏 4 鍗曞悜鎵弿绠楁硶 绋嬪簭鏄姩鐢绘紨绀虹殑锛岀▼搴忎互鍦嗘ā鎷熺閬擄紝浠ユ柟鍧楁ā鎷熺澶存牴鎹畻娉曞湪鐣岄潰涓婃紨绀恒傜▼搴忚繍琛屾埅鍥惧涓嬪浘鎵绀猴細
