操作系統(tǒng)課程設(shè)計報告

1、操作系統(tǒng)課程設(shè)計報告班級：計算機四班學(xué)號：08031422姓名：王 朋 飛實驗一 進程調(diào)度一、實驗?zāi)康耐ㄟ^一個簡單的進程調(diào)度模擬程序的實現(xiàn)，加深對進程調(diào)度算法，進程切換的理解。二、需求分析采用動態(tài)優(yōu)先數(shù)的方法，編寫一進程調(diào)度程序模擬程序。模擬程序只進行相應(yīng)的調(diào)度模擬操作，不需要實際程序。 (1) 假定系統(tǒng)有五個進程，每一個進程用一個進程控制塊PCB來代表，進程控制塊的格式為：進程名指針要求運行時間優(yōu)先數(shù)狀態(tài)其中，進程名作為進程的標(biāo)識，假設(shè)五個進程的進程名分別為P1，P2，P3，P4，P5。指針按優(yōu)先數(shù)的大小把五個進程連成隊列，用指針指出下一個進程的進程控制塊的首地址，最后一個進程中的指針為“0

2、”。要求運行時間假設(shè)進程需要運行的單位時間數(shù)。優(yōu)先數(shù)賦予進程的優(yōu)先數(shù)，調(diào)度時總是選取優(yōu)先數(shù)大的進程先執(zhí)行。狀態(tài)可假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個進程的初始狀態(tài)都為“就緒”，用“R”表示，當(dāng)一個進程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。(2) 在每次運行你所設(shè)計的處理器調(diào)度程序之前，為每個進程任意確定它的“優(yōu)先數(shù)”和“要求運行時間”。(3) 為了調(diào)度方便，把五個進程按給定的優(yōu)先數(shù)從大到小連成隊列。用一單元指出隊首進程，用指針指出隊列的連接情況。(4) 處理器調(diào)度總是選隊首進程運行。采用動態(tài)改變優(yōu)先數(shù)的辦法，進程每運行一次優(yōu)先數(shù)就減“1”。由于本實習(xí)是模擬處理器調(diào)度，所以，

3、對被選中的進程并不實際的啟動運行，而是執(zhí)行：優(yōu)先數(shù)-1要求運行時間-1來模擬進程的一次運行。提醒注意的是：在實際的系統(tǒng)中，當(dāng)一個進程被選中運行時，必須恢復(fù)進程的現(xiàn)場，讓它占有處理器運行，直到出現(xiàn)等待事件或運行結(jié)束。在這里省去了這些工作。(5) 進程運行一次后，若要求運行時間?0，則再將它加入隊列（按優(yōu)先數(shù)大小插入，且置隊首標(biāo)志）；若要求運行時間=0，則把它的狀態(tài)修改成“結(jié)束”（E），且退出隊列。(6) 若“就緒”狀態(tài)的進程隊列不為空，則重復(fù)上面（4）和（5）的步驟，直到所有進程都成為“結(jié)束”狀態(tài)。(7) 在所設(shè)計的程序中應(yīng)有顯示或打印語句，能顯示或打印每次被選中進程的進程名以及運行一次后進程隊

4、列的變化。(8) 為五個進程任意確定一組“優(yōu)先數(shù)”和“要求運行時間”，啟動所設(shè)計的處理器調(diào)度程序，顯示或打印逐次被選中進程的進程名以及進程控制塊的動態(tài)變化過程。三、概要設(shè)計1程序概要設(shè)計圖2 程序源代碼jingchendiaodu.cpp #include "stdio.h" #include <stdlib.h> #include <conio.h> #define getpch(type) (type*)malloc(sizeof(type) #define NULL 0 struct pcb /* 定義進程控制塊PCB */ char

5、 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, *second; int insert=0; if(ready=NULL)|(p->super)>(ready->super) /*優(yōu)先級最大者,插入隊首*/ p->link=ready; ready=p; else /* 進程比較優(yōu)先級,插入適當(dāng)?shù)奈恢弥?/

6、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;  in

7、put() /* 建立進程控制塊函數(shù)*/ int i,num; clrscr(); /*清屏*/ printf("n 請輸入進程號?"); 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"

8、,&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); disp(PCB * pr) /*建立進程顯示函

9、數(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"); chec

10、k() /* 建立進程查看函數(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); running(

11、) /* 建立進程就緒函數(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ù)*/ main() /*主函數(shù)*/ int len,h=0; char ch; input(); len=space(); while(len!=0)&&(ready!=NULL) ch=getchar(); h+; printf("n The

12、 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īng)完成.n"); ch=getchar(); 實驗二 存儲管理一、實驗?zāi)康拇鎯芾淼闹饕δ苤皇呛侠淼胤峙淇臻g。請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本實驗的目的是通過請求頁式存儲管理中頁面置換算法模擬設(shè)計 , 了解虛

13、擬存儲技術(shù)的特點 , 掌握請求頁式存儲管理的頁面置換算法。二、需求分析通過隨機數(shù)產(chǎn)生一個指令序列,共320條指令。指令的地址按下述原則生成 : 50% 的指令是順序執(zhí)行的； 25% 的指令是均勻分布在前地址部分； 25% 的指令是均勻分布在后地址部分。具體的實施方法是 :在 0,319 的指令地址之間隨機選取一起點 m;順序執(zhí)行一條指令;在前地址0,m+1中隨機選取一條指令并執(zhí)行 , 該指令的地址為 m; 順序執(zhí)行一條指令 , 其地址為 m+1;在后地址 m+2,319 中隨機選取一條指令并執(zhí)行 ;重復(fù)上述步驟 , 直到執(zhí)行 320 次指令。(1) 將指令序列變換成為頁地址流設(shè)：頁面大小為 1

14、K;用戶內(nèi)存容量為 4 頁到 32 頁 ;用戶虛存容量為 32K 。在用戶虛存中 , 按每 K 存放 10 條指令排列虛存地址 , 即 320 條指令在虛存中的存放方式為 :第 0 條 第 9 條指令為第 0 頁 ( 對應(yīng)虛存地址為 0,9);第 10 條 第 19 條指令為第 1 頁 ( 對應(yīng)虛存地址為 10,19 ) ;第 310 條 第 319 條指令為第 31 頁 ( 對應(yīng)虛存地址為 310,319) 。按以上方式 , 用戶指令可組成 32 頁。(2) 計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。 先進先出的算法 (FIFO)； 最近最久未使用算法 (LRU);命中率 = 1 -

15、頁面失效次數(shù)頁地址流長度在本實驗中 , 頁地址流長度為 320, 頁面失效次數(shù)為每次訪問相應(yīng)指令時 , 該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。三、概要設(shè)計1概要設(shè)計流程圖開 始生成地址流輸入算法號S1S4形成地址頁號用戶內(nèi)存空間msize=2Msize32 OPT()FIFO()LRU()LFU()Msize加1S=? 是否用其他算法繼續(xù)結(jié) 束NY1234YN提示出錯，重新輸入2程序源代碼produce_addstream.h#ifndef PRODUCE_ADDSTREAM_H#define PRODUCE_ADDSTREAM_H#include<stdio.h>#include<

16、;stdlib.h>#include<time.h>#include<iomanip.h>#include<vector> using namespace std;#define random(x) (rand()%x)#define MAX_LENGTH 320struct produceint num; /指令序號int zhiling; /指令地址int virtualpage; /指令虛頁號produce *next;struct produce*creatlist();void insert(struct produce *first,str

17、uct produce *s); /插入一個節(jié)點（尾插法）void print(struct produce *first); /打印函數(shù)int max(vector<vector<int> >,int );struct produce*creatlist()srand(int)time(0);struct produce*first=new produce;first->next=NULL;int m=0,m1=0;/*int yanzheng20=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1;for (int i=0;i<

18、;(MAX_LENGTH/4);i+)struct produce *s0;s0=new produce;s0->num=i*4+0;s0->zhiling=yanzhengi*4+0;s0->virtualpage=s0->zhiling;insert(first,s0);struct produce *s1;s1=new produce;s1->num=i*4+1;s1->zhiling=yanzhengi*4+1;s1->virtualpage=s1->zhiling;insert(first,s1);struct produce *s2;

19、s2=new produce;s2->num=i*4+2;s2->zhiling=yanzhengi*4+2;s2->virtualpage=s2->zhiling;insert(first,s2);struct produce *s3;s3=new produce;s3->num=i*4+3;s3->zhiling=yanzhengi*4+3;s3->virtualpage=s3->zhiling;insert(first,s3);/*/*for (int i=0;i<(MAX_LENGTH/4);i+)struct produce *s

20、0;s0=new produce;m=random(MAX_LENGTH);s0->num=i*4+0;s0->zhiling=m+1;s0->virtualpage=s0->zhiling/10;insert(first,s0);m1=random(m+1);struct produce *s1;s1=new produce;s1->num=i*4+1;s1->zhiling=m1;s1->virtualpage=s1->zhiling/10;insert(first,s1);struct produce *s2;s2=new produce;

21、s2->num=i*4+2;s2->zhiling=m1+1;s2->virtualpage=s2->zhiling/10;insert(first,s2);struct produce *s3;s3=new produce;s3->num=i*4+3;s3->zhiling=random(MAX_LENGTH-m1-2)+m1+2;s3->virtualpage=s3->zhiling/10;insert(first,s3);/*/return first;void insert(struct produce *first,struct pro

22、duce *s)struct produce *r=first;struct produce *p;while(r)p=r;r=r->next;p->next=s;p=s;p->next=NULL;void print(struct produce *first) /打印函數(shù)struct produce *p;p =first->next;cout<<"隨機產(chǎn)生的指令的信息如下"<<endl;cout<<"指令序號 "<<"指令地址 "<<"

23、指令虛頁號"<<endl;while (p)cout<<p->num<<'t'<<p->zhiling<<setw(14)<<p->virtualpage<<endl;p=p->next;int max(vector<vector<int> > page,int Maxpage)int a=0,position=0;for (int i=0;i<Maxpage;i+)if (pagei1>a)a=pagei1;position

24、=i;return position;#endif先來先出調(diào)度算法：fifo.h#ifndef FIFO_H#define FIFO_Hvoid fifo(struct produce *first,int Maxpage)vector<int> page(Maxpage);/for (int i=0;i<Maxpage;i+)pagei=-1;int rear=0;/定義一個變量，指向要被替換的位置int pages;/定義變量保存當(dāng)前指令的所在的地址int count1=0;/int count2=0;/缺頁次數(shù)int find=1;struct produce *p=f

25、irst->next;while (p)pages=p->virtualpage;for(int i=0;i<Maxpage;i+)if (pagei=-1|count1<Maxpage)pagei=pages;count1 +;count2 +;find =1;break;else if (pagei=pages)find =1;break;find=0;if (find=0)pagerear=pages;rear +;rear=rear%Maxpage;count2 +;p=p->next;cout<<"FIFO調(diào)度算法缺頁次數(shù) 缺頁率

26、命中率"<<endl;cout<<count2<<setw(25)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;#endif FIFO_HLRU調(diào)度算法lru.h#ifndef LRU_H#define LRU_H#include<vector>using namespace std;/int max(vector<vector<int> >,int );void l

27、ru(struct produce*first,int Maxpage)struct produce*p=first->next;vector<vector<int> > page2(Maxpage, vector<int>(2); int count1=0; /定義內(nèi)存已經(jīng)被占用的頁數(shù)int count2=0; /定義記錄缺頁次數(shù)int equal=0; /定義判斷如果當(dāng)前頁數(shù)與比較的頁數(shù)，如果相等則為1，否則為0int place=0; /定義要替換的位置for (int i=0;i<Maxpage;i+)page2i0=-1;page2i1

28、=0;while (p)if (count1<Maxpage)for (int i=0;i<Maxpage;i+)page2i1=page2i1+1;if (page2i0=-1)page2i0=p->virtualpage;count2+;break;else if (page2i0=p->virtualpage)page2i1 =1;count1+;elsefor (int i=0;i<Maxpage;i+)page2i1 +=1;if (page2i0=p->virtualpage)equal=1;place=i;break;if (equal=1)p

29、age2place1 =1;equal=0;else place = max(page2,Maxpage);page2place1=1;page2place0=p->virtualpage;count2+;p=p->next;cout<<"LRU調(diào)度算法缺頁次數(shù) 缺頁率 命中率"<<endl;cout<<count2<<setw(24)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<

30、;endl;#endif LRU_HOPT調(diào)度算法opt.h#ifndef OPT_H#define OPT_H#include<vector>using namespace std;int search(struct produce*place,int position);void opt(struct produce*first,int Maxpage)struct produce*p =first->next;vector<vector<int> > page3(Maxpage, vector<int>(2);int count1=0

31、; /定義內(nèi)存已被使用的頁數(shù)int count2=0; /定義缺頁次數(shù)int current=0; /定義當(dāng)前工作位置int equal=0; /定義判斷如果當(dāng)前頁數(shù)與比較的頁數(shù)，如果相等則為1，否則為0int place=0; /定義要替換的位置for (int i=0;i<Maxpage;i+)page3i0=-1;page3i1=0;while (p)/cout<<1111<<endl;if (count1<Maxpage)for (int i=0;i<Maxpage;i+)if (page3i0=-1)page3i0=p->virtual

32、page;page3i1=search(p,current);count2+;break;else if (page3i0=p->virtualpage)page3i1=search(p,current);count1+;elsefor (int i=0;i<Maxpage;i+)if (page3i0=p->virtualpage)equal=1;place=i;break;if (equal=1)page3place1 =search(p,current);equal=0;elseplace = max(page3,Maxpage);page3place1=search(

33、p,current);page3place0=p->virtualpage;count2 +=1;p=p->next;current +=1;cout<<"OPT調(diào)度算法缺頁次數(shù) 缺頁率 命中率"<<endl;cout<<count2<<setw(25)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;int search(struct produce*place,int position)struct produce*p=place->next;int current=place->virtualpage;int position1=position+1;while(p)if (current=p->virtualpage)return position1;position1+;p=p->next;return position1;#endif主函數(shù) 控制臺ccglmain.cpp