Operating Systems Notes.pdf

Operating System DCAP403 OPERATING SYSTEM  Copyright © 2011 Anindita Hazra All rights reserved Produced & Printed by EXCEL BOOKS PRIVATE LIMITED A-45, Naraina, Phase-I, New Delhi-110028 for Lovely Professional University Phagwara ...

Operating System DCAP403 OPERATING SYSTEM  Copyright © 2011 Anindita Hazra All rights reserved Produced & Printed by EXCEL BOOKS PRIVATE LIMITED A-45, Naraina, Phase-I, New Delhi-110028 for Lovely Professional University Phagwara  SYLLABUS Operating System Objectives: In order to meet the ever increasing need of computers, study of operating system is compulsory. This is core technology subject and the knowledge of which is absolutely essential for Computer Engineers. It familiarizes the students with the concepts and functions of operating system. This subject provides knowledge to develop systems using advanced operating system concepts. To learn the evolution of Operating systems. To study the operations performed by Operating System as a resource manager. To study computer security issues and Operating System tools. 1. Introduction: Operating system Meaning, Supervisor & User mode, operating system operations & Functions, Types of OS: Single-processor system, multiprogramming, Multiprocessing, Multitasking, Parallel, Distributed, RTOS etc. 2. Operating System Structure: OS Services, System Calls, System Programs, OS Structures, layered structure Virtual machines, 3. Processes: Process Concept, PCB, Operation on Processes, Cooperating Processes, Inter process Communication, Process Communication in Client Server Environment. Threads: Concept of Thread, Kernel level & User level threads, Multithreading, Thread Libraries, Threading Issues 4. Scheduling: scheduling criteria, scheduling algorithms, Type of Scheduling: Long term, Short term & Medium term scheduling, multi-processor scheduling algorithm, thread scheduling, 5. Process Synchronization: Critical Section problem, semaphores, monitors, Deadlock characterization, Handling of deadlocks - deadlock prevention, avoidance, detection, recovery from deadlock. 6. Memory Management: Logical & Physical Address space, Swapping, Contiguous memory allocation, paging, segmentation, Virtual memory, demand paging, Page replacement & Page Allocation algorithms, thrashing, Performance issues 7. File Management: File concepts, access methods, directory structure, file system mounting, file sharing, protection, Allocation methods, Free space Mgt., Directory Implementation. 8. I/O & Secondary Storage Structure: I/O H/W, Application I/O Interface, Kernel I/O subsystem, Disk Scheduling, disk management, swap-space management, RAID structure. 9. System Protection: Goals of protection, Access matrix and its implementation, Access control and revocation of access rights, capability-based systems 10. System Security: Security problem, program threats, system and network threats, cryptography as a security tools, user authentication, implementing security defenses, firewalling to protect systems and networks. Case studies Windows OS, Linux or any other OS  CONTENTS Unit 1: Introduction to Operating System 1 Unit 2: Operation and Function of Operating System 14 Unit 3: Operating System Structure 29 Unit 4: Process Management 48 Unit 5: Scheduling 70 Unit 6: Process Synchronization 96 Unit 7: Memory Management 119 Unit 8: File Management 139 Unit 9: I/O & Secondary Storage Structure 159 Unit 10: System Protection 182 Unit 11: System Security 200 Unit 12: Security Solution 225 Unit 13: Case Study: Linux 241 Unit 14: Windows 2000 300  Unit 1: Introduction to Operating System Unit 1: Introduction to Operating System Notes CONTENTS Objectives Introduction 1.1 Operating System: Meaning 1.2 History of Computer Operating Systems 1.3 Supervisor and User Mode 1.4 Goals of an Operating System 1.5 Generations of Operating Systems 1.5.1 0th Generation 1.5.2 First Generation (1951-1956) 1.5.3 Second Generation (1956-1964) 1.5.4 Third Generation (1964-1979) 1.5.5 Fourth Generation (1979 – Present) 1.6 Summary 1.7 Keywords 1.8 Self Assessment 1.9 Review Questions 1.10 Further Readings Objectives After studying this unit, you will be able to: Define operating system Know supervisor and user mode Explain various goals of an operating system Describe generation of operating systems Introduction An Operating System (OS) is a collection of programs that acts as an interface between a user of a computer and the computer hardware. The purpose of an operating system is to provide an environment in which a user may execute the programs. Operating Systems are viewed as resource managers. The main resource is the computer hardware in the form of processors, storage, input/output devices, communication devices, and data. Some of the operating system functions are: implementing the user interface, sharing hardware among users, allowing users to share data among themselves, preventing users from interfering with one another, scheduling resources among users, facilitating input/output, recovering from errors, accounting for resource usage, facilitating parallel operations, organising data for secure and rapid access, and handling network communications. LOVELY PROFESSIONAL UNIVERSITY 1 Operating System Notes 1.1 Operating System: Meaning An operating system (sometimes abbreviated as “OS”) is the program that, after being initially loaded into the computer by a boot program, manages all the other programs in a computer. The other programs are called applications or application programs. The application programs make use of the operating system by making requests for services through a defined Application Program Interface (API). In addition, users can interact directly with the operating system through a user interface such as a command language or a Graphical User Interface (GUI). Figure 1.1: Operating System Interface Hard Drive Computer Mouse Operating System Monitor Video Card Sound Card Keyboard Speakers In a computer system, you find four main components: the hardware, the operating system, the application software and the users. In a computer system, the hardware provides the basic computing resources. The applications programs define the way in which these resources are used to solve the computing problems of the users. The operating system controls and coordinates the use of the hardware among the various systems programs and application programs for the various users. You can view an operating system as a resource allocator. A computer system has many resources (hardware and software) that may be required to solve a problem: CPU time, memory space, files storage space, input/output devices etc. The operating system acts as the manager of these resources and allocates them to specific programs and users as necessary for their tasks. Since there may be many, possibly conflicting, requests for resources, the operating system must decide which requests are allocated resources to operate the computer system fairly and efficiently. An operating system is a control program. This program controls the execution of user programs to prevent errors and improper use of the computer. Operating systems exist because: they are a reasonable way to solve the problem of creating a usable computing system. The fundamental goal of a computer system is to execute user programs and solve user problems. While there is no universally agreed upon definition of the concept of an operating system, the following is a reasonable starting point: A computer’s operating system is a group of programs designed to serve two basic purposes: 1. To control the allocation and use of the computing system’s resources among the various users and tasks, and 2. To provide an interface between the computer hardware and the programmer that simplifies and makes feasible the creation, coding, debugging, and maintenance of application programs. 2 LOVELY PROFESSIONAL UNIVERSITY  Unit 1: Introduction to Operating System An effective operating system should accomplish the following functions: Notes 1. Should act as a command interpreter by providing a user friendly environment. 2. Should facilitate communication with other users. 3. Facilitate the directory/file creation along with the security option. 4. Provide routines that handle the intricate details of I/O programming. 5. Provide access to compilers to translate programs from high-level languages to machine language. 6. Provide a loader program to move the compiled program code to the computer’s memory for execution. 7. Assure that when there are several active processes in the computer, each will get fair and non-interfering access to the central processing unit for execution. 8. Take care of storage and device allocation. 9. Provide for long term storage of user information in the form of files. 10. Permit system resources to be shared among users when appropriate, and be protected from unauthorised or mischievous intervention as necessary. Figure 1.2: Abstract View of the Components of a Computer System User 1 User 2 User 3 User n Compiler Assembler Text editor Database system Application programs Operating System Computer hardware Though systems programs such as editors and translators and the various utility programs (such as sort and file transfer program) are not usually considered part of the operating system, the operating system is responsible for providing access to these system resources. The abstract view of the components of a computer system and the positioning of OS is shown in the Figure 1.2. Task “Operating system is a hardware or software”. Discuss. 1.2 History of Computer Operating Systems Early computers lacked any form of operating system. The user had sole use of the machine and would arrive armed with program and data, often on punched paper and tape. The program would be loaded into the machine, and the machine would be set to work until the program completed or crashed. Programs could generally be debugged via a front panel using switches and lights. It is said that Alan Turing was a master of this on the early Manchester Mark I machine, LOVELY PROFESSIONAL UNIVERSITY 3 Operating System Notes and he was already deriving the primitive conception of an operating system from the principles of the Universal Turing machine. Later machines came with libraries of support code, which would be linked to the user’s program to assist in operations such as input and output. This was the genesis of the modern-day operating system. However, machines still ran a single job at a time; at Cambridge University in England the job queue was at one time a washing line from which tapes were hung with different colored clothes-pegs to indicate job-priority. As machines became more powerful, the time needed for a run of a program diminished and the time to hand off the equipment became very large by comparison. Accounting for and paying for machine usage moved on from checking the wall clock to automatic logging by the computer. Run queues evolved from a literal queue of people at the door, to a heap of media on a jobs-waiting table, or batches of punch-cards stacked one on top of the other in the reader, until the machine itself was able to select and sequence which magnetic tape drives were online. Where program developers had originally had access to run their own jobs on the machine, they were supplanted by dedicated machine operators who looked after the well-being and maintenance of the machine and were less and less concerned with implementing tasks manually. When commercially available computer centers were faced with the implications of data lost through tampering or operational errors, equipment vendors were put under pressure to enhance the runtime libraries to prevent misuse of system resources. Automated monitoring was needed not just for CPU usage but for counting pages printed, cards punched, cards read, disk storage used and for signaling when operator intervention was required by jobs such as changing magnetic tapes. All these features were building up towards the repertoire of a fully capable operating system. Eventually the runtime libraries became an amalgamated program that was started before the first customer job and could read in the customer job, control its execution, clean up after it, record its usage, and immediately go on to process the next job. Significantly, it became possible for programmers to use symbolic program-code instead of having to hand-encode binary images, once task-switching allowed a computer to perform translation of a program into binary form before running it. These resident background programs, capable of managing multistep processes, were often called monitors or monitor-programs before the term operating system established itself. An underlying program offering basic hardware-management, software-scheduling and resource-monitoring may seem a remote ancestor to the user-oriented operating systems of the personal computing era. But there has been a shift in meaning. With the era of commercial computing, more and more “secondary” software was bundled in the operating system package, leading eventually to the perception of an operating system as a complete user-system with utilities, applications (such as text editors and file managers) and configuration tools, and having an integrated graphical user interface. The true descendant of the early operating systems is what we now call the “kernel”. In technical and development circles the old restricted sense of an operating system persists because of the continued active development of embedded operating systems for all kinds of devices with a data-processing component, from hand-held gadgets up to industrial robots and real-time control-systems, which do not run user-applications at the front-end. An embedded operating system in a device today is not so far removed as one might think from its ancestor of the 1950s. 1.3 Supervisor and User Mode Single user mode is a mode in which a multiuser computer operating system boots into a single superuser. It is mainly used for maintenance of multi-user environments such as network servers. Some tasks may require exclusive access to shared resources, for example running fsck on a network share. This mode may also be used for security purposes – network services are 4 LOVELY PROFESSIONAL UNIVERSITY  Unit 1: Introduction to Operating System not run, eliminating the possibility of outside interference. On some systems a lost superuser Notes password can be changed by switching to single user mode, but not asking for the password in such circumstances is viewed as a security vulnerability. You are all familiar with the concept of sitting down at a computer system and writing documents or performing some task such as writing a letter. In this instance, there is one keyboard and one monitor that you interact with. Operating systems such as Windows 95, Windows NT Workstation and Windows 2000 professional are essentially single user operating systems. They provide you the capability to perform tasks on the computer system such as writing programs and documents, printing and accessing files. Consider a typical home computer. There is a single keyboard and mouse that accept input commands, and a single monitor to display information output. There may also be a printer for the printing of documents and images. In essence, a single-user operating system provides access to the computer system by a single user at a time. If another user needs access to the computer system, they must wait till the current user finishes what they are doing and leaves. Students in computer labs at colleges or University often experience this. You might also have experienced this at home, where you want to use the computer but someone else is currently using it. You have to wait for them to finish before you can use the computer system. 1.4 Goals of an Operating System The primary objective of a computer is to execute an instruction in an efficient manner and to increase the productivity of processing resources attached with the computer system such as hardware resources, software resources and the users. In other words, you can say that maximum CPU utilisation is the main objective, because it is the main device which is to be used for the execution of the programs or instructions. Brief the goals as: 1. The primary goal of an operating system is to make the computer convenient to use. 2. The secondary goal is to use the hardware in an efficient manner. 1.5 Generations of Operating Systems Operating systems have been evolving over the years. you will briefly look at this development of the operating systems with respect to the evolution of the hardware/architecture of the computer systems in this section. Since operating systems have historically been closely tied with the architecture of the computers on which they run, you will look at successive generations of computers to see what their operating systems were like. You may not exactly map the operating systems generations to the generations of the computer, but roughly it provides the idea behind them. You can roughly divide them into five distinct generations that are characterized by hardware component technology, software development, and mode of delivery of computer services. 1.5.1 0th Generation The term 0th generation is used to refer to the period of development of computing, which predated the commercial production and sale of computer equipment. You consider that the period might be way back when Charles Babbage invented the Analytical Engine. Afterwards the computers by John Atanasoff in 1940; the Mark I, built by Howard Aiken and a group of IBM engineers at Harvard in 1944; the ENIAC, designed and constructed at the University of Pencylvania by LOVELY PROFESSIONAL UNIVERSITY 5 Operating System Notes Wallace Eckert and John Mauchly and the EDVAC, developed in 1944-46 by John Von Neumann, Arthur Burks, and Herman Goldstine (which was the first to fully implement the idea of the stored program and serial execution of instructions) were designed. The development of EDVAC set the stage for the evolution of commercial computing and operating system software. The hardware component technology of this period was electronic vacuum tubes. The actual operation of these early computers took place without the benefit of an operating system. Early programs were written in machine language and each contained code for initiating operation of the computer itself. The mode of operation was called “open-shop” and this meant that users signed up for computer time and when a user’s time arrived, the entire (in those days quite large) computer system was turned over to the user. The individual user (programmer) was responsible for all machine set up and operation, and subsequent clean-up and preparation for the next user. This system was clearly inefficient and dependent on the varying competencies of the individual programmer as operators. 1.5.2 First Generation (1951-1956) The first generation marked the beginning of commercial computing, including the introduction of Eckert and Mauchly’s UNIVAC I in early 1951, and a bit later, the IBM 701 which was also known as the Defence Calculator. The first generation was characterised again by the vacuum tube as the active component technology. Operation continued without the benefit of an operating system for a time. The mode was called “closed shop” and was characterised by the appearance of hired operators who would select the job to be run, initial program load the system, run the user’s program, and then select another job, and so forth. Programs began to be written in higher level, procedure-oriented languages, and thus the operator’s routine expanded. The operator now selected a job, ran the translation program to assemble or compile the source program, and combined the translated object program along with any existing library programs that the program might need for input to the linking program, loaded and ran the composite linked program, and then handled the next job in a similar fashion. Application programs were run one at a time, and were translated with absolute computer addresses that bound them to be loaded and run from these reassigned storage addresses set by the translator, obtaining their data from specific physical I/O device. There was no provision for moving a program to different location in storage for any reason. Similarly, a program bound to specific devices could not be run at all if any of these devices were busy or broken. The inefficiencies inherent in the above methods of operation led to the development of the mono-programmed operating system, which eliminated some of the human intervention in running job and provided programmers with a number of desirable functions. The OS consisted of a permanently resident kernel in main storage, and a job scheduler and a number of utility programs kept in secondary storage. User application programs were preceded by control or specification cards (in those day, computer program were submitted on data cards) which informed the OS of what system resources (software resources such as compilers and loaders; and hardware resources such as tape drives and printer) were needed to run a particular application. The systems were designed to be operated as batch processing system. These systems continued to operate under the control of a human operator who initiated operation by mounting a magnetic tape that contained the operating system executable code onto a “boot device”, and then pushing the IPL (Initial Program Load) or “boot” button to initiate the bootstrap loading of the operating system. Once the system was loaded, the operator entered the date and time, and then initiated the operation of the job scheduler program which read and interpreted the control statements, secured the needed resources, executed the first user 6 LOVELY PROFESSIONAL UNIVERSITY  Unit 1: Introduction to Operating System program, recorded timing and accounting information, and then went back to begin processing Notes of another user program, and so on, as long as there were programs waiting in the input queue to be executed. The first generation saw the evolution from hands-on operation to closed shop operation to the development of mono-programmed operating systems. At the same time, the development of programming languages was moving away from the basic machine languages; first to assembly language, and later to procedure oriented languages, the most significant being the development of FORTRAN by John W. Backus in 1956. Several problems remained, however, the most obvious was the inefficient use of system resources, which was most evident when the CPU waited while the relatively slower, mechanical I/O devices were reading or writing program data. In addition, system protection was a problem because the operating system kernel was not protected from being overwritten by an erroneous application program. Moreover, other user programs in the queue were not protected from destruction by executing programs. 1.5.3 Second Generation (1956-1964) The second generation of computer hardware was most notably characterised by transistors replacing vacuum tubes as the hardware component technology. In addition, some very important changes in hardware and software architectures occurred during this period. For the most part, computer systems remained card and tape-oriented systems. Significant use of random access devices, that is, disks, did not appear until towards the end of the second generation. Program processing was, for the most part, provided by large centralised computers operated under mono-programmed batch processing operating systems. The most significant innovations addressed the problem of excessive central processor delay due to waiting for input/output operations. Recall that programs were executed by processing the machine instructions in a strictly sequential order. As a result, the CPU, with its high speed electronic component, was often forced to wait for completion of I/O operations which involved mechanical devices (card readers and tape drives) that were order of magnitude slower. This problem led to the introduction of the data channel, an integral and special-purpose computer with its own instruction set, registers, and control unit designed to process input/output operations separately and asynchronously from the operation of the computer’s main CPU near the end of the first generation, and its widespread adoption in the second generation. The data channel allowed some I/O to be buffered. That is, a program’s input data could be read “ahead” from data cards or tape into a special block of memory called a buffer. Then, when the user’s program came to an input statement, the data could be transferred from the buffer locations at the faster main memory access speed rather than the slower I/O device speed. Similarly, a program’s output could be written another buffer and later moved from the buffer to the printer, tape, or card punch. What made this all work was the data channel’s ability to work asynchronously and concurrently with the main processor. Thus, the slower mechanical I/O could be happening concurrently with main program processing. This process was called I/O overlap. The data channel was controlled by a channel program set up by the operating system I/O control routines and initiated by a special instruction executed by the CPU. Then, the channel independently processed data to or from the buffer. This provided communication from the CPU to the data channel to initiate an I/O operation. It remained for the channel to communicate to the CPU such events as data errors and the completion of a transmission. At first, this communication was handled by polling – the CPU stopped its work periodically and polled the channel to determine if there is any message. Polling was obviously inefficient (imagine stopping your work periodically to go to the post office to see if an expected letter has arrived) and led to another significant innovation of the LOVELY PROFESSIONAL UNIVERSITY 7 Operating System Notes second generation – the interrupt. The data channel was able to interrupt the CPU with a message – usually “I/O complete.” Infact, the interrupt idea was later extended from I/O to allow signalling of number of exceptional conditions such as arithmetic overflow, division by zero and time-run-out. Of course, interval clocks were added in conjunction with the latter, and thus operating system came to have a way of regaining control from an exceptionally long or indefinitely looping program. These hardware developments led to enhancements of the operating system. I/O and data channel communication and control became functions of the operating system, both to relieve the application programmer from the difficult details of I/O programming and to protect the integrity of the system to provide improved service to users by segmenting jobs and running shorter jobs first (during “prime time”) and relegating longer jobs to lower priority or night time runs. System libraries became more widely available and more comprehensive as new utilities and application software components were available to programmers. In order to further mitigate the I/O wait problem, system were set up to spool the input batch from slower I/O devices such as the card reader to the much higher speed tape drive and similarly, the output from the higher speed tape to the slower printer. In this scenario, the user submitted a job at a window, a batch of jobs was accumulated and spooled from cards to tape “off line,” the tape was moved to the main computer, the jobs were run, and their output was collected on another tape that later was taken to a satellite computer for off line tape-to-printer output. User then picked up their output at the submission windows. Toward the end of this period, as random access devices became available, tape-oriented operating system began to be replaced by disk-oriented systems. With the more sophisticated disk hardware and the operating system supporting a greater portion of the programmer’s work, the computer system that users saw was more and more removed from the actual hardware- users saw a virtual machine. The second generation was a period of intense operating system development. Also it was the period for sequential batch processing. But the sequential processing of one job at a time remained a significant limitation. Thus, there continued to be low CPU utilisation for I/O bound jobs and low I/O device utilisation for CPU bound jobs. This was a major concern, since computers were still very large (room-size) and expensive machines. Researchers began to experiment with multiprogramming and multiprocessing in their computing services called the time-sharing system. Note A noteworthy example is the Compatible Time Sharing System (CTSS), developed at MIT during the early 1960s. Task CPU is the heart of computer system what about ALU. 1.5.4 Third Generation (1964-1979) The third generation officially began in April 1964 with IBM’s announcement of its System/360 family of computers. Hardware technology began to use Integrated Circuits (ICs) which yielded significant advantages in both speed and economy. Operating system development continued with the introduction and widespread adoption of multiprogramming. This marked first by the appearance of more sophisticated I/O buffering 8 LOVELY PROFESSIONAL UNIVERSITY  Unit 1: Introduction to Operating System in the form of spooling operating systems, such as the HASP (Houston Automatic Spooling) Notes system that accompanied the IBM OS/360 system. These systems worked by introducing two new systems programs, a system reader to move input jobs from cards to disk, and a system writer to move job output from disk to printer, tape, or cards. Operation of spooling system was, as before, transparent to the computer user who perceived input as coming directly from the cards and output going directly to the printer. The idea of taking fuller advantage of the computer’s data channel I/O capabilities continued to develop. That is, designers recognised that I/O needed only to be initiated by a CPU instruction – the actual I/O data transmission could take place under control of separate and asynchronously operating channel program. Thus, by switching control of the CPU between the currently executing user program, the system reader program, and the system writer program, it was possible to keep the slower mechanical I/O device running and minimizes the amount of time the CPU spent waiting for I/O completion. The net result was an increase in system throughput and resource utilisation, to the benefit of both user and providers of computer services. This concurrent operation of three programs (more properly, apparent concurrent operation, since systems had only one CPU, and could, therefore execute just one instruction at a time) required that additional features and complexity be added to the operating system. First, the fact that the input queue was now on disk, a direct access device, freed the system scheduler from the first-come-first-served policy so that it could select the “best” next job to enter the system (looking for either the shortest job or the highest priority job in the queue). Second, since the CPU was to be shared by the user program, the system reader, and the system writer, some processor allocation rule or policy was needed. Since the goal of spooling was to increase resource utilisation by enabling the slower I/O devices to run asynchronously with user program processing, and since I/O processing required the CPU only for short periods to initiate data channel instructions, the CPU was dispatched to the reader, the writer, and the program in that order. Moreover, if the writer or the user program was executing when something became available to read, the reader program would preempt the currently executing program to regain control of the CPU for its initiation instruction, and the writer program would preempt the user program for the same purpose. This rule, called the static priority rule with preemption, was implemented in the operating system as a system dispatcher program. The spooling operating system in fact had multiprogramming since more than one program was resident in main storage at the same time. Later this basic idea of multiprogramming was extended to include more than one active user program in memory at time. To accommodate this extension, both the scheduler and the dispatcher were enhanced. The scheduler became able to manage the diverse resource needs of the several concurrently active used programs, and the dispatcher included policies for allocating processor resources among the competing user programs. In addition, memory management became more sophisticated in order to assure that the program code for each job or at least that part of the code being executed, was resident in main storage. The advent of large-scale multiprogramming was made possible by several important hardware innovations such as: 1. The widespread availability of large capacity, high-speed disk units to accommodate the spooled input streams and the memory overflow together with the maintenance of several concurrently active program in execution. 2. Relocation hardware which facilitated the moving of blocks of code within memory without any undue overhead penalty. 3. The availability of storage protection hardware to ensure that user jobs are protected from one another and that the operating system itself is protected from user programs. 4. Some of these hardware innovations involved extensions to the interrupt system in order to handle a variety of external conditions such as program malfunctions, storage protection LOVELY PROFESSIONAL UNIVERSITY 9 Operating System Notes violations, and machine checks in addition to I/O interrupts. In addition, the interrupt system became the technique for the user program to request services from the operating system kernel. 5. The advent of privileged instructions allowed the operating system to maintain coordination and control over the multiple activities now going on with in the system. Successful implementation of multiprogramming opened the way for the development of a new way of delivering computing services-time-sharing. In this environment, several terminals, sometimes up to 200 of them, were attached (hard wired or via telephone lines) to a central computer. Users at their terminals, “logged in” to the central system, and worked interactively with the system. The system’s apparent concurrency was enabled by the multiprogramming operating system. Users shared not only the system hardware but also its software resources and file system disk space. The third generation was an exciting time, indeed, for the development of both computer hardware and the accompanying operating system. During this period, the topic of operating systems became, in reality, a major element of the discipline of computing. 1.5.5 Fourth Generation (1979 – Present) The fourth generation is characterised by the appearance of the personal computer and the workstation. Miniaturisation of electronic circuits and components continued and Large Scale Integration (LSI), the component technology of the third generation, was replaced by Very Large Scale Integration (VLSI), which characterizes the fourth generation. VLSI with its capacity for containing thousands of transistors on a small chip, made possible the development of desktop computers with capabilities exceeding those that filled entire rooms and floors of building just twenty years earlier. The operating systems that control these desktop machines have brought us back in a full circle, to the open shop type of environment where each user occupies an entire computer for the duration of a job’s execution. This works better now, not only because the progress made over the years has made the virtual computer resulting from the operating system/hardware combination so much easier to use, or, in the words of the popular press “user-friendly.” However, improvements in hardware miniaturisation and technology have evolved so fast that you now have inexpensive workstation – class computers capable of supporting multiprogramming and time-sharing. Hence the operating systems that supports today’s personal computers and workstations look much like those which were available for the minicomputers of the third generation. Example: Microsoft’s DOS for IBM-compatible personal computers and UNIX for workstation. However, many of these desktop computers are now connected as networked or distributed systems. Computers in a networked system each have their operating systems augmented with communication capabilities that enable users to remotely log into any system on the network and transfer information among machines that are connected to the network. The machines that make up distributed system operate as a virtual single processor system from the user’s point of view; a central operating system controls and makes transparent the location in the system of the particular processor or processors and file systems that are handling any given program. 1.6 Summary This unit presented the principle operation of an operating system. In this unit you had briefly described about the history, the generations and the types of operating systems. 10 LOVELY PROFESSIONAL UNIVERSITY  Unit 1: Introduction to Operating System An operating system is a program that acts as an interface between a user of a computer Notes and the computer hardware. The purpose of an operating system is to provide an environment in which a user may execute programs. The primary goal of an operating system is to make the computer convenient to use. And the secondary goal is to use the hardware in an efficient manner. 1.7 Keywords An Operating System: It is the most important program in a computer system that runs all the time, as long as the computer is operational and exits only when the computer is shut down. Desktop System: Modern desktop operating systems usually feature a Graphical user interface (GUI) which uses a pointing device such as a mouse or stylus for input in addition to the keyboard. Operating System: An operating system is a layer of software which takes care of technical aspects of a computer’s operation. 1.8 Self Assessment Choose the appropriate answers: 1. GUI stands for (a) Graphical Used Interface (b) Graphical User Interface (c) Graphical User Interchange (d) Good User Interface 2. CPU stands for (a) Central Program Unit (b) Central Programming Unit (c) Central Processing Unit (d) Centralization Processing Unit 3. FORTRAN stands for (a) Formula Translation (b) Formula Transformation (c) Formula Transition (d) Forming Translation 4. VLSI stands for (a) Very Long Scale Integration (b) Very Large Scale Interchange (c) Very Large Scale Interface (d) Very Large Scale Integration LOVELY PROFESSIONAL UNIVERSITY 11 Operating System Notes 5. API stands for (a) Application Process Interface (b) Application Process Interchange (c) Application Program Interface (d) Application Process Interfacing Fill in the blanks: 6. An operating system is a......................... 7. Programs could generally be debugged via a front panel using........................ and lights. 8. The data channel allowed some........................ to be buffered. 9. The third generation officially began in April......................... 10. The system’s apparent concurrency was enabled by the multiprogramming........................ 1.9 Review Questions 1. What is the relation between application software and operating system? 2. What is an operating system? Is it a hardware or software? 3. Mention the primary functions of an operating system. 4. Briefly explain the evolution of the operating system. 5. What are the key elements of an operating system? 6. What do you understand by the term computer generations? 7. Who give the idea of stored program and in which year? Who give the basic structure of computer? 8. Give the disadvantages of first generation computers over second generation computers. 9. On which system, the second generation computers based on? What are the new inventions in the second generation of computers? 10. Describe the term integrated circuit. 11. What is the significance of third generation computers? 12. Give the brief description of fourth generation computers. How the technology is better than previous generation? 13. What is the period of fifth generation computers? 14. What are the differences between hardware and software? 15. What are the differences between system software and application software? Answers: Self Assessment 1. (b) 2. (c) 3. (a) 4. (d) 5. (c) 6. control program 7. switches 8. I/O 9. 1964 10. operating system 12 LOVELY PROFESSIONAL UNIVERSITY  Unit 1: Introduction to Operating System 1.10 Further Readings Notes Books Andrew M. Lister, Fundamentals of Operating Systems, Wiley. Andrew S. Tanenbaum and Albert S. Woodhull, Systems Design and Implementation, Prentice Hall. Andrew S. Tanenbaum, Modern Operating System, Prentice Hall. Colin Ritchie, Operating Systems, BPB Publications. Deitel H.M., “Operating Systems, 2nd Edition, Addison Wesley. I.A. Dhotre, Operating System, Technical Publications. Milankovic, Operating System, Tata MacGraw Hill, New Delhi. Silberschatz, Gagne & Galvin, “Operating System Concepts”, John Wiley & Sons, Seventh Edition. Stalling, W., “Operating Systems”, 2nd Edition, Prentice Hall. Online links www.en.wikipedia.org www.web-source.net www.webopedia.com LOVELY PROFESSIONAL UNIVERSITY 13 Operating System Notes Unit 2: Operation and Function of Operating System CONTENTS Objectives Introduction 2.1 Operations and Functions of OS 2.2 Types of Operating System 2.3 Operating System: Examples 2.3.1 Disk Operating System (DOS) 2.3.2 UNIX 2.3.3 Windows 2.3.4 Macintosh 2.4 Summary 2.5 Keywords 2.6 Self Assessment 2.7 Review Questions 2.8 Further Readings Objectives After studying this unit, you will be able to: Describe operations and functions of operating system Explain various types of operating system Introduction The primary objective of operating system is to increase productivity of a processing resource, such as computer hardware or computer-system users. User convenience and productivity were secondary considerations. At the other end of the spectrum, an OS may be designed for a personal computer costing a few thousand dollars and serving a single user whose salary is high. In this case, it is the user whose productivity is to be increased as much as possible, with the hardware utilization being of much less concern. In single-user systems, the emphasis is on making the computer system easier to use by providing a graphical and hopefully more intuitively obvious user interface. 2.1 Operations and Functions of OS The main operations and functions of an operating system are as follows: 1. Process Management 2. Memory Management 3. Secondary Storage Management 4. I/O Management 14 LOVELY PROFESSIONAL UNIVERSITY  Unit 2: Operation and Function of Operating System 5. File Management Notes 6. Protection 7. Networking Management 8. Command Interpretation. Process Management The CPU executes a large number of programs. While its main concern is the execution of user programs, the CPU is also needed for other system activities. These activities are called processes. A process is a program in execution. Typically, a batch job is a process. A time-shared user program is a process. A system task, such as spooling, is also a process. For now, a process may be considered as a job or a time-shared program, but the concept is actually more general. The operating system is responsible for the following activities in connection with processes management: 1. The creation and deletion of both user and system processes 2. The suspension and resumption of processes. 3. The provision of mechanisms for process synchronization 4. The provision of mechanisms for deadlock handling. Memory Management Memory is the most expensive part in the computer system. Memory is a large array of words or bytes, each with its own address. Interaction is achieved through a sequence of reads or writes of specific memory address. The CPU fetches from and stores in memory. There are various algorithms that depend on the particular situation to manage the memory. Selection of a memory management scheme for a specific system depends upon many factors, but especially upon the hardware design of the system. Each algorithm requires its own hardware support. The operating system is responsible for the following activities in connection with memory management. 1. Keep track of which parts of memory are currently being used and by whom. 2. Decide which processes are to be loaded into memory when memory space becomes available. 3. Allocate and deallocate memory space as needed. Secondary Storage Management The main purpose of a computer system is to execute programs. These programs, together with the data they access, must be in main memory during execution. Since the main memory is too small to permanently accommodate all data and program, the computer system must provide secondary storage to backup main memory. Most modem computer systems use disks as the primary on-line storage of information, of both programs and data. Most programs, like compilers, assemblers, sort routines, editors, formatters, and so on, are stored on the disk until loaded into memory, and then use the disk as both the source and destination of their processing. Hence the proper management of disk storage is of central importance to a computer system. LOVELY PROFESSIONAL UNIVERSITY 15 Operating System Notes There are few alternatives. Magnetic tape systems are generally too slow. In addition, they are limited to sequential access. Thus tapes are more suited for storing infrequently used files, where speed is not a primary concern. The operating system is responsible for the following activities in connection with disk management: 1. Free space management 2. Storage allocation 3. Disk scheduling. I/O Management One of the purposes of an operating system is to hide the peculiarities or specific hardware devices from the user. For example, in UNIX, the peculiarities of I/O devices are hidden from the bulk of the operating system itself by the I/O system. The operating system is responsible for the following activities in connection to I/O management: 1. A buffer caching system 2. To activate a general device driver code 3. To run the driver software for specific hardware devices as and when required. File Management File management is one of the most visible services of an operating system. Computers can store information in several different physical forms: magnetic tape, disk, and drum are the most common forms. Each of these devices has it own characteristics and physical organisation. For convenient use of the computer system, the operating system provides a uniform logical view of information storage. The operating system abstracts from the physical properties of its storage devices to define a logical storage unit, the file. Files are mapped, by the operating system, onto physical devices. A file is a collection of related information defined by its creator. Commonly, files represent programs (both source and object forms) and data. Data files may be numeric, alphabetic or alphanumeric. Files may be free-form, such as text files, or may be rigidly formatted. In general a files is a sequence of bits, bytes, lines or records whose meaning is defined by its creator and user. It is a very general concept. The operating system implements the abstract concept of the file by managing mass storage device, such as types and disks. Also files are normally organised into directories to ease their use. Finally, when multiple users have access to files, it may be desirable to control by whom and in what ways files may be accessed. The operating system is responsible for the following activities in connection to the file management: 1. The creation and deletion of files. 2. The creation and deletion of directory. 3. The support of primitives for manipulating files and directories. 4. The mapping of files onto disk storage. 5. Backup of files on stable (non volatile) storage. 6. Protection and security of the files. 16 LOVELY PROFESSIONAL UNIVERSITY  Unit 2: Operation and Function of Operating System Protection Notes The various processes in an operating system must be protected from each other’s activities. For that purpose, various mechanisms which can be used to ensure that the files, memory segment, CPU and other resources can be operated on only by those processes that have gained proper authorisation from the operating system. Example: Memory addressing hardware ensures that a process can only execute within its own address space. The timer ensures that no process can gain control of the CPU without relinquishing it. Finally, no process is allowed to do its own I/O, to protect the integrity of the various peripheral devices. Protection refers to a mechanism for controlling the access of programs, processes, or users to the resources defined by a computer controls to be imposed, together with some means of enforcement. Protection can improve reliability by detecting latent errors at the interfaces between component subsystems. Early detection of interface errors can often prevent contamination of a healthy subsystem by a subsystem that is malfunctioning. An unprotected resource cannot defend against use (or misuse) by an unauthorised or incompetent user. Task “Memory is the most expensive part of system.” Discuss. Networking A distributed system is a collection of processors that do not share memory or a clock. Instead, each processor has its own local memory, and the processors communicate with each other through various communication lines, such as high speed buses or telephone lines. Distributed systems vary in size and function. They may involve microprocessors, workstations, minicomputers, and large general purpose computer systems. The processors in the system are connected through a communication network, which can be configured in the number of different ways. The network may be fully or partially connected. The communication network design must consider routing and connection strategies and the problems of connection and security. A distributed system provides the user with access to the various resources the system maintains. Access to a shared resource allows computation speed-up, data availability, and reliability. Command Interpretation One of the most important components of an operating system is its command interpreter. The command interpreter is the primary interface between the user and the rest of the system. Many commands are given to the operating system by control statements. When a new job is started in a batch system or when a user logs-in to a time-shared system, a program which reads and interprets control statements is automatically executed. This program is variously called (1) the control card interpreter, (2) the command line interpreter, (3) the shell (in Unix), and so on. Its function is quite simple: get the next command statement, and execute it. The command statements themselves deal with process management, I/O handling, secondary storage management, main memory management, file system access, protection, and networking. LOVELY PROFESSIONAL UNIVERSITY 17 Operating System Notes The Figure 2.1 depicts the role of the operating system in coordinating all the functions. Figure 2.1: Functions Coordinated by the Operating System I/O Management File Protection & Security Management Process Secondary Management Storage Management Operating System Communication Management Memory User Management Interface Networking 2.2 Types of Operating System Modern computer operating systems may be classified into three groups, which are distinguished by the nature of interaction that takes place between the computer user and his or her program during its processing. The three groups are called batch, time-sharing and real-time operating systems. Batch Processing Operating System In a batch processing operating system environment users submit jobs to a central place where these jobs are collected into a batch, and subsequently placed on an input queue at the computer where they will be run. In this case, the user has no interaction with the job during its processing, and the computer’s response time is the turnaround time the time from submission of the job until execution is complete, and the results are ready for return to the person who submitted the job. Time Sharing Another mode for delivering computing services is provided by time sharing operating systems. In this environment a computer provides computing services to several or many users concurrently on-line. Here, the various users are sharing the central processor, the memory, and other resources of the computer system in a manner facilitated, controlled, and monitored by the operating system. The user, in this environment, has nearly full interaction with the program during its execution, and the computer’s response time may be expected to be no more than a few second. Real-time Operating System (RTOS) The third class is the real time operating systems, which are designed to service those applications where response time is of the essence in order to prevent error, misrepresentation or even disaster. Examples of real time operating systems are those which handle airlines reservations, machine tool control, and monitoring of a nuclear power station. The systems, in this case, are designed to be interrupted by external signals that require the immediate attention of the computer system. 18 LOVELY PROFESSIONAL UNIVERSITY  Unit 2: Operation and Function of Operating System These real time operating systems are used to control machinery, scientific instruments and Notes ndustrial systems. An RTOS typically has very little user-interface capability, and no end-user utilities. A very important part of an RTOS is managing the resources of the computer so that a particular operation executes in precisely the same amount of time every time it occurs. In a complex machine, having a part move more quickly just because system resources are available may be just as catastrophic as having it not move at all because the system is busy. A number of other definitions are important to gain an understanding of operating systems: Multiprogramming Operating System A multiprogramming operating system is a system that allows more than one active user program (or part of user program) to be stored in main memory simultaneously. Thus, it is evident that a time-sharing system is a multiprogramming system, but note that a multiprogramming system is not necessarily a time-sharing system. A batch or real time operating system could, and indeed usually does, have more than one active user program simultaneously in main storage. Another important, and all too similar, term is “multiprocessing”. Figure 2.2: Memory Layout in Multiprogramming Environment Primary Memory MONITOR PROGRAM 1 PROGRAM 2...... PROGRAM N Buffering and Spooling improve system performance by overlapping the input, output and computation of a single job, but both of them have their limitations. A single user cannot always keep CPU or I10 devices busy at all times. Multiprogramming offers a more efficient approach to increase system performance. In order to increase the resource utilisation, systems supporting multiprogramming approach allow more than one job (program) to reside in the memory to utilise CPU time at any moment. More number of programs competing for system resources better will mean better resource utilisation. The idea is implemented as follows. The main memory of a system contains more than one program (Figure 2.2). The operating system picks one of the programs and starts executing. During execution of program 1 it needs some I/O operation to complete in a sequential execution environment (Figure 2.3a). The CPU would then sit idle whereas in a multiprogramming system, (Figure 2.3b) the operating system will simply switch over to the next program (program 2). LOVELY PROFESSIONAL UNIVERSITY 19 Operating System Notes Figure 2.3: Multiprogramming Program 1 Program 2 Idle Idle Idle Idle P1 P1 P1 P2 P2 P2 (a) Sequential Execution Program 1 P1 P1 P1 Program 2 (b) Execution in Multiprogramming Environment When that program needs to wait for some 110 operation, it switches over to program 3 and so on. If there is no other new program left in the main memory, the CPU will pass its control back to the previous programs. Multiprogramming has traditionally been employed to increase the resources utilisation of a computer system and to support multiple simultaneously interactive users (terminals). Multiprocessing System A multiprocessing system is a computer hardware configuration that includes more than one independent processing unit. The term multiprocessing is generally used to refer to large computer hardware complexes found in major scientific or commercial applications. A multiprocessor system is simply a computer that has >1 & not 0 THEN S := S – 1 ELSE (wait on S) The V (or signal or wakeup or up) operation on semaphore S, written as V(S) or signal (S), operates as follows: V(S): IF (one or more process are waiting on S) THEN (let one of these processes proceed) ELSE S := S + 1 Operations P and V are done as single, indivisible, atomic action. It is guaranteed that once a semaphore operations has stared, no other process can access the semaphore until operation has completed. Mutual exclusion on the semaphore, S, is enforced within P(S) and V(S). If several processes attempt a P(S) simultaneously, only process will be allowed to proceed. The other processes will be kept waiting, but the implementation of P and V guarantees that processes will not suffer indefinite postponement. Semaphores solve the lost-wakeup problem. Producer-Consumer Problem using Semaphores The Solution to producer-consumer problem uses three semaphores, namely, full, empty and mutex. The semaphore ‘full’ is used for counting the number of slots in the buffer that are full. The ‘empty’ for counting the number of slots that are empty and semaphore ‘mutex’ to make sure that the producer and consumer do not access modifiable shared section of the buffer simultaneously. Initialization 1. Set full buffer slots to 0. i.e., semaphore Full = 0. 2. Set empty buffer slots to N. i.e., semaphore empty = N. 3. For control access to critical section set mutex to 1. i.e., semaphore mutex = 1. Producer ( ) WHILE (true) produce-Item ( ); P (empty); P (mutex); enter-Item ( ) 102 LOVELY PROFESSIONAL UNIVERSITY  Unit 6: Process Synchronization V (mutex) Notes V (full); Consumer ( ) WHILE (true) P (full) P (mutex); remove-Item ( ); V (mutex); V (empty); consume-Item (Item) A semaphore is hardware or a software tag variable whose value indicates the status of a common resource. Its purpose is to lock the resource being used. A process which needs the resource will check the semaphore for determining the status of the resource followed by the decision for proceeding. In multitasking operating systems, the activities are synchronized by using the semaphore techniques. Semaphore is a machanism to resolve resources conflicts by tallying resource seekers what is the state of sought resources, achieving a mutual exclusive access to resources. Often semaphore operates as a type of mutual exclusive counters (such as mutexes) where it holds a number of access keys to the resources. Process that seeks the resources must obtain one of those access keys, one of semaphores, before it proceeds further to utilize the resource. If there is no more such a key available to the process, it has to wait for the current resource user to release the key. A semaphore could have the value 0,indicating that no wakeups were saved, or some positive values if one or more wakeups were pending. A semaphore s is an integer variable that apart from initialization, is accesssed only through two standard atomic operations, wait and signal. these operations were orignially termed p(for wait to test) and v(for signal to increment). The classical defination of wait in psedocode is: wait(s) { while(s think() writes(“age=”, age(), “, philosopher “, i, “ is hungry\n”) dcap.take_forks(i) writes(“age=”, age(), “, philosopher “, i, “ has taken forks\n”) eat() dcap.put_forks(i) writes(“age=”, age(), “, philosopher “, i, “ has returned forks\n”) od end phil end philosopher resource dining_server op take_forks(i : int), put_forks(i : int) body dining_server(num_phil : int) write(“dining server for”, num_phil, “philosophers is alive”) sem mutex := 1 type states = enum(thinking, hungry, eating) var state[1:num_phil] : states := ([num_phil] thinking) sem phil[1:num_phil] := ([num_phil] 0) procedure left(i : int) returns lft : int if i=1 -> lft := num_phil [] else -> lft := i-1 fi 104 LOVELY PROFESSIONAL UNIVERSITY  Unit 6: Process Synchronization end left Notes procedure right(i : int) returns rgh : int if i=num_phil -> rgh := 1 [] else -> rgh := i+1 fi end right procedure test(i : int) if state[i] = hungry and state[left(i)] ~= eating and state[right(i)] ~= eating -> state[i] := eating V(phil[i]) fi end test proc take_forks(i) P(mutex) state[i] := hungry test(i) V(mutex) P(phil[i]) end take_forks proc put_forks(i) P(mutex) state[i] := thinking test(left(i)); test(right(i)) V(mutex) end put_forks end dining_server resource start() import philosopher, dining_server var num_phil : int := 5, run_time : int := 60 getarg(1, num_phil); getarg(2, run_time) var max_think_delay[1:num_phil] : int := ([num_phil] 5) var max_eat_delay[1:num_phil] : int := ([num_phil] 2) fa i := 1 to num_phil -> getarg(2*i+1, max_think_delay[i]); getarg(2*i+2, max_eat_delay[i]) af var dcap : cap dining_server write(num_phil, “dining philosophers running”, run_time, “seconds”) dcap := create dining_server(num_phil) fa i := 1 to num_phil -> create philosopher(i, dcap, max_think_delay[i], max_eat_delay[i]) af nap(1000*run_time); write(“must stop now”); stop end start 108 LOVELY PROFESSIONAL UNIVERSITY  Unit 6: Process Synchronization 6.4 Monitors Notes A monitor is a software synchronization tool with high-level of abstraction that provides a convenient and effective mechanism for process synchronization. It allows only one process to be active within the monitor at a time. One simple implementation is shown below. monitor monitor_name { // shared variable declarations procedure P1 (…) { …. } … procedure Pn(…) {……} Initialization code ( ….) { …} … } 6.5 Deadlock Deadlock occurs when you have a set of processes [not necessarily all the processes in the system], each holding some resources, each requesting some resources, and none of them is able to obtain what it needs, i.e. to make progress. Those processes are deadlocked because all the processes are waiting. None of them will ever cause any of the events that could wake up any of the other members of the set, and all the processes continue to wait forever. For this model, I assume that processes have only a single thread and that there are no interrupts possible to wake up a blocked process. The no-interrupts condition is needed to prevent an otherwise deadlocked process from being awakened by, say, an alarm, and then causing events that release other processes in the set. In most cases, the event that each process is waiting for is the release of some resource currently possessed by another member of the set. In other words, each member of the set of deadlocked processes is waiting for a resource that is owned by another deadlocked process. None of the processes can run, none of them can release any resources, and none of them can be awakened. The number of processes and the number and kind of resources possessed and requested are unimportant. This result holds for any kind of resource, including both hardware and software. Figure 6.4: Processes are in Deadlock Situation Waiting Resource Owned for X X by B Process Process A B Resource Waiting Owned Y for Y by A LOVELY PROFESSIONAL UNIVERSITY 109 Operating System Notes 6.6 Deadlock Characterization Necessary Conditions Deadlock situation can arise if the following four conditions hold simultaneously in a system: 1. Resources are used in mutual exclusion. 2. Resources are acquired piecemeal (i.e. not all the resources that are needed to complete an activity are obtained at the same time in a single indivisible action). 3. Resources are not preempted (i.e. a process does not take away resources being held by another process). 4. Resources are not spontaneously given up by a process until it has satisfied all its outstanding requests for resources (i.e. a process, being that it cannot obtain some needed resource it does not kindly give up the resources that it is currently holding). Resource Allocation Graphs Resource Allocation Graphs (RAGs) are directed labeled graphs used to represent, from the point of view of deadlocks, the current state of a system. RESOURCE ALLOCATION GRAPHS Process [reusable] Resources with multiplicity 2 Request Edge from process Pi to resource Rj Pi Rj Assignment Edge from resource Rj to process Pi Pi Rj R1 P1 P1 holds two copies of resource R1, and P2 holds one copy of resource R1 and P2 requests one copy of R2 R2 State transitions can be represented as transitions between the corresponding resource allocation graphs. Here are the rules for state transitions: 1. Request: If process Pi has no outstanding request, it can request simultaneously any number (up to multiplicity) of resources R1, R2,..Rm. The request is represented by adding appropriate requests edges to the RAG of the current state. 2. Acquisition: If process Pi has outstanding requests and they can all be simultaneously satisfied, then the request edges of these requests are replaced by assignment edges in the RAG of the current state 3. Release: If process Pi has no outstanding request then it can release any of the resources it is holding, and remove the corresponding assignment edges from the RAG of the current state. 110 LOVELY PROFESSIONAL UNIVERSITY  Unit 6: Process Synchronization Here are some important propositions about deadlocks and resource allocation graphs: Notes 1. If a RAG of a state of a system is fully reducible (i.e. it can be reduced to a graph without any edges using ACQUISITION and RELEASE operations) then that state is not a deadlock state. 2. If a state is not a deadlock state then its RAG is fully reducible [this holds only if you are dealing with reusable resources; it is false if you have consumable resources] 3. A cycle in the RAG of a state is a necessary condition for that being a deadlock state 4. A cycle in the RAG of a state is a sufficient condition for that being a deadlock state only in the case of reusable resources with multiplicity one. Example: Here is an example of reduction of a RAG: R1 P2 R1  P1 P3 P1 P3 R2 R2  R1 R1  P1 P3 P3 R2 R2  R1 P3  R2 Reduction of a RAG And here is a deadlock-free system with a loop. R1 P1 P2 R2 P3 RAG with Loop but no Deadlock Task A monitor is a software synchronization tool or hardware synchronization tool. LOVELY PROFESSIONAL UNIVERSITY 111 Operating System Notes 6.7 Handling of Deadlocks There are several ways to address the problem of deadlock in an operating system. 1. Prevent 2. Avoid 3. Detection and recovery 4. Ignore 6.7.1 Deadlock Prevention Deadlocks can be prevented by ensuring that at least one of the following four conditions occur: 1. Mutual exclusion: Removing the mutual exclusion condition means that no process may have exclusive access to a resource. This proves impossible for resources that cannot be spooled, and even with spooled resources deadlock could still occur. Algorithms that avoid mutual exclusion are called non-blocking synchronization algorithms. 2. Hold and wait: The “hold and wait” conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations); this advance knowledge is frequently difficult to satisfy and, in any case, is an inefficient use of resources. Another way is to require processes to release all their resources before requesting all the resources they will need. This too is often impractical. (Such algorithms, such as serializing tokens, are known as the all-or- none algorithms.) 3. No preemption: A “no preemption” (lockout) condition may also be difficult or impossible to avoid as a process has to be able to have a resource for a certain amount of time, or the processing outcome may be inconsistent or thrashing may occur. However, inability to enforce preemption may interfere with a priority algorithm. Note Preemption of a “locked out” resource generally implies a rollback, and is to be avoided, since it is very costly in overhead. Algorithms that allow preemption include lock-free and wait-free algorithms and optimistic concurrency control. 4. Circular wait: The circular wait condition: Algorithms that avoid circular waits include “disable interrupts during critical sections” , and “use a hierarchy to determine a partial ordering of resources” (where no obvious hierarchy exists, even the memory address of resources has been used to determine ordering) and Dijkstra’s solution. 6.7.2 Deadlock Avoidance Deadlock Avoidance, assuming that you are in a safe state (i.e. a state from which there is a sequence of allocations and releases of resources that allows all processes to terminate) and you are requested certain resources, simulates the allocation of those resources and determines if the resultant state is safe. If it is safe the request is satisfied, otherwise it is delayed until it becomes safe. The Banker’s Algorithm is used to determine if a request can be satisfied. It uses requires knowledge of who are the competing transactions and what are their resource needs. Deadlock avoidance is essentially not used in distributed systems. 112 LOVELY PROFESSIONAL UNIVERSITY  Unit 6: Process Synchronization 6.7.3 Deadlock Detection and Recovery Notes Often neither deadlock avoidance nor deadlock prevention may be used. Instead deadlock detection and recovery are used by employing an algorithm that tracks resource allocation and process states, and rolls back and restarts one or more of the processes in order to remove the deadlock. Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the resource scheduler or OS. Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario. However, in specific environments, using specific means of locking resources, deadlock detection may be decidable. In the general case, it is not possible to distinguish between algorithms that are merely waiting for a very unlikely set of circumstances to occur and algorithms that will never finish because of deadlock. 6.7.4 Ignore Deadlock In the Ostrich Algorithm it is hoped that deadlock doesn’t happen. In general, this is a reasonable strategy. Deadlock is unlikely to occur very often; a system can run for years without deadlock occurring. If the operating system has a deadlock prevention or detection system in place, this will have a negative impact on performance (slow the system down) because whenever a process or thread requests a resource, the system will have to check whether granting this request could cause a potential deadlock situation. If deadlock does occur, it may be necessary to bring the system down, or at least manually kill a number of processes, but even that is not an extreme solution in most situations. 6.7.5 The Banker’s Algorithm for Detecting/Preventing Deadlocks Banker’s Algorithm for Single Resource This is modeled on the way a small town banker might deal with customers’ lines of credit. In the course of conducting business, our banker would naturally observe that customers rarely draw their credit lines to their limits. This, of course, suggests the idea of extending more credit than the amount the banker actually has in her coffers. Suppose we start with the following situation Customer Credit Used Credit Line Andy 0 6 Barb 0 5 Marv 0 4 Sue 0 7 Funds Available 10 Max Commitment 22 Our banker has 10 credits to lend, but a possible liability of 22. Her job is to keep enough in reserve so that ultimately each customer can be satisfied over time: That is, that each customer will be able to access his full credit line, just not all at the same time. Suppose, after a while, the bank’s credit line book shows. LOVELY PROFESSIONAL UNIVERSITY 113 Operating System Notes Customer Credit Used Credit Line Andy 1 6 Barb 1 5 Marv 2 4 Sue 4 7 Funds Available 2 Max Commitment 22 Eight credits have been allocated to the various customers; two remain. The question then is: Does a way exist such that each customer can be satisfied? Can each be allowed their maximum credit line in some sequence? We presume that, once a customer has been allocated up to his limit, the banker can delay the others until that customer repays his loan, at which point the credits become available to the remaining customers. If we arrive at a state where no customer can get his maximum because not enough credits remain, then a deadlock could occur, because the first customer to ask to draw his credit to its maximum would be denied, and all would have to wait. To determine whether such a sequence exists, the banker finds the customer closest to his limit: If the remaining credits will get him to that limit, The banker then assumes that that loan is repaid, and proceeds to the customer next closest to his limit, and so on. If all can be granted a full credit, the condition is safe. In this case, Marv is closest to his limit: assume his loan is repaid. This frees up 4 credits. After Marv, Barb is closest to her limit (actually, she’s tied with Sue, but it makes no difference) and 3 of the 4 freed from Marv could be used to award her maximum. Assume her loan is repaid; we have now freed 6 credits. Sue is next, and her situation is identical to Barb’s, so assume her loan is repaid. We have freed enough credits (6) to grant Andy his limit; thus this state safe. Suppose, however, that the banker proceeded to award Barb one more credit after the credit book arrived at the state immediately above: Customer Credit Used Credit Line Andy 1 6 Barb 2 5 Marv 2 4 Sue 4 7 Funds Available 1 Max Commitment 22 Now it’s easy to see that the remaining credit could do no good toward getting anyone to their maximum. So, to recap, the banker’s algorithm looks at each request as it occurs, and tests if granting it will lead to a safe state. If not, the request is delayed. To test for a safe state, the banker checks to see if enough resources will remain after granting the request to satisfy the customer closest to his maximum. If so, that loan is assumed repaid, and the next customer checked, and so on. If all loans can be repaid, then the request leads to a safe state, and can be granted. In this case, we see that if Barb is awarded another credit, Marv, who is closest to his maximum, cannot be awarded enough credits, hence Barb’s request can’t be granted —it will lead to an unsafe state3. Banker’s Algorithm for Multiple Resources Suppose, for example, we have the following situation, where the first table represents resources assigned, and the second resources still required by five processes, A, B, C, D, and E. 114 LOVELY PROFESSIONAL UNIVERSITY  Unit 6: Process Synchronization Resources Assigned Notes Processes Tapes Plotters Printers Toasters A 3 0 1 1 B 0 1 0 0 C 1 1 1 0 D