SYSTEMS PROGRAMMING D M Dhamdhere&§ Tata McGraw-Hill Published by Tata McGraw Hill Education Private Limited, 7 West Patel Nagar, New Delhi 110 008 Systems Programming Copyright © 2011 by Tata McGraw Hill Education Private Limited. First reprint 2011 RBZCRRBGRCQQZ No part of this publication may be reproduced or distributed in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise orstored in a database or retrieval system without the prior written permission of the publishers, The program listings (if any) may be entered, siored and executed in a computer system, but they may not be reproduced for publication. This edition can be exported from India only by the publishers, Tata McGraw Hill Education Private Limited. ISBN (13): 978-0-07-133311-5 ISBN (10): 0-07-133311-8 Vice President and Managing Direcior—McGraw-Hill Education, Asia Pacific Region: Afay Shukla Head—Higher Education Publishing and Marketing: Vibha Mahajan Publishing Manager—SEM & Tech Ed.: Shalini Jha Editorial Researcher: Noaman Khan Sr Copy Editor: Nimisha Kapoor Sr Production Manager: Satinder S Baveja Marketing Manager—Higher Education: Vijay S Jagannathan Sr Product Specialist SEM & Tech Ed.: John Mathews General Manager—Production: Rajender P Ghansela ‘Asst General Manager—Production: BL Dogra reliable. However, neither Tata McGraw-Hill nor its authors guarantee the accuracy or completeness of any information published herein, and neither Tata McGraw-Hill nor its authors shall be responsible for any errors, omissions, or damages arising out of use of this information, This work is published with the understanding that Tata McGraw-Hill and its authors ere supplying information but are not attempting to render engineering or other professional services. If such services are required, the assistance of an appropriate professional should be sought. [ Information contained in this work has been obtained by Teta McGraw-Hill, from sources believed to be ‘Typeset at Script Makers, 19, Al-B, DDA Market, Paschim Vihar, New Delhi 110 063 and text printed at Adarsh Printers, C-50-51, Mohan Park, Naveen Shahdara, Delhi — 110032 Cover Designer: Meenu Raghav Cover Printer: A. B. Offset ac aContents Preface L_introduction 1.1 What is System Software? 1.2 Goals of System Software all 1.3 System Programs and Systems Programming g 1.4 The Wonderland of System Software 8g 1.4.1 The Program Development and Production Environments 9 1.4.2 Making Software Portable ir 1.43 Realizing Benefits of the Internet 12 1.4.4 Treating Programs as Components 13 14.5 Quick-and-Dirty Programming 14 1.4.6 The Embedded System Environment 15 1.4.7 Dynamic Specification, Flexibility, and Adaptive Software 16 1.5 Views of System Software 19 1.5.1 The User-Centric View of System Software 20 1.5.2 The System-Centric View of System Software 20 1.7 Summary - 22 Test Your Concepts 23 Bibliography 23 Part 1: Language Processors 25 2. Overview of Language Processors 27 2.1 Programming Languages and Language Processors 28 2.1.1 Kinds of Language Processors 30 2.1.2 Procedure Oriented and Problem Oriented Programming Languages 32 2.2 Language Processing Activities 33 2.2.1 Program Generation 34gram Generators for 2.2.1.2 A General ose | Generator "2.2.2.1 Program Translation 2.2.2.2 Program Interpretation 2.3 Fundamentals of Language Processing 2.3.1 Multi-Pass Organization of Language Processors 2.3.2 A Toy Compiler 23.22 ‘The Back End 2.4 Symbol Tables 2.4.1 Symbol Table Entry Formats 2.4.2 Symbol Table Organizations Using Linear Data Structures 2.4.3 Linked List and Tree-Structured Symbol Table Organizations 2.5 Summary Test Your Concepts Bibliography aa : 3.1 Elements of Assembly Language Programming 3.1.1 Assembly Language Statements 3.1.2 Benefits of Assembly Language 3.2_A Simple Assembly Scheme 3.3 Pass Structure of Assemblers 3.4 Design of a Two-Pass Assembler | 3.4.4 Intermediate Code for Imperative Statements 3.4.5 Processing of Dec! larations and. Assembler Directives deena 3 st Error 3.48 Some Organizational Issues 3.5_A Single-Pass Assembler for Intel x86 Family Processors _ 3.5.3 The Assembly Language of Intel 8088 5.4 Problems of Single-Pass Assembly Design of the Assembler .5.6 Algorithm of the Single-Pass Assembler 3.6 Summary | “Test Your Concepts Exercises Bibliography RRERERRERESe See SBERE BERNER 4 SRRARUBEERBSEERRER CopyrightedContents _vii 4. Macros and Macro Preprocessors 123 4:1 Introduction 124 Shue oe 4.3 Macro Expansion 126 4.4 Nested Macro Calls eS - EGE 4.5.1 Conditional Expansion 135, 4.5.2 Expansion Time Loops 136 4.5.3 Semantic Expansion 138 4.6 Design of a Macro Preprocessor 139 4.6.1 Design Overview 139 4.6.2 Data Structures of the Macro Preprocessor 141 4.6.3 Processing of Macro Definitions 144 4.6.4 Macro Expansion 148 4.6.5 Handling Nested Macro Calls 149 & The Stack Data S r 5 4.6.6.1 The Extended StackModel SD 4.6.7 Use of Stacks in Expansion of Nested Macro Calls 153 4.6.8 Design of a Macro Assembler 155 4.7 Summary 157 Test Your Concepts 158 Exercises 159 Bibliography 160 5 Lis 6 1 Introduction 16: 5.2 Relocation and Linking Concepts 164 5.2.1 Program Relocation 164 5.2.2 Linking - 166 5.2.3 Object Module 168 5.3 Design of a Linker 169 §.3.2 Scheme for Linking 171 5.4 Self-Relocating Programs 173 5.5 Linking in MS DOS. 174 5.5.1 Relocation and Linking Requirements in Segment-Based Addressin; 174 5.5.2 Object Module Format = 176 4.5.3 Design of the Linker 182 5.6 Linking of Overlay Structured Programs 137 5.7 Dynamic Linking 190 5.8 Loaders 191 5.8.2 Relocating Loaders 192 5.9 Summary 193 Copyrighted materialviii_Contents Test Your Concepts Exercises Bibliography 6. Scanning and Parsing 6.1 Programming Language Grammars ifeitea af 6.1.2 Ambiguity in Grammatic Specification 6.2 Scanninj 63 Parsing 6.3.1 Top-Down Parsing 63.1.1 Practical Top-Down Parsing 6.3.2 Botiom-Up Parsing 6.3.2.1 Operator Precedence Parsing 6.4 Language Processor Development Tools 6.4.1 LEX 6.4.2 YACC 6.5 Summary Test Your Concepts Exercises Bibliography 7. Compilers 7.1 Causes of a Large Semantic Gap 7.2 Binding and Binding Times 7.3 Data Structures Used in Compilers 7.3.1 Stack 7.3.2 Heap 7.4 Scope Rules 7.3 Memory Allocation 7.5.1 Static and Dynamic Memory Allocation 7.5.2. Dynamic Memory Allocation and Access 7.8.3 Memory Allocation and Deallocation 7.5.3.1 Accessing Local and Noniocal Variables 75.32 Symbol Table Requirements 75.33 Recursion 1 Array Allocation and Access . 7.6 Compilation of Expressions 7.6.1 A Toy Code Generator for Expressions 7.6.2 Intermediate Codes for Expressions 7.6.3 Postfix Notation 7.6.4 Triples and Quadruples 7.6.5 Expression Trees 7.7 Compilation of Control Structures 2.1.1 Function and Procedure Calls REREER ESE SBEBRE 239 252 252 253 259 260 261 263 266 267 272 2B 282 283 284 289Contents _ix 7.8 Code Optimization 296} 7.8.1 Optimizing Transformations 207 7.8.2 Local Optimization 300 7.8.3 Global Optimization 303 7.8.3.1 Program Representation for Global Optimization 304 7.8.3.2 Control Flow Analysis 305 7.8.3.3 Data Flow Analysis 305 7.9 Summary 309 Test Your Concepts 310 Exercises 3 Bibliography 313 8. Interpreters 315 8.1 Benefits of Interpretation 316 8.2 Overview of Interpretation 317 8.2.1 A Toy Interpreter 317 8.2.2 Pure and Impure Interpreters 320 8.3 The Java Language Environment 321 8.3.1 Java Virtual Machine 323 8.4 Summary 326 Test Your Concepts 327 Exercises 327 Bibliography 327 9. Software Tools 329 9.1 What is a Software Tool? 330 9.2 Software Tools for Program Development 330 9.2.1 Program Design and Coding 331 9.2.2 Program Entry and Editing 331 9.2.3 Program Testing and Debugging 331 9.2.4 Program Performance Tuning 335 9.2.5 Source Code Management and Version Control 336 9.2.6 Program Documentation Aids 339 9.2.7 Design of Software Tools 339 9.3 Editors 341 9.3.1 Seren Editors 341 9.3.2 Word Processors 341 9.3.3 Structure Editors 342 9.3.4 Design of an Editor 342 9.4 Debug Monitors 343 9.4.1 Testing Assertions 345 9.5 Programming Environments 345 9.6 User Interfaces 347 9.6.1 Command Dialogs 348 9.6.2 Presentation of Data 349x_Contents 9.6.3 On-Line Help 349 9.6.4 Structure of a User Interface 350 9.6.5 User Interface Management Systems 350 9.7 Summary 351 Test your concepts 352 Exercises 352 Bibliography 353 Part Il : Operating Systems 355 10. Overview of Operating Systems 357 10.1 Fundamental Principles of OS Operation 358 10.2 The Computer 360 10.2.1 The CPU 360 10.2.2 Memory Hierarchy 363 10.23 Input/Output 367 10.2.4 Interrupts 368 10.3 OS Interaction with the Computer and User Programs 371 10.3.1 Controlling Execution of Programs 371 10.3.2 Interrupt Servicing 372 10.3.3 System Calls 376 10.4 Structure of Operating Systems 378 10.4.1 Portability and Extensibility of Operating Systems 378 10.4.2 Kernel-Based Operating Systems 379 10.43 Microkernel-Based Operating Systems 380 10.5 Computing Environments and Nature of Computations 381 10.6 Classes of Operating Systems 384 10.7 Batch Processing Systems 386 10.8 Multiprogramming Systems 388 10.8.1 Priority of Programs 390 10.9 Time Sharing Systems 393 10.9.1 Swapping of Programs 396 10.10 Real Time Operating Systems 397 10.10.1 Hard and Soft Real Time Systems 397 10.11 Multiprocessor Operating Systems 398 10.12 Distributed Operating Systems 400 10.13 Virtual Machine Operating Systems 402 10.14 Modem Operating Systems 404 10.15 Summary 405 Test Your Concepts 407 Exercises 407 Bibliography 40911.1.2 Relationships Between Processes and Programs 11.13 Child Processes: 11.1.4 Concurrency and Parallelism 11.2 Implementing Processes 11.2.2 Events Pertaining to a Process 11.23 Process Control Block 11.2.4 Data Sharing, Message Passing and Synchronization Between Processes 11,3 Process Scheduling 11.3.1 Scheduling Terminology and Concepts 11.3.2 Fundamental Techniques of Scheduling 11.3.3 Round-Robin Scheduling with Time Slicing (RR) 113.4 Multilevel Scheduling 114 Threads 11.5 Summary ‘Test Your Concepts Exercises Bibliography 12. Memory Management 12.1 Managing the Memory Hierarchy 2.1.1 Static and sic Me Allocation 12.2 Memory Allocation to a Process 12.2.1 Stacks and Heaps 12.2.2 Reuse of Memory 12.2.2.1 Maintaining a Free List 12.2.2.2 Performing Fresh Allocations Using a Free List 12.2.2.3 Fr ition 12.2.3 Buddy System Allocator 12.2.4 The Memory Allocation Model 12.2.5 Memory Protection 12.3 Contiguous Memory Allocation 12.4 Virtual Memory 12.5 Virtual Memory Using Paging 12.5.1 Memory Protection 12.5.2 Demand Paging 12.5.3 Page Replacement Algorithms 12.5.4 Controlling Memory Allocation to a Process 12.6 Summary Test Your Concepts Bibliography SBBREBE® SRREBE BSEEESE 452 452 457 BRABExii_Contents 13, File Systems 465 13.1 Overview of File Processing 466 13.1.1 File System and the IOCS 466 13.1.2 File Processing in a Program 467 13.2 Files and File Operations 468 13.3 Fundamental File Organizations 469 13.3.1 Sequential File Organization 469 13.3.2 Direct File Organization 470 13.3.3 Indexed and Index Sequential File Organizations 470 13.4 Directories 47 13.5 Allocation of Disk Space 414 13.5.1 Linked Allocation 414 13.52 Indexed Allocation gs 13.6 File Protection 476 13.7 File System Reliability 477 13.7.1 Recovery Techniques 4n 13.8 Implementing an /O Operation 478 13.9 Overview of I/O Organization 418 13.10 Device Level YO 480 13.10.1 1/0 Programming 480 13.11 The Input-Output Control System 481 13.1.1 Logical Devices 482 13.112 IOCS Data Structures 482 13.1.3 Overview of IOCS Operation 483 13.114 Device Drivers 484 13.115 Disk Scheduling 485 13.12 Buffering of Records 486 13.13 Blocking of Records 492 13.14 Disk and File Caches 4985 13.15 Summary 496 Test Your Concepts 497 Exercises 497 Bibliography 498 14. Security and Protection 500 14.1 Overview of Security and Protection 501 14.1.1 Goals of Security and Protection 503 14.1.2 Security and Protection Threats 504 14.2 Security Attacks 504 14.2.1 Trojan Horses, Viruses and Worms 505 14.2.2 The Buffer Overflow Technique 508 14,3 Encryption 510 14.4 Authentication and Password Security Sil14.5.1 Access Control Matrix 14,5.2 Access Control Lists (ACLs) 14.6 Classifications of Computer Security 14.7 Security Attacks in Distributed Systems 14.8 Message Security 14.8.1 Preventing Message Replay Attacks 14.9 Authentication of Data and Messages 14.9.1 Certification Authorities and Digital Certificates 14.9.2 Message Authentication Code and Digital Signature 14,10 Summary Test Your Concepts Exercises Bibliography Index Contents xiii 513 514 51S S16 517 520 521 521 522 523 525 526 526Copyrighted materialPreface Easy development of new programs and applications, and their efficient operation on a computer are the primary concems of computer users. However, both the concerns cannot be satisfied simultaneously. This situation has led to different kinds of schemes for program development which provide ease of program development to varying degrees and to many schemes for program execution which offer varying levels of execution efficiency. A user has to choose a scheme of each kind to obtain a suitable combination of ease of program development and efficiency of operation. Programs that implement the schemes for program development and program execution are called system programs and the collection of system programs of a computer is called system software. A course on systems programming deals with the fundamental concepts and techniques used in the design and implementation of system programs, and their properties concerning speed of program development and efficiency of operation. Accordingly, a book on systems programming has to focus on numerous topics—support for quick and efficient development of programs, design of adaptive and extensible programs that can be easily modified to provide new functionalities, models for execution of programs written in programming languages, and interactions among user programs, the operating system, and the computer to achieve efficient and secure operation of the computer. My previous book Systems Programming and Operating Systems covered the complete arca of sysiem software. It was used for three kinds of courses~-systems programming, compilers, and operating systems. However, it was a large book that needed to get even larger to keep pace with developments in this field, so I decided to offer two separate books in this area. This book focuses primarily on systems programming. It can be used for a course on systems programming that contains ‘a small module on operating systems and also for a course on compilers. It is expected that instructors and students of courses on operating systems would use my other book Operating Systems—A Concept- Based Approach. General approach Diversity of computer systems and system programs has been a major challenge in the writing of this text. Ihave used principles of abstraction and simple models of computer systems and system programs to present the key issues in design of system programs. This way, the text is free of dependence on specific computers, programming languages, or operating systems. Pedagogical features Chapter introduction The chapter introduction motivates the reader by describing the objectives of the chapter and the topics covered in it.xvi_ Preface Figuresand boxes Figures depict practical arrangements used to handle user computations and resources, stepwise operation of specific techniques, or comparisons of alternative techniques that project their strengths and weaknesses. Boxes are used to enclose key features of concepts or techniques being discussed. They also serve as overviews or summaries of specific topics. Examples Examples demonstrate the key issues conceming concepts and techniques being discussed. Examples are typeset in a different style to set them apart from the main body of the text, so a reader can skip an example if she does not want the flow of ideas to be interrupted, especially while reading a chapter for the first time. Algorithms Specific details of processing performed by system programs are presented in the form of algorithms. Algorithms are presented in an easy to understand pseudo-code form Case studies Case studies emphasize practical issues, arrangements and trade-offs in the design and implementation of specific schemes, Case studies are organized as separate sections in individual chapters. Tests of concepts A set of objective and multiple choice questions are provided at the end of each chapter, so that the reader can test the grasp of concepts presented in the chapter. Exercises Exercises are included at the end of each chapter. These include numerical problems based ‘on material covered in the text, as well as challenging conceptual questions which test understanding and also provide deeper insights. Chapter summary ‘The summary included at the end of each chapter highlights the key topics covered in the chapter and their interrelationships. Instructor resources A detailed solutions manual is provided. Organization of the book The first chapter describes goals of system software and discusses the characteristics that distinguish system programs from other kinds of programs. It also introduces the notion of effective utilization of a computer, it is a combination of user convenience, programmer productivity, and efficient and secure operation of a computer that suits a user’s purposes. The rest of the chapter describes the broad spectrum of considerations that influence the design of system programs. These considerations range from user expectations such as high productivity during program development, ease of porting a program from ‘one computer to another, ability to compose new programs by using existing programs as components, ability of software to adapt to its usage environment, and secure and efficient operation of programs. The first chapter also develops two views of system software from the perspectives of ease of programming and efficient operation, respectively. The user-centric view is comprised of system programs that assist a user in fulfilling her computational needs. It includes system programs that transform a user program written in a programming language into a form that can be executed on a computer, The systemeentric view is comprised of programs that achieve effective utilization of a computer system by sharing its resources among user programs and ensuring non-interference during their execution. We call these two kinds of system programs /anguage processors and operating system programs, respectively. The rest of the book is organized into two parts dealing with these two kinds of system programs, respectively.Preface _ xvii Language Software Processors Tools Aseetniett Hales and Panag Macro Assenbess Interpreters | | Compilers Chapters of Part 1 + Part I: Language processors A language processor is a system program that bridges the gap between how a user describes a computation in the form of a program, and how a computer executes a program. This gap is called the specification gap. The figure shows the interrelationship between chapters in this pan. Chapter 2 describes how the specification gap influences ease of programming and execution efficiency of programs, It describes two classes of language processors called program generators and translators. It then describes fundamentals of the language processing activity and the organization of language processors. Remaining chapters of this part discuss details of specific kinds of language processors. Chapter 3 discusses the design of an assembler, which is the translator of a low-level machine-specific language called the assembly language. Chapter 4 discusses the macro facility provided in assembly languages, which enables a programmer to define new operations and data structures of her own choice to simplify design and coding of programs. Chapter 5 discusses linkers and loaders, which are system programs that merge the code of many programs so that they can be executed together and make the merged code ready for execution by the computer. Chapter 6 describes the techniques of scanning and parsing that are used by a language processor to analyse a program written in a programming language. Chapters 7 and 8 discuss compilers and interpreters, which are two models of execution of programs written in programming languages. Finally, Chapter 9 discusses software tools, which are programs that suitably interface a program with other programs to simplify development of new applications. ‘Many of these tools use elements of language processing to achieve their goals. Part Il: Operating systems ‘The operatingsystem controls operationof the computer and organizes execution of programs. Part II comprises five chapters. Chapter 10 describes the fundamentals of an operating system—how it controls operation of the computer, and how it organizes execution of programs. It contains an overview of those features of a computer’s architecture that are relevant to the operating system and describes how an operating system functions. It then provides an overview of the concepts and techniques of operating systems used in the classical computing environments. Chapters 11-14 discuss concepts and techniques used in the four key functionalities of operating systems, namely, management of programs, management of memory, file systems, and security and protection in operating systems.xvili Preface Using this book Apart from an introduction to computing, this book does not assume the reader to possess any specific background, Hence it can be used by both students of systems programming and by working professionals. Dhananjay Dhamdhere April 2011CHAPTER 1 Introduction ‘A modem computer has powerful capabilities such as a fast CPU, large memory, sophisticated input-output devices, and newworking support; however, it has to be instructed through the machine language, which has strings of Os and Is as its instructions. A typical computer user does not wish to interact with the computer at this level. The system software is a collection of programs that bridge the gap between the level at which users wish to interact with the computer and the level at which the computer is capable of operating. It forms a software layer which acts as an intermediary between the user and the computer. It performs two functions: It translates the needs of the user into a form that the computer can understand so that the user’s program can actually get executed on the computer. However, the com- puter has more resources than needed by a program, so many of its resources would remain idle while it is servicing one program. To avoid this problem, the software layer gives the idle resources to some other programs and interleaves execution of all these programs on the computer. This way, the computer can provide service to many users simultaneously. Each program in the system software is called a system program. System pro- grams perform various tasks such as editing a program, compiling it, and arranging for its execution. They also perform various tasks that a user is often unaware of, such as readying a program for execution by linking it with other programs and with functions from libraries, and protecting a program against interference from other programs and users. The term systems programming is used to describe the collec- tion of techniques used in the design of system programs. In this chapter we define the design goals of system programs and discuss the -Giverse functions performed by them. We then discuss the functions performed by different kinds of system programs. Details of their functioning and design are dis- cussed in subsequent chapters.2. Systems Programming 1.1 WHAT IS SYSTEM SOFTWARE? To a computer user, a computer system is merely a means to an end. Thus, a question such as “Whatis a computer system?” is likely to evoke different answers, depending on the user's interest. For example, © Toaschool or college student, the computer system is the equipment that runs a browser for the Intemet. © To auser of an application package, such as an accounting package, the com- puter system is simply the equipment that facilitates use of the package. © To a programmer, the computer system is the equipment for developing new programs. For the student, the sole purpose of the computer system is to get onto the Inter- net. Hence the student thinks of the computer system as the means for browsing the Internet. The user of a package and the programmer identify the computer system with their particular purposes in using it. Since their purposes are different, their perceptions of the computer system are also different, Each of these views is an abstract view, because it focuses on those characteris- ties considered essential from the perspective of the individual viewer—it includes some elements of reality but ignores other elements. The student and the application user are end-users of the computer system. Their views contain the sofiware they use, but do not contain any features of the computer system. The programmer's view is that of a software developer. It includes those features of the computer system that are relevant for software development. ‘The computer system is actually quite different from each of these views. It is comprised of two parts—the electronic circuits that constitute the computer hard- ware, which we will simply call the computer, and the system software that enables a user to satisfy his computational needs by using the computer. A computer has to be instructed through its machine language, which is comprised of instructions that are strings of 0s and Is. A typical computer user does not wish to write programs in the machine language. The system software is a collection of programs that bridges the gap between the level at which users wish to interact with the computer and the level at which the computer is capable of operating. Figure 1.1 shows two representative views of a computer system. In both these views, the dashed box represents system software; however, it consists of a different arrangement of programs in each view. The view in Part (a) of the figure corresponds to the view of the student or the application user described earlier. It shows only the software and the operating system. Part (b) shows the view of the programmer in which language processors are programs such as compilers that assist the program- mer in developing programs. A third view of a computer system, which is not shown in Figure 1.1, is one in which the computer system is not seen at all. It is applicable when a computer is embedded in another system, which is often an equipment ofIntroduction 3 R User RR User User interface User interface Application programs Language processors Operating system Operating system Computer hardware Computer hardware @) () Figure 1.1 Abstract views of « computer system: (a) View of a student. (b) View of the programmer some kind. The typical functionalities of the system software shown in Figure 1.1 are as follows: © User interface: The user interface accepts users’ commands for using services provided by the operating system and initiates execution of one or more pro- grams to fulfill the command. The user interface is either a command line interface, as in Unix or Linux, which displays a command prompt to the user and accepts a user command, or is a graphical user interface (GUI), as in the Windows operating system, which interprets mouse clicks as user commands. © Application programs or language processors: These programs either imple- ment the user's application or assist in development of a program. ‘© Operating system: The operating system controls operation of the computer and provides a set of services for executing programs and using resources of the computer. ‘Two features of system software emerge from the views shown in Figure 1.1. System software is actually a collection of programs that facilitate execution of Programs and use of resources in 2 computer system. It contains a hierarchical ‘arrangement of layers in which programs in a higher layer use the facilities pro- vided by programs in the layer below it. In fact, each layer takes an abstract view of the layer below it, in which the lower layer is a machine that can understand certain commands. The fact that the lower layer is a set of programs rather than a machine makes no difference to the higher layer. This way, each higher layer acts as a more capable machine than the layer below it. To the user, the user interface appears like a machine that understands the commands issued by her. A.user specifies her computational needs in the form that best suits her. Typically, it takes the form of a program written in a programming language, or a command to4_ Systems Programming ‘a software package like an accounting package. Each layer of system software con- verts this specification into one that can be implemented by issuing a sequence of commands to the software layer below it. In this manner, finally the computer hard- ware receives a sequence of instructions in its machine language which it can execute straightaway. Thus, the needs of a user are translated into a form that a computer can understand. However, this process of translation consumes some resources of the ‘computer because the programs that constitute a layer of system software occupy a part of the computer's memory and use its CPU for a non-negligible amount of time. Such consumption of resources by the system software constitutes its overhead. The ‘overhead depends both on the number of software layers and the functions performed by each layer; it limits the number of software layers that may be used in a computer system. 1.2 GOALS OF SYSTEM SOFTWARE ‘A modern computer is resource-rich. It has a powerful CPU, large memory, disks with large capacity, several input-output devices, and networking hardware. Several of its resources remain idle while it is servicing one program. Hence the system software gives the idle resources to some other programs and interleaves execution of all these programs on the computer. This way, servicing of many users’ commands is in progress simultaneously. It naturally leads to the need for preventing interference between activities of users. Accordingly, the fundamental goals of system software are as follows: « User comenience: Provide convenient methods of using a computer system « Efficient use: Ensure efficient use of a computer's resources © Non-interference: Prevent interference in the activities of its users. Can the goals of user convenience and efficient use of the computer's resources conflict? That is, can a software that provides a high level of convenience make less efficient use of a computer's resources? As we shall see later in this chapter, such a conflict is possible. Hence designers of system software have to make a difficult deci- sion: Different classes of users desire different levels of convenience and efficiency, so how to decide whether to favour convenience or efficiency? For example, should anew layer of system software be added to provide a convenience even though its addition would reduce efficiency, or should users be made to put up with a little bit of inconvenience in interests of efficiency? In practice, this dilemma is resolved at two levels—by an individual user herself and by the operating system. As we shall see in a later section, the user can choose between available system softwares to select the ‘one that would provide either convenience or efficient use of resources as desired. An operating system resolves the dilemma between user convenience and effi- cient use by using the notion of a computing environment. A computing environ- ment represents the combination of three things—a computer system’s hardware, its interfaces with other computers, and the nature of its users’ computational needs. InIntroduction 5 each computing environment, users desire a specific combination of convenience and efficient use. This is the notion of effective utilization of the computer system. For example, users in an interactive environment would favour convenience, e.g., fast re- sponse, to efficient use, whereas in a commercial data processing environment users would prefer efficiency to convenience because it would reduce the cost of comput- ing. Hence an operating system simply chooses techniques that provide a matching combination of convenience and efficient use. We find a rich diversity in operating systems, and in system software in general, because effective utilization has a differ- ent flavour in each computing environment. We consider examples of this diversity in later sections of this chapter. Interference with a user’s activities may take the form of illegal use or modifi- cation of a user’s programs or data, or denial of resources and services to a user. It could be caused by users of acomputer system or by non-users. The system software must incorporate measures to prevent interference of all kinds and from all sources. We discuss important aspects of the three fundamental goals of system software in the following section. 1.2.1 User Convenience Table 1.1 lists many facets of user convenience. In the early days of computing, user convenience was synonymous with bare necessity—the mere ability to execute a program written in a higher level language was considered adequate. However, soon users were demanding better service, which in those days meant only fast response to a user command. ‘Table 1.1 Facets of user convenience Facet Examples Fulillment of necessity Ability to execute programs, use the file system Good Service Speedy response to computational requests User friendly interfaces Easy-to-use commands, Graphical user interface (GUI) New programming model Concurrent programming Web-oriented features Means to set up web enabled servers Evolution ‘Add new features, use new computer technologies Other facets of user convenience evolved with the use of computers in new fields. Early operating systems had command-line interfaces, which required a user to type in a command and its parameters. Users needed substantial training to learn use of commands, which was acceptable because most users were scientists or computer professionals. However, simpler interfaces were needed to facilitate use of comput- ers by new classes of users. Hence graphical user interfaces (GUIs) were designed. ‘These interfaces used icons on a screen to represent programs and files and inter- preted mouse clicks on the icons and associated menus as commands concerning6 Systems Programming them. Computer users attacked new problems as computing power increased. New models were proposed for developing cost-effective solutions to new classes of problems. Some of these models could be supported by the compiler technology and required little support from the operating system; modular and object oriented program design are two such models. Other models like the concurrent program- ming model required specific support features in the operating system. Advent of the Internet motivated setting up of web-enabled servers, which required networking support, an ability to interact with programs in other computer systems, and an abil- ity to scale up or scale down the performance of a server in response to the amount of load directed at it. Users and their organizations invest considerable time and effort in setting up their applications through an operating system. This investment must be protected when new application areas and new computer technologies develop, so system soft- ware needs to evolve to provide new features and support new application areas through new computer technologies. 1.2.2 Efficient Use The system software must ensure efficient use of the fundamental resources of the ‘computer system such as the CPU, memory, disks and other input-output devices. Poor efficiency can result if a program does not use a resource allocated to it, e.g., if memory or input-output devices allocated to a program remain idle. Such a situ- ation may have a snowballing effect: Since the resource is allocated to a program, it is denied to other programs that need it. These programs cannot execute, hence resources allocated to them also remain idle. In addition, overhead of the operating system also reduces the resources available to user programs. To achieve good effi- ciency, the system software must minimize the waste of resources by programs and also minimize its own overhead. 1.2.3. Non-interference ‘The system software of a computer must ensure that no person can illegally use pro- grams and resources in the system, or interfere with them in any manner. The security function counters threats of illegal use or interference that are posed by persons or programs outside the control of an operating system, whereas the protection function counters similar threats posed by its users. Figure 1.2 illustrates how security and protection threats arise in a computer system. Ina classical stand-alone environment, a computer system functions in complete isolation. In such a system, security and protection issues can be handled easily. The identity of a person wishing to use a computer system is verified through a password when the person logs in. This action, which is called authentication, ensures that no person other than a registered user can use a computer system. Consequently, secu-Introduction 7 Computer system Seciitty Resources Intruder R__threats, | Programs Authentication / Figure 1.2. Overview of security and protection threats rity threats do not arise in the system if the authentication procedure is foolproof. The operating system thwarts disruption of its own services and of other programs’ exe- cution with the help of hardware features such as memory protection. To thwart inter- ference with users’ files containing programs or data, the operating system allows a user to specify which other users can access which of her files. This action is called authoriation of access. The operating system blocks an unauthorized access to a file and aborts the program that made the access. When a computer system is connected to the Internet, and a user downloads a program from the Internet, there is a danger that the downloaded program may inter- fere with other programs or resources in the system. This is a security threat because the interference is caused by some person outside the system, called an intruder, who either wrote the downloaded program, or modified it, so that it would interfere with other programs. Such security threats are posed through either a Trojan horse, which is a program that has a known legitimate function and a well-disguised malicious function, or a virus, which is a piece of code with a malicious function that attaches itself to other programs in the system and spreads to other systems when such pro- grams are copied. Another class of security threats is posed by programs called worms, which replicate by themselves through holes in security set-ups of operat- ing systems. Worms can replicate at unimaginably high rates and cause widespread havoc. The Code Red worm of 2001 spread to a quarter of a million computer sys- tems in nine hours. Operating systems address security threats through a variety of means—by using sophisticated authentication techniques, by plugging security holes when they are discovered, by ensuring that programs cannot be modified while they are being copied over the Intemet, and by using Internet jirewalls to filter out unwanted In- ternet traffic through a computer system. Users are expected to contribute to security8 Systems Programming by using passwords that are impossible to guess and by exercising caution while downloading programs from the Internet. 13 SYSTEM PROGRAMS AND SYSTEMS PROGRAMMING ‘As mentioned in Section 1.1, system software is actually a collection of programs. Each program in this collection is called a system program. It plays a role in the effective servicing of users’ computational needs on a computer system. The term ‘servicing’ here includes all activities in the creation of a program and its processing by the computer system, namely, editing, storage, translation, relocation, linking and eventual execution. Since system programs perform such diverse functions, one wonders whether they have anything in common, Actually, system programs do not have any common functionalities but they share some fundamental goals. Let us see what these goals are. ‘Toa user writing a program fora specific problem at hand, the program is merely a means to obiain the results of the problem. So long as the program works correctly, the nature and characteristics of the program may be immaterial to her. Thus, effi- ciency, elegance, and structure of the program are of no consequence. On the con- trary, the writing of a system program is not merely a means to an end, it is an end in itself. Accordingly, a system program has the following design goals: ‘© The program should function correctly under all conditions. © The program should be effective in its computing environment. A system program also has two optional goals: © The program should be portable. © The program should be able to evolve to provide new functionalities and adapt to new technologies. Systems programming is the set of techniques used to realize these design goals. The second design goal, namely, effectiveness in a computing environment, leads to a balancing of the human and computer costs involved in developing or using a program, It may result in trading off a bit of user convenience to achieve execution efficiency or trading off a bit of execution efficiency to achieve user convenience. Note that the balancing of costs is performed for a specific computing environment and at a particular point in time, The trade-offs change as these factors change. It is evident when we discuss various kinds of system software in the following sections. 1.4 THE WONDERLAND OF SYSTEM SOFTWARE From the previous section it would appear that system software is a three-dimensional space with user convenience, efficient use and non-interference as the three axes and ities along each of the three axes. In this conception, it would even be possible toIntroduction 9 compare two system programs to decide which of them is ‘better’. However, reality is more complex than this conception for several reasons. An axis may not be homogeneous, so its calibration would be subjective and contentious. For example, how do we place the six facets of user convenience shown in Table 1.1 along the convenience axis in a non-controversial manner? Should we consider the ability to evolve more important than having web-oriented features? Similarly, given that a computer has several kinds of resources such as the CPU, memory and input-output devices, how do you assess efficient use of resources? Is. one kind of resource more or less important than another kind? We could resolve this difficulty by developing aresource utilization function in which each kind of resource is a parameter. But if we did that we would have to decide how much weightage to assign to each of the resource kinds, and so on. The second reason is that the nature of the computing environment in which a system program is used decides how it rates along each of the axes. For example, the computational needs of a user decide what facet of user convenience and efficiency are relevant. Consequently, a system program cannot be rated uniquely along the three axes. Due to these reasons, the question “Should system program A be preferred over system program B?” does not have a unique answer. In some situations A would be preferred while in some others B would be preferred. The purpose of studying system software is to know which of the two should be preferred in a specific situation. In the following sections we consider aspects which influence answers to this question. After a reader has gained a perspective for answering this question, she should try to answer the higher-level question “Under what situations should system program A. be preferred over system program B?” 1.4.1 The Program Development and Production Environments In a program development environment, users are engaged in developing programs to meet their computational needs. A user makes a trial run of her program to discover the presence of bugs, modifies the program to fix the bugs and makes further trial runs and so on until no new bugs can be discovered, In a production environment, the users merely execute already developed programs on one or more sets of data each to produce useful results; none of the programs face any modification. A compiler and an interpreter are two system programs that can be used to execute programs in these environments. The compiler translates a program P written in a higher level programming language L into the machine language of a computer. Thus, it generates a machine language program that can be executed later. The inter- preter does not generate a machine language program; instead it analyzes program P and directly carries out the computation described in it. ‘To understand comparative efficiency of a compiler and an interpreter, let us consider how they function: The compiler analyzes each statement in program P and generates a sequence of instructions in the machine language that would realize -meaning of the statement when executed, by computing values, making decisions10 Systems Programming or performing input-output. Thus, there are two distinct phases in the execution of a program by using a compiler: The program is compiled in the first phase and the generated instructions are executed in the second phase. The interpreter works differently. It keeps track of which statement in P should be executed next, analyzes the statement and itself carries out the computation described in it. The actions of the compiler and the interpreter seem similar, hence one might expect that their use would be equally efficient. However, it is not so. Consider a statement situated in a loop. The compiler would analyze the statement only once while generating the machine language instructions. The interpreter would analyze the statement every time it is encountered during execution, so it would analyze it many times because of the loop. It leads to a larger overhead during interpretation, so actually the interpreter would make less efficient use of a computer’s resources than the compiler. However, use of an interpreter is more efficient than use of a compiler in a pro- gram development environment. Let us illustrate this through an example. Let the program P under consideration have 1000 statements in it and let some of them be en- closed in a loop. Consider a trial run of P that requires execution of 100 statements— the loop iterates 10 times, with each iteration involving execution of 6 statements, and a few statements located in other parts of the program are also executed. Let a few statements of P be modified between successive trial runs, If a compiler is used, it would have to recompile the program even if a single statement is modified. So it would have to compile all 1000 statements before the next trial run. If an interpreter is used, it would not incur the recompilation cost, but it would analyze some state- ments in the loop more than once during the trial run, However, the time spent by the compiler in recompilation of the program would be more than the time consumed by the interpreter in interpreting 100 statements during the trial run. Hence use of the interpreter is more efficient in a program development environment. A program development environment has another distinctive feature called debugging support which facilitates debugging of programs. The debugging sup- port provides means for collecting information about how values are computed and used in a program and for using it to locate a bug. A primitive debugging support may allow a programmer to specify important statements and variables in a program. Using this information, it prints values of those variables when any of the important statements is executed. However, it would produce voluminous output if the program contained loops, which would make debugging cumbersome. An alternative form of debugging support provides an interactive means of debugging. It provides a capa- bility for suspending execution of the program when any of the important statements is encountered during execution and letting the user examine values of relevant vari- ables. This form of debugging support is implemented by making several checks during execution of the program, so it slows down execution; however, it helps to improve the productivity of programmers. An interpreter can provide debugging support easily because it knows which statement is being executed at any time and what values variables have.