深圳大学2015年操作系统复习提纲-吴少滨整理 下载本文

优点:保留高地址部分的大空闲区

缺点:低地址存在很多小的、无法利用的空闲分区,且查找时间较长 b.首次适应循环算法(CF):从上次找到空闲分区的下一个分区开始,按序选择第一个满足要求的内存区

优点:空闲分区在内存中均匀分布,查找时间少 缺点:缺乏大的空闲分区 c.最佳适应算法(BF):分区从小到大排列提高效率 优点:提高了内存使用效率,保留大的空闲区 缺点:存在许多很小的、无法利用的空闲分区 d.最坏适应算法(WF):在整个空闲分区中查找最大空闲分区分割给作业(分区从大到下) 优点:不产生很小的碎片,查找效率高 缺点:缺乏大的空闲分区 e.快速适应算法(QF)

将空闲分区按大小分类,同一类设立一个空闲链表,根据进程长度寻找容纳它的最小空闲区链表

优点:查找效率高,不分割空闲去,保留大分区 缺点:算法复杂,开销大

(4)动态重定位分区分配 ①紧凑(拼接):空闲分区的搬迁及合并 ②动态重定位:要有动态定位机制支持 考了具体的内容的方法

6.对换

对换是指把内存中暂不能运行的进程,或暂时不用的数据,换出到外存上,以腾出内存空间 整体对换:以进程为单位(挂起操作) 部分对换:以页或段为单位(虚拟存储器)

7.对换空间的管理

将外存分为文件区和对换区 对换区是连续的外存存储区

8.离散分配方式主要包括:分页存储管理、分段存储管理、段页式存储管理

9.内存物理块与进程页面:大小相等,页面可任意存放在任何物理快中,最后一页可不放满。 10.进程地址与页面地址

11.地址转换

(1)基本地址变换机构

有一基本分页存储管理系统,页面大小为1024B,地址长度为16位,请问该系统共有多少内存块?写出逻辑地址8230H的页号和页内地址;如果该页对应的内存块号为18H,求该逻辑地址对应的物理地址。 ①系统地址长度为16位;

? 现每页大小为1024B = 210B,即页内地址占10位; ? 因此系统中可表示页码的位数为:16-10=6位,即系统中内存块数为:26 = 64(块)。 ②逻辑地址8230H展开成二进制为:1000,0010,0011,0000B

? 页内地址占后10位,其余高位为页号; ? 因此,页内地址为:10,0011,0000 = 230H; ? 页号为:10,0000 = 20H。

③现该页对应的内存块号为18H,表示成二进制为:0001,1000B;

? 块内地址与页内地址相同,即:10,0011,0000;

? 将内存块号与块内地址合并后,得:0110,00 10,0011,0000B = 6230H。 缺点:访问一次逻辑地址,必须两次访问内存。

第一次访问内存(即访问页表)为取得逻辑地址对应的内存物理地址 第二次访问内存为取得逻辑地址中的数据

(2)具有快表的地址变换机构:内存也差,也到快表查 如果内存与快表不是同时进行:成功则只用访问一次内存120s,失败则要访问两次内存220s。

12.两级页表

有一基本分页存储管理系统,内存块大小为4096Bytes,每个块号占用4个Bytes,如果页表也以离散方式放在内存(块)中,求采用一级页表和两级页表,系统能支持文件的逻辑空间最多为多少?假如逻辑地址为123456H,求页内地址和外层页号。

? 每个内存块占4Bytes,即每个页表项占4B ? 每个内存块大小为4096Bytes,

? 每个内存可放下最多4096/4=1024个页表项

? 采用一级页表能支持文件的逻辑空间最多为:1024x4096=4MBytes

? 采用二级页表能支持文件的逻辑空间最多为:1024x1024x4096=4GBytes ? 4096占用12bits,即页内地址占12bits ? 1024占10bits,即外层页内地址占10bits ? 123456H=0001,0010,0011,0100,0101,0110b ? 页内地址=后12bits=0100,0101,0110b=456H ? 外层页号=(12+10)bits以上地址=00b=0H

13.分段存管理的目的:方便编程、分段共享、分段保护、动态链接、动态增长 14.分段地址结构:作业的地址是二维结构,

16.

17.信息共享:段是信息的逻辑单位,在各自的段表,标上相同的段基址和段长度即可共享。

18.分页和分段的主要区别

页是信息的物理单位(满足系统管理的需要) 段是信息的逻辑单位(满足用户的需要) 页的大小固定(由系统决定) 段的大小不固定(由用户决定) 分页的作业(进程)地址是一维的 分段的作业(进程)地址是二维的

19.段页式管理的优点:既节省内存空间,提高内存分配的效率,又兼顾用户编程的需要

20.段页式地址变换机构

当进程要访问某个逻辑地址时,先取得段号 如果段号大于段表长度,越界错误 将段表始址与段号相加,得段表中位置 从段表中相应位置,得到该段页表的首址 将段内页号与页表首址相加,得页表中位置 从页表中相应位置,得到物理块号p

将块号p与页内地址d组合成物理地址 练习

(1)有一基本分页存储管理系统,内存块大小为512Bytes,每个块号占有4个Bytes,如果页表也以离散方式存放在内存中,求采用三级页表,系统能支持文件的逻辑空间最多为多少。假如逻辑地址为15C3B6AH,求页内地址和外层页号。

每个内存块可以放512/4=128个内存块号。采用三级页表,系统能支持文件的逻辑空间最多为128*128*128*512B = 16*8*128*64*2*512B = 16*1K*64*1KB=1K*1K*1KB=1GB。 假如逻辑地址为15C3B6AH,则转化为二进制是:1,0101,1100,0011,1011,0110,1010 页内地址占(512=29)9位,为1,0110,1010=16AH

每层页号需用(128=27)7个比特存储。首层页号为0011,101,二层页号为101,1100,外层页号为10,即2H。

(2)段页式存储器管理系统中,某作业的段表、段内页表格式如下,页的大小为1K,现有逻辑地址[2]<2248>(十进制),求其对应的物理地址。

逻辑地址[2]<2248>,则页号为:2248/1024=2,找到321块2号页表块号为116,页内地址2248 mod 1024=200 (整除取余数),对应的物理地址为:116*1024+200=118984 (1D0C8).

21.虚拟存储器 概念:

虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定,其运行速度接近于内存速度,而每位的成本却又接近于外存。

特征:多次性、对换性、虚拟性

22.虚拟存储与实存的区别

23.局部性原理:程序执行具有局部性特征,即在一较短时间内,程序的执行仅限于某个部分;访问的存储空间也局限于某个区域。 (1)空间局部性 (2)时间局部性

24.虚拟存储器管理策略:调入策略、分配策略、淘汰策略

25.请求分页存储管理: