Process

• In general, a process is a program in execution.

• A program is not inherently a process. A program is a passive entity, meaning it is a file
containing a list of instructions stored on disk (secondary memory) and is often referred to
as an executable file.
• A program becomes a process when the executable file is loaded into main memory, and its
Process Control Block (PCB) is created.
• Conversely, a process is an active entity that requires resources like main memory, CPU time,
registers, system buses, etc. Even if two processes are associated with the same program,
they are considered separate execution sequences and are entirely different processes.
For instance, if a user has multiple copies of a web browser program running, each copy will
be treated as a separate process. Although the text section is the same, the data, heap,
and stack sections can vary.
• A Process consists of following sections:
• Text section: also known as Program Code.

• Stack: which contains the temporary data (Function

Parameters, return addresses and local variables).

• Data Section: Containing global variables.

• Heap: which is memory dynamically allocated during process

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

• PCB simply serves as the repository for any information that may vary from
process to process. It contains many pieces of information associated with a
specific process, including these:
• Process state: The state may be new, ready, running, waiting, halted, and so
on.

• Program counter: The counter indicates the address of the next instruction
to be executed for this process.

• CPU registers: The registers vary in number and type, depending on the
computer architecture. They include accumulators, index registers, stack
pointers, and general-purpose registers, plus any condition-code information.
Along with the program counter, this state information must be saved when
an interrupt occurs, to allow the process to be continued correctly afterward.
• CPU-scheduling information: This information includes a
process priority, pointers to scheduling queues, and any
other scheduling parameters.

• Memory-management information: This information may

include such items as the value of the base and limit
registers and the page tables, or the segment tables,
depending on the memory system used by the operating
system.

• Accounting information: This information includes the

amount of CPU and real time used, time limits, account
numbers, job or process numbers, and so on.

• I/O status information: This information includes the list

of I/O devices allocated to the process, a list of open files,
and so on.
 Process States
• A Process changes states as it executes. The state of a process is defined in parts by the
current activity of that process. A process may be in one of the following states:
• New: The process is being created.

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

• Running: Instructions are being executed.

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

• Terminated: The process has finished execution.

• Job Queue: Contains all processes in the
system. It is the initial queue where processes
are placed as they enter the system.

• Ready Queue: Holds processes that are in

main memory and ready to execute. This
queue is typically implemented as a linked list,
with a ready-queue header containing
pointers to the first and last process control
blocks (PCBs) in the list. Each PCB has a
pointer to the next PCB in the ready queue.

• Device Queues: These are used when

processes require I/O operations and the
requested I/O device is busy. Each device (like
a disk) has its own queue holding processes
that are waiting for it to become available.
• Each rectangular box 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. A new process is initially
put in the ready queue. It waits there until it is selected for execution, or dispatched.
• 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 child process and wait for the child’s termination.
• Time slice expired, 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.
 Schedulers
• Schedulers: A process migrates among the various scheduling queues throughout its lifetime. The operating
system must select, for scheduling purposes, processes from these queues in some fashion. The selection process
is carried out by the appropriate scheduler.

• Types of Schedulers
• Long Term Schedulers (LTS)/Spooler: In multiprogramming os, more processes are submitted than can be
executed immediately. These processes are spooled to a mass-storage device (typically a disk), where they
are kept for later execution. The long-term scheduler, or job scheduler, selects processes from this pool and
loads them into memory for execution.

• Short Term Scheduler (STS): The short-term scheduler, or CPU scheduler, selects from among the processes
that are ready to execute and allocates the CPU to one of them.
• Difference between LTS and STS - The primary distinction between these two schedulers lies
in frequency of execution.

• The short-term scheduler must select a new process for the CPU frequently. A process may
execute for only a few milliseconds before waiting for an I/O request. Often, the short-term
scheduler executes at least once every 100 milliseconds.

• Because of the short time between executions, the short-term scheduler must be fast. The
long-term scheduler on the other hand executes much less frequently; minutes may separate
the creation of one new process and the next.
Degree of Multiprogramming - The number of processes in memory is known as Degree of
Multiprogramming.
• The long-term scheduler controls the degree of multiprogramming as it is responsible for
bringing in the processes to main memory. 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. So, this means the long-term scheduler may need to be
invoked only when a process leaves the system. Because of the longer interval between
executions, the long-term scheduler can afford to take more time to decide which process
should be selected for execution.
Medium-term scheduler: The key idea behind a medium-term scheduler is that sometimes it
can be advantageous to remove a process from memory (and from active contention for the
CPU) and thus reduce the degree of multiprogramming.
Later, the process can be reintroduced into memory, and its execution can be continued where it
left off. This scheme is called swapping.
The process is swapped out, and is later swapped in, by the medium-term scheduler. Swapping
may be necessary to improve the process mix or because a change in memory requirements has
overcommitted available memory, requiring memory to be freed up.
• Dispatcher - The dispatcher is the module that gives control of the CPU to the process
selected by the short-term scheduler.
• This function involves the following: Switching context, switching to user mode, 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 is known as
the dispatch latency.
 CPU Bound and I/O Bound Processes
• A process execution consists of a cycle of CPU execution or wait and i/o execution or
wait. Normally a process alternates between two states.

• Process execution begin with the CPU burst that may be followed by a i/o burst, then
another CPU and i/o burst and so on. Eventually in the last will end up on CPU burst. So,
process keep switching between the CPU and i/o during execution.
• I/O Bound Processes: An I/O-bound process is one that spends more of its time doing I/O than
it spends doing computations.

• CPU Bound Processes: A CPU-bound process, generates I/O requests infrequently, using more
of its time doing computations.

• It is important that the long-term scheduler select a good process mix of I/O-bound and CPU-
bound processes. If all processes are I/O bound, the ready queue will almost always be empty,
and the short-term scheduler will have little to do.

• Similarly, if all processes are CPU bound, the I/O waiting queue will almost always be empty,
devices will go unused, and again the system will be unbalanced. So, to have the best system
performance LTS needs to select a good combination of I/O and CPU Bound processes.
 Context Switch
• When an interrupt occurs, the system needs to save
the current context of the process running on the CPU
so that it can restore that context when its processing
is done.
• Switching the CPU to another process requires
performing a state save of the current process and a
state restore of a different process. This task is known
as a context switch. When a context switch occurs, the
kernel saves the context of the old process in its PCB
and loads the saved context of the new process
scheduled to run. Context-switch time is pure
overhead, because the system does no useful work
while switching.

• Switching speed varies from machine to machine,

depending on the memory speed, the number of
registers that must be copied, and the existence of
special instructions (such as a single instruction to
load or store all registers). A typical speed is a few
milliseconds.
 Type of scheduling
• Non-Pre-emptive: Under Non-Pre-emptive scheduling, once the CPU has been allocated to a
process, the process keeps the CPU until it releases the CPU willingly.

• A process will leave the CPU only

1. When a process completes its execution (Termination state)
2. When a process wants to perform some i/o operations(Blocked state)
 Pre-emptive

• Under Pre-emptive scheduling, once the CPU has been allocated to a process, A process will
leave the CPU willingly or it can be forced out. So it will leave the CPU
1. When a process completes its execution
2. When a process leaves CPU voluntarily to perform some i/o operations
3. If a new process enters in the ready states (new, waiting), in case of high priority
4. When process switches from running to ready state because of time quantum expire.
• Scheduling criteria - Different CPU-scheduling algorithms have different
properties, and the choice of a particular algorithm may favour one class of
processes over another. So, in order to efficiently select the scheduling
algorithms following criteria should be taken into consideration:
• CPU utilization: Keeping the CPU as busy as possible.
• 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.
• Waiting time: Waiting time is the sum of the periods spent waiting in the ready queue.
• Response Time: Is the time it takes to start responding, not the time it
takes to output the response.
• Note: The CPU-scheduling algorithm does not affect the amount of time during
which a process executes I/0; it affects only the amount of time that a process
spends waiting in the ready queue.

• It is desirable to maximize CPU utilization and throughput and to minimize

turnaround time, waiting time, and response time.
 Terminology

• Arrival Time (AT): Time at which process enters a ready state.

• Burst Time (BT): Amount of CPU time required by the process to finish its execution.

• Completion Time (CT): Time at which process finishes its execution.

• Turn Around Time (TAT): Completion Time (CT) – Arrival Time (AT), Waiting Time + Burst Time (BT)

• Waiting Time: Turn Around Time (TAT) – Burst Time (BT)

 FCFS (FISRT COME FIRST SERVE)
• FCFS is the simplest scheduling algorithm, as the name suggest, the process that requests the
CPU first is allocated the CPU first.

• Implementation is managed by FIFO Queue.

• It is always non pre-emptive in nature.

 P. No Arrival Time Burst Time Completion Time Turn Around Time Waiting Time
(AT) (BT) (CT) (TAT) = CT - AT (WT) = TAT - BT
P0 2 4
P1 1 2
P2 0 3
P3 4 2
P4 3 1
Average
 P. No Arrival Time Burst Time Completion Time Turn Around Time Waiting Time
(AT) (BT) (CT) (TAT) = CT - AT (WT) = TAT - BT
P0 0 3
P1 2 2
P2 6 4
Average
 Advantage
• Easy to understand, and can easily be implemented using Queue data structure.

• Can be used for Background processes where execution is not urgent.

 P. No AT BT TAT=CT-AT WT=TAT -BT

P0 0 100

P1 1 2
Average

P. No AT BT TAT=CT-AT WT=TAT -BT

P0 1 100

P1 0 2
Average
 Convoy Effect

• If the smaller process have to wait more for the CPU because of Larger process then this effect
is called Convoy Effect, it result into more average waiting time.

• Solution, smaller process have to be executed before longer process, to achieve less average
waiting time.
 Disadvantage
• FCFS suffers from convoy which means smaller process have to wait larger
process, which result into large average waiting time.

• The FCFS algorithm is thus particularly troublesome for time-sharing systems (due
to its non-pre-emptive nature), where it is important that each user get a share of
the CPU at regular intervals.

• Higher average waiting time and TAT compared to other algorithms.

 Shortest Job First (SJF)(non-pre-emptive)
Shortest Remaining Time First (SRTF)/ (Shortest Next CPU Burst) (Pre-emptive)

• Whenever we make a decision of selecting the next process for CPU execution,
out of all available process, CPU is assigned to the process having smallest burst
time requirement. When the CPU is available, it is assigned to the process that
has the smallest next CPU burst. If there is a tie, FCFS is used to break tie.
• It supports both version non-pre-emptive and pre-emptive (purely greedy
approach)
• In Shortest Job First (SJF)(non-pre-emptive) once a decision is made and among the available
process, the process with the smallest CPU burst is scheduled on the CPU, it cannot be pre-
empted even if a new process with the smaller CPU burst requirement then the remaining
CPU burst of the running process enter in the system.

• In Shortest Remaining Time First (SRTF) (Pre-emptive) whenever a process enters in ready
state, again we make a scheduling decision weather, this new process with the smaller CPU
burst requirement then the remaining CPU burst of the running process and if it is the case
then the running process is pre-empted and new process is scheduled on the CPU.

• This version (SRTF) is also called optimal is it guarantee minimal average waiting
time.
 P. No Arrival Time Burst Time Completion Time Turn Around Time Waiting Time
(AT) (BT) (CT) (TAT) = CT - AT (WT) = TAT - BT
P0 1 7

P1 2 5

P2 3 1

P3 4 2
P4 5 8
Average
 P. No Arrival Time Burst Time Completion Time Turn Around Time Waiting Time
(AT) (BT) (CT) (TAT) = CT - AT (WT) = TAT - BT
P0 0 6

P1 1 4

P2 2 3

P3 3 1

P4 4 2
P5 5 1
Average
• Advantage
• Pre-emptive version guarantees minimal average waiting time so some time also referred
as optimal algorithm.
• Provide better average response time compare to FCFS
• Disadvantage
• Here process with the longer CPU burst requirement goes into starvation.
• No idea of priority, longer process has poor response time.
 Priority scheduling

Traffic on ROAD
 Priority scheduling
• Here a priority is associated with each process. At any instance of time out of all
available process, CPU is allocated to the process which possess highest priority (may
be higher or lower number).

• Tie is broken using FCFS order. No importance to senior or burst time. It supports both
non-pre-emptive and pre-emptive versions.

• In Priority (non-pre-emptive) once a decision is made and among the available process,
the process with the highest priority is scheduled on the CPU, it cannot be pre-empted
even if a new process with higher priority more than the priority of the running process
enter in the system.
• In Priority (pre-emptive) once a decision is made and among the available process, the
process with the highest priority is scheduled on the CPU.

• if it a new process with priority more than the priority of the running process enter in
the system, then we do a context switch and the processor is provided to the new
process with higher priority.

• Priorities are generally indicated by some fixed range of numbers, such as 0 to 7 or 0 to

4,095. There is no general agreement on whether 0 is the highest or lowest priority, it
can vary from systems to systems.
P. No AT BT Priority CT TAT = CT - AT WT = TAT - BT

P0 1 4 4

P1 2 2 5

P2 2 3 7

P3 3 5 8(H)

P4 3 1 5

P5 4 2 6
Average
 P. No AT BT Priority CT TAT = CT - AT WT = TAT - BT

P0 0 50 4

P1 20 20 1(h)

P2 40 100 3
P3 60 40 2
Average
• Advantage
• Gives a facility specially to system process.
• Allow us to run important process even if it is a user process.

• Disadvantage
• Here process with the smaller priority may starve for the CPU
• No idea of response time or waiting time.

• Note: - Specially use to support system process or important user process

• Ageing: - a technique of gradually increasing the priority of processes that wait in
the system for long time. E.g. priority will increase after every 10 mins
 Round robin
• This algo is designed for time sharing systems, where it is not, necessary to complete one
process and then start another, but to be responsive and divide time of CPU among the
process in the ready state. Here ready queue is treated as a circular queue (FIFO).

• It is similar to FCFS scheduling, but pre-emption is added to enable the system to switch
between processes. 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 equivalent 1
Time quantum (where value of TQ can be anything).
• We fix a time quantum, up to which a process can hold the CPU in one go, with in which either a
process terminates or process must release the CPU and enter the ready queue and wait for the next
chance. The process may have a CPU burst of less than given time quantum. In this case, the process
itself will release the CPU voluntarily.

• CPU Scheduler will select the next process for execution. OR The CPU burst of the currently running
process is longer than 1-time quantum, the timer will go off and will cause an interrupt to the operating
system.

• A context switch will be executed, and the process will be put at the tail of the ready queue. The CPU
scheduler will then select the next process in the ready queue.

• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of
the CPU time in chunks of at most q time units.

• Each process must wait no longer than (n - 1) x q time units until its next time quantum.
 P. No Arrival Time Burst Time Completion Time Turn Around Time Waiting Time (WT)
(AT) (BT) (CT) (TAT) = CT - AT = TAT - BT
P0 0 4
P1 1 5
P2 2 2
P3 3 1
P4 4 6
P5 6 3
Average
 P. No Arrival Time Burst Time Completion Time Turn Around Time Waiting Time (WT)
(AT) (BT) (CT) (TAT) = CT - AT = TAT - BT
P0 5 5
P1 4 6
P2 3 7
P3 1 9
P4 2 2
P5 6 3
Average
• If the time quantum is extremely large, the RR policy is the same as the FCFS policy.
• 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. We also need also to consider the effect of
context switching on the performance of RR scheduling.
• Advantage
• Perform best in terms of average response time
• Works will in case of time-sharing systems, client server architecture and interactive
system
• kind of SJF implementation

• Disadvantage
• Longer process may starve
• Performance depends heavily on time quantum - If value of the time quantum is very less,
then it will give lesser average response time (good but total no of context switches will be
more, so CPU utilization will be less), If time quantum is very large then average response
time will be more bad, but no of context switches will be less, so CPU utilization will be
good.
• No idea of priority
 Process Synchronization
• As we understand in a multiprogramming environment a good number of
processes compete for limited number of resources.

• Concurrent access to shared data at some time may result in data inconsistency
for e.g.

P ()
{
read ( i );
i = i + 1;
write( i );
}
 Race Condition
• The condition in which the output of a process depends on the execution
sequence of process. i.e. if we change the order of execution of different
process with respect to other process the output may change.

• That is why we need some kind of synchronization to eliminate the possibility of

data inconsistency.
 P()
General Structure of a process {
While(T)
• Initial Section: Where process is accessing private {
resources. Initial Section
Entry Section
• Entry Section: Entry Section is that part of code where, Critical Section
each process request for permission to enter its critical Exit Section
section. Remainder Section
}
• Critical Section: Where process is access shared }
resources.

• Exit Section: It is the section where a process will exit

from its critical section.

• Remainder Section: Remaining Code.

 Criterion to Solve Critical Section Problem
• Mutual Exclusion: No two processes should be present inside the critical section
at the same time, i.e. only one process is allowed in the critical section at an
instant of time.
• Progress: If no process is executing in its critical section and some processes wish
to enter their critical sections, then only those processes that are not executing
in their remainder sections can participate in deciding which will enter its critical
section next(means other process will participate which actually wish to enter).
there should be no deadlock.

• Bounded Waiting: There exists a bound or a limit on the number of times a

process is allowed to enter its critical section and no process should wait
indefinitely to enter the CS.
 Some Points to Remember
• Mutual Exclusion and Progress are mandatory requirements that needs to be
followed in order to write a valid solution for critical section problem.
• Bounded waiting is optional criteria, if not satisfied then it may lead to
starvation.
 Solutions to Critical Section Problem
We generally have the following solutions to a Critical Section Problems:
1. Two Process Solution
1. Using Boolean variable turn
2. Using Boolean array flag
3. Peterson’s Solution

2. Operating System Solution

1. Counting Semaphore
2. Binary Semaphore

3. Hardware Solution
1. Test and Set Lock
2. Disable interrupt
 Two Process Solution
• In general it will be difficult to write a valid solution in the first go to solve critical
section problem among multiple processes, so it will be better to first attempt
two process solution and then generalize it to N-Process solution.

• There are 3 Different idea to achieve valid solution, in which some are invalid
while some are valid.

• 1- Using Boolean variable turn

• 2- Using Boolean array flag

• 3- Peterson’s Solution
• Here we will use a Boolean variable turn, which is initialize randomly(0/1).

P0 P1
while (1) while (1)
{ {
while (turn! = 0); while (turn! = 1);
Critical Section Critical Section
turn = 1; turn = 0;
Remainder section Remainder Section
} }
• The solution follows Mutual Exclusion as the two processes cannot
enter the CS at the same time.

• The solution does not follow the Progress, as it is suffering from the
strict alternation. Because we never asked the process whether it
wants to enter the CS or not?
• Here we will use a Boolean array flag with two cells, where each cell is initialized to F

P0 P1
while (1) while (1)
{ {
flag [0] = T; flag [1] = T;
while (flag [1]); while (flag [0]);
Critical Section Critical Section
flag [0] = F; flag [1] = F;
Remainder section Remainder Section
} }
• This solution follows the Mutual Exclusion Criteria.

• But in order to achieve the progress the system ended up

being in a deadlock state.
• Peterson's solution is a classic Software-based solution to the critical-section problem for two
process. This solution ensures Mutual Exclusion, Progress and Bounded Wait.

P0 both: turn and Boolean flag.

• We will be using P1
while (1) while (1)
{ {
flag [0] = T; flag [1] = T;
turn = 1; turn = 0;
while (turn = = 1 && flag [1] = = T); while (turn = = 0 && flag [0] = =T);
Critical Section Critical Section
flag [0] = F; flag [1] = F;
Remainder section Remainder Section
} }
Critical Section Video
[Link]
 Operation System Solution
• Semaphores are synchronization tools using which we will attempt n-process solution.
• A semaphore S is a simple integer variable that, but apart from initialization it can be accessed only
through two standard atomic operations: wait(S) and signal(S).
• The wait(S) operation was originally termed as P(S) and signal(S) was originally called V(S).
• The definition of wait () is as follows:

Wait(S) Signal(S)
{
{
while(s<=0);
s++;
s--;
} }
• Peterson’s Solution was confined to just two processes, Pi()
and since in a general system can have n processes, {
Semaphores provides n-processes solution. While(T)
{
Initial Section
• While solving Critical Section Problem only we wait(s)
initialize semaphore S = 1. Critical Section
signal(s)
• Semaphores are going to ensure Mutual Exclusion and Remainder Section
}
Progress but does not ensures bounded waiting. }

Wait(S) Signal(S)
{ {
while(s<=0);
s++;
s--;
} }
Q Using Semaphores ensure that the order of execution of there
concurrent process p1, p2 and p3 must be p2 p3 p1?

P1() P2() P3()

code code code

 Classical Problems on Synchronization
• There are number of actual industrial problem we try to solve in order to
improve our understand of Semaphores and their power of solving problems.

• Here in this section we will discuss a number of problems like

• Producer consumer problem/ Bounder Buffer Problem

• Reader-Writer problem

• Dining Philosopher problem

 Producer-Consumer Problem
• Problem Definition – There are two process Producer and Consumers, producer produces
information and put it into a buffer which have n cell, that is consumed by a consumer.

• Both Producer and Consumer can produce and consume only one article at a time.
 Producer-Consumer Problem needs to sort out three major issues
• A producer needs to check whether the buffer is overflowed or not after producing an item before accessing the
buffer.

• Similarly, a consumer needs to check for an underflow before accessing the buffer and then consume an item.

• Also, the producer and consumer must be synchronized, so that once a producer and consumer it accessing the
buffer the other must wait.
 Solution Using Semaphores
Now to solve the problem we will be using three semaphores:
Semaphore S = 1 // CS
Semaphore E = n // Count Empty cells
Semaphore F = 0 // Count Filled cells
 Producer() Consumer()

Semaphore S =

Semaphore E =

Semaphore F =
Total three resources Producer() Consumer()
are used { {
• semaphore E take while(T) while(T)
count of empty cells
{ {
and over flow
• semaphore F take
count of filled cells
and under flow
• Semaphore S take
care of buffer

} }
} }
Total three resources Producer() Consumer()
are used { {
• semaphore E take while(T) while(T)
count of empty cells
{ {
and over flow
// Produce an item
• semaphore F take
count of filled cells
and under flow // Pick item from buffer
• Semaphore S take // Add item to buffer
care of buffer
Consume item
} }
} }
Total three resources Producer() Consumer()
are used { {
• semaphore E take while(T) while(T)
count of empty cells
{ {
and over flow
// Produce an item
• semaphore F take
count of filled cells wait(S)

and under flow wait(S) // Pick item from buffer

• Semaphore S take // Add item to buffer signal(S)
care of buffer signal(S)
Consume item
} }
} }
Total three resources Producer() Consumer()
are used { {
• semaphore E take while(T) while(T)
count of empty cells
{ {
and over flow
// Produce an item wait(F)//UnderFlow
• semaphore F take
count of filled cells wait(E)//OverFlow wait(S)

and under flow wait(S) // Pick item from buffer

• Semaphore S take // Add item to buffer signal(S)
care of buffer signal(S) signal(E)
signal(F) Consume item
} }
} }
 Reader-Writer Problem

• Suppose that a database is to be shared

among several concurrent processes. Some
of these processes may want only to read the
database (readers), whereas others may
want to update (that is, to read and write)
the database(writers). The former are
referred to as readers and to the latter as
writers.

• If two readers access the shared data

simultaneously, no adverse effects will result.
But, if a writer and some other process
(either a reader or a writer) access the
database simultaneously, chaos may ensue.
• To ensure that these difficulties do not arise, we require that the writers have
exclusive access to the shared database while writing to the database.

• Points that needs to be taken care for generating a Solutions:

• The solution may allow more than one reader at a time, but should not allow
any writer.
• The solution should strictly not allow any reader or writer, while a writer is
performing a write operation.

• Solution using Semaphores

• The reader processes share the following data structures:
• semaphore mutex = 1, wrt =1; // Two semaphores
• int readcount = 0; // Variable
Mutex = Writer() Reader()

Wrt =

Readcount =
 Writ Reader()
Three resources are used
• Semaphore Wrt is
used for
er() Wait(mutex)
synchronization Readcount++
between WW, WR,
RW
• Semaphore reader is
used to synchronize
between RR Wait(wrt) signal(mutex)
• Readcount is simple
int variable which CS //Write CS //Read
keep counts of
number of readers Signal(wrt) Wait(mutex)
Readcount--

signal(mutex)
Three resources are used Writer() Reader()
• Semaphore Wrt is
used for
Wait(mutex)
synchronization Readcount++
between WW, WR,
RW If(readcount ==1)
• Semaphore reader is
used to synchronize wait(wrt) // first
between RR Wait(wrt) signal(mutex)
• Readcount is simple
int variable which CS //Write CS //Read
keep counts of
number of readers Signal(wrt) Wait(mutex)
Readcount--
If(readcount ==0)
signal(wrt) // last
signal(mutex)
 Dining Philosopher Problem
• Scenario Setup: Five philosophers are seated around a circular table,
each with a bowl of rice in the center. The table has five chairs and
five single chopsticks placed between each pair of philosophers.
• Activity Cycle: Philosophers alternate between thinking and eating.
They do not interact with each other while thinking.
• Eating Process:
• A philosopher becomes hungry and attempts to pick up the two
closest chopsticks — one between her and the philosopher on
her left, and one between her and the philosopher on her right.
• Each philosopher can pick up only one chopstick at a time.
• A philosopher cannot pick up a chopstick if it is already being
held by a neighbor.
• Once a philosopher has both chopsticks, she eats without
releasing the chopsticks.
• Post-Eating: After eating, the philosopher puts both chopsticks back
on the table and resumes thinking.
Indian Chopsticks
Solution for Dining Philosophers
Void Philosopher (void)
{
while ( T )
{
Thinking ( ) ;
wait(chopstick [i]);
wait(chopstick([(i+1)%5]);
Eat( );
signal(chopstick [i]);
signal(chopstick([(i+1)%5]);
}
}

• Here we have used an array of semaphores called chopstick[]

• Solution is not valid because there is a possibility of deadlock.
• The proposed solution for deadlock problem is
• Allow at most four philosophers to be sitting simultaneously at the table.
• Allow six chopstick to be used simultaneously at the table.
• Allow a philosopher to pick up her chopsticks only if both chopsticks are available (to do
this, she must pick them up in a critical section).
• One philosopher picks up her right chopstick first
and then left chop stick, i.e. reverse the
sequence of any philosopher.

• Odd philosopher picks up first her left chopstick

and then her right chopstick, whereas an even
philosopher picks up her right chopstick and then
her left chopstick.
 Types of Semaphore
• Binary Semaphores: The value of a binary semaphore can range only between 0 and 1.

• Counting Semaphores: can range over an unrestricted domain Counting semaphore can range
over an unrestricted domain. i.e. -∞ to +∞.

• Counting semaphores can be used to control access to a given resource consisting of a finite
number of instances. The semaphore is initialized to the number of resources available.

• Each process that wishes to use a resource performs a wait() operation on the semaphore
(thereby decrementing the count). When a process releases a resource, it performs a signal()
operation (incrementing the count).

• When the count for the semaphore goes to 0, all resources are being used. After that,
processes that wish to use a resource will block until the count becomes greater than 0.
• Implementation of semaphore This simple implementation of semaphore with this wait(S) and signal(S) function
suffer from busy waiting.
• Modified Wait
• To overcome the need for busy waiting, we can modify the definition of the wait() and signal() operations as
follows: When a process executes the wait() operation and finds that the semaphore value is not >0, it must
wait. However, rather than engaging in busy waiting, the process can block itself. The block operation places
a process into a waiting queue associated with the semaphore, and the state of the process is switched to
the waiting state. Then control is transferred to the CPU scheduler, which selects another process to execute.

wait(semaphore *S)
{
S->value--;
if (S->value < 0)
{
add this process to S->list;
block();
}
}
• Modified Signal
• A process that is blocked, waiting on a semaphore S, should be restarted when some other
process executes a signal() operation. The process is restarted by a wakeup() operation,
which changes the process from the waiting state to the ready state. The process is then
placed in the ready queue. (The CPU may or may not be switched from the running
process to the newly ready process, depending on the CPU-scheduling algorithm.)

Signal(semaphore *S)
{
S->value++;
if (S->value <= 0)
{
remove a process P from S->list;
wakeup(P);
}
}
To implement semaphores under this definition, we define a semaphore as follows:
typedef struct
{
int value;
struct process *list;
} semaphore;

Each semaphore has an integer value and a list of processes list.

• The block() operation suspends the process that invokes it. The wakeup(P) operation resumes
the execution of a blocked process P. These two operations are provided by the operating
system as basic system calls.

• Note that in this implementation, semaphore values may be negative, whereas semaphore
values are never negative under the classical definition of semaphores with busy waiting. If a
semaphore value is negative, its magnitude is the number of processes waiting on that
semaphore. This fact results from switching the order of the decrement and the test in the
implementation of the wait() operation.

• The list of waiting processes can be easily implemented by a link field in each process control
block (PCB). Each semaphore contains an integer value and a pointer to a list of PCBs. One way
to add and remove processes from the list so as to ensure bounded waiting is to use a FIFO
queue, where the semaphore contains both head and tail pointers to the queue.