PAGEPAGE3《操作系統(tǒng)》實驗指導(dǎo)書河南科技大學(xué)電子信息工程學(xué)院計算機系2011.3PAGE10目錄TOC\o"1-3"\h\z實驗環(huán)境 1實驗報告要求 1實驗一進程控制與處理機調(diào)度綜合實驗 2實驗二存儲管理與頁面置換算法 7實驗環(huán)境本課程實驗硬件環(huán)境為PⅢ以上的處理器，帶有顯示器。操作系統(tǒng)使用windows98以上操作系統(tǒng)，基本編程語言為C語言。實驗報告要求實驗報告應(yīng)包含以下內(nèi)容：（1）實驗題目（2）實驗?zāi)康模?）實驗環(huán)境（4）算法描述（5）程序源代碼（6）出現(xiàn)的問題（7）對問題的解決方案（8）實驗結(jié)果與結(jié)果分析（9）實驗思考（學(xué)生對本次實驗的收獲的總結(jié)）實驗一進程控制與處理機調(diào)度綜合實驗一、實驗?zāi)康耐ㄟ^模擬進程控制方法及單處理機系統(tǒng)的進程調(diào)度，了解進程的結(jié)構(gòu)，進程的創(chuàng)建與撤消，進程的組織及進程的狀態(tài)及其轉(zhuǎn)換，掌握進程調(diào)度策略。二、實驗學(xué)時4學(xué)時三、實驗內(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)度算法的流程圖如下：圖1-1流程圖五、參考程序#include"stdio.h"#include<stdlib.h>#include<conio.h>#definegetpch(type)(type*)malloc(sizeof(type))#defineNULL0structpcb{/*定義進程控制塊PCB*/charname[10];charstate;intsuper;intntime;intrtime;structpcb*link;}*ready=NULL,*p;typedefstructpcbPCB;voidsort()/*建立對進程進行優(yōu)先級排列函數(shù)*/{}voidinput()/*建立進程控制塊函數(shù)*/{inti,num;printf("\n請輸入進程數(shù)量?");scanf("%d",&num);for(i=0;i<num;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ù)*/}}intspace(){intl=0;PCB*pr=ready;while(pr!=NULL){l++;pr=pr->link;}return(l);}voiddisp(PCB*pr)/*建立進程顯示函數(shù),用于顯示當(dāng)前進程*/{printf("\nqname\tstate\tsuper\tndtime\truntime\n");printf("|%s\t",pr->name);printf("|%c\t",pr->state);printf("|%d\t",pr->super);printf("|%d\t",pr->ntime);printf("|%d\t",pr->rtime);printf("\n");}voidcheck()/*建立進程查看函數(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;}}voiddestroy()/*建立進程撤消函數(shù)(進程運行結(jié)束,撤消進程)*/{printf("\n進程[%s]已完成.\n",p->name);free(p);}voidrunning()/*建立進程就緒函數(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ù)*/}}voidmain()/*主函數(shù)*/{intlen,h=0;charch;input();len=space();while((len!=0)&&(ready!=NULL)){ch=getchar();h++;printf("\nTheexecutenumber:%d\n",h);p=ready;ready=p->link;p->link=NULL;p->state='R';check();running();printf("\n按任一鍵繼續(xù)");ch=getchar();}printf("\n\n進程已經(jīng)完成.\n");ch=getchar();}完成上述實驗示例程序，按照優(yōu)先級算法補充出sort()子程序的內(nèi)容。若修改優(yōu)先數(shù)時增加下列原則：進程等待的時間超過某一時限時增加其優(yōu)先數(shù)，參考上述例程，寫出程序。六、選做題完成FCFS或SPF算法。七、思考題編寫一個多道程序系統(tǒng)的作業(yè)調(diào)度模擬程序,可采用任一調(diào)度算法。對于多道程序系統(tǒng)，要假定系統(tǒng)中具有的各種資源及數(shù)量、調(diào)度作業(yè)時必須考慮到每個作業(yè)的資源要求。實驗二存儲管理與頁面置換算法一、實驗?zāi)康耐ㄟ^模擬頁式虛擬存儲管理中地址轉(zhuǎn)換和頁面置換，了解頁式虛擬存儲管理的思想，掌握頁式地址轉(zhuǎn)換過程和缺頁中斷處理過程。二、實驗學(xué)時4學(xué)時三、實驗內(nèi)容單機模擬頁式虛擬存儲管理中地址轉(zhuǎn)換和頁面置換過程。首先對頁表進行初始化；輸入要訪問的邏輯地址（可為16進制或10進制），程序分離出邏輯地址的頁號，查找頁表，根據(jù)頁表完成地址轉(zhuǎn)換，輸出轉(zhuǎn)換后的地址；若缺頁則提示中斷發(fā)生，按某種頁面置換算法（FIFO，LRU）進行頁面置換，并修改和輸出頁表，輸出絕對地址。最后輸出置換情況和缺頁次數(shù)。四、算法描述1內(nèi)存的分配和管理方案在進程創(chuàng)建時必須為它分配一定的內(nèi)存資源，內(nèi)存資源的分配與管理有很多方法，從動態(tài)性分有靜態(tài)的和動態(tài)的分配方法，從連續(xù)性上分有連續(xù)的和不連續(xù)的分配方案。連續(xù)的分配方案是程序的執(zhí)行速度加快但會使內(nèi)存出現(xiàn)碎片而不能得到應(yīng)用，而不連續(xù)的分配方案可以使內(nèi)存碎片得到充分的應(yīng)用，但由于訪問內(nèi)存次數(shù)的增多使程序執(zhí)行的速度下降。2內(nèi)存的分配的過程在作業(yè)執(zhí)行前，向系統(tǒng)提供內(nèi)存的請求表，在系統(tǒng)為作業(yè)創(chuàng)建進程時，要為進程分配內(nèi)存資源。以分頁系統(tǒng)為例，系統(tǒng)首先確定進程需要的頁面數(shù)量，然后順序查找位圖(系統(tǒng)為每一個頁面分配一位內(nèi)存中的各個頁面組成一個數(shù)組，如果該位為1說明該位所指示的頁正在被使用，如果該位為0說明該位指示的頁面空閑)若存在所需要的空閑頁面則此次分配成功，否則分配失敗，若分配成功系統(tǒng)首先把分配出去的頁面所屬的位置為1，然后形成進程所需的頁表。3算法思想本程序有兩個功能：一是地址轉(zhuǎn)換；二是模擬頁面置換情況。(1)地址轉(zhuǎn)換:add_tran將邏輯地址中的頁號分離出來，查找頁表，將查找到的塊號與邏輯地址中的頁內(nèi)偏移量合成實際地址，若查找不到則產(chǎn)生缺頁中斷，按FIFO的方法置換頁面。(a)數(shù)據(jù)結(jié)構(gòu)：array[max][2]為頁表，其中array[n][0]為頁號，array[n][1]為塊號，size_PT表示系統(tǒng)分配給進程的塊數(shù)，即頁表中的頁數(shù)。（b）地址轉(zhuǎn)換算法思想首先初始化頁表：輸入分配的塊數(shù)(頁表的大小)，然后輸入初始頁表中的頁號和相對應(yīng)的塊號，初始化完成后程序輸出初始化后的頁表。然后是地址轉(zhuǎn)換：輸入16進制邏輯地址，程序分離出邏輯地址的頁號，然后查找頁表，若缺頁則提示中斷發(fā)生，并修改頁表，然后輸出轉(zhuǎn)換后的地址，輸出頁表。(c)執(zhí)行情況程序提示“pleaseinputsizeofthepagetable：”，要求輸入分配的塊數(shù)s_PT，即頁表的大小。然后根據(jù)size_PT，循環(huán)輸入初始化頁表里的頁號和對應(yīng)的塊號。用j來表示下一個將會被置換的頁面存放位置，初始指向頁表中最后一個頁面，按照(j+1)％size_PT循環(huán)。然后程序輸出頁表情況：頁號和對應(yīng)的塊號。至此初始化完成。程序提示“inputtheaddersswantedtobetranslated(0exit)：”，要求輸入要轉(zhuǎn)換的邏輯地址。程序分離出頁號后查找頁表，查找到則直接輸出轉(zhuǎn)換后的地址。否則提示“intermittenceoccurred,pageAhasbeenreplacedwithpageB”。（A代表被置換的頁號，B代表置換后的頁號。）然后再輸出轉(zhuǎn)換后的地址(16進制)。輸出轉(zhuǎn)換后的地址后，程序還把轉(zhuǎn)換后的頁表顯示出來，可以清楚地了解頁表是否被置換和置換情況。(d)結(jié)果舉例設(shè)size_PT為3，初始化頁表為Page：1block：2,page：3block：5，page：6block：3。輸入邏輯地址4ff(程序假設(shè)頁面大小為1k即1024)。則其頁號為1，查找頁表，不產(chǎn)生缺頁中斷，塊號為2，則輸出轉(zhuǎn)換后的地址為8FF，頁表不變。輸入邏輯地址81a，則其頁號為2，查找頁表，產(chǎn)生缺頁中斷，此時j指向page6，將page6置換為page2，塊號為3。則輸出轉(zhuǎn)換后的地址為c1a，頁表變?yōu)镻age：1block：2，page：3,block：5．page：2block：3。置換后j變成(2+1)％size_PT：0，指向頁表中第一項page1。（2）頁面置換模擬：page_si(a)算法思想輸入頁面序列，缺頁時按FIFO的策略進行頁面置換，輸出置換情況和缺頁次數(shù)。假設(shè)頁表大小不超過max，輸入的頁面數(shù)不超過max*lO。(b)數(shù)據(jù)結(jié)構(gòu)arrayl[max]表示簡化了的頁表，只包含頁號，array2[max*lO]存放頁面序列。size_PT表示分配給該進程的塊數(shù)，size2表示頁面序列長度。page_rep指向下一個將被置換的頁面，初始為O，指向頁表的第一項。Sum_int用來計算中斷次數(shù)。(c)程序執(zhí)行流程初始化：輸入分配的塊數(shù)size_PT，然后對頁表共size_PT項賦值-1，表示空。輸入頁面序列，存放于數(shù)組array2中。按照size2循環(huán)，依次查找頁面是否存在于頁表中，不存在則置換頁面，page_rep初始為0，變化同上。格式化依次輸出訪問下一個頁面后的頁表，然后輸出缺頁中斷總次數(shù)。(d)執(zhí)行結(jié)果舉例輸入size_PT為2輸入頁面序列為1，3，5，4，5，-1(-1表示輸入結(jié)束)輸出為113535454therehasbeen4intermittencesoccurred表示有4次中斷發(fā)生五、參考程序#include“stdio.h”#definemax100/*定義頁面數(shù)組大小的上限*/#definesize_pa1024voidadd_tran(){ intarray[max][2];/*頁表，其中array[n][0]為頁號，array[n][1]為塊號*/ intsize_PT； intno_page,no_block;/*no_page,no_block分別是頁號和塊號*/ intif_quit1;/*if_quit1退出子程序標(biāo)志*/ inti,j；/*j表示下一個將被置換的頁面位置*/ intadd_logic,add_sys;/*邏輯地址和絕對地址*/ intif_page;/*中斷標(biāo)志*/ if_quit1=0;/*退出標(biāo)志*/ /*初始化頁表*/ printf(“\npleaseinputsizeofthepagetable:”); scanf(“%d”,&size_PT); j=size_PT-1;printf(“\nnowinitializethepagetable,pleaseinputpagenumberandblocknumber\n”); for(i=0；I=size_PT;i++){ printf(“pagenumber:”) scanf(“%d”,&no_page);printf(“blocknumber:”) scanf(“%d”,&no_block); array[i][0]=no_page; array[i][1]=no_block;}printf(“initializingcomplete”);/*輸出初始化頁表*/printf(“\nPagetable:\n”);for(i=0;i<size_PT;i++){ printf(“page:%5d”,array[i][0]); printf(“block:%5d”,array[i][1]