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

《操作系统课程设计实验报告可变分区存储管理和多级队列调度算法模拟实现》由会员分享，可在线阅读，更多相关《操作系统课程设计实验报告可变分区存储管理和多级队列调度算法模拟实现（34页珍藏版）》请在装配图网上搜索。

1、操作系统课程设计报告姓 名： 学 号： 班 级： 院 系： 日 期： 指导教师： 实验一：可变分区存储管理一、实验要求 设计合理的数据结构来描述存储空间：对于未分配出去的部分，可以用空闲分区队列来描述，对于已经分配出去的部分，由装入内存的作业占据，可以将作业组织成链表或数组。 实现分区存储管理的内存分配功能，要求选择至少两种适应算法（如首次适应算法，最佳适应算法，最后适应算法，最坏适应算法）。 实现分区存储管理的内存回收算法：要求能够正确处理回收分区与空闲分区的四种邻接关系。 当碎片产生时，能够进行碎片的拼接。二、设计目的在掌握了计算机可变分区存储管理方式的原理的基础上，利用C语言在windo

2、ws操作系统下模拟实现操作系统的可变分区存储管理的功能，以便加深对可变分区存储管理原理的理解，提高根据已有原理通过编程解决操作系统实际问题的能力，另一方面提高根据已有原理通过编程解决实际问题的能力，为进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。三、各功能模块分析实现需要设计合理的数据结构来描述存储空间，包括：被程序占用的存储空间、空闲的存储空间、多个程序的组织。通常用链表把这些同种类型的存储空间连接起来，使用结构体来描述每个存储空间的属性信息。根据可变分区存储管理的基本原理，程序的实现主要包括以下几个部分：1内存的初始化：包括确定内存的起始地址、内存的大小等。2要进入内存的程

3、序链表的产生：多个要进入内存运行的程序的产生，包括程序编号、所占存储空间的大小。可以把这些内容以记录式文件的形式保存到磁盘上，也可以把他们存放在二维数组中。若保存在文件中，则可以多次使用，如保存在数组中只能使用一次。3为程序分配存储空间： 可以采用首次适应、最佳适应、最后适应算法来实现。主要是按照这三种算法的思想对空闲块进行排序，以便找出符合要求的那个空闲块。对空闲块的排序思路可以使用冒泡排序算法的思想。4记录和显示内存被程序占用的情况5记录和显示内存中空闲块的情况6回收存储空间：程序运行完毕后，要及时回收内存空间。四、主程序流程图创建分区头节点删除上次的结果文件键盘输入字符stepIniti

4、aliziation字符step为？ step=1 step=2 Put job into memory step=6Move fragment together step=3step=4 Finish job step=5 Show current memory used by jobsShow current free liststep=7Exit五丶主要实验代码void init()/初始化，设置物理内存中用户区的大小，选取适应算法fl = NULL;/将各值复位al = NULL;jl = NULL;userMemory = 0;fitAlgorithm = 0;count = 0;p

5、rintf(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 fitAlgorithm;

6、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 size)/最佳适应算法，找到链表中分区大小最小的分区t = j;break;

7、case 2:if (j-size t-size)/最坏适应算法，找到链表中分区大小最大的分区t = j;break;case 3:if (j-startAddress startAddress)/首次适应算法，找到链表中分区起始地址最小的分区t = j;break;case 4:if (j-startAddress t-startAddress)/最后适应算法，找到链表中分区起始地址最大的分区t = j;break;tmpStartAddress = i-startAddress;/将剩余链中找到的分区交换到剩余链的最前端tmpSize = i-size;i-startAddress = t

8、-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-siz

9、e = 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); elseprintf(n该作业成功得到内存分配！n);int

10、 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-la

11、st = 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-las

12、t = NULL)fl = i-next; else if (i-next = NULL)i-last-next = NULL; elsei-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 *

13、 i = jl; i != NULL; i = i-next)/找出该ID的作业if (i-id = id)job = i;flag = 1;break;if (flag = 0)printf(n该ID不存在！n); elseif (job-last = NULL)/将已完成的作业从作业链表中删除jl = job-next;/若该job为链表头结点，则jl链表直接指向其下一个结点 else if (job-next = NULL)job-last-next = NULL; elsejob-last-next = job-next;job-next-last = job-last;delete

14、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 = s

15、tartAddress + a-size - 1;if (a-last = NULL)al = a-next; else if (a-next = NULL)a-last-next = NULL; elsea-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;fNod

16、e * 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)/查找与其起始地址前相邻的空闲分区

17、ls = i;if (ls = NULL) & (ns = NULL)/没有相邻的空闲分区可以合并，则单独作为一个分区插入空闲分区链表if (fl = NULL)fl = t;elset-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

18、 != NULL) & (ns != NULL)/前后两个分区都与之合并if (ns-last = NULL)/若ns为头结点，则fl链表直接指向其下一个结点fl = ns-next; else if (ns-next = NULL)/若ns为尾结点，则直接将该结点删除ns-last-next = NULL; elsens-last-next = ns-next;ns-next-last = ns-last;ls-size = ls-size + t-size + ns-size;delete ns;void defragment()/碎片整理，进行碎片拼接int sum = 0;/记录已分配

19、空间的总大小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);voi

20、d 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); elsei-status = 1;printf(n %d号作业成功得到内存分配！n, i-id);void showFList()/显示当前空闲分区链的信息printf(n);printf(#当前空闲分区链信息#n);

21、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,

22、 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

23、(|%10d, i-size);printf();if (i-status = 0)printf(| 未装入内存); elseprintf(| 已装入内存);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)

24、;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：显示当前空闲分区：进行拼接后显示分区：七丶实验小结通过本次课程设计，自己的编程能力有所提高，对操

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

26、动态的增加作业。总而言之，究其原因还是自己平时没学牢固。希望在以后的学习中可以学到更多知识。实验二：多级队列调度算法模拟实现1.设计要求 在熟练掌握计算机处理机调度原理的基础上，利用一种程序设计语言模拟实现多级反馈队列进程调度算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。 调度算法中采用至少4级队列，每级队列的时间片大小预先指定。 由于只是模拟实现，调度的对象进程实际上并不包括程序和数据，而仅仅包括一个PCB数据结构，用PCB来代表一个进程，调度算法调度的对象只包括进程的PCB.处理

27、机的切换通过将PCB在运行指针和就绪队列之间进行移动来实现。又因为进程的组成只有PCB，没有程序和数据，因而进程只有运行和就绪两种状态，没有等待状态。 为避免显示结果超过1屏，调度结果要求写入文件中以方便检验。2.基础知识 由于处理机是计算机系统中最宝贵和稀有的资源，因而处理机调度是操作系统进行资源管理的一个重要功能。现代操作系统广泛采用多道程序设计的技术来提高系统吞吐量，提高程序的并发度和资源利用率。特别是进程调度程序，由于其运行频率高，更加要求调度算法简单，高效，系统开销小，进程切换快，可以说，调度算法的好坏直接影响整个计算机系统的性能。 多级队列调度算法是一种动态优先数调度算法。对于普通

28、的优先调度算法，如何确定进程优先级以真实地反映进程运行的紧迫程度是一个难题，但在多级队列调度算法中，可以预先规定优先级一样可以获得好的性能。该算法实际上综合了两种调度算法：队列内部是FCFS,队列之间是优先调度。3.数据结构参考 最核心的数据结构就是进程的逻辑结构。 进程中必须包括的内容很多（参见教材PCB部分的定义），为了简化起见，可以略去一些与本模拟调度算法关系不大的一些信息。请同学们自行设计，要求能够实现本调度算法即可。4.主程序流程图初始化输入a ；a=2创建进程N执行进程aenter？YNYa=2?N撤消进程Ya=3?N阻塞进程Y唤醒进程a=4?Na=0?NY退出系统终止5.程序运行

29、截图：此系统的界面是在DOS界面下输出的,所以以下的输出结果均是DOS界面截图。初始化界面：创建进程：依次创建进程：a,b,c和所需时间。运行进程： 进程运行结束：6.实验关键代码：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 != NUL

30、L) p=print -LinkPCB; while(p) printf(%st%dt%dt%dt%dtt%ctt%dn,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(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,p-count); p = p-next; p = run; while(

31、p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,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

32、 InsertPrio(ReadyQueue *in) ReadyQueue *fst,*nxt; fst = nxt = Head; if(Head = NULL) in-next = Head; Head = in; else if(in -prio = fst -prio) in-next = Head; Head = in; else while(fst-next != NULL) nxt = fst; fst = fst-next; if(fst -next = NULL) in -next = fst -next; fst -next = in; else nxt = in; in

33、 -next = fst; void PrioCreate() ReadyQueue *tmp; int i; printf(输入就绪队列的个数：n); scanf(%d,&ReadyNum); printf(输入每个就绪队列的CPU时间片：n); for(i = 0;i round); tmp -prio = 50 - tmp-round; tmp -LinkPCB = NULL; tmp -next = NULL; InsertPrio(tmp); void GetFirst(ReadyQueue *queue) run = queue -LinkPCB; if(queue -LinkPC

34、B != NULL) run -state = R; queue -LinkPCB = queue -LinkPCB -next; run -next = NULL; void InsertLast(PCB *in,ReadyQueue *queue) PCB *fst; fst = queue-LinkPCB; if( queue-LinkPCB = NULL) in-next = queue-LinkPCB; queue-LinkPCB = in; else while(fst-next != NULL) fst = fst-next; in -next = fst -next; fst

35、-next = in; void ProcessCreate() PCB *tmp; int i; printf(输入进程的个数：n); scanf(%d,&num); printf(输入进程名字和进程所需时间：n); for(i = 0;i name); getchar(); scanf(%d,&(tmp-needtime); tmp -cputime = 0; tmp -state =W; tmp -prio = 50 - tmp-needtime; tmp -round = Head -round; tmp -count = 0; InsertLast(tmp,Head); void R

36、oundRun(ReadyQueue *timechip) int flag = 1; GetFirst(timechip); while(run != NULL) while(flag) run-count+; run-cputime+; run-needtime-; if(run-needtime = 0) run -state = F; InsertFinish(run); flag = 0; else if(run-count = timechip -round) run-state = W; run-count = 0; InsertLast(run,timechip); flag

37、= 0; flag = 1; GetFirst(timechip); void MultiDispatch() int flag = 1; int k = 0; ReadyQueue *point; point = Head; GetFirst(point); while(run != NULL) Output(); if(Head -LinkPCB!=NULL) point = Head; while(flag) run-count+; run-cputime+; run-needtime-; if(run-needtime = 0) run -state = F; InsertFinish

38、(run); flag = 0; else if(run-count = run-round) run-state = W; run-count = 0; if(point -next!=NULL) run -round = point-next -round; InsertLast(run,point-next); flag = 0; else RoundRun(point); break; +k; if(k = 3) ProcessCreate(); flag = 1; if(point -LinkPCB = NULL) point =point-next; if(point -next

39、=NULL) RoundRun(point); break; GetFirst(point); 7.实验总结：多级反馈队列调度算法又称反馈循环队列或多队列策略，主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。使用这种调度策略具有较好的性能，能够满足各类用户的需要。此系统简单模拟实现多级反馈队列调度算法，但是只是人为的模拟多线程实现处理器的分配，没有真正地实现多线程，只是单执行流过程。在这次操作系统中，使我对操作系统中进程的概念，进程的状态转换，线程的概念和多线程实现对处理器分配的基本原理有了更加深刻的理解。其中也体现了我的不足：（1）系统冗余代码过多。为了实现在dos下表格的制作，使用了一些特殊的表格线而非利用C语言中的画图功能，频繁的进行光标定位和结果输出，冗余代码过多，浪费系统资源。（2） 算法效率较低。算法的实现都只考虑到效果的实现，而算法的效率则次之。（3） 使用dos界面运行程序而非可视化窗口界面。（4）为了实现模拟的效果而采用了些低效率的做法，如：对进程的状态切换直接使用删除、插入进程节点的方法，而非利用指针定位实现状态的切换，使系统每次运行相关程序时，都要大量地执行删除、插入等操作，降低了系统的性能。