第一篇：操作系統實驗二——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
/***************
隨機數，后面隨機生成進程用的 *************/ void rand_seed(){ int seed = static_cast
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;}
第二篇：操作系統進程調度實驗
一.實驗目的及實驗環境 1.實驗目的
通過觀察、分析實驗現象，深入理解進程及進程在調度執行和內存空間等方面的特點，掌握在POSIX 規范中fork和kill系統調用的功能和使用。2.實驗環境
（1）硬件
? CPU：I7-4500U ? 內存：8G DDR3 1600 ? 顯示器：華碩筆記本顯示器 ? 硬盤空間：80G
（2）軟件
? 虛擬機名稱及版本：非虛擬機
? 操作系統名稱及版本：Ubuntu Kylin 16.04 ? 編譯器：gcc 二.實驗內容
1、實驗前準備工作
學習man 命令的用法，通過它查看fork 和kill 系統調用的在線幫助，并閱讀參考資料，學會fork 與kill 的用法，復習C 語言的相關內容。
2、實驗內容
根據下發的Linux進程管理實驗PPT內容，將實驗代碼補充完整。并考慮： 先猜想一下這個程序的運行結果。假如運行“./process 20”，輸出會是什么樣？然后按照注釋里的要求把代碼補充完整，運行程序。可以多運行一會兒，并在此期間啟動、關閉一些其它進程，看process 的輸出結果有什么特點，記錄下這個結果。開另一個終端窗口，運行“ps aux|grep process”命令，看看process 究竟啟動了多少個進程。回到程序執行窗口，按“數字鍵+回車”嘗試殺掉一兩個進程，再到另一個窗口看進程狀況。按q 退出程序再看進程情況。
3、回答問題
編寫、編譯、鏈接、執行實驗內容設計中的代碼，并回答如下問題： 1）你最初認為運行結果會怎么樣？
手動輸入進程數，選擇輸入要殺死的進程編號，按q殺死所有進程。需手動輸入進程數，然后鍵入編號殺死進程，鍵入q殺死父進程即殺死2）實際的結果什么樣？有什么特點？試對產生該現象的原因進行分析。所有進程。
3）proc_number 這個全局變量在各個子進程里的值相同嗎？為什么？ 不相同，proc_number是存儲各個子進程的編號的，所以在各個子進程中
是不同的。
4）kill 命令在程序中使用了幾次？每次的作用是什么？執行后的現象是什么？
使用了2次，第一次是在while循環中的if語句中使用，用來殺死用戶鍵入的指定進程。第二次是殺死父進程，回到程序的開始。
5）使用kill 命令可以在進程的外部殺死進程。進程怎樣能主動退出？這兩種退出方式哪種更好一些？
調用return 函數或exit函數都可以正常退出，而使用kill函數是異常退出，使用正常退出的方法比較好。
6）寫出fork（）和kill（）函數原型，并解釋函數的功能和參數的含義？
原型： #include
功能：
一個現有進程可以調用fork函數創建一個新進程。由fork創建的新進程被稱為子進程。fork函數被調用一次但返回兩次。兩次返回的唯一區別是子進程中返回0值而父進程中返回子進程ID。原型：#include
int kill(pid_t pid, int sig);
功能：
向某個進程傳遞一個信號
7）ps aux|grep process命令功能是什么？并解釋結果的含義。
ps命令是最基本進程查看命令.使用該命令可以確定有進程正在運行數量和運行的狀態、進程是否結束、是否有僵尸進程、進程占用的資源。grep命令查看某進程的狀態并打印在屏幕上，ps aux是顯示所有進程和他們的狀態。ps aux輸出格式：
USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND
三．方案設計
每創建一個子進程時，將其pid存儲在數組pid[i]中，i存儲在proc_number中，然后調用死循環函數do_something()，輸出該進程的proc_number，當輸入數字是主進程執行kill(pid[pid-48],SIGTERM)，殺死ch-48進程。當輸入q時循環退出，kill(0,SIGTERM),殺死本組所有進程，程序退出。
#include
四．測試數據及運行結果
注釋：由于我的電腦運行這段代碼報錯，所以我和我組高宏偉同學使用的是同一實驗數據，同一代碼。五．總結
1． 實驗過程中遇到的問題及解決辦法；
實驗中由于代碼中的大部分已經給出，只需填寫重要部分。遇到了不懂fork的返回值，所以if和else語句會同時執行，知道了fork的原理后，fork會返回兩個值一個到子進程，一個到父進程。2． 對設計及調試過程的心得體會。
本次實驗學會了創建進程命令fork和殺死進程命令kill。在開始的時候不理解fork 和kill的原理，有點懵。后來通過看書和上網查詢知道了fork和kill的原理后明白了代碼要填寫的空白。六．附錄：源代碼（電子版）
#include
#define MAX_CHILD_NUMBER 10 #define SLEEP_INTERVAL 2
int proc_number=0;void do_something();
int main(int argc,char* argv[]){ int child_proc_number=MAX_CHILD_NUMBER;int i,ch;pid_t child_pid;
pid_t pid[10]={0};if(argc>1){
child_proc_number = atoi(argv[1]);
child_proc_number =(child_proc_number>10)?10:child_proc_number;
for(i=0;i child_pid=fork(); proc_number=i; if(child_pid==0){do_something(); }else if(child_pid>0){ pid[i]=child_pid; printf(“A Parent process,the pid is %dn”,getpid()); } } printf(“input the number you want to killn”); while((ch=getchar())!='q') { if(isdigit(ch)){ ch=(int)ch-48; if(kill(pid[ch],SIGKILL)<0){ perror(“kill”); exit(1); }else{ printf(“process %d has been killed!nn”,pid[ch]); } }else{ printf(“is not digitn”); } getchar(); printf(“input the number you want to kill:n”); } kill(0,SIGTERM);} return 0;} void do_something(){ for(;;){ printf(“This is process No.%*dn”,proc_number+3,proc_number); sleep(SLEEP_INTERVAL);} } 實驗一 進程控制與處理機調度綜合實驗 一、實驗目的 通過模擬進程控制方法及單處理機系統的進程調度，了解進程的結構，進程的創建與撤消，進程的組織及進程的狀態及其轉換，掌握進程調度策略。 二、實驗環境 開發工具使用windows平臺下的vc++6.0。 三、實驗內容 本實驗為單機模擬進程調度算法，在程序設計時不需真正地建立線程或者進程。實驗模擬創建若干進程（人為輸入或隨機數產生），選擇一種或幾種單處理機的進程調度算法，如FCFS（先來先服務），SPF（短進程優先），RR（時間片輪轉法），優先級算法等，模擬進行進程調度。每進行一次調度，都打印一次運行進程、就緒隊列、以及各個進程的PCB，并能在進程完成后及時撤消該進程。 四、完成情況 1、進程及進程的運行狀態 進程是現代計算機中的基本要素，是系統分配資源和調度的基本單位。進程與程序不同，進程是系統中動態的實體，有它的創建、運行和撤銷的過程。PCB塊是系統感知進程存在的唯一實體。進程的創建必須首先創建進程的PCB塊，而進程的運行也伴隨著PCB塊的變化，進城撤銷也要同時撤銷它的PCB塊。所以本實驗的任務就是通過模擬調度進程的PCB塊來調度進程。進程的PCB塊包含以下四方面的內容： a)進程標示符 b)處理及狀態信息 c)進程調度信息 d)進程控制信息 進程在運行中存在三種基本狀態，分別是運行狀態、就緒狀態和阻塞狀態。 2、進程調度 一個運行進程的時間片用完或發生阻塞時，系統就會選擇一個就緒進程調度執行。進程的調度算法有很多如FCFS、SPF、優先級調度和時間片輪轉方法。進程調度算法模擬試驗就是通過調度進程的PCB塊來模擬調度進程。在系統中PCB塊就表現為一個結構體，PCB塊之間的連接方式存在兩種，一種是連接方式，一種是索引方式。本試驗中可選擇任意一種連接方式。 3、例程 設計一個有 N個進程共行的進程調度程序。進程調度算法：采用最高優先數優先的調度算法（即把處理機分配給優先數最高的進程）。 每個進程有一個進程控制塊（PCB）表示。進程控制塊可以包含如下信息：進程名、優先數、到達時間、需要運行時間、已用CPU時間、進程狀態等等。進程的優先數及需要的運行時間可以事先人為地指定（也可以由隨機數產生）。進程的到達時間為進程輸入的時間。進程的運行時間以時間片為單位進行計算。每個進程的狀態可以是就緒 W（Wait）、運行R（Run）、或完成F（Finish）三種狀態之一。就緒進程獲得 CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。如果運行一個時間片后，進程的已占用 CPU時間已達到所需要的運行時間，則撤消該進程，如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間，也就是進程還需要繼續運行，此時應將進程的優先數減1（即降低一級），然后把它插入就緒隊列等待CPU。每進行一次調度程序都打印一次運行進程、就緒隊列、以及各個進程的 PCB，以便進行檢查。重復以上過程，直到所要進程都完成為止。 調度算法的流程圖如下： 開始初始化進程PCB，輸入進程信息各進程按優先數從高到低排列y就緒隊列空？結束就緒隊列首進程投入運行時間片到CPU占用時間+1運行已占用CPU時間已達到所需CPU時間y進程完成撤銷該進程是運行進程的優先數減1把運行進程插入就緒隊列 圖1-1 流程圖 源代碼：#include “stdio.h” #include int insert=0;if((ready==NULL)||((p->super)>(ready->super)))/*優先級最大者,插入隊首 */ { p->link=ready;ready=p;} else /* 進程比較優先級,插入適當的位置中*/ { first=ready;second=first->link; while(second!=NULL) { if((p->super)>(second->super))/*若插入進程比當前進程優先數 大,*/ { /*插入到當前進程前面*/ p->link=second; first->link=p; second=NULL; insert=1;} else /* 插入進程優先數最低,則插入到隊尾*/ { first=first->link;second=second->link; } } if(insert==0) first->link=p;} } void input()/* 建立進程控制塊函數*/ { int i,num;printf(“n請輸入進程數量:”);scanf(“%d”,&num);for(i=0;i printf(“n 進程號No.%d:n”,i); p=getpch(PCB); printf(“n 輸入進程名:”); scanf(“%s”,p->name); printf(“n 輸入進程優先數:”); scanf(“%d”,&p->super); printf(“n 輸入進程運行時間:”); scanf(“%d”,&p->ntime); printf(“n”); p->rtime=0;p->state='w'; p->link=NULL; sort();/* 調用sort函數*/ } } int space(){ int l=0;PCB* pr=ready;while(pr!=NULL){ l++; pr=pr->link;} return(l);} void show(){ printf(“nqnametstatetsupertndtimetruntimen”);} void disp(PCB * pr)/*建立進程顯示函數,用于顯示當前進程*/ { printf(“ %st”,pr->name);printf(“ %ct”,pr->state);printf(“ %dt”,pr->super);printf(“ %dt”,pr->ntime);printf(“ %dt”,pr->rtime);printf(“n”);} void check()/* 建立進程查看函數 */ { PCB* pr;printf(“n****當前正在運行的進程是:%s”,p->name);/*顯示當前運行進程*/ show();disp(p);pr=ready;if(pr==NULL) printf(“n****當前就緒隊列為空!”); else { printf(“n****當前就緒隊列狀態為:”);/*顯示就緒隊列狀態*/ show(); while(pr!=NULL) { disp(pr); pr=pr->link; } } } void destroy()/*建立進程撤消函數(進程運行結束,撤消進程)*/ { printf(“n 進程[%s]已完成.n”,p->name);free(p);} void running()/* 建立進程就緒函數(進程運行時間到,置就緒狀態*/ {(p->rtime)++;if(p->rtime==p->ntime)destroy();/* 調用destroy函數*/ else { (p->super)--; p->state='w'; sort();/*調用sort函數*/ } } void main()/*主函數*/ { int len,h=0;char ch;input();len=space();while((len!=0)&&(ready!=NULL)){ ch=getchar(); h++; printf(“n 當前運行次數為:%d n”,h); p=ready; ready=p->link; p->link=NULL; p->state='R'; check(); running(); printf(“n 按任一鍵繼續......”); ch=getchar();} printf(“nn 進程已經完成.n”);ch=getchar();} 輸入數據后運行結果如下圖所示： 五、問題及解決辦法 問題：當插入的進程優先級大于當前進程優先級的時候，插入的進程應該放在什么 位置？ 方法：通過指針的指向變換，把插入的進程放置在當前進程前面。 六、實驗心得 通過本次實驗，了解了進程的結構，進程的創建、撤銷，掌握了進程調度策略處理機調度的理解，我更加深刻的認識到調度進程的pcb塊來調度進程的過程，以及按照優先權進行排序的算法實現。對操作系統有了進一步的認識，后面會更加努力學習，掌握這門學科。 一．實驗目的 用高級語言編寫和調實一個進程調度程序，以加深對進程的概念及進程調度算法的理解． 二．實驗要求：設計一個有 N個進程并發執行的進程調度程序。三．算法講解 進程調度算法：采用最高優先數優先的調度算法（即把處理機分配給優先數最高的進程）和先來先服務算法以及時間片輪轉法。 每個進程有一個進程控制塊（PCB）表示。進程控制塊可以包含如下信息：進程名、優先數、到達時間、需要運行時間、已用CPU時間、進程狀態等等。 進程的優先數及需要的運行時間可以事先人為地指定（也可以由隨機數產生）。進程的到達時間為進程輸入的時間。 進程的運行時間以時間片為單位進行計算。每個進程的狀態可以是就緒 W（Wait）、運行R（Run）、或完成F（Finish）三種狀態之一。 就緒進程獲得 CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。 如果運行一個時間片后，進程的已占用 CPU時間已達到所需要的運行時間，則撤消該進程，如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間，也就是進程還需要繼續運行，此時應將進程的優先數減1（即降低一級），然后把它插入就緒隊列等待CPU。每進行一次調度程序都打印一次運行進程、就緒隊列、以及各個進程的 PCB，以便進行檢查。重復以上過程，直到所要進程都完成為止。四．實驗報告要求 1．寫出實驗目的： 2。寫出實驗要求： 3。寫出實驗內容：（包括算法描述，程序流程圖及給出部分實驗結果及結果分析）4。實驗心得體會。 附：進程調度源程序如下： /*jingchendiaodu.c*/ #include “stdio.h” #include scanf(“%d”,&p->ntime);printf(“n”);p->rtime=0;p->state='w';p->link=NULL;sort();/* 調用sort函數*/ } } int space(){ int l=0;PCB* pr=ready;while(pr!=NULL){ l++;pr=pr->link;} return(l);} disp(PCB * pr)/*建立進程顯示函數,用于顯示當前進程*/ { printf(“n qname t state t super t ndtime t runtime n”);printf(“|%st”,pr->name);printf(“|%ct”,pr->state);printf(“|%dt”,pr->super);printf(“|%dt”,pr->ntime);printf(“|%dt”,pr->rtime);printf(“n”);} check()/* 建立進程查看函數 */ { PCB* pr;printf(“n **** 當前正在運行的進程是:%s”,p->name);/*顯示當前運行進程*/ disp(p);pr=ready;printf(“n ****當前就緒隊列狀態為:n”);/*顯示就緒隊列狀態*/ while(pr!=NULL){ disp(pr);pr=pr->link;} } destroy()/*建立進程撤消函數(進程運行結束,撤消進程)*/ { printf(“n 進程 [%s] 已完成.n”,p->name);free(p); 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現象（也稱無窮阻塞），且不適用于分時系統或交互式事務處理環境。 優點：主要用于批處理系統中，也可用于某些對實時性要求不嚴的實時系統中。可以采用老化技術，每個進程執行以后其優先級降低，以此來克服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調度算法去實現。第三篇：操作系統 實驗一 進程調度
第四篇：1.操作系統實驗內容(進程調度)
第五篇：單核與多核的CPU調度算法
點擊咨詢 