Administrative Information

Professor

T.A.

Course Description

Operating systems control all of a computer's resources and present users with the equivalent of virtual machines that are easier to program than their underlying hardware. This course is an introduction to basic operating systems concepts including operating systems structures, processes and thread, memory management, and file systems.

The course assumes familiarity with basic computer organization and data structures. You will need to be able to program in C (or C++) in UNIX systems to perform most of the assignments.

Location and Time

Tuesdays and Thursdays 2:00-3:20.
Lectures will be held in 1890 Maple, Room 381.

In compliance with Section 504 of the 1973 Rehabilitation Act and the Americans with Disabilities Act, Northwestern University is committed to providing equal access to all programming. Students with disabilities seeking accommodations are encouraged to contact the office of Services for Students with Disabilities (SSD) at +1 847 467-5530 or ssd@northwestern.edu. SSD is located in the basement of Scott Hall. Additionally, I am available to discuss disability-related needs during office hours or by appointment.

Course Prerequisites

• Required: CS-311 Data structures and data management.
• Highly recommended: CS-213 Introduction to Computer Systems -- taking this course will make your life a lot easier.
• Familiarity with basic computer architecture concepts and proficiency in C programming in UNIX systems.

Communication Channels

There are a number of communication channels set up for this class:

• We will use the course web site ( http://www.cs.northwestern.edu/~fabianb/classes/cs-343.html) to post announcements related to the course. You should check this regularly for schedule changes, clarifications and corrections to assignments, and other course-related announcements.
• This year we will also be using the Northwestern's Blackboard System. The system includes a number of nice features such as an announcement board, group email, a place for assignment postings, and, more important to us, a discussion board. The Discussion Board is intended to foster communication among you, the students. You'll find that someone else in the class will have thought of the same problem that you have and will perhaps have some valuable insight that will prove helpful. The staff will be monitoring the discussion threads and will step in with guidance when appropriate.
• Finally, there is an email alias ( cs-343-ta@cs) for the TA that you should use for questions that would be inappropriate to post on the newsgroup (source code being a good example).

Announcements

• The quarter is over!

Materials

Required

• Textbook: Modern Operating Systems, 2nd Ed., A. S. Tanenbaum, Prentice-Hal, Upper Saddle River, NJ, 2001. (``MOS'' from now on.)
• Papers: A set of papers that will be made available.

Recommended

• Advanced Programming in the Unix Environment, R. Stevens, Addison-Wesley, 1992. A basic book for anyone writing programs that run under Unix.
• The C Programming Language, 2nd Ed., B. W. Kernighan and D. M. Ritchie, Prentice Hall, 1988. A must.
• The Practice of Programming, Brian W. Kernighan and Rob Pike. Addison-Wesley, 1999.
• D. M. Ritchie and K. Thompson, The UNIX time-sharing system , Communications of the ACM, 17(7), pp 365-375, July 1974.

References

• A nice introductory book to Unix: "UNIX for the Impatient (2nd Edition)" by Paul W. Abrahams, Bruce Larson (Contributor); there's also a pretty good O'Reilly Nutshell book: "Learning the Unix Operating System (Nutshell Handbook), 5th Ed.", by Jerry D. Peek, Grace Todino, John Strang.
• If you are having problems getting started: Programming with GNU Software, M. Loukides and Andy Oram, O'Reilly is a short introduction to C programming on a Unix environment. There are also a number of helpful pages in the web (Holmes' C programming and Summit's C Programming are just two examples).
• There is more to writing a program than getting the syntax right, fixing the bugs you have noticed, and making it run fast enough. Programs are read not only by computers but also by programmers. A well-written program is easier to understand, grade, and modify than a poorly-written one. People have collected tons of useful advice on the art of programming. Please take a look at Rob Pike's Notes on Programming in C. Brian W. Kernighan and Rob Pike have also published a very neat little book The Practice of Programming packed with useful advice.
• I am collecting some pointers on C/Unix resources.
• Ashish Gupta has pointed out some useful links on concurrency (Thanks!). Please take a look at:
  
  • Operating Systems Concurrency
  • CNE Workbenches
  • Concurrency models and programs

Grading

I will try very hard to give you the grade you deserve. I will use a criterion-referenced method; in other words, your grade will be based on how well you do relative to predetermined performance levels, instead of in comparison with the rest of the class. Thus, if a test has 100 possible points, anyone with a score of 90 or greater will get an A, those with scores of 80 or greater will get a B, those with scores of 70 or greater will get a C, and so on. Notice that this means that if everyone works hard and gets > 90, everyone gets an A.

Total scores (between 0 and 100) will be determined, roughly, as follows:

• Homeworks 10%
• Projects 50%
• Exams 40%

Exams

There will be a midterm and a final exam. Exams will be in-class, closed-book, and will cover materials from lecture, required readings and projects. The final exam will not be cumulative.

Homework

There will be two kinds of homework assignments given throughout the class: reading assignments and textbook-style questions. You should have finished the assigned reading before coming to lecture. In addition, there will be a set of written homeworks that must be done alone and turned in at the end of class on the due date (see course policies below).

Projects

As you can deduce from the allocation of weights for grading, programming projects make up a major portion of this class. There will be four (4) projects. Except for the first ``warm-up'' assignment that you will work by yourself, all other projects are to be done by teams of two (2) people. Both partners should work cooperatively on the design, implementation, and testing of their solution. You will have to choose different partners for different projects.

Course Outline and Approximate Dates

Because one has to be an optimist to begin an ambitious project, it is not surprising that underestimation of completion time is the norm.
-- Fernando J. Corbato, ``On Building Systems that Will Fail'', 1990 Turing Award Lecture.

• Introduction - 9/25

  Readings:
  

  • MOS chap. 1.1-1.3
  • P. H. Salus, Unix at 25, Byte 19, pp 75-82, Oct. 1994.

• Deep C - C and Systems level Programming - 9/30
• Architectural Support for Operating Systems - 10/02

  Readings:
  

  • MOS chap. 1.4

• Operating Systems Components and Structure - 10/02

  Readings:
  

  • MOS chap. 1.5-1.7

• Processes & Threads - 10/07-10/09

  Readings:
  

  • MOS chap. 2.1-2.2
  • A.D. Birrel. An Introduction to Programming with Threads. Tech. Report, Digital - Systems Research Center, Palo Alto, CA, Jan. 1989

• Interprocess Communication & Synchronization 10/14-10/16

  Readings:
  

  • MOS chap. 2.3-2.4

• Scheduling - 10/23

  Readings:
  

  • MOS chap. 2.5

• Deadlocks - 10/30

  Readings:
  

  • MOS chap. 3

• Memory Management - 11/04

  Readings:
  

  • MOS chap. 4.1-4.2

• Virtual Memory - 11/06-11/11

  Readings:
  

  • MOS chap. 4.3-4.5

• VM Design and Implementation Issues - 11/13

  Readings:
  

  • MOS chap. 4.6-4.8

• I/O Devices - 11/18

  Readings:
  

  • MOS chap. 5.1-5.4 (inclusive)

• File Systems - 11/20

  Readings: 6.1-6.2
  

  • MOS chap. 6

• FFS & LFS - 11/25

  Readings:
  

  • MOS chap. 6.3
  • McKusic, M.K., Joy, W.N., Leffler, S.J., and Fabry, R. S., A Fast File System for UNIX, ACM Trans. on Computer Systems, 2(3), pp. 181-197, Aug. 1984.
  • Rosenblum, M. and Ousterhout, J.K., The Design and Implementation of a Log-Structured File System, in Proceedings of the 13th Symposium on Operating Systems Principles (SOSP), pp. 1-15, 1991.

• Distributed Systems - 11/25

  Readings:
  

  • MOS chap. 8

• Review for final/Research in OS - 12/04

  Readings:
  

  • M. Swift, B. Bershad, H. Levy,Improving the reliability of comodity operating systems, ACM Symposium on Operating Systems Principles (SOSP), Bolton Landing, NY, USA, 2003.

Policies

Late policy:

Unless otherwise indicated, homeworks and projects are due by the end of lecture on their due date. If you hand in an assignment late, we will take off 10% for each day (or portion thereof) it is late.

Cheating vs. Collaboration:

Collaboration is a really good thing and we encourage it. On the other hand, cheating is considered a very serious offense. When in doubt remember that it's OK to meet with colleagues, study exams together, and discuss assignments with them. However, what you turn in must be your own (or for group projects, your group's own) work. Copying code, solution sets, etc. from other people or any other sources is strictly prohibited.