操作系统原理课程设计-Linux2.6进程管理和内存管理的仿真实现

1、 操作系统原理课程设计实践报告全套设计加扣 3012250582题 目: Linux2.6进程管理和内存管理的仿真实现 姓 名: 学 院: 信息科技学院 专 业: 计算机科学技术系 班 级: 计科121 学 号: 指导教师: 职称: 教授 2014年3月 12 日Linux2.6进程管理和内存管理的仿真实现摘要：处理机调度可分为三个级别，分别是高级调度、中级调度和低级调度。高级调度又称作业调度，作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪

2、队列。进程管理是操作系统中的重要功能，用来创建进程、撤消进程、实现进程状态转换，它提供了在可运行的进程之间复用CPU的方法。在进程管理中，进程调度是核心，因为在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态，当就绪进程个数大于处理器数目时，就必须依照某种策略决定哪些进程优先占用处理器。Linux2.6调度算法是基于优先级的调度，它的算法复杂度为O(1)，也就是说是调度器的开销是恒定的，与系统当前的负载没有关系。Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下，避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题。伙伴系统的宗旨就是用最小的内存块来满足内核的

3、对于内存的请求。关键字：Linux，进程调度，作业调度，内存管理，伙伴系统 1. 目的和意义通过模拟Linux操作系统的O（1）调度算法与windows操作系统下进程调度策略进行比较。加深对操作系统进程调度方面知识的认识与理解。通过模拟Linux环境下的内存管理。并将内存分配与作业调度相结合,使我们对伙伴算法的原理和作业调度的过程有了详细的了解。2.理论分析通过对操作系统书，数据结构和c/c+程序设计语言书的学习。我们把这次所要做的实验分为下面几个部分2.1进程管理Linux2.6的进程管理方面的知识我们参照的是操作系统教程第二章linux2.6O（1）算法章节的内容。Linux2.6的进程管

4、理保证了无论系统进程数目怎样增加，选择合适进程且为其分配处理器的时间。处理器拥有可运行队列组和等待队列组；在每个关键的时间点记录时间，确保正确的响应时间；保证公平性，无进程处于饥饿状态。O(1)调度器是以进程的动态优先级 prio为调度依据的,它总是选择目前就绪队列中优先级最高的进程作为候选进程 。由于实时进程的优先级总是比普通进程的优先级高,故能保证实时进程总是比普通进程先被调度。2.2内存管理当作业到达内存外时按先来先服务的顺序申请分配内存，若分配成功作业进入内存按最短剩余时间优先的顺序进入CPU开始执行；若分配失败，作业被阻塞在内存外。等待已进入内存的作业释放占有的内存后继续申请分配内存

5、。直到所有作业执行完毕。2.2.1作业调度我们设计的作业调度采取的是先来先服务策略，按照作业提交或进程变为就绪状态的先后次序，分派CPU；当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。进程调度采取的是最短剩余时间优先调度的策略。先来先服务作业调度策略是根据作业到达时间依次进入内存，而最短剩余时间优先调度策略是根据作业所需剩余时间决定谁先占用cpu。2.2.2 伙伴系统伙伴系统数据结构的定义，分配回收算法的定义和解释我们参照的是严蔚敏，吴伟民.数据结构:C语言版，该书的第203到20

6、6页伙伴系统的特征为： 1.把所有的空闲页框分组为m+1（11）个块链表，每个块链表分别包含大小为2n（n为010的整数）个连续的页框，即1、2、4、6、8、16、32、64、128、256、512和1024个连续的页框。2.每个块的第一个页框的物理地址是该块大小的整数倍。伙伴系统原理为：任何尺寸2i的空闲块都可以被分割成两个尺寸为2i-1的空闲块，这两个空闲块被称为伙伴，他们可以合并成一个尺寸为2i的空闲块。4.设计思想4.1进程调度设计思想设置一个优先级链作为优先级队列头，一共有140个优先级0139.它包含4个节点信息，status_bit位标志该优先级队列是否为空。pcblink_nu

7、m优先级值，next_pcb指向第一个该优先级队列的第一个的进程，next指向下一个优先级。每一个优先级队头都指向一条进程链（优先级相同）。进程节点包含 next指向下一个进程。如图：就绪队列组4.2内存管理设计思想4.2.1.作业调度设计思想我们定义了两个队列：waitjcb队列用于存放等待进入内存的作业readyjcb队列用于存放已经进入内存处于就绪状态和正在占用CPU运行的进程内存内 readyjcb队列 进程1 进程2 进程3 进程4 进程5.作业1 作业2 作业3 作业4 作业5内存外 waitjcb队列 内存内，进程被处理器调度 FIFO策略 先来先服务;即先到达的作业先进入rea

8、dyjcb最短剩余时间优先策略;即以每一个作业到达时间为准，对readyjcb重新排序，找到最合适的进程调度4.2.2伙伴系统的设计思想系统开始运行时整个内存是一个大小为2m的空闲块，运行一段时间后被分成若干占用块和空闲块。为分配查找方便。我们将所有大小相同的空闲块建于一张子表中，每个子表是一个双重链表。这样的链表有m+1个。将这m+1个表头指针用向量结构组织成一个表，最开始只在m子链上有一个大小为1024的空闲块。这就是伙伴系统中的可利用空间表。如下图：空闲链表5.核心数据结构说明5.1进程调度数据结构typedef struct task_structint pid; /进程号volati

9、le long state; /进程当前状态 unsigned long flags; /进程状态信息，非运行状态long prio; /进程优先级long counter; /时间片int nice; /交互性值long staticprio; /非实时进程优先级int starttimet; /进程启动时间int needtime; /进程所需时间int runtime; /进程已运行时间 int usetime; /进程已占用cpu时间int entertime; /进程进入CPU的时间int timeslice; /时间片余额struct task_struct *next; pcbn

10、ode,*pcblink;typedef struct pcblink_node /就绪队列 int pcblink_num; /优先级0139 int status_bit; /该就绪队列是否有进程 1有0无 pcblink next_pcb; /指向该优先级队列的进程;struct pcblink_node *next; /指向下一个优先级队列pcblink_node,*linklist;typedef struct queue /就绪队列组linklist front; linklist rear;queue;extern pcbnode *current;/指向当前正在运行的进程ext

11、ern pcbnode *newcreate；/指向最新产生的一个进程extern int k；/就绪队列某个优先级的进程数5.2内存管理数据结构5.2.1.作业调度的数据结构struct jcbchar name; /作业名int id; /作业号int needtime;/所需时间int cometime; /进入内存时间int prio; /优先级int size;/请求分配内存大小site *address;/请求分配内存的首地址jcb *next;int Clock=0;/模拟系统时间int num;/创建的作业数jcb *waitjcb=(jcb*)(malloc(sizeof j

12、cb);/内存外的后备作业队列jcb *ready;/指向正在CPU中运行的进程jcb *readyjcb=(jcb*)(malloc(sizeof jcb);/内存中就绪和正在运行的进程队列5.2.2伙伴系统的数据结构#define m 10/可利用空间总容量的2的幂次，子表的个数为m+1typedef struct pageblock/块信息的数据结构 pageblock *front;/前驱指针 pageblock *next;/后驱指针 int tag ;/0空闲。1使用 int kva ;/块大小 2的k次幂pageblock, *site;typedef struct headno

13、de/表头向量组织 int nodesize;/该链表空闲块大小 pageblock *first;/该链表表头指针 freelistm+1;/表头向量类型extern site f; /首地址6.核心函数及算法流程Main()progressjc();进程调度O（1）算法jcbrun();内存管理init(&a)初始化内存createjcb();创建作业run()三级调度Output（a）当前内存情况系统框架6.1进程调度函数void createqueue(queue &Q ); /创建优先级0140队列头void init(queue &Q); /构造一个空队列Qvoid createp

14、cb(queue &Q,int number); /创建进程 插入就绪队列unsigned int task_timeslice(pcbnode *p) ; /计算时间片 void change_state(pcbnode *p); /改变进程状态void pcblist_finder(queue Q); /查找就绪位图 void deletepcb(queue &Q,pcbnode *p); /撤销进程void addqueue(queue &Q,pcbnode *p); /将进程插入等待就绪组void pcblist_ergodic(queue Q); /所在进程链就绪队列的的遍历 voi

15、d Oone(queue &A,queue &E,queue &B); / O（1）算法void move_into_cpu(pcbnode *tar); /进入cpu 并处理计算void move_out_cpu(queue &Q,queue &E,pcbnode *tar) ; /离开cpu 有active 和 expired 两个优先级数组, active 数组中包含了有剩余时间片的任务,expired 数组中包含了所有用完时间片的任务。当一个任务的时间片用完了就会重新计算其时间片,并插入到 expired 队列中,当 active 队列中所有进程用完时间片时,只需交换指向 active

16、 和 expired 队列的指针即可算法流程O（1）算法流程图6.2内存管理函数及算法流程否是Clock+1否程序运行结束是当所需时间为0，执行完毕，从readyjcb队列撤销，释放内存两个队列是否均为空占用cpu执行，所需时间减1等待作业所需剩余时间是否最少成功作业进入内存，从waitjcb队列撤销并插入readyjcb队列失败作业请求分配内存否作业到达时间是否等于clock作业在waitjcb队列等待开始随机产生作业放入waitjcb队列设置时钟clock=0，模拟系统时间是6.2.1.作业调度的函数void createjcb()； /创建作业并插入后备队列void deletewait

17、(jcb *&p)；/删除后备队列中的作业void deleteready(jcb *p)；/删除内存中的作业void print(jcb *w)； /遍历队列void inready(jcb *readyjcb,jcb *p)；/将作业插入到readyjcb队列void sortready(jcb *readyjcb)；/将作业按照最短剩余时间进行排序void run()； /作业调度进程调度算法流程否是Clock+1否是否作业所需剩余时间是否最少等待否占用cpu执行，所需时间减1当所需时间为0，执行完毕，从readyjcb队列撤销，释放内存两个队列是否均为空程序运行结束是作业到达时间是否等

18、于clock作业在waitjcb队列等待内存是否已满作业进入请求分配内存，从waitjcb队列撤销并插入readyjcb队列开始随机产生作业放入waitjcb队列设置时钟clock=0，模拟系统时间是6.2.2伙伴系统的函数void init(freelist *a); /初始化空闲链表void output(freelist a); /输出空闲链表site allocpages(freelist *avail,int n)/分配内存块,并返回其首地址void printinsert(site p); / 显示已分配出去的内存块信息site buddy(site p); /返回初始地址为p,大

19、小为2的k次方的内存块，的伙伴块地址void freepages( freelist *free,site *p); / 回收内存void progressnc(); /内存管理算法流程分配算法查找成功查找失败开始请求分配大小为n的内存指向子表的第一个空闲块删除该空闲块，子表表头指向该块的下一个空闲块 返回该占用块的地址返回NULL将该空闲块的2k （2k-1nsize的内容Int cir; /用于设置时钟中断，当cir=0时发送中断信号处理之前未处理的进程请求（1）.为了模拟操作系统的并发环境，设置一个随机数 tag tag=0或1，当tag为0时 内存先工作 输出内存分配情况，然后进程开始

20、发出分配内存的请求，这时候请求不能得到满足。Tag=1时 进程先发送分配请求，内存接受请求开始工作并输出分配后的空闲链表情况；（2）首先给cpu-cir定一个初始值 假设为3；当开始作业调度时，系统时间clock=0；cir=3;创建时间为0的作业进入内存并请求分配内存。当循环一次clock+时，cir-；当cir!=0时此时根据tag的值来确定 作业请求能否得到满足。当tag=0时请求无法得到满足，进程阻塞无法进入内存。此时另cpu-sizei=jcb-size;当tag=1时请求得到满足。内存为进程分配空间并输出内存分配情况；当cir=0时cpu产生时钟中断。发送信号，唤醒没有满足内存分配

21、要求的进程，jcb-size=cpu-sizei;并将size的值传递给分配内存的算法。 处理完被阻塞的进程后，cir=3,等待产生下一个时钟中断现在程序还在调试过程中能否顺序运行出来还需要一定的时间。9.实践心得体会郑安琪：做了这次课程设计，大大提高了我的编写代码能力，和对整体程序框架理解和构思能力。虽然我们在这次课程设计中实现的操作系统的功能比较简单。但也是我们认真看书，查阅资料的成果。我觉得这样就是比较有意义了。最开始选这个题目是因为在上学期的实验中涉及过与进程管理相关的内容。寒假期间我们主要完成的是与进程调度有关的内容。查阅操作系统书本和相关资料后，我对linux2.6的O（1）调度算

22、法有了初步的认识。由于假期小组成员们都在家里。程序的编写和交流都不是很方便。我对小组成员任务的分工也不是很明确。所以假期的进度十分缓慢。程序的拼接和运行都有很多错误。开学来之后，又重新集合了成员们和我写的代码重新调试和运行。并且和成员们及时沟通顺利才将进程管理部分完成了。开学后的进展就比较快了。任务分工也较为明确。在和老师讨论过之后，老师建议我们写三级调度和模拟CPU运行环境。关于三级调度部分我们在后期实现了。我负责的是伙伴算法部分，以及作业调度和伙伴算法结合的部分。关于伙伴算法我最开始看操作系统书上的内容，一直都想不到到底用什么样的数据结构来模拟它的空闲链表。后来翻阅了大二上的课本数据结构C

23、语言版里面第八章有一章节就是详细讲解伙伴算法的，同过看书慢慢的领会最后成功写出来了。还有作业调度和内存分配的结合，拿到组员写好的作业调度程序后，我查阅了关于什么时候进行内存分配什么时候释放内存。并仔细了解了她所写的作业调度的过程并在作业调度算法中加入了关于内存分配的内容。总的来说这次课程设计我学到了很多。不像最开始那样程序运行不出来就非常烦躁。能够静下心来写代码，改代码。自己对各方面的知识也有了更全面的了解。施欣逸：通过本次的课程设计，感觉学到了很多。刚开始拿到组长分配的任务的时候，先是看了一遍书本，书上说到的一些时间分配，动态平衡等专有名词又不是写的清楚，只能去网上搜集相关的点来扩充和详细化

24、书上的概念。然后是把整体的算法分成一个个小块。从抽象化出每个数据结构，建立他们之间的联系，到实现过程中可能需要的细节函数。本来以为可以借鉴到第一次操作系统实验，但是并不是同一个思路。操作系统课程设计让我能更好的掌握各个数据结构的使用，自己的感觉还可以。但在和老师，助教交流的过程中，发现程序还不够完整。在于并没有模拟抽象一个可以支撑程序运行的环境，类似于CPU，时钟中断等。不能只停留在算法层面上，程序还需要改进。 在开始答辩的那一周，针对各种程序或者调试的问题，积极的寻找正确的突破点，由此意识到正确的思路对程序的实现有很大帮助。每当调试过程中出现问题时，先确定范围，再推算一遍。往往能找到之前思考

25、的不周到之处。 当然，虽然这次试验让我们学到了很多Linux2.6理论上知识，但是不可否认的是，团队意识的不可或缺。我们写程序的能力不是特别的突出，于是在某些部分才更需要思想的交流和碰撞。在每一次的揣摩概念和测试功能之下，稍许完整的程序才可以被写出来。 周晓梅：这次操作系统课程设计是我目前做过的最大的一个课程设计，一开始老师让选题的时候，因为知识掌握的不多，所以也很难下手。最终因为第一次实验是和进程调度有关，对进程了解还算多一点，所以我们小组确定了LINUX2.6进程管理与内存管理的仿真实现这个课题。对于这个课题，我们一开始也不知道怎么开始，头脑很空。所以寒假期间，我先把操作系统书上关于LIN

26、UX进程管理部分的内容看了几遍，上网查了一些关于O（1）算法的资料，然后初步开始了我们的课程设计。不过一开始的分工并不是很明确，大家一起写进程管理部分。组长确定好结构体之后，分给我们一个个小函数写，所以进程管理部分我只写了两个简单的函数。主要的O（1）算法函数和一些重要函数都是由另一位组员完成的。寒假因为大家都在家，网上交流毕竟没有当面交流那么方便，所以寒假我们课程设计的进度很慢，进程管理部分完成的还不是很完整，有很多错误。 开学第一周，我们每一天都泡在图书馆，继续我们的课程设计。完善进程管理部分，经过讨论对一些地方进行了修改。并把内存管理伙伴系统开了一个头。开学第二周，课程设计正式开始了。第

27、一天是汇报进度，第一组就是我们小组，经过汇报老师指出了我们的不足，就是分工不明确，没有结合作业调度和没有实现并发的问题。对于分工的问题，组长回去后就重新进行了分配，进程管理部分，因为大多都是另一位组员做的，所以剩下还未完善的继续交由她完成，而我和组长负责内存管理部分。我负责写作业调度，组长写伙伴算法，然后再由组长将两者连起来。一开始并不知道如何把作业调度和进程调度结合起来，尝试了很多，上网找了很多资料。最后只能写出用一个最简单的先来先来服务作业调度和进程调度结合起来。关于并发环境的问题，我们也请教了助教，但是目前还是未实现出来。总之，这一次课程设计，我最大的收获就是对O（1）算法和伙伴系统有了

28、更深的理解，对低级调度和高级调度的结合有了更深的理解，代码的编写能力也有了一些提高 参考文献：1费翔林，骆斌.操作系统教程M.北京:高等教育出版社,2014.2;2严蔚敏，吴伟民.数据结构:C语言版M.北京：清华大学出版社,2007;3应勤,孙兴芳.Linux编程实例解析M.北京:清华大学出版社,2009.1;4宋晓宇.C/C+程序设计M.北京:机械工业出版社,2014.1;5谢长生，叶志斌.Linux内存管理研究DB/OL.2005/2015; 核心代码：进程调度核心代码：void pcblist_ergodic(queue Q)/所在进程队列的遍历 int i; int j=0;linkl

29、ist q;q=Q.front-next;/指向队列的头的下一个指针;pcbnode *p2;coutn-当前就绪队列组-n;for(i=0;inext_pcb; /p2指向q优先级的第一个进程while(p2!=NULL) /遍历该优先级的队列 cout ID 进程优先级 时间片 所需时间 endl;cout pid prio counter needtime next; q=q-next;/指向下一个优先级k=j; /全局变量的赋值 coutnext; for(i=0;istatus_bit=1&p-prio=i)/如果当前位已有进程 并且p的优先级=此时q队头的优先级p1=p;p1-ne

30、xt=q-next_pcb;q-next_pcb=p1;if(q-status_bit=0&p-prio=i)/如果当前位没有进程 并且p的优先级=此时q队头的优先级p1=p;q-next_pcb=p1;q-status_bit=1;/为优先级队头q的status_bit位置1q=q-next;void deletepcb(queue &Q,pcbnode *p) /删除该优先级队列的进程linklist q;/各个优先级的队头链 q=Q.front-next;/第一个优先级0 while(q) /找到p的优先级所对应的优先级链/如果p的优先级=q的优先级 就跳出if(q-pcblink_nu

31、m=p-prio) break;q=q-next; /否则找下一个优先级q-next_pcb=p-next;/因为产生优先级相同的进程可能极小/直接从头删除if(q-next_pcb=NULL)q-status_bit=0;/当进程链为空，置status_bit为0;#define SCALE_PRIO(v, prio) max(v * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE) /计算时间片长度的函数#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)unsigned in

32、t task_timeslice(pcbnode *p) /计算时间片 if (p-staticprio staticprio); else /静态优先级在 121139之间 return SCALE_PRIO(DEF_TIMESLICE, p-staticprio); void Oone(queue &A,queue &E) /O（1）算法pcbnode *r;/进程类型的指针 linklist c;/优先级的队头链while(1)H:pcblist_ergodic(A);/就绪进程队列的遍历 if (k=0) /如果遍历为空的话 退出循环 break;pcblist_finder(A);/

33、找到第一位投入运行的优先级进程链printf(-n);r=current; /指向该优先级下的第一个进程while(r!=NULL) /不为空 投入运行Sleep(1000); /假设CPU上下文切换时间时间为1秒 move_into_cpu(r); /进入CPU处理 cout时间片余额为 : timeslice-所还需时间为: needtimeneedtime=0&r-timeslice0) /进程还在CPU中运行时 新创建进程实行抢占 if(r-needtime=500) /设置特定抢占的条件createpcb(A,1); /创建1个新进程 if(newcreate-prio=r-prio

34、) /原进程优先级大（数值小）不抢占time_t t;t=time(NULL); r-runtime=localtime(&t)-tm_hour*3600+localtime(&t)-tm_min*60+localtime(&t)-tm_sec;/当前时间记录r-usetime=r-runtime-r-entertime;/r已占用CPU的时间=r已运行时间-r进入CPU时间r-needtime=r-needtime-r-usetime;/r还需时间的处理coutn进程号pid的进程继续执行!endl;else /原进程优先级小（数值大） 抢占coutn进程号pid的进程抢占CPU执行!nee

35、dtime=r-needtime-100; /r所需时间变化r-timeslice-=100;/r时间余额变化if(r-timeslicetimeslice=0;if(r-needtimeneedtime=0;cout时间片余额为 : timeslice-所还需时间为: needtimeneedtimenext=NULL)/若改优先级就绪队列只有当前一个进程 则置位为0 ，/让出CPU 再次查找下一个置位为1的就绪队列，current指针指向该就绪队列进程 move_out_cpu(A,E,r);/让进程从A队列组进入E队列组 pcblist_finder(A);/遍历A r=current;

36、 else if(r-next!=NULL)/若该优先级就绪队列还有其他进程 则指向下一进程 r=r-next; /若A队列组没有进程，则交换A队列组和E队列组的指针c=E.front-next;E.front-next=A.front-next;A.front-next=c;内存管理核心代码：*伙伴系统*/avail0.m为可利用空间表,n为申请分配量,若有不小于n的空闲块, / 则分配相应的存储块,并返回其首地址;否则返回NULL。site allocpages(freelist *avail,int n)int i,k;site pa,pi,prev,suv;for(k=0;k=m&(*

37、avail)k.nodesizem)cout分配失败!请释放内存!front;suv=pa-next;if(prev=suv) /如果该子表只有一个空闲快则分配后该子表表为空(*avail)k.first=NULL;else /若该表不止一个空闲块 则删去块paprev-next=suv;suv-front=prev;(*avail)k.first=suv;/该表表头指针指向PA的下一个块for(i=1;(*avail)k-i.nodesize=n+1;i+)/剩余块插入相应2的k-i次幂的空闲链表pi=pa+(int)pow(2,k-i);pi-front=pi;pi-next=pi;pi-

38、kva=k-i;pi-tag=0;(*avail)k-i.first=pi;pa-tag=1;/pa被分配给用户 标志置为1 被占用pa-kva=k-(-i);return pa;/返回pa的首地址site buddy(site p)/起始地址为p,大小为2的k次方的内存块，其伙伴块的起始地址if(p-f)%(int)pow(2,p-kva+1)=0)/buddy(p,k)=p+2k 若p%2(k+1)=0return(p+(int)pow(2,p-kva);else /buddy(p,k)=p+2k 若p%2(k+1)=2kreturn(p-(int)pow(2,p-kva);void fr

39、eepages( freelist *free,site *p)/回收算法site s;s=buddy(*p);/s为P的伙伴块if(s-tag=1)/若P的伙伴块被占用 /直接插入相应的子链if(*free)(*p)-kva.first = NULL) / 若该子链表空 (*p)-front=(*p)-next=*p;(*free)(*p)-kva.first=*p;(*p)-tag=0; else / 若该子链表不为空 P插在表头 (*p)-next=(*free)(*p)-kva.first;(*p)-front=(*p)-next-front;(*p)-next-front=(*p);(*p)-front-next=(*p);(*free)(*p)-kva.first=(*p);(*p)-tag=0; while(s-f=0)&stag=0)/若P的伙伴块S没有被占用 且S的地址在有效范围内if(s-next=s-front)/如果该链表只有s一个块(*free)s-kva.first=NULL;/删除S块 该子链变为空else/如果该链表还有其他块 删除s块 表头为s的下一个节点 s-front-next = s-next; s-next-front =