实存储器管理技术课件

实存储器管理技术8.1引言存储器包括内存（主存）和外存（磁盘）存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。内存在访问速度方面的发展：DRAM、SDRAM、SRAM等；硬盘技术在大容量方面的发展：接口标准、存储密度等；主存储器管理技术分为两大类实存储器管理虚拟存储器管理8.1引言存储器的物理组织、多级存储器存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。其依据是访问速度匹配关系、容量要求和价格。“寄存器-内存-外存”结构“寄存器-缓存-内存-外存”结构；微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；8.1引言快速缓存：DataCacheTLB(TranslationLookasideBuffer)内存：DRAM,SDRAM等；外存：软盘、硬盘、光盘、磁带等；8.1引言主存储器管理功能存储分配和回收：分配和回收算法及相应的数据结构。地址变换和重定位：可执行文件生成中的链接技术程序加载(装入)时的重定位技术进程运行时硬件和软件的地址变换技术和机构存储共享和保护：代码和数据共享地址空间访问权限（读、写、执行）存储器扩充：存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）8.2固定分区单道作业（单一固定分区）内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间使用界地址寄存器保护系统信息最简单，适用于单用户、单任务的OS优点：易于管理缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存单一连续区存储管理8.2固定分区多道作业主存分为固定大小的若干块，主存分区的数量不变，每个分区的大小也不变分区的信息由存储分块表（MBT）管理大小：以字节为单位位置：分区的起始地址状态：分区是否被使用使用界地址寄存器采用静态重定位固定分区(大小相同)固定分区(多种大小)8.3可变分区多道管理技术（动态分区）主存事先并不划分分区，而是在作业级如主存时，按作业大小建立分区，分给作业使用优点：没有分区内部碎片缺点：有外碎片；如果大小不是任意的，也可能出现内碎片。8.3可变分区多道管理技术（动态分区）需要解决三个问题：分配管理的数据结构（MBT）、存储分配算法、分区的分配和回收MBT组织方法存储分块表分开设置两个存储管理表空闲存储块链8.3可变分区多道管理技术（动态分区）MBT组织方法：存储分块表缺点分区个数不固定，所以需要的分块表的表长度不能确定，可能造成预留空间不足或浪费的情况分区增多时，查找空闲分区的时间长8.3可变分区多道管理技术（动态分区）MBT组织方法：两个存储分块表设置空闲分区表（FBT），提高查找速度序号分区大小(K)分区始址(K)状态132256可用216512可用……………………8.3可变分区多道管理技术（动态分区）存储分配算法最先匹配法(first-fit)：按分区的先后次序，从头查找，找到符合要求的第一个分区该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。下次匹配法(next-fit)：按分区的先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。8.3可变分区多道管理技术（动态分区）存储分配算法最佳匹配法(best-fit)：找到其大小与要求相差最小的空闲分区从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。最坏匹配法(worst-fit)：找到最大的空闲分区基本不留下小空闲分区，但较大的空闲分区不被保留。请求分配16K8.3可变分区多道管理技术（动态分区）存储分块分配和回收分配从头开始查找检索完否？返回m.size>u.size查找下一个m.size-u.size>size划出u.size分区整块分配修改有关数据NYNYNm.size—空闲分区大小u.size—请求分区大小size—不可再分割大小按分区分配算法8.3可变分区多道管理技术（动态分区）存储分块分配和回收回收：当一个进程运行结束，要释放内存，操作回收内存，并把它插入到空闲区链表中。根据回收区的位置，有四种情况需要处理：空闲区回收区回收区空闲区空闲区回收区空闲区回收区情况1情况2情况3情况48.3可变分区多道管理技术（动态分区）存储器紧缩和程序浮动因为存储块的动态分配和回收，会产生大量的碎片，这些碎片的总量很大，但每一个碎片都不足以容纳一个程序处理碎片的方法：存储器紧缩，就是把已经使用的空间移动到存储器的一端，而使碎片移动到另一端连接起来8K12K6K18K44K紧缩8.3可变分区多道管理技术（动态分区）存储器紧缩和程序浮动处理器紧缩的关键是内存中的程序要移动，把这称为程序浮动1000Load250011003653500移动后0Load25001003652500移动前8.3可变分区多道管理技术（动态分区）存储器紧缩和程序浮动解决程序移动产生的访问地址错误——动态重定位0Load250010036525002500相对地址0重定位寄存器0Load25001003652500+处理机存储器移动前8.3可变分区多道管理技术（动态分区）存储器紧缩和程序浮动解决程序移动产生的访问地址错误——动态重定位0Load250010036525002500相对地址10000重定位寄存器10000Load25001010036512500+处理机存储器移动后8.3可变分区多道管理技术（动态分区）动态重定位分配算法在一个分区释放后立即移动当请求得不到满足时再移动请求分配u.size分区检索空闲分区链找到m.size≥u.size按动态分区分配方式进行分配空闲分区总和≥u.size进行“紧凑”返回分区号及首址无法分配返回yNYN8.4多重分区即一个程序可以占据主存中不连续的多个分区——可以解决碎片问题需要硬件支持（多对界地址寄存器）管理复杂多重分区的思想和实现类似于虚拟段式存储8.5简单分页把主存分成许多同样大小的存储块，并把这种存储块作为存储分配的最小单位8.5简单分页实现方法：把内存空间划分成若干大小相同的物理块，这些物理块叫“页架”(frame)，并依次编以连续的页架号0,1,2…..把用户程序的地址空间划分成与页架大小相同的部分(fixedsizechunk)，把它们叫“页”（不同系统的页大小不同）用户的逻辑地址表示为一个数对（p,d），其中p是页号，d是页内相对地址8.5简单分页实现方法：给定虚地址（逻辑地址）A，页面大小L，则p=INT[A/L]，d=[A]modL，其中INT是向下取整，mod是取余。例如L=2KB，A=2506B，则p=1，d=506，表示为(1,506)8.5简单分页主存分配把用户程序的任一页分配到内存中的任一帧，从而实现非连续的内存分配。问题如何管理、如何进行地址变换。8.5简单分页进程A页表00页号块号1124354859…………012345678内存9程序A0页1页2页3页4页5页n页程序B0页1页2页3页4页5页m页进程B页表02页号块号132637…………页表：实现页号到物理块号的映射。8.5简单分页地址组成：页号P+(页内地址)位移量d例如：32位地址，0~11为偏移量，12~31为页号，最大可以有1M页，每页4KB。地址结构：页号P位移量d12110318.5简单分页页面大小的确定分页系统中，页面的大小是由硬件的地址结构所决定的。机器确定、页面大小就确定。通常页面大小采用2的幂次（为什么？）影响因素：页面↓→内部碎块↓、内存的利用率↑页面↓→页表↑、占用内存↑页面↓→页面的换出换入效率↓。8.5简单分页计算机类型页面大小(B)IBMAS/400VAXIntel80386Motorola6803051251240964096常见机型页面8.5简单分页地址转换分页存储系统中，地址变换机构的任务是把逻辑地址中的页号转换为内存中物理块的块号。注意：页面大小与页框大小一致，无须进行页内地址转换。实现转换：借助于页表。页表的实现：寄存器：变换速度快、成本高，适应小型系统。页表驻留在内存：速度较低、成本低，适应大系统。8.5简单分页地址转换实现将逻辑地址的页号取出以页号为索引查找该进程的页表，找出和该页号对应的页架号用页架号和逻辑地址的页内相对地址拼接，得到的就是物理地址8.6简单分段分段管理思想的引入在分页管理中，只按页面大小划分程序，没有考虑程序的逻辑功能结构一个程序包含多个逻辑上相对独立的功能模块，也可能包含多个子程序，这些模块或者子程序完成相对独立的功能在分页系统中，一个逻辑段可能被分到不同的页内，不利于执行8.6简单分段分段的实现把作业的地址空间按逻辑功能划分若干段，每一段定义一组逻辑信息：段名、段的长度段名：用段号来替代。段的长度：不确定，由相应的逻辑信息组的长度决定。逻辑地址：SegmentNumberOffset311615064K个段64KB长度8.6简单分段主存分配以段为单位，每一段分配一个连续的主存分区，一个程序的各段所分到的主存分区不要求是连续的请考虑：程序的段是在什么时候由谁划分出来的？8.6简单分段段表：记录逻辑段与内存物理位置的对应映射关系。段号段长基址030K40K120K80K215K120K段表(MAIN)=0(x)=1(D)=2内存空间作业空间0(MAIN)=00(X)=10(D)=240K80K120K8.6简单分段段的地址转换段表始址段表长度段表寄存器2段号段内偏移量100+6K1K04K60018K500292002003基址段长段号段表+越界中断+8292物理地址012内存空间8K分页与分段的区别分块方式使用碎片长度目的分页存储管理物理分块，系统决定对程序员是不可见，使用简单每个进程只有一个内部碎片，大小不超过1页固定提高内存的利用率分段存储管理逻辑分块，大小与信息块有关，由编译系统划分对程序员可见，使用方便，但难度大每个进程会产生多个外部碎片不确定便于信息保护与共享，方便用户实存储管理技术的特点：程序要整体装入，一个程序在没有全部装入主存之前不能运行。请同学们课后分析一下这种技术的优缺点8.7内核主存管理即对操作系统内核程序占用的主存区的管理现代操作系统的内核程序大都驻留在ROM里但是一些系统内核程序在运行时，需要一些存储空间（属于内核存储区）存放临时信息预留一定大小的空间动态管理——内核主存分配器8.7内核主存管理二次幂空闲表分配器伙伴系统SVR3延迟伙伴算法8.7内核主存管理

（二次幂空闲表分配器）把内核存储区分成一些固定大小的空线块，如1KB,2KB等，每个空闲块有一个字长的头结构（不属于可用空间）用来存放链指针使用一组空闲表，每个表存放某一特定尺寸的空闲块内核程序需要存储区时，根据它需要的大小给它分配一个合适的空闲块见Page162图8.148.7内核主存管理

（二次幂空闲表分配器）优点快速分配和式访主存缺点因为要存放头结构，浪费空间存储块不能合并，不能满足对大主存块的要求8.7内核主存管理（伙伴系统）思想通过不断的对分大主存块来获得小主存块，并尽可能合并空闲块，但必须在伙伴的关系上才能合并伙伴：当一个主存块被对分后，每一部分称为另一部分的伙伴8.7内核主存管理（伙伴系统）概念伙伴系统是通过对分大空闲块来获得小空闲块，对分生成的两个空闲块互称伙伴，合并必须在伙伴之间进行系统中规定最小分配单位，通常为32byte或64byte系统使用位图位互主存中每一个最小单位的使用情况，1表示正在使用，0表示空闲系统为每一种可能大小的空闲块维护一个空闲链表缺点会有频繁的对分和合并8.7内核主存管理（伙伴系统）概念系统启动时，只有一个大的2次幂大小的空闲块。将请求的大小取整，然后寻找对应的空闲链表，如果有空闲块，则分配，否则将一个大空闲块对分，直到与请求大小相符合确定伙伴的方法是根据空闲块的基地址和大小1MBA：请求100K128KB：请求240K256K128KC：请求64K256K128K6