总公式
以下将“访问磁盘次数”简称为“访磁次数”
总访磁次数 = 从根目录找到目标文件FCB的访磁次数 + 从FCB找到目标页的访磁次数
其中: 根目录到FCB的访磁次数 = 每一级目录的访磁次数之和 FCB到目标页的访磁次数 = 寻找目标页所在物理块的访磁次数
详述
假设现在要访问文件J中的某一页,那么先要找到文件J的FCB,再根据FCB中文件记录的寻址方式找出目标页所在的物理块。 正方形表示目录文件,圆形表示普通文件 几个前提: 1、根目录常驻内存。即第一次访问磁盘从第一级目录开始。 2、每个磁盘块与普通文件的一页等长。 已知J的路径为 A/D/J,那么首先要访问A目录。图中目录文件A包括2个目录项(D和E),如果每个目录项占4B,那么A所占空间就为8B。
现在假设 一个磁盘块大小 = 一页大小 = 512B,那么A目录处于第一个物理块中,占用第1-8B存储空间。同理目录文件B也占8B,占用了第一个物理块的9-16B存储空间。也就是说,访问A或B目录下一级的普通文件或目录文件都只需要访问磁盘1次。图中A、B……C中间间隔的目录省略了,假如中间有N个512B,那么访问C目录下的目录项H就要搜索第N+1个物理块,需要访问磁盘N+1次。 可以看到寻找普通文件J时,每次读取都在第一个磁盘块下找到下级目录或文件,这是最好情况(访问磁盘次数最少)。类似的,最差情况就是每次读取都在最后一个磁盘块找到下级目录或文件。
所以,从根目录找到J的总访问次数为3次: 第1次:从内存的根目录找到目录文件A的磁盘地址并将其读入内存; 第2次:从内存的A目录中找到目录文件D的磁盘地址并将其读入内存; 第3次:从内存的D目录中找到文件J的FCB(文件控制块)地址读入内存。
下面根据J的具体的页的存放位置来确定访磁次数 在最好的情况下,访问的页在FCB的直接块中,那么按照直接块指示的地址读文件的相应页即可(访问磁盘1次),此时总共访问磁盘次数为3+1=4次。
若采用索引结构(或间接地址),那么M级索引(或M级间址)需要访问磁盘M+1次。前M次访问磁盘找出文件相应页的有效地址,最后1次读入相应页。此时总共访问磁盘次数为3+M+1次。
附:文件的字节偏移量转换为物理块号的过程
现要找出一个文件的第 150,000B所在的物理块号,已知FCB中共有13个地址项,第0-9个地址项为直接地址,第10个地址项为一次间接地址,第11个地址项为二次间接地址,第12个地址项为三次间接地址,每个盘块512B,盘块号占3B,每个盘块最多存放170个盘块地址。 分析:首先要明确一点,文件的存放是从累计存放的。就是先将直接块指向的地址空间存满,再将一级间址指向的地址空间存满,以此类推。
先将150,000B转换为物理块号,150,000B ÷ 512B = 292……496 含义是文件的150,000B存满了292个物理块而且还多出来496B。(所以是放在第293个物理块,块内偏移量为496。但是块号是从0开始计数的,所以对应的块号还是292)
直接地址能找到10块,一次间接地址能找到170块,二次间接地址能找到170×170块,所以150,000B一定在二次间接地址块指向的物理块中,292-10-170 = 112. 这个112表示在二次间接地址的170×170块下的块号,所以是在[0,112]项。最后得出寻找的过程,如下: 1、从FCB的第11个地址项中得到二次间接地址块的地址 2、从二次间接地址块的第0项中获得一个一次间接地址块的地址 3、从一次间接地址块的112项中获得对应的物理盘块号,块内位移为496
|