Subject Module 2 Prepared by: Dept.

of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

MODULE – II
Processes Concept
 A process is a program under execution.
 Its current activity is indicated by PC(Program Counter) and CPU registers.

2.1 The Process

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, returnaddress 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, itgrows downwards and when the heap is full, it grows upwards.

Process States
A Process has 5 states. Each process may be in one of the following states –

 New - The process is in the stage of being created.

 Ready - The process has all the resources it needs to run. It is waiting to be
assigned to theprocessor.
 Running – Instructions are being executed..
 Waiting - The process is waiting for some event to occur. For example the process may
be waiting for keyboard input, disk access request, inter-process messages, a timer to go
off, or a child process to finish.
 Terminated - The process has completed its execution.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

Process Control Block

For each process there is a Process Control Block (PCB), which stores the process-
specificinformation as shown below –

Process State – The state of the process may be new, ready, running, waiting, 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. Along
with the program counter, this state information must be saved when an interrupt occurs, to allow
the process to becontinued correctly afterward.
CPU scheduling information- This information includes a process priority, pointers to
schedulingqueues, and any other scheduling parameters.
Memory-management information – This include information such as the value of the base
and limit registers, the page tables, or the segment tables.
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 listof open files, and so on.
The PCB simply serves as the repository for any information that may vary from process to

process.

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.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

Scheduling Queues
 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 isgenerally 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.

A common representation of process scheduling is a queueing 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.
 The process could be removed forcibly from the CPU, as a result of an interrupt,
and be put backin the ready queue.

In the first two cases, the process eventually switches from the waiting state to the ready
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
state, and is then put back in the ready queue. A process continues this cycle until it
terminates, at which time it is removedfrom all queues.

Schedulers

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 [Link] 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.

 The short-term scheduler, or CPU Scheduler – selects job from memory and
assigns the CPUto it. It must select the new process for CPU frequently.

 The medium-term scheduler - selects the process in ready queue and

reintroduced into thememory.

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 readyqueue will be empty.
 If the scheduler selects more CPU bound process, then ready queue will be
full and I/Oqueue 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.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
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 )

Context Switch

The task of switching a CPU from one process to another process is

called context switching. 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 runningprocess is saved into the PCB and the state of another process is restored
from the PCB to the CPU.

Context switch time is an overhead, as the system does not do useful work while switching.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
Operations on Processes

Process Creation
A process may create several new processes. 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. Every process has a unique process ID.

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 [Link] a process creates a subprocess, the subprocess may be able to
obtain its resources in two ways :
 directly from the operating system
 Subprocess may take the resources of the
parent process. The resource can be
taken from parent in two ways –

o The parent may have to partition its resources among its children
o Share the resources among several children.

There are two options for the parent process after creating the child:

 Wait for the child process to terminate and then continue execution. The parent makes
a wait( ) system call.
 Run concurrently with the child, continuing to execute without waiting.

Two possibilities for the address space of the child relative to the parent:
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
 The child may be an exact duplicate of the parent, sharing the same program and
data segments in memory. Each will have their own PCB, including program
counter, registers, and PID. This is the behaviour of the fork system call in UNIX.
 The child process may have a new program loaded into its address space, with all
new code and data segments. This is the behaviour of the spawn system calls in
Windows.

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 childprocess completes, the parent process resumes and completes its execution.

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.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

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. Theparent 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 calledcascading termination.

Note : Processes which are trying to terminate but which cannot because their parent is not
waiting for them are termed zombies. These are eventually inherited by init as orphans and
killed off. (Modern UNIX shells do not produce as many orphans and zombies as older
systems used to. )

Interprocess Communication
Processes executing may be either co-operative or independent processes.
 Independent Processes – processes that cannot affect other processes or be
affected by otherprocesses executing in the system.
 Cooperating Processes – processes that can affect other processes or be
affected by otherprocesses 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 task by information sharing.

Cooperating processes require some type of inter-process communication. This is

allowed by twomodels : 1) Shared Memory systems 2)Message Passing systems.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

Sl. No. Shared Memory Message passing

1. A region of memory is shared by Message exchange is done among the

communicating processes, into which the processes by using objects.
information is written and read
2. Useful for sending large block of data Useful for sending small data.

3. System call is used only to create shared System call is used during every read
memory and write operation.
4. Message is sent faster, as there are no Message is communicated slowly.
system calls

 Shared Memory is faster once it is set up, because no system calls are required and
access occurs at normal memory speeds. Shared memory is generally preferable
when large amounts of information must be shared quickly on the same computer.
 Message Passing requires system calls for every
message transfer, and is therefore slower, but it is
simpler to set up and works well across multiple
computers. Message passing is generally preferable
when the amount and/or frequency of data transfers is
small.

Shared-Memory Systems

A region of shared-memory is created within the address space

of a process, which needs to communicate. Other processes
that needs to communicate uses this shared memory.

The form of data and position of creating shared

memory area is decided by the process. Generally a few messages must be passed back and
forth between the cooperating processes first in order to set up and coordinate the shared
memory access.

The process should take care that the two processes will not write the data to the
shared memoryat the same time.

Producer-Consumer Example Using Shared Memory

This is a classic example, in which one process is producing data and another process is
consuming the data.
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.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
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 byproducer. 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 theconsumer has to wait if the buffer is empty.
This example uses shared memory as a circular queue. The in and out are two pointers to
the array. Notein the code below that only the producer changes "in", and only the consumer
changes "out".
 First the following data is set up in the shared memory area:

#define BUFFER_SIZE 10 //buffer size

Typedef struct {
..

} item;
item buffer[ BUFFER_SIZE ];
int in = 0;
int out = 0;

 The producer process –

Note that the buffer is full when [ (in+1)%BUFFER_SIZE == out ]
item nextProduced;
while( true )
{
/* Produce an item and store it in nextProduced */
nextProduced = makeNewItem( . . . );

/* Wait for space to become available */

while( ( ( in + 1 ) % BUFFER_SIZE ) == out ) //full
; /* Do nothing */
/* And then, if not full store the item */
buffer[ in ] = nextProduced;
in = ( in + 1 ) % BUFFER_SIZE;
}

 The consumer process –

Note that the buffer is empty when [ in == out ]
item nextConsumed;
while( true )
{
/* Wait for an item to become available */
while( in == out ) // buffer empty
; /* Do nothing */
/* Get the next available item */
nextConsumed = buffer[ out ];
out = ( out + 1 ) % BUFFER_SIZE;
}
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

Message-Passing Systems
A mechanism to allow process communication without sharing
addressspace. 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 canbe sent.
 There are three methods of creating the link between the sender and the receiver-
o Direct or indirect communication ( naming )
o Synchronous or asynchronous communication (Synchronization)
o Automatic or explicit buffering.

a) Naming
The processes that wants to communicate should have a way to refer eachother. (
using someidentity)
Direct communication the sender and receiver must explicitly know eachothers name.
The syntax forsend() 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 tocommunicate. 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. Hereboth 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 datacan 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 changethe identifier in the whole system(sender and receiver), where the messages
are sent and received.

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.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
Two processes can communicate only if they have a

shared [Link] 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.

b) Synchronization
The send and receive messages can be implemented as either blocking or non-blocking.

Blocking (synchronous) send - sending process is blocked

(waits) until themessage is received by receiving process or the
mailbox.
Non-blocking (asynchronous) send - sends the message and
continues (doesnotwait)

Blocking (synchronous) receive - The receiving process is blocked

until a messageis available
Non-blocking (asynchronous) receive - receives the message
without block. Thereceived message may be a valid message or null.

c) 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 thequeue. 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. Aftersending ‘n’ bytes the sender is blocked.
Unbounded capacity - The queue is of infinite capacity. The sender never blocks.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

2.2 Multi-Threading Programming & Process Synchronization

Threads
 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. The user
cannot simultaneously type in characters and run the spell checker within
the same process, for example.

Many modern operating systems have extended the process concept to allow a
process to have multiple threads of execution and thus to perform more than
one task at a time.
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 heavy weight) 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.

Figure 2.14 Single-threaded and multithreaded processes.

Benefits of multithreaded programming
The benefits of multithreaded programming can be broken down into four major categories:
o 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. For
instance of a multithreaded Web browser could allow user interaction in
one thread while an image was being loaded in another thread.
o Resource sharing. Processes may only share resources through
techniques such as shared memory or message passing. However, threads
share the memory and the resources of the process to which they belong by
default. 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.
o Economy. Allocating memory and resources for process creation is costly.
Because threads share the resources of the process to which they belong, it
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
is more economical to create and context-switch threads.
o Scalability. 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 processor,
regardless how many are available. Multithreading on a multi CPU
machine increases parallelism.

Multithreading Models
Support for threads may be provided either at the user level, for user threads or
by the kernel, for kernel threads. User threads are supported above the kernel and
are managed without kernel support, whereas kernel threads are supported and
managed directly by the operating system. Ultimately, a relationship must exist
between user threads and kernel threads.
1. Many to One Model

Figure 2.15Many-to-one model.

 The many-to-one model (Figure 2.15) maps many user-level threads to one kernel
thread.
 Thread management is done by the thread library in user One to One
Model 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 unableto rum in parallel on multiprocessors.
 Example: Solaris
2. One to One Model
 The one-to-one model (Figure 2.16) 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 thecorresponding 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,
implement the one-to-onemodel.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

Figure 2.16 One-to-one model

3. Many to Many Model

 The many-to-many model (Figure 2.17) multiplexes many user-level
threads to smaller or equal number of kernel threads. The number of kernel
threads may be specific to either a particular application or a particular
machine.
 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.
 The many-to-many model suffers from neither of these shortcomings:
developers can create as many user threads as necessary, and the
corresponding kernel threads can run in parallel on a multiprocessor. Also,
when a thread performs a blocking system call, the kernel can schedule
another thread for execution.

Threading Issues
1. The fork() and exec() System Calls
□ If one thread in a program calls fork(), does the new process duplicate all
threads, or is the new process single-threaded? Some UNIX systems have
chosen to have two versions of fork(), one that duplicates all threads and
another that duplicates only the thread that invoked the fork() system call.
□ If a thread invokes the exec() system call, the program specified in the
parameter to exec () will replace the entire process-including all threads.
2. Cancellation
□ Thread cancellation is the task of terminating a thread before it has
completed. For example, if multiple threads are concurrently searching
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
through a database and one thread returns the result, the remaining threads
might be canceled.
□ A thread that is to be canceled is often referred to as the target thread.
□ Cancellation of a target thread may occur in two different scenarios:
o Asynchronous cancellation. One thread immediately
terminates the targetthread.
o Deferred cancellation. The target thread periodically checks
whether it should terminate, allowing it an opportunity to
terminate itself in an orderly fashion.
□ The difficulty with cancellation occurs in situations where resources have
been allocated to a canceled thread or where a thread is canceled while in
the midst of updating data it is sharing with other threads.

3. Signal Handling
□ A signal is used in UNIX systems to notify a process that a particular event has
occurred.
All signals, whether synchronous or asynchronous, follow the same pattern:
o A signal is generated by the occurrence of a particular event.
o A generated signal is delivered to a process.
o Once delivered, the signal must be handled.
□ Examples of synchronous signals include illegal memory access and
division by 0. If a running program performs either of these actions, a
signal is generated.
□ Every signal has a default signal handler that is run by the kernel when
handling that signal. This default action can be overridden by a user
defined signal handler that is called to handle the signal.
□ Handling signals in single-threaded programs is straightforward: signals
are always delivered to a process. However, delivering signals is more
complicated in multithreaded programs, where a process may have several
threads. Where, then, should a signal be delivered?
□ In general the following options exist:
o Deliver the signal to the thread to which the signal applies.
o Deliver the signal to every thread in the process.
o Deliver the signal to certain threads in the process.
o Assign a specific thread to receive all signals for the process.

4. Thread Pools
□ The first issue concerns the amount of time required to create the thread
prior to servicing the request, together with the fact that this thread will be
discarded once it has completed its work.
□ The second issue is more troublesome: if we allow all concurrent requests
to be serviced in a new thread, we have not placed a bound on the number
of threads concurrently active in the system. Unlimited threads could
exhaust system resources, such as CPU time or memory. One solution to
this problem is to use a thread pool.
□ The general idea behind a thread pool is to create a number of threads at
process startup and place them into a pool, where they sit and wait for
work.
□ Thread pools offer these benefits:
o Servicing a request with an existing thread is usually faster than
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
waiting to create a thread.
o A thread pool limits the number of threads that exist at any one
point. This is particularly important on systems that cannot
support a large number of concurrent threads.

5. Thread-Specific Data
□ Threads belonging to a process share the data of the process. Indeed, this
sharing of dataprovides one of the benefits of multithreaded programming.
□ However, in some circumstances, each thread might need its own copy of certain
data.
We will call such data thread specific data.
□ For example, in a transaction-processing system, we might service each transaction
in a
separate thread. Furthermore, each transaction might be assigned a unique
identifier. Toassociate each thread with its unique identifier, we could use
thread-specific data.

6. Scheduler Activations
 A final issue to be considered with multithreaded programs concerns
communication between the kernel and the thread library, which may be
required by the many-to-many and two-level models.
 Such coordination allows the number of kernel threads to be dynamically
adjusted to help ensure the best performance.
 This can be achieved with the help of scheduler
activations. Many systems implementing either the many-to-many or two-level
model place an intermediate data structure between the user and kernel threads.
 This data structure—typically known as a lightweight process, or LWP.
 The kernel provides an application with a set of virtual processors (LWPs), and
the applicationcan schedule user threads onto an available virtual processor.
 Furthermore, the kernel must inform an application about certain events.
This procedure isknown as an upcall.
 Upcalls are handled by the thread library with an upcall handler, and upcall
handlers must runon a virtual processor.
 One event that triggers an upcall occurs when an application thread is about to block.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

Difference between Process and Thread

S. Process Thread
N.
1 Process is heavy weight orresource Thread is light weight, taking lesser
intensive. resources than a process.
2 Process switching needs Thread switching does not need to interact
interaction with operating with operating system.
system.
In multiple processing
3 environments, each process All threads can share same set of openfiles,
executes the same code but hasits child processes.
own memory and file
resources.
If one process is blocked, then no While one thread is blocked and waiting, a
4 other process can execute until the second thread in the same task can run.
first process is unblocked.
5 Multiple processes without Multiple threaded processes use fewer
using threads use more resources.
resources.
6 In multiple processes each One thread can read, write or change
process operates independently another thread's data.
of the others.

Advantages of Thread
 Threads minimize the context switching time.
 Use of threads provides concurrency within a process.
 Efficient communication.
 It is more economical to create and context switch threads.
 Threads allow utilization of multiprocessor architectures to a greater scale and
efficiency.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

2.3 Process Scheduling

CPU-I/O Burst Cycle:
The success of CPU scheduling depends on an observed property of processes:
Process executionconsists of a cycle of CPU execution and I/O wait.
Processes alternate between these two [Link] execution begins with a CPU burst.
That is followed by an I/O burst, which is followed by another CPU burst, then
another I/O burst, andso on.
Eventually, the final CPU burst ends with a system request to terminate execution (Figure 5.1).

2.3.1CPU Scheduler
 Whenever the CPU becomes idle, the operating system must select one of the
processes in theready queue to be executed.
 The selection process is carried out by the short-term scheduler (or CPU scheduler).
 The scheduler selects a process from the processes in memory that are ready
to execute andallocates the CPU to that process.

2.3.2Preemptive Scheduling
□ CPU-scheduling decisions may take place under the following four circumstances:
1. When a process switches from the running state to the waiting
state (for example, as the result of an I/0 request or an invocation
of wait for the termination of oneof the child processes)
2. When a process switches from the running state to the ready
state (for example,when an interrupt occurs)
3. When a process switches from the waiting state to the ready state (for
example, at completion of I/0)
4. When a process terminates

□ When scheduling takes place only under circumstances 1 and 4, we say

that thescheduling scheme is non-preemptive or cooperative; otherwise,
it is preemptive.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

5.1.2 Dispatcher
□ The dispatcher is the module that gives control of the CPU to the process
selected by theshort-term scheduler. This function involves the following:
o Switching context
o Switching to user mode
o Jumping to the proper location in the user program to restart that program.
□ The dispatcher should be as fast as possible, since it is invoked during
every process switch. The time it takes for the dispatcher to stop one
process and start another running isknown as the dispatch latency.

5.2 Scheduling Criteria

Many criteria have been suggested for comparing CPU-scheduling algorithms.
□ CPU utilization. We want to keep the CPU as busy as possible. In a real
system, it should range from 40 percent (for a lightly loaded system) to 90
percent (for a heavily used system).
□ Throughput. If the CPU is busy executing processes, then work is being done.
One measure of work 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. Turnaround time is the sum of the
periods spent waiting to get into memory, waiting in the ready queue, executing
on the CPU, and doing I/O.
□ Waiting time. Waiting time is the sum of the periods spent waiting in the ready
queue.
□ Response time. In an interactive system, turnaround time may not be the best
criterion. Often, a process can produce some output fairly early and can continue
computing new results while previous results are being output to the user. Hence
another measure response time used, which is the time it takes to start
responding, not the time it takes to output the response. The turnaround time is
generally limited by the speed of the output device.

5.3 Scheduling Algorithms

1. First-Come, First-Served Scheduling

 With this scheme, the process that requests the CPU first is allocated the CPU first.
 The implementation of the FCFS policy is easily managed with a FIFO queue.
 When a process enters the ready queue, its PCB is linked onto the tail of the queue.
When the CPU is free, it is allocated to the process at the head of the queue.
The runningprocess is then removed from the queue.
 On the negative side, the average waiting time under the FCFS policy is often quite
long.
 FCFS scheduling algorithm is non-preemptive. Once the CPU has been allocated to a
process, that process keeps the CPU until it releases the CPU, either by terminating or
by requesting I/0.
 The FCFS algorithm is thus particularly troublesome for time-sharing systems,
where it is important that each user get a share of the CPU at regular intervals. It
would be disastrousto allow one process to keep the CPU for an extended period.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
Example:
Process Burst Time
P1 24
P2 3
P3 3
If the processes arrive in the order P1, P2, P3, and are served in FCFS
order, we get theresult shown in the following Gantt chart.

P1 P2 P3
0 24 27 30
Process Waiting Time Turnaround Time =
(Waiting Time + Burst Time)
P1 0 0 + 24 = 24
P2 24 24+ 3 = 27
P3 27 27 + 3 = 30

Another way to solve is as follows: OR

CPU
Burst Completion Turnaround
Time Wait Time Response
Process Time Time (TAT) (TAT (WT) Time
(CT) (CT – AT) – BT) (RT)
(BT)
P1 24 24 24 0 0
P2 3 27 27 24 24
P3 3 30 30 27 27
 Average Waiting Time = (0 + 24 + 27) / 3 = 17 milliseconds.
 Average Turnaround Time = (24 + 27 + 30) / 3 = 27 milliseconds

If the processes arrive in the order P2, P3 , P1, however, the results will
be as shown inthe following Gantt chart:
P2 P3 P1
0 3 6 30
Process Waiting Time Turnaround Time =
(Waiting Time + Burst Time)
P1 6 6 + 24 = 30
P2 0 0+3=3
P3 3 3+3=6
OR
CPU
Burst Completion Turnaround
Time Wait Time Response
Process Time Time (TAT) (WT) Time
(BT)
(CT) (CT – AT) (TAT – BT) (RT)

P1 24 30 30 6 6
P2 3 3 3 0 0
P3 3 6 6 3 3

 Average Waiting Time = (6 + 0 + 3) / 3 = 3 milliseconds.

 Average Turnaround Time = (30 + 3 + 6) / 3 = 13 milliseconds.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
2. Shortest-Job-First Scheduling (Non Preemptive SJF)
 This algorithm associates with each process the length of the process's next CPU
burst. When the CPU is available, it is assigned to the process that has the
smallest next CPU burst. If the next CPU bursts of two processes are the same,
FCFS scheduling is used to break the tie.
 The SJF scheduling algorithm is provably optimal, in that it gives the minimum
averagewaiting time for a given set of processes.
 The real difficulty with the SJF algorithm is knowing the length of the next CPU
request.

 Example:

Process Burst Time

P1 6
P2 8
P3 7
P4 3
Using SJF scheduling, we would schedule these processes according to the
followingGantt chart:

P4 P1 P3 P2
0 3 9 16 24

Process Waiting Time Turnaround Time =

(Waiting Time + Burst Time)
P1 3 3+6=9
P2 16 16 + 8 = 24
P3 9 9 + 7 = 16
P4 0 0+3=3
OR
CPU
Burst Completion Turnaround
Time Wait Time Response
Process Time Time (TAT) (TAT (WT) Time
(CT) (CT – AT) – BT) (RT)
(BT)
P1 6 9 9 3 3
P2 8 24 24 16 16
P3 7 16 16 9 9
P4 3 3 3 0 0

 Average Waiting Time = (3 + 16 + 9 + 0) /4 = 7 milliseconds.

 Average Turnaround Time = (9 + 24 + 16 + 3)/ 4 = 13 milliseconds.
 The real difficulty with the SJF algorithm is knowing the length of the next CPU
request.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
3. Shortest-Remaining-Time-First scheduling - SRTF (Preemptive SJF)
 A preemptive SJF algorithm will preempt the currently executing process, whereas a non-
preemptive SJF algorithm will allow the currently running process to finish its CPU burst.
Preemptive SJF scheduling is sometimes called shortest-remaining-time-first
scheduling.
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
 Preemptive SJF schedule is as depicted in the following Gantt chart:
P1 P2 P4 P1 P3
0 1 5 10 17 26

Process Waiting Time Turnaround Time =

(Waiting Time + Burst Time)
P1 10 – 1 - 0 = 9 9 + 8 = 17
P2 1-1=0 0+4=4
P3 17 - 2 = 15 15 + 9 = 24
P4 5-3=2 2+5=7
OR
CPU
Arrival Burst Completion Turnaround
Time Wait Time Response
Process Time Time Time (TAT) (TAT (WT) Time
(AT) (CT) (CT – AT) – BT) (RT)
(BT)
P1 0 8 17 17 9 0
P2 1 4 5 4 0 1
P3 2 9 26 24 15 17
P4 3 5 10 7 2 5

 The average waiting time ( 9 + 0 + 15 + 2 ) / 4 = 26 / 4 = 6.5 milliseconds.

 The average turnaround time is (17 + 4 + 24 + 7) / 4 = 52 / 4 = 13 milliseconds.

Non-preemptive SJF scheduling would result in an average waiting time of 7.75 milliseconds as
shown below:
Gantt Chart
P1 P2 P4 P3
0 8 12 17 26
CPU
Arrival Burst Completion Turnaround
Time Wait Time Response
Process Time Time Time (TAT) (TAT (WT) Time
(AT) (CT) (CT – AT) – BT) (RT)
(BT)
P1 0 8 8 8 0 0
P2 1 4 12 11 7 8
P3 2 9 26 24 15 17
P4 3 5 17 14 9 12
Thus average waiting time = (0 + 7 + 15 + 9)/4 = 7.75 ms.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
4. Priority Scheduling
The SJF algorithm is a special case of the general priority scheduling algorithm. A
priority is associated with each process, and the CPU is allocated to the process
with the highest priority. Equal-priority processes are scheduled in FCFS order.
As an example, consider the following set of processes, assumed to have arrived at
time 0 in the order P1, P2, P3, P4, P5with the length of the CPU burst given in
milliseconds:
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

Using priority scheduling, we would schedule these processes according

to the followingGantt chart:

P2 P5 P1 P3 P4
0 1 6 16 18 19

Process Waiting Time Turnaround Time =

(Waiting Time + Burst Time)
P1 6 6 + 10 =16
P2 0 0+1=1
P3 16 16 + 2 = 18
P4 18 18 + 1 = 19
P5 1 1+5=6
OR
CPU
Priority Burst Completion Turnaround
Time Wait Time Response
Process Time Time (TAT) (WT) Time
(CT) (CT – AT) (TAT – BT) (RT)
(BT)
P1 3 10 16 16 6 6
P2 1 1 1 1 0 0
P3 4 2 18 18 16 16
P4 5 1 19 19 18 18
P5 2 5 6 6 1 1

 The average waiting time is (6+0+16+18+1) / 5 = 8.2 milliseconds.

 The Average Turnaround Time = ( 16 + 1 + 18 + 19 + 6) / 5 = 12 ms
 Priority scheduling can be either preemptive or non-preemptive.
 A major problem with priority scheduling algorithms is indefinite blocking, or
starvation. A process that is ready to run but waiting for the CPU can be
considered blocked. A priority scheduling algorithm can leave some low priority
processes waiting indefinitely.
 A solution to the problem of indefinite blockage of low-priority processes is
aging.
 Aging is a technique of gradually increasing the priority of processes that wait in
the system for a long time. For example, if priorities range from 127 (low) to 0
(high), we could increase the priority of a waiting process by1 every 15 minutes.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
5. Round-Robin Scheduling
 The round-robin (RR) scheduling algorithm is designed especially for
timesharing systems. It is similar to FCFS scheduling, but preemption is
added to enable the systemto switch between processes.
 A small unit of time, called a time quantum or time slice, is defined. A
time quantum isgenerally from 10 to 100 milliseconds in length.
 The ready queue is treated as a circular queue. The CPU scheduler goes
around the ready queue, allocating the CPU to each process for a time
interval of up to 1 time quantum.
 The average waiting time under the RR policy is often long.
 Example:
Process Burst Time
P1 24
P2 3
P3 3
 If we use a time quantum of 4 milliseconds, then process P1 gets the first 4
milliseconds. Since it requires another 20 milliseconds, it is preempted after the
first time quantum, and the CPU is given to the next process in the queue, process
P2. Process P2 does not need 4 milliseconds, so it quits before its time quantum
expires and so on.
 Once each process has received 1 time quantum, the CPU is returned to process P1
for anadditional time quantum.
 The resulting RR schedule is as follows:

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

Process Waiting Time Turnaround Time =

(Waiting Time + Burst Time)
P1 10 - 4 = 6 6 + 24 =30
P2 4 4+3=7
P3 7 7 + 3 = 10

OR
CPU
Burst Completion Turnaround
Time Wait Time Response
Process Time Time (TAT) (TAT (WT) Time
(CT) (CT – AT) – BT) (RT)
(BT)
P1 24 30 30 6 0
P2 3 7 7 4 4
P3 3 10 10 7 7

 P1 waits for 6 milliseconds (10- 4), P2 waits for 4 milliseconds, and P3 waits
for 7milliseconds.
 The average waiting time is (6+4+7) = 17/3 = 5.66 milliseconds.
 The average turnaround time is now (30 + 7 + 10)/3 = 15.66 milliseconds.
 If a process's CPU burst exceeds 1 time quantum, that process is preempted and is
putback in the ready queue. The RR scheduling algorithm is thus preemptive.
 The performance of the RR algorithm depends heavily on the size of the time
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
quantum.
 At one extreme, if the time quantum is extremely large, the RR policy is the same
as theFCFS policy.
 In contrast, if the time quantum is extremely small (say, 1 millisecond), the RR
approach is called processor sharing and (in theory) creates the appearance that
each of n processes has its own processor running at 1 / n the speed of the real
processor.
Problem 1: Consider the following processes with the CPU burst time given in milliseconds

Process Arrival time Burst time

P1 0 8
P2 1 4
P3 2 9
P4 3 5

Calculate average turnaround time and average waiting time for the following algorithms
drawing Gantt chart.
i) FCFS
ii) Preemptive SJF
iii) Round Robin(quantum=1 unit)
Sol: i) FCFS
Gantt Chart
P1 P2 P3 P4
0 8 12 21 26
Process Arrival Burst Completion Turnaround Waiting Time
Time Time Time (CT) Time (TAT) (TAT – BT)
(AT) (BT) (CT – AT)
P1 0 8 8 8 0
P2 1 4 12 11 7
P3 2 9 21 19 10
P4 3 5 26 23 18

The average waiting time ( 0 +7 + 10 + 18 ) / 4 = 35/ 4 = 8.75 milliseconds.

The average turnaround time is (8 + 11 + 19 + 23) / 4 = 61 / 4 = 15.25 milliseconds.
ii) Preemptive SJF
Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

Arrival Burst Completion Turnaround Waiting Time

Process Time Time Time (CT) Time (TAT) (TAT – BT)
(AT) (BT) (CT – AT)
P1 0 8 17 17 9
P2 1 4 5 4 0
P3 2 9 26 24 15
P4 3 5 10 7 2
The average waiting time ( 9 +0 + 15 + 2) / 4 = 26/ 4 = 6.5 milliseconds.
The average turnaround time is (17 + 4 + 24 + 7) / 4 = 52 / 4 = 13 milliseconds.
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling
iv) Round Robin (Time quantum = 1)
Ready Queue
P1 P2 P1 P3 P2 P4 P1 P3 P2 P4 P1 P3 P2 P4 P1 P3 P4 P1

P3 P4 P1 P3 P1 P3 P3 P3

Gantt Chart

P1 P2 P1 P3 P2 P4 P1 P3 P2 P4 P1 P3 P2 P4 P1 P3 P4 P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

P3 P4 P1 P3 P1 P3 P3 P3
19 20 21 22 23 24 25 26

Process Arrival Burst Completion Turnaround Waiting Time

Time Time Time (CT) Time (TAT) (TAT – BT)
(AT) (BT) (CT – AT)
P1 0 8 23 23 15
P2 1 4 13 12 8
P3 2 9 26 24 15
P4 3 5 20 17 12

The average waiting time = (15 +8 + 15 + 12) / 4 = 50 / 4 = 12.5 milliseconds.

The average turnaround time is = (23 + 12 + 24 + 17) / 4 = 76 / 4 = 19 milliseconds.

Problem 2: Consider the following processes with the CPU burst time given in milliseconds

Process Arrival Priority CPU Burst I/O time CPU Burst

time time time
P1 0 2 1 5 3
P2 2 3 3 3 1
P3 3 1 2 3 1
P4 3 4 2 4 1

Assuming Preemptive mode and criteria as Priority based, compute the Completion time of each
process using Gantt chart. Also calculate CPU idle time and CPU usage time in percentage.

Sol:
Gantt Chart
|==P3 I/O === | |=====P4 I/O ====|

P1 P2 P3 P3 P2 P1 P1 P3 P1 P2 P4 P4 P2 P4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

|====P1 I/O===========| |==P2 I/O=====|

Completion Time of P1 = 10 Completion Time of P2 = 15

Completion Time of P3 = 9 Completion Time of P4 = 18

CPU Idle Time = 4/18 = 22.22% CPU Usage Time = 14/18 = 77.78
 Subject Module 2 Prepared by: Dept. of ISE, DBIT
Operating Systems Process, Thread and Process
(BCS303) Scheduling

6. Multilevel Queue Scheduling

A multilevel queue scheduling algorithm partitions the ready queue into
several separate queues

Figure 2.19 Multilevel Queue Schedule

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.
Each queue has absolute priority over lower-priority queues. No process in
the batch queue, for example, could run unless the queues for system
processes, interactive processes, and interactive editing processes were all
empty.
If an interactive editing process entered the ready queue while a batch
process was running, the batch process would be preempted.
Another possibility is to time-slice among the queues. Here, each queue
gets a certain portion of the CPU time, which it can then schedule among
its various processes.

7. Multilevel Feedback Queue Scheduling

The multilevel feedback queue scheduling algorithm allows a process to
move between queues. The idea is to separate processes according to the
characteristics of their CPU bursts. If a process uses too much CPU time, it
will be moved to a lower-priority queue.
This scheme leaves I/O-bound and interactive processes in the higher-
priority queues. In addition, a process that waits too long in a lower-
priority queue may be moved to a higher-priority queue. This form of
aging prevents starvation.
For example, consider a multilevel feedback queue scheduler with three
queues, numbered from 0 to 2 (Figure 2.20).
 Figure 2.20 Multilevel Feedback Queue

The scheduler first executes all processes in queue 0. Only when queue 0
is empty will it execute processes in queue 1. Similarly, processes in queue
2 will only be executed if queues 0 and 1 are empty. A process that arrives
for queue 1 will preempt a process in queue 2. A process in queue 1 will in
turn be preempted by a process arriving for queue 0.
A process entering the ready queue is put in queue 0. A process in queue 0
is given a time quantum of 8 milliseconds. If it does not finish within this
time, it is moved to the tail of queue 1. If queue 0 is empty, the process at
the head of queue 1 is given a quantum of 16 milliseconds. If it does not
complete, it is preempted and is put into queue 2. Processes in queue 2 are
run on an FCFS basis but are run only when queues 0 and 1 are empty.

Question Bank
1. With neat flow diagram explain the different stages of a Process.
2. Describe message passing model and Shared memory model of communication between
processes
3. Discuss the reasons for providing an environment that allows process
Cooperation.
4. Describe the differences among short-term, medium-term, and longterm
scheduling.
5. What is multithreading? What are the benefits of multithreaded programming?
(June 10 / Dec 11)
6. Write a note on multithreaded models. (June 09 / Dec 09)
7. Consider 4 jobs with (arrival time, burst time) as (0, 5) (0.2, 2) (0.6, 8) (1.2, 4).
Find the average turnaround time and waiting time for the jobs using FCFS, SJF
and RR(q=1) scheduling algorithms. (June11)
8. Consider the following set of processes. (June10)
Process Arrival Time Burst Time
P1 0 1
P2 1 9
P3 2 1
P4 3 9
a) Draw Gantt charts showing the execution of these processes using FCFS,
preemptive SJF, non-Pre-emptive SJF and RR (Quantum 1) scheduling
schemes.
b) Compute the turnaround time and waiting time for each process for each
 of the schemesabove.
c) Compute the average turnaround time and average waiting time in each
scheme and thusfind the best scheme in this particular case.
9. Why thread is called LWP? Describe any one threading model. (Dec 08)
10. Suppose the following jobs arrive for processing at the times indicated. Each
job will run the listed amount of time.
Job 1 2 3
Arrival Time 0.0 0.4 1.0
Burst Time 8 4 1
a) Give Gantt chart illustrating the execution of these jobs using the non-
preemptive FCFS and SJF scheduling algorithms..
b) What is turnaround time and waiting time of each job for the above algorithms?
c) Compute average turnaround time if CPU is left idle for 1 unit and then SJF is
used.(Job1and Job2 will wait during this time) Dec.09)
11. Consider the following set of processor with a length of CPU burst time given in
milliseconds.

Process Arrival time Burst time Priority

P1 0 7 4
P2 3 2 2
P3 4 3 1
P4 4 1 4
P5 5 3 3
Find the average waiting time &average turnaround time using Gantt chart for the
followingscheduling algorithms.
i. Preemptive SJF
ii. Preemptive Priority( Smaller number represents high priority)
iii. Round-Robin(time slice =1ms) (Dec 08)