| |
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.
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.
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.
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.
|
|
