Ch8 文件管理与外排序

1. I/O与磁盘

这部分知识在《操作系统》《系统级编程》中都有相关章节，这里不在赘述

• 《操作系统》Ch11 I/O管理与磁盘调度
• 《系统级编程》Ch11 存储与性能

2. 缓存区&缓存算法

当硬盘的一个扇区（sector）被读取，其中部分信息会被暂存在内存中，这就叫buffering和caching技术，利用了存储的时间局部性和空间局部性，缓存策略通常由：

• FIFO：先进先出队列
• LFU（Least Frequently Used ）：最近最少使用，为每个扇区维护一个频度，优先删去内存中频度小&时间久的
• LRU（Least Recently Used）：最近最久未使用，将新信息读取至缓冲区头，根据需要丢弃尾部信息或重新写至头部

*LRU和LFU有点类似，但LFU缓冲区中任意扇区被读取不会改变其位置；LRU中凡是要被读取的扇区一定先会被重置到头部才会被读取 :::info 例题：要读取的扇区序号为9 0 1 7 6 6 8 1，已知缓冲区大小为4个sectors，求访问磁盘而非缓冲区的次数
:::

3. 外排序

外排序与内排序相对，主要针对内存外(磁盘中)的数据排序，因此我们的算法应该尽量减少磁盘访问

3.1 简单2路归并

(Simple External Mergesort)
首先明确顺串(run)，表示有序的子序列，让run length=1即为无序，run length=2表示所有元素成对有序：[5，6]，[1，2]，[3，7]，[0，6]，run length=4类似[1，2，5，6]，[0，3，6，7]

1. 把文件分成两个等大的顺串文件，此时run length=1
2. 从每个run file中读取blocks放入input buffers
   1. 从每个input buffer逐个取出记录，按序写入对应output buffers
   2. 当output buffer满后写入合适的output file，一般input files有两个，则output file也有两个，此时其中的run length=2
3. output files作为新的input files读取下一个block，重复2-3，每次排序后run length翻倍，最终每个output file中的记录整体有序，即run length=size
4. 归并两个output file，得到一个有序的run file

:::info 书上的例子，只给出了run file的变化，不够详细，我在下方给出其中input buffer和output buffer的情况

::: | 小结简单2路归并
1. 设原始文件记录个数N,run length=1,归并次数
1. 设M为每个Block中存放记录数,则每次归并的磁盘IO次数是
【因为Block是IO基本单位,则N/M是每个文件最多可分块数,读写算作两次故乘2】
3. 总IO次数
3. RAM使用:4个buffer:2个input buffer,2个output buffer
3. Disk使用:4个File:2个input file,2个output file
| | —- |

:::danger 简单二路归并中总IO次数，我们的目的是尽量减少磁盘访问，因此可以有两种思路

• 增大初始顺串长度，即想办法使得开始时有序子序列越长越好==>置换选择排序
• 每一趟同时归并多个顺串，即修改对数log的底数2==>多路归并 :::

  3.2 置换选择排序

  (Replacement Selection)

1. 内存中有一个长M的数组+一个大小M的input buffer+一个output buffer
2. 假设数组已有来自input buffer的M个记录填满，用数组建立最小堆，令LAST=M-1
3. 重复以下步骤
   1. removemin()，将最小记录输出到output buffer
   2. 设R为input buffer下一记录，若R>刚输入的值，则R作为堆的根结点;否则swap(array，LAST，0)把LAST处记录作为根结点，再把R放到LAST后LAST—
   3. 重整堆有序
4. 当LAST=0时，output buffer中所有记录构成一个run，而此时数组M个元素又可进行第二轮求run的操作

算法即不断找到当前堆中最小的记录，不断构建一个从大到小的run，极端好的情况下第一个run就可包含所有数据，极端坏时第一个run length=1，即所有input都小于第一次output

小结置换选择排序 1. 总IO次数 1. RAM使用:1个input buffer,1个output buffer,1个Heap 1. Disk使用:1个input file

3.3 多路归并

(Multiway Merging)

小结B路归并 1. 总IO次数 1. RAM使用:B个input buffer,1个output buffer 1. Disk使用:B个input file,1个output file