CMSC 356: Concurrency and Co-Design in Operating Systems

Instructor: David Wonnacott

Semester: Spring 2011

Schedule: Lecture T/Th 1:00-2:30; Lab t.b.a.

Texts:

• Operating System Concepts with Java (a.k.a. OSC-J), by Silberschatz, Galvin, and Gagne
• Concurrent Programming in Java: Design Principles and Patterns, by Doug Lea
• 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)
• Recommended (for occasional reference, and in the library): either of the CMSC 240 textbooks (your choice): Computer Engineering: Hardware Design, by M. Morris Mano or Digital Design and Computer Architecture, by David Harris and Sarah Harris

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

• 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-Driven I/O
• Lab 5: Choice of
  • Adding Functionality to your HERA System
  • Advanced Topics in Shared Memory Concurrency