PROCESS MANAGEMENT

The O.S manages many kinds of activities ranging from user program to system programs like
spooler, print servers and proxy servers. Each of these activities is encapsulated in a process. A
process includes the complete execution context (code, data, program counters, register , and O.S
resources).
ACTIVITIES OF AN OPERATING SYSTEM IN REGARD TO PROCESS MANAGEMENT
1. Creation and deletion of user system process
2. Process synchronization
3. Process communication
4. Suspension and resumption of processes
5. Deadlock handling
A process is the unit of execution that has to follow a transition in execution.
MODEL OF A PROCESS CYCLE/PROCESS STATE
The process state consists of everything necessary used to resume a process execution.
A process state consists of at least the following
 Code for the program
 Program static data
 Program dynamic data
 Program procedure call stack
 Program counter
i. Blocking
A process waiting for some event to occur before continuing execution. The event could
be input/output operation where blocked do not require the CPU services, since
execution can’t proceed until the blocking events completes.
ii. Ready
A process that is not allocated to the CPU but its ready to execute
iii. Running
A process that is executing in the CPU.
iv. Terminating /Exit
A process that has halted execution but a record of its process is still maintained by the
OS which is referred to as Zombie process or if a process has successfully completed.
PROCESS TRANSITION
i. Null-New
It moves from Null to new state when it is created to execute a program
ii. New-Ready
When O.S moves processes from secondary memory to main memory.
However, there is a limit of processes that the main memory can hold.
iii. Ready-Running
It moves from ready to running when an O.S selects it for an execution.
iv. Running-Exit
It moves from running to exit if it has successfully terminated or halted.
v. Running-Ready
Moves from running to ready if it is empty or timed out
vi. Running –Blocked
If it is waiting for a request
vii. Blocked-Ready
If the request it was waiting has occurred
NOTE-A process can move from ready to exit if it is terminated by parental
process or parental request.
REASONS FOR TERMINATION
i. Normal completion of a process
 ii. Time limit exceeded i.e. if a process runs longer than specified
iii. Memory unavailable-A process can be terminated due to the two aspects:-
a. If an operating system cannot allocate a memory
b. If a process requires more memory than a system can provide.
iv. Bound violation-if a process tries to access memory allocation restricted
to it ,this will be terminated
v. Input/output failure-if mouse and keyboards are not functioning
vi. Arithmetic Errors-A process may try to perform illegal calculations e.g.
5/0
vii. Parental request-A parental process has authority to terminate any of its
offspring
viii. Operating system intervention-A process is terminated by O.S because of
some problems e.g. deadlock.
CHARACTERISTICS OF A SUSPENDED PROCESS
1. The process is not immediately available for execution
2. Process waiting for an event to occur
3. A suspended process placed in a suspended queue by an agent.
REASONS WHY A PROCESS MAY BE SUSPENDED
i. Swapping –This involves moving parts or all of the process from
main memory to disk
ii. Problematic process
iii. User request-It might be suspended for debugging
iv. Timing
v. Parental process request –A parent suspends a child process in
order to examine it.
PROCESS CONTROL BLOCK (PCB)/PROCESS DESCRIPTOR
It is a data block that describes the process to the O.S .With the PCB; the O.S can manipulate all
parts of the program state
The PCB is a data structure maintained by the O.S for every process. PCB is identified by an
integer process i.e. process ID
A PCB identifies a process by keeping all the information needed to keep track all the process
The architecture of a PCB is completely dependent on O.S and may contain different information
in different O.S

A STRUCTURE OF A PCB

 Process ID-It is a unique identification for each of the process in the operating
system(O.S)
 Process state – It is the current state of the process i.e. ready, running e.t.c.
 Pointer – It is a pointer or an address of the next process
 Priority (CPU scheduling information) – It refers to the process that requires the
CPU first
 Program Counter – it is the address of the next instruction to be executed for this
process.
 Program / CPU registers – Refers to various CPU registers where process need to
be stored for execution for running state.
 I/O status information – It includes a list of I/O devices allocated to the process
 PROCESS SCHEDULING/SCHEDULAR
In multiprocessing, scheduling is used to determine which process is given control of
the CPU. It is an O.S program that selects the next job to be admitted by the CPU.
It controls the order in which work is done and completed by the processor/CPU.

The process scheduling is the activity of the process manager that handles the removal of the
running process from the CPU and the selection of another process on the basis of a particular
strategy.
Process scheduling is an essential part of a Multiprogramming operating system. Such operating
systems allow more than one process to be loaded into the executable memory at a time and
loaded process shares the CPU using time multiplexing.
Scheduling Queues
Scheduling queues refers to queues of processes or devices. When the process enters into the
system, then this process is put into a job queue. This queue consists of all processes in the
system. The operating system also maintains other queues such as device queue. Device queue
is a queue for which multiple processes are waiting for a particular I/O device. Each device has
its own device queue.
This figure shows the queuing diagram of process scheduling.
 Queue is represented by rectangular box.
 The circles represent the resources that serve the queues.
The arrows indicate the process flow in the system.

Queues are of two types

 Ready queue
  Device queue

A newly arrived process is put in the ready queue. Processes waits in ready queue for allocating the
CPU. Once the CPU is assigned to a process, then that process will execute. While executing the
process, any one of the following events can occur.

 The process could issue an I/O request and then it would be placed in an I/O queue.

 The process could create new sub process and will wait for its termination.

 The process could be removed forcibly from the CPU, as a result of interrupt and put back
in the ready queue.

Two State Process Model

Two state process model refers to running and non-running states which are described below.

S.N. State & Description

1 Running
When new process is created by Operating System that process enters into the system
as in the running state.

2 Not Running
Processes that are not running are kept in queue, waiting for their turn to execute.
Each entry in the queue is a pointer to a particular process. Queue is implemented by
using linked list. Use of dispatcher is as follows. When a process is interrupted, that
process is transferred in the waiting queue. If the process has completed or aborted,
the process is discarded. In either case, the dispatcher then selects a process from the
queue to execute.

FUNCTIONS OF A PROCESS SCHEDULAR

1. Increases the CPU utilization thus CPU executing many times
2. Support multiprogramming i.e. the CPU is scheduled in O.S to allow several
programs to be executed and re-organized in the memory at the same time
3. Increases response time- This is the time for the submission of a request until the
first response is activated or accepted.
OBJECTIVES OF SCHEDULING
1. Maximize the system throughput
2. Provide tolerable response
 3. Consistent and predictable
TYPES /PHASES OF SCHEDULARS
a. Long term scheduling
 It is also known as job scheduler or high level scheduler. It determines the jobs to
be admitted for immediate processing where it selects processes from solid
devices like flash disk, hard disk e.t.c. to load them into the memory.
Solid state device-------------memory
 It executes less frequently than the short term scheduler
 It is a scheduler which selects processes that are supposed to be brought in the
ready queue
 It is only invoked when a processor departs from the system.
b. Short term scheduling
 It is also known as CPU scheduler or dispatcher where it selects processes from
the ready queue and assigns the CPU to one of them.
 Selects which process should be executed next and allocates CPU.
 It executes more frequently than the long term scheduler.
c. Medium term scheduler
 It is also known as a swapper which swaps processes in and out of the memory
 It is an interchange/exchange of swapping in and out processes
 Swapping out – is removing the process out of the memory when a
process is suspended. It can be suspended for I/O operations after being
executed for a while
 Swapping in – is returning it from suspended to ready queue. The medium
term scheduler is activated when the suspended condition is fulfilled.
SWAPPING
 Swapping is a mechanism in which a process can be swapped temporary or removed
temporary out of the main memory to secondary storage (disk) and make that memory
available to other processes.
 Through this sapping, the performance is affected because it helps in running multiple
and big processes in parallel .That’s why swapping is known as a technique of memory
compaction
In swapping it is used to free space in main memory

PERFORMANCE CRITERIA USED BY SCHEDULER TO MAXIMIZE THE

PERFORMANCE
1. CPU utilization
 It is high if the CPU is busy all the time
 The scheduler tries to make the CPU busy by providing processes at all time.
 For a single user system, the CPU utilization is not important but for time shared
system, CPU utilization is important.
2. Throughput
 Is the amount of work completed in a unit of time
 Each task consists of several processes i.e. the higher the number of processes
completed in a unit of time, there is more work to be done by the CPU.
3. Turn-around time
 It is the interval from the time of submission of a process to the time of is
completion
 It is the average time a process takes to execute and this may include the time the
process spends on the system which can be obtained as follows:-
TAT= Time process was terminated –Time process was created
 T.A.T can also be the time spent waiting to get into the memory, waiting time
in the ready queue, CPU time and input/ output operations.
4. Waiting Time
 It is the average time a process spends waiting to be executed which is expressed
as follows
Waiting time=T.A.T-Burst time/execution time/ processing time
5. Response time
 It is the time taken by the system to respond to users input
 It is the interval from the time the last character or command line of a program is
executed i.e. to be from the time the last result appeared on the terminal.
6. Fairness
 7. Priorities
SCHEDULING ALGORITHMS
These are policy used to determine which of the process in a ready queue is to be
allocated to the CPU.
We have two broad classification of algorithm
 Pre-emptive
 Non-preemptive
Pre-emptive algorithm
In this case, once a process has been assigned to the CPU, the CPU can be taken away from the
process before the process has completed execution i.e. even if the process is not fully executed,
the CPU can be taken away from that process.
Non-preemptive
Once a process is given to the CPU, the CPU cannot be taken away from the process. In non non
preemptive system, jobs are meant to wait for a long time i.e. smaller jobs suffers from this
algorithm.
It is more useful in low priority process e.g. FCFS can be used as a preemptive algorithm which
is a high priority process algorithm which requires immediate response.
FIFO/FCFS ALGORITHM
 In this algorithm, jobs are scheduled in the order they are received. FCFS tends to favor
CPU bound processes.
 Implementation is a accomplished by implementing a queue of the processes to be
scheduled/ storing the time the process was received.
 It is a non-preemptive scheduling algorithm which is easy to understand and implement
 This method is poor in performance as average waiting time is high.
Advantages of FCFS
 Easy to understand i.e. with this algorithm, single linked keeps track of all ready
processes.
 It is equally fair
 Suitable especially for batch O.S
Disadvantages
  Not suitable for time sharing system. It is important that each user should get
the CPU for an equal amount of arrival time

Process Wait Time : Service Time - Arrival Time

P0 0-0=0

P1 5-1=4

P2 8-2=6

P3 16 - 3 = 13

Average Wait Time: (0+4+6+13) / 4 = 5.75

ROUND-ROBIN
 It is an algorithm that selects the job that has been waiting the longest time i.e.
in this algorithm we assign equal CPU time. This is a pre-emptive scheduling
 Interrupts from an interval timer ensures that processing is suspended and
control transferred to the scheduling algorithm at the conclusion of the time
quantum
  Round robin is used extensively in time sharing system.
 Each process is provided a fixed time to execute ,which is called
Quantum/Time slices.
 In round robin, once a process is executed for a given time period, that process
is preempted and other process execute for a given time period

Wait time of each process is following

Process Wait Time : Service Time - Arrival Time

P0 (0-0) + (12-3) = 9

P1 (3-1) = 2

P2 (6-2) + (14-9) + (20-17) = 12

P3 (9-3) + (17-12) = 11

Average Wait Time: (9+2+12+11) / 4 = 8.5

Shortest job first algorithm

 In this algorithm, the O.S selects the shortest expected processing
time.
 In case of tie, FCFS algorithm can be used
 SJF favors short jobs over long ones and it can lead of starvation of
long ones.
  This is a non pre-emptive scheduling algorithm which has a best
approach to minimize waiting time.
 This algorithm is impossible to implement.
 The best approach to this SJF is that the processor should know in
advance how much time a process should take.
 Shortest job first (SJF) being a non preemptive algorithm can allow
other process to wait for the execution thus becomes the shortest
remaining job.
Shortest remaining jobs/shortest remaining time first scheduling
algorithm
 It’s a non preemptive version of the SJF algorithm or a preemptive
version of the shortest first job thus called shortest remaining time next
algorithm
 In this algorithm, if new process time is less, the currently scheduled,
process is preempted
 Long jobs using this method can be starved
 The processor is allocated to the job closest to completion but it can be
preempted by a newer ready job with shorter time to completion.
 This algorithm is impossible to implement in interactive systems where
required CPU time is not known.
Process Wait Time : Service Time - Arrival Time

P0 3-0=3

P1 0-0=0

P2 16 - 2 = 14

P3 8-3=5

Average Wait Time: (3+0+14+5) / 4 = 5.50

Priority based scheduling

 This is where each process is assigned a priority value and the process to
run is the one with the highest priority.
 In case of a tie, FCFS is used

Wait time of each process is following

Process Wait Time : Service Time - Arrival Time

P0 9-0=9

P1 6-1=5

P2 14 - 2 = 12

P3 0-0=0

Average Wait Time: (9+5+12+0) / 4 = 6.5

Multi-level algorithm
 The major disadvantages with the previous algorithms is that they basically
treat all jobs the same
 Multi level queuing addresses this deficiency by customizing the scheduling of
a process based on the processes performance characteristics
 This algorithm implements two or more scheduling queues i.e. (combination of
various algorithms together )
 An entering process is inserted into the top level queue (high level).
 Selected processes are allocating a time slices where upon expiration of a time
slice, the process is moved to the next lower queue.
 If a process blocks before using its entire time slice, it is moved to the next
higher queue or to the top level queue.
 If a process enters a high level queue, while a process of lower level queue is
executing, the low level queue may be pre-empted
PROCESS INTERRUPTS
 An interrupt is a signal sent to the CPU by an external device typically I/O
devices.
 This is an event that causes the CPU to temporarily transfer its control from
currently executing program to different programs
 The interrupt requests the CPU to interrupt its current activities and attend to
the interrupting device needs
 It is a signal sent to the CPU by an external device for any attention in need
 The CPU responds to traps and interrupts by saving the current value of the
program counter and resetting it to a new address.
 This allows the CPU to return to execution at point where it stopped before the
interrupt or trap occurred.
TYPES /CLASSES OF INTERRUPTS
i. Programmed interrupt
It is generalized by some conditions which occurs during program execution
e.g. division by zero, arithmetic overflow, trying to reference a location
outside a user allowed memory space.
ii. Timer interrupt
Generated by timer or clock within the processor. This allows the O.S to
perform certain functions on regular basis e.g. if a user downloading some
programs, there can be a timer interrupt if time elapses.
iii. Input/ output interrupt
Generated by I/O controller to signal normal completion of an operation or to
signal a variety of error condition.
iv. Hardware failure
It is caused by power failure i.e. catastrophic failure or brute force failure.
PURPOSE OF INTERRUPTS
1. To alert the O.S when a special event occurs so that it can suspend its activities
and deal with the situation
2. The interrupt improves the efficiency of computer system
DEADLOCK AND STARVATION
  It is also called deadly embrace.
 Deadlock occurs when two or more processes block waiting for an event to
occur which is under control of other blocked processes. E.g. a process A
sends messages to process B through one mail box and process B sends
message to process A through the second mail box.
 Consider what happens if both processes attempt to read an incoming message
before they send a message, both will be in lock waiting.
 For other processes to send a condition that can never be satisfied.
 A deadlock is a permanent blocking of several processes that either compete
for a resource or communicate with each other.
CONDITIONS THAT CHARACTERIZE A DEADLOCK
The following conditions are necessary for a deadlock to occur.
1. Mutual exclusion
Each resource maybe allocated to any resource at any instant i.e. No resource can be
shared by more than one process at a time
2. Hold and wait
A process will not release previously granted resource while waiting for a pending
request to be granted. I.e. A process may hold a located resource while waiting
assignment of other resources.
3. Non- preemptive
No resource can be forcibly removed from a process holding it. i.e. A resource can not be
preempted until it is complete.
4. Circular wait
There exist a chain of two or more processes such that each process in the chain is
holding a resource requested by the next process in the chain.

STRATEGIES OF DEADLOCK/STRATEGIES FOR HANDLING DEADLOCK

1. Deadlock prevention
 This is achieved by making that the condition does not occur.
 Prevents deadlock by retraining requests made to ensure that at least one of the
four deadlock condition do not occur.
 The prevention of deadlock can be carried out using two methods:-
o Indirect method- preventing the occurrence of the above conditions
o Direct method- Preventing the occurrence of circular wait
 In deadlock prevention , solves the above conditions through the use of the
following strategies in prevention;
o Mutual exclusion- if access to a resource requires mutual exclusion, then
it must be supported by the operating system. This condition cannot be
disallowed because most of the resources are by nature they are not
sharable. To prevent deadlock using mutual exclusion allow only one
process at a time to access resource.
o Hold and wait –it can be prevented by allowing a process request be
granted all of the resources it needs at once prior to execution. It can also
be avoided by disallowing a process from requesting resources whenever
it has previously been allocated resources. This strategy requires that all of
the resources a process will need must be requested at once. This strategy
can lead to a serious waste of the resources which results to in-efficient
due to the following reasons:-
 Since a process may sped a long time waiting for all its requests
to be filled when it would have only proceeded with one
resource.
 A resource allocated to a process may remain un-used for a
long time when they have been denied from other process
 Another problem is that a process may not know in advance
what resource it will require.
o No preemption-it can be prevented through:-
 Denying a process further request until it releases any
resource it’s holding.
 The O.S preempting a second process by requiring it to
release the resource its holding.
o Circular wait
  This can be prevented by defining a linear ordering of resource
types
 If a process has been allocated resources of type R, then, it may
subsequently request only those resources of type following R
 This method can only be prevented through the use of a graph that
is called wait for graph
2. Deadlock avoidance strategy
 In deadlock prevention, resources requests are constrained to prevent the four
conditions of deadlock. This leads to inefficient use of resources and inefficient
execution of processes.
 Deadlock avoidance allows the four conditions but allow judicious choices to
assure that deadlock point is never reached.
 With deadlock avoidance a decision is made dynamically whether the current
resource allocation request granted will lead to a deadlock.
 The problem with this method is that it requires knowledge of future resource
request of process.
 There are two main approaches to deadlock avoidance:-
 Do not start a process if its demand might lead to a deadlock referred to as
process initiation denial. Process initiation denial- A simple way is to
allocate a resource on only one process at a time using this method, if a
process A request a resource held by process B, then make sure that
process B is not waiting for a resource held by A,
 Do not grant an incremental resource request to a process if this allocation
might lead to deadlock referred to as resource allocation denial.
3. Deadlock detection strategy
 Deadlock detection does not limit resource access or restrict process as opposed to
deadlock prevention to limit access to resources by imposing restriction on
processes.
 With deadlock detection, requested resources are granted processes whenever
possible
  A resource allocation graph may be used to model the state of resource allocation
and request.
INTER-PROCESS COMMUNICATION (I.P.C) AND SYNCHRONIZATION
 A process need to communicate with other processes in a computing system.
 It describes the method used to pass information between two processes running on the
same computer/network environment.
 A process communicates with each other by shared memory or message passing.
 Message passing is passing messages or information from one computer to another. In
I.P.C, files are the mechanism used for information sharing.
 Information written into a file by one process can read by another process. The
information that can be shared is limited by the file size capacity of the file system.
 Shared memory location provides another mechanism for information sharing where
some O.S supports a supervisor call that creates a shared memory space. Many O.S
support an explicit messaging system for sending messages between processes.
 Message -------is a collection of data object consisting of a fixed size header and a
variable or constant length body, which can be managed by a process and delivered to its
destination
FACTORS USED IN DESIGNING MESSAGE SYSTEM
 Kind of object a message is sent
 Association of a process with message object
 Number of processes that may share a message object
PROCESS SYNCRONIZATION
 When two or more processes are reading or writing some shared data and the final result
depends on who runs precisely when are referred to as race condition
 The scheduling algorithm determines the relative timing of cooperating process through
synchronization which controls access to critical section.
 Synchronization ----is a set of constraints that falls events/processes to execute in a given
order. Synchronization is necessary during I.P.C where processes communicate with each
other by sharing data.
 To achieve successful communication between processes there must be a certain point of
which process must synchronize their activities.
  Most O.S provides services for synchronization for a process i.e. process that produces
output for printing may not be able to proceed until figures of output is printed.
 There are various synchronization condition /mechanisms which includes:--
o Relative speed
o No indivisibility---No two processes may be reading/writing to a memory location
simultaneously.
o Bounded use----A process only executes in the critical section for a given time
and not be terminated when in critical section.
o Ensuring correctness-----it’s a mechanism to control access to critical section
through satisfying the following:
 Mutual exclusion
 Progress----A process that terminates outside the critical section may not
prevent other process to enter the critical section.
There are two types of I.P.C
 Cooperating/shared/synchronized
 Non cooperating/unshared/asynchronous

COOPERATING PROCESSES
Cooperating process is a process that refers to two or more processes sharing some files in an
operating system. In cooperating process, independent process can not affect or be affected by
execution of another process
Advantages
 Information sharing
 Computational speed up
 Modularity
 Convenience
To avoid this effect of affecting each other, cooperating process uses the following approach:-
 No two processes may be simultaneously inside their critical region or section
 No process should have to wait forever to enter its critical section.
 No process running outside of its critical section may block other processes.
In process cooperation there are two main systems call used in IPC namely.
 Sleep
A sleep system call is called when a process is not permitted to access its critical section
It is a system call that causes a process to be suspended until any other process wakes it
up so it’s blocked.
 Wake-up
If a process has been blocked will not be scheduled to run until another process uses the
wake-up system calls.
In most cases, wake-up is called by a process hen it leaves the critical section if any
other process has been blocked.
NOTE
On producer –consumer approach problem i.e. when a producer want to put a new
data in a buffer but the buffer is already full, the solution to this is that the producer goes
to sleep and wake-up when the consumer has removed the data.
REMOTE PRODURE CALL
It is a technique by which two processes on different machine interacts using procedure
calls/return syntax and semantics or rules.
In R.P.C, both the called and the calling process behave as if the process were running on
the same machine.
Reasons for R.P.C
o Ease of use
o Efficient and has a well defined interface