Concurrent Programming with Threading by Appointment

Threading by Appointment (TAP) is a concurrent programming model that combines automatic stack management (thread-based) with system call queueing (event-driven). However, unlike conventional threads, TAP threads invoke system calls by appointment only, and, unlike events, appointments have a duration to accommodate preemptive I/O and synchronization techniques. The TAP mechanism essentially implements system call queueing using a given TAP policy that consists of a strategy to make appointments, i.e., enqueue system calls, and a logical clock to begin and end appointments, i.e., dequeue system calls. We have obtained encouraging performance results with a TAP policy that resembles traffic shaping in network routers, where system calls are treated as network packets. The policy distinguishes system calls for network and disk I/O, and gives priority to system calls invoked by short-running, interactive threads rather than long-running, bulk threads. We propose to study new concurrency mechanisms and policies as well as new concurrent programming techniques based on threading by appointment. We envision threading by appointment as an integral part of new kernel architectures that support predictable and composable concurrent programming. Our goal is to identify new principles of operating systems and programming languages that enable the design and implementation of complex concurrent applications such as high-performance web servers that are larger and yet more robust than conventionally build systems.

The original aim of this project was to study the role of time in concurrent programming. Yet the actual results not only involve time but also space as well as power. They advance our understanding of how to provide compositional execution environments for concurrent software processes in which the execution of each process is isolated from the other processes in terms of its temporal and spatial behavior and even its power consumption. Such compositionality is key to building robust, large-scale, concurrent software systems. We summarize the key results as follows. The temporal behavior of soft- ware processes (throughput, latency) can be controlled per process, time- and space-efficiently, and power-aware while scheduling overhead can be accounted for in higher system utilization and/or delayed process response (temporal isolation). Memory space can be managed in constant time per allocation and deallocation operation while memory fragmentation can be bounded in linear time per deallocation operation independently of the order of allocation and deallocation operations. Not-needed memory space can be self-collected concurrently and incrementally in constant time per memory management operation independently of the size of programmer-identified needed memory space (spatial isolation). Power consumption can be bounded per process while maintaining temporal isolation even in the presence of non-linear power models and discrete frequency scaling. There is a complex trade-off between compositionality (per-process power consumption jitter) and cost (total power consumption) that depends on multiple factors (power isolation). Finally, relaxing the semantics of concurrent data structures improves scalability on large multicore systems. Relaxation may be strictly or probabilistically bounded and become helpful for providing, e.g. process isolation on multicore hard- ware (non-linearizable computing).