Chapter-4: SCHEDULING

OBJECTIVES: -
- CPU scheduling is the basis of multiprogrammed operating systems. By switching the CPU among processes.
- Thus the operating system can make the computer more productive.

5.1 Basic Concepts: -

- In a single-processor system, only one process can run at a time, any others must wait until the CPU is free and
can be rescheduled.
- The objective of multiprogramming is to have some process running at times, to maximize CPU utilization. The
idea 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 then just sits idle. All this waiting time is wasted, no useful work is accomplished.
- With multiprogramming, we try to use this time, 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. Every time one process has to wait, another process can take over use of the CPU.
- Scheduling this kind is a fundamental operating-system function. Almost all computer resources are scheduled
before use. The CPU is, of course, one of the primary computer resources. Thus, its scheduling is central to
operating-system design.

5.2 Scheduling Criteria:-

- CPU utilization.
Conceptually, CPU utilization can range from 0 to 100 percent. In a real system, it should range from 40 percent
(for a lightly loaded system) to 90 percent (for a heavily used system).

- Throughput.
One measure of work is the number of processes that are completed per time unit, called throughput. For long
processes, this rate may be one process per hour; for short transactions, it may be 10 processes per second.

- Turnaround time.
One of 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 the ready queue, executing on the CPU, and doing I/O.

- 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.

- Response time.
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 until the
first response is produced.

- This measure, called response time, is the time it takes to start responding, not the time it takes to output the final
result.
- It is desirable to maximize CPU utilization and throughput and to minimize turnaround time, waiting time,
and response time.

OS-ch-4. SCHEDULING. Page 1

5.3 CPU-I/O Burst Cycle: -
- To realize the objective and criteria of scheduling, the scheduler must consider the system behavior of CPU and
I/O Burst Cycle.
- Process execution begins with a CPU burst. That is followed by an I/O burst, which is followed by another CPU
burst, then another I/O burst, and so on.
- This durations of CPU bursts have been measured extensively. Although they differ greatly from process to
process and from computer to computer.
- program might have a few long CPU burst, This distribution can be important in the selection of an appropriate
CPU-scheduling algorithm.

5.4. when scheduling happens/ condition when scheduling happen/ situation of 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.
2. When a process switches from the running state to the ready state.
3. When a process switches from the waiting state to the ready state (for e.g., at completion of I/O)
4. When a process terminates
Types of Scheduling : -
(1) Non-Preemptive Scheduling : -
- 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 was used by
Microsoft Windows 3.x;
- No other process are able to preempt (i.e. not able to interrupt) the current running process-
- (1) and (4) situation from above are the example of this.

(2) Preemptive Scheduling : -

- Under preemptive scheduling, once the CPU has been allocated to a process, the process can be preempted by the
other higher priority processes.
- This scheduling method was used by Microsoft Windows-95 and all the subsequent version of the windows operating
system.
- Other process are able to preempt (i.e. able to interrupt) the current running process.
- (2) and (3) situation from above are the example of this.

OS-ch-4. SCHEDULING. Page 2

- Preemptive scheduling incurs a cost associated with access to shared data. Consider the case of two processes that
share data. While one is updating the data, it is preempted so that the second process can run.

- The second process then tries to read the data, which are in an inconsistent state. In such situations, we need new
mechanisms to coordinate access to shared data.

- Preemption also affects 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 (for
instance, I/O queues). What happens if the process is preempted in the middle of these changes.

- Certain operating systems, including most versions 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.

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 the following:
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, since 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. And it should be as
min as possible.

5.4 Scheduling Algorithms: -

(1) First-Come, First-Served Scheduling: -

- With this scheme, the process that requests the CPU first is allocated the CPU first.
- The average waiting time under the FCFS policy, however, is often quite long.
- Consider the following set of processes that arrive at time 0, with the length of the CPU burst 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, we get the result shown in the following
Gantt chart:

- 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 = 51/3=17 milliseconds.
- If the processes arrive in the order P2, P3, P1, however, the results will be as shown in the following Gantt chart:

OS-ch-4. SCHEDULING. Page 3

 The average waiting time is now (6 + 0 + 3)/3 = 3 milliseconds.
 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 thus particularly troublesome for time sharing system where it is important that each user gets
a share of CPU at regular intervals.
 It would be disastrous to allow one process to keep the CPU for an extended period.

Advantage: -
- The implementation of the FCFS policy is easily managed with a FIFO queue.
- The code for FCFS scheduling is simple to write and simple to understand.

Disadvantage: -

- The average waiting time under an FCFS policy is generally not minimal and may vary substantially if the
process's CPU burst times vary greatly.
- The FCFS scheduling algorithm is non preemptive.
- The FCFS algorithm is thus particularly troublesome for time sharing system where it is important that each
user gets a share of CPU at regular intervals.
-

(2) Shortest-Job-First Scheduling: - [shortest-next-CPU-burst algorithm][shortest remaining time next.]

- A different approach to CPU scheduling is the shortest-job-first (SJF) scheduling algorithm.

- This algorithm associates with each process the length of the process's next CPU burst.
- When the CPU is available, it is assigned to the process that has the smallest next CPU burst.
- If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie.
- Note that a more appropriate term for this scheduling method would be the shortest-next-CPU-burst algorithm
because scheduling depends on the length of the next CPU burst of a process, rather than its total length.

- As an example of SJF scheduling, consider the following set of processes, with the length of the CPU burst given in
milliseconds : - [Note : this e.g. is same for SJF non-preemptive algorithm]

- Using SJF scheduling, we would schedule these processes according to the following Gantt chart:

- 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.
- By comparison, if we were using the FCFS scheduling scheme, the average waiting time would be 10.25
milliseconds.

OS-ch-4. SCHEDULING. Page 4

- Moving a short process before a long one decreases the waiting time of the short process Consequently, the
average waiting time decreases.

Advantage: -

- The SJF scheduling algorithm is optimal in that it gives the minimum average waiting time for a given set of
processes.
- SJF scheduling is used frequently in long-term scheduling.

Disadvantage: -

- The real difficulty with the SJF algorithm is knowing the length of the next CPU request. For long-term (job)
scheduling in a batch system, we can, use the length as the process time limit which is specified by user when he
submits the job.
- Thus, users are motivated to estimate the process time limit accurately, since a lower value may mean faster response.
(Too low a value will cause a time-limit-exceeded error and require resubmission.)

The SJF algorithm can be either preemptive or non preemptive. : --

- In preemptive SJF when a new process arrives at the ready queue while a previous process is still executing. Then the
next CPU burst of the newly arrived process may be shorter than 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.
- As an example, consider the following four processes, with the length of the CPU burst given in milliseconds:

- 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:

- Process P1 is started at time 0, since it is the only process in the queue. Process P2 arrives at time1. The remaining
time Tor process P1 (7 milliseconds) is larger than the time required by process P2 (4 milliseconds), so process P1 is
preempted, and process P2 is scheduled.

- The average waiting time for this example is ((10 - 1) + (1 - 1) + (17 - 2) + (5 - 3))/4 = 26/4 = 6.5 milliseconds.

- On the other hand Non preemptive SJF scheduling would result in an average waiting time of 7.75 milliseconds.

OS-ch-4. SCHEDULING. Page 5

(3) Priority Scheduling: -

- 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.
- The larger the CPU burst, the lower the priority, and vice versa.
Note: - This is for understanding only, no need to give in answers.
- Note that we discuss scheduling in terms of high priority and low priority. Priorities are
generally indicated by 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.
- We assume that low numbers represent high priority.
- 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 outside 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.

- As an example, 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 given in milliseconds:

- The Gantt chart will be as follows: -

--

- The average waiting time is 8.2 milliseconds.

- Priority scheduling can be either preemptive or non preemptive.
- When a process arrives at the ready queue, its priority is compared with the 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.

Advantage: -
- Easy to understand, It is not as complex as SJF.
- Scheduling is done on the basis of priority instead of CPU burst, this makes it easy to implement.

OS-ch-4. SCHEDULING. Page 6

Disadvantage: -

- A major problem with priority scheduling algorithms is indefinite blocking, or starvation. A priority scheduling
algorithm can leave some low-priority processes waiting indefinitely. In a heavily loaded computer system, a steady
stream of higher-priority processes can prevent a low-priority process from ever getting the CPU.
- Thus we have to use the priority Aging mechanism to deal with starvation problem.

[Note:- Aging mechanism for understanding, not be given in answer.]

- A solution to the problem of indefinite blockage of low-priority processes is aging.
Aging is a technique of gradually increasing the priority of processes that wait in the
system for a long time.

- For example, if priorities range from 127 (low) to 0 (high), we could increase the
priority of a waiting process by 1 every 15 minutes. Eventually, even a process with
an initial priority of 127 would have the highest priority in the system and would be
executed.

(4) Round-Robin Scheduling: -

- The round-robin (RR) scheduling algorithm is designed especially for timesharing 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.
- 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.
- 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.
- The average waiting time under the RR policy is often long. Consider the following set of processes that arrive at time
0, with the length of the CPU burst given in milliseconds:

- If we use a time quantum of 4 milliseconds, then the Gantt chart will be as follows: -

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

- In the RR scheduling algorithm, no process is allocated the CPU for more than 1 time quantum in a row (unless it is
the only run able process). 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 thus preemptive.

OS-ch-4. SCHEDULING. Page 7

- As the scheduling is based on time quantum, thus we want the time quantum to be large with respect to the context-
switch time.
-

Advantage: -
- Easy to understand.
- Easy to implement.

Disadvantage: -
- The performance of RR algorithm depends heavily on the size of the time quantum. if the time quantum is
extremely large, the RR policy is the same as the FCFS policy. If the time quantum is extremely small (say, 1
millisecond), then it incurs the overhead for continuously switching between process.
- Turnaround time also depends on the size of the time quantum, the average turnaround time of a set of processes does
not 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.

(5) Multilevel Queue Scheduling: -

- Another class of scheduling algorithms has been created for situations in which processes are easily classified into
different groups.
- For example, a common division is made between foreground (interactive) processes and background (batch)
processes.
- These two types of processes have different response-time requirements and so may have different scheduling needs.
- In addition, foreground processes may have priority (externally defined) over background processes.
- A multilevel queue scheduling algorithm partitions the ready queue into several separate queues.
- The processes are permanently assigned to one queue, generally based on some property of the process, such as
memory size, process priority, or 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 also, which is commonly implemented as fixed-priority
preemptive scheduling.
- For example, the foreground queue may have absolute priority over the background queue.
- Let's look at an example of a multilevel queue scheduling algorithm with five queues, listed below in order of priority:
1. System processes.
2. Interactive processes
3. Interactive editing processes
4. Batch processes
5. Student processes.

OS-ch-4. SCHEDULING. Page 8

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

Advantage: -
- low overhead as process does not changes its queue once it is assigned to any queue.

Disadvantage: -

- Processes are permanently assigned to a queue when they enter the system. That makes it inflexible.
- Process starvation may be there if the higher priority queue process are continuously executing.
- Turnaround time is more as compared to Multi-level feedback queue scheduling.

(6) Multilevel Feedback-Queue Scheduling: -

- The multilevel feedback-queue scheduling algorithm, in contrast, allows a process to move between queues.
- The idea is to separate processes according to the characteristics of their CPU bursts.
- 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.
- In addition, a process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This
form of aging prevents starvation.

- For example, consider a multilevel feedback-queue scheduler with three 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 time, 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 but are run 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 goes to queue 2 and are served in FCFS order with any CPU cycles left over from
queues 0 and 1.
- a multilevel feedback-queue scheduler is defined by the following parameters:
 The number of queue.
 The scheduling algorithm for each queue
 The method used to determine when to upgrade a process to a higher-priority queue
 The method used to determine when to demote a process to a lower-priority queue
 The method used to determine which queue a process will enter when that process needs service

OS-ch-4. SCHEDULING. Page 9

Advantage: -
- Turnaround time is less as compared to multilevel queue scheduling.
- More flexible than multilevel queue scheduling.
- Process starvation is eliminated.

Disadvantage: -
- Overhead of switching the process from one queue to another is present.

(7) Multiple-Processor Scheduling: -

- two approaches are there:-

- (a) Asymmetric multiprocessor scheduling : -
- If multiple CPUs are available, one processor is serving as master processor and all scheduling decisions, I/O
processing, and other system activities handled by that master processor i.e. the master server.
- The other processors execute only user code.
- This asymmetric multiprocessing is simple because only one processor accesses the system data structures,
reducing the need for data sharing.

- (b) Symmetric multiprocessor scheduling : -

- A second approach uses symmetric multiprocessing (SMP), where each processor is self-scheduling.
- All processes may be in a common ready queue, or each processor may have its own private queue of ready
processes.
- Scheduling proceeds by having the scheduler for each processor examine the ready queue and select a process to
execute on its own.
- But care should be taken that no two processor access the same process.
- Virtually all modern operating systems support SMP, including Windows XP, Windows 2000, Solaris, Linux, and
Mac OS X.

Issues concerning Symmetric multiprocessor scheduling : -

(l) Processor Affinity: -

- means once the process is assigned to any processor then the process must not migrate to another processor
and must complete its entire execution on the same assigned processor.
- if the process migrates to another processor: Then complete context switching has to be done.
- But because of the high cost of invalidating and re-populating caches, most SMP systems try to avoid migration
of processes from one processor to another and instead attempt to keep a process running on the same processor.
- This is known as processor affinity, meaning that a process has an affinity for the processor on which it is
currently running.

(2) Load Balancing: -

- Load balancing attempts to keep the workload evenly distributed across all processors in an SMP system.
- It is important to note that load balancing is typically only necessary on systems where each processor has its own
private ready queue.
- On Asymmetric- systems with a common run queue, load balancing is often unnecessary.
- There are two general approaches to load balancing: push migration and pull migration.
- With push migration, a specific task periodically checks the load on each processor and if it finds an imbalance
then evenly distributes the load by moving (or pushing) processes from overloaded processor to idle or less-busy
processors.
- Pull migration occurs when an idle processor pulls a waiting task from a busy processor to itself.

OS-ch-4. SCHEDULING. Page 10

DEAD LOCKS:-

- In a multiprogramming environment, several processes may compete for a finite / limited number of resources. A
process requests resources; and if the resources are not available at that time, the process enters a waiting state.
- Sometimes, a waiting process is NEVER again able to change state, because the resources it has requested are
held by other waiting processes. This situation is called a deadlock.

System Model: -

- A system consists of a finite number of resources to be distributed among a number of competing processes.
- The resources are partitioned into several types, each consisting of some number of identical instances.
- Memory space, CPU cycles, files, and I/O devices (such as printers and DVD drives) are examples of resource
types.
- If a system has two CPUs, then the resource type CPU has two instances. Similarly, the resource type printer may
have five instances.
- System model specify all of the available system resources which can be assigned to different processes.
- A process must request a resource before using it and must release the resource after using it. A process may
request as many resources as it requires to carry out its designated task.
- But the number of resources requested may not exceed the total number of resources available in the system.
- Under the normal mode of operation, a process may utilize a resource in only the following sequence:
o Request. If the request cannot be granted immediately (for example, if the resource is being used by
another process), then the requesting process must wait until it can acquire the resource.
o Use. The process can operate on the resource (for example, if the resource is a printer, the process can
print on the printer).
o Release. The process releases the resource.

- A system table records whether each resource is free or allocated; for each resource that is allocated, the table
also records the process to which it is allocated.
- If a process requests a resource that is currently allocated to another process, it can be added to a queue of
processes waiting for this resource.
- A set of processes is in a deadlock state when every process in the set is waiting for a resource that is held by
other process in the set.

Principle Necessary condition for deadlock: -

- A deadlock situation can arise if the following four conditions hold simultaneously in a system:
o 1. Mutual exclusion.[Mutex] 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.
o 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.
o 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 its task.
o 4. Circular wait. A set { P0, P1,..., Pn} of waiting processes must exist such that P0 is waiting for a
resource held by P1, P1 is waiting for a resource held by P2,and P2 is waiting for the resources held by
process P3 and so on.
- We emphasize that all four conditions must hold for a deadlock to occur.

- More on mutual exclusion : - [ Mutex ]

- The mutual-exclusion condition must hold for non sharable resources, for example, a printer cannot be
simultaneously shared by several processes.
- Sharable resources, in contrast, 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.

OS-ch-4. SCHEDULING. Page 11

 - 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.
- But we cannot prevent deadlocks by denying the mutual-exclusion condition, because some resources are
intrinsically/ by nature / implicitly non sharable.

The Critical-Section Problem: -

- The critical-section problem is designed for cooperating processes to share the sharable resources (i.e. common
resources.)
- This critical section is nothing but 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, no other
process is to be allowed, to execute in its critical section. That is, no two processes are executing in their
critical sections at the same time.

- 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.

- The general structure of a typical process P, is shown in Figure below.
Do
{
entry section

critical section

exit section
remainder section
} while (TRUE);

- Above block of code shows general structure of a typical process P for critical region.

- A solution to the critical-section problem must satisfy the following three requirements!
- 1- Mutual exclusion. If process P, 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 sections 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, or limit, 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.

Methods for Handling Deadlock: -

- We can deal with the deadlock problem in three different ways:

- (1) Deadlock prevention: -We can use a protocol to prevent or avoid deadlocks, ensuring that the system will
never enter a deadlock state.

OS-ch-4. SCHEDULING. Page 12

 - (2) Deadlock Avoidance: -We allocate the resources at software level and observe whether the system will be in
deadlock state or not, if safe then allocate else let the process wait.
- (3) Ignore: - We can ignore the problem altogether and pretend that deadlocks never occur in the system.

- The third solution is the one used by most operating systems, including UNIX and Windows; it is then up to the
application developer to write programs that handle deadlocks.

Deadlock prevention: - [also called as Peterson's solution]

- Provides a set of methods for ensuring that at least one of the necessary conditions of dead lock cannot hold.
- We examining each of the four necessary conditions separately.

- 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, in contrast, 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.
- But however, we cannot prevent deadlocks by denying the mutual-exclusion condition, because some resources
are intrinsically / implicitly / by nature non sharable.
- That is why it is not possible to avoid hold and wait.

- Hold and Wait

- To ensure that the hold-and-wait condition never occurs in the system, we must guarantee that, whenever a
process requests a resource, it does not hold any other resources.
- We can implement this provision by using protocol that allows a process to request resources only when it has
none.
- A process may request some resources and use them. And before it can request any additional resources, it must
release all the resources that it is currently allocated.
- But these protocols have two main disadvantages. First, low resource utilization, and Second, starvation of the
resources is possible.
- That is why again it is not possible to avoid hold and wait.

- No Preemption
- The third necessary condition for deadlocks is that there be no preemption of resources that have already been
allocated. To ensure that this condition does not hold by providing the preemption, we can use the following
protocol.
- (1) If a process is holding some resources and requests another resource that cannot be immediately allocated to it
(that is, the process must wait), then all resources currently being held are released and preempted by the
requesting process itself.
- 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 can regain its old resources, as well as the new ones that it is
requesting.

- (2) Alternatively, if a process requests some resources, we first check whether they are available. If they are, we
allocate them. If they are not, 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 neither available nor 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.

OS-ch-4. SCHEDULING. Page 13

 - 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, such as CPU registers and
memory space.
- It cannot generally be applied to such resources as printers and tape drives.

- Circular Wait
- to ensure that the fourth and final condition for deadlocks never happens we can impose a total ordering of all
resource types and to require that each process requests resources in an increasing order of enumeration.
- To illustrate, we let R = {Rl, R2, ..., Rn} be the set of resource types.
- We assign to each resource type a unique integer number, which, allows us to compare two resources and to
determine whether one precedes another in our ordering.
- 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 a resource type— say, R1. After that, the
process can request instances of resource type R2 and so on

- thus if R1 = tape drive and R2 = printer,

- and if 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 (i.e. in ascending order).

- But what if the process requires directly R2 and not the R1at all. Means reverse order, But this is contradicts to
our assumption.
- Thus we assume that even this scheme cannot be very foolproof.

- Thus we conclude that the deadlock can't be prevented by avoiding the necessary condition

DEAD LOCK AVOIDANCE: -

- Deadlock avoidance requires that the operating system be given in advance additional information about which
resources a process will request and use during its lifetime.
- With this additional knowledge, it can decide for each request 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
resource.
- For all of these purpose we use the following algorithm:-

Banker's Algorithm: -

- The name was chosen from banks philosophy that the bank will never allocate its available cash in such a way
that it could no longer satisfy the needs of all its customers.
- On the same line 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.
- Several data structures are maintained to implement the banker's algorithm. These are as follows:-

OS-ch-4. SCHEDULING. Page 14

 - Here P[i] = process, R[j] = resource type, k = instances of resource.

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

- Max.: An n x m matrix defines the maximum requirement / demand of each process. If Max[i][j]= k, then process
Pi, may require k instances of resource type Rj.

- Allocation. An n x 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.

- Need. An n x m matrix indicates the remaining resource needed by each process. If Need[i][j] = k, then process Pi
may need k more instances of resource type Rj to complete its task.

- An illustrative Example only for study and understanding:-

- Consider a system with five processes P0 through P4 and three resource types A, B, and 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:

- The content of the matrix Need is defined as Max — Allocation and is as follows:

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

- Suppose now that process P1 requests one additional instance of resource type A and two instances of resource
type C, so Request P1 = (1,0,2).
- To decide whether this request can be immediately granted, we check that Request <= Available
- that is, that (1,0,2) < (3,3,2), which is true. We then pretend that this request has been fulfilled, and we arrive at
the following new state:

OS-ch-4. SCHEDULING. Page 15

 - We must determine whether this new system state is safe. To do so, we execute our safety algorithm and find that
the sequence < P1, P3, P4, P0, P2 > satisfies the safety requirement. Hence, we can immediately grant the request
of process P1.
- But when the system is in this state, a request for (3,3,0) by P4 cannot be granted, since the resources are not
available.

Safety Algorithm: -

- We can now present the algorithm for finding out whether or not a system is in a safe state. This algorithm can be
described as follows:
- 1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available and Finish[i] =
false for i= 0, 1... n - 1.
- 2. Find an i such that both
-
 a. Finish[i] == false
 b. Need[i] < = Work
o If no such i exists, go to step 4.otherwise go to step 3

- 3. Work = Work + Allocation i

o Finish[i] = true
o Go to step 2.

- 4. if Finish[i] == true for all i, then the system is in a safe state.

- This algorithm may require an order of m x n operations to determine whether a state is safe.

Resource-Request Algorithm: -

- We now describe the algorithm which determines if requests can be safely granted.
- Let Request i be the request vector for process Pi. If Request i [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 Request i <= Need i, go to step 2. Otherwise, raise an error condition, since the process has exceeded its
maximum requirement.

- 2. If Request i <= Available, go to step 3. Otherwise, Pi must wait, since the resources are not available.

OS-ch-4. SCHEDULING. Page 16

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

o Available = Available - Request i

o Allocation i = Allocation i + Request i
o Need i = Need i - Request i;

- If the resulting resource-allocation state is safe, the transaction is completed, and process Pi is allocated its
resources.

OS-ch-4. SCHEDULING. Page 17