Post

프로세스 동기화

Posted
By idiot2222 21 min read





프로세스 동기화란

  • Independent Process
    • 다른 프로세스에게 영향을 주지도 받지도 않는 프로세스
  • Cooperating Process
    • 다른 프로세스에게 영향을 주거나 받는 프로세스
    • 프로세스 간 통신
      • 전자 우편, 파일 전송 등
    • 프로세스 간 자원 공유
      • 티켓 예매, 주식 거래 등 데이터베이스 접근 등
  • 공유 데이터에 동시에 2개 이상의 프로세스가 접근하면 데이터 불일치(data inconsistency)가 발생할 수 있다.

  • 데이터의 일관성(data consistency)을 유지하기 위해서 프로세스 동기화가 필요하다.

  • Bank Account Problem
    • 동기화 문제에 대한 예시이다.
    • 0원 밖에 없는 계좌가 있다.
      • 입금은 (계좌 잔액) 0원 + (입금할 금액) 100원 = 100원 이런 방식으로 진행된다.
    • A와 B가 동시에 계좌에 100원을 입금했다.
      • A의 입금 과정은 0 -> 100
      • B의 입금 과정 역시 0 -> 100
    • 200원을 입금했지만 100원은 증발해 버렸다.





임계 구역

  • Critical Section
  • 2개 이상의 프로세스 혹은 쓰레드가
    • 디비의 테이블이나 코드의 공유 변수 등 공유 자원에
    • 접근하여 변경을 일으킬 수 있는 영역을 말한다.

  • 간단하게 말하면 다른 애들이랑 같이 쓰는 걸 바꿔서 피해를 줄 수 있으니까 조심해야 되는 부분이다.

  • Solutions
    • 임계 구역 문제를 해결하기 위한 조건은 세 가지가 있다.
    • Mutual Execution
      • 상호 배제
      • 하나의 쓰레드만 임계 구역에 진입할 수 있어야 한다.
    • Progress
      • 진행
      • 임계 구역에 진입할 쓰레드의 결정은 유한 시간 내에 결정되어야 한다.
    • Bounded Waiting
      • 유한 대기
      • 임계 구역 진입을 대기하는 모든 쓰레드는 유한 시간 내에 임계 구역에 들어갈 수 있어야 한다.
    • 이 세 가지를 모두 만족해야 임계 구역 문제를 해결할 수 있다.





프로세스/쓰레드 동기화

  • 프로세스 동기화를 통해 얻을 수 있는 것은 세 가지가 있다.
    • 임계 구역 문제 해결 (예상과 다른 값이 나오지 않음)
    • 프로세스 실행 순서 제어
    • busy wait 등의 비효율성 제거
  • 프로세스 동기화에 사용하는 도구는 다음과 같다.
    • Semaphores
    • Monitor



Semaphore

  • 세마포는 상호 배제를 위한 소프트웨어 도구이다.
  • 구성은 간단하게 세 가지가 있다.
    • number of permit
      • 임계 구역 내부에 들어간 프로세스가 몇 개인지 세기 위한 값
    • acquire()
      • 임계 구역에 진입하려는 프로세스가 있으면 호출된다.
    • release()
      • 임계 구역에서 나가는 프로세스가 있으면 호출된다.
  • 간단하게 설명하면 임계 구역에 들어간 프로세스가 없으면 들여보내 주고
    • 임계 구역에 이미 누가 있으면 잡아뒀다가
    • 임계 구역에서 나가는 애가 있으면 잡아뒀던 애들 중에 하나를 들여보내 준다.
    • 이렇게 하면 한 번에 하나만 임계 구역에 들어갈 수 있다.


img-description Semaphore


  1. 임계 구역에 프로세스 A가 들어가려 한다.
    • acquire() 호출
    • 아무도 없으니 통과
  2. 임계 구역에 프로세스 B, C, D가 차례대로 접근해 왔다.
    • A가 이미 있으니 B, C, D 모두 세마포 내부의 큐에 잡힌다.
  3. A가 임계 구역을 나가면서 release()를 호출한다.
    • 잡혀있던 B가 풀려나서 임계 구역에 들어간다.
  4. 이를 반복한다.





전통적인 동기화 문제

  • Producer and Consumer Problem
    • 생산자 소비자 문제
    • 유한 버퍼 문제 (Bounded Buffer Problem)
  • Readers-Writers Problem
    • 공유 데이터베이스 접근
  • Dinning Philosopher Problem
    • 식사하는 철학자 문제



Producer and Consumer Problem


img-description Producer & Consumer


  • 생산자와 소비자
    • 생산자가 데이터를 생산하면, 소비자가 그것을 소비한다.
      • 컴파일러가 고급 언어를 어셈블리어로 생산하면, 어셈블러가 그 어셈블리어를 소비한다.
      • 서버가 데이터를 생산하면, 클라이언트는 데이터를 받아서 소비한다.
  • 유한 버퍼
    • 버퍼는 생산자와 소비자 사이의 창고 같은 개념이다.
      • 생산자의 생산 속도와 소비자의 소비 속도 차이의 갭을 줄이기 위해 만들어졌다.
    • 생산자는 데이터를 생산하여 버퍼에 저장한다.
      • 버퍼가 가득 차면 더 넣을 수 없다.
    • 소비자는 버퍼에서 데이터를 가져와 소비한다.
      • 버퍼가 비어 있으면 빼낼 수 없다.
  • busy-waiting
    • cpu가 다른 일은 하지 못하고 대기만 하는 현상이다.
      • 위에서 말한대로 생산자는 버퍼가 가득 찼는지, 소비자는 비어 있는지 체크가 필요하다.
      • 버퍼 체크가 계속 되는 동안 cpu를 잡아먹는 현상이 발생한다.



  • 생산자 소비자 문제
    • 생산자 소비자 문제에서 사용하는 데이터
      • in
        • 다음에 생산되어 들어올 데이터의 버퍼 포인터
      • out
        • 다음에 소비되어 나갈 데이터의 버퍼 포인터
      • count
        • 버퍼 내의 소비되지 않은 데이터 개수
        • 생산되면 ++;
        • 소비되면 –;
    • count와 버퍼는 생산자와 소비자가 같이 사용하는 공유 데이터이다.
      • 공유 데이터에 대한 동시적인 업데이트가 일어날 수 있다.
        • 즉, 임계 구역에 동시에 접근하는 꼴이다.
      • count가 이상한 값을 가지는 등의 잘못된 결과가 나타날 수 있다.
  • 생산자 소비자 문제 해결을 위해 세마포를 이용한다.
    • 상호 배제
      • 임계 구역에 대한 접근을 제한한다.
      • 생산자가 생산을 위해 임계 구역에 들어갔을 때 소비자를 잡아둔다. acquire()
        • 생산이 끝나면 release()
      • 소비자가 소비를 위해 임계 구역에 들어갔을 때 생산자를 잡아둔다. acquire()
        • 소비가 끝나면 release()
    • busy-waiting 해소
      • 프로세스를 세마포의 큐에 잡아둔다.
      • 생산자가 생산하려 할 때 버퍼가 가득찼으면 acquire() 호출, 소비자가 소비할 때 release() 호출한다.
      • 소비자가 소비하려 할 떄 버퍼가 비었으면 acquire() 호출, 생산자가 생산할 때 release() 호출한다다.


img-description Producer & Consumer


  • 초록색 세마포
    • 임계 구역에 생산자 혹은 소비자 하나만 들어갈 수 있다.
      • count, 버퍼 등의 공유 데이터에 하나씩만 접근하여 정확한 데이터를 유지할 수 있다.
  • 빨간색 세마포
    • 소비자가 소비하려는데 버퍼가 비어있을 때 busy-waiting을 방지할 수 있다.
    • 생산자가 생산을 하고 release() 해주면 그때 소비를 다시 시작한다.
  • 파란색 세마포
    • 생산자가 생산하려는데 버퍼가 꽉 차있을 때 busy-waiting을 방지할 수 있다.
    • 소비자가 소비를 하고 release() 해주면 그때 생산을 다시 시작한다.



Readers Writers Problem

  • 공유 데이터베이스에 관한 문제이다.
    • Readers
      • 데이터베이스를 조회만 하는 사람
    • Writer
      • 삽입, 수정, 삭제 등 데이터 변경 작업을 하는 사람
  • 문제 상황
    • 누군가 데이터를 조회하거나 수정하고 있을 때
    • 다른 writer가 또 데이터를 수정하면 데이터 정합성 문제가 발생한다.
  • 해결 방안
    • reader가 데이터를 조회할 때,
      • 다른 reader는 얼마든지 접근 가능
      • writer는 접근 불가능



Dinning Philosopher Problem


img-description Dinning Philosopher Problem


  • 식사하는 철학자 문제
    • 철학자는 다음과 같은 동작을 한다.
      • 생각한다.
      • 식사한다.
    • 식사를 위해서는 젓가락이 필요하다.
      • 왼쪽 젓가락을 집는다.
      • 오른쪽 젓가락을 집는다.
  • 문제 발생
    • 모든 철학자가 동시에 생각을 끝내고, 식사를 하려고 한다.
    • 모든 철학자가 동시에 왼쪽 젓가락을 집었다.
    • 이제 오른쪽 젓가락을 집으려고 보니 없어서 대기한다.
    • 모든 철학자가 오른쪽 젓가락을 기다리게 된다.
    • 모든 철학자가 기아 상태가 된다.





Deadlock

  • 교착 상태
  • 프로세스는 실행을 위해서는 여러 자원이 필요하다.
    • CPU, Memory, I/O 등
  • 그러나 내가 필요한 리소스를 다른 프로세스가 사용중이라면 대기해야 한다.
    • 이때 내가 키보드를 점유한 상태로 다른 프로세스가 갖고 있는 마우스를 대기하고 있다.
    • 마우스를 점유한 프로세스는 내가 갖고 있는 키보드를 대기하고 있다.
    • 이런 상황을 교착 상태라고 한다.
  • 교착 상태를 위한 필요 조건
    • Mutual Execution
      • 상호 배제
      • 누가 사용하는 리소스에 다른 프로세스가 접근할 수 없다.
    • Hold and Wait
      • 보유 및 대기
      • 본인이 필요한 다른 리소스를 점유한 상태로 또 다른 필요 리소스를 대기한다.
    • No preemption
      • 비선점
      • 다른 프로세스가 점유한 리소스를 뺏을 수 없다.
    • Circular Waiting
      • 환형 대기
      • 꼬리에 꼬리를 무는 형태로 대기를 하고 있는 상태
  • 이 네 가지를 모두 만족하면 교착 상태에 빠지게 된다.



자원 할당도

  • 어느 프로세스가 어떤 자원을 요청했는지, 어느 프로세스가 어떤 자원을 점유 중인지를 그린 그림이다.
  • 자원 할당도를 통해 교착 상태를 파악하기 쉬워진다.


img-description 식사하는 철학자 문제 자원 할당도


  • 네모
    • 젓가락(리소스)
    • 네모가 가리키는 하늘색 화살표가 네모를 점유중인 프로세스
  • 동그라미
    • 철학자(프로세스)
    • 동그라미가 가리키는 연두색 화살표가 동그라미가 요청중인 리소스



Deadlock Prevention

  • 교착 상태 방지
  • 교착 상태의 필요 조건 네 가지 중 하나라도 깨면 교착 상태를 방지할 수 있다.
    • 상호 배제
      • 자원을 공유 가능하게 한다.
      • 대부분의 자원에 대해 이 방법은 불가능하다.
        • 파일 정도
    • 보유 및 대기
      • 자원을 점유하고 다른 자원을 요청하지 못하게 한다.
      • 필요한 자원을 대기할 때 점유하고 있던 모든 자원의 점유를 포기하고 대기한다.
        • 기아 현상 발생 가능, 자원 활용률 저하
    • 비선점
      • 자원을 선점 가능하게 한다.
      • 대부분의 자원에 대해 이 방법은 불가능하다.
        • cpu 정도
    • 환형 대기
      • 자원에 번호를 부여하고, 번호의 오름차순으로 자원을 요청한다.
        • 자원 활용률 저하


img-description 환형 대기 예시


  • 자원들에 각각 R1~R5으로 번호가 붙어져 있다.
  • P1~P4는 번호의 오름차순 순으로 자원을 요청한다.
    • P1의 경우 R1 -> R2
    • P2의 경우 R2 -> R3
    • P3의 경우 R3 -> R4
    • P4의 경우 R4 -> R5
  • P5의 경우만 R1 -> R5으로 방향이 다르다.
  • 이런 방식으로 환형을 깰 수 있다.



Deadlock Avoidance

  • 교착 상태 회피
  • 프로세스가 필요한 리소스를 할당해주는 것이 os이다.
  • os의 적절한 리소스 분배로 교착 상태가 일어날 상황을 회피할 수 있다.
프로세스현재 필요한 리소스의 수최대로 필요한 리소스의 수
P1510
P224
P329
  • os는 총 12개의 리소스를 보유하고 있다.
  • 모든 프로세스가 교착 상태를 피할 수 있으려면 os는 리소스를 어떻게 할당해야 할까
    1. 세 프로세스 모두에게 현재 필요한 리소스만큼 할당해준다.
      • 12 - 9 = 3
    2. 한 프로세스를 끝내고, 걔가 점유하고 있던 리소스를 반환받기 위해서 P2가 필요한 2개의 리소스를 추가로 할당한다.
      • 3 - 2 = 1
      • P2 종료, 1 + 4 = 5
    3. 다음으로 종료할 수 있는 P1에 나머지를 할당한다.
      • 5 - 5 = 0
      • P1 종료, 0 + 10 = 10
    4. P3에 할당한다.
      • 10 - 7 = 3
      • P3 종료, 3 + 9 = 12
  • 이 경우 안전한 할당(Safe Allocation)이라고 한다.


프로세스현재 필요한 리소스의 수최대로 필요한 리소스의 수
P1510
P224
P339
  • os는 총 12개의 리소스를 보유하고 있다.
  • os가 적절하지 못한 리소스 분배로 프로세스가 교착 상태에 빠지는 것을
    • 불안전한 할당(Unsafe Allocation)이라고 한다.
      1. 모든 프로세스에 필요한 리소스를 분배한다.
      • 12 - 10 = 2
        1. P2에 리소스를 할당한다.
      • 2 - 2
      • P2 종료, 0 + 4
        1. P1이 필요한 리소스의 수는 5, P3이 필요한 리소스의 수는 6이다.
      • os가 현재 할당해줄 수 있는 최대의 리소스 수는 4밖에 되지 못한다.
      • 따라서 프로세스가 교착 상태에 빠지게 된다.



Deadlock Detection & Recovery

  • 교착 상태 검출 및 복구

  • 데드락을 허용하고, 교착 상태를 감지하여, 교착 상태를 복구하는 방법

  • 검출
    • 교착 상태에 빠진 프로세스가 있는지 검사한다.
    • 검사하는데 오버헤드가 발생한다. (계산 비용, 메모리 등)
  • 복구
    • 자원 할당 직후에 교착 상태를 검출하면, 자원 할당 직전으로 상태를 되돌린다.
    • 일부 프로세스를 강제 종료한다.
    • 일부 리소스를 os가 선점하여 다른 프로세스에 할당한다.
    • 역시 복구하는데도 오버헤드가 발생한다.



교착 상태 무시

  • 교착 상태를 위한 네 가지 필요 조건이 일어날 확률이 적다고 판단하여
  • 그냥 무시하고 내비두는 경우





CS, OS
cs os process
This post is licensed under CC BY 4.0 by the author.