os202

Mohammad Saddam Mashuri's OS202

Project maintained by saddamonpc Hosted on GitHub Pages — Theme by mattgraham

HOME

Top 10 List of Week 07

Why hello there! I’m grateful you have the time to read my top 10 of week 7 of this course. This week topic is Synchronization & Deadlock. Please note that this top 10 are my opinion and may not be the same with yours.

The way I grade this top 10 list are by 3 categories:

* how important it is,

* how simple it is,

* and how relevant the topic is to the operating system course.

More coding involved this week. I knew this is going to be harder, and the obscurity of the syntax of the C language doesn’t help either. Nevertheless, this course is important for getting better at computer science.

Please enjoy your stay here, and good luck to my other mates doing this course!

  1. Process Synchronization
    Like I usually say, fundamentals are important. We first need to understand why do we need to synchronize processes and such. Process Synchronization is the activity of coordinating the execution of processes such that no two processes can have access to the same shared data and resources. Synchronizing processes are important as when several threads share data, changes made by one process may override changes made by another process running parallel, which results in inconsistent data. Process synchronization prevents this.

  2. Support for Synchronization, supported by point no. 8.
    Although support for synchronization in modern computer architectures is not guaranteed for software-based solutions (like Peterson’s Solution in point no. 8), systems provide hardware support for synchronization, such as Uniprocesor systems (they disable interrupts) and Multiprocessor systems. There are three forms of hardware support:
    • Memory barriers
      Memory barriers guarantees that a computer architecture makes to application programs. Memory barriers may either be:
      - Strongly ordered (Memory modification of one processor is immediately visible to all other processors).
      - Weakly ordered (Memory modification of one processor is not immediately visible to all other processors).
    • Hardware instructions
      Special hardware instructions that allow us to either test and modify the content of a word, or swap the contents of two words atomically (without interruptions).
    • Atomic variables
      Updates or provide atomic operations on basic data types such as integers and booleans.

  3. Semaphores
    Very important for understanding how to solve the assignment. A semaphore is an object with an integer value that we can manipulate with two routines; in the POSIX standard, these routines are sem_wait() and sem_post(). sem_wait() will decrement the value of the semaphore, while sem_post() increments the value of the semaphore.

  4. Deadlocks
    Deadlocks may happen when a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. Deadlocks occurs if and only if, Mutual Exclusion, Hold and Wait, No preemption, and Circular Wait occurs. This is discussed in the next next point.

  5. Deadlock Prevention
    Preventing a deadlock can be done by ensuring that at least one of the conditions below cannot hold:
    • Mutual Exclusion
      One or more than one resource are non-shareable (Only one process can use at a time). Unfortunately, we cannot prevent deadlocks by denying the mutual-exclusion condition, because some resources are intrinsically non-shareable.
    • Hold and Wait
      A process is holding at least one resource and waiting for resources. To prevent this from happening, we must guarantee that whenever a thread requests a resource, it does not hold any other resource.
    • No Preemption
      A resource cannot be taken from a process unless the process releases the resource. To make sure that the condition does not hold, we can just make the resources to be implicitly released.
    • Circular Wait
      A set of processes are waiting for each other in circular form. Thankfully, a practical solution to invalidate this condition exists. One way is to impose a total ordering of all resource types and to require that each thread requests resources in an increasing order of enumeration.

  6. Deadlock Avoidance: Banker’s Algorithm
    Although deadlocks can be prevented, they do have side effects. Thankfully, we can avoid deadlocks by using the Banker’s algorithm. Banker’s Algorithm is resource allocation and deadlock avoidance algorithm which test all the request made by processes for resources, it checks for the safe state, if after granting request system remains in the safe state it allows the request and if there is no safe state it doesn’t allow the request made by the process.

  7. Recovery from Deadlock
    When a deadlock occurred in a system, the system must recover from that deadlock. There are two approaches in recovering from a deadlock:
    • Process and Thread Termination
      To eliminate the deadlock, we can simply kill one or more processes. For this, we use two methods:
      - Abort all the Deadlocked Processes (Aborting all the processes will break the deadlock, but at great expense. The deadlocked processes may have computed for a long time, and the results of these partial computations must be discarded and probably will have to be recomputed later).
      - Abort one process at a time until deadlock is eliminated (This method incurs considerable overhead, since after each process is aborted, a deadlock-detection algorithm must be invoked to determine whether any processes are still deadlocked).
    • Resource Preemption
      To eliminate deadlocks using resource preemption, we preempt some resources from processes and give those resources to other processes. This method will raise three issues:
      - Selecting a victim (Determine which resources and / or processes are to be preempted and also the order to minimize the cost).
      - Rollback (Determine what should be done with the processes from which resources are preempted. One idea is to abort the process and restart it).
      - Starvation (In a system, it may happen that same process is always picked as a victim. As a result, that process will never complete its designated task. This situation is called Starvation and must be avoided. One solution is that a process must be picked as a victim only a finite number of times).

  8. The Critical-Section Problem: Peterson’s Solution, supports point no. 2
    A quick note. I should put this higher, but I can’t help but think that deadlocks are also crucial to understand the synchronization problem and this sub-topic is quite complicated, which results in a lower rank. It is recommended that you read the book to understand this completely. Nevertheless this sub-topic supports point no. 2 which boosts how important this sub-topic is.

    Alright, back to it. Each process in a system has a segment of code, called a critical section, in which the process may be accessing and updating data that is shared with at least on other processes. The critical-section problem is to design a protocol that the processes can use to synchronize their activity so as to cooperatively share data. A classic software-based solution to the critical-solution problem known as Peterson’s solution. Peterson’s solution provides a good algorithmic description of solving the critical-section problem and illustrates some of the complexities involved in designing software that addresses the requirements of mutual exclusion, progress, and bounded waiting.

  9. Monitors
    This is deprecated, but nonetheless it is still important. A monitor is a synchronization construct that allows threads to have mutual exclusion among the processes. In simpler words, monitors helps in controlling shared data access.

  10. POSIX Synchronization
    The POSIX API is available for programmers at the user level to help provide multiple flows of execution within a process. Tools such as Mutex Locks, Semaphores, and Condition Variable helps the programmer to synchronize processes and threads within an OS without going to the kernel.

That’s it for this week’s top 10 list. How is it? Do you agree with it? Maybe something is missing or doesn’t seem right? Well, take a second to give me feedback and contact me through GitHub. Thank you for reading!

Sources:
Abraham Silberschatz - Operating System Concepts -Wiley (2018)
http://pages.cs.wisc.edu/~remzi/OSTEP/
https://www.javatpoint.com/os-process-synchronization-introduction
https://prepinsta.com/operating-systems/process-synchronization/
https://www.tutorialandexample.com/monitors-in-operating-system/
https://tutorialspoint.dev/computer-science/operating-systems/deadlock-prevention
https://www.geeksforgeeks.org/deadlock-detection-recovery/