课程设计报告书2014 / 2015 学年第 2 学期课程名称：操作系统课程设计专业班级：_计算机科学与技术1303班__ 学号：________ _________ 姓名：_________ ___________ 指导教师：_____ 邵虹崔文成 ______题目1 连续动态内存管理模拟实现1.1 题目的主要研究内容及预期达到的目标（1）针对操作系统中内存管理相关理论进行设计，编写程序并进行测试，该程序管理一块虚拟内存。
重点分析三种连续动态内存分配算法，即首次适应算法、循环首次适应算法和最佳适应算法。
（2）实现内存分配和回收功能。
1.2 题目研究的工作基础或实验条件（1）硬件环境：PC机（2）软件环境：Windows XP，Visual C++ 6.01.3 设计思想首次适应算法的实现：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法的目的在于减少查找时间。
为适应这种算法，空闲分区表中的空闲分区要按地址由低到高进行排序。
该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高址空间保留大的空闲区。
循环首次适应算法的实现：在分配内存空间时，不再每次从表头开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。
该算法能使内存中的空闲区分布得较均匀。
最佳适应算法的实现：从全部空闲区中找到能满足作业要求的、且最小的空闲分区，这种方法能使碎片尽量小。
为适应此算法，空闲分区表中的空闲分区要按从小到大进行排序，从表头开始查找第一个满足要求的自由分配。
1.4 流程图内存分配流程图，如图1-1所示。
图1-1 内存分配流程图内存回收流程图，如1-2所示。
图1-2 内存回收流程图1.5 主要程序代码（1）分配内存void allocate(char z,float l){int i,k;float ad;k=-1;for(i=0;i<m;i++)if(free_table[i].length >= l && free_table[i].flag == 1)if(k==-1 || free_table[i].length<free_table[k].length)k=i;if(k==-1)printf("无可用空闲区\n");return;}if(free_table[k].length-l <= minisize){free_table[k].flag=0;ad=free_table[k].address;l=free_table[k].length;}else{free_table[k].length=free_table[k].length-l;ad=free_table[k].address+free_table[k].length;}i=0;while(used_table[i].flag!=0 && i<n)i++;if(i>=n){printf("无表目填写已分分区，错误\n");if(free_table[k].flag==0)free_table[k].flag=1;else{free_table[k].length=free_table[k].length+l;return;}}elseused_table[i].address=ad;used_table[i].length=l;used_table[i].flag=z;}return;}（2）回收内存void reclaim(char z){int i,k,j,s,t;float S,L;s=0;while((used_table[s].flag!=z || used_table[s].flag==0)&&s<n) s++;if(s>=n){printf("找不到该作业\n");return;}used_table[s].flag=0;S=used_table[s].address;L=used_table[s].length;j=-1;k=-1;i=0;while(i<m&&(j==-1||k==-1)){if(free_table[i].flag==1){if(free_table[i].address+free_table[i].length==S)k=i;if(free_table[i].address==S+L)j=i;}i++;}if(k!=-1)if(j!=-1){free_table[k].length=free_table[j].length+free_table[k].length+L;free_table[j].flag=0;}elsefree_table[k].length=free_table[k].length+L;else if(j!=-1){free_table[j].address=S;free_table[j].length=free_table[j].length+L;}else{t=0;while(free_table[t].flag==1&&t<m)t++;if(t>=m){printf("主存空闲表没有空间,回收空间失败\n");used_table[s].flag=z;return;free_table[t].address=S;free_table[t].length=L;free_table[t].flag=1;}return;}（3）主函数void main( ){int i,a;float l;char z;free_table[0].address=10240;free_table[0].length=102400;free_table[0].flag=1;for(i=1;i<m;i++)free_table[i].flag=0;for(i=0;i<n;i++)used_table[i].flag=0;while(1){printf("1.分配主存\n");printf("2.回收主存\n");printf("3.显示主存\n");printf("0.退出\n");printf("请选择:");scanf("%d",&a);switch(a){exit(0);case 1:printf("输入作业名和作业所需长度:");scanf("%*c%c%f",&z,&l);allocate(z,l);break;case 2:printf("输入要回收分区的作业名");scanf("%*c%c",&z);reclaim(z);break;case 3:printf("输出空闲区表：\n起始地址分区长度标志\n");for(i=0;i<m;i++)printf("%6.0f%9.0f%6d\n",free_table[i].address,free_table[i].length, free_table[i].flag);printf(" 按任意键,输出已分配区表\n");getch();printf(" 输出已分配区表：\n起始地址分区长度标志\n");for(i=0;i<n;i++)if(used_table[i].flag!=0)printf("%6.0f%9.0f%6c\n",used_table[i].address,used_table[i].length, used_table[i].flag);elseprintf("%6.0f%9.0f%6d\n",used_table[i].address,used_table[i].length, used_table[i].flag);break;default:printf("没有该选项\n");}}}1.6 运行结果及分析（1）分配主存设作业名为w，作业所需长度为10。
如图1-3所示。
图1-3 分配主存（2）显示主存因为空闲区的初始地址为10240，空闲区的初始长度为102400，由于分配给作业w的作业所需长度为10，故未分配的分区长度为102390。
如图1-4所示。
图1-4 显示主存输出已分配区表，如图1-5所示。
图1-5 输出已分配区表由图1-5可知，根据首次适应算法，首先选择地址较低的空闲区。
因此分配给作业w的起始地址即为112630。
（3）回收主存由于已分配给作业w的分区长度为10，此时回收其主存，已将作业w从中去除，故该分区为空（“0”表示“空栏目”），但此时已存在一个长度为10的分区。
如图1-6所示。
图1-6 回收主存1.7 心得体会通过该题目的课程设计，让我明白了动态分区分配算法是如何实现的，如何实现内存的分配与回收。
也让我充分地理解了内存管理的机制的实现，从而对计算机有了进一步的了解，对于进一步学习和研究计算机系统起到了重大的作用。
题目2 进程调度算法的实现2.1题目的主要研究内容及预期达到的目标（1）针对操作系统中进程调度相关理论进行设计。
编写程序并进行测试，该程序可以对多个进程进行调度，调度算法采用基于时间片的高优先级调度。
（2）实现基于时间片的多优先级调度算法。
2.2 题目研究的工作基础或实验条件（1）硬件环境：PC机（2）软件环境：Windows XP，Visual C++ 6.02.3 设计思想首先设计一个结构体用来存放进程控制块（PCB）的各种信息，然后创建进程；根据输入的原始进程的数据，按照到达时间和优先级进行排序；通过输入时间片的大小，按照基于时间片的多优先级调度进行调度，输出其调度情况信息。
2.4 流程图进程调度算法流程图，如图2-1所示。
图2-1 进程调度算法流程图2.5 主要程序代码（1）创建进程typedef struct process{char name[100];int priority;int ReachTime;int NeedTime;int UsedTime;char state;}PCB;int n;PCB pcb[Max];int pTime;void AddProcess(){char ch;do{printf("\n请输入进程名:\n");scanf("%s",pcb[n].name);printf("请输入进程的优先级:\n");scanf("%d",&pcb[n].priority);printf("请输入进程需要的时间:\n");scanf("%d",&pcb[n].NeedTime);pcb[n].ReachTime=n;pcb[n].UsedTime=0;pcb[n].state='W';n++;printf("是否继续增加进程：是(Y),否(N)\n");do{ch=getchar();}while(ch!='Y'&&ch!='N'&&ch!='y'&&ch!='n');}while(ch=='Y'||ch=='y');}（2）进程调度信息排序先按照到达时间排序，再按照优先级排序。