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

1、實(shí)驗(yàn)一 進(jìn)程調(diào)度【目的要求】用高級語言編寫和調(diào)試一個(gè)進(jìn)程調(diào)度程序，以加深對進(jìn)程的概念及進(jìn)程調(diào)度算法的理解。【準(zhǔn)備知識】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)程都是由一系列操作（動作）所組成，通過這些操作來完成其任務(wù)。因此，不同的進(jìn)程，其內(nèi)部操作也不相同。在操作系統(tǒng)中，描述一個(gè)進(jìn)程除了需要程序和私有數(shù)據(jù)外，最主要的是需要一個(gè)與動態(tài)過程相聯(lián)系

2、的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)用來描述進(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)程一一對應(yīng)，PCB中記錄了系統(tǒng)所需的全部信息、用于描述進(jìn)程情況所需的全部信息和控制進(jìn)程運(yùn)行所需的全部信息。因此，系統(tǒng)可以通過進(jìn)程的PCB來對進(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)程）和先來先服務(wù)算法。每個(gè)進(jìn)程由一個(gè)進(jìn)程控制塊（PCB）表示。進(jìn)程控制塊可以包含如下信息：進(jìn)程名、優(yōu)先數(shù)、到達(dá)時(shí)間、

3、需要運(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來表示。如果運(yùn)行一個(gè)時(shí)間片后，進(jìn)程的已占用 CPU時(shí)間已達(dá)到所需要的運(yùn)行時(shí)間，則撤銷該進(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（即降低一級），然后把它插入就緒隊(duì)列等待CPU。

4、每進(jìn)行一次調(diào)度程序都打印一次運(yùn)行進(jìn)程、就緒隊(duì)列以及各個(gè)進(jìn)程的PCB，以便進(jìn)行檢查。重復(fù)以上過程，直到所有進(jìn)程都完成為止。調(diào)度算法的流程圖如圖10.2所示。開始初始化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)程完成撤銷該進(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 #include #define getpch(type) (ty

5、pe*)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() /* 建立對進(jìn)程進(jìn)行優(yōu)先級排列函數(shù)*/ PCB *first, *second; int insert=0; if(ready=NULL)|(p-super)(ready-super) /*優(yōu)先數(shù)最大者插入隊(duì)首*/ p-

6、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; second=NULL; insert=1; else /* 插入進(jìn)程優(yōu)先數(shù)最低，則插入到隊(duì)尾*/ first=first-link; second=second-link; if(insert=0) first-link

7、=p; input() /* 建立進(jìn)程控制塊函數(shù)*/ int i,num; clrscr(); /*清屏*/ printf(n 請輸入進(jìn)程號?); scanf(%d,&num); for(i=0;iname); 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=NULL; sort(); /* 調(diào)用sort函數(shù)*/ int space() int l=0; PCB* pr=ready; while(pr!=

8、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)前正在運(yùn)行的進(jìn)

9、程是:%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(pr!=NULL) disp(pr); pr=pr-link; destroy() /*建立進(jìn)程撤銷函數(shù)（進(jìn)程運(yùn)行結(jié)束，撤銷進(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

10、 (p-super)-; p-state=w; sort(); /*調(diào)用sort函數(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(); printf(nn 進(jìn)程已

11、經(jīng)完成.n); ch=getchar(); 實(shí)驗(yàn)二 作業(yè)調(diào)度【目的要求】用高級語言編寫和調(diào)試一個(gè)或多個(gè)作業(yè)調(diào)度的模擬程序，以加深對作業(yè)調(diào)度算法的理解。 【準(zhǔn)備知識】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）先來先服務(wù)算法是按照作業(yè)到來的先后次序進(jìn)行調(diào)度的。2）短作業(yè)優(yōu)先算法是比較作業(yè)申請中所指出的執(zhí)行時(shí)間，選取執(zhí)行時(shí)間最短的作業(yè)作為下一次服務(wù)的對象?！緦?shí)驗(yàn)內(nèi)容】作業(yè)調(diào)度和進(jìn)程調(diào)度結(jié)合在一起（1）作業(yè)流信息

12、從指定文本文件（TXT文件）中讀取。作業(yè)信息包括：作業(yè)號、進(jìn)入系統(tǒng)時(shí)間、估計(jì)運(yùn)行時(shí)間、優(yōu)先級、內(nèi)存需求量、磁帶機(jī)需求量，都為整型。（2）作業(yè)調(diào)度算法：先來先服務(wù)；最短作業(yè)優(yōu)先（二者選一）；進(jìn)程調(diào)度算法：先來先服務(wù)；基于優(yōu)先級的算法（靜態(tài)優(yōu)先級）（二者選一）。（3）輸出作業(yè)序列。格式：作業(yè)號 時(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 #include #include #include #include #define

13、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; int size; int tape; int *maddr; struct jnote *next; ; int rest=4,memory101,*mh=memory,logo=0,fid=0; struct jcb

14、 *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;i100;i+) datai=-1; for(i=0;i=0&pt=size) return(mp); while(*cp=1) cp+; mp=cp; return(null); zy_div_free(mp,msize,tape,h)/*資源分配與釋放*/ int *mp,msize,tape,h;

15、 int *cp,i=msize; cp=mp; if(h=1) for(;i0;i-) *cp=1; cp+; rest=rest-tape; return (1); if(h=2) for(;i0;i-) *cp=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-me

16、m,p-tape,1); p-state=0; newj=(struct jnote *)malloc(len); rp=newj; rp-id=p-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(plogo=2)

17、selectrp(plogo,time); else return (-1); else if(jh!=null&rp!=null) if(plogo=2) if(logo=0) if(jh-prirp-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-start=0; rp=temp; rp-start=rp-in; return (0); if(fid=1) if(jh-prirp-pri

18、) 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,plogo,count) int jlogo,plogo,count; int k=count,sum=0,time,t;/*sum是周轉(zhuǎn)時(shí)間之和*/ struct jnote *cp,*p1,*newj; int *mp; selec

19、trp(plogo,0); while(k0) p=job; do if(p-state=0) p+; while(p-state=-1&p-num!=-1&(logo=0&p-in start,rp-run)|(logo=1&p-instart,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

20、; newj-start=0; newj-run=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-next!=null) cp=jp; jp=jp-next; else if(ne

21、wj-runrun) 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); logo=1; else rp-end=rpend(rp-start,rp-run); /*此時(shí)計(jì)算結(jié)束時(shí)間*/ printf(%d : %d - %d n,rp-id,rp-start,rp-

22、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; selectrp(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()

23、int i,count; count=txt();/*返回作業(yè)總數(shù)*/ for(i=0;i100;i+) memoryi=0;memoryi=-1;mh=memory;/*內(nèi)存清0，處于 未分配狀態(tài)，最后一個(gè)用于標(biāo)識*/ printf(Job_Processnn); 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 t

24、he result of process is PRI ); getchar(); clrscr(); init(); printf(Job_Processn); printf(nFCFS_PRI :n); WORK(1,2,count); init(); printf(nSHORT_PRI :n); WORK(2,2,count); getchar(); 實(shí)驗(yàn)三 存儲管理【目的要求】通過編寫和調(diào)試存儲管理的模擬程序以加深對存儲管理方案的理解。熟悉虛存管理的各種頁面淘汰算法?！緶?zhǔn)備知識】1基本概念（1）存儲管理的基本功能。（2）分區(qū)存儲的基本概念和分配方法。（3）分頁存儲的基本概念和頁面置換算

25、法。2存儲管理（1）存儲管理的功能：內(nèi)存的分配和回收、地址重定位、內(nèi)存保護(hù)和虛擬內(nèi)存（2）頁面置換算法。1）OPT算法是從內(nèi)存中移出以后不再使用的頁面；如無這樣的頁面，則選擇以后最長時(shí)間內(nèi)不需要訪問的頁。2）FIFO算法總是先淘汰那些駐留在內(nèi)存時(shí)間最長的頁面，即先進(jìn)入內(nèi)存的頁面先被置換掉。3）LRU算法是如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很長時(shí)間沒有被訪問，那么最近也不太可能會被訪問（3）缺頁率。缺頁率為某段時(shí)間內(nèi)，缺頁中斷次數(shù)與頁面走向次數(shù)之比。【實(shí)驗(yàn)內(nèi)容】題目要求：（1）實(shí)現(xiàn)三種算法：先進(jìn)先出；OPT；LRU。（2）頁面序列從指定的文本文件（TXT文件）中取出。

26、（3）輸出：第一行：每次淘汰的頁面號；第二行：顯示缺頁的總次數(shù)。示例：#include #include #include #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-tag=-1

27、;p1-num=-1; while(counttag=-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; for(;cp-num!=*p&cp-next!=null;) cp=cp-next; if (cp-num=*p) printf( ! ); else

28、 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); 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,

29、n) int array,n; int count=0,*p=array; struct page *head,*cp,*dp,*rp,*new,*endp; head=create(n); 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 h

30、ead=head-next; endp-next=cp; cp-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=head-next; printf( %d ,dp-num); free(d

31、p); 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-next; if(cp-num!=*p) count+; cp=head; for(;cp-tag!=-1&cp-next!=null;) cp=cp-next; if(cp-ta

32、g=-1) printf( * ); cp-num=*p; cp-tag=0; else i=1;q=p;q+;cp=head; while(*q!=-1&inum&cp-next!=null;) cp=cp-next; if(*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); els