上海大学操作系统2复习资料

1、存储管理的主要功能：l 地址转换（逻辑地址转为物理地址l 存储器的分配和回收l 存储保护l 存储扩充地址转换（重定位）逻辑地址物理地址；多道程序中编译程序不可能预支经编译后所得到的目标模块应放在内存何处，不能用绝对装入，要用可重定位装入。l 静态转换：在装入时对目标程序中指令和数据地址进行修改l 动态转换n 地址转换推迟到真正执行时n 静态的不允许程序运行时在内存中移动位置，动态的可以分配方式n 连续分配n 单一连续分配u 单个程序独占n 固定分区分配u 划分分区：分区大小相等、不等u 内存分配：按大小排序，分区使用表u 优点：能在内存中装入多道程序u 缺点：存储空间浪费n 动态分区分配u 数

2、据结构：空闲分区表；空闲分区链u 动态分区分配算法：l 顺序搜索算法（用于不太大的系统）n 首次适应：空闲分区地址递增，从链首开始寻找，满足要求后切割u 优点：优先利用低址，保留高址大空闲区，为以后到达的大作业分配大的内存空间创造了条件u 缺点：低址部分被不断划分，留下许多难以利用的、很小的空闲分区n 循环首次适应：空闲分区地址递增，从上次找到的下个空闲分区开始u 优点：避免低址部分留下太多空闲分区u 缺点：缺乏大的空闲分区n 最佳适应：空闲分区大小递增，找到的第一个u 优点：避免大材小用u 缺点：每次切割剩下的都是最小的，会留下难以利用的碎片n 最坏适应：找最大的一个空闲分区u 优点：使剩下

3、的空间不会太小，产生碎片的可能性最小，对中小作业有利u 缺点：缺乏大的空闲分区l 索引搜索算法（大中型系统）n 快速适应：每一类相同容量的分区，单独设一个链表，查找时先去索引表，然后去链表取下第一块即可（可将其理解为一个菜单）u 优点：提高搜索速度u 缺点：分区归还主存时较为复杂；分配空闲分区时是以进程为单位的，一个分区只属于一个进程，存在浪费（以空间换空间）n 伙伴系统：内容看书吧u 时间性能 ：劣于快速适应，优于顺序搜索u 空间性能：劣于顺序搜索优于快速适应n 哈希算法u 直接根据分区大小利用哈希函数计算u 分配内存：m.size-u.sizeTL则段号太大，访问越界，产生越界中断信号n

4、分页分段管理比较分页分段大小固定、硬件决定不固定、程序决定信息信息的物理单位独立的信息逻辑单元，更便于共享目的提高内存利用率方便程序设计逻辑地址一维，页号+页内地址二维，段号+段内地址n 段页式管理u 既有分段系统的易于实现、分段可共享、易于保护、动态链接等优点，也能像分页系统那样，很好的解决内存的外部碎片问题u 先将用户程序分成若干段，再把每个段分成若干页，并为每个段赋予一个段名u 逻辑地址：段号+段内页号+页内地址（二维）u 数据结构：每个进程一张段表（页表地址和页表长度），每个段一张页表，位视图u 地址转换：硬件（段表寄存器）实现的动态地址转换机构，访问3次内存u 第一次访问内存中的段表

5、，得到页表始址；第二次访问内存中的页表，去除该页所在的物理块号，并将该号与页内地址一起形成指令或数据的物理地址，第三次访问从第二次访问得到的地址中取出指令或数据。常规存储器l 一次性：作业必须一次性装入内存后方能运行l 驻留性：作业被装入内存后，整个作业都一直驻留在内存中，其中任何部分都不会被换出，直至运行结束l 局部性原理n 在一较短时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。n 时间局限性：若程序的某条指令被执行，则不久后这条指令可能再次被执行，若某条数据被访问过，则这条数据可能再次被访问。原因是程序中存在着大量的循环操作n 空间局限性：一旦程序访问了某

6、个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址可能集中在一定的范围内。典型情况是程序的顺序执行虚拟存储器l 定义：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。逻辑容量由内存容量和外村容量之和决定，运行速度接近于内存速度，成本又接近外存l 特征n 多次性：一个作业的程序和数据无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存运行，只需将当前需要运行的那部分程序和数据装入内存即可n 对换性：一个作业的程序和数据，无需在作业运行时一直常驻内存，而是允许在作业的运行过程中进行换进换出n 虚拟性：用户看到的内存容量远大于十级内存

7、容量l 实现方法n 分页请求系统n 分段请求系统请求分页l 数据结构n 页号、物理块号、状态位P、访问字段A、修改位M、外存地址u 状态位：指示该页是否已调入内存u 访问字段：记录本页在一段时间内被访问的次数或时多久未被访问，提供给置换算法进行换进换出时的参考u 修改位：标识该页是否被修改过，供置换页面参考u 外存地址：通常时物理块号，供调入该页时参考l 动态地址转换n 硬件+软件n 缺页中断l 内存分配n 固定分配局部置换：进程物理块固定；缺页时只能从分配给该页的n个页面中选出一页换出，然后再调入一页，以保证分配给进程的内存空间不变n 可变分配全局置换：进程运行期间分配的物理块可调整；缺页则

8、将空闲的物理块分配给该进程，分配给该进程的内存空间增加n 可变分配局部置换l 调入策略n 预调页：预先估计在不久后便会被访问的页面，将其调入内存n 请求调页：进程发现需要访问某程序和数据，但此页面不在内存，便立即提出请求，由OS将需要的页面调入内存n 从哪里调入u 对换区：系统拥有足够的对换区空间（进程运行前将与该进程有关的文件从文件去拷贝仅对换区u 文件区：系统缺少足够的对换区空间u UNIX方式：放在文件区的直接从文件区调入；曾经用过又换出的，由于放在对换区，直接从对换区调入；由于unix系统允许页面共享，某进程请求的页面若被其他进程调入内存，可直接使用n 抖动：刚被换出的页面很快又要被使

9、用，需要重新调入，此时再选一页调出；而此刚被调出的页面又很快要被访问，又需要调入，如此频繁的更换页面，以致一个进程在运行中把大部分时间花费在页面置换工作上，称该进程发生了“抖动”u 预防方法：采用局部置换；把工作集算法融入处理机调度；利用“L=S”准则调节缺页率；选择暂停的进程n 影响缺页率的因素：置换算法、页面大小、进程分得的页块数量，进程访问内存的离散程度。n 工作集u 在某段时间间隔内，进程实际要访问页面的集合l 置换算法n OPT最佳置换算法：理想化，性能最好，实际无法实现，以其作为标准衡量其他算法的优劣n FIFO先进先出算法：最直观，性能最差，实际应用极少n LRU最近最久未用算法

10、n NRU 最近未用算法n LFU 最近最少使用算法请求分段l 段的大小受到物理内存配置的限制l 便于实现段的动态链接l 便于实现段的共享：共享段表l 段的置换时，有时还要“紧凑”合并空闲分区才能换入要装入的段。文件系统l 文件系统主要功能n 文件目录管理n 提供文件操作的接口n 文件存储空间的管理n 文件的共享和文件保护、保密l 文件：文件是指由创建者所定义的、 具有文件名的一组相关元素的集合l 文件系统：从用户角度看，是实现“按名存取”文件的软件。l 逻辑文件（逻辑结构）：用户所看到的n 文件是由一系列的逻辑记录组成的，是用户可以直接处理的数据及其结构，独立于文件的物理特性，又称问文件组织n 无结构的字符流文件n 有结构的记录文件l 物理文件（物理结构）：文件在存储介质上的结构，用户看不到l 逻辑结构与物理结构都会赢下对文件的检索速度l 文件目录：文件控制块的集合，UNIX中，文件目录是文件名与inode号构成的目录项的集合。l 目录文件：文件的内容是文件的目录（DOS中的每个子目录是一个目录文件，UNIX中的每个目录都是一个目录文件）l 目录管理的要求n 实现“按名存取”。