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

177,94,56,106,87,150。试给出采用扫描调度(SCAN)算法,磁头移动的顺序和移动总量(总磁道数)。 答:磁头由内往外运动,移动的顺序: 127 -> 132 -> 150 -> 177 -> 110 -> 106 -> 94 -> 87 -> 82 -> 56 移动距离: 5 18 27 67 4 12 7 5 26 移动总量(总磁道数):171 请求访问次序 1 2 3 4 5 6 7 8 9 平均寻道 总磁道 2. 简述什么是虚拟储存器。 答:虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定,其运行速度接近于内存速度,而每位的成本却又接近于外存。(参见课本4.6小节,只要答对基本要点即可)

磁道号 82 110 132 177 94 56 106 87 150 真正访问次序 8 4 1 3 6 9 5 7 2 19磁道 171磁道 移动距离(磁道数) 5 67 5 27 12 26 4 7 18

第6章

1.文件系统的功能:OS中实施文件管理的机构称为文件管理系统 实施文件存储空间的分配与回收(即磁盘管理)

实现文件名到文件空间的映射

实现用户要求的各种文件操作(如存、取等) 提供文件共享能力以及保护与保密措施

2.外存分配方法

(1)连续外存分配:指为文件分配一组相邻接的盘块 优点: 顺序访问容易

一次大批量数据的访问速度较快 缺点:

要求有连续的外存空间(同样存在“碎片”问题) 必须事先知道文件的长度

(2)隐式链接:将链接指针直接放在盘块数据区中

优点:①不存在“碎片” ②不需要连续外存空间③不需要事先知道文件长度 缺点:

①只适合于顺序访问,不适合随机访问(低效) ②可靠性差(中间任何指针出错,整个链断开)

③数据区大小不等于2的次幂(指针占用数据区空间),不利于与内存页对应

(3)显式链接:将用于链接文件各盘块的指针,显式地存放在一张链接表(文件分配表FAT)中 优点:

①FAT占空间小,可以调入内存 ②查找速度快,适合随机存取

同样不存在“碎片”,不需要连续外存空间 不需要事先知道文件长度 缺点:

①FAT需要占用外存空间

②FAT需要占用较大内存空间:对于大的硬盘,每次只调取部分FAT进入内存 ③不能高效直接存取

(4)索引分配

每个文件先分配一个索引块

当已分配的索引块装不下所有盘块号时,再分配新的索引块 优点:方便直接存取 缺点:需要更多外存空间 混合索引:

直接地址+一级间址+二级间址+三级间址=10*4KB+1K*4KB+1K*1K*4KB+1K*1K*1K*4KB

3.目录的功能:a实现按名存取 b.提高对目录的检索速度 c.文件共享 d.允许文件重名

4.目录管理的方法

(1)单级目录:优点:简单

缺点:查找速度慢,不允许重名,不便于实现文件共享

(2)两级目录:主文件目录(MFD)→用户文件目录(UFD)

优点:

①提高了检索目录的速度

②在不同的用户目录中,可以同名 ③不同用户可共享文件 缺点:

①不同用户之间不能互相访问 ②用户不能继续建立自己新的子目录 (3)树形目录结构:现在用的目录结构

具有三级或三级以上的目录结构称为树型结构的目录

树型目录结构中,允许在任何一级子目录中,再创建新的子目录

第5节文件存储空间的管理 6.空闲表法

空闲盘区的分配算法 (1)首次适应算法 (2)循环首次适应算法 (3)最佳适应算法 (4)最坏适应算法 空闲盘区的回收算法 对邻接盘区进行拼接

7.空闲链表法 (1)空闲盘块链表法 (2)空闲盘区链表法

8.位示图法:用二进制表示盘块使用情况

变换盘块号(n)

n=i*8+j(找到第i行第j列) 修改位示图 优点:

①位示图占用空间较小,可以调入内存 ②分配和回收操作简单、有效

9.成组链接法 (1)盘块的分配

①若s.free=1,则将栈底盘块号所对应的盘块(内容)调入空闲盘块号栈,并将该盘块分配出去 ②否则,直接将栈顶盘块号所对应的盘块分配出去,并将s.free递减1

(2)盘块的回收

①若s.free=N,则将空闲盘块栈内容写入新释放的盘块中,并使s.free=1,且将该盘块号作为栈底

②否则,s.free递增1,将该盘块号作为栈顶

成组链接法举例

某一操作系统采用成组链接法管理磁盘空闲空间。为简单起见,假定3块一组,并在某一时刻,空闲盘块号栈的内容从S.free开始依次为2,6,3,第6块中的管理信息为3,1,2,4。问: 分配3块,哪3块被分配出去?空闲盘块号栈的内容(从S.free开始)是什么?

回收第7,8块,空闲盘块号栈的内容(从S.free开始)是什么?如此时有空闲盘块的内容改变,是哪块?变为什么? 解:

成组链接法举例[分配3块]

先分配第3块,空闲盘块号栈的内容从S.free为:1,6

再分配第6块时,先将第6块的内容3,1,2,4调入空闲盘块号栈中,然后将第6块分配出去; 再分配第4块,空闲盘块号栈的内容从S.free为:2,1,2。

因此,分配3块,依次是第3、6、4块被分配出去,最后空闲盘块号栈的内容从S.free为:2,1,2。

成组链接法举例[回收第7、8块]

先回收第7块,空闲盘块号栈的内容从S.free为:3,1,2,7

再回收第8块时,先将空闲盘块号栈的内容写入第8块中,然后将第8块放在栈底。

因此,回收第7、8块,空闲盘块号栈的内容从S.free为:1,8;第8空闲盘块的内容被改变,其内容为3,1,2,7。

10.文件共享

联系客服:779662525#qq.com(#替换为@)