OS의 process synchronization?

이전에는 OS의 프로세스 관리 법 중 프로세스 스케줄링에 대해 배웠다면

지금은, 프로세스 동기화에대해 배워보자.

Synchronization

Synchronization(동기화)가 필요한 이유

병행 프로세스 : 두 개 이상의 프로세스가 동시에 실행 상태에 있는 것으로 병행성이 높아져 시스템 성능은 향상되지만 공유자원 선점을 위한 프로세스 간 경쟁현상*이 발생하게 된다.

Race condition : 동시에 여러 개의 프로세스들끼리 하나의 자원을 두고 서로 경쟁하는 상황

                             자료의 일관성을 해치는 결과가 나타낼 수 있다.

-> 이 문제를 해결하기 위해서는, 동기화가 필요하다

   동기화(Synchronization)? 병행프로세스가 공유자원을 사용할 때, 프로세스 간 처리순서를 결정하는 방법

동기화 하는 방법(mutex, semaphore, monitor)에 대해 알아보기 전, 

임계영역이라는 것을 알아둘 필요가 있다.

위의 그림에서 나온 임계 영역이라는 것에 대해 알아보고 임계영역에서 하는 동기화 방법(mutex)에 대해 알아보자.

전형적으로, 프로세스는 크게 4가지 구역으로 나뉘는데 이 중 하나가 임계 영역이다.

(1) 진입 구역(entry section)

      - 각 프로세스는 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 한다.

      - 이러한 요청을 구현하는 코드 부분을 진입 구역이라고 한다.

 (2) 임계 구역(critical section)

 (3) 퇴출 구역(exit section)

      - 임계구역 뒤에는 퇴출 구역이 따라올 수 있다.

 (4) 나머지 구역(remainder section)

      - 코드의 나머지 부분을 총칭하여 remainder section이라고 한다.

임계영역(critical section)

 - 병행 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서 안되는 공유 자원 영역

   즉, race condition이 발생할 수 있는 프로그램 코드 부분

 - 임계영역 문제 : 임계 구역으로 지정되어야 할 코드 영역이 임계 구역으로 지정되지 않았을 때

     임계 영역 문제를 해결하려면 다음 3가지 요구조건을 충족해야 한다.

①     상호 배제(mutual exclusion) : 특정한 프로세스가 임계 구역에서 실행되는 동안, 다른 프로세스는 접근이 불가능하다

②     진행(progress) : 임계구역을 사용하고 있지 않다면, 다른 프로세스가 접근할 수 있도록 한다.

③     한계 대기(bounded waiting) : 같은 프로세스가 임계구역을 계속 독점해서 사용하지 못한다. 어떤 프로세스도 임계구역으로 들어가는 것이 무한 연기되서는 안된다.

  

여기서 상호배제가 즉 동기화 방법이다. 정확히 말하면 동기화 방법 중에 하나가 상호배제이다.

상호배제에 대해 자세히 알아보자.

상호 배제(mutual exclusion) 

 - 위에서 말했듯이 프로세스 간 경쟁을 피하기 위한 방법.

 - 한 프로세스가 공유자원을 사용하고 있을 때 다른 프로세스들이 자원을 동시에 사용하지 못하고 번갈아 가면서 접근하도록 하는 방법 즉 동기화 시키는 것

 - 상호배제 알고리즘

①     소프트웨어적 구현 : Peterson’s solution(피터슨의 해결방안), Dekker 알고리즘 등

* 단점: 속도가 느리고, 구현이 복잡하며, Busy waiting이 일어날 수 있는 가능성이 높음, 

    또한 Interrupt로 인해 Premumtiation 될 확률이 높음

* Busy wating: 계속적으로 무한 루프를 돌면서 최대한 다른 스레드에게 CPU를 양보하지 않는 것 = spinlock

②    하드웨어적 구현: Synchronization Hardware(동기화 하드웨어) 

  –> 구현 방식 2가지: 인스트럭션(test_and_set or swap)

더 이상 쪼개지지 않는 원자적 명령어로 구현(즉 하드웨어 명령어 이용)

*단점: 3개 이상의 프로세스가 하나의 공유자원을 사용하는 경우, Busy waiting이 일어날 수 있는 가능성이 높음

 

           동기화 하드웨어는 공유변수 lock을 이용한다.

           임계구역에서 작업할 때는 true, 작업하지 않을 때는 false라고 한다.

- 소프트웨어적 구현에서 피터슨의 해결방안에 대해 자세히 알아보자.

   피터슨의 해결안에서는 공유하는 2개의 데이터 항목을 가지고 해결

   int turn; //임계구역으로 진입할 프로세스의 순번(turn = i이면, 프로세스 i가 임계구역에서 실행)

   boolean flag[2]; // 특정한 프로세스가 임계 구역으로 들어갈 준비가 되었다는것을 나타냄

(flag[i] = true면, 프로세스 i가 임계구역에 진입할 준비가 되었다는 것)

   두 가지 데이터항목을 가진 프로세스 i의 실행구조를 보자.

        

-> flag[i] = true에 의해 프로세스 i는 임계구역에 들어갈 준비가 됐다는 것을 알려준다.

-> 그 밑에 turn = j 에 의해 프로세스 j가 실행될 차례라는 것을 알 수 있다.

Step 1. flag[i] == true (프로세스 i가 임계구역에 들어갈 준비가 됐다) 이고 

     turn == j이면(프로세스 j가 임계구역에 들어갈 차례)이므로,

     프로세스 i는 무한루프에 들어가 다른 프로세스 j가 끝날때 까지 기다리게 된다.

(만약, 프로세스 j가 준비가 덜 되었거나, 늦게 진입하면 setting turn = i)

 

      Step 2. 그리고 프로세스 j가 임계구역 작업을 마치고 flag[j]의 값이 false가 되면, 

           프로세스 i 는 무한루프를 빠져나와 임계구역에 들어가게 된다. 

 

      Step 3. 프로세스 i가 작업을 완료 후 flag[i] = false 로 설정하고, 다른 프로세스가 임계구역을 사용할 수 있도록 해준다.

          

      위 과정을 보면 mutual exclusion, progress, bounded waiting 이 3가지 조건을 만족함을 볼 수 있다.

     피터슨 해결방안 예시)

 - 하드웨어적 구현에서 test_and set 명령어 방법과 swap 명령어 방법에 대해 보자.

   둘다 공유변수 lock을 사용

   먼저, test_and set 명령어 방법

   Test_and_set인스트럭션

  - 프로세스가 아무리 많아져도 상호 배제을 만족한다.

  - 아무리 많은 프로세스가 동시에 while() 을 실행해도, 그 중 하나만 while()을 지나 Critical section에 진입할 수 있도록       

    하드웨어적으로 처리되어 있다.

  - 문제는, 임계구역의 상호 배제 조건은 만족시키지만, 한정된 대기(한계 대기) 조건을 만족시키지는 못한다.

  - 구현 구조

제일 처음에는 lock은 FALSE값으로 초기화되어 있다. 

따라서, 처음으로 실행한 프로세스는 첫 while문을 통과한다. 

그리고, TestAndSet에 의해서 lock은 TRUE가 되었으므로, 다른 프로세스가 임계 영역을 실행하려고 해도, while문에서 걸려서 실행할 수 없다. 상호 배제 조건을 만족하는 셈이다. 

그리고 임계 영역을 다 끝낸 프로세스는 lock값을 다시 FALSE로 되돌려서 다른 프로세스도 임계영역을 실행할 수 있도록 한다. 따라서, 진행 조건도 만족하는 셈이다.

 

       다만, 한정 대기 조건을 만족한다고 볼 수는 없다.

 그 다음으로 swap 명령어 방법

 Swap 인스트럭션

 - 0, 1만을 사용했던 Test-and-Set과는 달리, 임의로 key를 정할 수 있는 장점이 있다.

 - Test-and-Set과 마찬가지로 상호 배제 조건은 만족시키지만, 한정된 대기 조건을 만족시키지는 못한다.

 - 구현 구조

제일 처음에는 lock값이 FALSE로 초기화되어있다. 

따라서, lock과 key를 swap하면 key 값이 FALSE가 되어 바로 while문을 통과한다. 

하지만, lock값이 TRUE가 되었으므로 다른 프로세스는 while문을 빠져나가지 못한다. 

즉, 상호 배제 조건을 만족하는 셈이다. 그리고 임계 영역을 다 진행한 프로세스는 lock값을 FALSE로 되돌리므로 다른 프로세스도 임계 영역을 실행할 수 있도록 한다. 따라서, 진행 조건도 만족하는 셈이다.

 

      다만, 한정 대기 조건을 만족한다고 볼 수는 없다.

 + 한정 대기 조건을 만족하도록 Test_and_set명령어를 사용할려면 어떻게 해야할까?

  -> boolean waiting[n], boolean lock;을 전역변수로 선언한 뒤,

      waiting배열을 이용해 한정 대기 조건을 만족하도록 구현하면 된다.

  - 구현 구조

처음에 lock값은 FALSE로 초기화되어 있다.

처음으로 임계영역에 들어가는 프로세스에서는 TestAndSet에 의해서 key가 FALSE가 된다. 

따라서 바로 while문을 통과하여 임계 영역을 진행한다. 이

때, lock은 TestAndSet에 의해서 TRUE가 되었으므로 key값은 계속해서 TRUE이고,다른 프로세스는 while문을 통과하지 못한다. 따라서, 상호 배제 조건을 만족한다고 할 수 있다.

     그 다음, 임계 영역을 모두 진행한 프로세스는 waiting 배열을 i+1, i+2, ... , n-1, 0, ... i-1 순서대로 조사한다. 

조사한 순서에서 가장 처음으로 waiting값이 TRUE인 프로세스를 찾으면, 그 프로세스가 다음 차례로 임계 영역을 실행하는 프로세스가 된다. 그리고 만약 모두 조사했음에도 waiting값이 TRUE인 프로세스가 없다면 완전히 lock을 FALSE로 돌려버린다. (즉, lock을 놓아버린다.) 

즉, 임계영역에 들어가기를 원하는 모든 프로세스들이 최대한 n-1 번 안에는 임계영역에 들어갈 수 있게 된다. 

한정 대기 조건을 만족하게 되었다. 

또한, 기다리는 프로세스가 없는 경우는 당연히 lock이 FALSE값이 되므로 바로 프로세스가 임계영역에 들어갈 수 있다.  

진행 조건도 만족한다.

 

      따라서, 위 구현은 3가지 조건을 모두 만족하므로 임계 영역을 완벽하게 해결한다.

  

  - 예시)

지금까지 동기화 방법인 mutex에 대해 배웠다.

병행 처리를 위한 프로세스 동기화 방법은 mutex뿐만이 아니라 semaphore와 monitor가 존재한다.

세마포어(Semaphore)

 - 뮤텍스가 동기화에 있어 하나의 프로세스만 실행되게 하지만, 세마포어는 지정한 수 만큼 프로세스가 동시에 실행되도록 동기화가 가능하다.

 - 0과 1 값을 가지는 이진세마포어(=뮤텍스)와 0과 양의 정수 값을 갖는 카운터 세마포어로 구성

 - 세마포어는 한 개의 변수와 두 개의 연산을 가지고 동기화를 한다.

   int S, 

   P연산(wait 동작) : 임계 구역 들어가기 전에 수행(프로세스 진입 여부를 자원의 개수 S를 통해 결정)

   V연산(signal 동작) : 임계 구역에서 나올 때 수행(자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)

 * 단점 : 세마포어를 잘못 사용하면 임계구역을 보호할 수 없다.

예1) P() - P() : wake_up신호가 발생하지 않아 무한대기에 빠진다.

           예2) V() - P() : 상호배제가 보장되지 않는 경우

 - 구현 구조

모니터(monitor)

 - 공유 자원을 프로세스들에게 할당하는 데 필요한 데이터와 프로시저의 집합으로 이루어지는 병행성 고급언어 구조체 

   (세마포가 어셈블리 언어에 적합한 도구라면, 모니터는 그보다 고수준인 언어의 도구)

 - 한 순간에 단 한 개의 프로세스만이 모니터 내부에 있을 수 있다.

 - 프로세스는 오직 모니터 집입부만을 호출함으로써 공유데이터에 접근할 수 있다.

 - 모니터 내부의 데이터는 자료 추상화와 정보 은폐 기법을 기초로 하여 모니터 외부에서는 접근 불가

 - P연산(wait 동작), V연산(signal 동작) 사용

 - 모니터 구조