Operating Systems: A Design-Oriented Approach 
by Charles Crowley

Operating Systems: A Design-Oriented Approach is a text for a junior or senior level class in operating systems. It covers the standard topics that one expects in such a course. It has several novel features that are described below.

Simple Operating System and Simulator

The book contains code for a simple operating system. There is a simulator that will allow you to compile and execute this code. For more information see the Simple Operating System Home Page.

There is also a Java version of this simulator. You can get the java files, compiled class files, documentation, and html files in zip format from] Java SOS distribution in zip format. or in gzipped tar format from Java SOS distribution in UNIX tar and GNU gzip format. Or you can run directly the Java version of SOS.

Code from the book

Look here to get the code from the book.

Supporting documents

There are several documents to support instructors using the book. These include a list of errata, notes for instructors, and lecture notes.

Here are three supportingdocuments in Microsoft Word format. I also have a link to an html version of each.

Here are PowerPoint presentations for each of the chapters in the book.

Main Features of the Book

The external operating system interface is described first.
Many students come to an operating system class without a clear understanding of what an operating system really does. These students should understand how operating system services are used before learning how these services are implemented. To deal with this problem, the book begins with a discussion of a simple set of system calls (similar to those used in UNIX). Example programs using these calls are given, and a simple shell program is used to integrate the examples.
Use of code
Concepts or case studies? There have always been two approaches to the operating systems class. The first approach is the concept or theory approach, which concentrates on the basic conceptual issues in the design of operating systems. These courses discuss each of the basic problems in operating systems design and the range of common solutions to those problems. The concepts books are mostly text and diagrams with little code. The second approach is the case study method which concentrates on an example operating system that is simple but complete. The example books contain a lot of code and spend a lot of pages explaining the code in detail.

 

 
 
 

There are advantages and disadvantages to both approaches. Some people feel the ideal situation is to take both classes, but this is rarely possible in an already crowded computer science curriculum so one is required to make a choice.

A middle course I have tried to find a middle course between the two approaches. This book is basically a concepts oriented book with more code than is usual. I have found that seeing actual code allows the students to understand the concepts more deeply, feel more comfortable about the material, and ask questions they wouldn't have thought to ask in a purely concepts oriented course. The code does not comprise a complete operating system however and it as simple as possible in order to reduce the number of pages devoted to explaining it

Development of concepts
I have tried to show how the important ideas in operating systems developed. The concepts in operating systems have developed over many years and the current solutions were developed slowly, in several stages. Each new solution had a problem that the next solution tried to fix. I think it helps the student to understand this development and see that these ideas were not brilliant flashes of insight that came out of nowhere but ideas that were improved by many people over many years. The development was a series of good ideas, where each improvement made sense in the context in which it was developed. Seeing this development helps to understand why the solutions have their present form. In addition, it is useful to know the design constraints that caused solutions to develop into their present form because technological advances often change these constraints and old solutions, that used to be inferior, become practical again. Finally, these developments give students examples of the design process through a series of potential, but flawed solutions to a problem to a final solution that is acceptable.
Examples
Each main topic is presented in a general way and then specific examples are given from a variety of operating systems, inclduing UNIX (several versions), Mach, OSF/1, Windows NT, OS/2, MS/DOS and MacOS.
Design orientation

 

 
 
 

Few computer professionals will participate in the design of an operating system during the course of their careers. While it is important that students of computer science have a good foundation in the basic concepts in specialized areas such as operating systems, it is not necessary that every computer science student understand all the details. There are many issued which are tackled during the design of an operating system which can be generalized and applied to other areas of computer science. In this book, I attempt to focus on these design issues and their implications for other areas.

The design techniques are noted in side bars as they come up, and longer explanations of each design topic are placed in separate chapters. The design principles are presented in the same format often used for design patterns. The instructor can structure a course with varying degrees of concentration on design aspects. The design sections are independent of the main flow of the text, and independent from each other. This will allow the instructor to pick and choose those design sections he or she finds to be useful.

I am striving for two things. First, I want to give the student an awareness of design issues, where they come up, which techniques to apply, how they can be generalized, etc. Clearly it is not possible to cover all design topics and issues. I do not present an organized survey of design techniques but a series of useful ones that come up in the context of operating systems. I hope to make the student aware of design and to enable the student to start doing their own generalizing about design. Second, I present a collection of useful design techniques that the students can use in their design toolkit.

I have oriented this book to provide a solid preparation for the larger design projects the student will encounter in later software engineering courses and as preparation for their career as a software professional designing, implementing and maintaining a wide variety of systems. The interrelations between the separate areas of computer science are becoming more important. For example, in the area of high speed parallel machines, it is clear that it is necessary to think of the hardware, the operating system and the programming language as a single system to get maximum performance. Optimization in any part of the system will have consequences for the other parts of the system.

Short Table of Contents

  1. Introduction
  2. The Hardware Interface
  3. The Operating System Interface
  4. Design Techniques I
  5. Implementing Processes
  6. Parallel Systems
  7. Interprocess Communication
  8. Processes
  9. Design Techniques II
  10. Memory Management
  11. Virtual Memory
  12. Virtual Memory Systems
  13. Design Techniques III
  14. IO Devices
  15. IO Systems
  16. File Systems
  17. File System Organization
  18. Design Techniques IV
  19. Resource Management
  20. The Client/Server Model

Longer Table of Contents

Also see a more detailed table of contents.
  1. Introduction
    1. Where does an operating system fit in?
    2. What does an operating system do?
    3. A Virtual Computer
    4. Do We Need an Operating System?
  2. The Hardware Interface
    1. The CPU
    2. Memory and Addressing
    3. Interrupts
    4. I/O Devices
  3. The Operating System Interface
    1. What Are System Calls?
    2. An Example System Call Interface
    3. Information and Meta-Information
    4. Naming Operating System Objects
    5. Devices as Files
    6. The Process Concept
    7. Communication Between Processes
    8. UNIX-style Process Creation
    9. Standard Input and Standard Output
    10. Communicating with Pipes
    11. Summary of System Call Interfaces
    12. Operating System Examples
    13. The User Interface to an Operating System
  4. Design Techniques I
    1. Operating Systems and Design
    2. Design Problems
    3. Design Techniques
    4. Two Level Implementation
    5. Interface Design
    6. Connection in Protocols
    7. Interactive and Programming Interfaces
    8. Decomposition Patterns
  5. Implementing Processes
    1. The System Call Interface
    2. Implementation of a Simple Operating System
    3. Implementation of Processes
    4. System Initialization
    5. Process Switching
    6. System Call Interrupt Handling
    7. Program Error Interrupts
    8. Disk Driver Subsystem
    9. Implementation of Waiting
    10. Flow of Control Through the Operating System
    11. Signaling in an Operating System
    12. Interrupts in the Operating System
    13. Operating Systems as Event and Table Managers
    14. Process Implementation
    15. Examples of Process Implementation
  6. Parallel Systems
    1. Parallel Hardware
    2. An Operating System for a Two Processor System
    3. Race Conditions With a Shared Process Table
    4. Atomic Actions
    5. A Multiprocessor Operating System
    6. Examples of Multiprocessor Operating Systems
    7. Threads
    8. Kernel-mode Processes
    9. Implementation of Mutual Exclusion
    10. Varieties of Computer Models
  7. Interprocess Communication Patterns
    1. Using Interprocess Communication
    2. Patterns of Interprocess Communication
    3. Problems When Processes Compete
    4. Race Conditions and Atomic Actions
    5. New Message Passing System Calls
    6. IPC Pattern: Mutual Exclusion
    7. IPC Pattern: Signaling
    8. IPC Pattern: Rendezvous
    9. IPC Pattern: Producer-Consumer
    10. IPC Pattern: Client-Server
    11. IPC Pattern: Multiple Servers and Clients
    12. IPC Pattern: Database Access and Update
    13. Review of Interprocess Communication Patterns
    14. A Physical Analogy
    15. Failure of Processes
  8. Processes
    1. Everyday Scheduling
    2. Preemptive Scheduling Methods
    3. Policy versus Mechanism in Scheduling
    4. A Scheduling Example
    5. Scheduling in Real Operating Systems
    6. Deadlock
    7. Why Deadlock is a Problem
    8. Conditions for Deadlock to Occur
    9. How To Deal With Deadlock
    10. A Sequence of Approaches to the Deadlock Problem
    11. Two Phase Locking
    12. Starvation
    13. Message Passing Variations
    14. Synchronization
    15. Separating Data Transfer and Synchronization
    16. Semaphores
    17. Implementing Semaphores
    18. Using Semaphores in the Simple Operating System
    19. Programming Language Based Synchronization Primitives
    20. Message Passing Design Issues
    21. IPC in Mach
    22. IPC and Synchronization Examples
  9. Design Techniques II
    1. Indirection
    2. Using State Machines
    3. Win Big Then Give Some Back
    4. Separation of Concepts
    5. Reducing a Problem to a Special Case
    6. Reentrant Programs
    7. Using Models for Inspiration
    8. Adding a New Facility To a System
  10. Memory Management
    1. Levels of Memory Management
    2. Linking and Loading a Process
    3. Variations in Program Loading
    4. Why Use Dynamic Memory Allocation?
    5. The Memory Management Design Problem
    6. Solutions to the Memory Management Design Problem
    7. Dynamic Memory Allocation
    8. Keeping Track of the Blocks
    9. Which Free Block To Allocate?
    10. Examples of Dynamic Memory Allocation
    11. Logical and Physical Memory
    12. Allocating Memory to Processes
    13. Multiprogramming Issues
    14. Memory Protection
    15. Memory Management System Calls
    16. Example Code for Memory Allocation
  11. Virtual Memory
    1. Fragmentation and Compaction
    2. Dealing with Fragmentation
    3. Memory Allocation Code With Pages
    4. Sharing the Processor and Sharing Memory
    5. Swapping
    6. Overlays
    7. Implementing Virtual Memory
    8. What is the cost of virtual memory?
    9. Virtual Memory Management
    10. Daemons and Events
    11. File Mapping
  12. Virtual Memory Systems
    1. Page Replacement
    2. Global Page Replacement Algorithms
    3. Page Replacement Examples
    4. Local Page Replacement Algorithms
    5. Evaluating Paging Algorithms
    6. Thrashing and Load Control
    7. Dealing with Large Page Tables
    8. Recursive Address Spaces
    9. Paging the Operating System Address Space
    10. Page Size
    11. Segmentation
    12. Sharing Memory
    13. Examples of Virtual Memory Systems
    14. Very Large Address Spaces
  13. Design Techniques III
    1. Multiplexing
    2. Late binding
    3. Static Versus Dynamic
    4. Space-Time Tradeoffs
    5. Simple Analytic Models
  14. I/O Devices
    1. Devices and Controllers
    2. Terminal Devices
    3. Communication Devices
    4. Disk Devices
    5. Disk Controllers
    6. SCSI Interfaces
    7. Tape Devices
    8. CD Devices
  15. I/O Systems
    1. I/O System Software
    2. Disk Device Driver Access Strategies
    3. Modeling of Disks
    4. Device numbers
    5. Unification of Files and I/O Devices
    6. Generalized Disk Device Drivers
    7. Disk Caching
    8. Two level structure of device drivers
    9. SCSI Device Drivers
    10. Examples of I/O Systems
  16. File Systems
    1. The Need for Files
    2. The File Abstraction
    3. File Naming
    4. File System Objects and Operations
    5. File System Implementation
    6. An Example File System Implementation
  17. File System Organization
    1. File System Organization
    2. File Descriptors
    3. How File Blocks Are Located On Disk
    4. Review of File Storage Methods
    5. Implementation of the Logical to Physical Block Mapping
    6. File Sizes
    7. Booting the Operating System
    8. File System Optimization
    9. File System Reliability
    10. File Security and Protection
    11. Examples of File Systems
  18. Design Techniques IV
    1. Caching
    2. Optimization and Hints
    3. Hierarchical Names
    4. Naming of Objects
    5. Unification of Concepts
  19. Resource Management
    1. Resources in an Operating System
    2. Resource Management Issues
    3. Types of Resources
    4. Integrated Scheduling
    5. Queuing Models of Scheduling
    6. Real-time Operating Systems
    7. Protection of Resources
    8. User Authentication
    9. Mechanisms for Protecting Hardware Resources
    10. Representation of Protection Information
    11. Mechanisms For Software Protection
    12. Examples of Protection Attacks
    13. Government Security Levels
    14. Protection Examples
    15. External Security
    16. The Use of Cryptography in Computer Security
  20. The Client Server Model
    1. Three Modes of Communication
    2. System Processes
    3. Micro-Kernel Operating Systems
    4. The Developments Towards a Distributed System
Back to Charles Crowley's Home Page

Last modified on 2 July 1996