广工操作系统实验报告.doc

操作系统实验报告

学生学院____ 计算机学院______
专业班级_ 计科（8）班
学 号
学生姓名____ _______
指导教师_____ ____

2013年 12月 29 日

目录
1 实验一 进程调度………………………………………………………………5
2 实验二 作业调度………………………………………………………………9
3 实验三 可变式分区分配………………………………………………………18
4 实验四 简单文件系统…………………………………………………………26

实验一 进程调度
一、实验目的
编写并调试一个模拟的进程调度程序，采用“短进程优先”调度算法对五个进程进行调度。以加深对进程的概念及进程调度算法的理解．
二、实验内容及要求
编写并调试一个模拟的进程调度程序，采用“短进程优先”调度算法对五个进程进行调度。
三、实验设计方案及原理
在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对调度的处理又都可采用不同的调度方式和调度算法。调度算法是指：根据系统的资源分配策略所规定的资源分配算法。
短进程优先调度算法是指对短进程优先调度的算法，它是从后备队列中选择一个或者若干个进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

四、重要数据结构或源程序中疑难部分的说明，需附详细注释

#include "stdio.h"
#include
#include
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL0
struct pcb
{ /* 定义进程控制块PCB */
char name[10]; //进程名
char state; //状态
int super; //优先数
int ntime; //需要运行时间
int rtime; //运行时间
struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB;
int num;
sort() /* 建立对进程进行短进程优先排列函数*/
{
PCB *first, *second;
int insert=0;
if((ready==NULL)||((p->ntime)<(ready->ntime))) /*需要运行时间最小者,插入队首*/
{
p->link=ready;
ready=p;
}
else /* 进程比较需要运行时间,插入适当的位置中*/
{
first=ready;
second=first->link;
while(second!=NULL)
{
if((p->ntime)<(second->ntime)) /*若插入进程比当前进程需要运行时间小,*/
{ /*插入到当前进程前面*/
p->link=second;
first->link=p;
second=NULL;
insert=1;
}
else /* 插入进程需要运行时间最大,则插入到队尾*/
{
first=first->link;
second=second->link;
}
}
if(insert==0) first->link=p;
}
}

void input() /* 建立进程控制块函数*/
{
int i;
//clrscr(); /*清屏*/
printf("\n 请输入进程数:");
scanf("%d",&num);
for(i=0;iname);
printf("\n 输入进程需要运行时间:");
scanf("%d",&p->ntime);
printf("\n");
p->rtime=0;p->state='w';
p->link=NULL;
sort(); /* 调用sort函数*/
}

}

void main() /*主函数*/
{
int i,len,h=0;
char ch;
input();
ch=getchar();
printf("\n调度序列为:");
p=ready;
for(i=num;i>0;i--)
{ printf(" %s",p->name);
p=p->link;
}
printf("\n\n 进程已经完成.\n");
ch=getchar();
}

五、程序运行结果

七、结果分析与实验小结
结果正确。
短进程优先需要把进程按左右运行时间排序，然后让其按顺序执行即可。

实验二 作业调度
一、 实验目的：用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。
二、 实验内容：
1． 写并调试一个单道处理系统的作业等待模拟程序。
2． 作业等待算法：分别采用先来先服务（FCFS）、响应比高者优先（HRN）的调度算法。
3． 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。
4． 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。
5． 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。
5、重要数据结构或源程序中疑难部分的说明，需附详细注释

三、实验设计方案及原理
编写一个程序将输入的进程按其提交时间进行排列，按排列顺序进行调度，计算其开始时间、完成时间、周转时间等数值
四、重要数据结构或源程序中疑难部分的说明，需附详细注释
先来先服务
#include "stdio.h"
#include
#include
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL0
struct pcb
{ /* 定义进程控制块PCB */
char name[10]; //进程名
char state; //状态
int super; //优先数
int ntime; //需要运行时间
int rtime; //运行时间
int ctime; //提交时间
int stime; //开始时间
int ftime; //完成时间
int ttime; //周转时间
float dtime; //带权周转时间
struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB;
int num;
void sort() /* 建立对进程先来先服务排列函数*/
{
PCB *first, *second;
int insert=0;
if((ready==NULL)||((p->ctime)<(ready->ctime))) /*达到时间最小者,插入队首*/
{
p->link=ready;
ready=p;
}
else /* 进程比较到达时间,插入适当的位置中*/
{
first=ready;
second=first->link;
while(second!=NULL)
{
if((p->ctime)<(second->ctime)) /*若插入进程比当前进程到达时间小,*/
{ /*插入到当前进程前面*/
p->link=second;
first->link=p;
second=NULL;
insert=1;
}
else /* 插入进程到达时间最大,则插入到队尾*/
{
first=first->link;
second=second->link;
}
}
if(insert==0) first->link=p;
}
}

void input() /* 建立进程控制块函数*/
{
int i;
//clrscr(); /*清屏*/
printf("\n 请输入进程数:");
scanf("%d",&num);
for(i=0;iname);
printf("\n 输入提交时间:");
scanf("%d",&p->ctime)
printf("\n 输入进程需要运行时间:");
scanf("%d",&p->ntime);
printf("\n");
p->rtime=0;p->state='w';
p->link=NULL;
sort(); /* 调用sort函数*/
}
}
void main() /*主函数*/
{ PCB *first,*second;
int i,x,y;
float s1=0,s2=0;
char ch;
input();
ch=getchar();
//输出
printf("进程名\t 开始时间\t 完成时间\t 周转时间\t 带权周转时间\n");
second=ready;
first=ready;
first->ftime=0;
for(i=num;i>0;i--)
{ if(second->ctime>first->ftime) /*计算完成时间，周转时间等*/
second->stime=second->ctime;
else
second->stime=first->ftime;
second->ftime=(second->ntime)+(second->stime);
second->ttime=(second->ftime)-(second->ctime);
x=second->ttime;
y=second->ntime;
second->dtime=(float)x/(float)y;
printf(" %s \t %d \t %d \t %d \t %f \n",second->name,second->stime,second->ftime,second->ttime,second->dtime);
s1=s1+second>ttime;
s2=s2+second->dtime;
if(second->link!=NULL)
{ first=second;
second=second->link;
}
}
s1=s1/num;
s2=s2/num;
printf("\n平均周转时间=%f\n",s1);
printf("平均周转时间=%f\n\n",s2);
printf("按任意键结束……");
ch=getchar();
}
响应比
#include
#include
#include
#define getpch(type) (type*)malloc(sizeof(type))
#define null 0
int n;
float T1=0,T2=0;
int times=0;
struct jcb //作业控制块
{
char name[10]; //作业名
int ctime; //作业到达时间
int stime; //作业开始时间
int ntime; //作业需要运行的时间
float super; //作业的响应比
int ftime; //作业完成时间
float ttime; //作业周转时间
float dtime; //作业带权周转时间
char state; //作业状态
struct jcb *next; //结构体指针
}*ready=NULL,*p,*q;
typedef struct jcb JCB;

void inital() //建立作业控制块队列,先将其排成先来先服务的模式队列
{
int i;
printf("\n输入作业数:");
scanf("%d",&n);
for(i=0;iname);
printf("\n输入作业到达时间:");
scanf("%d",&p->ctime);
printf("\n输入作业需要运行的时间:");
scanf("%d",&p->ntime);
p->state='W';
p->next=NULL;
if(ready==NULL) ready=q=p;
else{
q->next=p;
q=p;
}
}
}

void output(JCB* q)
{ /*显示所有作业的情况*/
JCB *pr=ready;float f=0.0;
printf("所有作业的情况：\n");//列表显示所有作业的情况
printf("作业名\t\t到达时间\t所需运行间\t响应比\t\t作业状态\n"); printf("%s\t\t%d\t\t%d\t\t%f\t%c\n", q->name,q->ctime,q->ntime,q->super,q->state);
while(pr)
{
if(pr->super<=0) printf("%s\t\t%d\t\t%d\t\t%f\t%c\n", pr->name,pr->ctime,pr->ntime,f,pr->state);
else printf("%s\t\t%d\t\t%d\t\t%f\t%c\n", pr->name,pr->ctime,pr->ntime,pr->super,pr->state);
pr = pr->next;
}
}

void disp(JCB* q) //显示作业运行后的周转时间及带权周转时间等
{
//显示高响应比算法调度作业后的运行情况
output(q);
printf("\n作业%s正在运行，估计其运行情况：\n",q->name);
printf("开始运行时刻\t完成时刻\t周转时间\t带权周转时间\t相应比\n\n"); printf("%d\t\t%d\t\t%f\t%f\t%f\n",q->stime,q->ftime,q->ttime,q>dtime,q->super);
getchar();

}

void running(JCB *p) //运行作业
{
if(p==ready) //先将要运行的作业从队列中分离出来
{
ready=p->next;
p->next=NULL;
}
else
{
q=ready;
while(q->next!=p) q=q->next;
q->next=p->next;
}
p->stime=times; //计算作业运行后的完成时间,周转时间等等
p->state='R'; p->ftime=p->stime+p->ntime; p->ttime=(float)(p->ftime-p->ctime); p->dtime=(float)(p->ttime/p->ntime);
T1+=p->ttime;
T2+=p->dtime;
disp(p); //调用disp()函数,显示作业运行情况
times+=p->ntime;
p->state='F';
printf("\n作业%s已经完成!\n请输入任意键继续......\n",p->name);
free(p); //释放运行后的作业
getchar();
}

void super() //计算队列中作业的高响应比
{
JCB *padv;
padv=ready;
do{ if(padv->state=='W'&&(padv->ctime)<=times)
{ padv->super=(float)(times-padv->ctime+padv->ntime)/padv->ntime;
}
padv=padv->next;
}while(padv!=NULL);
}

void final() //最后打印作业的平均周转时间,平均带权周转时间
{
float s,t;
t=T1/n;
s=T2/n;
getchar();
printf("\n\n作业已经全部完成!");
printf("\n%d个作业的平均周转时间是：%f",n,t);
printf("\n%d个作业的平均带权周转时间是%f：\n\n\n",n,s);
}

void hrn() //高响应比算法
{
JCB *min;
int i,iden;
system("cls");
inital();
for(i=0;iden=1;
super(); do{ if(p->state=='W'&&p->ctime<=times)
if(iden)
{
min=p;iden=0;
}
else if(p->super>min->super) min=p;
p=p->next;
}while(p!=NULL);
running(min) //调用running()函数
}
final(); //调用running()函数
}

void main() //主函数
{
hrn();
getchar();
printf("按回车结束\n");
getchar();
// system("cls");
}

五、程序运行结果

七、结果分析与实验小结

实验三 动态分区分配方式的模拟
一、实验目的：了解动态分区分配方式中的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解
二、实验内容：
（1）用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程和回收过程。其中，空闲分区通过空闲分区链（表）来管理；在进行内存分配时，系统优先使用空闲区低端的空间。
（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
•作业1申请130KB
•作业2申请60KB
•作业3申请100KB
•作业2释放60KB
•作业4申请200KB
•作业3释放100KB
•作业1释放130KB
•作业5申请140KB
•作业6申请60KB
•作业7申请50KB
•作业8申请60KB
请分别采用首次适应算法和最佳适应算法进行内存的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。

三、实验设计方案及原理
首次适应算法:使用该算法进行内存分配时，从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。
最佳适应算法:该算法总是把既能满足要求，又是最小的空闲分区分配给作业。为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算法似乎是最优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。

五、重要数据结构或源程序中疑难部分的说明，需附详细注释
#include "stdio.h"
#include
#include

#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1 //完成
#define ERROR 0 //出错
#define MAX_length 640 //最大内存空间为KB
typedef int Status;

typedef struct freearea//定义一个空闲区说明表结构
{
int ID; //分区号
long size; //分区大小
long address; //分区地址
int state; //状态
}ElemType;

//---------- 线性表的双向链表存储结构 ------------
typedef struct DuLNode //double linked list
{
ElemType data;
struct DuLNode *prior; //前趋指针
struct DuLNode *next; //后继指针
}DuLNode,*DuLinkList;

DuLinkList block_first; //头结点
DuLinkList block_last; //尾结点

Status alloc(int);//内存分配
Status free(int); //内存回收
Status First_fit(int,int);//首次适应算法
Status Best_fit(int,int); //最佳适应算法
void show();//查看分配
Status Initblock();//开创空间表

Status Initblock()//开创带头结点的内存空间链表
{
block_first=(DuLinkList)malloc(sizeof(DuLNode));
block_last=(DuLinkList)malloc(sizeof(DuLNode));
block_first->prior=NULL;
block_first->next=block_last;
block_last->prior=block_first;
block_last->next=NULL;
block_last->data.address=0;
block_last->data.size=MAX_length;
block_last->data.ID=0;
block_last->data.state=Free;
return OK;
}

//----------------------- 分配主存-------------------------
Status alloc(char ch)
{
int ID=0,request=0;
printf("请输入作业(分区号)：");
scanf_s("%d",&ID);
printf("请输入需要分配的主存大小(单位:KB)：");
scanf_s("%d",&request);
if(request<0 ||request==0)
{
printf("分配大小不合适，请重试！\n");
return ERROR;
}

if(ch==2) //选择最佳适应算法
{
if(Best_fit(ID,request)==OK) printf("分配成功！\n");
else printf("内存不足，分配失败！\n");
return OK;
}
else //默认首次适应算法
{
if(First_fit(ID,request)==OK) printf("分配成功！\n");
else printf("内存不足，分配失败！\n");
return OK;
}
}
//------------------ 首次适应算法-----------------------
Status First_fit(int ID,int request)//传入作业名及申请量
{
//为申请作业开辟新空间且初始化
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.ID=ID;
temp->data.size=request;
temp->data.state=Busy;

DuLNode *p=block_first->next;
while(p)
{
if(p->data.state==Free && p->data.size==request)
{//有大小恰好合适的空闲块
p->data.state=Busy;
p->data.ID=ID;
return OK;
break;
}
if(p->data.state==Free && p->data.size>request)
{//有空闲块能满足需求且有剩余"
temp->prior=p->prior;
temp->next=p;
temp->data.address=p->data.address;
p->prior->next=temp;
p->prior=temp;
p->data.address=temp->data.address+temp->data.size;
p->data.size-=request;
return OK;
break;
}
p=p->next;
}
return ERROR;
}
//-------------------- 最佳适应算法 ------------------------
Status Best_fit(int ID,int request)
{
int ch; //记录最小剩余空间
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.ID=ID;
temp->data.size=request;
temp->data.state=Busy;
DuLNode *p=block_first->next;
DuLNode *q=NULL; //记录最佳插入位置
while(p) //初始化最小空间和最佳位置
{
if(p->data.state==Free &&
(p->data.size>request || p->data.size==request) )
{
q=p;
ch=p->data.size-request;
break;
}
p=p->next;
}
while(p)
{
if(p->data.state==Free && p->data.size==request)
{//空闲块大小恰好合适
p->data.ID=ID;
p->data.state=Busy;
return OK;
break;
}
if(p->data.state==Free && p->data.size>request)
{//空闲块大于分配需求
if(p->data.size-requestdata.size-request;//更新剩余最小值
q=p;//更新最佳位置指向
}
}
p=p->next;
}
if(q==NULL) return ERROR;//没有找到空闲块
else
{//找到了最佳位置并实现分配
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.size=ch;
return OK;
}
}

//----------------------- 主存回收 --------------------
Status free(int ID)
{
DuLNode *p=block_first;
while(p)
{
if(p->data.ID==ID)
{
p->data.state=Free;
p->data.ID=Free;
if(p->prior->data.state==Free)//与前面的空闲块相连
{
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
}
if(p->next->data.state==Free)//与后面的空闲块相连
{
p->data.size+=p->next->data.size;
if(p>next->next!=NULL)
{ p->next->next->prior=p;
p->next=p->next->next;
}
}

break;
}
p=p->next;
}
return OK;
}

//--------------- 显示主存分配情况------------------
void show()
{
printf("+++++++++++++++++++++++++++++++++++++++\n");
printf("+++ 主存分配情况 +++\n");
printf("+++++++++++++++++++++++++++++++++++++++\n");
DuLNode *p=block_first->next;
while(p)
{
printf("分区号：");
if(p->data.ID==Free) printf("Free \n");
else printf("%d \n",p->data.ID);
printf("起始地址：%d\n",p->data.address);
printf("分区大小：%d KB \n",p->data.size);