Disabling interrupts
-> In this mechanism a process disables interrupts before entering the critical region and enables the interrupt immediately after exiting the critical region.
while( true )
{
< disable interrupts >;
< critical region >;
< enable interrupts >;
< remainder section>;
}
-> Mutual exclusion is achieved because with interrupts disabled, no clock interrupts can occur.
-> The CPU is only switched from process to process as a result of clock or other interrupts, and with interrupts turned off the CPU will not be switched to another process.
-> Thus, once a process has disabled interrupts, it can examine and update the shared memory without fear that any other process will intervene.
-> This approach is generally unattractive because it is unwise to give user processes the power to turn off interrupts.
-> Suppose that one of them did it and never turned them on again? That could be the end of the system.
-> Furthermore if the system is a multiprocessor, with two or more CPUs, disabling interrupts affects only the CPU that executed the disable instruction. The other ones will continue running and can access the shared memory.
-> On the other hand, it is frequently convenient for the kernel itself to disable interrupts for a few instructions while it is updating variables or lists.
-> If an interrupt occurred while the list of ready processes, for example, was in an inconsistent state, race conditions could occur.
-> The conclusion is: disabling interrupts is often a useful technique within the operating system itself but is not appropriate as a general mutual exclusion mechanism for user processes.
Shared lock variable:
-> In this mechanism there is a shared variable lock having value 0 or 1.
-> Before entering in to critical region a process check a shared variable lock’s value.
-> If the value of lock is 0 then set it to 1 before entering the critical region and enters into critical section and set it to 0 immediately after leaving the critical section.
While (true)
{
< set shared variable to 1>;
< critical section >;
< set shared variable to 0>;
< remainder section>;
}
-> If it is 1, means some other process is inside the critical section so, the process requesting to enter the critical region will have to wait until it becomes zero.
-> This mechanism suffers the same problem (race condition). If process P0 sees the value of lock variable 0 and before it can set it to 1, context switching occurs.
-> Now process P1 runs and finds value of lock variable 0, so it sets value to 1, enters critical region.
-> At the same point of time P0 resumes, sets the value of lock variable to 1, enters critical region.
-> Now two processes are in their critical regions accessing the same shared memory, which violates the mutual exclusion condition.
Strict Alteration:
-> In this proposed solution, the integer variable 'turn' keeps track of whose turn is to enter the critical section.
-> Initially turn=0. Process 1 inspects turn, finds it to be 0, and enters in its critical section. Process 2 also finds it to be 0 and therefore sits in a loop continually testing 'turn' to see when it becomes 1.
-> Continuously testing a variable waiting for some value to appear is called the busy waiting.
-> When process 1 exit from critical region it set turn to 1 and now process can find it to be 1 and enters in to critical region.
-> In this way both the process get alternate turn to enter in critical region.
-> Taking turns is not a good idea when one of the processes is much slower than the other.
-> Consider the following situation for two processes P0 and P1 P0 leaves its critical region, set turn to 1, enters non critical region.
-> P1 enters and finishes its critical region, set turn to 0.
-> Now both P0 and P1 in non-critical region.
-> P0 finishes non critical region, enters critical region again, and leaves this region, set turn to 1.
-> P0 and P1 are now in non-critical region.
-> P0 finishes non critical region but cannot enter its critical region because turn = 1 and it is turn of P1 to enter the critical section.
-> Hence, P0 will be blocked by a process P1 which is not in critical region. This violates one of the conditions of mutual exclusion.
-> It wastes CPU time, so we should avoid busy waiting as much as we can.
-> Can be used only when the waiting period is expected to be short.
TSL (Test and Set Lock) Instruction
-> Test and Set Lock that works as follows. 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 no other processor can access the memory word until the instruction is finished.
-> The CPU executing the TSL instruction locks the memory bus to prohibit other CPUs from accessing memory until it is done.
-> The solution using TSL is given above.
-> There is a four-instruction subroutine in a typical assembly language code.
-> The first instruction copies the old value of lock to the register and then sets lock to 1.
-> Then the old value is compared with 0. If it is nonzero, the lock was already set, so the program just goes back to the beginning and tests it again.
-> Sooner or later it will become 0 (when the process currently in its critical region is done with its critical region), and the subroutine returns, with the lock set.
-> Clearing the lock is simple. The program just stores a 0 in lock. No special instructions are needed.
-> One solution to the critical region problem is now straightforward.
-> Before entering its critical region, a process calls enter_region, which does busy waiting until the lock is free; then it acquires the lock and returns.
-> Whenever the process wants to leave critical region, it calls leave_region, which stores a 0 in lock.
-> As with all solutions based on critical regions, the processes must call enter_region and leave_region at the correct times for the method to work.
Exchange Instruction
-> An alternative instruction to TSL is XCHG.
-> Move value 1 to CPU register A (A = lock)
-> Exchange the value of CPU register and lock variable.
-> How does XCHG solve problem?
-> If any process wants to enter critical region, it calls the procedure enter_region.
-> Process executes XCHG RX, lock in order to gain access. If it finds lock =0 then it proceeds and enters in critical region (and resets lock to 1), but if it finds lock = 1 then it loops back and will keep doing so until lock =0. Other processes will see lock = 1 and similarly loop.
-> When process leaves it sets lock = 0 by calling leave_region, thereby allowing another process to enter.
Peterson’s Solution
-> By combining the idea of taking turns with the idea of lock variables and warning variables, Peterson discovered a much simpler way to achieve mutual exclusion.
-> This algorithm consists of two procedures written in ANSI C as shown below.
-> Before using the shared variables (i.e., before entering its critical region), each process calls procedure enter_region with its own process number, 0 or 1, as parameter.
-> This call will cause it to wait, if needed, until it is safe to enter critical region.
-> After it has finished with the shared variables, the process calls leave_region to indicate that it is done and to allow the other process to enter, if it so desires.
-> Let us see how this solution works. Initially neither process is in its critical region.
-> Now process 0 calls enter region.
-> It indicates its interest by setting its array element and sets turn to 0.
-> Since process 1 is not interested, enter_region returns immediately. If process 1 now calls enter_region, it will be blocked there until interested[0] goes to FALSE, an event that only happens when process 0 calls leave_region to exit the critical region.
-> Now consider the case that both processes call enter_region almost simultaneously.
-> Both will store their process number in turn. Whichever store is done last is the one that counts; the first one is overwritten and lost.
-> Suppose that process 1 stores last, so turn is 1. When both processes come to the while statement, process 0 executes it zero times and enters its critical region.
-> Process 1 loops and does not enter its critical region until process 0 exits its critical region.
Post a Comment