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++
3
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
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.
8
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.
11
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
P1
24
P2 3
P3 3
If the processes arrive in the
order P1,P2,P3, and are served in FCFS order,
the result is obtained as shown in the Gantt chart:
P1
|
P2
|
P3
|
0 24 27 30
The waiting time is 0 milliseconds for process P1,
24 milliseconds for process P2, and 27 milliseconds for process P3.
Thus, the average waiting time is (0+24+27)/3=17 milliseconds. If the processes
arrive in the order P2,P3,P1, the results will
be as shown in the following Gantt chart:
P2
|
P3
|
P1
|
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
P1 6
P2 8
P3 7
P4 3
Using SJF scheduling, these processes are scheduled
according to the following Gantt chart:
P4
|
P1
|
P3
|
P2
|
0 3 9 16 24
The
waiting time is 3 milliseconds for process P1, 16 milliseconds for
process P2, 9 milliseconds for process P3, and 0
milliseconds for process P4. 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.
15
The
next CPU burst is generally predicted as an exponential average of the measured
lengths of previous CPU bursts. Let tn be the length of the nth CPU
burst, and let Tn+1 be the predicted value for the next CPU burst.
Then, for α, 0 ≤ α ≤ 1, define
Tn+1= α tn+(1- α)Tn
This formula defines an exponential average. The value of tn
contains most recent information; Tn stores the past history in the prediction.
The parameter α controls the relative weight of recent and past history in the
prediction. If α=0, then Tn+1=tn, and only the most
recent CPU burst matters.
More commonly, α=1/2, so recent
history and past history are equally weighted. The initial T0 can be
defined as a constant or as an overall system average. Figure 6.1 shows an
exponential average with α=1/2 and T0=10.
To understand the behavior of the exponential average, the
formula for Tn+1 can be expanded by substituting for Tn,
to find
Figure 6.1: Prediction of the length of the next CPU burst
Tn+1=
α tn+ (1- α) α tn-1+…+ (1- α)j α tn-j+…+
(1- α)n+1T0
Since both α and (1- α) are less than or equal to 1, each
successive term has less weight than its predecessor.
16
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
P1 0 8
P2 1 4
P3 2 9
P4 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:
P1
|
P2
|
P4
|
P1
|
P3
|
0 1 5 10 17 26
Process P1 is started at time 0, since it is the
only process in the queue. Process P2 arrives at time 1. The
remaining time for process P1 (7 milliseconds) is larger than the
time required by process P2 (4 milliseconds), so process P1
is preempted, and process P 2
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 P1, P2, …, P5, with the length of the CPU
burst time given in milliseconds as an example:
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1
5
P5 5 2
Using priority scheduling, these processes are scheduled
according to the following Gantt chart:
P2
|
P5
|
P1
|
P3
|
P4
|
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.
18
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
P1 24
P2 3
P3 3
19
If
a time quantum of 4 milliseconds is used ,
then process P1 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 P2. Since
process P2 does not need 4 milliseconds, it quits before its time
quantum expires. The CPU is then given to the next process, process P3.Once
each process has received 1 time quantum, the CPU is returned to process P1
for an additional time quantum. The resulting RR schedule is
P1
|
P2
|
P3
|
P1
|
P1
|
P1
|
P1
|
P1
|
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
12
6
1
|
0
1
9
|
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.
21
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.
22
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.
23
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
24
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.
25
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.
27
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.
28
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
P1 10
P2 29
P3 3
P4 7
P5 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
29
P1
|
P2
|
P3
|
P4
|
P5
|
0 10 39
42 49 61
The waiting time is 0 milliseconds for process P1,
10milliseconds for process P2, 39 milliseconds for process P3,
42 milliseconds for process P4, and 49 milliseconds for process P5.
Thus, the average waiting time is (0+10+39+42+49)/5=28milliseconds.
With non-preemptive SJF scheduling, we execute the
processes as
P3
|
P4
|
P1
|
P5
|
P2
|
0 3 10 20 32
61
The waiting time is 10 milliseconds for process P1,
32 milliseconds for process P2, 0 milliseconds for process P3,
3 milliseconds for process P4 and 20 milliseconds for process P5.
Thus, the average waiting time is (10+32+0+3+20)/5=13 milliseconds.
With the RR algorithm, we execute the processes as
P1
|
P2
|
P3
|
P4
|
P5
|
P2
|
P5
|
P2
|
0 10
20 23 30 40 50 52
61
The waiting time is 0 milliseconds for process P1,
32 milliseconds for process P2, 20 milliseconds for process P3,
23 milliseconds for process P4 and 40 milliseconds for process P5.
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.
31
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.
32
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.
33
CHAPTER 7
INTRODUCTION TO SEMAPHORES
7.1 The Critical Section Problem
Consider
a system consisting of n processes {P0,P1, … ,Pn-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 Pi
entry section
|
critical section
remainder
section
|
remainder section
}while(1);
A
solution to the critical section problem must satisfy the following three
requirements:
1. Mutual Exclusion: If process Pi 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.
34
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);
}
}
35
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 {P0,
P1, …, Pn} of waiting processes must exist
36
such that P0 is waiting for a
resource that is held by P1, P1 is waiting for
a
resource that is held by P2,…,
Pn-1 is waiting for a resource that is held by Pn,
and Pn is waiting for a resource that is held by P0.
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,
37
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.
38
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.
39
Let R={R1,R2,…,Rm}
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 Ri.
After that, the process can request instances of resource type Rj if
and only if F(Rj)>F(Ri). 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 Rj,
it has released any resources Ri such that F(Ri)≥F(Rj).
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 {P0,P1,…,Pn},
where Pi is waiting for a resource Ri, which is held by process Pi+1.Then,
since process Pi+1 is holding resource Ri while requesting resource
Ri+1, we must have F(Ri)<F(Ri+1), for all
i. But this condition means that F(R0)<…<F(Rn)<F(R0).
By transitivity, F(R0)<F(R0), 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.
40
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 <P1,P2,…,Pn>
is a safe sequence for the current allocation state if, for each Pi,
the resources that Pi can still request can be satisfied by the currently
available resources plus the resources held by all the Pj, with
j<i. In this situation, if the resources that process Pi needs
are not immediately available, then Pi can wait until all Pj
have finished. When they have finished, Pi can obtain all of its
needed resources, complete its designated task, return its allocated resources,
and terminate. When Pi terminates, Pi+1 can obtain its
needed resources, and so on. If no such sequence exists, then the system state
is said to be unsafe.
41
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 Pi–›Rj indicates that process Pi may
request resource Rj at some time in the future. The edge resembles a
request edge in direction, but is represented by a dashed line. When process Pi
requests resource Rj, the claim edge Pi–›Rj is
converted to a request edge. Similarly, when a resource Rj is
released by Pi, the assignment edge Rj–›Pi is
reconverted to a claim edge Pi–›Rj. Before process Pi
starts executing, all its claim edges must already I the resource allocation
graph. We can relax this condition by allowing a claim edge Pi–›Rj
to be added to the graph only if all the edges associated with process Pi
are claim edges.
Suppose that process Pi
requests resource Rj. The request an be granted only if converting the
request edge Pi–›Rj to an assignment edge Rj–›Pi
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 n2
operations, where n is the number of processes in the system.an unsafe state.
Therefore, process Pi 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 Pi 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 P2 requests R2.
Although R2 is currently free, we cannot allocate it to P2,
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 P1 requests R2
and P2 requests R1then 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.
43
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 Rj available.
2. Max:
An n×m matrix defines the maximum demand of each process. If Max[i,j]=k, then process Pi may request at
most k instances of resource type Rj.
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 Pi is
currently allocated k instances of
resource type Rj.
4. Need: An n×m
matrix indicates the remaining resource need of each process. If Need[i,j]=k, then process Pi may need k more instances of resource type Rj to 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 Allocationi and Needi, respectively. The vector Allocationi specifies the resources currently allocated
to process Pi; the vector Needi specifies the
additional resources that process Pi
may still request to complete its task.
44
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+Allocationi
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 Requesti be the request
vector for process Pi. If Requesti[j]=k, then process Pi wants k instances of resource type Rj.
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-Requesti;
Allocationi:=Allocationi+Requesti;
Needi:=Needi-Requesti;
If the resulting resource-allocation
state is safe, the transaction is completed and process Pi is allocated its resources. If the new state is
unsafe, then Pi must wait
for Requesti and the old resources-allocation state
is restored.
45
8.5.3.1 An illustrative
Example
Consider the system with five processes P0
through P4 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 T0, the following snapshot of the system has been
taken:
Allocation Max Available
A
B C A B C A B C
P0
0 1 0 7
5 3 3 3 2
P1
2 0 0 3
2 2
P2
3 0 2 9
0 2
P3
2 1 1 2
2 2
P4
0 0 2 4
3 3
The content of the matrix Need is defined to be Max- Allocation
and is
Need
A B C
P0 7
4 3
P1 1
2 2
P2 6
0 0
P3 0
1 1
P4 4
3 1
We
claim that the system is currently in a safe state. The sequence
<P1, P3, P4,P2,
P0> satisfies the safety criteria. Suppose now that process P1
requests one additional instance of resource type A and two instances of
resource type C, so Request1=(1,0,2). To decide whether this request
can be immediately granted, we first check that Request1 ≤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
P0
0 1 0 7
4 3 2 3 0
P1
3 0 2 0
2 0
P2
3 0 2 6
0 0
P3
2 1 1 0
1 1
P4
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 <P1, P3, P4,
P0, P2> satisfies our safety requirement. Hence, the
request of process P1 can be granted immediately.
46
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!!";
}
50
void
main( )
{
bankers B;
clrscr( );
cout<<"
DEADLOCK BANKER’S ALGORITHM \n";
B.get( );
B.operation( );
B.display( );
getch( );
}
51
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.
52
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( )
53
Figure
A9.2: Flowchart for search( )
54
APPENDIX 4
9.4 SCREENSHOTS
Figure
A9.3: Screenshot for sample Input
55
Figure
A9.4: Screenshot for sample Input (Continuation)
Figure
A9.5: Screenshot for output
56
CHAPTER 10
REFERENCES
1.
Silberschatz/Galvin/Gagne
Sixth Edition “OPERATING SYSTEM CONCEPTS”.
57