Theory, in Practice

Programming Dynamic Multithreaded Algorithms Charles E. Leiserson and Bradley C. Kuszmaul
This series of lectures teaches dynamic multithreaded programming using the Cilk language, which has been developed at MIT. Cilk's fork-join programming semantics provide a simple but processor-oblivious computing model. Cilk programs can be scheduled on a multiprocessor with provable efficiency using a randomized work-stealing algorithm. Students will learn how the algorithmic measures of work and critical-path length can be used to predict and analyze the performance of multithreaded algorithms. The lectures will be coupled with several laboratories, where the students will explore this versatile model of computing through hands-on programming.

Design and Implementation of Concurrent Systems Matthew Flatt
Operating systems have successfully supported concurrency for decades through separate processes. OS-style processes are too heavyweight and coarse-grained for most application-level concurrency, but a safe programming language can provide process-like abstractions at a much lower cost. When processes become a central part of the program organization, then programmers need good abstractions for organizing processes and communications, so we will study Reppy's Concurrent ML. In addition, programmers need a way to terminate processes and account for resources, so we will look at PLT Scheme's custodians. Finally, we will consider the combination of Concurrent ML and custodians, and how programmers can implement communication patterns that are robust against termination of one communication party.

Concurrency in Practice for C Jeff Foster
There are a multitude of software programs written in legacy languages that have little or no support for ensuring that multi-threaded applications are safe. In these lectures we will look at how concurrent programs are written in these languages today, including synchronization as used in low-level programs such as the Linux kernel. We will investigate techniques that use static analysis for reasoning about such software. In particular, we will look at the problem of inferring the guarded-by relationship, which is a commonly-used technique for enforcing mutual exclusion in which each shared memory location is guarded consistently by at least one lock. We will discuss recent work on static race detection system for C programs based on an extension of alias analysis algorithms.

Making Concurrent Software Safer Michael Hicks
These lectures will present three approaches that use programming language technology to make it easier to write correct concurrent code. The first lecture will cover work on dynamic annotation inference, which uses execution traces in combination with type checking to prove race freedom for Java programs. The second lecture will cover work on using transparent proxies in Java to implement asynchronous method invocations that may return futures. Finally, the last lecture will discuss work on dynamic software updating (DSU), which supports dynamically modifying a running program to fix bugs or add new features. Many systems that are expected to run non-stop, and which would benefit from DSU, are multi-threaded or distributed, and this makes it more challenging to ensure that updates are safe.


This page is the property of the University of Oregon