Notes for CIS345 - Class day 8 - Tanenbaum Chapter 2 - Processes and Threads 2.3 Interprocess Communication IPC is needed to to share communications between processes without interrupts. 2.3.1 Race Condition Processes working together may share common storage that each can read/write. Example: Spooler directory is written to when processes wish to print, and a Printer daemon checks periodically for files to be printed. Process A needs a print slot, gets 7, and is interrupted. Process B needs a print slot, gets 7, and writes to slot 7. Process A returns and writes to slot 7, overwriting process B's info. Daemon does not recognize any problem - very hard bug to find. 2.3.2 Critical Sections To avoid problems with shared resources, some form of mutual exclusion needed. Critical section of a program is where operations can lead to race conditions. Four conditions needed to have a good solution for process cooperation: 1. No two processes may be simultaneously inside their critical sections. 2. No assumptions may be made about the speeds or the number of CPUs. 3. No process running outside its critical section may block other processes. 4. No process should have to wait forever to enter its critical section. 2.3.3 Mutual Exclusion with Busy Waiting Disabling interrupts is a simple solution, but not practical for user space. If user process turns off interrupts, what if it never turned them on again? If two or more CPUs, it only affects one CPU, other could access shared area. Kernel may, however, want to disable interrupts for a few instructions. End result: Disabling interrupts is OK for kernel, not good for user procs. Lock Variable is a single shared variable, with the initial value of 0. When process wants to enter its critical section, it tests lock variable. If lock is 0, set to 1 and enter area. If lock is 1, wait until it becomes 0. This solution has the same basic problem as the disabling interrupts solution. If one process tests, finds 0, is then interrupted, second tests, finds 0, sets to 1, enters critical area, and returns control to first process, which sets lock to 1 and enters its critical area at the same time as second proc. Strict Alternation while (TRUE) { while (TRUE) { while (turn != 0) /* wait */ ; while (turn != 1) /* wait */ ; critical_section(); critical_section(); turn = 1; turn = 0; noncritical_section; noncritical_section; } } Continuously testing a variable for some value to appear called Busy Waiting. If wait is expected to be short, busy waiting is used in form of a spin lock. Taking turns is not a good idea when one process is slower than the other. Although this solution does avoid all races, it is not a serious solution. #define FALSE 0 // Peterson's solution combines taking #define TRUE 1 // turns with lock and warning variables #define N 2 // Number of processes is two int turn; // Whose turn is it, 0 or 1? int interested(N); // All values initially 0 (FALSE) void enter_region(int process) { // Enter critical region, process is 0 or 1 int other; // The number of the other process other = 1 - process; // If other = 1, process = 0 and vice/versa interested[process] = TRUE; // Show that this process is interested turn = process; // Set flag same as the interested process while (turn == process && interested[other] == TRUE); // Loser waits here } void leave_region(int process) { // Leave critical region, process is 0 or 1 interested[process] = FALSE; // Indicate departure from critical region } // Solution correct; requires busy waiting Notes for CIS345 - Class day 8 - Tanenbaum Chapter 2 - Processes and Threads The TSL (Test and Set Lock) performs test/set/lock as an integral operation. It requires help from the hardware to lock out other CPUs from the memory bus. The solution using TSL is correct, but does require the use of busy waiting. 2.3.4 Sleep and Wakeup Peterson's solution and TSL both use busy waiting, which wastes CPU time. Potential also for priority inversion if high priority task uses busy waiting. Sleep and wakeup are system calls that block if busy instead of busy waiting. Sleep blocks until another process wakes it. Wakeup awakens sleeping process. The Producer-Consumer Problem Producer-consumer (also known as bounded-buffer) problem is a useful example. Producer puts items into the buffer, consumer removes items from the buffer. If buffer full, producer must wait (sleep). If buffer empty, consumer waits. Code for producer generates an item, then checks to see if count is maximum. If so, producer goes to sleep. If not, item is inserted into buffer, count is increased by one, and a wakeup is issued to the consumer if count is now 1. Consumer code checks for empty buffer, going to sleep if nothing to consume. Otherwise, item is removed from the buffer, count decreased by 1, and producer is sent a wakeup signal if count is now maximum - 1, then item is consumed. Race conditions still occur because access to count variable is unconstrained. If consumer is interrupted just after reading count and finding it to be zero, producer might also read count as zero, put an item in buffer and send wakeup. Interrupted consumer is not yet logically asleep, so wakeup signal is lost. Consumer reads zero when next run and goes to sleep. Producer fills up buffer eventually, and it goes to sleep also, having never woken up the consumer. Quick fix adds wakeup waiting bit to hold wakeup sent to nonsleeping process. This works for two processes, but may require additional wakeup bits for > 2. 2.3.5 Semaphores Semaphore is a new variable type proposed by E.W. Dijkstra in 1965 with value 0 if no wakeups pending, or some positive value if 1 or more wakeups pending. Semaphore operations called DOWN and UP (generalizations of SLEEP and WAKEUP). DOWN checks to see if value is > 0. If so, it decrements value and continue. If the value is 0, the process is put to sleep to wait for an UP semaphore. Checking, changing and possibly going to sleep is done as one atomic action. The UP operation simply increments the value of the semaphore addressed. If one or more processes were sleeping on that semaphore, one is chosen by the system and is allowed to complete its DOWN. Process never blocks on UP. Semaphore operations also called (P)roberen for DOWN and (V)erhogen for UP. Solving the Producer-Consumer Problem using Semaphores Semaphores solve the lost-wakeup problem, but they must be indivisible. OS disables all interrupts while it tests, updates and puts process to sleep. Multiple CPUs should protect the semaphore with lock variable and TSL. Figure 2-24 solution uses three semaphores: full=0, empty=#slots, mutex=1. Semaphores set to 1 and used for mutual exclusion called Binary Semaphores. To hide interrupts, have semaphore associated with each I/O device set to 0. After starting I/O device, manager does a DOWN on the process (stopping it). When interrupt comes in, interrupt handler does an UP on semaphore to run it. One use of semaphores is for mutual exclusion (mutex) to guarantee that only one process is in its critical section at a time; otherwise chaos results. Another use is for synchronization. Full and empty semaphores are used to ensure that certain event sequences do or do not occur on full/empty buffer. 2.3.6 Mutexes Simplified version of semaphore is a mutex, with binary values of 0/1 only. Mutexes manage mutual exclusion to shared resources; useful in threaded code. Mutex can be locked or unlocked, and are easily implemented using TSL code. Mutex lock is particularly useful for threads because it is not busy waiting. If one thread goes into busy waiting loop, another thread cannot execute code. To use Peterson's and semaphores, processes must have access to shared memory. Variables can be stored in kernel, common address space, or in a shared file.