MC306 Programming Concurrent Computer Systems

Next: MC307 Communication and Concurrency Up: Year 3 Previous: MC301 Formal Software Specifications

MC306 Programming Concurrent Computer Systems

Credits: 20

Convenor: Dr. Z. Liu

Semester: 1

Prerequisites:	essential: MC103	desirable: MC111
Assessment:	Continual assessment: 30%	Three hour exam in January: 70%

Lectures:	26	Classes:	none
Tutorials:	10	Private Study:	90
Labs:	24	Seminars:	none
Project:	none	Other:	none
Total:	150

Explanation of Pre-requisites

It is essential that students have taken a first course in basic programming, which includes skills involving both coding and design of sequential programs, to a level which includes the use of data types, functions and procedures.

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

Course Description

This course is about design and writing programs containing multiple processes that execute on parallel computers concurrently and interactively (or co-operatively) with each other. It provides a revolutionary insight in programming that allows us to cast off the shackles of sequential thought. This is both theoretically and practically very important as parallel computers become more common, and computers become more parallel.

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

The module will focus on basic concepts, principles and techniques in the programming of concurrent and distributed computing systems, and not on specific systems or languages. It provides students with methods in design and practical skill in writing concurrent programs in a variety of language models exemplifying different programming paradigms, including shared memory-based programming, Occam and Ada programming.

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

Break Away from single thread computation: Sequential programming, single processor system, sequential programming as total ordering (single-thread computation), multi-thread computation and its advantages, multi-processor system, concurrent programming as partial ordering, single-processor multi-tasking system, concurrent programming as interleaving.

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.

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 coursework for the continual assessment consists of five worksheets containing problems that test the ability to understand, analyse and write concurrent programs, as well as the conceptual aspects of the course.

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

Next: MC307 Communication and Concurrency Up: Year 3 Previous: MC301 Formal Software Specifications

Roy L. Crole
10/22/1998