Computer Laboratory

Course pages 2016–17

Operating Systems

Principal lecturer: Dr Richard Mortier
Taken by: Part IA CST 50%, Part IA CST 75%
Past exam questions

No. of lectures: 12
Suggested hours of supervisions: 3 to 4
Prerequisite courses: Computer Fundamentals, Digital Electronics
This course is a prerequisite for Concurrent & Distributed Systems (Part IB), Security (Parts IB and II) and Mobile and Sensor Systems (Part II).

Aims

The overall aim of this course is to provide a general understanding of the structure and key functions of the operating system. Case studies will be used to illustrate and reinforce fundamental concepts.

Lectures

  • Introduction to operating systems. Abstract view of an operating system. Elementary computer architecture. OS evolution: multi-programming, time-sharing. [1 lecture]

  • Protection. Dual-mode operation. Protecting I/O, memory, CPU. Kernels and micro-kernels. Subjects and objects. Authentication. Access matrix: ACLs and capabilities. Combined scheme. Covert channels. [1 lecture]

  • Processes. Job/process concepts. Lifecycle. Process management. Inter-process communication. [1 lectures]

  • Scheduling. 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. [3 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]

  • 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]


Objectives

At the end of the course students should be able to

  • describe the general structure and purpose of an operating system;
  • 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

* Bacon, J. & Harris, T. (2003). Operating systems. Addison-Wesley (3rd ed.).
Silberschatz, A., Peterson, J.L. & Galvin, P.C. (2008). Operating systems concepts. Wiley (8th ed.).
Anderson, T. & Dahlin, M. (2014). Operating Systems: Principles & Practice. Recursive Books (2nd ed.).
Leffler, S. (1989). The design and implementation of the 4.3BSD Unix operating system. Addison-Wesley.
McKusick, M.K., Neville-Neil, G.N. & Watson, R.N.M. (2014) The Design and Implementation of the FreeBSD Operating System. Pearson Education. (2nd ed.).
Solomon, D. & Russinovich, M. (2000). Inside Windows 2000. Microsoft Press (3rd ed.).