Back to Home

Top 10 List of Week 07

1. Race Conditions.
   Last week we have learned about concurrency, in which multiple sequences of instructions are executed simulataneously. While this is very efficient and useful in the context of Operating Systems, there are problems that may appear from parallel execution. The Race Condition is one such issue, in which multiple processes are running in parallel and they need access to a certain data that is shared between the multiple processes. The final result will then depend on which process is completed first. Since the processes are executed conccurently, the process that will be completed first is random every execution cycle, therefore resulting in the different final result everytime. This is obviously an undesirable situation that has to be resolved.

2. Critical Section
   Critical Sections are certain parts of your written code that involves accessing shared data that may be manipulated. Of course, this may result in the previously mentioned Race Conditions (which we do not want). Therefore, we have to make sure that these Critical Sections are properly equipped to prevent undesirable conditions that may result in corrupted values of your shared data. To do that, the critical sections have to fulfill three criterias:
   • Mutual Exclusion, which means that only a single process is allowed to execute the critical section at any given time.
   • Progress, when the critical sections is free, meaning it is not being executed by any process, the next process to enter the critical section is cooperatively determined.
   • Bounded Waiting, any process still waiting to enter the critical section is guaranteed to enter before its waiting time limit is up.
3. Critical Section Solutions.
   There are differing solutions to prevent Race Conditions from occuring, for example:
   • TestAndSet (Hardware Solution), in which a ‘shared lock’ is created. This shared lock may only have two different values, which are either 0 or 1. Each time a process would like to enter the critical section, a separate process will check the value of the lock. When a process enters the critical section, the lock value becomes 1. When the lock is activated (value is 1), no other process may enter the critical section. When the process exits the critical section, the lock becomes free (value is 0), and some other process may enter the critical section.
     
   • Semaphores (int variable), such as:
     • Binary Semaphores, in which the semaphore may only have two different values, either 0 or 1. The semaphore is shared between all processes and works in the same way as ‘shared lock’, therefore it can also be called the mutex lock.
     • Counting Semaphores, in which the semaphore can be any whole numbers. The values are used to limit access to a shared resource. When a resource can only allow 5 processes to simultaneously access it, the semaphore will first start at 5. Each time a process accesses it, the semaphore is decremented by 1 until it reaches 0. When the semaphore is 0, then the resource is locked until a process exits from it, incrementing the value to 1.
   • Peterson’s Solution (Software Solution), will contain two shared variable, a boolean array flag (size 2), and an integer to show which process may enter the critical section. The basic idea of this solution is to modify the flag and integer values each time a process enters and exits the critical section. When a process enters, the flag is set to True, and the integer takes the index of the second process. Therefore, the second process will execute first before the first process which is still waiting. When the second process is finished, the first process will then enter the critical section. When it is done executing, the flag is set back to False.

4. Deadlocks.
   Deadlocks are events in which the OS is stuck in a permanent waiting state. For example, imagine there are two processes running at the same time. Process 1 is currently running while accessing Resource 1. Process 2 is currently running while accessing Resource 2. To complete it’s instruction sequence, Process 1 needs to access Resource 2, which is currently occupied by Process 2. On the other hand, Process 2 needs to access Resource 1, which is currently occupied by Process 1. Since no process can continue due to the resources being occupied, the OS is in a deadlock state.

5. POSIX API.
   The POSIX (Portable Operating System Interface for UNIX) API is the standard family specified by the IEEE. It is mainly used to make uniform the programs that rely on POSIX standards, therefore simplifying the process of porting the program over into other UNIX Operating Systems (i.e. from Linux to MacOSX). The POSIX API also provides us with the standard forms of mutex locks, semaphores, and condition variables as specified in the above points. This means that any process can easily access the standard semaphores by referring to the provided named semaphores.

6. Monitors.
   Monitors, in the context of Process Synchronization, are an ADT (Abstract Data Type) for handling resources that are shared. They are used to provide a high-level form of process synchronization. The basic syntax for Monitor is wait(), which is used to make process wait for certain conditions to be fulfilled, and signal(), which is used to signal one another when the conditions have been met.

7. Coffman Conditions.
   Coffman Conditions are four conditions that have to be met before the deadlock event occurs.
   • Mutual Exclusion, meaning that there will be a resource that can only be accessed by a single process at a time.
   • Hold and Wait, meaning that there will be a process that can access multiple resources and can request to access more.
   • No Preemption, meaning that a resource cannot be forced to release a resource before it is done.
   • Circular Wait, meaning that a process will wait for the resource accessed by another process and that process is waiting for another resource held by the first process. This creates a circular loop of waiting for resources.
     Only when these four conditions are met will a deadlock occur.

8. Deadlock Detection.
   Deadlocks can be detected by a resource scheduler. The role of a resource scheduler in this case is to manage all resources and keep track of which resources are being allocated to which processes. The scheduler can then detect if the four Coffman conditions are met and determine if the set of processes is stuck in a deadlocked state. From here, the deadlock can be resolved by either killing all processes involved (not a good solution), or preempting other resources from other processes until the deadlock is resolved.

9. Preventing Deadlocks.
   Deadlocks can be prevented by implementing the Banker’s algorithm. What this algorithm does is to perform pre-checks before any resource allocation. If the pre-check detects that a deadlock may occur, then the corresponding processes will not be allowed to execute by not allocating resources to them.

10. Alternatives for Deadlock Preventions.
    In systems such as Windows and UNIX, the deadlock is allowed to occur if and only if it is very rare. What this means is that the deadlock is ignored since it rarely happens anyways. In such cases, the deadlock happens, is ignored, and then the system is rebooted.