计算机操作系统-存储器管理.ppt

第四章 存储器管理,存储器是计算机系统的重要组成部分之一。对存储器加以有效管理，不仅直接影响存储器的利用率，而且对系统性能有重大影响。内存管理的主要对象是内存，对外存的管理在文件管理中。,第四章 存储器管理,存储器的层次结构,多级存储器结构,存储器的层次结构,1、主存储器 CPU只能从主存储器中取得指令和数据。但运行速度远低于CPU执行指令的速度。2、寄存器 访问速度最快，但价格昂贵。3、高速缓存 容量远大于寄存器，但比主存小两三个数量级。4、磁盘缓存 利用主存中的存储空间。,第四章 存储器管理,4.1 程序的装入和链接4.2 连续分配方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器的基本概念4.6 请求分页存储管理方式4.7 页面置换算法4.8 请求分段存储管理方式,本章重点难点,1、掌握地址变换机构及实现方法。2、掌握虚拟存储器概念和虚拟存储技术。3、掌握页面置换算法。,4.1 程序的装入和链接,在多道程序环境下，要使程序运行，必须为之先建立进程。创建进程的第一件事是将程序和数据装入内存。将用户源程序变为可在内存中执行的程序的步骤：1、编译：由编译程序将用户源代码编译成若干个目标模块 2、链接：由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块 3、装入：由装入程序将装入模块装入内存,4.1 程序的装入和链接,4.1 程序的装入和链接,4.1.1 程序的装入将一个装入模块装入内存时，有三种方式：绝对装入方式可重定位装入方式动态运行时装入方式,4.1 程序的装入和链接,1.绝对装入方式 在编译时，如果知道程序驻留在内存的什么位置，那么编译程序将产生绝对地址的目标代码。装入模块装入内存后，程序中的逻辑地址与实际内存地址完全相同，不须对程序和数据的地址进行修改。程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员赋予。只适合于单道程序环境,4.1.1 程序的装入,4.1 程序的装入和链接,2.可重定位装入方式 在多道程序环境下，目标模块的起始地址通常从0开始，程序中的其他地址都是相对于起始地址计算的。因此应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。,注意：在采用可重定位装入方式将装入模块装入内存后，会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。,4.1 程序的装入和链接,在装入时对目标程序中指令和数据的修改过程称为重定位。地址变换在装入时一次完成，以后不再改变，称为静态重定位。,4.1 程序的装入和链接,3.动态运行时装入方式 动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，应设置一个重定位寄存器。,4.1 程序的装入和链接,4.1.2 程序的链接 程序经过编译后得到一组目标模块，再利用链接程序将目标模块链接，形成装入模块。根据链接时间的不同，把链接分成三种：1、静态链接：在程序运行前，将目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开。2、装入时动态链接：指将用户源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的链接方式。3、运行时动态链接：指对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行链接。,1.静态链接方式：事先进行链接，以后不再拆开,4.1.2 程序的链接,将目标模块装配成装入模块时需解决的两个问题：(1)对相对地址进行修改(2)变换外部调用符号,4.1.2 程序的链接,2.装入时动态链接：用户源程序经编译后所得的目标模块，是在装入内存时，边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要修改目标模块中的相对地址。优点：便于修改和更新 便于实现对目标模块的共享,3.运行时动态链接：运行时动态链接是将对某些模块的链接推迟到执行时才执行，即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡执行过程中未被用到的目标模块，不会调入内存和链接，这样不仅加快程序的装入过程，而且节省大量的内存空间。,4.1.2 程序的链接,第四章 存储器管理,4.1 程序的装入和链接4.2 连续分配方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器的基本概念4.6 请求分页存储管理方式4.7 页面置换算法4.8 请求分段存储管理方式,4.2 连续分配方式,内容及要求四种连续分配方式；理解和掌握动态分区分配及动态重定位分区分配方式；掌握动态分区分配算法,4.2 连续分配方式,连续分配方式，是指为一个用户程序分配一个连续的内存空间。,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,4.2.1 单一连续分配方式,把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常放在内存低址部分，用户区是指除系统区以外的全部内存空间，提供给用户使用。但只能用于单用户、单任务的操作系统中。,4.2 连续分配方式,连续分配方式，是指为一个用户程序分配一个连续的内存空间。,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,4.2.2 固定分区分配,1.原理 将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，便可以有多道作业并发执行。当有一空闲分区时，便可以再从外存的后备作业队列中，选择一个适当大小的作业装入该分区，当该作业结束时，可再从后备作业队列中找出另一作业调入该分区。,2.划分分区的方法(1)分区大小相等：所有的内存分区大小相等，缺乏灵活性(2)分区大小不等：把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。,3.实现为便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。,4.2.2 固定分区分配,4.2 连续分配方式,连续分配方式，是指为一个用户程序分配一个连续的内存空间。,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,4.2.3 动态分区分配,1.原理 动态分区分配是根据进程的实际需要，动态地为之分配内存空间。作业装入内存时，把可用内存分出一个连续区域给作业，且分区的大小正好适合作业大小的需要。分区的大小和个数依装入作业的需要而定2.实现在实现过程中涉及如下问题：,分区分配中的数据结构分区分配算法分区分配及回收操作,1）分区分配中的数据结构（1）空闲分区表示 空闲分区表：记录每个空闲分区的情况。每个空闲分区占一个表目。空闲分区链：在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针,将所有的空闲分区链接成一个双向链。,2.实现,4.2.3 动态分区分配,序号 大小 起址 状态 1 48k 116k 可用 2 252k 260k 可用（a）空闲分区表,作业号 大小 起址 1 32k 20k 2 64k 52k 4 96K 164K（C）已占分区表,（2）已占分区说明表 结构：作业号；起始地址；大小,2）分区分配算法 为把一个新作业装入内存，需按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。常用的分配算法：(1)首次适应算法FF(2)循环首次适应算法(3)最佳适应算法,4.2.3 动态分区分配,(1)首次适应算法FF FF算法要求空闲分区表以地址递增的次序排列。在分配内存时，从表首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表中。若从头到尾不存在满足要求的分区，则分配失败。优点：优先利用内存低址部分的内存空间,保留了高址部分的大空闲区。缺点：低址部分不断划分，产生小碎片（内存碎块、内存碎片、零头）；每次查找从低址部分开始，增加了查找的开销,4.2.3 动态分区分配,(2)循环首次适应算法 在分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现算法，需要：设置一起始查寻指针采用循环查找方式优点：使内存空闲分区分布均匀，减少查找的开销缺点：缺乏大的空闲分区,4.2.3 动态分区分配,(3)最佳适应算法 所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。缺点：产生许多难以利用的小空闲区,4.2.3 动态分区分配,3）分区分配及回收操作分配内存 利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小表示为m.size，若m.size-u.sizesize(规定的不再切割的分区大小)，将整个分区分配给请求者，否则从分区中按请求的大小划出一块内存空间分配出去，余下部分留在空闲链中，将分配区首址返回给调用者。,4.2.3 动态分区分配,4.2.3 动态分区分配,回收内存 当进程运行完毕释放内存时，系统根据回收区首址，在空闲分区链(表)中找到相应插入点，可能有四种情况：(1)回收区与插入点的前一个分区F1邻接：(2)回收区与插入点的后一个分区F2邻接：,(3)回收区与插入点的前后两个分区F1、F2邻接：(4)回收区既不与F1邻接，又不与F2邻接：,4.2 连续分配方式,连续分配方式，是指为一个用户程序分配一个连续的内存空间。,单一连续分配,固定分区分配,动态分区分配,可重定位分区分配,4.2.4 可重定位分区分配,1.动态重定位的引入 在连续分配方式中，必须把系统或用户程序装入一连续的内存空间。如果在统统中只有若干个小分区，即使它们的容量总和大于要装入的程序，但由于这些分区不相邻，所以无法将程序装入内存。,解决方法：将内存中的所有作业进行移动，使它们全部邻接，这样可把原来分散的小分区拼接成大分区，这种方法称为“拼接”或“紧凑”。缺点：用户程序在内存中的地址发生变化，必须重定位。,2.动态重定位的实现在动态运行时装入的方式，将相对地址转换为物理地址的工作在程序指令真正要执行时才进行。地址转换需要重定位寄存器的支持。程序执行时访问的内存地址是相对地址与重定位寄存器中的地址相加而成。,地址变换过程是在程序执行过程期间，随着对每条指令的访问自动进行的，称为动态重定位。,4.2.4 可重定位分区分配,3.动态重定位分区分配算法动态重定位分区分配算法与动态分区分配算法基本相同，差别在于增加了紧凑的功能。,4.2.4 可重定位分区分配,4.2 连续分配方式,4.2.1 单一连续分配4.2.2 固定分区分配4.2.3 动态分区分配4.2.4 可重定位分区分配4.2.5 对换,1.对换的引入多道程序环境下存在的问题：阻塞进程占据大量内存空间许多作业在外存而不能进入内存运行,4.2.4 对换,对换：把内存中暂时不能运行的进程或者暂时不用的程序和数据，调到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程和进程所需要的程序和数据，调入内存。,对换的分类：整体对换(或进程对换)：以整个进程为单位 页面对换或分段对换：以页或段为单位实现进程对换，系统必须具备的功能：对换空间的管理 进程的换出 进程的换入,2.对换空间的管理,在系统中设置相应的数据结构以记录外存的使用情况对换空间的分配与回收，与动态分区方式时的内存分配与回收雷同。,4.2.4 对换,一般从磁盘上划出一块空间作为对换区使用,3.进程的换出与换入进程的换出 换出过程：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。进程的换入 系统应定时查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将换出进程最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。,4.2.4 对换,4.2.4 对换,第四章 存储器管理,4.1 程序的装入和链接4.2 连续分配方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器的基本概念4.6 请求分页存储管理方式4.7 页面置换算法4.8 请求分段存储管理方式,4.3 基本分页存储管理方式,连续分配方式会形成“碎片”，虽然可以通过“紧凑”解决，但开销大。如果允许将一个进程直接分散地装入许多不相邻的分区中，则无需“紧凑”，由此产生离散分配方式。分类：分页存储管理方式：离散分配的基本单位是页 分段存储管理方式：离散分配的基本单位是段 基本的分页存储管理方式(或纯分页存储管理方式)：不具备页面对换功能，不具有支持实现虚拟存储器的功能，要求把每个作业全部装入内存后方能运行。,4.3 基本分页存储管理方式,4.3.1 页面与页表4.3.2 地址变换机构4.3.3 两级和多级页表,4.3.1 页面与页表,1.页面分页式存储管理的原理 分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片称为页面或页，并为各页加以编号，从0开始。同时把内存空间分成与页面相同大小的若干个存储块，称为块或页框。在为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻的物理块中。进程的最后一页经常装不满一块而形成“页内碎片”。,基本分页式存储管理（简单页式存储管理）的原理 系统若能满足一个作业所要求的全部块数，此作业才能被装入内存，否则不为它分配任何内存。请求分页式存储管理的原理 运行一个作业时，并不要求把该作业的全部程序和数据都装入内存，可以只把目前要执行的几页调入内存的空闲块中，其余的仍保存在外存中，以后根据作业运行的需要再调入内存。,页面大小的选择由机器的地址结构所决定的，即由硬件所决定某一种机器只能采用一种大小的页面。小：内碎片小，内存利用率高，但页面数目多，使页表过长，占大量内存，管理开销大大：页表短，管理开销小，内碎片大，内存利用率低,4.3.1 页面与页表,页面大小 页面大小应选地适中，应是2的幂，通常是512B8KB,2.地址结构,地址长度32位:011位为位移量(页内地址)，即每页的大小为4KB12 31位为页号，地址空间最多允许有1M页对于某特定的机器，其地址结构是一定的。,4.3.1 页面与页表,若给定一个逻辑地址空间中的地址为A，页面大小为L，则 页号P=INTA/L 页内地址d=A MOD L例如：系统页面大小为1KB，设A=2170D，则 P=2，d=122,数值的表示：二进制,十进制,八进制,十六进制,分别在其后加上B,D,Q,H.(Binary,Decimal,Q(Octal),Hexadecimal),4.3.1 页面与页表,3.基本分页式存储管理（简单页式存储管理）的实现 进程的每一页离散地存储在内存的任一存储块中，为方便查找，系统为每一进程建立一张页面映像表，简称页表。页表实现了从页号到物理块号的地址映射。,4.3.1 页面与页表,4.3.2 地址变换机构,为了能将用户地址空间的逻辑地址变换为内存空间的物理地址，在系统中必须设置地址变换机构。地址变换机构实现从逻辑地址到物理地址的转换，其任务是借助于页表，将逻辑地址中的页号转换为内存中的物理块号。,1.基本的地址变换机构 页表的功能可以由一组专门的寄存器来实现，一个页表项用一个寄存器。但寄存器成本高，系统页表可能很大，所以页表大多常驻内存。在系统中只设置一个页表寄存器PTR，在其中存放页表在内存中的始址和页表的长度。平时，进程没有执行时，页表的始址和页表长度存放在进程的PCB中，当调度到进程时，才将这两个数据装入到页表寄存器中。,4.3.2 地址变换机构,2.具有快表的地址变换机构由于页表是存放在内存中的，CPU在每存取一个数据时，需要两次访问内存：第一次：访问页表，找到指定页的物理块号，将块号与页内偏移量拼接形成物理地址。第二次：从第一次所得地址中获得所需数据，或向此地址中写入数据。存储器利用率提高，处理器处理速度降低。解决方法：在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲寄存器，称为“联想存储器”或“快表”。,4.3.2 地址变换机构,基本分页式存储管理之例,作业表,4.3.3 两级和多级页表,现代计算机系统都支持非常大的逻辑地址空间(232264)，页表就非常大，需占用较大的地址空间。例如：一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则每个进程页表的页表项可达1M个，若每个页表项占用一个字节，则每个进程的页表就要占据1MB的内存空间，而且要求连续存放。解决方法：采用离散方式存储 只将当前所需页表项调入内存,1.两级页表 将页表分页，并离散地将各个页面分别存放在不同的物理块中，同时为离散分配的页表再建立一张页表，称为外层页表，其每个页表项记录了页表页面的物理块号。,例如：32位逻辑地址空间，页面大小为4KB(即12位)，若采用一级页表机构，应有20位页号，即页表项应有1M个；在采用两级页表机构时，再对页表进行分页，使每页包含210(即1024)个页表项，最多允许有210个页表分页。即,4.3.3 两级和多级页表,为实现方便，在地址变换机构中需设一外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，再利用p2作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该块号和页内地址d即可构成访问的内存物理地址。,4.3.3 两级和多级页表,1.两级页表,上述方法用离散分配空间解决了大页表无需大片存储空间的问题，但并未减少页表所占的内存空间。解决方法:是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。在采用两级页表结构的情况下，对正在运行的进程，必须将其外层页表调入内存，而对页表则只需调入一页或几页。这就需要在外层页表项中增设一个状态位S，用于表示该页表是否调入内存。,4.3.3 两级和多级页表,1.两级页表,2.多级页表 两级页表对32位机器适用，64位呢？页面大小为4KB即212B，还剩52位，按物理块大小212位来划分页表，则剩余40位用于外层页号，此时外层页表可能有1024G个页表项，要占用4096GB的连续存储空间 解决方法：采用多级页表，将外层页表再进行分页。,关于分页的地址变换计算-虚地址结构,例1.设页面大小为1KB，将逻辑地址3BADH划分为页号和页内偏移量两部分。用16进制表示。,例2.设页面大小为2KB，将逻辑地址3BADH划分为页号和页内偏移量两部分。用16进制表示。,关于分页的地址变换计算-虚地址结构,关于分页的地址变换计算-虚地址结构,例3.设页面大小为2KB，作业的页表如下图。求逻辑地址3BADH的物理地址。用16进制表示。,关于分页的地址变换计算-页式地址映射,关于分页的地址变换计算-页式地址映射,例4：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。虚地址0AFEH0000 1010 1111 1110P1 d010 1111 1110MR0100 1010 1111 1110 4AFEH,虚地址1ADDH0001 1010 1101 1101P3 d010 1101 1101MR0010 1010 1101 11012ADDH,关于分页的地址变换计算-页式地址映射,虚地址 3412P3412 2048 1d 3412 mod 2048 1364MR=9*2048+1364=19796虚地址3412的内存地址是：19796,例5：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。,虚地址 7145P7145 2048 3d7145 mod 2048 1001MR=5*2048+1001=11241虚地址7145的内存地址是：11241,第四章 存储器管理,4.1 程序的装入和链接4.2 连续分配方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器的基本概念4.6 请求分页存储管理方式4.7 页面置换算法4.8 请求分段存储管理方式,4.4 基本分段存储管理方式,4.4.1 分段存储管理方式的引入4.4.2 分段系统的基本原理4.4.3 信息共享4.4.4 段页式存储管理方式,分页从根本上克服了外零头（地址空间、物理空间都分割）。内存利用率提高。,4.4.1 分段存储管理方式的引入,缺点：无论信息内容如何，按页长分割，分割后装入内存，有可能使逻辑完整的信息分到不同的页面，-执行速度降低。所以考虑以逻辑单位分配内存。如：,引入分段存储管理方式，主要是为了满足用户和程序员的需要 便于编程用户常把自己的作业按逻辑关系划分成若干个段，每段都有自己的名字，且都从零开始编址，这样，用户程序在执行中可用段名和段内地址进行访问。例如：LOAD 1，A|。分段共享在实现程序和数据的共享时，常常以信息的逻辑单位为基础，而分页系统中的每一页只是存放信息的物理单位，其本身没有完整的意义，因而不便于实现信息的共享，而段却是信息的逻辑单位，有利于信息的共享。,4.4.1 分段存储管理方式的引入,分段保护:信息保护是对相对完整意义的逻辑单位(段)进行保护 动态链接:当运行过程中又需要调用某段时，再将该段（目标程序）调入内存并链接起来。所以，动态链接是以段为基础的。动态增长:在实际系统中，有些数据段会不断地增长，而事先却无法知道数据段会增长到多大，分段存储管理方式能较好地解决这个问题,4.4.2 分段系统的基本原理,1.分段 在分段存储管理方式中，作业地址空间被划分为若干个段，每个段定义了一组逻辑信息，都有自己的名字。通常用段号代替段名，每段从0开始编址，并采用一段连续地址空间。段长由逻辑信息组的长度决定。整个作业的地址空间分成多个段，逻辑地址由段号(段名)和段内地址所组成。,该地址结构允许一个作业最长有64K个段，每段的最大长度为64KB。,4.4.2 分段系统的基本原理,1.分段分段式存储管理的原理 作业分为若干个段。每段分配一个连续的内存区，由于各段的长度不等，这些区域也就大小不一。作业各段间不要求连续。,基本分段式存储管理的原理 在段式存储管理原理的基础上，要求将整个作业的全部段装入内存。请求分段式存储管理的原理 在段式存储管理原理的基础上，不要求将整个作业的全部段装入内存。只装入作业的几段即可运行，其余段可根据运行的需要再装入内存。,2.基本分段式存储管理的实现1）段表为使程序正常运行，须在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项。段表结构：段号；段在内存中的起始地址(基址)；段长。段表可以存放在寄存器中，但更多的是存放在内存中。段表用于实现从逻辑段到物理内存区的映射。,4.4.2 分段系统的基本原理,2）地址变换机构 在系统中设置段表寄存器，用于存放段表始址和段表长度，以实现从进程的逻辑地址到物理地址的变换。,当段表存放在内存中时，每访问一个数据，都需访问两次内存，降低了计算机的速率。解决方法：设置联想寄存器，用于保存最近常用的段表项。,4.4.2 分段系统的基本原理,2.基本分段式存储管理的实现,物理地址,+,越界中断,分段系统的地址变换机构：,段表,9200,200,8K,500,4K,600,6K,1K,段长,基址,段号,0,1,2,3,+,8292,逻辑地址,物理地址,+,越界中断,基本分段式存储管理之例,段表,9200,200,8K,500,4K,600,6K,1K,段长,基址,段号,0,1,2,3,+,8292,作业表,逻辑地址,3.分页和分段的主要区别相似点：采用离散分配方式，通过地址映射机构实现地址变换不同点：页是信息的物理单位，分页是为了满足系统的需要；段是信息的逻辑单位，含有一组意义相对完整的信息，分段是为了满足用户的需要。页的大小固定且由系统确定，由系统把逻辑地址分为页号和页内地址，由机器硬件实现；段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。分页的作业地址空间是一维的；分段的作业地址空间是二维的。,4.4.2 分段系统的基本原理,4.4.3 信息共享,分段系统的一个突出优点是易于实现段的共享和保护，允许若干个进程共享一个或多个分段，且对段的保护十分简单易行。分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便。,在分段系统中，实现共享十分容易，只需在每个进程的段表中为共享程序设置一个段表项。,可重入代码又称为纯代码，是一种允许多个进程同时访问的代码，可重入代码不允许任何进程对它进行修改。,4.4.3 信息共享,在每个进程中，配以局部数据区，将在执行中可能改变的部分，拷贝到该数据区，这样，程序在执行时，只对该数据区(属于该进程私有)中的内容进行修改，而不去改变共享的代码，这时的可共享代码即成为可重入代码。例,4.4.3 信息共享,分段和分页存储管理方式各有优缺点。把两者结合成一种新的存储管理方式-段页式存储管理方式，具有两者的长处。1.基本原理 先将用户程序分成若干段，再把每个段分成若干页，并为每个段赋予一个段名。基本段页式存储管理：把作业的所有段装入内存方可运行。请求段页式存储管理：没必要把整个作业装入内存，可把作业 的几段或几页装入内存即可运行。在段页式系统中，地址结构：段号；段内页号；页内地址。,4.4.4 段页式存储管理方式,2.地址变换过程 在段页式系统中，为了实现地址变换，增加一个段表寄存器，用来存放段表始址和段长。,4.4.4 段页式存储管理方式,段表寄存器,段表大小段表始址,段页式存储管理 之例,在段页式系统中，为了获得一条指令或数据，需访问三次内存：第一次：访问内存中的段表，取得页表始址第二次：访问内存中的页表，取得该页所在的物 理块号，将块号与页内地址形成物理地址第三次：根据第二次所得的地址，取出指令或数据缺点：访存次数增加两倍解决方法：增设高速缓冲寄存器,4.4.4 段页式存储管理方式,作业,补充题1：某用户进程编程空间共4个页面，每页1KB，主存为64KB。假定该用户进程的页表如下。,求下面与虚拟地址相对应的物理地址（如果在主存中找不到，即为页失效）：（1）0A5C(H)（2）1A5C(H),答案：（1）125CH（2）越界中断,补充题2,每页1KB，对于下面的页表内容，逻辑地址37390，40462对应的物理地址分别是、。每页1KB，8页逻辑空间，32块物理块，逻辑地址的有效位是 位，物理地址至少 位。,答案：1）84*1024+526=86542；96*1024+526=988302）10+3=13；10+5=15,补充题3：,逻辑地址（2，88）对应的物理地址，（4，100）对应物理地址。,答案：90+88=178；越界中断,第四章 存储器管理,4.1 程序的装入和链接4.2 连续分配方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器的基本概念4.6 请求分页存储管理方式4.7 页面置换算法4.8 请求分段存储管理方式,4.5 虚拟存储器的基本概念,前面介绍的各种存储器管理方式，要求将一个作业全部装入内存后方能运行。于是出现了两种情况：有的作业很大，所要求的内存空间超过内存总容量，作业不能被全部装入内存，致使该作业无法运行。有大量作业要求运行，但内存容量不足以容纳所有作业，只能将少数作业装入内存使其运行，其他大量作业留在外存上等待。解决方法：从物理上增加内存容量从逻辑上扩充内存容量,4.5 虚拟存储器的基本概念,4.5.1 虚拟存储器的引入4.5.2 虚拟存储器的实现方法4.5.3 虚拟存储器的特征,4.5.1 虚拟存储器的引入,1.常规存储器管理方式的特征一次性：作业在运行前一次性地全部装入内存驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束。问题：一次性及驻留性在程序运行时是否是必须的？,2.程序运行的局部性原理 1968年，Denning.P提出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。,4.5.1 虚拟存储器的引入,局限性的表现：时间局限性空间局限性,3.虚拟存储器的定义,4.5.1 虚拟存储器的引入,虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却接近于外存。,4.5.2 虚拟存储器的实现方法,在虚拟存储器中，允许将一个作业分多次调入内存。如果采用连续分配方式，不仅造成内存资源的浪费，而且无法从逻辑上扩大内存容量。因此，虚拟存储器的实现都是建立在离散分配的存储管理方式的基础上。,1.请求分页系统在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入部分页面的程序(及数据)，便启动运行。以后再通过调页功能及页面置换功能，陆续将即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。置换时以页面为单位。为实现请求调页和置换功能，系统必须提供必要的支持：硬件支持：请求分页的页表机制 缺页中断机构 地址变换机构 软件支持：实现请求调页的软件 实现页面置换的软件,4.5.2 虚拟存储器的实现方法,2.请求分段系统 在分段系统的基础上，增加了请求调段功能和分段置换功能所形成的段式虚拟存储系统。它允许只装入若干段的程序(及数据)，便启动运行。以后再通过调段功能及段的置换功能，把暂不运行的段调出，同时调入即将要运行的段。置换时以段为单位。为实现请求调段和置换功能，系统必须提供必要的支持：硬件支持：请求分段的段表机制 缺段中断机构 地址变换机构软件支持：实现请求调段的软件 实现段的置换的软件,4.5.2 虚拟存储器的实现方法,4.5.3 虚拟存储器的特征,多次性：一个作业被分成多次调入内存运行 对换性：允许在作业的运行过程中进行换进、换出。虚拟性：能够从逻辑上扩充内存容量，使用户所看到的 内存容量远大于实际内存容量。虚拟性以多次性和对换性为基础；多次性和对换性又必须建立在离散分配的基础上。,第四章 存储器管理,4.1 程序的装入和链接4.2 连续分配方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器的基本概念4.6 请求分页存储管理方式4.7 页面置换算法4.8 请求分段存储管理方式,4.6 请求分页存储管理方式,请求分页系统是建立在基本分页基础上的，增加了请求调页功能和页面置换功能。换入和换出的基本单位都是长度固定的页面，因而在实现上比请求分段系统简单。,4.6.1 请求分页中的硬件支持,1.页表机制在请求分页系统中所需要的主要数据结构是页表。基本作用仍是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。由于只将程序的一部分装入内存，还有一部分在外存中，因此须在页表中增加若干项，供程序或数据在换进、换出时参考。,请求分页系统中的页表项：,(1)状态位P：指示该页是否已调入内存。,(2)访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问。,(3)修改位M：表示该页在调入内存后是否被修改过。,(4)外存地址：用于指出该页在外存上的地址。,2.缺页中断机构 在请求分页系统中，每当要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断作为中断，同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。但缺页中断是一种特殊的中断，与一般中断有明显区别：在指令执行期间产生和处理中断信号。一条指令在执行期间，可能产生多次缺页中断。,4.6.1 请求分页中的硬件支持,3.地址变换机构请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能而形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等。,请求分页中的地址变换过程,4.6.2 内存分配策略和分配算法,为进程分配内存时，涉及三个问题：最小物理块数的确定物理块的分配策略物理块的分配算法,1.最小物理块数的确定 最小物理块数，指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最小物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。,4.6.2 内存分配策略和分配算法,2.物理块的分配策略在请求分页系统中，可以采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可以采取两种策略，即全局置换和局部置换。于是可以组合出三种适合的策略。1）固定分配局部置换2）可变分配全局置换3）可变分配局部置换,4.6.2 内存分配策略和分配算法,1）固定分配局部置换 为每个进程分配一定数目的物理块，在整个运行期间不再改变。采用该策略时，如果进程在运行中发现缺页，只能从该进程在内存中的n个页面中选出一页换出，然后再调入一页。困难：应为每个进程分配多少个物理块难以确定。,内存分配策略和分配算法,2）可变分配全局置换在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲的物理块队列。如果某进程发生缺页时，由系统从空闲的物理块队列中，取出一个物理块分配给该进程，并将欲调入的页装入其中。当空闲物理块队列中的物理块用完后，OS才能从系统中的任一进程中选择一页调出。,4.6.2 内存分配策略和分配算法,3）可变分配局部置换 为每个进程分配一定数目的物理块，如果某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，不会影响其他进程执行。如果进程在运行中频繁发生缺页中断，则系统再为进程分配若干物理块；如果进程在运行中缺页率特别低，则适当减少分配给该进程的物理块。,4.6.2 内存分配策略和分配算法,3.物理块分配算法 在采用固定分配策略时，如何将系统中可供分配的物理块分配给各个进程，可采用以下几种算法：(1)平均分配算法:将系统中所有可供分配的物理块，平均分配给各个进程。缺点:未考虑各进程本身的大小。,4.6.2 内存分配策略和分配算法,4.6.2 内存分配策略和分配算法,又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：,bi应该取整，必须大于最小物理块数。,(2)按比例分配算法:根据进程的大小按比例分配物理块。设系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：,(3)考虑优先权的分配算法在实际应用中，为了照顾重要的、急迫的作业尽快完成，应为它分配较多的内存空间。方法：把内存中可供分配的物理块分为两部分，一部分按比例分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额，分配给各进程。,内存分配策略和分配算法,4.6.3 调页策略,1.何时调入页面为了确定系统将进程运行时所缺页面调入内存的时机，可采取预调页策略或请求调页策略。1）预调页策略 采用以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。主要用于进程的首次调入时，由程序员指出应该先调入哪些页。,2）请求调页策略 当程序在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需要的页面调入内存。优点：由请求调页策略所确定调入的页，一定会被访 问；请求调页策略比较容易实现。缺点：每次仅调入一页，需花费较大的系统开销，增 加了磁盘I/O的启动频率。,2.从何处调入页面将请求分页系统中的外存分为文件区和对换区。每当发生缺页时，系统应从何处将