Home Page for CS418 (Fall 2007)

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: Mon, Wed, Fri: 2:00pm-3:00pm; Wed: 9am-10am (or by appointment)
• Email: bhz@cs.montana.edu
• Phone: X4836

Syllabus by week

• I will update the syllabus before each lecture.
• Aug 27 --- Overview of OS (pdf) (read Chapter 2 of Stallings).
• Aug 29 --- Early memory management. Static and dynamic partition, memory deallocation (pdf) (read Chapter 2 of Stallings).
• Aug 31 --- Memory hierarchy and cache memory (pdf) (read 1.5, 1.6, Appendix 1A of Stallings).
• Sep 3 --- No class on Sep 3 (Labor Day holiday).
• Sep 5 --- Paging and demand paging (pdf) (read Chapter 7 of Stallings).
• Sep 7 --- Page replacement policies, segmented memory allocation, segmented/demand paged memory (pdf) (read Chapter 8 of Stallings).
• Sep 10 --- Class cancelled due to the CS Seminar by Chris Nelson (in EPS 108). Students should take this chance to review what we have covered. I am listing some of the important keywords for your reference: Memory allocation, Single-user system, Multiprogramming, Fixed partition (internal fragmentation), Dynamic partition (external fragmentation), First-fit/Best-bit memory allocation, Deallocation, Relocatable dynamic partition, Compaction (garbage collection), Bounds register, Relocation register, Memory hierarchy, Paging (page, page frame), Job table, Page map table (PMT), Displacement, Address resolution, Demand paging, Page fault, Page interrupt handler, Thrashing, Page swap, Page replacement policies (FIFO, LRU), Working set, Segmented memory allocation, Segment, Segment map table, Virtual memory.
• Sep 12 --- Buddy system. Hash tables (pdf) (read 8A of Stallings). ( Detailed Review on Hashing (ppt).)
• Sep 14, 17 --- Device management (pdf) (read Chapter 11 of Stallings).
• Sep 19 --- File management (pdf) (read Chapter 12 of Stallings).
• Sep 21 --- Test 1 (contents: everything covered up to the end of the Sep 17 lecture; note that one A4 cheat-sheet is allowed, but no books and class notes are allowed).
• Sep 24 --- File management (follow-up of Sep 19 lecture). Review of test 1.
• Sep 26, 28, Oct 1, 3 --- Processor management, part 1(pdf) (read Chapter 3, 4 and 9 of Stallings).
• Oct 1 --- Creating processes and threads in UNIX (Linux) system. Program 1, Program 2, Program 3.
• Oct 3 --- Processor management, part 1. Gentax presentation.
• Oct 5, 8, 10, 12 --- Processor management, part 2 -- deadlock, starvation and synchronization (read Chapter 5,6 of Stallings and the handouts).
• Oct 12, 15 --- Readers and Writers problem (read the handouts).
• Oct 15 --- Public Key Cryptosystem (read the class notes).
• Oct 17 --- Test 2 (contents: everything covered from Sep 19 up to the end of the Oct 12 lecture; note that one A4 cheat-sheet is allowed, but no books and class notes are allowed).
• Oct 19, 22 --- RSA Public Key Cryptosystem (read the handouts).
• Oct 24 --- Multiprocessor scheduling (pdf) (read 10.1 of Stallings).
• Oct 26, 29 --- Real-time scheduling (pdf) (read 10.2 of Stallings and the handouts).
• Oct 29, 31 --- Queuing Analysis (pdf) Queuing analysis (read Appendix 9B).
• Nov 2, 5 --- Introduction to distributed processing (pdf) (read 14.1 of Stallings).
• Nov 5, 7 --- Process Migration and Distributed Global States (pdf) (read 15.1-2 of Stallings).
• Nov 7, 9 --- Distributed mutual exclusion/deadlock (pdf) (read 15.3 of Stallings).
• Nov 12 --- Veteran's day (no class).
• Nov 14 --- Error detection/correction, CRC code.
• Nov 16 --- Test 3 (contents: everything covered since Oct 15).
• Nov 19 --- System administration.
• Nov 21, 23 --- Thanksgiving holidays (no class).
• Nov 26 --- Dev 7: presentation of projects.
• Dec 5 --- Review for final.

Tests (30%)

• CS418 - test 1 (Test 1 is scheduled on Sep 21, 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 16, during regular class time.)

Assignments (30%)

• CS418 - assignment 1 (pdf) (Due: Oct 10, 2007.)
• CS418 - assignment 2 (pdf) (Due: Nov 02, 2007.)
• CS418 - assignment 3 (pdf) (Due: Dec 03, 2007.)

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 XX 2007!
• 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.
• Palm OS (Eric Harlow, Tyson Joehler and Aric Walker; Presentation time: 4:10pm-4:35pm, Nov 26)
• Boehm's Garbage Collector vs Reference Counting (Andy Johnson; Presentation time: 4:35pm-4:45pm, Nov 26)
• Linux File System (Rance Harmon, Paul Scheible and Mark Wolfe; Presentation time: 4:10-4:35pm, Nov 28)
• Windows Vista Audio Stack (Barrett Fuhrmann, Kyle Davis and Cassie Reynolds; Presentation time: 4:35pm-5:00pm, Nov 28)
• Google File System (Brett Bukowski and Kyle Miller; Presentation time: 4:10-4:35pm, Nov 30)
• Google's Map Reduce System (Nick Howard, Ian Lake and David Wax; Presentation time: 4:35pm-5:00pm, Nov 30)
• File Compression (Mateo Jara and Eric Schweitzer) Presentation time: 4:10-4:35pm, Dec 3)
• Windows and Linux administration and security (Brett Sanborn and Chris Shover; Presentation time: 4:35pm-5:00pm, Dec 3)
• Windows File Management Systems: FAT, FAT32 and NFTS (David Hybner; Presentation time: 4:10pm-4:20pm, Dec 5)
• Database-based file systems (Michael Nolop and Michael Schuld; Presentation time: 4:20pm-4:40pm, Dec 5)
• DX10 in Windows XP (Kelly Kortum; Presentation time: 4:10pm-4:20pm, Dec 7)
• Mac OS X (William Hosbein, Chris Rossmith and Russell Tempero; Presentation time: 4:20pm-4:50pm, Dec, 7)
• Real-time OS (Scott Wahl; Presentation time: 4:50pm-5:00pm, Dec 7)

Final Exam (30%): Dec 13, 6:00pm--7:50pm

Final Grade