第五章存储器管理

第五章存储器管理

主讲教师:燕孝飞一、主要内容存储管理的基本概念早期的存储管理方式虚拟存储器分页存储管理请求分页分段存储管理1.存储管理的基本概念1.1程序的装入把目标模块装入内存时，可以采用三种方式：1）绝对装入方式：由装入程序根据装入模块的地址，将程序和数据装入内存。2）可重定位方式：装入程序根据内存当时的实际使用情况，将装入模块装入到内存的适当地址。3）动态运行时装入：程序运行时才将装入模块中的相对地址转换为绝对地址。1.存储管理的基本概念1.2程序的链接链接程序的功能是将经过编译或汇编后得到的一组目标模块以及它们所需的库函数，装配成一个完整的装入模块。实现链接的方式：1）静态链接2）装入时动态链接3）运行时动态链接1.3几个基本概念1）物理地址：是指存储单元的地址编号，又称为绝对地址或实地址。物理地址的集合称为物理地址空间，也叫绝对地址空间或实空间或存储空间，也就是内存空间。地址从0开始2）逻辑地址：是指用户程序中使用的地址，又称为相对地址或虚地址。逻辑地址的集合称为逻辑地址空间，也叫做相对地址空间或虚空间或地址空间。起始地址一般是0。1.存储管理的基本概念3）名空间：源程序中由符号名组成的空间。4）重定位：将进程地址空间中的逻辑地址转换为存储空间的物理地址的过程即为地址重定位，简称重定位。5）静态重定位：是指在程序运行之前由装入程序完成重定位的过程。6）动态重定位：是指在程序执行过程中由硬件地址变换机构实现的重定位过程。2.早期的存储管理方式（连续分配）2.1单一连续分配这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种方式时，内存分为以下两个分区：

1）系统区：仅供操作系统使用

2）用户区：提供给用户使用。设置地址保护机构。2.2固定分区分配

1)固定分区就是内存中分区的个数固定不变，各个分区的大小也固定不变，但不同分区的大小可以不同，每个分区只装入一道作业。

2)为了便于内存分配，系统建立一张分区使用表。每个分区对应表中的一项。各表项包括每个分区的起始地址,分区大小和状态。如下图所示。分区号大小（KB）开始地址（KB）状态12520正使用23545正使用35080正使用470130未使用固定分区分配的缺点：固定分区法管理方式简单，但内存空间利用率不高，有时浪费情况会相当严重。2.3动态分区分配为了实现分区分配，系统要设置相应的数据结构来记录内存的使用情况。数据结构有：

1）空闲分区表

2）空闲分区链空闲分区链是使用链指针把所有的空闲分区链接成一条链。每个分区的开头要设置状态和表示分区大小的项目。而且要设置前指针和后指针。分区号分区大小分区地址状态15075空闲226170空闲340275空闲分区分配算法首次适应算法该算法要求空闲分区链以地址递增的次序链接。在进行分配的时候，从链首查找，找到满足其大小的空闲分区为止。然后，进行分配，余下的空闲分区留在空闲链中。循环首次适应算法 是首次适应算法的演变。分配内存空间时，不从空闲分区链的链首查找，而是从上次找到的空闲分区的下一个开始找。最佳适应算法 将所有的空闲分区按照大小递增的顺序形成一空闲分区链。然后，从头开始找，第一次找到的满足条件的，肯定是最佳的。最坏适应算法分区分配操作分配内存回收内存2.4动态重定位分区1）紧凑将内存中的所有作业进行移动，使它们相邻接，将原来分散的小分区便拼凑成一个大分区。这种通过移动，把所个分散的小分区拼接成大分区的方法称为拼接或紧凑。2）动态重定位由于紧缩过程中作业在内存中要移动位置，地址改变，采用动态重定位很好地解决这个问题。动态重定位采用硬件来实现，一个基址寄存器，一个限长寄存器。2.5对换对换（Swapping，也称交换）技术，最早用在麻省理工学院的兼容分时系统CTSS中。所谓对换，是指把内存中暂不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需的程序和数据，换入内存。对换是提高内存利用率的有效措施。3.虚拟存储器的概念（1）局部性原理程序局部性原理是指程序在执行时将呈现出局部性规律，即在一较短时间内，程序的执行仅局限于某个部分。相应地，它所访问的存储空间也仅局限于某个区域。

1）时间局部性。产生时间局部性的典型原因是在程序中存在着大量的循环操作。

2）空间局部性。典型的情况是程序的顺序执行。（2）虚拟存储器的定义基于局部性原理，应用程序在运行之前并不必全部装入内存。我们将这种具有请求调入功能和调换功能，能从逻辑上对内存容量加以扩充的存储器系统称为虚拟存储器。（3）实现虚拟存储器的物质基础1）一定容量的主存2）大容量的辅存3）动态地址变换机构虚存的容量受字长、传送速度、使用频率的限制，其最大容量由计算机系统的地址单元确定。实现虚存的方案有：分页式虚存（请求分页）；分段；段页式。（4）虚拟存储器的特征1）离散性2）多次性3）对换性4）虚拟性4.分页存储管理针对连续分配方式形成较多碎片的问题，产生了离散分配方式，根据分配时所用的基本单位的不同，又可分为三种：分页存储、分段、段页式。4.1分页存储管理的基本方法（1）页面：把逻辑地址空间划分为一些相等的片，称为页面或页。每页有一个编号称为页号。页面大小由硬件确定的，一般选择为2的若干次幂。（2）块：内存空间也划分为与页面同样大小的存储块，称之为物理块或页框。地址结构（3）页表：页面映射表（PMT），包括页号和块号两项，主要作用实现从页号到物理块号的映射。注意：给定一个逻辑地址，会通过页表查找并计算它所对应的物理地址。

页内地址d

页号p311211分页的基本原理0页1页2页3页4页…N页页号块号0417233542…

…用户程序通过页表实现页面映射4.2地址变换机构－（1）基本的地址变换机构

块号

8页表地址页表长度页号页内地址0123块号块内地址逻辑地址页表寄存器页表越界判断(2)具有快表的地址变换机构因为页表是存放在内存中的CPU要存取一个数据，需访问主存两次。第一次：访内存中的页表，找到该页的的物理块号，将此块号与页内地址拼结形成物理地址；第二次：真正访问该物理地址，存取其中的内容。这样就把程序的执行速度降低一倍。为了提高存取速度，在地址变换机构中增设一组寄存器，用来存放访问的那些页表。把存放在高速缓冲寄存器中的页表叫快表，这个高速缓冲寄存器又叫联想存储器。具有快表的地址变换机构如下图：p’页表地址越界

l比较P>=lpp’...快表

b+页号p页内地址dP’d物理地址页表地址寄存器页表长度寄存器逻辑地址5请求分页存储管理5.1请求分页的基本原理（1）页表机制请求分页系统对地址空间和内存空间的管理采用与基本分页系统相同的方式，但它只要求将作业的部分页面装入内存，便可以开始运行，其余作业在外存，所以，要在页表中增加若干项。（2）缺页中断

在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去。（3）地址变换机构在分页系统的地址变换机构的基础上需要增加某些功能，如状态位，中断，调页，替换等。5.2页面分配和置换策略在请求分页系统中，可采取两种内存分配策略，即固定分配和可变分配策略。进行置换的时候，也可以采用两种策略，即全局置换和局部置换。于是，可组合出以下三种适用的策略。（1）固定分配局部置换（FixedAllocation,LocalReplacement）（2）可变分配全局置换(VariableAllocation,GlobalReplacement)（3）可变分配局部置换(VariableAllocation,LocalReplacement)5.3调页策略（1）请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即发出缺页中断，请求将所需页面调入内存。（2）预调页将那些预计在不久之后便会访问的几个页面预先调入内存。（3）抖动主存中刚刚移走某页后根据请求马上又调入该页。这种反复进行入页和出页的这种现象称为“抖动”，也叫系统颠簸。5.4页面置换算法（1）最佳置换算法最佳置换算法（OptimalReplacement）是1966年由Belady在理论上提出的一种算法。其实质是：当调入新的一页而必须预先淘汰某个老页时，所选择的老页应该时在将来不再被使用，或者在最远的将来才被访问的。使用这种算法保证最少的缺页率，但是实现是很困难的。（2）先进先出法(FIFO)最简单的页面置换算法是先进先出法.这种算法的实质是:总是选择在主存中停留时间最长(即最老)的一页淘汰,即先进入内存的页先被换出内存.FIFO页面置换算法容易理解和进行程序设计,然而它的性能并非总是好的.这种算法仅当按线性顺序访问地址空间时才是最理想的;否则,效率不高.（3）最近最久未使用置换法（LRU）以最近的过去来作为不久将来的近似。它的实质是：当需要置换一页时，把在最近一段时间里最久没有使用过的页面予以淘汰。这就是最近最久未用算法。LRU算法比OPT效果差，但是比FIFO好得多。LRU算法是经常采用的页面置换算法，实现起来需要实际硬件的支持。每个页表项应该对应一个“使用时间寄存器”。（4）Clock置换算法是LRU算法的近似方法，比较容易实现，而且开销较小。它在存储分块表的每个表项增加一个引用位，操作系统定期的将它们置为0，当某一页被访问时，由硬件将该位置1。将位为0的淘汰出去。（5）其他置换算法1）最少使用置换算法2）页面缓冲算法6.分段存储管理6.1分段存储管理的引入（1）方便编程（2）分段共享（3）分段保护（4）动态链接（5）动态增长6.2分段系统的基本原理（1）分段 作业的地址空间分成多个段，其逻辑地址要由两个成分表示：段号s和段内地址d。作业的地址空间是二维的。段内地址d

段号s3116150（2）段表为了能找出每个逻辑段所对应的物理内存中分区的位置，系统为每个进程建立一个段映射表，简称段表。段表项中一般包含：段号、段的长度、段在内存中的起始地址（基址）、段的状态、修改位、段在外存的地址等。（3）地址变换机构系统中设置段表寄存器，用于存放段表始址和段表长度。原理同页面存储管理。6.3段式管理的特点（1）优点：消除了碎片；提供了大量的虚存；可动态增加段长；便于动态装入和链接；可共享一个程序；便于实现存储保护。（2）缺点：地址变换和靠拢需要占用CPU时间；表格需占存储空间；在外存上管理可变长度的段比较困难，段的最大长度受限制；会出现系统抖动现象。6.4分页和分段的比较分页系统和分段系统有许多相似之处，比如：都采用离散分配来提高内存的利用率，都要通过地址变换机构来实现地址变换。但概念上两者是完全不同的，主要区别表现在以下三个方面：（1）页是信息的物理单位，系统管理的需要；段是信息的逻辑单位，用户的需要。（2）页的大小固定且由系统确定，一种系统的页面大小固定。段的长度不固定，决定于用户所编写的程序。（3）分页的作业地址空间是维一的，即单一的线性空间，程序员只须利用一个记忆符，即可表示一地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

7.段页式存储管理先将程序分段，段内再分页。其实就是段式和页式的结合。原理同前两种存储管理方式。二、重难点提示重定位的概念：为什么引入重定位，静态、动态重定位，以及如何实现动态分区分配分页和分段存储管理方式：分页、分段的基本原理、地址转换、共享和保护虚拟存储器的基本概念：定义、为什么引入、特征、关键技术请求分页系统的基本原理：页表机制、地址变换、页面置换算法。三、典型问题分析1.何谓虚拟存储器？举例说明操作系统是如何实现虚拟内存的。（定义，内存、外存结合、举例分页）2.选择题某页式存储管理系统中，地址寄存器长度为24位，其中页号占14位，则主存的分块大小应该是_____字节。A.210B.10C.14D.2143.某系统采用页式存储管理策略，拥有逻辑空间32页，每页2kb，拥有物理空间1Mb。（1）写出逻辑地址格式（5，11）（2）若不考虑访问权限等，进程的页表有多少项，每项多少位？（32，9）（3）如果物理地址减少一半，页表结构相应作怎样的改变？（32，8）四、习题1.假定某页式管理系统，主存为64KB，分成16块，块号为0，1，2，3，4，…，15。设某作业有4页，其页号为0、1、2、3，被分别装入2、4、1、6块。试问：（1）该作业的总长度是多少字节？（2）写出作业每一页在主存中的起始地址。（画出页表）（3）若给出逻辑地址[0,100],[1,50],[2,0],[3,60]，请计算出相应的内存地址。2.对于如表5－2所示的段表，请将逻辑地址[0,137],[1,4000],[2,3600],[5,230]转换成物理地址。段号内存地址段长/B050k10k160k3k270k5k3120k8k4150K4k3.已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执行时主存中没有页面。若只给该作业分配2个物理块，（1）当采用FIFO、LRU页面置换算法时，发生多少次缺页，缺页率为多少？（2）假定现在有一种置换算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问缺页情况如何？4.某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻，系统为用户的第0，1，2，3页分配的块号分别为5，10，4，7，而该用户的作业长度为6页，试将十六进制的虚拟地址0A5C和103C转化成物理地址。5.选择题1）________不是分段式虚拟存储管理优于分页式虚拟存储管理之处。A.没