Operating System Transactions

Operating systems manage resources, including files, memory mappings, pipes, and child processes, for applications, yet do not provide a mechanism for applications to ensure logically consistent updates. For instance, the file referred to by a path name may change between a stat system call and an open, allowing a malicious process to trick an honest one into opening an incorrect file (this race condition is commonly referred to as a Time-Of-Check-To-Time-Of-Use, or TOCCTOU race). As multi-core chips and OS-level concurrency become widespread, race conditions in the system call API will become increasingly problematic.

This research project aims to address this issue by adding transactions to the system call API. A system transaction executes a series of system calls in isolation from the rest of the system and atomically publishes the effects to the rest of the system.

TxOS is a proof-of-concept implementation of system transactions in the Linux 2.6.22.6 kernel. TxOS runs on commodity hardware and supports transactional semantics for 150 system calls.

Code Release

The TxOS source code is available here, by anonymous svn or tar.bz2 download.

Publications

Frequently Asked Questions

What is the performance overhead of using transactions?
It varies with workload, but for larger-scale benchmarks it in the very reasonable range of 1-2x overhead.
While further engineering may lower these overheads, system transactions incur a certain amount of unavoidable overheads. As a result, TxOS is designed to minimize the overhead for applications that do not use transactions. Currently, the overhead for non-transactional system calls on on TxOS ranges from 0-50%.

Is TxOS a transactional file system?
No, transactions in TxOS apply to all system-managed resources, not a single file system. As a result, much of the functionality needed to implement a transactional file system, such as conflict detection and version management, is implemented in shared kernel code, rather than file system-specific modules. This shared kernel code makes it fairly simple to convert a standard Linux file system, such as ext3 into a transactional file system.

What happens in TxOS if an application performs I/O in a transaction?
When an application writes to a device or socket, the OS generally buffers the data in memory for a time so that it may optimally schedule device accesses. TxOS leverages this buffering to hold writes in memory until a transaction commits. This approach supports a fairly simple implementation and incremental adoption.
There are two limitations to this that will be explored in future work. First, the amount of data that a transaction can access must fit in main memory. This can be ameliorated by spilling data to swap or unused disk blocks.
The second problem is that this prevents an application from sending a request out on the network and receiving a response in the same transaction. There are many network requests that are idempotent or protocols that could support transactions.

How do system transactions relate to transactional memory?
Transactional memory (TM) provides the abstraction of atomic and isolated access to memory. TM can be implemented in software or hardware, and generally targets user-level data structures. A key problem for TM is that it does not isolate or atomically execute system calls.
System transactions can be integrated into TM systems to extend the ACID properties from user-level memory to include system calls. We have extended both a hardware TM system (MetaTM) and a software TM system (DATM-J) to use system transactions.

Do system transactions require transactional memory?
No. Moreover, transactional memory applied by rote to the OS is insufficient to provide system transactions; OS extensions are required. TxOS does apply techniques and insights from TM to implement system transactions.

How is TxOS related to TxLinux?
While both systems were built by many of the same researchers, the systems were built to explore completely unrelated questions
TxLinux is a system that extended Linux to use hardware TM for synchronization within the kernel. TxLinux does not change the API the OS presents to applications, and is insufficient to provide system transactions. Moreover, TxLinux requires hardware that is not yet available, whereas TxOS runs on commodity hardware.

Can system transactions be implemented in other operating systems?
Yes. While our prototype implementation is on Linux, our techniques are sufficiently general that they could be adopted by other operating systems.

People

Other contributors