1、第3章 存储管理,3.1,3.2,3.3,本章讲述内容：,3.4,存储管理综述；,固定分区存储管理；,可变分区存储管理；,分页式存储管理;,3.5,分段式存储管理;,3.6,虚拟存储与请求页式存储管理。,3.1 存储管理综述,3.1.1 存储器的层次结构,目前，计算机采用的都是以存储器为中心的体系结构。存储器负责存放整个系统的程序与数据，是重要的系统资源。,.,磁带,磁盘,主存储器,高速缓存,寄存器,快,慢,存取速度,小,大,容量,昂贵,便宜,价格,.,在考虑计算机存储器的设计时，必须顾及“价格”、“容量”、“访问时间”这三个重要特性。各种实现技术间往往有以下的关系：存取时间越快，每“位”的价
2、格就越高；容量越大，每“位”的价格就越低；容量越大，存取速度就越慢。,.,只能在“价格”、“容量”、“访问时间”三者间寻求折中，采用存储器的层次结构 。这时，从上往下就有：每“位”的价格递减；存储容量递增；存取时间递增。,.,这种层次结构中，容量较大、价格便宜的慢速存储器（如磁盘），可作为容量较小、价格较贵的快速存储器的后备。这正是存储管理中虚拟存储技术的实现基础。,这种层次结构中，CPU可直接到寄存器、高速缓冲存储器、内存储器这三层上访问数据，不能直接到磁盘和磁带上访问数据，那里的数据只有转移到内存储器后，才能接受CPU的处理。,.,3.1.2 高速缓冲存储器的工作原理,高速缓冲存储器,CP
3、U,主存储器,字传送,块传送,相对于内存，高速缓存容量小、存取速度快。在它里面只存放内存中的一小部分数据内容。,.,在CPU与内存间，可安排“高速缓冲存储器”，简称为“高速缓存”。,.,.,当CPU试图访问内存中的某一个字时，就总是先检查该字是否在高速缓存中。如果在，就直接将它从高速缓存传送给CPU；如果不在，则先把内存中包含此字在内的一块数据读入高速缓存，然后再把所需的字从高速缓存传送给CPU。,槽号,标签,0,1,2,C-1,0,1,2,3,块,块（K个字）,2n-1,块（K个字）,地址,高速缓冲存储器,主存储器,内存和高速缓存间是以“块”为单位传递数据的，高速缓存与CPU之间则是以“字”
4、为单位传递数据的。,.,.,当CPU需存取内存中某块里的某字，而那块不在存储槽中，就把那块传到一槽里。高速缓存中的槽都有标签，用来标识这个存储槽在当前存放的是内存中的哪一块。,3.1.3 存储管理的功能,存储扩充的含义是通过技术手段，给用户造成有一个非常大的内存的虚幻感觉，但其实并没有扩大实际内存的容量。存储管理若能做到这种意义下的存储扩充，那么就能使用户程序的规模不受内存实际容量的限制。存储扩充无疑是一件非常好的事情。这是虚拟存储要讨论的话题。,1.,这是存储管理必须承担的任务，它应该随时记录内存的使用情况；根据用户程序的需要分配存储区；在用户程序运行完后，及时收回存储区，以提高内存的使用效
5、率。,内存的分配与回收,2.,存储保护和共享,存储共享是指允许多个进程访问内存中的同一部分，这是提高存储利用率的一种措施。,.,存储保护涉及两个问题，一是确保用户进程的程序不侵犯操作系统；二是确保两个用户程序之间不相互干扰。,.,3.,地址定位,为适应多道程序设计环境，为使内存中的程序能够移动，存储管理必须对用户程序逻辑地址空间中的地址实施重新定位，以保证进程程序的正确运行。,4.,存储扩充,把用户程序指令中的相对地址变换成为所在绝对地址空间中的绝对地址的过程，称为“地址重定位”。,3.2 固定分区存储管理,3.2.1 地址重定位,几个概念,1.,地址重定位的定义,2.,0,100,1KB,2
6、KB,3000,3KB,XXXXXX,call 100,用户程序A的相对地址空间,XXXXXX,call 100,内存储器,0,20KB,20KB+100,21KB,22KB,20KB+3000,23KB,操作系统,X,XXXXXX,call 20580,内存储器,0,20KB,20KB+100,21KB,22KB,20KB+3000,23KB,操作系统,XXXXXX,call 22628,内存储器,0,22KB,22KB+100,23KB,24KB,22KB+3000,25KB,操作系统,20KB,.,绝对地址(或物理地址),.,绝对地址空间(或物理地址空间),.,相对地址(或逻辑地址),.
7、,相对地址空间(或逻辑地址空间),要求编程人员熟悉内存使用情况，程序设计时要极小心地对待指令中的地址，不能够出现任何差错，否则后果不堪设想；,3.2.2 地址定位方式和静态重定位,1.,绝对定位方式,即在程序装入内存之前，程序指令中的地址就已经是绝对地址，已经正确地反映了它将要进入的存储区位置。,.,.,优点：程序中的逻辑地址与实际内存中的物理地址完全相同。因此在程序执行前不需对程序指令中的地址再进行任何调整和修改，装入到指定内存位置就可运行。,.,不适用于多道程序设计环境。,缺点：,(1),(2),(3),(4),程序进入内存后，不能做任何移动，只能固定在这个存储区内；,对程序做任何微小修改
8、，都可能会牵扯到程序整体的变动，费工耗时；,2.,静态重定位方式,.,在多道程序设计环境下，用户事先无法、也不愿意知道自己的程序会被装入到内存的什么位置，他们只是向系统提供相对于“0”编址的程序。,.,操作系统要有一个“重定位装入程序”，功能是：一根据当前内存使用情况，为欲装入的二进制目标程序分配所需的存储区；二根据所分配的存储区，对程序中的指令地址进行重新计算和修改；三将重定位后的二进制目标程序装入到指定的存储区中。,静态重定位由软件（重定位装入程序）实现，无须硬件提供支持；,静态重定位的特点,静态重定位是在程序运行之前完成地址重定位工作的；,地址重定位的工作是在程序装入时被一次集中完成的；
9、,物理地址空间里的目标程序与原逻辑地址空间里的目标程序面目已不相同，前者是后者进行地址调整后的结果 ；,实施静态重定位后，位于物理地址空间里的用户程序不能在内存中移动，除非再重新进行地址定位 ；,.,采用这种重定位方式，用户向装入程序提供相对于“0”编址的二进制目标程序，无需关注程序具体的装入位置。通过重定位装入程序的加工，目标程序进入分配给它的物理地址空间，程序指令中的地址也都被修改为正确反映该空间的情形。因为这种地址重定位是在程序执行前完成的，因此称为地址的“静态重定位” 。,.,(1),(2),(3),(4),(5),(6),适用于多道程序设计环境。,3.,动态重定位方式,对用户程序实行
10、地址的静态重定位后，定位后的程序就被“钉死”在了它的物理地址空间里，不能做任何移动。,.,.,将地址定位的时间推迟到程序执行时再进行，这就是地址“动态重定位”方式。在对程序实行动态重定位时需要硬件的支持。,为阻止用户程序指令中的地址闯入操作系统所占用的区域，在CPU里设置一个用于存储保护的专用寄存器：“界限寄存器”。,.,内存用户区又被分为“使用区”和“空闲区”两部分，分配给了用户、但又未使用的区域称为“内部碎片”。内部碎片的存在是对内存资源的一种浪费。,3.2.3 单一连续分区存储管理,1.,2.,单一连续分区存储管理的基本思想,单一连续区存储管理的特点,总体上把内存储器分为两个分区：一个分
11、区固定分配给操作系统使用；另一个分配给用户使用，称为“用户区” 。,.,.,.,.,.,作业3,作业2,作业1,操作系统,用户区,内存,0,a,b,操作系统,使用区,内存,0,a,b,空闲区,用户区,c,操作系统,使用区,内存,0,a,b,空闲区,c,a,界限寄存器,系统总是把整个用户区分配给一个用户使用 。,这种系统只适用于单用户（或单道）的情况。,进入内存作业独享系统中的所有资源，包括内存的整个用户区。,采用这种存储分配策略时，将对用户程序实行静态重定位。,.,作业比用户区小时，就会形成碎片，造成内存储器资源的浪费。,3.,单一连续分区管理的缺点,.,.,4.,覆盖技术,每次只能一个作业进
12、入内存，故不适宜多道程序设计，系统的工作效率不高，资源利用率低下。,若用户作业的相对地址空间比用户区大，该作业就无法运行。,“覆盖”是早期为程序设计人员提供的扩充内存的技术，中心思想是允许作业的若干个程序段使用同一个存储区域，共用的存储区被称为“覆盖区”。,MAIN(10KB),A(50KB),B(30KB),C(30KB),D(20KB),E(40KB),MAIN(10KB),A(50KB),B(30KB),C(30KB),D(20KB),E(40KB),0,180KB,连接装配,10KB,50KB,40KB,内存,MAIN,A或B,C或D或E,5.,对换技术,作业1,作业2,作业3,辅助存
13、储器,内存储器,操作系统,用户区,换出,换入,基本思想：将作业都存放在辅存。每次只让其中的一个进入内存投入运行。当运行中提出输入输出请求或分配给的时间片用完时，就把这个程序从内存“换出”到辅存，把辅存里的另一个作业“换入”运行 ，产生出“多道”的效果。,3.2.4 固定分区存储管理,1.,基本思想,所谓“固定分区”存储管理，是指预先把内存的用户区划分成若干个连续的分区，它们的尺寸可以相同，也可以不同。划分后，内存中分区的个数以及每个分区的尺寸保持不变。每个分区里只允许装入一个作业运行。,2.,对作业的组织,操作系统,第1分区(8KB),第2分区(32KB),第3分区(64KB),第4分区(13
14、2KB),0,256KB,20KB,A,B,C,D,E,F,操作系统,第1分区(8KB),第2分区(32KB),第3分区(64KB),第4分区(132KB),0,256KB,20KB,A,B,C,D,E,F,.,每个分区设置一个后备作业队列,.,多个分区只设置一个后备作业队列,一个作业到达时，总是进入到“能容纳该作业的最小分区”的那个后备作业队列里去排队。,当某个分区空闲时，统一都到这一个队列里去挑选作业，装入运行。,作业尺寸比任何一个分区的长度都大时，就无法运行。,.,.,3.,分区的分配与释放,.,分区空闲时，若它的队列非空，就把该分区分配给队列的第一个作业使用；作业运行完毕，收回该分区，
15、进行下一次分配。,每个分区设置一个后备作业队列,多个分区只设置一个后备作业队列,在任何一个分区释放时，就根据分配方案从该队列里挑选一个作业装入运行。,4.,地址重定位与存储保护,在固定分区存储管理中，实行静态重定位。,.,在固定分区存储管理中，要防止用户程序对操作系统的侵扰，也要防止用户程序间的侵扰。因此设置一对专用寄存器：“低界限寄存器”和“高界限寄存器” ，用于存储保护 。,地址重定位,存储保护,0,a,b,c,d,a,b,作业1,作业2,作业3,第1分区,第2分区,第3分区,操作系统,低界限寄存器,高界限寄存器,CPU,5.,固定分区存储管理的特点与缺点,.,是最简单的、具有“多道”色彩
16、的存储管理方案。,.,作业程序一次性全部装入分配给它的连续分区。,.,实行的是静态重定位。,.,.,会产生内部碎片，引起内存资源的浪费。,外部碎片：存储管理中，把那些无法分配出去满足作业存储请求的空闲区称为“外部碎片”。,3.3.1 可变分区存储管理的基本思想,3.3 可变分区存储管理,1.,基本思想,2.,内、外部碎片,在作业要求装入内存时，若当时内存中有足够的存储空间满足该作业的需求，那就划分出一个与作业相对地址空间同样大小的分区分配给它使用。,操作系统,空闲区,作业A(15KB),作业B(20KB),作业C(10KB),内存,操作系统,空闲区,作业A(15KB),作业B(20KB),内存
17、,操作系统,空闲区,作业A(15KB),内存,操作系统,空闲区,作业A(15KB),内存,作业B(20KB),作业C(10KB),.,.,内部碎片：存储管理中，把分配给了用户而用户未用的存储区称为“内部碎片”。,3.,实施可变分区存储管理要解决的三个问题,.,采用地址动态重定位技术，使程序能在内存中移动，为空闲区合并提供保证；,.,记住各分区的使用情况，当一个分区被释放时，要能判定它的前、后分区是否为空闲区。若是空闲区，就进行合并，形成一个大的空闲区。,.,给出分区分配算法，在有多个空闲区都满足作业的存储请求时，决定分配哪一个。,.,静态重定位是在程序运行之前完成地址转换的；动态重定位却是将地
18、址转换的时刻推迟到指令执行时进行。,实行静态重定位，原来的指令地址部分被修改了；实行动态重定位，只是按照所形成的地址去执行这条指令，并不对指令本身做任何修改。,静态重定位是在装入时一次集中地把程序指令中所有要转换的地址全部加以转换；而动态重定位则是每执行一条指令时，对其地址加以转换。,静态重定位是由软件完成地址转换工作的；动态重定位则由一套硬件提供的地址转换机构来完成。,1.,基本思想,2.,静态和动态重定位的比较,3.3.2 地址的动态重定位,把相对地址空间中的用户作业程序“原封不动” 地装入到分配给它的绝对地址空间中去。执行某条指令时，才根据当前程序所在区域，对指令中的地址进行重定位。即指
19、令中地址的转换是在程序执行时动态完成的，故称为地址的“动态重定位”。,0,用户作业A的相对地址空间,XXXXXX,100,1KB,2KB,3000,call 100,3KB,0,XXXXXX,22KB+100,23KB,24KB,22KB+3000,call 100,25KB,20KB,22KB,22KB,定位寄存器,22628,22528,操作系统,内存,.,.,.,一是调度到某作业时，若系统的每个空闲区尺寸都小于它的需要，但空闲区总存储量大于它的存储请求，于是进行空闲区合并，得到一个大的空闲区，满足该作业的需要；一是只要有作业运行完归还所占用的存储区，系统就进行空闲区的合并。,释放区的前、
20、后邻接分区都是空闲区。因此，释放区应该和前、后两个邻接的空闲区合并成一个新的空闲区。,释放区的前邻接分区是已分配区，后邻接分区是空闲区。因此，释放分区应该和后邻接的空闲区合并成一个新的空闲区。,释放分区的前邻接分区是空闲区，后邻接分区是已分配区。释放区应该和前邻接的空闲区合并成一个新的空闲区。,释放分区的前、后邻接分区都是已分配区，没有合并的问题存在。,3.3.3 空闲区的合并,1.,前后相邻接分区的四种关系,2.,空闲分区合并的时机,已分配区,空闲区,释放分区,空闲区,已分配区,释放分区,空闲区,空闲区,释放分区,已分配区,已分配区,释放分区,.,.,.,.,若有作业运行结束，则根据作业名到
21、已分配表里找到它的表目项，将该项的 “状态”改为“空”，随之在空闲区表里寻找一个状态为“空”的表目项，把释放分区的信息填入，并将表目项状态改为“空闲”。,作业提出存储需求时，查空闲区表里状态为“空闲”的表目项。若该项的尺寸能满足所求，就将它一分为二：分配出去的那部分在已分配表里找一个状态为“空” 的表目项进行登记，剩下的部分仍在空闲区表里占据一个表目项。,3.3.4 分区的管理与组织方式,1.,表格法,设置两张表：“已分配表”和“空闲区表”。其中“序号”是表目项的顺序号，“起始地址”、“尺寸”、“状态” 都是该分区的相应属性。由于系统中分区的数目是变化的，因此每张表格中的表目项数要足够的多，暂
22、时不用的表目项的状态被设为“空”。,内存,操作系统,空闲区(8KB),作业B(32KB),空闲区(32KB),作业D(120KB),空闲区(300KB),序号,起始地址,尺寸,状态,1,2,3,4,5,0,20KB,28KB,60KB,92KB,212KB,512KB,28KB,32KB,作业B,空,空,空,92KB,120KB,作业D,序号,起始地址,尺寸,状态,1,2,3,4,5,60KB,32KB,作业B,空闲,空,空,作业D,20KB,8KB,212KB,300KB,已分配表,空闲区表,.,.,.,把内存中每个空闲分区视为一个整体，在它里面开辟出两个单元，一个存放该分区的长度（size
23、），一个存放它下一个空闲分区的起址（next），操作系统开辟一个单元，存放第1个空闲分区的起址，这个单元称为“链首指针”。最后一个空闲分区的next里存放标志“NULL” 。这样一来，系统里所有空闲分区被next连接成一个链表。从链首指针出发，顺着各个空闲分区的next往下走，就能到达每一个空闲分区。,20KB,8KB,60KB,2.,单链表法,.,size,next,空闲区长度,下一个空闲区起址,空闲区,8KB,212KB,32KB,NULL,300KB,20KB,60KB,空闲区(8KB),32KB,212KB,空闲区(32KB),300KB,NULL,空闲区(300KB),作业B(32K
24、B),作业D(120KB),0,20KB,28KB,60KB,92KB,212KB,512KB,内存,操作系统,链首指针,链首指针,.,基本思想,对提出的任何一个存储请求，从空闲区链表首指针开始查看一个个空闲区。若有满足要求的，按尺寸分配，调整next指针；若到达NULL未见满足要求，则分配失败。,存储分配,.,存储释放,作业完成任务后，将占用的存储区释放，链入空闲区链表（要调整指针和空闲区合并）。,在每个空闲分区里，即存放下一个空闲区起址next，也存放它的上一个空闲区起址（prior）的信息。这样，通过双向链表，就可以方便地由next找到一个空闲区的下一个空闲区，也可以由prior找到一个
25、空闲区的上一个空闲区。,空闲区(300KB),size,next,.,3.,双链表法,基本思想,20KB,空闲区长度,下一个空闲区起址,空闲区,300KB,NULL,作业B(32KB),作业D(120KB),0,20KB,28KB,60KB,92KB,212KB,512KB,内存,操作系统,链首指针,prior,上一个空闲区起址,空闲区(32KB),32KB,212KB,60KB,20KB,空闲区(8KB),8KB,60KB,NULL,.,存储合并,把释放区链入空闲区双向链表时，若通过它的prior发现该释放区的前面一个空闲区的起址加上长度，等于释放区的起址，那么说明它前面的空闲区与它直接邻接
26、，应该把这个释放区与原先的空闲区合并。若释放区起址加上长度正好等于next所指的下一个空闲区的起址，那么说明它与后面的空闲区直接邻接，应该把这个释放区与原先的空闲区合并。,.,空闲区的两种组织形式,若将每个空闲分区按其起址由小到大排列在链表里，则把这种组织称为“地址法”；若按每个空闲分区的长度由小到大排列在链表里，则把这种组织称为“尺寸法”。,最先适应算法：总是把最先找到的、满足存储需求的那个空闲分区作为分配的对象。,3.3.5 空闲分区的分配算法,1.,三种分配算法,2.,可变分区存储管理的特点,最佳适应算法：总是从当前所有空闲区中找出一个能够满足存储需求的、最小的空闲分区作为分配的对象 。
27、,最坏适应算法：总是从当前所有空闲区中找出一个能够满足存储需求的、最大的空闲分区作为分配的对象。,.,.,.,3.,可变分区存储管理的缺点,.,.,作业一次性地全部装入到一个连续的存储分区中。,.,分区是按照作业对存储的需求划分的，因此不会出现内部碎片这样的存储浪费。,.,为确保作业能够在内存中移动，要由硬件支持实行指令地址的动态重定位。,.,只要作业的存储需求大于系统提供的整个用户区，该作业就无法投入运行。,.,有可能出现极小的分区暂时分配不出去的情形，产生外部碎片。,由于是通过移动程序来达到分区合并的目的，势必增加系统在这方面的投入与开销。,B请求240KB：,3.3.6 伙伴系统,.,伙
28、伴系统是基于固定分区和可变分区提出的一种折中存储管理方案。,.,在伙伴系统中，可用内存分区的大小为2K，LKU，其中： 2L表示分配的最小分区的尺寸； 2U表示分配的最大分区的尺寸。,C(64KB),64KB,A(128KB),128KB,B(256KB),512KB,A(128KB),B(256KB),512KB,A(128KB),128KB,256KB,512KB,1MB,C(64KB),64KB,A(128KB),B(256KB),D(256KB),C(64KB),64KB,A(128KB),256KB,D(256KB),256KB,256KB,C(64KB),64KB,128KB,25
29、6KB,D(256KB),256KB,C(64KB),64KB,E(128KB),256KB,D(256KB),256KB,E(128KB),128KB,256KB,D(256KB),256KB,512KB,D(256KB),256KB,1MB,1MB初启：,A请求100KB：,C请求64KB：,D请求256KB：,B释放256KB：,A释放128KB：,E请求128KB：,C释放64KB：,E释放128KB：,D释放256KB：,有一个1MB内存，采用伙伴系统管理存储空间的分配和回收。,例：,用户作业仍然相对于“0”进行编址，形成一个连续的相对地址空间。操作系统按照内存块的尺寸对该空间进行划
30、分，每一个分区被称为“页”，编号从0开始。,用户作业相对地址空间的划分,把整个内存储器划分成大小相等的许多分区，每个分区称为“块” 。比如把内存储器划分成n个分区，编号为0,1,2,n-1。块是存储分配的单位。,3.4 分页式存储管理,3.4.1 分页式存储管理的基本思想,操作系统,内存储器,作业A(第2页),作业A(第0页),作业A(第1页),0,20KB,24KB,28KB,32KB,36KB,40KB,44KB,48KB,256KB,(04块),第5块,第6块,第7块,第8块,第9块,第10块,第11块,0,4KB,8KB,11KB,12KB,第0页,第1页,第2页,1092,1008,
31、(1, 1092),(2, 1008),5188,9200,用户作业A的相对地址空间,1.,内存的划分,2.,3.,相对地址的映射,用户相对地址空间中的每一个相对地址，都可以用数对“页号，页内位移”来表示。,用数对里的“页号”2去查作业A的页、块对应关系表。,把内存第7块的起始地址与页内位移相加，就得到了相对地址3000现在的绝对地址，即7K+952=8120。,记录作业A的页、块对应关系,4.,分页式存储管理的地址重定位,用户作业A的相对地址空间,XXXXXX,call 3000,0,100,1KB,2KB,3000,3KB,952,第0页,第1页,第2页,内存储器,操作系统,call 30
32、00,作业A(第0页),XXXXXX,952,作业A(第2页),作业A(第1页),0,4KB,4KB+100,5KB,6KB,7KB,7KB+952,8KB,9KB,10KB,(03块),第4块,第5块,第6块,第7块,第8块,第9块,(2, 952),用户作业A的页、块对应关系,页号,块号,0,1,2,4,9,7,7K+952=8120,.,.,.,运行到指令“call 3000”时，把相对地址 3000 转换成：(2，952)。计算公式是： 页号=相对地址/块尺寸 页内位移=相对地址%块尺寸,.,.,系统就去做指令“call 8120”，从而得到了正确地执行 。,利用内存记录作业页、块对应
33、关系的表，就是“页表”。每个作业都有自己的页表。作业相对地址空间有多少页，页表就有多少个表项。为了地址转换，硬件设置一个专用寄存器：“页表控制寄存器”。进程调度时，把调度到作业的页表起址和长度放入寄存器中，达到映射不同作业地址的目的。,3.4.2 分页式存储管理的地址转换,1.,数对(页号，页内位移)的形成,把块(或页)的尺寸限定只能是2 的方幂，那么利用计算机系统设定的地址结构，很容易得到相对地址所对应的数对(页号，页内位移) 。,0,15,0,14,0,13,0,12,1,11,0,10,1,9,1,8,1,7,0,6,1,5,1,4,1,3,0,2,0,1,0,0,0,15,0,14,0
34、,13,0,12,1,11,0,10,1,9,1,8,1,7,0,6,1,5,1,4,1,3,0,2,0,1,0,0,0,15,0,14,0,13,0,12,1,11,0,10,1,9,1,8,1,7,0,6,1,5,1,4,1,3,0,2,0,1,0,0,页号(2),页内位移(952),页号(11),页内位移(184),2.,页表与快表,.,利用内存构成页表,操作系统,内存储器,块号,页内位移,绝对地址,页表,起始地址,长度,页表控制寄存器,页号,页内位移,相对地址,CPU,(1),(2),页表存放在内存，增加了系统在存储上的花销，还降低了CPU的访问速度。因为每次对某一地址的访问，先要访问
35、内存中的页表，形成绝对地址后，才能进行所需的真正访问。因此，以前只须一次访问就能实现的操作，现在要两次访问内存才能实现。,实现页表的另一方法是用一组快速硬件寄存器构成公用页表。调度到谁就把谁的页表装入该组寄存器中。这样硬件把页号与寄存器组中所有表项同时并行比较，立即输出与页号匹配的块号。这时无须访问内存，并且通过并行匹配直接完成地址变换，因此速度很快。,.,操作系统,内存储器,块号,页内位移,绝对地址,快速寄存器组,页号,页内位移,相对地址,CPU,快速寄存器组,(1),(2),快速寄存器价格昂贵，完全由它来组成页表的方案是不可取的。,.,页表/快表,考虑到大多数程序在一次运行时，倾向于在少数
36、页面中进行频繁访问（即程序的“局部性”原理），因此在实际系统中采用内存页表与快速寄存器组结合的解决方案，且只用极少几个快速寄存器来构成寄存器组，起名为：“相联寄存器”，或简称“快表”。,(1),快表中只存部分页表。把一个相对地址划分出数对：（页号，页内位移）后，系统先通过页号与快表中的所有表项进行并行比较。若发现了匹配的页，则将块号直接取出，不再通过页表。用该块号与页内位移拼接，形成所需要的绝对地址。,(2),作业长度不可能是页面尺寸的整数倍，平均说，分给作业的最后内存块会浪费掉一半。若内存中有n个作业，页面尺寸为p个字节，那么内存中就有n*p/2个字节被浪费掉。所以，页面尺寸要小。,当快表中
37、没有匹配的页号时，地址转换机构按普通访问页表的方式工作，获得所需的绝对地址；再把这个页号与块号的对应关系送入快表保存，以便下一次进行地址转换时能够命中。若快表里没有空表项，则要先删除快表中的一个表项，然后将新的页表表项替换进去。,页表控制寄存器,操作系统,内存储器,块号,页内位移,绝对地址,快表,页号,页内位移,相对地址,长度,起始地址,页表,(3),.,命中率,直接查快表就能实现内存访问的成功率为“命中率”。命中率越高，性能就越好。表中给出了平均命中率与相联寄存器个数的关系。从表中可以看出，设置快表，确实能够达到提高地址转换速度的目的。,相联寄存器个数,平均命中率,8,12,16,85%,9
38、3%,97%,.,3.,关于页面尺寸的讨论,.,页面尺寸小，用户作业相对地址空间的页面数就增加，页表就会加大。因此，从减少页表所需内存开销看，页面尺寸应该大一些为好。选择最佳页面尺寸，可能需在几个相互矛盾的因素间折中求得。,3.4.3 内存块的分配与回收,1.,对内存块的管理,.,.,存储分块表,单链表,操作系统,作业C第2页,作业B第0页,作业A第0页,空闲块,作业A第2页,空闲块,空闲块,作业B第1页,空闲块,空闲块,作业A第1页,作业C第3页,作业C第0页,作业C第1页,空闲块,内存储器,0,64K,空闲块链表起址,块号,状态,0,已分配,1,已分配,2,已分配,3,已分配,4,空闲,5
39、,已分配,6,空闲,7,空闲,8,已分配,9,空闲,10,空闲,11,已分配,12,已分配,13,已分配,14,已分配,15,空闲,空闲块总数：6,系统维持一张表格，表格表项与内存中的一块相对应， 记录该的块使用情况。只要表格中 “空闲块总数” 记录的数目大于请求的存储量，就可进行分配 ，并把分配出去的块的状态改为 “已分配” 。作业完成后归还存储块时，就把表中相应块的状态改为“空闲”。,单链表,存储分块表,把空闲块链接成一个单链表加以管理，系统必须设置一个空闲块链表的起始地址指针，以便进行存储分配时能够找到空闲的内存块。无论是进行空闲块的分配还是作业完成后归还存储块，都要调整空闲块间的链表指
40、针。,.,假定当前的内存储器使用情况，如图所示。,.,作业虽然不占据连续的存储区，但每次仍要求一次全部进入内存。因此，如果作业很大，其存储需求大于内存，那么还是存在小内存不能运行大作业的问题。,用户作业的相对地址空间按照块的尺寸划分成页。这种划分是在系统内部进行的，用户感觉不到，即对用户是“透明”的。,2.,分页式存储管理的特点,.,.,内存存储器事先被划分成相等尺寸的块，它是进行存储分配的单位。,.,.,相对地址空间中的页可以进入内存中的任何一个空闲块，并且分页式存储管理实行的是动态重定位，因此它打破了一个作业必须占据连续存储空间的限制，作业在不连续的存储区里，也能够得到正确的运行。,3.,
41、分页式存储管理的缺点,平均每一个作业要浪费半页大小的存储块。,.,位图,用二进制位与内存块的使用建立起关系，为“0”，表示对应块空闲；为“1”，表示对应块已分配。,1,1,1,1,0,1,0,0,1,0,0,1,1,1,1,0,空闲块总数：6,0,1,2,3,4,5,6,7,0,1,字节号,位号,位图,独立的地址空间有助于实施对过程和数据的共享，不必在每一个用户作业的地址空间里都必须有相关的备份。,每个程序段是一个独立的逻辑实体（比如一个过程、一个数组或一个堆栈），因此可以对它们进行不同类型的存储保护 。,每个程序段是一个独立的地址空间，它们可独自增长或减小而不用顾及别的程序段，不会影响到其他
42、程序段的地址空间。,所谓“分段式”存储管理，即要求用户将自己的作业程序以多个相互独立的称为“段”的地址空间提交给系统，每个段都是一个从“0”开始的一维地址空间，长度不一。操作系统按照段长为作业分配内存空间。,改变某程序段尺寸，就会影响其他无关程序段的起址；对某个程序段进行修改，会影响到其他相关部分，就可能要对所有的程序重新进行链接编辑。,3.5 分段式存储管理,3.5.1 分段及二维逻辑地址空间,1.,一维地址空间组织方式的缺点,.,不利于按照程序段的性质，实施存储保护和共享。,.,.,2.,分段式存储管理的含义,3.,分段式组织方式的优点,.,.,在编译过程中会建立很多表，其中主要有：供打印
43、程序清单的源程序文档；由变量名及其属性组成的符号表；由程序中所有的整型、实型常量组成的常量表；包含程序语法分析结果的语法分析树；内部过程调用时使用的堆栈。,通过编译程序在编译过程中建立的各种表，说明页式及段式存储管理中，作业程序地址空间组织形式的不同。,例 ：,解：,.,.,在分页式管理时，这5个表必须限定在一个一维的地址空间里，如图(a)所示。,使用,使用,使用,使用,使用,空闲,空闲,空闲,空闲,堆栈,语法分析树,常量表,源程序文档,符号表,(a),0KB,4KB,8KB,12KB,16KB,20KB,0KB,4KB,8KB,12KB,符号表,段0,0KB,源程序文档,常量表,段1,段3,
44、段4,0KB,4KB,8KB,12KB,16KB,语法分析树,0KB,4KB,8KB,12KB,堆栈,段2,(b),.,在分段管理时，是把这些表视为一个个相互独立的地址空间，比如：段0、段1等，它们组成了整个用户的地址空间，如图(b)所示。,系统为每个用户作业设置一个段表，用于记录各段在内存中的存放信息。逻辑空间中有多少段，段表里就有多少个表项。每个表项通常包括的信息有段号、段长、该段在内存的基址（即起始地址）等。,如果段号s大于段表长度，表示该地址越界出错；否则以此段号为索引查段表，得到该段在内存的基址。,硬件要提供一个段表基址寄存器。每当重新调度时，就把调度到的作业的段表起址及段表长度（即
45、段表中表项的个数）放入寄存器中，从而达到映射不同作业的目的。,.,在分段式存储管理时，要指示存储空间里的一个地址，必须提供两部分内容：段号和段内位移。即逻辑地址应该是二维的：段号，段内位移。,.,在图(a)所示的32位地址结构中，各用16个二进制位表示段号s和段内位移d，因此表示用户的逻辑地址空间最多可以有216个段，每段最大长度是64KB。,31,16 15,0,s,d,段号,段内位移,d,s,段号,段内位移,0,31,23 22,(a),(b),.,图(b) 所示的32位的地址结构中，由于用9个二进制位表示段号s，用23个二进制位表示段内位移d，因此表示允许用户的逻辑地址空间中最多可以有2
46、9个段，每段的最大长度是223=8192KB。,.,.,分段式存储管理时的地址转换步骤如下 ：,.,(1),从相对地址数对：段号s，段内位移d中提取出段号s，用来进行地址转换。,(2),(3),由段的基址和段内位移d拼装出所需的物理地址，实现对内存的访问。,3.5.2 段表及地址变换过程,段号(s),段内位移(d),相对地址,段表,段表基址寄存器,段号,长度,基址,基址,段内位移,物理地址,段s,d,内存,程序,分段地址转换机制,.,分段地址转换机制图示,例：,在分段式存储管理中，某作业的段表如下。有该作业的六个逻辑地址为： 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,
