第一篇：單核與多核的CPU調度算法

1.多核CPU調度算法 1.1全局隊列調度算法

操作系統維護一個全局的任務等待隊列，每個進程在執行階段可以使用全部的處理器資源。當系統中有一個CPU核心空閑時，操作系統就從全局任務等待隊列中選取Ready進程開始在此核心上執行。

優點：CPU核心利用率較高，能保證全局資源的充分利用。

缺點：多處理器同時查找工作時，可能會降低處理器效率。且同一進程可能在不同內核上執行，造成的進程遷移開銷較大。1.2局部隊列調度算法

操作系統為每個CPU內核維護一個局部的任務等待隊列，將所有進程分配到與處理器對應的進程隊列中。當系統中有一個CPU內核空閑時，便從該核心的任務等待隊列中選取恰當的任務執行。

優點：充分利用局部緩存，降低了進程遷移的開銷。任務基本上無需在多個CPU核心間切換，有利于提高CPU核心局部Cache命中率。目前多數多核CPU操作系統采用的是基于全局隊列的任務調度算法。

缺點：可能造成某些處理器超負荷，而某些處理器空閑，即資源分配不均衡不充分，引起全局資源的不充分利用。2.簡單單核CPU調度算法

2.1 先到先服務調度算法：FCFS（first-come,first-served）

當一個進程進入到Ready隊列，其PCB就被鏈接到隊列的尾部。當CPU空閑時，CPU被分配給位于隊列頭的進程（即當前Ready隊列中已等待時間最長的進程）。接著，該運行進程從隊列中被刪除。

缺點：對于一個進程隊列，其總的周轉時間太長，且當進程的I/O較為密集時，效率將會變得相當低，CPU利用率也會變得很低。

優點：實現方式簡單，適用于長程調度和處理器密集的進程調度。常與優先級策略結合提供一種更有效率的調度方法。

2.2 最短作業優先調度算法：SJF（shortest-job-first）

SJF是一種非搶占式的調度算法，其實現原則是取Ready隊列中處理時間最短的進程加載入CPU，進入CPU執行的進程執行完后才釋放CPU，然后加載第二個進程進入CPU執行。

缺點：忽視了作業等待時間，會出現starvation現象，且作業執行時間無法提前知道，也很難預估。

優點：算法實現簡單，能有效地降低作業的平均等待時間，提高系統吞吐量，是理論上的最優調度算法。

2.3 最短剩余時間優先調度算法：SRTF（Shortest Remaining Time First）SRTF調度算法是搶占式的SJF調度算法，調度程序總是首先選擇預期剩余時間最短的進程加載進入CPU執行。

缺點：總是選擇預期剩余時間最短的進程，會造成starvation現象。有處理時間預估，效率不足夠高。

優點：不偏向長進程，沒有額外的中斷，因此開銷較低。且對于一個進程隊列，總的周轉時間較短，執行效率較高，對短進程的響應較快。2.4 優先級調度算法

每個進程都有一個自己的優先級，Ready隊列采用優先級隊列實現，CPU每次取Ready隊列隊首的進程。通常情況，當兩個進程的優先級相同時，我們在相同優先級的進程之間采用FCFS調度算法。優先級可以通過內部或外部方式來定義。

缺點：會出現starvation現象（也稱無窮阻塞），且不適用于分時系統或交互式事務處理環境。

優點：主要用于批處理系統中，也可用于某些對實時性要求不嚴的實時系統中?？梢圆捎美匣夹g，每個進程執行以后其優先級降低，以此來克服starvation的缺點。2.5 輪轉法調度算法

輪轉法（RR）調度算法是專門為分時系統設計的，是一種基于時鐘的搶占策略。定義一個小時間單元，稱為時間量或時間片。時間片通常為10ms到100ms。將Ready隊列作為循環隊列處理。CPU調度程序循環就需隊列，為每個進程分配不超過一個時間片間隔的CPU。如果上下文切換時間約為時間片的10%，那么約10%的CPU時間會浪費在上下文切換上。

缺點：時間片長度設計較難，當時間片長度過大時，會退化成FCFS調度算法。調度I/O密集型進程時效率較低。由于輪詢調度在調度過程中不考慮瞬時信道條件，因此它將導致較低的整體系統性能。

優點：對不同的分組業務流隊列進行同樣的無差別的循環調度服務，對于等長業務流隊列是公平的，不存在starvation現象。2.6 最高響應比優先調度算法

首先需要理解一個概念，叫作響應比。響應比的計算表達式為

其中R為響應比，w為等待處理器的時間，s為預計服務的時間。當進程被立即調用時，R等于歸一化周轉時間。

調度算法的過程是，當進程完成執行或被阻塞時，選擇R值最大的Ready進程加載進入CPU執行。

缺點：需要預估服務時間s，效率不太高。優點：能克服starvation現象。3.復雜單核CPU調度算法

3.1 多級隊列調度算法（multilevel queue-scheduling algorithm）將Ready隊列分成多個獨立的隊列，對Ready隊列和每個獨立的隊列采用不同的調度算法進行執行。常用的方式是，Ready隊列采用優先級調度算法，不同隊列根據實際情況采用合適的調度算法即可。

優點：綜合了多種調度算法，避免了starvation現象，最大限度地提高了調度效率，也提高了CPU利用率。3.2 多級反饋隊列調度算法

UNIX OS采用的調度算法。其詳細過程如下： 1.進程在進入待調度的隊列等待時，首先進入優先級最高的Q1等待。

2.首先調度優先級高的隊列中的進程。若高優先級中隊列中已沒有調度的進程，則調度次優先級隊列中的進程。例如：Q1,Q2,Q3三個隊列，只有在Q1中沒有進程等待時才去調度Q2，同理，只有Q1,Q2都為空時才會去調度Q3。

3.對于同一個隊列中的各個進程，按照時間片輪轉法調度。比如Q1隊列的時間片為N，那么Q1中的作業在經歷了N個時間片后若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完后作業還不能完成，一直進入下一級隊列，直至完成。

4.在低優先級的隊列中的進程在運行時，又有新到達的作業，那么在運行完這個時間片后，CPU馬上分配給新到達的作業（搶占式）。

優點：既能使高優先級的作業得到響應又能使短作業(進程)迅速完成。4.多核CPU調度算法與單核CPU調度算法對比

從上面的不同CPU調度算法，我們不難發現，單核CPU調度算法是多核CPU調度算法的基礎，多核CPU調度算法是單核CPU調度算法的延伸和綜合使用。我以大篇幅介紹了單核CPU的調度算法，而以少量的篇幅介紹了多核CPU調度算法，其目的也在于說明此結論。

多核CPU調度算法中，無論是全局隊列調度算法還是局部隊列調度算法，其實現原理均可采用單核CPU調度算法中的某一個或一些綜合起來實現。例如局部隊列調度算法，每一個局部隊列就相當于一個單核CPU調度隊列，可以采用合適的單核CPU調度算法去實現。

第二篇：操作系統實驗二——cpu調度與內存分頁

一、試驗目的

理解操作系統內存管理的原理及分頁內存管理方案

二、試驗要求

1、實現分頁內存管理方案，假定頁和幀的大小均為4KB，物理內存為128MB

2、輸入為進程ID，所需內存大小等，輸出為頁表。

3、請按要求撰寫實驗報告，并和源程序一起打包上傳

4、實驗平臺不限，linux和windows均可

5、與第一次實驗的程序整合成一個程序

三、試驗環境

Windows XP Visual C++ 6.0

四、試驗內容

為了與上一個實驗結合，并且考慮到可能需要兼容以后的實驗，所以本次實驗不但重寫了PCB，而且按照自己對操作系統的理解構造出了一虛擬的I/O設備和兩套調度程序（作業調度程序和CPU調度程序）

一、首先從與內存分配相關的作業調度函數說起，程序中為Jobs_scheduler。Job_scheduler的作用如下圖所示;

Job_scheduler從大容量存儲設備上的緩沖池中載入新生成的進程到內存，同時生成新的PCB到就緒隊列中。這里涉及到了兩個數據結構class Program，class PCB。Program ：

PCB：

PCB中的state包含五個狀態NEW、READY、RUN、WAITING、TERMINATED，加入到ReadyQueue中等待運行的PCB均為READY狀態的，運行中會被置為RUN，WAITNG狀態為等待I/O設備的進程，如果進程狀態為TERMINATED，將會被移出作業隊列。

Job_scheduler函數在將program裝入內存前，會查看幀表內空閑的幀的數目是否大于等于program所需的頁數目，如果成立才裝入，并且為PCB構造頁表。構造時，先按照幀表通過順序查找找到可用的幀，然后就將頁的內容加載上去。

二、接下來是CPU調度程序，也成為短期調度程序。

CPU_scheduler所做的工作如下圖所示，其操作的隊列是就緒隊列RedayQueue

本程序采用的調度算法為分時調度，時間片大小TimeSlice取為1（當然這個隨時都可用改動），里面執行程序的函數Run是模擬CPU功能的，它會返回一個值，Normal表示執行正常，若是返回了INTERRUPT 中斷；ERROR 出錯就會中斷此次運行，并且將所指PCB從ReadyQueue中移除。

這里的Run函數其實模擬了CPU的取指令和翻譯指令的功能，本程序只有一個有實際作用的指令，'O'，如果內存中的內容為'0'（十進制ASCⅡ碼值），則代表需要利用I/O設備輸出該地址內容。如上圖所示，PCB會加入到WaitingQueue中等待I/O，并判斷此時I/O設備是否開啟，如果未開啟則開啟設備。Run函數也因此返回一個interrupt值。運行結果

在編號為1的進程中的第一個內存單位設置了一條I/O指令，可以看出其發生中斷后等待I/O完成才重新回到ReadyQueue中并執行完畢。

以上結果是在內存足夠大的情況，下面再看一組內存不能同時滿足需求的情況

此次內存設為11幀，編號為1的進程需要10幀，編號為2的進程需要1幀，我們看到，2號進程順利載入并執行了，但其他進程都要等到1號進程執行完釋放內存后才能載入內存，符合預期情況。

五、心得體會

為了很好的仿真，本次試驗盡可能地模擬了硬件的工作，如輸入輸出設備和模擬CPU的run函數，基本上把教材77頁調度問題的隊列圖所示功能模擬出來了，也大體實現了從用戶程序到系統進程再到硬件的執行過程。

對于本次實驗的核心內容——內存管理，實現了從磁盤到內存額裝載過程，實現了頁表的創建，實現了內存的釋放。缺陷是沒有考慮到換入換出等動態的情況，也就是說在此做了一個假設：每個進程相互獨立且對于每個單獨的進程來說，內存空間是足夠大的。

第二點缺陷是，沒有按照題目要求分配那么多的內存空間，因為那么大輸入輸出不好控制。

在本程序中，輸入輸出與要求有出入，并沒有輸入進程需要的時間，而是以進程的具體內容代替，在這里又有一個假設：假設進程在CPU中每執行一步需要一個單位的時間，這樣進程的大小也就等價于進程需要的時間了（排除有I/O請求的情況），個人認為這樣假設比人工限定執行時間更加貼近現實情況。

程序的輸入非即時的，而是通過事先設定好的5個進程加上運行后隨機生成的若干進程，也是為了模擬實際情況考慮。

因為全手工輸入需要輸入進程的到達時間，也就是需要根據到達時間來為緩沖池中進程排序的問題，但實際情況下到達時間是多余的，先創建的先加入隊列即可，所以采用了隨機生成的方式。

為了此次實驗，復習了調度和內存管理兩章的大部分內容，對操作系統對進程調度和內存分配管理有了更深入的認識，但只是從概念上，沒有看到真正操作系統的代碼或者算法實例，所以可能很多地方的代碼與實際情況出入很大。

代碼：

#include #include #include #include #include #include #include #include using namespace std;

/***************

隨機數，后面隨機生成進程用的 *************/ void rand_seed(){ int seed = static_cast(time(0));srand(seed);}

int rand_int(int a, int b){ return a + rand()%(b1)

{

pc[1]++;

}

else

{

pc[0]++;

pc[1] = 0;

}

pcb.state = READY;} else if(pc[1] < PAGE-1){

pc[1]++;} else

pcb.state = TERMINATED;}

bool io_equipment = OFF;/* I/O設備(DMA)*/ DWORD WINAPI IOEquipment(LPVOID lpParamter){ io_equipment = ON;list

::iterator pw = WaitingQueue.begin();while(pw!= WaitingQueue.end()){

/* 為了體現I/O設備速度較慢，所以在此用了Sleep函數 */

Sleep(1000);

cout << “P” << pw->number << “ I/O : ”<<(char)Memory[AddOfIO] << endl;

if(pw->state == WAITING)

pw->state = READY;

ReadyQueue.push_back(*pw);

pw = WaitingQueue.erase(pw);

if(pw!= WaitingQueue.end())

pw++;

else

pw = WaitingQueue.begin();} io_equipment = OFF;return FINISH;}

HANDLE ioEquipment;/**

模擬CPU執行

只實現了部分功能，并沒有完全按照原理模擬

**/ int Run(PCB& pcb){ pcb.state = RUN;list

::iterator p = pcb.PageTable.begin();int addr[2];

addr[1] = pcb.pc[1];addr[0] = pcb.findframe(pcb.pc[0]);

switch(Memory[addr[0] * FRAME + addr[1]]){ case 'O': //如果指令觸發了輸出設備

pcb.state = WAITING;

pcr[0] = pcb.pc[0];

pcr[1] = pcb.pc[1];

IncPc(pcb, pcr);

pcb.pc[0] = pcr[0];

pcb.pc[1] = pcr[1];

AddOfIO = addr[0] * FRAME + addr[1];

WaitingQueue.push_back(pcb);

/* 如果I/O設備未開啟，則打開，否則什么都不做 */

if(io_equipment == OFF)

ioEquipment = CreateThread(NULL, 0, IOEquipment, NULL, 0, NULL);

else

;

return INTERRUPT;default :

break;}

/* 在沒有跳轉的情況下，運行之后，pc自加 */ pcr[0] = pcb.pc[0];pcr[1] = pcb.pc[1];IncPc(pcb, pcr);pcb.pc[0] = pcr[0];pcb.pc[1] = pcr[1];

return NORMAL;}

HANDLE hMutex = CreateMutex(NULL, FALSE, “screen”);

/* 長期調度程序,將緩沖池中的進程加載到內存上 */ DWORD WINAPI Jobs_scheduler(LPVOID lpParamter){ list

::iterator p = BufferList.begin();while(true){

//WaitForSingleObject(hMutex, INFINITE);

if(p!= BufferList.end()&& p->page_numbers <= FraTable.free_frame)

{

ReadyQueue.push_back(PCB(*p));

p = BufferList.erase(p);

}

else if(p!= BufferList.end())

p++;

else

p = BufferList.begin();

//ReleaseMutex(hMutex);

} }

/* 利用RR算法的短期調度程序 */ DWORD WINAPI CPU_scheduler(LPVOID lpParamter){ list

::iterator p = ReadyQueue.begin();int run_time = 0;int total_time = 1;while(true){

WaitForSingleObject(hMutex, INFINITE);

if(p == ReadyQueue.end())

p = ReadyQueue.begin();

while(run_time < TimeSlice && p->state == READY)

{

p->run_time++;

run_time++;

//cout << total_time++ << endl;

cout << “p” << p->number << “ ” << “run time ” << p->run_time << endl;

if(Run(*p)== NORMAL)

/* do nothing */;

else

{

p = ReadyQueue.erase(p);

break;

}

/* 操作系統負責計時 */

}

run_time = 0;

if(p->state == TERMINATED)

{

Release(*p);

p = ReadyQueue.erase(p);

}

else

{

p++;

}

ReleaseMutex(hMutex);} }

int main(){ int num = 1;Program p1(num++, “O123456089”);Program p2(num++, “0”);Program p3(num++, “01”);Program p4(num++, “01”);Program p5(num++, “01234”);BufferList.push_back(p1);BufferList.push_back(p2);BufferList.push_back(p3);BufferList.push_back(p4);BufferList.push_back(p5);

HANDLE hThread1 = CreateThread(NULL, 0, Jobs_scheduler, NULL, 0, NULL);HANDLE hThread2 = CreateThread(NULL, 0, CPU_scheduler, NULL, 0, NULL);while(true)

{

if(num < 7)

BufferList.push_back(Program(num++, “156789”));}

return 0;}

第三篇：電梯優先調度算法

電梯優先調度算法

電梯調度算法(ms InterView)

移臂調度算法包括以下四種：

1）先來先服務算法：根據訪問者提出訪問請求的先后次序來決定執行次序。

2）最短尋找時間優先調度算法：從等待的訪問者中挑選尋找時間最短的那個請求執行，而不管訪問者的先后次序。

3）電梯調度掃描算法：從移動臂當前位置沿移動方向選擇最近的那個柱面的訪問者來執行，若該方向上無請求訪問時，就改變移動方向再選擇。

4）單向掃描調度算法：從0柱面開始往里單向掃描，掃到哪個執行哪個。

*/

// t1.cpp : 定義控制臺應用程序的入口點。

//

#include “stdafx.h” #include“math.h” #include“stdlib.h” #include“string.h” struct Head {

int nPosition;bool bVisited;};

void Visit(struct Head *pHead){

printf(“visite cy:%dn”,pHead->nPosition);pHead->bVisited=true;} int ReadInputKeyboard(struct Head *pHead,int *pCurrentPosition,int nMaxNumber){ int i;

printf(“please input Current position:”);scanf(“%d”,pCurrentPosition);

printf(“please input will visit position:”);for(i=0;i

scanf(“%d”,&pHead[i].nPosition);pHead[i].bVisited=false;if(pHead[i].nPosition<0)break;} return i;} int ReadInputFile(struct

Head

*pHead,int

*pCurrentPosition,int nMaxNumber){ int i;

char szFileName[256],*q,*p,szTemp[20];printf(“please input filename:”);scanf(“%s”,szFileName);

FILE *pFile=fopen(szFileName,“r”);if(pFile==NULL){

printf(“open file %s error”,szFileName);return-1;}

for(i=0;!feof(pFile)&&i

p=szFileName;fgets(p,256,pFile);

while(q=strchr(p,',')){

memset(szTemp,0,sizeof(szTemp)*sizeof(char));strncpy(szTemp,p,q-p);p=q+1;if(i==0)

*pCurrentPosition=atoi(szTemp);else { pHead[i-1].nPosition=atoi(szTemp);pHead[i-1].bVisited=false;} i++;}

memset(szTemp,0,sizeof(szTemp)*sizeof(char));pHead[i-1].nPosition=atoi(p);pHead[i-1].bVisited=false;//i++;

}

fclose(pFile);return i;}

int FifoVisit(int nCurrentPosition,struct Head *pHead,int nNumber){

//先來先服務

int nHaveVisited=0;int nMoveDistance=0;int i;while(nHaveVisited

for(i=0;i

if(pHead[i].bVisited)continue;

Visit(&pHead[i]);nHaveVisited++;

nMoveDistance+=abs(nCurrentPosition-pHead[i].nPosition);nCurrentPosition=pHead[i].nPosition;} }

printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;}

int SsfoVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ // 最短尋找時間優先

int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i;

while(nHaveVisited

nMinDistance=0xffff;nMinIndex=0;//找最小值

for(i=0;i

if(pHead[i].bVisited)continue;

if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){

nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } //訪問

Visit(&pHead[nMinIndex]);nHaveVisited++;

nMoveDistance+=nMinDistance;

nCurrentPosition=pHead[nMinIndex].nPosition;}

printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;}

int DtVisit(int nCurrentPosition,bool bOut,struct Head *pHead,int nNumber){

//電梯調度算法

int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i;

while(nHaveVisited

nMinDistance=0xffff;nMinIndex=0;//找最小值

for(i=0;i

if(pHead[i].bVisited)continue;

if(bOut&&pHead[i].nPositionnCurrentPosition){

if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){

nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } }

if(nMinDistance==0xffff){

bOut=!bOut;continue;}

//訪問

Visit(&pHead[nMinIndex]);nHaveVisited++;

nMoveDistance+=nMinDistance;

nCurrentPosition=pHead[nMinIndex].nPosition;}

printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;}

int DxVisit(int nCurrentPosition,struct Head *pHead,int nNumber){

//單向調度算法

int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i;while(nHaveVisited

nMinDistance=0xffff;nMinIndex=0;//找最小值

for(i=0;i

if(pHead[i].bVisited)continue;

if(pHead[i].nPosition>nCurrentPosition){

if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){

nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } }

if(nMinDistance==0xffff){

nMoveDistance+=199-nCurrentPosition;nCurrentPosition=0;continue;}

//訪問

Visit(&pHead[nMinIndex]);nHaveVisited++;

nMoveDistance+=nMinDistance;

nCurrentPosition=pHead[nMinIndex].nPosition;}

printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;}

int main(int argc, char* argv[]){ //p114 struct Head mylist[20];//={98,false,183,false,37,false,122,false,14,false,124,false,65,false,67,false};

//int nCurrentPosition=53;

//int nRealNumber=8;

int nCurrentPosition=0;

int nRealNumber=ReadInputFile(mylist,&nCurrentPosition,20);// FifoVisit(nCurrentPosition,mylist,nRealNumber);

// SsfoVisit(nCurrentPosition,mylist,nRealNumber);

//DtVisit(nCurrentPosition,false,mylist,nRealNumber);

DxVisit(nCurrentPosition,mylist,nRealNumber);

return 0;}

第四篇：常用進程調度算法的分析與評價

常用進程調度算法的分析與評價

（一）2009-10-31 22:48

進程調度是按照某種調度算法從就緒狀態的進程中選擇一個進程到處理機上運行。進程調度的兩種方式 ：

(1)非搶占調度方式

在這種調度方式中，OS一旦把處理機分配給某個就緒狀態的進程后，就讓該進程一直執行下去，直至該進程完成或由于該進程等待某事件發生而被阻塞時，才把處理機分配給其他進程。

(2)搶占調度方式

在這種調度方式中，進程調度程序可根據某種原則停止正在執行的進程，將已分配給當前進程的處理機收回，重新分配給另一個處于就緒狀態的進程。

搶占進程調度的原則：

（1）時間片原則：各進程按系統分配給的一個時間片運行，當該時間片用完或由于該進程等待某事件發生而被阻塞時，系統就停止該進程的執行而重新進行調度。

（2）優先級原則：每個進程均賦于一個調度優先級，通常一些重要和緊急的進程賦于較高的優先級。當一個新的緊迫進程到達時，或者一個優先級高的進程從阻塞狀態變成就緒狀態的時，如果該進程的優先級比當前進程的優先級高，OS就停止當前進程的執行，將處理機分配給該優先級高的進程，使之執行。

（3）短進程優先原則：當新到達的作業對應的進程比正在執行的作業對應進程的運行時間明顯短時，系統剝奪當前進程的執行，而將處理機分配給新的短進程，使之優先執行。進程調度算法評價依據

進程調度性能的衡量方法可以分為定性和定量兩種，在定性衡量方面，首先是調度的安全性。比如，一次進程調度是否可能引起數據結構的破壞等。這要求對調度時機的選擇和保存CPU現場十分小心。另外，系統開銷也是衡量進程調度的一個重要指標，由于調度程序的執行涉及到多個進程的上下文切換，如果調度策略過于繁瑣和復雜，將會耗去較大的系統開銷。這在用戶進程調度系統調用較多的情況下，將會造成響應時間大幅度增加。

進程調度的定量評價包括CPU的利用率評價、進程在就緒隊列中的等待時間與執行時間之比等。實際上，由于進程進入就緒隊列的隨機模型很難確定，而且進程上下文切換等也將影響進程的執行效率，從而對進程調度進行解析是很困難的，一般情況下，大多利用模擬或測試系統響應時間的方法來評價進程調度的性能。

常用進程調度算法的分析與評價

（二）2009-11-01 20:22

四種常用進程調度算法的分析與評價

3.1 先來先服務算法

3.1.1 算法思想

該算法思想是按照進入就緒隊列的先后次序來分配處理機。FCFS采用非剝奪調度方式，即

一旦某個進程占有處理機，就一直運行下去，直到該進程完成其工作或因等待某一事件而不能繼續執行時才釋放處理機。

3.1.2 算法實現原理圖

該算法實現原理圖如圖1所示。

說明：Ready表示就緒隊列，Pi表示新進入隊列的進程，Finish表示進程運行完畢退出。

3.1.3 算法分析與評價

① 該算法原理簡單，易于實現。

② 各進程平等競爭。

③ 由于各進程執行的時間不一樣，從而導致相對不公平現象的產生。

④ 該算法有利于長進程，不利于短進程。

⑤ 該算法很少用來作為主調度策略，常常用作輔助調度算法使用

3.2最高優先權優先調度算法

3.2.1 算法思想

該算法的基本思想是進程優先權高者優先調度，是一種最常用的進程調度算法。該算法的關鍵是如何確定優先數。通常確定優先數的方法有兩種，即靜態法和動態法。

靜態優先權是在創建進程時確定的，其運行特征是優先數確定之后在整個進行運行期間不再改變。確定靜態優先權的依據有進程的類型、進程所使用的資源、進程的估計運行時間等因素。進程所申請的資源越多，估計的運行時間越長，進程的優先權越低。進程類型不同，優先權也不同，如系統進程的優先權高于用戶進程的優先權。

動態優先權是指在創建進程時，其運行特征是根據系統資源的使用情況和進程的當前特點確定一個優先權，在進程運行過程中再根據情況的變化調整優先權。動態優先權一般根據進程占有CPU時間的長短、進程等待CPU時間的長短等因素確定。占有處理機的時間越長，則優先權越低；等待時間越長，則優先權越高。

3.3.2 算法分析與評價

① 靜態優先級調度算法實現較為簡單，但不能反映系統以及進程在運行過程中發生的各種變化。而動態優先級法可以滿足這個方面的需要。

② 動態優先級調度算法的性能一般介于時間片輪轉算法和先來先服務算法之間。

常用進程調度算法的分析與評價

（三）2009-11-01 20:23

3.3時間片輪轉調度算法

3.3.1 算法思想

該算法思想是使每個進程在就緒隊列中的等待時間與享受服務的時間成比例。即將CPU的處理時間分成固定大小的時間片，如果在執行的一個進程把它分給它的時間片用完了，但任務還沒有完成，則它也只能停止下來，釋放它所占的CPU資源，然后排在相應的就緒隊列的后面去。

3.3.2 算法實現原理圖

該算法實現原理圖如圖2所示

說明：Ready表示就緒隊列，Pi表示新進入隊列的進程，Finish表示進程運行完畢退出。Not Finish表示分配給某進程的時間片已用完但任務還沒有完成，從而插入到Ready隊列尾部。

3.3.3 算法分析與評價

① 時間片的長度選擇比較困難

時間片的長度選擇比較困難是因為時間片長度的選擇直接關系到系統開銷和進程的響應時間。如果時間片長度過短→導致調度程序剝奪處理器的次數增加→進程的上下文切換的次數增加→系統的開銷也加重；如果時間片長度過長，長到能使就緒隊列中所需要執行時間最長的進程執行完

畢→輪轉法就變成了FCFS算法→FCFS短處不足就顯示出來了。

又因為CPU的整個執行時間＝各進程執行時間之和＋系統開銷（各進程切換所花費的CPU時間之和，假定存儲開銷忽略不計）。即。因此，時間片的長短通常需要由以下因素確定：↙系統的響應時間。

↙就緒隊列中的進程數。

↙進程的切換時間。

↙ 計算機的處理能力，計算機的速度越高，時間片就可越短。

② 時間片長度選擇的動態性

以上僅僅作了靜態分析，通常情況下，就緒隊列里地進程個數是不斷變化的。因此，每一次的調度都需要計算新一輪的時間片長度，不能用固定的時間片長度來進行所有進程的輪轉執行。③ 該算法的擴充——多級反饋輪轉法

在上面的算法中，未對就緒隊列中的進程加以條件分析（即進入就緒隊列的因素），由于進入就緒隊列的原因不一樣，要求占用處理機的緊急程度也不一樣。主要因素有：↙分給該進程的時間片用完，但進程還未完成。

↙ 分給其時間片未用完，而發生了I/O等請求后由阻塞態轉變成就緒態。

↙新的進程進入。

因此，根據緊急程度的不一樣，建立多個就緒隊列，同時賦予不同的的優先級，優先權高的就緒隊列優先執行，同一就緒隊列中，優先級相同，按照先來先服務進行調度，運行一個給定的時間片，如果沒有執行完成則轉入到相應的就緒隊列中去（運行一次，優先級降低一個等級，等待一個時間片，則優先級升高一個等級）。其實現原理圖如圖3所示。

3.4 短進程優先調度算法

3.4.1 算法思想

該算法的基本思想是從就緒隊列（內存）中選擇一個估計運行時間最短的進程，將處理機分配給它。

3.4.2 算法分析與評價

① 該算法能有效降低作業的平均等待時間，提高系統吞吐量。

② 對長進程不利，甚至導致長期得不到處理。

③ 該算法完全未考慮進程的緊迫程度。

④ 進程的長短通常由某種策略估計提供，不能做到真正的短進程優先。

4結語

綜述所述，本文從算法思想、算法的實現原理、算法的優缺點等幾個方面對先來先服務算法、時間片輪轉算法、最高優先權優先調度算法、短進程優先調度算法等四種進程調度算法進行詳細地論述。（轉自《計算機與信息技術》）

第五篇：操作系統課程設計-磁盤調度算法

1.實驗題目:

磁盤調度算法。

建立相應的數據結構；

在屏幕上顯示磁盤請求的服務狀況；

將一批磁盤請求的情況存磁盤文件，以后可以讀出并重放； 計算磁頭移動的總距離及平均移動距離； 支持算法：FIFO、SSTF、SCAN、CSCAN;

2.設計目的:

調度磁盤I/O請求服務，采用好的方式能提高訪問時間和帶寬。本實驗通過編程對磁盤調度算法的實現，加深對算法的理解，同時通過用C++語言編寫程序實現這些算法，并在windos平臺上實現，更好的掌握操作系統的原理以及實現方法，提高綜合運用專業課知識的能力。

3.任務及要求

3.1 設計任務

編程實現下述磁盤調度算法，并求出每種算法的平均尋道長度：

1、先來先服務算法（FCFS）

2、最短尋道時間算法（SSTF）

3、掃描算法（SCAN）

4、循環掃描算法（CSCAN）

3.2 設計要求

對用戶指定的磁盤調度請求序列，基于以上四種算法，實現各自的調度順序并輸出，同時計算出各種算法下的平均尋道長度。

4.算法及數據結構

4.1算法的總體思想

queue[n] 為請求調度序列，diskrode為磁盤磁道數，headstarts為正在調度的磁道

①先來先服務算法（FCFS）按queue[n]數組的順序進行磁盤調度，將前一個調度磁道與下一個調度磁道的差值累加起來，得到總的尋道長度，再除以n得到平均尋道長度。

②最短尋道時間優先算法（SSTF）將queue[n]進行由小到大的排序，首先定位當前調度磁headstarts在queue[n]的位置，通過循環語句找出離起始磁頭最短的位置。

③掃描算法（SCAN）

將queue[n]進行由小到大的排序，首先定位當前調度磁headstarts在queue[n]的位置，然后在此位置按給定的方向遍歷queue[n]，當道端點（queue[0]或queue[n-1]）時，再在定位處反向遍歷到另一端。當調度磁道不在queue端點時，總的尋道長度為為前一個磁道與后一個磁

道差值的累加，當到達端點且queue[n]未全調度時，總尋道長度加上端點值再加上下一個調度磁道的值，再按前面的算法進行，直到磁道全部都調度完畢，得到總的尋道長度，除以n得到平均尋道長度。

④循環掃描算法（CSCAN）將queue[n]進行由小到大的排序，首先定位當前調度磁headstarts在queue[n]的位置，然后在此位置按給定的方向遍歷queue[n]，當道端點（queue[0]或queue[n-1]）時，反向到另一端點再以此方向進行遍歷，直到queue[n]中所有都調度完。當調度磁道不在queue端點時，總的尋道長度為為前一個磁道與后一個磁道差值的累加，當到達端點且queue[n]未全調度時，總尋道長度加上端點值再加上磁盤磁道總長度，再加上下一個調度磁道的值，再按前面的算法進行，直到磁道全部都調度完畢，得到總的尋道長度，除以n得到平均尋道長度。

5、源代碼：

#include #include #include void menu(){ cout<<“*********************菜單*********************”<

1、先來先服務算法（FCFS)**********”<

cout<<“******

2、最短尋道時間優先算法(SSTF)**********”<

cout<<“******

3、掃描算法(SCAN)**********”<

cout<<“******

4、循環掃描算法(CSCAN)**********”<

cout<<“******

5、退出 **********”<

/*======================初始化序列=======================*/ void init(int queue[],int queue_copy[],int n){ int i;for(i=0;i

//對當前正在執行的磁道號進行定位，返回磁道號小于當前磁道中最大的一個 int fix(int queue[], int n, int headstarts){ int i =0;while(iqueue[i]){ i++;} if(i>n-1)return n-1;//當前磁道號大于磁盤請求序列中的所有磁道 if(i==0)return-1;//當前磁道號小于磁盤請求序列中的所有磁道 else return i-1;//返回小于當前磁道號中最大的一個 } /*=================使用冒泡算法從小到大排序==============*/ int *bubble(int queue[],int m){ int i,j;int temp;for(i=0;i queue[j]){ temp=queue[i];queue[i]=queue[j];queue[j]=temp;} } cout<<“排序后的磁盤序列為：”;for(i=0;i

/* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts)//queue是請求調度序列，n為其個數，diskroad為磁盤磁道數，headstarts為正在調度的磁道 { cout<<“************以下為FCFS調度算法***********”<queue[0])count +=headstarts-queue[0];else count+=queue[0]-headstarts;cout<<“調度序列為: ”;cout<queue[i+1])count +=queue[i]-queue[i+1];else count +=queue[i+1]-queue[i];} cout<

/*=====================SSTF算法====================*/ void SSTF(int queue[], int n, int diskrode, int headstarts){ int k=1;int l,r;int i,j,count=0;queue =bubble(queue,n);cout<<“************以下為SSTF調度算法***********”<=0;i--)cout<=headstarts)//若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務 { cout<<“磁盤掃描序列為： ”;cout<queue[0] && headstarts =0)&&(r

-headstarts)){ cout<=0;j--){ cout<

/*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN調度算法*************”<>direction;double count=0;*bubble(queue,n);fixi = fix(queue,n,headstarts);cout<=0;i--){ cout<=0;i--)//從大到小 { cout<-1;i--){ cout<-1;i--)//從大到小 { cout<

/*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN調度算法*************”<>direction;int count=0;//count表示磁道移動的長度 *bubble(queue,n);fixi=fix(queue,n,headstarts);cout<<“調度序列為: ”<-1;--i){ cout<-1;--i){ cout<-1;i--){ cout<fixi;i--){ cout<

void main(){ int n, i, diskrode, headstarts;//n表示調度磁盤請求序列queue的長度，diskrode表示磁盤磁道的個數，headstarts表示目前正在調度的磁道； cout<<“請輸入磁盤的總磁道數:”<> diskrode;cout<<“請輸入磁盤調度請求序列個數:”<>n;int *queue;queue =(int*)malloc(n*sizeof(int));//給quneue數組分配空間...int *queue_copy;queue_copy =(int*)malloc(n*sizeof(int));cout<<“請依次輸入該序列的值:”<>queue[i];for(i=0;i>headstarts;int menux;menu();cout<<“請按菜單選擇，輸入相應的數字: ”;cin>>menux;while(menux!=0){ if(menux ==1)FCFS(queue,n,diskrode,headstarts);

if(menux ==2)SSTF(queue,n,diskrode,headstarts);

if(menux ==3)SCAN(queue,n,diskrode,headstarts);if(menux ==4)CSCAN(queue,n,diskrode,headstarts);if(menux ==5)cout<<“程序結束,謝謝使用！”<>menux;cout<