(Note)FreeVGA: Architecture Independent Video Graphis Initialization for LinuxBIOS

Li-Ta Lo et al

LinuxBIOS广泛使用于集群计算的应用，当前它也受到网络设备、桌面和虚拟应用开发者的关注。网络设备、桌面和虚拟应用需要支持多种多样的VGA硬件设备，而LinuxBIOS并不支持多样的VGA硬件。为解决该问题，本文提出了一个处于LinuxBIOS和VGA BIOS之间的兼容层，以来模拟VGA BIOS运行时需要的环境。该兼容层是以x86emu为基础的x86模拟器。

使用非传统方法初始化VGA显卡的方法：

SVGLib：一个提供支持老款VGA显卡通用接口的库。使用x86处理器的vm86模式来执行VGA BIOS，vm86模式下运行32位的程序没异样，但运行16位的代码时它就像是运行在传统8086CPU上。缺点是不可移植，难以调试。[http://www.svgalib.org/]

ADLO：在LinuxBIOS中增加一个BOCH BIOS，LinuxBIOS加载BOCH BIOS和VGA BIOS，并跳到BOCH BIOS执行，BOCH BIOS提供传统BIOS的环境并执行VGA BIOS。缺点是难以调试。[Adam Agnew, Adam Sulmicki, Ronald minnich, Willian Arbaugh. Flexibility in ROM: A stackable open source bios. In 2003 USENIX Annual Techinical Conference]

VIA/EPIA Port：实现一个跳板（trampoline）以在16位和32位模式之间切换，运行VGA BIOS直接在16位模式运行，但使用32位C代码来模拟标准的BIOS回调功能。缺点是不可移植，难以调试。

XFree86：为了支持多体系结构（但使用的仍是x86的显卡），在LinuxBIOS中加入一个x86模拟器x86emu，将VGA BIOS rom中的代码拷到内存有x86的模拟器执行。缺点是VGA硬件的初始化比较晚。[http://www.xfree86.com/]

FreeVGA：和XFree86类似，但对硬件的初始化比较早，并且使用以x86emu为基础的x86模拟器。

相关文章：
AMD. BIOS and Kernel Developer's Guide forAMD Athlon 64 and AMD OpteronProcessors, May 2003.
Richard F. Ferraro. Programmer's Guide to theEGA, VGA, and Super VGA Cards. AddisonWesley,1994.
Ron Minnich, James Hendricks, and Dale Webster.The Linux BIOS. In Proceedings of theFourth AnnualLinux Showcase and Conference, Atlanta, GA,October 2000.
Gregory R. Watson, Matthew J. Sottile, Ronald G.Minnich, Erik A. Hendriks, and Sung-EunChoi.Pink: A 1024-node single-system image linux cluster.In Proceedings of HPC Asia2004, Toyko,Japan, July 2004.

(SOSP'05 Note)Speculative Execution in a Distributed File System

Speculative Execution in a Distributed File System
Edmund B. Nightingale et al.
SOSP 2005

本文讨论了在分布式文件系统中支持进程级推测执行的问题。一个激动人心的主题。

Speculative Execution不是一个新的技术，在CPU设计中已经广泛使用。IA-64的EPIC架构中，speculative execution就是一个很重要的主题。（想想还是六、七年前接触这个词了。）作者将其思想应用在进程级别，修改OS使之支持进程speculative execute，并在失败时rollback。Introduction中是这样说的：
"We demonstrate that, with operating system support for lightweight checkpointing, speculative execution, and tracking of causal interdependencies between processes, distributed file systems can be fast, safe, and consistent. Rather than block a process while waiting for the result of a remote communication with a file server, the operating system checkpoints its state, predicts the result of the communication , and continues to execute the process speculatively. If the prediction is correct, the checkpoint is discarded; if it is false, the application is rolled back to the checkpoint."

作者的动机很清晰。NFS之类的分布式文件系统，虽然client端有cache，但为了保证cache的一致性，仍需要使用同步的远程调用对cache进行确认。由于cache不一致的概率是很低的，如果OS可以支持speculative execution，那么可以让进程先按照cache里的内容继续执行，同时异步地向服务器进行查询，发现错误后对进程进行回滚。作者明确列出了这种推测执行方法适用地条件：
1. The results of speculative operations are highly predictable.
2. Checkpointing is often faster than remote I/O.
3. Modern computers often have spare resources.

要推测执行，首先要在开始推测时建立checkpoint，以便rollback。本文所采用的方法是：在系统调用的入口进行fork，利用fork的copy-on-write机制，为进程构造推测执行的副本，并对内核对象进行跟踪，记录必要的undo操作。为了保证其正确性，需要确保下面两个条件：
1. Speculative state should never be visible to the user or any external devices.
2. A process should never view speculative state unless it is already speculatively dependent upon that state.

文章用了很多篇幅讨论因果依赖关系的传播问题，包括各种对象如何传播依赖关系等，例如：本地内存、本地文件、管道、FIFO、socket、signal等等。作者在NFS和BlueFS（作者开发的一个分布式文件系统）上应用了speculation技术。NFS中处理修改操作时，通过将依赖关系通知server（需要修改底层RPC），在Server一端解决了推测假定的判断问题，也算是一种bypass吧。

当然，speculation execution也不是作者发明的，请看作者对其工作的定位：
"To the best of our knowledge, Speculator is the first support for multi-porcess speculative execution in a commodity operating system and the first use of speculative execution to improve cache coherence and write throughput in distributed file systems."

P.S. 对于分布式文件系统的cache coherence问题，已有的一些策略如下：
1. polling the file server－向服务器确认cache是否有效，NFS和BlueFS是此类；
2. callbacks－由服务器通知客户端，AFS和Coda属于此类；
3. leases－客户端获得排他访问租约，SFS（也用callback）和Echo属于此类。

总之，一篇好文章，推荐大家读读。不同领域的思想嫁接，很棒！不过，我还没有想清楚除了DFS，还有什么应用可以用speculative execution。

(SOSP'05 Note)Hibernator: Helping Disk Arrays Sleep through the Winter

Hibernator: Helping Disk Arrays Sleep through the Winter
Qingbo Zhu et al.
SOSP 2005

本文讨论了数据中心中磁盘阵列节电的问题。

服务器磁盘阵列的耗电在整个服务器耗电中所占的比例是比较大。与CPU节电等使用动态速度、电压调整技术相比，磁盘的速度切换是比较困难的（需要相关硬件支持，SONY有产品），也是比较慢的（10s级别），代价也是比较高的（会影响磁盘寿命，也启动磁盘时耗电量很大）。作者讨论的磁盘阵列节电技术，仍然从降低磁盘旋转速度出发，但充分考虑了上述因素，采用了大时间粒度的调整策略，将磁盘阵列按照速度分层（tier），每层的磁盘速度相同，但层之间可能不同。根据性能监测结果，采用temperature-based方法将数据在速度不同的各层之间有效分布（访问多的放在高速运行的磁盘上）。在各层内部，仍然使用RAID5存储数据。

除了基本思想，文章讨论了数据分布的问题，对于relocation blocks(RBs)，可能需要根据temperature在层之间移动，怎样减小移动次数当然很重要。

另外，由于数据中心可能会对提供的服务性能作出承诺，若何保证性能在合同许可范围之内也是一个问题。一个简单的思路就是如果性能下降到阈值，就将所有硬盘调整到全速。

如果熟悉动态电压调整（DVS）等CPU功耗的话题，读读这篇文章可能会收获些新的角度、新的思考。