OPERATING SYSTEM – PROCESS MANAGEMENT
Process management
Process Concept
• Informally, a process is a program in execution. A process is more than the
program code, which is sometimes known as the text section. It also includes the
current activity, as represented by the value of the program counter and the
contents of the processor's registers. In addition, a process generally includes the
process stack, which contains temporary data (such as method parameters,
return addresses, and local variables), and a data section, which contains global
variables.
• An operating system executes a variety of programs:
✦ Batch system – jobs
✦ Time-shared systems – user programs or tasks
• Process – a program in execution; process execution must progress in
sequential fashion.
• A process includes: program counter , stack, data section
Difference between process and program
Parameter Process Program
A program is a group of ordered
An executing part of a program is
Definition operations to achieve a
called a process.
programming goal.
The nature of the program is
The process is an instance of the
Nature passive, so it's unlikely to do to
program being executing.
anything until it gets executed.
Resource The resource requirement is quite high The program only needs memory
management in case of a process. for storage.
MANJULA PRASAD 1
OPERATING SYSTEM – PROCESS MANAGEMENT
Parameter Process Program
Processes have considerable
Overheads No significant overhead cost.
overhead.
The process has a shorter and very A program has a longer lifespan as
Lifespan limited lifespan as it gets terminated it is stored in the memory until it is
after the completion of the task. not manually deleted.
New processes require duplication of
Creation No such duplication is needed.
the parent process.
The program is stored on disk in
Required Process holds resources like CPU,
some file and does not require any
Process memory address, disk, I/O, etc.
other resources.
A program is a passive or static
Entity type A process is a dynamic or active entity.
entity.
A process contains many resources like A program needs memory space on
Contain
a memory address, disk, printer, etc. disk to store all instructions.
Process state diagram
Process State
MANJULA PRASAD 2
OPERATING SYSTEM – PROCESS MANAGEMENT
As a process executes, it changes state
• New State: The process is being created.
• Running State: A process is said to be running if it has the CPU, that is,
process actually using the CPU at that particular instant.
• Blocked (or waiting) State: A process is said to be blocked if it is waiting for
some event to happen such that as an I/O completion before it can
proceed. Note that a process is unable to run until some external event
happens.
• Ready State: A process is said to be ready if it needs a CPU to execute. A
ready state process is runnable but temporarily stopped running to let
another process run.
• Terminated state: The process has finished execution.
Process Control Block (PCB)
Information associated with each process.
• Process state
MANJULA PRASAD 3
OPERATING SYSTEM – PROCESS MANAGEMENT
• Program counter
• CPU registers
• CPU scheduling information
• Memory-management information
• Accounting information
• I/O status information Process state: The state may be new, ready, running,
waiting, halted, and SO on.
Program counter: The counter indicates the address of the next instruction to be
executed for this process.
CPU registers: The registers vary in number and type, depending on the computer
architecture. They include accumulators, index registers, stack pointers, and
general-purpose registers, plus any condition-code information. Along with the
program counter, this state information must be saved when an interrupt occurs,
to allow the process to be continued correctly afterward.
CPU-scheduling information: This information includes a process priority, pointers
to scheduling queues, and any other scheduling parameters.
Memory-management information: This information may include such
information as the value of the base and limit registers, the page tables, or the
segment tables, depending on the memory system used by the operating system.
Accounting information: This information includes the amount of CPU and real
time used, time limits, account numbers, job or process numbers, and so on.
status information: The information includes the list of I/O devices allocated to
this process, a list of open files, and so on. The PCB simply serves as the repository
for any information that may vary from process to process.
Thread
A thread, sometimes called a lightweight process (LWP), is a basic unit of CPU
utilization; it comprises a thread ID, a program counter, a register set, and a stack.
It shares with other threads belonging to the same process its code section, data
section, and other operating-system resources, such as open files and signals. A
traditional (or heavyweight) process has a single thread of control. If the process
has multiple threads of control, it can do more than one task at a time.
MANJULA PRASAD 4
OPERATING SYSTEM – PROCESS MANAGEMENT
Advantages of Threads
1. Responsiveness: Multithreading an interactive application may allow a
program to continue running even if part of it is blocked or is performing a
lengthy operation, thereby increasing responsiveness to the user.
2. Resource sharing: By default, threads share the memory and the resources of
the process to which they belong. The benefit of code sharing is that it allows
an application to have several different threads of activity all within the same
address space.
3. Economy: Allocating memory and resources for process creation is costly.
Alternatively, because threads share resources of the process to which they
belong, it is more economical to create and context switch threads. It can be
difficult to gauge empirically the difference in overhead for creating and
maintaining a process rather than a thread, but in general it is much more time
consuming to create and manage processes than threads. In Solaris 2, creating
a process is about 30 times slower than is creating a thread, and context
switching is about five times slower.
4. Utilization of multiprocessor architectures: The benefits of multithreading
can be greatly increased in a multiprocessor architecture, where each thread
may be running in parallel on a different processor. A single threaded process
can only run on one CPU, no matter how many are available.
Inter Process Communication (IPC)
A process can be of two types:
• Independent process.
MANJULA PRASAD 5
OPERATING SYSTEM – PROCESS MANAGEMENT
• Co-operating process.
An independent process is not affected by the execution of other processes while a
co-operating process can be affected by other executing processes. Though one can
think that those processes, which are running independently, will execute very
efficiently, in reality, there are many situations when co-operative nature can be
utilised for increasing computational speed, convenience and modularity. Inter
process communication (IPC) is a mechanism which allows processes to
communicate with each other and synchronize their actions. The communication
between these processes can be seen as a method of co-operation between them.
Processes can communicate with each other through both:
1. Shared Memory
2. Message passing
Shared Memory: Communication between processes using shared memory
requires processes to share some variable and it completely depends on how
programmer will implement it.
Message Passing: processes communicate with each other without using any kind
of shared memory.
We need at least two primitives:
– send(message, destinaion) or send(message)
– receive(message, host) or receive(message)
Cooperating Processes
The concurrent processes executing in the operating system may be either
independent processes or cooperating processes. A process is independent if it
cannot affect or be affected by the other processes executing in the system.
Advantages of process cooperation
Information sharing: Since several users may be interested in the same piece
of information (for instance, a shared file), we must provide an environment to
allow concurrent access to these types of resources.
MANJULA PRASAD 6
OPERATING SYSTEM – PROCESS MANAGEMENT
Computation speedup: If we want a particular task to run faster, we must
break it into subtasks, each of which will be executing in parallel with the
others. Such a speedup can be achieved only if the computer has multiple
processing elements (such as CPUS or I/O channels).
Modularity: We may want to construct the system in a modular fashion,
dividing the system functions into separate processes or threads
Convenience: Even an individual user may have many tasks on which to work
at one time. For instance, a user may be editing, printing, and compiling in
parallel. Concurrent execution of cooperating processes requires mechanisms
that allow processes to communicate with one another and to synchronize
their actions.
Process Scheduling Queues
• Job Queue: This queue consists of all processes in the system; those
processes are entered to the system as new processes.
• Ready Queue: This queue consists of the processes that are residing in
main memory and are ready and waiting to execute by CPU. This queue
is generally stored as a linked list. A ready-queue header contains
pointers to the first and final PCBs in the list. Each PCB includes a pointer
field that points to the next PCB in the ready queue.
• Device Queue: This queue consists of the processes that are waiting for a
particular I/O device. Each device has its own device queue.
Schedulers
A scheduler is a decision maker that selects the processes from one scheduling
queue to another or allocates CPU for execution. The Operating System has
three types of scheduler:
MANJULA PRASAD 7
OPERATING SYSTEM – PROCESS MANAGEMENT
1. Long-term scheduler or Job scheduler
2. Short-term scheduler or CPU scheduler
3. Medium-term scheduler
Long-term scheduler or Job scheduler
The long-term scheduler or job scheduler selects processes from discs and
loads them into main memory for execution. It executes much less frequently.
It controls the degree of multiprogramming (i.e., the number of processes in
memory).
Because of the longer interval between executions, the long-term scheduler
can afford to take more time to select a process for execution.
Short-term scheduler or CPU scheduler
The short-term scheduler or CPU scheduler selects a process from among
the processes that are ready to execute and allocates the CPU.
The short-term scheduler must select a new process for the CPU frequently.
A process may execute for only a few milliseconds before waiting for an I/O
request.
Medium-term scheduler
The medium-term scheduler schedules the processes as intermediate level of
scheduling Processes can be described as either:
✦I/O-bound process – spends more time doing I/O than computations, many
short CPU bursts.
✦CPU-bound process – spends more time doing computations; few very long
CPU bursts.
MANJULA PRASAD 8
OPERATING SYSTEM – PROCESS MANAGEMENT
Context Switch
• When CPU switches to another process, the system must save the state of
the old process and load the saved state for the new process.
• Context-switch time is overhead; the system does no useful work while
switching.
CPU Scheduling
• Basic Concepts
• Scheduling Criteria
• Scheduling Algorithms
• Multiple-Processor Scheduling
• Real-Time Scheduling
• Algorithm Evaluation
Basic Concepts
• Maximum CPU utilization obtained with multiprogramming
• CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution
and I/O wait.
• CPU burst distribution
CPU Scheduler
• Selects from among the processes in memory that are ready to execute, and
allocates the CPU to one of them.
• CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state.
MANJULA PRASAD 9
OPERATING SYSTEM – PROCESS MANAGEMENT
2. Switches from running to ready state.
3. Switches from waiting to ready.
4. Terminates.
• Scheduling under 1 and 4 is non preemptive.
• All other scheduling is preemptive.
Dispatcher
Dispatcher module gives control of the CPU to the process selected by the
short-term scheduler; this involves:
✦ switching context
switching to user mode
✦ jumping to the proper location in the user program to restart that program
Dispatch latency – time it takes for the dispatcher to stop one process and
start another running.
Preemptive Scheduling is a scheduling method where the tasks are mostly
assigned with their priorities. Sometimes it is important to run a task with a higher
priority before another lower priority task, even if the lower priority task is still
running.
Non-Preemptive Scheduling:
Non-preemptive Scheduling is used when a process terminates, or a process
switches from running to waiting state. In this scheduling, once the resources (CPU
cycles) is allocated to a process, the process holds the CPU till it gets terminated or
it reaches a waiting state.
MANJULA PRASAD 10
OPERATING SYSTEM – PROCESS MANAGEMENT
PARAMENTER PREEMPTIVE SCHEDULING NON-PREEMPTIVE SCHEDULING
Once resources(CPU Cycle) are
In this resources(CPU Cycle)
allocated to a process, the process
Basic are allocated to a process for a
holds it till it completes its burst time or
limited time.
switches to waiting state.
Interrupt Process can be interrupted in Process can not be interrupted untill it
between. terminates itself or its time is up.
Starvation If a process having high priority If a process with long burst time is
frequently arrives in the ready running CPU, then later coming
queue, low priority process may process with less CPU burst time may
starve. starve.
Overhead It has overheads of scheduling It does not have overheads.
the processes.
Flexibility flexible Rigid
Cost cost associated no cost associated
CPU In preemptive scheduling, CPU It is low in non preemptive scheduling.
Utilization utilization is high.
Examples Examples of preemptive Examples of non-preemptive
scheduling are Round Robin scheduling are First Come First Serve
and Shortest Job First.
MANJULA PRASAD 11
OPERATING SYSTEM – PROCESS MANAGEMENT
PARAMENTER PREEMPTIVE SCHEDULING NON-PREEMPTIVE SCHEDULING
and Shortest Remaining Time
First.
Scheduling Criteria
• CPU utilization – keep the CPU as busy as possible
• Throughput – # of processes that complete their execution per time unit
• Turnaround time – amount of time to execute a particular process
• Waiting time – amount of time a process has been waiting in the ready
queue
• Response time – amount of time it takes from when a request was
submitted until the first response is produced, not output (for time-sharing
environment)
First Come First Serve (FCFS)
• Jobs are executed on first come, first serve basis.
• It is a non-preemptive, pre-emptive scheduling algorithm.
• Easy to understand and implement.
• Its implementation is based on FIFO queue.
• Poor in performance as average wait time is high.
MANJULA PRASAD 12
OPERATING SYSTEM – PROCESS MANAGEMENT
Wait time of each process is as follows −
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
Shortest Job Next (SJN)
• This is also known as shortest job first, or SJF
• This is a non-preemptive, pre-emptive scheduling algorithm.
• Best approach to minimize waiting time.
• Easy to implement in Batch systems where required CPU time is known in
advance.
• Impossible to implement in interactive systems where required CPU time is not
known.
• The processer should know in advance how much time process will take.
Given: Table of processes, and their Arrival time, Execution time
MANJULA PRASAD 13
OPERATING SYSTEM – PROCESS MANAGEMENT
Process Arrival Time Execution Time Service Time
P0 0 5 0
P1 1 3 5
P2 2 8 14
P3 3 6 8
Waiting time of each process is as follows −
Process Waiting Time
P0 0-0=0
P1 5-1=4
P2 14 - 2 = 12
P3 8-3=5
Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25
Priority Based Scheduling
• Priority scheduling is a non-preemptive algorithm and one of the most common
scheduling algorithms in batch systems.
• Each process is assigned a priority. Process with highest priority is to be
executed first and so on.
• Processes with same priority are executed on first come first served basis.
• Priority can be decided based on memory requirements, time requirements or
any other resource requirement.
Given: Table of processes, and their Arrival time, Execution time, and priority. Here
we are considering 1 is the lowest priority.
MANJULA PRASAD 14
OPERATING SYSTEM – PROCESS MANAGEMENT
Process Arrival Time Execution Time Priority Service Time
P0 0 5 1 0
P1 1 3 2 11
P2 2 8 1 14
P3 3 6 3 5
Waiting time of each process is as follows −
Process Waiting Time
P0 0-0=0
P1 11 - 1 = 10
P2 14 - 2 = 12
P3 5-3=2
Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6
Shortest Remaining Time
• Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.
• 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.
• Impossible to implement in interactive systems where required CPU time is not
known.
• It is often used in batch environments where short jobs need to give preference.
Round Robin Scheduling
• Round Robin is the preemptive process scheduling algorithm.
MANJULA PRASAD 15
OPERATING SYSTEM – PROCESS MANAGEMENT
• Each process is provided a fix time to execute, it is called a quantum.
• Once a process is executed for a given time period, it is preempted and other
process executes for a given time period.
• Context switching is used to save states of preempted processes.
Wait time of each process is as follows −
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
Multiple-Level Queues Scheduling
Multiple-level queues are not an independent scheduling algorithm.
They make use of other existing algorithms to group and schedule jobs
with common characteristics.
• Multiple queues are maintained for processes with common
characteristics.
• Each queue can have its own scheduling algorithms.
• Priorities are assigned to each queue.
MANJULA PRASAD 16
OPERATING SYSTEM – PROCESS MANAGEMENT
For example, CPU-bound jobs can be scheduled in one queue and all
I/O-bound jobs in another queue. The Process Scheduler then
alternately selects jobs from each queue and assigns them to the CPU
based on the algorithm assigned to the queue.
Algorithm Evaluation
1. Defining Criteria: The first thing we need to decide is how we will evaluate
the algorithms. To do this we need to decide on the relative importance of
the factors we listed above (Fairness, Efficiency, Response Times,
Turnaround and Throughput). Only once we have decided on our evaluation
method can we carry out the evaluation.
2. Evaluation of Algorithms
• Deterministic Modeling: This evaluation method takes a predetermined
workload and evaluates each algorithm using that workload.
• Queuing Models: Another method of evaluating scheduling algorithms is
to use queuing theory. Using data from real processes we can arrive at a
probability distribution for the length of a burst time and the I/O times for
a process. We can now generate these times with a certain distribution.
• Simulations: Rather than using queuing models we simulate a computer.
A Variable, representing a clock is incremented. At each increment the
state of the simulation is updated. Statistics are gathered at each clock
tick so that the system performance can be analysed.
• Implementation:
The best way to compare algorithms is to implement them on real machines.
This will give the best results but does have a number of disadvantages.
· It is expensive as the algorithm has to be written and then implemented on
real hardware.
· If typical workloads are to be monitored, the scheduling algorithm must be
used in a live situation. Users may not be happy with an environment that is
constantly changing.
· If we find a scheduling algorithm that performs well there is no guarantee
that this state will continue if the workload or environment changes.
MANJULA PRASAD 17
OPERATING SYSTEM – PROCESS MANAGEMENT
MANJULA PRASAD 18