CS 471 Operating Systems

Catalog Description

Major topics include system structure, memory management, and process management. Hands-on experience using the department’s minicomputer facilities are an important part of the course. Prerequisite - C or better in CS 202.

Prerequisites

• C Programming to the CS201/CS202 Level
• Understanding logical (boolean) operations to the CS303 Level
• Functions every citizen should know - close, execve, fclose, fgetc, fopen, fork, fprintf, fputc, fread, free, fscanf, fseek, fstat, fwrite, getchar, getpid, getuid, lseek, malloc, memcpy, memset, open, printf, pthread_create, pthread_exit, pthread_join, pthread_mutex_init, pthread_mutex_lock, pthread_mutex_unlock, putchar, random, read, realloc, scanf, sem_init, sem_post, sem_wait, shm_open, shm_unlink, sleep, srandom, stat, strcasecmp, strcat, strcmp, strcpy, strlen, time, unlink, usleep, wait, write

Standard Content

Course Outline

• Review - functions every citizen should know, basic data structures in C (1-2 weeks)
• Device Management, typically focusing on storage devices and filesystems (3 weeks)
• ext2 file system in detail
• Other filesystems at a high level
• Process/Thread Management (3 weeks)
• Single CPU execution - time slicing, scheduling
• Multi-core execution
• Shared data - semaphores, other mechanisms, synchronization issues, race conditions
• Memory Management (3 weeks)
• Memory organization, virtual memory, pages, page faults, CPU cache
• Other Topics, as time allows

Learning Outcomes

An Operating System is a complex computer program that mediates access to three essential resources: CPU, memory, and devices. The main goal of this class is gain an understanding of how these three objectives are met. A secondary goal is to understand how some of the ideas which originated as solutions to operating systems problems have contributed to solutions to other problems. Source code for unix system calls - can trace through and explain the code, can make modifications. Unix system calls - can write programs that use the calls to mimic unix utility commands. Synchronization primitives - can explain proper use and write correct code that uses primitives to avoid race conditions or logical errors. Common scheduling algorithms - can explain common algorithms and tradeoffs. Process accounting - can explain in detail at least one process accounting system. File systems - can explain in detail the layout of at least one modern file system, can explain basic properties and tradeoffs of a number of others. Virtual memory - can explain fundamental concepts and their impact on performance, can explain in detail the mechanism of at least one modern memory management system. Modern computer and operating system - can explain the basic architecture of modern computers and operating systems, including how an operating system ensures proper sharing of the following between different programs and users - CPU, disk, memory, other devices.

Important Assignments and/or Exam Questions

• Process Management: writing a simple scheduler for a simplified OS. A basic data file driven version of this assignment might use a data file which lists a sequences of jobs. For each job, the data file would specify the time and resource demands of the job. Output would include snapshots of the process table at any given time. A more challenging version of this assignment would call for a realistic process table (red-black trees, etc.).
• Memory Management: an implementation of a basic memory management scheme, e.g., the buddy system. A basic version of this assignment could use a data file similar to the one used in the Process Management assignment. An alternative, more challenging assignment would be implementing a library to replace malloc.
• Device Management: a program that requires students to read and write to a filesystem, updating inodes, directories, and block bitmaps. The ext2 filesystem is a useful simple example for which one can find a wealth of online resources. The ‘read’ portion of this assignment is significantly easier than the ‘write’ portion.

For at least one of these three assignments, the more ambitious variant should be expected.

Standard resources

• Understanding the Linux Kernel, Bovet and Cesati
• Unix Filesystems, Pate
• The Little Book of Semaphores
• The ext2 File System
• The Unix Timesharing System
• Operating Systems: Three Easy Pieces