OS.pdf

Race Condition Is an undesirable situation that occurs when a device or system attempts to perform two or more operations at the same time, but because of the nature of the device or system, the operations must be done in the proper sequence to be done correctly. The Critical Section...

Race Condition Is an undesirable situation that occurs when a device or system attempts to perform two or more operations at the same time, but because of the nature of the device or system, the operations must be done in the proper sequence to be done correctly. The Critical Section Is the part of a program which tries to access shared resources. The critical section cannot be executed by more than one process at the same time; operating system faces the difficulties in allowing and disallowing the processes from entering the critical section. The Critical Section A race condition might occur if two or more processes attempt to use a shared variable at the same time. The solution to this problem involves three aspects. First, the mutual exclusion requirement - should always be met in order to guarantee that only one process may enter its critical section at a time. If a process is currently executing its critical section, any process that attempts to enter its own critical section should wait until the other process leaves its critical section. Second is the progress requirement - The solution must guarantee that if a process wants to enter its critical section and no other process is in its critical section, the process will be able to execute in its critical section. Third is the bounded waiting requirement - The solution must guarantee that processes will not wait for an indefinite amount of time before it can enter its critical section. Software Solutions to the Critical Section Problem Software solutions are additional codes placed before or after the critical section to make sure that race conditions will not occur and the three requirements are met.. SOLUTION 1: The first solution uses a global or shared variable called TurnToEnter. If TurnToEnter = 0, P0 can execute its critical section. P0 changes its value to 1 to indicate that it has finished executing its critical section. If TurnToEnter = 1, P1 can execute its critical section. P1 changes its value to 0 to indicate that it has finished executing its critical section. The figure below illustrates this. SOLUTION TO THE CRITICAL SECTION PROBLEM INVOLVING SEVERAL PROCESSES: The solution to the critical section problem involving several processes is often called Bakery Algorithm. Bakery Algorithm - is one of the simplest known solutions to the mutual exclusion problem for the general case of N process. The algorithm preserves the first come first serve property. Before entering its critical section, the process receives a number. Holder of the smallest number enters the critical section. Hardware Solutions to the Critical Section Problem: Disabling Interrupts This feature enables a process to disable interrupts before it starts modifying a shared variable. If interrupts is disabled, the CPU will not be switched from one process to another. The operating system will then simply allow the process to complete the execution of the critical section even though its time quantum has finished. Upon exiting the critical section, the process will enable interrupts. Although this approach is appreciated for its simplicity, it will not work in a multiprocessor system. Disabling interrupts will only affect the processor that executed the disabled interrupt instruction. Other processors can still access/update the shared resources. On the other hand, disabling the interrupts of all the processors may take too much time. Special Hardware Instructions There are special machine instructions that will allow a process to modify a variable or memory location atomically. This means that if a process executes an atomic operation, no other process will be able to preempt it. Semaphores A semaphore is a tool used to solve more complex synchronization problems and does not use busy waiting. It is a special integer variable that is protected. Only the following operations can access it once initialized. Classic Synchronization Problems These two classic synchronization problems represent theoretical scenarios that aim to show typical synchronization problems and their possible solutions. The solution to these problems will be using semaphores. The Dining Philosophers Problem The Readers and Writers Problem  However, this solution may lead to starvation. What if all philosophers happen to pick up their left forks at the same time? When all the philosophers execute the wait (Right Fork) operation, all of them will be stuck in their while loop. A philosopher will not give up his left fork until he picks up the right fork. This event is called a deadlock. Deadlock - Happens when two or more processes are waiting for resources held by each other before it can proceed with its execution. The Readers and Writers Problem Another classic synchronization problem is the readers and writers problem, which represents access to a database. Readers are processes that only examine or read data stored in a database. Several readers are allowed simultaneous access to the same database file since they do not change any data. Writers are processes that modify or update the data. However, a writer must have exclusive access to the database. If a reader is currently reading data from the database, a writer cannot enter. If a writer is currently accessing the database, other writers (and also readers) are not allowed to access the database. This is strictly followed to maintain data consistency and integrity. The solution must follow these restrictions.  A solution that favors the writer processes is called writers-preference solution. It still does not grant a writer access to the database if there are readers or writers already in the database. However, a reader is denied access to the database if a writer is currently accessing the database or if there is a waiting writer process (even if other reader processes are already in the database). If it happens that a steady stream of incoming writer processes wants to access the database, this may cause the starvation of reader processes.  This solution is often called readers-preference solution. If it happens that a steady stream of incoming reader processes wants to access the database, this may cause the starvation of writer processes. Writer processes will have to wait for an indefinite period of time before it can access the database.