第四章_存储器管理

1、第四章第四章 存储器管理存储器管理计算机系统存储层次寄存器高速缓存主存储器磁盘缓存固定磁盘可移动存储介质Cpu内部寄存器内存外存n存储器包括内存和外存；n外存容量大，速度慢，价格低（每位价格） ，可以长期保存程序和数据；n内存容量小，速度快，价格高（每位价格），内存是易失性的，不能永久存储信息；n在计算机系统中，外存是作为外部设备存在的；n本章主要讨论对内存的管理存储器管理的对象外存内存OS装入内容提要内容提要n 存储器管理的任务n 程序的装入和链接n 内存分配技术n 虚拟存储管理技术 请求分页式存储管理方式 页面置换算法 请求分段式存储管理方式4.1 4.1 存储器管理的任务存储器管理的任务

2、存储器管理的任务n内存的分配与回收n地址重定位n存储共享n存储保护n存储扩充存储分配与回收n基本任务：管理内存空间的分配与回收n计算机内存被划分成两部分：系统区和用户区系统区：用于存放操作系统的程序和数据用户区：用于装入并存放各个用户进程的程序和数据n内存空间的分配与回收主要是针对用户区的分配和管理分配基本内存空间增加新的内存空间 动态申请或释放内存空间回收内存空间地址空间和逻辑地址n用户源程序经编译链接后形成的代码所限定的地址叫做该程序的地址空间。n地址空间中各个地址叫做相对地址，或逻辑地址，又叫虚地址。n逻辑地址的特点：其首地址为0，其余指令的地址都相对于首地址来编址不能用逻辑地址在内存中

3、读取信息存储空间和物理地址n指物理存储器中全部物理存储单元的集合所限定的空间。n每个存储单元都有它自己的编号地址，该地址被称为绝对地址，或物理地址，也叫实地址。n存储空间的大小由系统的硬件配置决定。进程在内存的映像进程控制块程序数据栈进程控制信息程序入口点当前栈顶跳转指令数据访问地址值增加进程执行时的寻址地址重定位n地址重定位：对目标程序中的指令和数据地址进行修改的过程。n把程序地址空间的逻辑地址转换为存储空间的物理地址的工作叫做地址重定位，又叫地址映射或地址变换。源程序源程序逻辑地址空间逻辑地址空间物理地址空间物理地址空间编译连接编译连接地址映射地址映射0100200逻辑地址、物理地址和地址

4、映射逻辑地址、物理地址和地址映射mov r1, data1data1 3456mov r1, 2003456100011001200mov r1, 12003456BA=1000地址重定位分类n静态地址重定位n动态地址重定位静态地址重定位n静态地址重定位：重定位工作是在程序装入主存时，由静态重定位装入程序集中一次完成，程序运行时不再改变。源程序源程序逻辑地址空间逻辑地址空间物理地址空间物理地址空间编译链接编译链接装入装入0100200逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射mov r1, data1data1 3456mov r1, 2003456100011001200mov

5、 r1, 12003456BA=1000静态重定位示意图静态地址重定位n特点：静态重定位实现简单，不需要硬件的支持静态重定位方法将程序一旦装入内存就不能再移动，且必须在程序执行之前将有关部分全部装入，主存利用率低。使用静态重定位方法进行地址变换不适合多道程序系统；不允许系统执行内存的碎片整理；无法实现虚拟存储器。不能做到程序和数据的共享。动态地址重定位n动态地址重定位：操作系统将程序装入内存之后，并不立即把目标程序中的逻辑地址转换为物理地址，而是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据的逻辑地址转换成内存地址。n特点：动态地址重定位依靠硬件地址变换机构完成。源程序源程序逻辑

6、地址空间逻辑地址空间物理地址空间物理地址空间编译链接编译链接装入装入0100200mov r1, data1data1 3456mov r1, 2003456100011001200mov r1, 2003456动态重定位示意图动态重定位示意图内存重定位寄存器CPU1000逻辑地址物理地址2001200动态重定位优点n动态重定位的优点（1）可以对内存进行非连续分配。显然，对于同一进程的各分散程序段，只要把它们在内存的首地址统一存放在不同的寄存器中，则可以由地址变换机构得到正确的待访问内存地址。（2）将程序装入内存之后仍可以再移动。（3）动态重定位提供了实现虚拟存储器的基础。因为动态重定位不要求

7、在作业执行前为所有程序分配内存，也就是说，可以部分地、动态地分配内存。（4）有利于程序段的共享。存储保护n防止地址越界，防止操作越权n地址越界：进程访问不属于自己的地址空间，或者说进程在运行时所产生的物理地址超越其自身的地址空间范围。可能侵犯其他用户进程空间也可能侵犯操作系统的存储空间n操作越权：进程对共享存储区的操作违反了系统规定的权限。存储共享n为了进程通信和节约内存空间，两个或多个进程共用内存中相同的分区，即他们的物理空间有相交的部分。n可以共享进程的代码，也可以共享进程数据n一般地，进程之间共享代码的目的主要是为了节约内存空间，共享数据的目的主要是为了实现进程间相互通信。共享数据n通过

8、共享存储区实现进程通信一个进程将共享数据写入共享存储区另一个进程从共享存储区读出数据共享程序n设计程序时，一般包括程序代码和数据两部分。n如果存储时，程序的代码区和数据区分开存放，代码区不包含运行程序时需要改变的数据，被处理的数据都放在独立的数据区，这样，进程执行过程中就不会修改代码区中的任何代码n很多的编译程序支持可重入的程序设计，这样，程序员在写程序时不需要考虑将程序代码和数据严格分开，编译程序在编译时会自动将数据和程序代码分开存储，以保证代码部分是纯的、可重入的。共享程序n可重入代码：又称纯代码，是指程序代码的一个副本在同一段时间中可被多个进程共享使用。n可重入的两个重要特征：程序代码不

9、能修改自身；每个用户的局部数据必须单独保存存储扩充n内存：速度快、容量小、价格贵n外存：容量大、速度慢、价格便宜n目的：在多道程序系统中能运行更多、更大的程序，降低系统的造价，提高系统的性价比n存储扩充：采用软件手段，在硬件的配合下，将部分外存空间虚拟为内存空间，并将内存和部分外存有机地结合起来，得到一个容量相当于外存、速度接近内存、价格十分便宜的虚拟存储系统。存储扩充n虚拟存储系统在逻辑上对外是一个整体，用户感觉到系统提供了一个非常大的内存空间。n操作系统负责完成内存与外存之间的透明切换：进程运行时将需要的数据或代码从外存装入内存，并将内存中暂时不用的部分交换到外存。4.2 4.2 程序的装

10、入和链接程序的装入和链接可执行程序的生成步骤n 一个用户源程序变为一个可在内存中执行的程序通常要经过以下几个步骤：编译：由编译程序将用户源代码编译成若干个目标模块；链接：由链接程序将编译后形成的一组目标模块以及它们需要的库函数链接在一起，形成一个完整的装入模块；装入：由装入程序将装入模块装入内存（构造PCB，形成进程）。对用户程序的处理步骤对用户程序的处理步骤对用户程序的处理步骤可执行程序的装入n如何装入待执行的程序及其所需的数据？n何时将程序的逻辑地址转换为物理地址？n3种装入方式：p绝对装入p可重定位装入p动态运行时装入绝对装入n 程序运行之前，按照程序的逻辑地址，将程序和数据装入内存指定

11、的地方。n实现简单，无须进行逻辑地址到物理地址的映射。绝对装入缺点n 程序每次必须装入同一内存区；n程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址；n程序的修改（增加或删除指令）将引起整个程序中指令地址的变动；n程序中的所有存储引用，例如函数调用或过程调用等，在装入之前都必须转换为物理地址，这不利于存储共享。可重定位装入n 允许将程序装入与逻辑地址不同的物理内存空间。即程序可以装入到内存的任何位置，其逻辑地址与装入内存后的物理地址无直接关系。n但是必须进行地址映射，将逻辑地址转换为物理地址。n静态重定位技术：地址映射在程序装入时进行，以后不再更改程序地址。可重定位装入n但是，

12、静态重定位不允许程序在内存中移动。这不便于进程交换和紧凑拼接操作，也很难实现多道程序环境下，多个程序同时装入内存的要求。n因此，重定位装入方式只适合于单道程序环境。可重定位装入Mov r1,50012340100500599Mov r1,1500010001100150015991234OS作业的地址空间作业的地址空间存储空间存储空间装入程序装入程序把程序装入起始地址为把程序装入起始地址为1000的内存区的内存区可重定位装入方式可重定位装入方式动态运行时装入n程序的地址转换不是在装入时进行，而是在程序运行时动态进行。n运行时动态装入需要硬件支持，即重定位寄存器，用于保存程序在内存中的起始地址。

13、n程序被执行时，通过重定位寄存器内的起始物理地址和指令或数据的逻辑地址计算其物理地址。n运行时动态装入有利于多道程序环境下，进程的换入/换出及实现紧凑技术。动态运行时装入把程序装入到起始地址为把程序装入到起始地址为1000的内存区的内存区Mov r1,50012340100500599作业的地址空间作业的地址空间Mov r1,500010001100150015991234存储空间存储空间1000+BR逻辑地址逻辑地址物理地址物理地址动态运行时装入动态运行时装入100VR可执行程序的链接n目标模块如何链接成装入模块？n2种链接方式：p静态链接p动态链接： 装入时动态链接 运行时动态链接静态链接

14、n程序被装入内存之前，必须完全链接成一个装入模块，将其中的存储引用全部转换成相对地址跳转语句，并将多个目标模块链接称为一个模块，使装入模块中的每一条指令具有相对于整个模块的第一条语句的逻辑地址。n静态链接生成的装入模块可以采用重定位装入或运行时动态装入方式。n静态链接需要花费大量的处理机时间。而其中的很多模块将不会运行，浪费存储空间和处理机时间。目标模块链接成装入模块模块1if(x1)call m1else call m2模块m1模块m2模块1if(x1)模块m1Else模块m2链接目标模块装入模块动态链接n不用事先链接多个目标模块形成一个完备的装入模块，而是生成一个含有未被链接的外部模块引用

15、的装入模块，这些外部模块可以在装入时链接，也可以在运行时链接。装入时动态链接n 当系统装入含有未链接的外部模块引用的装入模块时，每当遇到一个外部模块引用，则查找相应的目标模块。将其装入内存，并将模块内的指令地址转换为相对于整个装入模块起始地址的相对地址。n优点：有利于目标模块的更新与升级；有利于代码共享；有利于扩充软件的功能，可以将扩充部分作为动态链接模块。n但是，可能链接一些不会执行的模块，浪费存储空间和处理机时间。运行时动态链接n外部模块引用直至程序执行时才装入内存，并链接到装入模块中，进行地址转换。n可以解决静态链接和装入时动态链接都面临的存储空间和处理机时间浪费问题，不需要执行的模块就

16、不会装入内存。n广泛用于事务处理系统，如航空售票系统、银行管理系统等。简单存储n简单存储，或基本存储，相对于虚拟存储而言，指为了实现简单，执行之前，操作系统必须将待执行的程序全部装入内存。n然而，现代操作系统大都支持虚拟存储功能，允许进程装入部分程序即可执行，其余部分保留在外存。当执行所需的部分不在内存时，中断进程执行，使之阻塞等待，直到相应部分装入内存。程序在内存中如何组织n连续存储：需要内存中一块连续的、足够大的分区 n如果内存中没有足够大的连续内存分区，但存在总量足够的独立小分区，即外零头。系统要么拒绝分配空间，要么采用紧凑技术拼接外零头。n采用的连续存储技术：分区管理程序在内存中如何组

17、织n非连续存储：允许进程的程序和数据分别装在内存的不同分区中n必须登记一个进程分到的所有分区的位置、大小、使用情况等信息。n采用的非连续存储技术：分页存储技术、分段存储技术及段页式存储技术。4.3 4.3 连续分配方式连续分配方式连续分配n连续分配是指为用户程序分配连续的内存空间。n分类单一连续分配分区管理 固定分区 动态分区 动态重定位分区 单一连续分配方式n这是一种最简单的存储管理方式n在这种管理方式下，内存区分为系统区和用户区两部分，系统区仅供操作系统使用，用户区提供给用户使用n只能用于单用户、单任务的操作系统中n不支持虚拟存储方式单一连续分配方式n优点：管理简单，易于实现存储保护n缺点

18、：系统的存储空间浪费较大当正在执行的程序因等待某个事件，如等待外部设备输入数据，处理机就处于空闲状态。限制了用户程序和系统程序的可重入性，因而主存中的程序和数据不能被共享。系统的外围设备也只有一个程序使用，因此外围设备的利用率低。分区管理n基本思想： 将内存的用户可用区划分成若干个大小相等或不等的区域，每个进程占据一个区域，从而实现多道程序设计环境下各并发进程共享主存空间。n分类p固定分区p动态分区p可重定位分区固定分区管理n一种最简单的可运行多道程序的存储管理方式n将内存用户空间划分为若干个固定大小的区域，每个分区只装入一道作业，这样允许有几道作业并发运行。n当有空闲分区时，便可从外存的后备

19、作业队列中选择一个适当大小的作业装入该分区。划分分区的方法n分区大小相等分区大小相等：所有的内存分区大小相等。这种方法只适合于多个相同程序的并发执行。n分区大小不等分区大小不等：把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。这样，可根据程序的大小为之分配当前空闲的、适当大小的分区。固定分区Operating System8M8M8M8M8M固定分区（大小相同）固定分区（大小相同）Operating System8M2M6M8M12M4M固定分区（大小不同）固定分区（大小不同）固定分区的内存分配分区号分区号大小大小起始地址起始地址状态状态11220已分配已分配23232已分配已

20、分配36464已分配已分配4128128已分配已分配操作系统操作系统作业作业A作业作业B作业作业C作业作业D20K32K64K128K256K分区说明表分区说明表存储空间分配情况存储空间分配情况n 建立分区说明表来描述各个分区的分配情况。固定分区n优点：简单n缺点：内存利用不充分。因为作业的大小不可能刚好等于某个分区的大小，绝大多数已分配的分区中，都有一部分存储空间被浪费掉了，这个被浪费的空间叫做内部碎片（占用分区之内未被利用的空间）。动态分区分配n系统初始化时，除了操作系统中常驻主存部分以外，只存在一个空闲分区n分配程序根据进程的大小动态的划分分区n特点：p各分区的大小是不定的p内存中分区的

21、数目也是不定的动态分区分配FIFO调度方式时的内存初始分配情况调度方式时的内存初始分配情况动态分区分配中的数据结构n空闲分区表（链）：所有的空闲分区组成的一个表（链），用来记录内存中每个空闲分区的情况：包括分区序号，分区始址，分区大小等数据项。n已分配分区表：所有已分配分区组成的一个表，用来记录内存中每个已分配分区的情况：包括分区序号，分区始址，分区大小等数据项。动态分区分配中的数据结构空闲分区表空闲分区表空闲分区链空闲分区链连续分配方式（续）连续分配方式（续）利用空闲区表和已分配区表分配内存利用空闲区表和已分配区表分配内存连续分配方式（续）连续分配方式（续）利用空闲区表和已分配区表分配内存利

22、用空闲区表和已分配区表分配内存分配内存操作n(1)利用某种算法，从空闲分区中找到所需大小的分区。n(2)若找到的空闲分区和请求的分区的差值大于事先规定的不再切割的剩余分区的大小，则将空闲分区一分为二，一部分分配给进程，另一部分仍作为空闲区留在表中。n(3)将分配区的首址返回给调用者。动态分区分配算法动态分区分配算法n首次适应算法（First Fit，FF）n循环首次适应算法(Next Fit，NF)n最佳适应法(Best Fit，BF)首次适应算法n首次适应算法：要求空闲分区按地址递增的次序排列。当进行内存分配时，从空闲区链（表）链首开始顺序查找，直到找到第一个能满足其大小要求的空闲区为止。分

23、一块给请求者，余下部分仍留在空闲链中。n特点：优先利用低地址部分的空闲分区，保留了高地址部分的大空闲区。低地址端可能留下许多很小的空闲分区，而每次查找是从低地址部分开始，会增加查找开销。连续分配方式（续）连续分配方式（续）循环首次适应算法n由首次适应算法演化而来。在为进程分配内存空间时，不再每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划分出一块与请求大小相等的内存空间分配给作业。n特点：p使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销。p缺乏大的空闲分区。最佳适应法n要扫描所有的空闲分区，以获得能满足进程需求的且

24、为最小的空闲区。如果该空闲分区大于作业的大小，则将剩余空闲区仍留在空闲区链表中。n可从小到大对空闲区排序，方便查找。n特点：p因为分配分区要查找整个链表，所以比首次适应算法效率低。p因为它可能把主存划分得更小，成为无用的碎片（外部碎片），所以它比首次适应要浪费更多的存储空间。回收内存操作n进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链（表）中找到插入点。可能会出现以下四种情况之一：F1回收区 回收区F2F1回收区F2F1回收区F2回收内存操作p回收区与插入点的前一个空闲分区相邻接：此时将回收区与前一个分区合并，不必为回收分区分配新的表项，只需修改前一分区的大小。p回收分区与插入点的后

25、一空闲分区相邻接：此时将两个分区合并，形成新的空闲分区，用回收区的首址作为新空闲区的首址，大小为两者之和。p回收区同时与插入点的前后两个分区邻接：此时将三个分区合并，使用前一个分区的表项和首址，取消后一个分区的表项，大小为三个分区大小之和。p回收区既不与插入点的前一个空闲分区邻接，也不与后一个空闲分区邻接：这时应为回收区单独建一个表项，填写回收区的首址和大小，并根据其首址插入到空闲区链（表）的适当位置。分区管理方式n 优点：p有助于多道程序设计，提高了内存的利用率p要求硬件支持少，代价低 p管理算法简单，实现容易n 缺点：p必须给作业分配一连续的内存区域 p不能实现对内存的扩充p碎片问题严重，

26、内存仍不能得到充分利用 n 解决“碎片”问题的一种方法紧凑 内存拼接（紧凑）n如果作业请求的存储空间大于系统中任何一个空闲分区，但小于这些分区容量的总和时，利用动态重定位方法，移动内存中的所有作业，使它们在内存相邻接。这样，我们不需要对作业做任何修改，只要用该作业在内存的新起始地址，去置换原来的起始地址即可。n这种通过移动内存中作业的位置，把原来多个分散的小的空闲分区拼接成一个大空闲分区的方法，称为“拼接”或“紧凑”。内存拼接（紧凑）内存拼接（紧凑）n 代价与时间 紧凑的开销很大，当系统中每个空闲区域单独均不能满足进程请求的空间大小，但所有空闲区域之和能够满足时才进行一次紧凑。n 思考:如何实

27、现紧凑? 动态地址重定位加入紧凑功能的动态重定位分区分配算法 动态分区分配算法流程图动态分区分配算法流程图 请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否连续分配和离散分配n连续分配即要求给进程分配连续的内存空间。n连续分配方式会形成许多“碎片”，系统为拼接碎片会花费很大的系统开销。n离散分配：即允许一个进程直接分散地装入到许多不相邻接的分区中。n如果离散分配的基本单位是页，则称之为分页式存储管理方式；如果离散分配的基本单位是

28、段，则称为分段式存储管理方式。4.4 4.4 基本分页存储管理方式基本分页存储管理方式基本分页存储管理方式的实现原理n将一个进程的逻辑地址空间分成若干个大小相等的页，同时把内存空间以与页相等的大小划分为大小相等的内存块（物理块），这些内存块为系统中的任何进程所共享。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。实现原理示意图用户程序0 页1 页2 页3 页4 页5 页n 页内存012345678910指定进程页到空闲物理块01234567891011121314内存15个可用帧A.0A.1A.2A.301234567891011121314内存加载进程A

29、A.0A.1A.2A.3B.0B.1B.201234567891011121314内存加载进程BA.0A.1A.2A.3B.0B.1B.2C.0C.1C.2C.301234567891011121314内存加载进程C指定进程页到空闲物理块A.0A.1A.2A.3C.0C.1C.2C.301234567891011121314内存换出BA.0A.1A.2A.3D.0D.1D.2C.0C.1C.2C.3D.3D.401234567891011121314内存加载进程D页面和物理块n页面：进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。n物理块

30、：内存空间被分成与页面相同大小的若干个存储块，称为物理块或内存块， 也同样为它们加以编号，如0块、1块等等。页表n页表是系统为每个用户进程建立的一张页面映像表，用来记录进程的每个页面对应的物理块，一般放在内存。n页表的作用是实现从页号到物理块号的地址映射页表的作用用户程序0 页1 页2 页3 页4 页5 页n 页页表页号块号02132638495内存012345678910页面大小n在分页系统中页面的大小是由机器的地址结构所决定的，亦即由硬件决定。对于某一种机器只能采用一种大小的页面。n页面的大小要选择的适中。p若选择的页面较小，虽然可使内存碎片减小，提高内存利用率，但也会使每个进程占用较多的

31、页面，从而导致进程的页表过长，占用大量内存； p若选择的页面较大，虽然可以减少页表的长度，但却又会使页内碎片增大。p通常页面的大小是2的幂，且常在29-212之间，即在512字节-4K字节之间地址变换n地址变换即通过地址变换机构把逻辑地址变换成相应的物理地址，实际上是将逻辑地址中的页号，转换为内存中的物理块号。因为页表的作用就是用于实现页号到物理块号的地址映射，因此，地址变换任务是借助于页表来完成的n除此以外，系统设置了一个页表寄存器PTR,其中存放页表在内存的始址和页表的长度 页表寄存器页表寄存器n用来存放页表在内存的起始地址和长度的寄存器。n平时，进程未执行时，页表的始址和页表长度存放在本

32、进程的PCB中，当调度程序调度到某进程时，才将这两个数据装入页表寄存器。 动态地址变换n 地址结构p逻辑地址可以分解成：页号、页内位移量（页内地址） p物理地址可以分解成：物理块号、物理块内位移（物理块内地址） 页号页号p p 页内位移量页内位移量w w 0 0111112 12 3131p=逻辑地址/页面大小 w=逻辑地址%页面大小地址变换过程 根据逻辑地址计算出页号p和页内地址d， p=逻辑地址/页面大小 d=逻辑地址%页面大小 根据页号p查页表，得到对应块号f 块内地址和页内地址相同，计算物理地址 物理地址=f块大小+d （块大小等于页大小）n 由于页面大小为2的幂，则页号和页内地址可以

33、直接取高位和低位部分获得，物理地址可以用块号和块内地址拼接而成分页系统的地址变换机构分页系统的地址变换机构页表寄存器页表始址页表长度页号(3)页内 地 址逻辑地址L越界中断1块号b页表页号012物理地址3分页系统的地址变换机构分页系统的地址变换机构示例示例1 例例 说明运行作业的地址变换过程。说明运行作业的地址变换过程。 如下页图所示，作业地址空间共有如下页图所示，作业地址空间共有7 7个页，每页的大小个页，每页的大小为为10241024。其对应的主存块在页表中已列出。其对应的主存块在页表中已列出。 假定页表假定页表在主存始址为在主存始址为500500，页表中每个页表项占用一个字节。，页表中每

34、个页表项占用一个字节。若该程序从第若该程序从第0 0页开始运行，且现程序计数器内容（逻页开始运行，且现程序计数器内容（逻辑地址）为：辑地址）为：0100逻辑地址逻辑地址示例示例1页表寄存器页表寄存器逻辑地址逻辑地址L500 70 ( (页号）页号） 100（页内地址）（页内地址）+页表页表5（内存块号）内存块号） 100（页内地址）（页内地址）1234页式地址变换过程页式地址变换过程012345657915131016500每页的大小每页的大小为为10241024内存地址：内存地址：5 51024+100=52201024+100=5220500+0500+0* *1=5001=500示例2例

35、：在分页存储管理系统中，允许作业最大64KB，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址是多少？分析：块内地址=页内地址 块大小=页大小 假设为块大小2n字节,则页内地址和块内地址占n位 逻辑地址的位数为s，则作业最大可以为2s字节 逻辑地址的低n位为页内地址，高s-n位为页号 物理地址的位数为t，则内存空间大小为2t字节 物理地址的低n位为块内地址，高t-n位为块号 示例2答：由题目所给条件可知，分页存储管理系统的逻辑地址结构为： 15 12 11 0 逻辑地址2F6AH的二进制表示如下： 0010 11110110

36、1010 页号 页内位移 由此可知逻辑地址2F6AH的页号为2，小于页表长度3，没有越界，该页存放在第11个物理块中，用十六进制表示块号为B，所以物理地址为BF6AH。 页号页号 页内位移页内位移快表n由于页表存储在内存中，所以当要按照给定的逻辑地址进行读/写时，需要两次访问内存:p第一次是根据页号访问页表，读出页表相应栏中的块号以便形成物理地址；p第二次是根据物理地址进行读/写操作。n这样比通常执行指令的速度慢一倍。为了提高存取速度，在地址变换机构中增设了一个具有并行查找能力的特殊高速缓冲存储器，又称为“联想存储器”或“快表”，用来存储当前访问的哪些页表项。快表地址映象快表的格式- - 访问

37、位：指示该页最近是否被访问过。访问位：指示该页最近是否被访问过。0 0表示没有被访表示没有被访问，问，1 1表示访问过表示访问过 ；- - 状态位：指示该寄存器是否被占用。状态位：指示该寄存器是否被占用。0 0表示空闲，表示空闲，1 1表表示占用。示占用。页页 号号 块块 号号 访访 问问 位位 状状 态态 位位利用快表进行读/写操作的过程n首先按逻辑地址中的页号先查快表，若该页在快表中，则立即能得到相应的物理块号并与页内地址形成物理地址；n若该页不在快表中，则再查内存中的页表找到相应的块号，形成物理地址，同时将该页的对应项写入快表。n若快表已满，则按照一定策略淘汰一个旧项。最简单的策略是“先

38、进先出”原则，即淘汰最先进入快表的那一项。具有快表的地址变换机构页表寄存器页表始址页表长度页号页内 地 址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址具有快表的地址变换机构页表寄存器页表寄存器逻辑地址逻辑地址L500 70 ( (页号）页号） 100（页内地址）（页内地址）+页表页表5（内存块号）内存块号） 100（页内地址）（页内地址）12345使用快表后的地址变换过程使用快表后的地址变换过程012345657915131016500每页的大小每页的大小为为10241024内存地址：内存地址：5 51024+100=52201024+100=5220500+0=500

39、500+0=50005快表快表越界中断越界中断基本分页存储管理方式的分配算法基本分页存储管理方式的分配算法请求请求n个页面个页面空闲页面表中有空闲页面表中有n个个空闲页面吗？空闲页面吗？设置页表，将页表始址设置页表，将页表始址页表长度置入页表寄存器页表长度置入页表寄存器搜索内存空闲页面，分配搜索内存空闲页面，分配n个页面，个页面，将页面号和对应的物理块号填入页表将页面号和对应的物理块号填入页表无法分配无法分配否否是是分页存储管理的评价n彻底消除了外部碎片，仅有很少的内部碎片，提高了内存利用率。n分页操作由系统自动完成，一个页面不能实现某种逻辑功能。用户看到的逻辑地址是一维的，无法调试执行其中的

40、某个子程序或子函数。n采用分页技术不易实现存储共享，也不便于进程的动态链接。4.5 4.5 基本分段存储管理方式基本分段存储管理方式基本分段存储管理n基于模块化的程序设计时，常常需要将一个大任务划分成若干相对独立的子任务，对应于子任务编写子程序，称为段。n每个子程序可以独立的编辑、编译、链接和执行n各个子程序由实现的功能决定，长度各不相同。执行时，根据实际需要，将若干子程序链接成一个大程序。基本分段存储管理方式的实现原理n每个作业的逻辑地址空间按照自身的逻辑关系划分成若干段（比如主程序段、子程序段、数据段、堆栈段等）。n每个段都有自己的名字，通常可用一个段号来代替段名。n每个段都从0开始独立编

41、址，段内地址连续。n段的长度由相应的逻辑信息组的长度决定，因而各段的长度不等。n分配内存时，为每个段分配一连续的存储空间，段间地址空间可以不连续。作业空间(MAIN) 0030K(X) 1020K(D) 2015K(S) 3010K30K20K15K10K40K80K120K150K段长 基址段号(MAIN) 030K(X) 120K(D) 215K(S) 310K040K80K120K150K段表内存空间01230123逻辑段号实现原理段式地址结构 段号段号 段内地址段内地址31 12 11 0n 每个段的地址空间都是从“0”开始编址的一维地址空间；n作业的地址空间是二维地址空间；n每一个逻

42、辑地址均由两部分组成：段号和段内位移；段表n用于实现从逻辑段到物理内存区的映射；n进程的每个段在段表中占有一个表项，称为段表项；n每个段表项由段基址、段长度和段的存取方式组成。段表作业空间(MAIN) 0030K(X) 1020K(D) 2015K(S) 3010K30K20K15K10K40K80K120K150K段长 基址段号(MAIN) 030K(X) 120K(D) 215K(S) 310K040K80K120K150K段表内存空间0123利用段表实现地址映射地址变换机构分段系统的地址变换过程分段系统的地址变换过程8K+100存储保护n 在分段存储管理方式中，用户各分段是信息的逻辑单位

43、，因此容易对各段实现保护 。p越界保护 在地址变换过程中，段号和段表长度的比较，以及段内地址和段长的比较。p越权保护 在段表中设置存取控制字段来对各段进行保护。分段系统的快表n分段系统中，为了访问内存中的一条指令或数据，需要两次访问内存：第一次，访问内存中的段表，获得段的起始地址。根据段的起始地址和段内偏移量，计算出物理地址第二次，根据计算得到的物理地址，访问内存中的指令或数据。n为了提高系统效率，可以为分段系统增加一个快表，用于保存最近使用过的段表项。对分段系统的评价n有效消除了内部碎片，提高了内存利用率n允许子程序独立编译和修改，而不需要重新编译或链接其他相关子程序n容易实现存储共享n具有

44、较高的安全保障n很容易满足程序段的动态增长需要。分页和分段的比较n都采用非连续存储，由地址映射实现地址变换n区别：页是信息的物理单位，分页是为了系统管理内存的方便而进行的，故对用户而言，分页是不可见的，是透明的；段是信息的逻辑单位，分段是作业逻辑上的要求，对用户而言，分段是可见的。页的大小是固定的，由系统决定；段的大小是不固定的，由用户作业本身决定。从用户角度看，分页的地址空间是一维的，而段的地址空间是二维的 。段的共享与保护n段是信息的逻辑单位，分段式存储管理可以方便的实现内存信息共享，并有效进行内存保护。信息共享例：一个多用户系统，可同时接纳40个用户，他们都执行一个文本编辑程序。如果文本

45、编辑程序有160KB的代码和另外40KB的数据区，则总共需要8MB的内存空间来支持40个用户。如果160KB的代码是可重入的代码，则无论是在分页式系统还是在分段式系统中，该代码都可以被共享，即在内存中只保留一份文本编辑程序的副本，此时需要的内存空间仅为1760KB。分页式系统中的信息共享ed 1ed 2ed 40data 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进 程 22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180页表分页系统中共享editor的示意

46、图分段式系统中的信息共享editor进程1data 1进程2editordata 2段表段长 基址16080402401608040380editordata 1data 280240280380420分段系统中共享editor的示意图段的共享n段的共享是指两个以上的作业使用某个子程序或数据段，而在内存中只保留该信息的一个副本n实现：只需在每个进程的段表中，用相应的表项来指向共享段在内存的起始地址即可。n在共享中必须小心处理的一个问题是共享段的保护问题。共享段表n由于各进程对共享段的使用情况不同，每个进程为其分配的段号也不同。为了便于多进程共享主存中的公用子程序，可在内存中设置一个共享段段表。

47、共享段表n共享进程计数 记录有多少个进程需要共享该分段n存取控制字段 用来记录不同的进程对于同一共享段具有的不同的存取权限n段号 不同的进程可以用不同的段号去共享该段共享段的分配与回收n分配 在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、

48、存取控制等，再执行count =count+1操作，以表明有两个进程共享该段。共享段的分配与回收n回收 当共享此段的某进程不再需要该段时，应将该段释放， 包括撤销在该进程在共享段表中共享段所对应的表项，以及执行count =count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项， 表明此时已没有进程使用该段；否则(减1结果不为0)， 则只是取消调用者进程在共享段表中的有关记录。分段保护 n在分段存储管理方式中，用户各分段是信息的逻辑单位，因此容易对各段实现保护 。n越界检查p逻辑地址中的段号和段表寄存器中的段表长度比较，若段号段长，则发出地址越界

49、中断信号；p利用段表中的段长和逻辑地址中的段内地址相比较，如段内地址段长，则发出地址越界中断，系统便会对段进行保护。n存取控制检查（访问越权保护）p只读 p只执行 p读/写 分段保护n环保护机构 这是一种功能较完善的保护机制，该机制规定，低编号的环具有高优先权。Os核心处于0环，某些重要的实用程序和操作系统服务占据中间环（1环），而一般的应用程序在最外环（2环）。环系统中遵循以下规则：一个程序可以访问驻留在相同环或较低特权环中的数据一个程序可以调用驻留在相同环或较高特权环中的服务分段保护调用返回调用返回环0环1环2(a) 程序间的控制传输数据访问环0环1环2(b) 数据访问数据访问段页式存储管

50、理方式n分页存储管理有利于内存利用率的提高，分段存储管理有利于程序设计，把两种方式结合起来，形成了段页式存储管理方式。n基本思想：采用分段方法组织用户程序，采用分页方法分配和管理内存。n即，用户程序可以用模块化思想进行设计，一个用户程序由若干段组成；系统将内存划分成固定大小的物理块，并将程序的每一段分割成若干页后装入内存并执行。段页式存储管理方式 n基本原理04K8K12K15K16K子 程 序 段04K8K数 据 段04K8K10K12K(a)段 号 (S)段 内 页 号 (P)段 内 地 址 (W)(b)主 程 序 段作业地址空间和地址结构段页式系统中的地址映射段号 状态 页表大小页表始址

51、0111213041页号 状态 存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器利用段表和页表实现地址映射段页式系统中的地址变换过程 段表寄存器段表始址 段表长度段号 S 页号 P段超长段表0123页内地址页表0123b块号 b 块内地址页表始址页表长度段页式系统中的地址变换机构快表n第一次，访问段表，从中取得该段的页表首址n第二次，访问页表，从中取出逻辑地址指定的页面所在的物理块号，并将该物理块号和页内地址相加，形成指令或数据的物理地址。n第三次，访问内存，根据前面计算得到的物理地址，取出对应存储单元的指令或数据。n可以在地址变换机构中增设一个高速缓冲存储器，里面保

52、存 最近使用过的页号及其所属的段号。4.7 4.7 虚拟存储器虚拟存储器简单存储n简单存储：要求将一个进程所需要的程序和数据全部装入内存方可运行。n简单存储中出现的两种情况：p对于大进程，如果其要求的内存空间超过了内存最大容量，致使进程无法运行；p对于多道程序系统，由于每一个进程需要全部装入主存，使同时驻留内存的进程数量受到限制。虽然也能通过提高内存容量来解决，但代价高。解决方法n如果能将一部分价格较低的外存空间充当内存使用，从逻辑上扩充内存容量。进程运行之前，仅需要将一部分程序和数据（几个页面或段）装入内存，便可启动运行，其余部分暂时保留在磁盘上。那么，将获得更高的性价比。虚拟存储技术的理论

53、依据n程序的局部性原理：研究表明，程序在执行过程中呈现局部性原理。n这种局部性表现在两个方面：p时间局部性：一条指令被执行后，那么它可能很快会再次被执行； p空间局部性：若某一存储单元被访问，那么与该存储单元相邻的单元可能也会很快被访问。n因此，只要保证进程执行所需要的部分程序和数据驻留内存，一段时间内进程都能顺利执行。实现虚拟存储的一般过程n进程运行之前，仅需要将一部分页面或段装入内存，便可启动运行，其余部分暂时保留在磁盘上；n进程运行时，如果它所需要访问的页面（段）已经装入内存，则可以继续执行下去；n如果其所需要访问的页面（段）尚未装入内存，则发生缺页（段）中断，进程阻塞；n此时，系统将启

54、动请求调页（段）功能，将进程所需的页（段）装入内存。实现虚拟存储的一般过程n如果当前内存已满，无法装入新的页面（段） ，则还需要利用页（段）置换功能，将内存中暂时不用的页（段）交换到磁盘上，以腾出足够的内存空间。n再将进程所需的页（段）装入内存，唤醒阻塞的进程，使之重新参与调度执行。虚拟存储器n指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。n虚拟存储器的逻辑容量由内存和部分外存之和来确定，其运行速度接近于内存速度，而每位的成本接近于外存。引入虚拟存储技术的好处n大程序：可在较小的可用内存中执行较大的用户程序；n大的用户空间：提供给用户可用的虚拟内存空间远远大于物理

55、内存(real memory)；n并发：可在内存中容纳更多程序并发执行；n易于开发：与覆盖技术比较，不需要提供编程时的程序结构。虚拟存储器的特征n多次性：一个作业被分成多次调入内存运行， 多次性是虚拟存储器最重要的特征。n对换性：指允许在作业的运行过程中进行换进、换出。 换进和换出能有效地提高内存利用率n虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。注意： 虚拟性以多次性和对换性为基础。而多次性和对换性，又必须建立在离散分配的基础上 虚拟存储器的实现n虚拟存储器的实现建立在离散分配的存储管理方式基础上p在分页系统的基础上增加请求调页功能和页面置换功能，形成页式虚

56、拟存储系统 p在分段系统的基础上增加请求调段功能和分段置换功能，形成段式虚拟存储系统虚拟存储技术的技术支持n首先，必须有相应的硬件支持，用以实现分页或分段存储管理。n其次，操作系统必须提供相应的软件支持，管理页或段在内存和外存之间的移动。虚拟存储的好处n可以运行大程序，包括超过内存实际容量的大程序。n可以在有限的物理内存中运行更多的程序。4.8 4.8 请求分页式存储管理方式请求分页式存储管理方式基本原理n在作业或进程开始执行之前，只装入作业或进程的一部分，其他部分则在执行过程中动态装入。n调入方式：当需要执行某条指令而又发现它不在内存时或当执行某条指令需要访问其他的数据或指令时，该指令和数据

57、不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。请求分页中的硬件支持 页表页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地址 状态位P：指示该页是否在内存访问字段A：指示该页最近是否被访问过修改位：记录页面在调入内存后是否被修改过外存地址：记录该页在外存上的地址请求分页中的硬件支持缺页中断机构n请求分页式系统中，CPU硬件一定要提供对缺页中断的支持，根据页表项中的状态位判断是否产生缺页中断。n缺页中断是一个比较特殊的中断，主要体现在以下方面：p缺页中断在指令执行期间产生和处理中断信号。 通常，CPU都是在一条指令执行完后去检查是否有中断

58、请求到达。缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时产生的。p一条指令在执行期间，可能产生多次缺页中断。 因此，系统中的硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处继续执行。n发生缺页中断后，操作系统做什么？去外存调页。n调页过程？ 请求分页中的地址变换过程请求分页中的地址变换过程请求分页中的硬件支持地址变换机构 发生缺页中断时，操作系统要去外存调页。中断处理程序首先保存CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺页面调入内存，让后修改页表。如果

59、内存已满，则需要按照某种页面置换算法从内存中选出一页准备换出，如果此页未被修改过，可不必将该页写回磁盘，但如果此页已被修改，则必须将它写回磁盘，然后将所缺的页面调入内存，并修改页表中相应表项，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面调入过程对用户是透明的。虚拟存储系统的软件策略n最小物理块数的确定n物理块的分配策略n调页策略n置换策略n置换算法n清除策略最小物理块数的确定n最小物理块数：是指能保证进程正常运行所需的最少物理块数。n分配给每个活跃进程的物理块数越少，同时驻留内存的活跃进程数就越多，进程调度能调度就绪进程的

60、概率就越大。然而，这将导致进程发生缺页中断的概率较大；n为进程分配过多的物理块数，并不能显著地降低其缺页中断率。n最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。物理块的分配策略n固定分配：基于进程的类型或根据程序员的建议，为每个进程分配一定数量的物理块，在整个运行期间都不再改变n可变分配：根据进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块；随着程序的执行，可以动态的为进程增加或减少物理块。物理块的分配算法n平均分配算法:将系统中所有可供分配的物理块，等分给各个的进程。n按比例分配算法：根据进程的大小按比例分配物理块。如果系统各进程页面数总和为S,又假设m为