外存信息的存取.pptVIP

18 第十一章 外部排序 * * ￡11.1 外存信息的存取 ￡11.1.1 磁带信息的存取 ￡11.1.2 磁盘信息的存取 ￡11.2 外部排序的方法 ￡11.1 外存信息的存取 ￡11.1.1 磁带信息的存取 磁带：一条薄薄涂上一层磁性材料的窄带（现在使用的磁带大 多数有1/2英寸宽，最长可达3600英尺，绕在一个卷盘上）。它是 一种顺序存取的存储设备。 磁带的工作原理：使用时，将磁带放在磁带机上，驱动器控制 磁带盘转动，带动磁带向前移动。通过读/写头就可以读出磁带上的 信息或者把信息写入磁带中。 7道带：在1/2英寸宽的带面上记录7位二进制信息的磁带。 9道带：在1/2英寸宽的带面上记录9位二进制信息的磁带。每 一横排可表示一个字符（8位表示一个字符，剩下的一位作奇偶校 验位）。 信息密度：每英寸的二进制字符数。通常为每英寸800位或 1600位或6250位。 移动速度：每秒200英寸。 间隙IRG（Inter Record Gap）：磁带上相邻两组字符组（记录） 之间的空白区。根据启停时间的需要，这个间隙通常为1/4~3/4英寸。 例如，若每个字符组的长度是80个字符，IRG为3/4英寸，则对密 度为每英寸1600个字符的磁带，其利用率仅为1/16，有15/16的带用于 IRG。如图11.1(a)所示。 块间间隙IBG（Inter Block Gap）：将若干个字符组合并成块，每 个字符组间没有IRG，而变成块间的间隙。 例如，图11.1(b)表示将20个长度为80字符的字符组存放在磁带上的 一个物理块中的情况。 IRG IRG IRG 记 录 (a) 字符组长80字符的磁带 IBG IBG IBG 20个记录 20个记录 20个记录 (b) 成块存放的磁带 图11.1 磁带上信息存放示意图 磁带上读写一块信息所需的时间为： TI/O = ta + n * tw 其中：ta为延迟时间，读/写头到达传输信息所在物理块起始位置所需 时间（显然，延迟时间和信息在磁带上的位置、当前读/写头所在位置 有关）；tw为传输一个字符的时间。 成块的优点： （1）可以减少IRG的数目，从而提高磁带的利用率，块的长度大于 IBG的长度。 （2）可以减少I/O操作。因为一次I/O操作可把整个物理块都读到内 存缓冲区中，然后再从缓冲区中取出所需要的信息（一个字符组）。 每当要读一个字符组时，首先要查缓冲区中是否已有，若有，则不必执 行I/O操作，直接从缓冲区读取即可。 ￡11.1.2 磁盘信息的存取 磁盘：是一个扁平的圆盘，盘面上有许多称为磁道的圆圈，信息 就记载在磁道上。它是一种直接存取的存储设备（DASD）。 磁盘的工作原理：盘片装在一个主轴上，并绕主轴高速旋转，当 磁道在读/写头下通过时，便可进行信息的读/写。读/写信息的功能由 磁盘驱动器执行。 固定头盘：固定头盘的每一磁道上都有独立的磁头，这些磁头固 定不动，专负责读/写某一磁道上的信息。 活动头盘：活动头盘的磁头是可以移动的。一个盘面上只有一个 磁头，磁头装在一个动臂上，可以从该面上的一道移动到另一道。 ￡11.1.2 磁盘信息的存取 在磁盘上表明一个具体信息必须用一个三维地址：柱面号（确定 读/写头的径向运动)、盘面号、块号(确定信息在盘片圆圈上的位置）。 访问一块信息： （1）找柱面,移动臂使磁头移动到所需柱面上(称为定位或寻查)； （2）等待要访问的信息转动磁头之下； （3）读/写所需信息。 磁盘上读写一块信息所需的时间为： TI/O = tseek + tla + n * twm 其中：tseek为寻查时间（seek time）：即读/写头定位的时间； tla为等待时间（latency time）：即等待信息块的初始位置旋到 读/写头下的时间； twm为传输时间（transmission time）。 *