《计算机操作系统第四章-存储器管理(1-2)要点课件.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第四章-存储器管理(1-2)要点课件.ppt（71页珍藏版）》请在三一办公上搜索。
1、第四章 存储器管理,4.1 存储器的层次结构 4.2程序的装入和链接 4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,4.1 存储器的层次结构,寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。,在主存中,存储器管理：指内存的管理，外存管理在文件部分讲述；单道程序系统：内存被划分成两部分：一部分供OS使用，一部分供当前正在执行的程序使用。多道程序系统：存储器的用户部分必须进一步地细分，以适应多个进程的要求。细分的任务由操作系统
2、动态实现，这就是存储器管理。存储器管理的目的：一是方便用户使用，二是提高存储器的利用率。,基本概念补充,1、存储器管理功能,主存的分配和回收：系统应能记住每个存储区的状态；实施存储器的分配；回收系统或用户释放的存储区。提高主存利用率：使多道程序能动态地共享主存，最好能共享主存中的信息。地址转换或重定位主存保护：保证进入主存的各道作业都在自己的存储空间内运行，互不干扰。由硬件和软件配合完成。主存扩充：借助于虚拟存储技术，为用户提供比主存空间大的地址空间。,内存的每个存储单元都有一个编号，这种编号称为内存地址（或称为物理地址，绝对地址）。内存地址的集合称为内存空间（或物理地址空间）。例如，我们常说
3、内存为：512MB要求用户用内存地址编程是非常困难的，尤其是在多道程序设计的环境中（不知道）。,2、地址映射(地址重定位),用户编程所用的地址称为逻辑地址（或程序地址，或虚地址），由逻辑地址组成的空间称为逻辑地址空间（或程序地址空间）。我们把用户程序装入内存时，或在程序执行时，对有关指令或数据地址的修改称为从程序地址到内存地址的地址映射，或称为地址重定位。,1100,地址映射的方式,静态地址映射：1）程序被装入内存时由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换；2）地址转换工作是在程序执行前由装入程序集中一次完成。假定程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则
4、地址映射按下式进行：MR=BR+VR,把程序装入起始地址为1000的内存区,Mov r1,500,1234,0,100,500,600,Mov r1,1500,0,1000,1100,1500,1600,1234,作业的地址空间,存储空间,装入程序,静态映射优缺点,优点：不需要硬件的支持，简单易实现，成本低；缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动；主存利用率低；难以做到程序和数据的共享。,动态地址映射（重定位）,动态地址重定位：在程序执行的过程中，每次将要访问的指令或数据逻辑地址转换为内存地址。动态映射方法：装入程序把程序和数据原样装入到已分配的存储区中，然后把这个存储区的起
5、始地址送入重定位寄存器中。在程序执行时，再将相对地址转换成绝对地址。硬件支持：在动态地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。转换过程：MR=BR+VR,把程序装入起始地址为1000的内存区,1234,0,100,500,599,作业的地址空间,0,1000,1100,1500,1599,1234,存储空间,1000,+,重定位寄存器,逻辑地址VR,物理地址MR,MOV r1，500,MOV r1，500,动态地址映射的过程,程序装入内存后，它所占用的内存区的首地址由系统送入基地址寄存器BR中。在程序执行的过程中，若要访问内存，将访问的逻辑地址送
6、入VR中。地址转换机构把VR和BR中的内容相加，并将结果送入MR中，作为实际访问的地址。,动态重定位优缺点,优点：1）程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可；2）一个程序不一定要求占用一个连续的内存空间，可以部分地装入程序运行；4）便于多个进程共享同一个程序的代码。动态地址重定位的代价：1）需要硬件的支持；2）实现存储管理的软件算法较为复杂。,4.2 程序的装入和链接,（可能产生）可执行程序文件,编译,链接,装入,二进制内存映像,程序处理步骤：编译-编译程序，负责检查语法错，涉及名空间。输入：源程序；输出：多个目标模块；链接-链
7、接程序，负责将多个模块相关联，涉及逻辑地址空间。输入：多个目标模块、库函数；输出：装入模块；装入：装入程序，负责内存分配和地址映射，涉及内存空间。输入：装入模块；输出：可执行的二进制内存映像。,过程或函数可能分别对应一个模块！,4.1.2 程序的链接,1.静态链接方式(Static Linking),图 4-3 程序链接示意图,链接前，每个模块都有各自的相对起始地址0,链接后，每个模块使用同一个相对起始地址0,名空间,逻辑地址空间,在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块，又称为可执行文件，以后不再拆开。解决：对相对地址进行修改；变换外部调用符号,不要求！,2
8、.装入时动态链接(Loadtime Dynamic Linking),基本思想：源程序被编译生成的目标模块，是在装入内存时，边装入边连接。装入程序根据外部模块调用而逐个装入和连接。装入时动态链接方式有以下优点便于修改和更新：各个模块的修改极易编译和连接；便于实现对目标模块的共享：将内存中的一个模块可以连接到多个程序中。要运行的程序都必须在装入时，全部连接调入内存。,3.运行时动态链接(Run-time Dynamic Linking),动态链接方式：将对某些模块的链接推迟到执行时才实施，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用
9、者模块上。特点如下：特点：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。,三种链接方式的差别相当于：静态链接：上车（相当于进入内存）前集合起来装入时链接：上车后开车前集合起来运行时链接：开车后需要时集合起来,4.2.1 程序的装入,1.绝对装入方式(Absolute Loading Mode),程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予；编译程序生成的目标模块其逻辑地址与要装入内存的物理地址相同；缺点：单道程序可用，多道程序环境不能用。,采用绝对地址装入，目前很少使用,2.可重定位装入方
10、式(Relocation Loading Mode),图 4-2 作业装入内存时的情况,又称静态重定位：地址变换在装入时一次完成，其后不能移动。,逻辑地址（相对地址）,物理地址（绝对地址）,LOAD 1,12500,3.动态运行时装入方式(Denamle Run-time Loading),动态运行时装方式：装入内存后的所有地址都仍是相对地址；逻辑地址到物理地址的变换要推迟到程序真正执行时才进行；地址变换发生在程序执行过程中（即动态重定位）。为使地址转换不影响程序执行速度，必须使用硬件支持。,链接和装入的关系（一）,静态链接会形成磁盘上的可执行文件，而装入时动态链接和运行时动态链接不会产生磁盘
11、上的可执行文件。静态链接产生的可执行文件装入时内存是连续分配的，而地址映射既可采用可重定位装入方式（静态重定位）也可以采用动态运行时装入方式（动态重定位）,链接和装入间的关系（二）,装入时动态链接方式可以分别给每个装入模块分配一块内存区域，因而装入时各模块不一定连续存放。装入时的地址映射既可采用可重定位装入方式（静态重定位-链接后运行前一次性修改逻辑地址为物理地址）也可以采用动态运行时装入方式（动态重定位-运行时动态计算出逻辑地址到物理地址的映射）,链接和装入间的关系（三）,运行时动态链接方式一般情况下后装入的模块和原先已装入的模块是不连续存放的。运行时动态链接方式的地址变换不可能运行前一次性
12、映射地址，即不可能采用静态重定位方法，而只能使用动态重定位的方法。,链接和装入间的关系（四）,4.2 连续分配方式,4.2.1 单一连续分配,特征：最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中；常把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。,4.2.2 固定分区分配,1.划分分区的方法,分区大小相等，即使所有的内存分区大小相等。缺点：缺乏灵活性，大作业无法运行，小作业浪费空间。分区大小不等，即划分为小、中、大不等的固定分区。优点：灵活性好。,分配方法：将用户空间划分为若干个固定大小的区
13、域，在每个分区中装入一道作业；有几个分区，就有几道并发的作业；有空闲分区时，可调入一适当大小的作业；最简单的一种多道程序存储管理方法。,2.内存分配：为了便于内存分配，将分区按照大小排队，并建立一个分区表。如图所示。当为作业分配空间时，分配程序按照此表检索以合适分区分配；否则，拒绝分配。缺点：空间浪费。,图 4-4 固定分区使用表,4.2.3 动态分区分配,1.分区分配中的数据结构,空闲分区表。(2)空闲分区链。,图 4-5 空闲链结构,分配思想：根据进程的实际需要，动态的为进程分配（切分）内存空间，及需要多大，分配多大。提高内存的利用率。,未分配区表用空闲区链表表示：,0,0,10k,10k
14、,270k,0,0,730k,730k,100k,100k,100k,270k,空闲区链,head,空闲区大小,2.分区分配算法,首次适应算法FF：空闲分区按地址递增成链表；每次分配从链首依次查找一空间首次满足作业的空闲分区；再从该分区中切出与作业等量的空间分之，余者挂到链表中；若找不到满足作业空间要求的空闲分区，分配失败。优缺点：低地址部分将产生多个较小的空闲分区（碎片），增加分配开销。,问题：如何从空闲分区表或链表中，选择一分区分配个作业，常用的算法如下：,2.分区分配算法,循环首次适应算法：该算法是由首次适应算法演变而成的，区别仅是从上次已分配分区的下一个分区依次查找首次满足作业的空闲分
15、区，并从中划分出作业需要的分区。实现方法：起始循环指针+循环空闲分区链表最佳适应算法：空闲链表依照空间大小排列，每次从链首为作业找一个大小最合适的分区分配。缺点：最佳适应必将产生最小的空闲碎片。最坏适应算法(worst fit)：总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业有利，同时最坏适应分配算法查找效率很高。,3.分区分配操作,分配内存操作 分配操作如左图所示,回收内存操作 回收的分区有4种情况：与前、后、前后空分区相邻，如下图所示。,图 4-7 内存回收时的情况,当回收分区与前后空闲分区均不相邻时，为回收分区建立一个空闲分区
16、结点，并插入链表适当位置。,回收分区,4.2.4 可重定位分区分配,1.动态重定位的引入：动态回收碎片，将小而不可用的空闲分区拼接成较大的一个空闲分区。移动作业分区，必然要重定位。,图 4-8 紧凑的示意,2.动态重定位的实现：作业在内存中仍保持逻辑地址，在执行时再实施重定位。具体过程如下图。,图 4-9 动态重定位示意图,3.动态重定位分区分配算法：在动态分区算法增加了回收碎片的功能。,图 4-10 动态分区分配算法流程图,作业4-1,P142：4、5、6,4.2.5 对换(Swapping),1.对换的引入,对换定义：对换是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上
17、，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换目的：提高内存的利用率。进程对换：如果对换是以整个进程为单位进行的，则称为进程对换或整体对换；页面对换：如果对换是以页或段为单位进行的，称为页面对换或分段对换，统称部分对换。在实现虚拟存储系统时候，依靠页面或分段对换。,2.对换空间的管理,实现进程对换系统必须具备三个功能：对换空间管理、进程的换出和进程的换入。首先研究对换空间管理：将外存磁盘空间划分为文件区和对换区：文件区用于存放文件，管理以提高存储空间的利用率为目的；后者用于存储对换的进程，故应以提高对换速度为目标。对换去空间管理：建立对换区空闲空间分区
18、表（链）数据结构。其形式与内存动态分区分配方式中的空闲分区表或空闲分区链。在空闲分区表中的每个表项中应包含两项，对换区的首址及其大小，它们的单位是盘块号和盘块数。,2.对换空间的管理,对换区分配：采用连续分配，雷同内存动态分区方式的分配算法：可用首次适应算法，循环首次适应算法或最佳适应算法。对换区回收：也与内存动态分区回收算法雷同，要考虑回收区与前后地址相邻（磁盘块号）分区的合并。,3.进程的换出与换入,进程的换出：每当创建一新进程而又无足够的内存空间时，系统应将某进程换出。换出过程：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，并将该进程的程序和数据安全传送到磁盘的对换区上；然后回
19、收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改（该什么？）。进程的换入：系统定时找出“静止就绪”状态的进程，并将其中换出时间最久的进程作为换入进程换入，直至已无可换入的进程,4.3 基本分页存储管理方式,问题：由于为进程连续分配内存空间，将产生大量碎片；为了利用碎片必须将其合并，又需要系统开销。能否给进程离散（不连续）地分配内存空间，解决这些问题？离散分配：当前使用最多的内存分配方式是分页管理方式和分段管理方式；分页是页面为单位进行内存分配，分段方式是以段为单位进行内存分配。基本分页（段）存储管理方式：如果分页或分段存储管理方式中不具备页面或分段对换功能，将其称之为基本分页或基本
20、分段存储管理方式。,4.3.1 页面与页表,1.页面与物理块页面：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页顺序编号为0、1、2、n。物理块：把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0块、1块等等。内存分配原理：在为进程分配内存时，以页面为单位给进程离散分配与页面数等量的物理块，并分别装入到相应的物理块中（全部装入）页内碎片：由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。,举例：如左图所示，按照基本分页存储管理方式为进程分配内存空间。设页面大小为1KB,页面大小设定：在分页
21、系统中的页面其大小应适中，且页面大小应是2的幂，通常为512 B8 KB。页面大小利弊：若页面太小，内存碎片减小，从而减少了内存碎片的总空间，提高内存利用率；但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存等；若页面较大，可以减少页表的长度，节省内存，但却又会使页内碎片增大。,2、逻辑地址结构,最大页面数：220=1M个页面大小：212=4KB逻辑空间：0232-1一维的，并针对程序员,逻辑地址空间中的地址为A，页面大小为L，则有：,P=INTA/L,d=A MOD L,例：A=2170B，L=1KB时，则有P=2，d=122,3、页表分页存储管理方式按照进程页面的
22、多少，为进程离散分配相同数量的物理块，为了记录每一页所分配的物理块，必须为每个进程建立一个页表每个进程一个页表，每个页面一个表项；表项：页号：0、1、2、n；块号：离散分配形成；存取控制：读写控制,页表示意图,图 4-11 页表的作用,基本分页系统多进程内存分配示意图,4.3.2 地址变换机构,基本的地址变换机构：实现逻辑地址向物理地址的转换。由于页内地址与块内地址一一对应，所以地址转换关键是将逻辑地址中的页号转换为内存中的物理块号。转换机构设施：页表寄存器：存放进程页表在内存中的起地址和页表长度（进程不执行时放在PCB中，执行时调入寄存器中）；物理地址寄存器：存放转换后的物理地址（内存地址）
23、；查找表项：表项地址=页表起始地址+页号*表项长度；地址转换过程如下图。,图 4-12 分页系统的地址变换机构,例 说明运行进程的地址变换过程。如下图所示，进程程序地址空间共有7个页，每页的大小为1024。其对应的主存块在页表中已列出。假定页表在主存始址为500。若该程序从第0页开始运行，且现程序计数器内容为：,0,100,程序计数器：,逻辑地址,例：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。,虚地址 7145P7145 2048 3W7145 mod 2048 1001MR=5*2048+1
24、001=11241虚地址7145的内存地址是：11241,虚地址 3412P3412 2048 1W3412 mod 2048 1364MR=9*2048+1364=19796虚地址3412的内存地址是：19796,2、具有快表的地址变换机构问题：两次访问内存(页表，数据)，运行速度下降一半；解决方法：联想存储器，快表，存放当前访问的页表项；思路：将已访问的页号的页表项放入快表，方便下次访问，提高访问速度，争取一次访问内存；联想存储器：通常只要设定816个寄存器作为联想存储器，即可使程序执行速度大大提高。,具有快表的地址变换过程示意图,图 4-13 具有快表的地址变换机构,4.3.3 两级和多
25、级页表,问题：现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB即212 B，则在每个进程页表中的页表项可达1兆个之多，而且还要求是连续的。解决办法：采用离散分配方式存放页表；使用对换方式调入、调出页表。,1.两级页表(Two-Level Page Table),逻辑地址结构可描述如下：页面大小为4K（12位），每页包含1024个页表项（P2，占10位）；总共有1024个分页（P1，占10位）,图 4-14 两级页表结构,图 4-15 具有两级页表的
26、地址变换机构,二级页表地址转换过程示意图,2.多级页表 对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4 KB即212 B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表项，要占用16384 GB的连续内存空间。必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。对于64位的计算机，如果要求它能支持2(=1844744 TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际
27、应用中也无此必要。,例题一一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入有32个物理块的存储器中，问：(1)逻辑地址需要多少位二进制来表示？(2)绝对地址需要多少位二进制来表示？,解：页面数：8=23 块数：32=25 页面长度：1024=210,页面长度决定了页内地址的长度09，10位；页面数决定了页号的地址长度02，3位；块数决定了块号的地址程度04，5位；块内地址与页内地址的长度相等；故：逻辑地址需要用13位来表示；绝对地址需要用15位来表示；,习题二：设有一分页管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存总共有8个存储块，试问逻辑地址至少应为多少
28、位？物理地址至少应为多少位？内存空间共有多大？,答案：逻辑地址至少15位；物理地址至少14位；内存空间共有8*2048=214,习题三：现有一分页管理系统，其页表存放在内存中。若对内存的一次存取需要1.5ms，试问实现一次页面访问的存取时间是多少？现有一个加有快表的系统，快表的平均命中率为80%，当页表项在快表中时，其查找时间忽略为0，试问此时的存取时间是多少？若快表的平均命中率为90%时，存取时间又为多少呢？,解：若页表存在内存，则一个页面访问需要访问内存2次，已知一次存取时间为1.5ms，则一次页面访问的存取时间为3ms.若系统中有快表，则两种情况：需要访问的页面在快表中：访问内存1次；需要访问的页面不在快表中：访问内存2次；若快表的命中率为80%则：访问时间：0.8*1.5+(1-0.8)*2*1.5,
