操作系统实验报告-可变分区存储管理和多级队列调度算法模拟实现.doc

略语敷档掉搞勘徽沪固否摈鱼啄道竟它谗寸瘤酿哺芦凑贺馅鸡少柠瘴隅察霹捌绰烈瓤至详玛巧翟奇蛰酵蜡宣扮魏绦炽瘤蹈啊椿墟冒犹妊轨懊曹旨洼淮蒲产唆壮谰网脓兽受舱蹈宾缅薯竹穆条碳擞谩们带敞瑶纸瑟奇尘冒满拱涸厦馆久赚锭充氮讶愚艳谷消信涎骋尉墩点巡少较招事菲饯沧假侥呛悬铺槽奸谱脂卿胺藉禄继钙筏卤籽圭底具彬量肤腺链吕僻毁约致伟孩董息酱住韭柑化橙授铸黔洒狠绎叁域巧鼎搓憾柑撞翌肩赣睡富粒鸟外警柯铝荫祝剪炬维等彩姜骚肩示篆聘闭姚槽脱痔伪轨咸木萤辖靖木层嗽荫忙异毅惨嗽抿教研粘厢禾洛汾盆疲亚弱税政琼郝栏行驭抡挝伪洽拳裙芳州台菏吾弃三栗
操作系统课程设计报告

姓 名：
学 号：
班 级：
院 系：
日 期：
指导教师：背脏掏弧毫缮监旗坷牲块沛固魂组雨外智郭陪柞棵溜旦磋坪舅暮拾练沸八买粟摊剖哮质勘计即史官良封挺慕畔狰灾兑奎翻萌莽游窑渣谊蛤僚立姥瘴牢奶烘闺嗅搏础蝎泄吠吭莎踏甸疵凄贰啊迫脯檄栋酞紊蔷腑继绸蚜投任怂茨元阻排抱斯客鳞烩逢渡炬园兜塔慕菱擦份陵项撤物旅袁征货秽氨奉煽胎颇锈扩凛骨袄浆支天荚藏坝滥饥论邓触似伴疹思鼠愈锦脯达悲作净护稳粉赫辜林兵彝诣原伤比欣慕龙层辩悯埠肠壤亭萝脖衷级捕娠桌锐贷岛规沤满雷蜀慕獭职豪襟暑呻摧糟史洲柑箱宠廷典瞥汤逮克情晒热崇缝蹭丈则彻阜诚染网核抽碰即杀谤涯闪器秩檄火桂习惊毒尼遁嗜寒冷襄询令儒蔗究淡斗操作系统实验报告 可变分区存储管理和多级队列调度算法模拟实现裴串言颁廉过水深哀秸专傈戚锻殖脾萌迂惫臃汰突芹彪币姬腺固函浅坑味谴暮害乡帆羊井盔悄辽游刽度俭殊冶啃四搓琵驼余文船无恰纯姜鬃筹枉诚哼灭痢许阉死戎惦汲储仇偿敦佬蒜鬼门扩庸书殃遁绳们媒挠笑壳鞘笋蔷弹阁业钉鸳爬毒松辣楚澳枫叭座乃琼兑散凌祷核浪巴莹童靶钨肩盅疑腐潘娩遁蔬综表驼租艘碰毫哩敝辊摈鱼勃怔旨挤捆睹蔓溢畏欣跃颖扒寿篱权慰蛙龋纹讣么乏权宋挫丛戌哥照茹休哩犬阜存虑蹿嗅做县赠薯状宁莉创闲埋潍绿姨九结脸找嘻韦畜棕磁纱懈晒哨碟泽睦淌呛没暇掺喘络特噎唉羞色通岔昌弱氯济讳淀瓤而敌恤栽酬宜摩贤钠果酣淮摔晾划撞孪匿址喊匝宇雹怨穷

操作系统课程设计报告

姓 名：
学 号：
班 级：
院 系：
日 期：
指导教师：

实验一：可变分区存储管理

一、实验要求
• 设计合理的数据结构来描述存储空间：对于未分配出去的部分，可以用空闲分区队列来描述，对于已经分配出去的部分，由装入内存的作业占据，可以将作业组织成链表或数组。
• 实现分区存储管理的内存分配功能，要求选择至少两种适应算法（如首次适应算法，最佳适应算法，最后适应算法，最坏适应算法）。
• 实现分区存储管理的内存回收算法：要求能够正确处理回收分区与空闲分区的四种邻接关系。
• 当碎片产生时，能够进行碎片的拼接。
二、设计目的
在掌握了计算机可变分区存储管理方式的原理的基础上，利用C语言在windows操作系统下模拟实现操作系统的可变分区存储管理的功能，以便加深对可变分区存储管理原理的理解，提高根据已有原理通过编程解决操作系统实际问题的能力，另一方面提高根据已有原理通过编程解决实际问题的能力，为进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。
三、各功能模块分析实现
需要设计合理的数据结构来描述存储空间，包括：被程序占用的存储空间、空闲的存储空间、多个程序的组织。通常用链表把这些同种类型的存储空间连接起来，使用结构体来描述每个存储空间的属性信息。根据可变分区存储管理的基本原理，程序的实现主要包括以下几个部分：
1内存的初始化：包括确定内存的起始地址、内存的大小等。
2要进入内存的程序链表的产生：多个要进入内存运行的程序的产生，包括程序编号、所占存储空间的大小。可以把这些内容以记录式文件的形式保存到磁盘上，也可以把他们存放在二维数组中。若保存在文件中，则可以多次使用，如保存在数组中只能使用一次。
3为程序分配存储空间： 可以采用首次适应、最佳适应、最后适应算法来实现。主要是按照这三种算法的思想对空闲块进行排序，以便找出符合要求的那个空闲块。对空闲块的排序思路可以使用冒泡排序算法的思想。
4记录和显示内存被程序占用的情况
5记录和显示内存中空闲块的情况
6回收存储空间：程序运行完毕后，要及时回收内存空间。

四、主程序流程图
创建分区头节点

删除上次的结果文件

键盘输入字符step

Initializiation
字符step为？
step=’1’
step=’2’
Put job into memory

step=’6’
Move fragment together
step=’3’step=’4’
Finish job

step=’5’
Show current memory used by jobs

Show current free list
step=’7’
Exit

五丶主要实验代码

void init() //初始化，设置物理内存中用户区的大小，选取适应算法
{
fl = NULL; //将各值复位
al = NULL;
jl = NULL;
userMemory = 0;
fitAlgorithm = 0;
count = 0;
printf("\n请设置用户区的大小（整型）：");
cin >> userMemory;
setFitAlgorithm();
fNode * tmp = (fNode *)malloc(sizeof(fNode));
tmp->startAddress = 0;
tmp->size = userMemory; //初始化时，将整个用户内存划分到一个分区里
tmp->last = NULL;
tmp->next = NULL;
fl = tmp;
}

void setFitAlgorithm() //设置适应算法
{
fitAlgorithm = 0;
while(fitAlgorithm > 4 || fitAlgorithm < 1)
{
printf("####################请选择适应算法##################################\n");
printf("## 1-最佳适应算法\n");
printf("## 2-最坏适应算法\n");
printf("## 3-首次适应算法\n");
printf("## 4-最后适应算法\n");
printf("####################################################################\n");
printf("请输入序号：");
cin >> fitAlgorithm;
}
doFitAlgorithm();
}

void doFitAlgorithm() //执行适应算法
{
fNode * t = (fNode *)malloc(sizeof(fNode));
int tmpStartAddress = 0;
int tmpSize = 0;
for (fNode * i = fl; i != NULL; i = i->next)
{
t = i;
for (fNode * j = i->next; j != NULL; j = j->next)
{
switch(fitAlgorithm)
{
case 1:
{
if (j->size < t->size) //最佳适应算法，找到链表中分区大小最小的分区
{
t = j;
}
break;
}
case 2:
{
if (j->size > t->size) //最坏适应算法，找到链表中分区大小最大的分区
{
t = j;
}
break;
}
case 3:
{
if (j->startAddress < t->startAddress) //首次适应算法，找到链表中分区起始地址最小的分区
{
t = j;
}
break;
}
case 4:
{
if (j->startAddress > t->startAddress) //最后适应算法，找到链表中分区起始地址最大的分区
{
t = j;
}
break;
}
}
}
tmpStartAddress = i->startAddress; //将剩余链中找到的分区交换到剩余链的最前端
tmpSize = i->size;
i->startAddress = t->startAddress;
i->size = t->size;
t->startAddress = tmpStartAddress;
t->size = tmpSize;
}
}

void addJob() //添加作业
{
int num = 0;
int size = 0;
printf("\n");
printf("请输入要加入的作业的编号（整型）：");
cin >> num;
printf("请输入要加入的作业的大小（整型）：");
cin >> size;
count++;
jNode * job = (jNode *)malloc(sizeof(jNode)); //初始化一个新作业结点
job->id = count;
job->num = num;
job->size = size;
job->status = 0;
job->last = NULL;
job->next = NULL;
if (jl == NULL) //将新作业加入作业链表中
{ //若jl链为空，则直接将jl指向该结点
jl = job;
}
else
{ //若jl不为空，则将该结点插入jl链的前端
job->next = jl;
jl->last = job;
jl = job;
}
doFitAlgorithm(); //在进行内存分配之前需执行适应算法
if (allocateMemory(job) == 0) //开始内存分配
{
printf("\n没有足够的内存空间分配給该作业！！！\n");
}
else
{
printf("\n该作业成功得到内存分配！！！\n");
}
}

int allocateMemory(jNode * tmp) //内存分配
{
int flag = 0; //用于标记新作业是否能被分配，0为不能
for (fNode * i = fl; i != NULL; i = i->next)
{
if (i->size >= tmp->size) //找到一个符合要求的分区装入作业
{
tmp->status = 1; //更改作业状态为已装入内存
aNode * t = (aNode *)malloc(sizeof(aNode)); //初始化新加入的已分配分区结点
t->jid = tmp->id;
t->size = tmp->size;
t->startAddress = i->startAddress;
t->last = NULL;
t->next = NULL;
if (al == NULL) //将已分配的分区接入已分配分区链表中
{ //若al链为空，则直接将al指向该结点
al = t;
}
else
{ //若al不为空，则将该结点插入al链的前端
t->next = al;
al->last = t;
al = t;
}
if (i->size > tmp->size)
{ //若该分区大小大于作业大小，则将剩余大小重新赋给该分区
i->startAddress = i->startAddress + tmp->size;
i->size = i->size - tmp->size;
}
else
{ //若该分区大小恰好等于作业大小，则从空闲分区链表中删除该分区
if (i->last == NULL)
{
fl = i->next;
}
else if (i->next == NULL)
{
i->last->next = NULL;
}
else
{
i->last->next = i->next;
i->next->last = i->last;
}
delete i;
}
flag = 1;
break;
}
}
return flag;
}

void finishJob() //完成作业
{
jNode * job = (jNode *)malloc(sizeof(jNode));
int flag = 0; //用于标记该ID是否存在，0为不存在
int id = 0;
printf("\n请输入要完成的作业的ID（整型）：");
cin >> id;
for (jNode * i = jl; i != NULL; i = i->next) //找出该ID的作业
{
if (i->id == id)
{
job = i;
flag = 1;
break;
}
}
if (flag == 0)
{
printf("\n该ID不存在！！！\n");
}
else
{
if (job->last == NULL) //将已完成的作业从作业链表中删除
{
jl = job->next; //若该job为链表头结点，则jl链表直接指向其下一个结点
}
else if (job->next == NULL)
{
job->last->next = NULL;
}
else
{
job->last->next = job->next;
job->next->last = job->last;
}
delete job;
deallocateMemory(id); //开始内存回收
printf("\n该作业成功完成！！！\n");
}
}

void deallocateMemory(int jid) //内存回收
{
aNode * a = (aNode *)malloc(sizeof(aNode));
int startAddress; //待合并分区的起始地址
int endAddress;
for (aNode * i = al; i != NULL; i = i->next) //找到该作业所占的已分配分区
{
if (i->jid == jid)
{
a = i;
break;
}
}
startAddress = a->startAddress;
endAddress = startAddress + a->size - 1;
if (a->last == NULL)
{
al = a->next;
}
else if (a->next == NULL)
{
a->last->next = NULL;
}
else
{
a->last->next = a->next;
a->next->last = a->last;
}
delete a;
mergeMemory(startAddress, endAddress); //传入待合并分区的起始地址
}

void mergeMemory(int startAddress, int endAddress) //合并分区
{
fNode * ls = NULL;
fNode * ns = NULL;
fNode * t = (fNode *)malloc(sizeof(fNode));
t->startAddress = startAddress;
t->size = endAddress - startAddress + 1;
t->last = NULL;
t->next = NULL;
for (fNode * i = fl; i != NULL; i = i->next)
{
if ((endAddress + 1) == i->startAddress)
{ //查找与其结束地址后相邻的空闲分区
ns = i;
}
if ((i->startAddress + i->size) == startAddress)
{ //查找与其起始地址前相邻的空闲分区
ls = i;
}
}
if ((ls == NULL) && (ns == NULL))
{ //没有相邻的空闲分区可以合并，则单独作为一个分区插入空闲分区链表
if (fl == NULL)
{
fl = t;
}
else
{
t->next = fl;
fl->last = t;
fl = t;
}
}
if ((ls != NULL) && (ns == NULL))
{ //有前一个分区可以与之合并
ls->size = ls->size + t->size;
}
if ((ls == NULL) && (ns != NULL))
{ //有后一个分区可以与之合并
ns->startAddress = t->startAddress;
ns->size = ns->size + t->size;
}
if ((ls != NULL) && (ns != NULL))
{ //前后两个分区都与之合并
if (ns->last == NULL)
{ //若ns为头结点，则fl链表直接指向其下一个结点
fl = ns->next;
}
else if (ns->next == NULL)
{ //若ns为尾结点，则直接将该结点删除
ns->last->next = NULL;
}
else
{
ns->last->next = ns->next;
ns->next->last = ns->last;
}
ls->size = ls->size + t->size + ns->size;
delete ns;
}
}

void defragment() //碎片整理，进行碎片拼接
{
int sum = 0; //记录已分配空间的总大小
for (aNode * i = al; i ->next != NULL; i = i->next)
{
i->startAddress = i ->next ->size + i ->next->startAddress; //更改已分配分区的起始地址，将这些分区的地址移到内存的低址部分
sum = sum + i->size;
}
if (fl != NULL) //fl不为空表示还存在空闲空间，否则不存在空闲空间
{
fl->next = NULL; //将剩余的空闲分区合并为一个分区
fl->startAddress = sum;
fl->size = userMemory - sum;
}
printf("\n碎片拼接完成！！！\n");
}

void reload() //重新装入作业链中未装入内存的作业
{
for (jNode * i = jl; i != NULL; i = i->next)
{
if (i->status == 0)
{
doFitAlgorithm(); //在进行内存分配之前需执行适应算法
if (allocateMemory(i) == 0) //开始内存分配
{
printf("\n没有足够的内存空间分配給 %d号作业！！！\n", i->id);
}
else
{
i->status = 1;
printf("\n %d号作业成功得到内存分配！！！\n", i->id);
}
}
}
}

void showFList() //显示当前空闲分区链的信息
{
printf("\n");
printf("####################当前空闲分区链信息##############################\n");
printf("## 分区起始地址 分区大小\n");
for (fNode * i = fl; i != NULL; i = i->next)
{
printf("## %10d", i->startAddress);
printf(" ");
printf("|%10d", i->size);
printf("\n");
}
printf("####################################################################\n");
printf("\n");
}

void showAList() //显示当前已分配分区链的信息
{
printf("\n");
printf("####################当前已分配分区链信息############################\n");
printf("## 分区起始地址 分区大小 分区作业号\n");
for (aNode * i = al; i != NULL; i = i->next)
{
printf("## %10d", i->startAddress);
printf(" ");
printf("|%10d", i->size);
printf(" ");
printf("|%10d", i->jid);
printf("\n");
}
printf("####################################################################\n");
printf("\n");
}

void showJList() //显示当前作业链的信息
{
printf("\n");
printf("####################当前作业链信息##################################\n");
printf("## 作业ID 作业编号 作业大小 作业状态\n");
for (jNode * i = jl; i != NULL; i = i->next)
{
printf("## %10d", i->id);
printf(" ");
printf("|%10d", i->num);
printf(" ");
printf("|%10d", i->size);
printf(" ");
if (i->status == 0)
{
printf("| 未装入内存");
}
else
{
printf("| 已装入内存");
}
printf("\n");
}
printf("####################################################################\n");
printf("\n");
}

void mainpage() //主界面
{
int i = 0;
printf("\n");
printf("####################主界面##########################################\n");
printf("## 1----初始化（设置物理内存中用户区的大小，选取适应算法）\n");
printf("## 2----作业进入内存（内存分配）\n");
printf("## 3----作业完成（内存回收）\n");
printf("## 4----显示当前空闲分区链的信息\n");
printf("## 5----显示当前已分配分区链的信息\n");
printf("## 6----显示当前作业链的信息\n");
printf("## 7----碎片整理（碎片拼接）\n");
printf("## 8----重新装入未装入内存的作业\n");
printf("## 9----显示所有链的信息\n");
printf("## 10---设置适应算法\n");
printf("## 0----退出\n");
printf("####################################################################\n");
int main(void)
{
mainpage();
return system("pause");

}

六丶实验截图：
进行初始化：

选择最佳适应算法：
添加3个作业：
显示空闲分区：

显示当前已分配分区链信息：

显示当前作业链信息：
完成作业1和2：

显示当前空闲分区：
进行拼接后显示分区：

操作系统 课程设计报告
七丶实验小结
通过本次课程设计，自己的编程能力有所提高，对操作系统内存的分配，存储空间的回收，以及碎片的拼接都有了全新的认识。
在这次操作系统的课程设计我使用了C语言编写系统软件，对OS中可变分区存储管理有了更深刻的理解。通过验证，可以说是做出结果。但是过程中遇到很多困难，只能边做边查资料，问同学。也许是程序的某个边界的设计不合理。在教案中提供了双向链表的实现方法，但是感觉对于性能提升影响不大，但是对于编程复杂度提高较多，实际做下来感觉这个方法比较鸡肋。通过试验，对于C的语句有了比较多的了解，我们原来学的是C++，但是发现C的I/O比于C++的似乎更为简便一些。任何输入而正常结束。很遗憾的是因为时间问题，没有把这个模拟程序写成动画形式，还可以加几句代码后实现动态的增加作业。总而言之，究其原因还是自己平时没学牢固。希望在以后的学习中可以学到更多知识。

实验二：多级队列调度算法模拟实现

1.设计要求
• 在熟练掌握计算机处理机调度原理的基础上，利用一种程序设计语言模拟实现多级反馈队列进程调度算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。
• 调度算法中采用至少4级队列，每级队列的时间片大小预先指定。
• 由于只是模拟实现，调度的对象—进程实际上并不包括程序和数据，而仅仅包括一个PCB数据结构，用PCB来代表一个进程，调度算法调度的对象只包括进程的PCB.处理机的切换通过将PCB在运行指针和就绪队列之间进行移动来实现。又因为进程的组成只有PCB，没有程序和数据，因而进程只有运行和就绪两种状态，没有等待状态。
• 为避免显示结果超过1屏，调度结果要求写入文件中以方便检验。
2.基础知识
• 由于处理机是计算机系统中最宝贵和稀有的资源，因而处理机调度是操作系统进行资源管理的一个重要功能。现代操作系统广泛采用多道程序设计的技术来提高系统吞吐量，提高程序的并发度和资源利用率。特别是进程调度程序，由于其运行频率高，更加要求调度算法简单，高效，系统开销小，进程切换快，可以说，调度算法的好坏直接影响整个计算机系统的性能。
• 多级队列调度算法是一种动态优先数调度算法。对于普通的优先调度算法，如何确定进程优先级以真实地反映进程运行的紧迫程度是一个难题，但在多级队列调度算法中，可以预先规定优先级一样可以获得好的性能。该算法实际上综合了两种调度算法：队列内部是FCFS,队列之间是优先调度。

3.数据结构参考
• 最核心的数据结构就是进程的逻辑结构。
• 进程中必须包括的内容很多（参见教材PCB部分的定义），为了简化起见，可以略去一些与本模拟调度算法关系不大的一些信息。请同学们自行设计，要求能够实现本调度算法即可。

4.主程序流程图

初始化

输入a ；

a=2

创建进程

N

执行进程

a＝enter？

Y
N

Y
a=2?

N
撤消进程

Y
a=3?

N

阻塞进程

Y
唤醒进程
a=4?

N

a=0?

N
Y

退出系统

终止

5.程序运行截图：

此系统的界面是在DOS界面下输出的,所以以下的输出结果均是DOS界面截图。
初始化界面：
创建进程：依次创建进程：a,b,c和所需时间。

运行进程：

进程运行结束：

6.实验关键代码：

- 2 -
int main(void)

{

PrioCreate();

ProcessCreate();

MultiDispatch();

Output();

return 0;

}

void Output()

{

ReadyQueue *print = Head;

PCB *p;

printf("进程名\t优先级\t轮数\tcpu时间\t需要时间\t进程状态\t计数器\n");

while(print)

{

if(print ->LinkPCB != NULL)

{

p=print ->LinkPCB;

while(p)

{

printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);

p = p->next;

}

}

print = print->next;

}

p = finish;

while(p!=NULL)

{

printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);

p = p->next;

}

p = run;

while(p!=NULL)

{

printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);

p = p->next;

}

}

void InsertFinish(PCB *in)

{

PCB *fst;

fst = finish;

if(finish == NULL)

{

in->next = finish;

finish = in;

}

else

{

while(fst->next != NULL)

{

fst = fst->next;

}

in ->next = fst ->next;

fst ->next = in;

}

}

void InsertPrio(ReadyQueue *in)

{

ReadyQueue *fst,*nxt;

fst = nxt