1、 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 第四章第四章 存储管理存储管理 概述概述 分区存储管理分区存储管理 段式存储管理段式存储管理 页式存储管理页式存储管理 段页式存储管理段页式存储管理 交换技术与覆盖技术交换技术与覆盖技术 虚拟存储虚拟存储 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院&存储器是计算机系统的重要管理资源。存储器是计算机系统的重要管理资源。&因为任何程序和数据以及各种控制用的数因为任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间，故存储据结构都必须占用一定的存储空间，故存储管理直接影响着系统的性能。管理直接影响着系统的性能。&
2、操作系统的任务之一是要尽可能地操作系统的任务之一是要尽可能地方便方便用用户使用存储器，以及提高主存储器的户使用存储器，以及提高主存储器的利用率利用率。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 存储分配问题。存储分配问题。重点是研究存储共享和各种分重点是研究存储共享和各种分配算法。配算法。地址再定位问题。地址再定位问题。研究各种地址变换机构，研究各种地址变换机构，以及静态和动态再定位方法。以及静态和动态再定位方法。存储共享问题。存储共享问题。研究多个进程如何共享内存研究多个进程如何共享内存。存储保护问题。存储保护问题。研究保护各类程序、研究保护各类程序、数据区数据区的方法。的方
3、法。存储扩充问题。存储扩充问题。主要研究虚拟存储器问题及其主要研究虚拟存储器问题及其各种调度算法。各种调度算法。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 寄存器寄存器 registerregister高速缓存高速缓存 cachecache主存储器主存储器磁盘缓存磁盘缓存磁盘磁盘可移动存储介质可移动存储介质操作系统协调各存储器的使用操作系统协调各存储器的使用速度与速度与CPUCPU取取指速度相匹配指速度相匹配 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 内存：内存：是由存储单元（字节或字）组成的一维是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。
4、用来连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程是程序中指令本身地址所指的、亦即程序计数器所指的存储器序计数器所指的存储器。内存可以分为：内存可以分为：x系统区：用于存放操作系统用于存放操作系统x用户区：用于装入并存放用户程序和用于装入并存放用户程序和数据。数据。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 存储分配和回收：存储分配和回收：分配和回收算法及相应数据结构。分配和回收算法及相应数据结构。存储共享和保护：存储共享和保护：代码和数据共享，地址空间访问权限（读、写、执行）代码和数据共
5、享，地址空间访问权限（读、写、执行）地址变换（地址再定位、地址映射）：地址变换（地址再定位、地址映射）：可执行文件生成中的链接技术可执行文件生成中的链接技术程序加载程序加载(装入装入)时的重定位技术时的重定位技术进程运行时硬件和软件的地址变换技术和机构进程运行时硬件和软件的地址变换技术和机构存储器扩充：存储器扩充：存储器的逻辑组织和物理组织；存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由应用程序控制：覆盖；由由OSOS控制：交换（整个进程空间），虚拟存储的请求调入控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）和预调入（部分进程空间）北北 京京 林林 业业 大大 学
6、学 信信 息息 学学 院院 1.1.内存空间的管理、分配与回收内存空间的管理、分配与回收（1 1）内存空间的管理、分配与回收）内存空间的管理、分配与回收F 记录内存的使用情况记录内存的使用情况 设置相应的内存分配表设置相应的内存分配表 （内存分配回收的依据）（内存分配回收的依据）F 内存空间划分问题？内存空间划分问题？静态或动态，等长或不等长静态或动态，等长或不等长 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 内存分配表内存分配表5位示图：位示图：用一位（用一位（bitbit）表示一个空闲页面表示一个空闲页面（0 0：空闲，：空闲，1 1：占用）：占用）5空闲页面表：空闲页面表
7、：包括首页面号和页面个数，连包括首页面号和页面个数，连续若干的页面作为一组登记在表中续若干的页面作为一组登记在表中5空闲块表：空闲块表：空闲块首址和空闲块长度，没有空闲块首址和空闲块长度，没有记录的区域即为进程所占用记录的区域即为进程所占用5空闲块链表：空闲块链表：将所有的空闲块链成一个链表将所有的空闲块链成一个链表0 0.1 11 10 0.第第0 0页第页第1 1页页 第第i i页页 第第n-1n-1页页 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 分配与回收分配与回收l 确定分配算法确定分配算法 l 实施内存分配实施内存分配l 回收内存回收内存 l 内存存储分配和回收的三
8、种方式：内存存储分配和回收的三种方式：直接指定方式、静态和动态分配方式直接指定方式、静态和动态分配方式连续性连续性 离散性离散性驻留性驻留性 交换性交换性一次性一次性 多次性多次性 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 2.2.存储共享与保护存储共享与保护内存共享内存共享：两个或多个进程共用内存中两个或多个进程共用内存中相同区域相同区域目的：目的：节省内存空间，提高内存利用率节省内存空间，提高内存利用率实现进程通信（数据共享）实现进程通信（数据共享）共享内容：共享内容：代码共享，要求代码为纯代码代码共享，要求代码为纯代码 数据共享数据共享 北北 京京 林林 业业 大大 学
9、学 信信 息息 学学 院院 存储保护存储保护 保护目的：保护目的：为多个程序共享内存提供保障，使在内为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区存中的各道程序，只能访问它自己的区域，避免各道程序间域，避免各道程序间相互干扰相互干扰，特别是，特别是当一道程序发生错误时，不致于影响其当一道程序发生错误时，不致于影响其他程序的运行。他程序的运行。通常由通常由硬件完成硬件完成保护功能，由保护功能，由软件辅助软件辅助实现。实现。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 2存储空间一般分为两个部分存储空间一般分为两个部分2系统区系统区2用户区用户区2保护系统程序区
10、不被用户侵犯（有意保护系统程序区不被用户侵犯（有意或无意的）或无意的）2不允许用户程序读写不属于自己地址不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他空间的数据（系统区地址空间，其他用户程序的地址空间）用户程序的地址空间）北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 保护过程保护过程-防止地址越界防止地址越界 每个进程都有自己每个进程都有自己独立的进程空间独立的进程空间，如果一个进，如果一个进程在运行时所产生的地址在其地址空间之外，则程在运行时所产生的地址在其地址空间之外，则发生发生地址越界地址越界。即当程序要访问某个内存单元时，。即当程序要访问某个内存单元时，
11、由硬件检查是否允许，如果允许则执行，否则产由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。生地址越界中断，由操作系统进行相应处理。一般由硬件提供一对寄存器：一般由硬件提供一对寄存器：基址寄存器基址寄存器：存放起始地址：存放起始地址 限长寄存器限长寄存器：存放长度：存放长度 （或（或 上界寄存器上界寄存器/下界寄存器）下界寄存器）北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 程序程序320042003200320010001000基址寄存器基址寄存器界限寄存器界限寄存器3200320042004200上界寄存器上界寄存器下界寄存器下界寄存器上界上界
12、=被访问地址被访问地址=下界下界基址基址=被访问地址被访问地址=基址基址+界限界限3200=3200=被访问地址被访问地址=4200=4200 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 保护过程保护过程-防止操作越权防止操作越权 对于允许多个进程共享的存储区域，每对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则程对共享区域的访问违反了权限规定，则发生操作越权，即读写保护。发生操作越权，即读写保护。共享存储区域的保护共享存储区域的保护 北北 京京 林林 业业 大大 学学 信信 息息 学
13、学 院院 3.3.地址变换地址变换(地址再定位地址再定位,地址映射地址映射)直接指定方式直接指定方式:程序员在编程序时或编译程序程序员在编程序时或编译程序对源程序进行编译时，所用的是实际存储地址。对源程序进行编译时，所用的是实际存储地址。名空间名空间程序程序逻辑空间逻辑空间逻辑地址（相对地址，虚地址）逻辑地址（相对地址，虚地址）存储空间存储空间物理地址（绝对地址，实地址）物理地址（绝对地址，实地址）地址映射地址映射 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 程序的名空间、地址空间及存储空间程序的名空间、地址空间及存储空间符号符号源程序源程序目标目标代码代码可执行可执行代码代码
14、汇编汇编编译编译连接连接地址重定位地址重定位名空间名空间地址空间地址空间存储空间存储空间:x=x+1x=x+1:R=XR=XR=R+1R=R+1X=RX=R:0 0:K K 100100:100+100+K K:R=XR=XR=R+1R=R+1X=RX=R:北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射用户的程序经过汇编或编用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。译后形成目标代码，目标代码通常采用相对地址的形式。其首地址为其首地址为0 0，其余指令中的地址都相对于首地址来编址。，其余指令中的地
15、址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。不能用逻辑地址在内存中读取信息。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 地址映射地址映射Load A data1Load A data1data1 3456data1 3456源程序源程序编译连接编译连接Load A 200Load A 200 3456 34560 0100100200200逻辑地址空间逻辑地址空间Load A 200 3456 。1200物理地址空间物理地址空间BA=1100 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 静态分配和静态再定位静态分配和静态再定位程序中列出各个需要重定位
16、的地址单元和相对地程序中列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，址值。当用户程序被装入内存时，一次性实现逻一次性实现逻辑地址到物理地址的转换，辑地址到物理地址的转换，以后不再转换（一般以后不再转换（一般在装入内存时由软件完成）。在装入内存时由软件完成）。即：装入时根据所定位的内存地址去修改每个重即：装入时根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。定位地址项，添加相应偏移量。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 地址再定位（地址转换）OS000065008000作业作业2 2作业作业2 2作业作业1 120000000150000
17、002800作业作业1 14800 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 动态分配和动态再定位OSOS可以将一个程序分散存放于不连续的内存空间，可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。可以移动程序，有利用实现共享。能够支持程序执行中产生的地址引用，如指针变能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。量（而不仅是生成可执行文件时的地址引用）。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 0 0100100200200300300.LOAD A 200LOAD A 20034563456逻辑
18、地址空间逻辑地址空间200200VRVR10001000BRBR110011001200120013001300物理地址空间物理地址空间34563456.LOAD A 200LOAD A 200.北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 4.4.虚拟存储器概念的引入虚拟存储器概念的引入 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 虚拟存储的基本原理 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 v单一连续分配单一连续分配v分区分配分区分配v覆盖和交换覆盖和交换 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 一、单一连续存储管理 北北
19、 京京 林林 业业 大大 学学 信信 息息 学学 院院 OSOS内存内存连续存储管理实例连续存储管理实例用户用户A A作业作业用户用户B B作业作业用户用户C C作业作业用户独占用户独占内存内存用户作业用户作业队列队列界限地址界限地址栅栏寄存器栅栏寄存器用户用户A A作业作业用户用户B B作业作业用户用户C C作业作业 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 二、分区存储管理 系统把内存用户区划分为若干系统把内存用户区划分为若干分区，分区大小可以相等，也可以不分区，分区大小可以相等，也可以不等。每个进程占据一个分区。等。每个进程占据一个分区。固定分区固定分区可变分区可变分区
20、再定位分区再定位分区多重分区多重分区分区方式分区方式 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 1.1.原理原理 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 内存紧缩内存紧缩(compaction)compaction)：将各个占用将各个占用分区向内存一端移动。使各个空闲分区分区向内存一端移动。使各个空闲分区聚集在另一端，然后将各个空闲分区合聚集在另一端，然后将各个空闲分区合并成为一个空闲分区。并成为一个空闲分区。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 2.2.固定分区固定分区(f
21、ixed partitioning)fixed partitioning)预先把可分配的主存储器空间分割成若干个预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以连续区域，称为一个分区。每个分区的大小可以相同也可以不同，但分区大小固定不变，每个分相同也可以不同，但分区大小固定不变，每个分区装一个且只能装一个作业。区装一个且只能装一个作业。存储分配：如果有一个空闲区存储分配：如果有一个空闲区,则分配给进程。则分配给进程。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 8 M8 M8 M8 M8 MOperating SystemOperating Sys
22、tem8 M12 M8 M8 M6 M4 M2 M固定分区固定分区(大小相同大小相同)固定分区固定分区(多种大小多种大小)北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 分区号分区号 起始地址起始地址长度长度状态状态进程名进程名(a)分区号12345容量8 KB32 KB32 KB120 KB520 KB位置312 KB320 KB352 KB384 KB504 KB状态在使用在使用在使用未用未用(b)操作系统504 KB384 KB352 KB320 KB312 KB0520 KB120 KB32 KB32 KB8 KB312 KB固定分区说明表固定分区说明表主存分配图主存分配图
23、 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 分区号分区号 分区容量分区容量 作业容量作业容量 剩余容量剩余容量 1 12 23 34 45 58 8KBKB32KB32KB32KB32KB120KB120KB520KB520KB1 1KBKB9KB9KB9KB9KB33KB33KB121KB121KB7 7KBKB23KB23KB23KB23KB87KB87KB399KB399KB合合 计计 712 712 KB KB 173 173 KB KB 539 539 KB KB 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 分区分区4分区分区3分区分区2分区分区1操
24、作系统操作系统多个输入队列多个输入队列单个输入队列单个输入队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统700K400K100K0 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 操作系统区用户分区1用户分区2用户分区3用户分区4用户分区5B(B BL)L)B+LYesYesNoNo00000000 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 OS 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 覆盖(overlay)北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 A20KB50KC30KF30KD20KE40KTotal:19
25、0KResident20KOverlay 050KOverlay 140KTotal:110K覆盖技术 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 交换(swapping)北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 ：增加并发运行的程序数目，并且给用户提：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构；供适当的响应时间；编写程序时不影响程序结构；对换入和换出的控制增加处理机开销；程对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。地址访问
26、的统计特性。与覆盖技术相比，交换技术不要求用户给出程序段与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在进程或作之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段。覆盖只能覆盖那些与覆盖段无关的程序段。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 3.3.可变分区分配可变分区分配l基本思想：内存不是预先划分好的。基本思想：内存不是预先划分好的。n在装入程序时在装入程序时按其初始要求分配按其初始要求分配。当作业装入时，根据作业的需求和
27、内存空间的使用情况当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间。分分区给该进程；否则令其等待主存空间。n或在其执行中通过系统调用进行或在其执行中通过系统调用进行分配或改变分区大小分配或改变分区大小。内存管理：内存管理：设置内存空闲块表设置内存空闲块表记录了空闲区起记录了空闲区起始地址和长度始地址和长度内存分配：内存分配：动态分配动态分配内存回收：内存回收：当某一块归还后，前后空间合并，修改当某一块归还后，前后空间合并，修改内存空闲块表内存空闲块表 北北 京京
28、林林 业业 大大 学学 信信 息息 学学 院院 作业作业6 6256 256 KBKB作业作业5 5128 128 KBKB作业作业4 424 24 KBKB(a)a)作业作业3(120 3(120 KB)KB)作业作业2(32 2(32 K K B)B)作业作业1(8 1(8 KB)KB)OSOS1024 1024 KBKB504 504 KBKB384 384 KBKB352 352 KBKB320 320 KBKB312 312 KBKB0 0(b)b)作业作业3(120 3(120 KB)KB)作业作业2(32 2(32 KB)KB)作业作业1(8 1(8 KB)KB)OSOS1024
29、 1024 KBKB504 504 KBKB384 384 KBKB352 352 KBKB320 320 KBKB312 312 KBKB0 0作业作业6(256 6(256 KB)KB)作业作业5(128 5(128 KB)KB)作业作业4(24 4(24 KB)KB)888 888 KBKB632 632 KBKB376 376 KBKB(c)c)作业作业1(8 1(8 KB)KB)OSOS0 0作业作业6(256 6(256 KB)KB)作业作业5(128 5(128 KB)KB)作业作业4(24 4(24 KB)KB)1624 1624 KBKB504 504 KBKB352 352
30、 KBKB320 320 KBKB312 312 KBKB888 888 KBKB632 632 KBKB376 376 KBKB 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 分区号分区号分区容分区容量量分区位置分区位置状态状态1 18 8kBkB312312KBKB已分配已分配2 23232kBkB320320KBKB已分配已分配3 3空空4 4120120kBkB384384KBKB已分配已分配5 5空空分区号分区号分区容量分区容量分区分区位置位置状态状态1 13232KBKB352352KBKB 可用可用2 2520520KBKB504504KBKB 可用可用 北北 京京
31、 林林 业业 大大 学学 信信 息息 学学 院院 申请分配一个申请分配一个x xKBKB 大小的分区大小的分区置空白区号置空白区号 f f=1=1f f 大于最后大于最后一个空白区号？一个空白区号？空白区可用？空白区可用？保存空白区的起始地址保存空白区的起始地址空白区空白区 f f的大小的大小x xKBKB空白区的空白区的状态状态=空项空项修改空白区的大小修改空白区的大小和起始地址和起始地址在已分配表中找一个状在已分配表中找一个状态态=空项的分区号空项的分区号 P P置分区置分区P P的大小为的大小为 x xKBKB置分区起始地址置分区起始地址置分区状态为已分配置分区状态为已分配返回一个返回一
32、个分区号分区号此次无法分配此次无法分配f+1 f f+1 f Y YY YN NN N =北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 I I首次适应算法首次适应算法(First Fit:FF)First Fit:FF)将自由区按存贮顺序链成一个队列，将自由区按存贮顺序链成一个队列，用一指针指向队首，分配时将找到的第用一指针指向队首，分配时将找到的第一个满足要求的空白区分配给它。一个满足要求的空白区分配
33、给它。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 首次适应算法实例：指针指针1010k k6060k k9090k k2020k k要求：有四块自由区域，为一程序分配要求：有四块自由区域，为一程序分配1919k k内存内存。指针指针1010k k6060k k9090k k2020k k4141k kFFFF特点：特点：简单，查找次数少，简单，查找次数少，在高地址区中在高地址区中保持较大自由区域。保持较大自由区域。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 II II循环首次适应循环首次适应(Next fit:NF)Next fit:NF)1 12 2指针移动指
34、针移动将自由区组成环状队列，按循环顺序寻找自由区。将自由区组成环状队列，按循环顺序寻找自由区。(与与FFFF区别，头指针从低地址开始向高地址循环移动区别，头指针从低地址开始向高地址循环移动)NFNF特点：特点：使得小的自由区均匀分布，易于使得小的自由区均匀分布，易于与其它自由区合并。与其它自由区合并。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 IIIIII最佳适应算法最佳适应算法(Best fit:BF)Best fit:BF)将自由区按大小排成队列，寻找时总是以最将自由区按大小排成队列，寻找时总是以最小的自由区开始，找到第一个合适的分区。小的自由区开始，找到第一个合适的分区。
35、BFBF特点：特点：最佳地利用分区，查找效率低，碎最佳地利用分区，查找效率低，碎片多而小。片多而小。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 最佳适应算法实例指针指针1010k k2020k k6060k k9090k k1 1k k要求：有四块自由区，为一程序分配要求：有四块自由区，为一程序分配1919k k内存内存。指针指针1010k k6060k k9090k k2020k k 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 IV最坏适应算法(Worst fit:WF)将自由区排序将自由区排序(按从大到小按从大到小)，并寻找最大自由，并寻找最大自由区域进行分
36、配。区域进行分配。实例：实例：BFBF特点：特点：不会出现小的自由区。不会出现小的自由区。指针指针9090k k6060k k2020k k1010k k指针指针9090k k6060k k2020k k1010k k7171k k指针指针1010k k6060k k9090k k2020k k 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 算法比较实验实例：设系统自由区链表为实例：设系统自由区链表为指针指针7 7k k3 3k k1010k k8 8k k2020k k5 5k ka ab bc cd de ef f要求：要求：用户先后申请用户先后申请7.57.5k k，4k4
37、k内存空间，内存空间，试用试用四种算法求出分配块。四种算法求出分配块。北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 FF:c,a3k3k2.5k8k20k5kabcdefNF:c,d7k3k2.5k4k20k5kabcdef8.5k10k8k7k5k3kecdafbWF:e,e 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 3 3k k5 5k k7 7k k0.50.5k k1010k k2020k kb bf fa ad dc ce e3 3k k5 5k k7 7k k0.50.5k k1010k k2020k kb bf fa ad dc ce e再排序从小
38、到大再排序从小到大分配块为分配块为d,f d,f 3 3k k5 5k k7 7k k8 8k k1010k k2020k kb bf fa ad dc ce eBF:BF:首先从小到大排序首先从小到大排序0.50.5k k3 3k k1 1k k7 7k k1010k k2020k kd db bf fa ac ce e 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 作业7(256 KB)(a)(b)(c)作业6(256 KB)作业5(128 KB)作业4(24 KB)作业1(8 KB)OS作业7(256 KB)作业6(256 KB)作业5(128 KB)作业4(24 KB)作
39、业1(8 KB)OS01024 KB504 KB352 KB320 KB312 KB888 KB652 KB376 KB作业6(256 KB)作业5(128 KB)作业4(24 KB)作业1(8 KB)OS 4.4.可再定位式分区分配可再定位式分区分配 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 利用浮动寄存器进行利用浮动寄存器进行地址变换地址变换L 1,352 K+980001557100352 KB352 KB+50352 KB+9800376 KB352 KB+9800-32 KB+L 1,352 KB+980001557100320KB320 KB+50320 KB+9
40、800344 KB计算地址地址变换有效地址浮动寄存器地址变换地址变换 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 可再定位式分区分配算法流程可再定位式分区分配算法流程 请求分配请求分配一个大小为一个大小为xKB的分区的分区有大于有大于xKB的空白区的空白区吗？吗？空白区的总空白区的总和和 xKB？执行靠拢操作执行靠拢操作并修改状态表并修改状态表分配一个分区并分配一个分区并修改状态表修改状态表返回一个返回一个分区号分区号此时无此时无法分配法分配YYNN分区分配分区分配 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 可重定位分区的优缺点 北北 京京 林林 业业 大大
41、学学 信信 息息 学学 院院 5.5.多重分区多重分区 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 多重分区分配 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 主要优点：主要优点：分区分配方案的评价分区分配方案的评价 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 (1)(1)主存仍不能充分利用，除了可再定位式分区法外，都存主存仍不能充分利用，除了可再定位式分区法外，都存在着严重的碎片问题。另外，即使不把存储器分碎，整个空在着严重的碎片问题。另外，即使不把存储器分碎，整个空白区也可能因容纳不下一个作业而造成浪费。白区也可能因容纳不下一个作业而造成浪费。
42、(2)(2)不能实现对主存的扩充。不能实现对主存的扩充。因此，因此，作业的大小受到主存作业的大小受到主存可用空间的限制。可用空间的限制。(3)(3)和单一连续分配一样，要求一个作业在执行之前必须全和单一连续分配一样，要求一个作业在执行之前必须全部装入主存，因此在主存中可能包含从未使用过的信息。部装入主存，因此在主存中可能包含从未使用过的信息。(4)(4)采用靠拢方法，虽然能解决碎片问题，但有时需移动大采用靠拢方法，虽然能解决碎片问题，但有时需移动大量信息，从而损失了处理机时间。量信息，从而损失了处理机时间。(5)(5)除多重分区外，几个共行作业之间不能共享存入主存的除多重分区外，几个共行作业之
43、间不能共享存入主存的单一信息副本单一信息副本(如公用子程序、数据段等如公用子程序、数据段等)。主要缺点：主要缺点：北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 一、基本原理一、基本原理把用户程序按逻辑页划分成大小相等的部分，把用户程序按逻辑页划分成大小相等的部分，称为页。称为页。从从0 0开始编制页号，页内地址是相对于开始编制页号，页内地址是相对于0 0编址。编址。页号页号 页内地址页内地址4.3 分页存储管理逻辑地址逻辑地址 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 逻辑地址 用户程序的划分是由系统自动完成的，对用用户程序的划分是由系统自动完成的，对用户是透明
44、的。一般，一页的大小为户是透明的。一般，一页的大小为2 2的整数次的整数次幂，因此，地址的高位部分为页号，低位部分幂，因此，地址的高位部分为页号，低位部分为页内地址。为页内地址。0 0111112122323页号页号P P页内位移量页内位移量W W编号编号0409604096相对地址相对地址0409604096 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 内存空间 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 .01234560123456作业的作业的地址空间地址空间页框页框（物理块）（物理块）页页号号页页表表主存中页框主存中页框（物理块）（物理块）.北北 京京
45、林林 业业 大大 学学 信信 息息 学学 院院 页面变换表页面变换表 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 作业2(0页)操作系统作业2(1页)作业3(0页)作业1(0页)作业1(1页)作业2(2页)051601224708作业1作业2作业31 KB2 KB001 KB2 KB03 KB1 KB0逻辑地址空间页面变换表物理地址空间页号 块号1 KB2 KB3 KB4 KB5 KB6 KB7 KB8 KB9 KB10 KB 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 二、地址变换机构 页号页号P P位移量位移量W W3112 110MODLAdLAINTP
46、北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 使用位图表管理内存固定内存空间中，固定内存空间中，页面的大小决定页面的大小决定了位图的大小，了位图的大小，单位页面越大，单位页面越大，位图越小。位图越小。0000000011111111110010011100111111111 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 使用链表的内存管理空闲页面链空闲页面链空闲页面链头寄存器空闲页面链头寄存器空闲页面总数空闲页面总数n n指针指向第一个空闲页面页号指针指向第一个空闲页面页号 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 计算一个作业所需要的总块数计算一
47、个作业所需要的总块数N N查位示图，看看是否还有查位示图，看看是否还有N N个空闲块个空闲块如果有足够的空闲块，则页表长度设如果有足够的空闲块，则页表长度设为为N N，可填入可填入PCBPCB中；申请页表区，把中；申请页表区，把页表始址填入页表始址填入PCBPCB依次分配依次分配N N个空闲块，将块号和页号填个空闲块，将块号和页号填入页表入页表修改位示图修改位示图内存的分配与回收内存的分配与回收 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 如果把页表放在主存中，无疑会影响系统的性能。这如果把页表放在主存中，无疑会影响系统的性能。这是因为每次访问主存，首先必须访问页表，读出表目，
48、是因为每次访问主存，首先必须访问页表，读出表目，之后根据形成的实际地址再访问主存，这样使访问主存之后根据形成的实际地址再访问主存，这样使访问主存的次数加倍，因而使总的处理速度明显下降。的次数加倍，因而使总的处理速度明显下降。为了解决这个问题人们采用一组硬件寄存器，存放当为了解决这个问题人们采用一组硬件寄存器，存放当前访问过的页的表目，每次访问主存时，首先查找快表，前访问过的页的表目，每次访问主存时，首先查找快表，若找到所需的表目，则快速形成物理地址。否则从页表若找到所需的表目，则快速形成物理地址。否则从页表中查找后形成物理地址，同时把页描述子写入快表。如中查找后形成物理地址，同时把页描述子写入
49、快表。如果设计得当，快表的命中率可以很高。果设计得当，快表的命中率可以很高。快表快表 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 硬件支持硬件支持系统设置一对寄存器系统设置一对寄存器 页表始址寄存器页表始址寄存器 用于保存正在运行进程的页表的始址用于保存正在运行进程的页表的始址 页表长度寄存器页表长度寄存器 用于保存正在运行进程的页表的长度用于保存正在运行进程的页表的长度相联存储器相联存储器快表快表 相联（联想）存储器（相联（联想）存储器（associative memoryassociative memory）TLB TLB（Translation Translation l
50、ookasidelookaside buffers buffers）北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 相联存储器相联存储器快表快表 用途：用途：保存正在运行进程的页表的子集保存正在运行进程的页表的子集（部分表项）（部分表项）特点：特点：按内容并行查找按内容并行查找快表表项：快表表项：页号；内存块号；标识位；淘汰位页号；内存块号；标识位；淘汰位 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 PW有效地址BW输出寄存器输入寄存器物理地址页号 P页号 B利用快表加速查询利用快表加速查询 北北 京京 林林 业业 大大 学学 信信 息息 学学 院院 p页表页表地址
