操作系统原理课程设计-Linux2.6进程管理和内存管理

1、 操作系统原理课程设计实践报告全套设计加扣 3012250582题 目: Linux2.6进程管理和内存管理 姓 名: 学 院: 信息科技技术学院 专 业: 计算机科学技术系 班 级: 计科121 学 号:指导教师: 姜 2015年3月 18 日摘要通过学习Linux2.6系统的进程管理和内存管理，实现进程管理和内存管理的仿真实验。我们使用C#语言，采用面对对象的方式，并设计界面，然后通过代码实现各个模块，最后整合完成整个项目。实现的模块主要有Linux O(1)算法、伙伴系统算法、快表和LRU替换算法、虚存、页表等等。关键词：Linux 2.6，进程管理，内存管理一、理论基础 Linux是多

2、用户多任务操作系统，支持多道程序设计、分时处理和软实时处理。操作系统中的进程定义为程序执行的一个实例，都拥有属于自己的唯一的task_struct。每个进程都在CPU的虚拟内存中分配地址空间，并且每个进程的地址空间都是相互独立的。进程地址空间由允许进程使用的全部线性地址组成，每个进程所看到的线性地址集合是不同的，一个进程使用的地址与另外一个进程使用的地址这件没有关系，内核可以通过增加或删除某些线性区间来动态修改进程的地址空间。 CPU可以在用户模式下运行，也可以在内核模式下运行，当某个程序在用户模式下运行时，不能直接访问内核中的数据结构或程序，但是，当程序运行在内核模式时，可以访问用户态的数据

3、。对于某个执行的程序，多数的时间都处于用户模式，只有在需要内核提供服务时才会切换到内核模式，当内核满足了用户程序的需求后，再次返回到用户模式。 Linux系统中传统调度器对进程分别计算时间片，在进程的所有时间片用尽时，需要重新计算，现在的调度器只考虑进程的等待时间，也就是进程在就绪队列中已等待的时间。调度器的原理是按所分配的计算能力，想进程提供最大的公正性；每次调用调度器时，会选择等待时间最长的进程，把CPU提供给该进程，这样，进程的不公平性不会累积，不公平会均匀地分布到系统的所有进程中。 内存管理是内核中最重要同时也是最复杂的部分，需要处理器和内核之间的协作，内核在启动时通过调用start_

4、kernel()函数实现内存结构的初始化工作，之后内存管理的工作交由伙伴系统算法承担。伙伴算法采用页框作为基本内存区，适合于大块内存的请求，但是当有小内存的请求时，分配一整个页框是一种浪费，因此引入了新的数据结构来描述在同一页框内分配小内存区。 虚存空间管理以进程为基础，每个进程最大可以拥有3GB的私有虚存空间，进程的内核空间被所有进程共享，进程虚存空间由mm_struct结构和vm_area_struct结构描述。Linux系统采用分页机制实现虚存管理，每个进程都有自己独立的虚存地址空间，进程虚拟地址空间通过进程的页目录和页表实现与物理内存的映射。进程创建时分配一个虚拟地址空间，直到实际对物

5、理内存进行操作时才通过请页机制分配物理内存。二、目的及意义通过对Linux O(1)算法进行模拟，对就绪队列、active和expired队列进行模拟，对三级调度中的高级和低级调度进行模拟，对伙伴系统算法进行模拟，对虚存和物理内存进行模拟，对快表和LRU替换算法进行模拟，对页表进行模拟，加深对Linux2.6的进程管理和内存管理的了解，以及加强了团队意识。通过本次课程设计，我们能够深刻的理解Linux系统里的进程是如何运转调度的，连续空间的内存是如何分配的，物理内存和虚拟内存是如何映射的等等，从而了解到这些知识后，为我们设计或者改造出更好的进程管理和内存管理方案的想法提供了基础。 另外，熟悉C

6、#和面向对象语言设计。三、设计思想及设计功能说明本次课程设计主要分为两个部分：Linux的进程管理和内存管理。Figure 1 Linux进程管理和内存管理设计框图3.1 O(1)算法： 对于给定的CPU，调度程序选择active队列组的就绪队列位图中的第一个被设置的位，该位对应于优先级最高的就绪进程队列，然后选择此优先级就绪队列中的表头进程，它就是要被调度执行的进程。active队列组内的就绪队列上的进程都有剩余的时间片；expired队列组就绪队列上的进程都耗尽时间片。3.2 伙伴系统：Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下，避免碎片的产生。Linux采用一

7、种有效的方法来监视内存，保证在内核只要申请一小块内存的情况下，不会从大块的连续空闲内存中截取一段过来，从而保证了大块内存的连续性和完整性，也就是著名的伙伴系统。 伙伴系统的宗旨就是用最小的内存块来满足内核的对于内存的请求。在最初，只有一个块，也就是整个内存，假如为1M大小，而允许的最小块为64K，那么当我们申请一块200K大小的内存时，就要先将1M的块分裂成两等分，各为512K，这两分之间的关系就称为伙伴，然后再将第一个512K的内存块分裂成两等分，各位256K，将第一个256K的内存块分配给内存，这样就是一个分配的过程。我们可以用一个例子来描述这样一个过程：申请80K，50K，100K，60

8、K的内存。Figure 2 伙伴系统内存分配例图 我们设计一个buddy类，根据要分配的size和回收的物理内存首地址分配空间和回收空间。3.3 进程虚拟地址空间管理 进程虚存空间由mm_struct结构和vm_area_struct结构描述。设计时用了mm_struct类和vma类。Figure 3 进程虚存管理数据结构3.4 Linux页面替换算法（LRU） Linux页面替换算法是一种改进的最少使用频率策略。3.5快表 快表项包括页号和对应页框号，当把页号交给快表后，它通过和所有快表项比较，如果找到，则立即输出页框号并形成物理地址；如果找不到，再查内存中的页表以形成物理地址，同时将页号及

9、页框号登记到快表中；当快表已满且要登记新页时，系统需要淘汰旧的快表项。3.6 页表机制 Linux系统采用分页机制实现虚存管理，每个进程都有自己独立的虚拟地址空间，进程虚拟地址空间通过进程的页表实现与物理内存的映射。虚存以页为单位，大小等于物理页框。大小定义为4K，页面可以映射到任一物理页框。四、核心数据结构说明4.1 task_struct类class task_struct private int id;/ID号 private int priority;/优先级 private string state;/运行状态 private int hourIn,minuteIn,secondIn

10、;/进入时间 private int allTime;/程序所需要的时间private int size; /内存大小(以k为单位) private int addr_start; /逻辑地址首地址 private int addr_start_phy; /物理地址首地址 private int offset; /偏移量 public Boolean isInzhuncun = false; /是否在主存其各个元素意义如下：4.1.1 id进程ID号，是进程的唯一标识，数据类型为int，产生进程ID为0，1，24.1.2 priority进程优先级，标识进程的执行顺序，数据类型为int，优先级

11、越高的进程越先执行。4.1.3 state进程状态，标识进程现在的状态，数据类型为string，有未进入，就绪态，运行态，已结束几个状态4.1.4 hourIn,minuteIn,secondIn进程进入后备队列的时间（时分秒），数据类型为int4.1.5 allTime进程运行所需的总时间，数据类型为int4.1.6 size 进程运行所需的总内存大小，数据类型为int4.1.7 addr_start进程运行时的逻辑地址首地址，数据类型为int4.1.8 addr_start_phy进程运行时的物理地址首地址，数据类型为int4.1.9 offset 进程运行时的偏移量，数据类型为int4.

12、1.10 isInzhuncun标记该进程所需的data或者text是否在内存，数据类型为boolean；4.2后备队列类class MyQueue public void proList( List list,int n) /后备队列 Random rd = new Random(); int hour = DateTime.Now.Hour; int minu = DateTime.Now.Minute; int sec = DateTime.Now.Second; for (int i = 0; i = 60) sec -= 60; minu += 1; if (minu = 60) m

13、inu -= 60; hour += 1; task.setHourIn(hour); task.setMinuteIn(minu); task.setSecondIn(sec); task.setAllTime(rd.Next(2,5); task.setState(未进入); list.Add(task); 其函数意义如下：4.2.1 void proList( List list,int n)n个进程进入后备队列，函数返回值为void，函数参数为List list,int n,这里后备队列用一个task_struct类型的泛型List表示，相当于一个动态数组，在这个数组中就可以对数组中的

14、元素进行操作。4.3 CPU类class Cpu private ListList active=new ListList(); private ListList expired=new ListList(); public void initActive() public void initExpired() public void addActive(task_struct task,int n) public void addExpired(task_struct task, int n) public void delActive(int m,int n)/将activemn移除 pu

15、blic task_struct getActive(int m, int n)/得到activemn public List getList(int m)/得到active队列组中优先级为m的队列 其各个元素所代表的意义如下：4.3.1 activeCpu中的活跃进程队列组，类型为ListList，其相当于一个动态二维数组，每一维中放对应优先级的进程，相同悠闲级放在同一个队列中。4.3.2 expiredCpu中的过期进程队列组，类型为ListList，其相当于一个动态二维数组，每一维中放对应优先级的进程，相同悠闲级放在同一个队列中。4.3.3 void initActive()初始化act

16、ive队列组，返回类型为void，无参数。4.3.4 void initExpired()初始化expired队列组，返回类型为void，无参数。4.3.5 void addActive(task_struct task,int n)将优先级为n的进程加入到active队列组相应的队列中去，返回类型为void，参数为task_struct task,int n。4.3.6 void addExpired(task_struct task, int n)将优先级为n的进程加入到expired队列组相应的队列中去，返回类型为void，参数为task_struct task,int n。4.3.7

17、void delActive(int m,int n)将进程activemn从active队列组中去除，返回类型为void，参数为int m,int n。4.3.8 task_struct getActive(int m, int n)得到activemn，返回类型为task_struct，参数为int m, int n4.3.9 List getList(int m)得到active队列组中优先级为m的队列，返回类型为List，参数为m4.4 buddy类class Buddy public int BBuddy = new int10 2, 4, 8, 16, 32, 64, 128, 2

18、56, 512, 1024 ; /分区大小 2的k次幂public int free1 = new int10 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ;/空闲分区的个数，初始内存大小1024 public static int, use = new int100, 2; /已分配分区表 最多为100个进程分配 记录已分配分区大小，内存首地址 public int, free_addr = new int10, 50; /空闲分区的首地址 i,j表示2的i+1次方大小的空闲分区的第j+1个分区的首地址 int maxsize = 9;/最大空闲分区 初始为1024 int u

19、senum = 0; /进程数 初始为0其各个元素所代表的意义如下：4.4.1 BBuddy 10定义一个长度为10的数组，表示分区的大小。因为程序在内存分配的大小是2的n次幂，所以用这个数组表示单个程序的内存分布的大小。由于我们虚拟的内存大小为1GB，所以数组中最大的数为1024。数据类型为 int，数组长度为10，初始化内容是 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 。4.4.2 free1 10定义一个长度为10的数组，表示空闲分区的个数。初始化中，数组中最后一个数字为1，表示有且只有一个分区空闲，值为2的数组下标的幂。数据类型为 int，数组长

20、度为10，初始化内容是 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 。4.4.3 use 100, 2已分配分区表 最多为100个进程分配 记录已分配分区大小，内存首地址。数据类型为int，是一个1002的二维数组。4.4.4 free_addr10, 50空闲分区的首地址 i,j表示2的i+1次方大小的空闲分区的第j+1个分区的首地址。数据类型为int，是一个1050的二维数组。4.4.5 maxsize表示内存中最大的空闲分区，初始为9，和数组BBuddy相对应.随着内存的分配，BBuddymaxsize表示当前最大的可分配的内存。数据类型为int。4.4.6 usenum表

21、示当前内存中的进程个数，初始化为0。数据类型为int。4.5 mm_struct类class mm_struct private static int addr_base = 0; LinkedList vmalist = new LinkedList(); /虚拟内存链表 public static LinkedList pgdlist = new LinkedList();/指向页表 public Boolean add_one_vma(task_struct task,Buddy buddy) /该页表，改 其各个元素所代表的意义如下：4.5.1 addr_base记录虚存当前的可分配的

22、首地址，初始化为0。数据类型为statc int，保持每次使用该变量时都能取到可分配的首地址。4.5.2 vmalist意在指向虚拟内存，其实是一个以vma为节点的一个链表，保存虚存内容。数据类型为LinkedList。4.5.3 pgdlist意在指向页表，其实是一个以pgd为节点的一个链表，保存页表内容。数据类型为static LinkedList。4.5.4 add_one_vma增加进程时修改页表的函数，函数名为add_one_vma，函数返回类型为boolean，表示是否分配成功。参数为task_struct和Buddy。4.6 vma类class vma public vma(in

23、t id, int size)； public vma() /* 计算所占页面的数量*/ private int size;/内存大小 private int id; /进程号 private int vm_start; /vma的起始地址 private int vm_end;/vma的终止地址 private int count;/所占页面个数其各个元素所代表的意义如下：4.6.1 vma(int id,int size)vma构造函数之一，参数为id和size。函数权限为public；4.6.2 vma（）vma无参构造函数。函数权限为public。4.6.3 size表示进程在虚拟内存

24、中的大小。数据类型为int。4.6.4 id表示进程的id。数据类型为int。4.6.5 vm_start 表示该进程在虚拟内存的首地址。数据类型为int。4.6.6 vm_end表示该进程在虚拟内存的尾地址。数据类型为int。4.6.7 count表示该进程在虚拟内存所占的页面数。数据类型为int。4.7 pgd类class pgd private int page_Table;/逻辑页表号 private int page_frame;/物理页框号 public int getPage_Table() public int getPage_frame()其各个元素所代表的意义如下：4.7.

25、1 page_Table表示逻辑页表号，存放逻辑页表号。数据类型为int。4.7.2 page_frame表示物理页框号，存放物理页框号。数据类型为int。4.7.3 getPage_Table()用作取逻辑页表号的函数，返回类型为int。4.7.4 getPage_frame()用作取物理页框号的函数，返回类型为int。4.8 TLB类class TLB const int sum = 10; /TLB大小 private int page_Table; /逻辑页表号 private int page_frame;/物理页框号 public static LinkedList list =

26、new LinkedList(); public void LRU(task_struct task)/使用LRU实现替换 其各个元素所代表的意义如下：4.8.1 sum表示该TLB的大小，初始值为10，且不能改变。数据类型为int。4.8.2 list以int为节点的保存TLB的内容。数据类型为LinkedList。4.8.3 page_Table 表示逻辑页表号。数据类型为int。4.8.4 page_frame表示物理页框号。数据类型为int。4.8.5 LRU(task_struct task)LRU的替换TLB项的函数，函数类型为void，函数函数为task，函数权限为public。

27、五、核心算法流程5.1 进程管理（O(1)算法） 对于给定的CPU，调度程序选择active队列组的就绪队列位图中的第一个被设置的位，该位对应于优先级最高的就绪进程队列，然后选择此优先级就绪队列中的表头进程，它就是要被调度执行的进程。active队列组内的就绪队列上的进程都有剩余的时间片；expired队列组就绪队列上的进程都耗尽时间片。5.2 伙伴系统算法伙伴系统的大致框架如下：内存分配：内存回收：5.3 请求分页虚存地址转换5.4 LRU页面替换算法Linux页面替换算法是一种改进的最少使用频率策略。页表设置一个age，根据内存中当前页面的age来决定是否将其替换。每个调入内存的页面都有一

28、个其实年龄，其默认值为3.当页面长久没有被访问，会变老。系统规定，页面每次被访问时其age增加3。kswapd周期性扫描，每个页面减1，直到减到0。我们没有设置kswapd，直接在每次检测页面命中与否时减1。显然age越小，页面越老，被替换的次序越前。age越大，此页被使用的频率就高，也就越不适合替换。六、开发调试及运行环境6.1 开发调试visual studio 2010，visual studio 2013，windows7/8.16.2 运行环境windows xp/windows2007/windows8等七、功能说明及测试数据分析开始界面：（特别说明：由于我们的进程是实时运行的，所

29、以截图很难截，只通过QQ截得过程中的几张图。）在进程数输入1，即生成了一个进程。该进程id号为0，优先级为1，进入时间为14:18:30，状态为未进入，内存大小为76.点击“O(1)算法”按钮，进程比较进入时间和当前时间，选择运行，在此之前给他分配了76KB的内存，物理基址和逻辑基址都为0.快表中按照FIFO的算法进行替换。程序结束后，回收内存，内存条显示消失，即回收内存成功。当输入进程为5时：随机生成5个进程。所有进程开始运行，并且分配地址。运行结束后显示如上。八、存在问题（改进及其他设想）8.1 存在问题1) 没有模拟并发环境，将内存管理和进程管理设计成两个独立模块。2) 任务分配不合理，

30、组长没有统一公用类、数据类型等3) 理论和实际的结合不是令人满意，仿真不够彻底，这与实践和能力有直接关系。4) 在模拟内存时，由于系统时钟值太大，要显示页面替换等的变化几率很小，所有我们将偏移量值设定成以K为单位。8.2 改进和其他思想1) 因为操作系统强调的是并发并行，在实现模拟并发环境这一难题是使用C#多线程。2) 对于任务分配和团队管理，我们可以遵守软件工程中的瀑布模型，在充分认知需求的情况下进行编程。3) 关于理论和实际编程，我们有舍有取，取其主干，大致模拟了整个进程管理和内存管理系统。九、实践体会及心得1.郑鹏（组长）：做了这次操作系统的课程设计，我感受良多，特别是作为组长这一方面。

31、操作系统课程设计是我第三次做操作系统仿真的实验，但这一次的代码量和逻辑分析都比上两次要多，而且我要统筹三个人的工作量和设计整个框架，这无疑是一项新的挑战。一方面是对理论知识的了解，一方面是实际程序设计时的各项选择、舍取，任务分配，所以这对一个组长的要求是很高的。但是，我觉得我没有尽好一个组长的职责。寒假的时候，我只是粗略的分配了一下任务，让组员看相关部分的书，了解他们自己部分的东西。寒假结束后，我们到了学校，才真正开始写代码。最后才发现时间很紧，工作量也很大。虽然已经完成了代码，但是我从一些写代码、整合的问题中得到很多体会。在编写的代码的时候一定要注意命名的规范，提高代码的复用性，也防止以后别

32、人对你的代码进行修改，或者别人拿去用的时候遇到重复命名的问题，特别是全局变量或常量的命名，因为这种变量在以后一旦遇到问题，要进行大量的修改，会导致程序运行结果不正确，而且问题也比较难找到。参数的类型也要统一，一些公用的类，如PCB要在写代码前提供给各个组员。另外，及时的讨论是非常有必要的，因为一旦你修改了某个函数的返回值类型或者参数类型，结构体的定义等等，你的同伴在编写之后的函数时，会遇到很多问题，导致工作量剧增。在语言选择上，我们选择了C#，事实证明C#是一门十分方便好用的语言。我们将各个部件和功能都封装成了类，有利于后期的修改和维护。后来通过寒假报告的答辩，我们从姜老师那儿深切的体会到：在

33、操作系统中，所有的问题都要和进程的并发，作业的并发联系起来，孤立的算法模拟，是单一的不可信的。总之，一个好的团队，扎实的理论知识，娴熟的编码技术才能完成一件优秀的作品。虽然我在本次课程设计上没有很具体的仿真Liunx的进程管理和内存管理，但是我的理论知识更加扎实了，这无疑对以后，无论是考研保研还是工作面试都是很有帮助的。2.郑翔（组员）：通过这次操作系统课程设计，我知道了设计的重要性。在一次项目中，前期有一个良好的设计，会使你事半功倍。设计是编码的前提，在这次操作系统课程设计中，我前期由于没有对Linux系统进程管理进行充分的了解，浪费了很多的时间，对代码进行了很多的修改。在这次课程设计中，我

34、也体会到了团队协作的重要性。在一个团队中，每人负责一部分的功能实现，但是又不能是散乱的部分，必须各人都要有共通的东西，比如公共的数据结构什么的，在这次课程设计中，就是由于前期没有进行大局的设计，显得我们最后的代码显得比较散乱。3.王超（组员）：在这次课程设计中，我着实体会到了许多。我负责的部分是内存管理中的伙伴系统，伙伴系统中的分配函数和回收函数，都需要熟练掌握其数据结构，算法思想，以至于能够熟练运用。伙伴系统的宗旨就是用最小的内存块来满足内核的对于内存的请求。在最初，只有一个块，也就是整个内存，假如为1M大小，而允许的最小块为64K，那么当我 们申请一块200K大小的内存时，就要先将1M的块

35、分裂成两等分，各为512K，这两分之间的关系就称为伙伴，然后再将第一个512K的内存块分裂成两等分为256K，将第一个256K的内存块分配给内存，这样就是一个分配的过程。而回收的过程则是释放占用块，若能向上合并则不断向上合并。我利用了数组来实现伙伴系统算法的功能，定义一个空闲分区数组和已分配分区数组，这2个数组都为2维数组，分别记录空闲分区块和已分配分区块的大小和内存地址。这样，在实现伙伴系统算法的功能就转化为对数组的操作。在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定距离的。一切问题必须要靠自己一点一滴的解决，而在解决的过程当中你会发现自己在飞速的提升。程序设计是一个很灵活

36、的东西，它反映了你解决问题的逻辑思维和创新能力，是一个设计的灵魂所在。因为我的编程基础比较薄弱，我所负责的部分是较少的，而且其他组员使用的是C#语言来开发，而我一开始使用了C语言，后来在组长的帮助下改成了C#语言，在认识到自己不足的同时我也学习了一些C#编写图形界面的知识。对于一个算法不仅要了解其原理，也需要在编写前考虑好设计好它的数据结构，对于一个项目而言，更需要考虑各模块整合时的可操作性。感谢这次实践给我提供了一个认识到自己不足以及不断完善自我的机会，也感谢组长组员和老师们的帮助与指导。十、参考文献1 费翔林, 骆斌. 操作系统教程M. 北京:高等教育出版社, 2014.2 内存空间分几部

37、分：代码段、数据段，栈，堆 (收集整理） - YEYUANGEN的专栏 - 博客频道 - CSDN.NET, /yeyuangen/article/details/67665673 郑阿奇, 孙承龙. Linux内核精选M. 北京:电子工业出版社, 2013.4 孙钟秀. 操作系统教程M. 北京:高等教育出版社, 2008.5 伍俊良.C#程序应用与开发教程M.机械工业出版社,2009.6 戴宗友,张伍荣,杨辉.C#程序设计实训M.清华大学出版社,2009.十一、带注释的核心部分源码class Cpu private ListList active=new

38、 ListList(); private ListList expired=new ListList(); public void initActive() for (int i = 0; i = 10; i+) List task=new List(); active.Add(task); public void initExpired() for (int i = 0; i = 10; i+) List task = new List(); expired.Add(task); public void addActive(task_struct task,int n) activen.Ad

39、d(task); public void addExpired(task_struct task, int n) expiredn.Add(task); public void delActive(int m,int n)/将activemn移除 activem.Remove(activemn); class MyQueue public void proList( List list,int n,mm_struct mm)/后备队列 Random rd = new Random(); int hour = DateTime.Now.Hour; int minu = DateTime.Now.

40、Minute; int sec = DateTime.Now.Second; for (int i = 0; i = 60) sec -= 60; minu += 1; if (minu = 60) minu -= 60; hour += 1; task.setHourIn(hour); task.setMinuteIn(minu); task.setSecondIn(sec); task.setAllTime(rd.Next(3,10); task.setState(未进入); task.setSize(rd.Next(65, 100); /内存大小 1-100 task.setOffset

41、(0); /偏移量为0 list.Add(task); class task_struct private int id; /ID号 private int priority; /优先级 private string state; /运行状态 private int hourIn,minuteIn,secondIn; /进入时间 private int allTime; /程序所需要的时间 /*添加*/ private int size; /内存大小(以k为单位) private int addr_start; /逻辑地址首地址 private int addr_start_phy; /物理地址首地址 private int offset; /偏移量 public Boolean isInzhuncun = false; /是否在主存 private int pageNow; /现在的页号 public int getPageCount() /计算所占页面数 return this.offset + this.addr_start_phy+1;/物理内存+偏移量 class Buddy public int BBuddy = new int10 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 ; /分区大小 2的k次幂 p