You are previewing Operating Systems: Concurrent and Distributed Software Design.
O'Reilly logo
Operating Systems: Concurrent and Distributed Software Design

Book Description

Modern software systems rely on the concepts of concurrency, modularity and distribution, both within the design of the operating system and those systems that it supports. Underlying this book is the premise that distributed systems are now commonplace and a reader is more likely to be using one than a centralized time-sharing system. This modern approach therefore avoids the focus on centralized systems, instead placing the operating system within its context and providing an overview of system components and their relationships.The book is divided into four parts:
System Design, covering the basic operating system functions and describing the abstraction and implementation of a system as a community of (possibly distributed) concurrent processes. Distributed systems are introduced and a chapter on system security is included.
Concurrency Control in Main Memory, focusing on concurrency control in operating systems and application-level systems and exploring inter-process communication (IPC) in the context of (distributed) system design.
Transactions, demonstrating the general applicability of concurrent composite operations.
Case Studies, considering different systems in the light of the perspective developed in the book: Classical UNIX; Linux, Solaris and Contemporary Unix; Extensible Systems; Windows 2000; Web Programming; Middleware; and Transaction Processing Systems.The Java language has been used throughout to illustrate object-oriented concepts, concurrent algorithms and distributed programming and the book includes a chapter on system security. The case studies, covering a full suite of professional operating systems, enable the course to be taught as a blend of theory and practice, so that on completion of the course a student is able to adapt and build real operating systems that function within a distributed environment.

Table of Contents

  1. Copyright
  2. International Computer Science Series
  3. Preface
  4. System design requirements
    1. Inherently concurrent systems
    2. Supporting potentially concurrent applications
    3. Architectures for software systems
    4. Defining a concurrent system
    5. Systems implementation requirements
    6. Security, protection and fault tolerance in system design
  5. System design: Technology and principles
    1. System structure and dynamic execution
      1. System structure: Conceptual views
      2. System structure: Implementational views
      3. The process concept
      4. Operating system functions
      5. Operating system invocation and protection
      6. Operating system structure
      7. Object structuring within and supported by operating systems
      8. Distributed object systems, platforms and middleware
      9. Security and protection
      10. Summary
    2. The hardware interface, I/O and communications
      1. Overview
      2. Device interfacing
      3. Exceptions
      4. Multiprocessors
      5. User-level input and output
      6. Communications management
      7. Communications networks, interfaces and drivers
      8. Communications software
      9. Communications handling within and above an operating system
      10. Summary
    3. Support for processes
      1. Terminology
      2. Use of processes in systems
      3. Processes and processors
      4. Process state
      5. Synchronizing with the hardware: Events and the WAIT operation
      6. The process data structure
      7. Scheduling: General approaches
      8. Scheduling for shared-memory multiprocessors
      9. Process scheduling to meet real-time requirements
      10. Process abstraction and implementation
      11. Operating system structure and placement of processes
      12. Multi-threaded process implementation
      13. Processes in languages, runtime systems and operating systems
      14. Process state in language systems and operating systems
      15. Sequential programs with system calls
      16. Evolution of concurrency in programming languages
      17. Implementation of processes in language systems
      18. Thread package architectures
      19. Java threads and exceptions
      20. Summary
    4. Memory management
      1. Memory management
      2. The memory hierarchy
      3. The address space of a process
      4. Segmented virtual memory
      5. Paged virtual memory
      6. Combining segmentation and paging
      7. Operating system data structures
      8. An example of a memory management unit (MMU)
      9. Memory management in system design
      10. Summary
    5. File management
      1. File management
      2. An overview of filing system functions
      3. File and directory structure
      4. The filing system interface
      5. The filing system implementation
      6. Modern file system design
      7. Network-based file servers
      8. Integrating virtual memory and storage
      9. Summary
    6. Fundamentals of distributed systems
      1. Introduction
      2. Evolution of distributed systems for the workplace
      3. Personal computing
      4. Model and software architecture
      5. Special characteristics of distributed systems
      6. Time in distributed systems
      7. Naming
      8. Mobile users, computers and objects
      9. Summary
    7. Security
      1. Scenarios and security requirements
      2. Threats and risk analysis
      3. Approaches to encryption
      4. Algorithms
      5. Protocols
      6. Examples
      7. Summary
  6. Concurrency control in main memory
    1. System structure
      1. Processes sharing an address space
      2. Processes in separate address spaces
      3. Sharing the operating system
      4. Summary of process placement in the two models
      5. Requirements for process interaction
      6. Types of process interaction
      7. A process interaction
      8. Definition of single concurrent actions
    2. Low-level synchronization: Implementation
      1. Process synchronization compared with event signal and wait
      2. Mutual exclusion
      3. Hardware support for mutual exclusion
      4. Semaphores
      5. Styles of use of semaphores
      6. Implementation of semaphore operations
      7. Summary
    3. Low-level synchronization: Algorithms
      1. Introduction
      2. An example of semaphores in system design: The THE system
      3. The producer–consumer, bounded buffer problem
      4. Safety and liveness properties
      5. The multiple readers, single writer problem
      6. Limitations of semaphores
      7. Eventcounts and sequencers
      8. POSIX threads
      9. Summary
      10. Case study with exercises: Management of a disk block cache
    4. IPC with shared memory
      1. Critical regions in programming languages
      2. Monitors
      3. Synchronization at the granularity of operations
      4. Summary
    5. IPC and system structure
      1. Styles of inter-process communication
      2. System structure and IPC with shared memory
      3. System structure and IPC without shared memory
      4. Systems where shared-memory communication is appropriate
      5. Systems where shared-memory communication is not appropriate
      6. Examples from classical UNIX
      7. Overview of inter-process communication
      8. Duality of system structures
      9. Naming
      10. Summary
    6. IPC without shared memory
      1. Introduction
      2. Use of files for common data
      3. UNIX pipes
      4. Asynchronous message passing
      5. Variations on basic message passing
      6. Implementation of asynchronous message passing
      7. Synchronous message passing
      8. Message passing in programming languages
      9. Multi-threading in clients and servers
      10. Summary
    7. Crash resilience and persistent data
      1. Crashes
      2. A model of a crash
      3. Crash resilience or failure transparency
      4. Idempotent (repeatable) operations
      5. Atomic operations on persistent objects
      6. Implementation of atomic operations
      7. Non-volatile memory
      8. A single operation on persistent data
      9. Database management systems' requirements on operating systems
      10. Summary
    8. Distributed IPC
      1. Introduction
      2. Special characteristics of distributed systems
      3. Distributed IPC: Message passing
      4. Integration of IPC with communications
      5. Java's sockets and streams
      6. Distributed programming paradigms
      7. Remote procedure call (RPC)
      8. RPC–language integration
      9. Java's RMI: RPC in the general object model
      10. Critique of synchronous invocation
      11. Naming, location and binding
      12. Summary of Part II
  7. Transactions
    1. Composite operations
      1. Composite operations
      2. Composite operations in main memory
      3. Composite operations involving main memory and persistent memory
      4. Concurrent execution of composite operations
      5. Potential problems
      6. Crashes
      7. Summary
    2. Resource allocation and deadlock
      1. Requirements for dynamic allocation
      2. Deadlock
      3. Livelock and starvation
      4. Conditions for deadlock to exist
      5. The dining philosophers problem
      6. Object allocation graphs
      7. Data structures and algorithms for deadlock detection
      8. Deadlock avoidance
      9. Information on releasing objects: Multiphase processes
      10. Distributed deadlocks
      11. Summary
    3. Transactions
      1. Introduction
      2. Transaction specification and programming
      3. The definition of serializability and consistency
      4. The ACID properties of transactions
      5. Indicating specific orderings of transactions
      6. A system model for transaction processing
      7. Dependency graphs for transactions
      8. Histories and serialization graphs
      9. Dealing with aborts: More about the property of isolation
      10. Summary
    4. Concurrency control
      1. Introduction
      2. Concurrent composite operations in main memory only
      3. Structure of transaction management systems
      4. Concurrency control through locking
      5. Time-stamp ordering (TSO)
      6. Optimistic concurrency control (OCC)
      7. Summary
    5. Recovery
      1. Requirements for recovery
      2. The object model, object state and recovery
      3. Concurrency, crashes and the properties of transactions
      4. Logging and shadowing for crash resilience
      5. Use of a recovery log
      6. Idempotent undo and redo operations
      7. Transaction states on a failure
      8. An algorithm for recovery
      9. Location databases for mobile objects
      10. Summary
    6. Distributed transactions
      1. An object model for distributed systems
      2. Distributed transaction processing
      3. Communication
      4. Concurrency control: Two-phase locking (2PL)
      5. Concurrency control: Time-stamp ordering (TSO)
      6. Optimistic concurrency control (OCC)
      7. Commit and abort in a distributed system
      8. Atomic commitment: The two-phase commit (2PC) protocol
      9. Two-phase validation for OCC
      10. Summary
    7. Distributed computations
      1. Introduction
      2. Process groups
      3. Consistency of data replicas
      4. Ordering message delivery
      5. Distributed, N-process mutual exclusion
      6. Summary of Part III
  8. Case Studies
    1. Classical UNIX
      1. Introduction
      2. Evolution of UNIX
      3. System structure and the UNIX kernel
      4. File system interfaces
      5. File system implementation
      6. Process creation, termination and scheduling
      7. IPC: Pipes and signals
      8. Summary
    2. LINUX, Solaris and contemporary UNIX
      1. Introduction
      2. Kernel structure
      3. SVr4 IPC
      4. Sockets and file subsystem integrated IPC
      5. Memory management
      6. Multiprocessor scheduling
      7. Summary
    3. Extensible systems
      1. Mechanisms for extensibility
      2. Compile-time specialization
      3. Microkernel operating systems
      4. Downloadable code
      5. Exokernels and vertical structuring
      6. Nested virtual machines
      7. Extensible virtual machines
      8. Summary
    4. Windows 2000
      1. Introduction to Windows 2000
      2. System structure
      3. The object model and object manager
      4. The kernel
      5. Processes, threads, fibres and concurrency control
      6. The I/O subsystem
      7. The NT filing system, NTFS
      8. Networking
      9. Summary
    5. The World Wide Web
      1. A simple web-client, web-server interaction
      2. Naming web pages
      3. Communication using HTTP
      4. Document representation
      5. Executing programs at server and client
      6. Security
      7. Concurrency control
      8. Scalability issues
      9. Web-based middleware: XML and SOAP
      10. Summary
    6. Middleware
      1. Middleware paradigms
      2. Java middleware
      3. OMG and OMA
      4. CORBA
      5. ODMG
      6. COM, DCOM and .NET
      7. Message-oriented middleware (MOM)
      8. Summary
    7. Transaction processing monitors and systems
      1. Transaction processing monitors
      2. Introduction to some electronic funds transfer (EFT) applications
      3. International inter-bank payments: SWIFT
      4. Authentication by PIN
      5. The international automatic teller machine (ATM) network service
      6. Load and traffic in TP systems
      7. Summary and trends
    8. Evolution of computer systems
      1. Evolution and exploitation of technology
      2. Operating systems and distributed operating systems
      3. Databases
      4. Concurrency control
  9. Bibliography
  10. Glossary