計(jì)算機(jī)操作體系實(shí)驗(yàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)一 進(jìn)程調(diào)度【目的要求】用高級(jí)語(yǔ)言編寫(xiě)和調(diào)試一個(gè)進(jìn)程調(diào)度程序，以加深對(duì)進(jìn)程的概念及進(jìn)程調(diào)度算法的理解。【準(zhǔn)備知識(shí)】1基本概念（1）進(jìn)程的概念。（2）進(jìn)程的狀態(tài)和進(jìn)程控制塊。（3）進(jìn)程調(diào)度算法。2進(jìn)程調(diào)度（1）進(jìn)程的狀態(tài)。進(jìn)程狀態(tài)的轉(zhuǎn)換如圖10.1所示。運(yùn)行就緒阻塞進(jìn)程因某事件（如等待I/O完成）變成阻塞狀態(tài)某事件被解除（I/O完成）時(shí)間片已用完進(jìn)程調(diào)度程序把處理機(jī)分配給進(jìn)程圖10.1（2）進(jìn)程的結(jié)構(gòu)PCB。進(jìn)程都是由一系列操作（動(dòng)作）所組成，通過(guò)這些操作來(lái)完成其任務(wù)。因此，不同的進(jìn)程，其內(nèi)部操作也不相同。在操作系統(tǒng)中，描述一個(gè)進(jìn)程除了需要程序和私有數(shù)據(jù)外，最主要的

2、是需要一個(gè)與動(dòng)態(tài)過(guò)程相聯(lián)系的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)用來(lái)描述進(jìn)程的外部特性（名字、狀態(tài)等）以及與其他進(jìn)程的聯(lián)系（通信關(guān)系）等信息，該數(shù)據(jù)結(jié)構(gòu)稱為進(jìn)程控制塊（Process Control Block，PCB）。進(jìn)程控制塊（PCB）與進(jìn)程一一對(duì)應(yīng)，PCB中記錄了系統(tǒng)所需的全部信息、用于描述進(jìn)程情況所需的全部信息和控制進(jìn)程運(yùn)行所需的全部信息。因此，系統(tǒng)可以通過(guò)進(jìn)程的PCB來(lái)對(duì)進(jìn)程進(jìn)行管理?！緦?shí)驗(yàn)內(nèi)容】設(shè)計(jì)一個(gè)有N個(gè)進(jìn)程并行的進(jìn)程調(diào)度程序。 進(jìn)程調(diào)度算法：采用最高優(yōu)先數(shù)優(yōu)先的調(diào)度算法（即把處理機(jī)分配給優(yōu)先數(shù)最高的進(jìn)程）和先來(lái)先服務(wù)算法。每個(gè)進(jìn)程由一個(gè)進(jìn)程控制塊（PCB）表示。進(jìn)程控制塊可以包含如下信息：

3、進(jìn)程名、優(yōu)先數(shù)、到達(dá)時(shí)間、需要運(yùn)行時(shí)間、已用CPU時(shí)間、進(jìn)程狀態(tài)等。進(jìn)程的優(yōu)先數(shù)及需要的運(yùn)行時(shí)間可以事先人為地指定（也可以由隨機(jī)數(shù)產(chǎn)生）。進(jìn)程的到達(dá)時(shí)間為進(jìn)程輸入的時(shí)間。進(jìn)程的運(yùn)行時(shí)間以時(shí)間片為單位進(jìn)行計(jì)算。每個(gè)進(jìn)程的狀態(tài)可以是就緒W（Wait）、運(yùn)行R（Run）或完成F（Finish）三種狀態(tài)之一。就緒進(jìn)程獲得 CPU后都只能運(yùn)行一個(gè)時(shí)間片。用已占用CPU時(shí)間加1來(lái)表示。如果運(yùn)行一個(gè)時(shí)間片后，進(jìn)程的已占用 CPU時(shí)間已達(dá)到所需要的運(yùn)行時(shí)間，則撤銷(xiāo)該進(jìn)程，如果運(yùn)行一個(gè)時(shí)間片后進(jìn)程的已占用CPU時(shí)間還未到達(dá)所需要的運(yùn)行時(shí)間，也就是進(jìn)程還需要繼續(xù)運(yùn)行，此時(shí)應(yīng)將進(jìn)程的優(yōu)先數(shù)減1（即降低一級(jí)），然后把

4、它插入就緒隊(duì)列等待CPU。每進(jìn)行一次調(diào)度程序都打印一次運(yùn)行進(jìn)程、就緒隊(duì)列以及各個(gè)進(jìn)程的PCB，以便進(jìn)行檢查。重復(fù)以上過(guò)程，直到所有進(jìn)程都完成為止。調(diào)度算法的流程圖如圖10.2所示。開(kāi)始初始化PCB，輸入進(jìn)程信息各進(jìn)程按優(yōu)先數(shù)從高到低排列結(jié)束就緒隊(duì)列空？YN就緒隊(duì)列首進(jìn)程投入運(yùn)行時(shí)間片到，運(yùn)行進(jìn)程已占用CPU時(shí)間+1已到達(dá)運(yùn)行進(jìn)程已占用CPU時(shí)間已達(dá)到所需的運(yùn)行時(shí)間進(jìn)程完成撤銷(xiāo)該進(jìn)程使運(yùn)行進(jìn)程的優(yōu)先數(shù)減1把運(yùn)行進(jìn)程插入就緒隊(duì)列圖10.2 算法流程圖進(jìn)程調(diào)度源程序如下：jinchengdiaodu.cpp #include "stdio.h" #include <stdl

5、ib.h> #include <conio.h> #define getpch(type) (type*)malloc(sizeof(type) #define NULL 0 struct pcb /* 定義進(jìn)程控制塊PCB */ char name10; char state; int super; int ntime; int rtime; struct pcb* link; *ready=NULL,*p; typedef struct pcb PCB;     sort() /* 建立對(duì)進(jìn)程進(jìn)行優(yōu)先級(jí)排列函數(shù)*/ PCB *first, *secon

6、d; int insert=0; if(ready=NULL)|(p->super)>(ready->super) /*優(yōu)先數(shù)最大者插入隊(duì)首*/ p->link=ready; ready=p; else /* 進(jìn)程比較優(yōu)先數(shù)，插入適當(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;

7、 second=NULL; insert=1; else /* 插入進(jìn)程優(yōu)先數(shù)最低，則插入到隊(duì)尾*/ first=first->link; second=second->link; if(insert=0) first->link=p;  input() /* 建立進(jìn)程控制塊函數(shù)*/ int i,num; clrscr(); /*清屏*/ printf("n 請(qǐng)輸入進(jìn)程號(hào)?"); scanf("%d",&num); for(i=0;i<num;i+) printf("n 進(jìn)程號(hào)No.%d:n"

8、,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)程運(yùn)行時(shí)間:"); scanf("%d",&p->ntime); printf("n"); p->rtime=0;p->state='w' p->link

9、=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(&

10、quot;|%dt",pr->super); printf("|%dt",pr->ntime); printf("|%dt",pr->rtime); printf("n"); check() /* 建立進(jìn)程查看函數(shù) */ PCB* pr; printf("n * 當(dāng)前正在運(yùn)行的進(jìn)程是:%s",p->name); /*顯示當(dāng)前運(yùn)行進(jìn)程*/ disp(p); pr=ready; printf("n *當(dāng)前就緒隊(duì)列狀態(tài)為:n"); /*顯示就緒隊(duì)列狀態(tài)*/ while

11、(pr!=NULL) disp(pr); pr=pr->link; destroy() /*建立進(jìn)程撤銷(xiāo)函數(shù)（進(jìn)程運(yùn)行結(jié)束，撤銷(xiāo)進(jìn)程）*/ printf("n 進(jìn)程 %s 已完成.n",p->name); free(p); running() /* 建立進(jìn)程就緒函數(shù)（進(jìn)程運(yùn)行時(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

12、函數(shù)*/ main() /*主函數(shù)*/ int len,h=0; char ch; input(); len=space(); while(len!=0)&&(ready!=NULL) ch=getchar(); h+; printf("n The execute number:%d n",h); p=ready; ready=p->link; p->link=NULL; p->state='R' check(); running(); printf("n 按任一鍵繼續(xù)."); ch=getchar();

13、 printf("nn 進(jìn)程已經(jīng)完成.n"); ch=getchar(); 實(shí)驗(yàn)二 作業(yè)調(diào)度【目的要求】用高級(jí)語(yǔ)言編寫(xiě)和調(diào)試一個(gè)或多個(gè)作業(yè)調(diào)度的模擬程序，以加深對(duì)作業(yè)調(diào)度算法的理解。 【準(zhǔn)備知識(shí)】1基本概念（1）作業(yè)的概念。（2）作業(yè)調(diào)度的功能。（3）作業(yè)調(diào)度算法，調(diào)度性能的衡量。2作業(yè)調(diào)度（1）作業(yè)的狀態(tài)。如圖10.3所示。作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)錄入提交后備執(zhí)行等待就緒運(yùn)行完成圖10.3 作業(yè)的狀態(tài)變遷（2）作業(yè)調(diào)度算法。1）先來(lái)先服務(wù)算法是按照作業(yè)到來(lái)的先后次序進(jìn)行調(diào)度的。2）短作業(yè)優(yōu)先算法是比較作業(yè)申請(qǐng)中所指出的執(zhí)行時(shí)間，選取執(zhí)行時(shí)間最短的作業(yè)作為下一次服務(wù)的對(duì)象?！緦?shí)

14、驗(yàn)內(nèi)容】作業(yè)調(diào)度和進(jìn)程調(diào)度結(jié)合在一起（1）作業(yè)流信息從指定文本文件（TXT文件）中讀取。作業(yè)信息包括：作業(yè)號(hào)、進(jìn)入系統(tǒng)時(shí)間、估計(jì)運(yùn)行時(shí)間、優(yōu)先級(jí)、內(nèi)存需求量、磁帶機(jī)需求量，都為整型。（2）作業(yè)調(diào)度算法：先來(lái)先服務(wù)；最短作業(yè)優(yōu)先（二者選一）；進(jìn)程調(diào)度算法：先來(lái)先服務(wù)；基于優(yōu)先級(jí)的算法（靜態(tài)優(yōu)先級(jí)）（二者選一）。（3）輸出作業(yè)序列。格式：作業(yè)號(hào) 時(shí)間間隔 如：1 800-810 （/* 8：00-8：10 */） 2 810-900 1 900-930 平均周轉(zhuǎn)時(shí)間：總的周轉(zhuǎn)時(shí)間/作業(yè)總數(shù)（周轉(zhuǎn)時(shí)間就是作業(yè)結(jié)束時(shí)間減去作業(yè)進(jìn)入系統(tǒng)時(shí)間）。示例：#include <stdio.h> #i

15、nclude <string.h> #include <process.h> #include <stdlib.h> #include <conio.h> #define null 0 #define len sizeof(struct jnote) struct jcb int state; int num; int in; int run; int pri; int mem; int tape; job50; struct jnote int id; int in; int start; int run; int end; int pri;

16、int size; int tape; int *maddr; struct jnote *next; ; int rest=4,memory101,*mh=memory,logo=0,fid=0; struct jcb *p=job; struct jnote *jh=null,*rp=null,*jp=null; txt()/*從txt文件中讀取作業(yè)流*/ FILE *fp; char pt; int i,space=0,j=0,data100,h,k,count; char str10; for(i=0;i<100;i+) datai=-1; for(i=0;i<20;i+)

17、 jobi.num=-1; jobi.tape=-1; jobi.state=-1; i=0; fp=fopen("job.txt","r+"); if(fp=NULL) printf("Cann't the filen"); exit(0); while(pt=getc(fp)!=EOF) if(pt>='0'&&pt<='9') stri=pt; i+; space=0; else if(pt=' '|pt='n') if(spac

18、e=1) continue; else stri='0' dataj=atoi(str); j+; i=0; space=1; for(h=0,k=0;datak!=-1;k+,h+) jobh.num=datak;k+; jobh.in=datak;k+; jobh.run=datak;k+; jobh.pri=datak;k+; jobh.mem=datak;k+; jobh.tape=datak; if(jobh-1.tape=-1) stri='0' jobh-1.tape=atoi(str); clrscr(); for(i=0;jobi.num!=-

19、1;i+); return(i); rpend(start,run) /* 計(jì)算進(jìn)程的結(jié)束時(shí)間 */ int start, run; int end=0; int i=start%100+run; end=(start/100+i/60)*100+i%60; return(end); time_time(end,in)/*計(jì)算周轉(zhuǎn)時(shí)間或計(jì)算剩余的運(yùn)行時(shí)間*/ int in,end; int time; time=end/100*60+end%100-(in/100*60+in%100); return(time); int *m_pd(int size)/*內(nèi)存判斷*/ int *mp,*cp

20、; int i=0; mp=cp=mh; while(*mp!=-1) while(*cp=0) cp+;i+; if(i>=size) return(mp); while(*cp=1) cp+; mp=cp; return(null); zy_div_free(mp,msize,tape,h)/*資源分配與釋放*/ int *mp,msize,tape,h; int *cp,i=msize; cp=mp; if(h=1) for(;i>0;i-) *cp=1; cp+; rest=rest-tape; return (1); if(h=2) for(;i>0;i-) *cp

21、=0;cp+; rest=rest+tape; return (2); selectrp(plogo,time)/*選擇當(dāng)前運(yùn)行進(jìn)程*/ int plogo,time; struct jnote *newj; struct jnote *temp; if(jh=null&&rp=null) p=job; for(;p->state=0;) p+; zy_div_free(mh,p->mem,p->tape,1); p->state=0; newj=(struct jnote *)malloc(len); rp=newj; rp->id=p->

22、num; rp->in=p->in; rp->start=p->in; rp->run=p->run; rp->end=0; rp->pri=p->pri;rp->size=p->mem; rp->tape=p->tape; rp->maddr=mh; rp->next=null; return (0); else if(jh!=null&&rp=null) rp=jh; jh=jh->next; rp->next=null; rp->start=time; if(plo

23、go=2) selectrp(plogo,time); else return (-1); else if(jh!=null&&rp!=null) if(plogo=2) if(logo=0) if(jh->pri>rp->pri) temp=jh; jh=jh->next; temp->next=rp; printf("%d : %d - %d n",rp->id,rp->start,temp->in); rp->run-=time_time(temp->in,rp->start); rp-

24、>start=0; rp=temp; rp->start=rp->in; return (0); if(fid=1) if(jh->pri>rp->pri) temp=jh; jh=jh->next; temp->next=rp; rp=temp; rp->start=time; selectrp(plogo,time); else rp->start=time; return (0); return (0); else rp->start=time; return (0); return (0); WORK(jlogo,plo

25、go,count) int jlogo,plogo,count; int k=count,sum=0,time,t;/*sum是周轉(zhuǎn)時(shí)間之和*/ struct jnote *cp,*p1,*newj; int *mp; selectrp(plogo,0); while(k>0) p=job; do if(p->state=0) p+; while(p->state=-1&&p->num!=-1&&(logo=0&&p->in<rpend(rp-> start,rp->run)|(logo=1&

26、;&p->in<=rpend(rp->start,rp->run) mp=m_pd(p->mem); if(rest>=p->tape) t=1; else t=0; if(mp!=null&&t=1) zy_div_free(mp,p->mem,p->tape,1); p->state=0; newj=(struct jnote *)malloc(len); newj->id=p->num; newj->in=p->in; newj->start=0; newj->run=

27、p->run; newj->end=0; newj->pri=p->pri; newj->size=p->mem; newj->tape=p->tape; newj->maddr=mp; newj->next=null; if(jh=null) jh=newj; jp=jh; else if (jlogo=1) jp->next=newj;jp=newj; /*作業(yè)為FCFS*/ else /*作業(yè)為最短運(yùn)行時(shí)間優(yōu)先*/ jp=cp=jh; if(newj->run>=jp->run&&jp-&

28、gt;next!=null) cp=jp; jp=jp->next; else if(newj->run<jp->run) if(cp=jp) newj->next=jp; jh=newj; else cp->next=newj; newj->next=jp; else jp->next=newj; if (plogo=2) selectrp(plogo,0); p+; while(p->state=0); if (logo=0) zy_div_free(rp->maddr,rp->size,rp->tape,2); lo

29、go=1; else rp->end=rpend(rp->start,rp->run); /*此時(shí)計(jì)算結(jié)束時(shí)間*/ printf("%d : %d - %d n",rp->id,rp->start,rp->end); sum+=time_time(rp->end,rp->in);/*計(jì)算周轉(zhuǎn)時(shí)間總和*/ if(k-1=0) p1=rp;rp=rp->next;free(p1); break; time=rp->end; p1=rp; rp=rp->next; free(p1); k-; fid=1; sele

30、ctrp(plogo,time); fid=0; logo=0; printf("The average time : %d n",sum/count); init() int i; for(i=0;jobi.num!=-1;i+) jobi.state=-1; logo=0;fid=0; main() int i,count; count=txt();/*返回作業(yè)總數(shù)*/ for(i=0;i<100;i+) memoryi=0;memoryi=-1;mh=memory;/*內(nèi)存清0，處于 未分配狀態(tài)，最后一個(gè)用于標(biāo)識(shí)*/ printf("Job_Proce

31、ssnn"); printf("FCFS_FCFS :n"); WORK(1,1,count);/*作業(yè)FCFS, 進(jìn)程FCFS*/ init(); printf("nSHORT_FCFS :n"); WORK(2,1,count);/*作業(yè)最短運(yùn)行時(shí)間優(yōu)先,進(jìn)程FCFS*/ printf("nnPlease press keyboard to see the result of process is PRI "); getchar(); clrscr(); init(); printf("Job_Processn

32、"); printf("nFCFS_PRI :n"); WORK(1,2,count); init(); printf("nSHORT_PRI :n"); WORK(2,2,count); getchar(); 實(shí)驗(yàn)三 存儲(chǔ)管理【目的要求】通過(guò)編寫(xiě)和調(diào)試存儲(chǔ)管理的模擬程序以加深對(duì)存儲(chǔ)管理方案的理解。熟悉虛存管理的各種頁(yè)面淘汰算法?！緶?zhǔn)備知識(shí)】1基本概念（1）存儲(chǔ)管理的基本功能。（2）分區(qū)存儲(chǔ)的基本概念和分配方法。（3）分頁(yè)存儲(chǔ)的基本概念和頁(yè)面置換算法。2存儲(chǔ)管理（1）存儲(chǔ)管理的功能：內(nèi)存的分配和回收、地址重定位、內(nèi)存保護(hù)和虛擬內(nèi)存（2）頁(yè)面置換

33、算法。1）OPT算法是從內(nèi)存中移出以后不再使用的頁(yè)面；如無(wú)這樣的頁(yè)面，則選擇以后最長(zhǎng)時(shí)間內(nèi)不需要訪問(wèn)的頁(yè)。2）FIFO算法總是先淘汰那些駐留在內(nèi)存時(shí)間最長(zhǎng)的頁(yè)面，即先進(jìn)入內(nèi)存的頁(yè)面先被置換掉。3）LRU算法是如果某一頁(yè)被訪問(wèn)了，那么它很可能馬上又被訪問(wèn)；反之，如果某一頁(yè)很長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)，那么最近也不太可能會(huì)被訪問(wèn)（3）缺頁(yè)率。缺頁(yè)率為某段時(shí)間內(nèi)，缺頁(yè)中斷次數(shù)與頁(yè)面走向次數(shù)之比?！緦?shí)驗(yàn)內(nèi)容】題目要求：（1）實(shí)現(xiàn)三種算法：先進(jìn)先出；OPT；LRU。（2）頁(yè)面序列從指定的文本文件（TXT文件）中取出。（3）輸出：第一行：每次淘汰的頁(yè)面號(hào)；第二行：顯示缺頁(yè)的總次數(shù)。示例：#include <s

34、tdio.h> #include <stdlib.h> #include <malloc.h> #define null 0 #define len sizeof(struct page) struct page int num; int tag; struct page *next; ; struct page *create(int n) /*建立分配的內(nèi)存空間，并初始化，返回頭結(jié)點(diǎn)*/ int count=1; struct page *p1,*p2,*head; head=p2=p1=(struct page *)malloc(len); p1->t

35、ag=-1;p1->num=-1; while(count<n) count+; p1=(struct page *)malloc(len); p1->tag=-1;p1->num=-1; p2->next=p1; p2=p1; p2->next=null; return(head); void FIFO(array,n) int array,n; int *p; struct page *cp,*dp,*head,*new; int count=0; head=create(n); p=array; while(*p!=-1) cp=dp=head; fo

36、r(;cp->num!=*p&&cp->next!=null;) cp=cp->next; if (cp->num=*p) printf(" ! " ); else count+; cp=head; for(;cp->tag!=-1&&cp->next!=null;) cp=cp->next; if(cp->tag=-1) cp->num=*p; cp->tag=0; printf(" * "); else new=(struct page*)malloc(len

37、); new->num=*p; new->tag=0; new->next=null; cp->next=new; head=head->next; printf(" %d ",dp->num); free(dp); p+; printf("nQueye Zongshu : %d n",count); void LRU(array,n) int array,n; int count=0,*p=array; struct page *head,*cp,*dp,*rp,*new,*endp; head=create(n);

38、 while(*p!=-1) cp=dp=rp=endp=head; for(;endp->next!=null;) endp=endp->next; for(;cp->num!=*p&&cp->next!=null;) rp=cp;cp=cp->next; if(cp->num=*p) printf(" ! "); if(cp->next!=null) if(cp!=head) rp->next=cp->next; else head=head->next; endp->next=cp; c

39、p->next=null; else count+; cp=rp=head; for(;cp->tag!=-1&&cp->next!=null;) cp=cp->next; if(cp->tag=-1) printf(" * "); cp->num=*p; cp->tag=0; else new=(struct page *)malloc(len); new->num=*p; new->tag=0; new->next=null; cp->next=new; dp=head; head=hea

40、d->next; printf(" %d ",dp->num); free(dp); p+; printf("nQueye Zongshu : %d n",count); OPT(array,n) int array,n; int *p,*q,count=0,i; struct page *head,*cp,*dp,*new; p=array; head=create(n); while(*p!=-1) cp=head; for(;cp->num!=*p&&cp->next!=null;) cp=cp->ne

41、xt; if(cp->num!=*p) count+; cp=head; for(;cp->tag!=-1&&cp->next!=null;) cp=cp->next; if(cp->tag=-1) printf(" * "); cp->num=*p; cp->tag=0; else i=1;q=p;q+;cp=head; while(*q!=-1&&i<n) for(;*q!=cp->num&&cp->next!=null;) cp=cp->next; if(

42、*q=cp->num) cp->tag=1; i+; q+;cp=head; if(i=n) for(;cp->tag!=0;) cp=cp->next; printf(" %d ",cp->num); cp->num=*p; else cp=head; for(;cp->tag!=0;) cp=cp->next; if(cp=head) for(;cp->next!=null;) cp=cp->next; new=(struct page *)malloc(len); new->num=*p; new->tag=0; new->next=null; cp->next=new; dp=head; head=head->next; printf(" %d ",dp->num); free(dp); else printf(" %d ",cp->num); cp->num=*p; cp=h