52.206 Operating Systems I---the Web pages

The course is finished, and I'm buggered if I'm doing it next year. Here's what used to be on the Web pages anyway: they haven't changed since c. June 1998.

Some people even filled in the evaluation questionnaire.

Your lecturer for this evening was Andrew Forrest, whose e-mail address is af@cs.strath.ac.uk. (He lives in room L10.01.)

The recommended text for the class is Modern Operating Systems, by Andrew S. Tanenbaum. Prentice-Hall, 728 pages, ISBN 0-13-595752. Another book by the same author, Operating Systems: Design and Implementation covers much of the same material. The author reckons that both are up-to-date, but the former is more theoretical, the later more practical. If you consider yourself a 'hands on' person (and want an OS book with a code listing of an actual operating system in the appendices), go buy the 'Design and Implementation' one. Last time I checked, the book shop had both. (If I ever give page references, they will be for the 'Modern OS' book.)

For a bit more detail, refer to more stuff about the class.

The notes

The notes below are arranged by topic and not by lecture number---if you hadn't noticed---but the material is in largely the same order. Where references are given to the book, they are given as section references, not page references---as in (section 1.2.3).

1. What is an operating system?

What and why? Some history. Different kinds of OS. Different designs of OS. A few definitions.

2. Processes and multitasking

How the OS keeps track of tasks. What happens when it switches between tasks. Interrupts and UNIX signals. Processes going to sleep.

Scheduling processes: First-come, first-served (and Shortest Job First); Round-robin; Priority; Real-time; Multilevel; Linux's scheduling policy.

3. Concurrency issues

The problem with race conditions, and why we need mutual exclusion. Low-level mutual exclusion primitives: disabling interrupts, TAS instruction, alternation, Peterson's solution. Higher-level IPC mechanisms: message-passing, signals, pipes and...

...the all-conquering semaphore. Using for mutual exclusion. Theory of semaphores. Implementing semaphores.

Summary of IPC mechanisms.

Also, the producer-consumer problem (& solution), the readers and writers problem (& solution), the dining philosophers problem and my personal problems. Later we will examine the problem of deadlock in more depth.

4. Managing memory

The importance of memory management. MM in a single-process machine. Memory partitions: relocating and protecting. Swapping. External fragmentation.

Summary of memory management issues.

Paging and its advantages. Page tables: example page mapping, page table entries, multilevel page tables, translation lookaside buffer, contexts and flushing PTEs from the TLB. Choice of page size. Global vs. local frame allocation.

Virtual memory. Page replacement algorithms: The Optimal Algorithm, First-In-First-Out (FIFO), Least-Recently Used (LRU), Not Recently Used (NRU), Not Frequently Used (NFU) with aging. The paging dæmon.

Segmented memory systems.

Allocating memory on the heap: using a bitmap, linked lists, the buddy system. Garbage collection.

5. Managing disk space

Files, namespaces, filesystems. Directories and inodes.

Allocating disk space for files: contiguous file allocation; linked-list allocation; FAT allocation; indexed allocation. Indexed allocation in UNIX.

Links both hard and soft.

Maintaining the integrity of the filesystem, and remembering to back-up regularly.

6. I/O

Issues in Input/Output: resource naming, protection.

Block caches and spooling.

The physical structure of disks. Disk head scheduling.

Deadlocks: preventing, avoiding, detecting, ignoring.