운영체제 Sychronization ( 동기화, Mutual Execlusion, Progress, Bounded waiting, Interrupt-based solution, Peterson's solution, Memory Barrier )

먼저 Race condition에 대해 알아보자 Race condition이란 한정된 자원을 동시에 이용하려고 프로세스끼리 경쟁을 벌리는 걸 말한다.

 

예를 들어보자, 네이버에 서버 접속하면 fork()를 통해 고유의 PID를 배정받고 thread가 생성된다. 근데 동시에 네이버에 접속하는 사람이 있다면 누구에게 다음 PID를 배정해야 할까?? 이렇게 동기화의 문제가 생긴다.

 

 

이렇듯 중요한 정보를 가지고 있는 부분을 critical section이라고 부른다. critical section에는 공유 변수(common variables), updating tabel, writing file 등과 같은 것들이 있다. 이런 부분에는 혼자만 수정해야 한다. 그래야 동기화 문제가 생기지 않는다. 

 

크게 4개의 부분으로 나눌 수 있다. 

entry section

critical section

exit section

remainder section

 

이렇게 구조를 생각하고 동기화 문제를 해결 알고리즘을 생각했을 때, 이게 정말 잘 동작하는지 평가하는 기준이 3가지 있다. 

 

1. Mutual Execlusion 

- cirtical section에 한 명만 존재하는지 안 하는지 확인하는 것이다.

 

2. Progress

- critical section에 아무도 없다면 바로 들어갈 수 있는지, 자칫 잘못하면 Deadlock (아무도 사용 못하는 상황)에 걸릴 수 있다.

 

3. Bounded waiting

- critical section에 있던 애가 나갔을 때, entry에 여러 프로세스가 대기하고 있는데 이때 누구를 선택해서 들여보낼지 결정해야 한다. 혹은 안에 있는 애가 계속 안 나왔을 때의 starvation도 고려해야 한다. 가령 시간제한을 걸어 놓음으로써 말이다.

 

이렇게 3가지 기준을 가지고 알고리즘을 알아보자

 

 

Interrupt-based solution

 

가장 navie 하게 Interrupt-based solution이 있다. 이건 entry section에서 interrupt를 못하게 설정하는 것이다. 다른 말로 non-preemption으로 설정한다. 그리고 critical section으로 들어가면 스스로 나올 때까지 혼자 독점할 수 있다. 즉 Mutual Execlusion을 해결한 것이다.

 

하지만 너무 오래 있어서 다른 프로세스가 못 들어간다면 어떻게 할까?? 최악의 경우에 안에서 죽어버린다면?? 혹은 core가 여러 개라서 대기하던 다른 프로세스가 core 2에 들어가서 critical section을 수정할 수도 있다. 이런 문제에 대해 해결해야 한다. 그래서 나온 게 Peterson's solution이다. 

 

 

Peterson's solution

 

아쉽게 2개의 core에서만 적용 가능한 방법이다. 하지만 방법론으로는 좋은 아이디어를 가지고 있다. 

위에서 말한 것처럼 2개의 core에서 critical section에 접근하려 할 때, 어떻게 해야 할까??

 

이렇게 생각해보자, 2 core는 서로 공유하는 2개의 변수가 있는데, 하나는 turn이고 다른 하나는 flag변수라 하자.

 

turn 변수에는 누가 critical section에 들어갈 차례인지 저장한다. 

flag 변수에는 누가 critical section에 들어갈 준비가 됐는지 표기한다. boolean으로 True혹은 False로 나타낸다. 

간단한 코드로 확인해보자

 

while(true) {
    flag[i] = true;
    turn = j;
    
    while(flag[j] && turn == j);
        
    /* critical section */
        
    flag[i] = false;
}

 

먼저 j와 i라는 core 2개가 있다. 두 개 중에 하나만 써야 하니, 하나의 flag가 true라면 다른 하나는 반드시 false가 돼야 한다.

 

flag [i] = ture는 i번째 코어가 critical section에 들어가고 싶다는 의미다.

 

turn = j는 다음으로는 j번째 core가 들어갈 수 있다는 걸 알려준다.

 

while(flag [j] && turn ==j)는 i가 쓰고 있는데 j core가 접근하려 한다던가 할 때 spin lock에서 머무르는 코드다. 물론 아래서 조건을 바꿔서 빠져나올 수 있다. 이 부분을 busy waits이라고 부른다.

 

이 코드에서 false가 돼야 critical section에 들어갈 수 있다. 그러니 flag [j]는 이미 false가 돼 있기 때문에 false가 된다.

critical section으로 들어가고 다 쓰면 flag [i]를 false로 바꿔준다. 

 

이렇게 3가지 조건 ( Mutual Execlusion , Progress, Bounded-waiting )을 만족시킨다. 

Mutual Execlusion는 while문에서 하나만 CS에 들어갈 수 있도록 했다.

Progress는 i가 flag [j]가 false라면 바로 들어갈 수 있도록 했다.

Bounded-waiting은 바로 다음 core가 실행되도록 했다.

 

하지만 현대에선 이 방법을 사용하지 못한다. 이유는 현대의 구조에서는 reorder라는 기술을 사용하기 때문이다. 다른 말로, 비순차적 명령어 처리 혹은 Out-of-order execution (OoOE)라고 부른다. 그렇다면 reorder란 뭘까?

 

자세한 이해를 위해 아래 포스팅을 읽고 오는 걸 추천한다. 하지만 시간이 없다면, 간단히 말해 순차적으로 실행하지 않고 CPU 효율을 위해 비순차적으로 명령문을 실행한다는 의미다.

 

2022.05.12 - [내가 하는 전자공학/운영체제 (OS)] - 운영체제 비순차적 명령어 처리 ( Reorder , Out-of-order execution , OoOE )

운영체제 비순차적 명령어 처리 ( Reorder , Out-of-order execution , OoOE )

 

---

 

이런 reorder가 Peterson's solution에 어떤 영향을 끼칠까??

 

# share var 
boolean flag = false; 
int x = 0; 

# core 1 
while(!flag); 
print(x); 

# core 2 
x = 100; 
flag = true;

 

위와 같은 상황에서 두 개의 core가 동시에 CS에 접근할 수 있다. 

P0에서 flag [0] = true가 먼저 실행되는 것이 아니라, turn = 1이 먼저 실행되어 P1이 들어갈 수 있는 설정을 만들어 줄 수도 있다는 의미다.

 

 

이를 해결하기 위해선 SW에선 할 수 없었기 때문에 HW의 도움이 필요했다.

그래서 나온 게 Memory Barrier이다.

 

 

Memory Barrier

 

간단히 말해 memory barrier는 컴파일러나 cpu에게 barrier 명령문 전 후의 메모리 연산을 순서에 맞게 실행하도록 하는 기능이다. 이렇게 하여 reorder를 방지한다. 하드웨어가 도와줘야만 구현 가능한 API다. 

 

종류에는 2가지가 있는데

1. Strongly ordered : 하나의 프로세스로 인해 메모리가 변경되면 즉각적으로 다른 모든 프로세스들에게 알려주는 방식이다.

2. Weakly ordered :  반대로 하나의 프로세스가 메모리에 접근하여 뭔가를 할 때 다른 프로세스들이 모를 수도 있다.

 

구조마다 각각의 명령문을 가지고 있다. intel에선 아래와 같은 명령어를 제공한다

SFENCE : 메모리에 stores 할 때 순서에 맞게 실행해라

MFENCE : 메모리에 load/stores 할 때 순서에 맞게 실행해라.

LFENCE : 메모리에 load 할 때 순서에 맞게 실행해라.