home search a-z help
University of Cambridge Computer Laboratory
Operating Systems I
Computer Laboratory > Course material 2005-06 > Operating Systems I

Operating Systems I
2005-06

Principal lecturer: Dr Steven Hand
Taken by: Part IA (50% option), Part IA (25% option), Part IA (Maths with Computer Science)


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

The course comprises 16 lectures given M/W/F at 12:00 in the Heycok Lecture theatre, starting in Michaelmas on Monday 14th November, and resuming in Lent term on Friday 20th January. The course divides into three main parts as follows:

Part I. Computer Organisation

  • Computer Foundations. History: from vacuum tubes to VLSI. Von Neumann architecture. Hardware/software layers and languages.

  • Operation of a Simple Computer. Overview: 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.

  • Input/Output. General I/O architecture. Example devices. Buses: general operation, hierarchy, synchronous versus asynchronous. Interrupts. Direct Memory Access. Review of Part I.
Part II. Operating Systems

  • 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. Subjects and objects. Design principles. Authentication schemes. Access matrix: ACLs and capabilities. Combined scheme. Covert channels.
Part III. 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.

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

Supervisions and Revision

The first set of notes are available on-line in (gzipped postscript, 1up, PDF, 1up, or gzipped poscript, 2up) formats. The second set of notes covering the case studies is now also available (PDF, 2up).

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. There is also a set of additional questions for the first part of the course (computer organisation) which were prepared by Dr Tim Harris in 2002. They are available in ps.gz and pdf formats.

Supervisors: note that a section of the first part of the course includes additional material not for examination and not covered in lectures. However you may wish to go over this with interested students.

Recommended books

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.
  • 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. (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.

Useful Links

Feedback

Feedback is welcome at any time: either through the on-line comment system, by e-mail to me or through any of the other channels available.