Tuesday, 28 November 2017

Interprocess Communication in Operating Systems - Part 1

Under Interprocess Communication in Operating Systems, we would examine the following sub-topics:

  1. Introduction to Interproces Communication
  2. Race Conditions
  3. Critical Sections
  4. Mutual Exclusion With Busy Waiting
  5. Sleep and Wakeup
  6. Semaphores
  7. Event Counters
  8. Monitors
  9. Message Passing
1. Introduction to Interprocess Communication
Processes and Threads are examined in a different article. From there, we see that processes always need to communicate with other processes. For example, when a use wants to read from a file, the user must tell the process what it wants. Then the file process has to communicate with the disk process to read the required block. Sometimes, the output of the first process must be input into the second process. So we can see that there is need for a systematic way for process to communicate.

2. Race Conditions
In many operating systems, processes that are working together often share some common storage that each one can read and write to.  This shared storage can be in main memory or it may be a shared file or disk. the location of the shared memory does not change the nature  of the communication or the issues that may arise.

Print Spooler Example
Consider a simple but very common example of Interprocess Communication in action. That is the example of the print spooler. When a process needs to print to file, it writes the file name into the spooler directory. Then another process called the printer daemon checks this directory from time to time to see if any file is available to be printed. If there is any, it printed them and then removes an removes them from the directory.
Now assume that the spooler directory has slots numbered 0, 1, 0, 3,... Each slot is capable of holding a filename to be printed. Also assume, there are two shared variables: out which points to the next file in line to be printed and in, which points to the next free slot in the directory. If two processes, A and B, wants to write to the same directory and after reading the in variable,  a situation would arise that may make the values of the variables inconsistent. This situation is called race condition and is defined as a situation where two or more processes are reading and writing on the same shared data.

3. Critical Sections
Critical sections is a concept used a to avoid the race conditions. It applies in situations involving shared resources be it memory, file or variable. To handle the problem of race conditions, there need to be mutual exclusion: that is a way of ensuring that if a particular process is using a shared resource, then the other process would b prevented from using the same resource until the first process completes. So when a process is using a shared resource we say the process is in its critical section

Four Conditions For Avoiding Race Conditions 
No two processes may be in their critical section at the same time
No assumptions should be made about the relative speed or number of processors
No processes running outside its critical section should block other processes
No process should wait too long to enter its critical section

Lets not examine ways to achieve this four conditions. The first one we are going to discuss is Mutual Exclusion with Busy Waiting

Mutual Exclusion wit Busy Waiting
In this method, when one process is busy using a resource or shared memory, and is in its critical section, then no other process will enter its critical section. There are five ways to achieve this:
  • Disabling Interrupts
  • Lock Variables
  • Strict Alternations
  • Peterson's Solution
  • The TSL Instruction
i) Disabling Interrupts
This is the simplest say to achieve mutual exclusion. In this method, any process entering its critical section should disable all interrupts and reenable them when it comes out of its critical section. As such , no  interrupt can occur and the CPU cannot switch to another process until the process completes execution. 
The problem with this method is that is that  it could occur that the CPU interrupt is disabled without being enabled for a very long time. Or what if the interrupts is not enables aging? Then the system crashes.
Another challenge is that when a system have a number of CPUs, then disabling interrupts on one does not affect the other on.

ii) Lock Variables
In this case, a single share variable is maintained called the lock variable. This variable is initially set to 0. When a process is about to enter its critical section, it checks this variable. If the value is 0, then the process sets it to 1 and enters its critical section. If the value is already 1, the process waits until the value becomes 0. 
The challenge is that a process may set this variable to 0. Before it can set it back to 1, a process switching occurs and the value is set to 1. And this can lead to race conditions.

iii) Strict Alternation
This is a third approach for achieving mutual exclusion. In this method, the system maintains a variable called turn which keeps track of which process has the turn to enter its critical section.

iv) Peterson's Solution
This is a software solution to the problem of mutual exclusion proposed by T Decker. While this process does not require strict alternation, the process is very complicated and could hardly be used in practice

v) The TSL Solution
In this solution, methods are used by processes to either enter or leave the critical section. Before entering critical section, a process called a method enter_region. Then after leaving the critical section, the process calls the method leave_region.

vi) Sleep and Wake up
This is a solution that tend to eliminate the problem of busy-waiting.

Continue to Part 2