Course material 2010–11
Concurrent and Distributed Systems I
Lecturer: Dr B.N. Shand
No. of lectures: 8
Prerequisite courses: Operating Systems, Programming in Java
This course is a pre-requisite for Mobile and Sensor Systems (Part II).
These eight lectures, together with the eight in the Lent Term, form a single course of 16 lectures.
Aims
The aim of the Concurrent and Distributed Systems course is to introduce concurrency control and distribution concepts and their implications for system design and implementation.
Lectures on Concurrency (Michaelmas Term)
- Introduction; thread models.
Overview of properties of distributed and concurrent systems. Software
system structure. Occurrence of concurrency in systems. Recap of scheduling
and preemption. Thread models.
- Classical concurrency control.
Shared data and critical regions. Mutual exclusion and condition
synchronisation. Semaphores. Implementation of concurrency control.
- Classical problems using semaphores.
Bounded cyclic buffer (producer(s) and consumer(s)), multiple readers and
writers. Problems arising in semaphore programming.
- Concurrency support in programming languages.
Shared data: monitors, pthreads, Java. No shared data: occam, Ada active
objects, Erlang, Kilim, tuple spaces.
Lock-free programming.
- Concurrent composite operations.
Composite operations in main memory and persistent memory. Dynamic
resources allocation and deadlock. Dining philosophers program. Deadlock
detection and avoidance.
- Transactions.
ACID properties. Concurrency control and crash recovery. Definition of
conflicting operations. Serialisation. Cascading aborts.
- Database concurrency control.
Pessimistic concurrency control: two-phase locking, timestamp ordering.
Optimistic concurrency control.
- Database recovery and summary of “Concurrency”.
Write ahead log, undo/redo. Points to take forward.
Objectives
At the end of the course students should
- understand the need for concurrency control in operating systems and
applications, both mutual exclusion and condition synchronisation;
- understand how multi-threading can be supported and the implications of
different approaches;
- be familiar with the support offered by various programming languages for
concurrency control and be able to judge the scope, performance
implications and possible applications of the various approaches;
- be aware that dynamic resource allocation can lead to deadlock
- understand the concept of transaction; the properties of transactions,
how concurrency control can be assured and how transactions can be
distributed;
- understand the fundamental properties of distributed systems and their
implications for system design;
- understand the effects of large scale on the provision of fundamental
services and the tradeoffs arising from scale;
- be familiar with a range of distributed algorithms.
Recommended reading
* Bacon, J. & Harris, T. (2003). Operating systems: distributed and concurrent software design. Addison-Wesley.
Bacon, J. (1997). Concurrent Systems. Addison-Wesley.
Tanenbaum, A.S. & van Steen, M. (2002). Distributed systems. Prentice Hall.
Coulouris, G.F., Dollimore, J.B. & Kindberg, T. (2005, 2001). Distributed systems, concepts and design. Addison-Wesley (4th, 3rd eds.).