[운영체제] 프로세스 동기화

프로세스 동기화가 필요한 이유

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

 

race condition이란?

• 여러 프로세스(또는 스레드)가 공유자원에 동시에 접근할 때 공유자원에 대한 접근 순서에 따라 실행 결과가 달라질 수 있는 상황. 동시에 접근할 때 자료의 일관성을 해치는 결과가 나올 수 있다.
• 임계구역(critical section) : 여러 프로세스(또는 스레드)가 자원을 공유하는 상황에서 하나의 프로세스(스레드)만 접근할 수 있도록 제한해둔 영역 -> race condition을 막을 수 있는 해결책이 될 수 있다.

CSP(Critical Section Problem)란?

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

CSP 문제 해결방안 3가지 

critical section problem에 대한 해결안은 아래 세가지 요구조건을 충족해야한다

• mutual exclusion(상호배제) : 프로세스 P_i가 자기의 임계구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계구역에서 실행될수 없다.
• progress(deadlock 회피) (진행) : 임계구역을 사용하고 있지 않다면 다른 프로세스가 접근할 수 있도록 한다
  • 자신의 임계구역에서 실행되는 프로세스가 없고, 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는데 참여할 수 있으며, 이 선택은 무기한 연장될수 있다.
• bounded waiting(starvation 회피) (한정 대기) : 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
  • 임계구역 진입횟수에 한계를 두어 같은 프로세스가 계속해서 독점해서 사용하지 못하게 한다. -> 다른 프로세스들이 기아상태에 빠지지 않게 한다

peterson solution이란?

• CSP를 소프트웨어 기반으로 해결. 두 프로세스가 두개의 데이터 항목을 공유하며 해결.
  • int turn  : 임계구역으로 진입할 프로세스의 순번(turn = i이면 프로세스 Pi가 임계구역에서 실행)
  • bool flag[2] : 특정 프로세스가 임계구역으로 들어갈 준비가 되었다는 것을 나타냄 (flag[i] = true면 프로세스 Pi가 임계구역으로 들어갈 준비가 되었다는 것)

• 프로세스 Pi가 임계구역으로 진입하기 위해 flag[i]를 true로 만들고 turn을 j로 지정한다 (프로세스 Pj가 임계구역으로 진입하기를 원하면 진입가능하다는 것을 보장)
• 임계구역으로 진입하기 전 flag[j]가 true인지 확인하고(Pj가 임계구역에 진입해 있는지 확인) 그렇다면 무한루프, 아니라면 무한루프를 빠져나와 critical section으로 진입
• peterson solution은 완벽한가?
  • peterson solution은 3가지 요구조건을 모두 만족한다
    1. mutual exculsion 
       • while(flag[j] && turn == j) 로 busy waiting을 사용하는 동기화 프로세스. 어떠한 스레드라도 해당 조건을 만족하면 무한루프에 빠진다.
       • 다른 프로세스에서 반복분의 조건을 변경한다면 무한루프에서 탈출할 수 있음
       • 하나의 프로세스가 busy waiting을 넘어 그 아래 임계구역을 넘어갈때 다른 프로세스가 busy waiting의 반복문 조건을 만족하도록 flag와 turn을 조작 => 오직 하나의 프로세스만이 임계구역에 도달할 수 있음
    2. progress
       • 크리티컬 섹션을 이용하는 프로세스가 없는 경우, 어떤 프로세스라도 지체없이 크리티컬 섹션에 접근할 수 있는가?
       • 각 프로세스에 대해 초기 flag 값은 false를 가지고 있다가 크리티컬 섹션에서 할 작업이 생기면 피터슨의 솔루션에 접근하여 true 값을 가진다
       • flag가  2개인 경우에는 해당 조건을 고려할 필요가 없다. 상호배제에 의해서 이미 동기화 문제가 해결되기 때문
    3. bounded waiting
       • 어떠한 프로세스도 무한히 대기하는 기아상태(starvation)에 빠져서는 안된다
       • 프로세스가 2개인 해당 솔루션에서는 한쪽이 대기를 하고있다면 다른 한쪽이 critical section을 작업을 한 후 해당 critical section을 작업한 프로세스의 flag가 false가 되는 순간 대기하던 프로세스가 바로 무한루프를 빠져나와 임계구역으로 진입(실행)하므로 기아상태는 발생하지 않는다
  • 단, peterson solution의 특징이자 제약은 참여하는 프로세스가 최대 2개인 경우만 고려한 것 => 프로세스 갯수가 3개 이상인 경우에서는 사용할 수 없다
  • 3개 이상의 프로세스를 가지는 환경에서 해당 조건을 만족하려면 별도의 버퍼를 두어 프로세스가 이미 실행되었는지 파악하거나 일정한 시간대에 따라 counter를 돌려 대기시간에 따른 우선순위를 부여하는 스케줄링을 사용해야함
  • 또한 while(flag[j] && turn == j) 부분에서 임계 영역에 들어가기 위해 기다리고 있는 프로세스는 위 코드에 의해 무한루프를 돌며 임계 영역 직전에 머무르게 되는데, 이 무한 루프에 CPU 자원을 사용 (=> busy waiting)

Atomicity란?

• Atomic variable : 원자성을 보장하는 변수
  • 멀티스레드 환경에서 동기화 문제를 synchronized 키워드를 사용하여 lock을 걸곤 하는데, 이런 키워드 없이 동기화문제를 해결하기 위해 고안한 방법
  • synchronized는 특정  Thead가 해당 블럭 전체를 lock을 하기떄문에 다른 Thread는 아무런 작업을 하지 못하고 기다리며 낭비가 심할 수 있다.
  • 이를 막기 위해 nonblocking 하며 동기화 문제를 해결하기 위한 방법이 atomic => 동작 핵심원리는 CAS알고리즘(Compared and Swap)
• CAS(Compared and Swap) 알고리즘
  • 멀티쓰레드환경, 멀티코어 환경에서 각 CPU는 메인 메모리에서 변수값을 참조하는것이 아닌, 각 CPU의 캐시 영역에서 메모리를 참조. 이때 메인메모리에 저장된 값고 CPU캐시에 저장된 값이 다른 경우가 있다
  • 현재 쓰레드에 저장된 값과 메인메모리에 저장된 값을 비교하여 일치하는경우 새로운 값으로 교체되고 , 일치하지않는다면 실패하고 재시도

mutex lock

• mutex의 원리
  • 임계구역을 보호하고, 경쟁조건을 방지하기 위해 mutext lock사용
  • 프로세스는 임계구역에 들어가기전에 lock을 획득하고 나올때는 lock을 반환해야한다(화장실 열쇠)
  • lock을 사용할 수 있다면 acquire()을 호출해 lock을 획득하고, 다른 프로세스가 접근하지 못하게 lock은 사용할 수 없게 된다
  • lock을 반환할때는 release()를 호출

• busy-waiting이란?
  • 임계구역에 들어가기 전 lock을 얻기 위해 acquire()에서 무한루프에 빠진다. 이는 CPU cycle을 낭비하게한다.
• spinlock이란?
  • lock을 얻기 위해 이를 얻으려 acquire을 수행하는 과정에서 lock이 가용되어지기를 기다리며 프로세스가 계속 반복 회전하므로 이를 spinlock이라고 부른다.
  • context switching을 하지 않고 잠시 루프를 돌며 재시도하는것

 

semaphore

• semaphore의 원리
  • mutex가 공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 하나의 Process 혹은 Thread가 접근하는 것을 막아주는 것이라면 semaphore는 공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌 즉, 동기화 대상이 하나 이상
  • 리소스의 상태를 나타내는 간단한 카운터. 카운팅 세마포어와 이진 세마포어로 나뉠수 있으며 이진 세마포어는 이진수(0 또는 1)를 사용한다. 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 기다리도록 해야한다.
  • mutex는 상태가 0, 1 두개 뿐인 binary semaphore
  • 세마포어(S)는 프로세스가 임계구역에 들어가려할때 wait()를 호출해 값이 감소하고 임계구역 작업을 끝내고 lock을 반납할 때 signal()을 호출해 값이 증가한다.
  • 세마포어가 0이 되면 모든 자원이 프로세스들에 의해 모두 사용중이라는 것을 의미 -> busy waiting 

• 세마포어 atomic 연산자의 종류
  • wait(), signal() 함수에서 변경하는 S도 공유변수라 critical section문제가 생길 수 있다. 커널과 하드웨어가 두 함수를 atomic exclusive하게 동작함을 보장해야 함
  • 같은 세마포어에 대해 두 프로세스가 동시에 wait()와 signal() 연산을 실행할 수 없도록 반드시 보장
    • 이를 보장하기 위해 다중 처리기 환경에서 모든 처리기에서 인터럽트를 금지해야한다
  • wait() : 세마포어가 0이하라면 프로세스가 busy wait, 1이상이라면 자원을 획득하여 사용(공유 데이터를 획득)
  • signal() : 자원을 다 사용한 후 반납
• 세마포어가 busy-waiting 문제를 해결하는 방법
  • 임계구역 진입을 위해 무한루프를 돌며 대기하는 대신 프로세스를 중지시키고 큐에 넣는다
  • S가 0이하면 waiting하는 프로세스를 중지시키고 waiting queue 에 넣고, 어떤 프로세스가 임계 구역에서 나오면 signal()함수로 대기 큐에 있는 프로세스를 waiting queue에서 빼고 깨워 ready queue에 넣는다.

monitor란?

• 세마포어의 경우 세마포어를 이용해 임계구역 문제를 해결할 때 프로그래머가 세마포어를 잘못 사용하면 다양한 유형의 오류가 난다. 이를 막기 위한 고급 언어 구조물 중 하나
• 하나의 lock과 여러 condition variable로 구성된다. lock을 이용하여 여러개의 쓰레드가 동시에 critical section에 접근하지 못하도록 제어역할 수행
• syncronized의 의미
  • Thread 사이의 동기화를 맞추는 기법
  • 각 일반 Instance안에 존재하는 Monitor를 이용하여 Thread 사이의 동기화를 수행
• wait()와 notify(), notifyAll() 메소드의 의미
  • wait() : Instance의 Monitor의 Condition Variable을 이용하여 구현. Condition Variable에서 대기중인 Thread는 notify(), notifyAll() 함수를 통해서 깨울수 있다.
  • notify() : Condition Variable에서 대기중인 임의의 하나의 Thread만을 깨우는 동작을 수행
  • notifyAll() : Condition Variable에서 대기중인 모든 Thread를 깨운다. 모든 Thread가 깨어나도 하나의 Thread만 Lock을 획득하고 나머지 Thread들은 다시 대기한다.

 

세마포어와 모니터는 deadlock과 starvation을 해결할 수 있는가?

• Monitor는 동시 접근에 대한 문제는 해결해주지만 동기화에 대한 문제를 완전히 해결하지는 못한다. 이를 해결하기 위해 도입한 것이 Condition 변수. Condition 변수를 통해 프로세스들은 순서를 보장받는다.

Priority Inversion이란?

• 우선순위 역전 : 우선순위가 낮은 프로세스 때문에 우선순위가 높은 프로세스가 실행되지 않는 현상
  • 공유자원의 동기화로인해 발생하며 필연적으로 발생한다. => 피해를 최소화하는 것이 목적
  • 우선순위가 낮은 프로세스가 세마포어를 소유하며 실행중일때 우선순위가 높은 프로세스가 세마포어가 없어서 실행할 수 없는 경우
• 해결기법
  
  • 우선순위 계승 프로토콜(priority inheritance protocol) : 우선순위가 낮은 프로세스가 세마포어를 소유하며 실행중일때 우선순위가 높은 프로세스가 세마포어가 없어서 실행할 수 없는 경우 이때 우선순위가 낮은 프로세스를 세마포어를 요청한 프로세스의 우선순위만큼 우선순위를 일시적으로 높이는 것
    • 높은 우선순위 프로세스를 블록하고 있는 프로세스가 높은 우선순위를 가진 프로세스의 우선순위를 계승. 해당 프로세스가 세마포어를 반환하면 원래 우선순위로 돌아간다
    • 단, 공유자원이 여러개 있고 순환적으로 획득될 때, 데드락이 일어날 수 있음
    • 구현이 어렵지 않고 비교적 좋은 성능을 낼 수 있음
  • 우선순위 상한 프로토콜(priority ceiling protocol) : 모든 프로세스의 우선순위와 각 프로세스가 요구하는 공유자원을 미리 알고있다는 가정하에 가능
    • 우선순위 계승 프로토콜을 개선하기위해 제안, 그러나 구현이 매우 어려워 잘 쓰이지 않는다.