os_第4章存储器管理

1、第二章进程管理 操作系统南昌大学信息管理系南昌大学信息管理系NanChang UniversityDepartment of information manager操作系统操作系统Operating System 第二章进程管理 操作系统4.1 程序的装入和链接程序的装入和链接 一个用户源程序要变为一个可在内存中执行的程序，一般要经过： 目标模块 （1）编译（2）链接（3）装入 装入模块 装入内存 第二章进程管理 操作系统 4.1.1程序的装入:（1）绝对装入方式（2）可重定位装入方式（3）动态运行时装入方式第二章进程管理 操作系统一、绝对装入方式目标中代码中的地址就是绝对地址第二章进程管理

2、操作系统绝对装入方式只能将装入模块装入到内存中事先指定的位置。一般在程序中采用符号地址，在编译或汇编时，将符号地址转换为绝对地址。 绝对装入程序按照装入模块中的地址，装入时不用对程序和数据的地址进行修改。只能用于单道程序环境。 第二章进程管理 操作系统二、可重定位装入方式 可重定位装入方式，可将装入模块装入到内存中适当的位置，因此可用于多道程序环境。目标代码中的地址是相对地址当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）第二章进程管理 操作系统 11200 1200 LOAD 1200 400 JUMP 400 LOAD11200 104

3、00 JUMP10400 作业地址 空间相 内容空间 0 10000 第二章进程管理 操作系统原因: 当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换第二章进程管理 操作系统 重定位：重定位：在装入时对目标程序中的指令和数据地址的修改过程。 静态重定位静态重定位：地址变换只是在装入时一次完成，以后不再改变。 静态重定位不允许程序在运行中在内存中移动位置。第二章进程管理 操作系统静态重定位的主要缺点：静态重定位的主要缺点：1、只能连续存储，在重定位后不能移动，不利于内存空间的有

4、效利用。2、各用户进程很难共享内存中的同一程序的副本。第二章进程管理 操作系统三、动态运行时装入方式（动态重定位） 动态运行时的装入程序，在把装入模块装入内存后，并不马上把相对地址转换为绝对地址，而是在程序要真正执行时才进行地址转换。 第二章进程管理 操作系统动态重定位在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成） 硬件上需要一对寄存器的支持第二章进程管理 操作系统4.1.2 程序的链接程序的链接 一、静态链接一、静态链接 先进行链接所形成的一个完整的装入模块，先进行链接所形成的一个完整的

5、装入模块，又称为可执行文件。通常都不再拆开，要运行时又称为可执行文件。通常都不再拆开，要运行时可直接将它装入内存。这种事先进行链接，以后可直接将它装入内存。这种事先进行链接，以后不再拆开的链接方式，称为静态链接方式不再拆开的链接方式，称为静态链接方式 第二章进程管理 操作系统 C A LL B C A L LB ;Return; C A LLC ; Return; Return; 模 块 C 模 块 B 模 块 A 模 块 C 模 块 B 模 块 A 模 块 B JS R “L+ M ” Return; M -1 0 0 L-1 0 0 N -1 模 块 A JS R“L” L+ M M -1

6、 L L-1 0 模 块 C Return; 第二章进程管理 操作系统 编译后得到三个目标模块，要将这几个目标模块链接装配成一个装入模块，要解决两个问题。1、对相对地址进行修改 2、变换外部调用符号(B,C都属于外部调用号) 每个模块中所用的外部调用符号,都变换为相对地址。第二章进程管理 操作系统二、装入时动态链接 采用装入时动态链接方式把目标模块装入内存的同时，对相对地址进行修改。优点：1、便于软件版本的修改和更新。2、便于实现目标模块共享。第二章进程管理 操作系统三、运行时动态链接 该方式可将某些目标模块的链接，推迟到执行时进行。在执行时，如果发现有一个被调用模块不在内存中，就由操作系统找

7、到这个模块，把它装入内存，并链接到调用者模块上。 第二章进程管理 操作系统4.2 连续分配存储管理连续分配存储管理 连续分配是指为一个用户程序分配一个连续的内存空间。 连续分配有两种： 1、单一连续分配方式 2 2、分区式分配方式，又可分为： 固定分区式 动态分区 动态重定位分区第二章进程管理 操作系统4.2.1 单一连续分配单一连续分配 采用单一连续存储管理时，内存从概念上分为两个连续区： （1）系统区。（2）用户区。 第二章进程管理 操作系统 作 业 实 际 占 用 区 O S 空 闲 区 用 户 区 系 统 区 第二章进程管理 操作系统用户程序位于RAM中的操作系统00 xFFF用户程序

8、位于ROM中的操作系统ROM中的设备驱动程序用户程序位于RAM中的操作系统0基本输入输出系统BIOSMS-DOS00 xFFF第二章进程管理 操作系统第二章进程管理 操作系统 为了防止OS受到用户的破坏，存储保护可以通过硬件设置一个基址寄存器和界限寄存器来实现。 第二章进程管理 操作系统主要优点: 管理简单，只需要较少的软件和硬件支持，便于用户了解和使用。缺点：（1）若正在执行的程序等待某个事件，这时处理器就会于处于空闲状态，使处理器利用率不高。（2）由于可以进入系统运行的大多数用户作业尺寸都不可能正好与整个内存用户作业区一致，因此造成主存空间的浪费。 （3）计算机外围设备均被单个用户所占用。

9、因此利用率不高。程序和数据不可能被共享。 第二章进程管理 操作系统 为了增加CPU的使用率，要引进多道程序设计技术。 在多道程序环境下，必须使几个作业同时驻留内存。 如何组织存储器才能达到多道程序的运行呢？ 固定分区是最早使用的可运行多道程序的存储器管理方式。第二章进程管理 操作系统4.2.2 固定分区分配固定分区分配 固定分区式分配就是把内存空间分为若干个固定大小的区域。每一个作业占据一个连续的分区。 第二章进程管理 操作系统一、划分分区的方法 分区大小相等 分区大小不相等 分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。第二章进程管理 操作系统二、内存分配 系

10、统设有一张分区使用表，各表项包含有每个分区的起始地址、大小及状态（是否已分配）。 第二章进程管理 操作系统分区使用表分区号 大小（ K ）起址（ K ）状态11220已分配23232已分配36464已分配4128128已分配操作系统作业A作业B作业C作业D20K32K64K128K256K第二章进程管理 操作系统 采用固定分区时，把一个分区分配给某作业后，该作业就在此区域里运行、工作，直至完成。 有没有采用重定位？ 作业在装入时必须进行地址变换，因此固定分区方法实行的是“静态重定位”。 第二章进程管理 操作系统固定分区存储管理的地址转换和存储保护 B下限寄存器逻辑地址CPU绝对地址操作系统区用

11、户分区1用户分区2用户分区3B+L2上限寄存器size，从分区中划出u.size给请求者，其余的留在空闲分区链或空闲分区表中；将分配区的首址返回给调用者。 第二章进程管理 操作系统 2 2、回收内存 （1）回收区与插入点的前一个分区相邻接F1回收区F序号分区大小分区始址状态iF1.size addr1可用addr1第二章进程管理 操作系统 2 2、回收内存 （1）回收区与插入点的前一个分区相邻接F1序号分区大小分区始址状态iF.size+F1.sizeaddr1可用addr1第二章进程管理 操作系统（2）回收区与插入点的后一分区相邻接）回收区与插入点的后一分区相邻接 回收区F F2序号分区大小

12、分区始址状态iF2.sizeaddr2可用addraddr2第二章进程管理 操作系统（3）回收区同时与插入点的前、后两个分区邻）回收区同时与插入点的前、后两个分区邻接接F1回收区F序号分区大小分区始址状态iF1.sizeadd1可用i+1F2.sizeadd2可用F2add1add2第二章进程管理 操作系统（4）回收区既不与）回收区既不与F1邻接，也不与邻接，也不与F2邻接。邻接。回收区F序号分区大小分区始址状态addr第二章进程管理 操作系统分区回收算法：分区回收算法：(补充）补充）回收分区R,首址为baddrF上邻一个空白区f1?将f 放入自由主存队列从自由主存队列中摘下f1NYYN合并释

13、放分区f和空白分区f1成为一个大的空白区fF下邻一个空白区f2?从自由主存队列中摘下f2合并释放分区f和空白分区f2成为一个大的空白区f返回第二章进程管理 操作系统碎片问题： 经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片第二章进程管理 操作系统地址转换与存储保护 基址基址寄存器逻辑地址CPU绝对地址操作系统区空闲分区1用户作业1空闲分区2限长限长寄存器 + 第二章进程管理 操作系统 由上可知，在分页系统环境下，程序员编制的程序，以及由编译程序给出的目标程序，其地址空间是连续的，程序地址空间的分页是由系统自

14、动完成的，而不是程序员或编译程序的事。 第二章进程管理 操作系统页表全部放在内存页表全部放在内存 第一次访问内存第一次访问内存 根据页号访问页表根据页号访问页表 读出块号形成绝对地址读出块号形成绝对地址 根据绝对地址取数据根据绝对地址取数据 第二次访问内存第二次访问内存 取一个数据至少取一个数据至少要访问二次内存要访问二次内存 第二章进程管理 操作系统2、具有快表的地址变换机构、具有快表的地址变换机构 为了提高查表速度，在地址变换机为了提高查表速度，在地址变换机构中加入一个高速小容量的联想存储器，构中加入一个高速小容量的联想存储器，该存储器具有并行查寻能力，构成快表。该存储器具有并行查寻能力，

15、构成快表。第二章进程管理 操作系统越界中断 页内地址d 页表长度 页表始址 页号P 页号 快表快表 块号 页号 块号 物理地址物理地址 输入寄存器 d b b + b 联想存储器存放正在运行作业的当前最常用的页号和它的相应块号。 当CPU给出有效地址(p,d)，地址变换机构自动把页号P送入输入寄存器，然后立即和快表中的所有页号比较。第二章进程管理 操作系统 分页存储管理中的优缺点分页存储管理中的优缺点 优点：优点： 分页存储分配有效地解决了存储器的分页存储分配有效地解决了存储器的零头问题，能同时为更多的作业提供存储零头问题，能同时为更多的作业提供存储空间，也就能在更高的程度上进行多道程空间，也

16、就能在更高的程度上进行多道程序设计，提高了存储器和处理机的利用率。序设计，提高了存储器和处理机的利用率。 第二章进程管理 操作系统缺点：缺点： （1）采用了动态地址变换机构，降低了）采用了动态地址变换机构，降低了CPU的速度。的速度。 （2）必须用一部分存储空间来存放各种）必须用一部分存储空间来存放各种表格，要花费一定的处理机时间来建立和管表格，要花费一定的处理机时间来建立和管理这些表。理这些表。第二章进程管理 操作系统 （3）解决了分区间的零头，又出现了块内的零头。 （4）要求运行的作业，必须全部装入内存。 （5）和分区分配方案一样，作业的地址空间受到主存实际容量的限制。第二章进程管理 操作

17、系统 一个具有一个具有32位的逻辑地址空间的分页系统：位的逻辑地址空间的分页系统： 页面大小为页面大小为4KB=212B 每个进程的页表项可达每个进程的页表项可达220个个连续存放连续存放第二章进程管理 操作系统解决方法：解决方法：（1）采用离散分配方式来解决难以找到一块连）采用离散分配方式来解决难以找到一块连续的大内存空间的问题。续的大内存空间的问题。（2）只将当前需要的部分页表项调入内存，其）只将当前需要的部分页表项调入内存，其余的页表仍驻留在磁盘上，需要时再调入。余的页表仍驻留在磁盘上，需要时再调入。第二章进程管理 操作系统4.3.3 两级和多级页表两级和多级页表 1、两级页表、两级页表

18、 将页表分页，并离散地将各页面分别存放在不将页表分页，并离散地将各页面分别存放在不同的物理块，为离散分配的页面再建立一张同的物理块，为离散分配的页面再建立一张页表页表。外层页表外层页表外层页表的每个页表项中记外层页表的每个页表项中记录了页表页面的物理块号。录了页表页面的物理块号。第二章进程管理 操作系统 以以32位的逻辑地址空间的系统为例，页位的逻辑地址空间的系统为例，页面大小为面大小为4 KB：外层页号外层页号P1外层页内地址外层页内地址P2页内地址页内地址d3122 2112 11010位，可包含1024个页表分页10位，最多允许1024个页面12位第二章进程管理 操作系统10111078

19、17421461141151468 01141468外部页表第0页页表第1页页表第n页页表0n某页表分页的始址进程的某页在内存中的物理块号第二章进程管理 操作系统P1P2d外部页号外部页号外部页内地址外部页内地址页内地址页内地址逻辑地址逻辑地址外部页表寄存器外部页表寄存器+bd外部页表外部页表页表页表物理地址页表分页的始址采用离散分配的方式并没有减少页表所占的内存空间第二章进程管理 操作系统2.多级页表以64位的逻辑地址空间的系统为例，页面大小为4 KB,余下42位用于外层页号,则在外层页表中可能有4096G个页表项,要占用16384GB的连续内存空间.在64位OS中,把直接寻址的存储器空间减

20、少到45位长度,这样可利用三级页表结构来实现分页存储管理.第二章进程管理 操作系统分页式存储空间的分配和去配 分页式存储管理把主存的可分配区按页面大小可分成若干块，主存分配以块为单位。可用一张主存分配表来记录已分配的块和尚未分配的块以及当前有多少空闲块。 例如主存的可分配区有256块 用字长16位的16个字来构成主存分配表，表格的每一位与一个物理块对应，用0/1表示对应块为空闲/已占用，用另一字节记录当前空闲块数 第二章进程管理 操作系统位示图 0/10/10/10/10/10/10/10/1 0/10/10/10/10/10/10/10/10/10/1 0/10/10/10/10/10/10

21、/10/10/10/1 0/10/10/10/10/10/10/10/10/10/1 0/10/10/10/10/10/10/10/10/10/1 0/10/1 空闲块数空闲块数第二章进程管理 操作系统页的共享和保护 实现数据共享时，可允许不同的作业对共享的数据页用不同的页号，只要让各自页表中的有关表目指向共享的数据信息块就行了 。对共享程序必须规定一个统一的页号 。实现信息共享必须解决共享信息的保护问题。通常的办法是在页表中增加一些标志位，用来指出该页的信息可读/写；只读；只可执行；不可访问等，指令执行时进行核对。例如，要想向只块写入信息则指令停止，产生中断。第二章进程管理 操作系统4.4

22、基本基本分段存储管理方式分段存储管理方式 前面介绍的各种存储管理方案，为用户提供的是一个线性地址空间，这对于模块化程序和变化的数据结构的处理，以及不同作业之间对某些公用子程序或数据块的共享等问题的解决，都存在着较大的困难；另外，程序人员在编程和使用上也有多方面的要求，由此又引入了分段存储管理方式。 第二章进程管理 操作系统1、方便编程： 编程人员希望把作业按照逻辑关系，分成若干段，每个段有自己的名字和长度。 2、分段共享 ： 一般是以信息的逻辑单位为基础来实现程序和数据的共享的。 3、分段保护： 以信息的逻辑单位为基础对内存中信息采取保护措施 。 4、动态链接 5、动态增长4.4.1 分段存储

23、管理方式的引入第二章进程管理 操作系统4.4.2 分段系统的基本原理分段系统的基本原理 1 1、分段、分段 一个段定义为一组逻辑信息分段Main分段X分段A第二章进程管理 操作系统作业的地址空间是二维的。作业的地址空间是二维的。逻辑地址是由段名和段内地址构成。逻辑地址是由段名和段内地址构成。 段号段内地址 分段管理就是管理由若干分段组成的作业，且按分段来进行存储分配，即为每个段分配一个连续的分区，而各个段可以离散地放入内存中不同的分区中。 第二章进程管理 操作系统2、段表段号 段长 基址 逻辑段到物理内存区的映射系统调度到某个作业时，就为它建立一张段表第二章进程管理 操作系统B0SA0NY0L

24、X0PM0K逻辑段号逻辑段号作业的地址空间作业的地址空间10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000长度长度 段地址段地址操作系统操作系统第二章进程管理 操作系统3、地址变换机构、地址变换机构动态重定位技术动态重定位技术实现把二维地址结构变换成一个线性的地址结构实现把二维地址结构变换成一个线性的地址结构第二章进程管理 操作系统段表始址段表始址 段表长度段表长度1100段号S位移量W越界中断越界中断+01K6K1500K4K2300K8K3200K9200K4段号段长基址+4196123454196段表寄存器由硬件自动完成

25、由硬件自动完成第二章进程管理 操作系统 （1）页是信息的物理单位，分页活动用户是看不见的，仅仅用于对内存的管理，引进分页是为了消除内存的外零头，提高内存的利用率。 段是信息的逻辑单位，分段活动用户是可见的，分段的目的是为了更好地满足用户的需要。 分页和分段的主要区别分页和分段的主要区别 第二章进程管理 操作系统 （2）页的大小是固定的，并且由系统确定，由硬件实现把逻辑地址划分为页号和页内地址，一个系统只能有一种大小的页面。 段的长度却不固定，可以在用户编程时确定，也可以在编译程序对源程序进行编译时，根据信息的性质来划分。 第二章进程管理 操作系统 （3）分页的地址空间是一维的，程序员只要用一个

26、记忆符即可表示一个地址。 分段的作业地址空间是二维的，程序员在标识一个地址时，既要给出段名，又要给出段内地址。 LOAD 1，A 第二章进程管理 操作系统4.4.3 信息信息共享共享 可重入代码，又称为可重入代码，又称为“纯代码纯代码”，是一种允许多个进程同时访问的代码。是一种允许多个进程同时访问的代码。 可重入代码是一种不允许任何进程可重入代码是一种不允许任何进程对其进行修改的代码。对其进行修改的代码。 第二章进程管理 操作系统 例：有一个可同时例：有一个可同时接纳接纳40个用个用 户的多用户户的多用户系统，他们都执行一个系统，他们都执行一个文本文本 编辑程序（编辑程序（Text Edito

27、r），文本），文本 编辑程编辑程序含有序含有160KB的代码和的代码和40K的数据区。的数据区。 40个用户同时执行。个用户同时执行。 需要需要(160+40)40=8M的内存空间的内存空间 。第二章进程管理 操作系统 如果如果160K代码是可重代码是可重入的，那么代码就能被共入的，那么代码就能被共享。内存只要保留一份文享。内存只要保留一份文本编辑程序的副本，这时本编辑程序的副本，这时需要的内存空间就是：需要的内存空间就是： (160+4040)=1760KB。 第二章进程管理 操作系统 在分页系统中，假定页面大小为在分页系统中，假定页面大小为4KB，160KB的的代码占用代码占用160/4=

28、40个页面，数据区占个页面，数据区占40/4=10个页面。个页面。 为实现代码的共享，每个进程都要在页表中建为实现代码的共享，每个进程都要在页表中建立立40个页表项，物理块号都是从个页表项，物理块号都是从21#60#，还要为，还要为数据区建立数据区建立10个页表项，物理块号分别的个页表项，物理块号分别的61# 70#，71# 80#，81# 90#， 要把共享的程序安排到所有共享它的作业地址空要把共享的程序安排到所有共享它的作业地址空间中相同页号的页中。间中相同页号的页中。 第二章进程管理 操作系统ed1ed2ed40data1data102122607180ed1ed2ed40data1da

29、ta10进程进程1进程进程22122606170页表页表页表页表ed1ed2ed40data1data10 data1data10主存主存021226061707180分分 页页 共共 享享第二章进程管理 操作系统240280380420editordata1进程进程1进程进程2段表段表editordata1 data2 主存主存080 editordata2段长段长基址基址1608040240段长段长基址基址1608040380段表段表分 段 共 享第二章进程管理 操作系统4.4.4 段页式存储管理段页式存储管理 为了获得分段在逻辑上的优点和分页在管理存储空间方面的优点，兼用分段和分页方法，

30、即采用段页存储管理。 第二章进程管理 操作系统1 1、基本原理、基本原理 段页式系统的基本原理是分段和分页段页式系统的基本原理是分段和分页原理的组合。原理的组合。 在这个系统中，先把用户程序分为若在这个系统中，先把用户程序分为若干段，每个分段又被分成若干个固定大小干段，每个分段又被分成若干个固定大小的页，每个段有一个段名。的页，每个段有一个段名。第二章进程管理 操作系统 假定页面大小为假定页面大小为4K。一作业分成三段。一作业分成三段。 第一段第一段7k，占有，占有2页；页； 第二段第二段4k，占，占1页；页； 第三段第三段3k，占，占1页。页。 0104k8k004k04k0页内零头第二章进

31、程管理 操作系统 段号(s) 段内页号页内地址 在段页式系统中，地址空间由段、段内的页和页内的相对地址构成。 段页式存储管理中，程序的分段可以由程序员或编译程序根据信息的逻辑结构来划分。而分页和程序员无关，是由系统自动进行的。 第二章进程管理 操作系统 段页式存储管理中，地址结构是几维的？段页式存储管理中，地址结构是几维的？二维的二维的第二章进程管理 操作系统2 2、地址变换过程、地址变换过程 为了实现动态地址变换，段页式系统必须为每个作业建立一张段表，并为每个分段建立一张页表。 第二章进程管理 操作系统第二章进程管理 操作系统 进行地址变换时： 段号S与段表长度TL比较； 利用段表始址和段号

32、来求出该段对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的的物理块号b，再用块号b和页内地址构成物理地址。 第二章进程管理 操作系统 页 表 始 址 页 表 长 度 物 理 地 址 块 内 地 址 块 号b 页 表 段 表 页 内 地 址W 页 号P 段 号S 段 表 长 度 段 表 始 址 b 2 1 0 + 3 2 1 0 + 3 第二章进程管理 操作系统 段表和页表全放在主存的话，访问内存中的一条指令或数据，至少需要访问主存三次。 第一次是访问段表，以段号为索引找到页表所在位置。 第二次是访问页表，以页号为索引找

33、到该页所在的存储块号。 第三次是以形成的物理地址访问内存单元。第二章进程管理 操作系统 采用联想存储器来加速查表过程。 在快表中保存着当前最常用的一些段的段号、页号及相应的主存块号。 每次访问时，同时利用段号和页号去检索快表，若找到匹配的表项，便可从中得到相应页的物理块号，与页内地址一起形成物理地址；若找不到匹配的表项，仍然要访问三次内存。W P S 主存块号(S,P)第二章进程管理 操作系统 W P S 主存块号(S,P)第二章进程管理 操作系统4.5虚拟存储器的基本概念虚拟存储器的基本概念4.5.1 虚拟存储器的引入虚拟存储器的引入第二章进程管理 操作系统 前面讨论的各种存储管理方法虽前面

34、讨论的各种存储管理方法虽各有特长，但有一些共同的特点各有特长，但有一些共同的特点: : 首先是首先是“一次性分配一次性分配”。 其次是其次是“驻留性驻留性”。 作业全部信作业全部信息，必须一息，必须一次性装入内次性装入内存存 作业信息一作业信息一旦装入内存旦装入内存便一直驻留便一直驻留到作业运行到作业运行结束结束 一方面使大作业的运行受到限制，另一方面又影响了多道程序的实现。 第二章进程管理 操作系统2、局部性原理、局部性原理 程序的局部性规律，程序往往会不程序的局部性规律，程序往往会不均匀地高度局部化地访问内存。均匀地高度局部化地访问内存。 第二章进程管理 操作系统 （1）程序在执行时，在大

35、多数情况下仍是顺序执行的。 这种特性使得程序的执行在一段时间内被限制在作业的某一局部范围。 P.Denning还有以下一些论点： （2）过程调用将会使程序的执行轨迹由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。 在一段时间内，程序将会被局限于这些过程的范围内运行。第二章进程管理 操作系统 （3）程序中存在许多循环结构，它们可以）程序中存在许多循环结构，它们可以多次重复执行。多次重复执行。 for i:=1 to n ai:=ai+1;（4）程序中还包括许多对数据结构的处理，）程序中还包括许多对数据结构的处理，它们往往都局限于很小的范围内。它们往往都局限于很小的范

36、围内。第二章进程管理 操作系统（1）时间局限性时间局限性 时间局限性时间局限性是指最近被访问的存储位置，很可能不久的将来还要被访问。 支持这种现象的是： (a) 循环； (b) 子程序； (c) 栈； (d) 用于计数和总计的变量。 第二章进程管理 操作系统（2）空间局限性空间局限性 空间局限性空间局限性是指存储访问有集成一组的倾向，以致一旦某个位置被访问到，很有可能它附近的位置也要被访问。 支持这种现象的是： a、数组遍历； b、代码的顺序执行； c、程序员倾向于将相关的变量定义相互靠近存放。 第二章进程管理 操作系统 基于局部性原理，作业没有必要全部装入内存。 如果计算机系统把辅助存储器当

37、做主存储器的扩充，当作业运行时，不是将其全部信息装入内存，而是将必须部分先装入内存，其它部分仍存于辅存中。作业运行过程中随时把需要但又不在内存的信息装入内存，把暂时不用的信息淘汰出去，以确保作业的正确运行。 好象这个计算机系统向他们提供了一个容量很大的主存第二章进程管理 操作系统3、虚拟存储器的定义虚拟存储器的定义 所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 虚拟存储器的大小受计算机系统地址结构和可用外存数量的限制，与实际内存单元的数量无关。第二章进程管理 操作系统4.5.2 虚拟存储器的实现方式虚拟存储器的实现方式 离散分配存储管理方式是实现

38、虚拟存储器的基础。 第二章进程管理 操作系统1 1、分页请求系统、分页请求系统 是在分页系统的基础上，增加了请求是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚调页功能、页面置换功能所形成的页式虚拟存储系统。拟存储系统。 第二章进程管理 操作系统硬件支持：硬件支持： (1) (1) 请求分页的页表机制。请求分页的页表机制。 (2) (2) 缺页中断机构。缺页中断机构。 (3) (3) 地址变换机构。地址变换机构。 软件支持：软件支持： (1) (1) 实现请求调页的软件。实现请求调页的软件。 (2) (2) 实现页面置换的软件。实现页面置换的软件。 第二章进程管理 操作系统

39、2 2、请求分段系统、请求分段系统 这是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。 第二章进程管理 操作系统为了实现请求分段，系统要提供硬件支持： (1) 请求分段的段表机制。 (2) 缺段中断机构。 (3) 地址变换机构。 同样地，请求调段和段的置换功能的实现也需要得到OS的支持。 第二章进程管理 操作系统4.5.3 虚拟存储器的特征虚拟存储器的特征 离散性是虚拟存储器最基本的特性，虚拟性是它的最重要特征，另外虚拟存储器还具有多次性和对换性。 第二章进程管理 操作系统1、离散性 离散性是指在内存分配时采用离散分配方式。2、多次性 作业分多次装入内存 3、对

40、换性运行时换进换出 4、虚拟性逻辑上扩充内存容量 最基本特性第二章进程管理 操作系统4.6 请求分页存储管理方式请求分页存储管理方式 请求分页存储管理方式是建立在纯分页基础上的，换进换出的基本单位是固定长的页面，因而实现起来比较容易。 第二章进程管理 操作系统4.6.1 请求分页中的硬件支持请求分页中的硬件支持 一、页表机制一、页表机制 页表的作用是实现从用户地址空间中的逻辑地址到内存空间的物理地址的转换。第二章进程管理 操作系统 请求页式管理中对地址空间分页，内存分请求页式管理中对地址空间分页，内存分块与基本分页管理一样，但对虚页的管理是不块与基本分页管理一样，但对虚页的管理是不同的。同的。

41、 要访问的页面不在内存中，如何发现和处要访问的页面不在内存中，如何发现和处理这种情况？理这种情况？这是请求分页存储这是请求分页存储管理要解决的两个管理要解决的两个基本问题基本问题第二章进程管理 操作系统 在纯分页系统中，页表的内容为：在纯分页系统中，页表的内容为：页号物理块号针对第一个问题，扩充页表：针对第一个问题，扩充页表：页号物理块号状态位P外存地址第二章进程管理 操作系统针对第二个问题： 由地址变换机构产生一个缺页中断信号，OS进行中断处理后，根据该页的外存地址把它从外存调入内存。 引进修改位和访问字段。第二章进程管理 操作系统请求分页系统中，页表项如下：请求分页系统中，页表项如下： 页

42、号页号物理块号物理块号状态位状态位P访问字段访问字段A 修改位修改位M外存地址外存地址(1)(1)状态位（存在位）状态位（存在位）P。 (2)(2)访问字段访问字段A。(3)(3)修改位修改位M。(4)(4)外存地址。外存地址。第二章进程管理 操作系统 在虚拟存储系统中，当一个作业被编译或在虚拟存储系统中，当一个作业被编译或经链接装配后得到的地址空间，通常存在磁盘经链接装配后得到的地址空间，通常存在磁盘上。上。页号物理块号 保护信息外页外页面表面表 当一个作业被调度到而装入内存时，系统当一个作业被调度到而装入内存时，系统为它在内存建立一张页表。为它在内存建立一张页表。第二章进程管理 操作系统2

43、 2、缺页中断机构、缺页中断机构 在请求分页系统中，当要访问的页面不在内存时，硬件发一个缺页中断，转交OS处理。第二章进程管理 操作系统(1)在指令执行期间产生和处理中断信号。 (2)一条指令在执行期间，可能产生多次缺页中断。 它跟一般的中断有着明显的区别：它跟一般的中断有着明显的区别：第二章进程管理 操作系统3 3、地址变换机构、地址变换机构 请求分页系统中的地址变换机构是以分页系统请求分页系统中的地址变换机构是以分页系统的地址变换机构为基础的，还增加了产生缺页中断、的地址变换机构为基础的，还增加了产生缺页中断、处理缺页中断，置换等功能。处理缺页中断，置换等功能。 第二章进程管理 操作系统

44、在进行地址变换时，首先去检索快表；在进行地址变换时，首先去检索快表； 如果快表中没有这一页的页表项，再到内存中找如果快表中没有这一页的页表项，再到内存中找页表，根据状态位页表，根据状态位P来判断该页是否在内存中。来判断该页是否在内存中。 （1）在内存，将该页的页表写入快表；快表满时，）在内存，将该页的页表写入快表；快表满时，调出某页表项，再写入该页的页表项；调出某页表项，再写入该页的页表项； （2）不在内存，产生缺页中断，请求）不在内存，产生缺页中断，请求OS从外存从外存中把该页调入内存。中把该页调入内存。 第二章进程管理 操作系统 这里仅仅给出一个很粗略的框图，具体的过程是很复杂的。因为作业

45、的副本是以文件形式存于外存上，因而要求页面传输时，必然要涉及到文件系统，此外，还得调用输入输出进程。在多道程序环境下，一个作业在等待传输页时，它处于被阻塞的状态。此时，由系统调度另一作业运行。当页面传输完成后，才把原先被阻塞的那个作业重新置成就绪状态，但要等到再次调度到它时，才能恢复到原先中断的地方继续运行下去。 第二章进程管理 操作系统4.6.2 内存内存分配策略和分配算法分配策略和分配算法 在为进程分配物理块时，又要解决三个问题：1、保证进程正常运行而需要的最少物理块数；2、进行分配时，物理块数目是固定的还是可变的；3、是采取平均分配算法还是根据进程的大小按比例分配物理块。第二章进程管理

46、操作系统1、最小物理块数的确定 最小的物理块数，是指保证进程正常运行所需的最少物理块数。 最少物理块数与指令的格式、功能和寻址方式有关，也就是说与计算机的硬件结构有关。 第二章进程管理 操作系统2 2、页面分配页面分配和和置换策略置换策略 1)、固定分配局部置换（Fixed Allocation, Local Replacement） 采取固定和采取固定和可变分配策可变分配策略略 采取全局置采取全局置换和局部置换和局部置换策略换策略 第二章进程管理 操作系统2)、可变分配全局置换空闲物理块队列3)、可变分配局部置换要求保持要求保持适当的缺适当的缺页率页率 第二章进程管理 操作系统3 3、物理块

47、分配算法、物理块分配算法 在固定分配策略中，系统在为各个进程分配物理块时，可采取： 1)、平均分配算法 第二章进程管理 操作系统 系统中多进程页面数的总和为：niSiS1 每个进程所能分到的物理块数bi=Si/S m，m为可用的物理总数。 3)、考虑优先权的分配算法 2)、按比例分配算法 ，Si为某个进程的页面数。 第二章进程管理 操作系统4.6.3 调页策略调页策略1 1、何时调入页面、何时调入页面1、预调页策略2、请求调页策略用于首次调用于首次调入入第二章进程管理 操作系统2 2、从何处调入页面、从何处调入页面 (1)(1)系统拥有足够的对换区空间。系统拥有足够的对换区空间。 当缺页时，全

48、部从对换区把所需的页当缺页时，全部从对换区把所需的页面调入内存，使调页速度提高面调入内存，使调页速度提高。 第二章进程管理 操作系统刚开始时，都放在文件区 文件区对换区不改改外存可能被修改 不会被修改内存(2)(2)系统缺少足够的对换区空间。系统缺少足够的对换区空间。 第二章进程管理 操作系统文件区对换区第一次内存外存(3) UNIX方式方式 与进程有关的文件都放在文件区。没有运行过的页面，从文件区调入内存；已经运行过又被换出的页面，放在对换区，下次调入时，从对换区调入。第二章进程管理 操作系统外存物理块号内存空：调入内存不空：换出一页修改位为1，重新写入外存修改位为0，不必写入外存将缺页调入

49、内存修改页表，写入快表物理地址访问数据3、页面调入过程、页面调入过程 第二章进程管理 操作系统4.7 页面置换算法页面置换算法把选择换出页面的算法称为页面置换算法。第二章进程管理 操作系统 刚被换出的页很快又被访问，需要重新调入，为此又需再选出一页调出；而刚被换出的页，很快又要被访问，又需把它调入，如此频繁地更换页面，以致一个进程在运行中，把大部分时间花费在完成页面的置换工作上，我们称该进程发生了“抖动”。 抖动抖动第二章进程管理 操作系统4.7.1最佳置换算法和先进先出算法最佳置换算法和先进先出算法1 1、最佳置换算法、最佳置换算法 最佳置换算法是由Relady在1966年提出的，这种算法选

50、择的被淘汰页面，将是永不使用的，或在最长时间内不再被访问的页面。第二章进程管理 操作系统 假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串。 1 2 3 4 5 6 7 8 9 1011121314151617181920217 0 1 2 0 3 0 4 2 3 0 3122 0 1 1 7101702070170304238 91000214500231112130102141516171807011920210673020 采用最佳置换算法，只发生了6次页面置换，发生了9次缺页中断。缺页率=9/21第二章进程管理 操作系统2、先进先出页面置换算法（、先进先出页面置换算法（FI

51、FO） 这是最早出现的置换算法，这种算法总是淘汰最先进入内存的页面，选择在内存中驻留时间最久的页面予以淘汰。第二章进程管理 操作系统 我们来看看采用FIFO算法进行页面置换时的情况。 0 717002170031020 4 51230 60230 74300 84200 94230 100230 11-130130 140120 15-187120 197020 207010 21一共发生了12次页面置换，比最佳置换算法多了1倍。缺页率15/21=3/4，15次页面中断。 1 2 3 4 5 6 7 8 9 1011121314151617181920217 0 1 2 0 3 0 4 2 3

52、 0 3122 0 1 1 710第二章进程管理 操作系统 FIFO是根据各个页面调入内存的时间来选择被淘汰页面，但页面调入的先后并不能反映页面的使用情况。 FIFO算法只是在按线性顺序访问地址空间才是理想的。 未考虑到程序的动态特性。 可能引起异常。第二章进程管理 操作系统4.7.2 最近最久未使用最近最久未使用LRU置换算法置换算法 1、LRU（Least Recently Used）算法的描述）算法的描述 这种算法依据的原理是程序执行时所具有的局这种算法依据的原理是程序执行时所具有的局部性，即那些刚被使用过的页面可能马上再次被使部性，即那些刚被使用过的页面可能马上再次被使用，而那些最近未

53、被使用的页一般来说不会马上被用，而那些最近未被使用的页一般来说不会马上被使用到。使用到。选择淘汰的页面是最近最久未使用第二章进程管理 操作系统 我们用“最近的过去”来直接推断“最近的将来”。 7070717012 0 3402302 132 0 1 1 7 0 1120023043024 243032213012017发生了9次页面置换。 标明访问时标明访问时间间 第二章进程管理 操作系统 LRU算法是与每个页面最后使用的算法是与每个页面最后使用的时间有关的。当要淘汰一个页面时，时间有关的。当要淘汰一个页面时， LRU算法选择过去一段时间里最久未被算法选择过去一段时间里最久未被使用的页面。使用

54、的页面。第二章进程管理 操作系统2、LRU算法的硬件支持算法的硬件支持为了实现LRU算法必须解决： （1）一个进程在内存中的各个页面各有多久时间未被进程访问； （2）如何快速地知道哪一页是最近最久未使用的页面。 第二章进程管理 操作系统1 1、寄存器、寄存器 为每个在内存中的页面配置一个移位寄存器，为每个在内存中的页面配置一个移位寄存器，表示为：表示为： R=Rn-1Rn-2Rn-3R1R2R0 当进程访问某物理块时，要将相应的寄存器的当进程访问某物理块时，要将相应的寄存器的Rn-1位置为位置为1。 定时信号将每隔一定时间将寄存器右移一次，定时信号将每隔一定时间将寄存器右移一次，把把n位寄存器

55、的数看作是一个无符号的整数，最近位寄存器的数看作是一个无符号的整数，最近最久未使用的页面就对应着具有最小数值的寄存器最久未使用的页面就对应着具有最小数值的寄存器 。用于记录某进程在内存中各页的使用情况。用于记录某进程在内存中各页的使用情况。第二章进程管理 操作系统2、栈 LRU置换算法可用堆栈的方法来实现。 栈中存放当前内存中的页面号，每当访问一页时就调整一次堆栈，总是使最近访问的那页的页面号保持在栈顶，然后根据当前被访问时间的近远，依次排列，栈底总是最近最久未使用的那页的页面号。 淘汰淘汰第二章进程管理 操作系统1121231234214312431234215621237651241256

56、125612561265126313276327缺页中断假设，作业固定占用4块主存 例如，某作业按下列页号访问：例如，某作业按下列页号访问： 第二章进程管理 操作系统4.7.3 CLock置换算法置换算法 CLock算法就是用得较多的一种LRU近似算法。 第二章进程管理 操作系统1 1、简单的、简单的CLock置换算法置换算法 这种算法的实质是：当需要置换一页时，选择在最近一段时间内最久未用的页予以淘汰，因此称为最近未用的算法NRU（Not Recently Used）。第二章进程管理 操作系统 这种近似算法，要求为每一页设置一位访问位，再将内存中的所有页面都通过指针按FIFO链成一个循环队列

57、。 当某页被访问时，访问位由硬件自动置“1”。我们可以根据访问位的状态来判断各个页面最近使用的情况。如果是“0”，就选择该页换出；若为1，则重新将它置为0，再按照FIFO算法检查下一个页面。 第二章进程管理 操作系统块号页号访问位指针0124034215650711替换替换指针指针总是指向最近总是指向最近被替换的页所被替换的页所在的存储块，在的存储块，缺页时从其后缺页时从其后一块开始。一块开始。第二章进程管理 操作系统2、改进型CLock置换算法 1类 （A=0，M=0），最近既未被访问，又未被修改，是最佳淘汰页。 2类 （A=0，M=1），最近未被访问，但已被修改，不是很好的淘汰页。 3类

58、（A=1，M=0），最近已被访问，但未被修改，可能再被访问。 既要考虑到页既要考虑到页面的使用情况，面的使用情况，还要考虑置换还要考虑置换代价代价 4类 （A=1，M=1），最近已被访问且被修改，可能再被访问。 第二章进程管理 操作系统改进型改进型CLock算法，执行过程可分为以下三步：算法，执行过程可分为以下三步： （1）从指针的当前位置开始，扫描按先进先出循环队列，寻找A=0且M=0的第一类页面，将符合条件的第一个页面作为淘汰页，在第一次扫描期间A不改变。 第二章进程管理 操作系统（2）第一步失败，开始第二轮扫描，寻找A=0且M=1的第二类页面，将符合条件的第一个页面作为淘汰页。将所有经过

59、的页面的访问位置0。（3）第二步也失败，把指针返回到开始的位置，把所有的访问位A置为0，然后重复第一步，如还是失败，重复第二步，就一定能找到被淘汰的页。第二章进程管理 操作系统4.7.4 其它置换算法其它置换算法1、最少使用（Least Frequently Used）置换算法（LFU ）既可实现LRU，也可实现LFU 为内存中的每个页面为内存中的每个页面设置一个移位寄存器，用设置一个移位寄存器，用来记录页面被访问的频率，来记录页面被访问的频率，淘汰页是最少使用或是访淘汰页是最少使用或是访问次数最少的页面。问次数最少的页面。 ri最小的页就是最近一段时间使用最少的页面。最小的页就是最近一段时间

60、使用最少的页面。第二章进程管理 操作系统2、页面缓冲算法（Page Buffering Algorithm） PBA 淘汰页面未修改修改过空闲页面链表末尾已修改页面的链表中末尾采用可变分配和局部置换方式，采用可变分配和局部置换方式，采用采用FIFO置换算法置换算法 第二章进程管理 操作系统请求分页系统的性能分析请求分页系统的性能分析 请求分页系统中，程序在运行中产生的缺页情况，会影响程序的运行速度及系统性能。缺页率的高低又将直接与每个进程所占用的物理块数目有关。因此，应该把缺页率保持在一个合理的水平上。第二章进程管理 操作系统 请求分页管理是实现单段式虚拟存储器的一种具体方案，它允许作业的部分