CMSC 356: Concurrency and Co-Design in Operating Systems
Instructor:
John Dougherty
Semester: Spring 2009
Schedule: Lecture T/Th 1:00-2:30; Lab t.b.a.
Texts: t.b.a.
Requirements: Exams, weekly homework or lab assignments, class participation.
Collaboration: You are encouraged to discuss the lecture material,
labs, and written work with other students, subject to the following
restriction: the only "product" of your discussion should be your memory of
it - you may not write up solutions together, or exchange written work or
computer files.
Collaboration is not allowed on exams.
Prerequisites: CMSC 240
Concurrent enrollment in this and two other CMSC lab courses requires permission of the instructor.
Related Courses: CMSC 355: Operating Systems
is usually taught by Dianna Xu (at Bryn Mawr)
with an emphasis on the "kernel design" and "security" aspects of an operating system.
CMSC 356 briefly touches on these issues (to provide context),
but focuses primarily on general issues of shared-memory concurrency
and on the role of hardware/software co-design in the creation of
the "device driver" components of an operating system
(these typically treated only briefly in CMSC 355).
The instructors for CMSC 356 have communicated with Dianna Xu to ensure
minimal content overlap, so that students can take both courses for credit.
Description: A practical introduction to the principles of
shared-memory concurrent programming
and of hardware/software co-design,
which together underlie modern operating systems.
This course includes a substantial laboratory component
using Java and
HERA.
Topics covered in this course include:
- Programming with multiple "threads" of execution
- synchronization/sharing primitives: semaphores, message passing,
and monitors
- pitfalls of multithreaded software: race conditions, livelock, and
deadlock
- classic multiprogramming problems, such as the dining philosophers
problem
- Operating system design
- providing multi-threaded execution on a single processor
- including scheduling policies and algorithms
- management of shared and unshared memory
- virtual memory
- file system management
- input and output
- security
Note that topics listed in italics are mentioned only
briefly; for an in-depth treatment of this material that does not
include as much emphasis on concurrent software design,
hardware/software co-design or the writing of "device drivers"
within an operating system, see
CMSC355 at Bryn Mawr.
Schedule:
// Much of the course will
focus on principles of concurrent programming, drawing primarily from Doug
Lea's book;
interspersed with this will be elements of
hardware/software co-design for simple I/O.
If time permits, additional lectures may focus on
other aspects of operating system design and implementation
or concurrent programming.
((
- Concurrent execution and data races (OSC-J 5.7, Lea 2.2 (first
page))
- Design forces for concurrent software, especially deadlock, starvation,
and throughput (Lea 1.3)
- Paradigms for concurrent programming
- The "Pure functional" approach: "Initialize and Publish" (brief mention)
- Locking and Semaphores (OSC-J 7.5 except the section on implementation)
- Monitors (OSC-J 7.7)
- Message Passing (see CMSC 392)
- Atomic Transactions (brief mention)
- Concurrent programming techniques
- Immutability (Lea 2.1)
- Exclusive access to a single resource (Lea 2.2-2.2.5)
- Two-phase locking for multiple resources
- Resource ordering for multiple resources (Lea 2.2.6)
- Detection and response to deadlock, e.g. rollback (Lea 3 - 3.2)
- Ad-hoc solutions
) & (
- I/O hardware (Mano 11.1-11.2)
- Memory-mapped I/O
- Transfer modes (Mano 11.4)
- Polled and Interrupt-based I/O (Mano 9.9, 11.5-11.6)
- Processor Management and Thread Switching
- Implementation of Process Synchronization Primitives
));
// Advanced topics such as:
(
- Concurrency and transactional systems
- Processor scheduling
- Memory management
)
Lab Assignments:
- Lab 1: The Perils of Concurrency [HTML | PDF]
- Lab 2: Hardware and Software for Polled I/O [HTML | PDF]
- Lab 3: Concurrent Programming [HTML | PDF]
- Lab 4: Hardware and Software for Interrupt-Driven I/O [HTML | PDF]
- Lab 5: Adding functionality to HERA and HERACLOS [HTML | PDF] (Time Permitting)
