1 INTRODUCTION1.1 WHAT IS AN OPERATING SYSTEM?1.1.1 The Operating System as an Extended Machine1.1.2 The Operating System as a Resource Manager1.2 HISTORY OF OPERATING SYSTEMS1.2.1 The First Generation1.2.2 The Second Generation1.2.3 The Third Generation1.2.4 The Fourth Generation1.3 COMPUTER HARDWARE REVIEW1.3.1 Processors1.3.2 Memory1.3.3 Disks1.3.4 Tapes1.3.5 I/O Devices1.3.6 Buses1.3.7 Booting the Computer1.4 THE OPERATING SYSTEM ZOO1.4.1 Mainframe Operating Systems1.4.2 Server Operating Systems1.4.3 Multiprocessor Operating Systems1.4.4 Personal Computer Operating Systems1.4.5 Handheld Computer Operating Systems1.4.6 Embedded Operating Systems.1.4.7 Sensor Node Operating Systems1.4.8 Real-Time Operating Systems1.4.9 Smart Card Operating Systems1.5 OPERATING SYSTEM CONCEPTS1.5.1 Processes1.5.2 Address Spaces1.5.3 Files1.5.4 Input/Output1.5.5 Protection1.5.6 The Shell1.5.7 Ontogeny Recapitulates Phylogeny1.6 SYSTEM CALLS1.6.1 System Calls for Process Management1.6.2 System Calls for File Management1.6.3 System Calls for Directory Management1.6.4 Miscellaneous System Calls1.6.5 The Windows Win32 API1.7 OPERATING SYSTEM STRUCTURE1.7.1 Monolithic Systems1.7.2 Layered Systems1.7.3 Microkernels1.7.4 Client-Server Model1.7.5 Virtual Machines1.7.6 Exokernels1.8 THE WORLD ACCORDING TO C1.8.1 The C Language1.8.2 Header Files1.8.3 Large Programming Projects1.8.4 The Model of Run Time1.9 RESEARCH ON OPERATING SYSTEMS1.10 OUTLINE OF THE REST OF THIS BOOK1.11 METRIC UNITS1.12 SUMMARY 2 PROCESSES AND THREADS2.1 PROCESSES2.1.1 The Process Model2.1.2 Process Creation2.1.3 Process Termination2.1.4 Process Hierarchies2.1.5 Process States2.1.6 Implementation of Processes2.1.7 Modeling Multiprogramming2.2 THREADS2.2.1 Thread Usage2.2.2 The Classical Thread Model2.2.3 POSIX Threads2.2.4 Implementing Threads in User Space2.2.5 Implementing Threads in the Kernel2.2.6 Hybrid Implementations2.2.7 Scheduler Activations2.2.8 Pop-Up Threads2.2.9 Making Single-Threaded Code Multithreaded2.3 INTERPROCESS COMMUNICATION2.3.1 Race Conditions2.3.2 Critical Regions2.3.3 Mutual Exclusion with Busy Waiting2.3.4 Sleep and Wakeup2.3.5 Semaphores2.3.6 Mutexes2.3.7 Monitors2.3.8 Message Passing2.3.9 Barriers2.4 SCHEDULING2.4.1 Introduction to Scheduling2.4.2 Scheduling in Batch Systems2.4.3 Scheduling in Interactive Systems2.4.4 Scheduling in Real-Time Systems2.4.5 Policy versus Mechanism2.4.6 Thread Scheduling2.5 CLASSICAL IPC PROBLEMS2.5.1 The Dining Philosophers Problem2.5.2 The Readers and Writers Problem2.6 RESEARCH ON PROCESSES AND THREADS2.7 SUMMARY 3 MEMORY MANAGEMENT3.1 NO MEMORY ABSTRACTION3.2 A MEMORY ABSTRACTION: ADDRESS SPACES3.2.1 The Notion of an Address Space3.2.2 Swapping3.2.3 Managing Free Memory3.3 VIRTUAL MEMORY3.3.1 Paging3.3.2 Page Tables3.3.3 Speeding Up Paging3.3.4 Page Tables for Large Memories3.4 PAGE LACEMENT ALGORITHMS3.4.1 The Optimal Page Replacement Algorithm3.4.2 The Not Recently Used Page Replacement Algorithm3.4.3 The First-In, First-Out3.4.4 The Second Chance Page Replacement Algorithm3.4.5 The Clock Page Replacement Algorithm3.4.6 The Least Recently Used3.4.7 Simulating LRU in Software3.4.8 The Working Set Page Replacement Algorithm3.4.9 The WSClock Page Replacement Algorithm3.4.10 Summary of Page Replacement Algorithms3.5 DESIGN ISSUES FOR PAGING SYSTEMS3.5.1 Local versus Global Allocation Policies3.5.2 Load Control3.5.3 Page Size3.5.4 Separate Instruction and Data Spaces3.5.5 Shared Pages3.5.6 Shared Libraries3.5.7 Mapped Files3.5.8 Cleaning Policy3.5.9 Virtual Memory Interface3.6 IMPLEMENTATION ISSUES3.6.1 Operating System Involvement with Paging3.6.2 Page Fault Handling3.6.3 Instruction Backup3.6.4 Locking Pages in Memory3.6.5 Backing Store3.6.6 Separation of Policy and Mechanism3.7 SEGMENTATION3.7.1 Implementation of Pure Segmentation3.7.2 Segmentation with Paging: MULTICS3.7.3 Segmentation with Paging: The Intel Pentium3.8 RESEARCH ON MEMORY MANAGEMENT3.9 SUMMARY 4 FILE SYSTEMS4.1 FILES4.1.1 File Naming4.1.2 File Structure4.1.3 File Types4.1.4 File Access4.1.5 File Attributes4.1.6 File Operations4.1.7 An Example Program Using File System Calls4.2 DIRECTORIES4.2.1 Single-Level Directory Systems4.2.2 Hierarchical Directory Systems4.2.3 Path Names4.2.4 Directory Operations4.3 FILE SYSTEM IMPLEMENTATION4.3.1 File System Layout4.3.2 Implementing Files4.3.3 Implementing Directories4.3.4 Shared Files4.3.5 Log-Structured File Systems4.3.6 Journaling File Systems4.3.7 Virtual File Systems4.4 FILE SYSTEM MANAGEMENT AND OPTIMIZATION4.4.1 Disk Space Management4.4.2 File System Backups4.4.3 File System Consistency4.4.4 File System Performance4.4.5 Defragmenting Disks4.5 EXAMPLE FILE SYSTEMS4.5.1 CD-ROM File Systems4.5.2 The MS-DOS File System4.5.3 The UNIX V7 File System4.6 RESEARCH ON FILE SYSTEMS4.7 SUMMARY 5 INPUT/OUTPUT5.1 PRINCIPLES OF I/O HARDWARE5.1.1 I/O Devices5.1.2 Device Controllers5.1.3 Memory-Mapped I/O5.1.4 Direct Memory Access5.1.5 Interrupts Revisited5.2 PRINCIPLES OF I/O SOFTWARE5.2.1 Goals of the I/O Software5.2.2 Programmed I/O5.2.3 Interrupt-Driven I/O5.2.4 I/O Using DMA5.3 I/O SOFTWARE LAYERS5.3.1 Interrupt Handlers5.3.2 Device Drivers5.3.3 Device-Independent I/O Software5.3.4 User-Space I/O Software5.4 DISKS5.4.1 Disk Hardware5.4.2 Disk Formatting5.4.3 Disk Arm Scheduling Algorithms5.4.4 Error Handling5.4.5 Stable Storage5.5 CLOCKS5.5.1 Clock Hardware5.5.2 Clock Software5.5.3 Soft Timers5.6 USER INTERFACES: KEYBOARD, MOUSE, MONITOR5.6.1 Input Software5.6.2 Output Software5.7 THIN CLIENTS5.8 POWER MANAGEMENT5.8.1 Hardware Issues5.8.2 Operating System Issues:5.8.3 Application Program Issues5.9 RESEARCH ON INPUT/OUTPUT5.10 SUMMARY 6 DEADLOCKS6.1 RESOURCES6.1.1 Preemptable and Nonpreemptable Resources6.1.2 Resource Acquisition6.2 INTRODUCTION TO DEADLOCKS6.2.1 Conditions for Resource Deadlocks6.2.2 Deadlock Modeling6.3 THE OSTRICH ALGORITHM6.4 DEADLOCK DETECTION AND RECOVERY6.4.1 Deadlock Detection with One Resource of Each Type6.4.2 Deadlock Detection with Multiple Resources of Each Type6.4.3 Recovery from Deadlock6.5 DEADLOCK AVOIDANCE6.5.1 Resource Trajectories6.5.2 Safe and Unsafe States6.5.3 The Banker's Algorithm for a Single Resource6.5.4 The Banker's Algorithm for Multiple Resources6.6 DEADLOCK PREVENTION6.6.1 Attacking the Mutual Exclusion Condition6.6.2 Attacking the Hold and Wait Condition6.6.3 Attacking the No Preemption Condition6.6.4 Attacking the Circular Wait Condition6.7 OTHER ISSUES6.7.1 Two-Phase Locking6.7.2 Communication Deadlocks6.7.3 Livelock6.7.4 Starvation6.8 RESEARCH ON DEADLOCKS6.9 SUMMARY 7 MULTIMEDIA OPERATING SYSTEMS7.1 INTRODUCTION TO MULTIMEDIA7.2 MULTIMEDIA FILES7.2.1 Video Encoding7.2.2 Audio Encoding7.3 VIDEO COMPRESSION7.3.1 The JPEG Standard7.3.2 The MPEG Standard7.4 AUDIO COMPRESSION7.5 MULTIMEDIA PROCESS SCHEDULING7.5.1 Scheduling Homogeneous Processes7.5.2 General Real-Time Scheduling7.5.3 Rate Monotonic Scheduling7.5.4 Earliest Deadline First Scheduling7.6 MULTIMEDIA FILE SYSTEM PARADIGMS7.6.1 VCR Control Functions7.6.2 Near Video on Demand7.6.3 Near Video on Demand with VCR Functions7.7 FILE PLACEMENT7.7.1 Placing a File on a Single Disk7.7.2 Two Alternative File Organization Strategies7.7.3 Placing Files for Near Video on Demand7.7.4 Placing Multiple Files on a Single Disk7.7.5 Placing Files on Multiple Disks7.8 CACHING7.8.1 Block Caching7.8.2 File Caching7.9 DISK SCHEDULING FOR MULTIMEDIA7.9.1 Static Disk Scheduling7.9.2 Dynamic Disk Scheduling7.10 RESEARCH ON MULTIMEDIA7.11 SUMMARY 8 MULTIPLE PROCESSOR SYSTEMS8.1 MULTIPROCESSORS8.1.1 Multiprocessor Hardware8.1.2 Multiprocessor Operating System Types8.1.3 Multiprocessor Synchronization8.1.4 Multiprocessor Scheduling8.2 MULTICOMPUTERS8.2.1 Multicomputer Hardware8.2.2 Low-Level Communication Software8.2.3 User-Level Communication Software8.2.4 Remote Procedure Call8.2.5 Distributed Shared Memory8.2.6 Multicomputer Scheduling8.2.7 Load Balancing8.3 VIRTUALIZATION8.3.1 Requirements for Virtualization8.3.2 Type 1 Hypervisors8.3.3 Type 2 Hypervisors8.3.4 Paravirtualization8.3.5 Memory Virtualization8.3.6 I/O Virtualization8.3.7 Virtual Appliances8.3.8 Virtual Machines on Multicore CPUs8.3.9 Licensing Issues8.4 DISTRIBUTED SYSTEMS8.4.1 Network Hardware8.4.2 Network Services and Protocols8.4.3 Document-Based Middleware8.4.4 File System-Based Middleware8.4.5 Object-Based Middleware8.4.6 Coordination-Based Middleware8.5 RESEARCH ON MULTIPLE PROCESSOR SYSTEMS8.6 SUMMARY 9 SECURITY9.1 THE SECURITY ENVIRONMENT9.1.1 Threats9.1.2 Intruders9.1.3 Accidental Data Loss9.2 BASICS OF CRYPTOGRAPHY9.2.1 Secret-Key Cryptography9.2.2 Public-Key Cryptography9.2.3 One-Way Functions9.2.4 Digital Signatures9.2.5 Trusted Platform Module9.3 PROTECTION MECHANISMS9.3.1 Protection Domains9.3.2 Access Control Lists9.3.3 Capabilities9.3.4 Trusted systems9.3.5 Trusted Computing Base9.3.6 Formal Models of Secure Systems9.3.7 Multilevel Security9.3.8 Covert Channels9.4 AUTHENTICATION9.4.1 Authentication Using Passwords9.4.2 Authentication Using a Physical Object9.4.3 Authentication Using Biometrics9.5 INSIDER ATTACKS9.5.1 Logic Bombs9.5.2 Trap Doors9.5.3 Login Spoofing9.6 EXPLOITING CODE BUGS9.6.1 Buffer Overflow Attacks9.6.2 Format String Attacks9.6.3 Return to libc Attacks9.6.4 Integer Overflow Attacks9.6.5 Code Injection Attacks9.6.6 Privilege Escalation Attacks9.7 MALWARE9.7.1 Trojan Horses9.7.2 Viruses9.7.3 Worms9.7.4 Spyware9.7.5 Rootkits9.8 DEFENSES9.8.1 Firewalls9.8.2 Antivirus and Anti-Antivirus Techniques9.8.3 Code Signing9.8.4 Jailing9.8.5 Model-Based Intrusion Detection9.8.6 Encapsulating Mobile Code9.8.7 Java Security9.9 RESEARCH ON SECURITY9.10 SUMMARY 10 CASE STUDY 1: LINUX10.1 HISTORY OF UNIX AND LINUX10.1.1 UNICS10.1.2 PDP-11 UNIX10.1.3 Portable UNIX10.1.4 Berkeley UNIX10.1.5 Standard UNIX10.1.6 MINIX10.1.7 Linux10.2 OVERVIEW OF LINUX10.2.1 Linux Goals10.2.2 Interfaces to Linux10.2.3 The Shell10.2.4 Linux Utility Programs10.2.5 Kernel Structure10.3 PROCESSES IN LINUX10.3.1 Fundamental Concepts10.3.2 Process Management System Calls in Linux10.3.3 Implementation of Processes and Threads in Linux10.3.4 Scheduling in Linux10.3.5 Booting Linux10.4 MEMORY MANAGEMENT IN LINUX10.4.1 Fundamental Concepts10.4.2 Memory Management System Calls in Linux10.4.3 Implementation of Memory Management in Linux10.4.4 Paging in Linux10.5 INPUT/OUTPUT IN LINUX10.5.1 Fundamental Concepts10.5.2 Networking10.5.3 Input/Output System Calls in Linux10.5.4 Implementation of Input/Output in Linux10.5.5 Modules in Linux10.6 THE LINUX FILE SYSTEM10.6.1 Fundamental Concepts10.6.2 File System Calls in Linux10.6.3 Implementation of the Linux File System10.6.4 NFS: The Network File System10.7 SECURITY IN LINUX10.7.1 Fundamental Concepts10.7.2 Security System Calls in Linux10.7.3 Implementation of Security in Linux10.8 SUMMARY 11 CASE STUDY 2: WINDOWS VISTA11.1 HISTORY OF WINDOWS VISTA11.1.1 1980s: MS-DOS11.1.2 1990s: MS-DOS-based Windows11.1.3 2000s: NT-based Windows11.1.4 Windows Vista11.2 PROGRAMMING WINDOWS VISTA11.2.1 The Native NT Application Programming Interface11.2.2 The Win32 Application Programming Interface11.2.3 The Windows Registry11.3 SYSTEM STRUCTURE11.3.1 Operating System Structure11.3.2 Booting Windows Vista11.3.3 Implementation of the Object Manager11.3.4 Subsystems, DLLs, and User-mode Services11.4 PROCESSES AND THREADS IN WINDOWS VISTA11.4.1 Fundamental Concepts11.4.2 Job, Process, Thread and Fiber Management API Calls11.4.3 Implementation of Processes and Threads11.5 MEMORY MANAGEMENT11.5.1 Fundamental Concepts11.5.2 Memory Management System Calls11.5.3 Implementation of Memory Management11.6 CACHING IN WINDOWS VISTA11.7 INPUT/OUTPUT IN WINDOWS VISTA11.7.1 Fundamental Concepts11.7.2 Input/Output API Calls11.7.3 Implementation of I/O11.8 THE WINDOWS NT FILE SYSTEM11.8.1 Fundamental Concepts11.8.2 Implementation of the NT File System11.9 SECURITY IN WINDOWS VISTA11.9.1 Fundamental Concepts11.9.2 Security API Calls11.9.3 Implementation of Security11.10 SUMMARY 12 CASE STUDY 3: SYMBIAN OS12.1 THE HISTORY OF SYMBIAN OS12.1.1 Symbian OS Roots: Psion and EPOC12.1.2 Symbian OS Version 612.1.3 Symbian OS Version 712.1.4 Symbian OS Today12.2 AN OVERVIEW OF SYMBIAN OS12.2.1 Object Orientation12.2.2 Microkernel Design12.2.3 The Symbian OS Nanokernel12.2.4 Client/Server Resource Access12.2.5 Features of a Larger Operating System12.2.6 Communication and Multimedia12.3 PROCESSES AND THREADS IN SYMBIAN OS12.3.1 Threads and Nanothreads12.3.2 Processes12.3.3 Active Objects12.3.4 Interprocess Communication12.4 MEMORY MANAGEMENT12.4.1 Systems with No Virtual Memory12.4.2 How Symbian OS Addresses Memory12.5 INPUT AND OUTPUT12.5.1 Device Drivers12.5.2 Kernel Extensions12.5.3 Direct Memory Access12.5.4 Special Case: Storage Media12.5.5 Blocking I/O12.5.6 Removable Media12.6 STORAGE SYSTEMS12.6.1 File systems for Mobile Devices12.6.2 Symbian OS File systems12.6.3 File system Security and Protection12.7 SECURITY IN SYMBIAN OS12.8 COMMUNICATION IN SYMBIAN OS12.8.1 Basic Infrastructure12.8.2 A Closer Look at the Infrastructure12.9 SUMMARY 13 OPERATING SYSTEMS DESIGN13.1 THE NATURE OF THE DESIGN PROBLEM13.1.1 Goals13.1.2 Why is it Hard to Design an Operating System?13.2 INTERFACE DESIGN13.2.1 Guiding Principles13.2.2 Paradigms13.2.3 The System Call Interface13.3 IMPLEMENTATION13.3.1 System Structure13.3.2 Mechanism versus Policy13.3.3 Orthogonality13.3.4 Naming13.3.5 Binding Time13.3.6 Static versus Dynamic Structures13.3.7 Top-Down versus Bottom-Up Implementation13.3.8 Useful Techniques13.4 PERFORMANCE13.4.1 Why Are Operating Systems Slow?13.4.2 What Should Be Optimized?13.4.3 Space-Time Trade-offs13.4.4 Caching13.4.5 Hints13.4.6 Exploiting Locality13.4.7 Optimize the Common Case13.5 PROJECT MANAGEMENT13.5.1 The Mythical Man Month13.5.2 Team Structure13.5.3 The Role of Experience13.5.4 No Silver Bullet13.6 TRENDS IN OPERATING SYSTEM DESIGN13.6.1 Virtualization13.6.2 Multicore Chips13.6.3 Large Address Space Operating Systems13.6.4 Networking13.6.5 Parallel and Distributed Systems13.6.6 Multimedia13.6.7 Battery-Powered Computers13.6.8 Embedded Systems13.6.9 Sensor Nodes13.7 SUMMARY 14 READING LIST AND BIBLIOGRAPHY14.1 SUGGESTIONS FOR FURTHER READING14.1.1 Introduction and General Works14.1.2 Processes and Threads14.1.3 Memory Management14.1.4 Input/Output14.1.5 File Systems14.1.6 eadlocks14.1.7 Multimedia Operating Systems14.1.8 Multiple Processor Systems14.1.9 ecurity14.1.10 Linux14.1.11 Windows Vista14.1.12 The Symbian OS14.1.13 Design Principles14.2 ALPHABETICAL BIBLIOGRAPHY INDEX