ECS 244: Principles of Concurrent Programming

Subject
ECS 244
Title
Principles of Concurrent Programming
Status
Active
Units
4.0
Effective Term
2016 Spring Quarter
Learning Activities
Lecture - 3.0 hours
Laboratory - 3.0 hours
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.
Prerequisites
ECS 020; ECS 150
Enrollment Restrictions
Pass One and Pass Two open to Graduate Students in Computer Science only.

Summary of Course Content
I. Fundamental Concepts
A. Programming logics
1) Program notation
2) Inference rules for proof outline logic (PL)

B. Sequential programming
1) Invariants
2) Proofs in PL
3) Weakest precondition
4) Program derivation

C. Processes and Process Interaction
1) Concurrency
2) Interference
3) Synchronization
4) Critical section problem

II. Synchronization Based on Shared Variables
A. Busy Waiting
1) Techniques
2) Correctness proofs

B. Semaphores
1) Derivation method
2) Change of variables method
3) Passing the baton method

C. Conditional critical regions
1) Concepts
2) Proof rules
3) Implementation

D. Monitors
1) Concepts
2) Formal semantics
3) Derivation method
4) Implementation
5) Alternative signaling methods

III. Synchronization Based on Message Passing
A. Asynchronous message-passing
1) Naming
2) Synchronization
3) Conversations
4) Implementations

B. Synchronous message-passing
1) Remote procedure call
2) Rendezvous

C. Remote operations
1) Generating invocations
2) Servicing invocations

D. Distributed synchronization
1)Time
2)Clocks

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

ABET Category Content:

Engineering Science: 2 units
Engineering Design: 2 units



Illustrative Reading
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)



Potential Course Overlap
There is no significant overlap with any other course.

Course Category