Reading Papers - Speculative Execution
# Overview
# Kernel-Level Speculation
# ATC'03 - I/O Speculation
本文在 Linux Kernel 上实现了基于 speculative execution 的 disk data prefetcher ,利用等待 I/O 返回的空转时间预取未来可能读取的数据以改善 I/O 效率。
ATC'03 - Operating System I/O Speculation - How Two Invocations are Faster than One
Taxonomy : speculative execution / operating system / disk io / data prefetching
Tag : disk io / data prefetching
Preceding Work : (to-read) OSDI'99 - Automatic IO Hint Generation Through Speculative Execution
本文划分并让 kernel 区别对待两种不同的进程:normal process 即系统中原有的进程,当其正常执行因磁盘 I/O 而阻塞时,会通过 fork 产生 speculative process 。
speculative process 假装此次磁盘 I/O 已经完成,在 non-resident data 不存在的情况下继续执行后续程序,直到下一次磁盘 I/O 时发起 data prefetch ,以便 normal process 执行到此处时减少磁盘 I/O 阻塞时长。
如果 disk read 由显式的文件读取操作产生,(没看懂)
如果 disk read 由 pagefault 产生,
为保证 speculative execution 的安全性,speculative process 被禁止主动向父进程传递信息,其所有共享内存访问被改变为 copy-on-write access ,其系统调用受到限制或改变:对于被认为是不安全的系统调用,kernel 会根据情况拒绝其执行或改变为对外界不可见的执行(例如 copy-on-write)。
可能导致 speculative execution 失败的原因有很多,例如未来的执行中存在对 non-resident data 的依赖,或是涉及被拒绝的系统调用,等等。在遭遇失败时,父进程会尝试与 speculative process 同步(同步具体做了什么?为什么能提高子进程生成有用的 prefetch 的概率?)
在理想情况下,speculative execution 仅占用系统的空闲资源,对系统正常执行的效率没有影响。为了尽可能接近,本文采取了以下策略来限制 speculative process 的资源占用率:
在 scheduler 中为 speculative process 赋予最低的优先级,仅在无可调度线程时才启用,任何 normal process 被激活都会立即发生抢占。
引用其它工作中的技术,仅允许对正在处理不超过一个请求的磁盘发起 prefetch ,以避免 speculation 挤占正常磁盘 I/O 的带宽;
引用其它工作中的技术,使用启发式策略计算一个 threshold 用作估算 speculation 将不再能带来好处的最大 prefetch 个数,避免过快地生成过多的 speculative process 。
当 speculative process 终结时(例如抛出异常或执行到 exit 系统调用),若其父进程还在执行中,暂缓终止并回收其内存,直至父进程终止或尝试与之同步。
# 性能优化
为改善 speculative execution 的性能,需要保证同步操作不会影响到父进程正常执行的性能。本文的方法是定期检查先前阻塞的磁盘 I/O 是否完成,若完成则立即暂停 normal process 与 speculative process 的同步尝试。
one-way copy-on-write
memory overhead control
TBD.
# SOSP'05 - Speculator
Speculator 在 Linux Kernel 上实现了对 speculative execution 的支持,目标是在改善分布式文件系统性能的同时不影响其一致性和安全性的保障。
SOSP'05 - Speculative Execution in a Distributed File System
Taxonomy : speculative execution / operating system / distributed file system
Tag : causal tracking / distributed file system
诸如 NFS 的分布式文件系统普遍存在性能问题,需要 client 和 server 之间频繁同步信息以维护 cache consistency 。尽管许多 NFS 的实现都牺牲了一定的一致性,例如可能仅为文件提供 close-open consistency ,但是同步开销仍然很大。
Speculator 的可行性由以下几点保证:
大多数 fs operation 的结果是可预测的:distributed fs 的 client 在本地维护 cache ,而并发文件修改是少见的,大部分情况下不会发生 cache conflict ,因此 cache 可用于高效且高准确率的预测;
lightweight checkpoint 的时间开销比 remote I/O 要小得多;
现代计算机系统通常有足够的空闲资源来支撑 speculative execution 。
Speculator 的设计提供了策略和机制的分离:分布式文件系统控制 speculative execution 何时发起,并定性其成功或失败;实现在 Linux 内核中的 Speculator 提供支持 speculative execution 的底层机制,并对文件系统隐藏,仅暴露 create, commit, fail 三个行为接口。
正确的机制需要保证 speculative 的系统状态和执行流对外界(包括用户、外设、non-speculative process)保持不可见,以保证 speculative fs 的语义相对于 non-speculative fs 不变。
# Speculator 实现
TBD.
# EuroSys'11 - Application-Specific Speculation
本文将 speculative execution 的策略和机制分别实现在 kernel level 和 application level ,同时 argue 了这种设计的必要性和价值。
EuroSys'11 - Operating System Support for Application-Specific Speculation
Taxonomy : speculative execution / operating system
Tag : system design / application-level support
TBD.
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01