Operating System Second Edition

Rohit Khurana

Operating System Second Edition

This Page has been intentionally left blank

Operating System Second Edition

Rohit Khurana Founder and CEO ITLESL, Delhi

VIKAS® PUBLISHING HOUSE PVT LTD

VIKAS® PUBLISHING HOUSE PVT LTD E-28, Sector-8, Noida-201301 (UP) India Phone: +91-120-4078900 • Fax: +91-120-4078999 Registered Office: 576, Masjid Road, Jangpura, New Delhi-110014. India • Website: www.vikaspublishing.com • Ahmedabad : 305, Grand Monarch, 100 ft Shyamal Road, Near Seema Hall, Ahmedabad-380051 • Ph. +91-79-65254204, +91-9898294208 • Bengaluru : First Floor, N S Bhawan, 4th Cross, 4th Main, Gandhi Nagar, Bengaluru-560009 • Ph. +91-80-22281254, 22204639 • Chennai : E-12, Nelson Chambers, 115, Nelson Manickam Road, Aminjikarai, Chennai-600029 • Ph. +91-44-23744547, 23746090 • Hyderabad : Aashray Mansion, Flat-G (G.F.), 3-6-361/8, Street No. 20, Himayath Nagar, Hyderabad-500029 • Ph. +91-40-23269992 • Fax. +91-40-23269993 • Kolkata : 82, Park Street, Kolkata-700017 • Ph. +91-33-22837880 • Mumbai : 67/68, 3rd Floor, Aditya Industrial Estate, Chincholi Bunder, Behind Balaji International School & Evershine Mall, Malad (West), Mumbai-400064 • Ph. +91-22-28772545, 28768301 • Patna : Flat No. 101, Sri Ram Tower, Beside Chiraiyatand Over Bridge, Kankarbagh Main Rd., Kankarbagh, Patna-800020 • Ph. +91-612-2351147

E-mail: [email protected]

Operating System ISBN: 978-93259-7563-7 First Edition 2013 Second Edition 2014 Vikas® is the registered trademark of Vikas Publishing House Pvt Ltd Copyright © Author, 2013

All rights reserved. No part of this publication which is material protected by this copyright notice may be reproduced or transmitted or utilized or stored in any form or by any means now known or hereinafter invented, electronic, digital or mechanical, including photocopying, scanning, recording or by any information storage or retrieval system, without prior written permission from the publisher. Information contained in this book has been published by VIKAS® Publishing House Pvt Ltd and has been obtained by its Authors from sources believed to be reliable and are correct to the best of their knowledge. However, the Publisher and its Authors shall in no event be liable for any errors, omissions or damages arising out of use of this information and specifically disclaim any implied warranties or merchantability or fitness for any particular use. Disputes if any are subject to Delhi Jurisdiction only. Printed in India.

Preface to the Second Edition It is a well known fact that operating system is an integral part of a computer system. It is this which makes the computer system function. The market today is constantly witnessing an upgradation of popular operating systems, such as Microsoft Windows, Linux, Mac OS X, Android, and many more. The continuous advancements in technology have led the universities to revise their curricula so as to suit the knowledge and learning needs of their students. To keep pace with various updated curricula as well as equipping budding system programmers with the right knowledge and expertise, we have come up with the second edition of Operating System. The revised edition has become more comprehensive with the inclusion of several new topics. More emphasis has been laid on the aesthetics of text to make it more presentable and appealing. Like its previous edition, it continues to provide in-depth coverage of the fundamentals as well as advanced topics in the discipline. In addition, certain sections in the book have been thoroughly revised. I hope the readers will find the present edition more helpful and informative in expanding their knowledge in operating system.

Key Additions Though several enhancements have been made to the text, following are the key additions to this new edition. • Chapter 1 introduces two more types of operating system, including Personal Computer (PC) Operating System and Mobile Operating System. • Chapter 2 now also includes the methods used for communication in client-server systems: Socket, Remote Procedure Call (RPC) and Remote Method Invocation (RMI). • The topics Thread Library and Thread Scheduling have been added in Chapters 3 and 4, respectively. • A few topics, including Principles of Concurrency, Precedence Graph, Concurrency Conditions and Sleeping Barber Problem have been added in Chapter 5. • Chapter 7 comprises an additional topic Structure of Page Tables. • Chapter 8 introduces topics like Demand Segmentation and Cache Memory Organization.

vi Preface to the Second Edition • • •

Chapter 9 now covers the concept of STREAMS. It also throws light on how I/O requests from the users are transformed to hardware operations. Chapters 10 and 11 add topics such as Disk Attachment, Stable Storage, Tertiary Storage, Record Blocking and File Sharing. The text of Chapter 13 is a complete overhaul and includes new topics, such as Goals and Principles of Protection, Access Control Matrix and its Implementation, Revocation of Access Rights, Cryptography, Trusted Systems, and Firewalls.

Chapter Organization The text is organized into 17 chapters. • Chapter 1 introduces operating system, its services, and structure. Also, it provides an insight into the organization of computer system. • Chapter 2 deals essentially with basic concepts of processes, such as process scheduling, operations on processes and communication between processes. It also introduces the methods used for communication in client-server systems. • Chapter 3 helps to understand the need and advantages of threads, various multithreading models as well as threading issues. It also introduces the concept of thread libraries and discusses various operations on the threads of Pthread library. • Chapter 4 spells out the scheduling criteria and different types of scheduling algorithms. It also discusses several issues regarding scheduling in multiprocessor and real-time systems. • Chapter 5 throws light on several methods used for achieving synchronization among cooperating processes. • Chapter 6 describes the deadlock situation and the conditions that lead to deadlock. It also provides methods for handling deadlock. • Chapter 7 familiarises the reader with the various memory management strategies used for contiguous and non-contiguous memory allocation. • Chapter 8 introduces the concept of virtual memory. It also discusses how virtual memory is implemented using demand paging and demand segmentation. • Chapter 9 discusses system I/O in detail, including the I/O system design, interfaces, and functions. It also explains the STREAMS mechanism of UNIX System V and the transformation of I/O requests into hardware operation. • Chapter 10 explains disk scheduling algorithms, disk management, swap-space management and RAID. It also introduces the concept of stable and tertiary storage. • Chapter 11 acquaints the readers with basic concepts of files including file types, attributes, operations, structure, and access methods. It also describes the concepts of file-system mounting, file sharing, record blocking and protection. • Chapter 12 explores how the files and directories are implemented. Management of free space on the disk is explained as well.

Preface to the Second Edition vii • • •

•

•

Chapter 13 disseminates to the reader the need of security and protection in computer systems. It also explains methods to implement the same. Chapter 14 sheds light on multiprocessor and distributed systems including their types, architecture and benefits. It also describes the distributed file system. Chapter 15 covers the UNIX operating system including its development and structure. It discusses how processes, memory, I/O, files, and directories are managed in UNIX. It also introduces elementary shell programming. Chapter 16 presents an in-depth examination of the Linux operating system. It describes how theoretical concepts of operating system relate to one another and to practice. Chapter 17 expounds on implementation of various operating system concepts in Windows 2000 operating system.

Acknowledgement In all my efforts towards making this book a reality, my special thanks go to my technical and editorial teams, without whom this work would not have achieved its desired level of excellence. I sincerely extend my thanks to my research and development team for devoting their time and relentless effort in bringing out this high-quality book. I convey my gratitude to my publisher Vikas Publishing House Pvt. Ltd for sharing this dream and giving all the support in realizing it. In our attempt towards further improvement, I welcome you all to send your feedback to [email protected]. I will highly appreciate all your constructive comments. I hope you will enjoy reading the book and hope it proves to be a good resource for all. Rohit Khurana Founder and CEO ITLESL, Delhi

Contents ix

Contents Preface to the Second Edition Acknowledgement viii

v

1. Introduction to Operating System 1.1 1.2 1.3 1.4

Introduction 1 Operating System: Objectives and Functions Different Views of an Operating System 4 Evolution of Operating Systems 4

1 2

1.4.1 Serial Processing 5; 1.4.2 Batch Processing 5; 1.4.3 Multiprogramming 7

1.5 Types of Operating Systems 9 1.5.1 1.5.2 1.5.3 1.5.4 1.5.5 1.5.6 1.5.7

Batch Operating Systems 10; Multiprogramming Operating Systems 10; Time-sharing Systems 10; Real-time Operating Systems 11; Distributed Operating Systems 12; Personal Computer Operating Systems 12; Mobile Operating Systems 12

1.6 Comparison between Different Operating Systems 12 1.7 Computer System Organization 14 1.7.1 Computer System Operation 15; 1.7.2 Storage Structure 15; 1.7.3 I/O Structure 16

1.8 Computer System Architecture 18 1.8.1 Single-Processor Systems 18; 1.8.3 Clustered Systems 19

1.8.2 Multiprocessor Systems 18;

1.9 Operating System Operations 20 1.9.1 Dual-Mode Operation 20;

1.9.2 Timer 21

1.10 Operating-System Structures 22 1.10.1 1.10.3 1.10.4 1.10.6

System Components 22; 1.10.2 Operating-system Services 25; User Operating-System Interface 27; System Calls 28; 1.10.5 System Programs 30; System Structure 31; 1.10.7 Virtual Machines 34

Let us Summarize 35 Exercises 37

x Contents 2. Process Management

39

2.1 Introduction 39 2.2 Process Concept 40 2.2.1 The Process 40; 2.2.2 Process States 40; 2.2.3 Process Control Block (PCB) 42

2.3 Process Scheduling 43 2.4 Operations on Processes 47 2.4.1 Process Creation 47;

2.4.2 Process Termination 48

2.5 Cooperating Processes 49 2.6 Inter-process Communication 49 2.6.1 Shared Memory Systems 50;

2.6.2 Message Passing Systems 52

2.7 Communication in Client-Server Systems 54 2.7.1 Socket 55; 2.7.2 Remote Procedure Call (RPC) 55; 2.7.3 Remote Method Invocation (RMI) 56

Let us Summarize 57 Exercises 59

3. Threads

61

3.1 Introduction 61 3.2 Thread Concept 61 3.2.1 Advantages of Threads 63;

3.2.2 Implementation of Threads 63

3.3 Multithreading Models 65 3.3.1 Many-to-One (M:1) Model 65; 3.3.2 One-to-One (1:1) Model 65; 3.3.3 Many-to-Many (M:M) Model 66

3.4 Threading Issues 67 3.4.1 fork() and exec() System Calls 67; 3.4.3 Thread-specific Data 68

3.4.2 Thread Cancellation 67;

3.5 Thread Libraries 68 3.5.1 Pthreads Library 68

Let us Summarize 70 Exercises 71

4. CPU Scheduduling 4.1 Introduction 73 4.2 Scheduling Concepts

73 73

4.2.1 Process Behaviour 74; 4.2.3 Dispatcher 75

4.2.2 When to Schedule 74;

4.3 Scheduling Criteria 75 4.4 Scheduling Algorithms 76 4.4.1 4.4.2 4.4.3 4.4.4 4.4.5 4.4.6 4.4.8

First-Come First-Served (FCFS) Scheduling 77; Shortest Job First (SJF) Scheduling 80; Shortest Remaining Time Next (SRTN) Scheduling 82; Priority-based Scheduling 84; Highest Response Ratio Next (HRN) Scheduling 87; Round Robin (RR) Scheduling 88; 4.4.7 Multilevel Queue Scheduling 91; Multilevel Feedback Queue Scheduling 92

4.5 Multiple Processor Scheduling

94

Contents xi 4.6 Real-time Scheduling 96 4.6.1 Hard Real-time Systems 96;

4.6.2 Soft Real-time Systems 97

4.7 Algorithm Evaluation 98 4.8 Thread Scheduling 100 Let us Summarize 101 Exercises 103

5. Process Synchronization 5.1 5.2 5.3 5.4

Introduction 106 Principles of Concurrency Precedence Graph 109 Critical Regions 110

106 107

5.4.1 Critical-Section Problem 110

5.5 Synchronization: Software Approaches 111 5.5.1 5.5.2 5.5.3 5.5.4

Strict Alternation: Attempt for Two-Process Solution 111; Dekker’s Algorithm: Two Process solution 113; Peterson’s Algorithm: Two-Process Solution 114; Bakery Algorithm: Multiple-Process Solution 116

5.6 Synchronization Hardware 117 5.7 Semaphores 120 5.8 Classical Problems of Synchronization 5.8.1 5.8.2 5.8.3 5.8.4

123

Producer-Consumer Problem 123; Readers-Writers Problem 125; Dining-Philosophers Problem 127; Sleeping Barber Problem 128

5.9 Monitors 130 5.10 Message Passing 134 Let us Summarize 136 Exercises 138

6. Deadlock 6.1 Introduction 140 6.2 System Model 140 6.3 Deadlock Characterization 6.3.1 Deadlock Conditions 141;

140

141 6.3.2 Resource Allocation Graph 141

6.4 Methods for Handling Deadlocks 142 6.5 Deadlock Prevention 143 6.6 Deadlock Avoidance 144 6.6.1 Resource Allocation Graph Algorithm 146; 6.6.2 Banker’s Algorithm 147

6.7 Deadlock Detection 152 6.7.1 Single Instance of Each Resource Type 152; 6.7.2 Multiple Instances of a Resource Type 153

6.8 Deadlock Recovery 153 6.8.1 Terminating the Processes 153; 6.8.2 Preempting the Resources 154

Let us Summarize 155 Exercises 156

xii Contents 7. Memory Management Strategies 7.1 7.2 7.3 7.4

Introduction 158 Background 159 Bare Machine 159 Contiguous Memory Allocation 7.4.1 Single Partition 160;

158

160

7.4.2 Multiple Partitions 161

7.5 Non-contiguous Memory Allocation

169

7.5.1 Paging 169; 7.5.2 Segmentation 177; 7.5.3 Segmentation with Paging 180

7.6 Swapping 181 7.7 Overlays 182 Let us Summarize 182 Exercises 184

8. Virtual Memory

187

8.1 Introduction 187 8.2 Background 188 8.3 Demand Paging 188 8.3.1 Performance of Demand Paging 191

8.4 Process Creation 192 8.4.1 Copy-on-Write 192;

8.4.2 Memory-Mapped Files 193

8.5 Page Replacement 194 8.5.1 FIFO Page Replacement 194; 8.5.2 Optimal Page Replacement 195; 8.5.3 LRU Page Replacement 197; 8.5.4 Second Chance Page Replacement 200; 8.5.5 Counting-Based Page Replacement Algorithm 201

8.6 Allocation of Frames 202 8.7 Thrashing 204 8.7.1 Locality 205; 8.7.2 Working Set Model 205; 8.7.3 Page-fault Frequency (PFF) 206

8.8 Demand Segmentation 207 8.9 Cache Memory Organization

208

8.9.1 Terminologies Related to Cache 208; 8.9.2 Impact on Performance 209; 8.9.3 Advantages and Disadvantages of Cache Memory 210

Let us Summarize 210 Exercises 212

9. I/O Systems

214

9.1 Introduction 214 9.2 I/O Hardware 215 9.3 I/O Techniques 216 9.3.1 Polling 216; 9.3.2 Interrupt-driven I/O 216; 9.3.3 Direct Memory Access (DMA) 217

9.4 Application I/O Interface 219 9.5 Kernel I/O Subsystem 221 9.5.1 I/O Scheduling 221; 9.5.2 Buffering 222; 9.5.4 Spooling 223; 9.5.5 Error Handling 223

9.5.3 Caching 222;

Contents xiii 9.6 Transforming I/O Requests to Hardware Operations 9.7 Streams 225 9.8 Performance 226 Let us Summarize 227 Exercises 228

223

10. Mass-Storage Structure

231

10.1 Introduction 231 10.2 Disk Structure 231 10.3 Disk Scheduling 234 10.3.1 10.3.2 10.3.3 10.3.5

First-Come, First-Served (FCFS) Algorithm 235; Shortest Seek Time First (SSTF) Algorithm 236; Scan Algorithm 236; 10.3.4 Look Algorithm 237; C-Scan and C-Look Algorithms 238

10.4 Disk Management

242

10.4.1 Disk Formatting 242; 10.4.2 Boot Block 243; 10.4.3 Management of Bad Sectors 244

10.5 Swap-Space Management 245 10.6 Raid Structure 246 10.6.1 Improving Performance and Reliability 246; 10.6.2 Raid Levels 247

10.7 Disk Attachment

250

10.7.1 Host-attached Storage 250;

10.7.2 Network-attached Storage 251

10.8 Stable Storage 251 10.9 Tertiary Storage 252 10.9.1 Removable Disks 252;

10.9.2 Magnetic Tapes 254

Let us Summarize 255 Exercises 256

11. File Systems

259

11.1 Introduction 259 11.2 Files: Basic Concept 260 11.2.1 File Attributes 260; 11.2.2 File Operations 261; 11.2.3 File Types 262; 11.2.4 File Structure 263; 11.2.5 File Access 264

11.3 Directories

265

11.3.1 Single-level Directory System 266; 11.3.2 Two-level Directory System 266; 11.3.3 Hierarchical Directory System 267;

11.4 File-System Mounting 11.5 Record Blocking 270 11.6 File Sharing 271

11.3.4 Directory Operations 268

268

11.6.1 File Sharing among Multiple Users 271; 11.6.2 File Sharing in Remote File Systems 272; 11.6.3 Consistency Semantics 273

11.7 Protection 273 11.7.1 Types of Access

Let us Summarize 275 Exercises 277

273;

11.7.2 Access Control 274

xiv Contents 12. Implementation of File System 12.1 Introduction 280 12.2 File System Structure 280 12.3 File System Implementation

280

282

12.3.1 Operating Structures 282; 12.3.2 Partitions and Mounting 284; 12.3.3 Virtual File System (VFS) 285

12.4 Allocation Methods

286

12.4.1 Contiguous Allocation 286; 12.4.3 Indexed Allocation 289

12.4.2 Linked Allocation 288;

12.5 Implementing Directories 290 12.5.1 Linear List 291;

12.5.2 Hash Table 291

12.6 Shared Files 292 12.7 Free-Space Management 293 12.8 Efficiency and Performance 295 12.8.1 Efficiency 295;

12.8.2 Performance 296

12.9 Recovery 298 12.10 Log-Structured File System 299 Let us Summarize 301 Exercises 302

13. Protection and Security 13.1 13.2 13.3 13.4

304

Introduction 304 Goals of Protection 305 Principles of Protection 305 Protection Mechanisms 306 13.4.1 Protection Domain 306;

13.4.2 Access Control Matrix 307

13.5 Revocation of Access Rights 312 13.6 Security Problem 313 13.6.1 Intruders 313;

13.6.2 Types of Security Violations 314

13.7 Design Principles for Security 13.8 Security Threats 316 13.8.1 Program Threats 317;

13.9 Cryptography

316

13.8.2 System and Network Threats 319;

321

13.9.1 Encryption 321

13.10 User Authentication

324

13.10.1 Passwords 325; 13.10.2 One-time Passwords 325; 13.10.3 Smart Card 326; 13.10.4 Biometric Techniques 326

13.11 Trusted Systems 327 13.12 Firewalling to Protect Systems and Networks Let us Summarize 329 Exercises 331

327

14. Multiprocessor and Distributed Operating Systems 14.1 Introduction 333 14.2 Multiprocessor Systems

334

14.2.1 Interconnection Networks 334; 14.2.2 Architecture of Multiprocessor Systems 336; 14.2.3 Types of Multiprocessor Operating System 339

333

Contents xv 14.3 Distributed Systems

341

14.3.1 Distributed Operating System 342; 14.3.2 Storing and Accessing Data in Distributed Systems 343

14.4 Computer Networks

344

14.4.1 Types of Networks 344; 14.4.2 Network Topology 346; 14.4.3 Switching Techniques 349; 14.4.4 Communication Protocols 352

14.5 Distributed File System 354 Let us Summarize 356 Exercises 358

15. Case Study: UNIX 15.1 15.2 15.3 15.4

360

Introduction 360 History of UNIX 361 UNIX Kernel 362 Process Management 363 15.4.1 Process Creation and Termination 364; 15.4.2 Inter-process Communication 365; 15.4.3 Process Scheduling 366; 15.4.4 System Calls for Process Management 368

15.5 Memory Management

368

15.5.1 Implementation of Memory Management 369; 15.5.2 System Calls for Memory Management 372

15.6 File and Directory Management 372 15.6.1 UNIX File System 373; 15.6.2 UNIX Directory Structure 375; 15.6.3 System Calls for File and Directory Management 377

15.7 I/O Management 377 15.8 Elementary Shell Programming

379

15.8.1 Logging in UNIX 379; 15.8.2 Basic Shell Commands 379; 15.8.3 Standard Input, Output and Error 380; 15.8.4 Re-direction 380; 15.8.5 Wildcards 381; 15.8.6 Filters 381; 15.8.7 Shell Program 382

Let us Summarize 384 Exercises 386

16. Case Study: Linux

388

16.1 Introduction 388 16.2 The Linux System 388 16.3 Process and Thread Management

390

16.3.1 Creation and Termination of Processes and Threads 390; 16.3.2 Process Scheduling 391

16.4 Memory Management

392

16.4.1 Physical Memory Management 392; 16.4.2 Virtual Memory Management 393

16.5 File System 394 16.5.1 Linux ext2 File System 395; 16.5.3 Linux proc File System 396

16.6 I/O Management 396 Let us Summarize 397 Exercises 398

16.5.2 Linux ext3 File System 395;

Second Edition

Operating System The book Operating System by Rohit Khurana is an insightful work that elaborates on fundamentals as well as advanced topics of the discipline. It offers an in-depth coverage of concepts, design and functions of an operating system irrespective of the hardware used. With illustrations and examples the aim is to make the subject crystal clear, and the book extremely student-friendly. The book caters to undergraduate students of most Indian universities, who would find subject matter highly informative and enriching. Tailored as a guide for self-paced learning, it equips budding system programmers with the right knowledge and expertise. The book has been revised to keep pace with the latest technology and constantly revising syllabuses. Thus, this edition has become more comprehensive with the inclusion of several new topics. In addition, certain sections of the book have been thoroughly revised. KEY FEATURES OF THE BOOK < Case studies of Unix, Linux and Windows to put theory concepts into practice < A crisp summary for recapitulation with each chapter < A glossary of technical terms < Insightful questions and model test papers to prepare for the examinations

NEW IN THE SECOND EDITION < More types of operating system, like PC and mobile; Methods used for communication in client-server systems. < New topics like: Thread library; Thread scheduling; Principles of concurrency, Precedence graph, Concurrency conditions and Sleeping barber problem; Structure of page tables, Demand segmentation and Cache memory organization; STREAMS; Disk attachment, Stable and tertiary storage, Record blocking and File sharing; Goals and principles of protection, Access control matrix, Revocation of access rights, Cryptography, Trusted systems, and Firewalls.

Rohit Khurana is the Founder and CEO of ITL Education Solutions Limited (ITLESL) and has authored more than thirty-five best-selling textbooks. ITLESL is a part of the ITL group which has operations all over the world with a significant presence in education and IT-enabled services. It specializes in handling educational projects in IT domains with a dedicated R&D wing of industry experts that helps in designing and developing content.

` 399 ISBN 978-93259-7563-7

9 789325 975637