让人看了流泪的句子：爱情使人忘记时间,时间也使人忘记爱情

第四章存储器管理

/i/89.html第四章存储器管理装入和链接连续分配方式基本分页存储管理方式基本分段存储管理方式虚拟存储器请求分页存储管理方式页面置换算法请求分段存储管理方式4.1程序的装入和链接编辑―――编译―――链接―――装入―――运行4.1.1程序的装入1、绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。对（1）而言，编程用符号地址。2、可重定位装入：静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程，例：图4－23.动态运行时装入在执行时才完成相对—绝对地址的转换，且有硬件的支持,能保证进程的可移动性。0100025005000LOAD1,2500LOAD1,250036536510000110001250015000作业地址空间内存空间图4-24.1.2程序的链接1、静态链接

程序运行之前，链接成完整的装入模块a．对相对地址的修改b．变换外部调用符号2、装入时动态链接

目标模块在装入内存时，边装入边链接a.便于修改和更新b.便于实现对目标模块的共享3、运行时动态链接程序执行需要时，才将某些目标模块进行链接模块ACALLB;RETURN模块BCALLC;RETURN模块CRETURN0L-10M-10N-1(a)目标模块模块AJSRL;RETURN模块BJSRL+M;RETURN模块CRETURN0L-1LL+M-1L+ML+M+N-1(b)装入模块4.2连续分配方式单一连续分配用于单用户，单任务中分区式分配固定式动态式动态重定位4.2.1单一连续分配单用户单任务系统区+用户区存贮保护一般不设置保护也可，因单任务。

用户程序位于RAM中的操作系统00xfff…用户程序位于ROM中的操作系统0用户程序位于RAM中的操作系统0位于ROM中的设备驱动程序大型机和小型计算机上，现在很少用掌上型计算机和嵌入式系统中早期的PC中，BIOS(basicinputoutputsystem)4.2.2固定分区特点：内存划为n个分区，可同时装入n个作业/任务。一、分区大小：相等:缺乏灵活性不相等：利用率更高。二、内存分配：将分区按大小排序，建立分区使用表，并将起始地址、大小、分配标识作记录检索分区使用表找能满足要求的尚未分配的分区放到能容纳作业的最小分区的队列中。作业C作业B作业A操作系统20K32K64K128K256K~~~~分配情况已分配1281284已分配64643已分配32322已分配20121状态起址（K）大小（K)分区号分区说明表输入队列的组织每个分区有独立输入队列：小分区的队列长，大分区的队列空，浪费只维护一个输入队列：一旦有分区空闲，就把该分区能容纳的作业中最接近队列前面的作业调入分区：小作业浪费大分区

对队列进行搜索，一旦有分区空闲，就取该分区所能容纳的最大的一个作业运行：对小作业不利

至少保留一个小分区，允许小作业运行，而不至于为小作业分配大分区规定一个作业至多允许被跳过的次数，之后就不能被跳过了

操作系统分区1分区2分区3分区40100k200k400k700k800k操作系统分区1分区2分区3分区44.2.3动态分区分配（比固定式分区有改善）根据进程需要，动态地为之分配内存空间一、数据结构1．空闲分区表2．空闲分区链4.2.3动态分区分配二、分配算法1．首次适应算法FF。要求：分区按低址――高址链接特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。2．循环首次适应算法。从1中上次找到的空闲分区的下一个开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。3．最佳适应算法分区按大小递增排序；分区释放时需插入到适当位置。4.2.3动态分区分配三、分区分配1．分配：请求分区u.size空闲分区m.size内存回收时的情况2．回收：（1）上邻空闲区：合并，改大小（2）下邻空闲区：合并，改大小，首址。（3）上、下邻空闲区：合并，改大小。（4）不邻接，则建立一新表项。4.2.4可重定位分区分配1.动态重定位的引入连续式分配中，总量大于作业大小的多个小分区不能容纳作业。紧凑通过作业移动将原来分散的小分区拼接成一个大分区。紧凑10KB用户程序3

必须对移动了的作业进行重定位。动态（因作业已经装入，随着对指令或数据的访问自动进行）2、动态重定位的实现0100250050002500100001000010100+1250015000作业J处理机一侧存储器一侧重定位寄存器相对地址主存动态分区分配算法流程图4.2.5对换1对换的引入将阻塞进程，暂时不用的程序，数据换出。将具备运行条件的进程换入。类型：整体对换：进程对换，解决内存紧张部分对换：页面对换/分段对换：提供虚存支持操作系统A操作系统AB操作系统ABC操作系统BC操作系统DC操作系统ACD内存分配情况随着进程进出而变化4.2.5对换2对换空间的管理外存对换区比文件区侧重于对换速度。因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。4.2.5对换3换出与换入1）换出a．选出被换出进程： 因素：优先级，驻留时间，进程状态b．换出过程：对于共享段：计数减1，是0则换出，否则不换修改PCB和MCB（或内存分配表）2）换入：a．选择换入进程：优先级，换出时间等。b．申请内存。c．换入4.3基本分页存储管理连续分配引起:碎片碎片问题的解决：紧凑方式,消耗系统开销。换一种思路：离散分配

允许将一个进程直接分散的装入到许多不相邻的分区中分页分段段页1).页面(page)进程的逻辑空间分成若干个大小相等的页面，编号内存空间分为同等大小的物理块(frame)，编号页面大小要适中：页太小：内存碎片小，页表可能很长，换入/出效率低页太大：页内碎片大。2的幂4.3.1页面与页表2).地址结构逻辑地址A页面大小L页号P和页内地址d:

P=INT[A/L]d=[A]modL如：L=1024B,A＝2170B.则P=2,d=12216 1211 0为每个进程建立一张页面映像表

进程逻辑地址内存中对应的块号函数，实现从页号到物理块号的地址映射存取控制字段读/写/执行3).页表用户程序页表页号块号内存

4.3.2地址变换机构实现：逻辑页号——物理块号的映射，借助页表完成。1、基本地址变换机构：

每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址和页表长度装入页表寄存器。越界保护将十进制的逻辑地址1023，4500转换为物理地址以十进制的逻辑地址1023为例，画出地址转换图例：已知某分页系统，内存容量为64KB，每页为1KB。对一个4页大的作业，其调入内存的页面对应的物理块号如下表：1）对上述逻辑地址，可先计算出它们的页号和页内地址，然后通过页表转换成对应的物理地址：1023：1023/1K=页号0，页内地址1023，物理快号2，则物理地址为：2*1K+1023=30714500：4500/1K=页号4，页内地址404，页号>页表长度，则越界中断401023210232467≤2.具有快表的地址变换机构不具快表，则需两次访问内存。（1）访问页表，得到物理地址（2）访问物理地址，得到所需内容降低1/2的性能，发现只有少量的页表表项被反复读取解决办法：设置一硬件设备，将虚拟地址直接映射到物理地址，速度提高。联想寄存器（快表）快表贵，不能太多。2.具有快表的地址变换机构

例：有一页式系统，其页表存放在主存中：①如果对主存的一次存取需要1.5μs,试问实现一次页面访问的存取时间是多少?②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间是多少?答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。■页表在主存的存取访问时间=1.5*2=3(μs)■增加快表后的存取访问时间=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)4.3.3两级和多级页表页表可能很大，将其离散存放在不同页块中。建一“外部页表”来管理这些离散页表块。相当于单级页表中的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。64位机器页表一般>3级，最外层页表常驻。4.4基本分段存储管理为了满足用户（程序员）在编程和使用上的要求即多重定位分区管理4.4.1引入

每个段可有其逻辑意义及功能，使得便于（1）方便编程；（2）分段共享；（3）分段保护；（4）动态链接；（5）动态增长；（如数据段的增长）4.4.2分段系统的基本原理分段地址空间被划分为若干个段，每段定义了一组逻辑信息。段号+段内地址。段表：Mapping:逻辑段物理内存区每段分配一个连续分区，各段离散在不同分区中地址变换机构：分页与分段区别：（1）页是信息的物理单位，段是逻辑单位（2）页长度固定，段长度不固定（由用户指定）（3）一维与二维(Main)=030K(X)=120K(D)=230K(S)=330K40K80K120K150K04.4.3信息共享段式系统易于共享例：图4-18及4-19分页与分段共享比较可重入码（纯代码）各个进程应保留局部数据区40个用户，程序中160K代码，40K数据,每页4K,则代码40个页面，数据区10个页面进程1进程2页表页表主存分页系统中共享editor分段系统中共享editor4.4.4段页式存储管理一、基本原理先将用户程序分成若干段，再把每个段分成若干页，并为每一段赋予一个段名段号(S)分页的优点：提高内存利用率分段的优点：方便和满足用户04K8K12K15K04K8K04K8K10K段内页号(P)页内地址(W)主程序段子程序段数据段

？各取所长4.4.4段页式存储管理二、地址变换段表寄存器：存放段表始址和段长段表寄存器段表页表主存利用段表和页表实现地址映射4.4.4段页式存储管理二、地址变换段表寄存器：存放段表始址和段长段号S与段长进行比较，越界？未越界，则用段表始址和段号S求段表项的位置，读出该段的页表始址用段内页号P求页表项的位置，读出物理块号b用块号b和页内地址W构成物理地址段表寄存器段表页表++>段超长段页式系统的地址变换机构4.4.4段页式存储管理三次访内存操作访问内存中的段表，得页表始址访问内存中的页表，得到物理地址访问物理地址，得到所需内容为提高速度，在地址变换机构中增设一高速缓冲寄存器（Cache）4.5虚拟存储器怎么办？

增加物理内存or逻辑上增加内存全部装入内存后才能运行？大作业：超出内存容量？作业多：不能全部容纳4.5.1虚拟存储器的引入1.常规存储管理的特征：一次性（指全部装入）不是所有的程序和数据都能用到，一次性装入是一种浪费驻留性（指驻留在内存不换出）I/O等待或仅运行一次的进程长期占据内存资源是一种浪费

问题：是否需要一次性将作业全部装入作业是否需要长期地驻留在内存4.5.1虚拟存储器的引入2.局部性原理程序在执行时将呈现出局部性规律：即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的存储空间也局限于某个区域。程序在执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。过程调用将会使程序的执行有一部分内存区域转至另一部分区域，在大多数情况下，过程调用的深度都不超过5。循环结构将执行多次程序中对数据结构的处理，往往都局限于小的范围内。局部性表现时间局部性：（循环）指令一旦执行，不久以后可能再次执行；数据结构被访问，则不久以后可能再次被访问空间局部性：（顺序）一旦程序访问了某个存储单元，不久之后，其附近的存储单元也被访问4.5.1虚拟存储器的引入3、虚拟存贮器基于局部性原理，一个作业在运行之前，没有必要全部装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。

定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。虚拟大小由内存容量和外存容量之和决定。4.5.2虚拟存储器的实现方法虚拟存储器的实现，毫无例外地都是建立在离散分配存储管理方式的基础上的。？？连续分配方式需要动态重定位4.5.2虚拟存储器的实现方式一、请求分页系统在分页系统的基础上，增加请求调页功能和页面置换功能。以页为单位进行置换需硬件：（1）请求分页的页表机制（2）缺页中断机构（3）地址变换机构需实现请求分页机制的软件（置换软件等）二、请求分段系统在分段系统的基础上，增加请求调段功能和分段置换功能。以段为单位进行置换需硬件：（1）请求分段的段表结构（2）缺段中断机构（3）地址变换机构需实现请求分段机制的软件（置换软件等）三、段页式虚拟存储器4.5.3虚拟存储器的特征虚拟存储器最基本的特征是离散性，在此基础上又形成了多次性及对换性的特征。其所表出来的最重要的特征是虚拟性。1、离散性离散性是指在内存分配是采用离散分配方式，这是其他几个特征的基础。没有离散性，也就不可能实现虚拟存储器。2、多次性多次性是指一个作业被分成多次地调入内存运行3、对换性对换性是指允许在作业的运行过程中换进、换出。换进、换出能有效地提高内存利用率4、虚拟性虚拟性是指能够从逻辑上扩允内存容量，使用户所看到的内存容量远大于实现内存容量。4.6请求分页存储管理在分页系统的基础上，增加请求调页功能和页面置换功能。以页为单位进行置换——长度固定实现简单，最常用需硬件：（1）请求分页的页表机制（2）缺页中断机构（3）地址变换机构一、页表机制页表项：二、缺页中断机构：

每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺之页调入内存。4.6.1请求分页中的硬件支持涉及6次缺页中断的指令6543214.6.1请求分页中的硬件支持三、地址变换机构比简单分页机制，增加了缺页中断处理和页面置换过程：先检索快表，如果找到该页，则修改页表项中的访问位、修改位等，再计算形成物理地址；如果未找到，则应再到内存中去查找页表，看其页表项中的状态位P，确定该页是否调入内存。如果：（1）该页已经调入内存：应将此页的页表项写入快表，当快表已满时，应先调出一个按某种算法所确定的页的页表项，然后再写入该页的页表项。（2）该页尚未调入内存，这时便应产生缺页中断，请求OS从外存中把该页调入内存。4.6.2内存分配策略和分配算法一、最小物理块数是指能保证进程正常运行所需的最小物理块数。单地址指令且采用直接寻址方式，最小物理块数为2允许间接寻址时，则至少要求有3个物理块。

指令长度≥2，源地址和目的地址涉及的区域跨页面，则至少要求6个

4.6.2内存分配策略和分配算法二、物理块的分配策略分配策略：固定和可变分配策略。置换策略：全局置换和局部置换。于是可组合出以下三种页面分配和置换策略。1．固定分配局部置换。缺点：难以确定固定分配的页数.(少：频繁缺页，置换率高多：浪费)2.可变分配全局置换预先分配好，缺页时从系统空闲队列里取出分配，用完时选一页调出置换3.可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。三、分配算法1．平均分配算法将系统中所有可供分配的物理块，平均分配给各个进程：没考虑进程大小2．按进程大小比例分配算法：系统中各进程页面数的总和为：

每个进程所能分配到的物理块数为bi：

3．考虑优先权分配算法把可供分配的物理块分成：一部分按比例地分给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。

4.6.3调页策略1.调入时机：预调：采用一种以预测为基础的预调页策略，预计在不久之后便会被访问的程序或数据所在的页面，预先调入内存

成功率50％请求调：当进程在运行中需要访问某部分程序的数据时，发现其所在的页面不在内存，需立即提出请求，由系统将其所需页面调入内存。较费系统开销各有优劣4.6.3调页策略2．从何处调页：对换区空间足够大：全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，将进程有关文件从文件区拷贝到对换区。对换区空间不够大：不会被修改的文件，直接从文件区调入；可能被修改的部分，换出时须先调到对换区，需要时从对换区调入。UNIX方式：与进程有关的文件放在文件区，未运行过的页面，从文件区调入；运行过的而又被换出的页面，放在对换区，下次调入时从对换区调入。3.页面调入过程所需页面未在内存时，缺页中断，查找页表得到该页外存物理块号，再找置换页（回写问题），完成调入，改页表目的：减少对换量，提高系统性能4.7.1最佳置换算法和先进先出算法一、最佳置换算法（理论上的）4.7页面置换算法缺页率：6/124.7页置换算法二、先进先出算法FIFO缺页率：9/124.7.2最近最久未用LRU置换将“最近的过去”，作为“最近的将来”。选择最近最久未使用的页面予以淘汰所要解决的问题有：一个进程在内存中的各个页面各有多久时间未被进程访问；如何快速地知道哪一页最近最久未使用的页面硬件支持：

1．位移寄存器：（定时右移） R=R