Bibliographic record and links to related information available from the Library of Congress catalog.
Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.
CONTENTS Preface xix 1 Basic Concepts of Operating Systems 1 1.1 Introduction 1 1.2 Computer Systems 1 1.2.1 Hardware Components 2 1.2.1.1 Processor 2 1.2.1.2 Main Memory 3 1.2.1.3 Storage Devices 3 1.2.1.4 Input Devices 4 1.2.1.5 Output Devices 4 1.2.1.6 Bus 4 1.2.2 Computer Networks 4 1.2.3 Interrupts 5 1.2.4 Software Components 6 1.3 Operating Systems 7 1.3.1 Operating System Interfaces 8 1.3.2 Abstract Views of an Operating System 9 1.3.2.1 External View of an Operating System 9 1.3.2.2 Internal View of an Operating System 10 1.4 Categories of Operating Systems 12 1.5 Brief History of Operating Systems 13 1.6 Contemporary Operating Systems 15 1.6.1 Unix 15 1.6.2 Microsoft Windows 15 1.7 Summary 16 v vi Principles of Modern Operating Systems 1.8 Exercises and Questions 17 2 Processes and Threads 19 2.1 Introduction 19 2.2 Processes 19 2.2.1 Process States 20 2.2.2 Process Descriptor 22 2.3 Threads 23 2.3.1 Multithreading 23 2.3.2 User-Level Threads 25 2.3.3 Kernel-Level Threads 25 2.4 Multiprogramming 26 2.4.1 CPU and I/O Requests 26 2.4.2 Interrupting Processes 27 2.4.3 Context Switch 28 2.5 Summary 28 2.6 Exercises and Questions 29 3 System Performance and Models 31 3.1 Introduction 31 3.2 Simple Models of Computer Systems 32 3.3 Performance of Computer Systems 34 3.3.1 Performance Metrics 34 3.3.2 Workload and System Parameters 36 3.4 Simulation Models 37 3.4.1 Types of Simulation Models 38 3.4.2 Discrete-event Models 38 3.4.3 Stochastic Models 39 3.5 A Model of the Simple Batch System 40 3.5.1 Description of the Model 40 3.5.2 Implementations of the Model 41 3.5.3 Simulation Output of the Console Implementation 43 3.5.4 Output of the GUI Implementation 46 3.6 System Capacity and Bottleneck 47 3.7 Summary 48 3.8 Exercises and Questions 49 4 Systems with Multiprogramming 51 Principles of Modern Operating Systems vii 4.1 Introduction 51 4.2 Systems with Multiple Stations 51 4.2.1 CPU and I/O bursts 53 4.2.2 Overlapping of CPU and I/O Processing 53 4.2.3 Context Switches 54 4.3 Studying Systems with Multiprogramming 54 4.3.1 Model of a System with Multiprogramming 54 4.3.2 Model of a System with No Multiprogramming 58 4.3.3 Comparison of the Two Models 60 4.3.4 Models with GUI and Graphical Animation 61 4.4 Summary 63 4.5 Exercises and Questions 64 5 CPU Scheduling 67 5.1 Introduction 67 5.2 General Types of Scheduling 68 5.3 CPU Scheduling Concepts 68 5.3.1 The CPU Scheduler 69 5.3.2 Scheduling Multiple Classes of Processes 70 5.4 CPU Scheduling Policies 71 5.4.1 First-Come-First-Served 72 5.4.1.1 Simple Analysis with FCFS 72 5.4.1.2 Simulation Model with FCFS Scheduling 76 5.4.2 Shortest Process Next 81 5.4.2.1 Simple Analysis with SPN 82 5.4.2.2 Simulation Model For SPN Scheduling 84 5.4.3 Round Robin Scheduling 88 5.4.3.1 Simple Analysis with RR 90 5.4.3.2 Simulation Model For RR Scheduling 92 5.4.4 Shortest Remaining Time 98 5.4.4.1 Simple Analysis with SRT 99 5.4.4.2 Simulation Model For SRT Scheduling 100 5.4.5 Brief Comparison of the Four Scheduling Policies 105 5.4.6 Dynamic Priority Scheduling 106 5.4.7 Other Scheduling Policies 107 5.4.7.1 Longest Process Next 107 5.4.7.2 Real-Time Scheduling Policies 108 5.5 Multilevel Queues and Multiple Processors 108 viii Principles of Modern Operating Systems 5.6 Summary 110 5.7 Exercises and Questions 111 6 Synchronization Principles 115 6.1 Introduction 115 6.2 Basic Synchronization Principles 116 6.2.1 No Synchronization 116 6.2.2 Mutual Exclusion 116 6.2.3 Critical Sections 117 6.3 Approaches for Implementing Synchronization 118 6.4 Semaphores 118 6.5 Synchronization with Semaphores 120 6.5.1 Critical Section Problem 120 6.5.2 Event Ordering 121 6.6 Synchronization Case Studies 122 6.6.1 The Bounded-Bu®er Problem 122 6.6.2 Synchronization with Semaphores in Java 125 6.6.3 Simulation Models for the Bounded Bu®er Problem 127 6.6.4 The Readers-Writers Problem 132 6.6.4.1 Description of the Problem 132 6.6.4.2 Simulation Models of the Readers Writers Problem 134 6.7 Monitors 138 6.7.1 Synchronization with Monitors 139 6.7.2 The Producer-Consumer Problem with a Monitor 139 6.7.3 Monitor Synchronization with Java 140 6.7.4 Simulation Models Using Monitors 142 6.8 Interprocess Communication (IPC) 144 6.8.1 Asynchronous Communication 144 6.8.2 Simulation Model for Asynchronous Communication 146 6.8.3 Synchronous Communication 148 6.8.4 Simulation Model for Synchronous Communication 149 6.9 Atomic Transactions 152 6.10 Summary 154 6.11 Exercises and Questions 155 7 Deadlocks 157 7.1 Introduction 157 Principles of Modern Operating Systems ix 7.2 Basic Principles of Deadlock 158 7.2.1 Resource Allocation Graph 159 7.2.2 Conditions for the Existence of Deadlock 159 7.3 The Five Dining Philosophers 163 7.3.1 Modeling Deadlock 164 7.3.2 Informal Solution to Deadlock 167 7.4 Methods for Handling Deadlock 170 7.5 Deadlock Prevention 171 7.5.1 Disallowing Hold and Wait 171 7.5.2 Disallowing Circular Wait 176 7.5.3 Model with Graphical Animation 180 7.6 Deadlock Avoidance 182 7.6.1 Banker's Algorithm 182 7.6.2 Applying Banker's Algorithm 184 7.6.3 Simulation Model with Banker's Algorithm 185 7.6.3.1 The GUI Interface 186 7.6.3.2 Input of Maximum Claims 186 7.6.3.3 Entering Current Allocation 186 7.6.3.4 Displaying Data 188 7.6.3.5 Model Structure 188 7.7 Deadlock Detection and Recovery 191 7.7.1 Deadlock Detection 191 7.7.2 Recovery 192 7.7.2.1 Aborting Processes 192 7.7.2.2 Rollback 192 7.8 Summary 193 7.9 Exercises and Questions 193 8 File Management 195 8.1 Introduction 195 8.2 Files 195 8.2.1 File Attributes 196 8.2.2 Folders 197 8.2.3 Pathnames 198 8.3 Access Methods 199 8.3.1 Open 200 8.3.2 Close 201 8.3.3 Read 201 x Principles of Modern Operating Systems 8.3.4 Write 202 8.3.5 Sequential Access 203 8.3.6 Streams, Pipes, and I/O Redirection 203 8.3.7 Other I/O System Calls 205 8.4 Directory Functions 205 8.5 File Space Allocation 206 8.5.1 Cluster Allocation 206 8.5.2 Calculating Read/Write Addresses 207 8.5.3 Free Space Management 208 8.5.4 Disk Fragmentation 209 8.5.5 Reliability of Disk Space Management 210 8.6 Real World Systems 211 8.6.1 Microsoft FAT System 212 8.6.2 Microsoft NTFS System 214 8.6.3 Linux ext2 and ext3 Systems 214 8.6.4 Other File Systems 215 8.7 Virtual File System 216 8.8 Removable Media 217 8.9 The Future is Now 219 8.10 Summary 219 8.11 Exercises and Questions 220 9 The I/O System 221 9.1 Introduction 221 9.2 I/O Hardware 221 9.2.1 Direct Memory Access (DMA) 223 9.2.2 Disk Drives 224 9.3 Device I/O 226 9.3.1 Intelligent Buses 228 9.3.2 Handling Multiple Devices Simultaneously 229 9.4 I/O Performance Optimization 230 9.4.1 Reducing the Number of I/O Requests 233 9.4.2 Bu®ering and Caching 233 9.4.3 I/O Scheduling 236 9.5 Disk I/O Scheduling 236 9.5.1 First-Come First-Serve (FCFS) 237 9.5.2 Shortest Seek Time First (SSTF) 237 9.5.3 Elevator (SCAN) 238 Principles of Modern Operating Systems xi 9.5.4 Circular Scan 239 9.5.5 Optimizing Rotational Latency 239 9.5.6 Interaction of Disk Scheduling and Other System Functions 239 9.6 System Con¯guration 240 9.7 Disk Scheduling Simulation Model 241 9.8 Summary 244 9.9 Exercises and Questions 245 10 Memory Management 247 10.1 Introduction 247 10.2 Process Address Space 248 10.2.1 Binding 249 10.2.2 Static and Dynamic Loading 250 10.2.3 Static and Dynamic Linking 250 10.3 Contiguous Memory Allocation 250 10.3.1 Fixed Partitions 251 10.3.2 Dynamic Partitions 252 10.3.3 Swapping 255 10.4 Non-contiguous Memory Allocation 256 10.4.1 Paging 256 10.4.1.1 Logical Addresses 257 10.4.1.2 Address Translation 258 10.4.2 Segmentation 259 10.5 Virtual Memory 260 10.5.1 Basic Concepts 261 10.5.2 Process Locality 262 10.5.3 Using Segments 262 10.5.4 Memory Protection 263 10.5.5 Shared Memory 263 10.5.6 Address Translation 264 10.5.7 Page Size Considerations 265 10.6 Paging With Virtual Memory 266 10.6.1 Paging Policies 266 10.6.1.1 Fetch Policy 266 10.6.1.2 Replacement Policy 267 10.6.2 Frame Allocation 268 10.6.3 Page Faults and Performance Issues 269 xii Principles of Modern Operating Systems 10.7 Paging Algorithms 269 10.7.1 Static Paging Algorithms 270 10.7.1.1 FIFO Algorithm 270 10.7.1.2 Simulation Model with FIFO 271 10.7.1.3 Optimal Algorithm 275 10.7.1.4 Simulation Model with Optimal Algorithm 277 10.7.1.5 Least Recently Used (LRU) 281 10.7.1.6 Simulation Model with LRU 282 10.7.2 Dynamic Paging Algorithms 287 10.7.2.1 The Working Set Algorithm 287 10.7.2.2 Simulation Model of the Working Set Algorithm 288 10.7.2.3 The Page Fault Frequency 292 10.8 Thrashing 292 10.8.1 Combining Paging with Segmentation 293 10.9 Summary 293 10.10 Exercises and Questions 295 11 Security and Protection 297 11.1 Introduction 297 11.2 Problems of Security 298 11.3 Security and Protection Components 299 11.3.1 Physical Security 299 11.3.2 User Authentication 299 11.3.3 Protection 300 11.3.3.1 Domains on Unix/Linux 301 11.3.3.2 Domains on Microsoft Windows 302 11.3.3.3 The Access Matrix 302 11.3.3.4 Memory Protection 303 11.3.3.5 Capabilities and Higher Level Protection 304 11.3.4 Secure Communications 307 11.3.5 Digital Certi¯cates 308 11.3.6 People 310 11.3.7 Using Components 311 11.4 System Vulnerabilities 311 11.4.1 Social Engineering 311 11.4.2 Trojan Horse Programs 311 11.4.3 Spyware 312 Principles of Modern Operating Systems xiii 11.4.4 Trap Doors 312 11.4.5 Database Access Vulnerabilities 312 11.4.6 Bu®er and Stack Over°ow 313 11.5 Invasive and Malicious Software 313 11.6 Defending the System and the User 314 11.7 Intrusion Detection Management 315 11.8 Security and Privacy 316 11.9 Secure Systems vs. Systems Security 316 11.10 Summary 317 11.11 Exercises and Questions 318 12 Firewalls and Network Security 321 12.1 Introduction 321 12.2 Motivation 321 12.3 The TCP/IP Communication Protocol 322 12.4 The Medium of Internet Communication 322 12.5 Packets, the OSI protocol stack, Firewalls 323 12.5.1 Packets 323 12.5.2 Open Systems Interconnection (OSI) Stack 323 12.5.3 Firewalls 324 12.6 Attack and Defense Scenarios 325 12.7 The Modeling 327 12.8 Inter-process Socket Communication 328 12.9 Distributed File System WallsOfFire Software 330 12.10 External Attack and Defense Scenarios 333 12.11 Summary 334 12.12 Exercises and Questions 334 Appendix A: Introduction to Using Linux 337 A.1 Introduction 337 A.2 Command Line Interface 338 A.3 Files and Directories 339 A.3.1 Specifying Paths 339 A.3.2 Wildcards 340 A.4 Basic Commands 340 A.4.1 The passwd Command 340 A.4.2 The man Command 341 A.4.3 The ls Command 341 xiv Principles of Modern Operating Systems A.4.4 The cp Command 342 A.4.5 The mv Command 343 A.4.6 The rm Command 344 A.4.7 The cd Command 344 A.4.8 The mkdir Command 345 A.4.9 The rmdir Command 345 A.4.10 I/O Re-Direction and Pipe Operators 345 A.5 Shell Variables 347 A.5.1 The pwd Command 348 A.5.2 The more Command 348 A.5.3 The exit Command 349 A.6 Text Editing 349 A.7 File Access Permissions 350 A.8 Chaining Files 351 A.9 Commands for Process Control 351 A.10 Foreground and Background Processes 353 A.11 Script Files 353 A.11.1 Comments in Scripts 354 A.11.2 Positional Parameters 354 A.11.3 Command Substitution 354 A.11.4 The test Command 354 A.11.5 The if with the test Commands 355 A.11.6 The set Command 357 A.11.7 Muti-branch with the if Command 358 A.11.8 Repetition with for Command 359 A.11.9 Repetition with the while Command 360 A.12 Searching Data in Files 360 A.13 Evaluating Expressions 362 A.14 Connecting to a Remote Linux Server 363 A.14.1 The Putty Program 364 A.14.2 SSH Client 365 A.14.3 X-Window and Graphical Desktops 367 A.14.4 Using the K Desktop Environment 369 Appendix B: Java and Posix Threads 371 B.1 Introduction 371 B.2 Threads 371 B.3 Object-Oriented Concepts and Threads in Java 372 Principles of Modern Operating Systems xv B.3.1 Inheritance 373 B.3.1.1 Base and derived classes 373 B.3.1.2 Constructors of the Subclasses 374 B.3.2 Abstract Classes 374 B.3.3 Polymorphism 375 B.3.4 Classes and Interfaces 375 B.3.5 Exceptions 376 B.3.6 Java Threads 377 B.3.6.1 Using Threads 377 B.3.6.2 Inheriting the Thread Class 378 B.3.6.3 Other Basic Thread Methods 379 B.3.6.4 Thread Suspending Itself 380 B.3.6.5 Implementing the Runnable Interface 380 B.3.6.6 Interrupting a Thread Object 381 B.3.6.7 Thread Priorities in Java 383 B.3.6.8 Simple Thread Synchronization 383 B.3.6.9 Wait/Notify Mechanism in Threads 384 B.4 POSIX Threads 385 B.4.1 Creating POSIX Threads 385 B.4.2 Basic Synchronization of Pthreads 386 B.4.2.1 Wait for Termination 386 B.4.2.2 Termination of a Thread 387 B.4.3 Mutual Exclusion 387 B.4.4 Semaphores 388 B.4.4.1 Initializing Semaphores 388 B.4.4.2 Decrementing and Incrementing Semaphores 389 B.4.4.3 Destroying Semaphores 389 B.4.5 Conditions Variables 389 B.4.6 Scheduling and Priorities of POSIX Threads 391 B.5 Summary 392 Appendix C: The Java Modeling Framework 393 C.1 Introduction 393 C.2 Basic Structure of a Model 394 C.2.1 Simulation Model 394 C.2.2 Input Parameters 394 C.2.3 Class Input 395 C.2.4 Class UI 395 xvi Principles of Modern Operating Systems C.2.5 Processes 395 C.2.6 RequestProcessor 397 C.2.7 Request 397 C.2.8 Schedular 397 C.2.9 IncomingRequestGenerator Class 401 C.2.10 ResourceManager 401 C.2.11 Output Class 402 C.2.12 Simulation Display 402 C.2.13 Plotter 402 C.2.14 Qplotter 404 C.2.15 Animation 404 C.2.16 QGraphic 405 C.2.17 SchedularGraphic 405 C.2.18 Random Number Generator Classes 406 C.2.18.1 Randint Class 406 C.2.18.2 Erand Class 406 C.2.18.3 Normal Class 407 C.2.18.4 Poisson Class 407 C.2.18.5 Urand Class 407 C.2.19 Statistic Class 407 C.3 Java Coding Recommendations 409 C.4 The Simulation Package on CD-ROM 412 C.4.1 Files on the CD-ROM 412 C.4.2 Compiling with Java and the PsimJ Library 412 C.4.3 Example Program 412 Appendix D: Psim3 435 D.1 The Psim3 Library 435 D.1.1 The Time Dimension 435 D.1.2 De¯ning Active Objects 436 D.1.3 Running a Simulation 436 D.1.4 Features in Class process 437 D.1.4.1 Name of an Active Object 438 D.1.4.2 The Simulation Clock 438 D.1.4.3 Priority of an Active Object 438 D.1.4.4 States of an Active Object 439 D.1.5 Scheduling a Process 440 D.1.6 Suspending a Process 440 Principles of Modern Operating Systems xvii D.1.7 Interrupting a Process 440 D.1.8 Terminating a Process 441 D.2 The Queue Library 442 D.2.1 General Description 442 D.2.2 Features of Class squeue 442 D.2.3 Features of Class pqueue 444 D.3 The Resource Library 447 D.3.1 General Description 447 D.3.2 Relevant Features of the res Class 448 D.3.3 Features in Class bin 449 D.4 The waitq Class 450 D.5 The condq Class 451 D.6 Random Numbers 453 D.6.1 Class randint 454 D.6.2 Class erand 455 D.6.3 Class normal 456 D.6.4 Class poisson 457 D.6.5 Class urand 458 D.7 The Simulation Package on CD-ROM 459 D.7.1 Files on the CD-ROM 459 D.7.2 Brief Instructions for Compiling and Linking 459 Appendix E: Overview of Probability Theory 461 E.1 Introduction 461 E.2 Basic Concepts 461 E.3 Probability of an Event 462 E.4 Random Numbers 463 E.5 Probability Distribution Functions 465 E.5.1 The Geometric Distribution 467 E.5.2 The Binomial Distribution 468 E.5.3 The Exponential Distribution 468 E.5.4 The Poisson Distribution 469 E.5.5 The Uniform Distribution 470 E.5.6 The Normal Distribution 470 E.6 Statistics 470 E.7 Analyzing Sample Data 472 E.8 State-dependent Models 472 E.8.1 State Dependence 473 xviii Principles of Modern Operating Systems E.8.2 Stochastic Matrices 473 Appendix F: Using the C++ Models 475 F.1 Using Linux 475 F.2 Using Unix (Sun Solaris) 477 F.3 Using Microsoft Windows 477 Appendix G: Bibliography 479 Index 481
Library of Congress Subject Headings for this publication:
Operating systems (Computers).