計算機操作體系實驗

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

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

3、進程名、優(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ōu)先數(shù)減1（即降低一級），然后把

4、它插入就緒隊列等待CPU。每進行一次調(diào)度程序都打印一次運行進程、就緒隊列以及各個進程的PCB，以便進行檢查。重復以上過程，直到所有進程都完成為止。調(diào)度算法的流程圖如圖10.2所示。開始初始化PCB，輸入進程信息各進程按優(yōu)先數(shù)從高到低排列結(jié)束就緒隊列空？YN就緒隊列首進程投入運行時間片到，運行進程已占用CPU時間+1已到達運行進程已占用CPU時間已達到所需的運行時間進程完成撤銷該進程使運行進程的優(yōu)先數(shù)減1把運行進程插入就緒隊列圖10.2 算法流程圖進程調(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 /* 定義進程控制塊PCB */ char name10; char state; int super; int ntime; int rtime; struct pcb* link; *ready=NULL,*p; typedef struct pcb PCB;     sort() /* 建立對進程進行優(yōu)先級排列函數(shù)*/ PCB *first, *secon

6、d; int insert=0; if(ready=NULL)|(p->super)>(ready->super) /*優(yōu)先數(shù)最大者插入隊首*/ p->link=ready; ready=p; else /* 進程比較優(yōu)先數(shù)，插入適當?shù)奈恢弥?/ first=ready; second=first->link; while(second!=NULL) if(p->super)>(second->super) /*若插入進程比當前進程優(yōu)先數(shù)大，*/ /*插入到當前進程前面*/ p->link=second; first->link=p;

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

8、,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

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) /*建立進程顯示函數(shù)，用于顯示當前進程*/ 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() /* 建立進程查看函數(shù) */ PCB* pr; printf("n * 當前正在運行的進程是:%s",p->name); /*顯示當前運行進程*/ disp(p); pr=ready; printf("n *當前就緒隊列狀態(tài)為:n"); /*顯示就緒隊列狀態(tài)*/ while

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

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īng)完成.n"); ch=getchar(); 實驗二 作業(yè)調(diào)度【目的要求】用高級語言編寫和調(diào)試一個或多個作業(yè)調(diào)度的模擬程序，以加深對作業(yè)調(diào)度算法的理解。 【準備知識】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í)行等待就緒運行完成圖10.3 作業(yè)的狀態(tài)變遷（2）作業(yè)調(diào)度算法。1）先來先服務算法是按照作業(yè)到來的先后次序進行調(diào)度的。2）短作業(yè)優(yōu)先算法是比較作業(yè)申請中所指出的執(zhí)行時間，選取執(zhí)行時間最短的作業(yè)作為下一次服務的對象?！緦?/p>

14、驗內(nèi)容】作業(yè)調(diào)度和進程調(diào)度結(jié)合在一起（1）作業(yè)流信息從指定文本文件（TXT文件）中讀取。作業(yè)信息包括：作業(yè)號、進入系統(tǒng)時間、估計運行時間、優(yōu)先級、內(nèi)存需求量、磁帶機需求量，都為整型。（2）作業(yè)調(diào)度算法：先來先服務；最短作業(yè)優(yōu)先（二者選一）；進程調(diào)度算法：先來先服務；基于優(yōu)先級的算法（靜態(tài)優(yōu)先級）（二者選一）。（3）輸出作業(yè)序列。格式：作業(yè)號 時間間隔 如：1 800-810 （/* 8：00-8：10 */） 2 810-900 1 900-930 平均周轉(zhuǎn)時間：總的周轉(zhuǎn)時間/作業(yè)總數(shù)（周轉(zhuǎn)時間就是作業(yè)結(jié)束時間減去作業(yè)進入系統(tǒng)時間）。示例：#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) /* 計算進程的結(jié)束時間 */ 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)/*計算周轉(zhuǎn)時間或計算剩余的運行時間*/ 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)/*選擇當前運行進程*/ 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)時間之和*/ 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ō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); /*此時計算結(jié)束時間*/ printf("%d : %d - %d n",rp->id,rp->start,rp->end); sum+=time_time(rp->end,rp->in);/*計算周轉(zhuǎn)時間總和*/ 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)，最后一個用于標識*/ printf("Job_Proce

31、ssnn"); printf("FCFS_FCFS :n"); WORK(1,1,count);/*作業(yè)FCFS, 進程FCFS*/ init(); printf("nSHORT_FCFS :n"); WORK(2,1,count);/*作業(yè)最短運行時間優(yōu)先,進程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(); 實驗三 存儲管理【目的要求】通過編寫和調(diào)試存儲管理的模擬程序以加深對存儲管理方案的理解。熟悉虛存管理的各種頁面淘汰算法。【準備知識】1基本概念（1）存儲管理的基本功能。（2）分區(qū)存儲的基本概念和分配方法。（3）分頁存儲的基本概念和頁面置換算法。2存儲管理（1）存儲管理的功能：內(nèi)存的分配和回收、地址重定位、內(nèi)存保護和虛擬內(nèi)存（2）頁面置換

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