[OS] 프로세스 동기화

2023-12-09 7 분 소요

전 포스팅 《 IPC (프로세스간 통신) 》에서 임계 구역에 대해 살펴보았다.
이 포스팅에서 설명 하려는 것은 아래와 같다.
- “경쟁 상태는 문제이다. 왜? 데이터의 일관성을 보장할 수 없기 때문이다. 그럼 어떻게 해결할건데?” → 프로세스 동기화!
- 프로세스 동기화란 하나의 자원을 한 순간에 하나의 프로세스만이 이용하도록 제어하는 것이다.
경쟁 상태가 무엇인지 먼저 살펴보자!

▶ 경쟁상태와 임계구역

공유된 자원에 여러 프로세스/스레드가 동시에 접근하려고 하면 임계 구역 안에서 경쟁 상태가 생길 수 있다.
- 경쟁상태(race condition) : 두 개 이상의 프로세스가 공유 자원을 가지고 경쟁하는 상태
- 임계구역(Critical Section (CS)) : 공유 자원 접근 순서에 따라 실행 결과가 달라지는 영역, 공유 자원이 속해있어 경쟁 상태가 발생할 수 있는 영역 -> 한 번에 하나의 프로세스만 접근할 수 있도록 보장해줘야함!
  - ex. 주방에서 가스레인지는 공유가 가능한 자원이지만, 믹서기를 사용할 때는 순서를 지켜야 하므로 공유가 불가능한 자원이므로 CS(임계구역) 이다.

▶ 버퍼문제

생산자 - 소비자 문제는 empty와 buffer full을 구별할 수 없는 문제가 발생한다. 이에 대한 해결책으로
- BUFFER_SIZE-1만큼 사용 가능하도록 하여 문제를 해결한다. 하지만, 이 방법은 버퍼의 한 자리는 절대 채울 수 없다. 《 IPC (프로세스간 통신) 》참고하기
- 정수 카운터를 통해서 버퍼가 다 찼는지 살펴본다. 카운터 변수를 사용하여 버퍼를 끝까지 채울 수 있게 된다!

하지만, 카운터를 사용했을 때도 경쟁상태로 인한 공용데이터 값의 불일치 문제가 발생하게 된다.

▷ Counter 버퍼 문제

카운터 값을 변경할 때는 아래의 과정을 거친다.

counter++ 연산

register1 = counter; // 현재 카운터 값을 레지스터에 넣고
register1 = register1 + 1; // 레지스터 값에 1을 더한다음에 다시 레지스터 값에 넣어 저장
counter = register1; // 카운터 값을 변경

counter– 연산

register1 = counter; // 현재 카운터 값을 레지스터에 넣고
register1 = register1 - 1; // 레지스터 값에 1을 뺀다음에 다시 레지스터 값에 넣어 저장
counter = register1; // 카운터 값을 변경

counter++, counter– 연산을 동시에 한 상황을 살펴보자

공유 변수(counter)를 병렬적으로 사용 -> 경쟁상태

즉, 실행 순서에 의해 값이 달라짐 -> 임계구역 문제 발생

S0: producer execute register1 = counter {register1 = 5} // register1 = 5
S1: producer execute register1 = register1 + 1 {register1 = 6} // register1 = 6, 아직 counter 변수 저장 x
S2: consumer execute register2 = counter {register2 = 5} // register2 = 5
S3: consumer execute register2 = register2 – 1 {register2 = 4} // register2 = 4, 아직 counter 변수 저장 x
S4: producer execute counter = register1 {counter = 6 } // counter = 6
S5: consumer execute counter = register2 {counter = 4} // counter = 4

▶ 임계구역 해결 방법

▷ 임계구역 문제

위 코드에서 살펴봤듯, 공유 자원 접근 순서에 따라 실행 결과가 달라진다는 것을 확인했다.

그럼 임계 영역 문제를 어떻게 해결할 수 있을까?
3가지 조건을 동시에 충족해야한다.⭐
- 상호 배제 (Mutual Exclusive)
  - 한 번에 하나의 프로세스만 임계구역에 들어갈 수 있음 (화장실 둘이 들어갈 수 없잖아..?😲)
- 진행 (Progress)
  - 임계 영역에 들어간 프로세스가 없고, 대기하는 프로세스만 있으면 대기가 무한대로 연기될 수 없음
  - 즉, 무조건 프로세스 하나는 진행해야함
- 한정된 대기 (Bounded Waiting)
  - Starvation(기아)를 방지하기 위해 일정 시간 대기하면 들어갈 수 있음

➡️ 임계 구역의 동시 접근을 해결하기 위해 Lock(잠금), peterson’s Algorithms(피터슨 알고리즘), Semaphore(세마포어) 와 같은 방법이 있다.

▷ S/W적 CS 문제 해결

① peterson’s Algorithms⭐⭐

프로세스 2개가 경쟁하는 상황에서 사용되는 솔루션이다. (두 개의 프로세스만 비교 가능하다는 한계 존재)

가정: load 와 store 기계 명령어를 수행할 땐, 인터럽트가 걸리지 않는다.
사용되는 변수 (두 가지)
- turn
  - 차례를 나타내는 변수
  - 임계 구역에 들어갈 프로세서가 P0인지, P1인지 결정
  - 0 또는 1 이 저장된다.
- flag
  - 프로세스가 임계구역에 들어갈 준비가 되었는지 나타내는 변수
  - flag[0]=true : P0(프로세스0)이 임계 구역에 들어갈 준비가 되었음을 의미
  - flag[1]=true : P1(프로세스1)이 임계 구역에 들어갈 준비가 되었음을 의미

flag[0] = false; // false은 임계 구역 사용을 원하지 않음을 뜻함.
flag[1] = true;
turn = 0; // 0 은 0번 프로세스를 가리킴, 1은 1번 프로세스를 가리킴

예시 1 ⭐⭐

첫 번째 프로세스 (P0)에 대한 코드

 P0: flag[0] = true // 임계 구역 사용을 원함
     turn = 1 // 1번 프로세스에게 차례가 감
     while( flag[1] && turn == 1 )
     {
          // flag[1] 이 turn[1] 을 가지고 있으므로 현재 사용중임
          // 임계 구역이 사용 가능한지 계속 확인
     }// 임계 구역
     ...
    // 임계 구역의 끝
   flag[0] = false // 사용 완료시 false로 바꿔준다.

두 번째 프로세스 (P1)에 대한 코드

P1: flag[1] = true // 임계 구역 사용을 원함
    turn = 0 // 0번 프로세스에게 차례가 감
    while( flag[0] && turn == 0 )
    {
         // 임계 구역이 사용 가능한지 계속 확인
    }// 임계 구역
    ...
    // 임계 구역의 끝
    flag[1] = false // 사용 완료시 false로 바꿔준다.

예시 2 ⭐⭐

첫 번째 프로세스 (Pi)에 대한 코드

 Pi: flag[i] = true // 임계 구역 사용을 원함
     turn = j // j번 프로세스에게 차례가 감
     while( flag[j] && turn == j )
     {
          // flag[j] 이 turn[j] 을 가지고 있으므로 현재 사용중임
          // 임계 구역이 사용 가능한지 계속 확인
     }// 임계 구역
     ...
    // 임계 구역의 끝
   flag[i] = false // 사용 완료시 false로 바꿔준다.

두 번째 프로세스 (Pj)에 대한 코드

 Pi: flag[j] = true // 임계 구역 사용을 원함
     turn = i // i번 프로세스에게 차례가 감
     while( flag[i] && turn == i )
     {
          // flag[j] 이 turn[j] 을 가지고 있으므로 현재 사용중임
          // 임계 구역이 사용 가능한지 계속 확인
     }// 임계 구역
     ...
    // 임계 구역의 끝
   flag[j] = false // 사용 완료시 false로 바꿔준다.

▷ H/W적 CS 문제 해결⭐

① Locking 🔒

위에서 살펴본 피터슨 알고리즘과 같은 S/W 해결방법에는 한계가 있기 때문에, H/W 방법을 사용한다.

Locking 기법으로 CS문제를 해결해야 한다. ⇒ H/W적 해결을 해야한다.

H/W적 해결의 핵심
- atomic(원자적) 기계 명령어 사용
- 인터럽트가 되지 않는 특수한 명령어를 사용한다.
- 임계 구역이 존재할 때 하나의 프로세스가 CS(임계구역) 내에 있으면, 자물쇠를 걸어 다른 프로세스들은 CS에 들어오지 못하게 하는 방식이다. (화장실 하고 같은 상황)

Locking 기법의 기본 방식
- acquire lock
  - lock을 얻는 부분
  - lock을 얻어야만 CS영역에 진입할 수 있다.
- release lock
  - lock을 반환하는 부분
  - CS 실행 완료 시, lock을 돌려준다.

아래와 같이 나타낼 수 있다.
1. 임계 구역이 열렸는지 닫혔는지 확인
2. 열렸으면 들어가도 됨
3. 내가 들어가면서 닫음 (Lock → 무한 루프 문으로 구현)
4. 실행을 마치고 열고 나감

do{
  	acquire lock // lock을 얻는 부분 - CS영역에 진입가능
    	critical section
    release lock // lock을 반환하는 부분 - CS 실행 완료 시, lock을 돌려준다.
    	remainder section
} while (TRUE);

② Mutex Locks

등장 배경
- 기존 Lock을 사용하는 방식들은 복잡해서 Mutex Locks이라는게 등장했다!
- 다른 Lock 방식에 비해, 간단하다.
개념
- 공유된 자원의 cs에 하나의 Process 혹은 Thread가 접근하는 것을 막아준다. (즉, 동기화 대상이 하나)
  - ex. 데바데 게임으로써 살해(처형) 상태와 생존(도주) 상태가 둘 중 하나만 적용되어야 하는데 동시에 적용이되어서 살해당한 시체가 성공적으로 살인마한테서 도주하여 생존하는 오류가 발생하였다. 두 상태가 동시에 적용되지 않아야 할때 이를 방지하기 위해 사용하는게 뮤텍스(상호배제)이다.
- 공유 자원을 사용중인 스레드가 있을 때, 다른 스레드가 공유 자원에 접근한다면 Blocking 후 대기 큐로 보낸다.
- 즉, 바쁜 대기를 통해 lock을 얻으려고 시도하지만, 다른 스레드가 lock을 해제할 때까지 대기 큐를 사용하여 다른 스레드를 대기시키는 것이다.
사용 함수
- acquire() : lock 획득
- release() : lock 반환
Mutex Locks의 문제점
- 다른 Lock 방식들과 마찬가지로, Busy Waiting 방식을 사용한다.
- Busy Waiting
  - 특징 : while문을 계속 돌며, CS 진입을 대기하는 것, “지금 자리 있어? 나 들어가도 될까? 계속 물어봄”,
  - 단점 : 반복문을 반복하기 때문에 계속적으로 Context Switching이 발생하며 이로 인해 오버헤드가 발생한다.

③ spinlock

개념
- 기본적으로 뮤텍스와 Busy Waiting을 하기 때문에 유사하다고 볼 수 있다.
- 하지만, 대기 큐를 갖지 않는다.
대기큐를 갖지 않으면 비효율적인거 아니야 언제 사용하지?
- 컨텍스트 스위칭 시간이 짧을 때
  - ex. 대기실까지 이동하는 시간보다 식다엥 진입하게 될 시간이 더 짧을 때
- 멀티 코어 프로세스일 때
  - ex. 직원이 여러 명 있는 식당일 때 (계속해서 지금 자리 있어? 라고 물어보는 손님을 상대하는 직원이 존재할 떄)

④ Semaphore (세마포어)⭐

개념
- 세마포어란 깃발🚩 수기 신호이다. 여러 대의 기차가 하나의 철로를 공용하여 쓸 때, 오직 하나만 지나갈 수 있도록 하기 위해 양쪽 끝 선에 깃발 표시를 하여 사고가 안나게 하였던 장치이다.
- 공유된 자원의 cs에 여러 Process 혹은 Thread가 접근하는 것을 막아준다. (즉, 동기화 대상이 여러개)
  - ex. 식당(CS)에 여러 명의 손님 입장 가능
- CS에 진입한 순간 진입한 스레드는 P라고 외치고, 나갈 땐 V라고 외친다.
  - ex. 식당에 진입한 순간 진입한 손님은 p라고 외치고 나가는 손님은 v라고 외친다!
문제점
- 데드락(deadlock) 또는 기아(Starvation) 발생 가능성 (LIFO 형태로 제거할 경우)

CS 진입을 프로세스들은 2가지 방식으로 기다릴 수 있다!
- 즉, 세마포어를 사용하면 Busy Waiting 방식을 사용하지 않아도 된다.

sleep wating 방식

대기 큐를 사용하여 사용 가능한 자원이 생기면 진입을 허가하는 방식

Busy Waiting (=spin lock) 방식

어떠한 프로세스가 먼저 임계 구역에 진입을 할 수 있을지에 대한 처리를 할 수 없다.
음수의 값만큼 대기하는 프로세스가 있다는 뜻

뮤텍스 vs 세마포어
- 뮤텍스(Mutex) : 공유된 자원의 cs에 하나의 Process 혹은 Thread가 접근하는 것을 막아준다. (즉, 동기화 대상이 하나)
- 세마포어(Semaphore) : 공유된 자원의 cs에 여러 Process 혹은 Thread가 접근하는 것을 막아준다. (즉, 동기화 대상이 여러개)

▷ Deadlock

개념
- 교착 상태
- 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에, 무한 대기 상태에 빠지는 상태

▷ 우선순위 역전(Priority Inversion)

우선순위가 가장 높은 프로세스 A, 중간인 B, 가장 낮은 C가 존재할 때,

프로세스A가 CS 영역을 사용하고자 할 때, 프로세스 C가 CS 영역을 이미 사용 중이라면, 프로세스 C가 lock을 걸어 놨기 때문에 프로세스A는 우선순위가 높더라도 대기 상태에 들어가야한다.
이 타이밍에 공유자원을 필요로 하지 않는 B가 작업을 수행하기 위해서 오게 된다. B는 C보다 우선순위가 더 높은 프로세스이고 공유자원 또한 필요로 하지 않는 프로세스 이기 때문에 C는 하던 작업을 멈추고 B에게 CPU를 내어주게 된다.
결국 B가 작업을 모두 완료한 후, 다시 C가 작업을 진행하게 되고 최종적으로 A가 진행되어 진다.

➡️ 이렇듯, 상대적으로 우선순위가 가장 높은 프로세스인 ‘A’가 마치 우선순위가 가장 낮은 프로세스처럼 실행이 되는 현상인 우선순위 역전이 일어나게 된다.

➡️ 즉, 공유자원에 대한 lock에 대한 개념 때문에 발생하는 현상이다.

우선순위 역전 문제 해결 방법 : 우선순위 상속

낮은 우선순위 프로세스 C가 높은 우선순위 프로세스 A의 우선순위를 상속받아, CS를 실행한 후 Lock을 풀고 원래 우선순위로 복귀하는 것이다.(일시적으로 우선순위 높여줌)
이렇게 상속을 사용한다면, 낮은 우선순위 프로세스 C는 프로세스 B의 방해를 받지 않고 우선순위를 일시적으로 높여서 빨리 처리되도록 할 수 있다.

📎참조

성결대학교 강영명 교수님 운영체제 (2023)
『 Operating System Concept 10th 』
https://taegyunwoo.github.io/os/OS_SynchronizationTools
https://gooweon.tistory.com/147
https://velog.io/@octo__/%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4Semaphore
https://jwprogramming.tistory.com/13
https://www.youtube.com/watch?v=oazGbhBCOfU ⭐추천
https://namu.wiki/w/%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4
https://yabmoons.tistory.com/663
https://taeyoungcoding.tistory.com/m/369
https://ko.wikipedia.org/wiki/%ED%94%BC%ED%84%B0%EC%8A%A8%EC%9D%98_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

박시은