Operating System Functions
Principal lecturer: Dr Steven Hand (email@example.com)
Taken by: Part IB, Part II (General), Diploma
Lecturer: Dr S.M. Hand
No. of lectures: 8
Prerequisite course: Operating Systems or Operating System
This course is a prerequisite for Distributed Systems (Part II and Diploma).
This course hopes to impart a detailed understanding of the algorithms
and techniques used within operating systems. It aims to consolidate
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.
- Introduction and Review.
OS functions. Structures: kernel, microkernel,
vertical. Multiprocessor schemes. Execution: processes
and threads. User versus kernel threads.
Combined scheme: scheduler activations.
- CPU Scheduling.
Preemptive/non-preemptive. Static and dynamic priority schemes.
Multiprocessor issues. Problems with priority. Real-time scheduling:
static versus dynamic algorithms. Examples (RM, EDF, etc.).
Priority inversion. SRT scheduling.
- 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. Other VM techniques. [2 lectures]
- Storage Systems.
Basic I/O revisited. Disks. Logical volumes. RAID.
Disk scheduling: FCFS, SSTF, SCAN, C-SCAN, etc. SRT disk
scheduling. Disk caching; motivation,
Unix buffer cache, NT cache manager, extensibility. Filing
systems: overview, requirements. Data and metadata. Directory
retrieval. Examples: FAT, FFS/EXT2, NTFS. Other schemes.
Requirements. Subjects and objects. Design principles. Authentication
schemes. Access matrix: ACLs and capabilities. Combined scheme.
Covert channels. Hardware capability systems.
Software capability systems.
Motivation. Low-level techniques: VM, etc. OS-level techniques: linux,
NT, SPIN, Vino. User-level techniques: microkernels, Exokernel,
Nemesis. Future directions.
At the end of the course students should be able to
- differentiate threads and processes
- argue for and against dynamic priority-based scheduling
- 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
- compare and contrast user- and kernel-level threads
- describe the advantages/disadvantages of the
various page-replacement strategies
- understand the differences between ACLs and capabilities
- explain the operation of the RM and EDF scheduling algorithms
- discuss the benefits of disk caching
- describe three techniques for supporting extensibility
Bacon, J. (1997). Concurrent Systems. Addison-Wesley (2nd ed.).
Silberschatz, A., Peterson, J.L. & Galvin, P.B. (1998). Operating Systems Concepts. Addison-Wesley (5th ed.).
Stallings, W. (1997). Operating Systems: Internals and
Design Principles. Prentice-Hall (3rd ed.).
Tanenbaum, A.S. (1992). Modern Operating Systems. Prentice-Hall.
Leffler, S. (1989). The Design and Implementation of the 4.3BSD Unix
Operating System. Addison-Wesley.
Solomon, D. (1998). Inside Windows NT. Microsoft Press (2nd ed.).
Singal, M. & Shivaratri, N. (1994). Advanced Concepts in Operating
Systems: Distributed, Database, and Multiprocessor Operating
The lecture handouts, each covering approximately two lectures
each, will be available below as the course progresses.
past exam questions are also on line.
IB | II(G) | Dip
Provisional information only
Generated at 11:47.04 on 21/9/1999