操作系统四版课件3

1、3.13.23.3本章讲述内容：本章讲述内容：3.43.53.6基本概念基本概念内存储器内存储器（简称内存、主存、物理存储器）（简称内存、主存、物理存储器） 处理机能直接访问的存储器。用来存放系处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。储方式是以新换旧，断电信息丢失。外存储器外存储器（简称外存、辅助存储器）（简称外存、辅助存储器） 处理机不能直接访问的存储器。用来存放处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多用户的各种信息，存取速度相对内存而言

2、要慢得多，但它可用来长期保存用户信息。在文件系统中介，但它可用来长期保存用户信息。在文件系统中介绍。绍。存储器分类存储器分类指导思想：利用辅存（如磁盘、磁带等）提指导思想：利用辅存（如磁盘、磁带等）提供的大容量存储空间，存放准备运行的程序供的大容量存储空间，存放准备运行的程序和数据，当需要时或主存空间允许时，随时和数据，当需要时或主存空间允许时，随时将它们读入主存储器。将它们读入主存储器。信息的二级存储信息的二级存储 目前，计算机采用的都是以存储器为中心的体系结构。存储器负责存放整个系统的程序与数据，是重要的系统资源。.磁带磁盘主存储器高速缓存寄存器快慢存取速度小大容量昂贵便宜价格. 在考虑计

3、算机存储器的设计时，必须顾及“价格”、“容量”、“访问时间”这三个重要特性。各种实现技术间往往有以下的关系：存取时间越快，每“位”的价格就越高；容量越大，每“位”的价格就越低；容量越大，存取速度就越慢。. 只能在“价格”、“容量”、“访问时间”三者间寻求折中，采用存储器的层次结构 。这时，从上往下就有：每“位”的价格递减；存储容量递增；存取时间递增。 . 这种层次结构中，容量较大、价格便宜的慢速存储器（如磁盘），可作为容量较小、价格较贵的快速存储器的后备。这正是存储管理中虚拟存储技术的实现基础。 这种层次结构中，CPU可直接到寄存器、高速缓冲存储器、内存储器这三层上访问数据，不能直接到磁盘和磁

4、带上访问数据，那里的数据只有转移到内存储器后，才能接受CPU的处理。.高速缓冲存储器CPU主存储器字传送块传送 相对于内存，高速缓存容量小、存取速度快。在它里面只存放内存中的一小部分数据内容。 . 在CPU与内存间，可安排“高速缓冲存储器”，简称为“高速缓存”。. 当CPU试图访问内存中的某一个字时，就总是先检查该字是否在高速缓存中。如果在，就直接将它从高速缓存传送给CPU；如果不在，则先把内存中包含此字在内的一块数据读入高速缓存，然后再把所需的字从高速缓存传送给CPU。 槽号标签012C-10123块块（K个字）2n-1块（K个字）地址高速缓冲存储器主存储器 内存和高速缓存间是以“块”为单位

5、传递数据的，高速缓存与CPU之间则是以“字”为单位传递数据的。 . 当CPU需存取内存中某块里的某字，而那块不在存储槽中，就把那块传到一槽里。高速缓存中的槽都有标签，用来标识这个存储槽在当前存放的是内存中的哪一块。 存储扩充的含义是通过技术手段，给用户造成有一个非常大的内存的虚幻感觉，但其实并没有扩大实际内存的容量。存储管理若能做到这种意义下的存储扩充，那么就能使用户程序的规模不受内存实际容量的限制。存储扩充无疑是一件非常好的事情。这是虚拟存储要讨论的话题。1. 这是存储管理必须承担的任务，它应该随时记录内存的使用情况；根据用户程序的需要分配存储区；在用户程序运行完后，及时收回存储区，以提高内

6、存的使用效率。2. 存储共享是指允许多个进程访问内存中的同一部分，这是提高存储利用率的一种措施。. 存储保护涉及两个问题，一是确保用户进程的程序不侵犯操作系统；二是确保两个用户程序之间不相互干扰。.3. 为适应多道程序设计环境，为使内存中的程序能够移动，存储管理必须对用户程序逻辑地址空间中的地址实施重新定位，以保证进程程序的正确运行。4. 把用户程序指令中的相对地址变换成为所在绝对地址空间中的绝对地址的过程，称为“地址重定位地址重定位”。 1.2.01001KB2KB30003KBXXXXXXcall 100用户程序A的相对地址空间XXXXXXcall 100内存储器020KB20KB+100

7、21KB22KB20KB+300023KB操作系统XXXXXXXcall 20580内存储器020KB20KB+10021KB22KB20KB+300023KB操作系统XXXXXXcall 22628内存储器022KB22KB+10023KB24KB22KB+300025KB操作系统20KB.绝对地址(或物理地址).绝对地址空间(或物理地址空间).相对地址(或逻辑地址).相对地址空间(或逻辑地址空间)单元地址：单元地址：内存储器由一个个存储单元组成。一个存储单元内存储器由一个个存储单元组成。一个存储单元存放存放若干若干个二进制的位（个二进制的位（bitbit），），8 8个二进制的位被称做一个

8、二进制的位被称做一个字节（个字节（ByteByte）。内存中的存储单元按一定的顺序号进行）。内存中的存储单元按一定的顺序号进行编号，每个单元对应的编号，称为该单元的单元地址。编号，每个单元对应的编号，称为该单元的单元地址。物理地址：物理地址：在操作系统中，把单元地址称为内存储器在操作系统中，把单元地址称为内存储器的物理地址，也叫做的物理地址，也叫做绝对地址绝对地址。物理地址空间：物理地址空间：从任何一个绝对地址开始的一段连续的从任何一个绝对地址开始的一段连续的内存空间，被称为内存空间，被称为物理地址空间，物理地址空间，也称为也称为绝对地址绝对地址空间空间。逻辑地址空间逻辑地址空间：用户程序产生

9、出一个相对于用户程序产生出一个相对于“0”0”编编址的地址空间，这个地址空间被称为是址的地址空间，这个地址空间被称为是用户程序用户程序的的逻辑地址空间也称为逻辑地址空间也称为相对地址空间相对地址空间。逻辑地址逻辑地址：在逻辑地址空间中的地址被称为在逻辑地址空间中的地址被称为逻辑地址逻辑地址也叫做也叫做相对地址相对地址 。 要求编程人员熟悉内存使用情况，程序设计时要极小心地对待指令中的地址，不能够出现任何差错，否则后果不堪设想；1. 即在程序装入内存之前，程序指令中的地址就已经是绝对地址，已经正确地反映了它将要进入的存储区位置。. 优点：程序中的逻辑地址与实际内存中的物理地址完全相同。因此在程序

10、执行前不需对程序指令中的地址再进行任何调整和修改，装入到指定内存位置就可运行。.不适用于多道程序设计环境。缺点：(1)(2)(3)(4)程序进入内存后，不能做任何移动，只能固定在这个存储区内；对程序做任何微小修改，都可能会牵扯到程序整体的变动，费工耗时；2. 在多道程序设计环境下，用户事先无法、也不愿意知道自己的程序会被装入到内存的什么位置，他们只是向系统提供相对于“0”编址的程序。. 操作系统要有一个“重定位装入程序重定位装入程序”，功能是：一根据当前内存使用情况，为欲装入的二进制目标程序分配所需的存储区；二根据所分配的存储区，对程序中的指令地址进行重新计算和修改；三将重定位后的二进制目标程

11、序装入到指定的存储区中。 静态重定位由软件（重定位装入程序）实现，无须硬件提供支持； 静态重定位的特点静态重定位是在程序运行之前完成地址重定位工作的； 地址重定位的工作是在程序装入时被一次集中完成的； 物理地址空间里的目标程序与原逻辑地址空间里的目标程序面目已不相同，前者是后者进行地址调整后的结果 ； 实施静态重定位后，位于物理地址空间里的用户程序不能在内存中移动，除非再重新进行地址定位 ；. 采用这种重定位方式，用户向装入程序提供相对于“0”编址的二进制目标程序，无需关注程序具体的装入位置。通过重定位装入程序的加工，目标程序进入分配给它的物理地址空间，程序指令中的地址也都被修改为正确反映该空

12、间的情形。因为这种地址重定位是在程序执行前完成的，因此称为地址的“静态重定位静态重定位” 。 .(1)(2)(3)(4)(5)(6) 适用于多道程序设计环境。 3. 对用户程序实行地址的静态重定位后，定位后的程序就被“钉死”在了它的物理地址空间里，不能做任何移动。 . 将地址定位的时间推迟到程序执行时再进行，这就是地址“动态重定位”方式。在对程序实行动态重定位时需要硬件的支持。 为阻止用户程序指令中的地址闯入操作系统所占用的区域，在CPU里设置一个用于存储保护的专用寄存器：“界限寄存器”。 . 内存用户区又被分为“使用区”和“空闲区”两部分，分配给了用户、但又未使用的区域称为“内部碎片”。内部

13、碎片的存在是对内存资源的一种浪费。 1.2.单一连续分区存储管理的基本思想单一连续分区存储管理的基本思想单一连续区存储管理的特点单一连续区存储管理的特点 总体上把内存储器分为两个分区：一个分区固定分配给操作系统使用；另一个分配给用户使用，称为“用户区” 。.作业3作业2作业1操作系统用户区内存0ab操作系统使用区内存0ab空闲区用户区c操作系统使用区内存0ab空闲区ca界限寄存器系统总是把整个用户区分配给一个用户使用 。这种系统只适用于单用户（或单道）的情况。 进入内存作业独享系统中的所有资源，包括内存的整个用户区。 采用这种存储分配策略时，将对用户程序实行静态重定位。 . 作业比用户区小时，

14、就会形成碎片，造成内存储器资源的浪费。 3.4. 每次只能一个作业进入内存，故不适宜多道程序设计，系统的工作效率不高，资源利用率低下。 若用户作业的相对地址空间比用户区大，该作业就无法运行。 “覆盖”是早期为程序设计人员提供的扩充内存的技术，中心思想是允许作业的若干个程序段使用同一个存储区域，共用的存储区被称为“覆盖区”。 MAIN(10KB)A(50KB)B(30KB)C(30KB)D(20KB)E(40KB)MAIN(10KB)A(50KB)B(30KB)C(30KB)D(20KB)E(40KB)0180KB连接装配10KB50KB40KB内存MAINA或BC或D或E5. 对换技术对换技术

15、作业1作业2作业3辅助存储器内存储器操作系统用户区换出换入 基本思想：将作业都存放在辅存。每次只让其中的一个进入内存投入运行。当运行中提出输入输出请求或分配给的时间片用完时，就把这个程序从内存“换出”到辅存，把辅存里的另一个作业“换入”运行 ，产生出“多道”的效果。 1. 所谓“固定分区固定分区”存储管理，是指预先把内存的用户区划分成若干个连续的分区，它们的尺寸可以相同，也可以不同。划分后，内存中分区的个数以及每个分区的尺寸保持不变。每个分区里只允许装入一个作业运行。 2.操作系统第1分区(8KB)第2分区(32KB)第3分区(64KB)第4分区(132KB)0256KB20KBABCDEF操

16、作系统第1分区(8KB)第2分区(32KB)第3分区(64KB)第4分区(132KB)0256KB20KBABCDEF.每个分区设置一个后备作业队列 .多个分区只设置一个后备作业队列 一个作业到达时，总是进入到“能容纳该作业的最小分区”的那个后备作业队列里去排队。 当某个分区空闲时，统一都到这一个队列里去挑选作业，装入运行。 缺点 ：可能会产生有的分区队列忙碌、有的分区队列闲置的情形。作业尺寸比任何一个分区的长度都大时，就无法运行。 .3. 分区空闲时，若它的队列非空，就把该分区分配给队列的第一个作业使用；作业运行完毕，收回该分区，进行下一次分配。 每个分区设置一个后备作业队列 多个分区只设置

17、一个后备作业队列 在任何一个分区释放时，就根据分配方案从该队列里挑选一个作业装入运行。 4.在固定分区存储管理中，实行静态重定位实行静态重定位。. 在固定分区存储管理中，要防止用户程序对操作系统的侵扰，也要防止用户程序间的侵扰。因此设置一对专用寄存器：“低界限寄存器低界限寄存器”和和“高界高界限寄存器限寄存器” ，用于存储保护 。地址重定位存储保护0abcdab作业1作业2作业3第1分区第2分区第3分区操作系统低界限寄存器高界限寄存器CPU5.是最简单的、具有“多道”色彩的存储管理方案。 .作业程序一次性全部装入分配给它的连续分区。 .实行的是静态重定位。 .会产生内部碎片，引起内存资源的浪费

18、。 外部碎片：存储管理中，把那些无法分配出去满足作业存储请求的空闲区称为“外部碎片外部碎片”。 1.2. 在作业要求装入内存时，若当时内存中有足够的存储空间满足该作业的需求，那就划分出一个与作业相对地址空间同样大小的分区分配给它使用。 操作系统空闲区作业A(15KB)作业B(20KB)作业C(10KB)内存操作系统空闲区作业A(15KB)作业B(20KB)内存操作系统空闲区作业A(15KB)内存操作系统空闲区作业A(15KB)内存作业B(20KB)作业C(10KB). 内部碎片：存储管理中，把分配给了用户而用户未用的存储区称为“内部碎内部碎片片”。3. .采用地址动态重定位技术，使程序能在内存

19、中移动，为空闲区合并提供保证； . 记住各分区的使用情况，当一个分区被释放时，要能判定它的前、后分区是否为空闲区。若是空闲区，就进行合并，形成一个大的空闲区。 .给出分区分配算法，在有多个空闲区都满足作业的存储请求时，决定分配哪一个。 . 静态重定位是在程序运行之前完成地址转换的；动态重定位却是将地址转换的时刻推迟到指令执行时进行。 实行静态重定位，原来的指令地址部分被修改了；实行动态重定位，只是按照所形成的地址去执行这条指令，并不对指令本身做任何修改。 静态重定位是在装入时一次集中地把程序指令中所有要转换的地址全部加以转换；而动态重定位则是每执行一条指令时，对其地址加以转换。 静态重定位是由

20、软件完成地址转换工作的；动态重定位则由一套硬件提供的地址转换机构来完成。 1.2. 把相对地址空间中的用户作业程序“原封不动” 地装入到分配给它的绝对地址空间中去。执行某条指令时，才根据当前程序所在区域，对指令中的地址进行重定位。即指令中地址的转换是在程序执行时动态完成的，故称为地址的“动态重定位动态重定位”。 0用户作业A的相对地址空间XXXXXX1001KB2KB3000call 1003KB0XXXXXX22KB+10023KB24KB22KB+3000call 10025KB20KB22KB22KB定位寄存器2262822528操作系统内存.由地址变换线路取出 一是调度到某作业时一是调

21、度到某作业时，若系统的每个空闲区尺寸都小于它的需要，但空闲区总存储量大于它的存储请求，于是进行空闲区合并，得到一个大的空闲区，满足该作业的需要；一是只要有作业运行完一是只要有作业运行完归还所占用的存储区，系统就进行空闲区的合并。 释放区的前、后邻接分区都是空闲区。因此，释放区应该和前、后两个邻接的空闲区合并成一个新的空闲区。 释放区的前邻接分区是已分配区，后邻接分区是空闲区。因此，释放分区应该和后邻接的空闲区合并成一个新的空闲区。 释放分区的前邻接分区是空闲区，后邻接分区是已分配区。释放区应该和前邻接的空闲区合并成一个新的空闲区。 释放分区的前、后邻接分区都是已分配区，没有合并的问题存在。 1

22、.2.已分配区空闲区释放分区空闲区已分配区释放分区空闲区空闲区释放分区已分配区已分配区释放分区. 若有作业运行结束，则根据作业名到已分配表里找到它的表目项，将该项的 “状态”改为“空”，随之在空闲区表里寻找一个状态为“空”的表目项，把释放分区的信息填入，并将表目项状态改为“空闲”。 作业提出存储需求时，查空闲区表里状态为“空闲”的表目项。若该项的尺寸能满足所求，就将它一分为二：分配出去的那部分在已分配表里找一个状态为“空” 的表目项进行登记，剩下的部分仍在空闲区表里占据一个表目项。 1. 设置两张表：“已分配表”和“空闲区表”。其中“序号”是表目项的顺序号，“起始地址”、“尺寸”、“状态” 都

23、是该分区的相应属性。由于系统中分区的数目是变化的，因此每张表格中的表目项数要足够的多，暂时不用的表目项的状态被设为“空”。 内存操作系统空闲区(8KB)作业B(32KB)空闲区(32KB)作业D(120KB)空闲区(300KB)序号起始地址尺寸状态12345020KB28KB60KB92KB212KB512KB28KB32KB作业B空空空92KB120KB作业D序号起始地址尺寸状态1234560KB32KB作业B空闲空空作业D20KB8KB212KB300KB已分配表空闲区表. 把内存中每个空闲分区视为一个整体，在它里面开辟出两个单元，一个存放该分区的长度（size），一个存放它下一个空闲分区

24、的起址（next），操作系统开辟一个单元，存放第1个空闲分区的起址，这个单元称为“链首指针”。最后一个空闲分区的next里存放标志“NULL” 。这样一来，系统里所有空闲分区被next连接成一个链表。从链首指针出发，顺着各个空闲分区的next往下走，就能到达每一个空闲分区。 20KB8KB60KB2.sizenext空闲区长度下一个空闲区起址空闲区8KB212KB32KBNULL300KB20KB60KB空闲区(8KB)32KB212KB空闲区(32KB)300KBNULL空闲区(300KB)作业B(32KB)作业D(120KB)020KB28KB60KB92KB212KB512KB内存内存操

25、作系统链首指针链首指针.基本思想 对提出的任何一个存储请求，从空闲区链表首指针开始查看一个个空闲区。若有满足要求的，按尺寸分配，调整next指针；若到达NULL未见满足要求，则分配失败。 存储分配.存储释放作业完成任务后，将占用的存储区释放，链入空闲区链表（要调整指针和空闲区合并）。 在每个空闲分区里，即存放下一个空闲区起址next，也存放它的上一个空闲区起址（prior）的信息。这样，通过双向链表，就可以方便地由next找到一个空闲区的下一个空闲区，也可以由prior找到一个空闲区的上一个空闲区。 空闲区(300KB)sizenext.3.基本思想20KB空闲区长度下一个空闲区起址空闲区30

26、0KBNULL作业B(32KB)作业D(120KB)020KB28KB60KB92KB212KB512KB内存操作系统链首指针prior上一个空闲区起址空闲区(32KB)32KB212KB60KB20KB空闲区(8KB)8KB60KBNULL.存储合并 把释放区链入空闲区双向链表时，若通过它的prior发现该释放区的前面一个空闲区的起址加上长度，等于释放区的起址，那么说明它前面的空闲区与它直接邻接，应该把这个释放区与原先的空闲区合并。若释放区起址加上长度正好等于next所指的下一个空闲区的起址，那么说明它与后面的空闲区直接邻接，应该把这个释放区与原先的空闲区合并。 .空闲区的两种组织形式 若将

27、每个空闲分区按其起址由小到大排列在链表里，则把这种组织称为“地址法地址法”；若按每个空闲分区的长度由小到大排列在链表里，则把这种组织称为“尺寸法尺寸法”。 最先适应算法：最先适应算法：总是把最先找到的、满足存储需求的那个空闲分区作为分配的对象。 出发点尽量减少查找时间，有可能把大的空闲区分割许多小的分区，对大作业不利出发点尽量减少查找时间，有可能把大的空闲区分割许多小的分区，对大作业不利。1.2. 最佳适应算法：最佳适应算法：总是从当前所有空闲区中找出一个能够满足存储需求的、最小的空闲分区作为分配的对象 。尽可能不把大的空闲区分割许多小的分区，保证大作业需要。尽可能不把大的空闲区分割许多小的分

28、区，保证大作业需要。 最坏适应算法：最坏适应算法：总是从当前所有空闲区中找出一个能够满足存储需求的、最大的空闲分区作为分配的对象。出发点是照顾中、小作业的需求。出发点是照顾中、小作业的需求。.3.作业一次性地全部装入到一个连续的存储分区中。 . 分区是按照作业对存储的需求划分的，因此不会出现内部碎片这样的存储浪费。 .为确保作业能够在内存中移动，要由硬件支持实行指令地址的动态重定位。 . 只要作业的存储需求大于系统提供的整个用户区，该作业就无法投入运行。 . 有可能出现极小的分区暂时分配不出去的情形，产生外部碎片。 由于是通过移动程序来达到分区合并的目的，势必增加系统在这方面的时间投入与开销。

29、 地址法地址法 尺寸法尺寸法 最佳适应算法分配结果，找满足最佳适应算法分配结果，找满足需要，最小的空闲区需要，最小的空闲区 最坏适应算法分配结果，找满足最坏适应算法分配结果，找满足需要，最大的空闲区需要，最大的空闲区例例 3-3B请求240KB：.伙伴系统是基于固定分区和可变分区提出的一种折中存储管理方案。.在伙伴系统中，可用内存分区的大小为2K，LKU，其中： 2L表示分配的最小分区的尺寸； 2U表示分配的最大分区的尺寸。C(64KB)64KBA(128KB)128KBB(256KB)512KBA(128KB)B(256KB)512KBA(128KB)128KB256KB512KB1MBC(

30、64KB)64KBA(128KB)B(256KB)D(256KB)C(64KB)64KBA(128KB)256KBD(256KB)256KB256KBC(64KB)64KB128KB256KBD(256KB)256KBC(64KB)64KBE(128KB)256KBD(256KB)256KBE(128KB)128KB256KBD(256KB)256KB512KBD(256KB)256KB1MB1MB初启：A请求100KB：C请求64KB：D请求256KB：B释放256KB：A释放128KB：E请求128KB：C释放64KB：E释放128KB：D释放256KB：有一个1MB内存，采用伙伴系统管理

31、存储空间的分配和回收。 例：例：固定分区：限制可运行程序的道固定分区：限制可运行程序的道数，产生碎片，利用率低数，产生碎片，利用率低可变分区：按需求量划分，能可变分区：按需求量划分，能消除内部碎片，维护复杂。消除内部碎片，维护复杂。 用户作业仍然相对于“0”进行编址，形成一个连续的相对地址空间。操作系统按照内存块的尺寸对该空间进行划分，每一个分区被称为“页页”，编号从0开始。 把整个内存储器划分成大小相等的许多分区，每个分区称为“块块” 。比如把内存储器划分成n个分区，编号为0,1,2,n-1。块是存储分配的单位。 操作系统内存储器作业A(第2页)作业A(第0页)作业A(第1页)020KB24

32、KB28KB32KB36KB40KB44KB48KB256KB(04块)第5块第6块第7块第8块第9块第10块第11块04KB8KB11KB12KB第0页第1页第2页10921008(1, 1092)(2, 1008)51889200用户作业A的相对地址空间1.2.3.用户相对地址空间中的每一个相对地址，都可以用数对“页号，页内位移页号，页内位移”来表示。 用数对里的“页号”2去查作业A的页、块对应关系表。 把内存第7块的起始地址与页内位移相加，就得到了相对地址3000现在的绝对地址，即7K+952=8120。 记录作业A的页、块对应关系 4.用户作业A的相对地址空间XXXXXXcall 30

33、0001001KB2KB30003KB952第0页第1页第2页内存储器操作系统call 3000作业A(第0页)XXXXXX952作业A(第2页)作业A(第1页)04KB4KB+1005KB6KB7KB7KB+9528KB9KB10KB(03块)第4块第5块第6块第7块第8块第9块(2, 952)用户作业A的页、块对应关系页号块号0124977K+952=8120. 运行到指令“call 3000”时，把相对地址 3000 转换成：(2，952)。计算公式是： 页号=相对地址/块尺寸 页内位移=相对地址%块尺寸.系统就去做指令“call 8120”，从而得到了正确地执行 。 利用内存记录作业页

34、、块对应关系的表，就是“页表”。每个作业都有自己的页表。作业相对地址空间有多少页，页表就有多少个表项。为了地址转换，硬件设置一个专用寄存器：“页表控制寄存器”。进程调度时，把调度到作业的页表起址和长度放入寄存器中，达到映射不同作业地址的目的。 1. 把块(或页)的尺寸限定只能是2 的方幂，那么利用计算机系统设定的地址结构，很容易得到相对地址所对应的数对(页号，页内位移) 。0150140130121110101918170615141302010001501401301211101019181706151413020100015014013012111010191817061514130201

35、00页号(2)页内位移(952)页号(11)页内位移(184)2.利用内存构成页表操作系统内存储器块号页内位移绝对地址页表起始地址长度长度页表控制寄存器页号页内位移相对地址CPU(1)地址3000的二进制表示地址转换过程(2) 页表存放在内存，增加了系统在存储上的花销，还降低了CPU的访问速度。因为每次对某一地址的访问，先要访问内存中的页表，形成绝对地址后，才能进行所需的真正访问。因此，以前只须一次访问就能实现的操作，现在要两次访问内存才能实现。 实现页表的另一方法是用一组快速硬件寄存器构成公用页表。调度到谁就把谁的页表装入该组寄存器中。这样硬件把页号与寄存器组中所有表项同时并行比较，立即输出

36、与页号匹配的块号。这时无须访问内存，并且通过并行匹配直接完成地址变换，因此速度很快。 .操作系统内存储器块号页内位移绝对地址快速寄存器组页号页内位移相对地址CPU(1)(2) 快速寄存器价格昂贵，完全由它来组成页表的方案是不可取的。 .页表页表/快表快表 考虑到大多数程序在一次运行时，倾向于在少数页面中进行频繁访问（即程序的“局部性”原理），因此在实际系统中采用内存页表与快速寄存器组结合的解决方案，且只用极少几个快速寄存器来构成寄存器组，起名为：“相联寄存器”，或简称“快表”。 (1) 快表中只存部分页表。把一个相对地址划分出数对：（页号，页内位移）后，系统先通过页号与快表中的所有表项进行并行

37、比较。若发现了匹配的页，则将块号直接取出，不再通过页表。用该块号与页内位移拼接，形成所需要的绝对地址。(2) 作业长度不可能是页面尺寸的整数倍，平均说，分给作业的最后内存块会浪费掉一半。若内存中有n个作业，页面尺寸为p个字节，那么内存中就有n*p/2个字节被浪费掉。所以，页面尺寸要小。 当快表中没有匹配的页号时，地址转换机构按普通访问页表的方式工作，获得所需的绝对地址；再把这个页号与块号的对应关系送入快表保存，以便下一次进行地址转换时能够命中。若快表里没有空表项，则要先删除快表中的一个表项，然后将新的页表表项替换进去。页表控制寄存器操作系统内存储器块号页内位移绝对地址快表页号页内位移相对地址长

38、度起始地址页表(3).命中率 直接查快表就能实现内存访问的成功率为“命中率”。命中率越高，性能就越好。表中给出了平均命中率与相联寄存器个数的关系。从表中可以看出，设置快表，确实能够达到提高地址转换速度的目的。相联寄存器个数平均命中率8121685%93%97%.3. 页面尺寸小，用户作业相对地址空间的页面数就增加，页表就会加大。因此，从减少页表所需内存开销看，页面尺寸应该大一些为好。选择最佳页面尺寸，可能需在几个相互矛盾的因素间折中求得。 1.操作系统作业C第2页作业B第0页作业A第0页空闲块作业A第2页空闲块空闲块作业B第1页空闲块空闲块作业A第1页作业C第3页作业C第0页作业C第1页空闲块

39、内存储器064K空闲块链表起址块号状态0已分配1已分配2已分配3已分配4空闲5已分配6空闲7空闲8已分配9空闲10空闲11已分配12已分配13已分配14已分配15空闲空闲块总数：6 系统维持一张表格，表格表项与内存中的一块相对应， 记录该的块使用情况。只要表格中 “空闲块总数” 记录的数目大于请求的存储量，就可进行分配 ，并把分配出去的块的状态改为 “已分配” 。作业完成后归还存储块时，就把表中相应块的状态改为“空闲”。 单链表存储分块表 把空闲块链接成一个单链表加以管理，系统必须设置一个空闲块链表的起始地址指针，以便进行存储分配时能够找到空闲的内存块。无论是进行空闲块的分配还是作业完成后归还

40、存储块，都要调整空闲块间的链表指针。 . 作业虽然不占据连续的存储区，但每次仍要求一次全部进入内存。因此，如果作业很大，其存储需求大于内存，那么还是存在小内存不能运行大作业的问题。 用户作业的相对地址空间按照块的尺寸划分成页。这种划分是在系统内部进行的，用户感觉不到，即对用户是“透明”的。 2.内存存储器事先被划分成相等尺寸的块，它是进行存储分配的单位。 . 相对地址空间中的页可以进入内存中的任何一个空闲块，并且分页式存储管理实行的是动态重定位，因此它打破了一个作业必须占据连续存储空间的限制，作业在不连续的存储区里，也能够得到正确的运行。 3.平均每一个作业要浪费半页大小的存储块。 .位图 用

41、二进制位与内存块的使用建立起关系，为“0”，表示对应块空闲；为“1”，表示对应块已分配。 1111010010011110空闲块总数：60123456701字节号位号位图 独立的地址空间有助于实施对过程和数据的共享，不必在每一个用户作业的地址空间里都必须有相关的备份。 每个程序段是一个独立的逻辑实体（比如一个过程、一个数组或一个堆栈），因此可以对它们进行不同类型的存储保护 。 每个程序段是一个独立的地址空间，它们可独自增长或减小而不用顾及别的程序段，不会影响到其他程序段的地址空间。 所谓“分段式”存储管理，即要求用户将自己的作业程序以多个相互独立的称为“段”的地址空间提交给系统，每个段都是一个

42、从“0”开始的一维地址空间，长度不一。操作系统按照段长为作业分配内存空间。 改变某程序段尺寸，就会影响其他无关程序段的起址；对某个程序段进行修改，会影响到其他相关部分，就可能要对所有的程序重新进行链接编辑。 1.不利于按照程序段的性质，实施存储保护和共享。 .2.3. 在编译过程中会建立很多表，其中主要有：供打印程序清单的源程序文档；由变量名及其属性组成的符号表；由程序中所有的整型、实型常量组成的常量表；包含程序语法分析结果的语法分析树；内部过程调用时使用的堆栈。 通过编译程序在编译过程中建立的各种表，说明页式及段式存储管理中，作业程序地址空间组织形式的不同。 例例 ：解解： .在分页式管理时

43、，这5个表必须限定在一个一维的地址空间里，如图(a)所示。 使用使用使用使用使用空闲空闲空闲空闲堆栈语法分析树常量表源程序文档符号表(a)0KB4KB8KB12KB16KB20KB0KB4KB8KB12KB符号表段00KB源程序文档常量表段1段3段40KB4KB8KB12KB16KB语法分析树0KB4KB8KB12KB堆栈段2(b). 在分段管理时，是把这些表视为一个个相互独立的地址空间，比如：段0、段1等，它们组成了整个用户的地址空间，如图(b)所示。 系统为每个用户作业设置一个段表，用于记录各段在内存中的存放信息。逻辑空间中有多少段，段表里就有多少个表项。每个表项通常包括的信息有段号、段长

44、、该段在内存的基址（即起始地址）等。 如果段号s大于段表长度，表示该地址越界出错；否则以此段号为索引查段表，得到该段在内存的基址。 硬件要提供一个段表基址寄存器。每当重新调度时，就把调度到的作业的段表起址及段表长度（即段表中表项的个数）放入寄存器中，从而达到映射不同作业的目的。 . 在分段式存储管理时，要指示存储空间里的一个地址，必须提供两部分内容：段号和段内位移。即逻辑地址应该是二维的：段号，段内位移。. 在图(a)所示的32位地址结构中，各用16个二进制位表示段号s和段内位移d，因此表示用户的逻辑地址空间最多可以有216个段，每段最大长度是64KB。 3116 150sd段号段内位移ds段

45、号段内位移03123 22(a)(b). 图(b) 所示的32位的地址结构中，由于用9个二进制位表示段号s，用23个二进制位表示段内位移d，因此表示允许用户的逻辑地址空间中最多可以有29个段，每段的最大长度是223=8192KB。 .分段式存储管理时的地址转换步骤如下 ：.(1) 从相对地址数对：段号s，段内位移d中提取出段号s，用来进行地址转换。 (2)(3) 由段的基址和段内位移d拼装出所需的物理地址，实现对内存的访问。 段号(s)段内位移(d)相对地址段表段表基址寄存器段号 长度基址基址段内位移物理地址段sd内存程序分段地址转换机制.分段地址转换机制图示例：例： 在分段式存储管理中，某作

46、业的段表如下。有该作业的六个逻辑地址为： 0，430、3，400； 1，10、2，2500 、4，42、1，11。求对应的物理地址。段号 段 长 基 址 0 600 219 1 14 2300 2 100 90 3 580 1327 4 96 1954解：解： 对不同逻辑地址中的段号，有结果如下： （1）0，430的物理地址是219+430=649； （2）3，400的物理地址是1327+400=1727； （3）1，10的物理地址是2300+10=2310； （4）由逻辑地址知，是要访问第2段位于2500处的元素。但第2段的段长是100，表明所要访问的段内位移越界出错； （5）4，42的物理

47、地址是1954+42=1996； （6）1，11的物理地址是2300+11=2311。 在分页式环境下，存储保护只能以页面为单位。在页表的每一个表项里，设置一个所谓的“保护位”，该位的不同取值表示对应的页帧是可读、可写或只可读等。 .1. 被共享的程序文本部分不一定正好划分在一个或几个完整的页面中，有可能一个页面中既有允许共享的内容，又有不能共享的私有数据。因此，在分页式环境下实现页面的共享比较困难，但也不是不可能。 进程A的逻辑地址空间进程B的逻辑地址空间进程C的逻辑地址空间ed10ed21ed32dataA3ed10ed21ed32dataB3ed10ed21ed32dataC3进程A的页

48、表031426320314263203142632页号帧号进程B的页表页号帧号进程C的页表页号帧号操作系统0123456789101112dataAed1ed2ed3dataBdataC内存. 假定分页式存储管理的页帧尺寸为50KB，那么文本编辑程序被划分成3页，用户进程的数据段被划分成一页，合起来每个用户进程的逻辑地址空间为4页。 . 三个进程的逻辑地址空间和相应的页表，02页都划归文本编辑程序（即ed1，ed2，ed3），页表中的02表项都对应于页帧号3、4和6；进程的数据页（即dataA、dataB、dataC）都位于自己空间的第3页，分别存放在内存的2、8和11页帧。 811文本编辑程

49、序段0程序段段1数据段段2进程A的逻辑地址空间文本编辑程序段0程序段段1数据段段2进程B的逻辑地址空间堆栈段段30252861基址243062操作系统内存进程A的段表段号段长025286 1基址243062进程B的段表段号段长3A的数据段文本编辑程序B的数据段A的程序段B的堆栈段43062B的程序段2. 在分段式环境下，段是有完整意义的逻辑信息单位，因此对段中的所有内容可以采用相同的方式使用。 . 为实行存储保护，在段表表项里增加权限位，指出每段是可读、可写或只执行等信息。每次进行地址映射时，都将这次访问的类型与权限位比较，若不符合就产生出错中断。 . 在分段式存储管理中很容易实现段的共享，只

50、需在有关作业的段表中增加一个表项，让其基址指向共享段在内存中的起始地址即可。 . 进程A和B要共享文本编辑程序，就可把文本编辑程序作为它们地址空间中的段0。假定文本编辑程序存放在内存43062起始的连续分区里，那么在所对应的各段表中，段号为0的表项的基址都是43062，从而达到共享该文本编辑程序的目的。(1) 页是信息的物理单位，段是信息的逻辑单位：页是信息的物理单位，段是信息的逻辑单位：系统根据内存块的尺寸划分页，不考虑页中的信息是否完整。因此，一页对应的是信息的一个物理单位；段是基于用户程序结构提出的存储管理模式，用户知道自己的程序分多少段，每段在逻辑上都是相对完整的一组信息。所以，段是信

51、息的逻辑单位。 (2) 页的尺寸由系统确定，段的尺寸因段而异：页的尺寸由系统确定，段的尺寸因段而异：实行分页式存储管理的系统，页的尺寸是由系统确定的，它与内存页帧的大小相同。段的长度取决于用户编写的程序，不同的段有不同的长度。 (3) 页式地址空间是一维的，段式地址空间是二维的页式地址空间是一维的，段式地址空间是二维的 ：在分页式存储管理时，用户必须通过链接编辑程序，把各程序段链接成一个相对于0编址的一维线性空间，用户向系统提供的是一个一维的逻辑地址空间；在分段式存储管理时，用户不把各程序段连接成一个相对于0编址的一维线性空间，各程序段之间是通过段号，段内位移进行访问的。因此，用户向系统提供的

52、是一个二维的逻辑地址空间。. 形式上看，分段式与分页式存储管理有很多相似之处。比如，一个为（页号，页内位移），一个为段号，段内位移；一个有页表，一个有段表；如此等等。不过它们却是两个完全不同的概念 。.分段与分页的主要区别 1. 由于程序执行具有“局部性”，因此实际运行时，没有必要把全部信息都放在内存里。只要合理组织，调度恰当，在发现所需访问的信息不在内存时，能够找到它，能够把它调入内存，那么不仅可以保证作业的正确执行，而且还提高了系统的资源利用率，使得系统具有更高的运行效率。 2. 作业提交给系统时，先进入辅存。运行时，只将部分信息装入内存，大部分仍保存在辅存中。运行过程中需要用到不在内存的

53、信息时，再把它们调入，以保证程序的正常运行。这样一个被用户认为有的、但实际上不存在的“大”存储器，就被称为“虚拟存储器虚拟存储器”。. 虚拟存储器是一种扩大内存容量的设计技术，它把辅存作为计算机内存的后援。在虚拟存储意义下，用户作业的相对地址空间，就是系统提供给他的虚拟存储器。在多道程序设计环境下，每个用户都有自己的虚拟存储器。在提供虚拟存储管理的系统里，把用户作业的相对地址空间称为“虚拟地址空间虚拟地址空间”，里面的地址称为“虚拟地虚拟地址址”。 把内存划分成尺寸相同、位置固定的块。然后按照内存块的大小，把作业的虚拟地址空间（即以前的相对地址空间）划分成页。由于页的尺寸与块一样，因此虚拟地址

54、空间中的一页，可以装入到内存中的任何一块中。 最多可有2048页每页1KB第0页第1页第2页虚拟存储器第2045页第2046页第2047页第0块第1块第2块第29块第30块第31块内存储器1.2. 作业全部进入辅存。运行时，只装入要用的若干页，其他页仍在辅存。运行过程中，虚拟地址被转换成数对：(页号，页内位移)。由页号查页表，若该页在内存，运行就进行下去；若该页不在内存，表明“缺页”，运行无法继续。这时，就根据页号把该页从辅存调入内存。所所谓谓“请求分页式请求分页式”，即是当运行中需要某页时，再把它从辅存调入内存使用，即是当运行中需要某页时，再把它从辅存调入内存使用的意思。的意思。 中断处理程

55、序查存储分块表，找空闲块；根据页在辅存的位置，启动磁盘读信息。 2171.页号块号缺页中断位辅存地址 在请求分页式存储管理中，是由页表表目项的“缺页中断位缺页中断位”来判断所需页是否在内存的。该位为“1”，表示此页在内存；为“0”，表示不在内存，并发出“缺页”中断信号，以求得系统的处理。 2.作业2虚拟地址空间05184KB8KB830012KBcall 8300第0页第1页第2页XXXXXX205114012操作系统第7块作业2的页表内存储器作业2第2页 根据执行指令中的虚拟地址，（页号，页内位移）。用页号去查页表，判断该页是否在内存。 若该页缺页中断位为“0”，产生缺页中断，进行中断处理。

56、 把从磁盘上读出的信息装入到分配的内存块中。 修改页表中相应的表目内容，修改存储分块表里相应表目的状态。 在完成所需页面的装入后，返回原指令重新执行。(1)(2)(3)(4)(5)(6) 假定一个作业运行的页面走向中涉及的页面总数为A，其中有F次缺页，必须通过缺页中断把它们调入内存。定义： f=F/A称 f 为 “缺页中断率缺页中断率” 。显然 ，缺页中断率与缺页中断的次数有密切的关系。 缺页中断处理完成后，仍返回到原指令去重新执行，因为那条指令并未执行。而一般中断则是返回到下一条指令去执行，因为这条指令已经执行完毕了。 缺页中断是在执行一条指令时产生的中断，并立即转去处理;一般中断则是在一条

57、指令执行完后，发现有中断请求时才去响应和处理 。3.4. 作业运行时，虚拟地址在随时发生变化，它是程序的执行轨迹，是程序的一种动态特征。由于每个虚拟地址都与一个数对：（页号，页内位移）相对应，因此这种动态特征可以用程序执行时页号的变化来描述。通常，称一个程序执行过程中页号的变化序列为“页面走向页面走向”。 所给程序的页面走向是：0、1、0、2、0、1，涉及的页面总数是6.。.用户作业程序100 LOAD 1#, 1120104 ADD 1#, 2410108 STORE 1#, 1124虚拟地址100112010424101081124数对：(页号, 页内位移)(0, 100)(1, 96)(

58、0, 104)(2, 362)(0, 108)(1, 100)页面走向010201 程序1按行对a的元素初始化，缺页中断进一页，就能完成对a一行元素的初始化。a共128行，需128次缺页中断将它们调入，完成对a的初始化。程序2按列对a的元素初始化。通过缺页中断进来一页，只能对a的一行的一个列元素初始化。于是，每列元素的初始化，须128次缺页中断才完成。程序2需128128 = 16384次缺页中断，才能完成a的初始化工作。 要把128128的数组元素初始化为“0”。数组中的每个元素占一个字。若页面尺寸为128字，规定数组按行存放，系统只给该作业2个内存块：一个存程序，另一个用于数组初始化。开始

59、时，程序已在内存块，数据未进入。试问下面给出的两个程序在运行时各会发生多少次缺页中断？ 页面尺寸页面尺寸：页面尺寸是与块尺寸相同的，因此块大页也就大。页面增大了，在每个内存块里的信息相应增加，缺页的可能性下降。反之，页面尺寸减少，每块里的信息减少，缺页的可能性上升。 分配给作业的内存块数分配给作业的内存块数：由于分配给作业的内存块数多，同时能够装入内存的作业页面就多，缺页的可能性下降，发生缺页中断的可能性也就下降。影响缺页中断次数的因素影响缺页中断次数的因素 .(1)程序的实现程序的实现：作业程序的编写方法，对缺页中断产生的次数也会有影响。(2)(3)例：例：程序1：程序2：main()mai

60、n() int a128128; int a128128; int i,j; int i,j; for(i=0;i128;i+) for(j=0;j128;j+) for(j=0;j128;j+) for(i=0;i128;i+) aij=0; aij=0;解：解： 改变位：该位为“0”时，表示此页面在内存时数据未被修改过；为“1”时，表示被修改过。当其为淘汰对象时，根据此位的取值来确定是否要进行磁盘回写操作。 引用位：在系统规定的时间间隔内，该页是否被引用过的标志（该位在页面淘汰算法中将会用到）。1.缺页时，要从辅存把所需页面调入内存。若当时内存有空闲块，那么不会有什么问题；若当时内存中已没