操作系统——存储管理(完)..

计算机软件技术基础存储管理第四章存储管理4.1概述一、存储器的层次：三级存储器结构Cache内存外存由硬件寄存器构成，速度等同于电子线路的开关速度由顺序编制的单元组成的一维数组内存的后备支持，如：磁盘、磁带只有通过内存，cpu才能访问Cpu可以直接访问存取速度增加成本增加容量减少本章主要讨论几种常用的内存管理技术。计算机软件技术基础存储管理二、用户程序的处理过程执行代码数学模型源程序目标模块装配模块符号、名字相对地址（各模块都以0为基地址）（统一的外部访问地址）内存的物理地址4.1概述绝对装入方式：按模块中的地址，将程序和数据装入到内存对应位置。可重定位方式：在装入程序时，根据当时内存的实际使用情况，重新调整装入的内存位置，把程序装入到内存的适当地方。数学模型编辑用P,C源程序编译汇编目标模块连接装配模块装配执行代码计算机软件技术基础存储管理绝对目标程序（可执行代码）(绝对地址.物理地址)存储空间名字空间源程序(名字/符号)地址空间相对目标程序(相对地址.逻辑地址虚地址)编译连接地址重定位三、地址重定位（映射）---Relacation1.术语4.1概述名字空间：用户源程序中由符号指令，数据说明等符号名字构成的空间经汇编或编译后其目标程序占有的地址范围称为地址空间；这些地址编号是相对于起始地址（0）而定的，称为逻辑地址或相对地址。存储空间是目标程序装入内存后占用的一系列物理单元的集合。这些物理单元编号称为物理地址或绝对地址。把程序中的逻辑地址变成内存中的物理地址的过程。计算机软件技术基础存储管理2.重定位的两种方式静态重定位:在程序执行之前进行；由重定位装配程序根据将要装入的内存起始位置直接修改模块中的有关使用地址的指令。－－固定在内存的某个连续区域，不能再移动。重定位装配程序来实现(一对界地址寄存器实现保护)三、地址重定位（映射）x’=x+D物理地址逻辑地址下界地址—内存中的起始地址逻辑地址空间xLD上界下界界地址寄存器内存空间Lx’D内存中起始地址内存中结束地址计算机软件技术基础存储管理三、地址重定位（映射）特点：程序执行前一次性全部完成。性能分析：优点---实现简单，不需要硬件机构；缺点---程序重定位之后就不能再在内存中移动；要求程序的存储空间是连续的，不能放在若干个不连续的区域内；各个用户进程很难共享内存中的同一程序副本。例：假设已知一段程序的经汇编连接后逻辑地址空间如图所示，采用静态地址重定位，上，下界地址寄存器如图，试给出其存储空间图。0100300400LOAD1，300567814001000上界下界与地址有关的量要做变更X’=x+D13005678100011001400LOAD1，300内存X’=x+D300与地址有关的量如何处理？1300300计算机软件技术基础存储管理(2)动态重定位时机：在程序执行过程中进行，当CPU访问内存指令时由动态变换机构自动进行地址转换。实现：目标模块不加任何修改而装入内存，由定位寄存器和加法器硬件完成地址转换。三、地址重定位（映射）LOAD1，30056780100300400例：假设已知一段程序的经汇编连接后逻辑地址空间如图所示，采用动态地址重定位，试给出其存储空间图。10001100LOAD1，3001300567814001000+重定位寄存器加法器300与地址有关的量如何处理？300程序不做任何修改装入内存，在执行时访问内存时利用重定位寄存器进行地址重定位计算机软件技术基础存储管理特点：程序执行时动态地完成。性能分析：优点---程序装入内存之后再搬迁也不会影响其正确执行；每个目标模块装入的存储区不必顺序相邻，只需要各自对应的定位寄存器即可。--是虚拟存储器技术的基础缺点---需要硬件支持。三、地址重定位（映射）计算机软件技术基础存储管理四、存储管理的功能•内存的分配与回收；地址重定位；内存信息的共享与保护；内存的扩充（满足用户对内存超容量要求）；4.1概述计算机软件技术基础存储管理1。可由CPU调用执行的程序所对应的地址空间为。A.名称空间B.虚拟地址空间C.相对地址空间D.物理地址空间2。当程序经过编译或者汇编以后，形成了一种由机器指令组成的集合被称为。A.源程序B.目标程序C.可执行程序D.非执行程序3。目标程序指令的顺序都以0作为一个参考地址，这些地址被称为。A.虚拟地址B.物理地址C.绝对地址D.重定位地址4。若调用指令LOADA,Data，经动态重定位后，其对应指令代码。A.保持不变B.会变化，随装入起始地址变化而变化C.会变化，固定在某一存储区域D.重定位项等于重定位寄存器内容计算机软件技术基础存储管理目的：为了满足多道程序设计思想。方法：将内存划分为若干个分区，每个分区分配给一个作业，用静态重定位方式进行地址转换，提供必要的保护手段，保证各作业互不干扰。在分区的划分方式上有固定分区和可变分区两种。4.2早期的存储管理技术---分区式分配方式计算机软件技术基础存储管理一、固定式分区（静态分区）一、固定式分区区号大小起址标志18K20K0232K28K0364K60K04132K124K0(b)分区说明表0124K132K4作业C60K64K3作业B28K32K2作业A20K8K1标志起址大小区号D(150k)C(40k)B(25k)A(6k)(c)后备队列作业例：已知内存分配如图a所示，此时分区说明表如图b所示，现有后备作业队列如图c所示，试采用固定分区法进行内存分配，并给出相应的分区说明表。C(40k)B(25k)A(6k)性能：分区大小固定，分区表的结构可以是顺序表也可以是链表；实现了多个作业共享内存；分区的分配和回收算法简单；缺点是内存利用不充足，有“碎片”，即作业所需空间和分区大小不一定恰好相等。020k28k60k124kOS256K第一分区第二分区第三分区第四分区(a)内存分配图8K32K64K132KJobA(6k)JobB(25k)JobC(40k)内部碎片24K内部碎片7K内部碎片2K外部碎片剩余165K但不能分配给D计算机软件技术基础存储管理4.2分区式分配方式二、可变式分区（动态分区）1.思想：又称动态存储管理，只有当作业调入内存时，才按作业大小建立分区，当作业执行完后又释放此空间。P8P6P4P3P1图1占用块空闲块某一时刻内存区状态计算机软件技术基础存储管理2.分区的管理与组织方式采用可变分区方式管理内存储器时，内存中有两类性质的分区：•一类是已经分配给用户使用的“已分配区”，•另一类是可以分配给用户使用的“空闲区”。对分区的管理，常用的方式有三种：表格法、单链表法和双链表法。二、可变式分区计算机软件技术基础存储管理（1）表格法二、可变式分区内存分区的管理表格计算机软件技术基础存储管理（2）单链表法二、可变式分区单链表形式分区管理在每块开始与结束的几个字节中存放有关本块状态的信息，称为控制信息区,如图a所示。计算机软件技术基础存储管理二、可变式分区（3）双链表法0P0150000P4900035011901av空闲块链表UplinktagRlinksizetagLlink控制信息区计算机软件技术基础存储管理空间分配例题设某系统用户区大小为5000字节，地址为1～5000，初始状态如下图a所示，依次分配给5个作业P1～P5,作业占用区大小分别为1000，300，600，900，700。P0为余下的空闲块，各占用块和空闲块情况如下页图b和c所示。P2P5P0P4P3P115007009006003001000图a二、可变式分区0P015000图c—空闲块av3501注意：空间分配回收时使用空闲块链表1P11000111P230011P360011P57001100113012801图b—占用块1P490011901计算机软件技术基础存储管理0P015000av35010P0150000P4900035011901avP2P5P0P4P3P1P4释放P2P5P0P4P3P115007009006003001000图a1P490011901空间回收过程图（无空闲块合并发生）空间回收过程图（有空闲块合并发生）0P0+P4+P531000av1901P2P5P0P4P3P1P5释放当P5作业完成后，回收时由于其左右邻居均为空闲块，因此应进行合并。0P0150000P4900035011901av计算机软件技术基础存储管理4.分配算法：a.最先适应算法(First-Fit)：空闲表按空闲块的物理起始地址递增次序排列，分配时，从第一块依次查找，找到第一块能容纳作业的空闲块就停止。b.最佳适应算法(Best-Fit)：空闲表按空闲块的大小递增次序排列，分配时，从第一块依次查找，找到第一块能容纳作业的空闲块就停止。c.最差适应算法：(Worst-Fit):空闲表按空闲块的大小递减次序排列，分配时，将空闲块链表中第一块分配给用户。二、可变式分区计算机软件技术基础存储管理三、多重式分区一个作业装入内存中多个不一定相邻的分区。优点：灵活利用内存；缺点：碎片小了，但可能数量更多。4.2分区式分配方式计算机软件技术基础存储管理四、分区管理的存储保护界地址法：静态重定位使用4.2分区式分配方式一对基地址、限长寄存器。动态重定位使用。逻辑地址空间xLD上界下界界地址寄存器物理地址空间Lx’D内存中起始地址内存中结束地址用户2用户1限长寄存器基址寄存器+地址越界中断内存yesnoCPU计算机软件技术基础存储管理4.2分区式分配方式五、可重定位式分区（紧缩分区）1.实现：向一个方向移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。2.问题：a.地址项的修改---动态地址重定位；基址－限长寄存器保护；b.紧缩时机:回收时进行---每当作业结束,释放所占分区时;分配时进行---当新作业到来又没有能容纳的空闲区分配时;3.性能：消除了碎片，提高了内存利用率；但花费了大量的cpu时间。计算机软件技术基础存储管理1.分区管理要求对每一个作业都分配内存单元。A.地址连续B.若干地址不连续C.若干连续的帧D.若干不连续的帧2.碎片是指。A.存储分配完后剩余的空闲区B.没有被使用的存储区C.不能被使用的存储区D.未被使用，而又暂时不能使用的存储区计算机软件技术基础存储管理1.引入：最早用于分时系统中提高内存利用率的一种内存扩充技术。2.思想（roll-inroll-out）：除操作系统外，剩余的全部内存都分给当前正在执行的用户使用，当调度转向下一个用户时，当前用户内存区中的内容要写到外存中，被选中的用户的信息读入内存。3.实现：由换入和换出两个过程构成的交换进程完成。4.核心问题：保证对换信息量要最少---只要保证当前正在执行的用户进程在内存中完整保存。5.技术支持一般都有动态重定位机构---因而一个作业换入内存时不一定要装入它被换出前所占据的区域中.需要较多软件的支持.4.3多道程序对换技术计算机软件技术基础存储管理一、引入目的：为了解决分区存储管理中，当某作业需求空间大于内存物理空闲空间时，该作业无法运行的问题。二.原理:程序执行时的局部性原理三、思想：在一个程序执行过程中，不需要全部装入内存，而把不经常被进程访问的程序段和数据放在外存中，待需要访问它们时再将它们调入内存。（部分装入内存）4.4虚拟存储器的概念计算机软件技术基础存储管理三、虚拟存储器：是指仅把作业的一部分装入内存便可运行该作业的存储器系统，具有请求调入和置换功能。4.4虚拟存储器的概念虚拟存储管理技术需要解决的问题：（1）什么时候把哪部分程序装入内存。（2）放在内存什么位置。（3）当内存空间不足时，把哪部分程序淘汰出内存。常用的虚拟存储技术有：分页存储管理、分段存储管理、段页存储管理。计算机软件技术基础存储管理四、物质基础1.二级存储器(内/外存)---实现内/外存有机联系;2.动态地址转换机构(DAT)---实现动态定位实际上用户的虚拟地址空间并不可能是无限大，它受到以下两个条件制约：1.指令中地址长度的限制。2.外存储器容量的限制。计