PRINCIPLES OF Operating Systems Naresh Chauhan Professor and Chairman Department of Computer Engineering YMCA University of Science and Technology, Faridabad 33 OOxxffoorrdd UUnniivveerrssiittyy PPrreessss iiss aa ddeeppaarrttmmeenntt ooff tthhee UUnniivveerrssiittyy ooff OOxxffoorrdd.. IItt ffuurrtthheerrss tthhee UUnniivveerrssiittyy’’ss oobbjjeeccttiivvee ooff eexxcceelllleennccee iinn rreesseeaarrcchh,, sscchhoollaarrsshhiipp,, aanndd eedduuccaattiioonn bbyy ppuubblliisshhiinngg wwoorrllddwwiiddee.. OOxxffoorrdd iiss aa rreeggiisstteerreedd ttrraaddee mmaarrkk ooff OOxxffoorrdd UUnniivveerrssiittyy PPrreessss iinn tthhee UUKK aanndd iinn cceerrttaaiinn ootthheerr ccoouunnttrriieess.. PPuubblliisshheedd iinn IInnddiiaa bbyy OOxxffoorrdd UUnniivveerrssiittyy PPrreessss YYMMCCAA LLiibbrraarryy BBuuiillddiinngg,, 11 JJaaii SSiinngghh RRooaadd,, NNeeww DDeellhhii 111100000011,, IInnddiiaa ©© OOxxffoorrdd UUnniivveerrssiittyy PPrreessss 22001144 TThhee mmoorraall rriigghhttss ooff tthhee aauutthhoorr//ss hhaavvee bbeeeenn aasssseerrtteedd.. FFiirrsstt ppuubblliisshheedd iinn 22001144 AAllll rriigghhttss rreesseerrvveedd.. NNoo ppaarrtt ooff tthhiiss ppuubblliiccaattiioonn mmaayy bbee rreepprroodduucceedd,, ssttoorreedd iinn aa rreettrriieevvaall ssyysstteemm,, oorr ttrraannssmmiitttteedd,, iinn aannyy ffoorrmm oorr bbyy aannyy mmeeaannss,, wwiitthhoouutt tthhee pprriioorr ppeerrmmiissssiioonn iinn wwrriittiinngg ooff OOxxffoorrdd UUnniivveerrssiittyy PPrreessss,, oorr aass eexxpprreessssllyy ppeerrmmiitttteedd bbyy llaaww,, bbyy lliicceennccee,, oorr uunnddeerr tteerrmmss aaggrreeeedd wwiitthh tthhee aapppprroopprriiaattee rreepprrooggrraapphhiiccss rriigghhttss oorrggaanniizzaattiioonn.. EEnnqquuiirriieess ccoonncceerrnniinngg rreepprroodduuccttiioonn oouuttssiiddee tthhee ssccooppee ooff tthhee aabboovvee sshhoouulldd bbee sseenntt ttoo tthhee RRiigghhttss DDeeppaarrttmmeenntt,, OOxxffoorrdd UUnniivveerrssiittyy PPrreessss,, aatt tthhee aaddddrreessss aabboovvee.. YYoouu mmuusstt nnoott cciirrccuullaattee tthhiiss wwoorrkk iinn aannyy ootthheerr ffoorrmm aanndd yyoouu mmuusstt iimmppoossee tthhiiss ssaammee ccoonnddiittiioonn oonn aannyy aaccqquuiirreerr.. IISSBBNN-1-133:: 997788--00-1-199--880088228877-3-3 IISSBBNN-1-100:: 00--1199-8-80088228877-8-8 TTyyppeesseett iinn TTiimmeess NNeeww RRoommaann bbyy MMuukkeesshh TTeecchhnnoollooggiieess PPvvtt. . LLttdd.,., PPuudduucchheerrrryy 660055000055 PPrriinntteedd iinn IInnddiiaa bbyy IInnddiiaa BBiinnddiinngg HHoouussee,, NNooiiddaa 220011330011 TThhiirrdd-p-paarrttyy wweebbssiittee aaddddrreesssseess mmeennttiioonneedd iinn tthhiiss bbooookk aarree pprroovviiddeedd bbyy OOxxffoorrdd UUnniivveerrssiittyy PPrreessss iinn ggoooodd ffaaiitthh aanndd ffoorr iinnffoorrmmaattiioonn oonnllyy.. OOxxffoorrdd UUnniivveerrssiittyy PPrreessss ddiissccllaaiimmss aannyy rreessppoonnssiibbiilliittyy ffoorr tthhee mmaatteerriiaall ccoonnttaaiinneedd tthheerreeiinn.. Dedicated to my wife, Anushree Chauhan and my loving children, Smiti and Atharv Preface An operating system is an interface through which we are able to access and operate the computer hardware. Thanks to the operating system, the user need not worry about hardware or interact with different devices. The operating system, therefore, works in the background without letting us know who is doing the job. It is the software through which all the hardware devices are managed and utilized. However, an operating system is much more than just that and encompasses a vast domain. One reason is that an operating system and computer architecture affect each other and co-evolve. Sometimes, the computer architecture has forced the operating systems to evolve, and sometimes the operating system demanded the architecture to change. This has given rise to the operating system concepts in the light of computer architecture. Another reason is that the technology has shifted from single-processor to multi-processor technology. This has given birth to so many operating systems, such as multi-processor, distributed, networked operating systems, and so on. Another development that we have seen in the last 15 years is the mobile technology. Today, we are living in the world of mobile devices. The mobile technology has bred various developments in mobile operating systems. Besides this, there is the world of embedded and real-time systems, which produced yet another category of operating systems—embedded and real- time operating systems. The list is endless! All these advances have made operating systems a subject of rich concepts and frequent changes in user applications and technology. About the Book This book has been written after reviewing the syllabi of various Indian universities and, therefore, provides a wide coverage of the subject—operating systems. The target readers of this book are undergraduate students of computer engineering and IT. The book will also be useful to postgraduate students of MCA and M.Tech. as it includes many chapters on specialized operating systems as well as several other advanced topics. Each chapter begins with the learning objectives and ends with a summary containing a quick review of important concepts discussed in the chapter. Each chapter provides plenty of solved examples in-between the text for a practical understanding of the method or technique. Multiple choice questions, review questions, and brain teasers provided at the end of each chapter will assist the teaching faculty to prepare their students for the examinations. The book covers every aspect of the subject. It describes the development of modern operating systems, explaining the evolution starting from the mainframe systems. Since operating system is con- sidered to be a concept-rich subject, this book has focused on each and every concept in depth and explained the same in a lucid manner. The book also covers the practical aspect of the subject, empha- sizing shell programming. It has a complete chapter on shell programming, which will help the students in the operating system laboratory. Case studies of four operating systems, namely, UNIX, Solaris, Linux, and Windows are presented at the end of Parts I-VI. The different features of various versions of each operating system are explained. In UNIX, version SVR4; in SOLARIS, version 10; in Linux, version 2.6; and in Windows, Windows XP are emphasized in the case studies. Key Features This book is packed with the following features: • Explains how the modern operating system has been developed and discusses different types of OSs and OS architectures Preface vii • Highlights the hardware issues necessary to understand operating system concepts • Contains dedicated chapters on specialized OSs such as distributed OSs, multi-processor OSs, real-time OSs, mobile OSs (including Android OS), and multimedia OSs • Covers every concept in depth and provides numerous solved examples interspersed within the text • Provides specially designed brain teasers at the end of each chapter for the students to develop an analytical approach to problem solving • Includes case studies of four OSs, namely, UNIX, Solaris, Linux, and Windows and two real- time OSs, VxWorks and QNX • Contains a separate chapter on shell programming that will be helpful for operating system laboratory Online Resources The following resources are available to help the faculty and the students using this text: For Faculty • Chapter-wise PowerPoint Slides For Students • Solved questions for competitive examinations • Practical exercises for OS laboratory Content and Coverage The book consists of 23 chapters divided into eight parts. A brief outline of each chapter is as follows: PART I Introduction Chapter 1 introduces operating systems and explains their goals and functions along with their types. Chapter 2 discusses the need of hardware support for OSs and explains the hardware components such as I/O devices, device controllers, magnetic disk, etc. It explains the interrupt-driven nature of OSs along with the hardware protection mechanisms to implement multi-programming or multi-tasking OSs. Chapter 3 explains how an operating system functions as a resource manager. Various resource types, along with the components of resource manager, are also discussed. Chapter 4 explains the general working of an operating system along with the coverage of various structures of an operating system. PART II Process Management Chapter 5 introduces the basic concepts related to process management along with discussion on pro- cess life cycle. Further, it explains the implementation of process with various data structures and mod- ules and various process operations. Chapter 6 discusses every detail of process scheduling. Types of schedulers and scheduling algorithms are dealt with in detail. Chapter 7 introduces the concept of synchronization of processes with the help of various methods. Solutions to some classical synchronization problems are also discussed. Chapter 8 introduces the problem of deadlock in multi-programming environment, explaining how to represent deadlock and various conditions responsible for it. It also explains how to deal with deadlocks. Chapter 9 introduces the concept of multi-threading and various thread types and its operations. viii Preface PART III Memory Management Chapter 10 introduces the concepts related to basic memory management and explains various con- cepts like memory allocation, paging, and segmentation. Chapter 11 explains the importance of virtual memory and its implementation using various methods. PART IV File Management Chapter 12 introduces the concept of files, and their types, attributes, and operations along with details of directories. Chapter 13 elucidates file system structure and its implementation, data structures, along with the details of various file operations, file allocation methods, and implementation of directories. PART V Input–Output Management Chapter 14 introduces types of I/O, explains various issues related to I/O management, and kernel I/O subsystem along with the life cycle of an I/O request. Chapter 15 introduces the need for disk scheduling and various concepts related to disk management. PART VI Security and Protection Chapter 16 mainly deals with security issues in operating systems and various types of attacks and threats. Chapter 17 explains the protection mechanisms in operating systems to tackle threats and attacks. PART VII Advanced Operating Systems Chapter 18 introduces distributed operating systems and its features. Chapter 19 introduces multi-processor operating systems and various related issues. Chapter 20 introduces real-time operating systems and explains various issues therein. The chapter contains case studies on VxWorks and QNX. Chapter 21 discusses mobile devices and mobile operating systems and explains various issues therein. A popular operating system, Android OS, is discussed in detail. Chapter 22 discusses the various concepts in multimedia operating systems. PART VIII Shell Programming Chapter 23 introduces various types of shells of UNIX operating systems and explains various structures used in shell programming along with some programming examples. The readers are requested to send their valuable suggestions, comments, and constructive criticism for further improvement of the book at [email protected]. Naresh Chauhan Brief Contents Features of the Book iv Preface vi Detailed Contents xi PART I Introduction 1 1. Introduction to Operating Systems 3 2. Hardware Support for Operating Systems 35 3. Resource Management 56 4. Operating System Architectures 68 Case Study I: History and Architecture of Operating Systems 89 PART II Process Management 101 5. Fundamentals of Process Management 103 6. Process Scheduling 133 7. Process Communication and Synchronization 178 8. Deadlocks 224 9. Multi-threading 251 Case Study II: Process Management in UNIX/Solaris/Linux/Windows 267 PART III Memory Management 289 10. Basic Memory Management 291 11. Virtual Memory 333 Case Study III: Memory Management in UNIX/Solaris/Linux/Windows 382 Part IV File Management 395 12. File Systems 397 13. File System Implementation 415 Case Study IV: File Management in UNIX/Solaris/Linux/Windows 438 PART V Input –Output Management 451 14. Basics of I/O Management 453 15. Disk Management 469 Case Study V: Input/Output Management in UNIX/Solaris/Linux/Windows 499 PART VI Security and Protection 507 16. Security Issues 509 17. Protection Mechanisms 524 Case Study VI: Protection Mechanisms in UNIX/Solaris/Linux/Windows 547 PART VII Advanced Operating Systems 551 18. Distributed Operating Systems 553 19. Multi-processor Operating Systems 583 20. Real-time Operating Systems 594 21. Mobile Operating Systems 614 22. Multimedia Operating Systems 630 PART VIII Shell Programming 637 23. Shell Programming and UNIX Shells 639 Bibliography 657 Index 665 Detailed Contents Features of the Book iv Preface vi Brief Contents x PART I Introduction 1 1. Introduction to Operating Systems 3 2.8.1 Multiple Modes of Operation 43 1.1 Introduction 3 2.8.2 Input–Output Protection 45 1.2 The Need for Operating Systems 4 2.8.3 Memory Protection 45 1.3 Evolution of Operating Systems 6 2.8.4 CPU Protection 47 1.3.1 First Generation 6 2.9 Input–Output Communication 1.3.2 Second Generation 7 Techniques 47 1.3.3 Third Generation 9 2.9.1 Programmed I/O 48 1.3.4 Fourth Generation 11 2.9.2 Interrupt-driven I/O 48 1.4 Types of Operating Systems 14 2.9.3 Input/Output Using DMA 49 1.4.1 Batch Processing Systems 15 2.10 Magnetic Disks 49 1.4.2 Multi-programming Systems 15 2.10.1 Disk Formatting 51 1.4.3 Multi-user Time-sharing Systems 16 2.10.2 Disk Partitioning 52 1.4.4 Multi-tasking Systems 18 1.4.5 Network Operating Systems 19 3. Resource Management 56 1.4.6 Multi-processor Operating 3.1 Introduction 56 Systems 20 3.2 Functions of a Resource Manager 56 1.4.7 Distributed Operating Systems 20 3.2.1 Resource Abstraction/ 1.4.8 Real-time Operating Systems 21 Transformation 56 1.4.9 Embedded Operating Systems 22 3.2.2 Resource Sharing/Multiplexing 57 1.5 Goals of an Operating System 25 3.2.3 Resource Scheduling 57 1.6 Functions of Operating System 27 3.3 Resource Types 58 1.6.1 User View 27 3.3.1 Nature of Resources 59 1.6.2 System View 28 3.4 Goals of Resource Management 60 1.7 Operating System’s Generic 3.5 How Resource Manager Works? 61 Components 30 3.6 Components of Resource Management 62 3.6.1 Process/task Management 62 2. Hardware Support for 3.6.2 Memory Management 63 Operating Systems 35 3.6.3 Secondary Storage Management 64 2.1 Introduction 35 3.6.4 File Management 64 2.2 Interrupt-driven Operation for Operating 3.6.5 I nput–Output Management 65 System 35 3.6.6 Security and Protection 65 2.2.1 Types of Interrupts 37 2.2.2 Multiple Interrupts Handling 38 4. Operating System Architectures 68 2.3 Input–Output Devices 38 2.3.1 Timers or Clocks 39 4.1 Introduction 68 2.4 Device Controllers 40 4.2 General Working of an Operating 2.5 Device Driver 41 System 68 2.6 Problems in the Design of Modern OSs 42 4.2.1 BIOS 68 2.7 Need for Protection 43 4.2.2 Booting/Bootstrapping 69 2.8 Hardware Protection for 4.2.3 Boot Software/Boot Loader/Bootstrap Multi-programming/ Loader 69 Multi-tasking 43 4.2.4 Boot Device 69 xii Detailed Contents 4.2.5 Privileged Instructions 69 4.7 Monolithic Architecture 78 4.2.6 System Call 69 4.8 Layered Architecture 79 4.3 System Calls 71 4.8.1 Grouping of Functions in a 4.3.1 Making a System Call 72 Layer 79 4.3.2 Executing the System Call 72 4.8.2 Hierarchy of Layers 80 4.3.3 Types of System Calls 74 4.9 Virtual Machine OS 81 4.4 System Programs 76 4.10 Client–Server or Microkernel-based OS 83 4.5 System Generation Programs 76 4.11 ExoKernel 84 4.6 General Structure of OS 77 4.12 Hybrid Kernel-based OS 86 Case Study I: History and Architecture of Operating Systems 89 PART II Process Management 101 5. Fundamentals of Process 6.5 Scheduling Types 139 Management 103 6.6 Process-scheduling Goals 140 6.6.1 User-based Scheduling Goals 141 5.1 Introduction 103 6.6.2 System-based Scheduling 5.2 Terminology 103 Goals 142 5.3 Implicit/System and Non-implicit/User 6.7 Scheduling Algorithms 143 Processes 105 6.7.1 First Come First Served (FCFS) 143 5.4 Relationship Between Processes 106 6.7.2 Priority Scheduling 145 5.5 Life Cycle of a Process 106 6.7.3 Round Robin Scheduling 152 5.5.1 Process States and State 6.7.4 Improved Round Robin Transitions 107 Scheduling 156 5.5.2 Suspended Processes and Their 6.7.5 Highest Response Ratio Next (HRRN) State Transitions 111 Scheduling 158 5.6 Process Control Block 114 6.7.6 Virtual Round Robin 5.7 Implementation of Processes 115 Scheduling 163 5.8 Context Switching 118 6.7.7 Multi-level Queue Scheduling 166 5.9 Process Switching 119 6.7.8 Multi-level Feedback/Adaptive Queue 5.10 Schedulers 123 Scheduling 168 5.10.1 Long-term Scheduler 123 6.7.9 Fair-share Scheduling 169 5.10.2 Short-term Scheduler 123 6.7.10 Lottery Scheduling 171 5.10.3 Medium-term Scheduler 124 5.11 Process Operations 124 5.11.1 Creation 125 7. Process Communication 5.11.2 Dispatching 126 and Synchronization 178 5.11.3 Blocking/Wakeup 126 7.1 Introduction 178 5.11.4 Termination 126 7.2 Concurrent Processes 178 7.2.1 Data Access Synchronization 178 6. Process Scheduling 133 7.2.2 Control Synchronization 180 6.1 Introduction 133 7.2.3 Process Communication 182 6.2 P rocess Behaviour for Scheduling 133 7.2.4 Deadlocks 183 6.3 Scheduling Decision 134 7.3 Critical Section (CS) 184 6.4 Scheduling Levels 136 7.4 Algorithmic Approach to CS 6.4.1 Long-term Scheduling 136 Implementation 186 6.4.2 Medium-term 7.4.1 Two-process Solution 186 Scheduling 137 7.4.2 Dekker’s Solution 188 6.4.3 Short-term Scheduling 138 7.4.3 Peterson’s Solution 189