计算机操作系统教程_第四版_(张尧学著)_清华大学出版社_第5章new存储管理.ppt

2)最近最久未使用算法(LRU) 3)最近最不常用算法(LFU) 4)最近未使用算法(NRU)5)二次机会算法(Second Chance) （2）分配和回收 （3）重定位和存储保护 程序大小为x i=1 分区i的长度? y 分区i的状态==0? 置分区i的状态=1 置进程PCB中程序位置=i 分配完成 i=i+1 i 分区数? x 最大分区的长度? 推迟装入，等待下次调度 提示：程序超过分区长度，不能装入！ 图5-6 固定分区的分配流程 y y y 能够支持多道程序设计 并发执行的进程数受分区个数的限制 程序大小受分区长度的限制 存在“碎片” 3.主要特点 减少碎片 用户区作为空闲区，根据程序实际需求量，分配空间，并可回收使用后的空间。 四、可变分区存储管理1.基本思想 （1）数据结构设计 可用表 空闲区链表 请求表 struct FreeNode { long start； //分区的起始地址 long length； //分区的长度 struct FreeNode *next； //向下指针 }*freePartitionsList； //空闲区链表头指针 2.实现关键 空闲区链表 （2）分配 动态分区 存储空间分配的基本策略 最先适应法(FF，First Fit) 最佳适应法(BF，Best Fit) 最坏适应法(WF，Worst Best Fit) 程序A、B、C和D，它们的虚拟地址空间大小分别是80K、30K、130K和25K。 （3）回收 合并判断 在回收一个分区时，系统中空闲区的个数变化情况是：满足图5-12(a)类型时，空闲区个数增加1个；满足图5-12(b)或(c)类型时空闲区个数不变；而满足图5-12(d)类型时，空闲区的个数反而减少1个。 （4）重定位及存储保护 动态重定位 界限寄存器法 存在外碎片(External Fragmentation)，降低了存储空间的利用率 分区个数和每个分区的长度都在变化 为进程的动态扩充存储空间提供可能 需要相邻空间区的合并，增加系统的开销 基本分配算法FF、BF和WF，在存储空间利用率上没有很大差别 3.主要特点 （1）存储空间连续分配，管理方法容易实现 （2）存在碎片，存储空间利用率不高(内碎片和外碎片的区别) 内部碎片：就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间； 外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。 从存储单元的状态看，内碎片是分配状态，外碎片是空闲状态 从长度看，内碎片的长度可能很大，但外碎片的长度往往比较小。 （3）程序大小受分区的限制 4.分区管理总结 对换技术是由操作系统实现，程序员或用户看不到进程的调出/调入过程 对换技术可以增加并发执行的进程数，或者使得当前运行的进程拥有更多的可用存储空间 5.对换(Swaping)和覆盖(Overlay) 覆盖技术(Overlay)是早期操作系统(DOS)采用的一种内存逻辑扩充技术 程序员：可覆盖结构设计 操作系统提供关于内存空间的分配、撤销和设置(Setblock)等存储管理的系统调用，以及程序装入或程序装入并运行等的进程管理的系统调用（也称为EXEC功能） （1）内存分块 五、分页存储管理1.基本思想 （2）进程分页 分页存储管理由操作系统和硬件共同实现 由虚拟地址a计算页号p和页内地址w的两种方法： p=ak, w = a p=a/b,w=a%b。 （3）非连续分配 分页存储管理又分为静态分页和动态分页两种 （1）位示图(bitmap)及其作用 假定某内存空间共256个块，机器字长为16位，那么，表示内存块使用状况的位示图，如图5-17所示。 2.静态分页的实现关键 假定，在位示图中的一个位用bitmap[i,j]表示，其中i 称为字号，表示第i行即第i个字；j称为位号，表示在第i个字中的第j位，这里规定从低位开始计算。如果位示图中的第i个字记为bitmap[i]，那么 bitmap[i,j]=(bitmap[i] j )1 位示图的一个位bitmap[i,j]表示的块号为b，可以计算得到b=字长*i+j 相反地，如果已知一个块的块号，那么，这个块在位示图中的位bitmap[i,j]，则有 i=b/字长，j=b%字长 空闲块链表 （2）页表(Page Table)及其作用 每一个进程都有一个页表，页表描述进程页与块的对应关系 页表的主要作用是重定位和存储保护 页表的建立和初始化过程-内存分配 （3）请求表 （4）重定位及存储保护 重定位过程，其步骤概括如下： 1