Home Page for CS418 (Fall 2005)

Schedule

• Monday, Wednesday, Friday: 4:10pm--5:00pm in EPS103

Textbook

• Operating Systems (5th edition), by William Stallings, Prentice Hall (In fact, for about 50% of the course, I will use my own notes. This textbook complements with my notes. If you skip most of the classes and just try to follow the textbook, you will find that this course is hard.)

Instructor: Dr. Binhai Zhu

• Office: EPS 355
• Office hours: Wed: 9:00am-10:00am; Wed: 2pm-3pm; Thu: 9am-11am (or by appointment)
• Email: bhz@cs.montana.edu
• Phone: X4836

TA: Michael Thiesen

• Email: thiesen@cs.montana.edu

Syllabus by week

• This is a very rough schedule for each lecture/week (so far I am copying it from last year's, be prepared for the changes!). If you miss a lecture for some reason, you might want to contact me for detailed lecture notes. For your convenience, I also put my lecture slides here.
• week 1: Course overview. Operating system reviews. Components of operating systems (read Chapter 2 of Stallings). Letcure 1 Slides (pdf) or Letcure 1 Slides (ps). Early memory management. Static and dynamic partition, memory deallocation. Relocatable dynamic partition (read Chapter 7 of Stallings). Letcure 2 Slides (pdf) or Letcure 2 Slides (ps).
• week 2: No class on Sep 5 (Labor Day holiday). Memory hierarchy and cache memory (read 1.5, 1.6, Appendix 1A of Stallings) Letcure 3 Slides (pdf) or Letcure 3 Slides (ps). Recent memory management. Paging and demand paging (read Chapter 7 of Stallings). Letcure 4 Slides (pdf) or Letcure 4 Slides (ps).
• week 3: Page replacement policies (read Chapter 8 of Stallings). Segmented memory allocation, segmented/demand paged memory allocation (read Chapter 7 and 8 of Stallings). Letcure 5 Slides (pdf) or Letcure 5 Slides (ps). Buddy system. Hash tables (read 8A). Letcure 6 Slides (pdf) or Letcure 6 Slides (ps). Device management (read Chapter 11 of Stallings). Review for test 1.
• week 4: Test 1 on Sep 19. Device management (read Chapter 11 of Stallings). Letcure 7 Slides (pdf) or Letcure 7 Slides (ps).
• week 5: File management (read Chapter 12 of Stallings). Letcure 8 Slides (pdf) or Letcure 8 Slides (ps). Processor management, part 1 (read Chapter 3, 4 and 9 of Stallings). Letcure 9 Slides (pdf) or Letcure 9 Slides (ps).
• week 6: Processor management, part 1 (read Chapter 3, 4 and 9 of Stallings). Creating processes and threads in UNIX (Linux) system. Program 1, Program 2, Program 3. Processor management, part 2 -- deadlock, starvation and synchronization (read Chapter 5,6 of Stallings). Letcure 10 Slides (pdf) or Letcure 10 Slides (ps).
• week 7: Processor management, part 2 -- deadlock, starvation and synchronization (read Chapter 5,6 of Stallings). Readers and Writers Problem (read Chapter 5 of Stallings).
• week 8: Test 2 on Oct 17 (Test 2 contents: everything covered after Test 1 and before Readers and Writers problem). No class on Oct 19 (Governor's Energy Summit needs to use EPS 103). Security.
• week 9: Security, public key cryptography and RSA public key cryptography. Error detection and the CRC method. Multiprocessor scheduling (read 10.1 of Stallings). Multiprocessor scheduling (pdf) or Multiprocessor scheduling (ps).
• week 10: Real-time scheduling (read 10.2 of Stallings). Real-time scheduling (pdf) or Real-time scheduling (ps).
• week 11: Queuing analysis (read Appendix 9B). Queuing Analysis (pdf) or Queuing Analysis (ps). Introduction to distributed processing (pdf) or Introduction to distributed processing (ps), read 14.1 of Stallings. No class on Nov 11 (Veteran's Day holiday).
• week 12: Process Migration and Distributed Global States (pdf) or Process Migration and Distributed Global States(ps), read 15.1-2 of Stallings. Distributed mutual exclusion/deadlock (pdf) or Distributed mutual exclusion/deadlock (ps), read 15.3 of Stallings.
• week 13: Test 3 on Nov 21. No class on Nov 25 (Thanksgiving Day holiday).
• week 14 & 15: presentation of projects. December 9, 4:30-4:55pm: Brief review for the final exam.

Tests (30%)

• CS418 - test 1 (Test 1 is scheduled on Sep 19, during regular class time.)
• CS418 - test 2 (Test 2 is scheduled on Oct 17, during regular class time.)
• CS418 - test 3 (Test 3 is scheduled on Nov 21, during regular class time.)

Assignments (30%)

• CS418 - assignment 1 (pdf) or CS418 - assignment 1 (ps) (Due: Oct 24, 05.)
• CS418 - assignment 2 (pdf) or CS418 - assignment 2 (ps) (Due: Nov 16, 05.)
• CS418 - assignment 3 (pdf) or CS418 - assignment 3 (ps) (Due: Dec 7, 05.)

Project (10%)

• We will do a project at the end of this term (during the last weeks in late November and early December). (This project has been very very successful during the previous four occasions when I taught this course!) The rough idea is that students taking this course will be divided into 10-12 groups, each with about 3 people. Each group will be given (or choose) a specific OS (or part of it) for detailed survey and analysis. Finally each group will write a 6-10 pages report and give a (20~30)-minute presentation in class. (The rough idea is that each student is expected to present for about 10 minutes; e.g., a 3-people group should present for about 30 minutes, including question answering time.) The evaluation is based on the report as well as the presentation. Each member of the same group should participate in the presentation and will receive the same mark. For more details check the following possible topics. FINAL PROJECT REPORT DUE: Dec 9 2005!
• The following is a list of tentative topics for the projects. They can be chosen based on the first come first serve policy. But you can also propose your own projects. Two groups cannot share exactly the same topic, but situations like different parts of Unix are allowed.
• MSDOS (Yoshi Ako, Justin Heidema and Hind Zerktouni; Presentation time: 4:10-4:35pm, Nov 28)
• A comparison of clustered and distributed computing (Chris Huvaere and Kent Johnson; Presentation time: 4:35-4:55pm, Nov 28)
• Windows File Management Systems: FAT, FAT32 and NFTS (Andrew Frieze, Yoshihiro Fuyura and Kyle Suta; Presentation time: 4:10-4:30pm, Nov 30)
• Device management in Linux (Jeff Craig, Heath Fudge, Jeff Krajacich and Stephen Schultz; Presentation time: 4:30-5:00pm, Nov 30)
• Windows CE (Josh Arlint and Eric Julian; Presentation time: 4:10-4:25pm, Dec 2)
• Google File System (Jesse Dupre, William Dyer and Kyle McIntyre; Presentation time: 4:25-4:45pm, Dec 2)
• Windows Vista OS (Jeff Balboni and Kyle Stadler; Presentation time: 4:45-5:00pm, Dec 2)
• Palm OS (Andrew Cole, Seth Kurk, Brad Leary and Ryan Forbes; Presentation time: 4:08-4:27pm, Dec 5)
• Real-time OS: uC/OSII (Patrick Groff, Levi Junkert and Ernie Turner; Presentation time: 4:27-4:46pm, Dec 5)
• LiveCD OS (Colt Frederickson, Reggie Mead and Ben Poelstra; Presentation time: 4:46pm-5:05pm, Dec 5)
• Linux file system (Todd Howard and Jory Lenz; Presentation time: 4:10-4:25pm, Dec 7)
• Linux network stack (Jake Lucas, Ehson Mosleh and Tyghe Vallard; Presentation time: 4:25-4:45pm, Dec 7)
• Palm OS Cobalt (Mike McCarthy and Joey Moholt; Presentation time: 4:45-5:00pm, Dec 7)
• OpenBSD (Trevor Berg and Sheldon Ross; Presentation time: 4:10-4:20pm, Dec 9)
• Compression Algorithms (Julian Herrera; Presentation time: 4:20-4:30pm, Dec 9)

Final Exam (30%): Dec 13, 08:00am--9:50am

Final Grade