磁碟調度scan演算法

Ⅰ 磁碟調度 演算法

(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

Ⅱ 電腦技術 操作系統 LOOK SCAN演算法

C-LOOK=10到5到90到80到70到60到20=160
C-SCAN=10到5到0到199到90到80到70到60到20=388
LOOK=10到5到20到60到70到80到90=90
SCAN=10到5到0到20到60到70到80到90=100

Ⅲ 磁碟調度演算法

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

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

Ⅳ 求計算機操作系統的高手幫做一個題(急得很啊）

移動順序:223.198.176.156.149.142.136.245
共移動總量
8
僅做參考千萬莫模仿有恐誤人子弟

Ⅳ 磁碟調度演算法

1、對於如下給定的一組磁碟訪問進行調度：

2、要求分別採用先來先服務、最短尋道優先以及電梯調度方法進行調度。
3、要求給出每種演算法中磁碟訪問的順序，計算出平均移動道數。
4、假定當前讀寫頭在90號，向磁軌號增加的方向移動。

輸入磁軌序列(-1結束): 30 50 100 180 20 90 150 70 80 10 160 -1
磁軌讀取結果: 30 50 100 180 20 90 150 70 80 10 160
1.先進先出演算法(FIFO)
2.最短服務時間優先演算法(SSTF)
3.掃描演算法猜余(SCAN)
4.退出(exit)
請選擇演算法:1
當前的讀寫頭位於:90

FIFO 調度順序: 30 50 100 180 20 90 150 70 80 10 160
移動的總道數:810
平均尋道長度笑碼:73.6364

1.先進先出演算法(FIFO)
2.最短服務時間優先演算法(SSTF)
3.掃描演算法(SCAN)
4.退出(exit)
請選擇演算法:2
當前的讀寫頭位於:90

SSTF 調度順序: 90 80 70 50 30 20 10 100 150 160 180
移動的總道數:250
平均尋道長度:22.7273

1.先進先出演算法(FIFO)
2.最短服務時間優先演算法(SSTF)
3.掃描演算法(SCAN)
4.退出(exit)
請選擇演算法:3
當前的讀寫頭位於: 90

SCAN 調碰兆哪度順序:90 100 150 160 180 90 80 70 50 30 20 10
移動的總道數:260
平均尋道長度:23.6364

1.先進先出演算法(FIFO)
2.最短服務時間優先演算法(SSTF)
3.掃描演算法(SCAN)
4.退出(exit)
請選擇演算法:4

Ⅵ cscan演算法排序

C-Scan演算法是一種對磁碟調度的演算法，它的特點是在磁頭移動到最右邊的磁軌後，磁頭立即跳到最左邊的磁軌，然輪遲弊後臘族再按照順序掃描磁軌。
C-Scan演算法的步驟如下：
1. 從當前磁頭位置開始，按照順序掃描磁軌，直到掃描到最右邊的磁軌。
2. 磁旦團頭跳轉到最左邊的磁軌，繼續按照順序掃描磁軌，直到掃描到最右邊的磁軌。
3. 重復上述步驟，直到掃描完所有的磁軌。

Ⅶ 在磁碟調度，sstf演算法中，為什麼說：總是選擇最小尋找時間並不能保證平均尋找時間最小

FCFS演算法根據進程請求訪問磁碟的先後順序進行調度，這是一種最簡單的調度演算法。該演算法的優點是具有公平性。如果只有少量進程需要訪問，且大部分請求都是訪問簇聚的文件扇區，則有望達到較好的性能；但如果有大量進程競爭使用磁碟，那麼這種演算法在性能上往往接近於隨機調度。所以，實際磁碟調度中考慮一些更為復雜的調度演算法。
1、演算法思想：按訪問請求到達的先後次序服務。
2、優點：簡單，公平。
3、缺點：效率不高，相鄰兩次請求可能會造成最內到最外的柱面尋道，使磁頭反復移動，增加了服務時間，對機械也不利。
4、例子：
假設磁碟訪問序列：98，183，37，122，14，124，65，67。讀寫頭起始位置：53。求：磁頭服務序列和磁頭移動總距離（道數）。
由題意和先來先服務演算法的思想，得到下圖所示的磁頭移動軌跡。由此：
磁頭服務序列為：98，183，37，122，14，124，65，67
磁頭移動總距離=（98-53）+（183-98）+|37-183|+（122-37）+|14-122|+（124-14）+|65-124|+（67-65）=640（磁軌） SSTF算高租緩法選擇調度處理的磁軌是與當前磁頭所在磁軌距離最近的磁軌，以使每次的尋找時間最短。當然，總是選擇最小尋找時間並不能保證平均尋找時間最小，但是能提供比FCFS演算法更戚模好的性能。這種演算法會產生「飢餓」現象。
1、演算法思想：優先選擇距當型襲前磁頭最近的訪問請求進行服務，主要考慮尋道優先。
2、優點：改善了磁碟平均服務時間。
3、缺點：造成某些訪問請求長期等待得不到服務。
4、例子：對上例的磁碟訪問序列，可得磁頭移動的軌跡如下圖。 SCAN演算法在磁頭當前移動方向上選擇與當前磁頭所在磁軌距離最近的請求作為下一次服務的對象。由於磁頭移動規律與電梯運行相似，故又稱為電梯調度演算法。SCAN演算法對最近掃描過的區域不公平，因此，它在訪問局部性方面不如FCFS演算法和SSTF演算法好。
演算法思想：當設備無訪問請求時，磁頭不動；當有訪問請求時，磁頭按一個方向移動，在移 動過程中對遇到的訪問請求進行服務，然後判斷該方向上是否還有訪問請求，如果有則繼續掃描；否則改變移動方向，並為經過的訪問請求服務，如此反復。如下圖所示：
掃描演算法（電梯演算法）的磁頭移動軌跡
2、優點：克服了最短尋道優先的缺點，既考慮了距離，同時又考慮了方向。 在掃描演算法的基礎上規定磁頭單向移動來提供服務，回返時直接快速移動至起始端而不服務任何請求。由於SCAN演算法偏向於處理那些接近最里或最外的磁軌的訪問請求，所以使用改進型的C-SCAN演算法來避免這個問題。
釆用SCAN演算法和C-SCAN演算法時磁頭總是嚴格地遵循從盤面的一端到另一端，顯然，在實際使用時還可以改進，即磁頭移動只需要到達最遠端的一個請求即可返回，不需要到達磁碟端點。這種形式的SCAN演算法和C-SCAN演算法稱為LOOK和C-LOOK調度。這是因為它們在朝一個給定方向移動前會查看是否有請求。注意，若無特別說明，也可以默認SCAN演算法和C-SCAN演算法為LOOK和C-LOOK調度。

Ⅷ 請教關於磁碟調度的問題，到底按照哪種方法來啊

嗯，是問的這個問題我看的答案是大綱後面的答案，2010年第45題，為方便大家看，我把部分題目寫在下面某計算機系統採用CSCAN（循環掃描）磁碟調度策略，使用2KB的內存空間記錄16384個磁碟塊的空閑狀態，某單面磁碟旋轉速度為每分鍾6000轉，每個磁軌有100個扇區，相鄰磁軌間的平均移動時間為1ms。在某時刻，磁頭位於100號磁軌處，並沿著磁軌增大的方向移動，磁軌號請求隊列是50，90，30，120答案給出的磁軌移動時間是170ms（沒給過程），那就應該是按照100->120->30->50->90的順序來移動的了說明CSCAN演算法 不移動到頭，移動到請求的磁軌即可，並且返回到最小的磁軌時的移動時間也要計算但是我在有的輔導書上看到的是說，不計算返回時間剛翻了下課本，湯小丹的操作系統第三版196頁，根據敘述和例子，意思是說不用移動到頭，只到請求的最大磁軌，並且返回到請求的最小磁軌的時間需要計算而關於SCAN演算法，課本上也是說只移動到請求的最大磁軌而我在文×都的輔導書上看到的，關於SCAN演算法還特地強調了要移動到頭，甚至根據磁碟扇區的數目和每磁軌的扇區數計算出總磁軌數再計算移動時間，真是糾結啊

Ⅸ 目前常用的磁碟調度演算法有哪幾種

• 磁碟調度在多道程序設計的計算機系統中，各個進程可能會不斷提出不同的對磁碟進行讀/寫操作的請求。由於有時候這些進程的發送請求的速度比磁碟響應的還要快，因此我們有必要為每個磁碟設備建立一個等待隊列，常用的磁碟調度演算法有以下四種：[1]

• 先來先服務演算法（FCFS），

• 最短尋道時間優先演算法（SSTF），

• 掃描演算法（SCAN），

• 循環掃描演算法（CSCAN）