操作系统试验报告

????大学??学院

操作系统实验报告

姓 名： ??? 年 级： ???

专 业： 计算机科学与技术 学 号： ?????????? 任课教师：???

开课时间：2009~2010学年第二学期

实验（一）

（多级反馈队列）

一、问题描述：（四号黑体）

基于时间片轮转并结合优先权的调度算法，这种调度策略具有较好的性能，能够满足各类用户的需要。 二、程序分析与设计：（四号黑体） 1、基本思想（四号仿宋，单倍行距）

?

将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。

?

进程并非总是固定在某一队列中，新进程进入系统后，被存放在第一个队列的末尾。如果某个进程在规定的时间片内没有完成工作，则把它转入到下一个队列的末尾，直至进入最后一个队列。系统先运行第一个队列中的进程。当第一队列为空时，才运行第二个队列中的进程。依此类推，仅当前面所有的队列都为空时，才运行最后一个队列中的进程。

2、结构定义（四号仿宋，单倍行距） typedef struct node /*进程节点信息*/ {

char name[20]; /*进程的名字*/ int prio; /*进程的优先级*/

int round; /*分配CPU的时间片*/ int cputime; /*CPU执行时间*/

int needtime; /*进程执行所需要的时间*/

char state; /*进程的状态，W--就绪态，R--执行态，F--完成态*/ int count; /*记录执行的次数*/ struct node *next; /*链表指针*/ }PCB;

typedef struct Queue /*多级就绪队列节点信息*/ {

PCB *LinkPCB; /*就绪队列中的进程队列指针*/ int prio; /*本就绪队列的优先级*/ int round; /*本就绪队列所分配的时间片*/

struct Queue *next; /*指向下一个就绪队列的链表指针*/ }ReadyQueue;

3、算法描述（四号仿宋，单倍行距） #include #include #define ReadyNum 3 #define ProNum 5

typedef struct node /*进程节点信息*/ {

char name[20]; /*进程的名字*/

int needtime; /*进程执行所需要的时间*/

char state; /*进程的状态，W——就绪态，R——执行态，F——完成态*/

int count; /*记录执行的次数*/ struct node *next; /*链表指针*/ struct node *head; struct node *rear; }PCB;

typedef struct Queue /*多级就绪队列节点信息*/ {struct Queue *head; PCB LinkPCB[100]; struct Queue *rear;

int round; /*本就绪队列所分配的时间片*/

struct Queue *next; /*指向下一个就绪队列的链表指针*/ }ReadyQueue; int Num; int m=0; int b=0;

ReadyQueue Queue[ReadyNum];

void InsertPrio(); /*创建就绪队列，规定优先数越小，优先级越低*/

void MultiDispatch(); /*多级调度算法，每次执行一个时间片

*/ int printn=0; void print(PCB p1); void creatprint(PCB p1); PCB printhead[ProNum]; using namespace std;

void InsertPrio()//设置每个队列的时间片 {int i;

for(i=0;i

cout<<\请输入第\个就绪队列的时间片：\

cin>>Queue[i].round; } }

void InsertFinish(int m)//创建第一个就绪队列 {int i=0;

PCB p1;

cout<<\请输入进程信息\ cout<<\进程名和需要的执行时间\ for(i=0;i

cin>>p1.name;

cin>>p1.needtime; Queue[0].LinkPCB[i]=p1; } }

void Insert(PCB p1)//创建第二个就绪队列 {PCB *head;

Queue[1].LinkPCB[m]=p1;m++; }

void Insert2(PCB p1)//创建第三个就绪队列 { PCB *p2;

Queue[2].LinkPCB[b]=p1;b++; }

void MultiDispatch(int q) {int i=0,j;int flag=1;

PCB p1; int u=0;int u1=0;int u2=0; p1=Queue[0].LinkPCB[i];

for(i=0;i

if(((p1.needtime-Queue[0].round)<=0)) {p1.state='F';p1.count++;print(p1);

} else

{p1.needtime=p1.needtime-Queue[0].round;Insert(p1) ; } } p1=Queue[1].LinkPCB[0]; for(i=0;i

{ p1=Queue[1].LinkPCB[u1]; u1++;

if(((p1.needtime-Queue[1].round)<=0))

{p1.state='F';p1.count=p1.count+2;print(p1); } else

{p1=Queue[1].LinkPCB[u1-1];p1.needtime=p1.needtime-Queue[1].round;Insert2(p1) ; }

} p1=Queue[2].LinkPCB[0]; for(i=0;i

{ p1=Queue[2].LinkPCB[u2]; u2++;

if(((p1.needtime-Queue[2].round)<=0))

{p1.state='F';p1.count=p1.count+3;print(p1); }

else {p1.state='w';p1.count=0;print(p1); }

} }

void print(PCB p1) {int n=0;

if(printn==0) {printhead[printn]=p1;printn++;}

else {printhead[printn]=p1;printn++;} }

void Output() { int n=0;

cout<<\进程名\ \进程状态\ \进程轮转次数\ \ while(n

cout<

\ \ n++;

} } int main()

{ printf(\固定三个就绪队列，5个进程数\\n\

int i; InsertPrio(); InsertFinish(m); MultiDispatch(m); Output();

system(\ return EXIT_SUCCESS; }三、调试与运行：

四、总结：（四号黑体）

1、本程序的优点和不足之处（四号仿宋，单倍行距）

操作简单直观明了，但没有完全模拟出算法，如果进程所需时间过大，不能显示出完成的。仍然处于等待状态。固定了就绪队列的个

数和进程的个数。只是简单的模拟了多级反馈算法思路。 2、心得体会（四号仿宋，单倍行距） 对多级反馈队列调度算法更熟悉了一些

实验（二）

（页面置换）

一、问题描述：

主要包括三种典型的置换算法：最佳适用（OPT）算法，先进先出（FIFO）算法，最久未使用（URL）算法。 二、程序分析与设计： 1、基本思想

A.最佳适用算法：所选择的淘汰页是以后永不使用或者以后最长时间不需要访问的页，是一种理想化的算法，具有最好的性能，通常可以保证最低的缺页率。实现方法：利用一个与内存块相同大小的数组记录以后的重复出现的页面位置，如未出现则为最大，然后对这个数组进行比较，选出位置最大的页予以淘汰。

B．先进先出算法：总是淘汰最先进入内存的页，也就是将内存中中驻留时间最久的页面。实现方法：在内存块数组中，按顺序存入数组，依次淘汰，即最先进来的先淘汰。

C．最久未使用算法：根据页面调入内存后的使用情况进行决策，选择最近最久未使用的页面予以淘汰。实现方法：每次将页面存入内存数组栈顶，然后下面的一次向下移，在栈底位置的页面为下一次要淘汰的页。 2、结构定义

#define N 10 //页面数

int a[N],b[32]; // a[]为要调入内存的页面，b[]为内存块数组

while(f) //对内存块数组进行初始化 { for(j=0;j

b[j]=-1; } 3、算法描述 #include #include #define N 10 using namespace std;

int a[N],b[32]; //a[]为要调入内存的页面，b[]为内存块数组

void Optimal(int m) {

cout<<\ OPT\\n\

int i=0,j=0,count=0,k; while(i

算法置换

{

for(k=0;k

if(b[k]==a[i]) {

cout<<\内存中有这个页面,直接访问.\ break; }

} // 判断内存中是否有该页面.

if(k==m)

if(b[m-1]<0) //内存未满的情况// {

b[j]=a[i];

cout<

cout<<\产生\次缺页\ j++; j=j%m; }

else

{int temp[4]; //存储内存块中的页号在下一次使用的位置

int h=j;

while(a[h]!=b[0]&&h

temp[0]=h; h=j;

while(a[h]!=b[1]&&h

temp[1]=h; h=j;

while(a[h]!=b[2]&&h

temp[2]=h; h=j;

while(a[h]!=b[3]&&h

int max_x=0;//最后定位要换出的页号所在的内存号 int max=temp[0];

for(int c=0;c<4;++c) //找出要置换的页号// if(temp[c]>max) {max=temp[c];max_x=c; } count++;

cout<

cout<<\共缺页\次 缺页率为：\}

////-------------FIFO算法置---------------//// void FIFO( int m ) {

cout<<\ FIFO\\n\

算法置换

int i=0,j=0,count=0,k;

while(i<10) {

for(k=0;k

if(b[k]==a[i]) {

cout<<\内存中有这个页面,直接访问.\ break; }

} // 判断内存中是否有该页面.

if(k==m) {

if(b[m-1]<0) {

b[j]=a[i];

cout<

cout<<\产生\次缺页\ j++; j=j%m; }

else { count++;

cout<

}cout<

cout<<\共缺页\次 缺页率为：\}

///////---------------LRU算法--------------/////////////// void LRU(int m) {

cout<<\ LRU\\n\ int k;

int i=0,j=0,count=0; while(i<10) {

for(k=0;k

if(b[k]==a[i]) {

算法置换

cout<<\内存中有这个页面,直接访问.\ break; }

} // 判断内存中是否有该页面. if(k==m) { int temp,t; temp=b[m-1];

for(t=0;t

b[0]=a[i]; count++; if(temp==-1)

cout<

cout<

cout<

cout<<\共缺页\次 缺页率为：\}

int main(int argc, char *argv[]) {

int sf,f=1,m,i,j,n;

cout<<\请输入内存容量:\ cin>>m;

cout<<\请输入页面次序:(\个页面）\ for(i=0;i

cin>>n; a[i]=n; }

//初始化b[j];使等于-1,表示开始时内存中无页面. while(f)

{ for(j=0;j

b[j]=-1; }

cout<<\请输入页面置换算法：1、最佳置换算法 2、先进先出算法 3、最近最久为未使用算法 \ cin>>sf; switch(sf)

{case 1:Optimal(m);break; case 2:FIFO(m);break; case 3:LRU(m);break;

default:cout<<\选择错误！\ }

cout<

cout<<\是否继续,按1继续，按0退出\ cin>>f; }

system(\ return EXIT_SUCCESS; }三、调试与运行：

四、总结：

1、本程序的优点和不足之处（四号仿宋，单倍行距） 操作简单明了，结果用表格形式表现将会更直观 2、心得体会（四号仿宋，单倍行距）

三种页面置换算法FIFO,LRU,OPT,容易理解,但在实际实现过程的时候要注意各种细节。对算法的时间复杂度的分析还是不熟悉

实验（三）

银行家算法

一、问题描述：

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。 二、程序分析与设计： 1、基本思想

(1),进程一开始向系统提出最大需求量.

(2),进程每次提出新的需求都统计是否超出它事先提出的最大需求量.

(3),若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待. 2、结构定义

int Max[100][100]={0};//各进程所需各类资源的最大需求 int Avaliable[100]={0};//系统可用资源 char name[100]={0};//资源的名称

int Allocation[100][100]={0};//系统已分配资源 int Need[100][100]={0};//还需要资源 int Request[100]={0};//请求资源向量 int temp[100]={0};//存放安全序列

int Work[100]={0};//存放系统可提供资源 int M=100;//作业的最大数为100 int N=100;//资源的最大数为100 3、算法描述

#include #include #include #define False 0 #define True 1

int Max[100][100]={0};//各进程所需各类资源的最大需求 int Avaliable[100]={0};//系统可用资源 char name[100]={0};//资源的名称

int Allocation[100][100]={0};//系统已分配资源 int Need[100][100]={0};//还需要资源 int Request[100]={0};//请求资源向量 int temp[100]={0};//存放安全序列 int Work[100]={0};//存放系统可提供资源 int M=100;//作业的最大数为100 int N=100;//资源的最大数为100 void showdata()//显示资源矩阵 {

int i,j;

cout<<\系统目前可用的资源[Avaliable]:\ for(i=0;i

cout<

cout<<\ cout<<\进程名 \ for(j=0;j<3;j++) {

for(i=0;i

cout<

cout<<\ for(j=0;j

输出分配资源

cout<

cout<

cout<

int changdata(int i)//进行资源分配 { int j;

for (j=0;j

Avaliable[j]=Avaliable[j]-Request[j]; Allocation[i][j]=Allocation[i][j]+Request[j]; Need[i][j]=Need[i][j]-Request[j]; } return 1; }

int safe()//安全性算法

{

int i,k=0,m,apply,Finish[100]={0}; int j; int flag=0; for(i=0;i

for(j=0;j

if (Finish[i]==False&&Need[i][j]<=Work[j]) { apply++; if(apply==N) {

for(m=0;m

Work[m]=Work[m]+Allocation[i][m];//变分配数 Finish[i]=True; temp[k]=i; i=-1; k++; flag++; }

} } }

for(i=0;i

cout<<\系统不安全\不成功系统不安全 return -1; } }

cout<<\系统是安全的!\如果安全，输出成功 cout<<\分配的序列:\

for(i=0;i

cout<

void share()//利用银行家算法对申请资源对进行判定 { char ch; int i=0,j=0;

ch='y';

cout<<\请输入要求分配的资源进程号(0-\ cin>>i;//输入须申请的资源号

cout<<\请输入进程 \申请的资源:\for(j=0;j

cout<

cin>>Request[j];//输入需要申请的资源 }

for (j=0;j

if(Request[j]>Need[i][j])//判断申请是否大于需求，若大于则出错 {

cout<<\进程 \申请的资源大于它需要的资源\ cout<<\分配不合理，不予分配！\ ch='n'; break; }

else {

if(Request[j]>Avaliable[j])//判断申请是否大于当前资源，若大于则

{ //出错

cout<<\进程\申请的资源大于系统现在可利用的资源\ cout<<\分配出错，不予分配!\ ch='n'; break; } } }

if(ch=='y') {

changdata(i);//根据进程需求量变换资源 showdata();//根据进程需求量显示变换后的资源 safe();//根据进程需求量进行银行家算法判断 } }

void addresources(){//添加资源 int n,flag;

cout<<\请输入需要添加资源种类的数量:\cin>>n; flag=N; N=N+n;

for(int i=0;i>name[flag];

cout<<\数量:\

cin>>Avaliable[flag++]; }

showdata(); safe(); }

void delresources(){//删除资源 char ming; int i,flag=1;

cout<<\请输入需要删除的资源名称：\do{

cin>>ming; for(i=0;i

cout<<\该资源名称不存在，请重新输入：}

while(flag);

for(int j=i;j

\

{

name[j]=name[j+1];

Avaliable[j]=Avaliable[j+1]; } N=N-1; showdata(); safe(); }

void changeresources(){//修改资源函数

cout<<\系统目前可用的资源[Avaliable]:\ for(int i=0;i

cout<>Avaliable[0]>>Avaliable[1]>>Avaliable[2]; cout<<\经修改后的系统可用资源为\for (int k=0;k

cout<

void addprocess(){//添加作业

int flag=M; M=M+1;

cout<<\输入该作业的最大需求量[Max]\for(int i=0;i>Max[flag][i];

Need[flag][i]=Max[flag][i]-Allocation[flag][i]; }

showdata(); safe(); }

int main()//主函数 {

int i,j,number,choice,m,n,flag; char ming;

cout<<\输入系统可供资源种类的数量:\cin>>n; N=n;

for(i=0;i

cout<<\资源\的名称:\

cin>>ming; name[i]=ming; cout<<\资源的数量:\ cin>>number; Avaliable[i]=number; }

cout<

cout<<\请输入作业的数量:\cin>>m; M=m;

cout<<\请输入各进程的最大需求量(\矩阵)[Max]:\for(i=0;i>Max[i][j]; do{ flag=0;

cout<<\请输入各进程已经申请的资源量(\矩阵)[Allocation]:\ for(i=0;i

cin>>Allocation[i][j];

if(Allocation[i][j]>Max[i][j]) flag=1;

Need[i][j]=Max[i][j]-Allocation[i][j]; } if(flag)

cout<<\申请的资源大于最大需求量，请重新输入!\\n\}while(flag);

showdata();//显示各种资源

safe();//用银行家算法判定系统是否安全 while(choice) {

cout<<\银行家算法演示 \ cout<<\增加资源 \ cout<<\删除资源 \ cout<<\修改资源 \ cout<<\分配资源 \ cout<<\增加作业 \ cout<<\离开 \ cout<<\选择操作序号：\ cin>>choice;

switch(choice) {

case 1: addresources();break; case 2: delresources();break; case 3: changeresources();break; case 4: share();break; case 5: addprocess();break; case 0: choice=0;break;

default: cout<<\请正确选择操作序号(0-5)!\ } }

return 1; }}三、调试与运行：

四、总结：

1、本程序的优点和不足之处（四号仿宋，单倍行距）

输入提示信息太啰嗦

银行家算法从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。在实际情况中只有极少的系统使用银行家算法来避免死锁。 2、心得体会（四号仿宋，单倍行距）

通过实验认识到,实践的必要性,有许多地方没有考虑到,还有些地方写的不够好,程序还需要改进。

实验（四）

动态分配

一、问题描述：

根据进程的实际需要，动态地为之分配内存空间，在实现可变分区分配时，涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收。

二、程序分析与设计： 1、基本思想

A．首次适用算法：空闲分区链以地址递增的次序连接，而在分配时从链首开始按顺序查找，直到找到一个大小能满足要求的空闲分区。

B.最佳适用算法：所有空闲分区按其容量从小到大的顺序形成一空闲分区链。 2、结构定义 struct code {

int value; int xx; int fi; }co[20];

3、算法描述（四号仿宋，单倍行距）

#include #include struct code {

int value; int xx; int fi; }co[20];

using namespace std; void alloc(int ch); void opt(int x,int id); void first(int x,int id); void free(int id); void show(); int ch;

void show() {

int i,j;

printf(\初始容量\\t剩余容量\\t状态\\n\ if(ch==2)

for(i=0;i<10;i++)

printf(\ else if(ch==1) for(i=10;i<20;i++)

printf(\); }

void free(int id) {

int i,j;

if(ch==2)

{ for(i=0;i<10;i++) if(co[i].xx==id) {co[i].xx=co[i].value; co[i].fi=0;

printf(\内存释放完毕\\n\ break;} if(i>=10)

本文来源：https://www.bwwdw.com/article/u8d.html