Operating Systems

SE Sem IV
Module 3
Prof. Sangeetha Selvan
Assistant Professor
Computer Engineering Department
Pillai College of Engineering
Process Synchronization and Deadlocks

● Concurrency: Principles of Concurrency,Inter-Process Communication, Process

Synchronization.

● Mutual Exclusion: Requirements, Peterson Solution,Hardware Support (TSL),

Operating System Support (Semaphores), Classical Problem of Synchronization

● Principles of Deadlock: Conditions and Resource, Allocation Graphs, Deadlock

Handling Mechanism, Dining Philosophers Problem.
Concurrency

● Concurrency is the execution of a set of multiple instruction sequences at the same

time.
● This occurs when there are several process/threads running in parallel.
● These threads communicate with the other threads/processes through a concept of
shared memory or through message passing.
● Because concurrency results in the sharing of system resources - instructions,
memory, files - problems can occur like deadlocks and resources starvation.
Listening to music 🎵
Downloading a file 📥
Editing a document 📄
Principle of Concurrency
● It is possible to have more than a single process/thread accessing the same space in
memory, the same declared variable in the code, or even attempting to read/write to
the same file.
● The amount of time it takes for a process to execute is not easily calculated, so we are
unable to predict which process will complete first.
● The amount of time a process takes to complete depends on the following
○ The activities of other processes
○ The way operating system handles interrupts
○ The scheduling policies of the operating system
Problems in Concurrency
● Sharing global resources
○ if two processes both make use of a global variable and both make
changes to the variables value, then the order in which various
changes take place are executed is critical.
● Optimal allocation of resources
○ It is difficult for the operating system to manage the allocation of
resources optimally.
● Locating programming errors
○ It is very difficult to locate a programming error
● Locking the Channel
○ It may be inefficient for the operating system to simply lock the
resource and prevent its use by other processes.
Inter Process Communication
● A process can be of two types:
○ Independent process is not affected by the execution of other
processes
○ Co-operating process can be affected by other executing processes
Inter process communication (IPC) is a mechanism which allows processes to
communicate with each other and synchronize their actions.
● Processes can communicate with each other through both:
1. Shared Memory
2. Message passing
Inter Process Communication
Shared Memory
● Shared Memory is faster once it is set up, because no system calls are required and access
occurs at normal memory speeds.
● However it is more complicated to set up, and doesn't work as well across multiple
computers.
● Shared memory is generally preferable when large amounts of information must be shared
quickly on the same computer.
● In general the memory to be shared in a shared-memory system is initially within the
address space of a particular process, which needs to make system calls in order to make
that memory publicly available to one or more other processes.
● Other processes which wish to use the shared memory must then make their own system
calls to attach the shared memory area onto their address space.
● Generally a few messages must be passed back and forth between the cooperating
processes first in order to set up and coordinate the shared memory access.
Producer-Consumer Example Using Shared Memory

● This is a classic example, in which one process is producing data and another process is
consuming the data.
● The data is passed via an intermediary buffer, which may be either unbounded or bounded.
With a bounded buffer the producer may have to wait until there is space available in the
buffer, but with an unbounded buffer the producer will never need to wait. The consumer
may need to wait in either case until there is data available.
Message Passing
● Message Passing requires system calls for every message transfer, and is therefore
slower, but it is simpler to set up and works well across multiple computers.
● Message passing is generally preferable when the amount and/or frequency of data
transfers is small, or when multiple computers are involved
● Message passing systems must support at a minimum system calls for "send
message" and "receive message".
● A communication link must be established between the cooperating processes before
messages can be sent.
Message Passing

There are three key issues to be resolved in message passing systems

● Direct or indirect communication ( naming )
● Synchronous or asynchronous communication
● Automatic or explicit buffering.
Naming
● With direct communication the sender must know the name of the receiver to which it
wishes to send a message.
● There is a one-to-one link between every sender-receiver pair.
● For symmetric communication, the receiver must also know the specific name of the
sender from which it wishes to receive messages.
● For asymmetric communications, this is not necessary.
Naming
● Indirect communication uses shared mailboxes, or ports.
● Multiple processes can share the same mailbox or boxes.
● Only one process can read any given message in a mailbox
● The OS must provide system calls to create and delete mailboxes, and to send and
receive messages to/from mailboxes.
Synchronous or asynchronous communication

● Blocking is considered synchronous and blocking send means the sender

will be blocked until the message is received by receiver
● Similarly, blocking receive has the receiver block until a message is available
● Non-blocking is considered asynchronous and Non-blocking send has the sender
sends the message and continue.
● Non-blocking receive has the receiver receive a valid message or null.
Buffering
● Messages are passed via queues, which may have one of three capacity
configurations:
○ Zero capacity - Messages cannot be stored in the queue, so senders must
block until receivers accept the messages.
○ Bounded capacity- There is a certain predetermined finite capacity in the
queue. Senders must block if the queue is full, until space becomes
available in the queue, but may be either blocking or non-blocking
otherwise.
○ Unbounded capacity - The queue has a theoretical infinite capacity, so
senders are never forced to block.
Examples of IPC systems

● Posix : uses shared memory method.

● Mach : uses message passing
● Windows XP : uses message passing using local procedural calls
Process Synchronization
● A cooperative process is the one which can affect the execution of other process or
can be affected by the execution of other process.
● The procedure involved in preserving the appropriate order of execution of
cooperative processes is known as Process Synchronization.
● Race Condition:
A race condition is an undesirable situation that occurs when a device or system
attempts to perform two or more operations at the same time
● Critical Section
The regions of a program that try to access shared resources and may cause race
conditions are called critical section. To avoid race condition among the processes,
we need to assure that only one process at a time can execute within the critical
section
Critical Section Problem
● A critical section is a code segment that can be accessed by only one process
at a time. The critical section contains shared variables that need to be
synchronized to maintain the consistency of data variables.
● Each process must 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.
Critical Section Parts
The following are the four most important parts of the critical section:

● Entry Section: It is a step in the process that determines whether or not a process
may begin.
● Critical Section: This section enables a single process to access and modify a shared
variable.
● Exit Section: Other processes waiting in the Entry Section are able to enter the Critical
Sections through the Exit Section. It also ensures that a process that has completed
its execution gets deleted via this section.
● Remainder Section: The Remainder Section refers to the rest of the code that isn't in
the Critical, Entry, or Exit sections.
Requirements of Synchronization mechanisms
Mutual Exclusion
● By Mutual Exclusion, we mean that if one process is executing inside critical section
then the other process must not enter in the critical section.
Requirements of Synchronization mechanisms

Progress
● If no process is executing in the critical section and other processes are waiting
outside the critical section, then only those processes that are not executing in their
remainder section can participate in deciding which will enter in the critical section
next, and the selection cannot be postponed indefinitely.

Bounded Waiting
● No process should wait for a resource for infinite amount of time.
SOLUTION TO CRITICAL SECTION
1. Software Approach
i. Dekkerʼs Algorithm
ii. Peterson Algorithm
2. Hardware Approach
i. Interrupt Disable
ii. Test and set Instruction
3. OS Approach
i. Semaphore
ii. Monitor
4. Classical Synchronization
i. Producer Consumer
ii. Reader Writer
iii. Dining Philosopher