Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Operating Systems II
Computer Laboratory > Course material 2005-06 > Operating Systems II

Operating Systems II
2005-06

Principal lecturer: Dr Steven Hand
Taken by: Part IB


Operating Systems II

Lecturer: Dr S.M. Hand (smh22@cl.cam.ac.uk)

No. of lectures: 8

Prerequisite courses: Operating Systems, Concurrent Systems and Applications

Aims

This course hopes to impart a detailed understanding of the algorithms and techniques used within operating systems. It aims to consolidate and build upon the knowledge learned in earlier courses, and to encourage students to develop an appreciation for the trade-offs involved in designing and implementing an operating system.

Lectures

  • Thread scheduling. Recap: OS functions & structures. Thread package architectures (user, kernel, combined). Scheduling for multiprocessors.

  • Real-time systems. Introduction. Real-time scheduling: static versus dynamic algorithms. Examples (RM, EDF, etc.). Priority inversion. SRT/multimedia scheduling.

  • Virtual memory management. Logical versus physical addresses. Address binding. Single and multi-VAS models. Review: segmented/paged memory. Translation schemes. Demand paging/segmentation. Replacement strategies: OPT, FIFO, LRU (and approximations), NRU, LFU/MFU, MRU. Working set schemes. Application hooks. Prepaging and page daemons. Case studies. [2 lectures]

  • Storage systems. Basic I/O revisited. Disks I/O. Disk scheduling: FCFS, SSTF, SCAN, C-SCAN, etc. Logical volumes. RAID. Disk caching; motivation, Unix buffer cache, NT cache manager. Filing systems: file mapping algorithms, metadata, namespace. Directory implementation. Integrity management. Examples: FAT, FFS/EXT2, NTFS, LFS. [3 lectures]

  • Protection. Requirements. Subjects and objects. Design principles. Authentication schemes. Access matrix: ACLs and capabilities. Combined scheme. Covert channels.

Objectives

At the end of the course students should be able to

  • write a simple program which implements any simple disk scheduling algorithm

  • define the ``working set'' of a process

  • sketch the design of a log-structured file system

  • describe the advantages/disadvantages of the various page-replacement strategies

  • understand the differences between ACLs and capabilities

Recommended books

Bacon, J. & Harris, T. (2003). Operating Systems or Bacon, J. (1997) Concurrent Systems (2nd ed.). Addison-Wesley.
Silberschatz, A., Peterson, J.L. & Galvin, P.C. (1998). Operating Systems Concepts. Addison-Wesley (5th ed.).
Tanenbaum, A.S. (2001). Modern Operating Systems (2nd ed.). Prentice-Hall.
Leffler, S. (1989). The Design and Implementation of the 4.3BSD Unix Operating System. Addison-Wesley.
Solomon, D. & Russinovich, M. (2000). Inside Windows 2000. Microsoft Press (3rd ed.).
Singal, M. & Shivaratri, N. (1994). Advanced Concepts in Operating Systems: Distributed, Database, and Multiprocessor Operating Systems. McGraw-Hill.


Useful Links

The notes [gzipped postscript, PDF] and the past exam questions are available on-line. There are also some additional prose notes which discuss some of the lectured material in more detail (including additional, non-examinable material). Further past exam questions are available from the predecessor course entitled "Operating System Functions"; this had a slightly different syllabus, but most of the past questions should be answerable.

Additional reading:

You can also find a selection of miscellaneous other useful papers here.