磁碟調度電梯演算法
① 目前常用的磁碟調度演算法有哪幾種每種演算法優先考慮的問題是什麼
先來先服務演算法：這個演算法實際上不考慮訪問者要求訪問的物理位置，而只是考慮訪問者提出訪問請求的先後次序。
最短尋道時間優先演算法：要求訪問的磁軌，與當前磁頭所在的磁軌距離最近，以使每次的尋道時間最短。
掃描演算法：「電梯調度」是沿著臂的移動方向去選擇離當前讀寫詞頭最近的哪個磁軌的訪問者。
.循環掃描演算法：防止飢餓現象
② 磁碟調度演算法
上文介紹了磁碟的結構，本文介紹磁碟的調度演算法相關的內容。
本文內容
尋找時間（尋道時間） 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演算法，平均尋道時間更長。
③ 1000分求解
cccccc ,LOOK（查找）調度（電梯）電梯演算法。磁臂僅移雀簡拍動到請求的最外道就回轉。反方向查找服務。磁頭從53號磁軌開始移動，按照65, 67, 98, 122, 124, 183, 14, 37的順序依次查找，並將數據輸入內存。
電梯問題需求分析文檔 （討論稿）
1．電梯的基本需求功能
每一架電梯都有一個編號，以方便監控與維修。每一架電梯都有一實時監控器，負責監控電梯上下，向電梯升降盒咐山發送啟動、制動、加速、減速、開關電梯門的信號。若電梯發生故障，還應向相應的電梯負責人發送求救信號。
2．電梯按鈕功能分析
電梯（升降盒）上下來回地運動，電梯內部有一些按鈕，每一個按鈕代表一層樓，當按下按鈕時，按鈕的燈亮。電梯沿某一方向運動，在將要到達某一層樓時，實時監控器判斷電梯內是否有乘客要在此層樓下電梯，若有，則發送信號給電梯升降架，讓其減速，同時讓電梯在此層樓的電梯入口處平穩地停下，電梯停下後，實時監控器讓電梯內相應的按鈕燈滅，讓乘客出電梯，然後關閉電梯門，而且繼續朝原方向運動，直至到達當前運動方向上，有乘客要求到達的最後一層樓為止（即如：若該建築物有50層，電梯當前正向上運動，若有乘客要求到達的最高樓層為30層，則電梯運動到30層之後，若30層以上沒有乘客發出請求，則電梯可根據電梯內是否「有人」而向下運動或停止）。
除底層和頂層只有一個按鈕外，每個樓層有兩個按鈕，分別指示上樓和下樓請求，當按下後，按鈕燈亮，並向實時監控器發送請求，實時監控程序負責判斷乘客的上下樓請求是否與電梯的當前運動方向一致，若不一致，則暫頃羨不受理此請求，此時按鈕燈繼續亮；若一致，則實時監控器將相應的上下請求按鈕燈熄滅，並讓電梯平穩地停在此層樓的電梯入口處，讓相應的乘客入電梯，而後繼續朝原方向運動。若同時有兩層或兩層以上的樓發出請求，產生了沖突，則實時監控器調用沖突處理器進行抉擇，受理其中的一個請求，並負責將各請求上下樓的按鈕燈熄滅。
3．當電梯發生異常現象時的功能需求
若電梯發生故障時，則實時監控器立即將電梯置為「不可用」狀態，並且忽略任何請求，同時向相應的電梯管理人員發送求救信號。待電梯修復後管理員可將電梯置為「工作」狀態，然後恢復正常工作。磁頭初始位於0磁軌，磁碟請求以16、29、19、12、55、6、69柱面的次序到達磁碟驅動器
FCFS先來先服務：（順序訪問）
0——16——29——19——12——55——6——69
SSTF最短尋道時間優先(在把磁頭移到遠處為另外的請求服務之前，應先把接近於磁頭當前位置的所有請求都服務完。SSTF選擇的請求距當前磁頭所在位置有最短的尋道時間)：
0——6——12——16——19——29——55——69
電梯演算法(需要一個方向，因為初始位於0道，則肯定是從低位到高位的。磁頭從初始處出發，向一端移動，遇到所需的磁軌是就進行服務，直至到達最遠的請求磁軌上，如果當前方向上沒有請求就會反過來繼續服務)：
0——6——12——16——19——29——55——69
因為初始時位於0道，所以電梯演算法和最短尋道演算法一樣，如果是從中間開始就會不同的。
我們上學期剛學過，如果你還有不懂得地方可以給我留言。
希望可以幫到你，呵呵
④ 若磁頭的當前位置100柱面，磁頭正向磁軌號減小方向移動。現有一磁碟讀寫請求隊列，柱面號依次為:
磁碟調度在多道程序設計的計算機系統中，各個進程可能會不斷提出不同的對磁碟進行讀/寫操作的請求。為了盡快的響應進程的磁碟請求，人們設計了磁碟調度演算法。主要有四種磁碟調度演算法。先來先服務演算法（FCFS），最短尋道時間優先演算法（SSTF），掃描演算法（SCAN），循環掃描演算法（CSCAN）。
運用最短尋道優先演算法依次悄嘩賀選擇的磁軌是：90、80、125、140、160、190、啟派30、29、25、20、10。
運用電梯調度演算法依次經過的磁軌是：90、80、30、29、25、20、10、125、140、160、190。
我們根據演算法的尋道序列可以得出：最短尋道優先演算法的經過的煮麵數為310個柱面，電梯調度演算法經過的柱面數為270次。
(4)磁碟調度電梯演算法擴展閱讀：
每種磁碟調度演算法的優缺點
先來先服務演算法的優點會根據進程請求訪問磁碟的先後次序進行調度。此演算法的優點是公平、簡單，蘆鉛且每個進程的請求都能依次得到處理，不會出現某一進程的請求長期得不到滿足的情況，此演算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。
最短尋道優先演算法的缺點每次的尋道時間最短，該演算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。其缺點是對用戶的服務請求的響應機會不是均等的，因而導致響應時間的變化幅度很大。在服務請求很多的情況下，對內外邊緣磁軌的請求將會無限期地被延遲，有些請求的響應時間將不可預期。
掃描演算法的優缺點此演算法基本上克服了最短尋道時間優先演算法的服務集中於中間磁軌和響應時間變化比較大的缺點，而具有最短尋道時間優先演算法的優點即吞吐量較大，平均響應時間較小，但由於是擺動式的掃描方法，兩側磁軌被訪問的頻率仍低於中間磁軌。
循環掃描演算法的優點是這些磁軌剛被處理，而磁碟另一端的請求密度相當高，且這些訪問請求等待的時間較長，為了解決這種情況，循環掃描演算法規定磁頭單向移動。
參考資料來源：網路-磁碟調度演算法
⑤ 操作系統的主要演算法都有哪些
一、進程(作業)調度演算法
l 先來先服務調度演算法（FCFS）：每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執行。該進程一旦佔有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。特點：利於長進程，而不利於短進程。
l 短進程（作業）優先調度演算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之佔有處理器並執行，直到該進程完成或因發生事件而阻塞，然後退出處理器，再重新調度。
l 時間片輪轉調度演算法 ：系統將所有的就緒進程按進入就緒隊列的先後次序排列。每次調度時把CPU分配給隊首進程，讓其執行一個時間片，當時間片用完，由計時器發出時鍾中斷，調度程序則暫停該進程的執行，使其退出處理器，並將它送到就緒隊列的末尾，等待下一輪調度執行。
l 優先數調度演算法 ：它是從就緒隊列中選擇一個優先權最高的進程，讓其獲得處理器並執行。
l 響應比高者優先調度演算法：它是從就緒隊列中選擇一個響應比最高的進程，讓其獲得處理器執行，直到該進程完成或因等待事件而退出處理器為止。特點：既照顧了短進程，又考慮了進程到達的先後次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的演算法，但每次進行調度時，都需要對各個進程計算響應比。所以系統開銷很大，比較復雜。
l 多級隊列調度演算法
基本概念：
作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)
作業平均周轉時間(T)＝周轉時間/作業個數
作業帶權周轉時間（Wi）＝周轉時間/運行時間
響應比＝（等待時間＋運行時間）/運行時間
二、存儲器連續分配方式中分區分配演算法
n 首次適應分配演算法（FF）：對空閑分區表記錄的要求是按地址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查找空閑分區表，找到第一個能滿足作業長度要求的空閑區，分割這個空閑區，一部分分配給作業，另一部分仍為空閑區。
n 循環首次適應演算法：每次分配均從上次分配的位置之後開始查找。
n 最佳適應分配演算法(BF)：是按作業要求從所有的空閑分區中挑選一個能滿足作業要求的最小空閑區，這樣可保證不去分割一個更大的區域，使裝入大作業時比較容易得到滿足。為實現這種演算法，把空閑區按長度遞增次序登記在空閑區表中，分配時，順序查找。
三、頁面置換演算法
l 最佳置換演算法（OPT) ：選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。
l 先進先出置換演算法（FIFO）：選擇最先進入內存的頁面予以淘汰。
l 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。
l 最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。
四、磁碟調度
n 先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置
n 最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題
n 掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。
n 循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。