scan調度演算法

① 雙向掃描演算法和電梯調度演算法區別

雙向掃描演算法和電梯調度演算法區別：
1、雙向掃描(SCAN)演算法不僅考慮到欲訪問的磁軌與當前磁軌間的距離，更優先考慮的是磁頭，當前的移動方向。例如，當磁頭正在自里向外移動時，SCAN演算法所考慮的下一個訪問對象應足其欲訪問的磁軌既在巧芹當前磁軌之外，又是距離最近的。這樣自里向外地訪問直至再無更外的磁軌需要訪問時，才將磁臂換向為自外向里移動。
2、電梯調度演算法基於BUS演算法的結構，增加了在中間核仿樓層是否停靠的判斷和在頂、改寬纖底層時下一個停靠點的尋找。

② 電梯調度和scan演算法區別

電梯調度和scan演算法沒有區別。經查詢相關資料信息配或得知，scan演算法通常稱為電梯調度演算法，兩者是早賣清陸前一樣的，沒有區別。

③ 在磁碟調度，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調度。

④ 磁碟調度演算法有哪幾種

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

⑤ 目前功率控制演算法都有哪幾種

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

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

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

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

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

⑥ 電梯調度演算法...

不管你是在北上廣還是在港澳台，甚至三四線城市，凡是有規模的地區，高樓比比皆是。不管是寫字樓，還是大型商城，讓你最頭痛的就是乘電梯，尤其是在趕時間的時候。

每天早上，那些差5分鍾就遲到的程序員，在等電梯時，一般會做兩件事：

前者可能是寫字樓里上班族慣有的精神類疾病，但後者肯定是程序員的職業病。本文對「罵電梯」不給予任何指導性建議。

但說起電梯調度演算法，我覺得還是可以給大家科普一下，好為大家在等電梯之餘，打發時間而做出一點貢獻。

（電梯調度演算法可以參考各種硬碟換道演算法，下面內容整理自網路）

先來先服務（FCFS-First Come First Serve）演算法，是一種隨即服務演算法，它不僅僅沒有對尋找樓層進行優化，也沒有實時性的特徵，它是一種最簡單的電梯調度演算法。

它根據乘客請求乘坐電梯的先後次序進行調度。此演算法的 優點是公平、簡單，且每個乘客的請求都能依次地得到處理，不會出現某一乘客的請求長期得不到滿足的情況 。

這種方法在載荷較輕松的環境下，性能尚可接受，但是在載荷較大的情況下，這種演算法的性能就會嚴重下降，甚至惡化。

人們之所以研究這種在載荷較大的情況下幾乎不可用的演算法，有兩個原因：

最短尋找樓層時間優先（SSTF-Shortest Seek Time First）演算法，它注重電梯尋找樓層的優化。最短尋找樓層時間優先演算法選擇下一個服務對象的原則是 最短尋找樓層的時間。

這樣請求隊列中距當前能夠最先到達的樓層的請求信號就是下一個服務對象。

在重載荷的情況下，最短尋找樓層時間優先演算法的平均響應時間較短，但響應時間的方差較大 ，原因是隊列中的某些請求可能長時間得不到響應，出現所謂的「 餓死」現象 。

掃描演算法（SCAN） 是一種按照樓層順序依次服務請求，它讓電梯在最底層和最頂層之間連續往返運行，在運行過程中響應處在於電梯運行方向相同的各樓層上的請求。

它進行尋找樓層的優化，效率比較高，但它是一個 非實時演算法 。掃描演算法較好地解決了電梯移動的問題，在這個演算法中，每個電梯響應乘客請求使乘客獲得服務的次序是由其發出請求的乘客的位置與當前電梯位置之間的距離來決定的。

所有的與電梯運行方向相同的乘客的請求在一次電向上運行或向下運行的過程中完成， 免去了電梯頻繁的來回移動 。

掃描演算法的平均響應時間比最短尋找樓層時間優先演算法長，但是響應時間方差比最短尋找樓層時間優先演算法小， 從統計學角度來講，掃描演算法要比最短尋找樓層時間優先演算法穩定 。

LOOK 演算法是掃描演算法（SCAN）的一種改進。對LOOK演算法而言，電梯同樣在最底層和最頂層之間運行。

但 當 LOOK 演算法發現電梯所移動的方向上不再有請求時立即改變運行方向 ，而掃描演算法則需要移動到最底層或者最頂層時才改變運行方向。

SATF（Shortest Access Time First）演算法與 SSTF 演算法的思想類似，唯一的區別就是 SATF 演算法將 SSTF 演算法中的尋找樓層時間改成了訪問時間。

這是因為電梯技術發展到今天，尋找樓層的時間已經有了很大地改進， 但是電梯的運行當中等待乘客上梯時間卻不是人為可以控制 。

SATF 演算法考慮到了電梯運行過程中乘客上梯時間的影響 。

最早截止期優先（EDF-Earliest Deadline First）調度演算法是最簡單的實時電梯調度演算法，它的 缺點就是造成電梯任意地尋找樓層，導致極低的電梯吞吐率。

它與 FCFS 調度演算法類似，EDF 演算法是電梯實時調度演算法中最簡單的調度演算法。 它響應請求隊列中時限最早的請求，是其它實時電梯調度演算法性能衡量的基準和特例。

SCAN-EDF 演算法是 SCAN 演算法和 EDF 演算法相結合的產物。SCAN-EDF 演算法先按照 EDF 演算法選擇請求列隊中哪一個是下一個服務對象，而對於具有相同時限的請求，則按照 SCAN 演算法服務每一個請求。它的效率取決於有相同 deadline 的數目，因而效率是有限的。

PI（Priority Inversion）演算法將請求隊列中的請求分成兩個優先順序，它首先保證高優先順序隊列中的請求得到及時響應，再搞優先順序隊列為空的情況下在相應地優先順序隊列中的請求。

FD-SCAN（Feasible Deadline SCAN）演算法首先從請求隊列中找出時限最早、從當前位置開始移動又可以買足其時限要求的請求，作為下一次 SCAN 的方向。

並在電梯所在樓層向該請求信號運行的過程中響應處在與電梯運行方向相同且電梯可以經過的請求信號。

這種演算法忽略了用 SCAN 演算法相應其它請求的開銷，因此並不能確保服務對象時限最終得到滿足。

以上兩結介紹了幾種簡單的電梯調度演算法。

但是並不是說目前電梯調度只發展到這個層次。目前電梯的控制技術已經進入了電梯群控的時代。

隨著微機在電梯系統中的應用和人工智慧技術的發展，智能群控技術得以迅速發展起來。

由此，電梯的群控方面陸續發展出了一批新方法，包括：基於專家系統的電梯群控方法、基於模糊邏輯的電梯群控方法、基於遺產演算法的電梯群控方法、基於勝景網路的電梯群控方法和基於模糊神經網路的電梯群控方法。

本人設置的電梯的初始狀態，是對住宅樓的電梯的設置。

(1)建築共有21層，其中含有地下一層（地下一層為停車場）。
(2)建築內部設有兩部電梯，編號分別為A梯、B梯。
(3)電梯內部有23個按鈕，其中包括開門按鈕、關門按鈕和樓層按鈕，編號為-1，1，2，3，4……20。
(4)電梯外部含有兩個按鈕，即向上運行按鈕和向下運行按鈕。建築頂層與地下一層例外，建築頂層只設置有向下運行按鈕，地下一層只設置有向上運行按鈕。
(5)電梯開關門完成時間設定為1秒。電梯到達每層後上下人的時間設定為8秒。電梯從靜止開始運行到下一層的時間設置為2秒，而運行中通過一層的時間為1秒。
(6)在凌晨2：00——4：30之間，如若沒有請求信號，A梯自動停在14層，B梯自動停在6層。
(7)當電梯下到-1層後，如果沒有請求信號，電梯自動回到1層。

每一架電梯都有一個編號，以方便監控與維修。每一架電梯都有一實時監控器，負責監控電梯上下，向電梯升降盒發送啟動、制動、加速、減速、開關電梯門的信號。若電梯發生故障，還應向相應的電梯負責人發送求救信號。

電梯內部的樓層按鈕：

這樣就表示乘客將要去往此層，電梯將開往相應層。當電梯到達該層後，按鈕恢復可以使用狀態。

電梯內部開門按鈕：

如若電梯到了乘客曾經按下的樓層，但是無乘客按開門按鈕，電梯將自動在停穩後1秒後自動開門。

電梯內部關門按鈕：

電梯外部向上按鈕：

電梯外部向下按鈕：

你肯能意識到 哪個演算法都不是一個最佳方案，只是它確實解決了一定情況的問題 。但是對一個優秀的程序員而言，研究各種演算法是無比快樂的。也許你下一次面試，就有關於調度演算法的問題。

⑦ scan調度演算法要到0嗎

要到。根據查詢相關信息顯示scan調度演算法是需要每次都到的，沒有到是需要手動進行調整的襪渣數。調度演算法在操作系告首統中調度是指一梁局種資源分配，因而調度演算法是指根據系統的資源分配策略所規定的資源分配演算法。

⑧ 磁碟調度演算法

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. 重復上述步驟，直到掃描完所有的磁軌。

⑩ 磁碟調度演算法

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

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