Operating System Concepts BCS303

Module 2
PROCESS
MANAGEMENT

1. Process concept:
A process can be thought of as a program in execution. A process will
need certain resources-such as CPU time, memory, files, and I/O devices to
accomplish its task. These resources are allocated to the process either when it
is created or while it is executing.
The operating system is responsible for the following activities in
connection with process and thread management: the creation and deletion of
both user and system processes; the scheduling of processes; and the provision
of mechanisms for synchronization, communication, and deadlock handling for
processes. The terms job and process are used almost interchangeably.

1.1 Process:
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. A
process generally also includes the process stack, which contains temporary
data (such as function parameters, return addresses, and local variables), and

CIT,MANDYA Page 1
 Operating System Concepts BCS303

a data section, which contains global variables. A process may also include a
heap, which is memory that is dynamically allocated during process run
time.

Process memory is divided into four sections as shown in the figure

below:
 The stack is used to store local variables, function parameters,
function return values, return address etc.
 The heap is used for dynamic memory allocation.
 The data section stores global and static variables.
 The text section comprises the compiled program code.
 Note that, there is a free space between the stack and the heap. When
the stack is full, it grows downwards and when the heap is full, it
grows upwards.

Process in memory

CIT,MANDYA Page 2
 Operating System Concepts BCS303

1.2 Process State:

As a process executes, it changes state. The state of a process is defined in
part by the current activity of that process. Each process may be in one of the
following states:
• 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/O
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 Process State

1.3 Process Control Block:

Each process is represented in the operating system by a process control
block (PCB)-also called a task control block. A PCB is shown in figure. It
contains many pieces of information associated with a specific process,
including these:

CIT,MANDYA Page 3
 Operating System Concepts BCS303

Process control block (PCB)

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

CIT,MANDYA Page 4
 Operating System Concepts BCS303

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

The PCB simply serves as the repository for any information that may
vary from process to process.

Diagram showing CPU switch from process to process

1.4 Threads:

The process model discussed so far has implied that a process is a program
that performs a single thread of execution. For example, when a process is
running a word-processor program, a single thread of instructions is being executed.
This single thread of control allows the process to perform only one
task at one time.

CIT,MANDYA Page 5
 Operating System Concepts BCS303

2. Process scheduling :
Process Scheduler selects an available process for program execution on
the CPU. In a multiprocessor system - one process will be under execution and
the rest of the processes have to wait until the CPU is free and can be
rescheduled. The main objective of process scheduling is to keep the CPU busy at
all times.

2.1 Scheduling Queues:

As processes enter the system, they are put into a job queue, which
consists of all processes in the system. The processes that are residing in main
memory and are ready and waiting to execute are kept on a list called the
ready queue.

• All processes admitted to the system are stored in the job queue.
• Processes in main memory and ready to execute are placed in the ready
queue.
• Processes waiting for a device to become available are placed in device
queues. There is generally a separate device queue for each device.

These queues are generally stored as a linked list of PCBs. A queue

header will contain two pointers - the head pointer pointing to the first
PCB and the tail pointer pointing to the last PCB in the list. Each PCB has
a pointer field that points to the next process in the queue.

When a process is allocated to the CPU, it executes for a while and

eventually quits, interrupted, or waits for the completion of an I/O request.
Since there are many processes in the system, the disk may be busy with the
I/O request of some other process. The process therefore may have to wait
for the disk in the device queue.

CIT,MANDYA Page 6
 Operating System Concepts BCS303

The ready queue and various 1/0 device queues

A common representation of process scheduling is a queuing diagram.

Each rectangular box in the diagram represents a queue. Two types of queues
are present: the ready queue and a set of device queues. The circles represent
the resources that serve the queues, and the arrows indicate the flow of
processes in the system.

A new process is initially put in the ready queue. It waits in the ready
queue until it is selected for execution and is given the CPU. Once the process
is allocated the CPU and is executing, one of several events could occur:

• The process could issue an I/O request, and then be placed in an I/O
queue.
• The process could create a new subprocess and wait for its termination.

CIT,MANDYA Page 7
 Operating System Concepts BCS303

• The process could be removed forcibly from the CPU, as a result of

an interrupt, and be put back in the ready queue.

In the first two cases, the process eventually switches from the waiting
state to the ready state, and is then put back in the ready queue. A process
continues this cycle until it terminates, at which time it is removed from all
queues.

Queuing-diagram representation of process scheduling

2.2 Schedulers:
A process migrates among the various scheduling queues throughout its
lifetime. The operating system must select, for scheduling purposes,
processes from these queues in some fashion. The selection process is carried
out by the appropriate scheduler.
Schedulers are software which selects an available program to be assigned
to CPU.
 A long-term scheduler or Job scheduler – selects jobs from the
job pool (of secondary memory, disk) and loads them into the memory.
If more processes are submitted, than that can be executed
immediately, such
processes will be in secondary memory. It runs infrequently, and can take time
to select the next process.

CIT,MANDYA Page 8
 Operating System Concepts BCS303

 The short-term scheduler, or CPU Scheduler – selects job

from memory and assigns the CPU to it. It must select the new process for
CPU frequently.
 The medium-term scheduler - selects the process in ready queue
and reintroduced into the memory.

Processes can be described as either:

 I/O-bound process – spends more time doing I/O than computations,
 CPU-bound process – spends more time doing computations and few
I/O operations.

An efficient scheduling system will select a good mix of CPU-bound

processes and I/O bound processes.
 If the scheduler selects more I/O bound process, then I/O queue will be
full and ready queue will be empty.
 If the scheduler selects more CPU bound process, then ready queue will
be full and I/O queue will be empty.

Time sharing systems employ a medium-term scheduler. It swaps out the

process from ready queue and swap in the process to ready queue. When system
loads get high, this scheduler will swap one or more processes out of the ready
queue for a few seconds, in order to allow smaller faster jobs to finish up quickly
and clear the system.

Advantages of medium-term scheduler –

 To remove process from memory and thus reduce the degree of
multiprogramming (number of processes in memory).
 To make a proper mix of processes(CPU bound and I/O bound )

CIT,MANDYA Page 9
 Operating System Concepts BCS303

Addition of medium-term scheduling to the queuing diagram

2.3 Context Switch:

Interrupts cause the operating system to change a CPU from its current task
and to run a kernel routine. Such operations happen frequently on general-
purpose systems. When an interrupt occurs, the system needs to save the current
of the process running on the CPU so that it can restore that context when its
processing is done, essentially suspending the process and then resuming it. The
context is represented in the PCB of the process; it includes the value of the CPU
registers, the process state.

Diagram of Process State

Context-switch times are highly dependent on hardware support

(Number of CPU registers). Whenever an interrupt occurs (hardware or
software interrupt), the state of the currently running process is saved into the
PCB and the state of another process is restored from the PCB to the CPU.

CIT,MANDYA Page 10
 Operating System Concepts BCS303

Context switch time is an overhead, as the system does not do useful work while
switching.

3. Operations on processing:
The processes in most systems can execute concurrently, and they may be
created and deleted dynamically. Thus, these systems must provide a mechanism
for process creation and termination.

3.1 Process Creations:

A process may create several new processes, via a create-process system call
during the course of execution. The creating process is called a parent
process, and the new processes are called the children of that process. Each of
these new processes may in turn create other processes, forming a tree of
processes. Every process has a unique process ID.

A tree of processes on a typical Solaris system

CIT,MANDYA Page 11
 Operating System Concepts BCS303

On typical Solaris systems, the process at the top of the tree is the ‘sched’
process with PID of 0. The ‘sched’ process creates several children processes –
init, pageout and fsflush. Pageout and fsflush are responsible for managing
memory and file systems. The init process with a PID of 1, serves as a parent
process for all user processes.
A process will need certain resources (CPU time, memory, files, I/O
devices) to accomplish its task.
When a process creates a new process, two possibilities exist in terms of
execution:
 The parent continues to execute concurrently with its children.
 The parent waits until some or all of its children have terminated.

There are also two possibilities in terms of the address space of the new
process:
 The child process is a duplicate of the parent process (it has the
same program and data as the parent).
 The child process has a new program loaded into it.

To illustrate these differences, let's first consider the UNIX operating system.
In UNIX, as we've seen, each process is identified by its process identifier,
#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>

int main ()
{
pid_t pid;

CIT,MANDYA Page 12
 Operating System Concepts BCS303

/* fork a child process */

pid = fork();

if (pid < 0) {/* error occurred

*/ fprintf (stderr I "Fork
Failed"); exit(-l) ;
}
else if (pid == 0) {/* child process * /
execlp (" /bin/ Is" I "ls" , NULL) ;
}
else {/* parent process */
/* parent will wait for the child to complete */
wait (NULL) ;
printf ("Child Complete") ;
exit(O) ;

C program forking a separate process

In UNIX OS, a child process can be created by fork() system call. The fork
system call, if successful, returns the PID of the child process to its parents
and returns a zero to the child process. If failure, it returns -1 to the parent.
Process IDs of current process or its direct parent can be accessed using the
getpid( ) and getppid( ) system calls respectively.

The parent waits for the child process to complete with the wait() system
call. When the child process completes, the parent process resumes and
completes its execution.

CIT,MANDYA Page 13
 Operating System Concepts BCS303

Process Creation
In windows the child process is created using the function createprocess( ).
The createprocess( ) returns 1, if the child is created and returns 0, if the child
is not created.

3.2 Process Termination:

A process terminates when it finishes executing its last statement and
asks the operating system to delete it, by using the exit( ) system call. All of
the resources assigned to the process like memory, open files, and I/O
buffers, are deallocated by the operating system.
A process can cause the termination of another process by using
appropriate system call. The parent process can terminate its child processes
by knowing of the PID of the child.
A parent may terminate the execution of children for a variety of reasons,
such as:
• The child has exceeded its usage of the resources, it has been allocated.
• The task assigned to the child is no longer required.
• The parent is exiting, and the operating system terminates all the
children. This is called cascading termination.

CIT,MANDYA Page 14
 Operating System Concepts BCS303

4. Interprocess communication:
Processes executing may be either co-operative or independent processes.
 Independent Processes – processes that cannot affect other processes
or be affected by other processes executing in the system.
 Cooperating Processes – processes that can affect other processes
or be affected by other processes executing in the system.

Co-operation among processes are allowed for following reasons –

 Information Sharing - There may be several processes which need to
access the same file. So the information must be accessible at the same time
to all users.
 Computation speedup - Often a solution to a problem can be solved
faster if the problem can be broken down into sub-tasks, which are solved
simultaneously (particularly when multiple processors are involved )
 Modularity - A system can be divided into cooperating modules and
executed by sending information among one another.
 Convenience - Even a single user can work on multiple tasks by information
sharing.
Cooperating processes require some type of inter-process communication. This is
allowed by two models: Shared Memory systems and Message Passing systems.

Communications models (a) Message passing. (b) Shared

memory

CIT,MANDYA Page 15
 Operating System Concepts BCS303

4.1 Shared-memory Systems:

Interprocess communication using shared memory requires
communicating processes to establish a region of shared memory. Typically,
a shared-memory region resides in the address space of the process creating
the shared-memory segment. Other processes that wish to communicate
using this shared-memory segment must attach it to their address space.
Recall that, normally, the operating system tries to prevent one process from
accessing another process's memory. Shared memory requires that two or
more processes agree to remove this restriction. They can then exchange
information by reading and writing data in the shared areas. The form of the
data and the location are determined by these processes and are not under
the operating system's control. The processes are also responsible for
ensuring that they are not writing to the same location simultaneously.

Example: To illustrate the concept of cooperating processes, let's consider the

producer-consumer problem, which is a common paradigm for cooperating
processes. A producer process produces information that is consumed by a
consumer process.
The data is passed via an intermediary buffer (shared memory). The
producer puts the data to the buffer and the consumer takes out the data
from the buffer. A producer can produce one item while the consumer is
consuming another item. The producer and consumer must be synchronized,
so that the consumer does not try to consume an item that has not yet been
produced. In this situation, the consumer must wait until an item is
produced.

CIT,MANDYA Page 16
 Operating System Concepts BCS303

There are two types of buffers into which information can be put –

• Unbounded buffer
• Bounded buffer

With Unbounded buffer, there is no limit on the size of the buffer, and so
on the data produced by producer. But the consumer may have to wait for new
items.

With bounded-buffer – As the buffer size is fixed. The producer has to

wait if the buffer is full and the consumer has to wait if the buffer is empty.

4.2 Message-passing Systems:

 A mechanism to allow process communication without sharing
address space. It is used in distributed systems.
 Message passing systems uses system calls for "send message" and
"receive message".
 A communication link must be established between the cooperating
processes before messages can be sent.
There are three methods of creating the link between the sender and the
receiver-
1. Direct or indirect communication (naming)
2. Synchronous or asynchronous communication (Synchronization)
3. Automatic or explicit buffering

CIT,MANDYA Page 17
 Operating System Concepts BCS303

4.2.1 Naming:
The processes that want to communicate should have a way to refer each
other. (Using some identity).
 Direct Communication – Direct communication the
sender and receiver must explicitly know each other’s name. The
syntax for send() and receive() functions are as follows-
send (P, message) – send a message to process P
receive(Q, message) – receive a message from process
Q

Properties of communication link:

 A link is established automatically between every pair of
processes that wants to communicate. The processes
need to know only each other's identity to communicate.
 A link is associated with exactly one pair of
communicating processes
 Between each pair, there exists exactly one link.

Types of addressing in direct communication –

 Symmetric addressing – the above described

communication is symmetric communication. Here both the
sender and the receiver processes have to name each other to
communicate.
 Asymmetric addressing – Here only the sender name is
mentioned, but the receiving data can be from any system.

Send (P, message) --- Send a message to

process P Receive (id, message)-Receive a
message from any process

Disadvantages of direct communication – any

changes in the identifier of a process, may have to change
the identifier in the whole system (sender and receiver),
where the messages are sent and received.

CIT,MANDYA Page 18
 Operating System Concepts BCS303

 Indirect Communication - Indirect communication uses shared

mailboxes, or ports.
A mailbox or port is used to send and receive messages. Mailbox is an
object into which messages can be sent and received. It has a unique
ID. Using this identifier messages are sent and received.

Two processes can communicate only if they have a shared mailbox.

The send and receive functions are –
send(A, message) – send a message to mailbox A
receive(A, message) – receive a message from mailbox A

Properties of communication link:

 A link is established between a pair of processes only if they
have a shared mailbox
 A link may be associated with more than two processes
 Between each pair of communicating processes, there may
be any number of links; each link is associated with one
mailbox.
A mail box can be owned by the operating system. It must take
steps to –
 Create a new mailbox
 Send and receive messages from mailbox
 Delete mailboxes

CIT,MANDYA Page 19
 Operating System Concepts BCS303

4.2.2 Synchronization:
The send and receive messages can be implemented as either
blocking or non-blocking.
• Blocking (synchronous) send - sending process is blocked
(waits) until the message is received by receiving process or the mailbox.
• Non-blocking (asynchronous) send - sends the
message and continues (does not wait)
• Blocking (synchronous) receive - The receiving process is
blocked until a message is available
• Non-blocking (asynchronous) receive - receives the
message without block. The received message may be a valid
message or null.

4.2.3 Buffering:
When messages are passed, a temporary queue is created. Such
queue can be of three capacities:
• Zero capacity – The buffer size is zero (buffer does not exist).
Messages are not stored in the queue. The senders must block until receivers
accept the messages.
• Bounded capacity- The queue is of fixed size(n). Senders must
block
if the queue is full. After sending ‘n’ bytes the sender is blocked.
• Unbounded capacity - The queue is of infinite capacity. The
sender never blocks.

CIT,MANDYA Page 20
 Operating System Concepts BCS303

5. Multithreading
models:
Introduction:
A thread 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 a process has multiple
threads of control, it can perform more than one task at a time.

Single-threaded and multithreaded processes

CIT,MANDYA Page 21
 Operating System Concepts BCS303

Benefits:
The benefits of multithreaded programming can be broken down into four
major categories:
1. Responsiveness: Multithreading an interactive application may allow a
program to continue rU1U1ing even if part of it is blocked or is performing a
lengthy operation, thereby increasing responsiveness to the user. For instance, a
multithreaded web browser could still allow user interaction in one thread while
an image was being loaded in another thread.
2. Resource sharing: By default, threads share the memory and the
resources of the process to which they belong. The benefit of sharing code and
data is that it allows an application to have several different threads of activity
within the same
address space.
3. Economy: Allocating memory and resources for process creation is
costly. Because threads share resources of the process to which they belong, it is
more economical to create and context-switch threads. Empirically
gauging the
difference in overhead can be difficult, but in general it is much more time
consuming to create and manage processes than threads. In Solaris, for example,
creating a process is about thirty 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 threads may be
running in parallel on different processors. A single-threaded process can only
run on one CPU, no matter how many are available. Multithreading on a multi-
CPU machine increases concurrency.

CIT,MANDYA Page 22
 Operating System Concepts BCS303

Multithreading Models:
1. Many-to-One Model – The many-to-one model maps many user-level
threads to one kernel thread. Thread management is done by the thread
library in user space, so it is efficient; but the entire process will block if a
thread makes a blocking system call. Also, because only one thread can
access the kernel at a time, multiple threads are unable to run in parallel
on multiprocessors. Green threads-a thread library available for Solaris-
uses this model, as does GNU Portable Threads.

Many-to-one model

2. One-to-One Model – The one-to-one model maps each user thread

to a kernel thread. It provides more concurrency than the many-to-one
model by allowing another thread to run when a thread makes a blocking
system call; it also allows multiple threads to run in parallel on
multiprocessors. The only drawback to this model is that creating a user
thread requires creating the corresponding kernel thread.
Because the overhead of creating kernel threads can burden the
performance of an application, most implementations of this model
restrict the number of threads supported by the system. Linux, along with
the family of Windows operating systems-including Windows 95, 98, NT,
2000, and xp implement the one-to-one model.

CIT,MANDYA Page 23
 Operating System Concepts BCS303

One-to-one model

3. Many-to-Many Model – The many-to-many model multiplexes

many user-level threads to a smaller or equal number of kernel threads. The
number of kernel threads may be specific to either a particular application
or a particular machine (an application may be allocated more kernel
threads on a multiprocessor than on a uniprocessor). Whereas the many-
to-one model allows the developer to create as many user threads as she
wishes, true concurrency is not gained because the kernel can schedule
only one thread at a time.
One popular variation on the many-to-many model still
multiplexes many user-level threads to a smaller or equal number of
kernel threads but also allows a user-level thread to be bound to a kernel
thread.

Many-to-many model

CIT,MANDYA Page 24
 Operating System Concepts BCS303
THREAD LIBRARIES
It provides the programmer with an API for the creation and management of threads. Two
ways of implementation:
1) First Approach  Provides a library entirely in user space with no kernel support.  All
code and data structures for the library exist in the user space.
2) Second Approach  Implements a kernel-level library supported directly by the OS.  Code
and data structures for the library exist in kernel space.

Three main thread libraries:

1) POSIX Pthreads
2) Win32
and 3) Java.

Pthreads:
• This is a POSIX standard API for thread creation and synchronization.
• This is a specification for thread-behavior, not an implementation.
• OS designers may implement the specification in any way they wish.
• Commonly used in: UNIX and Solaris.

Java Threads
• Threads are the basic model of program-execution in Java program and Java language.
• The API provides a rich set of features for the creation and management of threads.
• All Java programs comprise at least a single thread of control.

Two techniques for creating threads:

1) Create a new class that is derived from the Thread class and override its run() method.
2) Define a class that implements the Runnable interface. The Runnable interface is defined as follows:
Public interface runnable
{

Public abort void run()

CIT,MANDYA Page 25
 Operating System Concepts BCS303
}

THREADING ISSUES
***Discuss any 3 threading issues that come with multi-threaded programs
1. System call fork() and exec() in multi-thread programming
2. Thread cancellation
3. Signal handling
4. Thread pools

[Link] call fork() is used to create a separate, duplicate process. If one thread in a program
calls fork(), then some systems duplicates all threads and other systems duplicate only the
thread that invoked the fork(). If a thread invokes the exec(), the program specified in the
parameter to exec() will replace the entire process including all threads.
[Link] Cancellation: This is the task of terminating a thread before it has completed.
Target thread is the thread that is to be canceled. Thread cancellation occurs in two different
cases: 3) Asynchronous cancellation: One thread immediately terminates the target thread. 4)
Deferred cancellation: The target thread periodically checks whether it should be terminated.
3)Signal Handling: In UNIX, a signal is used to notify a process that a particular event has
occurred.
All signals follow this pattern:

1. A signal is generated by the occurrence of a certain event.

2. A generated signal is delivered to a process.
3. Once delivered, the signal must be handled.
A signal handler is used to process signals. A signal may be received either synchronously or
asynchronously, depending on the source.

1) Synchronous signals  Delivered to the same process that performed the operation
causing the signal.  E.g. illegal memory access and division by 0.

CIT,MANDYA Page 26
 Operating System Concepts BCS303

2) Asynchronous signals  Generated by an event external to a running process.  E.g. user

terminating a process with specific keystrokes .
Every signal can be handled by one of two possible handlers:

1) A Default Signal Handler  Run by the kernel when handling the signal.
2) A User-defined Signal Handler  Overrides the default signal handler.

In single-threaded programs, delivering signals is simple. In multithreaded programs,

delivering signals is more complex. Then, the following options exist:
1) Deliver the signal to the thread to which the signal applies.
2) Deliver the signal to every thread in the process.
3) Deliver the signal to certain threads in the process.
4) Assign a specific thread to receive all signals for the process.

4)Thread Pools: The basic idea is to create a no. of threads at process-startup and place the
threads into a pool (where they sit and wait for work). Procedure:
1. When a server receives a request, it awakens a thread from the pool.
2. If any thread is available, the request is passed to it for service. Once the service is
completed, the thread returns to the pool.

Advantages:
1) Servicing a request with an existing thread is usually faster than waiting to create a thread.
2) The pool limits the no. of threads that exist at any one point. No. of threads in the pool can
be based on factors such as: no. of CPUs, amount of memory and expected no. of concurrent
client-requests.

CIT,MANDYA Page 27
 Operating System Concepts BCS303

PROCESS SCHEDULING

Basic Concepts: In a single-processor system, only one process may run at a time and other
processes must wait until the CPU is rescheduled. The main objective of multiprogramming is
to have some process running at all times, in order to maximize CPU utilization.
CPU-I/O Burst Cycle: Process execution consists of a cycle of CPU execution and an I/O wait
as shown in below figure. Process execution begins with a CPU burst, followed by an I/O burst,
then another CPU burst, etc… Finally, a CPU burst ends with a request to terminate execution.
An I/O- bound program typically has many short CPU bursts. A CPU-bound program might
have a few long CPU bursts.
CPU SCHEDULER:
CPU scheduler selects a waiting-process from the ready-queue and allocates CPU to the
waiting- process. The ready-queue could be a FIFO, priority queue, tree and list. The records in
the queues are generally process control blocks (PCBs) of the processes.
CPU SCHEDULING Four situations under which CPU scheduling decisions take place:
1. When a process switches from the running state to the waiting state. For ex; I/O request.
2. When a process switches from the running state to the ready state. For ex: when an
interrupt occurs.
3. When a process switches from the waiting state to the ready state. For ex: completion of I/O.
4. When a process terminates.

Scheduling under 1 and 4 is on-preemptive. Scheduling under 2 and 3 is preemptive.

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.
Preemptive Scheduling This is driven by the idea of prioritized computation. Processes that
are runnable may be temporarily suspended.
Disadvantages:
1) Incurs a cost associated with access to shared-data.
2) Affects the design of the OS kernel.
CIT,MANDYA Page 28
 Operating System Concepts BCS303

Dispatcher :
It gives control of the CPU to the process selected by the short-term scheduler. The function
involves:
1) Switching context
2) Switching to user mode &
3) Jumping to the proper location in the user program to restart that program.
It should be as fast as possible, since it is invoked during every process switch.
Dispatch latency :means the time taken by the dispatcher to stop one process and to start
another process to run.

SCHEDULING CRITERIA USED IN OS

******Discuss the scheduling criteria used in operating system.
The various scheduling criteria used in OS are:
1. CPU Utilization
2. Throughput
3. Turnaround time
4. Waiting time
5. Response time

[Link] Utilization: We must keep the CPU as busy as possible. In a real system, it ranges from
40% to 90%.

2. Throughput: The number of processes completed per time unit. For long processes, throughput may
be 1 process per hour; For short transactions, throughput might be 10 processes per second.

3. Turnaround Time: The interval from the time of submission of a process to the time of
completion. Turnaround time is the sum of the periods spent in waiting to get into memory,

CIT,MANDYA Page 29
 Operating System Concepts BCS303
waiting in the ready-queue, executing on the CPU and doing I/O.

4. Waiting Time: The amount of time that a process spends waiting in the ready-queue.

5. Response Time: The time from the submission of a request until the first response is
produced.

SCHEDULING ALGORITHMS :CPU scheduling deals with the problem of deciding which
of the processes in the ready queue is to be allocated the CPU.
Following are some scheduling algorithms:
1) FCFS scheduling (First Come First Served)
2) Round Robin scheduling
3) SJF scheduling (Shortest Job First)
4)Priority scheduling

FCFS SCHEDULING The process that requests the CPU first is allocated the CPU first. That
means process which arrives the ready-queue first, get scheduled first if the CPU is free. This is
a non-preemptive scheduling concept. The implementation is easily done using a FIFO queue.
Procedure:
1) When a process enters the ready-queue, its PCB is linked onto the tail of the queue.
2) When the CPU is free, the CPU is allocated to the process at the queue‘s head.
3) The running process is then removed from the queue.
Advantage: Code is simple to write & understand.
Disadvantages:
1) Convoy effect: All other processes wait for one big process to get off the CPU.
2) Non-preemptive (a process keeps the CPU until it releases it).
3) Not good for time-sharing systems.
4) The average waiting time is generally not minimal.

CIT,MANDYA Page 30
 Operating System Concepts BCS303

SJF SCHEDULING:

SJF is a CPU scheduling algorithm that selects the process with the shortest CPU burst time next.

 Can be preemptive (Shortest Remaining Time First – SRTF)

 Or non-preemptive

ADVANTAGE:

1. Minimum average waiting time

SJF gives the best possible average waiting time among all scheduling algorithms.

2. High throughput

More processes are completed in less time because short jobs are executed first.

DISADVANTAGE:

1. Requires knowing CPU burst time

The exact length of each job must be known in advance, which is usually not possible.

2. Starvation of long processes

Longer processes may wait indefinitely if short processes keep arriving.

PRIORITY: Priority Scheduling is a CPU scheduling algorithm in which each process is assigned
a priority value, and the CPU is allocated to the process with the highest priority (or lowest
numerical value, depending on the system).
If two processes have the same priority, another scheduling method like FCFS is used to break the
tie.

Priority scheduling can be:

CIT,MANDYA Page 31
 Operating System Concepts BCS303
 Preemptive: A newly arrived process with higher priority immediately preempts the current
process.
 Non-preemptive: The CPU finishes the current process before switching to a higher-priority
one.

ADVANTAGES:

1. Useful for processes with different importance

Important or time-critical tasks can be given higher priority.

2. Efficient for real-time systems

High-priority jobs get CPU quickly, making the system responsive.

DISADVANTAGE:

1. Starvation of low-priority processes

Low-priority jobs may never get CPU if high-priority jobs keep arriving.

2. Priority inversion

Lower-priority processes may block high-priority ones, causing delays.

ROUND ROBIN: Round Robin (RR) is a CPU scheduling algorithm in which each process is
assigned a fixed time quantum (time slice). The CPU executes each process for at most one time
quantum in a circular order.
If a process does not finish within its time quantum, it is preempted and placed at the end of the
ready queue, and the next process is scheduled.

This ensures fairness, as every process gets an equal share of CPU time.

ADVANTAGES:1. Fair to all processes

Every process gets an equal share of CPU time due to the fixed time quantum.

CIT,MANDYA Page 32
 Operating System Concepts BCS303
2. Good for time-sharing systems

Provides quick response time, making it suitable for interactive systems.

DISADVANTAGES:

1. High context-switch overhead

Frequent switching between processes can waste CPU time.

2. Performance depends on time quantum

 If the quantum is too small → too many context switches

 If too large → behaves like FCFS (loses fairness)

PROBLEMS: REFER MY CLASS WORK

THREAD SCHEDULING: Thread Scheduling is the process of deciding which thread in a
multithreaded process should run on the CPU next.
The scheduler assigns CPU time to threads based on a scheduling policy (such as priority, round
robin, or time slicing).
Since each thread represents a unit of execution, the system manages threads to ensure efficiency,
responsiveness, and fairness.
TYPES OF THREAD SCHEDULING:
1)PROCESS CENTRIC SCHEDULING(USER LEVEL THREAD SCHEDULING):

 Threads are managed in user space by the thread library, not by the OS.
 The kernel is unaware of these threads.
 Scheduling decisions are made by the user-level thread library (e.g., POSIX threads).

Key Points:

 Fast context switching

 But if one thread blocks, the entire process may block

2)THREAD CENTRIC SCHEDULING(KERNEL LEVEL THREAD SCHEDULING):

 Threads are managed directly by the operating system kernel.

CIT,MANDYA Page 33
 Operating System Concepts BCS303
 The kernel schedules each thread independently.

Key Points:

 True parallelism on multiprocessor systems

 Slower context switching compared to ULT due to kernel involvement

Additional Classification:

A. Preemptive Thread Scheduling

 The scheduler can interrupt a running thread and switch to another.

EG:I f thread T1 is running and T2 arrives with higher priority , os stops T1 and runs T2.

B. Non-Preemptive Thread Scheduling

 A thread continues to run until it voluntarily yields or finishes.

EG: IF thread T1 is running and T2 arrives with high priority, still T1 continue to execute.

MULTIPROCESSOR THREAD SCHEDULINGG:

Multiprocessor thread scheduling refers to how the operating system assigns threads to run on
multiple CPUs or processor cores.
It decides which thread runs on which processor and ensures load balancing, efficiency, and
minimal overhead.

TYPES:

1. Symmetric Multiprocessing (SMP)

 All processors are identical and share memory.

 Each processor can schedule any ready thread.
 Most modern OS (Windows, Linux) use this.

ADVANTAGES: Better performance and load balancing

DISADVANTAGES: Requires proper coordination to avoid conflicts.

2. Asymmetric Multiprocessing (AMP)

 Only one processor (master) does all scheduling and system tasks.

 Other processors run only user threads.

CIT,MANDYA Page 34
 Operating System Concepts BCS303
ADVANTAGES: Simple design

DISADVANTAGES: Master CPU becomes a bottleneck.

CIT,MANDYA Page 35
 Operating System Concepts BCS303

CIT,MANDYA Page 36
 Operating System Concepts BCS303

CIT,MANDYA Page 37
 Operating System Concepts BCS303

CIT,MANDYA Page 38