第一篇：操作系統(tǒng)實驗二——cpu調(diào)度與內(nèi)存分頁

一、試驗?zāi)康?/p>

理解操作系統(tǒng)內(nèi)存管理的原理及分頁內(nèi)存管理方案

二、試驗要求

1、實現(xiàn)分頁內(nèi)存管理方案，假定頁和幀的大小均為4KB，物理內(nèi)存為128MB

2、輸入為進(jìn)程ID，所需內(nèi)存大小等，輸出為頁表。

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

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

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

三、試驗環(huán)境

Windows XP Visual C++ 6.0

四、試驗內(nèi)容

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

一、首先從與內(nèi)存分配相關(guān)的作業(yè)調(diào)度函數(shù)說起，程序中為Jobs_scheduler。Job_scheduler的作用如下圖所示;

Job_scheduler從大容量存儲設(shè)備上的緩沖池中載入新生成的進(jìn)程到內(nèi)存，同時生成新的PCB到就緒隊列中。這里涉及到了兩個數(shù)據(jù)結(jié)構(gòu)class Program，class PCB。Program ：

PCB：

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

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

二、接下來是CPU調(diào)度程序，也成為短期調(diào)度程序。

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

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

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

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

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

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

五、心得體會

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

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

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

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

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

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

為了此次實驗，復(fù)習(xí)了調(diào)度和內(nèi)存管理兩章的大部分內(nèi)容，對操作系統(tǒng)對進(jìn)程調(diào)度和內(nèi)存分配管理有了更深入的認(rèn)識，但只是從概念上，沒有看到真正操作系統(tǒng)的代碼或者算法實例，所以可能很多地方的代碼與實際情況出入很大。

代碼：

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

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

隨機數(shù)，后面隨機生成進(jìn)程用的 *************/ 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設(shè)備(DMA)*/ DWORD WINAPI IOEquipment(LPVOID lpParamter){ io_equipment = ON;list

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

/* 為了體現(xiàn)I/O設(shè)備速度較慢，所以在此用了Sleep函數(shù) */

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執(zhí)行

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

**/ 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': //如果指令觸發(fā)了輸出設(shè)備

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設(shè)備未開啟，則打開，否則什么都不做 */

if(io_equipment == OFF)

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

else

;

return INTERRUPT;default :

break;}

/* 在沒有跳轉(zhuǎn)的情況下，運行之后，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”);

/* 長期調(diào)度程序,將緩沖池中的進(jìn)程加載到內(nèi)存上 */ 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算法的短期調(diào)度程序 */ 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;

}

/* 操作系統(tǒng)負(fù)責(zé)計時 */

}

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;}

第二篇：操作系統(tǒng)進(jìn)程調(diào)度實驗

一.實驗?zāi)康募皩嶒灜h(huán)境 1.實驗?zāi)康?/p>

通過觀察、分析實驗現(xiàn)象，深入理解進(jìn)程及進(jìn)程在調(diào)度執(zhí)行和內(nèi)存空間等方面的特點，掌握在POSIX 規(guī)范中fork和kill系統(tǒng)調(diào)用的功能和使用。2.實驗環(huán)境

（1）硬件

? CPU：I7-4500U ? 內(nèi)存：8G DDR3 1600 ? 顯示器：華碩筆記本顯示器 ? 硬盤空間：80G

（2）軟件

? 虛擬機名稱及版本：非虛擬機

? 操作系統(tǒng)名稱及版本：Ubuntu Kylin 16.04 ? 編譯器：gcc 二.實驗內(nèi)容

1、實驗前準(zhǔn)備工作

學(xué)習(xí)man 命令的用法，通過它查看fork 和kill 系統(tǒng)調(diào)用的在線幫助，并閱讀參考資料，學(xué)會fork 與kill 的用法，復(fù)習(xí)C 語言的相關(guān)內(nèi)容。

2、實驗內(nèi)容

根據(jù)下發(fā)的Linux進(jìn)程管理實驗PPT內(nèi)容，將實驗代碼補充完整。并考慮： 先猜想一下這個程序的運行結(jié)果。假如運行“./process 20”，輸出會是什么樣？然后按照注釋里的要求把代碼補充完整，運行程序?？梢远噙\行一會兒，并在此期間啟動、關(guān)閉一些其它進(jìn)程，看process 的輸出結(jié)果有什么特點，記錄下這個結(jié)果。開另一個終端窗口，運行“ps aux|grep process”命令，看看process 究竟啟動了多少個進(jìn)程?；氐匠绦驁?zhí)行窗口，按“數(shù)字鍵+回車”嘗試殺掉一兩個進(jìn)程，再到另一個窗口看進(jìn)程狀況。按q 退出程序再看進(jìn)程情況。

3、回答問題

編寫、編譯、鏈接、執(zhí)行實驗內(nèi)容設(shè)計中的代碼，并回答如下問題： 1）你最初認(rèn)為運行結(jié)果會怎么樣？

手動輸入進(jìn)程數(shù)，選擇輸入要殺死的進(jìn)程編號，按q殺死所有進(jìn)程。需手動輸入進(jìn)程數(shù)，然后鍵入編號殺死進(jìn)程，鍵入q殺死父進(jìn)程即殺死2）實際的結(jié)果什么樣？有什么特點？試對產(chǎn)生該現(xiàn)象的原因進(jìn)行分析。所有進(jìn)程。

3）proc_number 這個全局變量在各個子進(jìn)程里的值相同嗎？為什么？ 不相同，proc_number是存儲各個子進(jìn)程的編號的，所以在各個子進(jìn)程中

是不同的。

4）kill 命令在程序中使用了幾次？每次的作用是什么？執(zhí)行后的現(xiàn)象是什么？

使用了2次，第一次是在while循環(huán)中的if語句中使用，用來殺死用戶鍵入的指定進(jìn)程。第二次是殺死父進(jìn)程，回到程序的開始。

5）使用kill 命令可以在進(jìn)程的外部殺死進(jìn)程。進(jìn)程怎樣能主動退出？這兩種退出方式哪種更好一些？

調(diào)用return 函數(shù)或exit函數(shù)都可以正常退出，而使用kill函數(shù)是異常退出，使用正常退出的方法比較好。

6）寫出fork（）和kill（）函數(shù)原型，并解釋函數(shù)的功能和參數(shù)的含義？

原型： #include

功能：

一個現(xiàn)有進(jìn)程可以調(diào)用fork函數(shù)創(chuàng)建一個新進(jìn)程。由fork創(chuàng)建的新進(jìn)程被稱為子進(jìn)程。fork函數(shù)被調(diào)用一次但返回兩次。兩次返回的唯一區(qū)別是子進(jìn)程中返回0值而父進(jìn)程中返回子進(jìn)程ID。原型：#include #include

int kill(pid_t pid, int sig);

功能：

向某個進(jìn)程傳遞一個信號

7）ps aux|grep process命令功能是什么？并解釋結(jié)果的含義。

ps命令是最基本進(jìn)程查看命令.使用該命令可以確定有進(jìn)程正在運行數(shù)量和運行的狀態(tài)、進(jìn)程是否結(jié)束、是否有僵尸進(jìn)程、進(jìn)程占用的資源。grep命令查看某進(jìn)程的狀態(tài)并打印在屏幕上，ps aux是顯示所有進(jìn)程和他們的狀態(tài)。ps aux輸出格式：

USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND

三．方案設(shè)計

每創(chuàng)建一個子進(jìn)程時，將其pid存儲在數(shù)組pid[i]中，i存儲在proc_number中，然后調(diào)用死循環(huán)函數(shù)do_something()，輸出該進(jìn)程的proc_number，當(dāng)輸入數(shù)字是主進(jìn)程執(zhí)行kill(pid[pid-48],SIGTERM)，殺死ch-48進(jìn)程。當(dāng)輸入q時循環(huán)退出，kill(0,SIGTERM),殺死本組所有進(jìn)程，程序退出。

#include pid_t fork(void);

四．測試數(shù)據(jù)及運行結(jié)果

注釋：由于我的電腦運行這段代碼報錯，所以我和我組高宏偉同學(xué)使用的是同一實驗數(shù)據(jù)，同一代碼。五．總結(jié)

1． 實驗過程中遇到的問題及解決辦法；

實驗中由于代碼中的大部分已經(jīng)給出，只需填寫重要部分。遇到了不懂fork的返回值，所以if和else語句會同時執(zhí)行，知道了fork的原理后，fork會返回兩個值一個到子進(jìn)程，一個到父進(jìn)程。2． 對設(shè)計及調(diào)試過程的心得體會。

本次實驗學(xué)會了創(chuàng)建進(jìn)程命令fork和殺死進(jìn)程命令kill。在開始的時候不理解fork 和kill的原理，有點懵。后來通過看書和上網(wǎng)查詢知道了fork和kill的原理后明白了代碼要填寫的空白。六．附錄：源代碼（電子版）

#include #include #include #include #include #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);} }

第三篇：操作系統(tǒng) 實驗一 進(jìn)程調(diào)度

實驗一

進(jìn)程控制與處理機調(diào)度綜合實驗

一、實驗?zāi)康?/p>

通過模擬進(jìn)程控制方法及單處理機系統(tǒng)的進(jìn)程調(diào)度，了解進(jìn)程的結(jié)構(gòu)，進(jìn)程的創(chuàng)建與撤消，進(jìn)程的組織及進(jìn)程的狀態(tài)及其轉(zhuǎn)換，掌握進(jìn)程調(diào)度策略。

二、實驗環(huán)境

開發(fā)工具使用windows平臺下的vc++6.0。

三、實驗內(nèi)容

本實驗為單機模擬進(jìn)程調(diào)度算法，在程序設(shè)計時不需真正地建立線程或者進(jìn)程。實驗?zāi)M創(chuàng)建若干進(jìn)程（人為輸入或隨機數(shù)產(chǎn)生），選擇一種或幾種單處理機的進(jìn)程調(diào)度算法，如FCFS（先來先服務(wù)），SPF（短進(jìn)程優(yōu)先），RR（時間片輪轉(zhuǎn)法），優(yōu)先級算法等，模擬進(jìn)行進(jìn)程調(diào)度。每進(jìn)行一次調(diào)度，都打印一次運行進(jìn)程、就緒隊列、以及各個進(jìn)程的PCB，并能在進(jìn)程完成后及時撤消該進(jìn)程。

四、完成情況

1、進(jìn)程及進(jìn)程的運行狀態(tài)

進(jìn)程是現(xiàn)代計算機中的基本要素，是系統(tǒng)分配資源和調(diào)度的基本單位。進(jìn)程與程序不同，進(jìn)程是系統(tǒng)中動態(tài)的實體，有它的創(chuàng)建、運行和撤銷的過程。PCB塊是系統(tǒng)感知進(jìn)程存在的唯一實體。進(jìn)程的創(chuàng)建必須首先創(chuàng)建進(jìn)程的PCB塊，而進(jìn)程的運行也伴隨著PCB塊的變化，進(jìn)城撤銷也要同時撤銷它的PCB塊。所以本實驗的任務(wù)就是通過模擬調(diào)度進(jìn)程的PCB塊來調(diào)度進(jìn)程。進(jìn)程的PCB塊包含以下四方面的內(nèi)容： a)進(jìn)程標(biāo)示符 b)處理及狀態(tài)信息 c)進(jìn)程調(diào)度信息 d)進(jìn)程控制信息

進(jìn)程在運行中存在三種基本狀態(tài)，分別是運行狀態(tài)、就緒狀態(tài)和阻塞狀態(tài)。

2、進(jìn)程調(diào)度

一個運行進(jìn)程的時間片用完或發(fā)生阻塞時，系統(tǒng)就會選擇一個就緒進(jìn)程調(diào)度執(zhí)行。進(jìn)程的調(diào)度算法有很多如FCFS、SPF、優(yōu)先級調(diào)度和時間片輪轉(zhuǎn)方法。進(jìn)程調(diào)度算法模擬試驗就是通過調(diào)度進(jìn)程的PCB塊來模擬調(diào)度進(jìn)程。在系統(tǒng)中PCB塊就表現(xiàn)為一個結(jié)構(gòu)體，PCB塊之間的連接方式存在兩種，一種是連接方式，一種是索引方式。本試驗中可選擇任意一種連接方式。

3、例程

設(shè)計一個有 N個進(jìn)程共行的進(jìn)程調(diào)度程序。進(jìn)程調(diào)度算法：采用最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法（即把處理機分配給優(yōu)先數(shù)最高的進(jìn)程）。

每個進(jìn)程有一個進(jìn)程控制塊（PCB）表示。進(jìn)程控制塊可以包含如下信息：進(jìn)程名、優(yōu)先數(shù)、到達(dá)時間、需要運行時間、已用CPU時間、進(jìn)程狀態(tài)等等。進(jìn)程的優(yōu)先數(shù)及需要的運行時間可以事先人為地指定（也可以由隨機數(shù)產(chǎn)生）。進(jìn)程的到達(dá)時間為進(jìn)程輸入的時間。進(jìn)程的運行時間以時間片為單位進(jìn)行計算。每個進(jìn)程的狀態(tài)可以是就緒 W（Wait）、運行R（Run）、或完成F（Finish）三種狀態(tài)之一。就緒進(jìn)程獲得 CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。如果運行一個時間片后，進(jìn)程的已占用 CPU時間已達(dá)到所需要的運行時間，則撤消該進(jìn)程，如果運行一個時間片后進(jìn)程的已占用CPU時間還未達(dá)所需要的運行時間，也就是進(jìn)程還需要繼續(xù)運行，此時應(yīng)將進(jìn)程的優(yōu)先數(shù)減1（即降低一級），然后把它插入就緒隊列等待CPU。每進(jìn)行一次調(diào)度程序都打印一次運行進(jìn)程、就緒隊列、以及各個進(jìn)程的 PCB，以便進(jìn)行檢查。重復(fù)以上過程，直到所要進(jìn)程都完成為止。

調(diào)度算法的流程圖如下：

開始初始化進(jìn)程PCB，輸入進(jìn)程信息各進(jìn)程按優(yōu)先數(shù)從高到低排列y就緒隊列空？結(jié)束就緒隊列首進(jìn)程投入運行時間片到CPU占用時間+1運行已占用CPU時間已達(dá)到所需CPU時間y進(jìn)程完成撤銷該進(jìn)程是運行進(jìn)程的優(yōu)先數(shù)減1把運行進(jìn)程插入就緒隊列 圖1-1 流程圖

源代碼：#include “stdio.h” #include #include #define getpch(type)(type*)malloc(sizeof(type))#define NULL 0 struct pcb { /* 定義進(jìn)程控制塊PCB */ char name[10];char state;int super;int ntime;int rtime;struct pcb* link;}*ready=NULL,*p;typedef struct pcb PCB;void sort()/* 建立對進(jìn)程進(jìn)行優(yōu)先級排列函數(shù)*/ { PCB *first, *second;

int insert=0;if((ready==NULL)||((p->super)>(ready->super)))/*優(yōu)先級最大者,插入隊首 */ {

p->link=ready;ready=p;} else /* 進(jìn)程比較優(yōu)先級,插入適當(dāng)?shù)奈恢弥?/ {

first=ready;second=first->link;

while(second!=NULL)

{

if((p->super)>(second->super))/*若插入進(jìn)程比當(dāng)前進(jìn)程優(yōu)先數(shù)

大,*/

{ /*插入到當(dāng)前進(jìn)程前面*/

p->link=second;

first->link=p;

second=NULL;

insert=1;}

else /* 插入進(jìn)程優(yōu)先數(shù)最低,則插入到隊尾*/

{

first=first->link;second=second->link;

}

}

if(insert==0)

first->link=p;} } void input()/* 建立進(jìn)程控制塊函數(shù)*/ { int i,num;printf(“n請輸入進(jìn)程數(shù)量:”);scanf(“%d”,&num);for(i=0;i

printf(“n 進(jìn)程號No.%d:n”,i);

p=getpch(PCB);

printf(“n 輸入進(jìn)程名:”);

scanf(“%s”,p->name);

printf(“n 輸入進(jìn)程優(yōu)先數(shù):”);

scanf(“%d”,&p->super);

printf(“n 輸入進(jìn)程運行時間:”);

scanf(“%d”,&p->ntime);

printf(“n”);

p->rtime=0;p->state='w';

p->link=NULL;

sort();/* 調(diào)用sort函數(shù)*/ } }

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)/*建立進(jìn)程顯示函數(shù),用于顯示當(dāng)前進(jìn)程*/ {

printf(“ %st”,pr->name);printf(“ %ct”,pr->state);printf(“ %dt”,pr->super);printf(“ %dt”,pr->ntime);printf(“ %dt”,pr->rtime);printf(“n”);} void check()/* 建立進(jìn)程查看函數(shù) */ { PCB* pr;printf(“n****當(dāng)前正在運行的進(jìn)程是:%s”,p->name);/*顯示當(dāng)前運行進(jìn)程*/ show();disp(p);pr=ready;if(pr==NULL)

printf(“n****當(dāng)前就緒隊列為空!”);

else

{

printf(“n****當(dāng)前就緒隊列狀態(tài)為:”);/*顯示就緒隊列狀態(tài)*/

show();

while(pr!=NULL)

{

disp(pr);

pr=pr->link;

}

} } void destroy()/*建立進(jìn)程撤消函數(shù)(進(jìn)程運行結(jié)束,撤消進(jìn)程)*/ { printf(“n 進(jìn)程[%s]已完成.n”,p->name);free(p);} void running()/* 建立進(jìn)程就緒函數(shù)(進(jìn)程運行時間到,置就緒狀態(tài)*/ {(p->rtime)++;if(p->rtime==p->ntime)destroy();/* 調(diào)用destroy函數(shù)*/ else {

(p->super)--;

p->state='w';

sort();/*調(diào)用sort函數(shù)*/ } } void main()/*主函數(shù)*/ { int len,h=0;char ch;input();len=space();while((len!=0)&&(ready!=NULL)){

ch=getchar();

h++;

printf(“n 當(dāng)前運行次數(shù)為:%d n”,h);

p=ready;

ready=p->link;

p->link=NULL;

p->state='R';

check();

running();

printf(“n 按任一鍵繼續(xù)......”);

ch=getchar();} printf(“nn 進(jìn)程已經(jīng)完成.n”);ch=getchar();}

輸入數(shù)據(jù)后運行結(jié)果如下圖所示：

五、問題及解決辦法

問題：當(dāng)插入的進(jìn)程優(yōu)先級大于當(dāng)前進(jìn)程優(yōu)先級的時候，插入的進(jìn)程應(yīng)該放在什么

位置？

方法：通過指針的指向變換，把插入的進(jìn)程放置在當(dāng)前進(jìn)程前面。

六、實驗心得

通過本次實驗，了解了進(jìn)程的結(jié)構(gòu)，進(jìn)程的創(chuàng)建、撤銷，掌握了進(jìn)程調(diào)度策略處理機調(diào)度的理解，我更加深刻的認(rèn)識到調(diào)度進(jìn)程的pcb塊來調(diào)度進(jìn)程的過程，以及按照優(yōu)先權(quán)進(jìn)行排序的算法實現(xiàn)。對操作系統(tǒng)有了進(jìn)一步的認(rèn)識，后面會更加努力學(xué)習(xí)，掌握這門學(xué)科。

第四篇：1.操作系統(tǒng)實驗內(nèi)容(進(jìn)程調(diào)度)

一．實驗?zāi)康?/p>

用高級語言編寫和調(diào)實一個進(jìn)程調(diào)度程序，以加深對進(jìn)程的概念及進(jìn)程調(diào)度算法的理解． 二．實驗要求：設(shè)計一個有 N個進(jìn)程并發(fā)執(zhí)行的進(jìn)程調(diào)度程序。三．算法講解

進(jìn)程調(diào)度算法：采用最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法（即把處理機分配給優(yōu)先數(shù)最高的進(jìn)程）和先來先服務(wù)算法以及時間片輪轉(zhuǎn)法。

每個進(jìn)程有一個進(jìn)程控制塊（PCB）表示。進(jìn)程控制塊可以包含如下信息：進(jìn)程名、優(yōu)先數(shù)、到達(dá)時間、需要運行時間、已用CPU時間、進(jìn)程狀態(tài)等等。

進(jìn)程的優(yōu)先數(shù)及需要的運行時間可以事先人為地指定（也可以由隨機數(shù)產(chǎn)生）。進(jìn)程的到達(dá)時間為進(jìn)程輸入的時間。

進(jìn)程的運行時間以時間片為單位進(jìn)行計算。每個進(jìn)程的狀態(tài)可以是就緒 W（Wait）、運行R（Run）、或完成F（Finish）三種狀態(tài)之一。

就緒進(jìn)程獲得 CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。

如果運行一個時間片后，進(jìn)程的已占用 CPU時間已達(dá)到所需要的運行時間，則撤消該進(jìn)程，如果運行一個時間片后進(jìn)程的已占用CPU時間還未達(dá)所需要的運行時間，也就是進(jìn)程還需要繼續(xù)運行，此時應(yīng)將進(jìn)程的優(yōu)先數(shù)減1（即降低一級），然后把它插入就緒隊列等待CPU。每進(jìn)行一次調(diào)度程序都打印一次運行進(jìn)程、就緒隊列、以及各個進(jìn)程的 PCB，以便進(jìn)行檢查。重復(fù)以上過程，直到所要進(jìn)程都完成為止。四．實驗報告要求

1．寫出實驗?zāi)康模?2。寫出實驗要求：

3。寫出實驗內(nèi)容：（包括算法描述，程序流程圖及給出部分實驗結(jié)果及結(jié)果分析）4。實驗心得體會。

附：進(jìn)程調(diào)度源程序如下：

/*jingchendiaodu.c*/ #include “stdio.h” #include #include #define getpch(type)(type*)malloc(sizeof(type))#define NULL 0 struct pcb /* 定義進(jìn)程控制塊PCB */ { char name[10];char state;int super;int ntime;int rtime;struct pcb* link;}*ready=NULL,*p;typedef struct pcb PCB;sort()/* 建立對進(jìn)程進(jìn)行優(yōu)先級排列函數(shù)*/ {

scanf(“%d”,&p->ntime);printf(“n”);p->rtime=0;p->state='w';p->link=NULL;sort();/* 調(diào)用sort函數(shù)*/ } } int space(){ int l=0;PCB* pr=ready;while(pr!=NULL){ l++;pr=pr->link;} return(l);} disp(PCB * pr)/*建立進(jìn)程顯示函數(shù),用于顯示當(dāng)前進(jìn)程*/ { 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()/* 建立進(jìn)程查看函數(shù) */ { PCB* pr;printf(“n **** 當(dāng)前正在運行的進(jìn)程是:%s”,p->name);/*顯示當(dāng)前運行進(jìn)程*/ disp(p);pr=ready;printf(“n ****當(dāng)前就緒隊列狀態(tài)為:n”);/*顯示就緒隊列狀態(tài)*/ while(pr!=NULL){ disp(pr);pr=pr->link;} } destroy()/*建立進(jìn)程撤消函數(shù)(進(jìn)程運行結(jié)束,撤消進(jìn)程)*/ { printf(“n 進(jìn)程 [%s] 已完成.n”,p->name);free(p);

第五篇：單核與多核的CPU調(diào)度算法

1.多核CPU調(diào)度算法 1.1全局隊列調(diào)度算法

操作系統(tǒng)維護(hù)一個全局的任務(wù)等待隊列，每個進(jìn)程在執(zhí)行階段可以使用全部的處理器資源。當(dāng)系統(tǒng)中有一個CPU核心空閑時，操作系統(tǒng)就從全局任務(wù)等待隊列中選取Ready進(jìn)程開始在此核心上執(zhí)行。

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

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

操作系統(tǒng)為每個CPU內(nèi)核維護(hù)一個局部的任務(wù)等待隊列，將所有進(jìn)程分配到與處理器對應(yīng)的進(jìn)程隊列中。當(dāng)系統(tǒng)中有一個CPU內(nèi)核空閑時，便從該核心的任務(wù)等待隊列中選取恰當(dāng)?shù)娜蝿?wù)執(zhí)行。

優(yōu)點：充分利用局部緩存，降低了進(jìn)程遷移的開銷。任務(wù)基本上無需在多個CPU核心間切換，有利于提高CPU核心局部Cache命中率。目前多數(shù)多核CPU操作系統(tǒng)采用的是基于全局隊列的任務(wù)調(diào)度算法。

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

2.1 先到先服務(wù)調(diào)度算法：FCFS（first-come,first-served）

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

缺點：對于一個進(jìn)程隊列，其總的周轉(zhuǎn)時間太長，且當(dāng)進(jìn)程的I/O較為密集時，效率將會變得相當(dāng)?shù)?，CPU利用率也會變得很低。

優(yōu)點：實現(xiàn)方式簡單，適用于長程調(diào)度和處理器密集的進(jìn)程調(diào)度。常與優(yōu)先級策略結(jié)合提供一種更有效率的調(diào)度方法。

2.2 最短作業(yè)優(yōu)先調(diào)度算法：SJF（shortest-job-first）

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

缺點：忽視了作業(yè)等待時間，會出現(xiàn)starvation現(xiàn)象，且作業(yè)執(zhí)行時間無法提前知道，也很難預(yù)估。

優(yōu)點：算法實現(xiàn)簡單，能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量，是理論上的最優(yōu)調(diào)度算法。

2.3 最短剩余時間優(yōu)先調(diào)度算法：SRTF（Shortest Remaining Time First）SRTF調(diào)度算法是搶占式的SJF調(diào)度算法，調(diào)度程序總是首先選擇預(yù)期剩余時間最短的進(jìn)程加載進(jìn)入CPU執(zhí)行。

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

優(yōu)點：不偏向長進(jìn)程，沒有額外的中斷，因此開銷較低。且對于一個進(jìn)程隊列，總的周轉(zhuǎn)時間較短，執(zhí)行效率較高，對短進(jìn)程的響應(yīng)較快。2.4 優(yōu)先級調(diào)度算法

每個進(jìn)程都有一個自己的優(yōu)先級，Ready隊列采用優(yōu)先級隊列實現(xiàn)，CPU每次取Ready隊列隊首的進(jìn)程。通常情況，當(dāng)兩個進(jìn)程的優(yōu)先級相同時，我們在相同優(yōu)先級的進(jìn)程之間采用FCFS調(diào)度算法。優(yōu)先級可以通過內(nèi)部或外部方式來定義。

缺點：會出現(xiàn)starvation現(xiàn)象（也稱無窮阻塞），且不適用于分時系統(tǒng)或交互式事務(wù)處理環(huán)境。

優(yōu)點：主要用于批處理系統(tǒng)中，也可用于某些對實時性要求不嚴(yán)的實時系統(tǒng)中?？梢圆捎美匣夹g(shù)，每個進(jìn)程執(zhí)行以后其優(yōu)先級降低，以此來克服starvation的缺點。2.5 輪轉(zhuǎn)法調(diào)度算法

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

缺點：時間片長度設(shè)計較難，當(dāng)時間片長度過大時，會退化成FCFS調(diào)度算法。調(diào)度I/O密集型進(jìn)程時效率較低。由于輪詢調(diào)度在調(diào)度過程中不考慮瞬時信道條件，因此它將導(dǎo)致較低的整體系統(tǒng)性能。

優(yōu)點：對不同的分組業(yè)務(wù)流隊列進(jìn)行同樣的無差別的循環(huán)調(diào)度服務(wù)，對于等長業(yè)務(wù)流隊列是公平的，不存在starvation現(xiàn)象。2.6 最高響應(yīng)比優(yōu)先調(diào)度算法

首先需要理解一個概念，叫作響應(yīng)比。響應(yīng)比的計算表達(dá)式為

其中R為響應(yīng)比，w為等待處理器的時間，s為預(yù)計服務(wù)的時間。當(dāng)進(jìn)程被立即調(diào)用時，R等于歸一化周轉(zhuǎn)時間。

調(diào)度算法的過程是，當(dāng)進(jìn)程完成執(zhí)行或被阻塞時，選擇R值最大的Ready進(jìn)程加載進(jìn)入CPU執(zhí)行。

缺點：需要預(yù)估服務(wù)時間s，效率不太高。優(yōu)點：能克服starvation現(xiàn)象。3.復(fù)雜單核CPU調(diào)度算法

3.1 多級隊列調(diào)度算法（multilevel queue-scheduling algorithm）將Ready隊列分成多個獨立的隊列，對Ready隊列和每個獨立的隊列采用不同的調(diào)度算法進(jìn)行執(zhí)行。常用的方式是，Ready隊列采用優(yōu)先級調(diào)度算法，不同隊列根據(jù)實際情況采用合適的調(diào)度算法即可。

優(yōu)點：綜合了多種調(diào)度算法，避免了starvation現(xiàn)象，最大限度地提高了調(diào)度效率，也提高了CPU利用率。3.2 多級反饋隊列調(diào)度算法

UNIX OS采用的調(diào)度算法。其詳細(xì)過程如下： 1.進(jìn)程在進(jìn)入待調(diào)度的隊列等待時，首先進(jìn)入優(yōu)先級最高的Q1等待。

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

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

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

優(yōu)點：既能使高優(yōu)先級的作業(yè)得到響應(yīng)又能使短作業(yè)(進(jìn)程)迅速完成。4.多核CPU調(diào)度算法與單核CPU調(diào)度算法對比

從上面的不同CPU調(diào)度算法，我們不難發(fā)現(xiàn)，單核CPU調(diào)度算法是多核CPU調(diào)度算法的基礎(chǔ)，多核CPU調(diào)度算法是單核CPU調(diào)度算法的延伸和綜合使用。我以大篇幅介紹了單核CPU的調(diào)度算法，而以少量的篇幅介紹了多核CPU調(diào)度算法，其目的也在于說明此結(jié)論。

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