Course material 2010–11
The overall aim of this course is to provide a general understanding of how low-level computer software works. This includes some aspects of the underlying hardware as well as the structure and key functions of the operating system. Case studies will be used to illustrate and reinforce fundamental concepts.
The course comprises 12 lectures given M/W/F at 12:00 in the Hopkinson Lecture Theatre, starting in Michaelmas on Wednesday 3rd November. The course divides into two main parts as follows:
Part I. Operating Systems Functions
- Introduction to Operating Systems. Abstract view of an operating system. OS Evolution: multi-programming, time-sharing. Dual-mode operation. Protecting I/O, memory, CPU. Kernels and micro-kernels.
- Processes and Scheduling. Job/process concepts. Scheduling basics: CPU-I/O interleaving, (non-)preemption, context switching. Scheduling algorithms: FCFS, SJF, SRTF, priority scheduling, round robin. Combined schemes.
- Memory management. Processes in memory. Logical addresses. Partitions: static versus dynamic, free space management, external fragmentation. Segmented memory. Paged memory: concepts, internal fragmentation, page tables. Demand paging/segmentation. Replacement strategies: OPT, FIFO, LRU (and approximations), NRU, LFU/MFU, MRU. Working set schemes.
- I/O Subsystem. General structure. Polled mode versus interrupt-driven I/O. Application I/O interface: block and character devices, buffering, blocking versus non-blocking I/O. Other issues: caching, scheduling, spooling, performance.
- File Management. File concept. Directory and storage services. File names and meta-data. Directory name-space: hierarchies, DAGs, hard and soft links. File operations. Access control. Existence and concurrency control.
- Protection. Requirements. Subject and Objects. Design Principles. Authentication schemes. Access matrix (ACLs and capabilities; combined schemes). Cover channels.
Part II. OS Case Studies
- Unix case study. History. General structure. Unix file system: file abstraction, directories, mount points, implementation details. Processes: memory image, life cycle, start of day. The shell: basic operation, commands, standard I/O, redirection, pipes, signals. Character and block I/O. Process scheduling.
- Windows NT case study. History. Design principles. Overall architecture. HAL. Kernel: objects, processes, threads, scheduling. Executive: object manager and object namespace, process manager, VM manager, I/O manager. File-System. Security System.
At the end of the course students should be able to
- explain the concepts of process, address space, and file
- compare and contrast various CPU scheduling algorithms
- understand the differences between segmented and paged memories, and be able to describe the advantages and disadvantages of each
- compare and contrast polled, interrupt-driven and DMA-based access to I/O devices
Supervisions and Revision
In previous years, there was a second course in Part IB which covered additional topics in operating systems. Some parts of this have been incorporated into the current Part 1A course, but some others were not (due to space constraints). For interested students, I've put the old Part IB notes here, as well as a short document which expands on some of the aspects therein here. Please feel free to read these yourselves and/or discuss them with your supervisor.
The past exam questions are also online and are useful for exam practice, or for assigning supervision work. Note that the course was substantially revised in 1998/99, and so many questions prior to to 1999 are not relevant; some exceptions are 1998 P1Q4 and 1998 P1Q11.
Finally, one of the PhD students in the systems research group has put together a set of sample / revision questions which cover all parts of the course. Some questions cover topics which are no longer lectured in this course, instead being covered in Computer Fundamentals, but should still be able to attempt them. The latest version is available here.
There are a large number of books covering the various topics in this course; a selection are listed below. One caveat regarding operating systems texts; many details of process synchronization issues are not relevant to this course, being a topic covered in subsequent lecture series.
- Bacon, J. & Harris, T (2003). Operating Systems. Addison-Wesley (3rd ed).
- Silberschatz, A., Peterson, J.L. &; Galvin, P.C. (1998). Operating Systems Concepts. Addison-Wesley (5th or 6th ed).
- Leffler, S. (1989). The Design and Implementation of the 4.3BSD Unix Operating System. Addison-Wesley.
- Solomon, D. & Russinovich, M. Inside Windows 2000. Microsoft Press (3rd ed.), 2000, or Windows Internals, Microsoft Press (4th ed.), 2005.
- On-line Information for Operating Systems (Bacon & Harris)
- On-line Information for Operating Systems Concepts (Silberschatz et al)
- Guide to the linux kernel