KITS/CAI OS-UNIT-2

UNIT-2
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.
Q) Write a short note on Process Concept?
A process is a program in execution.
A process generally also includes the process stack, which contains
temporary data (such as function parameters, return addresses, and local
variables), and a data section, which contains global variables. The structure
of a process in memory is shown in Figure

1|
KITS/CAI OS-UNIT-2

A process may also include a heap, which is memory that iis

s dynamically
allocated during process run time. We emphasize that a program by itself is
not a process; a program is a passive entity, such as a file containing a list
of instructions stored on disk (often called an executable file), whereas a
process is an active entity, with a program counter specifying the next
instruction to execute and a set of associated resources. A program becomes
a process when an executable file is loaded into memory.

Q)Write about different states of Process?

As a process executes,
cutes, it changes state. The state of a process is defined in
part by the current activity of that process. Each process may be in one of
the following states:
 New. The process is being created.
 Running. Instructions are being executed.
 Waiting. The process
ss is waiting for some event to occur (such as an
I/O completion or reception of a signal).
 Ready. The process is waiting to be assigned to a processor.
 Terminated.

2|
KITS/CAI OS-UNIT-2

Q) Explain in detail Process Control Block ( PCB)?

When the process is created by the operating system it creates a data
structure to store the information of that process. This is known as Process
Control Block (PCB). Process Control block (PCB) is a data structure that
stores information of a process.
PCBs are stored in especially reserved memory for the operating
system known as kernel space. It can be represented as follows

Note: The Random Access Memory (RAM) can be logically divided into
two distinct regions namely - the kernel space and the user space.
PCB is unique for every process which consists of various attributes
such as process ID, priority, registers, program counters, process states, list
of open files, etc.
Structure of Process Control Block
The process control block contains many attributes such as process ID,
process state, process priority, accounting information, program counter,
CPU registers`, etc for each process.

3|
KITS/CAI OS-UNIT-2

1. Process ID:
When a new process is created by the user, the operating system
assigns a unique ID i.e a process
process-ID
ID to that process. This ID helps
h the
process to be distinguished from other processes existing in the system.
2. Process states:

3. Process Priority:
Process priority is a numeric value that represents the priority of each
process. The lesser the value, the greater the priority of that process. This
priority is assigned at the time of the creation of the PCB and may depend

4|
KITS/CAI OS-UNIT-2

on many factors like the age of that process, the resources consumed, and
so on. The user can also externally assign a priority to the process.
4. Process Accounting Information:
This attribute gives the information of the resources used by that
process in its lifetime. For Example: CPU time connection time, etc.
5. Program Counter:
The program counter is a pointer that points to the next instruction in
the program to be executed. This attribute of PCB contains the address of
the next instruction to be executed in the process.
6. CPU registers:
A CPU register is a quickly accessible small-sized location available to
the CPU. These registers are stored in virtual memory(RAM).
6. Context Switching:
A context switching is a process that involves switching the CPU from one
process or task to another. It is the process of storing the state of a process
so that it can be restored and resume execution at a later point. This allows
multiple processes to share a single CPU and is an essential feature of a
multitasking operating system.
So, whenever context switching occurs in the code execution then the
current state of that process is stored temporarily in CPU registers. This
helps in the fast execution of the process by not wasting time-saving and
retrieving state information from the secondary memory (hard disk).
8. PCB pointer:
This field contains the address of the next PCB, which is in ready state.
This helps the operating system to hierarchically maintain an easy control
flow between parent processes and child processes.

5|
KITS/CAI OS-UNIT-2

9. List of open files:

As the name suggests, It contains information on all the files that are used
by that process. This field is important as it helps the operating system to
close all the opened files at the termination state of the process.
10. Process I/O information:
In this field, the list of all the input/output devices which are required
by that process during its execution is mentioned.
Q) Explain the operations performed on processes?
Operations on Process in OS:
Two operations on a process in OS:
1. Process creation
2. Process Termination
1. Process Creation
A process during its execution can create many new processes via system
call (depending upon the OS).
The creating process is called the parent while the created process is called
the child. Each child process may in turn create new child process.
Every process in the system is identified with a process identifier(PID) which
is unique for each process.
For Example fork() system call can be used for creating new process.
The fork() System Call is used to create processes. It does not take any
arguments and returns a process ID (mostly an integer value). Fork system
call creates a new process (called child process) that runs concurrently with
the parent process (the process that makes the fork() call).
fork() return the following values:
Negative value - it represents the creation of the child process was
unsuccessful.
Zero - it represents a new child process is created.

6|
KITS/CAI OS-UNIT-2

Positive value - The process ID of the child process to the parent. The
returned process ID is type pid_t defined in sys/types.h. Usually, the process
ID is an integer.
2. Process Termination
There are two methods a process can terminate:
Normal termination – A process finishes executing its final statement. All the
resources allocated to it are freed by the operating system.
Forced Termination – a parent process can terminate its child process by
invoking the appropriate system call. The paren
parentt can terminate the child due
to the following reasons:
Child exceeds its usage of resources
Task assigned to the child is no longer required
Parent exits and OS does not allow child to run if parent terminates
Example: kii and exit system calls can be use
usedd for process forced
termination
Q) Discus about the IPC( Inter process communication)?
communication)
Interprocess communication is the mechanism provided by the operating
system that allows processes to communicate with each other.

There are several reasons for providing an environment that allows process
cooperation:
Here, are the reasons for using the interprocess communication protocol for
information sharing:
 It helps to speedup modularity
 Computational

7|
KITS/CAI OS-UNIT-2

 Privilege separation
 Convenience
 Helps operating system to communicate with each other and
synchronize their actions.
There are two fundamental models of interprocess communication:
(1) Shared memory and
(2) Message passing.
(1) Shared memory:
Shared memory system is one of the fundamental models of interprocess
communication. In the shared memory system, the cooperating processes
communicate with each other by establishing the shared memory region, in
its address space. Shared memory model allows the fastest interprocess
communication.
Working
In Shared Memory system, the cooperating processes communicate, to
exchange the data or the information with each other. For this, the
cooperating processes establish a shared region in their memory. The
processes share data by reading and writing the data in the shared segment
of the processes.
Consider a scenario, there are two cooperating processes P1 and P2. Both
the processes P1 and P2, have their different address spaces. Now, P1 wants
to share some data with P2. So, P1 and P2 will have to perform the following
steps.
Step 1: As the process P1 has some data, to share with process P2. Process
P1 has to take the initiative and establish a shared memory region in its own
address space and store the data or information to be shared in it’s shared
memory region.

8|
KITS/CAI OS-UNIT-2

Step 2: Now, P2 requires the information stored in the shared segment of

the P1. So, process P2 has to attach itself to the shared address space of P1.
Now, P2 can read out the data from there.
Step 3: Process P1 and P2 can exchange information or data by reading and
writing data in the shared segment of the process.
Example for shared memory concept “producer and consumer”.
let us clear this concept with the help of the diagram given below.

(2) Message passing:

It refers to means of communication between
- Different thread with in a process .
- Different processes running on same node.
- Different processes running on different node.
In this a sender or a source process send a message to a destination
process.
Message has a predefined structure and message passing uses two system
call: Send and Receive
send(name of destination process, message);
receive(name of source process, message);

9|
KITS/CAI OS-UNIT-2

it can be represented as follows

In this calls, the sender and receiver processes address each other by
names. Mode of communication between two process can take place through
two methods
1) Direct Addressing
2) Indirect Addressing
Direct Addressing:
In this type that two processes need to name other to communicate. This
become easy if they have the same parent.
Example
If process A sends a message to process B, then
send(B, message);
Receive(A, message);
By message passing a link is established between A and B. Here the receiver
knows the Identity of sender message destination. This type of arrangement
in direct communication is known as Symmetric Addressing.

Indirect addressing:
In this message send and receive from a mailbox. A mailbox can be
abstractly viewed as an object into which messages may be placed and from

10 |
KITS/CAI OS-UNIT-2

which messages may be removed by processes. The sender and receiver

processes should share a mailbox to communicate.

Q) Explain how to provide communication in Client-Server

Systems?
we described how processes can communicate using shared memory
and message passing. These techniques can be used for
communication in client-server systems
There are also other strategies can be used for providing
communication between client and server environment. They are
Socket:
Sockets are strategies that are used for communication between
processes. It is mainly used in client-server based systems.
When two systems want to communicate with each other, sockets are
the endpoint on either end of the communicating processes.
A socket is identified by an IP address concatenated with a port number.
Servers implementing specific services (such as TELNET, FTP, and HTTP)
listen to well-known ports.
In Client-Server systems, the Client asks for information from the server and
the Server provides the information to the client. In order for the client to
communicate to the server and the server to communicate back to the
Client, there needs to be a connection between the Client and the Server.

11 |
KITS/CAI OS-UNIT-2

In order to establish this connection, we are going to use sockets.

2. RPC (Remote Procedure Call):

A remote procedure call is an interprocess communication technique that is
used for client-server
server based applications. It is also known as a subroutine
call or a function call.
A client has a request message 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. The client is blocked while the server is processing the call
and only resumed execution after the server is finished.

12 |
KITS/CAI OS-UNIT-2

Q) What is Thread? Explain the different Multithreading models?

Threads
A thread refers to a single sequential flow of activities being executed in a
process; it is also known as the thread of execution or the thread of control.
Each thread has its own program counter, a stack and a set of registers
that reside in a process. Threads can’t exist outside any process. Also, each
thread belongs to exactly one process.

Threads are popularly used to improve the application through parallelism.

Actually only one thread is executed at a time by the CPU, but the CPU
switches rapidly between the threads to give an illusion that the threads

are running parallelly.

Threads are also known as Lightweight processes. Threads are a popular

way to improve the performance of an application through parallelism.
Types of Thread
There are two types of threads:
1. User Threads
2. Kernel Threads
User threads are above the kernel and without kernel support. These are
the threads that application programmers use in their programs.

13 |
KITS/CAI OS-UNIT-2

Kernel threads are supported within the kernel of the OS itself. All modern
OSs support kernel-level threads, allowing the kernel to perform multiple
simultaneous tasks and/or to service multiple kernel system calls
simultaneously.
Multithreading Models
The user threads must be mapped to kernel threads, by one of the
following strategies:
1. Many to One Model
2. One to One Model
3. Many to Many Model
Many to One Model
In the many to one model, many user-level threads are all mapped onto a
single kernel thread.

One to One Model

The one to one model creates a separate kernel thread to handle each
and every user thread.
Most implementations of this model place a limit on how many threads
can be created.
Linux and Windows from 95 to XP implement the one-to-one model for
threads.

14 |
KITS/CAI OS-UNIT-2

Many to Many Model

The many to many model multiplexes any number of user threads onto an
equal or smaller number of kernel threads, combining the best features of
the one-to-one and many-to-one models.
Users can create any number of threads.

Q) What are Thread Libraries?

Thread libraries provide programmers with API for the creation and
management of threads.
Thread libraries may be implemented either in user space or in kernel space.
The user space involves API functions implemented solely within the user
space, with no kernel support. The kernel space involves system calls and
requires a kernel with thread library support.

15 |
KITS/CAI OS-UNIT-2

Three types of Thread

POSIX Pitheads may be provided as either a user or kernel library, as an
extension to the POSIX standard.
Win32 threads are provided as a kernel-level library on Windows systems.
Java threads: Since Java generally runs on a Java Virtual Machine, the
implementation of threads is based upon whatever OS and hardware the
JVM is running on, i.e. either Pitheads or Win32 threads depending on the
system.
Q) Explain the threading issues?
We discuss some of the issues to consider with multithreaded programs.
1. Discus about fork (), exec () system calls
2. Thread Cancellation
Thread cancellation means terminating a thread before it has finished
working. There can be two approaches for this, one is Asynchronous
cancellation, which terminates the target thread immediately. The other is
Deferred cancellation allows the target thread to periodically check if it
should be canceled.
[Link] Handling
Signals are used in UNIX systems to notify a process that a particular event
has occurred. Now in when a Multithreaded process receives a signal, to
which thread it must be delivered? It can be delivered to all or a single
thread.
Q) What is Process Scheduling? Explain the different types
process scheduling?
The act of determining which process is in the ready state, and should be
moved to the running state is known as Process Scheduling.
The prime aim of the process scheduling system is to keep the CPU busy all
the time and to deliver minimum response time for all programs. For

16 |
KITS/CAI OS-UNIT-2

achieving this, the scheduler must apply appropriate rules for swapping
processes IN and OUT of CPU.
Scheduling fell into one of the two general categories:
Preemptive Scheduling is a CPU scheduling technique that works by
dividing time slots of CPU to a given process. The time slot given might be
able to complete the whole process or might not be able to it.
Non-preemptive Scheduling is a CPU scheduling technique the process
takes the resource (CPU time) and holds it till the process gets terminated or
is pushed to the waiting state. No process is interrupted until it is completed,
and after that processor switches to another process.
Q) Explain the different types Scheduling Queues?
All processes, upon entering into the system, are stored in the Job Queue.
Processes in the “Ready” state are placed in the Ready Queue.
Processes waiting for a device to become available are placed in Device
Queues. There are unique device queues available for each I/O device.
A new process is initially put in the Ready queue. It waits in the ready
queue until it is selected for execution (or dispatched). Once the process is
assigned to the CPU and is executing, one of the following several events
can occur:
The process could issue an I/O request, and then be placed in the I/O
queue.
The process could create a new sub process and wait for its termination.
The process could be removed forcibly from the CPU, as a result of an
interrupt, and be put back in the ready queue.

17 |
KITS/CAI OS-UNIT-2

1. Every new process first put in the Ready queue .It waits in the ready
queue until it is finally processed for execution. Here, the new process
is put in the ready queue and wait until it is selected for execution or it
is dispatched.
2. One of the processes is allocated the CPU and it is executing
3. The process should issue an I/O request
4. Then, it should be placed in the I/O queue.
5. The process should create a new sub process
6. The process should be waiting for its termination.
7. It should remove forcefully from the CPU, as a result interrupt. Once
interrupt is completed, it should be sent back to ready queue.
Types of Schedulers
There are three types of schedulers available:
Long Term Scheduler
Short Term Scheduler
Medium Term Scheduler
Let's discuss about all the different types of Schedulers in detail:

18 |
KITS/CAI OS-UNIT-2

Long Term Scheduler

Long term scheduler runs less frequently. Long Term Schedulers decide
which program must get into the job queue. From the job queue, the Job
Processor, selects processes and loads them into the memory for
execution. Primary aim of the Job Scheduler is to maintain a good degree
of Multiprogramming. An optimal degree of Multiprogramming means the
average rate of process creation is equal to the average departure rate of
processes from the execution memory.
Short Term Scheduler
This is also known as CPU Scheduler and runs very frequently. The
primary aim of this scheduler is to enhance CPU performance and
increase process execution rate.
Medium Term Scheduler
This scheduler removes the processes from memory (and from active
contention for the CPU), and thus reduces the degree of
multiprogramming. At some later time, the process can be reintroduced
into memory and its execution van 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. This complete process is descripted in the

below diagram:

19 |
KITS/CAI OS-UNIT-2

Context Switch
A context switch is the mechanism to store and restore the state or context
of a CPU in Process Control block so that a process execution can be
resumed from the same point at a lat
later
er time. Using this technique, a context
switcher enables multiple processes to share a single CPU. Context switching
is an essential part of a multitasking operating system features.
When the scheduler switches the CPU from executing one process to execute
execut
another, the state from the current running process is stored into the
process control block. After this, the state for the process to run next is
loaded from its own PCB and used to set the PC, registers, etc. At that point,
the second process can start executing.

20 |
KITS/CAI OS-UNIT-2

Q) Explain the various Operations performed on Process?

Process Creation
Through appropriate system calls, such as fork or spawn, processes may
create other processes. The process which creates other process, is termed
the parent of the other process, while the created sub-process is termed
its child.
Each process is given an integer identifier, termed as process identifier, or
PID. The parent PID (PPID) is also stored for each process.
A child process may receive some amount of shared resources with its
parent depending on system implementation. To prevent runaway children
from consuming all of a certain system resource, child processes may or
may not be limited to a subset of the resources originally allocated to the
parent.
There are two options for the parent process after creating the child :
 Wait for the child process to terminate before proceeding. Parent
process makes a wait() system call, for either a specific child process
or for any particular child process, which causes the parent process to
block until the wait() returns. UNIX shells normally wait for their
children to complete before issuing a new prompt.
 Run concurrently with the child, continuing to process without waiting.
When a UNIX shell runs a process as a background task, this is the
operation seen. It is also possible for the parent to run for a while, and
then wait for the child later, which might occur in a sort of a parallel
processing operation.
There are also two possibilities in terms of the address space of the new
process:
1. The child process is a duplicate of the parent process.
2. The child process has a program loaded into it.

21 |
KITS/CAI OS-UNIT-2

Process Termination
By making the exit(system call), typically returning an integer, processes
may request their own termination. This int is passed along to the parent if it
is doing a wait(), and is typically zero on successful completion and some
non-zero code in the event of any problem.
Processes may also be terminated by the system for a variety of reasons,
including :
 The inability of the system to deliver the necessary system resources.
 In response to a KILL command or other unhandled process interrupts.
 A parent may kill its children if the task assigned to them is no longer
needed.
Q) Explain the various scheduling algorithms?
There are various CPU scheduling algorithms are available. They are
1. First Come First Serve:
FCFS considered to be the simplest of all operating system scheduling
algorithms. First come first serve scheduling algorithm states that the
process that requests the CPU first is allocated the CPU first and is
implemented by using FIFO queue.
Characteristics of FCFS:
FCFS supports non-preemptive and preemptive CPU scheduling algorithms.
Tasks are always executed on a First-come, First-serve concept.
FCFS is easy to implement and use.
This algorithm is not much efficient in performance, and the wait time is
quite high.
Advantages of FCFS:
Easy to implement
First come, first serve method
Disadvantages of FCFS:

22 |
 KITS/CAI OS-UNIT-2

FCFS suffers from Convoy effect.

The average waiting time is much higher than the other algorithms.
Convoy Effect: In convoy effect, Consider processes with higher burst time
arrived before the processes with smaller burst time.
Then, smaller processes have to wait for a long time for longer processes to
release the CPU.
2. Shortest job first (SJF) is a scheduling process that selects the waiting
process with the smallest execution time to execute next. This scheduling
method may or may not be preemptive. Significantly reduces the average
waiting time for other processes waiting to be executed. The full form of
SJF is Shortest Job First.
Characteristics of SJF Scheduling
 It is associated with each job as a unit of time to complete.
 In this method, when the CPU is available, the next process or job with
the shortest completion time will be executed first.
 It is Implemented with non-preemptive policy.
 It improves job output by offering shorter jobs, which should be
executed first, which mostly have a shorter turnaround time.
3. Round-Robin Scheduling
The name of this algorithm comes from the round-robin principle, where
each person gets an equal share of something in turns. It is the oldest,
simplest scheduling algorithm, which is mostly used for multitasking.
Characteristics of Round-Robin Scheduling
 Round robin is a pre-emptive algorithm
 The CPU is shifted to the next process after fixed interval time, which
is called time quantum/time slice.
 The process that is preempted is added to the end of the queue.
 Time slice should be minimum, which is assigned for a specific task
that needs to be processed.

23 |
KITS/CAI OS-UNIT-2

 It is a real time algorithm which responds to the event within a specific

time limit.
 Round robin is one of the oldest, fairest, and easiest algorithm.
4. Priority scheduling algorithm:
Priority Scheduling is a method of scheduling processes that is based on
priority. In this algorithm, the scheduler selects the tasks to work as per the
priority.
The processes with higher priority should be carried out first, whereas jobs
with equal priorities are carried out on a round-robin or FCFS basis. Priority
depends upon memory requirements, time requirements, etc.
Types of Priority Scheduling
Priority scheduling divided into two main types:
Preemptive Scheduling
In Preemptive Scheduling, the tasks are mostly assigned with their priorities.
Sometimes it is important to run a task with a higher priority before another
lower priority task, even if the lower priority task is still running. The lower
priority task holds for some time and resumes when the higher priority task
finishes its execution.
Non-Preemptive Scheduling
In this type of scheduling method, the CPU has been allocated to a specific
process. The process that keeps the CPU busy, will release the CPU either by
switching context or terminating. It is the only method that can be used for
various hardware platforms. That’s because it doesn’t need special hardware
(for example, a timer) like preemptive scheduling.
Characteristics of Priority Scheduling
 A CPU algorithm that schedules processes based on priority.
 It used in Operating systems for performing batch processes.

24 |
KITS/CAI OS-UNIT-2

 If two jobs having the same priority are READY, it works on a FIRST
COME, FIRST SERVED basis.
 In priority scheduling, a number is assigned to each process that
indicates its priority level.
 Lower the number, higher is the priority.
 In this type of scheduling algorithm, if a newer process arrives, that is
having a higher priority than the currently running process, then the
currently running process is preempted.
Interprocess communications:
Race conditions:
Each of the processes has some sharable resources and some non-shareable
resources. The sharable resources can be shared among the cooperating
processes.
The non-cooperating processes don’t need to share the resources. Then
what is the race condition. When we synchronize the processes and the
synchronization is not proper then the race condition occurs.
How to Identify Race Conditions:
Before we understand how to identify possible race scenarios, let us
understand what a critical section of a code is:
Critical Section
A critical section of a code is that part that is executed by multiple threads.
Different orders of execution across threads that run concurrently can lead
to different outputs, which make the critical section susceptible to a race
condition.
For example:
Consider the operation of adding money to your bank account. Let us say
you are doing so using two different apps simultaneously. The following
steps take place while doing so:
The app reads your current balance

25 |
KITS/CAI OS-UNIT-2

The additional amount is added to the current balance

The bank balance is finally updated
Assume your current balance is ₹1000, and you add ₹200 from app A, and
₹500 from app B
The following race condition occurs:
App A reads the current balance, which is ₹1000
App A adds ₹200 to ₹1000 and gets ₹1200 as the final balance
Meanwhile, app B fetches the current balance, which is still ₹1000, as app A
has not executed step 3
App B adds ₹500 to ₹1000 and gets ₹1500 as the final balance
App B updates the account balance to ₹1500
App A updates the account balance to ₹1200
Thus the final balance is ₹1200 instead of ₹1700.
This is an example of a “read-write-modify” race condition.
Avoiding Race Conditions:
To avoid race condition we need Mutual Exclusion. Mutual Exclusion is some
way of making sure that if one process is using a shared variable or file, the
other processes will be excluded from doing the same things.
The program where the shared memory is accessed is called the critical
region or critical section. If we could arrange matters such that no two
processes were ever in their critical regions at the same time, we could
avoid race conditions. Although this requirement avoids race conditions.
(Rules for avoiding Race Condition) Solution to Critical section problem:
1. No two processes may be simultaneously inside their critical regions.
(Mutual Exclusion)
2. No assumptions may be made about speeds or the number of CPUs.
3. No process running outside its critical region may block other processes.
4. No process should have to wait forever to enter its critical region.

26 |
KITS/CAI OS-UNIT-2

Busy and waiting:

For implementing “mutual exclusion” we can use technique is called “Busy
and waiting”.
Busy waiting, also known as spinning, or busy looping is a process
synchronization technique in which a process waits and constantly checks for
a condition to be satisfied before proceeding with its execution.
In busy waiting, a process executes instructions that test for the entry
condition to be true, such as the availability of a lock or resource in the
computer system.
For resource availability, consider a scenario where a process needs a
resource for a specific program. However, the resource is currently in use
and unavailable at the moment, therefore the process has to wait for
resource availability before it can continue. This is what is known as busy
waiting as illustrated below:

27 |
KITS/CAI OS-UNIT-2

In some operating systems, busy waiting can be inefficient because the

looping procedure is a waste of computer resources. In addition, the system
is left idle while waiting.
This is particularly wasteful if the task/process at hand is of low priority. In
that case, resources that can be diverted to complete high-priority tasks are
hogged by a low-priority task in busy waiting.
Sleep and Wakeup
As we have seen, busy waiting can be wasteful. Processes waiting to enter
their critical sections waste processor time checking to see if they can
proceed. A better solution to the mutual exclusion problem, which can be
implemented with the addition of some new primitives, would be to block
processes when they are denied access to their critical sections. Two
primitives, Sleep and Wakeup, are often used to implement blocking in
mutual exclusion.
How do Sleep and Wakeup Work?
Essentially, when a process is not permitted to access its critical section, it
uses a system call known as Sleep, which causes that process to block. The
process will not be scheduled to run again, until another process uses the
Wakeup system call. In most cases, Wakeup is called by a process when it
leaves its critical section if any other processes have blocked.

28 |
KITS/CAI OS-UNIT-2

Example: Producer and consumer problem

The Producer-Consumer problem is a classic synchronization problem in
operating systems.
The problem is defined as follows: there is a fixed-size buffer and a Producer
process, and a Consumer process.
The Producer process creates an item and adds it to the shared buffer. The
Consumer process takes items out of the shared buffer and “consumes”
them.
In order to synchronize these processes, we will block the producer when
the buffer is full, and we will block the consumer when the buffer is empty.
So the two processes, Producer and Consumer, should work as follows:
Producer performs the following steps
(1) The producer must first create a new widget.
(2) Then, it checks to see if the buffer is full. If it is, the producer will put
itself to sleep until the consumer wakes it up.
A "wakeup" will come if the consumer finds the buffer empty.
(3) Next, the producer puts the new widget in the buffer. If the producer
goes to sleep in step (2), it will not wake up until the buffer is empty,
so the buffer will never overflow.
(4) Then, the producer checks to see if the buffer is empty. If it is, the
producer assumes that the consumer is sleeping, an so it will wake the
consumer.
Keep in mind that between any of these steps, an interrupt might occur,
allowing the consumer to run.
Consumer performs the following steps:
1) The consumer checks to see if the buffer is empty. If so, the consumer
will put itself to sleep until the producer wakes it up. A "wakeup" will occur
if the producer finds the buffer empty after it puts an item into the buffer.

29 |
KITS/CAI OS-UNIT-2

(2) Then, the consumer will remove a widget from the buffer. The consumer
will never try to remove a widget from an empty buffer because it will not
wake up until the buffer is full.
(3) If the buffer was full before it removed the widget, the consumer will
wake the producer.
(4) Finally, the consumer will consume the widget. As was the case with the
producer, an interrupt could occur between any of these steps, allowing the
producer to run.
Pseudo code for above problem:

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.
In semaphore there are two types of operations down and up. In down
operation we perform decrement operation and up operation performs
increment operation.

30 |
 KITS/CAI OS-UNIT-2

Types of semaphores:
There are 2 types of semaphores.
1. Counting semaphore
2. Binary semaphore
 Counting Semaphores:
Counting semaphore can be used to manage the resources for allotting the
number of processes.
There are the scenarios in which more than one processes need to execute
in critical section simultaneously. However, counting semaphore can be used
when we need to have more than one process in the critical section at the
same time.
Consider there are P1, P2, P3, P4 and P5 processes wants to resources
R1,R2 and R3.

R1 R2 R3

DOWN UP

As per the schedule concept we assign the process “P1” assign to R1,
And it perform down operation.
In the same way R2 assigned to P2, R3 assigned P3, both process
performing down operation.
Let us assume the structure of semaphore as follows:
struct Semaphore
{
int value; // processes that can enter in the critical section simultaneously.
queue type L; // L contains set of processes which get blocked
}

31 |
KITS/CAI OS-UNIT-2

Down (Semaphore S)
{
[Link] = [Link] - 1; //semaphore's value will get decreased when a new
//process enter in the critical section
if ([Link]< 0)
{
put_process(PCB) in L; //if the value is negative then
//the process will get into the blocked state.
Sleep();
}
else
return;
}
up (Semaphore s)
{
[Link] = [Link]+1; //semaphore value will get increased when
//it makes an exit from the critical section.
if([Link]<=0)
{
select a process from L; //if the value of semaphore is positive
//then wake one of the processes in the blocked queue.
wake-up();
}
}
}

Let [Link]=3 (3 because there are three resources available),

when P1 performs the down operation [Link]=2.
when P2 performs the down operation [Link]=1.
when P3 performs the down operation [Link]=0.
If P4 wants try access resources and it performs the down operation
[Link]=-1, when semaphore value becomes negative, the process block it
self and place it into waiting queue.
If anyone process who utilizing the resources is completed, it going to
perform up operation in which [Link] is incremented. Before going to

32 |
 KITS/CAI OS-UNIT-2

perform the up operation it check is there any process wait in waiting queue.
If there is process, then resources allotted it. Otherwise it performs the up
operation.
Binary semaphore:
BS contains only 2 values (0,1) use to deal with critical section for multiple
process. it performs two atomic operations they are down and up. BS can be
used to deal with critical section problems. Let us consider

CRITICAL SECTION AREA

Processes available to enter into critical section are:

P1, P2, P3, P4
 if the process “P1” wants to enter critical section it performs the “down”
operation and check the value of BS, if its value is "1" in that time only we
allow "P1" process into critical section and change the “value” of BS 1 to 0

P1P1

 Process P2 also wants try to enter into critical section it performs the "down"
operation in which we check the value of BS. If its “value” is "1" then we
allow it in CRITICAL SECTION. Otherwise we place it into waiting queue.
 Process P3 also wants try to enter into critical section it performs the "down"
operation in which we check the value of BS. If its value is "1" then we allow
it in CRITICAL SECTION. Otherwise we place it into waiting queue.
 Process P4 also wants try to enter into critical section it performs the “down”
operation in which we check the value of BS. If its value is "1" then we allow
it in CRITICAL SECTION. Otherwise we place it into waiting queue.
33 |
 KITS/CAI OS-UNIT-2

 If "P1" completes utilizing the resources then it performs “up” operation.

Here important notice is that it does not change the value of BS 0 to 1, it
checks the "waiting queue". if there is any process are in waiting state it
does not change the “value” of BS and it that allows process into critical
section.
 if there is no other process available in waiting queue then only change the
value of BS value to 0 to 1.

pseudo code for binary semaphore

struct BSemaphore
{
enum value{0,1}
}s;
DOWN(struct BSemaphore s)
{
if([Link]==1)
{
[Link]=0
}
else
{
put the process in S.L(waiting queue) & block it
}
}
UP(struct BSemaphore s)
{
if(S.L is empty)
{
[Link]=1;
}
else
{
select a process from S.L & wakeup()
}
}

34 |
KITS/CAI OS-UNIT-2

Producer and Consumer problem using semaphore

#define N 100
int buffer[N]
csemaphore empty=N
full=0
/* empty means how many slots are availbe
full means how many slots are filled */
bsemaphore mutex=1;

"in" means represents index of buffer where item placed

out means represent item which is to be out from buffer

empty=0 means slots are not available to place items.

empty=N buffer is empty.

full=0 means buffer is empty

full=N buffer is full with items.

void producer(void)
{
int itemp,in=0;
while(1)
{
Produce_item(itemp);
down(empty);
/* requesting for buffer to place item. N=100-1=99*/
down(mutex);
/* mutex value changed to 1 to 0*/
buffer[in]=itemp;
in=(in+1) mod N;

35 |
KITS/CAI OS-UNIT-2

up(mutex);
/* mutex value changed to 0 to 1*/
up(full);
/* full value changed full=full+1, 0+1=1
}
}

void consumer(void)
{
int itempc,out=0;
while(1)
{
down(full);
/* reqeusting for consuming the item*/
full=full-1=1-1=0
down(mutex);
/* mutex value changed to 1 to 0
itemc=buffer[out];
out=(out+1)mod N
up(mutex)
/* mutex value changed to 0 to 1
up(empty);
/* empty value incremented so 99+1=100*/
process_item(itemc);
}
}

36 |
KITS/CAI OS-UNIT-2

Dining Philosophers Problem (DPP)

The dining philosophers problem states that there are 5 philosophers sharing
a circular table and they eat and think alternatively.
There is a bowl of rice for each of the philosophers and 5 chopsticks. A
philosopher needs both their right and left chopstick to eat.
A hungry philosopher may only eat if there are both chopsticks
available. Otherwise a philosopher puts down their chopstick and begin
thinking again.

Pseudo Code for above problem using semaphore

#define N 5
#define thinking 0
#define hungry 1
#define eating 2
#define left (i+N-1)%N // let i=1 (1+5-1)%5=0
#define left (i+1)%N // let i=1 (1+1)%5=2
bsemaphore mutex=1
bsemaphore s[N]={0}
int state[N]=0 // represents the philosopher state

37 |
KITS/CAI OS-UNIT-2

void phlisopher(int i) (let i=1)

{
while (true)
{
thinking();
takeforks(i);
eat();
putforks(i);
}
}

void takeforks(int i) (i=1)

{
down mutex; // i=1 ,mutex=1-->0
state[i]=hungry; // makes hungry
test(i); // calling test function
up(mutex); // 0 to 1
down(s[i]); // 1-->0
}

void test(int i) (i=1)

{
//state[1]==hungry (T) && T && T
if(state[i]==hungry && state[left]!=eating && state[right]!=eating)
{
state[i]=eating; //state[1]=eating
up(s[i]); //up(s[1])=1
}
}
void putforks(int i) (i=1)
{
down(mutex) // 1-->0
state[i]=thinking;
test[left]; //test[0]
test[right];
up(mutex);
}
}

38 |
KITS/CAI OS-UNIT-2

Monitors
Monitors are used for process synchronization. With the help of
programming languages, we can use a monitor to achieve mutual exclusion
among the processes. Example of monitors: Java Synchronized
methods such as Java offers notify() and wait() constructs.
Characteristics of Monitors.
1. Inside the monitors, we can only execute one process at a time.
2. Monitors are the group of procedures, and condition variables that are
merged together in a special type of module.
3. If the process is running outside the monitor, then it cannot access the
monitor’s internal variable. But a process can call the procedures of
the monitor.
4. Monitors offer high-level of synchronization
5. Monitors were derived to simplify the complexity of synchronization
problems.
6. There is only one process that can be active at a time inside the
monitor.
Components of Monitor
There are four main components of the monitor:
1. Initialization
2. Private data
3. Monitor procedure
4. Monitor entry queue
Initialization: - Initialization comprises the code, and when the monitors
are created, we use this code exactly once.
Private Data: - Private data is another component of the monitor. It
comprises all the private data, and the private data contains private
procedures that can only be used within the monitor. So, outside the
monitor, private data is not visible.

39 |
KITS/CAI OS-UNIT-2

Monitor Procedure: - Monitors Procedures are those procedures that can

be called from outside the monitor.
Monitor Entry Queue: - Monitor entry queue is another essential
component of the monitor that includes all the threads, which are called
procedures.
syntax:

Condition Variables
There are two types of operations that we can perform on the condition
variables of the monitor:
1. Wait
2. Signal
Suppose there are two condition variables
condition a, b // Declaring variable
Wait Operation
[Link](): - The process that performs wait operation on the condition
variables are suspended and locate the suspended process in a block queue
of that condition variable.
Signal Operation
[Link]() : - If a signal operation is performed by the process on the
condition variable, then a chance is provided to one of the blocked
processes.
Advantages of Monitor
It makes the parallel programming easy, and if monitors are used, then
there is less error-prone as compared to the semaphore.

40 |
KITS/CAI OS-UNIT-2

Example:

41 |