INTERPROCESS COMMUNICATION

The process within a computing system does not act in isolation.  They must co-operate to achieve the desired objective of running user jobs.  They are in competition for the use of limited resources such as processors, memory or files.  The two elements of co-operation and competition imply the need for some form of communication between processes.  Processes can inter-communicate by sending messages, data or code between them.  Processes frequently need to communicate with other processes.

Example:

In a shell pipeline, the output of the first process must be passes to the second and so on down the line.  Therefore, there is need for communication between processes in a well –structured manner.

–           Issues relating to interprocess communication

(a)        How one process can pass information to another

(b)        To make sure that two or more processes do not get in each other’s way eg. Two processes in an airline reservation system each trying to grab the last seat on a plane for a different customer.

(c)        Proper sequencing when dependencies are present. E.g If process A produces data and process B prints them.  Process B has to wait until A has produced some data before starting to print.  Two processes might want to co-operate in performing a particular task. 

Eg.  A process might want to print a document in response to a user’s request, so it starts another process to handle the printing and sends a message to start printing.  Once the process handling the printing request finishes, it sends message back to the original process, which reads the message and uses this to pop up a dialog box informing the user the document has been printed.

Race Conditions:

            In some O/S, processes that are working together may share some common storage that each one can read and write.  This shared storage may be in main memory or it may be a shared file and its position does not change the nature of the communication or the problem that arises.

Practical example:

(1)        A print spooler

            When a process want to print a file, it enters the file name in a special spooler director.  Another process, the printer deamor, periodically checks to see if there are any files to be printed.  If there are, it prints them and removes their names from the directory.  Assuming our spooler directly has many slots which are number from o, 1, …, each slot is capable of hold a file name.

Also assume there are two shared variables “out”, which points to the next file to be printed and “in” which points to the next free slot in the directory, these two variables might be kept in a file available to all processes.

Dig. 1:  Two processes wanting access shared memory

            At certain time, slots 0 to 3 are empty which means that the files in those slots have been printed, slot 4, 5 and 6 are filled with names of file to be printed.  This can be seen in the diagram 1.

            In this Process A reads the variable `in’ and stores the value 7 in a local variable called next-free-slot.  An interrupt occurs and the CPU switches from Process A to Process B.  Again Process B reads the variable in and also gets a 7 and stores it in its local variable next-free-slot.

            At this instant, both processes think that the next available slot is 7.  Process B continues to run and stores the name of its file in slot 7 and updates the variable “in” to be an 8 and goes off to do some other things. Eventually, Process A runs again starting from the place it left off.  It looks at it next-free-slot and finds 7 and writes its filename in slot 7 overwriting or erasing the name Process B has just put there.  It also computes its next-free-slot + 1 and gets an 8 which it put in the variable “in” to become 8.  The “printer deamor” which periodically checks to see if there are any files to be printed will not notice anything wrong, rather Process B will never receive any output, user B will hang around the printer room for a long period of time hoping for output that never comes.  In situation like this where two or more processes are reading or writing some shared data and the final result depends on who runs precisely when, are called race conditions.  How do we avoid race conditions?  The key to preventing trouble in many other situations involving shared memory, shared files and shared everything is to find some way to prohibit more than one process from reading and writing the shared data at the same time.  We need mutual exclusion ie some way of making sure that when one process is using the shared variable or file, the other process will be excluded from doing the same thing. The problem with Process A and Process B occurred because Process B started using one of the shared variable without allowing Process A to finish with it.

1. PROCESS SYNCHRONIZATION

Process Synchronization means sharing system resources by processes in a such a way that, Concurrent access to shared data is handled thereby minimizing the chance of inconsistent data. Maintaining data consistency demands mechanisms to ensure synchronized execution of cooperating processes.

Process Synchronization was introduced to handle problems that arose while multiple process executions. Some of the problems are discussed below.

Critical Section Problem

A Critical Section is a code segment that accesses shared variables and has to be executed as an atomic action. It means that in a group of cooperating processes, at a given point of time, only one process must be executing its critical section. If any other process also wants to execute its critical section, it must wait until the first one finishes.

Solution to Critical Section Problem

A solution to the critical section problem must satisfy the following three conditions :

1. Mutual Exclusion

Out of a group of cooperating processes, only one process can be in its critical section at a given point of time.

2. Progress

If no process is in its critical section, and if one or more threads want to execute their critical section then any one of these threads must be allowed to get into its critical section.

3. Bounded Waiting

After a process makes a request for getting into its critical section, there is a limit for how many other processes can get into their critical section, before this process’s request is granted. So after the limit is reached, system must grant the process permission to get into its critical section.

Synchronization Hardware

Many systems provide hardware support for critical section code. The critical section problem could be solved easily in a single-processor environment if we could disallow interrupts to occur while a shared variable or resource is being modified.

In this manner, we could be sure that the current sequence of instructions would be allowed to execute in order without pre-emption. Unfortunately, this solution is not feasible in a multiprocessor environment.

Disabling interrupt on a multiprocessor environment can be time consuming as the message is passed to all the processors.

This message transmission lag, delays entry of threads into critical section and the system efficiency decreases.

Mutex Locks

As the synchronization hardware solution is not easy to implement fro everyone, a strict software approach called Mutex Locks was introduced. In this approach, in the entry section of code, a LOCK is acquired over the critical resources modified and used inside critical section, and in the exit section that LOCK is released.

As the resource is locked while a process executes its critical section hence no other process can access it.

Semaphores

In 1965, Dijkstra proposed a new and very significant technique for managing concurrent processes by using the value of a simple integer variable to synchronize the progress of interacting processes. This integer variable is called semaphore. So it is basically a synchronizing tool and is accessed only through two low standard atomic operations, wait and signal designated by P() and V() respectively.

The classical definition of wait and signal are :

• Wait : decrement the value of its argument S as soon as it would become non-negative.
• Signal : increment the value of its argument, S as an individual operation.

Properties of Semaphores

1. Simple
2. Works with many processes
3. Can have many different critical sections with different semaphores
4. Each critical section has unique access semaphores
5. Can permit multiple processes into the critical section at once, if desirable.

Types of Semaphores

Semaphores are mainly of two types:

1. Binary Semaphore

It is a special form of semaphore used for implementing mutual exclusion, hence it is often called Mutex. A binary semaphore is initialized to 1 and only takes the value 0 and 1 during execution of a program.

2. Counting Semaphores

These are used to implement bounded concurrency.

Limitations of Semaphores

1. Priority Inversion is a big limitation os semaphores.
2. Their use is not enforced, but is by convention only.
3. With improper use, a process may block indefinitely. Such a situation is called Deadlock. We will be studying deadlocks in details in coming lessons.

Classical Problem of Synchronization

Following are some of the classical problem faced while process synchronaization in systems where cooperating processes are present.

Bounded Buffer Problem

• This problem is generalised in terms of the Producer-Consumer problem.
• Solution to this problem is, creating two counting semaphores “full” and “empty” to keep track of the current number of full and empty buffers respectively.

The Readers Writers Problem

• In this problem there are some processes(called readers) that only read the shared data, and never change it, and there are other processes(called writers) who may change the data in addition to reading or instead of reading it.
• There are various type of the readers-writers problem, most centred on relative priorities of readers and writers

Dining Philosophers Problem

• The dining philosopher’s problem involves the allocation of limited resources from a group of processes in a deadlock-free and starvation-free manner.
• There are five philosophers sitting around a table, in which there are five chopsticks kept beside them and a bowl of rice in the centre, When a philosopher wants to eat, he uses two chopsticks – one from their left and one from their right. When a philosopher wants to think, he keeps down both chopsticks at their original place.
• DEADLOCK

What is a Deadlock?

Deadlocks are a set of blocked processes each holding a resource and waiting to acquire a resource held by another process.

How to avoid Deadlocks

Deadlocks can be avoided by avoiding at least one of the four conditions, because all this four conditions are required simultaneously to cause deadlock.

1. Mutual Exclusion

Resources shared such as read-only files do not lead to deadlocks but resources, such as printers and tape drives, requires exclusive access by a single process.

2. Hold and Wait

In this condition processes must be prevented from holding one or more resources while simultaneously waiting for one or more others.

3. No Preemption

Preemption of process resource allocations can avoid the condition of deadlocks, where ever possible.

4. Circular Wait

Circular wait can be avoided if we number all resources, and require that processes request resources only in strictly increasing(or decreasing) order.

The basic idea of deadlock avoidance is to grant only those requests for available resources that can not possibly lead to deadlock.  One way to avoid deadlock is for the operating system to deny granting a resource when a process requests it.  The process is blocked even though the resource is available.  In deadlock detection, it is assumed that when a process asks for resources, it asks for all of them at once.  Rather in most systems, resources are requested one at a time.  This means that the system must be able to decide whether granting a resource is safe or not.  The system will only make the allocation if it is safe.  This poses the question of whether there is an algorithm which can be used to make the right choice whenever needed in order to avoid deadlock.  The answer is yes, only if certain information is available in advance.  The main algorithm for this avoidance is based on the concept of safe states.  The algorithm uses the information of D₄

1.         Resources in existence denoted by (E₁, E₂, …E_m)

2.         Resources available denoted by (A₁, A₂, … A_m)

3.         Current allocation matrix denoted by

4.         Request matrix denoted by

In this, n is the number of processes while m is the number of resources.

            From the above,

å Cij + Aj = Ej

This means that when we add all the resources allocated to all the processes to the resources available, it will be equal to the resources that are in existence.  At any point in time, there is a current state consisting of E, A, C and R.  A state is said to be safe if there is at least one way for all users to finish or if there is a scheduling order in which every process can run to completion even if all of them suddenly request their maximum number of resources immediately.  This is shown in the following diagram with the assumption that a total of 10 resources is available.

Process	Allocated Has	Max need			Has	Max. need			Has	Need
A	3	9		A	3	9		A	3	9
B	2	4		B	3	3		B	0	–
C	2	7		C	2	7		C	2	7
A		B		C

            Free: 3                                     Free: 1                         Free: 5

	Has	Need			Has	Need
A	3	9		A	3	9
B	0	–		B	0	–
C	2	7		C	0	–
D		C

            Free: 0                                     Free: 7

From D₁ with seven resources already allocated, only three resources will be free.  The scheduler may decide to run process B until it requires the two resources needed for it to complete.  If the two resources are granted to it, it run to completion and be able to release its 4 resources, plus one remaining after the allocations.  This leaves five resources free for allocation.  Again since Process C has a maximum need of 7 for it to complete and it already has 2, the five free resources can be allocated to it for it to run to completion.  This then makes it to release the 7 resources.  With this seven free and Process A has a max need of 9 for it to run.  A can now get the six it also need to complete.

From the above fig. A is a safe state because by careful scheduling of the resources, we were able to avoid deadlock.

Similarly, if a system has 12 resources and is allocated as follows:

Process	Has	Max
A	8	10
B	2	5
C	1	3
Free: 1

In this eleven of the resources are already allocated and only one is available.  No matter how the scheduler decides to run the processes, there is no guarantee that all three processes will finish.  This is actually an unsafe state. A deadlock could occur if indeed each process needs to request at least for one more resource before releasing any resource to the system.  It is important to note that an unsafe state does not imply the existence, or even the eventual existence of deadlock.  What it implies is simply that some unfortunate sequence of events might lead to a deadlock.

Banker’s Algorithm

            This is a scheduling algorithm that can avoid deadlock due to Dijkstra (1965).  This is modeled on the way a small town banker might deal with a group of customers he has granted some lines of credit.  The algorithm checks to see if granting the request leads to an unsafe state.  If it does the request is denied, if it will lead to a safe state, it is granted.

In this analogy,

Customers are processes,

            Units are resources eg tapes, drives

Banker is the operating system

Banker is the operating system

Customer	Has	Max Need
A	0	6
B	0	5
C	0	4
D	0	7

From this, the total number needed for the four customers is 22 units.  Since the banker knows that not all the customers will need their maximum units immediately, he decides to reserve only ten units to service them.  The customers now go about their business making their loan request as shown below:

Customer	Has	Max
A	1	6
B	1	5
C	2	4
D	4	7

With 2 units still remaining.

This state is safe because with the 2 units left, the banker can delay any request except customer C’s thereby letting C finish and release all four resources.  With the four units, the banker can let either D or B have the necessary unit and so on.

            The banker’s algorithm considers each request as it occurs and sees if granting it leads to a safe state.  If it does, it is granted, if not, it is postponed until later.

            Consider what would happen if a request from B for one more unit were granted .

 We would have the following situation;

E = (6 3 4 2)    =          Total no of each resource

P = (5 3 2 2 )   =          Total no of each assigned

A = ( 1 0 2 0)  =          Total no of each available

            This shows that the total resources the system has for the different resources are as follows;  6 number of R₁, 3 of R₂, 4 of R₃, 2 of R₄.

            Also the total number of resources the system has already assigned for each of the resources are as follows.  Out of the 6 of R₁, 5 of them is already assign.  Similarly, 3 of R₂, 2 of R₃ and 2 of R₄.

            The available resources left to be assigned are 1 of R₁, none of R₂ is left, 2 of R₃ and none for R₄.

            For this the algorithm for checking to see if a state is safe can be stated as follows:

We would have the following situation;

Customer	Has	Max
A	1	6
B	2	5
C	2	4
D	4	7

                                    Free unit = 1

This is an unsafe state.  If all the customers namely A, B, C, D asked for their maximum loans, the banker could not satisfy any of the and there will be deadlock.

The Banker’s algorithm can also be used for multiple resources.

Process	R1	R2	R3	R4		Process	R1	R2	R3	R4
A	3	0	1	1		A	1	1	0	0
B	0	1	0	0		B	0	1	1	2
C	1	1	1	0		C	3	1	0	0
D	1	1	0	1		D	0	0	1	0
E	0	0	0	0		E	2	1	1	0
Resources assigned		Resources still needed

1.         Look for a row R, whose unmet needs are all smaller than or equal to A.  if no such row exists, the system will eventually be deadlock since no process can run to completion.  It is assumed that the processes keep all resources until the exist.

2.         Assume the process of the row chosen requests all resources it needs (which is guaranteed to be possible) and finished.  That process is marked as terminated and all its resources is returned to A.

3.         Step 1 and Step2 are repeated until all the rows are marked terminated.  (This shows that the initial state is safe)  Again if no process is left whose resources needs can be met (this is deadlock).

Handling Deadlock

The above points focus on preventing deadlocks. But what to do once a deadlock has occured. Following three strategies can be used to remove deadlock after its occurrence.

1. Preemption

We can take a resource from one process and give it to other. This will resolve the deadlock situation, but sometimes it does causes problems.

2. Rollback

In situations where deadlock is a real possibility, the system can periodically make a record of the state of each process and when deadlock occurs, roll everything back to the last checkpoint, and restart, but allocating resources differently so that deadlock does not occur.

3. Kill one or more processes

This is the simplest way, but it works.

What is a Livelock?

There is a variant of deadlock called livelock. This is a situation in which two or more processes continuously change their state in response to changes in the other process(es) without doing any useful work. This is similar to deadlock in that no progress is made but differs in that neither process is blocked or waiting for anything.

A human example of livelock would be two people who meet face-to-face in a corridor and each moves aside to let the other pass, but they end up swaying from side to side without making any progress because they always move the same way at the same time.