Operating Systems II
Principal lecturer: Dr Steven Hand
Taken by: Part IB
Operating Systems II
Lecturer: Dr S.M. Hand
No. of lectures: 8
Prerequisite courses: Operating Systems, Concurrent Systems and Applications
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.
- 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]
Requirements. Subjects and objects. Design principles. Authentication
schemes. Access matrix: ACLs and capabilities. Combined scheme.
At the end of the course students should be able to
- write a simple program which implements any simple disk
- 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
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.).
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
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).
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.
- Process Control and Scheduling Issues
for Multiprogrammed Shared-Memory Multiprocessors, Tucker and
Gupta, SOSP 1989.
- A Comparison of basic CPU Scheduling
Algorithms for Multiprocessor Unix, Curran, Computing Systems
- First Class User-Level
Threads, Marsh et al, SOSP 1991.
- Scheduler Activations: Effective Kernel
Support for the User-Level Management of Parallelism, Anderson
et al, ACM TOCS 1992.
- A Fast File System for UNIX,
McKusick et al, TOCS '84.
- The Design and Implementation
of a Log-Structured File System,Rosenblum et al, SOSP '91.
You can also find a selection of miscellaneous other useful papers