[OS] 5-1. 프로세스 동기화

협력적 프로세스는 시스템 내에서 실행 중인 다른 프로세스에게 영향을 주거나 영향을 미칠 수 있다. Shared Memory라는 개념이 존재하기 때문이다
만약 두 프로세스가 공유 데이터를 동시에 접근한다면?? 어떠한 과정에 의해서 데이터의 일관성을 해칠 수도 있다.

---

Producer-Consumer Problem에 어떠한 조건들을 추가해보자

1. "count" 변수 설정

• Producer는 생산할 때마다 count++
• Consumer는 소비할 때마다 count--

2. Producer-Consumer 사이의 공유 버퍼를 유한하게 만들기

---

## Producer Code ##

while(true){
    while(count == BUFFER_SIZE){
        /* can't produce */
    }
    
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    count++;
    /* produce an item in next_produced */
}

## Consumer Code ##

while(true){
    while(count == 0){
        /* can't consume */
    }

    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    count--;
    /* consume the item in next_consumed */
}

물론 고급언어의 코드로 봤을 때는 별 문제가 없는 코드이다.
하지만 두 프로세스들을 "병행적"으로 실행시킬 경우 올바르게 동작하지 않을 수 있다 :: By Interrupt

// count++
r1 = count
r1 = r1 + 1
count = r1

// count--
r2 = count
r2 = r2 - 1
count = r2

count++ & count--를 어셈블리어로 표현하면 3개의 어셈블리 명령어로 구성되어 있다
근데 만약 count++이든 count--이든 어셈블리 명령어 수행 중간에 Interrupt가 발생한다면???

1. "r1 = count"
2. "r1 = r1 + 1" → Interrupt
3. "r2 = count"
4. "r2 = r2 - 1" → Interrupt
5. "count = r1"
6. "count = r2"

저 과정들 사이에서 count변화를 표로 나타낸다면 다음과 같다

초기 count = 10이라고 가정
	명령어 구분	명령어	레지스터 값 & count 변화
T(0)	"count++ 명령어 수행"	r1 = count	r1 = 10
T(1)	"count++ 명령어 수행"	r1 = r1 + 1	r1 = 11
T(2)	"count-- 명령어 수행"	r2 = count	r2 = 10
T(3)	"count-- 명령어 수행"	r2 = r2 - 1	r2 = 9
T(4)	"count++ 명령어 수행"	count = r1	count = 11
T(5)	"count-- 명령어 수행"	count = r2	count = 9

T(2)에서 r2 = 10인 이유는 앞에 과정에서 count++의 명령어들을 수행하기는 했지만, count 값만 읽은 상태이고 최종적으로 count를 업데이트하지 않았기 때문에 T(2)에서 r2에는 count의 동기화되지 않은 값인 "10"이 저장된다

count++을 통해서 11도 표현되고, count--를 통해서 9도 표현되었지만, 최종적으로 count에 저장되는 값은 9이다

>> 결국 실제로 초기 10에서 Producer가 하나 생산하고, Consumer가 하나 가져갔으므로 count = 10이 되어야 하지만, 동기화 문제로 인해서 count = 9가 되었다. 이러한 문제의 원인은 "공유 데이터에 동시에 접근"해서 발생한 문제이다

 

Race Condition

여러 주체들이 하나의 공유 데이터를 동시에 접근하려는 경우 :: "경쟁 상태"

>> 결국 Race Condition을 해결하기 위해서 프로세스들이 동기화되도록 할 필요가 있다

 

Race Condition 발생 상황

1) kernel mode로 수행 중 Interrupt 발생

"count = 50"이라고 가정하자

// count++
r1 = count
r1 = r1 + 1
count = r1

// count--
r2 = count
r2 = r2 - 1
count = r2

결국 위에서 설명한 예제와 동일한 문제가 발생하기 된다

>> 여기서 Race Condition을 막는 방법은 kernel상에서 중요한 공유 데이터를 처리할 때는 "Interrupt Disable"로 설정해줘서 해당 작업 중에는 ISR로 넘어가지 못하게 막아버리면 된다

 

2) 프로세스가 System Call을 통해서 kernel mode로 어떠한 작업 수행 도중 프로세스 간 "Context Switch" 발생

프로세스가 실행된다는 의미는 user mode에서 본인 메모리 영역의 code가 실행되고, 중간에 System Call을 통해서 kernel mode에서 kernel의 code도 실행이 된다

RR 방식으로 스케줄링을 해서 해당 프로세스의 time quantum이 10이라고 가정하고 kernel mode 중간에 Timer Interrupt에 의해서 "Context Switch"된다고 가정하자

그러면 여기도 마찬가지로 공유 데이터의 동기화 문제가 발생하게 된다

>> 여기서 Race Condition을 해결하는 또 다른 방법은 kernel mode에서 수행중이면 "선점"하지 않으면 된다 :: kernel mode이면 time quantum이 끝나도 CPU를 빼앗지 않으면 된다

• 어차피 Time Sharing은 Real-Time처럼 Deadline안에 끝내지 못하면 시스템에 치명적인 영향을 주지는 않기 때문에 time quantum을 약간 지나쳐도 괜찮을 거다

 

3) Multiprocessor에서 Shared Memory 내의 kernel data

CPU가 여러개 존재하고 각 CPU가 메모리 하나를 공유한다면?? 앞에서 제시한 해결책으로는 Race Condition문제가 해결되지 않는다

• (1), (2)는 CPU가 하나이고, 공유 데이터 작업 도중에 CPU가 넘어가서 생긴 문제
• (3)은 애초에 CPU가 여러개이고 각 CPU가 공유 데이터에 동시에 접근하려 해서 발생하는 문제

 

>> 여기서 Race Condition을 해결하는 간단한 방법은 "데이터에 접근할 때 Lock을 걸어라"

• 내가 데이터에 접근하면 "lock"을 걸어서 다른 누구도 접근할 수 없게 막으면 된다
• 물론 해당 데이터에 대한 처리가 완료되면 "unlock"해줘야 한다

결국 공유 데이터의 동기화 관련 문제는 "공유 데이터에 대한 동시 접근"에 의한 "데이터 불일치"이다. 따라서 "데이터 일관성"을 위해서는 협력 프로세스끼리 데이터 접근에 대한 순서(lock)을 정해줘야 한다

---

Critical Section Problem

Critical Section은 임계 구역 :: "공유 데이터가 존재하는 구역"이다

여기서 2개의 프로세스는 서로 공유 데이터 "x = 2"를 보유하고 있다
그리고 각 프로세스마다 "x = x + 1" & "x = x - 1"인 공유 데이터를 접근하는 "Critical Section"이 존재한다

while(true){
    entry section
        critical section
    exit section
        remainder section
}

entry section

• 각 프로세스가 Critical Section 진입 허가 요청을 하고 조건을 검사받는 구역

critical section

• 공유 데이터 접근 구역

exit section

• Critical Section에서 빠져나와서 맞이하는 구역

remainder section

• 나머지 구역

결국 각 프로세스들에 대해서 "Entry Section"에서 Critical Section에 대한 "lock"을 걸어줘서 내가 들어가있을 때 다른 어떤 프로세스도 들어오지 못하도록 설계해줘야 한다

Critical Section Problem 해결 조건

1. Mutual Exclusion (상호 배제)

"어느 프로세스가 Critical Section 영역에 접근하고 있으면 다른 프로세스들은 절대로 Critical Section 영역에 접근하면 안된다"

• entry section & exit section을 통해서 통제해야 한다

 

2. Progress (진행)

"어느 프로세스도 Critical Section에 접근하고 있지 않을 때, Critical Section에 접근하고 싶어하는 프로세스가 존재하면 해당 프로세스는 들어가게 해줘야 한다"

• 물론 여러 프로세스들이 들어가고 싶어하면 어느 프로세스가 들어갈지 결정을 해줘야 한다

 

3. Bounded Waiting (유한 대기)

"프로세스 입장에서 Critical Section에 들어가고 싶어하는데 계속 들어가지 못하는 Starvation이 발생하면 안된다"

• 다른 측면에서 보면, 어떤 프로세스가 Critical Section 접근 요청을 하면, 요청을 하고 요청이 허용될 때까지 다른 프로세스들의 Critical Section 접근 횟수에 제한이 존재해야 한다

 

---

Algorithm 1)

"int turn" 변수 사용

• turn에는 어느 프로세스가 Critical Section에 들어갈지를 표현
  • "P(i) can enter its Critical Section if (turn == i)

## Process A ##

while(true){
    while(turn != A);
        "Critical Section"
    turn = B;
        "Remainder Section";
}

## Process B ##

while(true){
    while(turn != B);
        "Critical Section"
    turn = A;
        "Remainder Section"
}

Entry Section : "while(turn != (A or B))"

본인의 입장(A, B)에서 볼 때 while문을 통해서 turn이 상대방이면 "Busy Waiting"을 통해서 turn이라는 조건변수가 변경될 때까지 대기한다

Exit Section : "turn = (A or B)"

"Critical Section"에서 나와서 turn을 상대방으로 바꿔준다

---

Mutual Exclusion 만족 O

따라서 이 알고리즘은 turn 변수에 의해서 서로 교대로 Critical Section에 들어갈 수 있다

Progress 만족 X

하지만 이 알고리즘의 치명적 단점은 "반드시 Critical Section에 들어갔다 나와야 turn을 상대방으로 바꿔줄 수 있다"라는 점이다
만약 프로세스 A는 C-S에 50번 들어가고 싶고, 프로세스 B는 C-S에 1번만 들어가고 싶다면 프로세스 B는 1번 들어가면 더 이상 들어갈 일이 없으므로 프로세스 A는 영원히 들어가고 싶어도 못들어간다

---

Algorithm 2)

"boolean flag[2] 변수 사용"

flag변수는 본인이 Critical Section에 들어갈 준비가 다 되었고 들어가고 싶다고 의사표명을 하는 것이다

• true = 들어갈 준비 완료 / false = 아직 들어갈 준비 X

## Process A ## 
while(true){
    flag[A] = true;
    while(flag[B]);
        "Critical Section"
    flag[A] = false;
        "Remainder Section"
}

## Process B ##
while(true){
    flag[B] = true;
    while(flag[A]);
        "Critical Section"
    flag[B] = false;
}

Entry Section : "flag[본인] = true / while(flag[상대방])"

일단 본인이 Critical Section에 들어가고 싶으니까 flag를 통해서 그러한 의사표명을 해준다

그리고 상대방의 현재 상태를 while문을 통해서 check한다
→ 만약 상대방도 flag설정을 완료했다면 "나"는 대기
→ 만약 상대방이 flag설정을 하지 않았다면 "내"가 Critical Section에 들어가기

Exit Section : "flag[본인] = false"

"Critical Section"에서 나와서 "나"의 준비 상태를 false로 바꿈으로써 상대방이 나의 조건을 check함에 따라서 무한루프를 돌고있는 것을 멈춰준다

---

Mutual Exclusion 만족 O

flag라는 변수를 설정해주고 true / false를 통해서 서로 교대로 들어갈 수 있으므로 Mutual Exclusion은 만족한다

Progress 만족 X

하지만 만약 둘다 flag 설정을 해놓았으면?? while문에서 서로를 무한으로 대기하는 "과잉양보" 때문에 Critical Section이 비었음에도 불구하고 아무도 들어가지 못한다

---

Algorithm 3) "Peterson's Solution"

"int turn & boolean flag[2]"변수 둘 다 사용

## Process A ## 
while(true){
    flag[A] = true;
    turn = B;
    while(flag[B] && turn == B);
        "Critical Section"
    flag[A] = false;
        "Remainder Section"
}

## Process B ##
while(true){
    flag[B] = true;
    turn = A;
    while(flag[A] && turn == A);
        "Critical Section"
    flag[B] = false;
}

Entry Section : "flag[본인] = true & turn = 상대 && while(flag[상대] && turn == 상대)"

일단 "나"는 flag에 대한 설정을 완료하고 "상대방에게 먼저 turn을 제공해준다"
→ 상대방이 flag설정까지 완료했다면? 그러면 상대방에게 먼저 들어가라고 해준다
→ 상대방이 flag설정을 완료하지 못했다면? 그러면 내가 들어간다

Exit Section : "flag[본인] = false"

"Critical Section"에서 나와서 "나"의 준비 상태를 false로 바꿈으로써 상대방이 나의 조건을 check함에 따라서 무한루프를 돌고있는 것을 멈춰준다

Mutual Exclusion 만족 O

일단 프로세스 A가 Critical Section에 들어가려면 "flag[B] = false" or "turn == A"를 만족해야 한다

• 일단 나는 준비 완료 상태이고 상대방에게 turn을 줌으로써 기회를 먼저 주기 때문에 "상대방이 준비가 되지 않았거나 아예 상대방이 turn을 나로 넘긴 상태"이여야 한다

두 프로세스가 동시에 Critical Section에 들어가려면 "flag[A] == flag[B] == true && turn == A == B"도 만족해야 한다

• 왜냐하면 while문을 벗어나려면 반드시 만족해야 하는 조건이기 때문이다

>> 하지만 결론적으로 위의 문장들은 성립되지 않는 문장들이다

왜냐하면 "turn 변수"는 오직 하나의 값만 할당받을 수 있기 때문이다

• turn은 i, j가 공통으로 사용하는 "공유 자원"이다

따라서 flag가 둘다 true로 설정되어 있다 하더라도 두 프로세스간의 "공유 자원"인 turn 변수에 의해서 둘 중 하나만 while문을 통과해서 Critical Section에 들어갈 수 있을 것이다

 

Progress 만족 O

결국 Progress는 Critical Section에 아무도 없을 때 "내가 들어가길 원하면 들어갈 수 있어야 한다"가 중요하다

1)

Process A		Process B
flag[A] = true		flag[B] = false	turn

>> 상대방에게 turn을 주었지만 상대방이 준비를 하지 않았기 때문에 A가 Critical Section에 진입

1.5)

Process A		Process B
flag[A] = true		flag[B] = true	turn

>> B가 while루프내에서 "이제 나도 들어갈 준비가 다 되었다"라고 생각하면서 flag = true로 변경하였다. 하지만 아직 flag[A] = true이므로 while루프를 벗어날 수는 없다

2)

Process A		Process B
flag[A] = false		flag[B] = true	turn

>> 마침내 A가 Critical Section에서 나와서 자신의 flag = false로 변경을 했으므로 B는 while 루프를 벗어날 수 있고 Critical Section에 들어갈 수 있게 되었다

결국 본인이 원하면 들어갈 수 있기 때문에 Progress를 만족한다

하지만 A의 입장에서 flag[A] = true로 다시 재지정하면 반드시 turn도 A로 지정해줘야 한다. 왜냐하면 B는 while루프를 돌다가 Critical Section에 들어갔으므로 while 문을 수행하는 도중에는 turn을 바꾸지 않았다.

하지만 "Peterson's Solution"은 while문에서 대기하는 프로세스 입장에서는 계속해서 CPU & 메모리를 사용하면서 while 조건을 판별한다. 판별만 해서는 while 루프를 벗어날 수 없기 때문에 상대방이 조건을 변경해줘야 while문을 빠져나갈 수 있다. 따라서 "Busy Waiting"이라고 할 수 있다

 

---

하드웨어적 프로세스 동기화

"Peterson's Solution"은 최신 컴퓨터 아키텍쳐에서는 보장되지 않는 Solution이다. 왜냐하면 최신 컴퓨터 아키텍처에서는 시스템 성능 향상을 위해서 프로세서/컴파일러가 종속성이 없는 읽기/쓰기 작업에 대해서 본인 임의로 재정렬을 할 수 있기 때문이다
따라서 최신 컴퓨터 아키텍처에서 보장하기 위해서는 "Memory Barrier"를 사용해야 한다

1) Memory Barrier

컴퓨터 아키텍처가 프로그램에게 제공하는 "메모리 접근 시 보장되는 사항을 결정한 방식"

▶ Strongly Ordered

한 프로세서의 메모리 변경 결과가 다른 모든 프로세스에게 즉시 보인다

▶ Weakly Ordered

한 프로세스의 메모리 변경 결과가 다른 프로세서에게 즉시 보이지 않는다

>> 따라서 Memory Barrier Instruction이 실행될 때, 시스템은 또 다른 LOAD/STORE 연산이 수행되기 전에 현재에 대한 모든 LOAD/STORE을 완료되도록 해준다

while(!flag)
    memory_barrier();
print x;

------------------------

x = 100;
memory_barrier();
flag = true;

 

2) 하드웨어 명령어

"test_and_set()" / "compare_and_swap()"

 

▶ test_and_set(boolean *target)

중요한 특징은 "test_and_set() 명령은 원자적(Atomically)으로 실행된다"라는 점이다

• 따라서 2개의 test_and_set()이 동시에 실행되어도 어차피 원자적으로 실행되므로 임의의 순서로 순차적으로 실행된다
• test_and_set()명령을 지원한다면 "boolean lock = false"를 통해서 Mutual Exclusion을 구현할 수 있다

"Synchronization variable"
    boolean lock = false;

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

while(true){
    while(test_and_set(&lock)){
        /* do nothing */
    }
    "Critical Section"
    lock = false;
    "Remainder Section";
}

boolean lock = false

lock = false이고, test_and_set(&lock)을 통해서 읽은 값은 false이고, 그에 따라서 Critical Section에 들어갈 수 있다
그리고 test_and_set(&lock)을 통해서 해당 lock은 true로 되므로 다른 프로세스들은 아무리 test_and_set(&lock)을 읽어도 lock = false이므로 무한루프를 돌게 된다
그리고 Critical Section에서 빠져나와서 lock = false로 설정해주기 때문에 다른 프로세스들 중에서 test_and_set(&lock)을 읽어서 Critical Section에 들어갈 수 있다

boolean lock = true

어차피 test_and_set(&lock)을 읽어도 true로 뜨기 때문에 무한루프를 돌게 된다
test_and_set()은 값을 읽고 -> "true"로 설정해주기 때문에 어차피 원래 값이 true이므로 계속 true이다

>> 위의 test_and_set() 알고리즘은 Mutual Exclusion은 만족하지만, Critical Section에서 빠져나와서 lock을 풀어줄 프로세스가 존재하지 않는다면 while에서 계속 돌고있는 프로세스들은 영원히 기다려야 하기 때문에 Bounded Waiting을 만족하지 않는다

 

▶ compare_and_swap(int *value, int expected, int new_value)

"Synchronization Variable"
    boolean waiting[n];
    int lock;

int compare_and_swap(int *value, int expected, int new_value){
    int temp = *value;

    if(*value == expected){
        *value = new_value;
    }

    return temp;
}

while(true){
    while(compare_and_swap(&lock, 0, 1) != 0){
        /* do nothing */
    }
    "Critical Section"
    lock = 0;
    "Remainder Section"
}

공유 변수인 waiting & lock은 각각 false & 0으로 초기화된다

---

## Bounded Waiting을 만족하는 CAS ##

"Synchronization Variable"
    boolean waiting[n];
    int lock;

int compare_and_swap(int *value, int expected, int new_value){
    int temp = *value;

    if(*value == expected){
        *value = new_value;
    }

    return temp;
}

while(true){
    waiting[i] = true;
    key = 1;
    while(waiting[i] && key == 1){
        key = compare_and_swap(&lock, 0, 1);
    }
    waiting[i] = false;

    "Critical Section"

    j = (i + 1) % n;
    while((j != i) && !waiting[j]){
        j = (j + 1) % n;
    }

    if (j == i){
        lock = 0;
    }
    else{
        waiting[i] = false;
    }

    "Remainder Section"
}