1、第四章 存 储 器 管 理 存储组织存储组织=存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。=存储组织存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。v其依据是访问速度匹配关系、容量要求和价格；v“寄存器-内存-外存”结构；v“寄存器-缓存-内存-外存”结构；第四章 存 储 器 管 理 内存内存 由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器分为：系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据第四章 存 储 器 管 理 存储管理的功
2、能存储管理的功能=存储分配和回收存储分配和回收：分配和回收算法及相应的数据结构。：分配和回收算法及相应的数据结构。=地址变换地址变换：vv可执行文件生成中的链接技术可执行文件生成中的链接技术 vv程序加载程序加载(装入装入)时的重定位技术时的重定位技术 vv进程运行时硬件和软件的地址变换技术和机构进程运行时硬件和软件的地址变换技术和机构=存储共享和保护存储共享和保护：vv代码和数据共享代码和数据共享 vv地址空间访问权限（读、写、执行）地址空间访问权限（读、写、执行）=存储器扩充存储器扩充：存储器的逻辑组织和物理组织；：存储器的逻辑组织和物理组织；vv由应用程序控制：覆盖；由应用程序控制：覆盖
3、；vv由由OS控制：交换（整个进程空间），虚拟存储的请求调控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）入和预调入（部分进程空间）第四章 存 储 器 管 理 逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射=逻辑地址逻辑地址（相对地址，虚地址）：用户的程序经过汇编（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址或编译后形成目标代码，目标代码通常采用相对地址的形式。的形式。vv其首地址为其首地址为0，其余指令中的地址都相对于首地址来，其余指令中的地址都相对于首地址来编址。编址。vv不能用逻辑地址在内存中读取信息。不能用逻辑地址
4、在内存中读取信息。=物理地址物理地址（绝对地址，实地址）：内存中存储单元的地（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。址。物理地址可直接寻址。=地址映射地址映射：将用户程序中的逻辑地址转换为运行时由机：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。器直接寻址的物理地址。vv当程序装入内存时当程序装入内存时,操作系统要为该程序分配一个合操作系统要为该程序分配一个合适的内存空间，由于适的内存空间，由于程序的逻辑地址与分配到内存程序的逻辑地址与分配到内存物理地址不一致物理地址不一致,而而CPU执行指令时，是按物理地执行指令时，是按物理地址进行的，所以要进行地址转换
5、址进行的，所以要进行地址转换。第四章 存 储 器 管 理 4.1 程序的装入和链接程序的装入和链接=程序在成为进程前的准备工作程序在成为进程前的准备工作 vv编辑：形成源文件编辑：形成源文件(符号地址符号地址)vv编译：形成目标模块编译：形成目标模块(模块内符号地址解析模块内符号地址解析)vv链接：由多个目标模块或程序库生成可执行链接：由多个目标模块或程序库生成可执行文件文件(模块间符号地址解析模块间符号地址解析)vv装入：构造装入：构造PCB，形成进程，形成进程(使用物理地址使用物理地址)第四章 存 储 器 管 理 图 4-1 对用户程序的处理步骤 库链接程序装入模块装入程序编译程序产生的目
6、标模块第一步第二步第三步内存第四章 存 储 器 管 理 4.1.1 程序的装入程序的装入1.绝对装入方式绝对装入方式(Absolute Loading Mode)程序中使用绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。一旦程序或数据被修改后，可能要改变程序中的所有地址。LOAD 1，12500365LOAD 1，125003651000011000125001500015000125001100010000作业地址空间内存空间第四章 存 储 器 管 理 2.可重定位装入方式可重定位装入方式(Relocation Loading Mode)=重定位重定位：在可执行文件装入时需要解决可执
7、行文件中地址（指令和数据）和内存地址的对应。由操作系统中的装入程序loader来完成。第四章 存 储 器 管 理 图 4-2 作业装入内存时的情况 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作 业 地 址 空 间内 存 空 间第四章 存 储 器 管 理 3.动态运行时装入方式动态运行时装入方式(Denamle Run-time Loading)动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相
8、对地址。第四章 存 储 器 管 理 LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存第四章 存 储 器 管 理 4.1.2 程序的链接程序的链接 1.静态链接方式静态链接方式(Static Linking)图 4-3 程序链接示意图 模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn
9、；(a)目标模块(b)装入模块第四章 存 储 器 管 理 2.装入时动态链接装入时动态链接(Loadtime Dynamic Linking)链接在装入时进行，即在装入一个模块时，若发链接在装入时进行，即在装入一个模块时，若发生一个外部模块调用事件，则由装入程序去找出相生一个外部模块调用事件，则由装入程序去找出相应的外部模块，将它装入内存，并把它链接到调用应的外部模块，将它装入内存，并把它链接到调用模块上去模块上去 这种链接方式的优点是便于对程序模块进行修这种链接方式的优点是便于对程序模块进行修改和更新，并且可以对目标模块实现共享，以提高改和更新，并且可以对目标模块实现共享，以提高内存和外存的
10、利用率。内存和外存的利用率。第四章 存 储 器 管 理 3.运行时动态链接运行时动态链接(Run-time Dynamic Linking)将对某些模块的链接推迟到执行时才执行，亦即，在将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立执行过程中，当发现一个被调用模块尚未装入内存时，立即由即由OS去找到该模块并将之装入内存，去找到该模块并将之装入内存，把它链接到调用者把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的调入内存和被链接到
11、装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。装入过程，而且可节省大量的内存空间。第四章 存 储 器 管 理 4.2 连续分配方式连续分配方式4.2.1 单一连续分配单一连续分配 内存分为两个区域：系统区，用户区内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。应用程序装入到用户区，可使用用户区全部空间。最简单，最简单，适用于单用户、单任务的适用于单用户、单任务的OS。优点优点：易于管理。：易于管理。缺点缺点：对要求内存空间少的程序，造成内存浪费；程序全：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。部装入，
12、很少使用的程序部分也占用内存。第四章 存 储 器 管 理 用户程序用户程序位于位于RAM中的中的操作系统操作系统0 xFFF.0位于位于RAM中的中的操作系统操作系统用户程序用户程序0ROM中的中的设备驱动程序设备驱动程序用户程序用户程序位于位于RAM中的中的操作系统操作系统0单用户存储管理方案第四章 存 储 器 管 理 4.2.2 固定分区分配固定分区分配=把内存分为一些大小相等或不等的分区把内存分为一些大小相等或不等的分区(partition)，每个，每个应用进程占用一个或几个分区。应用进程占用一个或几个分区。操作系统占用其中一个分区。=特点：适用于多道程序系统和分时系统 v支持多个程序并
13、发执行支持多个程序并发执行v难以进行内存分区的共享难以进行内存分区的共享。=问题：可能存在内碎片和外碎片。v内碎片：内碎片：占用分区之内未被利用的空间占用分区之内未被利用的空间 v外碎片外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）：占用分区之间难以利用的空闲分区（通常是小空闲分区）。第四章 存 储 器 管 理 分区的数据结构分区的数据结构：=分区的数据结构：分区表，或分区链表分区的数据结构：分区表，或分区链表 v可以只记录空闲分区，也可以同时记录空闲和占用分区 v分区表中，表项数目随着内存的分配和释放而动态改变，可以规定最大表项数目。v分区表可以划分为两个表格：空闲分区表，占用分
14、区表。从而减小每个表格长度。空闲分区表中按不同分配算法相应对表项排序。=分区的数据结构：分区表，或分区链表分区的数据结构：分区表，或分区链表 第四章 存 储 器 管 理 固定分区分配固定分区分配=分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。=分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。=优点：易于实现，开销小。=缺点：v内碎片造成浪费 v分区总数固定，限制了并发执行的程序数目。=可以和覆盖、交换技术配合使用。=采用的数据结构：分区表记录分区的大小和使用情况把内存划分为若干个固定大小的连续分区。把内存划分为若
15、干个固定大小的连续分区。第四章 存 储 器 管 理 第四章 存 储 器 管 理 4.2.3 动态分区分配动态分区分配 内存不是预先划分好的内存不是预先划分好的动态创建分区：在装入程序时按其初始要求在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配，或在其执行过程中通过系统调用进行分配或改变分区大小。分配或改变分区大小。优点：没有内碎片。缺点：有外碎片；如果大小不是任意的，也可能出现内碎片。第四章 存 储 器 管 理 1.分区分配算法分区分配算法=分区分配算法分区分配算法：寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的
16、大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。=分区释放算法分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。(这时要解决的问题是：合并条件的判断和合并时机的选择)第四章 存 储 器 管 理 首次适应算法FF。(2)循环首次适应算法，该算法是由首次适应算法演变而成的。(3)最佳适应算法。(4)最坏适应算法(5)快速适应算法 2.分区分配算法分区分配算法 第四章 存 储 器 管 理 0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始
17、址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空首次适应算法FFJ1J2J3J4第四章 存 储 器 管 理 0K15K38K48K68K80K110K120K空闲区表空闲区表已分配区表已分配区表始址长度标志20K18K未分配48K20K未分配104K6K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ415K5KJ580K24KJ6104K有个5K的作业J5，24K的作业J6到来：20KJ1J2J3J4J5J6第四章 存 储 器 管 理 分区分配操作分区分配操作 从从头头开开始始查查表表检检索索完完否否？m.size u.siz
18、e?m.sizeu.size size?从从该该分分区区中中划划出出u.size大大小小的的分分区区将将该该分分区区分分配配给给请请求求者者修修改改有有关关数数据据结结构构返返回回返返回回继继续续检检索索下下一一个个表表项项将将该该分分区区从从链链中中移移出出YNNYYN内存分配流程第四章 存 储 器 管 理=循环首次适应算法循环首次适应算法：由首次适应算法演变而成，每次分配均从上次分配的位置之后查找，并将第一个能满足要求的空闲分区分割并分配出去。=最佳适应算法最佳适应算法：找到其大小与要求相差最小的空闲分区 v从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。
19、最坏适应算法最坏适应算法快速适应算法快速适应算法第四章 存 储 器 管 理 最坏适应法最坏适应法要求空闲区按大小递减大小递减的顺序组织空闲区表（或队列）。第四章 存 储 器 管 理 分配：进程申请一个大小为SIZE的存储区时，总是检查空闲区表的第一个空闲区的大小是否大于或等于SIZE。若空闲区小于SIZE，则分配失败；否则从空闲区中分配SIZE的存储区给用户，然后修改和调整空闲区表。第四章 存 储 器 管 理 回收：按释放区的首址，查询空闲区表（队列），若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列）。分配和回收后要对空
20、闲区表（队列）重新排序。第四章 存 储 器 管 理 分析最坏适应法看起来公似乎有些荒唐，但在更加严密地考察后，还是有它的优点：当程序装入内存中最大的空闲区后，剩当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较下的空闲区还可能相当大，还能装下较大的程序。大的程序。另一方面每次仅作一次查询工作。另一方面每次仅作一次查询工作。第四章 存 储 器 管 理 几种策略比较 上述几种放置策略各有利弊，到底哪种最好不上述几种放置策略各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。能一概而论，而应针对具体作业序列来分析。对于某一作业序列来说，某种算法能将该作业对于某一作业序列
21、来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说序列中所有作业安置完毕，那么我们说该算法该算法对这一作业序列是合适的对这一作业序列是合适的。对于某一算法而言，如它不能立即满足某一要对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则求，而其它算法却可以满足此要求，则这一算这一算法对该作业序列是不合适的法对该作业序列是不合适的。第四章 存 储 器 管 理 动态分配算法 举例 例例1 1：有作业序列：作业：有作业序列：作业A A要求要求18K18K；作业；作业B B要求要求25K25K，作业，作业C C要求要求30K30K。系统中空闲区按三种算法组成的空闲区队列。系
22、统中空闲区按三种算法组成的空闲区队列 经分析可知：最佳适应法对这个作业序列是合适的，而经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。其它两种对该作业序列是不合适的。第四章 存 储 器 管 理 练习 有作业序列：作业A要求21K；作业B要求30K，作业C要求25K。第四章 存 储 器 管 理 作业1.已知主存有256KB的容量，其中OS占有顶端的20KB,假如有如下作业序列：作业1要求140KB,作业2要求16KB,作业3要求80KB,作业1完成；作业3完成，作业4要求80KB,作业5要求120KB。试用首次适应分配算法和最佳适应分配算法来处理上述作业序列，并完
23、成：(1)画出作业1，2，3进入主存后，主存的分配情况。(2)画出作业1，3完成后，主存的分配情况。(3)作业4，5是否能够同时投入运行时，若能，画出主存的分配情况。第四章 存 储 器 管 理 某基于动态分区存储管理的计算机，其主存容量为55Mb（初始为空），采用最佳适配（Best Fit）算法，分配和释放的顺序为：分配15Mb，分配30Mb，释放15Mb，分配8Mb，分配6Mb，此时主存中最大空闲分区的大小是（）A、7Mb B、9Mb C、10Mb D、15Mb答案：B第四章 存 储 器 管 理 回收内存 图 4-7 内存回收时的情况 当某一块归还后，前后空间合并，修改内存空闲块表当某一块归
24、还后，前后空间合并，修改内存空闲块表 考虑：上邻、下邻、上下相邻、上下不相邻考虑：上邻、下邻、上下相邻、上下不相邻第四章 存 储 器 管 理 碎片问题 由于空闲区的大小与申请内存的大小相由于空闲区的大小与申请内存的大小相等的情况是很少的，绝大多数情况是从等的情况是很少的，绝大多数情况是从一个空闲区中切去一块，剩下的部分作一个空闲区中切去一块，剩下的部分作为一个空闲区仍留在空闲区表中，随着为一个空闲区仍留在空闲区表中，随着时间的推移，空闲区的发展趋势是越来时间的推移，空闲区的发展趋势是越来越小，直至不能满足任何用户要求。越小，直至不能满足任何用户要求。这种不能被任何用户使用的极小的空闲这种不能被
25、任何用户使用的极小的空闲区称为区称为碎片碎片/零头。碎片的出现造成了存。碎片的出现造成了存储空间的浪费。储空间的浪费。第四章 存 储 器 管 理 在分区存储管理中解决碎片的办法 规定门限值（由操作系统规定，如1K），分割空闲区时，若剩余部分小于门限值，则不再分割此空闲区。定期压缩存储空间，将所有空闲区集中到内存的一端，但这种方法的系统开销太大。-紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域问题：开销 大第四章 存 储 器 管 理 伙伴系统 内存中所有块的长度：2的幂次 划分方式：等分成伙伴分区；回收方式：合并伙伴分区 分配策略：分配2i的分区(2i-1k2i)数据结构：为
26、每一种长度的空闲块保留一个单独的链表；有N个不同的长度，因此最多有N个这样的链表。分配过程：查找划分，直到存在2i的空闲块 回收过程：合并伙伴分区第四章 存 储 器 管 理 伙伴系统优缺点伙伴系统优缺点 缺点内部碎片太大 好处外部碎片更少检索一个合适长度的块的代价比最佳适配等更少而且合并相邻的空闲块很容易在占用块中不需要存储标记字段或者其他信息字段s第四章 存 储 器 管 理 4.2.4 可重定位分区分配可重定位分区分配 1.动态重定位的引入动态重定位的引入 图 4-8 紧凑的示意 操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程
27、序3用户程序6用户程序980 KB(a)紧凑前(b)紧凑后分配一个连续的内存空间“紧凑紧凑”第四章 存 储 器 管 理 2.动态重定位的实现动态重定位的实现 图 4-9 动态重定位示意图 LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存第四章 存 储 器 管 理 3.动态重定位分区分配算法动态重定位分区分配算法 图 4-10 动态分区分配算法流程图 请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数
28、据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否第四章 存 储 器 管 理 分区的保护分区的保护 界限寄存器界限寄存器 保护键保护键第四章 存 储 器 管 理 4.2.5 对换对换(Swapping)=引入：多个程序并发执行，可以将暂时不能执行的程序送到外存多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。目前到达就绪状态的进程。v程序暂时不能执行的可能原因：处于阻塞状态，低优先级（确保高优先级程序
29、执行）=原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出换出swap out），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入换入swap in）。第四章 存 储 器 管 理=优点：增加并发运行的程序数目，并且给用户提供适当的响应时间=缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。=考虑的问题：v程序换入时的重定位；v进程换出的时机 v对外存交换区空间的管理：如动态分区方法；第四章 存 储 器 管 理 4.3 基本分页存储管理方式基本分页存储管理方式 将程序的逻辑地址空间和
30、物理内存划分为将程序的逻辑地址空间和物理内存划分为固固定大小的页或页面定大小的页或页面(page or page frame)，程序，程序加载时，分配其所需的所有页，这些页不必连加载时，分配其所需的所有页，这些页不必连续。续。需要需要CPU的硬件支持的硬件支持。缺点：程序全部装入内存。优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多，地址空间可相应增长。第四章 存 储 器 管 理 地址结构地址结构 分页中的逻辑地址逻辑地址结构如下：页号P位移量W3112110用户程序的划分是由系统自动完成的，对用户是透明的。用户程序
31、的划分是由系统自动完成的，对用户是透明的。对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：MODLAdLAINTP第四章 存 储 器 管 理 用户程序划分用户程序划分 把用户程序按逻辑页划分成大小相等的部分，称把用户程序按逻辑页划分成大小相等的部分，称为页。从为页。从0开始编制页号，页内地址是相对于开始编制页号，页内地址是相对于0编址编址 内存空间内存空间 按页的大小划分为大小相等的区域，称为内存按页的大小划分为大小相等的区域，称为内存块（物理页面，页框）块（物理页面，页框）内存分配内存分配 以页为单位进行分配，并按作业的
32、页数多少来以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻分配。逻辑上相邻的页，物理上不一定相邻第四章 存 储 器 管 理 页表页表 每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序；第四章 存 储 器 管 理 页表页表 图 4-11 页表的作用 用户程序0 页1 页2 页3 页4 页5 页n 页页表页号块号02132638495内存012345678910第四章 存 储 器 管 理 4.3.2 地址变换机构地址变换机构 1.基本的地址变换机构基本的地址变换机构 图 4-12 分页系统的地址变换机构 页表寄存器页表始址页表长度页号(3)页内地址逻辑地址L
33、越界中断1块号b页表页号012物理地址3第四章 存 储 器 管 理 2.具有快表的地址变换机构具有快表的地址变换机构 图 4-13 具有快表的地址变换机构 页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址第四章 存 储 器 管 理 4.3.3 两级和多级页表两级和多级页表 现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。可以采用这样两个方法来解决这一问题：采用离散分配方式来解决难以找到一块连续的大内存空间的问题：只将当前需要的部分页表项调入内存，其余的页表项仍
34、驻留在磁盘上，需要时再调入。第四章 存 储 器 管 理 1.两级页表两级页表(Two-Level Page Table)逻辑地址结构可描述如下：第四章 存 储 器 管 理 图 4-14 两级页表结构 101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345671141151468第n页页表14680121023内存空间第四章 存 储 器 管 理 图 4-15 具有两级页表的地址变换机构 外部页号P1P2外部页内地址页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址第四章 存 储 器 管 理 页式存储管理方案小结 优点：解决了
35、碎片问题 便于管理 缺点：不易实现共享 不便于动态连接第四章 存 储 器 管 理 1、要保证一个程序在主存中被改变了存放位置后仍能正确、要保证一个程序在主存中被改变了存放位置后仍能正确执行，对主存空间应该采用的技术是执行，对主存空间应该采用的技术是 A、静态重定位、静态重定位 B、动态重定位、动态重定位 C、动态分配、动态分配 D、静态分配、静态分配2、在分页系统中，地址结构长度为、在分页系统中，地址结构长度为16位，页面大小为位，页面大小为2K，作业地址空间为作业地址空间为6K，该作业的各业依次存放在，该作业的各业依次存放在2,3,6号物号物理地址块中，相对地址理地址块中，相对地址2500处
36、有一条指令处有一条指令 Store 1,4500 则该指令的物理单元及数据存放的物理单元是则该指令的物理单元及数据存放的物理单元是 A、6596,12692 B、4548,10644 C、8644,12692 D、6596,10644 BA第四章 存 储 器 管 理 4.4 基本分段存储管理方式基本分段存储管理方式 4.4.1 分段存储管理方式的引入分段存储管理方式的引入 引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：1)方便编程 2)信息共享 3)信息保护 4)动态增长 5)动态链接 第四章 存 储 器 管 理 1.基本思想 用户程序划分 按程序自身的逻辑关系划分为若干个
37、程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的 逻辑地址段号 段内地址第四章 存 储 器 管 理.0S工作区段工作区段B主程序段主程序段M.0EP子程序段子程序段X0K.CALL X E.CALL Y FCALL A 116.0FL子程序段子程序段Y0116N数组数组A12345.第四章 存 储 器 管 理 操作系统操作系统.B0SA0NY0LX0PM0K逻辑段号逻辑段号01234作业作业1的地址空间的地址空间10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000长度长度 段地址
38、段地址01234操作系统操作系统第四章 存 储 器 管 理 基本思想（续）内存划分 内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定 内存分配 以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放第四章 存 储 器 管 理 2.管理 段表 记录了段号，段的首（地）址和长度之间的关系 每一个程序设置一个段表，放在内存 属于进程的现场信息段号段号012段首址段首址段长度段长度58K20K100K110K260K140K第四章 存 储 器 管 理 图 4-16 利用段表实现地址映射 作业空间(MAIN)0
39、030K(X)1020K(D)2015K(S)3010K30K20K15K10K40K80K120K150K段长基址段号(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表内存空间0123第四章 存 储 器 管 理 控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址图 4-17 分段系统的地址变换过程 3.地址变换机构 第四章 存 储 器 管 理 段式存储管理方案小结优点：便于动态申请内存 管理和使用统一化 便于共享 便于动态链接缺
40、点：产生碎片思考：与可变分区存储管理方案的相同点与不同点？第四章 存 储 器 管 理 4.分页和分段的主要区别分页和分段的主要区别 (1)页是信息的物理单位。分页的目的是为了提高内存的利用率。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。(2)页的大小固定且由系统决定，段的长度却不固定。(3)分页的作业地址空间是一维的，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。第四章 存 储 器 管 理 一个分段存储管理系统中，地址长度是32位，其中段号占8位，则最大段长是
41、A、28字节 B、216 C、224 D、232答案：C第四章 存 储 器 管 理 4.4.4 段页式存储管理方案 1、产生背景 结合页式段式优点，克服二者的缺点2、基本思想 用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）逻辑地址：内存划分：按页式存储管理方案 内存分配：以页为单位进行分配段号段号段内地址段内地址页号页号页内地址页内地址第四章 存 储 器 管 理 3.管理管理 段表：记录了每一段的页表始址和页表长度 页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）第四章 存 储 器 管 理 图 4-21 利用段表和页表实
42、现地址映射 段号状态页表大小页表始址0111213041页号状态存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器第四章 存 储 器 管 理 2.地址变换过程地址变换过程 图 4-22 段页式系统中的地址变换机构 段表寄存器段表始址段表长度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度第四章 存 储 器 管 理 小结连续存储连续存储非连续存储非连续存储静态划分静态划分动态划分动态划分伙伴系统伙伴系统定长分区定长分区异长分区异长分区分区分配算法分区分配算法静态划分静态划分动态划分动态划分页式页式段式段式段页式段页式地址映射机制：地址映
43、射机制：寄存器、寄存器、寄存器寄存器使用表/空闲表/链队列位示图/空闲页框表/地址映射机制：地址映射机制：、基址基址界限界限页表页表/段表段表/段页表段页表页表寄存器页表寄存器段表寄存器段表寄存器快表快表第四章 存 储 器 管 理 4.4.5 信息的共享和保护 信息的共享 信息的保护第四章 存 储 器 管 理 1 信息共享信息共享ed 1ed 2ed 40data 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存0212260617071
44、80页表图 4-18 分页系统中共享editor的示意图第四章 存 储 器 管 理 图 4-19 分段系统中共享editor的示意图 editor进程1data 1进程2editordata 2段表段长基址16080402401608040380editordata 1data 280240280380420第四章 存 储 器 管 理 2、信息的保护、信息的保护 越界检查 存取控制检查 环保护机制第四章 存 储 器 管 理 4.5 虚拟存储器的基本概念虚拟存储器的基本概念 4.5.1 虚拟存储器的引入虚拟存储器的引入 1.常规存储器管理方式的特征常规存储器管理方式的特征 一次性。(2)驻留性。
45、思考：思考：程序必须小于内存或完全装入内存才能运行？程序必须小于内存或完全装入内存才能运行？程序暂时不执行或运行完是否还必须占用内存？程序暂时不执行或运行完是否还必须占用内存？第四章 存 储 器 管 理 2.理论依据：程序局部性原理理论依据：程序局部性原理 在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面：时间局部性 一条指令被执行了，则在不久的将来它可能再被执行（程序中大量的循环操作）空间局部性 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用（程序的顺序执行）第四章 存 储 器 管 理 虚拟存储技术虚拟存储技术虚存：把内存与外存有机的结合起来使
46、用，从而得到一个容量很大的“内存”，这就是虚存实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作目的：提高内存利用率第四章 存 储 器 管 理 3.虚拟存储器定义虚拟存储器定义 所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。第四章 存 储 器 管 理 4.5.2 虚拟存储器
47、的特征虚拟存储器的特征 多次性多次性 对换性对换性3.虚拟性虚拟性 第四章 存 储 器 管 理 4.6 请求分页存储管理方式请求分页存储管理方式基本思想基本思想 在进程开始运行之前，不是装入全部页面，而在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面汰某个页面，以便装入新的页面 基本分页基本分页+请求调页功能请求调页功能+页面置换功能页面
48、置换功能第四章 存 储 器 管 理 XXXX7X5XXX34061260K-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虚地址空间虚地址空间物理地址空间物理地址空间 虚页虚页页框页框第四章 存 储 器 管 理 1.页表机制页表机制 页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地
49、址 第四章 存 储 器 管 理 2 缺页中断（缺页中断（Page Fault）处理）处理在地址映射过程中，在页表中发现所要访问的在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，据页表中给出的外存地址，将该页调入内存，使作业继续运行下去使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻页装入内存，并修改页表中相应页表项目
50、的驻留位及相应的内存块号留位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存该页在内存期间被修改过，则要将其写回外存第四章 存 储 器 管 理 3.地址变换机构地址变换机构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是
