Operating System — Inter-process Communication (IPC)

Understand IPC in just 3 minutes

Inter-process communication (IPC) is simply a mechanism for the processes to manage shared data. The most commonly used object to share data between two processes is pipe.

What’s a pipe?

Pipe is a shared object between two processes which data from one to another. It is unidirectional, which means data can only flow from left to right.

Example of Inter-process Communication

Deep down in the kernal, the pipe() system call creates a piece of shared FIFO queue in the kernel space.

In this example, the “ls” process is a producer and it writes data into the pipe. The “less” process is a consumer and it reads the data from the pipe.

However, you may realise that there could be a problem. The buffer’s size is limited. What if “ls” produces too fast while “less” consumes too slow?

It’s called producer-consumer problem and it’s a synchronization problem. Producer-consumer problem is one of the classic IPC problems and I will talk about it later.

As user space memory is not sharable between processes even they are parent and child, shared objects are therefore provided at the kernel level. There are other IPC problems beyond pipe. You may have to use shared memory and shared files directly. The concurrent access may cause unpredictable outcomes and Kernel won’t help you to take care of it.

Race condition

When processes share a same memory together, we could not skip talking about race condition. It could become a bug if we don’t take a good care of it.

A race condition means the outcome of an execution depends on a particular order in which the shared resource is accessed. It may happen when:

1. there are shared objects
2. there are multiple processes
3. the processes are concurrently accessing shared objects

Race condition is always a nightmare as it’s hard to debug.

How to resolve race condition on a shared object?

Mutual Exclusion

Mutual Exclusion

When I’m playing with the shared memory, no one could touch it. A set of processes would not have the problem of race condition if mutual exclusion is guaranteed.

Bear in mind. Shared object is still sharable, but:
- the shared object could not be shared at the same time
- it has to be shared one by one

To Achieve mutual exclusion, the program code could be divided into 3 sections:

1. Section Entry: start of critical section. Telling other process that the shared memory is in used.
2. Critical Section: code segment that is accessing the shared object. It should as tight as possible.
3. Section Exit: end of critical section. Telling other process that the shared memory is now free.

In short, mutual exclusion is achieved by blocking other processes from entering a critical section if a process is already accessing the critical section.

How to achieve mutual exclusion by programming?

Spin lock

It is to loop on another shared object, “turn”, to detect the status of other processes.

For example, Process A:

while (TRUE) {
  while( turn != 0 ) /* busy waiting */
  ----------------------
  critical_section();
  ----------------------  
  
  turn = 1;
  
  remainder_section();
}

Process B:

while (TRUE) {
  while( turn != 1) /* busy waiting */
----------------------
  critical_section();
----------------------  
  
  turn = 0;
  
  remainder_section();
}

Example of spin lock

Peterson’s solution

Peterson’s solution is similar to spin lock. Apart from “turn”, one more extra shared object, “interested”, is used. If I don’t show interest, I’ll let other processes to use the shared memory. If all processes both show interest, all the processes have to take turns.

For example, Process A:

interested[process] = TRUE;
while( turn == process && interested[other process] == TRUE )
/* busy waiting */
----------------------
  critical_section();
----------------------  
  
  interested[process] = FALSE;
  
  remainder_section();
}

Process B (same as Process A):

interested[process] = TRUE;
while( turn == process && interested[other process] == TRUE )
/* busy waiting */
----------------------
  critical_section();
----------------------  
  
  interested[process] = FALSE;
  
  remainder_section();
}

However, mutual exclusion has one obvious disadvantage. It hinders the performance of parallel computations.

Next Steps

If you’re reading this line, congratulations!!! You made it. You have learnt the basics of IPC and how to resolve the race condition of processes. There are some interesting IPC problems like producer-consumer problem and dining philosopher problem which definitely worth a mention. Hopefully I can discuss some of them in the future.

Feel free to check other articles about operating system below:

Overview of Operating System

To know more about my backend learning path, check out my journey here:

My Backend Developer Learning Journey 我的後端學習之旅