淮 阴 工 学 院
实 验 报 告
__2012 _-__2013__学年 第__1__学期
学 院___计算机工程学院__
课程名称_____操作系统 __
班 级_____软件1101_____
学 号____1101305114_____
姓 名_______王 祥______
指导教师_______严云洋______
实验一：进程调度
1. 实验目的：
通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。
2. 实验内容：
设计程序模拟进程的轮转法调度过程。假设初始状态为：有n个进程处于就绪状态，有m个进程处于阻塞状态。采用轮转法进程调度算法进行调度(调度过程中，假设处于执行状态的进程不会阻塞)，且每过t个时间片系统释放资源，唤醒处于阻塞队列队首的进程。
程序要求如下：
1）.输出系统中进程的调度次序；
2）.计算CPU利用率。
3. 实验环境：
硬件环境：Ghost XP SP3 纯净版 Y6.0 Pentium(R) Dual-Core CPU E6700 @ 3.20GHz 3.19 GHz, 1.96 GB 的内存物理地址扩展
软件环境：Microsoft Windows XP , Visual Studio 2008
4. 源代码：
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
onst int MaxNum = 100;
struct Node{
int index;
int arriveTime;
int rest;
};
bool NodeCmp(const Node& a,const Node& b)
{
return a.arriveTime < b.arriveTime;
}
int n; //进程数
int ArrivalTime[MaxNum];
int ServiceTime[MaxNum];
int PServiceTime[MaxNum];
int FinishTime[MaxNum];
int WholeTime[MaxNum];
double WeightWholeTime[MaxNum];
bool Finished[MaxNum];
double AverageWT,AverageWWT;
bool isEnterQue[MaxNum];
int cntTimes[MaxNum];
void init()
{
memset(PServiceTime,0,sizeof(PServiceTime));
memset(Finished,0,sizeof(Finished));
memset(FinishTime,0,sizeof(FinishTime));
memset(WholeTime,0,sizeof(WholeTime));
memset(WeightWholeTime,0,sizeof(WeightWholeTime));
}
int sum(int array[],int n)
{
int sum=0;
int i;
for(i=0;i<n;i++)
{
sum += array[i];
}
return sum;
}
double sum(double array[],int n)
{
double sum=0;
int i;
for(i=0;i<n;i++)
{
sum += array[i];
}
return sum;
}
void print()
{
int i=0;
cout<<"进程完成时间:";
for(i=0;i<n;i++)
{
cout<<FinishTime[i]<<' ';
}
cout<<endl;
cout<<"周转时间:";
for(i=0;i<n;i++)
{
cout<<WholeTime[i]<<' ';
}
cout<<endl;
cout<<"带权周转时间:";
for(i=0;i<n;i++)
{
printf("%.2f ",WeightWholeTime[i]);
}
cout<<endl;
}
void SearchToEnterQue(queue<Node>& que,Node* pArr,int maxArrivalTime)
{
int i;
for(i=0;i<n;i++)
{
if(pArr[i].arriveTime>maxArrivalTime)
break;
if(isEnterQue[pArr[i].index]==false)
{
que.push(pArr[i]);
isEnterQue[pArr[i].index] = true;
}
}
}
void Work(int q)
{
init();
memset(isEnterQue,0,sizeof(isEnterQue));
memset(cntTimes,0,sizeof(cntTimes));
Node* pNodeArr = new Node[n];
int i;
for(i=0;i<n;i++)
{
pNodeArr[i].index = i;
pNodeArr[i].arriveTime = ArrivalTime[i];
pNodeArr[i].rest = ServiceTime[i];
}
sort(pNodeArr,pNodeArr+n,NodeCmp);
int totalTime = sum(ServiceTime,n);
int time=pNodeArr[0].arriveTime;
queue<Node> que;
que.push(pNodeArr[0]);
isEnterQue[pNodeArr[0].index]=true;
Node cur;
cout<<"================================================="<<endl;
while(!que.empty()) {
cur = que.front();
que.pop();
cntTimes[cur.index]++;
if(cntTimes[cur.index]==1)
printf("在%d时刻，进程%d开始执行。。。\n",time,cur.index);
if(cur.rest > q)
{
time += q;
cur.rest -= q;
}
else
{
time += cur.rest;
Finished[cur.index]=true;
FinishTime[cur.index] = time;
cur.rest = 0;
printf("在%d时刻，进程%d执行结束。\n",time,cur.index);
}
SearchToEnterQue(que,pNodeArr,time);
if(cur.rest!=0)
que.push(cur);
if(que.empty())//若队列为空，则在time之后才达到的进程找最早到达的进程入队列
{
for(i=0;i<n;i++)
{
if(isEnterQue[i]==false)//找到了
{
que.push(pNodeArr[i]);//入队列
time = pNodeArr[i].arriveTime;
break;
}
}
}
}
for(i=0;i<n;i++)
{
WholeTime[i] = FinishTime[i] - ArrivalTime[i];
WeightWholeTime[i] = (double)WholeTime[i] / (double)ServiceTime[i];
}
AverageWT = (double)sum(WholeTime,n)/(double)n;
AverageWWT=(double)sum(WeightWholeTime,n)/(double)n; cout<<"================================================="<<endl;
print();
cout<<endl<<endl; cout<<"================================================="<<endl;
printf("平均周转时间:%.2f,平均带权周转时间:%.2f\n",AverageWT,AverageWWT);
delete[] pNodeArr;
}
int main()
{
// freopen("test.txt","rw",stdin);
int q;//时间片大小
int i;
cout<<"输入进程数:";
cin>>n;;
cout<<"输入每个进程的到达时间:"<<endl;
for(i=0;i<n;i++)
cin>>ArrivalTime[i];
cout<<"输入每个进程的服务时间:"<<endl;
for(i=0;i<n;i++)
cin>>ServiceTime[i];
cout<<"输入时间片大小"<<endl;
cin>>q;
Work(q);
return 0;
}
5. 实验结果：
6. 试验分析和体会：
实验二 分区式存储管理
1. 实验目的：
通过这次实验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想。
2. 实验内容：
设计程序模拟内存的动态分区法存储管理。内存空闲区使用自由链管理，采用最坏适应算法从自由链中寻找空闲区进行分配，内存回收时假定不做与相邻空闲区的合并。
假定系统的内存共640K，初始状态为操作系统本身占用64K。在t1时间之后，有作业A、B、C、D分别请求8K、16K、64K、124K的内存空间；在t2时间之后，作业C完成；在t3时间之后，作业E请求50K的内存空间；在t4时间之后，作业D完成。要求编程序分别输出t1、t2、t3、t4时刻内存的空闲区的状态。
3. 实验环境：
硬件环境：Ghost XP SP3 纯净版 Y6.0 Pentium(R) Dual-Core CPU E6700 @ 3.20GHz 3.19 GHz, 1.96 GB 的内存物理地址扩展
软件环境：Microsoft Windows XP , Visual Studio 2008
4. 源代码：
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
struct freelink
{
int len, address; // len为分区长度；address为分区起始地址
struct freelink * next;
};//内存占用区用链表描述，其结点类型描述如下：
struct busylink
{
char name; // 作业或进程名 name='S' 表示OS占用
int len , address;
struct busylink *next;
} ;
//并设全程量：
struct freelink *free_head=NULL; // 自由链队列带头结点）队首指针?
struct busylink *busy_head=NULL, *busy_tail=NULL; // 占用区队列队（带头结点）首指针
// 占用区队列队尾指针
// 设计子函数：
void start(void) /* 设置系统初始状态*/
{
struct freelink * p;
struct busylink *q;
free_head=(struct freelink*)malloc(sizeof(struct freelink));
free_head->next=NULL; // 创建自由链头结点
busy_head=busy_tail=(struct busylink*)malloc(sizeof(struct busylink));
busy_head->next=NULL; // 创建占用链头结点
p=( struct freelink *)malloc(sizeof(struct freelink));
p->address=64;
p->len=640-64; //（OS占用了K）
p->next=NULL;
free_head->next=p;
q=( struct busylink *)malloc(sizeof(struct busylink));
q->name='S'; /* S表示操作系统占用 */
q->len=64; q->address=0; q->next=NULL;
busy_head->next=q; busy_tail=q;
}
void requireMemo(char name, int require) /*模拟内存分配*/
{
struct freelink *w,*u,*v,*x,*y;
struct busylink *p;
x=free_head;
y=free_head->next;
while((y!=NULL) &&(y->len<require)) //找到第一个满足条件的空闲区
{
x=y;
y=y->next;
}
if(y!=NULL)
{
p=(struct busylink*)malloc(sizeof(busylink));
p->name=name;
p->address=y->address;
p->len=require;
p->next=NULL;
busy_tail->next=p; //把p插入到busy_head的尾部
busy_tail=p;
w=x->next;
x->next=w->next;
if(w->len==require)
{
free(w);
}
else
{
w->address=w->address+require;
w->len=w->len-require;
u=free_head;
v=free_head->next;
while((v!=NULL) && (v->len<w->len))//如果此结点还有多余，就此又重新插入到空闲区域链中（按照长度由小到大的次序排列）
{
u=v;
v=v->next;
}
u->next=w;
w->next=v;
}
}
else
printf("can't allocate!\n");
}
void freeMemo(char name) /* 模拟内存回收*/
{
struct busylink *p,*q;
struct freelink *w,*u,*v,*s1=NULL,*s2=NULL;
int len,address;
int flag1=1,flag2=1;
p=busy_head->next;
while((p!=NULL)&&(p->name!=name)) //找到要回收的结点
{
q=p;
p=p->next;
}
if(p==NULL)
{
printf("%c is not exist\n",name);
}
else
{
if (p==busy_tail)
busy_tail=q;
q->next=p->next;
len=p->len;
address=p->address;
free(p);
w=(struct freelink*) malloc(sizeof(freelink));
w->len=len;
w->address=address;
u=free_head;
v=free_head->next;
while((v!=NULL) && (flag1==1 || flag2==1)) //归并算法
{
if((w->address==(v->address+v->len)) &&flag1)
{
s1=v;
u->next=s1->next;
w->address=v->address;
w->len+=v->len;
v=v->next;
flag1=0;
}
else if(((w->address+w->len)==v->address) &&flag2)
{
s2=v;
u->next=s2->next;
w->len+=v->len;
v=v->next;
flag2=0;
}
else
{
u=v;
v=v->next;
}
}
if(s1!=NULL)
free(s1);
if(s2!=NULL)
free(s2);
u=free_head;
v=free_head->next;
if(v!=NULL)
{
while((v!=NULL) && (v->len<w->len))
{
u=v;
v=v->next;
}
}
u->next=w;
w->next=v;
}
}
void past(int time) /* 模拟系统过了时间time，用sleep(),或者用个空循环*/
{
printf("时间%d后：\n",time);
}
void printlink() /* 输出内存空闲情况（自由链的结点）*/
{
struct freelink *p;
p=free_head->next;
if(p==NULL)
printf("无空闲区！\n");
else
{
while(p!=NULL)
{
printf("首地址:%d\t长度:%d\n",p->address,p->len);
p=p->next;
}
}
printf("----------------------------------------\n");
}
void printlink1() /* 输出内存占用的情况*/
{
struct busylink *p;
p=busy_head->next;
if(p==NULL)
printf("无内存占有区！\n");
else
{
while(p!=NULL)
{
printf("名字:%c\t首地址:%d\t长度:%d\n",p->name,p->address,p->len);
p=p->next;
}
}
}
// 设计主函数：
int main()
{
start();
past(1);
requireMemo('A',8); requireMemo('B',16);
requireMemo('C',64); requireMemo('D',124);
printf("内存占用区为：\n");
printlink1();
printf("内存空闲区为:\n");
printlink();
past(2);
freeMemo('C');
printf("内存占用区为：\n");
printlink1();
printf("内存空闲区为:\n");
printlink();
past(3);
requireMemo('E',50);
printf("内存占用区为：\n");
printlink1();
printf("内存空闲区为:\n");
printlink();
return 0;
}
5. 实验结果：
6. 试验分析和体会：
首先，对链表又有进一步的理解，还有就是加深理解内存的分配与回收，分配与回收的策略，并掌握动态分区这种内存管理的具体实施方法。
再者，就是在编程中遇到的困难，在编写归并程序首先是自己考虑问题不全面，写的程序就只顾及到一个结点，而没有实现有两个结点的情况，于是后来再加了一条else语句，就没有出现问题。还有一个问题就是将多余的结点free时也出现问题，加了一条if(s==NULL）,成立就释放掉。一开始把free语句写在while循环内，一旦把找到的结点释放掉，则找不到下一个结点，也会出错，所以应该把free放到while循环外。
实验三 虚拟存储管理
1. 实验目的：
存储管理的主要功能之一是合理的分配空间。请求页式管理是一种常用的虚拟存储管
理技术。
本实验的目的是请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换方法。
2. 实验内容：
（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：
①、 50%的指令是顺序执行的；
②、 25%的指令是均匀分布在前地址部分；
③、 25%的指令是均匀分布在后地址部分。
具体的实施方法是：
① 在[0,319]的指令地址之间随机选取一起点m;
② 顺序 执行一条指令，即执行地址为m+1的指令；
③ 在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’；
④ 顺序执行一条指令，其地址为m’+1;
⑤ 在后地址[m’+2,319]中随机选取一条指令并执行；
⑥ 重复上述步骤，直至执行320次指令。
（2） 将指令序列变换成页地址流
设：①页面大小为1K；
②用户内存容量为4页到32页；
③用户虚存容量为32K；
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条~第9条指令为第0页（对应的虚存地址为[0，9]）；
第10条~第19条指令为第1页（对应的虚存地址为[10，19]）；
.
第310条~第319条指令为第31页（对应的虚存地址为[310，319]）；
按以上方式，用户指令可组成32页。
（3） 计算并输出下述各种算法在不同的内存容量下的命中率。
① 先进先出的算法（FIFO）；
② 最近最少使用算法（LRR）；
③ 最佳淘汰法（OPT）：先淘汰最不常用的页地址；
④ 最少访问页面算法（LFR）；
⑤ 最近不经常使用算法（NUR）。
其中③和④为选择内容。
命中率=1-（页面失效次数）/（页地址流长度）
在本实验中，页地址流的长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。
2、 随机数产生办法
关于随机书产生办法，可以使用系统提供函数rand()，分别进行初始化和产生随机数。例如：srand();语句可初始化的一个随机数；a[0]=10*rand()/32767*319+1;
a[1]=10*rand()/32767*a[0];
语句可用来产生a[0]与a[1]中的随机数。
3. 实验环境：
硬件环境：Ghost XP SP3 纯净版 Y6.0 Pentium(R) Dual-Core CPU E6700 @ 3.20GHz 3.19 GHz, 1.96 GB 的内存物理地址扩展
软件环境：Microsoft Windows XP , Visual Studio 2008
4. 源代码：
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NULL 0
#define total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清周期*/
typedef struct /*页面结构*/
{
int pn,pfn,counter,time;
}pl_type;
pl_type pl[total_vp]; /*页面结构数组*/
struct pfc_struct{ /*页面控制结构*/
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
int diseffect, a[total_instruction];
int page[total_instruction], offset[total_instruction];
int initialize(int);
int FIFO(int); /*先进先出法（Fisrt In First Out）*/
int LRU(int); /*最近最久未使用（Least Recently Used）*/
int LFU(int); /*最不经常使用法（Least Frequently Used）*/
int NUR(int); /*最近未使用法（No Used Recently）*/
int OPT(int); /*最佳置换算法（Optimal）*/
/*主函数*/
int main( )
{
int s,i,j;
srand(10*getpid()); /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/
s=(float)319*rand( )/32767/32767/2+1; //
for(i=0;i<total_instruction;i+=4) /*产生指令队列*/
{
if(s<0||s>319)
{
printf("When i==%d,Error,s==%d\n",i,s);
exit(0);
}
a[i]=s; /*任选一指令访问点m*/
a[i+1]=a[i]+1; /*顺序执行一条指令*/
a[i+2]=(float)a[i]*rand( )/32767/32767/2; /*执行前地址指令m' */
a[i+3]=a[i+2]+1; /*顺序执行一条指令*/
s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2;
if((a[i+2]>318)||(s>319))
printf("a[%d+2],a number which is :%d and s==%d\n",i,a[i+2],s);
}
for (i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i<=32;i++) /*用户内存工作区从个页面到个页面*/
{
printf("---%2d page frames---\n",i);
FIFO(i);
LRU(i);
LFU(i);
NUR(i);
OPT(i);
}
return 0;
}
int initialize(total_pf) /*初始化相关数据结构*/
int total_pf; /*用户进程的内存页面数*/
{int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl[i].pn=i;
pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/
pl[i].counter=0;
pl[i].time=-1; /*页面控制结构中的访问次数为，时间为-1*/
}
for(i=0;i<total_pf-1;i++)
{
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
} /*建立pfc[i-1]和pfc[i]之间的链接*/
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*空页面队列的头指针为pfc[0]*/
return 0;
}
int FIFO(total_pf) /*先进先出算法*/
int total_pf; /*用户进程的内存页面数*/
{
int i,j;
pfc_type *p;
initialize(total_pf); /*初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect+=1; /*失效次数*/
if(freepf_head==NULL) /*无空闲页面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID;
freepf_head=busypf_head; /*释放忙页面队列的第一个页面*/
freepf_head->next=NULL;
busypf_head=p;
}
p=freepf_head->next; /*按FIFO方式调新页面入内存页面*/
freepf_head->next=NULL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if(busypf_tail==NULL)
busypf_head=busypf_tail=freepf_head;
else
{
busypf_tail->next=freepf_head; /*free页面减少一个*/
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf("FIFO:%6.4f\n",1-(float)diseffect/320);
return 0;
}
5. 实验结果：
6. 试验分析和体会：