一、前言

本次博客我將簡單介紹一下前兩次的電梯作業，并簡單解析一下我的程序結構，進一步對我的第二次作業的算法核心和一些想法做一些分享，我的電梯設計算法并不是由調度器來決定電梯的捎帶與否，而是由電梯自主判斷，在沒有人員限制與其他條件的情況下，電梯自行判斷電梯外是否有人以及是否需要捎帶。

二、電梯作業的介紹

北航面向對象的課程第二單元要求設計一個載客電梯，該電梯為目的選層電梯，即需要使用電梯的人在未進入電梯時便已經輸入自己要去的樓層（該種電梯已經在一些辦公樓中投入使用），我們的任務是要實現它的調度算法，以實現最快最好運送完所有乘客，乘客的請求會在電梯運行過程紅不斷提出，我們則需要根據他們的請求控制電梯的運行，開關門，上下乘客。

三、第一、二次電梯作業的架構邏輯

簡單的電梯作業不考慮電梯的最大載客量和電梯可去樓層的限制，用多線程的方法實現，是一個經典的生產者-消費者模型，可以設計一個請求池，乘客這個群體視為生產者，不斷將請求放入池中，而電梯即使消費者，通過運行來滿足乘客請求，視為將請求取走，因此完全是一個標準的生產者-消費者模型，因此我們創建一個Elevator電梯類作為實現電梯動作的載體，即消費者，創建一個Input類從終端接受請求，并將請求不斷加入請求池中，即生產者，另外創建一個Dispatcher類，調度器，在第一次作業中調度器主要承擔請求池的角色，而我們的請求池則是一個Queue隊列，來存放和提供請求。

第一次作業UML類圖如下：

主類中是一個死循環，不斷從Input中接受請求，將請求放入Dispatcher，其中值得一提的是由于Input和Elevator都需要不斷調用調度器，因此Dispatcher實現單例模式，以保證線程的安全，每一次循環創建一個接受請求的線程和執行電梯動作的線程，Operate是一個線程類，Elevator也是單例模式，接受Operate的調用，結束的標志是Input接受到null后返回一個標志表示請求結束，而后便跳出死循環結束程序

第一次作業的調度算法是傻瓜調度，即接受一個完成一個，按順序執行請求，不存在捎帶，這樣的執行效率也毫無疑問是最低的，但是實現起來非常簡單，不再贅述

這里值得一提的是單例模式

單例模式，毫無疑問，從名字上就可以明白即對于一個類來說在整個程序中只創建一個實例，不允許創建多個實例，每次只能調用一個實例，對于共享的資源和需要重復調用的代碼塊使用synchronized關鍵字保護起來，單例模式是多線程設計中最為基礎和常見的一個模式，很好的保證了線程的安全，它的優點便是對于這種需要不安全的類實現了線程安全，但是缺點也顯而易見，對于公用的代碼塊或共享的數據資源，如果有一個線程在用，那么其他所有線程都必須在這里等待，必須等前一個線程用完后才可繼續執行，浪費了線程執行的時間；其次這樣的先到先得也破壞了線程之間的優先級，如果線程并發有優先級的限制，那么毫無疑問單例模式不能勝任這樣的任務，而信號量的機制，wait和notify的使用都可以解決這一問題。

第二次作業UML類圖如下：

整體架構與第一次作業沒有任何差別，因此不再贅述

設計思想有一些改變，首先調度器需要與電梯產生更多的交互，這要從我們的電梯說起，本次作業的電梯需要實現ALS即捎帶策略，那我的想法是由電梯自行決定是否捎帶，創建一個數組，對應每一樓層外的等待人數，例如如果8層有一個人按下了請求，那么floor[8]就會+1，如果這一層的人上了電梯，那么floor[8]就會-1。那么電梯每次執行都需要分兩步，1.判斷運行方向，運行方向有三種：向上，向下，停下，如果樓層外有人，或者電梯里有人要出來就停止運行，否則，根據電梯里所有請求的目的樓層離電梯目前樓層最近的那個樓層確定電梯向上or向下運行。2、在判斷完運行方向后，如果向上或向下，那么直接輸出相關信息，如果電梯停下，那么一定有人要進或者有人要出，先判斷是否有人出去，遍歷一下電梯中的人的目的樓層，如果有等于當前樓層的，就開門，先讓要出的人出去，隨后判斷是否有人要進入，如果電梯外的人的請求運行方向與電梯下一步的運行方向一致，便讓人進來，隨后關上電梯，并且根據電梯下一步運行方向執行向上或向下操作。

優化：以上是我的設計算法，但是這樣的捎帶策略未必會達到時間上的最優，因為我判斷電梯運行方向的方式是根據電梯里所有人的目的樓層離當前樓層最近的那一位而確定的，但是這樣的算法可能會出現多次折返的情況，因此，我想如果每次按電梯里所有人中離當前樓層最遠的那個樓層來確定執行方向，這樣最多兩次折返即可完成電梯中所有人的請求，雖然在一些小規模數據上性能并不一定優于之前的設計，甚至可能還差一點，但是不會出現那種極端的不斷折返的情況，提高了電梯調度的可靠性。

四、第三次作業的任務分配算法

在討論課上很多同學出現了A,B電梯任務繁重但是C電梯任務很輕的極大反差，請求任務的不均分配一定會降低電梯執行的效率，那么如何合理分配任務給電梯呢？我在這里提出我的一些想法：調度器中創建三個請求池，每一個請求隊列對應一個電梯，這樣每個電梯相互獨立，只會執行自己任務隊列中的任務，請求來的時候就確定加入哪一個請求隊列，也就確定了任務的分配，那么如何公平分配任務呢？首先給每個任務隊列對應一個變量，該變量是隊列中任務個數與電梯容量的比值，即任務越多，電梯越小，那么該值就會越大，每次來一個任務時，先判斷是否存在某兩個電梯之間的變量值之差超過了0.5，如果是，則讓任務輕的電梯接任務，如果該電梯不可以獨立完成，便確定兩電梯合作的匯合交接地點進而確定交接。如果沒有，則判斷是否可以由電梯獨立完成，可以便讓可以獨立完成并且值相對小的電梯接任務，如果否，便確定兩個合作的電梯，確定的原則還是值相對小的兩個電梯合作接任務，將請求拆分分別加入兩個請求隊列，對請求隊列中的每個請求設置有效值，只有前一個請求完成，后一個請求才有效可以執行，否則電梯會一直忽略該任務，知道該請求有效。

轉載于:https://www.cnblogs.com/oocj/p/buaaoo_homework_unit_2.html

總結

以上是生活随笔為你收集整理的Java实现目的选层电梯的调度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。