休電梯演算法

Ⅰ 電梯調度演算法

(1)電梯調度演算法的處理次序為:
5
8
1
4
3
6
2
7
(2)最短尋找時間優先演算法的處理次序為:
5
8
6
2
7
1
4
3

Ⅱ 五分鍾聊完磁碟

盤可以說是硬體裡面比較簡單的構造了，同時也是最重要的。下面我們從盤談起，聊聊它的物理構造

盤會有很多種類型。其中最簡單的構造就是 磁碟(magnetic hard disks) ， 也被稱為 hard disk,HDD 等。磁碟通常與安裝在磁臂上的磁頭配對，磁頭可將數據讀取或者將數據寫入磁碟，因此磁碟的讀寫速度都同樣快。在磁碟中，數據是隨機訪問的，這也就說明可以通過任意的順序來 存儲 和 檢索 單個數據塊，所以你可以在任意位置放置磁碟來讓磁頭讀取，磁碟是一種 非易失性 的設備，即使斷電也能永久保留。

在計算機發展早期一般是用光碟來存儲數據的，然而隨著固態硬碟的流行，固態硬碟不包含運動部件的特點，成為現在計算機的首選存儲方式。

為了組織和檢索數據，會將磁碟組織成特定的結構，這些特定的結構就是 磁軌、扇區和柱面

每一個磁碟都是由無數個同心圓組成，這些同心圓就好像樹的年輪一樣

磁碟被組織成柱面形式，每個盤用軸相連，每一個柱麵包含若干磁軌，每個磁軌由若干扇區組成。軟盤上大約每個磁軌有 8 - 32 個扇區，硬碟上每條磁軌上扇區的數量可達幾百個，磁頭大約是 1 - 16 個。

對於磁碟驅動程序來說，一個非常重要的特性就是控制器是否能夠同時控制兩個或者多個驅動器進行磁軌定址，這就是 重疊尋道(overlapped seek) 。對於控制器來說，它能夠控制一個磁碟驅動程序完成尋道操作，同時讓其他驅動程序等待尋道結束。控制器也可以在一個驅動程序上進行讀寫操作，與此同時讓另外的驅動器進行尋道操作，但是軟盤控制器不能在兩個驅動器上進行讀寫操作。

RAID 稱為 磁碟冗餘陣列 ，簡稱 磁碟陣列 。利用虛擬化技術把多個硬碟結合在一起，成為一個或多個磁碟陣列組，目的是提升性能或數據冗餘。

RAID 有不同的級別

磁碟由一堆鋁的、合金或玻璃的碟片組成，磁碟剛被創建出來後，沒有任何信息。磁碟在使用前必須經過 低級格式化(low-levvel format) ，下面是一個扇區的格式

前導碼相當於是標示扇區的開始位置，通常以位模式開始，前導碼還包括 柱面號 、 扇區號 等一些其他信息。緊隨前導碼後面的是數據區，數據部分的大小由低級格式化程序來確定。大部分磁碟使用 512 位元組的扇區。數據區後面是 ECC，ECC 的全稱是 error correction code ， 數據糾錯碼 ，它與普通的錯誤檢測不同，ECC 還可以用於恢復讀錯誤。ECC 階段的大小由不同的磁碟製造商實現。ECC 大小的設計標准取決於 設計者願意犧牲多少磁碟空間來提高可靠性 ，以及程序可以處理的 ECC 的復雜程度。通常情況下 ECC 是 16 位，除此之外，硬碟一般具有一定數量的備用扇區，用於替換製造缺陷的扇區。

低級格式化後的每個 0 扇區的位置都和前一個磁軌存在 偏移 ，如下圖所示

這種方式又被稱為 柱面斜進(cylinder skew) ，之所以採用這種方式是為了提高程序的運行性能。可以這樣想，磁碟在轉動的過程中會經由磁頭來讀取扇區信息，在讀取內側一圈扇區數據後，磁頭會進行向外側磁軌的定址操作，定址操作的同時磁碟在繼續轉動，如果不採用這種方式，可能剛好磁頭定址到外側，0 號扇區已經轉過了磁頭，所以需要旋轉一圈才能等到它繼續讀取，通過柱面斜進的方式可以消除這一問題。

柱面斜進量取決於驅動器的幾何規格。柱面斜進量就是兩個相鄰同心圓 0 號扇區的差異量。如下圖所示

這里需要注意一點，不只有柱面存在斜進，磁頭也會存在 斜進(head skew) ，但是磁頭斜進比較小。

磁碟格式化會減少磁碟容量，減少的磁碟容量都會由前導碼、扇區間間隙和 ECC 的大小以及保留的備用扇區數量。

在磁碟使用前，還需要經過最後一道工序，那就是對每個分區分別執行一次 高級格式化(high-level format) ，這一操作要設置一個引導塊、空閑存儲管理（採用點陣圖或者是空閑列表）、根目錄和空文件系統。這一步操作會把碼放在分區表項中，告訴分區使用的是哪種文件系統，因為許多操作系統支持多個兼容的文件系統。在這一步之後，系統就可以進行引導過程。

下面我們來探討一下關於影響磁碟讀寫的演算法，一般情況下，影響磁碟快讀寫的時間由下面幾個因素決定

這三種時間參數也是磁碟尋道的過程。一般情況下，尋道時間對總時間的影響最大，所以，有效的降低尋道時間能夠提高磁碟的讀取速度。

如果磁碟驅動程序每次接收一個請求並按照接收順序完成請求，這種處理方式也就是 先來先服務(First-Come, First-served, FCFS) ，這種方式很難優化尋道時間。因為每次都會按照順序處理，不管順序如何，有可能這次讀完後需要等待一個磁碟旋轉一周才能繼續讀取，而其他柱面能夠馬上進行讀取，這種情況下每次請求也會排隊。

通常情況下，磁碟在進行尋道時，其他進程會產生其他的磁碟請求。磁碟驅動程序會維護一張表，表中會記錄著柱面號當作索引，每個柱面未完成的請求會形成鏈表，鏈表頭存放在表的相應表項中。

一種對先來先服務的演算法改良的方案是使用 最短路徑優先(SSF) 演算法，下面描述了這個演算法。

假如我們在對磁軌 6 號進行定址時，同時發生了對 11 , 2 , 4, 14, 8, 15, 3 的請求，如果採用先來先服務的原則，如下圖所示

我們可以計算一下磁碟臂所跨越的磁碟數量為 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51，相當於是跨越了 51 次盤面，如果使用最短路徑優先，我們來計算一下跨越的盤面

跨越的磁碟數量為 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17 ，相比 51 足足省了兩倍的時間。

但是，最短路徑優先的演算法也不是完美無缺的，這種演算法照樣存在問題，那就是 優先順序 問題，

這里有一個原型可以參考就是我們日常生活中的電梯，電梯使用一種 電梯演算法(elevator algorithm) 來進行調度，從而滿足協調效率和公平性這兩個相互沖突的目標。電梯一般會保持向一個方向移動，直到在那個方向上沒有請求為止，然後改變方向。

電梯演算法需要維護一個 二進制位 ，也就是當前的方向位： UP(向上) 或者是 DOWN(向下) 。當一個請求處理完成後，磁碟或電梯的驅動程序會檢查該位，如果此位是 UP 位，磁碟臂或者電梯倉移到下一個更高級未完成的請求。如果高位沒有未完成的請求，則取相反方向。當方向位是 DOWN 時，同時存在一個低位的請求，磁碟臂會轉向該點。如果不存在的話，那麼它只是停止並等待。

我們舉個例子來描述一下電梯演算法，比如各個柱面得到服務的順序是 4，7，10，14，9，6，3，1 ，那麼它的流程圖如下

所以電梯演算法需要跨越的盤面數量是 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22

電梯演算法通常情況下不如 SSF 演算法。

一些磁碟控制器為軟體提供了一種檢查磁頭下方當前扇區號的方法，使用這樣的控制器，能夠進行另一種優化。如果對一個相同的柱面有兩個或者多個請求正等待處理，驅動程序可以發出請求讀寫下一次要通過磁頭的扇區。

對於磁碟來說，最影響性能的就是尋道時間和旋轉延遲，所以一次只讀取一個或兩個扇區的效率是非常低的。出於這個原因，許多磁碟控制器總是讀出多個扇區並進行高速緩存，即使只請求一個扇區時也是這樣。一般情況下讀取一個扇區的同時會讀取該扇區所在的磁軌或者是所有剩餘的扇區被讀出，讀出扇區的數量取決於控制器的高速緩存中有多少可用的空間。

磁碟控制器的高速緩存和操作系統的高速緩存有一些不同，磁碟控制器的高速緩存用於緩存沒有實際被請求的塊，而操作系統維護的高速緩存由顯示地讀出的塊組成，並且操作系統會認為這些塊在近期仍然會頻繁使用。

當同一個控制器上有多個驅動器時，操作系統應該為每個驅動器都單獨的維護一個未完成的請求表。一旦有某個驅動器閑置時，就應該發出一個尋道請求來將磁碟臂移到下一個被請求的柱面。如果下一個尋道請求到來時恰好沒有磁碟臂處於正確的位置，那麼驅動程序會在剛剛完成傳輸的驅動器上發出一個新的尋道命令並等待，等待下一次中斷到來時檢查哪個驅動器處於閑置狀態。

磁碟在製造的過程中可能會有瑕疵，如果瑕疵比較小，比如只有幾位，那麼使用壞扇區並且每次只是讓 ECC 糾正錯誤是可行的，如果瑕疵較大，那麼錯誤就不可能被掩蓋。

一般壞塊有兩種處理辦法，一種是在控制器中進行處理；一種是在操作系統層面進行處理。

這兩種方法經常替換使用，比如一個具有 30 個數據扇區和兩個備用扇區的磁碟，其中扇區 4 是有瑕疵的。

控制器能做的事情就是將備用扇區之一重新映射。

還有一種處理方式是將所有的扇區都向上移動一個扇區

上面這這兩種情況下控制器都必須知道哪個扇區，可以通過內部的表來跟蹤這一信息，或者通過重寫前導碼來給出重新映射的扇區號。如果是重寫前導碼，那麼涉及移動的方式必須重寫後面所有的前導碼，但是最終會提供良好的性能。

磁碟經常會出現錯誤，導致好的扇區會變成壞扇區，驅動程序也有可能掛掉。RAID 可以對扇區出錯或者是驅動器崩潰提出保護，然而 RAID 卻不能對壞數據中的寫錯誤提供保護，也不能對寫操作期間的崩潰提供保護，這樣就會破壞原始數據。

我們期望磁碟能夠准確無誤的工作，但是事實情況是不可能的，但是我們能夠知道的是，一個磁碟子系統具有如下特性：當一個寫命令發給它時，磁碟要麼正確地寫數據，要麼什麼也不做，讓現有的數據完整無誤的保留。這樣的系統稱為 穩定存儲器(stable storage) 。穩定存儲器的目標就是不惜一切代價保證磁碟的一致性。

穩定存儲器使用兩個一對相同的磁碟，對應的塊一同工作形成一個無差別的塊。穩定存儲器為了實現這個目的，定義了下面三種操作：

穩定寫指的就是首先將塊寫到比如驅動器 1 上，然後將其讀回來驗證寫入的是否正確，如果不正確，那麼就會再次嘗試寫入和讀取，一直到能夠驗證寫入正確為止。如果塊都寫完了也沒有驗證正確，就會換塊繼續寫入和讀取，直到正確為止。無論嘗試使用多少個備用塊，都是在對你驅動器 1 寫入成功之後，才會對驅動器 2 進行寫入和讀取。這樣我們相當於是對兩個驅動器進行寫入。

穩定讀指的就是首先從驅動器 1 上進行讀取，如果讀取操作會產生錯誤的 ECC，則再次嘗試讀取，如果所有的讀取操作都會給出錯誤的 ECC，那麼會從驅動器 2 上進行讀取。這樣我們相當於是對兩個驅動器進行讀取。

崩潰恢復指的是崩潰之後，恢復程序掃描兩個磁碟，比較對應的塊。如果一對塊都是好的並且是相同的，就不會觸發任何機制；如果其中一個塊觸發了 ECC 錯誤，這時候就需要使用好塊來覆蓋壞塊。

如果 CPU 沒有崩潰的話，那麼這種方式是可行的。如果在穩定寫期間出現 CPU 崩潰會怎麼樣？這就取決於崩潰發生的精確時間，有五種情況，下面來說一下

這種模式下進行任何優化和改進都是可行的，但是代價高昂，一種改進是在穩定寫期間監控被寫入的塊，這樣在崩潰後進行檢驗的塊只有一個。

有一種 非易失性 RAM 能夠在崩潰之後保留數據，但是這種方式並不推薦使用。

Ⅲ 電梯演算法是怎樣的

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

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

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

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

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

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

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

Ⅳ 求關於 多部電梯調度演算法研究

這里是我 一些 想法 LZ可以看看 在這里 主要告訴你的是 C程序設計裡面很重要的一個思想那就是 增量開發
首先設計 一個MAIN函數 確定要調用的函數 在函數裡面 盡量使用指針變數,這是第一塊
第二快: 電梯的初始化
第三快: RUNNING電梯的運行
第四快: 電梯的移動
第五快: 上和下
第六快: 用戶的要求 也就是說 電梯到底是上 還是下的設計
第七快 延遲程序 也就說 等待的時間
第八塊:STOP
按照這個思路的話,代碼加起來有100多行的樣子吧
還有就是 LZ在採用這個思路的時候 一定要對函數的運用 很上手啊
要不在調試的時候很容易出BUG的!
希望能幫到你!

Ⅳ 電梯調度演算法...

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

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

電梯內部關門按鈕：

電梯外部向上按鈕：

電梯外部向下按鈕：

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

Ⅵ 帕累托原則是什麼麥肯錫30秒電梯理論，莫法特休息法則是什麼

帕累托法則也叫20/80法則：在因和果，努力和收獲之間普遍存在著不平衡關系，典型的情況是，80%的收獲來自20%的努力，其他80%的氣力只產生20%的結果。

Ⅶ 操作系統模擬電梯調度演算法C語言程序

多級反饋隊列調度演算法 多級反饋隊列調度演算法是一種CPU處理機調度演算法，UNIX操作系統採取的便是這種調度演算法。 多級反饋隊列調度演算法即能使高優先順序的作業得到響應又能使短作業(進程)迅速完成。（對比一下FCFS與高優先響應比調度演算法的缺陷）。 多級(假設為N級)反饋隊列調度演算法可以如下原理： 1、設有N個隊列（Q1,Q2....QN），其中各個隊列對於處理機的優先順序是不一樣的，也就是說位於各個隊列中的作業(進程)的優先順序也是不一樣的。一般來說，優先順序Priority(Q1) > Priority(Q2) > ... > Priority(QN)。怎麼講，位於Q1中的任何一個作業(進程)都要比Q2中的任何一個作業(進程)相對於CPU的優先順序要高（也就是說，Q1中的作業一定要比Q2中的作業先被處理機調度），依次類推其它的隊列。 2、對於某個特定的隊列來說，裡面是遵循時間片輪轉法。也就是說，位於隊列Q2中有N個作業，它們的運行時間是通過Q2這個隊列所設定的時間片來確定的（為了便於理解，我們也可以認為特定隊列中的作業的優先順序是按照FCFS來調度的）。 3、各個隊列的時間片是一樣的嗎？不一樣，這就是該演算法設計的精妙之處。各個隊列的時間片是隨著優先順序的增加而減少的，也就是說，優先順序越高的隊列中它的時間片就越短。同時，為了便於那些超大作業的完成，最後一個隊列QN(優先順序最高的隊列)的時間片一般很大(不需要考慮這個問題)。 多級反饋隊列調度演算法描述： 1、進程在進入待調度的隊列等待時，首先進入優先順序最高的Q1等待。 2、首先調度優先順序高的隊列中的進程。若高優先順序中隊列中已沒有調度的進程，則調度次優先順序隊列中的進程。例如：Q1,Q2,Q3三個隊列，只有在Q1中沒有進程等待時才去調度Q2，同理，只有Q1,Q2都為空時才會去調度Q3。 3、對於同一個隊列中的各個進程，按照時間片輪轉法調度。比如Q1隊列的時間片為N，那麼Q1中的作業在經歷了N個時間片後若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完後作業還不能完成，一直進入下一級隊列，直至完成。 4、在低優先順序的隊列中的進程在運行時，又有新到達的作業，那麼在運行完這個時間片後，CPU馬上分配給新到達的作業（搶占式）。 我們來看一下該演算法是如何運作的： 假設系統中有3個反饋隊列Q1,Q2,Q3，時間片分別為2，4，8。 現在有3個作業J1,J2,J3分別在時間 0 ，1，3時刻到達。而它們所需要的CPU時間分別是3，2，1個時間片。 1、時刻0 J1到達。於是進入到隊列1 ， 運行1個時間片 ， 時間片還未到，此時J2到達。 2、時刻1 J2到達。 由於時間片仍然由J1掌控，於是等待。 J1在運行了1個時間片後，已經完成了在Q1中的 2個時間片的限制，於是J1置於Q2等待被調度。現在處理機分配給J2。 3、時刻2 J1進入Q2等待調度，J2獲得CPU開始運行。 4、時刻3 J3到達，由於J2的時間片未到，故J3在Q1等待調度，J1也在Q2等待調度。 5、時刻4 J2處理完成，由於J3，J1都在等待調度，但是J3所在的隊列比J1所在的隊列的優先順序要高，於是J3被調度，J1繼續在Q2等待。 6、時刻5 J3經過1個時間片，完成。 7、時刻6 由於Q1已經空閑，於是開始調度Q2中的作業，則J1得到處理器開始運行。 8、時刻7 J1再經過一個時間片，完成了任務。於是整個調度過程結束。

Ⅷ 操作系統磁碟調度的電梯演算法是怎麼回事阿思想是什麼比如磁軌號從41開始，磁碟請求序列為:20

就是讀取時按找當前的移動方向讀取下一個，到頂後再反著讀，就跟坐電梯一樣，要不先上，要不先下。
下：41 20 12 4 上： 44 76 80
合起來就是： 41 20 12 4 44 76 80
這樣的話磁頭的總移動距離會相對減少

Ⅸ 電梯調度演算法

(1)電梯調度演算法的處理次序為：
58143627

(2)最短尋找時間優先演算法的處理次序為：
58627143

Ⅹ 如何將各種演算法應用到實際的電梯調度中

說明 假設大廈有31層樓.電梯每經過1層(不論上下行)的時間是4秒.也就是說,電梯從1樓到31樓且中間不停則需要(31-1)*4=120秒.電梯每次需要停10秒,因此,如果電梯每層都停一次,就需要30*4+29*10=410秒.與此同時,員工步行一層樓(不論上下行)需要20秒,從1樓到31樓就需要30*20=600秒.明顯,這個主意不好.因此,很多員工依賴電梯前往他們的辦公室.現在我們需要設計一個方案，這個方案的設計目標是讓最後一個到達辦公室的員工花費最短的時間(也就是說,他並不保證每一位員工都能最快到達自己辦公室).比如,如果員工想到達4,5和10層,則電梯的運行方案是在4和10層停止.因為電梯在第12秒到達4層,停止10秒,則電梯到達10層需要3*4+10+6*4=46秒.按此計劃,住在4層的員工需要12秒,5層的員工需要12+20=32秒,10層的員工需要46秒.因此,最後到達辦公室的員工需要46秒.對於大家來說,這是個不錯的方案.

實現 下面就詳細說一說我實現的具體方式，雖然花了我近2天的時間，但是其實並不是很復雜，這里我本著拋磚引玉的原則，下面就一起來看看吧：

我們將定義一個名叫Case的class用來存儲一些要測試的數據，然後再定義一個叫CaseUtil的class用來實現我們的方案。

首先我說一下具體得思路：這里我只考慮從下到上的方案(從上到下其實是一樣的，具體自己想吧)。舉個例子，假設當前的樓層是【29 30 31】.3個。那麼我們該如何做呢？

首先，不管怎麼說，假設最後一層即31的到達時間為 （31-1）* 4 + （stopNums-1）*10 說明一下，這里為了簡單起見我們就按照案例的數據進行分析，實際上4表示電梯經過每層所需時間，而10表示電梯每層停靠的時間。上面的stopNums是什麼呢？就是電梯到達31層時所有的停靠次數，減去1是除去31層得停靠。而最後一層到達的人則很可能為最後一位到達的人，為什麼不是一定呢，按照本例，上面舉得例子就可以很簡單的看出，在28、31停2次即可，此時最後一個到達的就是地30層的人了。當然在僅僅是在本例中，實際上會由於具體數值不一樣而有不同。所以這里我用了可能，而它也和我們的最優解很接近了，而這給了我想法。雖然最後一層不一定是最後一位，但已經很接近了，而它所花費的時間，僅僅只和一個變數有關，即stopNums，即可以得出如下結論：

電梯的停靠次數越少，最後一層的時間也就越少，同樣最佳時間也就越少。

假設我們有一個方法可以根據當前的停靠次數來計算最佳的停靠方案，那麼我們該如何得到實際最佳方案呢？下面的一段代碼很好的可以達到我們的目標。