Review posting 2

5. How to decide the number of threads based on CPU bound/IO bound

Burst is a phenomenon that occurs intensively within a short time.

CPU burst refers to the time a process is continuously executed on the CPU.

IO burst refers to the time a process waits for an IO operation to complete after requesting it.

The life of a process is a continuous sequence of CPU and IO bursts.

CPU bound process
A process that has many CPU bursts.
ex) video editing software, machine learning programs

IO bound process
A process that has many IO bursts.
ex) typical backend API servers

CPU bound 프로그램이 dual-core CPU에서 실행될 때 몇 개의 thread가 사용되어야 할까?

→ Thread 개수 = CPU 개수 +1
너무 많은 thread가 있으면 쓸데없이 context switching이 발생해서 CPU 사용이 낭비되고 늘어나기 때문에.

6. Synchronization, Race Condition, Critical Section

What happens when two threads access one object?

The result can be different depending on when the context switching occurs.

Race condition: A situation where the result may vary depending on the timing or access order when multiple processes/threads manipulate the same data.

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

How to synchronize?

Critical section: An area that only one process/thread can enter and execute to ensure the consistency of shared data.

Conditions for solving the critical section problem

1. Mutual exclusion
→ Only one process/thread can execute the critical section at a time.

2. Progress
→ If the critical section is empty and multiple processes/threads want to enter the critical section, one of them must be executed.

3. Bounded waiting
→ Waiting indefinitely to enter the critical section should not be allowed.

7. Features and Differences of Spinlock, Mutex, and Semaphore

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;
}

1. 두 개의 thread가 있다고 가정할 때, T1이 while loop에 먼저 들어간다.
2. test_and_set(&lock) 함수에서, lock의 value인 0은 oldLock에 저장되고 새롭게 1이라는 value를 가지게 된다.
3. 그리고 이 함수는 oldLock, 즉 0을 리턴하게 되면서 while이 false이기 때문에 T1은 while을 종료하고 critical section으로 진입한다.
4. T2가 이때 while에 접근하지만, test_and_set(&lock)은 계속해서 1을 리턴하기 때문에 true라서 while에 갇히게 된다.
5. T1이 critical section에서 나오면 lock은 0이 되고 그 때 T2는 while에서 나오게 되어 critical section에 진입하게 된다.

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

CPU가 오직 하나만 들어올 수 있게 해준다.

이 방법은 CPU를 낭비하게 된다.
Spinlock: Repeatedly try until you can have the lock (while loop).

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();

1. Critical section에 들어가기 위해 경쟁할 때, lock이 실행된다.
2. value가 0일 때, 현재 thread를 queue에 넣는다.
3. unlock이 queue에 하나라도 대기중이라면 그 중 하나를 깨운다. &arr; CPU 사용율를 줄일 수 있음
4. guard는 여러 개의 process나 thread가 접근할 때 value를 보호하는 장치이다.

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.

Semaphore: A device that allows one or more processes/threads to access the critical section using signal mechanisms.
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();

Multi-core environment
Multi-core environment에서 value가 0으로 세팅되어 있을 때, P1과 P2는 동시에 실행되기 위해 할당되고 task3는 task1 다음에 실행되게 한다.

• 만약 P1이 signal을 먼저 호출하고 value가 1이 되면, P2는 wait를 호출하고 value를 0으로 만든다. 그런 다음 task3가 실행된다.
• 만약 P2가 먼저 wait를 호출하고 value가 여전히 0이면, queue에 들어가게 된다. P1이 signal을 호출하고 나면 value는 1이 되고 P2는 wait에서 나올 수 있게 되고 task3이 실행된다.

mutex와 binary의 차이점

• Mutex에서는 오직 lock을 가지고 있는 것만 lock을 해제 할 수 있지만 semaphore에서는 그렇지 않다. 하지만 semaphore에서는 wait와 signal이 꼭 같은 프로세스, 스레드에서 실행될 필요가 없다.
• Mutex는 priority inheritance 속성을 가진다. 여러 프로세스나 스레드가 동시에 실행이 되면 우선순위에 따라 실행시키게 되는데 이를 스케줄링이라고 한다.