Linux内存管理与进程调度策略

《嵌入式操作系统》课程论文Linux内存管理与进程调度策略学号PB092028109班级09计算机科学与技术姓名王华联系电话13027824983Email：810946067@qq.com学院贵州大学人民武装学院2010年06月29日贵州大学人民武装学院《嵌入式操作系统》论文2Linux内存管理与进程调度策略【摘要】内存是Linux内核所管理的最重要的资源之一，内存管理系统是操作系统中最为重要的部分。对于Linux的学习和熟悉Linux的内存管理是非常重要的。进程是运行于虚拟地址空间的一个程序。可以说，任何在Linux系统下运行的程序都是进程。Linux系统中包括交互进程和批处理进程。交互进程是由Shell控制和运行的，既可以在前台运行，也可以在后台运行。批处理进程不属于某个终端，被提交到一个队列中以便顺序执行。大多数的进程都需要虚拟内存。因此，Linux进程的学习也是至关重要的。【关键词】linux;进程调度；调度策略；内存管理引言在Intel80X86CPU中，程序在寻址过程中使用的是由段和偏移值构成的地址。该地址并不能直接用来寻址物理内存地址，因此被称为虚拟地址。为了能寻址物理内存，就需要一种地址变换机制将虚拟地址映射或变换到物理内存中，这种地址变换机制就是内存管理的主要功能之一（内存管理的另外一个主要功能是内存的寻址保护机制。。虚拟地址通过段管理机制首先变换成一种中间地址形式—CPU32位的线性地址，然后使用分页管理机制将此线性地址映射到物理地址。为了弄清Linux内核对内存的管理操作方式，我们需要了解内存分页管理的工作原理，了解其寻址的机制。分页管理的目的是将物理内存页面映射到某一线性地址处。在分析本章的内存管理程序时，需明确区分清楚给定的地址是指线性地址还是实际物理内存的地址。内存管理以提高内存利用率和扩大内存量为主要目标，设计了各种内存分配管理方法、算法和数据结构，通过分析比较，得到不同管理方法的异同。同时，以地址映射为辅线条，描述分区、分页、分段、请求分页和请求分段的映射原理。贵州大学人民武装学院《嵌入式操作系统》论文3Linux内存管理一个操作系统的内存管理方式很大程度上决定了它的效率,时间与空间的对立统一在内存管理上体现得最为明显,首先,分配/释放内存是一个发生频率很高的操作,所以它要求有一定的实时性,另外,内存又是一种非常宝贵的资源.所以要尽量减少内存碎片的产生.Linux采用了伙伴系统算法来管理内存,即把内页按2^0,2^1,2^2…2^10大小进行分组.每次分配内存时,从相应大小的池中分配内存,然后再把余下的内存分配给它的下一级缓存池.如右图首先,它会到相应大小的(2^0)的空闲链表入队.判断相邻块的空闲情况,此时,因为第三个是空闲的,所以可以合并为一块2^1的空闲块.继续判断2^1链中相邻块是否是空闲的,上图中可以将2^1的两个块合成一个大块,然后继续判断2^2中是否可以继续合并,依次类推.上述内容,涉及到几个位操作,分析如下:1:得到相邻块的的起始page:buddy1=base+(page_idx^(1order))贵州大学人民武装学院《嵌入式操作系统》论文4align=center根据上面的分析,可得知page_idx本身就是order位对齐的,所以,它的低order位为零.此外,再根据0与任何数异或值不变,1与数异或都相反的规律,我们可以得知,位运算结果只跟order+1位有关.据此就可以计算出它的“伙伴块”2:得到高一级空闲链的首空闲块序号：mask=1;page_idx&=mask;只要按着高一级链表的order位对齐就行了3:得到空闲块在高一级链表中对应的分配位图位index=1;在前面分析过对应位的计算方法，在高一级空闲链中的位对应当前除二其实这一个过程在操作系统设计中也叫“内存拼凑”，就是把剩余小内存，拼成连续的大内存，以满足某些程序的需要。在Intel80x86体系结构中，Linux内核的内存管理程序采用了分页管理方式。利用页目录和页表结构处理内核中其它部分代码对内存的申请和释放操作。内存的管理是以内存页面为单位进行的，一个内存页面是指地址连续的4K字节物理内存。通过页目录项和页表项，可以寻址和管理指定页面的使用情况。在Linux0.11的内存管理目录中共有三个文件，如列表10-1中所示：贵州大学人民武装学院《嵌入式操作系统》论文5其中，page.s文件比较短，仅包含内存页异常的中断处理过程（int14）。主要实现了对缺页和页写保护的处理。memory.c是内存页面管理的核心文件，用于内存的初始化操作、页目录和页表的管理和内核其它部分对内存的申请处理过程。一·内存管理的硬件机理1内存分页管理机制在Intel80x86的系统中，内存分页管理是通过页目录表和内存页表所组成的二级表进行的。见图10-1所示。“那么，一个线性地址如何使用这两个表来映射到一个物理地址上呢？”。为了使用分页机制，一个32位的线性地址被分成了三个部分，分别用来指定一个页目录项、一个页表项和对应物理内存页上的偏移地址，从而能间接地寻址到线性地址指定的物理内存位置。见图10-2所示。贵州大学人民武装学院《嵌入式操作系统》论文6在内存管理的函数中，大量使用了从线性地址到实际物理地址的变换计算。对于给定一个进程的线性地址，通过图10-2中所示的地址变换关系，我们可以很容易地找到该线性地址对应的页目录项。若该目录项有效（被使用），则该目录项中的页框地址指定了一个页表在物理内存中的基址，那么结合线性地址中的页表项指针，若该页表项有效，则根据该页表项中的指定的页框地址，我们就可以最终确定指定线性地址对应的实际物理内存页的地址。反之，如果需要从一个已知被使用的物理内存页地址，寻找对应的线性地址，则需要对整个页目录表和所有页表进行搜索。若该物理内存页被共享，我们就可能会找到多个对应的线性地址来。图10-3用形象的方法示出了一个给定的线性地址是如何映射到物理内存页上的。对于第一个进程（任务0），其页表是在页目录表之后，共4页。对于应用程序的进程，其页表所使用的内存是在进程创建时向内存管理程序申请的，因此是在主内存区中。贵州大学人民武装学院《嵌入式操作系统》论文7一个系统中可以同时存在多个页目录表，而在某个时刻只有一个页目录表可用。当前的页目录表是用CPU的寄存器CR3来确定的，它存储着当前页目录表的物理内存地址。但在本书所讨论的Linux内核中只使用了一个页目录表。在图10.1中我们看到，每个页表项对应的物理内存页在4G的地址范围内是随机的，是由页表项中页框地址内容确定的，也即是由内存管理程序通过设置页表项确定的。每个表项由页框地址、访问标志位、脏（已改写）标志位和存在标志位等构成。表项的结构可参见图10-4所示。2Linux中物理内存的管理和分配有了以上概念，我们就可以说明Linux进行内存管理的方法了。但还需要了解一下Linux0.11内核使用内存空间的情况。对于Linux0.11内核，它默认最多支持16M物理内存。在一个具有16MB内存的80x86计算机系统中，Linux内核占用物理内存最前段的一部分，图中end标示出内核模块结束的位置。随后是高速缓冲区，它的最高内存地址为4M。高速缓冲区被显示内存和ROMBIOS分成两段。剩余的内存部分称为主内存区。主内存区就是由本章的程序进行分配管理的。若系统中还存在RAM虚拟盘时，则主内存区前段还要扣除虚拟盘所占的内存空间。当需要使用主内存区时就需要向本章的内存管理程序申请，所申请的基本单位是内存页。整个物理内存各部分的功能示意图如图10-5所示。贵州大学人民武装学院《嵌入式操作系统》论文8为了节约物理内存，在调用fork()生成新进程时，新进程与原进程会共享同一内存区。只有当其中一个进程进行写操作时，系统才会为其另外分配内存页面。这就是写时复制的概念。page.s程序用于实现页异常中断处理过程（int14）。该中断处理过程对由于缺页和页写保护引起的中断分别调用memory.c中的do_no_page()和do_wp_page()函数进行处理。do_no_page()会把需要的页面从块设备中取到内存指定位置处。在共享内存页面情况下，do_wp_page()会复制被写的页面（copyonwrite，写时复制），从而也取消了对页面的共享。3Linux内核对线性地址空间的使用分配在阅读本章代码时，我们还需要了解一个执行程序进程的代码和数据在虚拟的线性地址空间中的分布情况，参见下面图所示。每个进程在线性地址中都是从nr*64M的地址位置开始（nr是任务号），占用线性地址空间的范围是64M。其中最后部的环境参数数据块最长为128K，其左面起始堆栈指针。在进程创建时bss段的第一页被初始化为全０。4关于写时复制（copyonwrite）机制当进程A使用系统调用fock创建一个子进程B时，由于子进程B实际上是贵州大学人民武装学院《嵌入式操作系统》论文9父进程A的一个拷贝，因此会拥有与父进程相同的物理页面。也即为了达到节约内存和加快创建速度的目标，fork()函数会让子进程B以只读方式共享父进程A的物理页面。同时将父进程A对这些物理页面的访问权限也设成只读。详见memory.c程序中的copy_page_tables()函数。这样一来，当父进程A或子进程B任何一方对这些以共享的物理页面执行写操作时，都会产生页面出错异常(page_faultint14)中断，此时CPU会执行系统提供的异常处理函数进程是运行于虚拟地址空间的一个程序。可以说，任何在Linux系统下运行的程序都是进程。Linux系统中包括交互进程和批处理进程。交互进程是由Shell控制和运行的，既可以在前台运行，也可以在后台运行。批处理进程不属于某个终端，被提交到一个队列中以便顺序执行。大多数的进程都需要虚拟内存。存储管理子系统是操作系统中最重要的组成部分之一。在早期计算时代，由于人们所需要的内存数目远远大于物理内存，因此设计出了各种各样的策略来解决此问题，其中最成功的就是虚拟内存技术，它使得系统中有限的物理内存竞争进程所需内存空间得到满足。虚拟内存通过在各个进程之间共享内存，而使系统看起来有多于实际内存的内存容量。Linux支持虚拟内存,就是使用磁盘作为RAM的扩展，使可用内存相应地有效扩大。核心把当前不用的内存块存到硬盘，腾出内存给其它目的。当原来的内容又要使用时，再读回内存。运行于Linux的程序只看到大量的可用内存，而不关心哪部分在磁盘上。当然，读写硬盘比真的内存慢(大约慢千倍)，所以程序运行较慢。用做虚拟内存的这部分硬盘叫对换空间。虚拟内存技术不仅仅让我们可以使用更多的内存，它还提供了下面这些功能：1.巨大的寻址空间:操作系统让系统看上去有比实际内存大得多的内存空间。虚拟内存可以是系统中实际物理空间的许多倍。每个进程运行在其独立的虚拟地址空间中，这些虚拟空间相互之间都完全隔离开来，所以进程间不会互相影响。同时，硬件虚拟内存机构可以将内存的某些区域设置成不可写，这样可以保护代码与数据不会受恶意程序的干扰。贵州大学人民武装学院《嵌入式操作系统》论文102.公平的物理内存分配:内存管理子系统允许系统中每个运行的进程公平地共享系统中的物理内存。3.共享虚拟内存:尽管虚拟内存允许进程有其独立的虚拟地址空间，但有时也需要在进程之间共享内存。例如，有可能系统中有几个进程同时运行BASH命令外壳程序。为了避免在每个进程的虚拟内存空间内都存在BASH程序的拷贝，较好的解决办法是系统物理内存中只存在一份BASH的拷贝，并在多个进程间共享。动态库则是另外一种进程间共享执行代码的方式。共享内存可用来作为进程间通信(IPC)的手段，多个进程通过共享内存来交换信息。Linux支持SYSTEMV的共享内存IPC机制。4.进程的保护:系统中的每一个进程都有自己的虚拟地址空间。这些虚拟地址空间是完全分开的，这样一个进程的运行不会影响其它进程，并且硬件上的虚拟内存机制是被保护的，内存不能被写入。这样可以防止迷失的应用程序覆盖代码的数据