UNIT II

Process Concept: Process scheduling, Operations on processes, Inter-process communication,

Communication in client server systems.
Multithreaded Programming: Multithreading models, Thread libraries, Threading issues.
Process Scheduling: Basic concepts, Scheduling criteria, Scheduling algorithms, Multiple
processor scheduling, Thread scheduling.
Inter-process Communication: Race conditions, Critical Regions, Mutual exclusion with busy
waiting, Sleep and wakeup, Semaphores, Mutexes, Monitors, Message passing, Barriers,
Classical IPC Problems - Dining philosophers problem, Readers and writers problem.

Process
A process is basically a program in execution. The execution of a process must progress in a
sequential fashion.
A process is defined as an entity which represents the basic unit of work to be implemented in
the system.

To put it in simple terms, we write our computer programs in a text file and when we execute
this program, it becomes a process which performs all the tasks mentioned in the program.

When a program is loaded into the memory and it becomes a process, it can be divided into
four sections ─ stack, heap, text and data. The following image shows a simplified layout of a
process inside main memory −
Stack
The process Stack contains the temporary data such as method/function parameters, return
address and local variables.

Heap
This is dynamically allocated memory to a process during its run time.

Text
This includes the current activity represented by the value of Program Counter and the
contents of the processor's registers.

Data
This section contains the global and static variables.
Program
A program is a piece of code which may be a single line or millions of lines. A computer
program is usually written by a computer programmer in a programming language. A computer
program is a collection of instructions that performs a specific task when executed by a computer.
When we compare a program with a process, we can conclude that a process is a dynamic instance of
a computer program.

Process Life Cycle

When a process executes, it passes through different states. These stages may differ in
different operating systems, and the names of these states are also not standardized.

In general, a process can have one of the following five states at a time.

Start
This is the initial state when a process is first started/created.
Ready
The process is waiting to be assigned to a processor. Ready processes are waiting to have the
processor allocated to them by the operating system so that they can run. Process may come into this
state after Start state or while running it by but interrupted by the scheduler to assign CPU to some
other process.
Running
Once the process has been assigned to a processor by the OS scheduler, the process state is
set to running and the processor executes its instructions.
Waiting
Process moves into the waiting state if it needs to wait for a resource, such as waiting for user
input, or waiting for a file to become available.
Terminated or Exit
Once the process finishes its execution, or it is terminated by the operating system, it is
moved to the terminated state where it waits to be removed from main memory.
Process Control Block (PCB)
A Process Control Block is a data structure maintained by the Operating System for every
process. The PCB is identified by an integer process ID (PID). A PCB keeps all the information
needed to keep track of a process as listed below in the table −
The architecture of a PCB is completely dependent on Operating System and may contain
different information in different operating systems. Here is a simplified diagram of a PCB −

Process State
The current state of the process i.e., whether it is ready, running, waiting, or
whatever.

Process privileges
This is required to allow/disallow access to system resources.

Process ID
Unique identification for each of the process in the operating system.

Pointer
A pointer to parent process.

Program Counter
Program Counter is a pointer to the address of the next instruction to be executed for
this process.
CPU registers
Various CPU registers where process need to be stored for execution for running
state.

CPU Scheduling Information

Process priority and other scheduling information which is required to schedule the
process.

Memory management information

This includes the information of page table, memory limits, Segment table depending
on memory used by the operating system.

Accounting information
This includes the amount of CPU used for process execution, time limits, execution
ID etc.

IO status information
This includes a list of I/O devices allocated to the process.
The PCB is maintained for a process throughout its lifetime, and is deleted once the process
terminates.
Operations on processes
There are many operations that can be performed on processes. Some of these are
process creation, process preemption, process blocking, and process termination. These are
given in detail as follows −

Process Creation
Processes need to be created in the system for different operations. This can be done
by the following events −
• User request for process creation
• System initialization
• Execution of a process creation system call by a running process
• Batch job initialization
A process may be created by another process using fork(). The creating process is
called the parent process and the created process is the child process. A child process can
have only one parent but a parent process may have many children. Both the parent and child
processes have the same memory image, open files, and environment strings. However, they
have distinct address spaces.
A diagram that demonstrates process creation using fork() is as follows −
Process Preemption
An interrupt mechanism is used in preemption that suspends the process executing
currently and the next process to execute is determined by the short-term scheduler.
Preemption makes sure that all processes get some CPU time for execution.
A diagram that demonstrates process preemption is as follows −

Process Termination
After the process has completed the execution of its last instruction, it is terminated.
The resources held by a process are released after it is terminated.
A child process can be terminated by its parent process if its task is no longer
relevant. The child process sends its status information to the parent process before it
terminates. Also, when a parent process is terminated, its child processes are terminated as
well as the child processes cannot run if the parent processes are terminated.
 Inter-process communication
Interprocess communication is the mechanism provided by the operating system that
allows processes to communicate with each other. This communication could involve a
process letting another process know that some event has occurred or the transferring of data
from one process to another.
A diagram that illustrates interprocess communication is as follows −

Synchronization in Interprocess Communication

Synchronization is a necessary part of interprocess communication. It is either
provided by the interprocess control mechanism or handled by the communicating processes.
Some of the methods to provide synchronization are as follows –
• Semaphore
A semaphore is a variable that controls the access to a common resource by
multiple processes. The two types of semaphores are binary semaphores and counting
semaphores.
• Mutual Exclusion
Mutual exclusion requires that only one process thread can enter the critical
section at a time. This is useful for synchronization and also prevents race conditions.
• Barrier
A barrier does not allow individual processes to proceed until all the processes
reach it. Many parallel languages and collective routines impose barriers.
• Spinlock
This is a type of lock. The processes trying to acquire this lock wait in a loop
while checking if the lock is available or not. This is known as busy waiting because
the process is not doing any useful operation even though it is active.
 Communication in client server systems.
Client/Server communication involves two components, namely a client and a server.
They are usually multiple clients in communication with a single server. The clients send
requests to the server and the server responds to the client requests.
There are three main methods to client/server communication. These are given as
follows −

Sockets
Sockets facilitate communication between two processes on the same machine or
different machines. They are used in a client/server framework and consist of the IP address
and port number. Many application protocols use sockets for data connection and data
transfer between a client and a server.
Socket communication is quite low-level as sockets only transfer an unstructured byte
stream across processes. The structure on the byte stream is imposed by the client and server
applications.
A diagram that illustrates sockets is as follows −

Remote Procedure Calls

These are interprocess communication techniques that are used for client-server based
applications. A remote procedure call is also known as a subroutine call or a function call.
A client has a request that the RPC translates and sends to the server. This request
may be a procedure or a function call to a remote server. When the server receives the
request, it sends the required response back to the client.
Pipes
These are interprocess communication methods that contain two end points. Data is
entered from one end of the pipe by a process and consumed from the other end by the other
process.
The two different types of pipes are ordinary pipes and named pipes. Ordinary pipes
only allow one way communication. For two way communication, two pipes are required.
Ordinary pipes have a parent child relationship between the processes as the pipes can
only be accessed by processes that created or inherited them.
Named pipes are more powerful than ordinary pipes and allow two way
communication. These pipes exist even after the processes using them have terminated. They
need to be explicitly deleted when not required anymore.
A diagram that demonstrates pipes are given as follows −

Multithreaded Programming
What is Thread?
A thread is a flow of execution through the process code, with its own program
counter that keeps track of which instruction to execute next, system registers which hold its
current working variables, and a stack which contains the execution history.
A thread shares with its peer threads few information like code segment, data
segment and open files. When one thread alters a code segment memory item, all other
threads see that.
A thread is also called a lightweight process. Threads provide a way to improve
application performance through parallelism. Threads represent a software approach to
improving performance of operating system by reducing the overhead thread is equivalent to
a classical process.
Each thread belongs to exactly one process and no thread can exist outside a process.
Each thread represents a separate flow of control. Threads have been successfully used in
implementing network servers and web server. They also provide a suitable foundation for
parallel execution of applications on shared memory multiprocessors. The following figure
shows the working of a single-threaded and a multithreaded process.
Difference between Process and Thread
S.No 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, All threads can share same set of open files,
each process executes the same code but child processes.
has 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.

Advantages of Threads
• 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.
Types of Thread
Threads are implemented in following two ways −
• User Level Threads − User managed threads.
• Kernel Level Threads − Operating System managed threads acting on kernel, an
operating system core.
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.

Multithreading Models
Some operating system provide a combined user level thread and Kernel level thread
facility. Solaris is a good example of this combined approach. In a combined system,
multiple threads within the same application can run in parallel on multiple processors and a
blocking system call need not block the entire process. Multithreading models are three
types
• Many to many relationship.
• Many to one relationship.
• One to one relationship.

Many to Many Model

The many-to-many model multiplexes any number of user threads onto an equal or
smaller number of kernel threads.
The following diagram shows the many-to-many threading model where 6 user level
threads are multiplexing with 6 kernel level threads. In this model, developers can create as
many user threads as necessary and the corresponding Kernel threads can run in parallel on a
multiprocessor machine. This model provides the best accuracy on concurrency and when a
thread performs a blocking system call, the kernel can schedule another thread for execution.
Many to One Model
Many-to-one model maps many user level threads to one Kernel-level thread. Thread
management is done in user space by the thread library. When thread makes a blocking
system call, the entire process will be blocked. Only one thread can access the Kernel at a
time, so multiple threads are unable to run in parallel on multiprocessors.
If the user-level thread libraries are implemented in the operating system in such a
way that the system does not support them, then the Kernel threads use the many-to-one
relationship modes.

One to One Model

There is one-to-one relationship of user-level thread to the kernel-level thread. This
model provides more concurrency than the many-to-one model. It also allows another thread
to run when a thread makes a blocking system call. It supports multiple threads to execute in
parallel on microprocessors.
Disadvantage of this model is that creating user thread requires the corresponding
Kernel thread. OS/2, windows NT and windows 2000 use one to one relationship model.
S.No. User-Level Threads Kernel-Level Thread
1 User-level threads are faster to create Kernel-level threads are slower to create and
and manage. manage.
2 Implementation is by a thread library Operating system supports creation of Kernel
at the user level. threads.
3 User-level thread is generic and can Kernel-level thread is specific to the
run on any operating system. operating system.
4 Multi-threaded applications cannot Kernel routines themselves can be
take advantage of multiprocessing. multithreaded.

Process Scheduling
Basic concepts
Definition
The process scheduling is the activity of the process manager that handles the
removal of the running process from the CPU and the selection of another process on the
basis of a particular strategy.
Process scheduling is an essential part of a Multiprogramming operating systems.
Such operating systems allow more than one process to be loaded into the executable
memory at a time and the loaded process shares the CPU using time multiplexing.
Process Scheduling Queues
The OS maintains all PCBs in Process Scheduling Queues. The OS maintains a
separate queue for each of the process states and PCBs of all processes in the same
execution state are placed in the same queue. When the state of a process is changed, its
PCB is unlinked from its current queue and moved to its new state queue.
The Operating System maintains the following important process scheduling queues −
• Job queue − This queue keeps all the processes in the system.
• Ready queue − This queue keeps a set of all processes residing in main memory,
ready and waiting to execute. A new process is always put in this queue.
• Device queues − The processes which are blocked due to unavailability of an I/O
device constitute this queue.
 The OS can use different policies to manage each queue (FIFO, Round Robin,
Priority, etc.). The OS scheduler determines how to move processes between the ready and
run queues which can only have one entry per processor core on the system; in the above
diagram, it has been merged with the CPU.
Two-State Process Model
Two-state process model refers to running and non-running states which are
described below −
S.No State & Description
1
Running
When a new process is created, it enters into the system as in the running state.
2
Not Running
Processes that are not running are kept in queue, waiting for their turn to
execute. Each entry in the queue is a pointer to a particular process. Queue is
implemented by using linked list. Use of dispatcher is as follows. When a
process is interrupted, that process is transferred in the waiting queue. If the
process has completed or aborted, the process is discarded. In either case, the
dispatcher then selects a process from the queue to execute.

Types of Schedulers
Schedulers are special system software which handle process scheduling in various
ways. Their main task is to select the jobs to be submitted into the system and to decide
which process to run. Schedulers are of three types −
• Long-Term Scheduler
• Short-Term Scheduler
• Medium-Term Scheduler
Long Term Scheduler
It is also called a job scheduler. A long-term scheduler determines which programs
are admitted to the system for processing. It selects processes from the queue and loads them
into memory for execution. Process loads into the memory for CPU scheduling.
The primary objective of the job scheduler is to provide a balanced mix of jobs, such
as I/O bound and processor bound. It also controls the degree of multiprogramming. If the
degree of multiprogramming is stable, then the average rate of process creation must be
equal to the average departure rate of processes leaving the system.
On some systems, the long-term scheduler may not be available or minimal. Time-
sharing operating systems have no long term scheduler. When a process changes the state
from new to ready, then there is use of long-term scheduler.

Short Term Scheduler

It is also called as CPU scheduler. Its main objective is to increase system
performance in accordance with the chosen set of criteria. It is the change of ready state to
running state of the process. CPU scheduler selects a process among the processes that are
ready to execute and allocates CPU to one of them.
Short-term schedulers, also known as dispatchers, make the decision of which
process to execute next. Short-term schedulers are faster than long-term schedulers.
Medium Term Scheduler
Medium-term scheduling is a part of swapping. It removes the processes from the
memory. It reduces the degree of multiprogramming. The medium-term scheduler is in-
charge of handling the swapped out-processes.
A running process may become suspended if it makes an I/O request. A suspended
processes cannot make any progress towards completion. In this condition, to remove the
process from memory and make space for other processes, the suspended process is moved
to the secondary storage. This process is called swapping, and the process is said to be
swapped out or rolled out. Swapping may be necessary to improve the process mix.
Comparison among Scheduler
S.No Long-Term Scheduler Short-Term Scheduler Medium-Term
Scheduler
1 It is a job scheduler It is a CPU scheduler It is a process swapping
scheduler.
2 Speed is lesser than short Speed is fastest among other Speed is in between both
term scheduler two short and long term
scheduler.
3 It controls the degree of It provides lesser control over It reduces the degree of
multiprogramming degree of multiprogramming multiprogramming.
4 It is almost absent or It is also minimal in time It is a part of Time sharing
minimal in time sharing sharing system systems.
system
5 It selects processes from It selects those processes It can re-introduce the
pool and loads them into which are ready to execute process into memory and
memory for execution execution can be
continued.
 CPU Scheduling Criteria
Different CPU scheduling algorithms have different properties and the choice of a particular
algorithm depends on the various factors. Many criteria have been suggested for comparing CPU
scheduling algorithms.
The criteria include the following:
• CPU utilisation –
The main objective of any CPU scheduling algorithm is to keep the CPU as busy as possible.
Theoretically, CPU utilisation can range from 0 to 100 but in a real-time system, it varies from 40
to 90 percent depending on the load upon the system.

• Throughput –
A measure of the work done by CPU is the number of processes being executed and
completed per unit time. This is called throughput. The throughput may vary depending upon the
length or duration of processes.

• Turnaround time –
For a particular process, an important criteria is how long it takes to execute that process. The
time elapsed from the time of submission of a process to the time of completion is known as the
turnaround time. Turn-around time is the sum of times spent waiting to get into memory, waiting
in ready queue, executing in CPU, and waiting for I/O.

• Waiting time –
A scheduling algorithm does not affect the time required to complete the process once it starts
execution. It only affects the waiting time of a process i.e. time spent by a process waiting in the
ready queue.

• Response time –
In an interactive system, turn-around time is not the best criteria. A process may produce
some output fairly early and continue computing new results while previous results are being
output to the user. Thus another criteria is the time taken from submission of the process of
request until the first response is produced. This measure is called response time.

Scheduling algorithms
A Process Scheduler schedules different processes to be assigned to the CPU based on
particular scheduling algorithms. There are six popular process scheduling algorithms
There are various CPU Scheduling algorithms such as-
• First Come First Served (FCFS)
• Shortest Job First (SJF)
• Longest Job First (LJF)
• Priority Scheduling
• Round Robin (RR)
• Shortest Remaining Time First (SRTF)
• Longest Remaining Time First (LRTF)
First Come First Serve (FCFS)
• Jobs are executed on first come, first serve basis.
• It is a non-preemptive, pre-emptive scheduling algorithm.
• Easy to understand and implement.
• Its implementation is based on FIFO queue.

• Poor in performance as average

wait time is high.

Wait time of each process is as follows −

Process Wait Time : Service Time - Arrival Time
P0 0-0=0
P1 5-1=4
P2 8-2=6
P3 16 - 3 = 13
Average Wait Time: (0+4+6+13) / 4 = 5.75

Shortest Job Next (SJN)

• This is also known as shortest job first, or SJF
• This is a non-preemptive, pre-emptive scheduling algorithm.
• Best approach to minimize waiting time.
• Easy to implement in Batch systems where required CPU time is known in advance.
• Impossible to implement in interactive systems where required CPU time is not
known.
• The processer should know in advance how much time process will take.
Given: Table of processes, and their Arrival time, Execution time
Process Arrival Time Execution Time Service Time
P0 0 5 0
P1 1 3 5
P2 2 8 14
P3 3 6 8

Waiting time of each process is as follows −

Process Waiting Time
P0 0-0=0
P1 5-1=4
P2 14 - 2 = 12
P3 8-3=5
Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Priority Based Scheduling

• Priority scheduling is a non-preemptive algorithm and one of the most common
scheduling algorithms in batch systems.
• Each process is assigned a priority. Process with highest priority is to be executed
first and so on.
• Processes with same priority are executed on first come first served basis.
• Priority can be decided based on memory requirements, time requirements or any
other resource requirement.

Given: Table of processes, and their Arrival time, Execution time, and priority. Here we are
considering 1 is the lowest priority.
Process Arrival Time Execution Time Priority Service Time
P0 0 5 1 0
P1 1 3 2 11
P2 2 8 1 14
P3 3 6 3 5
Waiting time of each process is as follows −
Process Waiting Time
P0 0-0=0
P1 11 - 1 = 10
P2 14 - 2 = 12
P3 5-3=2
Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

Shortest Remaining Time

• Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.
• The processor is allocated to the job closest to completion but it can be preempted by
a newer ready job with shorter time to completion.
• Impossible to implement in interactive systems where required CPU time is not
known.
• It is often used in batch environments where short jobs need to give preference.

Round Robin Scheduling

• Round Robin is the preemptive process scheduling algorithm.
• Each process is provided a fix time to execute, it is called a quantum.
• Once a process is executed for a given time period, it is preempted and other process
executes for a given time period.
• Context switching is used to save states of preempted processes.
Wait time of each process is as follows −
Process Wait Time : Service Time - Arrival Time
P0 (0 - 0) + (12 - 3) = 9
P1 (3 - 1) = 2
P2 (6 - 2) + (14 - 9) + (20 - 17) = 12
P3 (9 - 3) + (17 - 12) = 11
Average Wait Time: (9+2+12+11) / 4 = 8.5

Multiple-Level Queues Scheduling

Multiple-level queues are not an independent scheduling algorithm. They make use of other
existing algorithms to group and schedule jobs with common characteristics.
• Multiple queues are maintained for processes with common characteristics.
• Each queue can have its own scheduling algorithms.
• Priorities are assigned to each queue.
For example, CPU-bound jobs can be scheduled in one queue and all I/O-bound jobs
in another queue. The Process Scheduler then alternately selects jobs from each queue and
assigns them to the CPU based on the algorithm assigned to the queue.

Multiprocessor Scheduling:
Multiple processor scheduling or multiprocessor scheduling focuses on
designing the system's scheduling function, which consists of more than one processor.
Multiple CPUs share the load (load sharing) in multiprocessor scheduling so that various
processes run simultaneously. In general, multiprocessor scheduling is complex as compared
to single processor scheduling. In the multiprocessor scheduling, there are many processors,
and they are identical, and we can run any process at any time.
The multiple CPUs in the system are in close communication, which shares a
common bus, memory, and other peripheral devices. So we can say that the system is tightly
coupled. These systems are used when we want to process a bulk amount of data, and these
systems are mainly used in satellite, weather forecasting, etc.
There are cases when the processors are identical, i.e., homogenous, in terms of their
functionality in multiple-processor scheduling. We can use any processor available to run any
process in the queue.
Multiprocessor systems may be heterogeneous (different kinds of CPUs)
or homogenous (the same CPU). There may be special scheduling constraints, such as
devices connected via a private bus to only one CPU.
 There is no policy or rule which can be declared as the best scheduling solution to a
system with a single processor. Similarly, there is no best scheduling solution for a system
with multiple processors as well.

Approaches to Multiple Processor Scheduling

There are two approaches to multiple processor scheduling in the operating system:
Symmetric Multiprocessing and Asymmetric Multiprocessing.

• Symmetric Multiprocessing: It is used where each processor is self-scheduling. All

processes may be in a common ready queue, or each processor may have its private
queue for ready processes. The scheduling proceeds further by having the scheduler
for each processor examine the ready queue and select a process to execute.

• Asymmetric Multiprocessing: It is used when all the scheduling decisions and I/O
processing are handled by a single processor called the Master Server. The other
processors execute only the user code. This is simple and reduces the need for data
sharing, and this entire scenario is called Asymmetric Multiprocessing.

Thread Scheduling
As mentioned briefly in the previous section, many computer configurations have a single
CPU. Hence, threads run one at a time in such a way as to provide an illusion of concurrency.
Execution of multiple threads on a single CPU in some order is called scheduling. The Java runtime
environment supports a very simple, deterministic scheduling algorithm called fixed-priority
scheduling. This algorithm schedules threads on the basis of their priority relative to other Runnable
threads.

When a thread is created, it inherits its priority from the thread that created it. You also can
modify a thread's priority at any time after its creation by using the setPriority method. Thread
priorities are integers ranging between MIN_PRIORITY and MAX_PRIORITY (constants defined in
the Thread class). The higher the integer, the higher the priority. At any given time, when multiple
threads are ready to be executed, the runtime system chooses for execution the Runnable thread that
has the highest priority. Only when that thread stops, yields, or becomes Not Runnable will a lower-
priority thread start executing. If two threads of the same priority are waiting for the CPU, the
scheduler arbitrarily chooses one of them to run. The chosen thread runs until one of the following
conditions is true:
 • A higher priority thread becomes runnable.
• It yields, or its run method exits.
• On systems that support time-slicing, its time allotment has expired.
Then the second thread is given a chance to run, and so on, until the interpreter exits.
The Java runtime system's thread scheduling algorithm is also preemptive. If at any time a
thread with a higher priority than all other Runnable threads becomes Runnable, the runtime system
chooses the new higher-priority thread for execution. The new thread is said to preempt the other
threads.
Inter-process Communication:
"Inter-process communication is used for exchanging useful information between numerous
threads in one or more processes (or programs)."
• Race conditions: A race condition is an undesirable situation that occurs when a device or
system attempts to perform two or more operations at the same time, but because of the nature
of the device or system, the operations must be done in the proper sequence to be done
correctly.
A race condition is an undesirable situation that occurs when a device or system
attempts to perform two or more operations at the same time, but because of the nature of the
device or system, the operations must be done in the proper sequence to be done correctly.
In computer memory or storage, a race condition may occur if commands to read and
write a large amount of data are received at almost the same instant, and the machine attempts
to overwrite some or all of the old data while that old data is still being read. The result may
be one or more of the following:
• The computer crashes or identifies an illegal operation of the program
• Errors reading the old data
• Errors writing the new data

A race condition can also occur if instructions are processed in the incorrect order.
There are a few types of race conditions. Two categories that define the impact of the race condition
on a system are referred to as critical and noncritical:
• A critical race condition will cause the end state of the device, system or program to change. For
example, if flipping two light switches connected to a common light at the same time blows the
circuit, it is considered a critical race condition. In software, a critical race condition is when a
situation results in a bug with unpredictable or undefined behavior.
• A noncritical race condition does not directly affect the end state of the system, device or
program. In the light example, if the light is off and flipping both switches simultaneously turns
the light on and has the same effect as flipping one switch, then it is a noncritical race condition.
In software, a noncritical race condition does not result in a bug.

Critical and noncritical race conditions aren't limited to electronics or programming. They can
occur in many types of systems where race conditions happen.

How do you prevent race conditions?

Two ways programmers can prevent race conditions in operating systems and other software include:
• Avoid shared states. This means reviewing code to ensure when shared resources are part of a
system or process, atomic operations are in place that run independently of other processes and
locking is used to enforce the atomic operation of critical sections of code. Immutable objects can
also be used that cannot be altered once created.
• Use thread synchronization. Here, a given part of the program can only execute one thread at a
time.
 CRITICAL REGIONS:
When more than one processes access a same code segment that segment is known as
critical section. Critical section contains shared variables or resources which are needed to
be synchronized to maintain consistency of data variable.
Critical Section is the part of a program which tries to access shared resources.
That resource may be any resource in a computer like a memory location, Data
structure, CPU or any IO device.
The critical section cannot be executed by more than one process at the same
time; operating system faces the difficulties in allowing and disallowing the processes
from entering the critical section.
The critical section problem is used to design a set of protocols which can
ensure that the Race condition among the processes will never arise.
In order to synchronize the cooperative processes, our main task is to solve the
critical section problem. We need to provide a solution in such a way that the
following conditions can be satisfied.

Requirements of Synchronization mechanisms

Primary
• Mutual Exclusion
Our solution must provide mutual exclusion. By Mutual Exclusion, we mean that if
one process is executing inside critical section then the other process must not enter in
the critical section.
• Progress
Progress means that if one process doesn't need to execute into critical section then it
should not stop other processes to get into the critical section.

Secondary
• Bounded Waiting
We should be able to predict the waiting time for every process to get into the critical
section. The process must not be endlessly waiting for getting into the critical section.
• Architectural Neutrality
Our mechanism must be architectural natural. It means that if our solution is working
fine on one architecture then it should also run on the other ones as well.

Sleep and Wake up:

Assume that we have two system calls as sleep and wake. The process which calls
sleep will get blocked while the process which calls will get waked up.
There is a popular example called producer consumer problem which is the most
popular problem simulating sleep and wake mechanism.
The concept of sleep and wake is very simple. If the critical section is not empty then
the process will go and sleep. It will be waked up by the other process which is currently
executing inside the critical section so that the process can get inside the critical section.
In producer consumer problem, let us say there are two processes, one process writes
something while the other process reads that. The process which is writing something is
called producer while the process which is reading is called consumer.
 The producer produces the item and inserts it into the buffer. The value of the global
variable count got increased at each insertion. If the buffer is filled completely and no slot is
available then the producer will sleep, otherwise it keep inserting.
On the consumer's end, the value of count got decreased by 1 at each consumption. If
the buffer is empty at any point of time then the consumer will sleep otherwise, it keeps
consuming the items and decreasing the value of count by 1.
The consumer will be waked up by the producer if there is at least 1 item available in
the buffer which is to be consumed. The producer will be waked up by the consumer if there
is at least one slot available in the buffer so that the producer can write that.
Well, the problem arises in the case when the consumer got preempted just before it
was about to sleep. Now the consumer is neither sleeping nor consuming. Since the producer
is not aware of the fact that consumer is not actually sleeping therefore it keep waking the
consumer while the consumer is not responding since it is not sleeping.
This leads to the wastage of system calls. When the consumer get scheduled again, it
will sleep because it was about to sleep when it was preempted.
The producer keep writing in the buffer and it got filled after some time. The producer
will also sleep at that time keeping in the mind that the consumer will wake him up
when there is a slot available in the buffer.
The consumer is also sleeping and not aware with the fact that the producer will wake him
up.
Using a flag bit to get rid of this problem
A flag bit can be used in order to get rid of this problem. The producer can set the bit
when it calls wake-up on the first time. When the consumer got scheduled, it checks the bit.
The consumer will now get to know that the producer tried to wake him and therefore
it will not sleep and get into the ready state to consume whatever produced by the producer.
This solution works for only one pair of producer and consumer, what if there are n
producers and n consumers. In that case, there is a need to maintain an integer which can
record how many wake-up calls have been made and how many consumers need not sleep.
This integer variable is called semaphore. We will discuss more about semaphore later in
detail.

Semaphores:
Semaphores are integer variables that are used to solve the critical section problem by
using two atomic operations, wait and signal that are used for process synchronization. The
definitions of wait and signal are as follows − Wait. The wait operation decrements the value of its
argument S, if it is positive.

To avoid a series of issues caused by multiple processes (or programs) accessing a

shared resource at the same time, we need a method that can be authorised by generating and
using a token, so that only one execution thread can access the critical section of the code at
any given time. The critical section is a code segment where the shared variables can be
accessed and the atomic action is required in this section.

A semaphore is a signaling mechanism, and a thread that is waiting on a semaphore

can be signaled by another thread. It uses two atomic operations, 1)wait, and 2) signal for the
process synchronization.
 A semaphore either allows or disallows access to the resource, which depends on how
it is set up.

Semaphore was proposed by Dijkstra in 1965 which is a very significant technique to

manage concurrent processes by using a simple integer value, which is known as a
semaphore. Semaphore is simply an integer variable that is shared between threads. This
variable is used to solve the critical section problem and to achieve process synchronization
in the multiprocessing environment.

Here, are characteristic of a semaphore:

It is a mechanism that can be used to provide synchronization of tasks.

It is a low-level synchronization mechanism.

Semaphore will always hold a non-negative integer value.

Semaphore can be implemented using test operations and interrupts, which should be
executed using file descriptors.

Semaphores are of two types:

Binary Semaphore –

This is also known as mutex lock. It can have only two values – 0 and 1. Its value is
initialized to 1. It is used to implement the solution of critical section problems with multiple
processes.

The binary semaphores are quite similar to counting semaphores, but their value is
restricted to 0 and 1. In this type of semaphore, the wait operation works only if semaphore =
1, and the signal operation succeeds when semaphore= 0. It is easy to implement than
counting semaphores.

Counting Semaphore –

Its value can range over an unrestricted domain. It is used to control access to a
resource that has multiple instances.

This type of Semaphore uses a count that helps task to be acquired or released
numerous times. If the initial count = 0, the counting semaphore should be created in the
unavailable state.

However, If the count is > 0, the semaphore is created in the available state, and the
number of tokens it has equals to its count.
Wait and Signal Operations in Semaphores

Both of these operations are used to implement process synchronization. The goal of this semaphore
operation is to get mutual exclusion.

Wait for Operation

This type of semaphore operation helps you to control the entry of a task into the critical section.
However, If the value of wait is positive, then the value of the wait argument X is decremented. In the
case of negative or zero value, no operation is executed. It is also called P(S) operation.

After the semaphore value is decreased, which becomes negative, the command is held up until the
required conditions are satisfied.

Signal operation

This type of Semaphore operation is used to control the exit of a task from a critical section. It helps
to increase the value of the argument by 1, which is denoted as V(S).

Advantages of Semaphores

Here, are pros/benefits of using Semaphore:

It allows more than one thread to access the critical section

Semaphores are machine-independent.

Semaphores are implemented in the machine-independent code of the microkernel.

They do not allow multiple processes to enter the critical section.

As there is busy waiting in semaphore, there is never a wastage of process time and resources.

They are machine-independent, which should be run in the machine-independent code of the
microkernel.

They allow flexible management of resources.

Disadvantage of semaphores

Here, are cons/drawback of semaphore

One of the biggest limitations of a semaphore is priority inversion.

The operating system has to keep track of all calls to wait and signal semaphore.

Their use is never enforced, but it is by convention only.

In order to avoid deadlocks in semaphore, the Wait and Signal operations require to be executed in the
correct order.
Semaphore programming is a complicated, so there are chances of not achieving mutual exclusion.

It is also not a practical method for large scale use as their use leads to loss of modularity.

Semaphore is more prone to programmer error.

It may cause deadlock or violation of mutual exclusion due to programmer error.

Summary:

Semaphore is defined as a variable that is non-negative and shared between threads.

It is a mechanism that can be used to provide synchronization of tasks.

Counting semaphore uses a count that helps task to be acquired or released numerous times.

The binary semaphores are quite similar to counting semaphores, but their value is restricted to 0 and
1.

Wait operation helps you to control the entry of a task into the critical section

Signal semaphore operation is used to control the exit of a task from a critical section

Counting Semaphore has no mutual exclusion whereas Binary Semaphore has Mutual exclusion

Semaphore means a signaling mechanism whereas Mutex is a locking mechanism

Semaphore allows more than one thread to access the critical section

One of the biggest limitations of a semaphore is priority inversion.

Mutexes:Strictly speaking, a mutex is a locking mechanism used to synchronize access to a

resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It
means there is ownership associated with a mutex, and only the owner can release the lock (mutex).

Mutex is a mutual exclusion object that synchronizes access to a resource. It is created with a unique
name at the start of a program. The Mutex is a locking mechanism that makes sure only one thread
can acquire the Mutex at a time and enter the critical section. This thread only releases the Mutex
when it exits the critical section.

Mutex is also known as the object of mutual exclusion. Mutex is a mechanism that locks a specified
thread for a specified time. It enables only one thread to acquire it for a limited time. This specific
time is called a critical section.

The developers use mutex inside the threads to avoid any drastic outcome of inefficient resource
utilization, whether it is a variable, a function, an array, or a file. All the mutex objects have a unique
name given to them since the beginning of the program.
This is shown with the help of the following example −

wait (mutex);

…..

Critical Section

…..

signal (mutex);

A Mutex is different than a semaphore as it is a locking mechanism while a semaphore is a

signalling mechanism. A binary semaphore can be used as a Mutex but a Mutex can never be used as
a semaphore.

Mutex is locking mechanism in OS

difference between mutex and semaphore:-

1. Mutex is used for thread but semaphore is used for process.

2.mutex is work in userspace but semaphore is work in kernal space.

3.mutex is locking mechanism ownership mathead but seamphore is signalling mechanism/didn't

ownership.

4.thread to thread mutex is used but process to process locking mechanism semaphore is used.

Monitors: The monitor is one of the ways to achieve Process synchronization. The monitor is
supported by programming languages to achieve mutual exclusion between processes. For example
Java Synchronized methods. Java provides wait() and notify() constructs.

1. It is the collection of condition variables and procedures combined together in a special kind of
module or a package.
2. The processes running outside the monitor can’t access the internal variable of the monitor but can
call procedures of the monitor.
3. Only one process at a time can execute code inside monitors.

Condition Variables:

Two different operations are performed on the condition variables of the monitor.

Wait.

signal.

let say we have 2 condition variables

condition x, y; // Declaring variable

Wait operation

x.wait() : Process performing wait operation on any condition variable are suspended. The suspended
processes are placed in block queue of that condition variable.

Signal operation

x.signal(): When a process performs signal operation on condition variable, one of the blocked
processes is given chance.

Advantages of Monitor:

Monitors have the advantage of making parallel programming easier and less error prone than using
techniques such as semaphore.

Disadvantages of Monitor:

Monitors have to be implemented as part of the programming language . The compiler must generate
code for them. This gives the compiler the additional burden of having to know what operating system
facilities are available to control access to critical sections in concurrent processes. Some languages
that do support monitors are Java, C#, Visual Basic, Ada and concurrent Euclid.

Message passing: In computer science, message passing is a technique for invoking behavior
(i.e., running a program) on a computer. The invoking program sends a message to a process (which
may be an actor or object) and relies on that process and its supporting infrastructure to then select
and run some appropriate code.

Process communication is the mechanism provided by the operating system that allows
processes to communicate with each other. This communication could involve a process letting
another process know that some event has occurred or transferring of data from one process to
another. One of the models of process communication is the message passing model.

Message passing model allows multiple processes to read and write data to the message queue
without being connected to each other. Messages are stored on the queue until their recipient retrieves
them. Message queues are quite useful for interprocess communication and are used by most
operating systems.

1. In message-passing systems, processors communicate with one another by sending and receiving
messages over a communication channel. So how the arrangement should be done?

2. The pattern of the connection provided by the channel is described by some topology systems.

3. The collection of the channels are called a network.

4. So by the definition of distributed systems, we know that they are geographically set of computers.
So it is not possible for one computer to directly connect with some other node.

5. So all channels in the Message-Passing Model are private.

6. The sender decides what data has to be sent over the network. An example is, making a phone call.

7. The data is only fully communicated after the destination worker decides to receive the data.
Example when another person receives your call and starts to reply to you.

8. There is no time barrier. It is in the hand of a receiver after how many rings he receives your call.
He can make you wait forever by not picking up the call.

9. For successful network communication, it needs active participation from both sides.

Algorithm:

1. Let us consider a network consisting of n nodes named p0, p1, p2……..pn-1 which are bidirectional
point to point channels.

2. Each node might not know who is at another end. So in this way, the topology would be arranged.

3. Whenever the communication is established and whenever the message passing is started then only
the processes know from where to where the message has to be sent.

Advantages of Message Passing Model :

1. Easier to implement.

2. Quite tolerant of high communication latencies.

3. Easier to build massively parallel hardware.

4. It is more tolerant of higher communication latencies.

5. Message passing libraries are faster and give high performance.

Disadvantages of Message Passing Model :

1. Programmer has to do everything.

2. Connection setup takes time that’s why it is slower.

3. Data transfer usually requires cooperative operations which can be difficult to achieve.

4. It is difficult for programmers to develop portable applications using this model because message-
passing implementations commonly comprise a library of subroutines that are embedded in source
code. Here again, the programmer has to do everything on his own.

Barriers: In parallel computing, a barrier is a type of synchronization method. A barrier for a

group of threads or processes in the source code means any thread/process must stop at this point and
cannot proceed until all other threads/processes reach this barrier.

In parallel computing, a barrier is a type of synchronization method. A barrier for a group of

threads or processes in the source code means any thread/process must stop at this point and cannot
proceed until all other threads/processes reach this barrier.
Many collective routines and directive-based parallel languages impose implicit barriers. For
example, a parallel do loop in Fortran with OpenMP will not be allowed to continue on any thread
until the last iteration is completed. This is in case the program relies on the result of the loop
immediately after its completion. In message passing, any global communication (such as reduction or
scatter) may imply a barrier.
1. Dynamic barriers
Classic barrier constructs define the set of participating processes/threads statically. This is
usually done either at program startup or when a barrier like the Pthreads barrier is instantiated. This
restricts the possible applications for which barriers can be used.
To support more dynamic programming paradigms like fork/join parallelism, the sets of
participants have to be dynamic. Thus, the set of processes/threads participating in a barrier operation
needs to be able to change over time. X10* introduced the concept of clocks for that purpose, which
provide a dynamic barrier semantic. Building on clocks, phasers have been proposed to add even
more flexibility to barrier synchronization. With phasers it is possible to express data dependencies
between the participating processes explicitly to avoid unnecessary over-synchronization.

2. Processor and compiler barriers

Memory barrier is a class of instructions which cause a processor to enforce an ordering
constraint on memory operations issued before and after the barrier instruction.
A barrier can also be a high-level programming language statement which prevents the
compiler from reordering other operations over the barrier statement during optimization passes. Such
statements can potentially generate processor barrier instructions. Different classes of barrier exist and
may apply to a specific set of operations only.

Classical IPC Problems –

Dining philosophers problem: The dining philosopher's problem is the classical

problem of synchronization which says that Five philosophers are sitting around a circular
table and their job is to think and eat alternatively. A bowl of noodles is placed at the center
of the table along with five chopsticks for each of the philosophers. To eat a philosopher
needs both their right and a left chopstick. A philosopher can only eat if both immediate left
and right chopsticks of the philosopher is available. In case if both immediate left and right
chopsticks of the philosopher are not available then the philosopher puts down their (either
left or right) chopstick and starts thinking again.

The dining philosopher demonstrates a large class of concurrency control problems hence it's
a classic synchronization problem.

do {
wait( chopstick[i] );
wait( chopstick[ (i+1) % 5] );
..
. EATING THE RICE
.
signal( chopstick[i] );
signal( chopstick[ (i+1) % 5] );
.
. THINKING
 .
} while(1);
The design of the problem was to illustrate the challenges of avoiding deadlock, a
deadlock state of a system is a state in which no progress of system is possible. Consider a
proposal where each philosopher is instructed to behave as follows:
o The philosopher is instructed to think till the left fork is available, when it is available,
hold it.
o The philosopher is instructed to think till the right fork is available, when it is
available, hold it.
o The philosopher is instructed to eat when both forks are available.
o then, put the right fork down first
o then, put the left fork down next
o repeat from the beginning.

Readers and writers problem: The readers-writers problem is a classical problem of

process synchronization, it relates to a data set such as a file that is shared between more than
one process at a time. Among these various processes, some are Readers - which can only
read the data set; they do not perform any updates, some are Writers - can both read and write
in the data sets.

The readers-writers problem is used for managing synchronization among various

reader and writer process so that there are no problems with the data sets, i.e. no
inconsistency is generated.

Let's understand with an example - If two or more than two readers want to access the
file at the same point in time there will be no problem. However, in other situations like when
two writers or one reader and one writer wants to access the file at the same point of time,
there may occur some problems, hence the task is to design the code in such a manner that if
one reader is reading then no writer is allowed to update at the same point of time, similarly,
if one writer is writing no reader is allowed to read the file at that point of time and if one
writer is updating a file other writers should not be allowed to update the file at the same
point of time. However, multiple readers can access the object at the same time.

The solution of readers and writers can be implemented using binary semaphores.
We use two binary semaphores "write" and "mutex", where binary semaphore can be defined
as:
Semaphore: A semaphore is an integer variable in S, that apart from initialization is
accessed by only two standard atomic operations - wait and signal, whose definitions are as
follows:
1. 1. wait( S )
2. {
3. while( S <= 0) ;
4. S--;
5. }
6.
7. 2. signal( S )
8. {
9. S++;
10. }

1. static int readcount = 0;

2. wait (mutex);
3. readcount ++; // on each entry of reader increment readcount
4. if (readcount == 1)
5. {
6. wait (write);
7. }
8. signal(mutex);
9.
10. --READ THE FILE?
11.
12. wait(mutex);
13. readcount --; // on every exit of reader decrement readcount
14. if (readcount == 0)
15. {
16. signal (write);
17. }
18. signal(mutex);

while(TRUE)
{
//acquire lock
wait(m);
read_count++;
if(read_count == 1)
wait(w);

//release lock
signal(m);

/* perform the reading operation */

// acquire lock
wait(m);
read_count--;
if(read_count == 0)
signal(w);