Module II CPU Scheduling and Process Synchronization 9

Process: Process Concept-Process Scheduling-Process Synchronization: The critical section

problem -Peterson’s Solution – CPU Scheduling: Scheduling criteria – Scheduling algorithms:
FCFS, SJF, Priority, Round Robin- Semaphores – Classic problems of synchronization.

Self Study Topics - Monitors.

Process Concept

Explain the process state diagram.(4) Explain long term, medium term and short
term scheduling(6) (or) What is meant by a process? Explain states of process with
neat sketch and discuss process state transition and process control block(16) (May
2006, 07, 09, 10, Nov 2006,08,10,12)
Process Concept
A Process is a program in execution. A Process contains program code, which is
sometimes known as text section. It also includes program counter, contents of
processor’s registers, process stack and a data section.
A program is a passive entity such as the contents of a file stored on disk. A
process is an active entity with a program counter and a set of resources.
1.1 Process State Transition
The state of a process is defined by the current activity of that process.

Fig: Diagram of Process State

New: The process is being created.
Running: Instructions are being executed.
Waiting: The process is waiting for some event to occur
Ready: The process is waiting to be assigned to a processor.
Terminated: The process has finished execution.
1.2 Process Control Block
All information about a process is maintained in Process Table or Process Control
Block(PCB)
Each process is represented in the operating System by a Process Control Block
(PCB).
 Fig: Process Control Block
Process State:
The state may be new, ready, running, waiting, halted etc.
Program Counter:
The counter indicates the address of the next instruction to be executed.
CPU Registers:
It includes accumulators, index registers, stack pointers, general purpose registers
and condition code information.
CPU Scheduling Information:
It includes a process priority, pointers to scheduling queues and other scheduling
parameters.
Memory Management Information:
It includes the value of the base and limit registers, the page tables or segment
tables.

Fig: CPU switch from process to process

Accounting Information:
This includes the amount of CPU and time limits, account numbers, job or process
numbers
I/O Status information:
This includes the list of I/O devices allocated, a list of open files etc.
1.3 Threads
Thread is a flow of control within a process.
Single thread allows the process to perform only one task at a time. Eg: While
typing characters in the MS WORD, it is not possible to check the spelling
simultaneously.
A process has multiple threads which perform more than one task at a time, it is
called multithreading.
1.4 Process Scheduling
The objective of multiprogramming is to have some process running at all times,
so as to maximize CPU utilization.
A uniprocessor system can have only one running process. If more processes
exist, the rest must wait until the CPU is free and can be rescheduled.
1) Scheduling Queues
As processes enter the system, they are put into a job queue. The processes that
are residing in main memory and are ready and waiting to execute are kept on
a ready queue.
A Ready Queue header contains a pointer to the first and final PCBs in the
list.
Each PCB contains a pointer field that points to the next PCB in the ready
queue.
The list of processes waiting for the particular I/O device is called a device
queue. Each device has its own device queue.

Fig: Ready Queue and I/O Device Queues

A common representation of process scheduling is a queueing diagram. Each
rectangular box represents a queue. Two types of queues are present: the Ready
queue and I/O device queue. The circles represent the resources and the arrows
indicate the flow of processes in the system.
 Fig: Queueing diagram representation of process scheduling
2) Schedulers
The operating system must select processes from various scheduling queues. The
selection process is carried out by the scheduler.
Schedulers are of three types
a) Long term scheduler
b) Short term scheduler
c) Medium term scheduler
a) Long term scheduler
It is also called job scheduler.
Long term scheduler selects processes from job pool and loads them into
memory.
The long term scheduler executes much less frequently.
b) Short term scheduler
It is also called CPU scheduler.
The short term scheduler selects processes from main memory that are
ready to execute and allocates the CPU to one of them.
The short term scheduler must select a new process for the CPU
frequently
c) Medium term scheduler
Medium term scheduler performs swapping process.
The medium term scheduler, removes processes from memory thus
reduces the degree of multiprogramming.
At some later time, the process can be reintroduced into memory and its
execution can be continued where it left off. This scheme is called
swapping.
 Fig: Medium Term Scheduler
3) Context switch
Switching the CPU to another process requires saving the state of the old
process and loading the saved state for the new process. This task is known as
a context switch.
The context of a process is represented in the PCB of a process. It includes the
value of the CPU registers, the process state and memory management
information.
Context switch time is pure overhead because the system does no useful work while
switching.
A Context Switch simply requires changing the pointer to the current register
set.
Explain the process creation and process termination on process(8) (May 2008, Nov 2008)
1.5 OPERATIONS ON PROCESSES
1) Process Creation
A process may create several new processes using create process system call.
The creating process is called a parent process whereas the new processes are
called the children.
Each new process may in turn create other processes, forming a tree of
processes.

Fig: A tree of processes in a UNIX system.

A process will need certain resources to accomplish its task.
When a process creates a sub process, that sub process obtain its resources
directly from the operating system or it use the parent resources.
When a process is created, it obtains initialization data (or input) from the parent
process.
In UNIX, each process is identified by its process identifier (pid) which is a unique
integer.
A new process is created by the fork system call i.e.) The parent creates a child
process using fork( ).
The child process consists of a copy of address space of the parent process.
The fork system call returns zero (value of pid) for the child (new) process and
process id of the child (non zero) for the parent process.
The execlp system call is used by the child process to replace its address space
with the UNIX command /bin/ls.
The parent waits for the child process to complete with the wait system call.
 When the child process completes, the parent process terminates using the exit system
call.
#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
#include<stdlib.h>
main( )
{
pid_t pid;
pid=getpid();
printf("Before fork process id is %d\n",getpid());
pid=fork();
if(pid==0)
{
printf("Child process id is %d\n",getpid());
execl("/bin/ls","ls",NULL);
}
else if(pid>0)
wait(NULL);
else
{
printf("Fork failed\n");
exit(-1);
}
}
Fig: C Program forking a separate process
2) Process Termination
A process terminates when it finishes executing using the exit system call.
The process may return data (output) to its parent process through wait system
call.
All process resources including physical and virtual memory, open files, I/O buffers
are deallocated by OS.
The parent process that is to be terminated can terminate another process using
abort system call. So the parent must know the identities of its children for
termination.
A parent may terminate the execution of its children for various reasons
1) The child has exceeded its usage of some of the resources that has been
allocated.
2) The task assigned to the child is no longer required.
3) If a parent terminates, then all of its children must also be terminated. This
phenomenon is referred to as cascading termination.

PROCESS SYNCHRONIZATION
A cooperating process is one that can affect or be affected by other processes
executing in the system. Cooperating processes may either directly share a logical
address space(code and data) or be allowed to share data only through files.
 Concurrent access to shared data may result in data consistency.
A situation where several processes access and manipulate the same data
concurrently and the outcome of the execution depends on the particular order in
which the access takes place, is called a race condition. To guard against race
condition, we need to ensure that only one process at a time can be manipulating.
i.e) there must be synchronization and coordination between processes.
What is critical section? Specify the requirements for a solution to the critical
section problem. (8) (Nov 2006,2008,2010,2012, May 2006,2007,2008,2009,2010)

[Link] SECTION PROBLEM

Consider a system consisting of n processes {P0, P1,……,Pn-1}. Each process has
a segment of code, called critical section, in which process may change common
variables, updating a table, writing a file.
When one process is executing in its critical section, no other process is to be
allowed to execute in its critical section i.e) mutually exclusive.
The critical section problem is to design a protocol that the processes can use to
cooperate.
Each process can request permission to enter its critical section. The section of
code implementing this request is the entry section. The critical section may be
followed by an exit section. The remaining code is the remainder section.

Fig: General structure of a typical process Pi

A solution to the critical section problem must satisfy the following three
requirements
1. Mutual Exclusion. If process Pi is executing in its critical section, then no
other processes can be executing in their critical sections.
2. 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 section can participate in the decision
on which will enter the critical section next, and this selection cannot be
postponed indefinitely.
3. Bounded Waiting. There exists a bound on the number of times that other
processes are allowed to enter their critical sections after a process has made
a request to enter its critical section and before that request is granted.
Two Process Solutions
 Algorithms are applicable to only two processes at a time. The processes are
numbered P0 to P1
When presenting Pi , we use Pj to denote the other process; that is j=1-i.
Algorithm 1
The processes share a common integer variable turn initialized to 0(or 1). If
turn==i, process Pi is allowed to execute in its critical section.

Fig: The structure of process Pi in algorithm 1

Algorithm 1 satisfies mutual exclusion. However it does not satisfy the progress
requirement.
Algorithm 2
In algorithm 2, the variable turn can be replaced with the array boolean flag[2] to
indicate the state of each process. The elements of the array are initialized to false.
If flag[i] is true, Pi is ready to enter the critical section.

Fig: The structure of process Pi in algorithm 2

Algorithm 2 satisfies mutual exclusion. However it does not satisfy the progress
requirement.
Algorithm 3
In algorithm 3, the processes share two variables:
boolean flag[2];
int turn;
Initially flag[0]=flag[1]=false; and the value of turn is either 0 or 1.
 Fig: The structure of process Pi in algorithm 2
Algorithm 3 satisfies mutual exclusion, progress and bounded waiting
requirement.
Multiple Process Solutions
Bakery algorithm is used for solving the critical section problem for n processes.
If Pi and Pi receive same number and if i < j then Pi is served first. i.e) process with
lowest name is served first
The common variables used are boolean choosing[n]; and int number[n];
Initially, these variables are initialized to false and 0.

Fig: The structure of process Pi in bakery algorithm

Bakery algorithm satisfies mutual exclusion, progress and bounded waiting
requirement.
CPU SCHEDULING
CPU scheduling is the task of selecting a waiting process from the ready queue
and allocating the CPU to it. CPU scheduling is the basis of multiprogrammed
operating systems.
The main objective of scheduling is to increase CPU utilization and throughput.
3.1. Basic Concepts
The objective of multiprogramming is to have some process running at all times,
in order to maximize CPU utilization.
A uniprocessor system can have only one running process. If more processes
exist, the rest must wait until the CPU is free and can be rescheduled.
 In a multiprogrammed system, several processes are kept in memory at one
time. The OS picks up and executes one of the jobs in main memory. When that
job needs to wait, the CPU is switched to another job. The first job finishes
waiting and gets the CPU back.
3.2. CPU – I/O Burst Cycle
Process execution consists of a cycle of CPU execution(CPU burst) and I/O
wait(I/O burst).
An I/O bound process spends more of its time doing I/O than it spends doing
computation. A CPU bound process spends more of its time doing computation
than an I/O bound process.
An I/O bound process would have many very short CPU bursts. A CPU bound
process might have a few very long CPU bursts.

Fig: Alternating sequence of CPU and I/O bursts

3.3. CPU Scheduler
The operating system must select one of the processes in the ready queue to be
executed. The selection process is carried out by the short term scheduler (or
CPU scheduler).
The short term scheduler selects processes from main memory that are ready to
execute and allocates the CPU to one of them.
3.4. Preemptive Scheduling
CPU scheduling decisions may take place under the following four circumstances:
1. When a process switches from running state to waiting state.
(nonpreemptive)
2. When a process switches from running state to ready state. (preemptive)
3. When a process switches from waiting state to ready state. (preemptive)
4. When a process terminates. (nonpreemptive)
A preemptive scheduling algorithm will preempt the currently executing
processes, whereas a nonpreemptive scheduling algorithm will allow the currently
running process to finish its work.
3.5. Dispatcher
The process of assigning the CPU to a process is called dispatching.
 The time it takes for the dispatcher to stop one process and start another running is known
as dispatch latency.
The dispatcher is the function that is responsible for assigning the CPU to the
process that has been selected by the short term scheduler. This function involves:
1. Switching context.
2. Switching to user mode.
3. Jumping to the proper location in the user program to restart that
program.
Explain the various scheduling criteria in evaluating scheduling algorithms.(4)
(Nov 2012)
Describe the following scheduling algorithms (16) (May 2008)
i. Shortest Job First scheduling
ii. Round Robin scheduling
iii. Real time scheduling
iv. Priority scheduling
Explain the various process scheduling algorithms with examples (16) (May 11,Nov 09,11)
CPU SCHEDULING
CPU scheduling is the task of selecting a waiting process from the ready queue
and allocating the CPU to it. CPU scheduling is the basis of multi programmed
operating systems.
The main objective of scheduling is to increase CPU utilization and throughput.
SCHEDULING CRITERIA
Many criteria have been used for comparing CPU scheduling algorithms.
1. CPU utilization: It is defined as the average fraction of time during which
CPU is busy.
CPU utilization may range from 0 to 100 percent. CPU utilization must be
high.
2. Throughput: It is defined as the average amount of work completed per unit
time. For long
processes, throughput - 1 process/hour; For short processes, throughput - 10
processes/second.
3. Turnaround time: The interval from the time of submission of a process to
the time of completion
4. Waiting time: It is defined as the sum of the periods spent waiting in the
ready queue.
5. Response time: The interval from the time of submission of a process until
the first response is produced. i.e) the amount of time it takes to start
responding.
SCHEDULING ALGORITHMS
CPU scheduling is the process of deciding which of the processes in the ready
queue is to be allocated the CPU. The various CPU scheduling algorithms are
1. First-Come, First-Served Scheduling.
2. Shortest-Job-First Scheduling.
 3. Priority Scheduling.
4. Round-Robin Scheduling.
5. Multilevel Queue Scheduling.
6. Multilevel Feedback Queue Scheduling.
1. First-Come, First-Served Scheduling(FCFS)
It is the simplest CPU scheduling algorithm.
In FCFS, the process that requests the CPU first is allocated the CPU first.
The FCFS policy is easily managed with a FIFO queue.
The FCFS scheduling algorithm is nonpreemptive. Once the CPU has been
allocated to a process, that process keeps the CPU until it terminates.
If many processes are waiting for the one big process to get off the CPU, it is
known as convoy effect. This effect results in lower CPU and device utilization.
The average waiting time under the FCFS policy is often quite long.
The FCFS algorithm is not suitable for time sharing systems, but it is suitable for
batch systems.
Example:
Process Burst Time
P1 24
P2 3
P3 3

P1 P2 P3
0 24 27 30
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17
Suppose that the processes arrive in the order:
P2 , P3 , P1
➢ The Gantt chart for the schedule is:

P2 P3 P1
0 3 6 30
➢ Waiting time for P1 = 6; P2 = 0; P3 = 3
➢ Average waiting time: (6 + 0 + 3)/3 = 3
➢ Much better than previous case
➢ Convoy effect - short process behind long process
Consider one CPU-bound and many I/O-bound processes

2. Shortest-Job-First Scheduling(SJF) or Shortest-Next-CPU burst Scheduling

SJF algorithm allocates the CPU to the process that has the smallest CPU burst
time.
If two processes have the same CPU burst time then FCFS algorithm is used.
 SJF scheduling algorithm may be either preemptive or non preemptive.
A preemptive SJF algorithm will preempt the currently executing processes,
whereas a nonpreemptive SJF algorithm will allow the currently running process
to finish its work.
Preemptive SJF scheduling is sometimes called shortest-remaining-time-first
scheduling.
SJF scheduling algorithm is optimal since it gives the minimum average waiting
time.
The real difficulty with the SJF algorithm is knowing the length of the next CPU
burst time.
The exponential average formula is

Τn+1=αtn+(1-α)Τn
Example:
Process Arrival Time Burst Time
P1 0.0 6
P2 2.0 8
P3 4.0 7
P4 5.0 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24
Average waiting time = (3 + 16 + 9 + 0) / 4 = 7

Example of Shortest-remaining-time-first
Now add the concepts of varying arrival times and preemption to the analysis
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

Average waiting time = [(10-1)+(1-1)+(17-2)+5-3)]/4 = 26/4 = 6.5 msec

3. Priority Scheduling
 A priority is associated with each process, and the CPU is allocated to the process
with the highest priority. Equal priority processes are scheduled in FCFS order.
Priority scheduling can be either preemptive or nonpreemptive.
A preemptive priority scheduling algorithm will preempt the CPU if the priority
of the newly arrived process is higher the priority of the currently running
process. A nonpreemptive priority scheduling algorithm will simply put the new
process at the head of the ready queue.
A major problem with priority scheduling algorithm is indefinite blocking (or
starvation). A priority scheduling algorithm can leave some low priority
processes waiting indefinitely for the CPU.
A solution to the indefinite blocking or starvation problem is aging. Aging is a
technique of gradually increasing the priority of processes that wait in the system
for a long time.
Example:
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

Average waiting time = 8.2 msec

4. Round-Robin Scheduling
It is similar to FCFS scheduling, but preemption is added to switch between
processes. A small unit of time, called a time quantum is defined. A time quantum
is generally from 10 to 100 milliseconds
The RR scheduling algorithm is preemptive. If a process CPU burst exceeds the
given time quantum, that process is preempted and is put back in the ready queue.
If the process CPU burst is lesser than the given time quantum the process itself
will release the CPU voluntarily.
The RR policy is easily managed with a FIFO queue. The average waiting time
under RR policy is often quite long. The round robin algorithm is designed
especially for time sharing systems.
Example : Time Quantum = 4
Process Burst Time
P1 24
P2 3
 P3 3
The Gantt chart is:

P1 P2 P3 P1 P1 P1 P1 P1

➢ 0 4 7 10 14 18 22 26 30
Typically, higher average turnaround than SJF, but better response
➢ q should be large compared to context switch time
➢ q usually 10ms to 100ms, context switch < 10 usec
Time Quantum and Context Switch Time

Priority Scheduling with Round-Robin

Process Burst Time Priority
P1 4 3
P2 5 2
P3 8 2
P4 7 1
P5 3 3
Run the process with the highest priority. Processes with the same priority run round-robin
Gantt Chart wit 2 ms time quantum

5. Multilevel Queue Scheduling

When processes can be easily classified into different groups then multilevel
queue scheduling is applied. For example: foreground (or interactive) processes
and background (or batch) processes.
 A multilevel queue scheduling algorithm partitions the ready queue into several
separate queues. The processes are permanently assigned to one queue.
Each queue has its own scheduling algorithm. For example: foreground queue
follows RR algorithm and background queue follows FCFS algorithm.

6. Multilevel Feedback Queue Scheduling

Multilevel Feedback Queue Scheduling allows a process to move between
queues.
If a process uses too much CPU time, it will be moved to a lower priority queue.
i.e) I/O bound
processes stay in the higher priority queues and CPU bound processes stay in the lower
priority queues.
Similarly, a process that waits too long in a lower priority queue may be moved to
a higher
priority queue. This form of aging prevents starvation.

Fig: Multilevel Feedback Queue Scheduling

************************************************************************
******************
Multiple Processor scheduling
CPU scheduling is more complex when multiple CPU’s are available.
In a homogeneous system, where the processors are identical, any available
processor can be used to run any processes in the queue.
In a heterogeneous system, where the processors are different, only programs
compiled for a given processor’s instruction set could be run on that processor.
If several identical processors are available, then load sharing can occur. With a
separate queue for each processor, there could be a situation where one processor
could be idle, with an empty queue, while another processor was very busy. To
 prevent this situation, we use a common ready queue. All processes go into one
queue and are allocated onto any available processor.
Two scheduling approaches may be used:
1. Symmetric multiprocessing
2. Asymmetric multiprocessing
Real-Time scheduling
Real-time system is divided into two types: 1. Hard real-time system 2. Soft
real-time system
Hard real-time systems are required to complete a critical task within a guaranteed
amount of time. The scheduler admits the process, guaranteeing that the process
will complete on time, or rejects the request as impossible. This is known as
resource reservation.
Soft real-time system is less restrictive. A critical real time task gets priority
over other tasks, and retains that priority until it completes.
If a higher priority process is waiting for a lower priority process to finish, it is
known as priority inversion. This problem can be solved using the priority
inversion protocol.
The conflict phase of dispatch latency has two components
1. Preemption of any process running in the kernel.
2. Release by low priority processes resources needed by the high priority
process.

Fig: Dispatch Latency

Algorithm Evaluation
To select an algorithm, we must first define the criteria. Our criteria include
several measures such as
1. Maximize CPU utilization under the constraint the maximum response time is
1 second.
2. Maximize throughput such that turnaround time is linearly proportional to
total execution time.
Once the selection criteria have been defined, it can be evaluated using various
methods.
[Link] Modeling
 This method takes a particular predetermined workload and defines the
performance of the algorithm for that workload.
For example, assume that all five processes arrive at time 0, in the order given,
with the CPU burst time given in milliseconds.
Process Burst Time
P1 10
P2 29
P3 3
P4 7
P5 12
We can apply FCFS, SJF and RR(q=2) scheduling algorithms and find out the
average waiting time for all algorithms. Since SJF gives the minimum average
waiting time, it is the best algorithm.
2. Queueing Models
It is an area of study that can be useful in comparing scheduling algorithms.
Knowing arrival time and burst time, we can compute CPU utilization, average
queue length and average wait time.
Little’s formula can be defined as
N = λ*W
where N – Average Queue Length
λ – Average arrival time in the Queue
W – Waiting time of the process.
Using little’s formula we can compute one of the three variables, if we know the
other two.
3. Simulations
More accurate results or evaluations of scheduling algorithms can be done with
simulations. Simulation involves programming a model of the computer system.
Software data structures represent the major components of the system. When the
simulation executes, statistics that indicate algorithm performance are gathered.
 Fig: Evaluation of CPU schedulers by simulation
Write about semaphores in detail.(16) (May 2011,Nov 2007)
What do you mean by busy waiting? What other kinds of waiting are there? Can
busy waiting be avoided altogether? Explain your answer.(8) (May 2009,2010,2012)
Explain the structure of a semaphore, wait and signal to overcome busy
waiting.(8) (May 06)
What is synchronization? Explain how semaphores can be used to deal with n-process
critical section problem.(8) (May 2010)
SEMAPHORES
Semaphore is a synchronization tool used to solve more complex critical section
problems.
A semaphore S is an integer variable that is accessed only through two atomic
operations:
P (wait) and V(signal).
The wait and signal operations must be executed indivisibly i.e) when one process
modifies the semaphore value, no other process can simultaneously modify that
same semaphore value.
wait(S)
{
while(S<=0)
;
S--;
}
Fig: Definition of wait operation
signal(S)
{
S++;
}
Fig: Definition of signal operation
Usage
 Semaphores can also be used to solve the n-process critical section problem. The
n processes share a semaphore mutex, initialized to 1

Fig: Mutual-exclusion implementation with TestAndSet instruction

Implementation
While a process is in its critical section, any other process that tries to enter its
critical section must loop continuously in the entry code. It is known as busy
waiting. Busy waiting wastes CPU cycles and it is a problem in a
multiprogramming system.
The semaphore that is used to handle busy waiting problem is called as a
spinlock. The advantage of a spinlock is that no context switch is required when a
process is wait on a lock.
Each semaphore has an integer value and a list of processes.
struct semaphore
{
int value;
struct process *L;
}
Fig: Definition of Semaphore
When a process must wait on a semaphore, it is added to the list of processes.
The block operation suspends the process that invokes it.
A signal operation removes one process from the list of waiting processes and
awakens that process. The wakeup(P) operation resumes the execution of a
blocked process P.

If the semaphore value is negative, its magnitude is number of processes waiting

on semaphore.
Deadlocks and starvation
 When two or more processes are waiting definitely for an event that can be caused
only by one of the waiting processes, these processes are said to be deadlocked.
When many processes are waiting indefinitely within the semaphore, it is known
as indefinite blocking or starvation.
Binary Semaphores
A binary semaphore is a semaphore with an integer value that can range only
between 0 and 1.
A counting semaphore value can range over an unrestricted domain.
The common data structures are binary-semaphore S1,S2; and int C;
Initially S1=1, S2=0 and C=initial value of counting semaphore.

Explain Readers and Writers problem and present its solution using semaphores.(8)
(May 12)
Write short notes on readers-writers problem and dining-philosophers problem (8)
(May11)
Discuss critical section problem, solving the dining philosophers problem using
semaphores.(16) (Nov 06)
State the dining philosophers problem and show how to allocate the several
resources among several processes in a deadlock and starvation free manner. (16)
(May 2008)
CLASSIC PROBLEMS OF SYNCHRONIZATION
The different synchronization problems are
1. The Bounded-Buffer Problem
2. The Readers-Writers Problem
3. The Dining-Philosophers Problem.
1. The Bounded-Buffer Problem
Assume a pool consists of n buffers, each capable of holding one item. The mutex
semaphore provides mutual exclusion for access to the buffer pool and is
initialized to the value 1.
 The empty and full semaphores count the number of empty and full buffers. The
semaphore empty is initialized to the value n; the semaphore full is initialized to
the value 0.

Fig: The structure of the producer process Fig: The structure of the
consumer process
2. The Readers-Writers Problem
Process reader reads the content of the shared object. Process writer updatesthe
shared object.
If a writer and some other processes access the shared object simultaneously,
chaos may occur. For this, we require that the writers have exclusive access to the
shared object. This synchronization problem is known as readers-writers
problem.
The first readers-writers problem requires that no reader should wait for other
readers to finish simply because a writer is waiting.
The reader process share the following data structures:
semaphore mutex,wrt;
int readcount;
Initially mutex=wrt=1 and readcount=0
 Fig: The structure of the reader process

Fig: The structure of the writer process

3. The Dining-Philosophers Problem
Consider five philosophers who spend their lives thinking and eating. A
philosopher may pick up only one chopstick at a time. When a hungry
philosopher has both her chopsticks at the same time, she eats without releasing
her chopsticks. This is known as dining-philosophers problem.

One simple solution is to represent chopstick by a semaphore. A philosopher tries

to grab the chopstick by executing a wait operation on that semaphore. She
releases her chopsticks by executing the signal operation on that semaphore.
The shared data is semaphore chopstick[5]; where all the elements are initialized
to 1.
Fig: The structure of Philosopher i.