Interprocess Communication

Interprocess communication (IPC) often occurs between processes and threads. Since multiple processes and threads are accessing shared data and communication with one another, it is important to have a synchronized way to perform such action. This entry is to provide some information about IPC.

Race Condition

Most of the time, IPC requires access to shared data. Race condition occurs when 2 or more processes/threads try to read or write onto the shared data and the outcome of the shared data is depends on who runs precisely when. The outcome is usually indeterministic. For example, 2 processes trying to write to a shared variable. Process A update the X=5, and before Process A managed to use the variable for further calculation, it is being context switched. Now, Process B is allow to update X=6 and carry on with its calculation. When Process A allows to continue, it will see X=6 and the calculation for Process A is wrong.

Critical Section

Race condition bring in the idea of critical section. Critical section is a mutually exclusive section whereby more than 1 process reading or writing the shared data is prohibited. So to avoid Race Condition, the following 4 conditions are needed

1. No 2 processes may be simultaneously inside their critical section
2. No assumptions may be made about speeds or the number of CPU
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

The TSL Instruction

TSL means Test and Set Lock. It is a hardware level instruction that guarantee no other processor can access the memory word until the instruction finished. The instruction is atomic. Atomic means that TSL cannot be interrupted when it is being performed. So, to create a critical section with TSL, an example can be as follows:

enter_region:

TSL REGISTER LOCK -> Set lock to 1 using TSL and put in register

CMP REGISTER #0 -> Was lock 0

JNE enter_region -> if it is not 0, jump to enter_region

RET -> return if 0

leave_region

MOVE LOCK #0 -> store 0 to LOCK

RET -> return

enter_region helps to flag that you are going into critical section and no other processes are able to use that section. However, the downside of this enter_region is if someone is inside the critical section, enter_region will does busy waiting until someone release the LOCK. In general, busy waiting is bad as it wastes CPU cycles.

Semaphores

Semaphores was invented by E. W. Dijkstra. He proposed 2 operations, up and down. It requires a variable initiated with 0. The up operation increment the value of this variable and the down operation decrement the value of this variable. It is important the the up and down operation is atomic. Furthermore, during the down operation, if the value reaches 0, the process will goes into sleep state and wait for the value to increase. When some process perform up operation, it will increase the value. At the same time, it will wake up any processes that are asleep due to their down operation reaches 0.

Normally, semaphores can be implement with short disable of interrupt. Disabling interrupt is generally bad and may cause hardware malfunction if the process forget to re-enable the interrupt. Moreover, disable interrupt will not work for multi-processor. Thus, it is more common to implement semaphores with TSL (similar to the example above).

Since semaphores have a value to be initialized, and if it is initialized to 1, it is a binary semaphores which only allow 1 processes to enter the critical section at any 1 time.

Mutex

Mutex is a simplified version of semaphores. It does not have the ability of counting. It is good when you want to only manage mutual exclusive access to resource. Mutex have 2 states, lock and unlock. Below is an example

mutex_lock:

TSL REGISTER MUTEX -> copy mutex to register and set it to 1

CMP REGISTER #0 -> check if previously 0

JZE ok -> get lock

CALL thread_yield -> give up thread CPU time

JMP mutex_lock -> try acquire mutex lock again

ok: RET -> return

mutex_unlock

MOVE MUTEX #0 -> store 0 to mutex

RET -> return

Comparing to enter_region, instead of busy wait, it calls thread_yield when it fails to acquire the lock. This has the benefit of saving CPU cycles. Also, thread_yield calls thread scheduler in user space. Thus, it does not require kernel call and can be easily implemented at user level.

Note that Mutex is actually binary semaphores. The main different is that Semaphores allow access to the shared resource up to the maximum N initialized while Mutex only allow 1 at any time.

Monitor

It is a high level synchronization primitive. It allows user to provide mutually exclusive access to procedures, variables and data structure. However, monitor is a programming language construct. That is, it is compiler dependent and it is up to the compiler how to interpret monitor entry. Commonly, monitor is similar to mutex and binary semaphore.

When a process enter a critical section and realized that it cannot continue, it will goes into wait state and wait for critical section to be free. When some procedure finish using the critical section, it will wake up sleeping processes by a signal. If you are familiarized with Java, the synchronized keyword is actually a monitor. By now, you may also feel that wake and signal is similar to Java wait and notify. However, wait and notify are subjected to race condition if they are not used within synchronized keyword.

Barrier

Barrier are designed for synchronizing a group of processes. Since different processes may complete their task at different rate, barrier provide a synchronization mechanism for waiting all processes to complete their task before going into next phase.

Imagine that you have a big mathematical problem that have 2 computation phase and want to perform parallel computation with multiprocessors. You can break the first phase of computation into parts and calculated by each processors. However, all these minor part have to be completed before second phase of calculation. This is when barrier is useful.

Reference: Modern Operating System by Andrew S. Tanenbaum