课 程 设 计
课程设计名称：操作系统课程设计
专业班级：
学生姓名：
学 号：
指导教师：
课程设计时间： 6月13日-——6月17日
计算机科学 专业课程设计任务书
说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页
1：需求分析
（1） 用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。
（2） 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请50KB；作业6释放60 KB。采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。
2：概要设计
（1） 数据结构：作业队列数据结构，用于存储待处理作业；阻塞作业队列数据结构，用于存储阻塞的作业。已分配内存块的双向链表，记录当前系统已分配的各个内存块；未分配内存块的双向链表，记录系统中剩余的各个内存块；系统内存分配总情况的结点对象，记录系统中阻塞的作业总数，已分配的内存块数，剩余的内存块数。
（2） 主函数：对作业队列、阻塞队列、已分配内存块链表、未分配内存块链表、系统总内存分配情况结点对象进行初始化，调用分配函数或回收函数，循环处理11个作业步。
（3） 分配函数alloc()：首次适应算法检索未分配的内存块链表，若找到合适的内存块，则加以判断，空闲内存块大小减去作业去请求内存块大小小于系统额定的最小碎片值，把空闲块全部分配，否则进行分割分配，最后显示分配的内存信息。
（4） 回收函数free()：首次适应算法检索已分配的内存块链表，找到要释放的内存块后，在已分配链表中删除该结点，并把该结点挂到未分配内存块链表的结尾处，然后进行两次调整，把未分配的内存块链表调整为首地址从小到大的排列顺序，并且物理上相邻的空闲内存块要进行合并，以方便下次进行分配。调度分配函数，循环处理阻塞作业队列，最后显示回收后的内存情况。
（5） 调度图如下：
3：运行环境
硬件：计算机
软件：windowsXP vc++6.0
4:开发工具和编程语言
开发工具：vc++6.0
编程语言：C语言
5：详细设计
（1）：数据结构模块
struct job//作业结点
{
int num;//作业编号
int state;//0表示释放，1表示申请
int length;//作业要求处理大小
};
struct yifenpei//已分配内存块结点
{
int num;//占有内存区域的作业编号
int firstadd;//内存区域的首地址
int length;//内存区域的大小
struct yifenpei*forward;
struct yifenpei*next;
};
struct weifenpei//未分配内存块结点
{
int firstadd;//空闲区域的首地址
int length;//空闲区域的大小
struct weifenpei*forward;
struct weifenpei*next;
};
struct total//内存分配状况记录结点
{
int totalyifen;//已分配的总内存块数
int totalweifen;//未分配的总内存块数
int totalzuse;//阻塞的作业个数
};
struct job jobarray[11];//作业处理队列
struct yifenpei*headyifen=(struct yifenpei*)malloc(len2);//已分配的内存块所构成的双向链表的头指针
struct weifenpei*headweifen=(struct weifenpei*)malloc(len3);//未分配的内存块所构成的双向链表的头指针
struct job zuse[11];//阻塞作业队列
struct total totalnow;
2：主函数模块
void main()
{
jobarray[0].num=1; jobarray[0].state=1; jobarray[0].length=130;/* 初始化请求序列，共11个作业步*/
jobarray[1].num=2; jobarray[1].state=1; jobarray[1].length=60;
jobarray[2].num=3; jobarray[2].state=1; jobarray[2].length=100;
jobarray[3].num=2; jobarray[3].state=0; jobarray[3].length=60;
jobarray[4].num=4; jobarray[4].state=1; jobarray[4].length=200;
jobarray[5].num=3; jobarray[5].state=0; jobarray[5].length=100;
jobarray[6].num=1; jobarray[6].state=0; jobarray[6].length=130;
jobarray[7].num=5; jobarray[7].state=1; jobarray[7].length=140;
jobarray[8].num=6; jobarray[8].state=1; jobarray[8].length=60;
jobarray[9].num=7; jobarray[9].state=1; jobarray[9].length=50;
jobarray[10].num=6; jobarray[10].state=0; jobarray[10].length=60;
totalnow.totalyifen=0;totalnow.totalweifen=1;totalnow.totalzuse=0;//初始化系统内存分配状况
struct weifenpei*weifen=(struct weifenpei*)malloc(len3);
weifen->firstadd=1;weifen->forward=headweifen;weifen->length=640;weifen->next=NULL;
headweifen->forward=NULL;headweifen->next=weifen;//初始化未分配的内存块双向链表
headyifen->next=NULL;headyifen->forward=NULL;//初始化已分配的内存块双向链表
for(int m=0;m<11;m++)//初始化阻塞作业队列
{
zuse[m].num=0;zuse[m].state=0;
zuse[m].length=0;
}
for(int i=0;i<11;i++)//循环处理11个作业步
{
if(jobarray[i].state==1)
{
alloc(jobarray[i],jobarray[i].num);//调用分配函数
}
else
{
free(jobarray[i],jobarray[i].num);//调用释放函数
}
}
printf("全部作业已处理完成!");
}
3：分配函数模块
void alloc(struct job jobnow,int i)
{
int j=1;
struct weifenpei*weifennow1=NULL;struct weifenpei*weifennow2=NULL;
struct yifenpei*yifennow2=NULL;struct yifenpei*yifennow1=NULL;
weifennow1=headweifen;weifennow2=headweifen->next;
yifennow1=headyifen;yifennow2=headyifen->next;
while(yifennow2!=NULL)
{
yifennow1=yifennow2;
yifennow2=yifennow2->next;
}
yifennow2=(struct yifenpei*)malloc(len2);
while(weifennow2!=NULL)//首次适应算法检索合适的内存块
{
if(weifennow2->length>=jobnow.length)
{
if((weifennow2->length-jobnow.length)<=erding)//内存碎片小于额定值全部分配
{
weifennow1->next=weifennow2->next;
yifennow2->num=i;yifennow2->firstadd=weifennow2->firstadd;
yifennow2->length=weifennow2->length;yifennow2->forward=yifennow1;
yifennow1->next=yifennow2;yifennow2->next=NULL;
totalnow.totalyifen++;totalnow.totalweifen--;
}
else//否则进行分割分配诶
{
yifennow2->num=i;yifennow2->firstadd=weifennow2->firstadd;
yifennow2->length=jobnow.length;yifennow2->next=NULL;
yifennow2->forward=yifennow1;yifennow1->next=yifennow2;
weifennow2->length=weifennow2->length-jobnow.length;
weifennow2->firstadd=weifennow2->firstadd+jobnow.length;
totalnow.totalyifen++;
}
j=0;
break;
}
weifennow1=weifennow2;weifennow2=weifennow2->next;
}
if(j)//未找到合适内存块则把作业放入阻塞队列
{
for(int y=0;y<11;y++)
{
if(zuse[y].num==0)
{
zuse[y].num=jobnow.num;zuse[y].length=jobnow.length;
zuse[y].state=jobnow.state;
totalnow.totalzuse++;
break;
}
}
}
weifennow1=headweifen;weifennow2=headweifen->next;
yifennow1=headyifen;yifennow2=headyifen->next;
printf("当前阻塞作业个数为:%d\n",totalnow.totalzuse);//显示分配后的信息
printf("当前已分配%d个存储块:\n",totalnow.totalyifen);
while(yifennow2!=NULL)
{
printf("作业号:%d 首地址:%d 大小:%d\n",yifennow2->num,yifennow2->firstadd,yifennow2->length);
yifennow1=yifennow2;yifennow2=yifennow2->next;
}
printf("当前还有%d个空闲存储块:\n",totalnow.totalweifen);
while(weifennow2!=NULL)
{
printf("首地址:%d 大小:%d\n",weifennow2->firstadd,weifennow2->length,"\n");
weifennow1=weifennow2;weifennow2=weifennow2->next;
}
printf("\n");
}
4：回收函数模块
void free(struct job jobnow,int i)
{
int j=1;
struct weifenpei*weifennow1=NULL;struct weifenpei*weifennow2=NULL;
struct yifenpei*yifennow2=NULL;struct yifenpei*yifennow1=NULL;
weifennow1=headweifen;weifennow2=headweifen->next;
yifennow1=headyifen;yifennow2=headyifen->next;
while(weifennow2!=NULL)
{
weifennow1=weifennow2;
weifennow2=weifennow2->next;
}
while(yifennow2!=NULL)//首次适应算法检索已分配链表
{
if((yifennow2->num==jobnow.num)&&(yifennow2->length==jobnow.length))//找到后直接释放到未分配的内存块的表尾
{
yifennow1->next=yifennow2->next;yifennow2->next->forward=yifennow1;
weifennow2=(struct weifenpei*)malloc(len3);
weifennow2->forward=weifennow1;weifennow2->next=NULL;
weifennow1->next=weifennow2;
weifennow2->firstadd=yifennow2->firstadd;
weifennow2->length=yifennow2->length;
totalnow.totalyifen--;totalnow.totalweifen++;
j=0;
break;
}
yifennow1=yifennow2;yifennow2=yifennow2->next;
}
if(j==1)//未找到则作业队列有问题
{
printf("参数错误!");
}
else//将放到未分配的链表尾部的结点移动到合适的位置
{
struct weifenpei*weifennow3=headweifen;struct weifenpei*weifennow4=headweifen->next;
while(weifennow4!=weifennow2)
{
if(weifennow4->next==weifennow2)
{
if((weifennow2->firstadd+weifennow2->length)<weifennow4->firstadd)
{
weifennow4->next=weifennow2->next;
weifennow3->next=weifennow2;weifennow2->forward=weifennow3;
weifennow2->next=weifennow4;weifennow4->forward=weifennow2;
break;
}
if((weifennow2->firstadd+weifennow2->length)==weifennow4->firstadd)
{
weifennow2->length+=weifennow4->length;
weifennow3->next=weifennow2;weifennow2->forward=weifennow3;
totalnow.totalweifen--;
break;
}
}
else
{
if((weifennow2->firstadd+weifennow2->length)<weifennow4->firstadd)
{
weifennow2->forward->next=NULL;
weifennow3->next=weifennow2;weifennow2->forward=weifennow3;
weifennow2->next=weifennow4;weifennow4->forward=weifennow2;
break;
}
if((weifennow2->firstadd+weifennow2->length)==weifennow4->firstadd)
{
weifennow2->forward->next=NULL;
weifennow2->length+=weifennow4->length;
weifennow3->next=weifennow2;weifennow2->forward=weifennow3;
weifennow2->next=weifennow4->next;weifennow4->next->forward=weifennow2;
totalnow.totalweifen--;
break;
}
}
weifennow3=weifennow4;weifennow4=weifennow4->next;
}
}
weifennow1=headweifen;weifennow2=headweifen->next;
while(weifennow2!=NULL)//对未分配的内存块的双向链表进行合并紧凑操作，使得物理上相邻的内存块放到一个记录中
{
if((weifennow1!=headweifen)&&((weifennow1->firstadd+weifennow1->length)==weifennow2->firstadd))
{
weifennow2->length+=weifennow1->length;
weifennow2->firstadd=weifennow1->firstadd;
weifennow2->forward=weifennow1->forward;
weifennow1->forward->next=weifennow2;
totalnow.totalweifen--;
}
weifennow1=weifennow2;
weifennow2=weifennow2->next;
}
if(totalnow.totalzuse!=0)//释放内存后再循环处理阻塞队列中的阻塞作业，若仍无合适内存块则继续阻塞
{
for(int x=0;x<11;x++)
{
if(zuse[x].num!=0)
{
totalnow.totalzuse--;
zuse[x].num=0;zuse[x].state=0;
zuse[x].length=0;
alloc(zuse[x],zuse[x].num);
}
if(totalnow.totalzuse==0)
{
break;
}
}
}
weifennow1=headweifen;weifennow2=headweifen->next;
yifennow1=headyifen;yifennow2=headyifen->next;
printf("当前阻塞作业个数为:%d\n",totalnow.totalzuse);//显示释放内存以及处理完阻塞作业后的内存分配情况
printf("当前已分配%d个存储块:\n",totalnow.totalyifen);
while(yifennow2!=NULL)
{
printf("作业号:%d 首地址:%d 大小:%d\n",yifennow2->num,yifennow2->firstadd,yifennow2->length);
yifennow1=yifennow2;yifennow2=yifennow2->next;
}
printf("当前还有%d个空闲存储块:\n",totalnow.totalweifen);
while(weifennow2!=NULL)
{
printf("首地址:%d 大小:%d\n",weifennow2->firstadd,weifennow2->length);
weifennow1=weifennow2;weifennow2=weifennow2->next;
}
printf("\n");
}
6：调试分析
（1）设计数据结构时考虑到有两种可供选择，一种是用一个数据结构来描述内存块的分配情况，另外一种是分开描述，我采用了第二种，用两个双向链表来分别描述已分配和未分配的内存块。
（2）设计主函数以及分配函数时都是借鉴书上的知识，过程也很顺利。设计回收函数时，我发现我的这种数据结构若采用书上的算法，将很难实现，于是就另外设计了一种针对我这种数据结构的简单可行的回收算法，于是就解决了这个问题。
7：测试结果
程序运行结果如图1,2,3：
图1：
图2：
图3：
参考文献：
【1】任满杰 《操作系统原理实用教程》 电子工业出版社 2006
【2】汤子瀛 《计算机操作系统》（修订版） 西安电子科技大学出版社 2001
【3】张尧学 《计算机操作系统教程实验指导》 清华大学出版社 20##
【4】罗宇等 《操作系统课程设计》 机械工业出版社 2005
【5】 动态分区模拟算法 （网络文章）
心得体会
这次课程设计时间上比较紧迫，因为我们还有几门课程要考试，因此要留出一部分时间用于复习，所以我就压缩了课程设计的时间，选择了一个难度不是太大的题目。以前虽然老师让自学C语言，但总感觉没学到什么，但通过这次课程设计我对C语言的相关知识点又加深了认识和理解，同时在设计的过程中又设计了新的数据结构以及回收算法，提高了创新能力，总之，在这次课程设计中也收获了很多东西，但如果时间能再充裕点的话，我会做的更好。以后的自己还要再接再厉，努力，加油！