Department of Mathematics & Computer Science

MC306 Programming Concurrent Computer Systems

Explanation of Pre-requisites

It is desirable that students have some knowledge of the elementary discrete mathematics and basic skills in abstraction and rigorous reasoning.

Course Description

Programming Concurrent and Distributed Computer Systems is an important and currently active field in computer science research. This module also provides the essential background for further study and research in this and related topics such as distributed systems, real-times systems and fault-tolerant systems.

Aims

Objectives

• To understand the nature of concurrent and distributed computer systems, and the concepts of non-determinism, interleaving, concurrency, synchronisation, and communication (interaction);
• to be able to analyse important properties of concurrent programs executions, such as safety, liveness, deadlock and livelock;
• to understand the abstraction and solutions to the problems of mutual exclusion, condition synchronization, producers and consumers, readers and writers, dining philosophers, resource allocation, and automatic control systems;
• to grasp techniques and to develop the skills in the use of the tools: busy waiting, semaphores, Monitors, synchronous message passing and remote invocation, to solve problems in concurrent programming.

Transferable Skills

• The ability to understand the models semaphores and monitors and skills in programming them are important in design and implementation of multi-tasking operating systems;
• the ability to understand and use the model of synchronous message prepares the students with the skills to understand and write programs in Occam or a similar language;
• the ability to understand and use the model of remote invocation enables students to understand and write programs in Ada or a similar language;
• the students who master the material offered will be prepared not only to write concurrent programs or to read the research literature, but also to evaluate systems, algorithms and languages from a broad perspective.

Syllabus

Problems in concurrent programming: Non-determinism, synchronisation, communication, critical sections, atomic actions.

Mutual exclusion and condition synchronisation: Communication via shared variables, multiple updating problem, active and passive objects, abstraction of mutual exclusion and condition synchronisation, old-fashioned recipes for synchronisation, notions of busy-waiting, deadlock, livelock, safety, and liveness.

Semaphores: Motivations and definitions, implementation issues, programming techniques using semaphores (the producers and consumers problem, the readers and writers problem, and the dining philosophers problem), reasoning about semaphore programs.

Conditional critical regions and monitors: Motivations and definitions, implementation issues, programming techniques using CCRs and Monitors (the producers and consumers problem and the readers and writers problem), reasoning about monitor programs.

Synchronous message passing: Distributed computing, asynchronous vs synchronous, channels for inter-process communication and synchronisation, selective waiting construct for non-determinism, implementation issues, programming techniques using message passing.

Remote invocation: Motivation and definitions, message passing and synchronisation with remote invocation, client-server paradigm of process interaction, implementation issues, programming techniques using remote invocation.

Summing up: summary of the course and industry relevance.

Reading list

Essential:

A. Burns and G.Davies, Concurrent Programming, Addison-Wesley 1993.

Recommended:

M. Ben-Ari, Principles of Concurrent Programming, Prentice-Hall 1982.

M. Ben-Ari, Principles of Concurrent and Distributed Programming, Prentice-Hall 1990.

G.R. Andrews, Concurrent Programming - Principles and Practice, The Benjaming/Cummings Publishing Company, Inc. 1991.

G.R. Andrews and R.A. Olsson, The SR Programming Language, Benjaming/Cummings Publishing Company, Inc. 1993.

J.G.P. Barnes, Programming in Ada (3rd Edition), Addison-Wesley 1991.

G. Jones and M. Goldsmith, Programming in occam 2, Prentice-Hall 1988.

Background:

R. Milner, Communication and Concurrency, Prentice-Hall 1989.

C.A.R. Hoare, Communicating Sequential Processes, Prentice-Hall 1985.

A. Burns and A. Wellings, Real-Time Systems and Their Programming Languages, Addison-Wesley 1990.

Details of Assessment

The written January examination contains six questions, and candidates can obtain full marks from four good questions.

Author: S. J. Ambler, tel: +44 (0)116 252 3884
Last updated: 10/4/2000
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.