c++-存储空间管理

存储空间管理东南大学电气工程学院定义存储器的分级结构：寄存器高速缓冲存储器(缓存)内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。外存储器（简称外存、辅助存储器）

处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。内存——存储器管理外存——文件管理存储器管理的功能（系统区和用户区，针对用户区）存储空间的分配与管理；地址重定位（逻辑地址与物理地址的对应关系）存储保护存储空间扩充：虚拟存储器技术以及各种调度算法。存储器管理地址重定位分区存储管理覆盖和交换页面式存储管理请求式页面存储管理段式存储管理段页式存储管理地址重定位地址空间和存储空间逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。逻辑地址、物理地址和地址映射地址映射1100LoadA,12003456

。

。

。1200物理地址空间LoadA,data1data13456源程序LoadA,20034560100200编译连接逻辑地址空间BA=1000地址重定位地址重定位：实现程序的相对地址空间到绝对地址空间之间的映射。程序在成为进程前的准备工作编辑：形成源文件(符号地址)编译：形成目标模块(模块内符号地址解析)链接：由多个目标模块或程序库生成可执行文件(模块间符号地址解析)装入：构造PCB，形成进程(使用物理地址)重定位方法：静态重定位：是指在程序装入主存时已经完成了逻辑地址到物理地址的变换,在程序执行期间不会再发生变化.动态重定位：在程序运行期间完成逻辑地址到物理地址的变换.地址重定位分区存储管理基本思想：将主存储空间划分成若干个连续的存储区，称为分区。每个分区只能存储一道程序，一个程序只能访问其所在分区的存储单元。单一连续区存储管理

适用于单道程序系统内存分为两个连续区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。最简单，适用于单道程序设计的OS。优点：易于管理。缺点：对要求内存空间少的程序，造成内存浪费（空闲存储区）。0H7FFFHFFFFFH操作系统用户程序区08000H界限寄存器中断矢量表空闲区单片机中的内存设置基本思想：把内存分为一些大小相等或不等连续区域－－－－分区(partition)，每个分区只能驻留一个程序。操作系统占用其中一个分区。特点：适用于多道程序系统和分时系统支持多个程序并发执行问题：存在碎片（小得难以使用的分区）问题，可能存在内部碎片和外部碎片。内部碎片：占用分区之内未被利用的空间外部碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。固定分区存储管理分区存储管理固定分区(大小相同)固定分区(多种大小)分区存储管理优点：简单易于实现，开销小。缺点：内部碎片造成浪费分区总数固定，限制了并发执行的程序数目。采用的数据结构：分区表(分区说明表)－－记录分区的大小和使用情况OperatingSystem空闲分区分区5作业C分区4分区3分区2分区1空闲分区作业B作业A00000H08000H0A000H12000H1A000H3A000H区号起始地址大小使用标志作业大小108000H8KY6K20A000H32KY24K312000H32KN41A000H128KY118K53A000H512KN内存分区说明表分区存储管理动态分区：在装入作业和处理过程中，按其要求的内存容量以及当时的内存资源使用情况，将一块大小与所要求相近的存储区分配给作业。优点：没有内部碎片。缺点：有外部碎片。动态分区(dynamicpartitioning)分区存储管理Operating

System128K896KOperating

SystemProcess1320

K576KOperating

SystemProcess1320KProcess2224

K352K分区存储管理Operating

SystemProcess1320

KProcess2Process3224

K288K64

KOperating

SystemProcess1320KProcess3224K288K64KOperating

SystemProcess1320

KProcess3288K64

KProcess4128

K96

K分区存储管理Process2结束Process4运行分区存储管理Process1结束Process2再运行分区的数据结构：分区表，或分区链表可以只记录空闲分区，也可以同时记录空闲和占用分区单一分区表中，表项数目随着内存的分配和释放而动态改变，表长难以确定，分配回收分区时降低查找速度。分区表可以划分为两个表：空闲分区表，使用分区表。从而减小每个表长度。空闲分区表（一般常用链表结构）中按不同分配算法相应对表项排序。分区分配和释放算法最先匹配法(first-fit)：可能造成碎片化问题最佳匹配法(best-fit)：每次要从碎片开始查找，回收算法复杂最差匹配法(worst-fit)：分配速度快，碎片小动态分区管理：分区存储管理引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。基本思想:一个作业的若干程序段，或几个作业的某些部分共享同一存储区。优点：解决小主存容量与大作业之间的矛盾。缺点：实现覆盖管理的系统开销较大。覆盖和交换覆盖(overlay)注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；覆盖技术不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)缺点：1、确定覆盖关系的复杂度2、牺牲时间换取空间引入：解决主存容量不足的矛盾。多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作“对换”或“滚进/滚出(roll-in/roll-out)”。基本思想:暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swapout），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swapin）。交换优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构。缺点：

对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。考虑的问题：换出进程的选择：一般换出短时间不会运行的进程交换时机的选择：内存不够后有危险时换出短时间不会运行的进程交换空间的分配：可交换到外存的相同或不同对换区换回内存位置的确定：动态重定位可以换回到不同的内存区，否则只能换回到相同的内存区交换交换技术与覆盖技术相比，交换技术的缺点是要花费大量内、外存交换时间，所以外存中应该保留交换程序的副本覆盖与交换技术都实现了大作业在小内存上运行。覆盖于与换技术的区别：覆盖由用户解决空间不足问题（即：覆盖只能在一个程序内部进行）交换由系统解决空间不足问题（即：交换可以在任意程序间进行）覆盖对程序结构有严格的限制交换对程序结构没有限制覆盖与交换的比较引入：避开作业的连续性要求，将一个作业存放在不连续的存储空间中，以很好地解决碎片问题。基本思想:系统把内存物理空间等分为若干大小相等、位置固定的块（或帧）。将程序的逻辑地址空间划分为与块大小相同的页或页面(pageorpageframe)，程序加载时，分配其所需的所有块，这些块不必连续。需要CPU的硬件支持。页面式存储管理地址空间分成大小相同的部分–––

页存贮空间分成大小相同的部分–––

块(页帧)页大小＝块大小

页表(PMT)

：又称页面映象表，记录一个作业程序的页号所对应的内存块号。需要CPU的硬件支持。页号块号012238分配时页对应块，但不要求连续页表包括：页号，块号页面式存储管理页帧19OperatingSystem作业2（页0）00000H0B000H0A800H0B800H0C000H0E000H作业1（页0）作业2（页2）作业1（页1）作业2（页1）作业3（页0）……物理地址空间页帧0页帧20页帧21页帧22页帧23页帧24页帧25页帧26页帧27页帧280C800H0D000H0D800H01逻辑地址空间作业1(4K)01作业2(5K)20作业3(1.8K)01页表0120页帧号222025212427页面式存储管理页面式存储管理硬件地址变换：指令所给出地址分为两部分：逻辑页号，页内偏移地址－>查进程页表，得物理页号－>物理地址页面大小：通常是几KB到几十KB（取2的幂）。小－>内部碎片小；大－>页表短，管理开销小，交换时对外存I/O效率高。页面式存储管理页式地址变换页面式存储管理引入：向用户提供大容量存储器，把内存和外存统一考虑，外存作为存储信息的主要媒介，内存作为处理机需要访问的数据缓冲区。基本思想:运行一个作业程序时，并不要求把该作业的全部程序和数据都装入内存，可只把目前要执行的几页调入内存的空闲存储块，其余部分仍保存在外存，以后根据作业程序运行情况需要时再调入内存。请求式页面存储管理需解决的问题：提供一种机制，检测访问的页是否在内存，若不在，为之分配一物理页，修改页表项，并将逻辑页调入到物理页。选择淘汰算法：当外存上某页信息需调入内存而内存中又无空闲存储块时，则需按某种淘汰算法从内存中选择一页将其内容淘汰。淘汰算法不合理将产生抖动现象－－刚被调出的页马上又被要求调入。存储保护的目的：保护系统程序区不被用户侵犯（有意或无意的）不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）1.存储保护由于存储保护检查是针对每个存储访问操作进行的，必须由相应的处理器硬件机构支持。页面的共享与保护存储保护类型界限保护：所有访问地址必须在上下界之间；每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。访问方式保护：通过保护键匹配来判断存储访问方式是否合法。对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权(即读写保护)。对每个内存区域指定一个键值和若干禁止的访问方式，进程中也指定键值，如果访问时键值不匹配而且是被禁止的访问方式，则出错；环保护：处理器状态分为多个环(ring)，分别具有不同的存储访问特权级别(privilege)，通常是级别高的在内环，编号小（如0环）级别最高；可访问同环或更低级别环的数据；可调用同环或更高级别环的服务。页面的共享与保护共享页面：在物理页面表中有引用计数。只能共享不被修改的页面。这对用户应用是透明的，完全由操作系统控制，目的在于减少系统内的物理页面总数。当共享页从内存中淘汰或重新装入内存时，共享该页的所有作业进程的页表中的相应页表项必须被同时更新。写时复制(copyonwrite)：如果一个进程要改写共享页面，则先把该页面复制一份，让该进程访问复制后的页面，而让其他进程访问复制前的页面。通过引用计数(referencecount)来描述存储区的共享，引用计数表示共享它的进程的数目：2.存储共享页面的共享与保护段式存储管理基本思想：将程序的地址空间划分为若干个段(segment)，程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。需要CPU的硬件支持。段式存储管理地址结构如下：段号S段内位移量d通过段表实现逻辑地址到物理地址的映射段表结构：该段在内存中的首地址；段长；访问权限，段存在位（该段是否在内存）段表中各表项按段号从小到大顺序排列B0SA0NY0LX0PM0K逻辑段号01234作业1的地址空间10003200500060008000PKSLN主存K

3200P1500L6000N8000S5000长度

段地址01234操作系统段式存储管理地址转换段式存储管理程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段。可以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进行共享，包括通过动态链接进行代码共享优点：没有内部碎片，外部碎片可以通过内存拼接来消除。便于改变进程占用空间的大小。便于模块化，便于处理共享问题。缺点：进程全部装入内存。段的最大长度受限于主存空间，开销大。段式存储管理页式管理和段式管理的比较分页是出于系统管理的需要，分段是出于用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。页大小是系统固定的，而段大小则通常不固定。逻辑地址表示：分页是一维的，各个模块在链接时必须组织成同一个地址空间；分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。是页式和段式存储管理的结合。段页式存储管理为了获得分段在逻辑上的优点和分页在管理存储空间方面的优点采用段页式存贮管理。1.将逻辑地址空间以段划分－－段式特征2.将物理地址空间以页划分－－页式特征3.每一段的地址空间划分为页存储管理的分配单位是：段，页逻辑地址的组成：段号，页号，页内偏移地址。将段内地址d分为段内页号和页内偏移地址两部分。地址变换：先查段表，再查该段的页表。缺段中断和缺页中断。地址结构：SPWS：段号 P：页号 W：页内偏移地址d段页式存储管理优点：具有分段存储管理和分页存储管理的全部优点；为用户提供了大量的虚拟存储空间，提高内存的利用率。对大、中型计算机来说，是使用最广泛、最灵活的一种存储管理。缺点：增加了硬件成本、系统复杂性和管理上的开销；表格占用了大量的存储空间；仍存在内部碎片，存在系统颠簸的危险。段页式存储管理文件管理文件管理的功能文件系统概念文件结构与存取方法文件目录管理文件存储空间管理文件使用一般模型文件共享、保护和保密文件管理的功能目标：使用方便，便于共享，安全可靠功能：提供用户对文件操作的命令；实现文件的“按名存取”。提供用户共享文件的机制；提供文件的存取控制的机制，保障文件及文件系统的安全性；管理文件的存储介质.文件系统概念文件：逻辑上具有完整意义的数据或信息的集合。文件名：一个有限长度的字符串。文件名·[文件扩展名]按文件性质和用途分：系统文件库文件用户文件按保护级别分：只读文件读写文件执行文件不保护文件有效地分配文件存贮器的存贮空间(物理介质)提供一种组织数据的方法(按名存取、逻辑结构、组织数据)提供合适的存取方法(顺序存取、随机存取)从系统的角度看：文件系统是一个负责文件存储空间管理的机构。从用户的角度看：文件系统是用户在计算机上存储信息和使用信息的接口。文件系统概念文件结构与存取方法逻辑文件：从用户观点出发，所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件及其介质的物理特性，又称为文件组织。物理文件：文件的存储结构，是文件在外存上存储组织形式，与存储介质的存储特性有关。逻辑结构：指用户思维中文件的结构。物理结构：指文件在存储介质上的结构（或存储组织）。文件的存储介质：磁盘（软盘、硬盘、光盘）、磁带，磁鼓。目前文件的物理结构主要是指磁盘上文件的结构。文件的逻辑结构记录式文件（有格式文件）：是一种有结构的文件。由一个或多个记录组成。

以逻辑记录为单位进行存取。定长记录文件：文件中所有记录的长度相同。变长记录文件：每个记录的长度可以不同无结构的流式文件（无格式文件）：是有序字符的集合，文件的长度等于该文件包含的字符数。流式文件不分成记录，而是直接由一连串信息组成。UNIX、DOS、WINDOWS系统中的普通文件都是流式文件。文件结构与存取方法l1记录1l2记录2(a)变长指示记

录长度l1l2记录1记录2ll(b)定长记录文件变长：每个记录的头几个字节存储记录长度文件结构与存取方法优点：

在空间利用上比较省，没有额外的说明和控制信息。对流式文件而言，它是按信息的个数或以特殊字符为界进行存取的。流式文件文件结构与存取方法文件的物理结构文件存储介质格式化后就分成许多大小相等的单位－－存储块（物理盘块）。一般来说，每个物理块是一个磁盘的扇区，512字节。每个存储块有个编号，称为物理块号。文件的物理结构指文件在存储介质上结构，目前有三种基本结构:连续结构链接结构索引结构连续结构连续文件是一种连续结构的文件，对每个文件要求存放在存储介质上的连续的物理块中。存储空间利用率不高。类似于存储管理中的分区，适用于变化不大的顺序访问的文件。在UNIX系统中仍保留了连续文件结构。优点：结构简单，实现容易，不需要额外的开销。缺点：用户创建文件时要给出文件的大小；不利于文件的动态增加和修改；链接结构链接结构是按顺序由链接的块组成的。即每个物理块的最末一个字(或第一个字)作为链接字，它指出后继块的物理地址。链首指针存放在该文件目录中。文件的结尾块的指针为“NULL”。不要求连续存放。对于记录式文件一块中可包含一个逻辑记录或多个逻辑记录，也可以若干物理块包含一个逻辑记录。存储空间利用率高；文件创建时用户不必指出文件的大小；文件动态扩充和修改容易。顺序存取效率高，随机存取效率太低，如果访问文件的最后的内容，实际上是要访问整个文件。链接结构索引结构非连续文件存放文件索引表：每个文件有一个索引表，表中包括：逻辑块号，物理块号。访问文件时，根据文件的逻辑块号查文件索引表，找到对应的物理块号，然后，进行访问。索引结构即保持了链式结构的优点，又克服了其缺点（既能顺序存取，也可随机存储）索引结构是当代计算机操作系统中普遍采用的结构，如UNIX系统、LINUX系统。索引结构顺序存取：记录式文件中：严格按照物理记录排列的顺序依次存取。无结构的流式文件：从文件当前位置开始读写，然后根据当前位置的位移读写后继的信息。读写文件存储器上的一个物理块的方法。直接存取（随机存取）：按任意次序存取文件中的记录，而不是顺序的记录式文件中：对定长记录的顺序文件，可直接存取；对变长记录的顺序文件，需建立一张索引表，以指出每个记录的长度和起始位置，索引表按记录号顺序排列。无结构的流式文件：事先把该文件的现行位置指针设置到欲读写信息的起始位置。文件的存取方法l1记录1l2记录2(a)变长指示记

录长度l1l2记录1记录2ll(b)定长记录文件变长：每个记录的头几个字节存储记录长度，这里为2个字节文件的存取方法磁盘（磁鼓）磁带文件的物理结构

连续链表索引连续存取方法

顺序、直接顺序顺序、直接顺序文件结构、存储设备和存取方法之间的关系文件的存取方法文件目录管理

文件的组成一级目录二级目录多级目录文件的组成文件目录项：又称为文件控制块（F