IPC

IPC

1. Race conditions

   • Critical Regions
   • mutual exclusion
     • Make sure that if one process is using a shared variable or file, the other processes will be excluded from doing the same thing.
     • No two processes may be simultaneously inside their critical regions
     • No assumption may be made about speeds or the number of CPUs.
     • No process running outside its critical region may block any process.
     • No process should have to wait forever to enter its critical region.

2. Busy waiting

   • What these solutions do is this: when a process wants to enter its critical region, it checks to see if the entry is allowed. If it is not, the process just sits in a tight loop waiting until it is.
   • Disadvantages: 1.Wast CPU time. 2.Priority inversion problem. 
   • Disable interrupts
     • Disadvantages: 1. One process can disable interrupt forever. 2. In multiprocessor system, it disables one CPU without affecting others.
   • Lock Variables
     • Setting a lock variable can have race condition if process A got interrupt before updating it and process B tested the variable.
   • Strict Alternation
     • It violates condition 3.
   • spin lock
   • Peterson's solution
     • (Needs to understand and study the code)
   • TSL instruction
     • It reads the contents of the memory word lock into register RX and then stores a nonzero value at the memory address lock.
     • The operations of reading the word and storing into it are guaranteed to be indivisible- on other processor can access the memory word until the instruction is finished. It is different from disable interrupts.

3. sleep/wakeup

   • It is interprocess communication primitives that blocks instead of wasting the CPU time when they are not allowed to enter their critical regions. One of the simplest pair (sleep) and (wakeup). Sleep is a system call that causes the caller to block, be suspended until another process wakes it up. The wakeup call has one parameter, the process to be awakened. 
   • If processes have disjoint address spaces, how can they share the turn variable in Peterson or semaphores or a common buffer? 1.Some of the shared data structure -semaphores- can be stored in the kernel and accessed only by means of system calls.  2.Most modern OS offer a way for processes to share some portion of their address space with other processes. 3.Worst case, a shared file can be used.
   • Semaphores
     • Integer variable to count the number of wakeups saved for future use. It could have the value 0, indicating that no wakeups were save, or some positive value if one or more wakeups were pending. 
     • The operations down/up are atomic action. It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has completed or blocked. Operating system can briefly disable all the interrupts while testing the semaphore, since its actions takes few instructions, no harm is done in disabling interrupts. If multiple CPUs are being used, each semaphore should be protected by a lock variable, with the TSL or XCHG instructions.
     • If the downs in the producer's code were reversed in order, so mutex was decremented before empty instead of after it. Both producer and consumer will be blocked (Dead Lock)
     • up
       • Increment the semaphore or wakeup one sleeping process and keep the semaphore 0.
     • down
       • If semaphore > 0, it decrements its value by one and continue, else if it is 0, it puts the process to sleep without completing the process.
     • binary semaphore
       • Mutex is used for mutual exclusion. It is designed to guarantee that only one process at a time will be reading or writing the buffer and the associated variables.  full and empty are used for synchronization. They are needed to guarantee that certain event sequences do or do not occur. In this case, they ensure that the producer stops running when the buffer is full, and that the consumer stops running when it is empty.
     • Mutexes
       • Mutexes are good only for managing mutual exclusion to some shared resource or piece of code. It is very useful in thread packages that are implemented entirely in user space.
       • Calling thread_yield means the caller thread gives up the CPU to another thread.  When it runs the next time, it tests the lock again. 
     • Condition Variables
       • Condition variables allow threads to block due to some condition not being met.
       • Condition variables unlike semaphores have no memory. If a signal is sent to a condition variable on which no thread is waiting, the signal is lost.
   • producer-consumer
     • Race condition: If the consumer read counter as 0 but before going to sleep, CPU switch happen and producer increment the items/counter by one, then it calls wakeup assuming consumer is asleep.  When the switch returns back to the consumer it will go to sleep since counter is 0, then the producer will keep adding items until it is full and sleep also. Both will sleep forever.  
     • lost wakeup signal
       • wakeup waiting bit
         • When a wakeup is sent to a process that is still awake, this bit is set. Later, when the process tries to sleep, if the wakeup waiting bit is on, it will be turned off, but the process will stay awake.

4. Monitor

   • Monitor is a collection of procedures, variables and data structures that are all grouped together in a special kind of module or package.
   • Processes may call the procedures in a monitor whenever they want to, but they cannot directly access the monitor's internal data structures from procedures declared outside the monitor.
   • Condition Variables
     • Although monitors provide an easy way to achieve mutual exclusion, that is not enough. We also need a way for processes to block when they cannot proceed. (Condition Variables) 
     • CV have two operations on them (signal) and (wait).
     • wait and signal look similar to sleep and wakeup, they are very similar, but with one crucial difference: sleep and wakeup failed because while one process was trying to go to sleep, the other one was trying to wake it up.  With monitors, that cannot happen. The automatic mutual exclusion on monitor procedures guarantees that if the producer inside a monitor procedure discovers that the buffer is full, it will be able to complete wait operation without having to worry about the possibility that the scheduler may switch to the consumer just before wait completes. The consumer will not even be let into the monitor at all until wait is finished and the producer has been marked as no longer runnable.
     • wait
       • This action causes the calling process to block.  It also allows another process that had been previously prohibited from entering the monitor to enter now. 
     • signal
       • It wake up its sleeping partner on the condition variable that its partner is waiting on. To avoid having tow active processes in the monitor at the same time, we need a rule to tell what happens after a (signal) Hoare: Letting the newly awakened process run, suspending the other one.
       • Brinch Hansen: Finessing the problem by requiring that a process doing a signal must exit the monitor immediately. In other words, a signal statement may appear only as the final statement in a monitor procedure.
       • Third proposal: Le the signaler continue to run and allow the waiting process to start running only after signaler has exited the monitor.