OPERATING SYSTEMS

MODULE II: PROCESS MANAGEMENT

Process

➢ Process can be thought of as a program in execution.

Program vs Process

➢ A program is a passive entity, such as a file containing a list of instructions stored on disk
(often called an executable file).

➢ A process is an active entity, with a program counter specifying the next instruction to
execute and a set of associated resources.

➢ A program becomes a process when an executable file is loaded into memory.

Process State

New: The process is being created.

Running: Instructions are being executed.

Waiting: The process is waiting for some event to occur (such as an I/0 completion or
reception of a signal).

Ready: The process is waiting to be assigned to a processor.

Terminated: The process has finished execution.

Diagram of a process state

Process Control Block(PCB)

• Each process is represented in the operating system by a process control block(PCB) also
called a task control block.

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: They include accumulators, index registers, stack pointers, and general-purpose
registers, plus any condition-code information

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.

I/O status information: This information includes the list of I/O devices allocated to the process, a
list of open files, and so on.

Non-Preemptive vs. Preemptive Processes„

A process can give up CPU in two ways „

Non-preemptive: once a process has been given the CPU, the CPU cannot be taken away
from that process. Process can not be interrupted till it terminates or switches to
waiting state. „

Preemptive: A scheduling discipline is preemptive if, once a process has been given the
CPU can taken away. Process can be interrupted in between.

Thread

→ A thread is a basic unit of CPU utilization;

Process Scheduling Queues

• Job queue – set of all processes in the system.

• Ready queue – set of all processes residing in main memory,

ready and waiting to execute.

• Device queues – set of processes waiting for an I/O device.

• Process migration between the various queues.

Schedulers
→ Long-term scheduler (or job scheduler)
• selects which processes should be brought into the ready queue.
• Long-term scheduler is invoked very infrequently (seconds, minutes) Þ (may be slow).
• The long-term scheduler controls the degree of multiprogramming.
→ Short-term scheduler (or CPU scheduler)
• Selects which process should be executed next and allocates CPU.
• Short-term scheduler is invoked very frequently (milliseconds)
Þ (must be fast).
→ medium-term scheduler
• remove a process from memory (and from active contention for the CPU) and thus
reduce the degree of multiprogramming.
• Later, the process can be reintroduced into memory, and its execution can be
continued where it left off. This scheme is called swapping .
• The process is swapped out, and is later swapped in, by the medium-term scheduler.
I/O-bound process and CPU-bound process

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

Scheduling Criteria

CPU utilization.

• We want to keep the CPU as busy as possible.

• Conceptually, CPU utilization can range from 0 to 100 percent.

• In a real system, it should range from 40 percent to 90 percent

Throughput

• is the number of processes that are completed per time unit, called throughput.

Turnaround Time

• The interval from the time of submission of a process to the time of completion is the
turnaround time.

Waiting Time

• Waiting time is the sum of the periods spent waiting in the ready queue.

Response Time

• It is the time from the submission of a request until the first response is produced.
Scheduling Algorithms

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.

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

• If the processes arrive in the order P1 , P2 , P3 , and are served in FCFS order, the Gantt
chart, which is a bar chart that illustrates a particular schedule, including the start and finish
times of each of the participating processes as follows.

• 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.
• The disadvantage of FCFS algorithm 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.

Shortest-Job-First Scheduling

• the process that shortest burst time is allocated the CPU first.
As an example of SJF scheduling, consider the following set of processes, with the length of the CPU
burst given in milliseconds:
the average waiting time is (3 + 16 + 9 + 0)/4 = 7 milliseconds.

Priority Scheduling

• A priority number (integer) is associated with each process

• SJF is a priority scheduling where priority is the predicted next CPU burst time.

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 average waiting time is 8.2 milliseconds.

Round-Robin Scheduling
→ The round-robin (RR) scheduling algorithm is designed especially for timesharing systems.
→ A small unit of time, called a time quantum or time slice, is defined.
→ The ready queue is treated as a circular queue.
→ To implement RR scheduling, we again treat the ready queue as a FIFO queue of processes.
→ New processes are added to the tail of the ready queue.

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

P1 waits for 6 milliseconds (10 - 4), P2 waits for 4 milliseconds, and P3 waits for 7 milliseconds. Thus, the
average waiting time is 17/3 = 5.66 milliseconds.

Multilevel Queue Scheduling

→ 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.
→ An example of a multilevel queue scheduling algorithm with five queues, listed below in order of
priority:
o System processes
o Interactive processes
o Interactive editing processes
o Batch processes
o Student processes

Multilevel Feedback Queue Scheduling

→ The multilevel feedback queue scheduling algorithm, in contrast, allows a process to move between
queues.
→ If a process uses too much CPU time, it will be moved to a lower-priority queue.
→ 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.
 Co-operating Process • A cooperating process is one that can affect or be affected by other
processesexecuting in the system.
Race Condition • Several processes access and manipulate the same data concurrently and the
outcome of the execution depends on the particular order in which the access takes place, is called
a race condition
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
• When one process is executing in its critical section, no other process is to be allowed to
execute in its critical section
• 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 theremainder section

Deadlock.
A process requests resources; if the resources arenot available at that time, the process
enters a waiting state. Sometimes, awaiting process is never again able to change state,
because the resources ithas requested are held by other waiting processes. This situation is
calleda deadlock.

Necessary Conditions for a deadlock

• Mutual exclusion. At least one resource must be held in a non sharable mode;
• 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.
• No preemption a resource can be released only, after that process has completed its
task.
• Circular wait. A set {P0, P1, ..., Pn} of waiting processes must exist suchthat P0 is
waiting for a resource held by P1, P1 is waiting for a resourceheld by P2, ..., Pn−1 is
waiting for a resource held by Pn, and Pn is waitingfor a resource held by P0.
Resource-Allocation Graph
• Deadlocks can be described in terms of a directed graph called a system resource-
allocation graph.
• This graph consists of a set of vertices V and a set of edges E.
• A directed edge from process Pi to resource type Rj is denoted by Pi → Rj ;it signifies
that process Pi has requested an instance of resource type Rj and is currently waiting
for that resource.
• A directed edge from resource type Rj to process Pi is denoted by Rj → Pi ; it signifies
that an instance of resource type Rj has been allocated to process Pi .
• A directed edge Pi → Rj is called a request edge; a directed edge Rj → Pi is called an
assignment edge.
• In Graph, each process Pi is represented as a circle and each resource type Rj as a
rectangle.
• Since resource type Rj may have more than one instance, werepresent each such
instance as a dot within the rectangle