Features and Differences of Spinlock, Mutex, and Semaphore

Review

Race condition: A situation where multiple processes/threads manipulate the same data at the same time, and the result can vary depending on the timing or access order.

Synchronization: Maintaining the consistency of shared data even when multiple processes/threads are executed simultaneously.

Critical section: An area that can only be entered and executed by one process/thread to ensure the consistency of shared data.

→ Mutual exclusion: Allowing only one process/thread to enter and execute.

How can we ensure mutual exclusion?

→ Let's use locks!

do {
    acquire lock
        critical section
    release lock
        remainder section
} while (TRUE)

volatile int lock = 0; //global

void critical() {
    while (test_and_set(&lock) == 1);
// int TestAndSet(int*lockPtr) {
//     int oldLock = *lockPtr;
//     *lockPtr = 1;
//     return oldLock;
    ... critical section
    lock = 0;
}

Process:

1. Assuming there are two threads, T1 and T2, and T1 executes the while loop first.
2. In the test_and_set(&lock) function, the value of lock(lockPtr), which is 0, is stored in oldLock, and lock(lockPtr) is changed to 1.
3. Since this function returns lodLock, which is 0, the while loop becomes false, and T1 exits the while loop and enters the critical section.
4. At this point, T2 executes, and enters the while loop (T1 is still in the critical section). Since the value of lock is 1, test_and_set(&lock) returns 1.
5. When you look inside the function, lock(lockPtr) has a value of 1, and this value is stored in oldLock. Then, lock(lockPtr) remains 1 and oldLock, which is 1, is returned. T6. herefore, the while loop is true, and T2 continues to run the while loop.
6. After that, when T1 exits the critical section and the value of lock changes to 0, T2 inside the while loop can exit and enter the critical section.

→ In other words, simultaneous execution is not possible.

What if both enter the while loop at the same time?

The TestAndSet function uses the help of the CPU.

→ CPU atomic instructions

• They are not interfered with or interrupted during execution.
• They are not executed simultaneously for the same memory area. → Even if two or more processes/threads access it, the CPU allows only one to come. It synchronizes two processes so that they cannot run simultaneously.

Note: The TestAndSet function does not necessarily have to have that body, but it proceeds in such a form.

Spinlock: Repeatedly try until you can have the lock (while loop).

→ Waste CPU while waiting.

class Mutex {
        int value = 1;
        int guard = 0;
}
------------------
Mutex::lock() {
        while(test_and_set(&guard));
        if(value == 0) {
             ...현재 스레드를 큐에 넣음;
             guard = 0; & go to sleep
        } else {
             value = 0;
             guard = 0;
        }
}
--------------------
Mutex::unlock(){
    while(test_and_set(&guard));
    if(큐에 하나라도 대기중이라면){
            그 중에 하나를 깨운다;
    } else {
            value = 1;
  }
    guard = 0;
}
---------------
mutex -> lock();
...critical section
mutex -> unlock();

Process:

• When competing to access the critical section, a lock is executed based on whether or not the value can have a value.
• If the value cannot have a value (value == 0), it goes into a queue and later one of the threads in the queue is awakened in the unlock phase. → This minimizes unnecessary CPU cycles.
• The guard is a device installed in test_and_set to protect the value in case multiple processes/threads access it (an atomic device at the CPU level).

Mutex: Rest until you can have the lock.

Is a mutex always better than a spinlock?

If the multi-core environment and the operation in the critical section are completed faster than context switching, then spinlock has more advantages than mutex.

Context switching occurs during sleeping and awakening in mutex.

In a CPU with two cores, if T1 is executing in C1's critical section and T2 continues to spinlock in C2, T2 can execute immediately when T1 exits the critical section.

Semaphore: A device that allows one or more processes/threads to access the critical section using signal mechanisms.

A semaphore is a synchronization tool that allows one or more processes or threads to access the critical section. The semaphore consists of an integer variable that can have a value of 0 or higher.

class Semaphore {
        int value = 1; //0,1,2,3 이 될 수도 있음
        int guard = 0;
}
------------------
Semaphore::wait() {
        while(test_and_set(&guard));
        if(value == 0) {
             ...현재 스레드를 큐에 넣음;
             guard = 0; & go to sleep
        } else {
             value -= 1;
             guard = 0;
        }
}
--------------------
Semaphore::signal(){
    while(test_and_set(&guard));
    if(큐에 하나라도 대기중이라면){
            그 중에 하나를 깨운다;
    } else {
            value += 1;
  }
    guard = 0;
}
---------------
semaphore -> wait();
...critical section
semaphore -> signal();

In the class Semaphore, the value determines how many threads/processes can run simultaneously.

• value = 1; binary semaphore.
  When Semaphore::wait is called and value is not 0, value -= 1 is executed, and value becomes 0. Subsequently, threads/processes after that point will enter a queue because value is 0.

• When value is set to 2 or more, counting semaphore

signal mechanisms : for order

In a multi-core environment where value is set to 0, P1 and P2 are allocated to run simultaneously, and task3 is scheduled to run after task1 finishes.

• If P1 calls signal first, value becomes 1, P2 calls wait, and value becomes 0. Then, task3 can start running.

• If P2 calls wait first, value is still 0, so it enters the queue in the if statement. When P1 finishes calling signal and value becomes 1, P2 can exit wait and task3 can start running.

→ Therefore, in Semaphore, it is not necessary for wait and signal to be executed in the same process/thread.

The difference between mutex and binary

• Semaphore is that only the lock holder can release the lock in mutex, while in semaphore, it is not necessary. However, in semaphore, it is not necessary for wait and signal to be executed in the same process/thread.
• Mutex has the property of priority inheritance. When multiple processes/threads are executed at the same time, the scheduling is done based on priority. → If P2 has a lower priority than P1 and P2 holds the lock and executes first, P1 has to wait until P2 finishes. This slows down the speed of leaving the critical section, and P1 continues to wait. To solve this, P2's priority can be increased to match P1's, allowing for faster exit from the critical section.

If only mutual exclusion is required, it is recommended to use mutex. If synchronization of execution order between tasks is required, it is recommended to use semaphore.

This posting is just a study note which was written after watching youtube videos in Korean.
https://youtu.be/gTkvX2Awj6g