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.
