電梯演算法又稱

1. 電梯調度演算法...

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

每天早上，那些差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秒後自動開門。

電梯內部關門按鈕：

電梯外部向上按鈕：

電梯外部向下按鈕：

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

2. 磁碟調度演算法

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

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

3. 電梯調度和scan演算法區別

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

4. 習題精編上 磁碟尋到演算法中的LOOK 和 C_LOOK 是啥意思啊

LOOK 和 C_LOOK 分別是回看的掃描和循環掃描，它與scan ,cscan不通之處是scan掃描是要回到磁軌最外出或最里處才返回，而LOOK只需要到達要訪問的磁軌最外或最里處就會返回。比如磁軌1—1000，分別要訪問150,300,800道的內容，那如果現在在500磁軌，向磁軌小的方向訪問的話，scan 演算法會移到磁軌1後再返回，LOOK演算法移到磁軌150或就會返回了了。同理 C_LOOK 與cscan的不同之處類似

5. 電梯演算法是怎樣的

電梯演算法是通過操作系統學術名為SCAN演算法。磁臂僅移動到請求的最外道就回轉。反方向查找服務。

如果請求調度的磁軌為98, 183, 37, 122, 14, 124, 65, 67，磁頭從53號磁軌開始移動，磁頭就會按照65, 67, 98, 122, 124, 183, 37,14 的順序依次查找，並將數據輸入內存。

電梯（升降盒）上下來回地運動，電梯內部有一些按鈕，每一個按鈕代表一層樓，當按下按鈕時，按鈕的燈亮。

電梯沿某一方向運動，在將要到達某一層樓時，實時監控器 判斷電梯內是否有乘客要在此層樓下電梯，若有，則發送信號給電梯升降架。

電梯是指服務於建築物內若干特定的樓層，其轎廂運行在至少兩列垂直於水平面或與鉛垂線傾斜角小於15°的剛性軌道運動的永久運輸設備。

也有台階式，踏步板裝在履帶上連續運行，俗稱自動扶梯或自動人行道。服務於規定樓層的固定式升降設備。垂直升降電梯具有一個轎廂，運行在至少兩列垂直的或傾斜角小於15°的剛性導軌之間。

轎廂尺寸與結構形式便於乘客出入或裝卸貨物。習慣上不論其驅動方式如何，將電梯作為建築物內垂直交通運輸工具的總稱。

6. 操作系統的主要演算法都有哪些

一、進程(作業)調度演算法
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）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。