CPSC 431:
Operating Systems

   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Fall, 2016.

   Instructor:  David J. Eck.

   Monday, Wednesday, Friday, 12:20--1:15
         Coxe 7.

About This Course

An operating system is the core software on a computer. It enables the execution of other programs, it provides them with basic services, it controls access to the hardware, and it imposes security restrictions that prevent programs from performing unauthorized actions and from interfering with the execution of other programs. This course is an introduction to the theory and practice of operating systems.

Operating systems can be very complex. As our textbook notes right at the start, "A modern, general-purpose operating system can exceed 50 million lines of code, or in other words, more than a thousand times longer than this textbook." Fortunately, you don't have to understand everything that goes on in an operating system to understand the fundamental concepts. We will cover the basic functions of operating systems and some of the many techniques that are used to implement them. Topics include process control (how the operating system creates and manages the processes that execute user programs), scheduling (assigning CPU time to all the running processes), memory management (giving processes access to memory and preventing one process from improperly accessing the memory of another), input/output (responding to interrupts and communicating with hardware devices), and file systems (managing and organizing permanent storage).

When you hear the term "operating system," you might think Windows or Mac OS or maybe some version of Linux — that is, a GUI interface to the computer. However, this course is not about the GUI aspect of operating systems. The screen is just one hardware device, and it does not get special attention in this course. In fact, we will be working almost exclusively on the command line. Also, this course is not about operating system administration. You won't be learning UNIX shell programming or how to administer Windows.

The textbook for the course is Operating Systems Principles & Practice, 2nd edition, by Anderson and Dahlin. It will be supplemented by some handouts and on-line readings related to assignments.

Programming and Other Assignments

The programming for this course will be in C. It is assumed that you have some basic knowledge of C, but that you are not proficient in it. In particular, we will spend some time getting you more used to working with C pointers. (If you don't know any C at all, just take Java, strip out classes and interfaces, try..catch, automatic garbage collection, generic programming, and the whole idea of "public" and "private", and you'll have a good starting point.)

A couple of the early assignments will be about C itself, rather than about operating systems. Some assignments will be about using Linux system calls in C, such as the fork and join functions that are used for one type of parallel processing. For some assignments, you will program tasks that are typically performed by the operating system, but you will not be programming them as part of an actual operating system. For example, in an early assignment, you will do some simple memory management, but in a regular C program. And towards the end of the course, you will probably implement a fake file system.

However, I do want you to do some work with an actual operating system. For that, there will be some assignments using Pintos, a small but functional educational operating system that was developed at Stanford University and is used in operating system courses at various institutions. In the Stanford course, the programming consists of four big assignments in Pintos, but they require a very strong background in C programming, and I don't feel that it would be reasonable to base our whole course on Pintos. You will do the first Pintos assignment in several stages. If that goes well, we will probably do the second, and we can decide as a group whether we want to do more than that. We will not get to Pintos until the fifth week of the semester.

In addition to the programming, you can expect written assignments. Some of them might be based on exercises from the textbook.

Note that some of our class meetings will be in a computer lab. The first lab will be on Monday of the second week of classes, September 5.

Tests and grading.

There will be two tests, one given during class on Friday, October14, and one given during the scheduled final exam period, Thursday, December 15, at 8:30 AM. (The final exam will not be much longer than an in-class test, and we might consider a later starting time.)

Each test will count for one-quarter of the final grade. The remaining one-half will be based on assignments. I reserve the right to adjust the grade to some extent based on attendance and class participation, but I won't lower your grade without warning you first.

Statement from the CTL

Disability Accommodations: If you are a student with a disability for which you may need accommodations, you should self-identify, provide appropriate documentation of your disability, and register for services with the Coordinator of Disability Services at the Center for Teaching and Learning (CTL). Disability related accommodations and services generally will not be provided until the registration and documentation process is complete. The guidelines for documenting disabilities can be found at the following website: http://www.hws.edu/academics/ctl/disability_services.aspx

Please direct questions about this process or Disability Services at HWS to David Silver, Coordinator of Disability Services, at silver@hws.edu or x3351.

Office Hours, etc.

Please make liberal use of office hours. I will announce official office hours, but I will often be in my office at other times, and you are welcome to drop by whenever you can find me there. I can also make appointments, and you can always communicate with me by email.

The Web page for this course is http://math.hws.edu/eck/cs431/index_f16.html. This course does not use the Canvas website.

Tentative Schedule

Here is a very tentative weekly schedule of readings and topics for the course. We will depart from this schedule freely, but we will cover all major topics to at least some extent. Except for the most important chapters, I will only assign a part of each chapter as reading. Nevertheless, I encourage you to read the entire textbook.

Dates Readings, Etc.
Aug. 29 and 31; Sept. 2 Introduction to OS (Optional reading: Chapter 1).
Programming and Debugging in C (Reading: handouts).
Sept. 5, 7, and 9 Start Chapter 2: Kernel mode and user mode.
Lab: Debugging C, and a short programming exercise.
Sept. 12, 14, and 16 Finish Chapter 2 and start 3: Fork and Join in UNIX.
Lab on list.c from Pintos; assignment on memory management.
Sept. 19, 21, and 23 Finish Chapter 3: UNIX I/O, etc.
Lab: Some Linux OS programming in C.
Sept. 26, 28, and 30 Chapter 4: Concurrency and Threads. (Also: Semaphores)
Lab introducing Pintos; Pintos assignment: sleep.
Oct. 3, 5, and 7 Chapter 5: Locks and Condition Variables.
Section 7.1: Basic scheduling.
Pintos Assignment: Priority scheduling and mlfq scheduling.
Oct. 12 and 14 Fall Break; no class on Monday.
Test on Friday, October 14.
Oct. 17, 19, and 21 Selections from Chapters 6 and 7: Scheduling.
Possible assignment: Pintos priority donation.
Oct. 24, 26, and 28 Selections from Chapter 8: Address translation and paging.
Possible assignment: Pintos system calls.
Oct. 31; Nov. 2 and 4 Selections from Chapters 9: Caching, etc.
Possible assignment: More Pintos system calls.
Nov. 7, 9, and 11 Selections from Chapter 10: Advanced memory management.
Possible assignment: Memory management.
Nov. 14, 16, and 18 Selections from Chapters 11 and 12: Files.
Possible lab: Files in C.
Nov. 21 Start Chapter 13: Implementing Files.
Thanksgiving; no class on Wednesday or Friday.
Nov. 28 and 30; Dec. 2 Chapter 13: More on file systems.
Possible assignment: Implementing a (fake) file system.
Dec. 5, 7, and 9 Chapter 14: Reliable Storage.
Wrap up the course!
Dec. 13 Final Exam: Thursday, December 15, 8:30 AM