20CST206

OPERATING SYSTEMS
Hari M
Assistant Professor
Saintgits College of
Engineering
Kottayam, Kerala
Module-II Processes and Process
Scheduling

Processes :
Process states, Process control block, threads, Scheduling
Operations on processes: process creation and termination
Inter-process communication: Shared memory systems, Message
Passing
Process Scheduling:
Basic concepts, Scheduling Criteria- Scheduling algorithms – First
come First Served, Shortest Job First, Priority scheduling, Round Robin
Scheduling
Process

• A process is a program in execution

• Conceptually, each process has its own virtual CPU
• In reality, the real CPU switches back and forth from
process to process.
• This rapid switching back and forth is called
multiprogramming.
• Program is passive entity stored on disk (executable file), process is active
• Program becomes process when executable file loaded into memory
• Execution of program started via GUI mouse clicks, command line entry of
its name, etc
• One program can be several processes
• Consider multiple users executing the same program.
• For instance, several users may be running different copies of the mail
program, or the same user may invoke many copies of the web browser
program. Each of these is a separate process; and although the text
sections are equivalent, the data, heap, and stack sections vary.
Process in the Memory

• A process has the program code, which is known as

the text section.
• Process 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),
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 States
Process States

1. New State-
A process is said to be in new state when a program present in the
secondary memory is initiated for execution.
2. Ready State-
• A process moves from new state to ready state after it is loaded into
the main memory and is ready for execution.
• In ready state, the process waits for its execution by the processor.
• In multiprogramming environment, many processes may be present
in the ready state.
3. Run State-
• A process moves from ready state to run state after it is
assigned the CPU for execution.
4. Terminate State-
• A process moves from run state to terminate state after its
execution is completed.
• After entering the terminate state, context (PCB) of the process is
deleted by the operating system.
5. Block Or Wait State-
• A process moves from run state to block or wait state if it requires an
I/O operation or some blocked resource during its execution.
• After the I/O operation gets completed or resource becomes available,
the process moves to the ready state.
6. Suspend Ready State-
• A process moves from ready state to suspend ready state if a process
with higher priority has to be executed but the main memory is full.
• Moving a process with lower priority from ready state to suspend
ready state creates a room for higher priority process in the ready
state.
• The process remains in the suspend ready state until the main
memory becomes available.
• When main memory becomes available, the process is brought back
to the ready state.
6. Suspend Wait State-
• A process moves from wait state to suspend wait state if a process
with higher priority has to be executed but the main memory is full.
• Moving a process with lower priority from wait state to suspend wait
state creates a room for higher priority process in the ready state.
• After the resource becomes available, the process is moved to the
suspend ready state.
• After main memory becomes available, the process is moved to the
ready state.
Excercise

• Draw process state transition diagram for an OS

which satisfy the below two criteria will be as
follows

1. Each process is in one of the states NEW (Create),

Ready , Running, Blocked (Stop/Wait) and
Terminated.
2. Only non preemptive scheduling is used by the OS.
Process Control Block (PCB)

• Process Control Block (PCB) is a data

structure that stores information
about a particular process.
• This information is required by the
CPU while executing the process.
• Each process is identified by its own
process control block (PCB).
• It is also called as context of the
process.
Process Attributes

The various attributes of process stored in the PCB are-

1. Process Id-
Process Id is a unique Id that identifies each process of the system uniquely.
A process Id is assigned to each process during its creation.

2. Program Counter-

Program counter specifies the address of the instruction to be executed next.

Before execution, program counter is initialized with the address of the first instruction of
the program.
After executing an instruction, value of program counter is automatically incremented to
point to the next instruction.
This process repeats till the end of the program.
3. Process State-
• Each process goes through different states during its lifetime.
• Process state specifies the current state of the process.
4. Priority-
• Priority specifies how urgent is to execute the process.
• Process with the highest priority is allocated the CPU first among all the processes.
5. General Purpose Registers-
• General purpose registers are used to hold the data of process generated during its
execution.
• Each process has its own set of registers which are maintained by its PCB.
6. List of Open Files-
• Each process requires some files which must be present in the main
memory during its execution.
• PCB maintains a list of files used by the process during its
execution.

7. List of Open Devices-

• PCB maintains a list of open devices used by the process during its
execution.
Important Notes
• PCB of each process resides in the main memory.
• There exists only one PCB corresponding to each process.
• PCB of all the processes are present in a linked list.
How PCBs are Stored

PCBs are stored in the form of LinkedList in memory

Operating System uses Process Table to find the PCB present in
memory.
 Process table
• Process table is a table that contains Process ID and the reference to the corresponding PCB
in memory.
Context Switch

• When CPU switches to another process, the system must

save the state of the old process and load the saved state
for the new process via a context switch.
• Context of a process represented in the PCB
• Context-switch time is overhead; the system does no useful
work while switching – The more complex the OS and the
PCB → longer the context switch
• Time dependent on hardware support – Some hardware
provides multiple sets of registers per CPU → multiple
contexts loaded at once
Threads

• Thread is an execution unit that consists of its own program

counter, a stack, and a set of registers where the program
counter mainly keeps track of which instruction to execute
next, a set of registers mainly hold its current working
variables, and a stack mainly contains the history of
execution.
• Threads are also known as Lightweight processes. Threads
are a popular way to improve the performance of an
application through parallelism.
Thread Control Block
1. Thread ID: It is a unique identifier assigned by the Operating System to
the thread when it is being created.
2. Thread states: These are the states of the thread which changes as the
thread progresses through the system
3. CPU information: It includes everything that the OS needs to know
about, such as how far the thread has progressed and what data is being
used.
4. Thread Priority: It indicates the weight (or priority) of the thread over
other threads which helps the thread scheduler to determine which thread
should be selected next from the READY queue.
5. A pointer which points to the process which triggered the creation of this
thread.
6. A pointer which points to the thread(s) created by this thread.
PCB TCB relation
Advantages of Thread

• Responsiveness
• Faster context switch
• Effective utilization of multiprocessor system
• Resource sharing
• Communication
• Enhanced throughput of the system
[Link]: If the process is divided into multiple threads, if one
thread completes its execution, then its output can be immediately
returned.
[Link] context switch: Context switch time between threads is lower
compared to process context switch. Process context switching requires
more overhead from the CPU.
[Link] utilization of multiprocessor system: If we have multiple
threads in a single process, then we can schedule multiple threads on
multiple processor. This will make process execution faster.
[Link] sharing: Resources like code, data, and files can be shared
among all threads within a process. Note: stack and registers can’t be
shared among the threads. Each thread has its own stack and registers.
[Link]: Communication between multiple threads is easier, as
the threads shares common address space. while in process we have to
follow some specific communication technique for communication between
two process.
[Link] throughput of the system: If a process is divided into
multiple threads, and each thread function is considered as one job, then
the number of jobs completed per unit of time is increased, thus increasing
the throughput of the system.
 Difference between Process and Thread
S.N. Process Thread
1 Process is heavy weight or resource Thread is light weight, taking lesser resources
intensive. than a process.
2 Process switching needs interaction with Thread switching does not need to interact
operating system. with operating system.
3 In multiple processing environments, each All threads can share same set of open files,
process executes the same code but has child processes.
its own memory and file resources.

4 If one process is blocked, then no other While one thread is blocked and waiting, a
process can execute until the first process second thread in the same task can run.
is unblocked.
5 Multiple processes without using threads Multiple threaded processes use fewer
use more resources. resources.
6 In multiple processes each process One thread can read, write or change another
operates independently of the others. thread's data.
Single-threaded and multithreaded
processes
Types of Threads Threads

There are two types of threads:

• User Level Thread
• Kernel Level Thread
 User Level Threads

• In this case, the thread

management kernel is not aware
of the existence of threads.
• The thread library contains code
for creating and destroying
threads, for passing message and
data between threads, for
scheduling thread execution and
for saving and restoring thread
contexts.
• The application starts with a
single thread.
Advantages
• Thread switching does not require Kernel mode privileges.
• User level thread can run on any operating system.
• Scheduling can be application specific in the user level thread.
• User level threads are fast to create and manage.
Disadvantages
• In a typical operating system, most system calls are blocking.
• Multithreaded application cannot take advantage of
multiprocessing.
Kernel Level Threads

• In this case, thread management is done by the Kernel.

• There is no thread management code in the application area.
• Kernel threads are supported directly by the operating system.
• Any application can be programmed to be multithreaded.
• All of the threads within an application are supported within a single
process.
• The Kernel maintains context information for the process as a whole and
for individuals threads within the process.
• Scheduling by the Kernel is done on a thread basis.
• The Kernel performs thread creation, scheduling and management in
Kernel space.
• Kernel threads are generally slower to create and manage than the user
threads.
Advantages
• Kernel can simultaneously schedule multiple threads from the
same process on multiple processes.
• If one thread in a process is blocked, the Kernel can schedule
another thread of the same process.
• Kernel routines themselves can be multithreaded.
Disadvantages
• Kernel threads are generally slower to create and manage than
the user threads.
• Transfer of control from one thread to another within the same
process requires a mode switch to the Kernel.
 User Level threads Kernel Level Threads
These threads are implemented by Operating
These threads are implemented by users.
systems
These threads are not recognized by operating
These threads are recognized by operating systems,
systems,

In User Level threads, the Context switch requires

In Kernel Level threads, hardware support is needed.
no hardware support.

These threads are mainly designed as dependent These threads are mainly designed as independent
threads. threads.

In User Level threads, if one user-level thread On the other hand, if one kernel thread performs a
performs a blocking operation then the entire blocking operation then another thread can continue
process will be blocked. the execution.
Example of User Level threads: Java thread, POSIX
Example of Kernel level threads: Window Solaris.
threads.

Implementation of User Level thread is done by a While the Implementation of the kernel-level thread
thread library and is easy. is done by the operating system and is complex.

This thread is generic in nature and can run on any

This is specific to the operating system
operating system.
Multithreading Models

• Many to many relationship.

• Many to one relationship.
• One to one relationship.
Many to Many Model
Many to One Model
One to One Model
Process Scheduling

• The act of determining which process is in the ready state, and should
be moved to the running state is known as Process Scheduling.
• The prime aim of the process scheduling system is to keep the CPU
busy all the time and to deliver minimum response time for all
programs. For achieving this, the scheduler must apply appropriate
rules for swapping processes IN and OUT of CPU.
• Scheduling fell into one of the two general categories:

• Non Pre-emptive Scheduling: When the currently executing process

gives up the CPU voluntarily.
• Pre-emptive Scheduling: When the operating system decides to
favour another process, pre-empting the currently executing process.
Process Scheduling Queues
Process Scheduling Queues

• All processes, upon entering into the system, are stored in the Job Queue.
• Processes in the Ready state are placed in the Ready Queue.
• Processes waiting for a device to become available are placed in Device Queues. There
are unique device queues available for each I/O device.
• A new process is initially put in the Ready queue. It waits in the ready queue until it is
selected for execution(or dispatched). Once the process is assigned to the CPU and is
executing, one of the following several events can occur:

• The process could issue an I/O request, and then be placed in the 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 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 and has its
PCB and resources deallocated.
Types of Schedulers

There are three types of schedulers available:

• Long Term Scheduler

• Short Term Scheduler
• Medium Term Scheduler
Long Term Scheduler

• A job scheduler is another name for it. A long-term

scheduler determines which programmes are accepted for
processing into the system. It picks processes from the
queue and then loads them into memory so they can be
executed. For CPU scheduling, a process loads into
memory.
Short Term Scheduler

• CPU scheduler is another name for it. Its major goal is to

improve system performance according to the set of
criteria defined. It refers to the transition from the process’s
ready state to the running stage. The CPU scheduler
happens to choose a process from those that are ready to
run and then allocates the CPU to it.
Medium Term Scheduler

• It includes medium-term scheduling. Swapping clears the

memory of the processes. The degree of multiprogramming
is reduced. The switched out processes are handled by the
medium-term scheduler.
Operations on Process

• There are many operations that can be performed on

processes. Some of these are process creation, process
preemption, process blocking, and process termination.
• During the course of execution, 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, forming a tree of
processes.

• Process identifier (or pid)( which is typically an integer number) , is associated with each
process.

• The pid provides a unique value for each process in the system, and it can be used as an
index to access various attributes of a process within the kernel.
A typical process tree for the Linux
operating system
• The init process (which always has a pid of 1) serves as the root parent
process for all user processes.

• Once the system has booted, the init process can also create various user
processes, such as a web or print server, an ssh server etc.

• In Figure there is three children of init—login, kthreadd and sshd.

• The kthreadd process is responsible for creating additional processes that

perform tasks on behalf of the kernel (in this situation, khelper and
pdflush).
Resource usage of Child processes

• When a process creates a child process, that child process

will need certain resources (CPU time, memory, files, I/O
devices) to accomplish its task.

Resource sharing options

• Parent and children share all resources

• Children share subset of parent’s resources
• Parent share no resources
Execution of a child process

• When a process creates a new process, two possibilities for execution exist:
1. The parent continues to execute concurrently with its children.
2. The parent waits until some or all of its children have terminated.
• There are also two address-space possibilities for the new process:
1. The child process is a duplicate of the parent process (it has the same
program and data as the parent).
2. The child process has a new program loaded into it.
Process Creation Example
UNIX examples
• fork() system call creates new
process
• exec() system call used after a
fork() to replace the process’
memory space with a new
program.
• wait() system call issued by a
parent process and move
itself off the ready queue until
the termination of the child
How many times does the following
program print “yes”?

#include<stdio.h>
#include <unistd.h>
main()
{
fork();
fork();
printf(“Hello World");
}
int main()
{
fork();
fork();
fork();
printf("Hello world!\n");
return 0;
}
How many times does the following
program print “Hello World”?
int main(void) {
pid_t pid = fork();

if(pid == 0) {
printf("Child => PPID: %d PID: %d\n", getppid(), getpid());
exit(EXIT_SUCCESS);
}
else if(pid > 0) {
printf("Parent => PID: %d\n", getpid());
printf("Waiting for child process to finish.\n");
wait(NULL);
printf("Child process finished.\n");
}
else {
printf("Unable to create child process.\n");
}

return 0;
}
void forkexample()
{
if (fork() == 0)
printf("Hello from Child!\n");

else
printf("Hello from Parent!\n");
}
int main()
{
forkexample();
return 0;
}
void forkexample()
{
int x = 1;

if (fork() == 0)
printf("Child has x = %d\n", ++x);
else
printf("Parent has x = %d\n", --x);
}
int main()
{
forkexample();
return 0;
}
#include<stdio.h> else if (pid == 0)
void main( ) {
{ execlp("/bin/ls","ls",NULL);
int pid; }
pid = fork(); else
if(pid < 0) {
{ wait(NULL);
fprintf(stderr, "Fork Failed"); printf("Child complete");
exit(-1); exit(0);
} }
}
 Process Termination

• A process terminates when it finishes executing its final statement and asks
the operating system to delete it by using the exit() system call.

• At that point, the process may return a status value (typically an integer) to
its parent process (via the wait() system call).

• All the resources of the process like physical and virtual memory, open
files, and I/O buffers are deallocated by the operating system.
Process Termination

• A process can cause the termination of another process by system call (for
example, TerminateProcess() in Windows).

• Usually, such a system call can be invoked only by the parent of the process that is
to be terminated.

• Parent needs to know the identities of its children if it is to terminate them.

• When one process creates a new process, the identity of the newly created process
is passed to the parent.
Process Termination

• A parent may terminate the execution of one of its children for a variety of
reasons, such as :
• The child has exceeded its usage of some of the resources that it has
been allocated.

• The task assigned to the child is no longer required.

• The parent is exiting, and the operating system does not allow a child
to continue if its parent terminates.
Process Termination- Cascading
termination

• Some systems do not allow a child to exist if its parent has

terminated.
• If a process terminates (either normally or abnormally), then all its
children must also be terminated. This phenomenon, referred to as
cascading termination, is normally initiated by the operating
system.
 Process Termination- Zombie process

• When a process terminates, its resources are deallocated by the operating system.

• However, its entry in the process table must remain there until the parent calls wait(),
because the process table contains the process’s exit status.

• A process that has terminated, but whose parent has not yet called wait(), is known as
a zombie process.

• Once the parent calls wait(), the process identifier of the zombie process and its entry
in the process table are released.
Process Termination- Zombie
process
Process Termination- Orphans.

• If a parent did not invoke wait() and instead terminated, its child processes
left as orphans.

• Linux and UNIX handles orphans by assigning the init process as the new
parent to orphan processes.

• The init process periodically invokes wait(), thereby allowing the exit
status of any orphaned process to be collected and releasing the orphan’s
process identifier and process-table entry.
Process Termination- Orphans -
Example