<<< $\color{blue}{ (●’◡’●) 点赞 <(- ●’◡’●) }$
/\\ //>>>>
/__\\ // 关注加RP,AC更容易!
/ \\ //>>>>>
<<< $\color{blue}{ (●’◡’●) 收藏 <(- ●’◡’●) }$
$算法基础课的内容在实际计算机及软件系统中有着相当广泛的应用。$
$本文通过实际硬件的介绍和抽象,介绍磁盘读取问题中可以运用的相关知识点。$
$文章最后附有知识点习题指路。$
涉及算法基础知识点, 完整版见基础课内容
$\Large\textbf{基础算法}$
$\color{Gray}{ |— 离散化}$
$\color{Gray}{ |— 区间合并}$
$\Large\textbf{数据结构}$
$\color{Gray}|— 栈与队列:单调队列、单调栈$
$\color{Gray}|— 哈希表$
硬盘的工作原理及抽象
$要找到算法能解决的问题,首先需要理解复杂的设备工作原理,并从中抽象出需要解决的问题模型。$
$硬盘可以宽泛地分成两类:机械(HDD)和固态(SSD)$
$\color{brown}{机械硬盘(HDD)}: $
$数据存储在磁性介质里,介质被划分成多个同心圆,每个同心圆还会划分不同的扇区。$
$读写时,通过机械摇臂,磁盘移动到对应的扇区位置进行读写。$$\color{brown}{固态硬盘(SSD)}: $
$数据存储在晶体管阵列中。$
$读写时通过设置触发电平实现。$
$这里不讨论两种方式的优缺点,实际两种存储介质都会被广泛地使用,因此抽象和优化需要兼顾二者。$
$无论哪种硬盘,直接擦写单个字节数据的开销都太大,因此数据都是以一定长度为单位进行操作的。$
$这相当于将所有Byte$$\color{Cyan}{【哈希】}$$成数量较少的Page/Block。$
$操作系统对硬盘的每次读写操作,也可以抽象成一个指令:$
Read/Write DiskStartAddress len MemoryStartAddress
$从磁盘开始位置,读/写len个字节,如果是读操作,结果将送到MemoryStartAddress中,$$如果是写操作,则从MemoryStartAddress中获取$
$系统将若干指令下发给$$\color{brown}{【硬盘控制器】}$$,硬盘控制器负责$$\color{orange}{决定指令操作的顺序}$$并将数据取回。$
$当然实际发生的事情要更复杂。$
$从磁盘到内存,还需要经过磁盘本身的buffer,经过计算机的PCI总线调度,才能进入内存。$
$但是这些开销在数据量和操作数一定的情况下,大概相当于常数开销,所以提升效率的关键指令数和数据量。$
$接下来我们要讨论的,就是如何用基础算法优化指令操作。$
硬盘控制器中的目标及第一个算法版本
$硬盘控制器负责决定指令该如何执行。$
$从功能上来说,每个硬盘的物理结构可以不同,作为系统无法决定如何组合指令能达到最佳的性能。$
$因此这类决策从功能上,应该由磁盘的控制器自己实现。$
$对控制器而言,CPU的指令一条接一条地到达,这天然地可以用$$\color{Cyan}{【队列】}$$数据结构来描述。$
$接下来我们根据上文所说的指令定义一下数据结构, 方便给出伪代码描述 $
struct Command {
enum op_type; // read or write
size_t disk_start_address; // disk开始地址
size_t len;
size_t memory_start_address; // 内存开始地址
};
$基于这个结构,每个指令的执行时间可以分为三部分: $
Cost = CommandTrans + MemoryLoad(len) + ContextSwitch
$即使不传输任何数据,单纯地收发Command需要一定时间,称为CommandTrans; $
$MemoryLoad指读取数据的时间,它与数据块大小(Len)相关。$
$ContextSwitch则是不同指令间切换需要的时间;$
$比如机械硬盘中,上一个寻址地址到下一个需要机械臂移动的时间。$
$读和写操作之间也需要不同的指令切换时间。$
$我们自然希望磁盘控制器能尽快地完成所有请求的数据,但是根据应用的类型不同,不可避免地需要取舍。$
$比如,硬盘的IOPS和吞吐量。$
$如果读取大量小文件,硬盘需要执行尽量多的IOPS。这时大量的时间执行时间花在通信上,吞吐量自然会降低。$
$如果读取单个大文件,硬盘大量的时间将花在内部的数据读取和传输上,$$这时需要较高的吞吐量,才能尽快完成任务。$
$最基础的一个执行方式:像队列一样先进先出: $
$这里假设所有任务都是单线程模式,暂不考虑加锁的问题。$
std::queue<Command> cmd_queue;
void add(Command cmd) {
cmd_queue.push(cmd);
}
void main_loop() {
while (1) {
if (cmd_queue.empty()) continue;
cmd = cmd_queue.front();
cmd_queue.pop();
exec(md);
sleep(sometime);
}
}
$操作系统可以调用add添加请求,硬盘处理器在main_loop中完成。$
利用算法基础进行改进
$朴素版本的问题也很明显,假设有两个读请求有重复的区间,这个程序仍然会分别执行两遍。$
$回到Cost,至少我们希望$$\color{Orange}{MemoryLoad(len)}$$部分能够减少;$
$另外,如果有连续的间隔不远的小数据,我们也希望它们的操作能够合并。$
$所以我们可以对收到的指令做一个排序,进行$$\color{Cyan}{【区间合并}。$
$在此需要着重考虑的是合并条件,必须避免操作顺序不一致带来的结果不一致$$和因为不断合并导致的有些指令迟迟无法执行。$
$主要考虑的条件如下:$
$\bullet\quad$$两条指令都在待操作队列中。$
$\bullet\quad$$间隔距离不能太长。$
$\bullet\quad$$两条指令之间对涉及的地址不能有其他类型的操作,即读中间没有写操作,写操作没有读操作。$
std::queue<Command> cmd_queue;
void add(Command cmd) {
int end_pos = cmd_queue.size() - 1;
int start_pos = end_pos - MERGE_STEP;
for (int i = end_pos; i > start_pos; i--) {
auto cur_pos = cmd_queue.at(i);
if (cmd.type != cur_pos.type) break;
if (can_merge(cmd, cmd_queue.at(i)) {
merge(cmd, cmd_queue[i]);
};
}
}
void merge(const Command &cmd, Command &cmd_to_upd) {
// 分别记录两个地址对应的内存地址 并 更新cmd_to_upd的地址;
// 这里需要改变数据结构, 每个command存储多个原始指令和对应地址
}
bool can_merge(const Command &a, const Command &b) {
// MERGE_DIS即两个数据块地址的阈值
bool can_merge = !(a.disk_start_address > b.disk_start_address + b.len + MERGE_DIS
|| a.disk_start_address + a.len + MERGE_DIS < b.disk_start_address);
return can_merge;
}
void main_loop() {
while (1) {
if (cmd_queue.empty()) {
sleep(sometime); //队列为空时等待,否则不等;
continue;
}
auto cmd = cmd_queue.front();
cmd_queue.pop();
exec(cmd);
}
}
$这里在每次收到新命令的时候判断是否能合并,以平摊每次合并的开销。$
$计算合并必然会引入一定的额外开销,如果策略命中率太低的话,必定会影响性能。$$策略合不合适,队列大小如何,都需要细致的测试才能决定。$
$对机械硬盘来说,还有位于不同扇区时移动机械臂的$$\color{Orange}{ContextSwitch(len)}$
$这点可以采用排序的方法改进。对一段时间内的扫描请求,可以按扫描位置排序$$然后扫描头按内圈->外圈的顺序扫描一遍。$
$此时主循环需要做相应的变更,每次轮询固定扫描一遍磁盘。$
void main_loop() {
while (1) {
sleep(sometime);
if (cmd_queue.empty()) continue;
sort_by_disk_start_address(cmd_queue);
move_to_begin(cmd_queue.front().start_disk_address); //只移动磁头,不执行命令
for (auto &cmd : cmd_queue) exec(cmd);
}
}
$这种轮询方法也称为$$\color{Brown}{CScan}$$, 是厂家提供的一种策略。$$另外还有其他扫描策略,可参阅:$ 磁盘调度算法
知识点习题指路
Hash基础/桶排序:
队列:
区间合并: