CS 3210 OS Design
Spring
2007, TuTh 1:35-2:25
Environmental
Science & Technology (EST) L1118
Instructor
Phillip
W. Hutto pwh@cc.gatech.edu and phillip.hutto.gt@gmail.com
Note: Office hour
location TBA
cell
404.423.8878 - home 404.892.7444
Office
Hours: TuTh 2:30-3:30 and by appointment!
Note:
I
also teach at Emory University MWF so you will mostly find me on the Tech
campus TuTh. I am highly available by email and encourage you to contact me by
email or by calling me at home. Asking questions by email or phone is quick and
convenient. Some students feel generally confused and don’t know how to
formulate a question. I encourage you to give it a shot. I am pretty good at
understanding what you are asking even if it doesn’t make complete sense and
the process of formulating the question is helpful itself. Please don’t
hesitate to arrange an appointment outside of office hours if you need to.
Optional
Extra Sessions (2:25-2:55)
This class has only two 50 minute lectures each week
yet we have the room reserved for a full 90 minutes. the last 30 minutes will be
used for occasional optional sessions that introduced interesting new material
that will not be tested and for project review sessions.
Web: http://www.cc.gatech.edu/classes/AY2007/cs3210_spring
News: news://news.gatech.edu/git.cc.class.cs3210
Swiki: http://swiki.cc.gatech.edu:8080/cs3210
Class Mailing List: cs3210@cc
Quick
Links
Prerequisites
CS
2200 (required!) Familiarity with general OS concepts at the level of the
Dinosaur Book (Silbershatz). Knowledge of Linux is not required but helpful.
Sys admin experience is helpful. This is a second course in operating systems
and assumes that you have knowledge of basic OS concepts. We will briefly
review such concepts at the beginning of each topic but move quickly to
specifics of UNIX/Linux semantics and implementation details.
Objectives
Deep
understanding of OS principles by detailed study of a modern OS kernel
(internals). Along the way you will learn a fair amount about Linux/Unix
programming interfaces (externals).
Surviving
and Thriving
There
is an enormous amount of detail involved in the kernel and in this class. Some
students are initially overwhelmed and stop reading the text. No one
understands everything, not even Linus! Learning the kernel is a gradual
process. The more you are exposed to a concept the more it makes sense. If you
turn away the first time you see something because you don’t completely
understand then you are lost. You must press on and keep turning the pages,
getting whatever you can from them. This is something like learning a new
language. We will use the immersion approach. I approach the material using
levels of understanding. First just skim the chapter. Get an idea of the basic
concepts and system calls. Then look again and try to understand some more
detail, perhaps the major data structures and functions. Skip over little
details or confusing bits. Return to these after a break and see if they make
more sense. While grades are important, I am most interested in everyone
getting excited about operating systems and making an effort to learn
something. If you have a lot of background already you will probably be able to
go deeper into the material. Whatever your initial starting place, I want
everyone to make an effort and learn something this semester! Perhaps the best
way of studying is sitting around and talking about the kernel with other
students or the course staff during office hours.
Texts
Understanding the Linux Kernel: From I/O
Ports to Process Management 3e (2.6 kernel) [required]
Bovet & Cesati (BC), O’Reilly November
2005 942 pages
ISBN 0596005652 (about $30)
Linux
Kernel Development 2e (2.6 kernel) [required]
Love (L), Novell Press, January 2005 432 pages
ISBN 0672327201 (about $25)
Linux Device Drivers 3e [recommended]
Rubini and Corbet (RC), O’Reilly February 2005
636 pages
ISBN 0596005903 (about $25)
Second Edition Available Online (Free): http://www.xml.com/ldd/chapter/book/
Safari
You
might want to consider accessing the class textbooks using O’Reilly’s Safari
online book portal (http://safari.oreilly.com). All three course
texts are available in Safari. Access can be purchased a month at a time
starting at $10 per month. You can try it free for two weeks. (More expensive
accounts give you access to more books and allow you to download and print
chapters.)
Resources
I
will include and maintain a detailed list of related texts and other online
resources that you may consider supplemental material for this class on the
website.
New! Linux Kernel in a Nutshell: A Desktop Quick Reference
Kroah-Hartman O’Reilly December 2006
198 pages
ISBN 0596100795
New! Mac OS X Internals
Singh Addison-Wesley June 2006 1680
pages
ISBN 0321278542
New! Operating Systems: Design and Implementation 3e
Tanenbaum Prentice-Hall January 2006
1080 pages
ISBN 0131429388
New!
Solaris Internals: Solaris 10 and OpenSolaris Kernel Architecture 2e
Mauro, McDougall, Prentice-Hall July 2006 1072 pages
ISBN 0131482092
Understanding
Linux Network Internals
Benvenuti O’Reilly December 2005
1024 pages
ISBN 0596002556
Advanced
Programming in the UNIX Environment 2e
Stevens, Rago Addison-Wesley June
2005 960 pages
ISBN 0201433079
The
Linux Kernel Primer: A Top-Down Approach for x86 and PowerPC Architectures
Salzberg, Fischer, Smolski
Prentice-Hall September 2005 560 pages
ISBN 0131181637
Microsoft
Windows Internals: Server 2003, XP, and 2000 4e
Solomon, Russinovich, Solomon, Microsoft Press December 2004 976 pages
ISBN 0735619174
Linux
Application Development 2e
ISBN 0321219147
The
Linux Networking Architecture: Design and Imp. of Network Protocols in the
Linux Kernel
Wehrle, Pahlke, Ritter, Muller, Bechler, Pearson, April 2004 648 pages
ISBN 0131777203
The Design and Implementation of the FreeBSD Operating System
Marshall McKusick, George Neville-Neil (MN), Pearson, July 2004 720 pages
ISBN 0201702452 (about $60)
The Linux TCP/IP Stack: Networking for Embedded Systems
Thomas Herbert (H), Charles River Media, June 2004 586 pages
ISBN 1584502843 (about $35)
Understanding the Linux Virtual Memory Manager (2.6 kernel)
Mel Gorman (G), Prentice-Hall, April 2004 768 pages
ISBN 0131453483 (about $60)
Online version describing 2.4 kernel: http://www.csn.ul.ie/~mel/projects/vm/
Unix Filesystems: Evolution, Design, and Implementation
Steve D. Pate (P), Wiley, January 2003 443 pages
ISBN 0471164836 (about $30)
Building Embedded Linux Systems
Yaghmour, O’Reilly, April 2003 391 pages
ISBN 059600222X
The Linux Process Manager
Gorman, Wiley, February 2003 640 pages
ISBN 0470847719
GCC: The Complete Reference
Griffith, McGraw-Hill, 2002 647 pages
ISBN 0072224053
Running Linux 4e
Welsh, Kaurman, Dalheimer, Dawson, O’Reilly December 2003 750 pages
ISBN 0596002726
IA-64 Linux Kernel: Design and Implementation
Mosberger, Eranian, Prentice-Hall January 2002 560 pages
Operating Systems Concepts 6e XP Update (the Dinosaur Book)
Silbershatz, Gavin, Gagne, Wiley & Sons June 2003 951 pages
ISBN 0471250600
Modern Operating Systems 2e
Tanenbaum, Prentice-Hall February 2001 976 pages
Operating Systems 3e
Deitel, Deitel, Choffnes, Pearson 2004 1209 pages
ISBN 0131828274
Lions’ Commentary on UNIX 6e with Source Code
ISBN 1573980137
Accounts
You
will need a CoC account. I will need to sign the authorization form if you do
not already have one. Get one now! You will also need to use your campus
(acme) account to access the campus wireless network (LAWN).
http://www.cc.gatech.edu/cns/forms/account_form.shtml
Grading
|
20% |
Midterm
Exams |
2
– 10%, 10% |
|
24% |
Homeworks |
6
– 4% each |
|
35% |
Projects |
5
– 5%, 7.5%, 7.5%,7.5%, 7.5% |
|
12% |
Final
Project |
|
|
3% |
Notes |
2
– 1.5% each |
|
6% |
Participation |
Attendance,
office hours, etc. |
Exam
and class grades are curved. That means grades are calculated relative to the
performance of other students. Generally I start with a standard deviation
about the mean as the B range. One standard deviation below is C, one above is
A, etc. I then adjust the cut-offs to reflect my expectations of your
performance. When calculating final course grades I use raw numerical values
(not a numerical score corresponding to your letter grade) and then curve as
usual. Course grade summaries will be provided after the first exam and before
the final to let you know your standing. You may ask me about your grades at
any time. I will give a passing grade to anyone that makes a consistent effort
to understand the material throughout the semester. I rarely give D’s. So most
students make As, Bs, and Cs in this class. It is very important to me that I
see you making an effort. Coming to class, asking questions, and seeing me in
office hours are all very good ways to demonstrate your interest in the
material.
Pass/Fail
students should focus on the team projects and are exempt from homeworks and
the final exam/project.
Wisdom
Turn
something in for every assignment including notes! People generally do well on
homeworks and project grades often cluster closely together (depending on the
difficulty of the project). Differences in final course grades are often
decided by just a few percentage points. Not doing lecture notes or not turning
in a homework, for example, can mean the difference between an A and a B in
borderline cases. Not turning in a project is a guaranteed way to get a poor
grade! Doing well on exams correlates highly to reading the primary course
textbook (Bovet & Cesati).
Team
Projects
Teams of three this term. You will have the
same team all semester under normal circumstances. Teams will schedule project
demonstrations with the instructor. Do a simple code walk-through, run project,
answer prepared and spontaneous questions from the instructor. All team members
must be able to answer all questions equally! Please identify partners by
next class (Thursday 11 January) or I will assign you to a team arbitrarily.
All
team members will receive the same grade. You may submit evaluations of fellow
team member’s participation at the end of the semester and I will take these
into account when assigning final grades. If a team member drops or stops
participating, I will split or merge teams as necessary. Audit and pass-fail
students should form their own teams (without L/G members). We will expect
a little more from teams of four, a little less from teams of two. For example,
a partially working solution will receive a higher grade for a team of two.
Team members will be assigned to a special per-team group and be given access
to a large disk partition for holding the kernel source tree.
Team
Etiquette
We
always have some conflicts with assigned teams (members don’t participate
equally, don’t show up for planned meetings, flame each other via email, etc.).
I will do conflict resolution as necessary but keep in mind that the value
of working in teams is to learn how to interact profitably. We all get a little
frayed by the pace of things at Tech but please make special efforts to get
along with your teammates. Be willing to compromise. If there are differences
of opinion, make an effort to understand your teammate’s perspective.
Understand that everyone else is as busy as you are and respect their efforts.
Be sure to show up for planned meetings or make every effort to inform your
teammates that you can’t make it. Being a good teammate also means not trying
to do everything else yourself. Give others some time and space to struggle
with the material. That’s how we all learn.
Homeworks (1 submission per student)
You
will be asked to submit written homeworks about every two weeks. Homeworks
should be prepared using a word processor or similar tool. Homeworks this
semester will be designed to help you study for the midterm exams. Homeworks
will emphasize “essential” material that I expect you to have mastered from the
previous two weeks of lectures and readings. Question format will be similar to
exams but I will expect more detailed and thorough answers since you will be
able to use reference material. Bring a print-out of your homework solutions to
class on the due date.
Homework 1 – OS / Kernel Intro, Booting / Kernel Init, Syscalls / Modules / Procfs
DUE: TBA
Homework 2 - Memory
Addressing, Processes, Interrupts, Timing, Synchronization
DUE: TBA
Homework 3 –
DUE:
TBA
Programs (1 submission per team)
This
is a project-oriented class and you will do a significant amount of programming
this semester. We grade demos by holding brief (20-30 minute) “demos” for each
project. You will sign-up for a demo slot on the class swiki and all team
members must be present. You will describe your implementation, do a code
walkthrough of relevant code, and then demonstrate your kernel modifications
working properly. Throughout, the grader will ask a variety of questions about
the assignment, your solution and about the relevant kernel subsystem. All team
members must be able to answer questions to the satisfaction of the grader,
even if they did not code a particular portion of the solution. In some cases,
we may ask for a short write-up as well. You do not need to submit code
electronically. Assignments (such as the filesystem assignments) that are
independent of the iPAQ hardware may be developed and demo’ed on your own
laptop or Linux workstation if you wish.
The
following due dates and topics are tentative and subject to change:
Program 1 – Warm-up, System Calls
DUE: TBA
Program 2 – Where Does the Time Go?
DUE: TBA
Resource: “Measuring Program Execution Time”,
Bryant/O’Hallaron (pdf)
Sample System V Semaphore Code (tgz)
DUE: TBA
DUE: TBA
DUE:
TBA
Program 6 – Hello, World File System (Final Exam Replacement)
DUE: TBA
Ch 14
Pate “Developing a Filesystem for the Linux Kernel” (pdf)
NOTE:
Concerning
program due dates, recall that programs must be demo’ed when completed.
Therefore the due dates given are fairly fuzzy since you must arrange a demo
time with the instructor. Practically speaking you should demo your
program within 2 or 3 days of the due date.
Closed-book,
in the evening (outside of class-time). I schedule evening exams to conserve
lectures and to give you more time on the exam. Make-ups will be scheduled for
students who have conflicts with the evening times. Short answer under time
pressure. Exams emphasize mid-level concepts and include some detail questions.
Study guides and old exams with solutions will be made available. Exams will
emphasize most recent material (~80%). Exam grades (and course grades) strongly
correlate with how well people read the text!
There
will be no Final Exam this semester. All groups will be required to do the
Final Project in place of the Final Exam.
Exam 1 – Wednesday 21 February 7-8:30 pm (EST
L1118)
·
Old Exam (word) (pdf) (html)
·
Study Guide (word) (pdf) (html)
Exam 2 – Wednesday 18 April 7-8:30 pm (EST L1118)
·
Old Exam (word) (pdf) (html)
·
Study Guide (word) (pdf) (html)
Each
student will be responsible for taking detailed class notes two times
during the semester and posting to the class swiki. Students may take notes a
third time for extra credit. Phil will review and grade notes. Post these
within one week of the lecture. Your notes must be well-formatted,
detailed and accurate. Simply transcribe whatever happens in class on your
assigned day (include informational announcements, etc.). Note-taking will
begin Thursday 11 January. You
should transcribe whatever happens in class on your assigned day including
announcements and interesting questions or discussions. Contact Phil to clarify
any material you might not understand. You are welcomed to check your notes for
accuracy with other assigned note-takers. I will simply rotate through name
alphabetically to assign note-takers so you can anticipate your assigned dates.
Equipment
/ Lab Setup
Each
team will be assigned an iPAQ and associated equipment for use during the
semester. We have an elaborate development environment setup here at Tech.
Adventurous students with Linux systems may wish to setup their own home
development environment. Most of the software we will use with iPAQ comes from www.handhelds.org. This is the primary site for Linux on the
iPAQ. Working with the iPAQ is similar to working on an embedded system. You
will normally work in the States Cluster and connect the iPAQ to a serial port
and interact using a terminal emulator (minicom or secure-crt). In addition,
you will use a wireless card to remote
I
will take individual photos of students to help me learn names and faces. I
will place these on the website unless you want me to keep your photo private.
The
2.6 Kernel
The
newest stable version of the Linux kernel (2.6), under development for almost 3
years, has been released for some time but still isn’t fully functioning on our
iPAQ platform. The textbook by Robert Love describes features of this kernel. The
new Bovet & Cesati also describes the 2.6 kernel. We will continue to use
the 2.4 kernel on the iPAQs this semester for stability. I will cover what you
need to know about the 2.4 kernel in lecture so you will be able to do the
projects. This might be slightly confusing, keeping the two implementations
straight in your mind, but there are many new and exciting features in 2.6 that
are worth looking at. Also it is worth noting that more things stay the same
than change between two iterations of the kernel so much of what we study is
relevant to the new kernel. In addition, there is great value in looking at old
kernel implementations to understand the evolution of the code.
Kernel
Source Browser: LXR
We
will use a very nice online kernel source browser frequently this semester
called LXR (“licks-ser”). It is available at http://lxr.linux.no and contains indexed
and hyperlinked versions of many versions of the kernel source tree. An
experimental site using LXR to index various BSD kernels has recently opened
and makes for interesting comparisons (http://fxr.watson.org).
Other
Kernels?
Why
do we study the Linux kernel? It is under vigorous development with new
features added all the time. It is fairly well documented (as kernels go). It
also enjoys a very large community of followers that make a large number of
resources available for understanding the kernel. Other kernels would also
work. The Solaris and Windows kernels make interesting counterpoints to Linux.
The OpenSolaris project (www.opensolaris.org) is nicely under way
but it is a massive system. They have a nice source browser that they describe
as “wicked fast” (cvs.opensolaris.org/source). Microsoft has
recently announced availability of several resources for exploring
OS/kernel design such as ProjectOZ and the Windows
Research Kernel (WRK). These resources are available under license. There is
also available a video presentation discussing the new Windows Vista architecture. The BSD systems in
particular are probably more elegantly structured but they are not as well
documented. However, an updated version of the very good BSD book by Marshall
McKusick has just been released that describes FreeBSD. I will try to include
some Linux vs. FreeBSD comparisons in lectures this semester.
My
Favorite Online Linux Resources
Kernel
Traffic (www.kerneltraffic.org) is a moderated
version of the kernel developers mailing list. Not for the weak of heart. Fun to
look at every now and then to see how people rant at each other. Linux Weekly
News (www.lwn.net) is my favorite site with a very good
weekly kernel section. Moderated by Corbet, co-author of the Device Driver
book. Kernel Newbies (www.kernelnwebies.org) is a good place to
begin. And just to prove that not all kernel hackers are men, visit Linux Chix
(www.linuxchix.org).
Assembly Language
A
moderate percentage of the kernel is written in assembly language. Some things
must be written in assembly (such as the code that sets up stack frames for
signal delivery) while other portions are written in assembly as a performance
optimization (spinlock code). We will look at some of this code and I will
expect you to understand the basic flow but not all the details. It is
sufficient to recognize basic assembly commands like INC and LOAD. We will look
at both x86 and ARM assembly. A good Intel assembly reference is:
The
Art of Assembly Language
Randall Hyde, No Starch Press,
September 2003 928 pages
ISBN: 1886411972
Available
Online: http://webster.cs.ucr.edu/AoA/DOS/AoADosIndex.html
User Mode Linux (UML)
The
2.6 kernel includes a very interesting subsystem known as User Mode Linux. This
is an emulation of the kernel as a collection of user-mode processes that run
under Linux! It is used extensively by kernel developers and has gained a
following among folks that are into “virtualization” (for whatever reason). It
is very efficient and increasingly stable, although it isn’t as well-documented
as you might hope and it can be tricky getting a host kernel and root
filesystem that work well together. It has been included in the 2.6 kernel
source tree as an “architecture”. That means you just build the kernel the way
you would normally, but targeted for the (mythical) UML machine! The UML home
page on Sourceforge (http://user-mode-linux.sourceforge.net/) is a good place to
start learning about UML. A few adventurous students have used UML for some of
the class projects in the past. If we have enough time, we might do one of the
class projects using UML this semester. There are several advantages to using
UML: 1) debugging is easier; 2) you can use an Intel-based kernel; 3) you can
always use the very latest kernel tree.
We
will cover Bovet & Cesati (BC) roughly in order with a few additional
topics. Supplemental reading will be taken from Love (L), Rubini & Corbet
(RC) and handouts. Optional, suggested readings are in italics. I have lecture
notes for most but not all topics. Don’t assume that notes will necessarily
appear! Do not omit things from your note-taking just because they appear in
the lecture notes I provide.
|
Tu
9 Jan |
Course
Intro
|
|
|
Th
11 |
OS,
Kernel Intro |
BC
Ch 1 (General Intro) Handout:
Tannenbaum OS
Design |
|
Tu
16 |
Booting,
Kernel Init |
BC
Appendix A (Startup) Handout:
Running Linux Ch 5 |
|
Th
18 |
System
Calls, Modules, /proc |
BC
Ch 10 (Sys Calls), Appendix B (Modules) |
|
Tu
23 |
Debugging,
Coding Style, GCC Magic |
|
|
Th
25 |
Memory
Addressing 1 |
BC
Ch 2 (Memory Addressing) |
|
Tu
30 |
Memory
Addressing 2 |
BC
Ch 2 (Memory Addressing) |
|
Th
1 Feb |
Processes |
BC
Ch 3 (Processes) L
Ch 3 (Process Management) |
|
Tu
6 |
Interrupts,
Exceptions |
BC
Ch 4 (Interrupts/Exceptions) L
Ch 6 (interrupts), 7 (Deferred Work) |
|
Th
8 |
Interrupts,
Exceptions |
BC
Ch 4 (Interrupts/Exceptions) L
Ch 6 (interrupts), 7 (Deferred Work) |
|
Tu
13 |
Timing
Measurements |
BC
Ch 6 (Timing Measurements) L
Ch 10 (Timers/Time Management) |
|
Th
15 |
Timing
Measurements |
BC
Ch 6 (Timing Measurements) L
Ch 10 (Timers/Time Management) |
|
Tu
20 Oct |
Kernel
Synchronization |
BC
Ch 5 (Kernel Synch) L
Ch 8, 9 (Kernel Synch) |
|
Wed
21 |
Exam 1 – EST L1118
7-8:30 pm
|
Intro,
Booting, GCC Magic, BC 1-7, 10 |
|
Th
22 |
Scheduler
(2.4) |
BC
Ch 7 (Scheduling) L
Ch 4 (Scheduling) |
|
Tu
27 |
Scheduler
(2.6) |
BC
Ch 7 (Scheduling) L
Ch 4 (Scheduling) |
|
Th
1 Mar |
Scheduler
(2.6) |
BC
Ch 7 (Scheduling) L
Ch 4 (Scheduling) |
|
Tu
6 |
Memory
Management |
BC
Ch 8 (Memory Management) L
Ch 11 (Memory Management) |
|
Th
8 |
|
|
|
Tu
13 |
Process
Address Space |
BC
Ch 9 (Process Address Space) L
Ch 14 (Process Address Space) |
|
Th
15 |
Signals
|
BC
Ch 11 (Signals) |
|
Tu
20 |
Spring Break! |
|
|
Th
22 |
Spring Break! |
|
|
Tu
27 |
Virtual
File System |
BC
Ch 12 (VFS) L
Ch 12 (VFS) |
|
Th
29 |
Virtual
File System 2 |
BC
Ch 12 (VFS) L
Ch 12 (VFS) |
|
Tu
3 Apr |
|
|
|
Th
5 |
Access
Control Lists (ACLs) |
Handouts |
|
Tu
10 |
I/O
Architecture and Device Drivers
|
BC
Ch 13 (I/O, Drivers) L
Ch 17 (Device Model) |
|
Th
12 |
|
|
|
Tu
17 |
Block
Device Drivers
|
BC
Ch 14 (I/O Devices) L
Ch 13 (Block I/O Layer) |
|
Wed
18 |
Exam
2 – EST L1118 7-8:30 pm
|
BC
Chs 8, 9, 11-14, ACLs |
|
Th
19 |
Page
Cache Accessing
Files |
BC
Ch 15 (Page Cache) L
Ch 15 (Page Cache) BC
Ch 16 (Accessing Files) |
|
Tu
24 |
Ext2/Ext3
|
BC
Ch 18 (Ext2/3) |
|
Th
26 |
|
|
|
Fri
4 May |
Final
Projects DUE
|
|
|
Mon
7 |
Grades
Due! |
|
Enjoy
the semester and good luck!