玩 转 数 据 结 构
刘 财 政第七讲 高阶专题考点二: 存储器管理专题
虚拟存储器考点二: 存储器管理专题
1. 某计算机存储器按字节编址,虚拟(逻辑)地址空间大小为16MB,主存(物
理)地址空间大小为1MB,页面大小为4KB;Cache 采用直接映射方式,共8行;
主存与 Cache 之间交换的块大小为32B。系统运行到某一时刻时,页表的部分内
容和 Cache 的部分内容分别如题a 图、题 b 图所示,图中页框号及标记字段的内
容为十六进制形式。考点二: 存储器管理专题
请回答下列问题。
(1)虚拟地址共有几位,哪几位表示虚页号?物理地址共有几位,哪几位表示页
框号(物理页号)?
某计算机存储器按字节编址,虚拟(逻辑)地址空间大小为16MB,主存(物理)
地址空间大小为1MB,页面大小为4KB;
逻辑地址位数:log 16M = 24位
2
物理地址位数:log 1M= 20位
2
页内地址位数:log 4K= 12位
2
LA 页号(12) 页内地址(12位)
块号(8) 页内地址(12位)
PA考点二: 存储器管理专题
请回答下列问题。
(2)使用物理地址访问 Cache 时,物理地址应划分成哪几个字段?要求说明每
个字段的位数及在物理地址中的位置。
在直接映射方式下的主存结构如表所示,
主存标记 Cache块号(行号) Cache(主存)块内地址
Cache被分为8个块,那么Cache块号是3位;
Cache块大小是32B ,则块内地址5位。
因此主存标记是20-5 - 3=12(位)
主存标记 Cache块号(行号) Cache(主存)块内地址
(12位) (3位) (5位)考点二: 存储器管理专题
(3)虚拟地址 001C60H 所在的页面是否在主存中?若在主存中,则该虚拟地址
对应的物理地址是什么?访问该地址时是否 Cache 命中?要求说明理由。
LA 页号(12) 页内地址(12位)
001C60H 中虚页号为 001H=1,查页表知其有效位为 1,在内存中;该物理地
址对应的也表项中,页框号为 04H 故物理地址为 04C60H;考点二: 存储器管理专题
(3)虚拟地址 001C60H 所在的页面是否在主存中?若在主存中,则该虚拟地址
对应的物理地址是什么?访问该地址时是否 Cache 命中?要求说明理由。
在直接映射方式下的主存结构如表所示,
主存标记 Cache块号(行号) Cache(主存)块内地址
(12位) (3位) (5位)
物理地址 04C60H = 0000
0100 1100 0110 0000,在
直接映射方式下,对应的行号
为 3,有效位为 1 但是标记位
为 105H≠04CH 故不命中。考点二: 存储器管理专题
(4)假定为该机配置一个 4 路组相联的 TLB 共可存放 8 个页表项,若其当前内
容(十六进制)如题 c 图所示,则此时虚拟地址 024BACH 所在的页面是否存在
主存中?要求说明理由。
组相联映射方式
标记 TLB组号(C位) 页内地址
逻辑地址
每一个线性地址块都可通过模运算对应到唯一的一组TLB表项
这样只需进行一次比较
TLB组号 = 页号 mod 2C考点二: 存储器管理专题
(4)假定为该机配置一个 4 路组相联的 TLB 共可存放 8 个页表项,若其当前内
容(十六进制)如题 c 图所示,则此时虚拟地址 024BACH 所在的页面是否存在
主存中?要求说明理由。
一个4路组相联的TLB,共可存放8个页表项,则共有2组,组号是1位。则
标记是12-1=11位
标记 TLB组号(C位) 页内地址
(11位) (1位) (12位)
逻辑地址考点二: 存储器管理专题
(4)假定为该机配置一个 4 路组相联的 TLB 共可存放 8 个页表项,若其当前内
容(十六进制)如题 c 图所示,则此时虚拟地址 024BACH 所在的页面是否存在
主存中?要求说明理由。
标记 TLB组号(C位) 页内地址
(11位) (1位) (12位)
024BACH = 0000 0010 0100 1011 1010 1100H,
前 12 位为 0000 0010 0100,组地址位为 0,第 0 组中存在标记为 012H 的页,
其页框号为 1F,故 024BACH 所在的页面存在主存中。考点二: 存储器管理专题
2、某程序中有如下循环代码段 p:“for(int i = 0; i < N; i++) sum+=A[i];”。
假设编译时变量 sum 和 i 分别分配在寄存器 R1 和 R2 中。常量 N 在寄存器 R6
中,数组 A 的首地址在寄存器 R3 中。程序段 P 起始地址为 0804 8100H,对应
的汇编代码和机器代码如下表所示。考点二:存储器系统专题
执行上述代码的计算机 M 采用 32 位定长指令字,其中分支指令 bne 采用如下
格式:
OP 为操作码;Rs 和 Rd 为寄存器编号;OFFSET 为偏移量,用补码表示。请回
答下列问题,并说明理由。
假设对于题中的计算机 M 和程序 P 的机器代码,M 采用页式虚拟存储管理;P
开始执行时,(R1)=(R2)=0,(R6)=1000,其机器代码已调入主存但不在 Cache
中;数组 A 未调入主存,且所有数组元素在同一页,并存储在磁盘同一个扇区。
请回答下列问题并说明理由。考点二:存储器系统专题
1)P 执行结束时,R2 的内容是多少?
(1) R2 里装的是 i 的值,循环条件是 i<N(1000),即当 i 自增到不满足这个条件
时跳出循 环,程序结束,所以此时 i 的值为 1000。考点二:存储器系统专题
2)M 的指令 Cache 和数据 Cache 分离。若指令 Cache 共有 16 行,Cache 和
主存交换的块大小为 32 字节,则其数据区的容量是多少?若仅考虑程序段 P 的
执行,则指令 Cache 的命中率为多少?
Cache 共有 16 行,每块 32 字节,所以 Cache 数据区的容量为16*32B=512B。考点二:存储器系统专题
2)M 的指令 Cache 和数据 Cache 分离。若指令 Cache 共有 16 行,Cache 和
主存交换的块大小为 32 字节,则其数据区的容量是多少?若仅考虑程序段 P 的
执行,则指令 Cache 的命中率为多少?
程序段 P 的首地址是0804 8100H,又块大小为 32 字节,则块内地址是5位,
于是程序段P从一块的开始位置进行存放;
程序段P一共有6条指令,每条指令占用4B,则程序段P一共占有24B,能够放
入到一个Cache块中。
读取第一条指令时会发生 Cache 缺失,故将 P 所在的主存块调入 Cache 某
一行,以后每次读取指令时,都能在指令 Cache 中命中。
因此在 1000 次循环中,只会发生 1 次指令访问缺失,所以指令 Cache 的命
中率为: (1000×6-1)/(1000×6)=99.98%。考点二:存储器系统专题
3)P 在执行过程中,哪条指令的执行可能发生溢出异常?哪条指令的执行可能产
生缺页异常?对于数组 A 的访问,需要读磁盘和 TLB 至少各多少次?
指令 4 为加法指令,即对应 sum+=A[i],当数组 A 中元素的值过大时,则会
导致这条加法指令发生溢出异常;考点二:存储器系统专题
3)P 在执行过程中,哪条指令的执行可能发生溢出异常?哪条指令的执行可能产
生缺页异常?对于数组 A 的访问,需要读磁盘和 TLB 至少各多少次?
指令 2、5 虽然都是加法指令,但他们分别为数组地址的计算指 令和存储变
量 i 的寄存器进行自增的指令,而 i 最大到达 1000,所以他们都不会产生溢
出异常。考点二:存储器系统专题
3)P 在执行过程中,哪条指令的执行可能发生溢出异常?哪条指令的执行可能产
生缺页异常?对于数组 A 的访问,需要读磁盘和 TLB 至少各多少次?
只有访存指令可能产生缺页异常,即指令 3 可能产生缺页异常。考点二:存储器系统专题
3)P 在执行过程中,哪条指令的执行可能发生溢出异常?哪条指令的执行可能产
生缺页异常?对于数组 A 的访问,需要读磁盘和 TLB 至少各多少次?
数组 A 未调入主存,且所有数组元素在同一页,并存储在磁盘同一个扇区。
因此访问A[0]时,出现访存缺页,将数组A调入内存,只需要访问一次磁盘。考点二:存储器系统专题
3)P 在执行过程中,哪条指令的执行可能发生溢出异常?哪条指令的执行可能产
生缺页异常?对于数组 A 的访问,需要读磁盘和 TLB 至少各多少次?
数组 A 未调入主存,且所有数组元素在同一页,并存储在磁盘同一个扇区。
因此访问A[0]时,出现访存缺页,此时的访问路径是③,访问了两次TLB。
①TLB
LA → PA ②TLB+ 页表
③TLB + 页表 + 中断 +TLB考点二:存储器系统专题
3)P 在执行过程中,哪条指令的执行可能发生溢出异常?哪条指令的执行可能产
生缺页异常?对于数组 A 的访问,需要读磁盘和 TLB 至少各多少次?
数组A的后续元素,A[1]~A[999], 在进行地址映射时,由于A已经在内存中了,
不会再产生访存缺页了,因此无论走路径①或者②,每个元素只会访问一次
TLB,共计2 + 999 = 1001次
①TLB
LA → PA ②TLB+ 页表
③TLB + 页表 + 中断 +TLB考点二: 存储器管理专题
3. 某虚拟存储器的用户编程空间共32个页面,每页1KB,主存为16KB。假定某时
刻该用户页表中已调入主存的页面的页号和物理块号为: (0,5), (1,10), (2,4)(3,7).
求出虚地址0A5CH和 1A5CH对应的物理地址,若在内存中找不到对应的页面,
会出现什么情况?
【解析】请求分页存储管理方式。页面大小L=1KB=210B,于是低10位为页内地址
对于虚地址A=0A5CH=(00001010 0101 1100) ,其中后10位为页内地址,前6
2
位000010为页号即2,
对 应 的 物 理 块 号 为 4 , 物 理 地 址 E1=100 10 0101 1100=1 0010 0101
1100=125CH(表示地址拼接)。
对于虚地址A=1A5CH=(0001 10100101 1100)2,前6位000110为页号即6,此
时内存中没有该页面,则产生缺页中断。考点二: 存储器管理专题
4、某请求分页存储管理系统,允许用户空间为32 个页面(每页1KB), 主存为
16KB, 如一个用户程序有10 页长,且在某时刻该用户进程的页表如表所示。
(1) 如果程序执行时遇到以下两个虚地址: 0AC5(H) 、1AC5(H), 试计算它们对
应的物理地址。
(1)页面大小L=1KB=210B,低10位为页内地址
对于虚地址A1=0A5CH=(0000 1010 0101 1100) , 前6 位000010 为页号即2,
2
对应的物理块号为4 (二进制数为100) , 后10位为页内地址,所以物理地址
E1=100 10 0101 1100=0001 0010 0101 1100 =125CH 。考点二: 存储器管理专题
4、某请求分页存储管理系统,允许用户空间为32 个页面(每页1KB), 主存为
16KB, 如一个用户程序有10 页长,且在某时刻该用户进程的页表如表所示。
(1) 如果程序执行时遇到以下两个虚地址: 0AC5(H) 、1AC5(H), 试计算它们对
应的物理地址。
(1)页面大小L=1KB=210B,低10位为页内地址
对于虚地址A2=1A5C(H)=(0001 1010 0101 1100) , 前6 位000110 为页号即6,
2
对应的物理块号为2( 二进制数为10), 后10位为页内地址,所以物理地址E2=10
10 0101 1100= 1010 0101 1100=A5CH 。考点二: 存储器管理专题
4、某请求分页存储管理系统,允许用户空间为32 个页面(每页1KB), 主存为
16KB, 如一个用户程序有10 页长,且在某时刻该用户进程的页表如表所示。
(2) 页表存放在主存中,对主存的一次存取需要1.5μs, 对TLB 表(快表)的查找
时间忽略为0, 试问这两次访问共耗费多少时间?
(2)对于虚地址A1=0A5CH=(0000 1010 0101 1100) , 前6 位000010 为页号即2,
2
不在TLB,但是在页表中,因此访问时间是1.5us * 2 = 3us。
对于虚地址A2=1A5C(H)=(0001 1010 0101 1100) , 前6 位000110 为页号即6,
2
在TLB中,因此访问时间是1.5。考点二: 存储器管理专题
5、在请求分页存储管理系统中,假设页表内容如表所示,页面大小为2^12B, 主
存的访问时间是100ns, 联想存储器的访问时间是10ns, 换入页面(含重新设置页
表项,并用新页表项置入联想存储器)的平均时间为100 000 000ns, 进程所用
页帧固定且驻留集大小为2, 采用LRU 页面淘汰算法,当进程被调度执行时,依次
访问虚地址: (23362) 、(14565) 、(24575) , 问各需要多少访问时间?
8 8 8
(14565)s 的物理地址是多少并解释(假设联想存储器初始为空,变址时先访问联
想存储器)?考点二: 存储器管理专题
【解析】对于15位虚地址,由于页面为12位,所以前3为页号,后12位为页内地址。
当页面驻留(驻留位为1) 时,访问虚地址时间=访问TLB时间+访问内存单元时间;
否则(驻留位为0) 当TLB 未命中时,访问虚地址时间=访问TLB时间+访问页表时
间+调页时间+访问TLB 时间+访问内存单元时间。
(23362) 的页号为2, 该页面驻留内存,所以访问时间
8
=10ns+100ns+100ns=210ns 。
(14565) 的页号为1, 该页面未驻留内存,需要调页,所以访问时间=10ns+
8
100ns+100 000 000ns+ 1 0ns+ 100ns=100 000 220ns 。考点二: 存储器管理专题
【解析】对于15位虚地址,由于页面为12位,所以前3为页号,后12位为页内地
址。当页面驻留(驻留位为1) 时,访问虚地址时间=访问TLB时间+访问内存单元
时间;否则(驻留位为0) 当TLB未命中时,访问虚地址时间=访问TLB 时间+访问
页表时间+调页时间+访问TLB 时间+访问内存单元时间。
(24575) 的页号为2, 该页面驻留内存,所以访问时间=10ns+100ns = 110ns 。
8
由于进程所用页帧固定且驻留集大小为2, 并采用LRU页面淘汰算法。先访问
(23362) 再访问(14565) 时,产生缺页中断,将其页面调入101页帧(因为101
8 8
页帧是最近未使用页,被置换),因此(14565) 虚地址的物理地址是(1014565)
8 8考点二: 存储器管理专题
6、有一请求分页存储管理系统,页面大小为100 字节。有一个50x50 的整型数
组按行连续存放,每个整数占两个字节,将数组初始化为0 的程序描述如下:
int a[50][50];
int i,j;
for(int i = 0; i <= 49; i++)
for(int j = 0; j <= 49; j++)
a[i][j] = 0;
若在程序执行时内存中只有一个块用来存放数组信息,试问该程序执行时产生多
少次缺页中断?考点二: 存储器管理专题
【解析】 由题目所给条件可知,数组a中共有 50 * 50=2500(个)整数,每个整数占用
2个字节,共需存储空间为 2 * 2500=5000(字节)。
而页面大小为100字节(块大小=页面大小=100 字节),则数组a占用空间
5000/100=50(页)。
假设数组a从作业地址空间的第m页开始存放,则数组a分布在第m页~第m+49页中,
其排列顺序为
a[0][0],a[0][1],…,a[0][49] 第 m 页
a[1][0],a[1][1],…,a[1][49] 第 m+1页
a[49][0],a[49][1,…,a[49][49] 第m+49页
数组初始化程序是按行进行的,每次缺页中断调进一页后,位于该页内的数组元素全
部赋予0值,然后再调入下一页,由于内存中只有一个页面用来存放数组信息,所以执
行上述程序涉及的页面走向为 m,m+1,…,m+49,故缺页中断次数为 50 次。谢谢大家考点三:
文件管理专题考点框架
文件管理和目录
磁盘管理和分配考点三: 文件管理专题
文件管理和目录考点三: 文件管理专题
1、某文件系统为一级目录结构,文件的数据一次性写入磁盘,已写入的文件不
可修改,但可多次创建新文件。请回答如下问题。
(1)在连续、链式、索引三种文件的数据块组织方式中,哪种更合适?要求说
明理由。为定位文件数据块,需要 FCB 中设计哪些相关描述字段?
【解析】(1)连续更合适,根据题意,文件的数据一次性写入磁盘,而一次写入
不存在,连续的数据块组织方式完全可以满足一次性写入磁盘,且连续文件组织方
式减少了其他不必要的空间开销,而连续的组织方式顺序查找读取速度是最快的。
已写入的文件不可修改,即插入或者删除问题,避免了连续文件因为插入或者删
除文件带来的开销。为定位文件数据块,需要FCB中包含起始位置和长度。考点三: 文件管理专题
1、某文件系统为一级目录结构,文件的数据一次性写入磁盘,已写入的文件不
可修改,但可多次创建新文件。请回答如下问题。
(2)为快速找到文件,对于FCB,是集中存储好,还是与对应的文件数据块连续
存储好?要求说明理由。
【解析】(2)FCB 集中存储好。目录(FCB文件)是存在磁盘上的,所以检索
目录的时候需要访问磁盘;集中存储是将文件控制块的一部分数据分解出去,存
在另一个数据结构中,而在目录中仅留下文件的基本信息和指向该数据结构的指
针,这样一来就有效地缩短减少了目录的体积,减少了目录在磁盘中的块数,于
是检索目录时读取磁盘的次数也减少,于是就加快了检索目录的次数。考点三: 文件管理专题
2、某文件系统空间的最大容量为4TB(1TB=2^40),以磁盘块为基本分配单位。
磁盘块大小为1KB。文件控制块(FCB)包含一个512B的索引表区。请回答下列
问题。
(1)假设索引表区仅采用直接索引结构,索引表区存放文件占用的磁盘块号,
索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节?
【解析】(1)文件系统空间的最大容量为 4TB,磁盘块大小为 1KB,因此文件
系统中所能容纳的磁盘块总数为 4TB/1KB=232。为了表示磁盘块,因此索引项中
的块号最少要占 32位/8位=4B。
而索引表区仅采用直接索引结构,且索引表区用于存放文件占用的磁盘块号,故
512B 的索引表区能容纳 512B/4B=128个索引项。由于每个索引项对应一个磁盘
块,所以该系统可支持的单个文件最大长度是 128×1KB=128KB。考点三: 文件管理专题
2、某文件系统空间的最大容量为4TB(1TB=2^40),以磁盘块为基本分配单位。
磁盘块大小为1KB。文件控制块(FCB)包含一个512B的索引表区。请回答下列
问题。
(2)假设索引表区采用如下结构:第0~7字节采用<起始块号,块数>格式表示
文件创建时预分配的连续存储空间。其中起始块号占6B,块数占2B,剩余504字
节,采用直接索引结构,一个索引项占6B,则可支持的单个文件最大长度是多少
字节?
(2)根据题意,可知所求的单个文件最大长度一共包含两部分:预分配的连续空间和直接索
引区。直接索引区共 504B,直接索引区共 504B,因此直接索引区共 504B/6B=84 个索引
项。由于每个索引项对应一个磁盘块,因此直接索引区空间大小是84KB。连续区起始块号占
6B,块数占 2B,因此连续区的磁盘块数是216 个磁盘块,所以连续区大小是216KB。所以该
系统可支持的单个文件最大长度是 216KB+84KB。考点三: 文件管理专题
2、某文件系统空间的最大容量为4TB(1TB=2^40),以磁盘块为基本分配单位。
磁盘块大小为1KB。文件控制块(FCB)包含一个512B的索引表区。请回答下列
问题。
(2)假设索引表区采用如下结构:第0~7字节采用<起始块号,块数>格式表示
文件创建时预分配的连续存储空间。为了使单个文件的长度达到最大,请指出起
始块号和块数分别所占字节数的合理值并说明理由。
根据上述计算,可知,直接索引区的大小是固定的84KB。而连续区的大小可以根据起始块
号和块数所占字节的不同而调整。根据题意,第 0~7 字节采用<起始块号,块数>格式表示
文件创建时预分配的连续存储空间。为了使单个文件的长度达到最大且不浪费起始块号的位
置,应使连续区的块数字段表示的空间大小尽可能接近(大于等于)系统最大容量 4TB。而
4TB所对应的磁盘块是232块,因此分别设起始块号和块数分别占 4B,这样起始块号可以寻
址的范围是232个磁盘块,共4TB,即整个系统空间。同样的,块数字段可以表示最多 232 个
磁盘块,共4TB。考点三: 文件管理专题
3、文件F由200条记录组成,记录从1开始编号。用户打开文件后,欲将内存中的
一条记录插入到文件F中,作为其第30条记录。请回答下列问题,并说明理由。
(1) 若文件系统采用连续分配方式,每个磁盘块存放一条记录,文件F存储区域前
后均有足够的空闲磁盘空间,则完成上述插入操作最少需要访问多少次磁盘块?
F 的文件控制块内容会发生哪些改变?
(1)系统采用顺序分配方式时,插入记录需要移动其他的记录块,整个文件共有 200 条记 录,
要插入新记录作为第 30 条,而存储区前后均有足够的磁盘空间,且要求最少的访问存 储
块数,则要把文件前 29 条记录前移,若算访盘次数移动一条记录读出和存回磁盘各是一
次访盘,29 条记录共访盘 58 次,存回第 30 条记录访盘 1 次,共访盘 59 次。F 的文件控
制区的起始块号和文件长度的内容会因此改变。考点三: 文件管理专题
3、文件F由200条记录组成,记录从1开始编号。用户打开文件后,欲将内存中的
一条记录插入到文件F中,作为其第30条记录。请回答下列问题,并说明理由。
(2) 若文件系统采用链接分配方式,每个磁盘块存放一条记录和一个链接指针,
则完成上述插入操作需要访问多少次磁盘块?若每个存储块大小为1KB,其中4
个字节存放链接指针,则该文件系统支持的文件最大长度是多少?
(2)文件系统采用链接分配方式时,插入记录并不用移动其他记录,只需找到相应的记录,
修改指针即可。插入的记录为其第 30 条记录,那么需要找到文件系统的第 29 块,一共需
要 访盘 29 次,然后把第 29 块的下块地址部分赋给新块,把新块存回内存会访盘 1 次,
然后修 改内存中第 29 块的下块地址字段,再存回磁盘,一共访盘 31 次。
4 个字节共 32 位,可以寻址 232 =4G 块存储块,每块的大小为 1KB,即 1024B,其中下
块 地 址 部 分 占 4B , 数 据 部 分 占 1020B , 那 么 该 系 统 的 文 件 最 大 长 度 是
4G×1020B=4080GB。考点三: 文件管理专题
4、某磁盘文件系统使用链接分配方式组织文件, 簇大小为4KB。目录文件的每个
目项包括文件名和文件的第一个簇号, 其他簇号存放在文件分配表FAT中。
(1)假定目录树如下图所示, 各文件占用的簇号及顺序如下表所示, 其中dir、dir1
是目录, file1、file2是用户文件。请给出所有目录文件的内容。
(1)目录文件的每个目项包括文件名和文件的第一个簇号,在本题中只有两个目录文件
dir和dir1。且dir包含一个目录dir1,其第一个簇号是48。
文件名 簇号
dir1 48考点三: 文件管理专题
4、某磁盘文件系统使用链接分配方式组织文件, 簇大小为4KB。目录文件的每个
目项包括文件名和文件的第一个簇号, 其他簇号存放在文件分配表FAT中。
(1)假定目录树如下图所示, 各文件占用的簇号及顺序如下表所示, 其中dir、dir1
是目录, file1、file2是用户文件。请给出所有目录文件的内容。
(1)目录文件的每个目项包括文件名和文件的第一个簇号,dir1包含2个文件file1和file2,
且file1的第一个簇号是100,file2的第一个簇号是200.因此dir和dir1目录文件如下表所示。
文件名 簇号
file1 100
file2 200考点三: 文件管理专题
(2) 若FAT的每个表项仅存放簇号, 占2个字节, 则FAT的最大长度为多少字节? 该文
件系统支持的文件长度最大是多少?
(2) FAT文件表每一项有两个含义:
①表项的地址代表当前文件的数据实际存储在磁盘中的簇的地址。
②表项中的数据表示文件的下一个簇数据所在磁盘中的地址。
若FAT的每个表项仅存放簇号, 占2个字节,那么FAT的项数(可以提供的最大磁盘块簇号)
是216。而FAT中存放的又是磁盘簇号,块号占2B,因此FAT的最大长度为216×2B=128KB。
又FAT表项占2个字节,也就是可以提供的最大磁盘簇编号数是216,也就是系统中最多有
216个磁盘簇,簇大小为4KB,因此文件的最大长度是216×4KB=256MB。考点三: 文件管理专题
(3) 系统通过目录文件和FAT实现对文件的按名存取, 说明file1的106、108两个簇
号分别存放在FAT的哪个表项中?
(3) 根据FAT的原理,表项中的数据表示文件的下一个簇所在磁盘中的地址。file1中包含
100,106和108,其中文件的首个簇号放置到目录文件中,随后的每一个簇号表项都存放
文件的下一个簇数据所在磁盘中的地址。filel的簇号106存放在FAT的100号表项中,簇号
108存放在FAT的106号表项中。考点三: 文件管理专题
(4) 假设仅FAT和dir目录文件已读入内存, 若需将文件dir/dir1/file1的第5000个字
节读入内存, 则要访问哪几个簇?
(4)FAT和dir目录文件已读入内存,不需要再读磁盘。通过dir找到dir1,需要读取dir1中
的目录文件,此时需要读取48号簇。根据48号簇,可以读出file1和file2的地址(本题只需
要file1);通过file1的目录项,我们知道file1从100簇开始。由于要读取file1的第5000个
字节,且簇大小是4KB(4096B),因此需要读取的内容在第二个簇中,因此读取文件file1
的106号簇。考点三: 文件管理专题
5、文件物理结构是指一个文件在外存上的存储组织形式,主要有连续结构、链接
结构和索引结构三种,请分别简述它们的优、缺点。
连续结构的优点:
①存储管理简单,容易实现;
②支持顺序存取和随机存取;
③顺序记问速度快。
连续结构的缺点:
①要求为每个文件分配连续的存储空间;
②必须事先知道文件的长度;
③不能灵活地插入和删除记录;
④不利于文件的动态增长。考点三: 文件管理专题
5、文件物理结构是指一个文件在外存上的存储组织形式,主要有连续结构、链接
结构和索引结构三种,请分别简述它们的优、缺点。
链接结构的缺点:
①存取速度较慢,不适合随机存取;
②物理块间的链接指针可能发生错误,造成数据丢失,可靠性差;
③需要较多的寻道次数和较长的寻道时间;
④链接指针占用了一定的空间,降低了空间利用率。考点三: 文件管理专题
5、文件物理结构是指一个文件在外存上的存储组织形式,主要有连续结构、链接
结构和索引结构三种,请分别简述它们的优、缺点。
索引结构的优点:
①既能满足顺序存取,又能满足随机存取;
②能适应文件的动态增长;
③方便插入、修改和删除记录。
索引结构的缺点:
①需要较多的寻道次数和较长的寻道时间;
②索引表增加了系统开销,包括内存空间和存取时间。考点三: 文件管理专题
6、某文件系统采用混合索引分配方式,如下图所示,有10个直接块(每个直接块指向
一个数据块), 1个一级间接块,1个二级间接块和1个三级间接块,间接块指向的是一
个索引块,每个索引块和数据块的大小均为512字节,索引块编号大小为4字节。问:
(1)如只使用直接块,文件最大为多少字节?
【解析】(1)如果只使用直接块,
文件最大为10 * 512 = 5120B。考点三: 文件管理专题
6、某文件系统采用混合索引分配方式,如下图所示,有10个直接块(每个直接块指向
一个数据块), 1个一级间接块,1个二级间接块和1个三级间接块,间接块指向的是一
个索引块,每个索引块和数据块的大小均为512字节,索引块编号大小为4字节。问:
(2)在该系统中能存储的文件最大是多少?考点三: 文件管理专题
(2)直接块指向数据的块数是10块,
一级间接块指向的索引块里的指针数=512B/4B=128(个),所以一级间接块指向数
据的块数是128块。
二级间接块指向的索引块里的指针数=512B/4B=128(个),指向的索引块里还有
128个指针,所以二级间接块指向数据的块数是1282块。
同理,三级间接块指向数据的块数是 1283块。
所以该系统能存储的文件最大为(10+128+1282+1283) * 512B=1082201088B =
1056837 KB.考点三: 文件管理专题
6、某文件系统采用混合索引分配方式,如下图所示,有10个直接块(每个直接块指向
一个数据块), 1个一级间接块,1个二级间接块和1个三级间接块,间接块指向的是一
个索引块,每个索引块和数据块的大小均为512字节,索引块编号大小为4字节。问:
(3)如读取某文件第10M字节的内容,需要访问磁盘几次?
(3)10 MB 的文件需要的数据块数=10MB/512B=20480(块)。
直接块和一级间接块指向的数据块数=10+128=138(块)<20480块。
直接块、一级间接块和二级间接块指向的数据块数=10+128+1282=16552(块)<20480块,
所以第 10 MB的数据应该存放在三级间接块下的某个数据块中,共需要访问磁盘4次。考点三: 文件管理专题
7、设某文件A由100个物理块组成,现分别用连续(顺序)文件、链接(串联)
文件、索引文件来构造。针对3种不同的结构,执行以下操作时各需要多少次磁
盘I/O。(假设文件控制块已读入内存中)
(1) 采用连续文件时,由于文件的头部没有空间扩展文件,故而情况如下:
①若要把一个物理块加到文件的头部,必须查文件控制块,找到文件的第一个物理块,计
算文件第100 块的位置。然后将第100 块都读到内存,再将它写到磁盘的下一块中。并将
第99 块、98 块、…、1 块依次读入内存,并写到磁盘的下一块中(即盘块后移,给待插入
块腾出空间)。这样,一个物理块需要两次访问磁盘(一次读入,一次写入)。最后将新
加入内容从内存写到磁盘的物理块中,所以共访问磁盘201 次。
②如果将一个物理块加到文件正中间,根据上述分析,需要访问磁盘101 次。
③因为连续文件可直接计算文件存放的位置,如果将一物理块加到文件尾部,直接将新加
入的内容从内存写到磁盘的物理块中即可,只需要访问磁盘一次。考点三: 文件管理专题
7、设某文件A由100个物理块组成,现分别用连续(顺序)文件、链接(串联)
文件、索引文件来构造。针对3种不同的结构,执行以下操作时各需要多少次磁
盘I/O。(假设文件控制块已读入内存中)
(2) 采用链接文件时,情况如下。
①如果要将一物理块加到文件头部,只需要将新加入的内容从内存写到磁盘的物理块,然
后将该物理块的指针指向原来第一个物理块,并修改文件控制块中第一块的地址和文件大
小即可,所以访问磁盘一次。
②如果将一物理块加到文件正中间,需要读出前50 块(访问磁盘50 次),以便找到第50
块的链接指针,将新加入的内容从内存写到新分配的物理块中,将新分配的物理块的链接
指针指向第51 块(访问磁盘一次),再将第50 块的链接指针指向新插入的物理块(访问磁
盘一次。即第50 块先前已经读入内存,用于找到第51 块的链接指针,而本次访问磁盘,是
修改该指针指向插入盘块,并写回到磁盘中)。共需要访问磁盘52 次。考点三: 文件管理专题
7、设某文件A由100个物理块组成,现分别用连续(顺序)文件、链接(串联)
文件、索引文件来构造。针对3种不同的结构,执行以下操作时各需要多少次磁
盘I/O。(假设文件控制块已读入内存中)
(2) 采用链接文件时,情况如下。
③如果将一物理块加到文件尾部,需要将第100 块读出(访问磁盘100 次),以便找到第
100 块,修改它的链接指针指向新插入的物理块并写回外存(访问磁盘一次),再将待写
入的数据写入磁盘(访问一次磁盘),故而需要访问磁盘102 次。考点三: 文件管理专题
7、设某文件A由100个物理块组成,现分别用连续(顺序)文件、链接(串联)
文件、索引文件来构造。针对3种不同的结构,执行以下操作时各需要多少次磁
盘I/O。(假设文件控制块已读入内存中)
(3) 采用索引文件,且索引块在内存。情况如下。
①如果要将一物理块加到文件头部。需要将新加入的内容从内存写到磁盘的物理块,并在文
件控制块中的头部增加新加入物理块的地址和文件大小即可,所以访问磁盘一次。
②如果将一物理块加到文件正中间,只需要将新加入的内容从内存写到磁盘的物理块,并在
文件控制块中的正中间增加新加入物理块的地址和文件大小即可,所以访问磁盘一次。
③如果将一物理块加到文件尾部,只需要将新加入的内容从内存写到磁盘的物理块,并在文
件控制块中的尾部增加新加入物理块的地址和文件大小即可,所以访问磁盘一次。考点三: 文件管理专题
8、有一个文件系统如图所示。图中的框表示目录,圆圈表示普通文件。根目录
常驻内存,目录文件组织成链接文件,不设文件控制块,普通文件组织成索引文
件。目录表目指示下一级文件名及其磁盘地址(各占2个字节,共4个字节)。若
下一级文件是目录文件,指示其第一个磁盘块地址。若下级文件是普通文件,指
示其文件控制块的磁盘地址。每个目录文件磁盘块最后4个字节供拉链使用。下
级文件在上级目录文件中的次序在图中为从左至右。每个磁盘块有512字节,与
普通文件的一页等长。考点三: 文件管理专题
普通文件的文件控制块组织描述如下:每个磁盘地址占2个字节,前10个地址直
接指示该文件前10页的地址;第11个地址指示一级索引表地址,一级索引表中每
个磁盘地址指示一个文件页地址;第12个地址指示二级索引表地址,二级索引表
中每个地址指示一个一级索引表地址;第13个地址指示三级索引表地址,三级索
引表中每个地址指示一个二级索引表地址。间:
(1) 一个普通文件最多可有多少个文件页?
(1) 由题目中所给条件可知,磁盘块大小512 个字节,每个磁盘地址占2 个字节,因此一个
一级索引可容纳256 个磁盘地址。同理,一个二级索引表可容纳256 个一级索引表地址,一
个三级索引表可容纳256 个二级索引表地址。
因为普通文件的文件控制块共13 个地址项, 10 个直接地址,1个1 级索引地址,1 个二级
索引地址,一个三级索引地址。故而,一个普通文件最多可有的页数为:10+256+256 *
256+256* 256*256=16 843 018 。考点三: 文件管理专题
普通文件的文件控制块组织描述如下:每个磁盘地址占2个字节,前10个地址直
接指示该文件前10页的地址;第11个地址指示一级索引表地址,一级索引表中每
个磁盘地址指示一个文件页地址;第12个地址指示二级索引表地址,二级索引表
中每个地址指示一个一级索引表地址;第13个地址指示三级索引表地址,三级索
引表中每个地址指示一个二级索引表地址。间:
(2) 若要读文件J 中某一页,最多启动磁盘多少次?
(2) 从图中可以看出,目录文件A和目录文件D中目录项都只有2个,因此这两个目录文件
都不需要拉链。若要读取文件J 中某一页,
首先从内存的根目录中找到目录文件A的磁盘地址,将其读入内存(第1次读磁盘)。
然后再从目录A中找到D的磁盘地址,并将其读入内存(第2次读磁盘)。
从D目录中找到文件J 的文件控制块地址,将其读入内存(第3次读磁盘)。考点三: 文件管理专题
普通文件的文件控制块组织描述如下:每个磁盘地址占2个字节,前10个地址直
接指示该文件前10页的地址;第11个地址指示一级索引表地址,一级索引表中每
个磁盘地址指示一个文件页地址;第12个地址指示二级索引表地址,二级索引表
中每个地址指示一个一级索引表地址;第13个地址指示三级索引表地址,三级索
引表中每个地址指示一个二级索引表地址。间:
(2) 若要读文件J 中某一页,最多启动磁盘多少次?
(2) 在最坏的情况下,要访问页的地址需通过三级索引才能找到,这时要三次读取磁盘才能
将三级索引读入内存(第4 、5 、6 次读磁盘)。
最后读入文件J的相应页(第7次读磁盘)。由此可知, 若要读文件J 中某一页,最多启动
磁盘7 次。考点三: 文件管理专题
普通文件的文件控制块组织描述如下:每个磁盘地址占2个字节,前10个地址直
接指示该文件前10页的地址;第11个地址指示一级索引表地址,一级索引表中每
个磁盘地址指示一个文件页地址;第12个地址指示二级索引表地址,二级索引表
中每个地址指示一个一级索引表地址;第13个地址指示三级索引表地址,三级索
引表中每个地址指示一个二级索引表地址。间:
(3) 若要读文件W 中的某一页,最少启动磁盘多少次?
从图中可以看出,目录文件C和目录文件U中,目录项数目较多。每个盘块可以放128个目
录项,而最后4个字节用作链接,若目录项数超过127, 则目录文件的读入可能需要多次读盘
(因目录文件组织成链接文件)。考点三: 文件管理专题
普通文件的文件控制块组织描述如下:每个磁盘地址占2个字节,前10个地址直
接指示该文件前10页的地址;第11个地址指示一级索引表地址,一级索引表中每
个磁盘地址指示一个文件页地址;第12个地址指示二级索引表地址,二级索引表
中每个地址指示一个一级索引表地址;第13个地址指示三级索引表地址,三级索
引表中每个地址指示一个二级索引表地址。间:
(3) 若要读文件W 中的某一页,最少启动磁盘多少次?
在最好情况下,所找的目录项都在目录的第一个磁盘块中。若要读文件W的某一页, 首先
从内存的根目录中找到目录文件C的地址,将其读入内存(第1次读磁盘) 。
在最好情况下,能从目录C的第一个盘块中找到目录文件I 的地址,将其读入内存(第2次读
磁盘) 。考点三: 文件管理专题
普通文件的文件控制块组织描述如下:每个磁盘地址占2个字节,前10个地址直
接指示该文件前10页的地址;第11个地址指示一级索引表地址,一级索引表中每
个磁盘地址指示一个文件页地址;第12个地址指示二级索引表地址,二级索引表
中每个地址指示一个一级索引表地址;第13个地址指示三级索引表地址,三级索
引表中每个地址指示一个二级索引表地址。间:
(3) 若要读文件W 中的某一页,最少启动磁盘多少次?
从目录1中找到目录文件P的地址,将其读入内存(第3次读磁盘)。从目录P 中找到目录文
件U的地址,将其读入内存(第4次读磁盘)。
在最好情况下,能从目录U的第一个盘块中找到目录文件W 的文件控制块的地址,将其读
入内存(第5次读磁盘)。
在最好情况下,要访问的页在前10页中,这时可以直接读到该页的地址。最后读入文件W
的相应页(第6次读磁盘) 。由此可知, 若要读文件W中的某一页, 最少启动磁盘6 次。考点三: 文件管理专题
普通文件的文件控制块组织描述如下:每个磁盘地址占2个字节,前10个地址直
接指示该文件前10页的地址;第11个地址指示一级索引表地址,一级索引表中每
个磁盘地址指示一个文件页地址;第12个地址指示二级索引表地址,二级索引表
中每个地址指示一个一级索引表地址;第13个地址指示三级索引表地址,三级索
引表中每个地址指示一个二级索引表地址。间:
(4) 就(3) 而言,为最大限度减少启动磁盘次数,可采用什么方法?此时,磁盘最
多启动多少次?
(4) 由于通过文件控制块访问文件所需的读盘次数无法改变,要减少访问磁盘次数,只有通
过减少访问目录文件的次数来达到。为最大限度地减少启动磁盘次数,可将文件W直接链接
在根目录的最左端(其目录项在根目录的前127个目录项内)。这样,若要读文件W的某页
时,首先从内存的根目录中找到文件W的文件控制块地址,将文件W的文件控制块读入内
存(第1次读磁盘)。考点三: 文件管理专题
普通文件的文件控制块组织描述如下:每个磁盘地址占2个字节,前10个地址直
接指示该文件前10页的地址;第11个地址指示一级索引表地址,一级索引表中每
个磁盘地址指示一个文件页地址;第12个地址指示二级索引表地址,二级索引表
中每个地址指示一个一级索引表地址;第13个地址指示三级索引表地址,三级索
引表中每个地址指示一个二级索引表地址。间:
(4) 就(3) 而言,为最大限度减少启动磁盘次数,可采用什么方法?此时,磁盘最
多启动多少次?
(4) 在最好情况下,要访问的页在前10页中,这时可以直接读到该页的地址。在最坏的情况
下,要访问页的地址需三级索引才能找到,这时要3次访问磁盘(第2 、3 、4 次读磁盘)。
最后读入文件W的相应页(最好情况下,第2次读盘;最坏情况下,第5次读磁盘)。由此
可知,若将文件W直接链接在根目录的最左端,要读文件W中的某一页,最少启动磁盘2次,
最多启动磁盘5次。考点三: 文件管理专题
9、某文件系统以硬盘作为文件存储器,物理块大小为512B 。有文件A包含590
个逻辑记录,每个记录占255B, 每个物理块存放2个记录。文件A 在该文件目录
中的位置如图所示。此树形文件目录结构由根目录节点、作为目录文件的中间节
点和作为信息文件的叶子节点组成。每个目录项占127B, 每个物理块存放4个目
录项。根目录的内容常驻内存。考点三: 文件管理专题
(1) 若文件采用链接分配方式,如果要将文件A 读入内存,至少要存取几次硬盘,
为什么?
【解析】(1)首先要检索到文件 A,即通过路径\root\usr\userl\mytext\A来进行。在最好情
况下的步骤如下:
①从内存中的根目录中找出目录usr的目录文件,读入内存(计1次硬盘访问)。
②从目录usr的目录文件中找出目录user1的目录文件,读入内存(计1次硬盘访问)。
③从目录 user1 的目录文件中找出目录 mytext的目录文件,读入内存(计1次硬盘访问)。
④从目录 mytext的目录文件中找出文件A对应的物理位置,即文件在外存上的存储位置。
文件 A包含 590个逻辑记录,需占590/2=295(个)物理块。采用链接分配方式,所有物理块一
个一个地读入,因此读入文件A需要访问硬盘295次。所以总的存取硬盘次数
=3+295=298(次)。考点三: 文件管理专题
(2) 若文件采用连续分配方式,如果要将文件A 的逻辑记录号为480的记录读入内
存,至少要存取几次硬盘,为什么?
(2)如果采用连续分配方式,同样需要3次硬盘访问得到文件A的起始物理块号S。由于是连续文
件,因此可以通过逻辑记录号直接换算成相应的物理块号: S+480/=S+240。
要读入该记录只需访问硬盘1次,因此总的访问次数=3+1=4(次)。考点三: 文件管理专题
10、假定磁盘块的大小为1KB, 对于540MB的硬盘,其文件分配表FAT最少需要占
用多少存储空间?
当硬盘容量为1.2GB 时, FAT 最少需要占用多少空间?
【解析】对于540 MB的硬盘,硬盘总块数为 540MB/1KB=540K(个)。因为 540K
小于220,所以文件分配表的每个表项可用 20位,为方便起见,每个表项用 24位二
进制表示,即文件分配表的每个表项大小为3个字节。
这样FAT占用空间=3B * 540K=1620KB。
对于 1.2 GB的硬盘,硬盘总块数为 1.2GB/1KB=1.2 M(块)。因为1.2M刚好小于
221,所以文件分配表的每个表项可用21位,但为方便起见,每个表项用24位二进制表
示,即文件分配表的每个表项大小为3个字节。
这样FAT占用空间=3B * 1.2M=3.6MB考点三: 文件管理专题
11、某文件系统采用多级索引的方式组织文件的数据存放,假定在文件的i_node中
设有13个地址项,其中直接索引10项,一次间接索引项1项,二次间接索引项1项,
三次间接索引项1项。数据块大小为4KB,磁盘地址用4B表示,问:
(1)这个文件系统允许的最大文件长度是多少?
【解析】(1)数据块大小为4KB,磁盘地址为4B,则每个物理块可存储的地址数为
4KB/4 B=1024。
最大文件的物理块数可达10+1024+10242 +10243,每个物理块大小为4 KB,
因此总长度为(10+1024+10242+10243)×4 KB=40 KB+4 MB+4 GB+4 TB,
所以这个文件系统允许的最大文件长度是4 TB+4 GB+4 MB+40 KB,约为4TB。考点三: 文件管理专题
11、某文件系统采用多级索引的方式组织文件的数据存放,假定在文件的i_node中
设有13个地址项,其中直接索引10项,一次间接索引项1项,二次间接索引项1项,
三次间接索引项1项。数据块大小为4KB,磁盘地址用4B表示,问:
(2)一个2GB大小的文件,在这个文件系统中实际占用多少空间?
(2)该文件占用2 GB/4 KB=512×1024个数据块。
直接索引指向10个数据块;
一级间接索引指向1024个数据块,需1个索引块;
二级间接索引项指向512×1024-10-1024个数据块,
共需1+(512×1024-10-1024)/1024=512个索引块。
索引块所占空间大小为(1+512)×4 KB=2 MB+4 KB。
另外每个文件使用的i_node数据结构占13×4 B=52 B,
因此该文件实际占用磁盘空间大小为2 GB+2MB+4 KB+52 B。考点三: 文件管理专题
12、假定盘块的大小为1KB,硬盘的大小为500MB,采用显示链接分配方式时,
其FAT需占用多少存储空间?
如果文件A占用硬盘的第11、12、16、14中各盘块间的链接情况及FAT的情况。
【解析】由题意可知,该硬盘共有 500KB个盘块,故FAT中共有500KB个表项;如果
盘块从0开始编号,为了能保存最大的盘块号 500 KB(218<500KB<219),FAT表项最
少需要19位,将它扩展为半个字节的整数倍后,可知每个FAT表项需20位,即2.5个字
节。
因此,FAT占用的存储空间的大小为2.5x500 KB=1250 KB.考点三: 文件管理专题
12、假定盘块的大小为1KB,硬盘的大小为500MB,采用显示链接分配方式时,
其FAT需占用多少存储空间?
如果文件A占用硬盘的第11、12、16、14中各盘块间的链接情况及FAT的情况。
【解析】文件A中各盘块间的链接情况及FAT的情况如图所示考点三: 文件管理专题
磁盘管理和分配考点三: 文件管理专题
1、假设计算机系统采用C-SCAN(循环扫描)磁盘调度策略, 使用2KB的内存
空间记录16384个磁盘块的空闲状态。
(1) 请说明在上述条件下如何进行磁盘块空闲状态的管理。
【解析】(1) 在C-SCAN(循环扫描)磁盘调度策略下,磁盘块空闲状态的管理可采用位图
法。因为用2KB=16384位,也就是使用16384个位置的内存空间,记录16384个磁盘块的
空闲状态,即每一位表示一个磁盘块的空闲状态。考点三: 文件管理专题
1、假设计算机系统采用C-SCAN(循环扫描)磁盘调度策略, 使用2KB的内存
空间记录16384个磁盘块的空闲状态。
(2) 设某单面磁盘旋转速度为每分钟6000转,每个磁道有100个扇区,相邻磁道
间的平均移动时间为1ms。 若在某时刻,磁头位于100号磁道处,并沿着磁道号
增大的方向移动(如下图所示), 磁道号请求队列为50, 90,30,120,对请
求队列中的每个磁道需读取1个随机分布的扇区,则读完这4个扇区点共需要多少
时间?要求给出计算过程。考点三: 文件管理专题
(2)访问磁盘的时间包括三个部分:①寻道时间②旋转时延③读写时延。
①寻道时间:采用 CSCAN 调度算法,访问磁道的顺序和移动的磁道数如下表所示:
移动的磁道数为 20+90+20+40=170,故总的移动磁道时间为 170ms。
②旋转时延:由于转速为 6000r/m,则平均旋转延迟为 5ms, 总的旋转延迟时间=20ms。
③读写时延:由于转速为 6000r/m,则读取一个磁道上一个扇区的平均读取时间为 0.1ms,
总的读取扇区的时间平均读取 时间为 0.1ms,总的读取扇区的时间为 0.4ms。
综上,读取上述磁道上所有扇区所花的总时间为 190.4ms。考点三: 文件管理专题
1、假设计算机系统采用C-SCAN(循环扫描)磁盘调度策略, 使用2KB的内存
空间记录16384个磁盘块的空闲状态。
(3) 如果将磁盘替换为随机访问的Flash半导体存储器(如 U 盘、SSD 等), 是
否有比 C-SCAN 更高效的磁盘调度策略?若有,给出磁盘调度策略的名称并说
明理由;若无,说明理由。
(3) 在Flash半导体存储器中,而Flash半导体存储结构可以采用随机的方式进行读取,也即
读写时间与物理位置无关,可直接FCFS(先来先服务)调度策略,即按I/O请求的先后顺序
服务。
事实上Flash半导体存储器没有寻到时间和旋转时延。考点三: 文件管理专题
2、磁盘共有200个柱面(0~199),它刚刚从92号磁道移到98号磁道完成读写,假设
此时系统中等待访问磁盘的磁道序列为:190,97,90,45,150,32,162,108,112,80。
试给出采用下列算法后磁头移动的顺序,并计算寻道距离。
(1) FCFS 算法 (2) SSTF 算法。
(3) SCAN 算法 (4) C-SCAN算法。考点三: 文件管理专题
【解析】 (1)FCFS算法的磁头移动顺序:98,190,97,90,45,150,32,162,108,112,80。
FCFS算法的寻道距离:(190-98)+(190-97)+(97-90)+(90-45)+(150-45)+(150-
32)+(162-32)+(162-108)+(112-108)+(112-80)=680。
(2)SSTF算法的磁头移动顺序:98,97,90,80,108,112,150,162,190,45,32。SSTF算
法的寻道距离(98-97)+(97-90)+(90-80)+(108-80)+(112-108)+(150-
112)+(162-150)+(190-162)+(190-45)+(45-32)=286考点三: 文件管理专题
【解析】 (3)SCAN算法的磁头移动顺
序:98,108,112,150,162,190,97,90,80,45,32。SCAN算法的寻道距离:(108-
98)+(112-108)+(150-112)+(162-150)+(190-162)-(190-97)+(97-90)-(90-
80)+(80-45)+(45-32=250
(4)C-SCAN算法的磁头移动顺序:98,108,112,150,162,190,32,45,80,90,97。C-
SCAN算法的寻道距离:(108-98)+(112-108)+(150-112)+(162-150)+(190-
162)+(190-32)+(45-32)+(80-45)+(90-80)+(97-90)=315。考点三: 文件管理专题
3、假定某磁盘上共有200个柱面,编号为0~199,当前磁头的位置位于90号柱面,当
前正在向199号柱面方向前进。同时有若干请求者在等待服务,它们依次要访问的
柱面号为: 85,132,188,94,155,100,170,125。假设每移动一个柱面所需的时间为2
us,试分别采用最短寻道优先算法和电梯调度算法计算实际的服务次序,并计算各个
算法的平均寻道时间。考点三: 文件管理专题
【解析】最短寻道优先算法的服务次序: 90,94,100,85,125,132,155,170,188.
最短寻道优先算法的寻道时间=[(94-90)+(100-94)+(100-85)+(125-85)+(132-
125)+(155-132)+(170-155)+(188-170)] x 2us = 256us.
平均寻道时间=256us/9≈28.4μs.
电梯调度算法的服务次序: 90,94,100,125,132,155,170,188,85
电梯调度算法的寻道时间=[(94-90)+(100-94)+(125-100)+(132-125)+(155-
132)+(170-155)+(188-170)+(188-85)] x 2us=402us。
平均寻道时间=402μs/9≈44.7μs。谢谢大家