Operating Systems I
Principal lecturer: Dr Steven Hand
Taken by: Part IA CST
Past exam questions
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
The course comprises 17 lectures given M/W/F at 12:00 in the Hopkinson
Lecture Theatre, starting in Michaelmas on Wednesday 5th November, and
resuming in Lent term on Monday 19th January. The course divides into
three main parts as follows:
Part I. Computer Organisation
Part II. Operating Systems
- 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 III. OS Case Studies
- Introduction to Operating Systems.
Abstract view of an operating system. OS Evolution:
Dual-mode operation. Protecting I/O, memory, CPU.
Kernels and micro-kernels.
- Processes and Scheduling.
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.
- 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.
- 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
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 handouts are available on-line:
For the MIPS assembly section of the course it is strongly recommended
that you get a copy of SPIM, the MIPS simulator. Versions are available
for linux, mac OS X, or windows from
http://pages.cs.wisc.edu/~larus/spim.html. The same page has a
list of additional resources towards the end, and you should be able
to find a number of other sites with tutorial info or example programs.
It is of course best to learn by doing, so get programming!
- handout-1 (computer organization) [1up
- handout-2 (MIPS assembly) [2up]
- handout-3 (OS intro, processes, memory management)
- handout-4 (I/O, filing systems)
[1up] or [2up]
- handout-5 (case studies)
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.
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.
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. You can find them 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
- 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.
Feedback is welcome at any time: either through the on-line feedback
system, by e-mail to me or
through any of the other channels available.