操作系统内存管理.docx

《操作系统内存管理.docx》由会员分享，可在线阅读，更多相关《操作系统内存管理.docx（8页珍藏版）》请在三一办公上搜索。

1、操作系统内存管理内存管理 1. 分页内存管理方案 分页的最大作用就在于：使得进程的物理地址空间可以是非连续的。物理内存被划分为一小块一小块，每块被称为帧(Frame)。分配内存时，帧是分配时的最小单位，最少也要给一帧。在逻辑内存中，与帧对应的概念就是页(Page)。 每个操作系统都有自己的方法来保存页表。绝大多数都会为每个进程分配一个页表。现在由于页表都比较大，所以放在内存中(以往是放在一组专用寄存器里)，其指针存在进程控制块(PCB)里，当进程被调度程序选中投入运行时，系统将其页表指针从进程控制块中取出并送入用户寄存器中。随后可以根据此首地址访问页表。 页表的存储方式是TBL(Transla

2、tion look-aside buffer, 翻译后备缓冲器)+内存。TBL实际上是一组硬件缓冲所关联的快速内存。若没有TBL，操作系统需要两次内存访问来完成逻辑地址到物理地址的转换，访问页表算一次，在页表中查找算一次。TBL中存储页表中的一小部分条目，条目以键值对方式存储。 图1. 带TLB的分页硬件 2. 分段内存管理方案 采用分页内存管理有一个不可避免的问题：用户视角的内存和实际内存的分离。设想一段main函数代码，里面包含Sqrt函数的调用。按照编写者的理解，这段代码运行时，操作系统应该分配内存给：符号表(编译时使用)，栈(存放局部变量与函数参数值)，Sqrt代码段，主函数代码段等。

3、这样，编写者就可以方便地指出：函数sqrt内存模块的第五条指令，来定位一个元素。而实际上，由于采用Paging的管理方式，所有的一切都只是散落在物理内存中的各个帧上，并不是以编写者的理解来划分模块。 图2. 逻辑地址空间 Segmentation的内存管理方式可以支持这种思路。逻辑地址空间由一组段组成。每个段都有名字和长度。地址指定了段名称和段内偏移。因此用户通过两个量来指定地址：段名称和偏移。段是编号的，通过段号而非段名称来引用。因此逻辑地址由有序对构成： () 段偏移d因该在0和段界限之间，如果合法，那么就与基地址相加而得到所需字节在物理内存中的地址。因此段表是一组基地址和界限寄存器对。

4、图3. 页式存储管理中的地址转换机构 3. 内存分配算法 在内存管理中存在两类算法：一类是内存分配算法，一类是页面置换算法。内存分配算法是指怎么从连续的逻辑地址空间上分配内存地址给进程。 3.1 首次适应算法 使用该算法进行内存分配时，从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。 该算法倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内 存空间创造了条件。缺点在于低址部分不断被划分，留下许多难以

5、利用、很小的空闲区，而每次查找又都从低址部分开始，这无疑会增加查找的开销。 3.2 循环首次适应算法 该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区开始查找，直至 找到一个能满足要求的空闲分区，并从中划出一块来分给作业。该算法能使空闲中的内存分区分布得更加均匀，但将会缺乏大的空闲分区。 3.3 最佳适应算法 该算法总是把既能满足要求，又是最小的空闲分区分配给作业。 为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看， 该算法似乎是最优的，但事实上

6、并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序， 这也带来了一定的开销。 3.4 最差适应算法 最差适应算法中，该算法按大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲分区中 分配。很显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。这种分配方法初看起来不太合理，但它也有很强的直观 吸引力：在大空闲区中放入程序后，剩下的空闲区常常也很大，于是还能装下一个较大的新程序。 最坏适应算法与最佳适应算法的排序正好相反，它的队列指针总是指向最大的空闲区，在进行分配时，总是从最大的空闲区开始查寻。 该算法克服了最

7、佳适应算法留下的许多小的碎片的不足，但保留大的空闲区的可能性减小了，而且空闲区回收也和最佳适应算法一样复杂。 基于局部性原理,应用程序在运行之前并不必全部装入内存,仅需将当前运行到的那部分程序和数据装入内存便可启动程序的运行,其余部分仍驻留在外存上。当要运行的指令或访问的数据不在内存时,再由操作系统通过请求调入功能将它们调入内存,以使程序能继续运行。如果此时内存已满,则还需通过置换功能,将内存中暂时不用的程序或数据调至盘上,腾出足够的内存空间后,再将要访问的程序或数据调入内存,使程序继续运行。 请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请

8、求分页是目前最常用的一种实现虚拟存储器的方法。 在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。 4. 页面置换算法 页面置换算法是指线性地址转化为物理地址的过程中的算法，由于实际物理内存有限，一个进程的所有逻辑页并不是都会被映射到实际的物理帧上，而是分配一定数量的物理帧，之后通过一定的页面置换算法把需要调入内存的逻辑页调入内存。 4.1 FIFO页置换 最简单的页面置换算法是先入先出法。这种算法的实质是，总是选择在主存中停留时

9、间最长的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。 这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。 FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。 4.2 最优置换 这是一种理想情况下的页面置换算法，但实际上是不可能实

10、现的。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问，而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。 4.3 LRU页置换 FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面

11、的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法。 LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。 LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法： 1). 计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每

12、次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做，不仅要查页表，而且当页表改变时要维护这个页表中的时间，还要考虑到时钟值溢出的问题。 2). 栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，

13、用不着查找，因为尾指针指向栈底，其中有被置换页。 因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。 一种LRU近似算法是最近未使用算法。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。 4.4 近似LRU算法 很少有计算机系统能提供足够的硬件来支持真正的LRU页置换。有的系统不提供任何支持，因此必须使用其它置换算法。然而，许多系统都通过

14、引用位方式提供一定的支持，页表内的每项都关联着一个引用位。每当引用一个页时，相应页表的引用位就被硬件置位。 开始，操作系统会将所有引用位都清零。随着用户进程的执行，与引用相关联的引用位被硬件置位。之后，通过检查引用位，能够确定哪些页使用过而哪些页未使用过。虽然不知道使用顺序，但是知道哪些页用过而哪些页未用过。这信息是许多近似LRU算法的基础。 1）附加引用位算法。在一个页的引用位保留8位，初始为0000 0000，第一次被使用，则1000 0000，第二次未被使用，则0100 0000.以此类推。找到这8位化为10进制后最小的页置换。 2）二次机会算法。第二次机会算法的基本思想是与FIFO相同

15、的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。 第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的

16、访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。 3）增强型二次机会算法。将引用位和修改位作为有序对，：表示未被引用和修改，则说明是最佳的LRU置换页；：最近没有使用但修改过不是很好，因为在置换之前需要将也写出到磁盘；：最近使用过但没有修改过它很可能很快又要被使用；最近使用过且修改过有可能很快又要被使用，且置换之前需要将页写出到磁盘。这种方法与简单时钟算法的主要差别是这里给那些已经修改过的页以更高的级别，从而降低了所需I/O的数量。 4.5 LFU置换算法 最近最少使用算法要求置换计数最小的页。这种选择的理由是活动页应该有更大的引用次数。这种算法会产生如下问题：一个页在进程开始时使用很多，但以后就不再使用。由于其使用过很多，所以它有较大的次数。所以即使不再使用仍然会在内存中。解决方法之一是定期将次数寄存器右移一位，以形成指数衰减的平均使用次数。 4 .6页缓冲算法 除了特定页置换算法外，还经常采用其它措施。例如，系统通常保留一个空闲帧 缓冲池。当出现页错误时，会像以前一样选择一个牺牲帧。然而，在牺牲帧写出之前，所需要的页就从缓冲池中读到空闲内存。这种方法允许进程尽可能快地重启，而无须等待牺牲帧页的写出。当在牺牲帧以后写出时，它再加入到空闲帧池。 图4. 常见页面置换算法示例图