Locking¶

Lock Variable¶

1. Introduction to LOCK Variable¶

The LOCK variable is one of the oldest software-based mechanisms for process synchronization. It is a user-mode solution, meaning it is implemented at the application level and does not require support from the operating system kernel. It is intended for multi-process synchronization.

2. How it Works¶

The solution uses a single shared variable called lock.

• lock = 0: The critical section is free (vacant).

• lock = 1: The critical section is occupied by a process.

Basic Code Structure:¶

1. Entry Section:

   while (lock == 1); // Wait if lock is 1 (busy waiting)
   lock = 1;          // Set lock to 1 and enter
   

2. Critical Section: (Process executes its code)

3. Exit Section:

   lock = 0;          // Release the lock
   

3. Operational Scenarios¶

• Normal Case: Process P1 checks the lock (0), finds it free, sets it to 1, and enters the critical section. If Process P2 tries to enter, it finds the lock is 1 and gets stuck in the while loop (busy waiting) until P1 exits and resets the lock to 0.

• Failure Case (Preemption): If P1 executes the while check and finds lock = 0, but is preempted before it can set lock = 1, a major problem occurs. Process P2 could then run, find lock = 0, set it to 1, and enter the critical section. When P1 resumes, it continues from where it left off and also sets lock = 1 and enters. Result: Both processes are in the critical section simultaneously.

4. Evaluation of the Solution¶

To be a valid synchronization solution, it must meet specific criteria:

• Mutual Exclusion: FAILED. As shown in the preemption scenario, multiple processes can enter the critical section at the same time if an interrupt occurs at the wrong moment.

• Progress: SUCCESS. If no process is in the critical section, a process that wants to enter can generally do so.

• Bounded Waiting: There is no guarantee against starvation.

5. Summary¶

The LOCK Variable is simple but not a guaranteed solution because it fails to ensure Mutual Exclusion under preemption. This led to the development of more advanced hardware-supported methods like the Test-and-Set Lock (TSL).

Test and Set Instruction¶

1. The Problem with Basic Lock Variables¶

The standard Lock Variable approach often fails to ensure Mutual Exclusion due to its non-atomic nature.

• The Race Condition: In a lock variable system, the process first tests the lock (checks if it's 0) and then sets it (changes it to 1).

• Preemption: If a process (P1) is preempted after checking the lock but before setting it, another process (P2) can enter the critical section. When P1 resumes, it also enters, leading to multiple processes in the critical section simultaneously.

• Root Cause: The separation of "testing" and "setting" into two distinct instructions allows for context switching in between.

2. Concept of Test and Set Instruction (TSL)¶

The Test and Set instruction is a hardware-based synchronization tool that combines the testing and setting of a lock into a single, atomic (indivisible) operation.

• Atomicity: Because the instruction is atomic, it cannot be interrupted by a context switch halfway through. This ensures that no other process can interfere between the moment the lock is read and the moment it is updated.

• Mechanism: It reads the current value of the lock, returns it to the caller, and simultaneously updates the lock value to 1 (True).

3. Algorithm and Implementation¶

The logic relies on a shared boolean variable (e.g., lock), which is initially false (0).

The TSL Function Logic:¶

1. Read Original Value: Store the current value of the target (lock) in a local variable.

2. Set to True: Update the target value to True (1) immediately.

3. Return Original: Return the value that was read before the update.

Process Execution Flow:¶

• Entry Section: A process executes a while(Test_and_Set(&lock)) loop.

  • If the lock is 0, the function returns 0 (False), the loop terminates, and the process enters the Critical Section. Importantly, the lock is already set to 1 by the function.

  • If the lock is 1, the function returns 1 (True), and the process continues to "spin" in the loop (Busy Waiting).

• Critical Section: The process performs its task.

• Exit Section: The process sets the lock back to 0 so other processes can enter.

4. Key Advantages¶

• Mutual Exclusion: Guaranteed. Since the check and set happen in one step, two processes can never see the lock as 0 at the same time.

• Progress: If the critical section is empty, any process wishing to enter can do so without being blocked by others.

• Simplicity: It is easier to implement compared to complex software algorithms like Dekker’s or Peterson’s.

5. Limitations¶

• Busy Waiting: Processes "spin" in a loop while waiting, which consumes CPU cycles (Spinlocks).

• Bounded Waiting: There is no inherent guarantee of bounded waiting; a process might be waiting forever if other processes keep entering the critical section before it.

• Hardware Dependency: This solution requires specific hardware support for the atomic instruction.

Turn Variable¶

1. Introduction to Turn Variable¶

The Turn Variable method is a software solution used to manage the critical section problem between two processes (e.g., \(P_0\) and \(P_1\)).

• Type: Software-based solution (no hardware or kernel support required).

• Scope: Restricted to exactly two processes.

• Shared Variable: Uses a common variable called turn.

  • If turn = 0, it is \(P_0\)'s turn to enter the critical section.

  • If turn = 1, it is \(P_1\)'s turn to enter the critical section.

2. Algorithm and Mechanism¶

The processes follow a specific structure for their entry and exit sections:

Process \(P_0\):¶

• Entry Section: while(turn != 0); (The process spins/waits as long as it is not its turn).

• Critical Section: Executes its task.

• Exit Section: turn = 1; (After finishing, it explicitly hands the turn over to \(P_1\)).

Process \(P_1\):¶

• Entry Section: while(turn != 1); (Spins/waits as long as turn is not 1).

• Critical Section: Executes its task.

• Exit Section: turn = 0; (After finishing, it explicitly hands the turn back to \(P_0\)).

3. Analysis of Synchronization Criteria¶

A. Mutual Exclusion (Satisfied)¶

Mutual exclusion is guaranteed. If \(P_0\) is in the critical section, turn must be 0. For \(P_1\) to enter, turn would need to be 1. Since turn can only have one value at a time, both processes cannot be in the critical section simultaneously.

B. Progress (Not Satisfied)¶

The "Strict Alteration" nature is the main drawback.

• A process can only enter the critical section if it is its turn.

• Problem Scenario: If the critical section is empty and \(P_1\) wants to enter, but turn is currently 0, \(P_1\) is blocked. \(P_1\) cannot enter until \(P_0\) enters and then leaves the critical section to change the turn to 1.

• Even if \(P_0\) has no desire to enter the critical section, \(P_1\) is forced to wait. This lack of independent entry means the "Progress" requirement is failed.

C. Bounded Waiting (Satisfied)¶

Waiting is bounded because the turn strictly alternates. Once \(P_0\) leaves the critical section, it must set turn = 1, ensuring that \(P_1\) will get the next chance. A process cannot "hog" the critical section by entering it multiple times in a row without giving the other process a turn.

D. Architectural Neutrality (Satisfied)¶

Since this is a software-based solution implemented at the user application level, it is portable and can run on different hardware platforms without specialized instructions.

4. Summary Table¶