Banker's Algorithm

MINI PROJECT ON RESOURCE SCHEDULING IN CPU USING BANKERS ALGORITHM

By Brundha T

GUIDE: Mr C Vignesh Manikandan

Associate Professor

ABSTRACT

The Bankers algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes a "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue. The algorithm was developed in the design process for the operating system and originally described (in Dutch) in EWD108. The name is by analogy with the way that bankers account for liquidity constraints.

The Banker's algorithm is run by the operating system whenever a process requests resources. The algorithm avoids deadlock by denying or postponing the request if it determines that accepting the request could put the system in an unsafe state (one where deadlock could occur). When a new process enters a system, it must declare the maximum number of instances of each resource type that may not exceed the total number of resources in the system. Also, when a process gets all its requested resources it must return them in a finite amount of time.

For the Banker's algorithm to work, it needs to know three things:

1. How much of each resource each process could possibly request

2. How much of each resource each process is currently holding

3. How much of each resource the system currently has available

Resources may be allocated to a process only if it satisfies the following conditions:

1. request ≤ max, else set error condition as process has crossed maximum claim made by it.

2. request ≤ available, else process waits until resources are available.

Some of the resources that are tracked in real systems are memory, semaphores and interface access. It derives its name from the fact that this algorithm could be used in a banking system to ensure that the bank does not run out of resources, because the bank would never allocate its money in such a way that it can no longer satisfy the needs of all its customers. By using this algorithm, the bank ensures that when customers request money the bank never leaves a safe state. If the customer's request does not cause the bank to leave a safe state, the cash will be allocated; otherwise the customer must wait until some other customer deposits enough.

CHAPTER 1

INTRODUCTION

1.1 Overview

SCHEDULING RESOURCES IN CPU USING BANKERS ALGORITHM. The main objective of this project is to schedule the resources in CPU using Bankers Algorithm. Though there are many scheduling algorithms, they suffer from some kind of disadvantage. The resources are scheduled using the algorithm proposed by Edsger Dijkstra. The same system is used in bank by the Bankers so. This project also simulates a bank process.

CHAPTER 2

FEASIBILITY ANALYSIS

2.1 Economic Feasibility

Economic analysis is the most frequently used method for evaluating the effectiveness of a new system. In economic feasibility, cost benefit analysis is done in which expected costs and benefits are evaluated. For any system if the expected benefits equal or exceed the expected costs, the system can be judged to be economically feasible. The cost for developing this project does not exceed the actual cost deposited. No special software is used for scheduling the processes. This improves the efficiency of this project, so it is economically feasible to implement.

2.2 Operational Feasibility

Operational feasibility is mainly concerned with issues like whether the system will be used if it is developed and implemented. This project is more useful for the users schedule the process without waiting time if the system is in safe state. If this project is developed and launched in the market, the feedback will be received from the customers. So it is operationally feasible to implement.

2.3 Technical Feasibility

This project is developed using Turbo C software. So, this project is technically feasible by the normal programmers. Less manpower is needed to develop this tool. This project can also run in Microsoft visual C++, Borland C++.

CHAPTER 3

SYSTEM SPECIFICATION

3.1 HARDWARE REQUIREMENTS

The hardware used for the development of the project is:

Processor: AMD

Ram: 1GB

Hard disk: 250GB

IO devices: Mouse and Keyboard

System Type: 32-bit Operating System

3.2 SOFTWARE REQUIREMENTS

The software used for the development of the project is:

Operating system: Windows XP Professional

Professional Environment: Turbo C

Language: C++

CHAPTER 4

SOFTWARE DESCRIPTION

4.1 SPECIFICATION

Hardware

Turbo C requires a 100 percent IBM-compatible personal computer (PC), including the IBM PC-XT (extended Technology) and the IBM PC-AT (Advanced Technology) models.

Operating System

It also requires the MS-DOS version 2.0 or greater. It is not compatible with Microsoft Windows.

Memory

Turbo C necessitates that 384K of the first 512K of random access memory (RAM) is free and available to the program.

Disk Drive

While Turbo C can run with only one floppy disk drive, the recommended configuration is to use a hard disk drive. Because Turbo C is now provided in a compressed file rather than on floppy disks, a floppy disk drive is not required.

Monitor

Turbo C supports a monitor with 80 columns. It does not support Microsoft Windows graphics.

4.2 FEATURES

Integrated Development Environment

In the early days of PC development, before Windows, MS/DOS had no multitasking support. Only one program could run at a time. A programmer would run one program to edit code, another to compile the program then the new program was run to test for errors. This process was repeated many, many times. The integrated development environment (IDE) that Borland first introduced with Turbo Pascal greatly simplified this by wrapping the entire development process into one program.

Optimized C Compiler

By the time Turbo C was released, the C programming language had been around for over a decade and optimization techniques were well known. C is a low-level language that creates small, fast tight code. Turbo C offered a number of optimization choices that enhanced size and speed at a time when memory and processor cycles were still limited resources.

Integrated Assembler Language

Assembly language allows developers to write symbolic machine language, the same instructions used by the microprocessor. For most purposes, C is a much better choice since a line of C usually translates to 10 or more machine instructions. Nevertheless, a few lines of assembler code in the right place can often solve a sticky problem. Assembler also allows full access to the microprocessor registers and interrupts. Turbo C allows assembly code to be placed anywhere inside a C program.

Hardware Level Debugging

The Turbo Debugger lets developers view computer memory and registers in real time as the program steps through the code. Breakpoints and watches can be set so the program runs and stops at predefined points or when memory locations or registers reach certain values.

Multiple Memory Models

Most developers have forgotten this part of 16-bit development, but one of the difficulties involved memory management. With a 16-bit memory address, only a small portion of memory could be accessed at one time. The early C languages 5 solved this with a number of different memory models: tiny, small, compact and large. IBM has a detailed description of these memory models (see References).

Native Program Development

Although most development is now targeted toward Windows, there are applications where the code needs to get down close to the bare metal. Device drivers, hard disk utilities, interfaces to specialized hardware and diagnostic programs all need low-level access.

CHAPTER 5

CPU SCHEDULING

5.1 Introduction

CPU scheduling is the basis of multi programmed operating systems. By switching the CPU among processes, the operating system can make the computer more productive.

5.2 Basic Concepts

The objective of multiprogramming is to have some process running at all times, in order to maximize CPU utilization. In a uniprocessor system, only one process may run at a time; any other processes must wait until the CPU is free and can be rescheduled.

The idea of multiprogramming is relatively simple. A process is executed until it must wait, typically for the completion of some I/O request. In a simple computer system, the CPU would then sit idle; all this waiting time is wasted. With multiprogramming, the time is to be used productively. Several processes are kept in memory at one time. When one process has to wait, the operating system takes the CPU away from that process and gives the CPU to another process. This pattern continues.

Scheduling is a fundamental operating system function. Almost all computer resources are scheduled before use. The CPU is one of the primary computer resources. Thus, its scheduling is central to operating system design.

5.3 CPU-I/O Burst Cycle

The success of CPU scheduling depends on the following observed property of processes: Process execution consists of a cycle of CPU execution and I/O wait. Processes alternate between these two states. Process execution begins with a CPU burst i.e. by an I/O burst, and then another CPU burst will end with a system request to terminate execution, rather than with another I/O burst (figure 5.1).

The durations of these CPU bursts have been extensively measured. Although they vary greatly by process and by computer, they tend to have a frequency curve similar to that shown in figure 5.2. The curve is generally characterized as exponential or hyper exponential, with many short CPU bursts, and a few long CPU bursts. An I/O bound program might have a few very long CPU bursts. This distribution can help to select an appropriate CPU scheduling algorithm.

5.4 CPU Scheduler

Whenever the CPU becomes idle, the operating system must select one of the processes in thread queue to be executed. The selection process is carried out by the short-term scheduler (or CPU scheduler). The scheduler selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them.

The ready queue is not necessarily a first-in, first-out (FIFO) queue. A ready queue may be implemented as a FIFO queue, a priority queue, a tree, or simply an unordered linked list. All the processes in the ready queue are lined up waiting for a chance to run on the CPU. The records in the queue are generally process control blocks (PCBs) of the processes.

5.5 Preemptive Scheduling

CPU scheduling decisions may take place under the following four circumstances:

1. When a process switches from the running state to the waiting state (for example, I/O request, or invocation of wait for the termination of one of the child processes)

2. When a process switches from the running state to the ready state (for example, when an interrupt occurs)

3. When a process switches from the waiting state to the ready state( for example, completion of I/O)

4. When a process terminates

In circumstances 1 and 4, there is no choice in terms of scheduling. A new process must be selected for execution. There is a choice in circumstances 2 and 3.

When the scheduling takes place only under circumstances 1 and 4, the scheduling is non-preemptive; otherwise, the scheduling scheme is preemptive. Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state. This scheduling method is used by the Microsoft Windows 3.1 and by the Apple Macintosh operating systems. It is the only method that can be used on certain hardware platforms, because it does not require the special hardware needed for preemptive scheduling.

Preemptive scheduling incurs a cost. Consider the case of two processes sharing data. One may be in the midst of updating the data when it is preempted and

the second process is run. The second process may try to read the data, which are currently in an inconsistent state. New mechanisms are thus needed to coordinate access to shared date.

Preemption also has an effect on the design of the operating system kernel. During the processing of a system call, the kernel may be busy with an activity on behalf of a process. Such activities may involve changing important kernel data. If the process is preempted in the middle of these changes, and the kernel needs to read or modify the structure, chaos could ensue. Some operating systems, including most version of UNIX, deal with this problem by waiting either for a system call to complete, or for an I/O block to take place, before doing a context switch. This scheme ensures that the kernel structure is simple, since the kernel will not preempt a process while the kernel data structures are in an inconsistent state. Unfortunately, this kernel execution model is a poor one for supporting real-time computing and multiprocessing.

In case of UNIX, sections are still at risk. Because interrupts can, by definition, occur at any time, and because they cannot always be ignored by the kernel, the sections of code affected by interrupts must be guarded from simultaneous use. The operating system needs to accept interrupts at almost all times; otherwise input might be lost or output overwritten. So that these code sections are not accessed concurrently by several processes, they disable interrupts at entry and reenable interrupts at exit. Unfortunately, disabling and enabling interrupts is time consuming, especially on multiprocessor systems. Interrupt state changes must be minimized and fine-grained locking maximized for systems to scale efficiently beyond a few CPUs,. For instance, this is a challenge to the scalability of Linux.

5.6 Dispatcher

Another component involved in the CPU scheduling function is the dispatcher. The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves:

1. Switching context

2. Switching to user mode

3. Jumping to the proper location in the user program to restart that program

The dispatcher should be as fast as possible, given that it is invoked during every process switch. The time it takes for the dispatcher to stop one process and start another running is known as the dispatch latency. 10

5.7 Scheduler Criteria

Different CPU scheduling algorithms have different properties and may favor one class of processes over another. In choosing which algorithm to use in a particular situation, the properties of various algorithms must be considered.

Many criteria have been suggested for comparing CPU scheduling algorithms. The characteristics used for comparison can make a substantial difference in the determination of the best algorithm. The criteria include the following:

1. CPU utilization: It may range from 0 to 100 percent. In a real system, it should range from 40 percent (for lightly loaded system) to 90 percent (for heavily used system).

2. Throughput: If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes completed per time unit, called throughput. For long processes, this rate may be 1 process per hour; for short transactions, throughput might be 10 processes per second.

3. Turnaround Time: From the point of view of a particular process, the important criterion is how long it takes to execute that process. The interval from the time of submission of a process to the time of completion is the turnaround time. Turnaround time is the sum of the periods spent waiting to get into memory, waiting in thread queue, executing on the CPU, and doing I/O.

4. Waiting Time: The CPU scheduling algorithm does not affect the amount of time during which a process executes or does I/O; it affects only the amount of time that a process spends waiting in the ready queue. Waiting time is the sum of the periods spent waiting in the ready queue.

5. Response Time: In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early, and can continue computing new results while previous results are being output to the user. Thus, another measure is the time from the submission of a request time, is the amount of time it takes to start responding, but not the time that it takes to output that response. The turnaround time is generally limited by the speed of the output device.

The CPU utilization and throughput should be maximized and turnaround time, waiting time and response time should be minimized. In most case, the average measure is optimized. For example, to guarantee that all users get good service, the maximum response time should be reduced.

For interactive systems (such as time-sharing systems), some analysts suggest that minimizing the variance in the response time is more important than minimizing the average response time. A system with reasonable and predictable response time may be considered more desirable than a system that is faster on the average, but is highly variable. However, little work has been done on CPU scheduling algorithm to minimize variance.

CHAPTER 6

SCHEDULING ALGORITHMS

6.1 Introduction

CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated in the CPU.

6.2 First-Come, First-Served Scheduling

The simplest CPU scheduling algorithm is the first-come, first-served (FCFS) scheduling algorithm. With this scheme, the process that requests the CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with a FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue. The running process is then removed from the queue. The code for FCFS scheduling is simple to write and understand.

The average waiting time under the FCFS policy, is often quite long. Consider the following set of processes that arrive at time 0, with the length of the CPU burst time given in milliseconds.

Process Burst Time

P₁ 24

P₂ 3

P₃ 3

If the processes arrive in the order P₁,P₂,P₃, and are served in FCFS order, the result is obtained as shown in the Gantt chart:

P₁

P₂

P₃

0 24 27 30

The waiting time is 0 milliseconds for process P₁, 24 milliseconds for process P₂, and 27 milliseconds for process P₃. Thus, the average waiting time is (0+24+27)/3=17 milliseconds. If the processes arrive in the order P₂,P₃,P₁, the results will be as shown in the following Gantt chart:

P₂

P₃

P₁

0 3 6 30

The average waiting time is now (0+3+6)/3=3 milliseconds. This reduction is substantial. Thus, the average waiting time under FCFS policy is generally not minimal, and may vary substantially if the process CPU burst times vary greatly.

In addition, consider the performance of FCFS scheduling in a dynamic situation. Assume only one CPU bound process and many I/O bound processes are there. As the processes flow around the system, the following scenario may result. The CPU bound process will get the CPU and hold it. During this time, all the other processes will finish their I/O and move into the ready queue, the I/O devices are idle. Eventually, the CPU bound process finishes its CPU burst and moves to an I/O device. All the I/O bound processes, which have very short CPU bursts, execute quickly and move back to the I/O queues. At this point, the CPU sits idle. The CPU bound process will then move back to the ready queue and be allocated to the CPU. Again, all the I/O processes end up waiting in the ready queue until the CPU bound process is done. There is a convoy effect, as all the other processes wait for the one big process to get off the CPU. This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.

Limitations

The FCFS scheduling algorithm is non-preemptive. Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O. The FCFS algorithm is particularly troublesome for time-sharing systems, where each user needs to get a share of the CPU at regular intervals. It would be disastrous to allow one process to keep the CPU for an extended period.

6.3 Shortest-Job-First Scheduling

A different approach to CPU scheduling is the shortest-job-first (SJF) scheduling algorithm. This algorithm associates with each process the length of the latter’s next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If two processes have the same length next CPU burst, FCFS scheduling is used to break the tie. The appropriate term would be the shortest next CPU burst, because the scheduling is done by examining the length of the next CPU burst of a process, rather than its total length. 14

Consider the following set of processes, with length of the CPU burst time given in milliseconds as an example:

Process Burst Time

P₁ 6

P₂ 8

P₃ 7

P₄ 3

Using SJF scheduling, these processes are scheduled according to the following Gantt chart:

P₄

P₁

P₃

P₂

0 3 9 16 24

The waiting time is 3 milliseconds for process P₁, 16 milliseconds for process P₂, 9 milliseconds for process P₃, and 0 milliseconds for process P₄. Thus, the average waiting time is (3+16+9+0)/4=7 milliseconds. If it was FCFS scheduling scheme, then the waiting time would have been 10.25 milliseconds.

The SJF scheduling algorithm is provably optimal, in that it gives the minimum average waiting time for a given set of processes. By moving a short process before a long one, the waiting time of the short process decreases more than it increases the waiting time of the long process. Consequently, the average waiting time decreases.

The real difficulty with the SJF algorithm is to know the length of the next CPU request. For long term (or job) scheduling in a batch system, we can use as the length the process time limit that a user specifies when he submits the job. Thus, users are motivated to estimate the process time limit accurately, since a lower value may mean faster response. SJF scheduling is used frequently in long-term scheduling.

Although the SJF algorithm is optimal, it cannot be implemented at the level of short term CPU scheduling. There is no way to know the length of the next CPU burst. One approach is to try to approximate SJF scheduling. The length of the next CPU burst may not be known, but it can be predicted. It is expected that the next CPU burst will be similar in length to the previous ones. Thus, by computing an approximation of the length of the next CPU burst, the process with the shortest predicted CPU burst can be picked.

The next CPU burst is generally predicted as an exponential average of the measured lengths of previous CPU bursts. Let t_n be the length of the nth CPU burst, and let T_n+1 be the predicted value for the next CPU burst. Then, for α, 0 ≤ α ≤ 1, define

T_n+1= α t_n+(1- α)T_n

This formula defines an exponential average. The value of t_n contains most recent information; T_n stores the past history in the prediction. The parameter α controls the relative weight of recent and past history in the prediction. If α=0, then T_n+1=t_n, and only the most recent CPU burst matters.

More commonly, α=1/2, so recent history and past history are equally weighted. The initial T₀ can be defined as a constant or as an overall system average. Figure 6.1 shows an exponential average with α=1/2 and T₀=10.

To understand the behavior of the exponential average, the formula for T_n+1 can be expanded by substituting for T_n, to find

Figure 6.1: Prediction of the length of the next CPU burst

T_n+1= α t_n+ (1- α) α t_n-1+…+ (1- α)^j α t_n-j+…+ (1- α)ⁿ⁺¹T₀

Since both α and (1- α) are less than or equal to 1, each successive term has less weight than its predecessor.

The SJF algorithm may be either preemptive or non-preemptive. The choice arises when a new process arrives at the ready queue while a previous process is executing. The new process may have a shorter next CPU burst than what is left of the currently executing process. A preemptive SJF algorithm will preempt the currently executing process, whereas a non-preemptive SJF algorithm will allow the currently running process to finish its CPU burst. Preemptive SJF scheduling is sometimes called shortest-remaining-time-first scheduling.

Consider the following four processes, with length of the CPU burst time given in milliseconds:

Process Arrival Time Burst Time

P₁ 0 8

P₂ 1 4

P₃ 2 9

P₄ 3 5

If the processes arrive at the ready queue at the times shown and need the indicated burst times, then the resulting preemptive SJF schedule is as depicted in the following Gantt chart:

P₁

P₂

P₄

P₁

P₃

0 1 5 10 17 26

Process P₁ is started at time 0, since it is the only process in the queue. Process P₂ arrives at time 1. The remaining time for process P₁ (7 milliseconds) is larger than the time required by process P₂ (4 milliseconds), so process P₁ is preempted, and process P₂ is scheduled. the average waiting time for this example is ((10-1)+(1-1)+(17-2)+(5-3))/4=26/4=6.5 milliseconds. A non-preemptive SJF scheduling would result in an average waiting time of 7.75 milliseconds.

6.4 Priority Scheduling

The SJF algorithm is a special case of the general priority-scheduling algorithm. A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order.

An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the priority, and vice versa. 17

Priorities are generally some fixed range of numbers, such as 0 to 7, or 0 to 4, 095. However, there is no general agreement on whether 0 is the highest or lowest priority. Some systems use low numbers to represent low priority; others use low numbers for high priority. This difference can lead to confusion. In this description, low priority numbers are used to represent high priority.

Consider the following set of processes, assumed to have arrived at time 0, in the order P₁, P_2,…, P₅, with the length of the CPU burst time given in milliseconds as an example:

Process Burst Time Priority

P₁ 10 3

P₂ 1 1

P₃ 2 4

P₄ 1 5

P₅ 5 2

Using priority scheduling, these processes are scheduled according to the following Gantt chart:

P₂

P₅

P₁

P₃

P₄

0 1 6 16 18 19

The average waiting time is 8.2 milliseconds.

Priorities can be defined either internally or externally. Internally defined priorities use some measurable quantity or quantities to compute the priority of a process. For example, time limits, memory requirements, the number of open files, and the ratio of average I/O burst to average CPU burst have been used in computing priorities. External priorities are set by criteria that are external to the operating system, such as the importance of the process, the type and amount of funds being paid for computer use, the department sponsoring the work, and other, often political factors.

Priority scheduling can be either preemptive or non-preemptive. When a process arrives at the ready queue, its priority is compared with priority of the currently running process. A preemptive priority scheduling algorithm will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process. A non-preemptive priority scheduling algorithm will simply put the new process at the head of the ready queue.

Limitations

A major problem with priority scheduling algorithm is indefinite blocking (or starvation). A process that is ready to run but lacking the CPU can be considered blocked- waiting for the CPU. A priority scheduling algorithm can leave some low priority processes waiting indefinitely for the CPU. In a heavily loaded computer system, a steady stream of higher priority processes can prevent a low priority process from ever getting the CPU. Generally, one of two things will happen. Either the process will eventually be run or the computer system will eventually crash and lose all unfinished low priority processes.

6.5 Round Robin Scheduling

The round robin (RR) scheduling algorithm is designed especially for time-sharing systems. It is similar to FCFS scheduling, but preemption is added to switch between processes. A small unit of time called a time quantum (or time slice) is defined. A time quantum is generally from 10 to 100 milliseconds. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.

To implement RR scheduling, the ready queue is kept as a FIFO queue of processes. New processes are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.

One of two things will then happen. The process may have a CPU burst of less than 1 time quantum. In this case, the process itself will release the CPU voluntarily. The scheduler will then proceed to the next process in thread queue. Otherwise, if the CPU burst of the currently running process is longer than 1 time quantum, the timer will go off and will cause an interrupt to the operating system. A context switch will be executed, and the process will be put at the tail of the ready queue. The CPU scheduler will then select the next process in the ready queue.

Consider the following set of processes that arrive at time 0, with the length of the CPU burst time given in milliseconds:

Process Burst Time

P₁ 24

P₂3

P₃3

If a time quantum of 4 milliseconds is used , then process P₁ gets the first 4 milliseconds. Since it requires another 20 milliseconds, it is preempted after the first time quantum, and the CPU is given to the next process in the queue, process P₂. Since process P₂ does not need 4 milliseconds, it quits before its time quantum expires. The CPU is then given to the next process, process P₃.Once each process has received 1 time quantum, the CPU is returned to process P₁ for an additional time quantum. The resulting RR schedule is

P₁

P₂

P₃

P₁

0 4 7 10 14 18 22 26 30

The average waiting time is 17/3=5.66 milliseconds.

In RR scheduling algorithm, no process is allocated the CPU for more than 1 time quantum in a row. If a process’s CPU burst exceeds 1 time quantum, that process is preempted and is put back in the ready queue. The RR scheduling algorithm is preemptive.

If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units. Each process must wait no longer than (n-1)×q time units until its next time quantum. For example, then each process will get up to 20 milliseconds every 100 milliseconds.

The performance of the RR algorithm depends heavily on the size of the time quantum. At one extreme, if the time quantum is very large (infinite), the RR policy is the same as the FCFS policy. If the time quantum is very small, the RR approach is called processor sharing, and appears to the users as though each of n processes has its own processor running at 1/n the speed of the real processor. This approach was used in Control Data Corporation (CDC) hardware to implement 10 peripheral processors with only one set of hardware and 10 sets of registers. The hardware executes one instruction for one set of registers, then goes on to the next. This cycle continues, resulting in 10 slow processors rather than one fast processor.

In software, we also need to consider the effect of context switching on the performance of RR scheduling. Let us assume that we have only one process of 10 time units. If the quantum is 12 time units, the process finishes in less than 1 time quantum, with no overhead. If the quantum is 6 time units, the process requires 2 quanta, resulting in 1 context switch. If the time quantum is 1 time unit, then 9 context switches will occur, slowing the execution of the process accordingly (Figure 6.2). 20

Thus, the time quantum is to be large with respect to the context switch time. If the context switch time is approximately 10 percent of the time quantum, then about 10 percent of the CPU time will be spent in context switch.

Turnaround time also depends on the size of the time quantum. As seen from figure 6.3, the average turnaround time of a set of processes does not necessarily improve as the time-quantum size increases. In general, the average turnaround time can be improved if most processes finish their next CPU burst in a single time quantum. For example, given three processes of 10 time units each and a quantum of 1 time unit, the average turnaround time is 29. If the time quantum is 10, the average turnaround time drops to 20. If context switch time is added in, the average turnaround time increases for a smaller time quantum, since more context switches will be required.

Process time=10 quantum context

switches

Figure 6.2: Showing how a smaller time quantum increases context switches

On the other hand, if the time quantum is too large, RR scheduling degenerates to FCFS policy. A rule of thumb is that 80 percent of the CPU bursts should be shorter than the quantum.

Figure 6.3: Showing how turnaround time varies with the time quantum

6.6 Multilevel Queue Scheduling

Another class of scheduling algorithms has been created for situations in which processors are easily classified into different groups. For example, a common division is made between foreground (or interactive) processes and background (or batch) processes. These two types of processes have different response time requirements, and so might have different scheduling needs. In addition, foreground processes may have priority over background processes.

A multilevel queue-scheduling algorithm partitions the ready queue into several separate queues (Figure 6.4). The processes are permanently assigned to one queue, generally based on some property of the process, such as memory size, process type. Each queue has its own scheduling algorithm. For example, separate queues might be used for foreground and background processes. The foreground queue might be scheduled by an RR algorithm, while the background queue is scheduled by an FCFS algorithm.

In addition, there must be scheduling among the queues, which is commonly implemented as fixed-priority preemptive scheduling. For example, the foreground queue may have absolute priority over the background queue.

Figure 6.4: Multilevel queue scheduling

Let us look at an example of a multilevel queue-scheduling algorithm with five queues:

1. System processes

2. Interactive processes

3. Interactive editing processes

4. Batch processes

5. Student processes

Each queue has absolute priority over lower priority queues. No process in the batch queue, for example, could run unless the queues for system processes, interactive processes, and interactive editing processes were all empty. If an interactive editing process entered the ready queue while a batch process was running, the batch process would be preempted. Solaris2 uses a form of this algorithm.

Another possibility is to time slice between the queues. Each queue gets a certain portion of the CPU time, which can then schedule among the various processes in its queue. For instance, in the foreground-background queue example, the foreground queue can be given 80 percent of the CPU time for RR scheduling among its processes, whereas the background queue receives 20 percent of the CPU to give to its processes in a FCFS manner.

6.7 Multilevel Feedback Queue Scheduling

Normally, in a multilevel queue-scheduling algorithm, processes are permanently assigned to a queue on entry to the system. Processes do not move between queues. If there are separate queues for foreground and background processes, for example, processes do not move from one queue to the other, since processes do not change their foreground or background nature. This setup has the advantage of low scheduling overhead, but the disadvantage of being inflexible.

Multilevel feedback queue scheduling allows a process to move between queues. The idea is to separate processes with different CPU burst characteristics. If a process uses too much CPU time, it will be moved to a lower priority queue. This scheme leaves I/O bound and interactive processes in the higher priority queues. Similarly, a process that waits too long in a lower priority queue may be moved to higher priority queue. This form of aging prevents starvation.

For example, consider a multilevel feedback queue scheduler with three queues, numbered from 0 to 2(Figure 6.5). The scheduler first executes all processes in queue 0. Only when queue 0 is empty will it execute processes in queue 1. Similarly, processes in queue 2 will executed only if queues 0 and 1 are empty. A process that arrives for queue 1 will preempt a process in queue 2. A process that arrives for queue 0 will, in turn, preempt a process in queue 1.

Figure 6.5: Multilevel feedback queues

A process entering the ready queue is put in queue 0. A process in queue 0 is given a time quantum of 8 milliseconds. If it does not finish within this tie, it is moved to the tail of queue 1. If queue 0 is empty, the process at the head of queue 1 is given a quantum of 16 milliseconds. If it does not complete, it is preempted and is put into queue 2. Processes in queue 2 are run on an FCFS basis, only when queues 0 and 1 are empty.

This scheduling algorithm gives highest priority to any process with a CPU burst of 8 milliseconds or less. Such a process will quickly get the CPU, finish its CPU burst, and go off to its next I/O burst. Processes that need more than 8, but less than 24, milliseconds are also served quickly, although with lower priority than shorter processes. Long processes automatically sink to queue 2 and are served in FCFS order with any cycles left over from queue 0 and 1.

In general, a multilevel feedback queue scheduler is defined by the following parameters:

1. The number of queues

2. The scheduling algorithm for each queue

3. The method used to determine when to upgrade a process to a higher priority queue

4. The method used to determine when to upgrade a process to a lower priority queue

5. The method used to determine which queue a process will enter when that process needs service

The definition of a multilevel feedback queue scheduler makes it the most general CPU scheduling algorithm. It can be configured to match a specific system under design. Unfortunately, it also requires some means of selecting values for all the parameters to define the best scheduler. Although a multilevel feedback queue is the most general scheme, it is also the most complex.

6.8 Multiple Processor Scheduling

If multiple CPUs are available, the scheduling problem is correspondingly more complex. Many possibilities have been tried, and with single processor CPU scheduling, there is no one best solution.

Even with homogenous multiprocessor, there are sometime limitations on scheduling. Consider a system with an I/O device attached to a private bus of one processor. Processes wishing to use that device must be scheduled to run on that processor; otherwise the device would not be available.

If several identical processors are available, then load sharing can occur. It would be possible to provide a separate queue for each processor. In this case, one processor could be idle, with an empty queue, while another processor was very busy. To prevent this situation, a common ready queue is used. All processes go into one queue and are scheduled onto any available processor.

In such a scheme, one of two scheduling approaches may be used. In one approach, each processor is self-scheduling. Each processor examines the common ready queue and selects a process to execute. If multiple processors are trying to access and update a common data structure, each processor must be programmed very carefully. It is to be ensured that two processors do not choose the same process, and that processes are not lost from the queue. The other approach avoids this problem by appointing one processor as scheduler for the other processors, thus creating a master-slave structure.

Some systems carry this structure one step further, by having all scheduling decisions, I/O processing, and other system activities handled by one single processor-the master server. The processors only execute user code.

This asymmetric multiprocessing is far simpler than symmetric multiprocessing, because only one processor accesses the system data structures, alleviating the need for data sharing. It is also not efficient. I/O bound processes may bottleneck on the one CPU that is performing all of the operations. Typically, asymmetric multiprocessing is implemented first within an operating system, and is then upgraded to symmetric multiprocessing as the system evolves.

6.9 Real-Time Scheduling

Real time computing is divided into two types. Hard real time systems are required to complete a critical task within a guaranteed amount of time. Generally, a process is submitted along with a statement of the amount of time in which it needs to complete or perform I/O. The scheduler then either admits the process, guaranteeing that the process will complete on time, or rejects the request as impossible. This is known as resource reservation. Such a guarantee requires that the scheduler know exactly how long each type of operating system function takes to perform, and therefore each operation must be guaranteed to take a maximum amount of time. Such a guarantee is impossible in a system with secondary storage or virtual memory, because these subsystems cause unavoidable and unforeseeable variation in the amount of time to execute a particular process. Therefore, hard real-time systems are composed of special-purpose software running on hardware dedicated to their critical process, and lack the full functionality of modern computers and operating systems. 26

Soft real-time computing is less restrictive. It requires that critical processes receive priority over less fortunate ones. Although adding soft real-time functionality to a time-sharing system may cause an unfair allocation of resources and may result in longer delays, or even starvation, for some processes, it is at least possible to achieve. The result is a general purpose system that can also support multimedia, high speed interactive graphics, and a variety of tasks that would not function acceptably in an environment that does not support soft real time computing.

Implementing soft real time functionality requires careful design of the scheduler and related aspects of the operating system. First, the system must have priority scheduling, and real time processes must have the highest priority. The priority of real time processes must not degrade over time, even though the priority of non-real time processes may. Second, the dispatch latency must be small. The smaller the latency, the faster a real time process can start executing once it is runnable.

It is relatively simple to ensure that the former property holds. For example, we can disallow process aging on real time processes, thereby guaranteeing that the priority of the various processes does not change. However ensuring the latter property is much more involved. The problem is that many operating systems, including most versions of UNIX, are forced to wait either for a system call to complete or for an I/O block to take place before doing a context switch. The dispatch latency in such systems can be long, since some system calls are complex and some I/O devices are slow.

It is needed to allow system calls to be pre-emptible, to keep dispatch latency low. There are several ways to achieve this goal. One is to insert preemption points in long duration system calls, which check to see whether a high priority process needs to be run. If so, a context switch takes place and, when the high priority process terminates, the interrupted process continues with the system call. Preemption points can be placed at only safe locations in the kernel-only where kernel data structures are not being modified. Even with preemption points dispatch latency can be large, because only a few preemption points can be practically added to a kernel.

Another method for dealing with preemption is to make the entire kernel pre-emptible. So that correct operation is ensured, all kernel data structures must be protected through the use of various synchronization mechanisms. With this method, the kernel can always be pre-emptible, because any kernel data being updated are protected from modification by the high priority process. This is the most effective method in widespread use; it is used in Solaris 2.

If the higher priority process needs to read or modify kernel data currently being accessed by another lower priority process, the high priority process would be waiting for a lower priority one to finish. This situation is known as priority inversion. In fact, a chain of processes could all be accessing resources that the high priority process needs.

Figure 6.6: Dispatch latency

In figure 6.6, the makeup of dispatch latency is shown. The conflict phase of dispatch latency has two components:

1. Preemption of any process running in the kernel

2. Release by low priority processes resources needed by the high priority process

As an example, in Solaris 2, the dispatch latency with preemption disabled is over 100 milliseconds. However, the dispatch latency with preemption enabled is usually reduced to 2 milliseconds.

6.10 Algorithm Evaluation

How to select a CPU scheduling algorithm for a particular system? As we saw that there are many scheduling algorithms, each with its own parameters. As a result, selecting an algorithm can be difficult.

The first problem is defining the criteria to be used in selecting an algorithm. To select an algorithm, the relative importance of CPU utilization, response time, and throughput must be defined. The criteria may include several measures such as;

1. Maximize CPU utilization under the constraint that the maximum response time is 1 second.

2. Maximize throughput such that turnaround time is linearly proportional to total execution time.

Once the selection criteria have been defined, various algorithms under consideration must be evaluated.

6.11 Deterministic Modeling

One major class of evaluation methods is called analytic evaluation. Analytic evaluation uses the given algorithm and the system workload to produce a formula or number that evaluates the performance of the algorithm for that workload.

One type of analytic evaluation is deterministic modeling. This method takes a particular predetermined workload and defines the performance of each algorithm for that workload.

For example, assume that we have the workload shown. All five processes arrive at time 0, in the order given, with the length of the CPU burst time given in milliseconds:

Process Burst Time

P₁ 10

P₂ 29

P₃ 3

P₄ 7

P₅12

Consider the FCFS, SJF, and RR (quantum=10milliseconds) scheduling algorithms for this set of processes. The average time for each algorithm should be calculated and the algorithm which produces minimum average time is selected.

For FCFS algorithm, we would execute the processes as

P₁

P₂

P₃

P₄

P₅

0 10 39 42 49 61

The waiting time is 0 milliseconds for process P₁, 10milliseconds for process P₂, 39 milliseconds for process P₃, 42 milliseconds for process P₄, and 49 milliseconds for process P₅. Thus, the average waiting time is (0+10+39+42+49)/5=28milliseconds.

With non-preemptive SJF scheduling, we execute the processes as

P₃

P₄

P₁

P₅

P₂

0 3 10 20 32 61

The waiting time is 10 milliseconds for process P₁, 32 milliseconds for process P₂, 0 milliseconds for process P₃, 3 milliseconds for process P₄ and 20 milliseconds for process P₅. Thus, the average waiting time is (10+32+0+3+20)/5=13 milliseconds.

With the RR algorithm, we execute the processes as

P₁

P₂

P₃

P₄

P₅

P₂

P₅

P₂

0 10 20 23 30 40 50 52 61

The waiting time is 0 milliseconds for process P₁, 32 milliseconds for process P₂, 20 milliseconds for process P₃, 23 milliseconds for process P₄ and 40 milliseconds for process P₅. Thus, the average waiting time is (0+32+20+23+40)/5=23 milliseconds.

In this case, the SJF policy results in less than one-half the average waiting time obtained with FCFS scheduling; the RR algorithm gives us an intermediate value.

Deterministic modeling is simple and fast. It gives exact numbers, allowing the algorithms to be compared. However, it requires exact numbers for input, and its answers apply to only those cases. The main uses of deterministic modeling are in describing scheduling algorithms and providing examples. In cases where we may be running the same programs over and over again and can measure the program’s processing requirements exactly, we may be able to use deterministic modeling to select a scheduling algorithm. Over a set of examples, deterministic modeling may indicate trends that can then be analyzed and proved separately. For example, it can be shown that, for the environment described, the SJF policy will always result in the minimum waiting time. 30

In general, deterministic modeling is too specific, and requires too much exact knowledge, to be useful.

6.12 Queuing Models

The processes that are run on many systems vary from day to day, so there is no static set of processes to use for deterministic modeling. What can be determined is the distribution of CPU and I/O bursts. These distributions may be measured and then approximated or simply estimated. The result is a mathematical formula describing the probability of a particular CPU burst . Commonly, this distribution is exponential and is described by its mean. Similarly, the distribution of times when processes arrive in the system the arrival time distribution must be given.

The computer system is described as a network of servers. Each server has a queue of waiting processes. The CPU is a server with its ready queue, as is the I/O system with its device queues. Knowing arrival rates and service rates, we can compute utilization, average queue length, average wait time, and so on. This area of study is called queuing network analysis.

As an example, let n be the average queue length (excluding the process being serviced), let W be the average waiting time in the queue, and let λ be the average arrival rate for new processes in the queue. Then, we expect that during the time W that a process waits, λ×W new processes will arrive in the queue. to. If the system is in a steady state, then the number of processes leaving the queue must be equal the number of processes that arrive. Thus,

n= λ×W

This equation is known as Little’s formula. Little’s formula is particularly useful because it is valid for any scheduling algorithm and arrival distribution.

This formula can be used to compute one of three variables, if other two is known. For example, if it is known that seven processes arrive every second, and that there are normally 14 processes in the queue, then the average waiting time per process is computed as 2 seconds.

Queuing analysis can be useful in comparing scheduling algorithms, but it also has limitations. At the moment, the classes of algorithms and distributions that can be handled are fairly limited. The mathematics of complicated algorithms or distributions can be difficult to work with. Thus, arrival and service distributions are often defined in unrealistic, but mathematically tractable ways. It is also generally necessary to make a number of independent assumptions, which may not be accurate. Thus, so that they will be able to compute an answer, queuing models are often only an approximation of a real system. As a result, the accuracy of the computed results may be questionable.

6.13 Simulations

To get more accurate evaluation of scheduling algorithms, simulations can be used. Simulations involve programming a model of the computer system. Software data structures represent the major components of the system. The simulator has a variable representing a clock; as this variable’s value is increased, the simulator modifies the system state to reflect the activities of the devices, the processes and the scheduler. As the simulation executes, statistics that indicate algorithm performance are gathered and printed.

The data to drive simulation can be generated in several ways. The most common method uses a random number generator, which is programmed to generate processes; CPU burst times, arrivals, departures, and so on, according to probability distributions. The distributions may be defined mathematically or empirically. If the distribution is to be defined empirically, measurements of the actual system under study are taken. The results are used to define the actual distribution of events in the real system, and this distribution can then be used to drive the simulation.

Figure 6.7: Evaluation of CPU schedulers by simulation

A distribution driven simulation may be inaccurate due to relationships between successive events in the real system. The frequency distribution indicates only how many of each event occur; it does not indicate anything about the order of their occurrence. To correct this problem, trace tapes can be used. Trace tapes can be created by monitoring the real system, recording the actual sequence of actual events (Figure 6.7). This sequence is then used to drive the simulation. Trace tapes provide an excellent way to compare two algorithms on exactly the same set of real inputs. This method can produce accurate results for its inputs.

Simulations can be expensive often requiring hours of computer time. A more detailed simulation provides more accurate results, but also requires more computer

time. In addition, trace tapes can require large amounts of storage space. Finally, the design, coding and debugging of the simulator can be a major risk.

6.14 Implementation

Even a simulation is of limited accuracy. The only completely accurate way to evaluate a scheduling algorithm is to code it, put it in the operating system, and see how it works. This approach puts the actual algorithm in the real system for evaluation under real operating conditions.

The major difficulty is the cost of this approach. The expense is incurred not only in coding the algorithm and modifying the operating system to support it as well as its required data structures, but also in the reaction of the users to a constantly changing operating system; they merely want to get their processes executed and to use their work done. A form of this method is used commonly for new computer installations. For instance, a new web facility may have simulated user loads generated against it before it goes live to determine any bottlenecks in the facility and to estimate how many users the system can support.

The other difficulty with any algorithm evaluation is that the environment in which the algorithm is used will change. The environment will change not only the usual way, as new programs are written and the types of problems change, but also as a result of the performance of the scheduler. If short processes are given priority, then users may break larger processes into sets of smaller processes. If interactive processes are given priority over non-interactive processes, then users may switch to interactive use.

For example, in DEC TOPS-20, the system classified interactive and non-interactive processes automatically by looking at the amount of terminal I/O. If a process did not input or output to the terminal in a 1-minute interval, the process was classified as non-interactive and was moved to a lower priority queue. This policy resulted in a situation where one programmer modified his programs to write an arbitrary character to the terminal at regular intervals of less than 1 minute. The system gave his programs a high priority, even though the terminal output was completely meaningless.

The most flexible scheduling algorithms can be altered by the system managers or by the users. During operating system build time, boot time, or run time, the variables used by the schedulers can be changed to reflect the expected future use of the system. The need for flexible scheduling is another instance where the separation of mechanism from policy is useful. For instance, if paychecks need to be processed and printed immediately, but are normally done as a low priority batch job, the batch queue could be given a higher priority temporarily. Unfortunately, few operating systems allow this type of tunable scheduling.

CHAPTER 7

INTRODUCTION TO SEMAPHORES

7.1 The Critical Section Problem

Consider a system consisting of n processes {P₀,P_1,… ,P_n-1}. Each process has a segment of code, called a critical section, in which the process may be changing common variables, updating a table, writing a file, and so on. The important feature of the system is that, when one process is executing in its critical section. Thus, the execution of critical sections by the processes is mutually exclusive in time. The critical section problem is to design a protocol that the processes can use to cooperate. Each process must request permission to enter its critical section. The section of code implementing this request is the entry section. The critical section may be followed by an exit section. The remaining code is the remainder section.

General structure of a process P_i

entry section

do{

critical section

remainder section

}while(1);

A solution to the critical section problem must satisfy the following three requirements:

1. Mutual Exclusion: If process P_i is executing in its critical section, then no other processes can be executing in their critical sections.

2. Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.

3. Bounded waiting: There exists a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

There are two different solutions for this critical section problem i.e. two process solutions and multi process solution.

7.2 Semaphores

The solutions to the critical solution problem are not easy to generalize to more complex problems. To overcome this difficulty, synchronization tool is used called semaphore. A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait and signal. The definitions of wait and signal in pseudo code is:

wait(S){

while(S<=0);

S--;

}

signal(S){

S++;

}

Semaphores are implemented in C as:

typedef struct{

int value;

struct process *L;

}semaphore;

The wait semaphore operation can be defined as

void wait(semaphore S) {

S.value--;

if(S.value<0) {

add this process to S.L;

block( );

}

The signal semaphore operation can be defined as

void signal(semaphore S) {

S.value++;

if(S.value<=0) {

remove a process P from S.L;

wakeup(P);

}

CHAPTER 8

DEADLOCKS

8.1 Introduction

The implementation of a semaphore with a waiting queue may result in a situation where two or more processes are waiting indefinitely for an event that can be caused only one of the waiting processes. The event in the question is the execution of a signal operation. When such a state is reached these processes are said to be deadlocked.

In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a wait state. Waiting processes may never again change state, because the resources they have requested are held by other waiting processes. This situation is called a deadlock.

Most current operating systems do not provide deadlock-prevention facilities, but such features will probably be added soon. Deadlock problems can only become more common, given current trends, including larger numbers of processes, multithreaded programs, many more resources within a system, and the emphasis on long-lived file and database servers rather than batch systems.

8.2 Deadlock Characterization

In a deadlock, processes never finish executing and system resources are tied up, preventing other jobs from starting.

Necessary Conditions

A deadlock situation can arise if the following four conditions hold simultaneously in a system.

1. Mutual exclusion: At least one resource must be held in a non-sharable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.

2. Hold and wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.

3. No preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed it task.

4. Circular wait: A set {P₀, P₁, …, P_n} of waiting processes must exist

such that P₀ is waiting for a resource that is held by P₁, P₁ is waiting for

a resource that is held by P₂,…, P_n-1is waiting for a resource that is held by P_n, and P_n is waiting for a resource that is held by P₀.

We emphasize that all four conditions must hold for a deadlock to occur. The circular-wait condition implies the hold-and -wait condition, so the four conditions are not completely independent.

8.3 Methods for Handling Deadlocks

Principally, deadlocks can be dealt in one of the following three ways:

1. Protocol can be used to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state.

2. A system can be allowed to enter a deadlock state, detect it and recover.

3. The problem can be ignored altogether, and pretend that deadlocks never occur in the system. This solution is used by most operating systems, including UNIX.

The system can use either a deadlock-prevention or a deadlock-avoidance scheme to ensure that deadlocks never occur. Deadlock prevention is a set of methods for ensuring that at least one of the necessary conditions cannot hold. These methods prevent deadlocks by constraining how requests for resources can be made. Deadlock avoidance requires that the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime. With this additional knowledge, we can decide whether or not the process should wait. To decide whether the current request can be satisfied or must be delayed, the system must consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process.

If a system does not employ either a deadlock-prevention or a deadlock-avoidance algorithm, then a deadlock situation may occur. In this environment, the system can provide an algorithm that examines the state of the system to determine whether a deadlock has occurred, and an algorithm to recover from the deadlock.

If a system does not ensure that a deadlock will never occur, and also does not provide a mechanism for deadlock detection and recovery, then we may arrive at a situation where the system is in a deadlock state yet has no way of recognizing what has happened. In this case, the undetected deadlock will result in the deterioration of the system performance, because resources are being held by processes that cannot run, and because more and more processes, as they make requests for resources, enter a deadlock state. Eventually, the system will stop functioning and will need to be restarted manually.

Although this method does not seem to be viable approach to the deadlock problem, it is nevertheless used in some operating systems. In many systems,

deadlocks occur infrequently thus; this method is cheaper than the costly deadlock-prevention, deadlock-avoidance, or deadlock-detection and recovery methods that must be used constantly. Also, in some circumstances, the system is in a frozen state but not in a deadlock state.

As an example, consider a real-time process running at the highest priority and never returning control to the operating system. Thus, systems must have manual recovery methods for non-deadlock conditions, and may simply use those techniques for deadlock recovery.

8.4 Deadlock Prevention

We saw that for a deadlock to occur, each of the four necessary conditions must hold. By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence of a deadlock.

Mutual Exclusion

The mutual exclusion condition must hold for non-sharable resources. For example, a printer cannot be simultaneously shared by several processes. Sharable resources, on the other hand, do not require mutually exclusive access, and thus cannot be involved in a deadlock. Read-only files are a good example of a sharable resource. If several processes attempt to open a read-only file at the same time, they can be granted simultaneous access to the file. A process never needs to wait for a sharable resource. In general, we cannot prevent deadlocks by denying the mutual exclusion condition. Some resources are intrinsically non-sharable.

Hold and Wait

We must assure that, whenever a process requests a resource, it does not hold any other resources to ensure that the hold-and-wait condition never occurs in the system. One protocol that can be used requires each process to request and be allocated all its resources before it begins execution. This provision can be implemented by requiring that system calls requesting resources for a process precede all other system calls.

An alternative protocol allow as a process to request resources only when the process has none. A process may request some resources and use them. Before it can request any additional resources it must release all the resources that it is currently allocated.

To illustrate the difference between these two protocols, we consider a process that copies data from a tape drive to a disk file, sorts the disk file, and then prints the results to a printer. If all resources must be requested at the beginning of the process, then the process must initially request the tape drive, it needs the printer only at the end.

The second method allows the process to request initially only the tape drive and disk file. It copies from the tape drive to the disk, then releases both the tape drive and disk file. The process must then again request the disk file and the printer. After copying the disk file to the printer, it releases these two resources and terminates. These protocols have two main disadvantages. First, resource utilization may be low, since many of the resources may be allocated but unused for a long period. In the example, for instance, we can release the tape drive and disk file, and then again request the disk file and printer, only if we can be sure that our data will remain on the disk file. If we cannot be assured that they will, then we must request all resources at the beginning for both protocols.

Second, starvation is possible. A process that needs several popular resources may have to wait indefinitely, because at least one of the resources that it needs is always allocated to some other process.

No Preemption

The third necessary condition is that there be no preemption of resources that have already been allocated. To ensure that this condition does not hold, we can use the following protocol. If a process is holding some resources and requests another resource that cannot be immediately allocated to it, then all resources currently being held are preempted. In other words, these resources are implicitly released. The preempted resources are added to the list of resources for which the process is waiting. The process will be restarted only when it regain its old resources, as well as the new ones that it is requesting.

Alternatively, if a process requests some resources, we first check whether they are available. If they are, we allocate them. If they are not available, we check whether they are allocated to some other process that is waiting for additional resources. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process. If the resources are not either available or held by a waiting process, the requesting process must wait. While it is waiting, some of its resources may be preempted, but only if another process requests them. A process can be restarted only when it is allocated the new resources it is requesting and recovers any resources that were preempted while it was waiting.

This protocol is often applied to resources whose state can be easily saved and restored later, such as CPU registers and memory space. It cannot generally be applied to such resources as printers and tape drives.

Circular Wait

The fourth and final condition for deadlocks is the circular-wait condition. One way to ensure that this condition never holds is to impose a total ordering of all resource types, and to require that each process requests resources in an increasing order of enumeration.

Let R={R₁,R₂,…,R_m} be the set of resource types. We assign to resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering. Formally, we define a one-to-one function F:R→N, where N is the set of natural numbers. For example, if the set of resource types R include tape drives, disk drives, and printers, then the function F might be defined as follows:

F (tape drive) =1,

F (disk drive) =5,

F (printer) =12.

We can now consider the following protocol to prevent deadlocks: Each process can request resources only in an increasing order of enumeration, that is, a process can initially request any number of instances of resource type, say R_i. After that, the process can request instances of resource type R_j if and only if F(R_j)>F(R_i). If several instances of the same resource type are needed, a single request for all of them must be issued. For example, using the function defined previously, a process that wants to use the tape drive and printer at the same time must first request the tape drive and then request the printer.

Alternatively, we can require that, whenever a process requests an instance of resource type R_j, it has released any resources R_i such that F(R_i)≥F(R_j). If these two protocols are used, then the circular-wait condition cannot hold. We can demonstrate this fact by assuming that a circular-wait exists. Let the set of processes involved in the circular wait be {P₀,P₁,…,P_n}, where Pi is waiting for a resource R_i, which is held by process P_i+1.Then, since process P_i+1is holding resource Ri while requesting resource R_i+1, we must have F(R_i)<F(R_i+1), for all i. But this condition means that F(R₀)<…<F(R_n)<F(R₀). By transitivity, F(R₀)<F(R₀), which is impossible. Therefore, there can be no circular wait.

8.5 Deadlock Avoidance

Deadlock-prevention algorithms prevent deadlocks by restraining how requests can be made. The restraints ensure that at least one of the necessary conditions for deadlock cannot occur, and hence that deadlocks cannot hold. Possible side effects of preventing deadlocks by this method are low device utilization and reduced system throughput.

An alternative method for avoiding deadlocks is to require additional information about how resources are to be requested. For example, in a system with one tape drive and printer, we might be told that process P will request first the tape drive, and later the printer, before releasing both resources. Process Q, on the other hand will request first the printer, and then the tape drive. With this knowledge of the complete sequence of requests and releases should wait. Each request requires that the system consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process, to decide whether the current request can be satisfied or must wait to avoid a possible future deadlock.

The various algorithms differ in the amount and type of information required. The simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need. Given that may be requested for each process, it is possible to construct an algorithm that ensures that the system will never enter a deadlock state. This algorithm defines the deadlock-avoidance approach. A deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that a circular-wait condition can never exist. The resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.

Figure 8.1: Illustration of safe and unsafe states of Resource R and Process P

The following are the methods of deadlock avoidance:

1. Safe state

2. Resource Allocation Graph Algorithm

3. Banker’s Algorithm

8.5.1 Safe State

A state is safe if the system can allocate resources to each process in some order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe sequence. A sequence of processes <P₁,P₂,…,P_n> is a safe sequence for the current allocation state if, for each P_i, the resources that P_i can still request can be satisfied by the currently available resources plus the resources held by all the P_j, with j<i. In this situation, if the resources that process P_i needs are not immediately available, then P_i can wait until all P_j have finished. When they have finished, P_i can obtain all of its needed resources, complete its designated task, return its allocated resources, and terminate. When P_i terminates, P_i+1 can obtain its needed resources, and so on. If no such sequence exists, then the system state is said to be unsafe.

Figure 8.2: Safe, unsafe and deadlock state spaces

A safe state is not a deadlock state. Conversely, a deadlock state is an unsafe state. Not all unsafe states are deadlocks. An unsafe state may lead to a deadlock. As long as the state is safe, the operating system can avoid unsafe states. In an unsafe state, the operating system cannot prevent processes from requesting resources such that a deadlock occurs. The behavior of the processes controls unsafe states.

Given the concept of a safe state, avoidance algorithms that ensure that the system will never deadlock must be defined. The idea is simply to ensure that the system will always remain in a safe a state. Initially, the system is in a safe state. Whenever a process requests a resource that is currently available, the system must decide whether the resource can be allocated immediately or must wait. The request is granted only if the allocation leaves the system in a safe state.

In this scheme, if a process requests a resource that is currently available, it may still have to wait. Thus, resource utilization may be lower than it would be without a deadlock avoidance algorithm.

8.5.2 Resource Allocation Graph Algorithm

If we have a resource allocation system with only one instance of each resource type, a variant of the resource allocation graph can be used for deadlock avoidance.

In addition to the request and assignment edges, a new type of edge is introduced called a claim edge. A claim edge P_i–›R_j indicates that process P_i may request resource R_j at some time in the future. The edge resembles a request edge in direction, but is represented by a dashed line. When process P_i requests resource R_j, the claim edge P_i–›R_j is converted to a request edge. Similarly, when a resource R_j is released by P_i, the assignment edge R_j–›P_i is reconverted to a claim edge P_i–›R_j. Before process P_i starts executing, all its claim edges must already I the resource allocation graph. We can relax this condition by allowing a claim edge P_i–›R_j to be added to the graph only if all the edges associated with process P_i are claim edges.

Suppose that process P_i requests resource R_j. The request an be granted only if converting the request edge P_i–›R_jto an assignment edge R_j–›P_i does not result in the formation of a cycle in the resource allocation graph. Safety is checked by using a cycle detection algorithm. 42

An algorithm for detecting a cycle in this graph requires an order of n² operations, where n is the number of processes in the system.an unsafe state. Therefore, process P_i will have to wait for its requests to be satisfied.

If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is found, then the allocation will put the system in an unsafe state. Therefore, process P_i will have to wait for its requests to be satisfied.

To illustrate this algorithm, we consider the resource allocation graph of Figure 7.3. Suppose that P₂requests R₂. Although R₂ is currently free, we cannot allocate it to P₂, since this action will create a cycle in the graph (Figure 8.4). A cycle indicates that the system is in an unsafe state. If P₁ requests R₂ and P₂ requests R₁then a deadlock will occur.

Figure 8.3: Resource allocation graph for deadlock avoidance

8.5.3 Bankers Algorithm

The resource-allocation graph algorithm is not applicable to a resource-allocation system with multiple instances of each resource type. The deadlock-avoidance algorithm that we describe next is applicable to such a system, but is less efficient than the resource-allocation graph scheme. This algorithm is commonly known as the banker’s algorithm. The name was chosen because this algorithm could be used in a banking system to ensure that the bank never allocates its available cash such that it can no longer satisfy the needs of all its customers.

When a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system. When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the process must wait until some other process releases enough resources.

Figure 8.4: An unsafe state in a resource allocation graph

Algorithm

Several data structures must be maintained to implement the banker’s algorithm. These data structures encode the state of the resource-allocation system. Let n be the number of processes in the system and m be the number of resource types. We need the following data structures:

1. Available: A vector of length m indicates the number of available resources of each type. If Available[j]=k, there are k instances of resource type R_j available.

2. Max: An n×m matrix defines the maximum demand of each process. If Max[i,j]=k, then process P_imay request at most k instances of resource type R_j.

3. Allocation: An n×m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i,j]=k, then process P_i is currently allocated k instances of resource type R_j.

4. Need: An n×m matrix indicates the remaining resource need of each process. If Need[i,j]=k, then process P_imay need k more instances of resource type R_jto complete its task.

Need[i,j]=Max[i,j]-Allocation[i,j]

These data structures vary over time in both size and value.

To simplify the presentation of the banker’s algorithm, let us establish some notation. Let X and Y be vectors of length n, X≤Y if and only if X[i]≤Y[i] for all i=1,2,…,n. For example, if X=(1,7,3,2) and Y=(0,3,2,1), then Y≤X. Y<X if Y≤X and Y≠X.

We can treat each row in the matrices Allocation and Need as vectors and refer to them as Allocation_iand Need_i, respectively. The vector Allocation_i specifies the resources currently allocated to process P_i; the vector Need_i specifies the additional resources that process P_i may still request to complete its task.

Safety Algorithm

The algorithm for finding out whether or not a system is in a safe state can be:

Let Work and Finish be vectors of length m and n, respectively. Initialize Work:=Available and Finish [i]:=false for i=1,2,…,n

1. Find an i such that both

a. Finish[i]=false

b. Needi≤Work

If no such i exists, go to step 4.

2. Work:=Work+Allocation_i

Finish[i]:=true

go to step 2.

3. If Finish[i]=true for all i, then the system is in a safe state.

This algorithm may require an order of m×n² operations to decide whether a state is safe.

Resource-Request Algorithm

Let Request_i be the request vector for process P_i. If Request_i[j]=k, then process P_i wants k instances of resource type R_j. When a request for resources is made by process Pi, the following actions are taken:

1. If Requesti≤Needi, go to step2. Otherwise, raise an error condition, since the process has exceeded its maximum claim.

2. If Requesti≤Available, go to step3. Otherwise, Pi must wait, since the resources are not available.

3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:

Available:=Available-Request_i;

Allocation_i:=Allocation_i+Request_i;

Need_i:=Need_i-Request_i;

If the resulting resource-allocation state is safe, the transaction is completed and process P_i is allocated its resources. If the new state is unsafe, then P_imust wait for Request_iand the old resources-allocation state is restored.

8.5.3.1 An illustrative Example

Consider the system with five processes P₀ through P₄ and three resource types A,B,C. Resource type A has 10 instances, resource type B has 5 instances, and

resource type C has 7 instances. Suppose that, at time T₀, the following snapshot of the system has been taken:

Allocation Max Available

A B C A B C A B C

P₀ 0 1 0 7 5 3 3 3 2

P₁ 2 0 0 3 2 2

P₂ 3 0 2 9 0 2

P₃ 2 1 1 2 2 2

P₄ 0 0 2 4 3 3

The content of the matrix Need is defined to be Max- Allocation and is

Need

A B C

P₀ 7 4 3

P₁ 1 2 2

P₂ 6 0 0

P₃ 0 1 1

P₄ 4 3 1

We claim that the system is currently in a safe state. The sequence

<P₁, P₃, P₄,P₂, P₀> satisfies the safety criteria. Suppose now that process P₁ requests one additional instance of resource type A and two instances of resource type C, so Request₁=(1,0,2). To decide whether this request can be immediately granted, we first check that Request₁≤Available which is true. Then this request has been fulfilled, and the following new state is arrived:

Allocation Need Available

A B C A B C A B C

P₀ 0 1 0 7 4 3 2 3 0

P₁ 3 0 2 0 2 0

P₂ 3 0 2 6 0 0

P₃ 2 1 1 0 1 1

P₄ 0 0 2 4 3 1

We must determine whether this new system state is safe. To do so, safety algorithm should be executed and the sequence is found to be <P₁, P₃, P₄, P₀, P₂> satisfies our safety requirement. Hence, the request of process P1 can be granted immediately.

CHAPTER 9

APPENDIX

APPENDIX 1

9.1 SOURCE CODE

#include<iostream.h>

#include<conio.h>

#define MAX 5

class bankers

{

int alloc[MAX][MAX], max[MAX][MAX], need[MAX][MAX];

int avail[MAX], nop, nor, k, result[MAX], pnum, work[MAX];

int finish[MAX];

public:

bankers( );

void get( );

void operation( );

int search(int);

void display( );

};

bankers::bankers( )

{

k=0;

for(int i=0;i<MAX;i++)

{

for(int j=0;j<MAX;j++)

{

alloc[i][j]=max[i][j]=need[i][j]=0;

}

avail[i]=result[i]=finish[i]=0;

}

void bankers::get( )

{ int i,j; 47

cout<<"\nEnter the number of processes:";

cin>>nop;

cout<<"\nEnter the number of resources:";

cin>>nor;

cout<<"\nEnter the allocated resources for each process:";

for(i=0;i<nop;i++)

{

cout<<"\nProcess "<<i;

for(j=0;j<nor;j++)

{

cout<<"\nResource "<<j<<":";

cin>>alloc[i][j];

}

cout<<"Enter the maximum resources that are needed for each process: \n”;

for(i=0;i<nop;i++)

{

cout<<"\nProcess "<<i;

for(j=0;j<nor;j++)

{

cout<<"\nResource "<<j<<":";

cin>>max[i][j];

need[i][j]=max[i][j]-alloc[i][j];

}

cout<<"Enter the currently available resources in the system:\n ";

for(j=0;j<nor;j++)

{

cout<<"Resource "<<j<<":";

cin>>avail[j];

work[j]=-1;

}

for(i=0;i<nop;i++)

finish[i]=0;

}

void bankers::operation( )

{

int i=0,j,flag;

while(1)

{

if(finish[i]==0)

{ 48

pnum =search(i);

if(pnum!=-1)

{

result[k++]=i;

finish[i]=1;

for(j=0;j<nor;j++)

{

avail[j]=avail[j]+alloc[i][j];

}

i++;

if(i==nop)

{

flag=0;

for(j=0;j<nor;j++)

if(avail[j]!=work[j])

flag=1;

for(j=0;j<nor;j++)

work[j]=avail[j];

if(flag==0)

break;

else

i=0;

}

int bankers::search(int i)

{

int j;

for(j=0;j<nor;j++)

if(need[i][j]>avail[j])

return -1;

return 0;

}

void bankers::display( )

{

int i,j;

cout<<"\nOUTPUT:\n";

cout<<"========\n";

cout<<"PROCESS\t ALLOTED\t MAXIMUM\t NEED";

for(i=0;i<nop;i++) 49

{

cout<<"\np"<<i<<"\t\t";

for(j=0;j<nor;j++)

{

cout<<alloc[i][j]<<" ";

}

cout<<"\t\t";

for (j=0;j<nor;j++)

{

cout<<max[i][j]<<" ";

}

cout<<"\t\t";

for(j=0;j<nor;j++ )

{

cout<<need[i][j]<<" ";

}

cout<<"\nThe sequence of the safe processes is: \n";

for(i=0;i<k;i++)

{

int temp = result[i];

cout<<"p"<<temp<<" ";

}

cout<<"\nThe sequence of unsafe processes is: \n";

int flg=0;

for (i=0;i<nop;i++)

{

if(finish[i]==0)

{

flg=1;

}

cout<<"p"<<i<<" ";

}

cout<<"\n=======";

if(flg==1)

cout<<"\nThe system is not in safe state and deadlock may occur!!";

else

cout<<"\nThe system is in safe state and deadlock will not occur!!";

}

void main( )

{

bankers B;

clrscr( );

cout<<" DEADLOCK BANKER’S ALGORITHM \n";

B.get( );

B.operation( );

B.display( );

getch( );

}

APPENDIX 2

9.2 FEATURES IMPLEMENTED

The following features are implemented in the source code:

1. Data Abstraction: It is the way of implementing data hiding.

2. Data Encapsulation: Wrapping up of data and its related code in a single function i.e. class.

3. Dynamic Memory Allocation: Allocating memory to the object during its creation. Constructor allows this feature to the above code.

4. Message Passing: It is defined as the invoking of the member function using object and dot operator (.).

These are the features of Object Oriented Programming (OOP). These features are the drawbacks of C language. So the above source code cannot be executed in any C Compiler.

APPENDIX 3

9.3 DATA FLOW DIAGRAM

The following flowchart depicts the flow of data in the routines operation( ) and search( ) which will be easy for the banker to understand the program.

Figure A9.1: Flowchart for operation( )

Figure A9.2: Flowchart for search( )

APPENDIX 4

9.4 SCREENSHOTS

Figure A9.3: Screenshot for sample Input

Figure A9.4: Screenshot for sample Input (Continuation)

Figure A9.5: Screenshot for output

CHAPTER 10

REFERENCES

1. Silberschatz/Galvin/Gagne Sixth Edition “OPERATING SYSTEM CONCEPTS”.

Banker's Algorithm

Thursday, 9 May 2013

Implementation of Bankers Algorithm

MINI PROJECT ON RESOURCE SCHEDULING IN CPU USING BANKERS ALGORITHM

By Brundha T

GUIDE: Mr C Vignesh Manikandan

4.1 SPECIFICATION

Hardware

Operating System

Memory

Disk Drive

Monitor

Integrated Development Environment

Optimized C Compiler

Integrated Assembler Language

Hardware Level Debugging

Multiple Memory Models

Native Program Development

6.12 Queuing Models

Thursday, 9 May 2013

Implementation of Bankers Algorithm

MINI PROJECT ON RESOURCE SCHEDULING IN CPU USING BANKERS ALGORITHM By Brundha T GUIDE: Mr C Vignesh Manikandan

4.1 SPECIFICATION

Hardware

Operating System

Memory

Disk Drive

Monitor

Integrated Development Environment

Optimized C Compiler

Integrated Assembler Language

Hardware Level Debugging

Multiple Memory Models

Native Program Development

6.12 Queuing Models

MINI PROJECT ON RESOURCE SCHEDULING IN CPU USING BANKERS ALGORITHM

By Brundha T

GUIDE: Mr C Vignesh Manikandan