book

Operating System Concepts Essentials

by Peter Baer Galvin, Abraham Silberschatz, Greg Gagne

November 2010

Beginner

744 pages

23h 48m

English

Wiley

Read now

Unlock full access

Organization of This BookContent of This BookOperating-System EnvironmentsOperating System EssentialsProgramming Problems and ProjectsTeaching SupplementsContacting UsAcknowledgments
1.1. What Operating Systems Do1.1.1. User View1.1.2. System View1.1.3. Defining Operating Systems1.2. Computer-System Organization1.2.1. Computer-System Operation1.2.2. Storage Structure1.2.3. I/O Structure1.3. Computer-System Architecture1.3.1. Single-Processor Systems1.3.2. Multiprocessor Systems1.3.3. Clustered Systems1.4. Operating-System Structure1.5. Operating-System Operations1.5.1. Dual-Mode Operation1.5.2. Timer1.6. Process Management1.7. Memory Management1.8. Storage Management1.8.1. File-System Management1.8.2. Mass-Storage Management1.8.3. Caching1.8.4. I/O Systems1.9. Protection and Security1.10. Distributed Systems1.11. Special-Purpose Systems1.11.1. Real-Time Embedded Systems1.11.2. Multimedia Systems1.11.3. Handheld Systems1.12. Computing Environments1.12.1. Traditional Computing1.12.2. Client-Server Computing1.12.3. Peer-to-Peer Computing1.12.4. Web-Based Computing1.13. Open-Source Operating Systems1.13.1. History1.13.2. Linux1.13.3. BSD UNIX1.13.4. Solaris1.13.5. Utility1.14. Summary1.15. Practice Exercises1.16. Exercises1.17. Bibliographical Notes
2.1. Operating-System Services2.2. User Operating-System Interface2.2.1. Command Interpreter2.2.2. Graphical User Interfaces2.3. System Calls2.4. Types of System Calls2.4.1. Process Control2.4.2. File Management2.4.3. Device Management2.4.4. Information Maintenance2.4.5. Communication2.4.6. Protection2.5. System Programs2.6. Operating-System Design and Implementation2.6.1. Design Goals2.6.2. Mechanisms and Policies2.6.3. Implementation2.7. Operating-System Structure2.7.1. Simple Structure2.7.2. Layered Approach2.7.3. Microkernels2.7.4. Modules2.8. Virtual Machines2.8.1. History2.8.2. Benefits2.8.3. Simulation2.8.4. Para-virtualization2.8.5. Implementation2.8.6. Examples2.8.6.1. VMware2.8.6.2. The Java Virtual Machine2.9. Operating-System Debugging2.9.1. Failure Analysis2.9.2. Performance Tuning2.9.3. DTrace2.10. Operating-System Generation2.11. System Boot2.12. Summary2.13. Practice Exercises2.14. Exercises2.15. Programming Problems2.16. Programming Projects2.16.1. Adding a system call to the Linux kernel.2.16.2. Part 1: Getting Started2.16.3. Part 2: Building a New Kernel2.16.4. Part 3: Extending the Kernel Source2.16.5. Part 4: Adding a System Call to the Kernel2.16.6. Part 5: Using the System Call from a User Program2.17. Bibliographical Notes
3.1. Process Concept3.1.1. The Process3.1.2. Process State3.1.3. Process Control Block3.1.4. Threads3.2. Process Scheduling3.2.1. Scheduling Queues3.2.2. Schedulers3.2.3. Context Switch3.3. Operations on Processes3.3.1. Process Creation3.3.2. Process Termination3.4. Interprocess Communication3.4.1. Shared-Memory Systems3.4.2. Message-Passing Systems3.4.2.1. Naming3.4.2.2. Synchronization3.4.2.3. Buffering3.5. Examples of IPC Systems3.5.1. An Example: POSIX Shared Memory3.5.2. An Example: Mach3.5.3. An Example: Windows3.6. Communication in Client–Server Systems3.6.1. Sockets3.6.2. Remote Procedure Calls3.7. Summary3.8. Practice Exercises3.9. Exercises3.10. Programming Problems3.11. Programming Projects3.11.1. POSIX Message Passing3.11.1.1. Part 1: Overview3.11.1.2. Part 2: The Message-Passing System3.11.1.3. Part 3: Creating the Processes3.11.1.4. Part 4: Implementation Hints3.12. Bibliographical Notes
4.1. Overview4.1.1. Motivation4.1.2. Benefits4.1.3. Multicore Programming4.2. Multithreading Models4.2.1. Many-to-One Model4.2.2. One-to-One Model4.2.3. Many-to-Many Model4.3. Thread Libraries4.3.1. Pthreads4.3.2. Win32 Threads4.3.3. Java Threads4.4. Threading Issues4.4.1. The fork() and exec() System Calls4.4.2. Cancellation4.4.3. Signal Handling4.4.4. Thread Pools4.4.5. Thread-Specific Data4.4.6. Scheduler Activations4.5. Operating-System Examples4.5.1. Windows Threads4.5.2. Linux Threads4.6. Summary4.7. Practice Exercises4.8. Exercises4.9. Programming Projects4.9.1. Project 1: Naming Service Project4.9.1.1. The Server4.9.1.2. The Client4.9.2. Project 2: Matrix Multiplication Project4.9.2.1. Passing Parameters to Each Thread4.9.2.2. Waiting for Threads to Complete4.10. Bibliographical Notes
5.1. Basic Concepts5.1.1. CPU–I/O Burst Cycle5.1.2. CPU Scheduler5.1.3. Preemptive Scheduling5.1.4. Dispatcher5.2. Scheduling Criteria5.3. Scheduling Algorithms5.3.1. First-Come, First-Served Scheduling5.3.2. Shortest-Job-First Scheduling5.3.3. Priority Scheduling5.3.4. Round-Robin Scheduling5.3.5. Multilevel Queue Scheduling5.3.6. Multilevel Feedback Queue Scheduling5.4. Thread Scheduling5.4.1. Contention Scope5.4.2. Pthread Scheduling5.5. Multiple-Processor Scheduling5.5.1. Approaches to Multiple-Processor Scheduling5.5.2. Processor Affinity5.5.3. Load Balancing5.5.4. Multicore Processors5.5.5. Virtualization and Scheduling5.6. Operating System Examples5.6.1. Example: Solaris Scheduling5.6.2. Example: Windows Scheduling5.6.3. Example: Linux Scheduling5.7. Algorithm Evaluation5.7.1. Deterministic Modeling5.7.2. Queueing Models5.7.3. Simulations5.7.4. Implementation5.8. Summary5.9. Practice Exercises5.10. Exercises5.11. Bibliographical Notes

6.1. Background6.2. The Critical-Section Problem6.3. Peterson's Solution6.4. Synchronization Hardware6.5. Semaphores6.5.1. Usage6.5.2. Implementation6.5.3. Deadlocks and Starvation6.5.4. Priority Inversion6.6. Classic Problems of Synchronization6.6.1. The Bounded-Buffer Problem6.6.2. The Readers–Writers Problem6.6.3. The Dining-Philosophers Problem6.7. Monitors6.7.1. Usage6.7.2. Dining-Philosophers Solution Using Monitors6.7.3. Implementing a Monitor Using Semaphores6.7.4. Resuming Processes Within a Monitor6.8. Synchronization Examples6.8.1. Synchronization in Solaris6.8.2. Synchronization in Windows XP6.8.3. Synchronization in Linux6.8.4. Synchronization in Pthreads6.9. Deadlocks6.9.1. System Model6.9.2. Deadlock Characterization6.9.3. Necessary Conditions6.9.4. Resource-Allocation Graph6.9.5. Methods for Handling Deadlocks6.10. Summary6.11. Practice Exercises6.12. Exercises6.13. Programming Problems6.14. Programming Projects6.14.1. Producer-Consumer Problem6.14.1.1. The Buffer6.14.1.2. Producer and Consumer Threads6.14.1.3. Pthreads Thread Creation6.14.1.4. Pthreads Mutex Locks6.14.1.5. Pthreads Semaphores6.14.1.6. Win326.14.1.7. Win32 Mutex Locks6.14.1.8. Win32 Semaphores6.15. Bibliographical Notes
7.1. Background7.1.1. Basic Hardware7.1.2. Address Binding7.1.3. Logical Versus Physical Address Space7.1.4. Dynamic Loading7.1.5. Dynamic Linking and Shared Libraries7.2. Swapping7.3. Contiguous Memory Allocation7.3.1. Memory Mapping and Protection7.3.2. Memory Allocation7.3.3. Fragmentation7.4. Paging7.4.1. Basic Method7.4.2. Hardware Support7.4.3. Protection7.4.4. Shared Pages7.5. Structure of the Page Table7.5.1. Hierarchical Paging7.5.2. Hashed Page Tables7.5.3. Inverted Page Table7.6. Segmentation7.6.1. Basic Method7.6.2. Hardware7.7. Example: The Intel Pentium7.7.1. Pentium Segmentation7.7.2. Pentium Paging7.7.3. Linux on Pentium Systems7.8. Summary7.9. Practice Exercises7.10. Exercises7.11. Programming Problems7.12. Bibliographical Notes
8.1. Background8.2. Demand Paging8.2.1. Basic Concepts8.2.2. Performance of Demand Paging8.3. Copy-on-Write8.4. Page Replacement8.4.1. Basic Page Replacement8.4.2. FIFO Page Replacement8.4.3. Optimal Page Replacement8.4.4. LRU Page Replacement8.4.5. LRU-Approximation Page Replacement8.4.5.1. Additional-Reference-Bits Algorithm8.4.5.2. Second-Chance Algorithm8.4.5.3. Enhanced Second-Chance Algorithm8.4.6. Counting-Based Page Replacement8.4.7. Page-Buffering Algorithms8.4.8. Applications and Page Replacement8.5. Allocation of Frames8.5.1. Minimum Number of Frames8.5.2. Allocation Algorithms8.5.3. Global Versus Local Allocation8.5.4. Non-Uniform Memory Access8.6. Thrashing8.6.1. Cause of Thrashing8.6.2. Working-Set Model8.6.3. Page-Fault Frequency8.7. Memory-Mapped Files8.7.1. Basic Mechanism8.7.2. Shared Memory in the Win32 API8.7.3. Memory-Mapped I/O8.8. Allocating Kernel Memory8.8.1. Buddy System8.8.2. Slab Allocation8.9. Other Considerations8.9.1. Prepaging8.9.2. Page Size8.9.3. TLB Reach8.9.4. Inverted Page Tables8.9.5. Program Structure8.9.6. I/O Interlock8.10. Operating-System Examples8.10.1. Windows8.10.2. Solaris8.11. Summary8.12. Practice Exercises8.13. Exercises8.14. Programming Problems8.15. Bibliographical Notes
9.1. File Concept9.1.1. File Attributes9.1.2. File Operations9.1.3. File Types9.1.4. File Structure9.1.5. Internal File Structure9.2. Access Methods9.2.1. Sequential Access9.2.2. Direct Access9.2.3. Other Access Methods9.3. Directory and Disk Structure9.3.1. Storage Structure9.3.2. Directory Overview9.3.3. Single-Level Directory9.3.4. Two-Level Directory9.3.5. Tree-Structured Directories9.3.6. Acyclic-Graph Directories9.3.7. General Graph Directory9.4. File-System Mounting9.5. File Sharing9.5.1. Multiple Users9.5.2. Remote File Systems9.5.2.1. The Client–Server Model9.5.2.2. Distributed Information Systems9.5.2.3. Failure Modes9.5.3. Consistency Semantics9.5.3.1. UNIX Semantics9.5.3.2. Session Semantics9.5.3.3. Immutable-Shared-Files Semantics9.6. Protection9.6.1. Types of Access9.6.2. Access Control9.6.3. Other Protection Approaches9.7. Summary9.8. Practice Exercises9.9. Exercises9.10. Bibliographical Notes
10.1. File-System Structure10.2. File-System Implementation10.2.1. Overview10.2.2. Partitions and Mounting10.2.3. Virtual File Systems10.3. Directory Implementation10.3.1. Linear List10.3.2. Hash Table10.4. Allocation Methods10.4.1. Contiguous Allocation10.4.2. Linked Allocation10.4.3. Indexed Allocation10.4.4. Performance10.5. Free-Space Management10.5.1. Bit Vector10.5.2. Linked List10.5.3. Grouping10.5.4. Counting10.5.5. Space Maps10.6. Efficiency and Performance10.6.1. Efficiency10.6.2. Performance10.7. Recovery10.7.1. Consistency Checking10.7.2. Log-Structured File Systems10.7.3. Other Solutions10.7.4. Backup and Restore10.8. Summary10.9. Practice Exercises10.10. Exercises10.11. Bibliographical Notes
11.1. Overview of Mass-Storage Structure11.1.1. Magnetic Disks11.1.2. Magnetic Tapes11.2. Disk Structure11.3. Disk Attachment11.3.1. Host-Attached Storage11.3.2. Network-Attached Storage11.3.3. Storage-Area Network11.4. Disk Scheduling11.4.1. FCFS Scheduling11.4.2. SSTF Scheduling11.4.3. SCAN Scheduling11.4.4. C-SCAN Scheduling11.4.5. LOOK Scheduling11.4.6. Selection of a Disk-Scheduling Algorithm11.5. Disk Management11.5.1. Disk Formatting11.5.2. Boot Block11.5.3. Bad Blocks11.6. Swap-Space Management11.6.1. Swap-Space Use11.6.2. Swap-Space Location11.6.3. Swap-Space Management: An Example11.7. RAID Structure11.7.1. Improvement of Reliability via Redundancy11.7.2. Improvement in Performance via Parallelism11.7.3. RAID Levels11.7.4. Problems with RAID11.8. Summary11.9. Practice Exercises11.10. Exercises11.11. Bibliographical Notes
12.1. Overview12.2. I/O Hardware12.2.1. Polling12.2.2. Interrupts12.2.3. Direct Memory Access12.2.4. I/O Hardware Summary12.3. Application I/O Interface12.3.1. Block and Character Devices12.3.2. Network Devices12.3.3. Clocks and Timers12.3.4. Blocking and Nonblocking I/O12.4. Kernel I/O Subsystem12.4.1. I/O Scheduling12.4.2. Buffering12.4.3. Caching12.4.4. Spooling and Device Reservation12.4.5. Error Handling12.4.6. I/O Protection12.4.7. Kernel Data Structures12.4.8. Kernel I/O Subsystem Summary12.5. Transforming I/O Requests to Hardware Operations12.6. STREAMS12.7. Performance12.8. Summary12.9. Practice Exercises12.10. Exercises12.11. Bibliographical Notes
13.1. Goals of Protection13.2. Principles of Protection13.3. Domain of Protection13.3.1. Domain Structure13.3.2. An Example: UNIX13.3.3. An Example: MULTICS13.4. Access Matrix13.5. Implementation of Access Matrix13.5.1. Global Table13.5.2. Access Lists for Objects13.5.3. Capability Lists for Domains13.5.4. A Lock-Key Mechanism13.5.5. Comparison13.6. Access Control13.7. Revocation of Access Rights13.8. Capability-Based Systems13.8.1. An Example: Hydra13.8.2. An Example: Cambridge CAP System13.9. Summary13.10. Practice Exercises13.11. Exercises13.12. Bibliographical Notes
14.1. The Security Problem14.2. Program Threats14.2.1. Trojan Horse14.2.2. Trap Door14.2.3. Logic Bomb14.2.4. Stack and Buffer Overflow14.2.5. Viruses14.3. System and Network Threats14.3.1. Worms14.3.2. Port Scanning14.3.3. Denial of Service14.4. Cryptography as a Security Tool14.4.1. Encryption14.4.1.1. Symmetric Encryption14.4.1.2. Asymmetric Encryption14.4.1.3. Authentication14.4.1.4. Key Distribution14.4.2. Implementation of Cryptography14.4.3. An Example: SSL14.5. User Authentication14.5.1. Passwords14.5.2. Password Vulnerabilities14.5.3. Encrypted Passwords14.5.4. One-Time Passwords14.5.5. Biometrics14.6. An Example: Windows14.7. Summary14.8. Exercises14.9. Bibliographical Notes
15.1. Linux History15.1.1. The Linux Kernel15.1.2. The Linux System15.1.3. Linux Distributions15.1.4. Linux Licensing15.2. Design Principles15.2.1. Components of a Linux System15.3. Kernel Modules15.3.1. Module Management15.3.2. Driver Registration15.3.3. Conflict Resolution15.4. Process Management15.4.1. The fork() and exec() Process Model15.4.1.1. Process Identity15.4.1.2. Process Environment15.4.1.3. Process Context15.4.2. Processes and Threads15.5. Scheduling15.5.1. Process Scheduling15.5.2. Kernel Synchronization15.5.3. Symmetric Multiprocessing15.6. Memory Management15.6.1. Management of Physical Memory15.6.2. Virtual Memory15.6.2.1. Virtual Memory Regions15.6.2.2. Lifetime of a Virtual Address Space15.6.2.3. Swapping and Paging15.6.2.4. Kernel Virtual Memory15.6.3. Execution and Loading of User Programs15.6.3.1. Mapping of Programs into Memory15.6.3.2. Static and Dynamic Linking15.7. File Systems15.7.1. The Virtual File System15.7.2. The Linux ext2fs File System15.7.3. Journaling15.7.4. The Linux Process File System15.8. Input and Output15.8.1. Block Devices15.8.2. Character Devices15.9. Interprocess Communication15.9.1. Synchronization and Signals15.9.2. Passing of Data Among Processes15.10. Network Structure15.11. Security15.11.1. Authentication15.11.2. Access Control15.12. Summary15.13. Practice Exercises15.14. Exercises15.15. Bibliographical Notes
16.1. History16.2. Design Principles16.2.1. Security16.2.2. Reliability16.2.3. Windows and POSIX Application Compatibility16.2.4. High Performance16.2.5. Extensibility16.2.6. Portability16.2.7. International Support16.2.8. Energy Efficiency16.2.9. Dynamic Device Support16.3. System Components16.3.1. Hardware-Abstraction Layer16.3.2. Kernel16.3.2.1. Kernel Dispatcher16.3.2.2. Threads and Scheduling16.3.2.3. Implementation of Synchronization Primitives16.3.2.4. Software Interrupts: Asynchronous and Deferred Procedure Calls16.3.2.5. Exceptions and Interrupts16.3.2.6. Switching Between User-Mode and Kernel-Mode Threads16.3.3. Executive16.3.3.1. Object Manager16.3.3.2. Virtual Memory Manager16.3.3.3. Process Manager16.3.3.4. Facilities for Client–Server Computing16.3.3.5. I/O Manager16.3.3.6. Cache Manager16.3.3.7. Security Reference Monitor16.3.3.8. Plug-and-Play Manager16.3.3.9. Power Manager16.3.3.10. Registry16.3.3.11. Booting16.4. Terminal Services and Fast User Switching16.5. File System16.5.1. NTFS Internal Layout16.5.1.1. NTFS B+ Tree16.5.1.2. NTFS Metadata16.5.2. Recovery16.5.3. Security16.5.4. Volume Management and Fault Tolerance16.5.4.1. RAID Sets16.5.4.2. Sector Sparing and Cluster Remapping16.5.5. Compression16.5.6. Mount Points, Symbolic Links, and Hard Links16.5.7. Change Journal16.5.8. Volume Shadow Copies16.6. Networking16.6.1. Network Interfaces16.6.2. Protocols16.6.2.1. Server-Message Block16.6.2.2. Transmission Control Protocol/Internet Protocol16.6.2.3. Point-to-Point Tunneling Protocol16.6.2.4. HTTP Protocol16.6.2.5. Web-Distributed Authoring and Versioning Protocol16.6.2.6. Named Pipes16.6.2.7. Remote Procedure Calls16.6.2.8. Component Object Model16.6.3. Redirectors and Servers16.6.3.1. Distributed File System16.6.3.2. Folder Redirection and Client-Side Caching16.6.4. Domains16.6.5. Active Directory16.7. Programmer Interface16.7.1. Access to Kernel Objects16.7.2. Sharing Objects between Processes16.7.3. Process Management16.7.3.1. Scheduling Rule16.7.3.2. Thread Priorities16.7.3.3. Thread Suspend and Resume16.7.3.4. Thread Synchronization16.7.3.5. Thread Pool16.7.3.6. Fibers16.7.3.7. User-Mode Scheduling (UMS) and ConcRT16.7.3.8. Winsock16.7.4. Interprocess Communication Using Windows Messaging16.7.5. Memory Management16.7.5.1. Virtual Memory16.7.5.2. Memory-Mapping Files16.7.5.3. Heaps16.7.5.4. Thread-Local Storage16.8. Summary16.9. Practice Exercises16.10. Exercises16.11. Bibliographical Notes

Content preview from Operating System Concepts Essentials

Part 6. Case Studies

We can now integrate the concepts described in this book by describing real operating systems. Two such systems are covered in great detail—Linux and Windows XP. We chose Linux for several reasons: It is popular, it is freely available, and it represents a full-featured UNIX system. This gives a student of operating systems an opportunity to read—and modify—real operating-system source code.

We also cover Windows XP in great detail. This recent operating system from Microsoft is gaining popularity, not only in the stand-alonemachine market, but also in the workgroup–server market. We chose Windows XP because it provides an opportunity for us to study a modern operating system that has a design and implementation drastically different from those of UNIX.

In addition, we briefly discuss other highly influential operating systems. We have chosen the order of presentation to highlight the similarities and differences among the systems; it is not strictly chronological and does not reflect the relative importance of the systems.

Finally, we provide on-line coverage of three other systems. The FreeBSD system is another UNIX system. However, whereas Linux combines features from several UNIX systems, FreeBSD is based on the BSD model of UNIX. FreeBSD source code, like Linux source code, is freely available. The Mach operating system is a modern operating system that provides compatibility with BSD UNIX. Windows is another modern operating system from Microsoft for Intel ...