Computer Science @ UC Davis | Course Descriptions

ECS 244 PRINCIPLES OF CONCURRENT PROGRAMMING (4) I

Lecture: 3 hours

Laboratory: 3 hours

Prerequisite: Courses ECS 20, ECS 150

Grading: Letter; based on 4-5 homework sets/labs (70%) and a final (30%)

Catalog Description:
Fundamental concepts and applications of concurrent programs; concurrent program verification and derivation; synchronization mechanisms in programming languages; distributed programming techniques; case studies of languages.

Goals:

Understanding of basic concepts and techniques in concurrent programming
Understanding the synchronization methods available in concurrent programming languages
Understanding the role of axiomatic semantics in both deriving and understanding concurrent programs
Gain hands-on experience in writing concurrent programs that use explicit synchronization mechanisms

Expanded Course Description:

Fundamental Concepts
1. Programming logics
  1. Program notation
  2. Inference rules for proof outline logic (PL)
2. Sequential programming
  1. Invariants
  2. Proofs in PL
  3. Weakest precondition
  4. Program derivation
3. Processes and Process Interaction
  1. Concurrency
  2. Interference
  3. Synchronization
  4. Critical section problem
Synchronization Based on Shared Variables
1. Busy Waiting
  1. Techniques
  2. Correctness proofs
2. Semaphores
  1. Derivation method
  2. Change of variables method
  3. Passing the baton method
3. Conditional critical regions
  1. Concepts
  2. Proof rules
  3. Implementation
4. Monitors
  1. Concepts
  2. Formal semantics
  3. Derivation method
  4. Implementation alternative signaling methods
  5. Alternative signaling methods
Synchronization Based on Message Passing
1. Asynchronous message-passing
  1. Naming
  2. Synchronization
  3. Conversations
  4. Implementations
2. Synchronous message-passing
  1. Remote procedure call
  2. Rendezvous
3. Remote operations
  1. Generating invocations
  2. Servicing invocations
4. Distributed synchronization
  1. Time
  2. Clocks

Textbook:
G.R. Andrews, Concurrent Programming: Principles and Practice, Benjamin/Cummings, 1991.

R.A. Olsson and A.W. Keen, The JR Programming Language: Concurrent Programming in an Extended Java, (draft).

Homework:
Each homework set includes programming problems (see Laboratory section below) in addition to problems dealing with program derivation, correctness proofs, developing inference rules and implementation techniques.

Laboratory:
Students work individually or in small groups on several programming problems, which are an integral part of the homework sets. These projects are designed to reinforce and complement the lecture material. The specific problems are programmed using the JR concurrent programming language. For shared variables, semaphores, and rendezvous problems, students write programs in native JR. For CCRs (Conditional Critical Regions), monitors, and CSP (Communicating Sequential Processes) problems, students write programs using preprocessors for JR that support those notations. Students therefore gain hands-on experience in using a wide range of synchronization mechanisms.

Engineering Design Statement:
The course material includes design and implementation issues in concurrent programming. Lectures discuss various synchronization mechanisms, how they are implemented, and the tradeoffs (usability, efficiency, etc.) between them. The homework sets including the laboratory problems follow these themes too. They also examine in detail the different programming styles that result in using the different constructs. Homework sets grades are based in part on these design issues. Examination questions are based on design issues discussed in lecture and from the homework.

ABET Category Content:
Engineering Science: 2 units
Engineering Design: 2 units

Instructors: R. Olsson, R. Pandey

Prepared by: R. Olsson, R. Pandy (March 2003)

Overlap Statement: There is no significant overlap with any other course.

Revised: 3/03

Back to Course Descriptions