nstepscan磁碟調度演算法

❶ 磁碟調度 演算法

(1)FCFS(先來先服務):
143-86=57
147-86=61
147-91=56
177-91=86
177-94=97
150-94=56
150-102=48
175-102=73
175-130=45
57+61+56+86+97+56+48+73+45=579
(2)SSTF(最短尋道時間優先)：
尋道順序：143（當前），147，150，130，102，94，91，86，175，177；
4+3+20+28+8+3+5+89+2=162
(3)SCAN：
當前方向：從143#向磁軌號增加的方向
依次訪問：143（當前），147，150，175，177
再從遞減方向：130，102，94，91，86
4+3+25+2+47+28+8+3+5=125
(4)LOOK:(即SCAN，電梯調度演算法)
(5)CSCAN:
當前方向：從143#向磁軌號增加的方向
依次訪問：143（當前），147，150，175，177
再從0開始增加方向：86,91,94,102,130
4+3+25+2+91+5+3+8+28=169

❷ 除了fcfs之外，沒有哪個磁碟調度演算法是真正公平的

先來先服務FCFS：公平，簡單，每個進程的請求都能依次得到處理。沒有對尋道優化，平均尋道時間長。

最短時間優先調度演算法SSTF：要求訪問的磁軌是當前磁頭所在的磁軌最近，每次尋道時間最短。可能導致一些請求無限期推延。

電梯調度演算法SCAN：不僅考慮當前磁軌的距離，優先考慮在磁軌前進方向的最短時間，排除磁頭在盤面上的往復運動。電梯原理。

N-SCAN：是SCAN的改良。磁頭改變方向時，以到達請求服務的最短時間。對中間請求服務更有利。

C-SCAN：磁頭單項移動。消除N-SCAN對兩端請求的不公平。

❸ 磁碟調度演算法

  上文介紹了磁碟的結構，本文介紹磁碟的調度演算法相關的內容。
   本文內容

   尋找時間（尋道時間） 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演算法，平均尋道時間更長。

❹ 磁碟調度演算法的簡介

一次磁碟讀寫操作的時間由尋找（尋道）時間、延遲時間和傳輸時間決定：
1) 尋找時間Ts：活動頭磁碟在讀寫信息前，將磁頭移動到指定磁軌所需要的時間。這個時間除跨越n條磁軌的時間外，還包括啟動磁臂的時間s，即：Ts = m * n + s。式中，m是與磁碟驅動器速度有關的常數，約為0.2ms，磁臂的啟動時間約為2ms。
2)延遲時間Tr：磁頭定位到某一磁軌的扇區（塊號）所需要的時間，設磁碟的旋轉速度為r，則：Tr = 1 / (2 * r)。對於硬碟，典型的旋轉速度為5400r/m，相當於一周11.1ms，則Tr為5.55ms;對於軟盤，其旋轉速度在300~600r/m之間，則Tr為50~100ms。
3) 傳輸時間Tt：從磁碟讀出或向磁碟寫入數據所經歷的時間，這個時間取決於每次所讀/寫的位元組數b和磁碟的旋轉速度：Tt = b / (r * N)。式中，r為磁碟每秒鍾的轉數；N為一個磁軌上的位元組數。
在磁碟存取時間的計算中，尋道時間與磁碟調度演算法相關，下面將會介紹分析幾種演算法，而延遲時間和傳輸時間都與磁碟旋轉速度相關，且為線性相關，所以在硬體上，轉速是磁碟性能的一個非常重要的參數。
總平均存取時間Ta可以表示為：Ta = Ts + Tr + Tt。
雖然這里給出了總平均存取時間的公式，但是這個平均值是沒有太大實際意義的，因為在實際的磁碟I/O操作中，存取時間與磁碟調度演算法密切相關。調度演算法直接決定尋找時間，從而決定了總的存取時間。

❺ 常見的磁碟調度演算法有哪些，有什麼優缺點

1.先來先服務（FCFS）
2.最短尋道時間優先（SSTF）
3.掃描（scan）演算法
4循環掃描（CSCAN）演算法
5.NStep和FSCAN調度演算法

❻ 磁碟調度演算法用來改善磁頭的性能對不對

對的，磁碟是計算機系統中最重要的存儲設備，其中含有絕大部分文件。對文件的操作直接涉及到磁碟的訪問，磁碟IO的速度效率和可靠性將直接影響系統的性能。因此，好的磁碟調度演算法、優越的冗餘技術，都是提高磁碟系統性能的切入點。
磁碟調度演算法

1.先來先服務：按照進程訪問磁碟的先後順序進行調度。

優點：公平、簡單

缺點：效率低，平均尋道時間較長

2.最短尋道時間優先：要求訪問磁軌與當前磁頭的磁軌距離最近。

優點：相比於先來先服務，明顯減少平均尋道長度

缺點：磁頭可能在一個小的范圍內一直尋到，造成遠處請求不滿足而飢餓

3.掃描演算法：又稱電梯調度演算法，像電梯一樣上下連續來回尋道

優點：避免了「飢餓」現象

缺點：對於剛剛經過的磁軌又來了新的請求，再次訪問要最多等2個磁軌長度

4.循環掃描演算法：磁頭單向移動，其餘和掃描演算法一樣

優點：解決了可能的錯過型請求的雙倍延遲

缺點：浪費一個磁頭的移動次數，什麼都沒做

5.NStepSCAN演算法：磁碟請求分成N個隊列，隊列間用先來先服務處理，隊列內用掃描演算法處理

優點：避免新請求帶來的粘著問題

缺點：N值很大時，接近於掃描演算法；N=1時，就是先來先服務

6.FSCAN演算法：磁碟請求只分成兩個隊列，一個是當前請求隊列，一個是未來請求隊列，當前隊列按照掃描演算法處理，當前隊列處理完就處理另一個，此時另一個為當前隊列，已經處理完的是未來請求隊列

優點：簡化NStepSCAN演算法

缺點：所有新來的請求都在下次掃描時再處理，對於緊急的高優先順序的請求也要放到下次