[운영체제] Synchronization

배경 지식

---

Race Condition

두 개 이상의 job이 Shared Memory의 데이터에 동시에 접근하여 실행 결과가 모호해지는 상태를 의미한다.

 

동시에 접근한다는 것의 의미

프로그래머가 의도한 실행 절차가 끝나기 전에 해당 데이터를 사용하는 다른 코드가 중간에 실행되는 것을 의미한다.

따라서 Race Condition은 Multicore 환경뿐만 아니라 Single-core 환경에서도 발생할 수 있다.

 

실행 순서가 보장되어 있지 않은 경우 모든 Shared Memory에 대해 Race Condition이 발생할 수 있다.

 

Race Condition이 발생할 수 있는 Shared Memory 환경

1. Multithread
2. IPC through shared Memory
3. Kernel space

---

Synchronization

---

 

Critical-Section Problem

Critical-Section을 실행하던 중 Interrupt가 발생하여 Race-Condtion 문제가 발생하는 것을 Critical-Section Problem이라고 한다. Synchronization을 통해 해결할 수 있다.

 

Critical-Section

Shared Memory에 접근하는 X=X+1과 같은 Code Segment를 의미한다.

 

Critical-Section Problem의 해결책

동기화를 이용해 문제를 해결하는 방법에 대해 알아보자.

do {
    // entry section
        critical-section
    // exit section
    
        remainder-section
 } while(true);

 

하나의 프로세스가 Critical-Section의 코드를 실행 중일 때 다른 프로세스들은 접근하지 못하도록 막으면 해당 문제를 해결할 수 있다. Critical-Section을 수행하기 전후로 entry section과 exit section을 두어 접근 권한을 확인하고 반납하는 형태로 이를 구현할 수 있다. (remainder section은 critical section이 아닌 코드 영역을 의미한다.)

 

그렇다면, entry section과 exit section은 어떻게 구현할까? 구현하는 방법에는 Software 방식과 Hardware 방식이 있다.

---

Software Solution

Critical-Section이 제대로 동작하기 위해선 다음 요구사항을 준수해야 한다.

 

1. Mutual Exclusion

Critical-Section을 동시에 사용하는 프로세스가 없어야 한다.

 

2. Progress

Deadlock이 발생하지 않아야 한다.

 

3. Bounded Waiting

Starvation이 발생하지 않아야 한다.

 

두 개의 프로세스가 동시에 접근하는 상황을 가정하자.

 

Algorithm 1

배열에 해당 Critical Section의 사용 여부를 저장하여 실행 중인 다른 작업이 있는지 확인한다.

i, j는 작업을 의미한다.

do {
    // Entry Section
    wants[i] = true; 
    while (wants[j]);
    
    ... // Critical Section

    // Exit Section
    wants[i] = false;

} while(true);

 

해당 방법은 Mutual Exclusion은 보장되나 Progress와 Bounded Waiting을 보장할 수 없다.

`wants[i] = true` -> `Interrupt` -> `wants[j] = true`의 경우 Deadlock이 발생한다.

 

 

Algorithm 2

not_turn이라는 공유 변수를 통해 상대 프로세스가 먼저 Critical-Section을 사용하도록 한다.

do {
    // Entry Section
    while(not_turn == i);
    
    ... // Critical Section
    
    // Exit Section
    not_turn = i;

} while(true);

 

 

해당 방법도 Mutual Exclusion와 Bounded Waiting은 보장되나 Progress를 보장할 수 없다.

Critical Section의 실행을 마친 후 또 실행되어야 하는 경우 다른 프로세스가 해당 Critical Section을 사용하기 전에는 실행이 불가능하다.

 

Peterson's Algorithm

배열과 공유 변수를 모두 사용하면 요구 사항을 만족하는 알고리즘을 만들 수 있다.

while (true) {
    // entry section
    wants[i] = true;
    not_turn = i;
    while (wants[j] && not_turn == i);
    
    ... // critical section
    
    // exit section
    wants[i] = false;
}

 

Mutual Exclusion

wants[] 또는 not_turn에 의해 보장됨

 

Bounded Waiting

not_turn 에 의해 보장됨

 

Progress

i와 j 프로세스의 wants[]의 값이 true이더라도 not_turn을 통해 하나의 프로세스는 무조건 CS를 통과할 수 있다.

또한, i 프로세스의 not_turn이 i더라도 wants[j]의 값이 false면, i 프로세스를 실행할 수 있다. 따라서, 한 프로세스가 연속으로 CS를 실행하는 것도 가능해진다.

 

그러나

현대 아키텍쳐에서는 성능 향상을 위해 종속성이 없는 작업에 대해 순서를 변경할 수 있으므로 Peterson's Algorithm이 제대로 동작하지 않을 수 있다. 아래와 같이 순서가 바뀔수 있으며, Mutual Exclusion에 위배되는 상황이 발생할 수 있다.

while (true) {
    // entry section
    not_turn = i;
    wants[i] = true;

    while (wants[j] && not_turn == i);
    
    ... // critical section
    
    // exit section
    wants[i] = false;
}

 

또한, 세 개 이상의 프로세스가 동시에 접근할 때는 위의 Peterson's Algorithm 코드는 사용할 수 없다. 

 

N개의 프로세스에 대한 Peterson's Algorithm을 알고싶다면 아래 글을 참조하자.

https://www.geeksforgeeks.org/n-process-peterson-algorithm/  

N process Peterson algorithm - GeeksforGeeks

 

---

Hardware Solution

Memory barrier

모든 읽기/쓰기 활동이 완료되도록 강제하여 실행 순서를 보장하는 명령입니다.

Peterson's algorithm에 적용하여 명령 순서가 바뀌지 않도록 할 수 있습니다.

wants[i] = true;
memory_barrier();
not_turn = i;

 

Atomic Instruction

Hardware의 도움을 받아 Interrupt가 발생하지 않는 명령을 의미합니다.

 

Atomic : non-interruptible

 

TestAndSet

Mutual Exclusion을 보장하는 Atomic Instruction입니다.

보통 TestAndSet()은 다른 Synchronization Tool을 만드는데 사용됩니다.

 

TestAndSet()

함수명 그대로 false인 경우 false를 반환하고 해당 변수에 true를 할당하여 Mutual Exclusion을 보장한다.

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

 

사용 예시

// initially, lock = false
do {
    while (TestAndSet(&lock));
    
    ... // critical section
    
    lock = false;
    
} while(true);

 

Atomic variable

TestAndSet() 함수를 이용한 Synchronization Tool으로, 기본 자료형에 대해 Atomic하게 연산이 가능한 변수입니다.

 

Mutex Lock

high-level language에서 쉽게 사용가능한 Mutual Exclusion을 보장하는 Atomic instruction입니다.

이것 또한 TestAndSet() 함수를 사용하여 구현됩니다.

 

구성

while (true) {
    // acquire lock
    // ciritical section
    // release lock
}

acquire() {
    while (!available); // 사용 가능한 상태가 될 때까지 기다리다가
    available = false; // 사용 할 때는 문 닫기
}

release() {
    available = true; // 사용이 끝나면 문 열기
}

---

Semaphore

---

Semaphore

• Mutual Exclusion을 위한 Atomic Integer Variable입니다.
• wait()과 signal()이라는 atomic instruction을 통해 Semaphore을 조작합니다.
• N개의 프로세스에 대해 Mutual Exclusion을 가능하게 만듭니다.

연산

Semaphore S; // Shared Variable

wait(S) {
    while (S <= 0);
    S--;
}

signal(S) {
    S++;
}

 

Binary Semaphore

0 또는 1의 값을 가지는 Semaphore를 의미합니다.

S = 1로 초기화하면 binary semaphore가 되며, Mutex lock과 동일하게 동작합니다.

 

Counting Semaphore

양의 정수 범위를 가지는 Semaphore를 의미합니다.

S를 2 이상의 값으로 초기화 하면 counting semaphore가 됩니다.

 

문제점

1. Busy Waiting

Spinlock이라고도 불리며, Running 상태의 프로세스가 entry section에서 계속해서 while문을 돌고 있는 상태를 의미합니다. Semaphore 뿐만 아니라 CS를 얻기 위해 while을 사용하는 모든 방법에서 발생할 수 있습니다. 

wait(S) {
    while (S <= 0);
    S--;
}

 

단점

• 권한을 얻기 전까지 아무것도 하지 못한다.
• CPU Cycle이 낭비된다.

장점

• 권한을 얻기 전까지 Context-Switch가 발생하지 않아 busy waiting의 시간이 context-switch 시간보다 짧다면 이득이 될 수 있다. 따라서 context-switch time vs busy waiting time을 잘 고려해야 한다.

해결책

entry section에서 해당 프로세스를 waiting queue로 보내고, exit section에서 waiting queue로 보내진 프로세스를 다시 ready queue로 불러와 CPU Cycle이 낭비되지 않도록한다.

typedef struct Semaphore {
    int value;
    struct process *list; // waiting semaphores
} Semaphore;

Semaphore S.value = 1;

wait(S) {
    S.value--;
    if (S.value < 0) {
        block();
    }
}

signal(S) {
    S.value++;
    if (S.value <= 0) {
        wakeup(P);
    }
}

 

2. Deadlock

두 개 이상의 프로세스가 서로에 의해 아무것도 실행되지 못하는 상황을 Deadlock이라고 한다.

 

Semaphore를 사용하는 두 프로세스

 

signal()이 실행되기 전 두 프로세스의 wait() 함수가 모두 실행된다면 Deadlock 상황이 발생한다.

이를 해결하는 방법은 나중에 다룰 것이다.

 

3. Priority Inversion

L : 우선순위가 낮은 프로세스

M : 우선순위가 중간인 프로세스

R : 우선순위가 높은 프로세스

가 있다고 하자.

 

L이 현재 CS를 실행 중이고 H가 대기 중일 때, CS가 필요하지 않은 M에 의해 L이 preemption되어 H보다 M이 먼저 실행되는 경우를 Priority Inversion이라고 한다.

 

해결책

priority-inheritance protocol (우선순위 상속)

대기하고 있는 프로세스의 우선순위를 상속하여 preemption되지 않게 만들어 문제를 해결할 수 있다.

 

4. Semaphore의 잘못된 사용

Semaphore은 사용자가 작성하는 것이므로 실수가 나올 수 있다.

 

정상적인 사용

wait(S) ... signal(S)

 

잘못된 사용

Case 1. signal(S) ... wait(S)

=> mutual exclusion을 보장하지 못한다.

 

Case 2. wait(S) ... wait(S)

=> Deadlock이 발생한다.

 

Case 3. wait(S)의 누락

=> mutual exclusion을 보장하지 못한다.

 

Case 4. signal(S)의 누락

=> Deadlock이 발생한다.