Process Synchronization
CH 4 Unit II
Process Synchronization is a mechanism in operating systems used to
manage the execution of multiple processes that access shared resources.
Its main purpose is to ensure data consistency, prevent race conditions and
avoid deadlocks in a multi-process environment.
● On the basis of synchronization, processes are categorized as one of the
following two types:
● Independent Process: e execution of one process does not a ect the
execution of other processes.
● Cooperative Process: A process that can a ect or be a ected by other
processes executing in the system.
Race condition
A race condition arises when two or more threads, processes, or components access and
modify shared resources concurrently, and the nal outcome depends on the order of
execution.
● Imagine you and your friend both want to turn on a tube light that has two switches.
● If you both press your switches at the same time, the light might icker, stay o , or
turn on depending on the exact timing.
● e problem isn’t the switches themselves—it’s that there’s no rule about who should
press rst.
● Suppose you have ₹1000 in your bank account.
● One program tries to withdraw ₹500, while another tries to deposit ₹200 at the same
time.
● If both act without coordination, the nal balance might end up as ₹700, ₹1200, or
even stay at ₹1000—depending on timing.
● at’s a race condition: the outcome depends on who “wins the race” to update the
account.
Critical section problem
e critical section problem occurs when multiple processes or threads access shared
resources simultaneously, requiring synchronization to
prevent race conditions and ensure data consistency.
A critical section is a part of a program where shared resources (like memory, les, or
variables) are accessed by multiple processes or threads.
Structure of a Critical Section
1. Entry Section:
e process requests permission to enter the critical section.
Synchronization tools (e.g., mutex, semaphore) are used to control access.
2. Critical Section: e actual code where shared resources are accessed or modi ed.
3. Exit Section: e process releases the lock or semaphore, allowing other processes
to enter the critical section.
4. Remainder Section: e rest of the program that does not involve shared resource
access.
e three key rules to solve the critical
section problem
● Mutual exclusion: this rule states that only 1 process or thread can be in the
critical section at a time.
● Progress : If no process is in the critical section, and some processes want to
enter, the choice of who enters next should not be postponed inde nitely.
Ensures that the system continues to make progress rather than getting stuck.
● Bounded waiting : ere must be a limit on how long a process waits before it
gets a chance to enter the critical section. is ensures that every process gets
a chance to enter critical section and prevents starvation or inde nite waiting
time.
Preemptive and non preemptive kernels
Preemptive Kernel Non Preemptive kernel
a kernel form that permits a process to be replaced Non-preemptive kernels enable a process executing in
when it is in kernel mode kernel mode to be preempted.
Preemptive kernels are complex to design non-preemptive kernels are simpler to design.
In a preemptive kernel, the response time is more the response time is nondeterministic and less
responsive and deterministic. responsive in the non-preemptive kernel.
Preemptive kernels are more reliable and useful in Non-preemptive kernels o er less security and are less
practical situations. practical.
More prone to race conditions as multiple processes Less prone to race conditions
can run and modify kernel data at the same time.
Examples preemptive kernel are IRIX, Linux, and Solaris OS.
non-preemptive kernel are Windows XP and 2000.
Common solution to the critical section
problem
● Peterson’s solution : this ensures that two processes share a
variable to indicate whose turn it is to enter into the critical
section.
● Synchronization hardware: various types of hardware instructions
provide critical section solutions.
● Mutex locks: a process must acquire a lock before entering into the
critical section.
● Semaphore solution: semaphores can be used to solve problems
and can be used to provide exclusive access to the critical section
for any no. of processes
● Monitors: safe way for multiple threads to access shared resources.
Peterson’s solution
Peterson’s solution is a software based solution to the critical section problem where multiple processes
or threads access shared resources or critical section. e algorithm is designed speci cally for two
processes and uses two shared variables:
● ag[i]: A boolean array where ag[i] =true indicates that process i wants to enter the critical section.
●turn: An integer variable indicating whose turn it is to enter the critical section if both processes
want access simultaneously.
Working Steps
1. Intent to Enter: A process sets its ag[i] to true to indicate it wants to enter the critical section.
2. Turn Assignment: e process sets turn to the other process, giving the other process priority if it
also wants to enter.
3. Waiting Condition: e process waits in a loop while the other process also wants to enter
( ag[j] == true) and it is the other process's turn (turn == j).
4. Critical Section: Once the waiting condition is false, the process enters the critical section safely.
5. Exit: After completing its critical section, the process sets ag[i] to false, allowing the other process to
proceed.
flag[i]= ag[j]=false
Pi Pj
do do
{ {
flag[j]=true;
flag[i]=true; turn=i;
turn=j; while( ag[i] && turn==i);
while( ag[j] && turn==j); Critical section
Critical section flag[j]=false;
flag[i]=false; }
while(true);
}
while(true);
Peterson's solution ensures the following properties:
● Mutual Exclusion: Only one process can enter the critical section
at a time.
● Progress: If no process is in the critical section, a process that
wants to enter will eventually be allowed.
● Bounded Waiting: No process waits inde nitely; each process gets
a fair chance to enter the critical section.
🍽
● Imagine 5 kids sitting around a round table . ere’s one fork between
each pair of kids, so 5 forks total.
● Each kid wants to eat spaghetti, but they need 2 forks to eat (one in each
hand).
e problem 🤔
● All kids follow the same rule:
● Pick up the fork on the left
● en pick up the fork on the right
● Eat 🍝
But here’s what can go wrong:
🚫 Deadlock (everyone stuck)
● All 5 kids pick up their left fork at the same time.
● Now:
● Everyone has 1 fork 🤏
● No one can get their second fork
● So no one eats 😬
● 👉 ey’re all waiting forever. is is called deadlock.
😓 Starvation (someone never eats)
● Maybe some kids are faster or luckier:
● One kid keeps grabbing forks quickly
● Another kid keeps missing out
● 👉 at unlucky kid might never get to eat. is is called starvation
● Kids → programs (processes/threads)
● Forks → resources (like les, memory, locks)
● Programs often need multiple resources at once, just like kids need 2
forks.
If they aren’t careful, they can:
● Get stuck forever (deadlock)
● Or some programs never get a turn (starvation)
Here are some ways to solve it:
🔄
● Rule change: One kid picks right fork rst instead of left
→ breaks the circular waiting
● Limit eating: Only 4 kids allowed to try at once
→ at least one kid always gets both forks
● Take turns: A teacher (scheduler) tells who can eat
Dining Philosopher’s problem
Dining Philosophers Problem is a classic synchronization problem in
operating systems that illustrates how multiple processes compete for limited
shared resources and may lead to deadlock and starvation.
● ere are 5 philosophers sitting around a circular table.
● ere is 1 fork between each pair (total 5 forks).
● inking
● Eating 🍝🤔
Each philosopher alternates between:
● To eat, a philosopher must acquire both left and right forks.
● ❌ Deadlock
● All philosophers hold one fork and wait forever.
● ❌ Starvation
● Some philosophers may never get both forks due to unfair scheduling.
Solution to philosopher’s problem
//i is the philosopher’s id, assuming 0 to 4
While(true) {
think(); //think while holding no fork
Wait (fork[i]); //attempt to pick up the left chopstick.
Wait(fork[i+1]%5); //attempt to pick the right chopstick (i+1)%5
Eat(); //eat holding both chopsticks
Signal(fork[i]); //release the left chopstick
Signal(fork[(i+1)%5]); //release the right chopstick
}
Producer consumer problem
Solution
Semaphores used :
Empty : keeps track of empty slots in the bu er.
Full: keeps a track of full slots in the bu er.
Mutex: binary semaphore for mutual exclusion.
Producer code :
Do{ consumer code :
Do{
Wait(empty) // decrement the no. of empty slots Wait(full) // decrement the no. of full slots
Wait(mutex) // acquire lock on the bu er Wait(mutex) // acquire lock on the bu er
Add items to the bu er remove item to the bu er
Signal(mutex) //release the lock of bu er
Signal(mutex) //release the lock of bu er Signal(empty) // increment no. of empty slots
Signal(full) // increment no. of full slots } while(true);
} while(true);
● Imagine you and your friends share a big notebook.
● Some friends only read the notebook (they don’t change anything).
● Some friends write in the notebook (they change or add things).
● Now, here’s the problem:
● 📖 e Rules of the Notebook
● Many readers can read at the same time
→ If 5 friends are just reading, that’s ne. No one is changing anything.
● Only one writer at a time
→ If someone is writing, no one else (reader or writer) should touch the
notebook.
● No reading while writing
→ If a writer is writing, readers must wait. Otherwise, they might see
half-written or messy information.
🧠 Why is this a problem?
Because in a computer (Operating System), many processes (like your friends) want to:
●Read shared data (like les, memory, databases)
●Write/update that data
If we don’t control this properly:
●Readers might see incorrect data
●Writers might overwrite each other’s work
In Operating Systems, is is called the Reader-Writer Problem, and it’s solved using tools
like:
●Locks
●Semaphores
●Monitors
ese act like a “permission system” deciding:
●Who can read
●Who can write
●Who must wait
e Readers writers problem
Writer process Reader process
While(true){
While(true){ //acquire lock so that other readers don’t modify
Wait(w); the rc
Wait(m);
/*perform write operation*/ rc++
Signal(w); If(rc==1)
} Wait(w);
//release lock
Signal(m);
/*perform operation*/
//acquire lock
m is mutex Wait(m);
w is semaphore for writer to access shared Rc--;
resource one at a time If(rc==0)
rc integer variable to count no. of currently Signal(w);
accessing resource. Release lock
Signal(m);
}
Monitors
ink of your computer like a busy kitchen. Lots of things are happening at
once—cooking, cleaning, serving—and someone needs to keep an eye on
everything to make sure it all runs smoothly.
● In an operating system, a monitor is like that supervisor.
● A monitor is a special tool the operating system uses to control access to
shared stu (like memory, les, or printers) so programs don’t mess
things up.
What a monitor does
A monitor helps by:
● Allowing only one program at a time to use a shared resource
● Making others wait their turn
● Waking them up when it’s safe to continue
A monitor in an operating system is a high-level synchronization tool
used to safely manage shared resources between multiple processes or
threads. It helps prevent problems like data corruption when many
tasks try to access the same resource at the same time.
A monitor typically has:
● Shared variables → the data being used (e.g., a bu er)
● Procedures/functions → ways to access that data
● Mutual exclusion → only one process runs inside at once
● Condition variables → allow processes to wait and be noti ed