Computer Laboratory – Course material 2008–09: Paper 2: Operating Systems I

Next: Lent Term 2009: Part Up: Michaelmas Term 2008: Part Previous: How to Study Computer Contents

Paper 2: Operating Systems I

This Paper 2 course is taken by Part IA Computer Science Tripos students only.

Lecturer: Dr S.M. Hand

No. of lectures: 17 (Continued into Lent Term)

Prerequisite course: Digital Electronics.

This course is a prerequisite for the Part IB courses Concurrent Systems and Applications and Introduction to Security, and the Part II courses Advanced System Topics, Distributed Systems and Security.

Aims

The overall aim of this course is to provide a general understanding of how a computer works. This includes 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.

Lectures

Computer organization. History: from vacuum tubes to VLSI. Von Neumann architecture. Hardware/software layers and languages. Operation of a simple computer (processors, memory, buses, devices). Memory: concepts, structures, hierarchy. Processor: control and execution units. ALU and computer arithmetic. Logical and conditional operations. Branches. Memory access. Data representation: (integers), text, reals, compound structures, instructions. Fetch-Execute cycle revisited. General I/O architecture. Example devices. Buses: general operation, hierarchy, synchronous versus asynchronous. Interrupts. Direct Memory Access. Programming in assembly. [5 lectures]
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. [1 lecture]
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. [2 lectures]
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. [2 lectures]
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. [1 lecture]
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. [1 lecture]
Protection. Requirements. Subjects and objects. Design principles. Authentication schemes. Access matrix: ACLs and capabilities. Combined scheme. Covert channels. [1 lecture]
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. [2 lectures]
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. [2 lecture]

Objectives

At the end of the course students should be able to

describe the fetch-execute cycle of a simple computer with reference to the control and execution units
understand the different types of information which may be stored within a computer memory
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

Recommended reading

Tanenbaum, A.S. (1990). Structured computer organisation. Prentice Hall (3rd ed).
Patterson, D. & Hennessy, J. (1998). Computer organisation and design. Morgan Kaufmann (2nd ed.).
* Bacon, J. & Harris, T. (2003). Operating systems. Addison-Wesley (3rd ed.).
Silberschatz, A., Peterson, J.L. & Galvin, P.C. (2005). Operating systems concepts. Addison-Wesley (7th 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.).

Next: Lent Term 2009: Part Up: Michaelmas Term 2008: Part Previous: How to Study Computer Contents