[자료 구조] 프로세스 동기화 #1 critical section

 

먼저 포스팅했던 데드락에서의 연장선으로 프로세스 동기화에 대해서 포스팅한다.

주제에 대해서 좀 더 많은 자료를 공부하고 포스팅하려 하다 보니 텀이 발생하는 것 같다.

취업준비하며 공부할 내용이 생각보다 많다..기존에 알던 것들에 더해 정보들을 더해나가다 보니 이해를 해야 하는 부분이 굉장히 많은 것 같다.

 

혹시 잘못된 내용이 있다면 지적해주시면 감사합니다.

---

🤔데이터가 어떻게 접근하는지부터 알아보자

1. 저장소에 있는 Data를 연산하는 곳으로 보낸다.

2. 연산하는 부분에서 연산 후 연산 결과를 원 위치로 보낸다.

 

ex) CPU와 Memory(프로세스가 연산의 주체이며 주소공간이 저장소가 된다)

 

 

✔그럼 프로세스 동기화는 왜 필요할까

프로세스 동기화(Process Synchronization)

 : 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것

 

여러 프로세스가 서로 협력해 공유자원을 사용하는 상황에서 경쟁조건(race condition)이 발생하면 공유자원의 신뢰성이 떨어진다. 때문에 이를 방지하기 위해 프로세스들이 공유자원을 사용할 때 특별한 규칙을 만드는 것이다.

 

👀경쟁 상태(Race condition)?

두 개 이상의 프로세스가 공통 자원을 병행적으로(concurrently) 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이뤄졌는지에 따라 결과 값이 달라지는 상황을 말한다. 

공유 데이터의 동시 접근(Concurent access)은 데이터의 불일치 문제를 발생시킬 수 있다.

따라서 condition을 막고 일관성을 유지하기 위해 협력 프로세스 간 실행 순서를 정해주는 동기화(Synchronization)가 필요한 것이다.

---

경쟁 상태가 발생하는 경우는 대표적으로 3가지이다.

1️⃣ 커널 모드로 수행 중 인터럽트가 발생하는 경우

의도된 동작은 count ++과 count --이 모두 반영돼 count가 초기값을 유지하는 것인데, 만약 Load를 한 후에 인터럽트가 발생하는 경우 인터럽트의 결과는 반영되지 않고 count++만 반영된다.

이는 커널 모드의 수행이 끝나기 전 인터럽트를 받지 않도록 하는 방법(disable/enable)으로 문제를 해결할 수 있다.

 

>> 데이터를 건드리는 경우에 인터럽트가 들어와도 작업이 끝날 때까지 인터럽트를 처리하지 않도록 한다.(disable)

데이터 처리 작업이 완료된 후, 인터럽트로 넘겨서 인터럽트를 수행한다.(enable)

 

2️⃣ 프로세스가 시스템 콜을 호출해서 커널 모드로 수행 중인데 Context switch(문맥 교환)가 발생하는 경우

두 프로세스 간에 데이터 공유가 없어도 시스템 콜이 일어나서 커널 모드로 작동하는 경우에는 커널 주소 공간의 데이터를 공유할 수 있게 된다. 이때 작업 도중, CPU를 뺏기면 경쟁 상태가 발생하는 것이다.

그럼 두 번째 케이스의 경우, 어떻게 이것을 해결할 수 있을까?

>> 간단하다. CPU를 뺏어가면 문제가 발생하니, 커널모드에서 수행중일 때는 CPU를 뺏는 것(preempt)을 금하고, 커널 모드에서 유저 모드로 넘어갈 때 preempt를 되도록 함으로써 해결가능하다.

 

3️⃣ 멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근하는 경우

이 경우, 어떤 Count가 마지막에 Count를 저장했는지에 따라 결괏값이 달라진다.

싱글 프로세서의 경우는, 1번 케이스처럼 disable/enable 방법으로 해결 가능하나 멀티 프로세서의 경우 인터럽트 제어만으로는 해결할 수 없다.

 

>> 해결 방법

1. 한 번에 하나의 CPU만 커널에 접근 가능하도록 한다.

2. 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대해서만 lock/unlock을 하는 방식

 

1번의 경우 하나의 cpu에만 접근할 수 있는 비효율성으로 인해 2번을 주로 사용한다.

 

---

경쟁 프로세스는 3가지 제어 문제에 직면하는데, Mutual exclusion, deadlock, starvation이 있다.

1️⃣Mutual exclusion (상호 배제) 

Race condition을 막기 위해서는 두 개 이상의 프로세스가 동시에 임계영역(CS : Critical Section)에 진입하는 것을 방지하기 위해 사용되는 알고리즘

 

공유자원의 동시 사용을 방지하여 race condition같은 문제를 피할 수 있다.

 

2️⃣Deadlock (교착상태)

race condition의 예방을 위한 상호 배제를 시행하게 되면 추가적으로 제어 문제가 발생하는데, 교착상태이다.

프로세스가 각자 프로그램을 실행하기 위해 두 자원 모두를 필요로 하므로 필요한 두 리소스를 사용해 프로그램을 수행할 때까지 먼저 소유한 자원을 해제하지 않는다. 이런 상황에서 프로세스는 교착 상태에 빠질 수 있다.

 

3️⃣Starvation (기아 상태)

프로세스들이 더는 진행을 못하고 영구적으로 블록된 상태로, 시스템 자원에 대한 경쟁 도중 발생하거나 프로세스 간의 통신 과정에도 발생할 수 있는 문제이다. 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리기에 결과적으로 아무것도 완료하지 못하는 상태가 된다.

 

특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태

 

이처럼 위 3가지 경우를 야기하는 경우는 항상 발생하는 것이 아닌, 특정 순서대로 수행되었을 때 발생하는 것이다.

문제는 디버깅을 할 때는 보이지 않는다는 것이며, 발생 후 모든 프로세스에 원하는 결과를 보장할 수 없기에 더욱 큰 문제로 이어질 수 있다. 

---

앞서 언급했던 프로세스 동기화에서 race condition을 예방할 수 있는 방법이 있는데, 

유저 동기화에는 Critical Section(임계영역), 커널 동기화에는 Mutex(뮤텍스), Semaphore(세마포어)가 있다.

 

Critical Section(임계 구역)

: 멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근하면 안되는 공유자원의 코드

 

코드 상에서 Race condition이 발생할 수 있는 특정 부분이다. 즉, 공유 데이터를 접근하는 코드 부분

시간이 지나면 임계구역은 종료되며, 특정 프로세스가 임계구역에 접근하기 위해서는 지정된 시간만큼 대기해야 한다.

이 경우에 쓰레드나 프로세스가 배타적인 사용권 보장을 받기 위해 세마포어와 같은 동기화 매커니즘이 사용된다.

 

• enter section(entry section) : 각 프로세스가 임계 구역(critical section)에 들어가기 위해 진입허가 요청을 하는 코드가 있는 부분
• critical section : 한 프로세스가 자신의 임계구역에서 작업을 수행하는 동안에는 다른 프로세스는 그들의 임계 구경게 접근 불가하다
• exit section : 임계 구역을 빠져나오는 코드가 있는 부분
• remainder section : 나머지 구역

 

 

임계구역 문제를 해결하기 위한 3가지 조건

임계구역 내의 문제들은 3가지 조건을 충족 시 해결가능하다

1. Mutual Exclusion(상호배제) : 하나의 프로세스가 임계구역에 들어가 있으면 다른 프로세스는 들어갈 수 없다.

2. Progress (진행) : 임계구역에 들어간 프로세스가 없다면, 어느 프로세스가 들어갈 것인지 적절히 선택해야 한다

3. Bounded Waiting (한정 대기) : 기아 상태를 방지하기 위해, 들어갔다 나온 프로세스는 다음에 들어갈 때 제한을 준다.

 

>>임계구역 진입 횟수에 제한을 두어 같은 프로세스가 계쏙 해 독점 사용하지 못하도록 한다. => 다른 프로세스들의 기아상태를 예방한다

 

[Algorithm 1]

현재 Critical Section에 들어갈 프로세스가 어떤 프로세스인지를 한 변수로 나타내 일치하는 프로세스만 진입하도록 하는 단순한 방식

//Synchronization variable
    int turn;
    intially turn = 0;
    //p[i]인 프로세스가 자신의 턴이 되기 위해서는 turn = i 가 되어야 한다.
    
// Process P0
          do{
          while (turn !=0); //turn이 본인 순서가 안니면 대기
          crtical section // 본인 순서라면 critical section을 수행
          turn = 1; //critical section 사용이 끝나면 다른 프로세스의 turn으로 바꾼다
          remainder section // critical section이 아닌 다른 section의 작업을 수행
          }while(1);

Mutual Exclusion(상호 배제)는 만족하나 Progress(진행)은 만족하지 못한다.

다른 프로세스가 critical section를 수행하고 나서 턴을 바꿔줘야 자신이 차례가 될 수 있다. 누군가 critical section에 접근하지 않으면 turn도 바꿔주지 않기 때문에 progress문제가 발생한다.

 

[Algorithm 2]

특정 프로세스가 Critical Section에 진입할 준비가 되었다는 것을 나타내는 변수를 두어, 다른 프로세스가 Critical Section에 진입하려 한다면 현 프로세스는 기다리는 방법이다.

//Synchronization variables 
        boolean flag[2]; (initially flag[0] = flag[1] = false)
        //만약 준비완료 상태가 되면 flag[i] == true
        
//Process P[i]
		do{
          flag[i] = true; //자신의 flag를 true로 설정
          while(flag[j]); //다른 flag가 true인지 확인 후, true면 대기
          critical section //다른 flag가 true가 아니라면 critical section 수행
          flag[i] = false; //자신의 flag를 false로 바꾼다
          remainder section //crtical section 외의 section을 수행
          } while(1);

critical section을 수행하지 못했지만, 둘 다 flag를 true로 설정한 상태가 되면 계속 critical section에 접근할 수 없기에 progress 문제가 발생한다. 이 경우에도 critical section에 들어갔다 와야 flag를 내릴 수 있기에 누구도 진입하지 못하게 된다.

 

[Algorithm 3]

Peterson's Algorithm (피터슨의 알고리즘)

CSP(Critical Section Problem)를 소프트웨어 기반으로 해결하는 방법

두 프로세스가 두 개의 데이터 항목을 공유하며 해결

위 3가지 조건을 충족하며 임계구역 문제를 해결한다. flag&turn변수를 활용

//Peterson`s Algorithm : combined synchronization variables of algorithm 1&&2

//Process P[i]
    do{
    flag[i] = true; //깃발들기
    turn =j; //상대방으로 순서 바꾸기
    while(flag[j] && turn ==j); // 상대방이 깃발을 들고 상대방 순서일 때는 대기
    critical section // 아닐 경우 자신의 critical section 진행
    flag[i] = false; // 자신의 깃발 내려놓기
    remainder section // 나머지 코드 실행
    }while(1);

자신의 깃발을 들고, 턴은 상대로 바꿔준다. 상대방의 턴과 순서가 본인일 경우에만 critical section이 진행되기에 3가지 해결법의 충족 조건을 만족한다.

 

그러나 프로세스가 많이 몰리게 되면 계속 while 문을 대기해야 하는데, Busy Waiting(바쁜 대기)상태라고 부른다.

cpu 자원을 계속 사용하면서 critical section에는 들어가지 못하고 기다리는 경우를 의미한다. critical section을 사용할 수 있는 조건인지 계속 확인하는 과정(while문)을 뜻한다.

 

---

 

공유자원을 안전하게 관리하기 위해서 상호배제(Mutual exclusion)를 달성하는 기법이 두 가지 있다.

뮤텍스와 세마포어는 이를 위해 고안된 기법으로 서로 다른 방식으로 상호배제를 달성하는데, 이 글에서는 둘의 차이에 대해 간단히 알아보겠다.

 

  Mutex(뮤텍스)

: 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

 

- 임계 구역을 가진 스레드들의 실행 시간이 겹치지 않고 각각 단독 실행하는 기술

- 한 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제 기법

- 다중 프로세스들의 공유 리소스에 대한 접근 조율을 위해 동기화나 락 기법을 사용한다

- 뮤텍스 객체를 두 스레드가 동시 사용은 할 수 없다

 

  Sepaphore(세마포어)

: 두 개의 원자적 함수로 조작되는 정적 변수로써, 멀티프로그래밍 환경에서 공유 자원(critical section)에 대한 접근을 제한하는 방법

 

-  공유 자원에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근 가능

- 각 프로세스는 세마포어의 값을 확인, 변경할 수 있다

- 자원을 사용하지 않는 상태가 될 때, 대기하던 프로세스가 즉시 자원을 사용한다

- 이미 다른 프로세스에 의해 자원이 사용 중이라면, 재시도 전에 일정시간을 대기해야 한다

- 세마포어는 이진수를 사용하거나 추가적인 값을 가질 수 있다.

 

 

---

다음 포스팅에서 뮤텍스&세마포어에 대해 자세히 다루겠다.