Computer Laboratory

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.


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.


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