Resource Management - Operating System

• Critical section
  • The critical section refers to the segment of code where processes/threads access shared resources, such as common variables and files, and perform write operations on them. Since processes/threads execute concurrently, any process can be interrupted mid-execution
• Race Condition
  • A race condition occurs when two or more threads can access shared data and they try to change it at the same time. Because the thread scheduling algorithm can swap between threads at any time, you don't know the order in which the threads will attempt to access the shared data. Therefore, the result of the change in data is dependent on the thread scheduling algorithm, i.e., both threads are "racing" to access/change the data
• Solution to Race Condition
  • Atomic operations => Make Critical code section an atomic operation, i.e., Executed in one CPU cycle
  • Mutual Exclusion using Locks/Mutex
    • Disadvantages
      1. Contention => one thread has acquired the lock, other threads will be busy waiting, what if thread that had acquired the lock dies, then all other threads will be in infinite waiting
      2. Deadlocks
      3. Debugging
      4. Starvation of high priority threads
  • Semaphores
• Condition to Fulfill
  • Mutual Exclusion => Only 1 process can enter the Critical section at a time
  • Progress => Both the Entry section should not stop each other which results in no progress
  • Bounded Wait => Each conditions should be bounded to give others a chance
  • No assumption related to Hardware or Speed => Solution should be Universal
• Lock Variable => Mutual Exclusion Fails when Pre-emption between I1 & I2 => Lock variable
• Test and Set
  • Combines I1 & I2 of Lock variable => Mutual Exclusion & Progress is satisfied => Lock variable
• Turn Variable/Strict Alteration
  • 2 Process solution, Run in User mode => ME & BW is satisfied => Turn variable
• Bakery Algorithm
  • Each process is assigned a number (a ticket) in a lexicographical order
  • Before entering the critical section, a process receives a ticket number, and the process with the smallest ticket number enters the critical section
  • If two processes receive the same ticket number, the process with the lower process ID is given priority
• Peterson’s solution => Can be used to avoid race condition but holds good for only 2 process/threads
  • Algorithm

        # Fot T1
        while(1):
            flag[0] = T
            turn = 1
            while(turn == 1 && fla[1] = T):
            # CS
            flag[0] = F
    
        # Fot T2
        while(1):
            flag[1] = T
            turn = 0
            while(turn == 0 && fla[0] = T):
            # CS
            flag[1] = F
    

• Condition Variable
  • The condition variable is a synchronization primitive that lets the thread wait until a certain condition occurs
  • Thread can enter a wait state only when it has acquired a lock. When a thread enters the wait state, it will release the lock and wait until another thread notifies that the event has occurred. Once the waiting thread enters the running state, it again acquires the lock immediately and starts executing
  • Contention is not here
• Semaphores
  • An integer that is equal to number of resources
  • Multiple threads can go and execute C.S concurrently
  • Allows multiple program threads to access the finite instance of resources whereas mutex allows multiple threads to access a single shared resource one at a time
  • Types
    • Binary semaphore => value can be 0 or 1
      • Aka, mutex locks
    • Counting semaphore
      • Can range over an unrestricted domain
      • Can be used to control access to a given resource consisting of a finite number of instances
  • To overcome the need for busy waiting, we can modify the definition of the wait () and signal () semaphore operations. When a process executes the wait () operation and finds that the semaphore value is not positive, it must wait. However, rather than engaging in busy waiting, the process car block itself. The block- operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the Waiting state. Then control is transferred to the CPU scheduler, which selects another process to execute
  • A process that is blocked, waiting on a semaphore S, should be restarted when some other process executes a signal () operation. The process is restarted by a wakeup () operation, which changes the process from the waiting state to the ready state. The process is then placed in the ready queue
• Monitors => Shared Variable + Procedures
  • Shared variables can be accessed via Procedures by Processes
  • Only 1 process can access the procedure at a time and others are kept in Blocked queue
• Multiprocessors and Locking
  • Scalable Locks
  • Lock-free coordination

Classical Synchronization Problems

• Printer Spooler Problem
  • Loss of Data Case => P1 I1 I2 I3 | P2 I1 I2 I3 I4 | P1 I4
• Producer Consumer Problem/Bounded Buffer Problem
  • Producer Thread & Consumer Thread
  • Race Condition Case
    • Producer I1 I2 | Consumer I1 I2 | Producer I3 | Consumer I3
  • Solution using Semaphores
    • m, mutex => Binary Semaphore, Used to acquire lock on buffer
    • empty => A counting semaphore, Initial value is n, Tracks empty slots
    • full => Initial value 0, Tracks filled slots
    • Producer

          do {
              wait(empty); // Wait until empty > 0, then empty -> value
              wait(mutex);
              // CS, Add data to buffer
              signal(mutex);
              signal(full); // Increment full -> value
          } while (1);
      

    • Consumer

          do {
              wait(full); // Wait until full > 0, then full--
              wait(mutex);
              // CS, Remove data from buffer
              signal(mutex);
              signal(empty); // Increment empty
          } while (1);
      

• Read-Write Problem
  • Reader & Writer Thread
  • Problem
    • If more than 1 Reader then no issue
    • There should be only 1 Writer at a time
    • There should be no Reader when there is Writer in CS
  • Solution using Semaphores
    • mutex => Binary Semaphore, To ensure mutual exclusion when read count (rc) is updated, So no 2 threads modify rc at the same time
    • wrt => Binary Semaphore, Common for both reader and writer
    • read count (rc) => Integer {0}, Tracks how many reader are reading
    • Writer

          do {
              wait(wrt);
              // Do Write Operation
              signal(wrt);
          } while (1);
      

    • Reader

          do {
              wait(mutex); // To mutex readcount variable
              rc++;
              if (rc == 1) {
                  wait(wrt); // Ensures no writer can enter if there is even 1 writer
              }
              signal(mutex);
              // CS, Reader is reading
              wait(mutex);
              rc--; // A Reader leaver
              if (rc == 0) {
                  // No reader is left in CS
                  signal(wrt); // Writer can enter
              }
              signal(mutex); // Reader leaves
          } while (1);
      

• Dining Philosophers Problem
  • Problem Statement
    • 5 Philosopher => Thinking or Eating
    • 5 Forks => 2 fork required to eat
  • Semaphore Solution
    • Code

          // Each fork is a binary semaphore
          do {
              wait(fork[i]);
              wait(fork[(i+1) % 5]);
              // Eat
              signal(fork[i]);
              signal(fork[(i+1) % 5]);
              // Think
          } while(1);
          // Can lead to Deadlock
      

    • Solutions to avoid Deadlock
      • Allow at most (n-1) philosopher to be sitting simultaneously
      • Allow a philosopher to pick up his fork only if both forks are available and to do this, he must pick them up in a critical section (atomically)
      • Odd-even rule => An odd philosopher picks up first his left fork and then his right fork, whereas an even philosopher picks up his right fork then his left fork