CMSC 356: Concurrency and Co-Design in Operating Systems

Semester: Spring 2013

NOTE If you are considering this class for the Spring of 2013, but are not preregistered, please contact email Dave W to be included in planning discussions.

Schedule: Attendance at all of the following is a requirement of the course:

Lecture M/W 2:30-4:00 in KINSC H110 (the CS teaching lab);
Lab T 2:30-3:30 or 1 hour t.b.a. on T/W 10AM-2:30PM;
Individual "interactive grading"/status meetings 15 minutes/week t.b.a.

Required Texts/Resources:

Prior knowledge of Java or access to the suggested sections of the Java tutorial
Java Concurrency in Practice, available in both paper (from the bookstore, though possibly a bit late due to slowness on the part of Dave W) and ebook (Kindle, Google Play books, maybe others) editions.
The Haverford Educational RISC Architecture by David Wonnacott (this booklet is available with a nice cover at the Haverford book store (the lulu.com version, but without the shipping cost) or you can print your own (without the cool cover) from the HERA web site)

Additional Recommended Texts:

A computer organization textbook, such as either: Computer Engineering: Hardware Design, by M. Morris Mano or Digital Design and Computer Architecture, by David Harris and Sarah Harris
For those wanting more treatment of traditional O.S. topics (i.e., for preparing for the CS GRE), Operating System Concepts with Java (a.k.a. OSC-J), by Silberschatz, Galvin, and Gagne
For those wanting even more information about concurrent programming techniques, Concurrent Programming in Java: Design Principles and Patterns, by Doug Lea

Requirements:

Exams,
individual and team lab assignments,
attendance at "interactive grading"/status meetings,
class participation (includes attendance, in-class exercises, "mini-homework" assignments, and reading/responding to email including the hc-cs356-s13 mailing list).

Collaboration: You are encouraged to discuss the lecture material, labs, and written work with other students, subject to the following restriction: on individual lab assignments, 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. On Team assignments, you may exchange other materials only within your team; on Mini-homework assignments, you are encouraged to work together as much as you like.

Collaboration is not allowed on exams.

Prerequisites: CMSC 240; Concurrent enrollment in this and two or more 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 more traditional operating system course elements (such as O.S. organization, resource allocation policies and algorithms, and security). 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 (the latter is usually treated briefly in O.S. courses).

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 in a shared-memory system
- creating and using threads
- race conditions
- avoiding races with synchronization, locks, and other approaches
- deadlock and livelock
- classic multiprogramming problems, such as the dining philosophers problem
Co-design in Operating Systems: hardware and software for
- polled I/O
- interrupt-based I/O
- simulating multi-threaded execution on a single processor
- protected memory segments and independent address spaces
- various other O.S. subsystems, if time permits

Schedule:

// Much of the course will focus on principles of concurrent programming; 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. Page numbers below refer to previous years' textbooks; current readings are being added as we go, on this document.

((

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
Lab 2: Hardware and Software for Polled I/O
Lab 3: Concurrent Programming
Lab 4: Hardware and Software for Interrupt-Based I/O
Lab 5: A thread-safe ADT in Java
Lab 6: Final project: Other approaches to concurrency (Actors paradigm, Transactional paradigm, implementation of threads in HERA)

Page maintained by David Wonnacott.
Computer Science Department, Haverford College.