A. 2018-06-09
一、常見的批處理作業調度演算法
1.先來先服務調度演算法（FCFS）:就是按照各個作業進入系統的自然次序來調度作業。這種調度演算法的優點是實現簡單，公平。其缺點是沒有考慮到系統中各種資源的綜合使用情況，往往使短作業的用戶不滿意，因為短作業等待處理的時間可能比實際運行時間長得多。
2.短作業優先調度演算法(SPF): 就是優先調度並處理短作業，所謂短是指作業的運行時間短。而在作業未投入運行時，並不能知道它實際的運行時間的長短，因此需要用戶在提交作業時同時提交作業運行時間的估計值。
3.最高響應比優先演算法(HRN)：FCFS可能造成短作業用戶不滿，SPF可能使得長作業用戶不滿，於是提出HRN，選擇響應比最高的作業運行。響應比=1+作業等待時間/作業處理時間。
4. 基於優先數調度演算法(HPF)：每一個作業規定一個表示該作業優先順序別的整數，當需要將新的作業由輸入井調入內存處理時，優先選擇優先數最高的作業。
5.均衡調度演算法，即多級隊列調度演算法
基本概念：
作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)
作業平均周轉時間(T)＝周轉時間/作業個數
作業帶權周轉時間（Wi）＝周轉時間/運行時間
響應比＝（等待時間＋運行時間）/運行時間
二、進程調度演算法
1.先進先出演算法(FIFO)：按照進程進入就緒隊列的先後次序來選擇。即每當進入進程調度，總是把就緒隊列的隊首進程投入運行。
2. 時間片輪轉演算法(RR)：分時系統的一種調度演算法。輪轉的基本思想是，將CPU的處理時間劃分成一個個的時間片，就緒隊列中的進程輪流運行一個時間片。當時間片結束時，就強迫進程讓出CPU，該進程進入就緒隊列，等待下一次調度，同時，進程調度又去選擇就緒隊列中的一個進程，分配給它一個時間片，以投入運行。
3. 最高優先順序演算法(HPF)：進程調度每次將處理機分配給具有最高優先順序的就緒進程。最高優先順序演算法可與不同的CPU方式結合形成可搶占式最高優先順序演算法和不可搶占式最高優先順序演算法。
4. 多級隊列反饋法：幾種調度演算法的結合形式多級隊列方式。
三、空閑分區分配演算法
\1. 首先適應演算法：當接到內存申請時，查找分區說明表，找到第一個滿足申請長度的空閑區，將其分割並分配。此演算法簡單，可以快速做出分配決定。
2. 最佳適應演算法：當接到內存申請時，查找分區說明表，找到第一個能滿足申請長度的最小空閑區，將其進行分割並分配。此演算法最節約空間，因為它盡量不分割到大的空閑區，其缺點是可能會形成很多很小的空閑分區，稱為「碎片」。
3. 最壞適應演算法：當接到內存申請時，查找分區說明表，找到能滿足申請要求的最大的空閑區。該演算法的優點是避免形成碎片，而缺點是分割了大的空閑區後，在遇到較大的程序申請內存時，無法滿足的可能性較大。
四、虛擬頁式存儲管理中的頁面置換演算法
1.理想頁面置換演算法(OPT)：這是一種理想的演算法，在實際中不可能實現。該演算法的思想是：發生缺頁時，選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。
2.先進先出頁面置換演算法(FIFO)：選擇最先進入內存的頁面予以淘汰。
3. 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。
4.最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。
三、磁碟調度
1.先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置
2.最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題
3.掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。
4.循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。
對一個進程來說,一個重要的指標是它執行所需要的時間. 從進程提交到進程完成的時間間隔為周轉時間.也就是等待進入內存的時間,在就緒隊列中等待的時間,在 CPU中執行的時間和I/O操作的時間的總和.
例1.設一個系統中有5個進程，它們的到達時間和服務時間如下，A的到達時間為0，服務時間為3；B的到達時間為2，服務時間為6；C的到達時間為4，服務時間為4；D的到達時間為6，服務時間為5；E的 到達時間為8，服務時間為2，忽略1/0以及其他開銷時間，若分別按先來先服務（fFCFS）進行CPU調度，其平均周轉時間為？
10.2
6.4
8.6
4.5
先來先服務調度演算法
進程名 到達時間 服務時間 開始執行時間 完成時間 周轉時間
A 0 3 0 3 3
B 2 6 3 9 7
C 4 4 9 13 9
D 6 5 13 18 12
E 8 2 18 20 12
周轉時間 = 完成時間 - 到達時間
平均周轉時間 = 所有進程周轉時間 / 進程數 = （3+7+9+12+12）/ 5 = 8.6
單道批處理系統中有4個作業，J1的提交時間8.0，運行時間為2.0；J2的提交時間8.6，運行時間為0.6；J3提交時間8.8，運行時間為0.2；J4的提交時間9.0，運行時間為0.5。在採用響應比高者優先調度演算法時，其平均周轉時間為T為（）小時？
2.5
1.8
1.975
2.675
周轉時間=作業完成時間-作業提交時間
響應比=（作業等待時間+作業執行時間）/作業執行時間
當提交J1時，只有J1作業，執行J1，J1的周轉時間為2，此時時間為10.
J2、J3、J4提交時，由於正在執行J1，因此等待。
當J1執行完畢（此時時間為10），J2、J3、J4的等待時間分別為：1.4,1.2,1，
其響應比分別為：1.4/0.6+1=3.33 1.2/0.2+1=7 1/0.5+1=3，因此執行J3，J3的周轉時間為1.2+0.2=1.4
當J3執行完畢（此時時間為10.2），J2和J4的等待時間分別為1.6,1.2，
其響應比分別為：1.6/0.6+1=3.66 1.2/0.5+1=3.4，因此執行J2，J2的周轉時間為1.6+0.6=2.2
執行J2完畢後時間為10.8，接下來執行J4，執行完後時時間為11.3，J4的周轉時間為2.3
於是平均周轉時間為（2+1.4+2.2+2.3）/4=1.975
如果系統作業幾乎同時到達，則使系統平均作業周轉時間最短的演算法是短作業優先。
例3、
現有4個同時到達的作業J1,J2,J3和J4,它們的執行時間分別是3小時,5小時,7小時,9小時系統按單道方式運行且採用短作業優先演算法,則平均周轉時間是()小時
12.5
24
19
6
作業到達時間執行時間開始時間完成時間周轉時間
J103033
J20 5388
J30781515
J409152424
平均周轉時間（3+8+15+24）/4=12.5
有4個進程A,B,C,D,設它們依次進入就緒隊列，因相差時間很短可視為同時到達。4個進程按輪轉法分別運行11,7,2,和4個時間單位，設時間片為1。四個進程的平均周轉時間為 （）？
15.25
16.25
16.75
17.25
17.75
18.25
A:1 4 4 3 3 2 2 2 1 1 1 共24
B:2 4 4 3 3 2 2 共20
C:3 4 共7
D:4 4 3 3 共14
字母後面的數字為等待的時間加運行時間
平均周轉時間為（24+20+7+14）/4=16.25
例5、假設系統按單值方式運行且採用最短作業優先演算法，有J1,J2,J3,J4共4個作業同時到達，則以下哪幾種情況下的平均周轉時間為10分鍾?
執行時間J1:1分鍾 J2:5分鍾 J3:9分鍾 J4:13分鍾
執行時間J1:1分鍾 J2:4分鍾 J3:7分鍾 J4:10分鍾
執行時間J1:2分鍾 J2:4分鍾 J3:6分鍾 J4:8分鍾
執行時間J1:3分鍾 J2:6分鍾 J3:9分鍾 J4:12分鍾
首先，短作業優先則短時間的作業利用資源，其餘的作業等待
根據平均周轉時間概念，將所有作業"等待時間"加上"運行時間"除以"作業數量"即可得到平均周轉時間
A： (J1執行1分鍾 + J2等待1分鍾 + J2執行5分鍾 + J3等待6分鍾 + J3執行9分鍾 + J4等待15分鍾 + J4執行13分鍾) / 4 = 50/4 = 12.5
B： (J1執行1分鍾 + J2等待1分鍾 + J2執行4分鍾 + J3等待5分鍾 + J3執行7分鍾 + J4等待12分鍾 + J4執行10分鍾) / 4 = 40/4 = 10
C： (J1執行2分鍾 + J2等待2分鍾 + J2執行4分鍾 + J3等待6分鍾 + J3執行6分鍾 + J4等待12分鍾 + J4執行8分鍾) / 4 = 40/4 = 10
D： (J1執行3分鍾 + J2等待3分鍾 + J2執行6分鍾 + J3等待9分鍾 + J3執行9分鍾 + J4等待18分鍾 + J4執行12分鍾) / 4 = 50/4 = 12.5
例6、假設系統中有5個進程，它們的到達時間和服務時間見下表1，忽略I/O以及其他開銷時間，若按先來先服務（FCFS）、非搶占的短作業優先和搶占的短作業優先三種調度演算法進行CPU調度，請給出各個進程的完成時間、周轉時間、帶權周轉時間、平均周轉時間和平均帶權周轉時間，完成表2。 表1 進程到達和需要服務時間 進程 到達時間 服務時間 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2
表2 進程的完成時間和周轉時間
進程 A B C D E 平均
FCFS 完成時間 3 9 13 18 20
周轉時間 3 7 9 12 12 8.6
帶權周轉時間 1.00 1.17 2.25 2.40 6.00 2.56
SPF(非搶占) 完成時間 3 9 15 20 11
周轉時間 3 7 11 14 3 7.6
帶權周轉時間 1.00 1.17 1.75 2.80 1.50 1.84
SPF(搶占) 完成時間 3 15 8 20 10
周轉時間 3 13 4 14 2 7.2
帶權周轉時間 1.00 2.16 1.00 2.80 1.00 1.59
例7、假定在單道批處理環境下有5個作業，各作業進入系統的時間和估計運行時間如下表所示： 作業 進入系統時間 估計運行時間/分鍾 1 8:00 40 2 8:20 30 3 8:30 12 4 9:00 18
5 9:10 5
如果應用先來先服務和應用最短作業優先的作業調度演算法，試將下面表格填寫完整。
(1) 如果應用先來先服務的作業調度演算法，試將下面表格填寫完整。
作業 進入系統時間 估計運行時間/分鍾 開始時間 結束時間 周轉時間/分鍾
1 8:00 40 8：00 8：40 40
2 8:20 30 8：40 9：10 50
3 8:30 12 9：10 9：22 52
4 9:00 18 9：22 9：40 40
5 9:10 5 9：40 9：45 35
作業平均周轉時間T= 43.4 217
2）如果應用最短作業優先的作業調度演算法，試將下面表格填寫完整。 作業 進入系統時間 估計運行時間/分鍾 開始時間 結束時間 周轉時間/分鍾 1 8:00 40 8：00 8：40 40 2 8:20 30 8：52 9：22 62 3 8:30 12 8：40 8：52 22 4 9:00 18 9：27 9：45 45 5 9:10 5 9：22 9：27 17作業平均周轉時間T= 37.2 186
CPU和兩台輸入/輸出設備(I1,I2)多道程序設計環境下,同時有三個作業J1,J2,J3進行,這三個作業
使用CPU和輸入/輸出設備的順序和時間如下所示:
J1:I2(35ms);CPU(15ms);I1(35ms);CPU(15ms);I2(25ms)
J2:I1(25ms);CPU(30ms);I2(35ms)
J3:CPU(30ms);I1(25ms);CPU(15ms);I1(15ms);
假定CPU,I1,I2都能並行工作,J1的優先順序最高,J2次之,J3優先順序最低,優先順序高的作業可以搶占優先順序低的作業的CPU,但不能搶佔I1,I2,作業從J3開始到完成需要多少時間?
B. 用C語言如何描述電梯的運行機制
printf("上下選擇:1-上樓,2-下樓); scanf("%d",&input_direction); fflush(stdin);printf("輸入該層的乘客想到達的樓層,以-1結束
"）。
C語言是一門面向過程、抽象化的通用程序設計語言，廣泛應用於底層開發。1972 年，為了移植與開發 UNIX 操作系統，丹尼斯·里奇在貝爾電話實驗室設計開發了 C 語言。C語言是一種廣泛使用的計算機語言，它與 Java 編程語言一樣普及，二者在現代軟體程序員之間都得到廣泛使用。
C. 用C語言編寫一個關於電梯的程序
這是以前作的課程設計，是一個10層電梯的模擬，供樓主參考吧：
printf("上下選擇:1-上樓,2-下樓\t");
scanf("%d",&input_direction);
fflush(stdin);
printf("輸入該層的乘客想到達的樓層,以-1結束\n");
void check(liftor &myliftor) int flag1=0,flag2=0,flag3=0;
for(i=0;i<10;i++)
{
if(myliftor.stored_flare[i]!=0)
flag1=1;
if(myliftor.stored_flare[i]==1)
flag2=1;
if(myliftor.stored_flare[i]==2)
flag3=1;
}
if(!flag1) myliftor.set_direction(0);
else if(!flag2&&flag3) myliftor.set_direction(2);
else if(!flag3&&flag2) myliftor.set_direction(1);
int main(int argc, char *argv[])
liftor myliftor;
char flag;
int j;
myliftor.direction=1;
printf("**************************************\n");
printf("該程序用於模擬10(0-9)層的電梯控制\n");
printf("先輸入按下電梯的層號及上下選\n擇（類似電梯外的按鈕）\n");
printf("每到一層時，輸入乘客要到的樓\n層號（類似電梯內的按鈕)\n");
D. 操作系統模擬電梯調度演算法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再經過一個時間片，完成了任務。於是整個調度過程結束。
E. 這段代碼那裡錯了
首先你的排序函數是不對的，具體錯在你的交換a[i]和a[small]的值上，下面是我改的代碼：
void SelectSort(int a[],int n)
{
int i,j,small;
int temp;//temp是需要的。
for(i=0;i<n-1;i++)
{
small=i;//設第i個數據元素關鍵字最小
for(j=i+1;j<n;j++)//尋找關鍵字最小的數據元素
if(a[j]<a[small]) small=j;//記住最小元素的下標
if(small!=i)//當前最小元素的下標不為i是交換位置
{
temp = a[i]; //樓主錯在這里
a[i]=a[small];
a[small]=temp;
}
}
}
其次電梯調度部分寫得很混亂，錯誤很多，這里先來指出樓主的錯誤。
void SCAN(int a[],int m,int direction){
int k=0,j=0,i;
int temp[m];//存放磁軌的調度順序號
//int cur;//臨時變數，用於記錄調度的起始磁軌位置
if(direction==0)//磁頭向磁軌號增加的方向移動
{
for(;k<m;k++)
{
if(b[k]>=StartTrack)
{
//下面樓主開始犯錯誤了
//for(;k==m-1;k++)temp[k]=b[k];//樓主的源代碼，這里他犯了2個錯誤
//1、是for循環的條件，他寫的k==m-1，如果是這樣的話，那麼循環一次也不會進行。
//2、直接把b[k]上的值賦給了temp[k],注意此時k不是0...
//下面是修改後的代碼
for(i=0;k+1<m;i++)
{
temp[i]=b[k+i];
}
//在這里程序是不完整的，電梯這里只是走到了序號最大的地點，樓主的想法是想直接轉到else部分，其實他沒有理解if else到底是什麼意思。。。
}
else if(k==m-1)//樓主此處假設初始位置到頂了
{
direction=1;//省略部分代碼//這里不知道樓主省了什麼代碼，不過單是一個direction=1是無法完成演算法的，程序不會轉到else部分
int n;
for(n=i;i>0;i--,n++)
{
temp[n]=b[i];
}
}
}
}
else//磁頭向磁軌號減少的方向移動
{
for(;k<m;k++)
{
if(b[k]>StartTrack)
{
//這里樓主犯錯了for(;k==0;k--)temp[k]=b[k];//省略部分代碼//理由同上
for(i=0;k>0;i++){
temp[i]=b[k-1-i]; //修改好的代碼
}
//理由同上面相應部分
}
else if(k==m-1)
{
direction=0;//省略部分代碼
//此處理由同前相應部分
}
}
}
}
總結一下，樓主對 交換2個參量的值，條件判斷語句， for循環方面的知識需要加強。
下面貼出正確的電梯調度代碼：
本人使用的C++寫的，使用C語言的話，需要替換相應的代碼，如cout 換成相應的 printf（）
經測試可以通過。
#include<iostream>
int StartTrack=143;
void SelectSort(int[],int);
void SCAN(int[],int,int);
void display(int[],int);
int get_Position(int[],int,int);
int scanUP(int[] , int , int[] , int , int );
int scanDOWN(int[] , int , int[] , int , int);
void main()
{
int a[10] = {11,99,200,176,56,33,188,210,34,46};
SelectSort( a , 10 );
SCAN( a , 10 , 1);
}
void SelectSort(int a[] , const int a_size)
{
int i,j,small;
int temp;
for(i=0;i<a_size-1;i++)
{
small=i;//設第i個數據元素關鍵字最小
for( j = i + 1 ; j < a_size ; j++)//尋找關鍵字最小的數據元素
if( a[j] < a[small] ) small = j;//記住最小元素的下標
if( small != i)//當前最小元素的下標不為i是交換位置
{
temp = a[i];
a[i] = a[small];
a[small] = temp;
}
}
}
void display(int a[] ,const int a_size)
{
using namespace std;
for (int i = 0; i < a_size ; i++)
{
cout<<a[i]<<" ";
}
cout<<"\n";
cin.get();
cin.get();
}
void SCAN(int a[] ,const int a_size , int direction)
{
int result_Array[10];
int channel_number = StartTrack;
int current_pos = get_Position( a , a_size , channel_number );
if( direction == 0){
int pos = scanUP( a , a_size , result_Array , 0 , current_pos);
scanDOWN( a , a_size ,result_Array , pos , current_pos );
}
else {
int pos = scanDOWN( a , a_size , result_Array , 0 , current_pos);
scanUP( a , a_size ,result_Array , pos , current_pos );
}
display(result_Array , a_size);
}
/*
get_Position
This function return the position that the value
of this position in array a[] is larger than the StartTrack
*/
int get_Position(int a[] ,int a_size , int channel_number)
{
for(int i = 0 ; i < a_size ; i++ )
{
if( a[i] > channel_number) return i;
}
return a_size;
}
/*
Scan up
a[] is the array to be scaned.
a_size is the size of the array.
result[] is the array to store the result.
result_tear is the last position that the position of result[] is empty.
*/
int scanUP(int a[] , int a_size , int result[] , int result_tear , int start_position)
{
int i = 0;
for( ; start_position + i < a_size ;i++)
{
result[ result_tear + i] = a [start_position + i];
}
return i + result_tear;
}
/*
Scan down
a[] is the array to be scaned.
a_size is the size of the array.
result[] is the array to store the result.
result_tear is the last position that the position of result[] is empty.
*/
int scanDOWN(int a[] , int a_size , int result[] , int result_tear , int start_position)
{
int i = 0 ;
for( ; start_position - i > 0 ;i++)
{
result[i + result_tear] = a [start_position - 1 - i];
}
return i + result_tear;
}
F. 電梯程序 C語言
一頭霧水！
G. 關於電梯的C語言應用題求解答
#include<stdio.h>
intmain()
{
intn;
while(~scanf("%d",&n)&&n)
{
intlast=0;
intcur;
intt=0;
while(n--)
{
scanf("%d",&cur);
if(cur>last)t+=cur-last;
elset+=last-cur;
last=cur;
}
printf("%.2lf ",t*5.9);
}
return0;
}
H. 電梯調度演算法...
不管你是在北上廣還是在港澳台，甚至三四線城市，凡是有規模的地區，高樓比比皆是。不管是寫字樓，還是大型商城，讓你最頭痛的就是乘電梯，尤其是在趕時間的時候。
每天早上，那些差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秒後自動開門。
電梯內部關門按鈕：
電梯外部向上按鈕：
電梯外部向下按鈕：
你肯能意識到 哪個演算法都不是一個最佳方案，只是它確實解決了一定情況的問題 。但是對一個優秀的程序員而言，研究各種演算法是無比快樂的。也許你下一次面試，就有關於調度演算法的問題。
I. c語言電梯調度
為什麼沒人來回答呢？？