第一篇:操作系統(tǒng) 實驗一 進程調(diào)度
實驗一
進程控制與處理機調(diào)度綜合實驗
一、實驗?zāi)康?/p>
通過模擬進程控制方法及單處理機系統(tǒng)的進程調(diào)度,了解進程的結(jié)構(gòu),進程的創(chuàng)建與撤消,進程的組織及進程的狀態(tài)及其轉(zhuǎn)換,掌握進程調(diào)度策略。
二、實驗環(huán)境
開發(fā)工具使用windows平臺下的vc++6.0。
三、實驗內(nèi)容
本實驗為單機模擬進程調(diào)度算法,在程序設(shè)計時不需真正地建立線程或者進程。實驗?zāi)M創(chuàng)建若干進程(人為輸入或隨機數(shù)產(chǎn)生),選擇一種或幾種單處理機的進程調(diào)度算法,如FCFS(先來先服務(wù)),SPF(短進程優(yōu)先),RR(時間片輪轉(zhuǎn)法),優(yōu)先級算法等,模擬進行進程調(diào)度。每進行一次調(diào)度,都打印一次運行進程、就緒隊列、以及各個進程的PCB,并能在進程完成后及時撤消該進程。
四、完成情況
1、進程及進程的運行狀態(tài)
進程是現(xiàn)代計算機中的基本要素,是系統(tǒng)分配資源和調(diào)度的基本單位。進程與程序不同,進程是系統(tǒng)中動態(tài)的實體,有它的創(chuàng)建、運行和撤銷的過程。PCB塊是系統(tǒng)感知進程存在的唯一實體。進程的創(chuàng)建必須首先創(chuàng)建進程的PCB塊,而進程的運行也伴隨著PCB塊的變化,進城撤銷也要同時撤銷它的PCB塊。所以本實驗的任務(wù)就是通過模擬調(diào)度進程的PCB塊來調(diào)度進程。進程的PCB塊包含以下四方面的內(nèi)容: a)進程標(biāo)示符 b)處理及狀態(tài)信息 c)進程調(diào)度信息 d)進程控制信息
進程在運行中存在三種基本狀態(tài),分別是運行狀態(tài)、就緒狀態(tài)和阻塞狀態(tài)。
2、進程調(diào)度
一個運行進程的時間片用完或發(fā)生阻塞時,系統(tǒng)就會選擇一個就緒進程調(diào)度執(zhí)行。進程的調(diào)度算法有很多如FCFS、SPF、優(yōu)先級調(diào)度和時間片輪轉(zhuǎn)方法。進程調(diào)度算法模擬試驗就是通過調(diào)度進程的PCB塊來模擬調(diào)度進程。在系統(tǒng)中PCB塊就表現(xiàn)為一個結(jié)構(gòu)體,PCB塊之間的連接方式存在兩種,一種是連接方式,一種是索引方式。本試驗中可選擇任意一種連接方式。
3、例程
設(shè)計一個有 N個進程共行的進程調(diào)度程序。進程調(diào)度算法:采用最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法(即把處理機分配給優(yōu)先數(shù)最高的進程)。
每個進程有一個進程控制塊(PCB)表示。進程控制塊可以包含如下信息:進程名、優(yōu)先數(shù)、到達時間、需要運行時間、已用CPU時間、進程狀態(tài)等等。進程的優(yōu)先數(shù)及需要的運行時間可以事先人為地指定(也可以由隨機數(shù)產(chǎn)生)。進程的到達時間為進程輸入的時間。進程的運行時間以時間片為單位進行計算。每個進程的狀態(tài)可以是就緒 W(Wait)、運行R(Run)、或完成F(Finish)三種狀態(tài)之一。就緒進程獲得 CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。如果運行一個時間片后,進程的已占用 CPU時間已達到所需要的運行時間,則撤消該進程,如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間,也就是進程還需要繼續(xù)運行,此時應(yīng)將進程的優(yōu)先數(shù)減1(即降低一級),然后把它插入就緒隊列等待CPU。每進行一次調(diào)度程序都打印一次運行進程、就緒隊列、以及各個進程的 PCB,以便進行檢查。重復(fù)以上過程,直到所要進程都完成為止。
調(diào)度算法的流程圖如下:
開始初始化進程PCB,輸入進程信息各進程按優(yōu)先數(shù)從高到低排列y就緒隊列空?結(jié)束就緒隊列首進程投入運行時間片到CPU占用時間+1運行已占用CPU時間已達到所需CPU時間y進程完成撤銷該進程是運行進程的優(yōu)先數(shù)減1把運行進程插入就緒隊列 圖1-1 流程圖
源代碼:#include “stdio.h” #include
int insert=0;if((ready==NULL)||((p->super)>(ready->super)))/*優(yōu)先級最大者,插入隊首 */ {
p->link=ready;ready=p;} else /* 進程比較優(yōu)先級,插入適當(dāng)?shù)奈恢弥?/ {
first=ready;second=first->link;
while(second!=NULL)
{
if((p->super)>(second->super))/*若插入進程比當(dāng)前進程優(yōu)先數(shù)
大,*/
{ /*插入到當(dāng)前進程前面*/
p->link=second;
first->link=p;
second=NULL;
insert=1;}
else /* 插入進程優(yōu)先數(shù)最低,則插入到隊尾*/
{
first=first->link;second=second->link;
}
}
if(insert==0)
first->link=p;} } void input()/* 建立進程控制塊函數(shù)*/ { int i,num;printf(“n請輸入進程數(shù)量:”);scanf(“%d”,&num);for(i=0;i printf(“n 進程號No.%d:n”,i); p=getpch(PCB); printf(“n 輸入進程名:”); scanf(“%s”,p->name); printf(“n 輸入進程優(yōu)先數(shù):”); scanf(“%d”,&p->super); printf(“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)/*建立進程顯示函數(shù),用于顯示當(dāng)前進程*/ { printf(“ %st”,pr->name);printf(“ %ct”,pr->state);printf(“ %dt”,pr->super);printf(“ %dt”,pr->ntime);printf(“ %dt”,pr->rtime);printf(“n”);} void check()/* 建立進程查看函數(shù) */ { PCB* pr;printf(“n****當(dāng)前正在運行的進程是:%s”,p->name);/*顯示當(dāng)前運行進程*/ 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()/*建立進程撤消函數(shù)(進程運行結(jié)束,撤消進程)*/ { printf(“n 進程[%s]已完成.n”,p->name);free(p);} void running()/* 建立進程就緒函數(shù)(進程運行時間到,置就緒狀態(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īng)完成.n”);ch=getchar();} 輸入數(shù)據(jù)后運行結(jié)果如下圖所示: 五、問題及解決辦法 問題:當(dāng)插入的進程優(yōu)先級大于當(dāng)前進程優(yōu)先級的時候,插入的進程應(yīng)該放在什么 位置? 方法:通過指針的指向變換,把插入的進程放置在當(dāng)前進程前面。 六、實驗心得 通過本次實驗,了解了進程的結(jié)構(gòu),進程的創(chuàng)建、撤銷,掌握了進程調(diào)度策略處理機調(diào)度的理解,我更加深刻的認識到調(diào)度進程的pcb塊來調(diào)度進程的過程,以及按照優(yōu)先權(quán)進行排序的算法實現(xiàn)。對操作系統(tǒng)有了進一步的認識,后面會更加努力學(xué)習(xí),掌握這門學(xué)科。 一.實驗?zāi)康募皩嶒灜h(huán)境 1.實驗?zāi)康?/p> 通過觀察、分析實驗現(xià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進程管理實驗PPT內(nèi)容,將實驗代碼補充完整。并考慮: 先猜想一下這個程序的運行結(jié)果。假如運行“./process 20”,輸出會是什么樣?然后按照注釋里的要求把代碼補充完整,運行程序??梢远噙\行一會兒,并在此期間啟動、關(guān)閉一些其它進程,看process 的輸出結(jié)果有什么特點,記錄下這個結(jié)果。開另一個終端窗口,運行“ps aux|grep process”命令,看看process 究竟啟動了多少個進程。回到程序執(zhí)行窗口,按“數(shù)字鍵+回車”嘗試殺掉一兩個進程,再到另一個窗口看進程狀況。按q 退出程序再看進程情況。 3、回答問題 編寫、編譯、鏈接、執(zhí)行實驗內(nèi)容設(shè)計中的代碼,并回答如下問題: 1)你最初認為運行結(jié)果會怎么樣? 手動輸入進程數(shù),選擇輸入要殺死的進程編號,按q殺死所有進程。需手動輸入進程數(shù),然后鍵入編號殺死進程,鍵入q殺死父進程即殺死2)實際的結(jié)果什么樣?有什么特點?試對產(chǎn)生該現(xiàn)象的原因進行分析。所有進程。 3)proc_number 這個全局變量在各個子進程里的值相同嗎?為什么? 不相同,proc_number是存儲各個子進程的編號的,所以在各個子進程中 是不同的。 4)kill 命令在程序中使用了幾次?每次的作用是什么?執(zhí)行后的現(xiàn)象是什么? 使用了2次,第一次是在while循環(huán)中的if語句中使用,用來殺死用戶鍵入的指定進程。第二次是殺死父進程,回到程序的開始。 5)使用kill 命令可以在進程的外部殺死進程。進程怎樣能主動退出?這兩種退出方式哪種更好一些? 調(diào)用return 函數(shù)或exit函數(shù)都可以正常退出,而使用kill函數(shù)是異常退出,使用正常退出的方法比較好。 6)寫出fork()和kill()函數(shù)原型,并解釋函數(shù)的功能和參數(shù)的含義? 原型: #include 功能: 一個現(xiàn)有進程可以調(diào)用fork函數(shù)創(chuàng)建一個新進程。由fork創(chuàng)建的新進程被稱為子進程。fork函數(shù)被調(diào)用一次但返回兩次。兩次返回的唯一區(qū)別是子進程中返回0值而父進程中返回子進程ID。原型:#include int kill(pid_t pid, int sig); 功能: 向某個進程傳遞一個信號 7)ps aux|grep process命令功能是什么?并解釋結(jié)果的含義。 ps命令是最基本進程查看命令.使用該命令可以確定有進程正在運行數(shù)量和運行的狀態(tài)、進程是否結(jié)束、是否有僵尸進程、進程占用的資源。grep命令查看某進程的狀態(tài)并打印在屏幕上,ps aux是顯示所有進程和他們的狀態(tài)。ps aux輸出格式: USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND 三.方案設(shè)計 每創(chuàng)建一個子進程時,將其pid存儲在數(shù)組pid[i]中,i存儲在proc_number中,然后調(diào)用死循環(huán)函數(shù)do_something(),輸出該進程的proc_number,當(dāng)輸入數(shù)字是主進程執(zhí)行kill(pid[pid-48],SIGTERM),殺死ch-48進程。當(dāng)輸入q時循環(huán)退出,kill(0,SIGTERM),殺死本組所有進程,程序退出。 #include 四.測試數(shù)據(jù)及運行結(jié)果 注釋:由于我的電腦運行這段代碼報錯,所以我和我組高宏偉同學(xué)使用的是同一實驗數(shù)據(jù),同一代碼。五.總結(jié) 1. 實驗過程中遇到的問題及解決辦法; 實驗中由于代碼中的大部分已經(jīng)給出,只需填寫重要部分。遇到了不懂fork的返回值,所以if和else語句會同時執(zhí)行,知道了fork的原理后,fork會返回兩個值一個到子進程,一個到父進程。2. 對設(shè)計及調(diào)試過程的心得體會。 本次實驗學(xué)會了創(chuàng)建進程命令fork和殺死進程命令kill。在開始的時候不理解fork 和kill的原理,有點懵。后來通過看書和上網(wǎng)查詢知道了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);} } 一.實驗?zāi)康?/p> 用高級語言編寫和調(diào)實一個進程調(diào)度程序,以加深對進程的概念及進程調(diào)度算法的理解. 二.實驗要求:設(shè)計一個有 N個進程并發(fā)執(zhí)行的進程調(diào)度程序。三.算法講解 進程調(diào)度算法:采用最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法(即把處理機分配給優(yōu)先數(shù)最高的進程)和先來先服務(wù)算法以及時間片輪轉(zhuǎn)法。 每個進程有一個進程控制塊(PCB)表示。進程控制塊可以包含如下信息:進程名、優(yōu)先數(shù)、到達時間、需要運行時間、已用CPU時間、進程狀態(tài)等等。 進程的優(yōu)先數(shù)及需要的運行時間可以事先人為地指定(也可以由隨機數(shù)產(chǎn)生)。進程的到達時間為進程輸入的時間。 進程的運行時間以時間片為單位進行計算。每個進程的狀態(tài)可以是就緒 W(Wait)、運行R(Run)、或完成F(Finish)三種狀態(tài)之一。 就緒進程獲得 CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。 如果運行一個時間片后,進程的已占用 CPU時間已達到所需要的運行時間,則撤消該進程,如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間,也就是進程還需要繼續(xù)運行,此時應(yīng)將進程的優(yōu)先數(shù)減1(即降低一級),然后把它插入就緒隊列等待CPU。每進行一次調(diào)度程序都打印一次運行進程、就緒隊列、以及各個進程的 PCB,以便進行檢查。重復(fù)以上過程,直到所要進程都完成為止。四.實驗報告要求 1.寫出實驗?zāi)康模?2。寫出實驗要求: 3。寫出實驗內(nèi)容:(包括算法描述,程序流程圖及給出部分實驗結(jié)果及結(jié)果分析)4。實驗心得體會。 附:進程調(diào)度源程序如下: /*jingchendiaodu.c*/ #include “stdio.h” #include 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)/*建立進程顯示函數(shù),用于顯示當(dāng)前進程*/ { 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()/* 建立進程查看函數(shù) */ { PCB* pr;printf(“n **** 當(dāng)前正在運行的進程是:%s”,p->name);/*顯示當(dāng)前運行進程*/ disp(p);pr=ready;printf(“n ****當(dāng)前就緒隊列狀態(tài)為:n”);/*顯示就緒隊列狀態(tài)*/ while(pr!=NULL){ disp(pr);pr=pr->link;} } destroy()/*建立進程撤消函數(shù)(進程運行結(jié)束,撤消進程)*/ { printf(“n 進程 [%s] 已完成.n”,p->name);free(p); 進程調(diào)度算法模擬 專業(yè):XXXXX 學(xué)號:XXXXX 姓名:XXX 實驗日期:20XX年XX月XX日 一、實驗?zāi)康?/p> 通過對進程調(diào)度算法的模擬加深對進程概念和進程調(diào)度算法的理解。 二、實驗要求 編寫程序?qū)崿F(xiàn)對5個進程的調(diào)度模擬,要求至少采用兩種不同的調(diào)度算法分別進行模擬調(diào)度。 三、實驗方法內(nèi)容 1.算法設(shè)計思路 將每個進程抽象成一個控制塊PCB,PCB用一個結(jié)構(gòu)體描述。 構(gòu)建一個進程調(diào)度類。將進程調(diào)度的各種算法分裝在一個類中。類中存在三個容器,一個保存正在或未進入就緒隊列的進程,一個保存就緒的進程,另一個保存已完成的進程。還有一個PCB實例。主要保存正在運行的進程。類中其他方法都是圍繞這三個容器可以這個運行中的PCB展開。 主要用到的技術(shù)是STL中的vector以維護和保存進程容器、就緒容器、完成容器。 當(dāng)程序啟動時,用戶可以選擇不同的調(diào)度算法。然后用戶從控制臺輸入各個進程的信息,這些信息保存到進程容器中。進程信息輸入完畢后,就開始了進程調(diào)度,每調(diào)度一次判斷就緒隊列是否為空,若為空則系統(tǒng)時間加一個時間片。判斷進程容器中是否有新的進程可以加入就緒隊列。2.算法流程圖 主程序的框架: 開始void FCFS();//先來先服務(wù)void SJF();//最短進程優(yōu)先調(diào)度void RR();//簡單時間片輪轉(zhuǎn)void PD();//最高優(yōu)先數(shù)優(yōu)先void PCBInput();//輸入進程信息選擇調(diào)度算法輸入進程信息將輸入容器中以滿足進入條件的進程調(diào)入就緒隊列void ProcessQueueProcess();//查看當(dāng)前時間下,有無進程加入。若有則把該進程調(diào)入就緒隊列按照選擇的算法開始選擇就緒隊列的進程開始執(zhí)行void ProcessSelect();//若當(dāng)前就緒隊列不為空則根據(jù)選擇的調(diào)度算法開始調(diào)度,否則,系統(tǒng)時間加一個時間片.以等待新的進程到判斷就緒容器和輸入容器是否為空!processScheduler.m_WaitQueue.empty()||!processScheduler.m_ProcessQueue.empt()Y打印各進程信息進行統(tǒng)計計算周轉(zhuǎn)時間等結(jié)束void PCBDisplay();//打印當(dāng)前狀況下。就緒隊列、完成隊列、運行中的進程信息void SchedulerStatistics();//調(diào)度統(tǒng)計,計算周轉(zhuǎn)時間等進程調(diào)度過程: 開始為空判斷就緒隊列是否為空if(m_WaitQueue.empty())非空讓系統(tǒng)等待一個時間片TimePast()根據(jù)設(shè)定的調(diào)度算法從就緒隊列中調(diào)入一個進程并執(zhí)行(此時進程從就緒隊列中刪除,賦值到表示運行中的成員變量中)void FCFS();//先來先服務(wù)void SJF();//最短進程優(yōu)先調(diào)度void RR();//簡單時間片輪轉(zhuǎn)void PD();//最高優(yōu)先數(shù)優(yōu)先進程運行一個時間片N是否達到該進程停止運行的條件Y選入的進程狀態(tài)是否為“完成”如進程已完成,或者分得的時間片個數(shù)已到ProcessRun()Yvector m_WaitQueue;//進程就緒隊列進程未完成,將進程優(yōu)先數(shù)減一,并放回到就緒隊列中設(shè)置進程完成時間,將該進程放入完成隊列vector m_FinishQueue;//完成隊列結(jié)束 3.算法中用到的數(shù)據(jù)結(jié)構(gòu) struct fcfs{ //先來先服務(wù)算法從這里開始 char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; }; //定義一個結(jié)構(gòu)體,里面包含的有一個進程相關(guān)的信息 4.主要的常量變量 vector m_ProcessQueue;//進程輸入隊列 vector m_WaitQueue;//進程就緒隊列 vector m_FinishQueue;//完成隊列 vector ::iterator m_iter;//迭代器 PCB m_runProcess;//運行中的進程 int m_ProcessCount;//進程數(shù) float m_RunTime;//運行時間 int m_tagIsRun;//是否在運行標(biāo)志。表示正在運行,表示沒有 float m_TimeSlice;//時間片大小 int m_TimeSliceCount;//指時間片輪轉(zhuǎn)中一次分到的時間片個數(shù) char m_SchedulerAlgorithm;//調(diào)度算法 5.主要模塊 void PCBInput();//輸入進程信息 void PCBSort();//對進程控制塊按照優(yōu)先級排序(采用冒泡排序)void ProcessSelect();//若當(dāng)前就緒隊列不為空則根據(jù)選擇的調(diào)度算法開始調(diào)度。否則,系統(tǒng)時間void PCBDisplay();//打印當(dāng)前狀況下。就緒隊列、完成隊列、運行中的進程信息 void ProcessRun();//進程運行一次。運行時間加個時間片。并判斷進程是否達到完成條件。若是則void ProcessQueueProcess();//查看當(dāng)前時間下,有無進程加入。若有則把該進程調(diào)入就緒隊列 void ProcessDispatch();//進程分派,進程執(zhí)行完成后決定進程該進入哪個隊列(就緒、完成)void TimePast(){ m_RunTime +=m_TimeSlice;ProcessQueueProcess();}//當(dāng)前系統(tǒng)時間加個時間void SchedulerStatistics();//調(diào)度統(tǒng)計,計算周轉(zhuǎn)時間等 void FCFS();//先來先服務(wù) void SJF();//最短進程優(yōu)先調(diào)度 void RR();//簡單時間片輪轉(zhuǎn) void PD();//最高優(yōu)先數(shù)優(yōu)先 加.以等待新的進程到來 ProcessStatus='f'.否則為'w';片,并檢查是否有新的進程加入 四、實驗代碼 #include using namespace std; struct fcfs{ //先來先服務(wù)算法從這里開始 char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; }; //定義一個結(jié)構(gòu)體,里面包含的有一個進程相關(guān)的信息 fcfs a[100]; void input(fcfs *p,int N) { int i; cout< printf(“ 請您輸入進程的名字 到達時間 服務(wù)時間:(例如: a 0 100)nn”); for(i=0;i<=N-1;i++) { printf(“ 請您輸入進程%d的信息:t”,i+1); scanf(“ttt%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime); } } void Print(fcfs *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) { int k; printf(“nn調(diào)用先來先服務(wù)算法以后進程運行的順序是: ”); printf(“%s”,p[0].name); for(k=1;k { printf(“-->%s”,p[k].name); } cout< printf(“n 具體進程調(diào)度信息:n”); printf(“t進程名 到達時間 服務(wù)時間 開始時間 結(jié)束時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間n”); for(k=0;k<=N-1;k++) { printf(“t%st%-.2ft %-.2ft %-.2ft %-.2ft %-.2ft %-.2fn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } getchar(); //此處必須要有這個函數(shù),否則就看不到顯示器上面的輸出,可以看到的結(jié)果只是一閃而過的一個框剪 } void sort(fcfs *p,int N)//排序 { for(int i=0;i<=N-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { fcfs temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) //運行階段 { int k; for(k=0;k<=N-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+p[k].servicetime;} } for(k=0;k<=N-1;k++) { p[k].zztime=p[k].finishtime-p[k].arrivetime; p[k].dqzztime=p[k].zztime/p[k].servicetime; } } void FCFS(fcfs *p,int N) { float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N); deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); getchar(); } //先來先服務(wù)算法到此結(jié)束 struct sjf{//最短進程優(yōu)先調(diào)度算法從這里開始 char name[10];float arrivetime;//到達時間 float servicetime;//運行時間 float starttime; //開始時間 float finishtime; //完成時間 };sjf a1[100]; void input(sjf *p,int N1)//進程信息輸入 { int i;cout< printf(“ 請您輸入進程的名字 到達時間 服務(wù)時間:(例如: a 0 100)n”); for(i=0;i<=N1-1;i++){ printf(“ 請您輸入進程%d的信息:t”,i+1); scanf(“ttt%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} } void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,int N1)//最終結(jié)果輸出 { int k; printf(“nt調(diào)用最短進程優(yōu)先調(diào)度算法以后進程的調(diào)度順序為:”); printf(“%s”,p[0].name); for(k=1;k {printf(“-->%s”,p[k].name);} cout< printf(“n給個進程具體調(diào)度信息如下:n”); printf(“nt進程名t到達時間t運行時間t開始時間t完成時間n”); for(k=0;k<=N1-1;k++) { printf(“ t%st %-.2ftt %-.2ftt %-.2ftt %-.2ftn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime); } getchar(); } void sort(sjf *p,int N1)//排序 { for(int i=0;i<=N1-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { sjf temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,int N1)//運行階段 { int k; for(k=0;k<=N1-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+float(p[k].servicetime)/60;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+float(p[k].servicetime)/60;} } } void sjff(sjf *p,int N1){ float arrivetime=0,servicetime=0,starttime=0,finishtime=0; sort(p,N1); for(int m=0;m {if(m==0) p[m].finishtime=p[m].arrivetime+float(p[m].servicetime)/60; else p[m].finishtime=p[m-1].finishtime+float(p[m].servicetime)/60; int i=0; for(int n=m+1;n<=N1-1;n++) { if(p[n].arrivetime<=p[m].finishtime) i++; } float min=p[m+1].servicetime; int next=m+1; for(int k=m+1;k { if(p[k+1].servicetime {min=p[k+1].servicetime; next=k+1;} } sjf temp; temp=p[m+1]; p[m+1]=p[next]; p[next]=temp; } deal(p,arrivetime,servicetime,starttime,finishtime,N1); Print(p,arrivetime,servicetime,starttime,finishtime,N1); getchar();}//最短進程優(yōu)先調(diào)度算法到這里結(jié)束 char menu()//用來輸出相關(guān)信息的函數(shù) { char cse1; while(1) { system(“cls”); fflush(stdin); cout< cout< cout<<“t”<<“|| <<<<<<<<<<<<歡<<<<<<<<<<< >>>>>>>>>>>>迎>>>>>>>>>>> ||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“t 進程調(diào)度算法模擬”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“tt 1.先來先服務(wù)調(diào)度算法 ”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“tt 2.最短進程優(yōu)先調(diào)度算法”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“|| <<<<<<<<<<<<<<<<<<<<<<<<<您>>>>>>>>>>>>>>>>>>>>>>>>> ||”< cout< cout< cout<<“tt 請輸入您的選擇(1/2):”; cse1=getchar(); if(cse1<'1'||cse1>'2') cout<<“你的輸入有錯!”< else break; } return cse1;} int main(int argc, char *argv[]){ while(1) { switch(menu()) { case '1': int N; cout< cout< printf(“tt<<---!!@@@先來先服務(wù)調(diào)度算法@@@!!--->>n”); cout< printf(“輸入進程數(shù)目:”); scanf(“%d”,&N); input(a,N); FCFS(a,N); case '2': int N1; cout< cout< printf(“tt<<---!!@@@最短進程優(yōu)先調(diào)度算法@@@!!--->>n”); cout< printf(“輸入進程數(shù)目: ”); scanf(“%d”,&N1); input(a1,N1); sjf *b=a1; sjf *c=a1; sjff(b,N1); getchar(); } } system(“PAUSE”); return EXIT_SUCCESS;} 五、實驗結(jié)果 1.執(zhí)行結(jié)果 2.結(jié)果分析 先來先服務(wù)調(diào)度算法就是根據(jù)進程達到的時間為依據(jù),哪一個進程先來那么該進程就會先執(zhí)行;最短進程優(yōu)先調(diào)度算法則是以每個進程執(zhí)行所需時間長短為依據(jù),某一個進程執(zhí)行所需花的時間要短些那么該進程就先執(zhí)行。以上就是本次進程調(diào)度實驗的依據(jù)。 六、實驗總結(jié) 通過本次實驗了解到算法很重要,又更加明白算法本身可以節(jié)約時間,而且不同的函數(shù)之間在調(diào)用的時候要注意很多的問題。 一.實驗內(nèi)容描述 1.目的 (1)了解Windows內(nèi)存管理器(2)理解Windows的地址過程 2.內(nèi)容 任意給出一個虛擬地址,通過WinDbg觀察相關(guān)數(shù)據(jù)并找到其物理地址 二.理論分析 Windows采用頁式虛擬存儲管理技術(shù)管理內(nèi)存,頁面是硬件級別上的最小保護單位 1.Windows內(nèi)存管理器 Windows的內(nèi)存管理主要由Windows執(zhí)行體中的虛存管理程序負責(zé),并由環(huán)境子系統(tǒng)負責(zé),并由環(huán)境子系統(tǒng)負責(zé)與具體API相關(guān)的一些用戶態(tài)特性的實現(xiàn)。虛存管理程序是Windows中負責(zé)內(nèi)存管理的那些子程序和數(shù)據(jù)結(jié)構(gòu)的集合 內(nèi)存管理器的主要任務(wù)是: 地址變換:將一個進程的虛擬地址空間轉(zhuǎn)譯為物理內(nèi)存地址 交換:當(dāng)內(nèi)存不足時,將內(nèi)存中的有些內(nèi)容轉(zhuǎn)移到磁盤上,并且以后還要再次將這些內(nèi)容讀回 2.Windows內(nèi)存管理策略 Windows采用頁式虛擬存儲管理技術(shù)管理內(nèi)存,頁面是硬件級別上最小的保護單位。根據(jù)硬件的體系結(jié)構(gòu)不同,頁面尺寸被分為兩種,大頁面和小頁面。X86系統(tǒng)下小頁面為4KB,大頁面為4MB。大頁面的優(yōu)點是:當(dāng)引用同一頁面內(nèi)其他數(shù)據(jù)時,地址轉(zhuǎn)移的速度會很快。不過使用大頁面通常要較大的內(nèi)存空間,而且必須用一個單獨的保護項來映射,因此可能會造成出現(xiàn)錯誤而不引發(fā)內(nèi)存訪問違例的情況。通常PC機都為小頁面 3.Windows虛擬地址空間布局 x86結(jié)構(gòu)下的布局方式: 默認情況下,32位Windows系統(tǒng)中每個用戶進程可以占有2GB的私有地址空間。操作系統(tǒng)占有另外的2GB 2GB用戶的進程地址空間布局如表: 2GB的系統(tǒng)地址空間布局如同: 3.虛擬地址轉(zhuǎn)譯 地址轉(zhuǎn)譯是指將進程的虛擬地址空間映射到實際物理頁面的過程。x86系統(tǒng)中地址轉(zhuǎn)譯過程如圖: 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)如下: 頁目錄:每個進程都有一個頁目錄,它是內(nèi)存管理器為了映射進程中所有的頁表位置而創(chuàng)建的一個頁面。進程也目錄的地址被保存在內(nèi)核進程快KPROCESS中,在x86系統(tǒng)上,它被映射到虛擬地址0xC0300000,當(dāng)一個進程正在執(zhí)行時,CPU可以通過寄存器CR3知道該進程頁目錄的位置。頁目錄由目錄項(PDE)構(gòu)成,每個PDE長4字節(jié),描述了該進程中所有可能的頁表的狀態(tài)和位置。其格式和PTE類似。x86系統(tǒng)上,要描述完整的4GB虛擬地址空間,需要1024個頁表。因此映射這些頁表的進程頁目錄需包含1024個PDE,恰好占用一個頁面。 頁表:進程的頁目錄項指向頁表。每個頁表占用一個頁面,由1024項PTE組成。一個有效的PTE大小為4字節(jié),包含兩個主域:數(shù)據(jù)所在的物理頁面的頁面幀編號(PNF)或者內(nèi)存中一個頁面的物理地址的PFN;一些描述該頁面狀態(tài)和保護屬性的標(biāo)志。 虛擬地質(zhì)結(jié)構(gòu):x86系統(tǒng)上,一個32位虛擬地址被解釋為三個單獨的部分,頁目錄索引、頁表索引和字節(jié)索引。由于頁目錄項有1024個,因此頁目錄索引為10位;一個也表中含有1024個PTE。因此頁表索引也為10位,字節(jié)索引為12位,正好表示一頁(4KB)內(nèi)容 三.實驗步驟及結(jié)果 1.查找頁目錄首地址 以程序WG.exe作為觀測對象。 啟動WinDbg到內(nèi)核調(diào)試模式,運行程序WG.exe。終斷目標(biāo)機運行,輸入命令:kd>!process 發(fā)現(xiàn)WG.exe進程正處于運行狀態(tài) 輸入命令: 在KPROCESS中名為DirectoryTableBase的域,對應(yīng)值為0x9fa6000,即WG.exe進程頁目錄的物理地址 查看CR3寄存其中的內(nèi)容,輸入命令: CR3寄存其中的值和KPROCESS中記錄的頁目錄基址相同。這是因為在CPU切換執(zhí)行任務(wù)時,其內(nèi)容要更新為當(dāng)前進程的頁目錄基址。2.地址轉(zhuǎn)譯過程 假設(shè)給定的虛擬地址為0x401001 輸入命令: 可以看到: PDE的虛擬地址為C0300004.PTE的虛擬地址為C0001004 最后一行信息“pfn 9e4a---DA--UWEV”表示PDE中的具體內(nèi)容,9e4a是給定虛擬地址所在頁表在內(nèi)存中對應(yīng)的物理頁號,“---DA—UWEV”是標(biāo)志信息,“pfn a173----A--UREV”表示PTE中的具體內(nèi)容,a173是數(shù)據(jù)頁裝入內(nèi)存的物理頁號。 將數(shù)據(jù)頁對應(yīng)的物理頁號a173加上業(yè)內(nèi)索引(0x1)即可得到虛擬地址0x401001的物理地址 3.觀察系統(tǒng)頁表 給定觀測虛擬地址為0x80001001 輸入命令: 當(dāng)前正在執(zhí)行的進程是:WG.exe 輸入命令: 得到PDE為C0300800,其對應(yīng)的物理頁號為3b 繼續(xù)讓目標(biāo)機運行,啟動A.exe,然后中斷目標(biāo)機運行。輸入命令: 當(dāng)前正在執(zhí)行的進程為A.exe 輸入命令: PDE信息和對應(yīng)的物理頁號與前面觀測到的相同 四.結(jié)論 1.數(shù)據(jù)頁對應(yīng)的物理頁號加上相應(yīng)業(yè)內(nèi)索引即可得到虛擬地址的物理地址 2.不同的進程頁目錄都指向了相同的系統(tǒng)表頁 五.心得體會 在這次上機實驗,通過對WinDbg和VPc的調(diào)試運用,我熟悉了Windows內(nèi)存管理器的結(jié)構(gòu),也認知到Windows如何進行地址轉(zhuǎn)譯和轉(zhuǎn)換。對相關(guān)的知識也進行了溫習(xí),更牢的掌握了相關(guān)知識。當(dāng)然這些還遠遠不夠,我以后還要繼續(xù)不斷努力,去學(xué)習(xí)了解掌握操作系統(tǒng)的各方面知識。 附錄: 1.A.exe代碼 #include #define N 1 HANDLE mutexSemaphore;HANDLE synchSemaphore_1;HANDLE synchSemaphore_2; HANDLE mutexDisplay; void Display(char*str,int delayTime){ if(WaitForSingleObject(mutexDisplay,INFINITE)==WAIT_OBJECT_0){ printf(“%snn”,str);ReleaseMutex(mutexDisplay);Sleep(delayTime);} } void useTime(double limit){ for(double i=0;i<=limit;i+=0.001);} void CreateProduct(){ Display(“Creating a production...”,0);useTime(200000);Display(“Creating finished.”,100);} void PutProduct(){ Display(“Putting a production...”,0);useTime(150000);Display(“Putting finished”,100);} void GetProduct(){ Display(“Getting a production...”,0);useTime(100000);Display(“Getting finished.”,100);} void ConsumeProduct(){ Display(“Cosuming a production...”,0);useTime(100000);Display(“Cosuming finished.”,100);} void Producer(){ while(true){ CreateProduct(); if(WaitForSingleObject(synchSemaphore_1,INFINITE)==WAIT_OBJECT_0){ if(WaitForSingleObject(mutexSemaphore,INFINITE)==WAIT_OBJECT_0){ PutProduct();ReleaseSemaphore(mutexSemaphore,1,NULL);} ReleaseSemaphore(synchSemaphore_2,1,NULL);} } } void Consumer(){ while(true){ if(WaitForSingleObject(synchSemaphore_2,INFINITE)==WAIT_OBJECT_0){ if(WaitForSingleObject(mutexSemaphore,INFINITE)==WAIT_OBJECT_0){ GetProduct();ReleaseSemaphore(mutexSemaphore,1,NULL);} ReleaseSemaphore(synchSemaphore_1,1,NULL);} ConsumeProduct();} } int main(){ HANDLE thread[2];DWORD threadID[2]; synchSemaphore_1=CreateSemaphore(NULL,N,N,NULL);synchSemaphore_2=CreateSemaphore(NULL,0,N,NULL);mutexSemaphore=CreateSemaphore(NULL,1,1,NULL); mutexDisplay=CreateMutex(NULL,FALSE,NULL); printf(“Program start.Please use WinDbg to observe main thread.nPress any key to continue...n”);getchar(); thread[0]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Producer),NULL,CREATE_SUSPENDED,&threadID[0]);printf(“A producer was created.Please use WinDbg to observe producer thread.nPress any key to continue...n”);getchar(); thread[1]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Consumer),NULL,CREATE_SUSPENDED,&threadID[1]);printf(“A Consumer was created.Please use WinDbg to observe Consumer thread.nPress any key to continue...n”);getchar(); printf(“Please select:n[1]Make producer thread runn[2]Make Consumer thread runn”);bool flag=true;bool flag_1=true,flag_2=true;int count=0;while(flag){ if(getchar()=='1'&&flag_1){ ResumeThread(thread[0]);count++;flag_1=false;} else if(getchar()=='2'&&flag_2){ ResumeThread(thread[1]);count++;flag_2=false;} if(count==2)flag=false;} WaitForMultipleObjects(1,thread,TRUE,INFINITE); return 0;} 2.WG.exe代碼: #include int main(){ int a=0;printf(“I'm Wangn”);while(true){a++;} }第二篇:操作系統(tǒng)進程調(diào)度實驗
第三篇:1.操作系統(tǒng)實驗內(nèi)容(進程調(diào)度)
第四篇:操作系統(tǒng)進程調(diào)度算法模擬實驗報告
第五篇:操作系統(tǒng) 單處理機系統(tǒng)的進程調(diào)度