Academics
  /  
Courses
  /  
Descriptions
COMP_SCI 343: Operating Systems

Quarter Offered

Fall : 11:20-12:40 TuTh ; Ghena
Winter : 11-12:20 TuTh ; Dinda

Prerequisites

Comp_sci 214 and (213 or Comp_Eng 205)

Description

A fundamental overview of operating systems (OSes) with an emphasis on practice.   Topics covered include: OS structure, OS models, OS abstractions, concurrency sources, concurrency challenges, concurrency control, scheduling and resource management, virtual memory, device drivers, protection and security, memory management, file systems, and design principles. Requires substantial low-level programming projects at both user-level and within a kernel. 

  • This course satisfies the Systems breadth & project requirement.

REFERENCE TEXTBOOK as Winter: Andrew S. Tanenbaum and Herbert Bos, Modern Operating Systems, 4th Edition, Pearson, 2014, (ISBN-13: 978-0133591620, ISBN-10: 013359162X)

COURSE INSTRUCTOR(S): Prof. Dinda (Winter), Prof. Ghena (Fall)

COURSE COORDINATOR: Prof. Peter Dinda

COURSE GOALS: This course introduces you to the basic, foundational concepts and principles of operating systems, many of which generalize to other areas of computer science and engineering. You will learn many of these concepts and principles by applying them in practice on a modern machine through labs that are designed to put you in the shoes of a systems-level developer operating at both user-level and within the kernel. OS (and systems more broadly) is very much a learn-by-doing kind of area.

DETAILED COURSE TOPICS:

  • OS Structure: kernel, device drivers, file systems, network stacks, schedulers, system calls, libraries, toolchains, language virtual machines, user interface/shell, applications, etc.
  • OS Models: monolithic kernel, microkernel, virtual machine monitor/hypervisor, jail/zone/container, and more esoteric models.
  • OS Abstractions: thread, name space, address space, process, IPC, virtual machine, container, file, directory, stream, etc.  Plus abstraction design within the kernel (devices, file systems, ...)
  • Concurrency Sources: multiprocessors, devices, interrupts, threads, processes, horror stories, …
  • Concurrency Challenges: memory system coherence/consistency, race conditions, deadlock, livelock, horror stories, …
  • Concurrency Control: interrupt control, atomics, spinlocks, critical sections, blocking vs waiting, mutexes, semaphores,condvars, monitors, barriers, lockfree/waitfree models, plus typical synchronization problems such as producer-consumer, reader-writer, and dining philosophers.
  • Scheduling and Resource Management: basic theory, FCFS, GPS, SRPT, dynamic priority (e.g. Unix), lottery, fixed priority, preemptive vs non-preemptive, real-time vs non-real-time, horror stories, …
  • Virtual Memory: hardware-software co-design, paging, swapping, segmentation and (possibly) current alternatives. 
  • Device Drivers: interrupts, DMA vs PIO, MMIO vs PMIO, atomics, hardware memory barriers, software memory barriers.
  • Protection and Security: kernel/user mode, mode/ring transitions, role of encryption, interaction with virtual memory, horror stories.
  • Memory Management: page allocation versus heap allocation, garbage collection, allocation in special contexts (e.g. interrupt context), page replacement, working set.
  • File Systems: issues/interfaces, data structures on block devices, examples (V7, FAT+, ext2+)
  • Principles: policy versus mechanism, orthogonality, worse-is-better, lazy evaluation, caching, end-to-end argument, mythical man-month, no silver bullet, hw/sw co-design

 

The hardware environment that we will focus on is Intel/AMD machines running in 64 bit mode ("x64"), which is the commonplace platform for systems ranging from laptops to supercomputers today.   Lab work is done in the C programming language on user-level Linux or in the Nautilus kernel framework ("NK"), a research kernel developed at Northwestern and other institutions. The experience you gain in NK will generalize to the Linux kernel, for the most part.

Labs: Varies; current labs are:

  • Getting Started Lab (build and run a custom kernel)
  • Producer-Consumer Lab (learn about concurrency control)
  • Queue Lab (learn about scheduling via a discrete event simulator)
  • Driver Lab (extend a kernel with a new device driver)
  • Paging Lab (add simple address translation to a kernel)

Except for the Getting Started Lab, labs can be done in groups. 

GRADES:

  • Labs 60%
  • Midterm 20%
  • Final 20%

COURSE ORGANIZATION: The course is organized as a series of lectures, labs, and exams.  There is also an optional weekly TA-lead discussion session.   The instructor, TAs, and PMs arrange office hours so that every student has access to at least one office hour per week.   An online discussion group is regularly monitored by all course staff.