操作系统第四章

1、计算机操作系统第四章 存储器管理9/19/202219/19/202229/19/20223第四章 存储器管理 4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法 4.8 请求分段存储管理方式 存储管理研究的课题 存储分配问题。 重点是研究存储共享和各种分 配算法。 地址再定位问题。 研究各种地址变换机构， 以 及静态和动态再定位方法。 存储保护问题。 研究保护各类程序、 数据区的 方法。 存储扩充问题。 主要研究虚拟存储器问题及其各 种调度算法。存储器管理

2、主要研究三方面的问题： 取（fetch） 放（placement） 替换（replacement）请调、预调连续、非连续存储层次结构9/19/20227外存(secondary storage)DOS核心命令处理程序内存(primary storage)高速缓存(cache)寄存器(register)速度容量小大低高本章主要研究内容主存管理的功能 地址映射(地址重定位) 主存分配和回收 存储保护和共享 主存扩充(虚拟内存) 9/19/20228 二. 主存分配与回收 要完成内存的分配和回收工作，要求设计者选择和确定以下几种策略和结构：调入策略放置策略置换策略分配结构9/19/20229调入策略

3、用户程序在何时调入内存的策略。目前有请调和预调两种9/19/202210放置策略用户程序调入内存时，确定将其放置在何处的策略。9/19/202211置换策略当需要将某个用户程序调入内存而内存空间又不够时，就要确定哪个或哪些程序可以从内存中移走。9/19/202212分配结构分配结构是用来登记内存使用情况的数据结构。如空闲区表、空闲区队列等。9/19/202213引起内存分配和回收的原因进程的开始和结束。进程运行的过程中，它所占用的内存也可能发生变化。如栈的变化。进程映像在内存和外存之间传递。由于内存有限，系统中不可能容纳所有进程，有些进程的映像可以存放在外存，当要运行这些进程时，必须把它们调入

4、内存。系统为了充分利用内存空间，有时可能对内存空间进行调整。9/19/202214三.存储保护保证在内存中的多道程序只能在给定的存储区域内活动并互不产生干扰。 包括：防止地址越界防止越权(对共享区有访问权)9/19/202215存储保护的硬件支持界地址寄存器（界限寄存器）界地址寄存器被广泛使用的一种存储保护技术机制比较简单，易于实现9/19/202216实现方法在CPU中设置一对下限寄存器和上限寄存器存放用户作业在主存中的下限和上限地址也可将一个寄存器作为基址寄存器，另一寄存器作为限长寄存器（指示存储区长度）每当CPU要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否

5、越界如果未越界，则按此地址访问主存，否则将产生程序中断越界中断（存储保护中断）9/19/202217图示9/19/202218四.主存扩充(虚拟内存)为了使程序员在编程时不受内存的结构和容量的限制，系统为用户构造一种存储器，其结构可能与内存结构不同，容量可能远远超过内存的实际容量。这种面向编程的存储器称为虚拟存储器。由虚存构成的存储空间称为虚存空间。或称虚地址空间。9/19/202219实现虚拟内存的基本原理将程序正在使用的部分内容放在内存，而暂时不用的部分放在外存，在需要时由系统调入内存，并将不需要（或暂不需要）的部分调出内存。由于程序在执行时，在一段时间内一般仅使用它的程序的一部分（或一小

6、部分），所以程序仅有部分装入内存完全能够正确执行。要由操作系统结合相关硬件来完成上述工件，这样计算机好象为用户提供了一个容量远大于内存的存储器，这个存储器称为虚拟存储器。 9/19/2022204.1 程序的装入和链接将用户源程序变为可在内存中执行的程序的步骤：编译：由编译程序将用户源代码编译成若干个目标模块链接：由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块装入：由装入程序将装入模块装入内存，构造PCB，形成进程(使用物理地址)9/19/2022214.1 程序的装入和链接9/19/202222库链接程序装入模块装入程序编译程序产生的目标模块第

7、一步第二步第三步内存一.地址映射(地址重定位)物理地址（内存地址，绝对地址，实地址）：内存的每个存储单元都有一个编号，这个编号称为物理地址；内存地址的集合称为内存空间（或物理地址空间）；物理地址可直接寻址9/19/202223一.地址映射(地址重定位)逻辑地址（程序地址，相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式；由逻辑地址组成的空间称为逻辑地址空间（或程序地址空间）其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。9/19/2022249/19/202225 地址映射（地址重定位）：用户程序装入内存时对有关指令

8、的地址部分的修改定义为从程序地址到内存地址的地址映射，或称为地址重定位创建进程时，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址映射。为何要进行地址映射？一.地址映射(地址重定位)地址映射的方式静态地址映射（静态重定位）动态地址映射（动态重定位）9/19/2022261、静态地址映射静态地址映射（静态重定位）：程序被装入内存时由操作系统的链接装入程序完成程序的逻辑地址到内存地址的转换。9/19/202227映射方法假定程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则地址映射按下式进行：MR=BR+VR 。例如，程序装入内存的

9、首地址为1000，则装配程序就按MR=1000+VR对程序中所有地址部分进行修改9/19/2022289/19/202229地址映射BR=1000Load A 1200 3456 。 。1200物理地址空间Load A data1data1 3456源程序Load A 200 34560100200编译逻辑地址空间逻辑地址、物理地址和地址映射名空间地址空间存储空间优缺点优点：不需要硬件的支持，可以装入有限多道程序。缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。9/19/2022302、动态地址映射动态地址映射（动态重定位）：是在程序执行的过程中，每次访问内存之

10、前，将要访问的程序地址转换为内存地址；一般来说这种转换是由专门的硬件机构来完成的。9/19/202231映射方法最简单的硬件机构是重定位寄存器；在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。9/19/2022329/19/20223303456.LOAD A 200.0100200300.LOAD A 2003456110012001300200VR+1000BR1200MR地址映射的具体过程程序装入内存后，它所占用的内存区的首地址由系统送入基地址寄存器BR中。在程序执行的过程中，若要访问内存，将访问的逻辑地址送入程序地址寄存器VR中。 地址转换机

11、构把VR和BR中的内容相加，并将结果送入内存地址寄存器MR中，作为实际访问的地址。9/19/202234动态地址映射的优缺点优点：OS可以将一个程序分散存放于不连续的内存空间可以移动程序有利于实现共享缺点：需要硬件支持OS实现较复杂9/19/202235虚拟存储的基础4.1.2 程序的链接静态链接：在程序运行前，将目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开。装入时动态链接：指将用户源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的链接方式。运行时动态链接：指对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行链接。9/19/2022361、静态链接(

12、static-linking)9/19/202237返回静态链接是在生成可执行文件时进行的。在目标模块中记录符号地址(symbolic address)，而在可执行文件中改写为指令直接使用的数字地址。4.1.2 程序的和链接9/19/202238静态链接方式：事先进行链接，以后不再拆开模块ACALL B;Return;0L-1模块BCALL C;Return;0M-1模块CReturn;0N-1模块AJSR “L”Return;0L-1模块BJSR “L+M”Return;LL+M-1模块CReturn;L+ML+M+N-1目标模块装入模块将目标模块装配成装入模块时需解决的两个问题：(1)变换

13、外部调用符号(2)对相对地址进行修改对相对地址进行修改变换外部调用符号2. 装入时动态链接 (Load-time Dynamic Linking) 边装入边链接。优点：(1) 便于修改和更新(2) 便于实现对目标模块的共享9/19/202239动态链接(dynamic-linking)在装入或运行时进行链接。通常被链接的共享代码称为动态链接库(DLL, Dynamic-Link Library)或共享库(shared library)。3. 运行时动态链接(Run-time Dynamic Linking)边执行边链接！优点： 加快装入过程、节省内存空间9/19/2022409/19/2022

14、414.2 连续分配方式 特点： 为每个用户程序分配连续的内存空间 方法 单一连续分配 固定分区分配 动态分区分配 可重定位分区分配9/19/2022424.2.1 单一连续分配 最简单的一种存储分配管理方法只能用于单用户、单任务的操作系统中把内存分为两部分系统区：提供给OS使用，内存的低址部分用户区：提供给用户使用。 内存系统区（OS）用户区0100k进程A进程B9/19/2022434.2.2 固定分区分配 1. 划分分区的方法 分区大小相等， 即使所有的内存分区大小相等。 (2) 分区大小不等。 9/19/2022442. 内存分配 内存OS作业A作业B作业C作业D分区号大小(K)起址(

15、K)状态11224已分配22436已分配33060未分配43590已分配540125未分配650165已分配7297215未分配0K24K90K36K60K165K125K215K进程F(70K)已分配进程G(70K)分区使用表内存分配程序9/19/2022454.2.3 动态分区分配 1. 分区分配中的数据结构 空闲分区表。 (2) 空闲分区链。 内存OS42K作业B20K作业C15K作业D30K0K35K111K77K91K151K136K226K分区号大小(K)始址(K)24235420916151368302263542912022630151369/19/2022462. 分区分配算

16、法 首次适应算法FF (2) 最佳适应算法(3) 最坏适应算法 首次适应法要求空闲区按首址递增的次序组成空闲区表（链）。 内存OS42K作业B20K作业C15K作业D30K9/19/2022470K35K111K77K91K151K136K226K354291202263015136内存OS42K作业B20K作业C15K作业D30K9/19/2022480K35K111K77K91K151K136K226K429135201361522630首次适应算法FF1）作业1请求内存空间25K（分配）2）作业D完成（回收）思考：作业1完成（回收）作业117K6017120K12030K作业作业A作业2

17、0K9/19/202249（1）（2）30K作业A作业20K作业（3）作业30K作业作业A20K（4）作业30K作业A20K作业1003050020100305002010030500201003018020回收内存的四种情况20050首址200大小50K大小50K大小50K首址450大小50K80回收作业A45070100分析优点：优先利用低地址空间，从而保证高址空间有较大的空闲区缺点：低址部分被不断划分，留下许多难以利用的、很小的空闲分区每次都从低址开始，查找开销大9/19/202250返回最佳适应法每次把能满足作业要求，并且是最小的空闲分区分配给作业要求按空闲区大小从小到大的次序组成空闲

18、区表（链）。内存OS42K作业B20K作业C15K作业D30K9/19/2022510K35K111K77K91K151K136K226K136159120354230226内存OS42K作业B20K作业C15K作业D30K9/19/2022520K35K111K77K91K151K136K226K最佳适应算法1）作业1请求内存空间25K（分配）2）作业D完成（回收）思考：作业1完成（回收）作业15K90K136159120226303542251590分析优点：在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。若系统中不存在与申请分区大小相等的空闲区，则选中的

19、空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。缺点：空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区总是最小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费。 9/19/202253返回最坏适应法每次把能满足作业要求，并且是最大的空闲分区分配给作业要求空闲区按大小递减的顺序组织空闲区表（或链）。 内存OS42K作业B20K作业C15K作业D30K9/19/2022540K35K111K77K91K151K136K226K354222630136152091内存OS42K作业B20K作业C15K作业D30K9/19/20225

20、50K35K111K77K91K151K136K226K最坏适应算法1）作业1请求内存空间25K（分配）2）作业D完成（回收）思考：作业1完成（回收）作业117K120K3542226309120136156017136120分析最坏适应法看起来似乎有些荒唐，但在严密地考察后，还是有它的优点：当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。另一方面分配时每次仅作一次查询工作。9/19/202256三种策略比较上述三种放置策略各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算

21、法对这一作业序列是合适的。对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。 9/19/202257举例例1：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。画出空闲区链并分析一下哪个算法最合适此序列？9/19/202258经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。OS30作业20作业5作业46首次最佳最坏20501001201601652100203010020210465160160510020210463020210462030160520100练习有作业序列：作业A要求21K

22、；作业B要求30K，作业C要求25K。9/19/202259思考 用动态分区分配方式管理主存时,假定主存中按地址顺序依次有5个空闲区,空闲区的大小依次为32K,10K,5K,228K和100K,现有5个作业A,B,C,D,E.它们各需主存1K,10K,108K,28K和115K.若采用首次适应算法能把这5个作业按顺序全部装入主存吗?你认为怎样的次序装入这5个作业可使主存的利用率最高?9/19/2022609/19/2022614.2.4 可重定位分区分配OS作业110作业230作业314作业426分区号起址大小35010512030716514923026 空闲分区表 205060120150

23、165179230作业A(40)80重定位寄存器作业120作业260作业3150作业4179306015512050110125176 9 216 409/19/2022624.2.5 对换(Swapping) 1. 对换的引入 所谓“对换”， 是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。 9/19/2022632. 对换空间的管理 为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所

24、用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。 9/19/2022643. 进程的换出与换入 (1) 进程的换出。 每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。 其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。 9/19/202265 (2) 进程的换入。 系统应定时地查看所有进程

25、的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。 9/19/2022664.3 基本分页存储管理方式 4.3.1 分页存储管理的基本方法 将程序的逻辑地址空间和物理内存划分为固定大小的页或页面(page or page frame)，程序加载时，分配其所需的所有页，这些页不必连续。基本分页存储管理方式9/19/2022679/19/2022684.3.1 分页存储管理的基本方法优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。便于改变程序占用空间的大小。即随着程序运行而动态生成的

26、数据增多，地址空间可相应增长。缺点：程序全部装入内存。9/19/2022694.3.1 分页存储管理的基本方法基本分页存储管理方式9/19/2022704.3.1 分页存储管理的基本方法所需表目：(1)页表，每个进程一个 块号 页号:152216320123所需寄存器(1) 页表寄存器：bl系统一个(2) 快表：系统一组： 页号块号.fp页表首址 页表长度9/19/202271进程页表4.3.1 分页存储管理的基本方法基本分页存储管理方式9/19/2022721. 页面页面和物理块 分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片称为页面或页，并为各页加以编号，从0开始。 同时把内

27、存空间分成与页面相同大小的若干个存储块，称为块或页框。 在为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻的物理块中。 进程的最后一页经常装不满而形成“页内碎片”。4.3.1 分页存储管理的基本方法基本分页存储管理方式9/19/202273页面大小页面大小应选地适中，应是2的幂，通常是512B8KB。9/19/2022742. 地址结构位移量W页号P31 12 11 0地址长度32位:011位为位移量(页内地址)，即每页的大小为4KB12 31位为页号，地址空间最多允许有1M页基本分页存储管理方式 若给定一个逻辑地址空间中的地址为A，页面大小为L，则: 页号P=INTA/L

28、 页内地址d=A MOD L 例如：系统页面大小为1KB，设A=2170B，则: P=2，d=1229/19/202275基本分页存储管理方式9/19/202276n页5页4页3页2页1页0页用户程序59483623120页号块号页表内存203456789101页表的作用：基本分页存储管理方式4.3.1 地址变换机构1. 基本的地址变换机构 页表可以由一组专门的寄存器来实现，一个页表项用一个寄存器。但寄存器成本高，系统页表可能很大，所以页表大多常驻内存。 在系统中只设置一个页表寄存器PTR，在其中存放页表在内存中的始址和页表的长度。9/19/202277基本分页存储管理方式9/19/20227

29、8页表长度页表始址页表寄存器页内地址页号(3)逻辑地址L物理地址b1块号页号01234+越界中断页表分页系统的地址变换机构：逻辑地址1023：1023/1K得页号为0，页内地址为1023，查页表找到对应得物理块为2，故物理地址为2*1K+1023=3071。逻辑地址2500：2500/1K得页号为2，页内地址为452，查页表找到对应得物理块为6，故物理地址为6*1K+452=6596。逻辑地址4500：4500/1K得页号为4，页内地址为404，页号大于页表长度，产生越界中断 某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块

30、中。将十进制的逻辑地址1023、2500、4500转换为物理地址 9/19/202279页式地址变换举例页表始址页表长度控制寄存器页号页面号有效地址02132821C4物理地址81C4基本分页存储管理方式例：设页长为1K，程序地址字长为16位，用户程序空间和页表如图，求用户程序中Move指令中相对地址对应的绝对地址。9/19/202280用户程序Move r1,250001001K2K25003K-1页表页号块号021427内存01K2K3K4K5K6K7K8K9K10K-1课堂练习9/19/202281 假定某页式管理系统，主存为64KB，分成16块，块号为0，1，2，15。设某作业有4页，

31、其页号为0，1，2，3，被分别装入主存的2、4、1、6块。试问：该作业的总长度是多少字节？写出该作业每一页在主存中的起始地址；对多个逻辑地址0，100、1，50、2，0、3，60，试计算出相应的内存地址。课堂练习9/19/202282例：设虚地址为(357101)8 每一块为128字节，求出页号及页内地址（偏移量）12827(357101)8(011, 101, 111, 00 1, 000, 001)21 6 74101偏移为(101)8, 页号为(1674)8块号由页表指定，偏移不变2. 具有快表的地址变换机构CPU在每存取一个数据时，需要两次访问内存：第一次：访问页表，找到指定页的物理块

32、号，将块号与页内偏移量拼接形成物理地址。第二次：从第一次所得地址中获得所需数据，或向此地址中写入数据。处理速度降低！解决方法：在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲寄存器，称为“联想存储器”或“快表”。9/19/202283基本分页存储管理方式9/19/202284页表长度页表始址页表寄存器页内地址页号(3)逻辑地址Ldb物理地址+越界中断b1块号页号页表具有快表的分页系统的地址变换机构：b块号页号快表输入寄存器9/19/202285假定快表的命中率为98%,快表的访问时间为20ns,内存的一次访问时间为100ns,则有效访问时间为:课堂练习EAT(Effective Acc

33、ess Time)=98%(20+100)+2%(20+200)=122ns基本分页存储管理方式4.3.2 两级和多级页表 现代计算机系统都支持非常大的逻辑地址空间(232264)，页表就非常大，需占用较大的地址空间。例如：一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则每个进程页表的页表项可达1M个，若每个页表项占用4个字节，则每个进程的页表就要占据4MB的内存空间，而且要求连续存放。9/19/202286基本分页存储管理方式1. 两级页表 9/19/202287例如： 32位逻辑地址空间，页面大小为4KB(即12位)，若采用一级页表机构，应有20位页号，即页表项应有

34、1M个；在采用两级页表机构时，再对页表进行分页，使每页包含210(即1024)个页表项，最多允许有210个页表分页。即页内地址外层页内地址外层页号dp2p1 31 22 21 12 11 0 基本分页存储管理方式9/19/202288012345671141151468内存空间641第0页页表0121023115114第1页页表01210231468第n页页表0121023174210781011012n外部页表两级分页结构9/19/202289外部页表寄存器外部页表页表db物理地址+dP2P1逻辑地址外部页号外部页内地址页内地址具有两级页表的地址变换机构： 上述方法用离散分配空间解决了大页表

35、无需大片存储空间的问题，但并未减少页表所占的内存空间。 解决方法是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。2. 多级页表 两级页表对32位机器适用，64位呢？ 页面大小为4KB即212B，还剩52位，按物理块大小212位来划分页表，则剩余40位用于外层页号，此时外层页表可能有1024G个页表项，要占用4096GB的连续存储空间 解决方法：采用多级页表，将外层页表再进行分页。9/19/202290基本分页存储管理方式9/19/202291多级页表地址映射基本分页存储管理方式9/19/2022924.4 基本分段存储管理方式 4.4.1 分段存储管理方式的引入 引入分段存储管理方式

36、， 主要是为了满足用户和程序员的下述一系列需要： 1) 方便编程Load r1,A,100 Store r2,B,500 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接 基本分段存储管理方式9/19/202293页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。将程序的地址空间划分为若干个段(segment)，程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。需要硬件支持。4.4.2 分段系统的基本原理基本分段存储管理方式 程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段。可

37、以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进行共享，包括通过动态链接进行代码共享 优点：没有内碎片，外碎片可以通过内存紧缩来消除。便于改变进程占用空间的大小。 缺点：进程全部装入内存。9/19/2022944.4.2 分段系统的基本原理基本分段存储管理方式9/19/202295段号段表9/19/202296 所需表目(1) 段表：每进程一个段首址段长度100k40k80k60k段号 0: 1: 2: 3:20k200k320k300k(2) 空闲表：系统一个 array of (addr,size)基本分段存储管理方式9/19/202297 所需寄存器(1) 段表寄存器

38、：bl段表首址 段表长度系统一个(2) 快表：系统一组： 段号 段首址 段长度.ls.b.基本分段存储管理方式9/19/2022984.4.2 分段系统的基本原理 1. 分段 分段地址中的地址具有如下结构： 段号段内地址31 16 15 0基本分段存储管理方式该地址结构允许一个作业最长有64K个段，每段的最大长度为64KB。2. 段表 段表可以存放在寄存器中，但更多的是存放在内存中。 段表可以实现从逻辑段到物理内存区的映射。9/19/202299基本分段存储管理方式9/19/2022100 利用段表实现地址映射 M (0)30KX(1)20KD(2)15KF(3)10K用户作业作业空间内存空间

39、M (0)30KX(1)20KD(2)15KF(3)10K040K80K120K150K30K40K20K80K15K120K10K150K段表 段长 基址01239/19/2022101分段系统的地址变换过程 3. 地址变换机构 段号S位移量W210K控制寄存器段表始址200K段表长度4越界+30K40K20K80K15K120K10K150K段长 基址+内存040K80K120K150K越界9/19/2022102例: 段表如下：回答下列问题：1计算该作业访问 0，432，1，10，2，500，3，400 时的绝对地址2总结段式存储管理的地址转换过程。段号段长主存起始地址012346601

40、401005809602219330090123719599/19/2022103 段表如下：计算该作业访问 0，216，1，120，2，210，3，456 时的绝对地址段号段长主存起始地址01234660140100580960221933009012371959课堂练习9/19/2022104 注意：当段表存放在内存中时，每访问一个数据，都需访问两次内存，降低了计算机的速率。 解决方法：设置联想寄存器，用于保存最近常用的段表项。基本分段存储管理方式4. 分页和分段的主要区别相似点：采用离散分配方式，通过地址映射机构实现地址变换不同点：页是信息的物理单位，分页是为了满足系统的需要；段是信息的

41、逻辑单位，含有一组意义相对完整的信息，分段是为了满足用户的需要。页的大小固定且由系统确定，由系统把逻辑地址分为页号和页内地址，由机器硬件实现；段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。分页的作业地址空间是一维的；分段的作业地址空间是二维的。9/19/2022105基本分段存储管理方式9/19/20221064.4.3 信息共享 分页系统中共享editor的示意图（页面大小为1K）两个进程共享文本编辑程序Editor，程序大小4K，另每个进程自身的数据2K进程1ed1ed2ed3ed4data1data2进程2ed1ed2ed3ed4data1data2页表202

42、122234041页表202122235051主存0Ed120Ed221Ed322ed423data140data241data150data251辽东学院信息技术学院9/19/2022107分段系统中共享editor的示意图进程1editordata1进程2editordata2段表段长基址4K20K2K40K段表段长基址4K20K2K50K主存020editor40data150data2分段系统的一个突出优点是易于实现段的共享，允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。辽东学院信息技术学院9/19/2022108段的共享段长 段首址 . l b . .段号 si .P1

43、段表：段长 段首址 . l b . .段号 sj .P2段表：共享段.b:l内存空间基本分段存储管理方式辽东学院信息技术学院9/19/2022109段名 共享记数 段长 段首址 其它 . vi 3 35k 125k ? .共享段表：进程段表(n)共享段表(1)共享段(1)基本分段存储管理方式9/19/2022110 段的保护 (1) 段表的改进：段长 段首址 . . . l b 1 0 1段号 s .访问权限R W E . . . 段号 段长 段首址 . . . s l b 1 0 1访问权限R W E(2) 快表的改进： . . .基本分段存储管理方式9/19/20221114.4.4 段页

44、式存储管理 (segmentation with paging)段式优于页式便于共享和保护页式优于段式消除“外碎片”问题段页式：结合二者优点每个进程包含若干段每个段包含若干页基本分段存储管理方式9/19/20221121. 基本原理 图 4-20 作业地址空间和地址结构 页基本分段存储管理方式9/19/2022113 基本原理 内存空间划分：(同页式) 静态等长，2i, 称为一页。 物理地址=(块号,块内地址)=(f,w) 进程空间划分： 一个进程若干个段 一个段若干个页 逻辑地址=(段号, 逻辑页号, 页内地址)=(s,p,w)基本分段存储管理方式9/19/2022114利用段表和页表实现地

45、址映射主程序段0123子程序段01数据段012段号状态页表大小页表始址041001220023400段表页号状态存储块#020122223324页表页号状态存储块#040142页表页号状态存储块#050151252页表主存020212223244041425051529/19/2022115段表长度段表始址段表寄存器块内地址块号b物理地址+段超长2.段页式系统的地址变换机构：页内地址页号P段号Sf1块号页号页表0123+段表0123页表长度页表始址9/19/20221164.5 虚拟存储器的基本概念 4.5.1 引入1.常规存储管理的特征：一次性（指全部装入）、驻留性（指驻留在内存不换出）2、

46、局部性原理时间局部性：如循环执行空间局部性：如顺序执行。3、虚拟存贮器具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。虚拟大小由_决定。9/19/2022117引入虚拟存储技术的好处大程序：可在较小的可用内存中执行较大的用户程序；大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory)并发：可在内存中容纳更多程序并发执行；易于开发：与覆盖技术比较，不必影响编程时的程序结构9/19/20221184.5.2 虚拟存储器的实现方法 需要动态重定位一、请求分页系统以页为单位转换需硬件：（1）请求分页的页表机制（2

47、）缺页中断（3）地址变换机构需实现请求分页机制的软件（置换软件等）二、请求分段系统以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构需实现请求分段机制的软件（置换软件等）9/19/20221194.5.3 虚拟存储器的特征 多次性：一个作业被分成多次调入内存运行对换性：允许在作业的运行过程中进行换进、换出。虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。辽东学院信息技术学院9/19/20221204.6 请求分页存储管理方式 4.6.1 请求分页中的硬件支持 1. 页表机制 页号 物理块号 状态位P 访问字段A 修改位M外存地址 指示该页是否已

48、调入内存记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考该页在调入内存后是否被修改过，供置换页面时参考指出该页在外存上的地址，供调入该页时参考9/19/20221212. 缺页中断机构 TO B指令copy A A: B:页面6543219/19/20221223. 地址变换机构 9/19/20221234.6.2 内存分配策略和分配算法 1. 最小物理块数的确定 进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式如： Mov A, B允许间接寻址：则至少要求3个物理块。9/19/20221242. 物理块的分配策略 内存

49、分配策略：固定和可变分配策略置换策略：全局置换和局部置换 1) 固定分配局部置换(Fixed Allocation, Local Replacement)缺点：难以确定固定分配的页数(少：置换率高/多：浪费) 2) 可变分配全局置换(Variable Allocation, Global Replacement) 3) 可变分配局部置换(Variable Allocation, Local Replacement）根据进程的缺页率进行页面数调整，进程之间相互不会影响9/19/20221253. 物理块分配算法 1) 平均分配算法 将系统中所有可供分配的物理块，平均分配给各个进程。缺点：未考虑各

50、进程本身的大小。9/19/20221262) 按比例分配算法 这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为： 又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。 9/19/20221273) 考虑优先权的分配算法 在实际应用中，为了照顾重要的、急迫的作业尽快完成，应为它分配较多的内存空间。方法：一部分按比例分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。9/19/20221284.6.3 调页策略 1. 何时调入页面 （1）

51、请调(demand paging) upon page fault, 发生缺页中断时调入（较费系统开销） （2） 预调(prepaging) before page fault, 将要访问时调入(根据程序顺序行为， 不一定准）（根据空间局部性，目前：成功率50）预调必须辅以请调。9/19/20221292. 从何处调入页面 外存：文件区、对换区系统拥有足够的对换区空间：系统缺少足够的对换区空间：UNIX方式：9/19/2022130缺页中断保留CPU环境缺页中断处理访问内存数据3. 页面调入过程小结1、基本思想在进程开始运行之前，不是装入全部页面，而是装入几个或零个页面，之后根据进程运行的需要

52、，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面9/19/20221319/19/2022132XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虚地址空间物理地址空间 虚页页框2、页表表项页号、物理块号、状态位、外存地址、访问位、修

53、改位状态位：表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：查看此页是否在内存中被修改过9/19/2022133页号物理块号状态位外存地址访问位修改位9/19/2022134151413121110 9 8 7 6 5 4 3 2 10000000000000000111100001011000000000000011110010001110100110101 00010000000000100011000000000100110在/不在内存页表虚地址8196物理地址245803、缺页中断（Page Fault）处理在地址映射过程中，在页表中发现所要访问的

54、页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，准备将该页调入内存此时应将缺页的进程挂起（调页完成唤醒）9/19/2022135如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项目的状态位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）9/19/2022136思考缺页中断同一般中断的区别？9/19/2022137缺页中断同一般中断都是中断，相同点是：保护现场 中断处理 恢复现场不同点：一般中断是一条指令完成后接受和处理中断，缺页中断是一条指令执行过程中产生和

55、处理中断一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些地址在不同的页中。9/19/20221389/19/20221394.7 页面置换算法 4.7.1 最佳置换算法和先进先出置换算法 1. 最佳(Optimal)置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。 用于：页淘汰、段淘汰、快表淘汰。9/19/2022140 假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4

56、，2，3，0，3，2，1，2，0，1，7，0，1 7F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺页标志70F701F201F201203F203243F243243203F203203201F201201201701F701701缺页9次，总访问次数20次，缺页率9/2045页面置换6次，置换率6/20=30%最佳置换算法（OPT）例9/19/20221412. 先进先出(FIFO)页面置换算法 该算法的实质是：总是选择作业中在主存驻留时间最长（即最老）的一页淘汰。即先进入主存的页先退出主存。其理由是，最早调入主存的页，其不再被使用的可能性比最近调

57、入主存的页要大。9/19/20221427F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺页标志70F701F201F201231F230F430F420F423F023F023023013F012F012012712F702F701F缺页15次，总访问次数20次，缺页率15/2075页面置换12次，置换率12/20=60%先进先出置换算法（FIFO）例9/19/2022143有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配3块。进程执行时使用页号的顺序为 4 3 2 1 4 3 5 4 3 2 1 5(1)该进程运行时总共出现几次

58、缺页（假设进程运行前所有页面均不在内存中）。(2)若每个进程在内存有4块，又将产生几次缺页。(3)如何解释所出现的现象。例 9/19/20221444 3 2 1 4 3 5 4 3 2 1 5m=3413214214354352352143432共缺页中断9次9/19/2022145m=3时，缺页中断9次m=4时，缺页中断10次FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加9/19/2022146 在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现

59、象称为颠簸或抖动原因：页面淘汰算法不合理分配给进程的物理页面数太少颠簸（抖动）9/19/20221474.7.2 最近最久未使用(LRU)置换算法 1. LRU(Least Recently Used)置换算法的描述 该算法的基本思想是:利用局部性原理，根据一个作业在执行过程中过去的页访问的踪迹来推测未来的行为。它认为过去一段时间里不曾被访问过的页，在最近的将来可能也不会再被访问。所以这种算法的实质是：当需要置换一页时，选择在最近一段时间内最久不用的页予以淘汰。9/19/2022148m=44 3 2 1 4 3 5 4 3 2 1 544321532154215431543214324343

60、21532共缺页中断10次9/19/20221497F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺页标志70F701F201F201203F203403F402F432F032F032032132F132102F102107F107107缺页12次，总访问次数20次，缺页率12/2060页面置换9次，置换率9/20=45%最近最久未使用置换算法（LRU）例9/19/20221502. LRU置换算法的硬件支持 1) 寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3 R2R1