프로세스 동기화 (Process Synchronization)

Posted by Jungwoon Blog on July 31, 2019

프로세스 동기화 (Process Synchronization)

이번 포스팅에는 프로세스간 동기화와 동기화시 발생할 수 있는 여러 문제와 해결 방법에 대해서 다뤄보도록 하겠습니다.

  • 협력하는 프로세스들 사이의 실행 순서 규칙 보장
  • 공유되는 데이터 일관성 (consistency) 보장

경쟁 조건 (Race Condition)

공유된 자원의 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말합니다.

  1. 여러 프로세스가 공유 데이터를 동시에 조작할 때, 실행의 특정 순서에 따라 결과가 달라지는 상황
  2. 공유 데이터 조작을 원자적 연산으로 처리하면 경쟁 조건은 발생하지 않는다.
* 원자적 연산

1. 어떤 연산의 결과가 외부의 간섭에 관계없이 전체가 완료되든지 전혀 실행되지 않은 상태로만 나타남 (All or Nothing)
2. 원자적 연산이 필요한 예
    1. 파일 시스템의 메타데이터 갱신
    2. 데이터베이스 시스템의 트랜잭션 처리

임계 영역 (Critical Section)

동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역을 의미합니다.

  • 경쟁 조건이 발생할 수 있는 프로그램 코드 부분
    • 다른 프로세스와 공유하는 변수나 파일을 변경
  • 임계 영역 문제의 해결 방법
    • 한 번에 하나의 프로세스만 임계 영역을 실행하도록 보장 (Lock)
      • 적절한 동기화 기법을 설계
      • 임계 영역 전체를 원자적으로 처리하는 효과
  • 임계 영역 문제 해결을 위한 기본 조건 : 3가지 조건을 모두 만족해야지 안전한 동기화를 했다 (=임계 영역 문제를 해결했다)
    • 상호 배제 (Mutual Exclusion)
      • 어떤 프로세스가 자신의 임계 영역 내에서 실행 중일 때 다른 프로세스는 각자의 임계 영역으로 진입할 수 없다.
    • 진행 (Progress)
      • 임계 영역에서 실행 중인 프로세스가 없다면, 임계 영역으로 진입하려는 프로세스들 중 하나는 유한한 시간 내에 진입할 수 있어야 한다.
    • 한정된 대기 (Bounded waiting)
      • 한 프로세스가 임계 영역에 대한 진입을 요청한 후에는 다른 프로세스의 임계 영역 진입이 유한한 횟수로 제한되어야 한다.
      • 즉 임계 영역에 대한 진입 요청 후 무한히 기다리지 않는다.

동기화의 기본적인 해결 방법

동기화 문제에 대한 가장 기본적인 해결 방법은 Lock 입니다. 특정 프로세스가 공유 자원에 접근 중일때는 다른 프로세스는 접근을 하지 못하도록 Lock을 걸어 해결합니다.

  • 임계 영역 진입 부분을 안전하게 처리
    • 임계 영역으로의 진입 가능성 확인과 진입을 원자적으로 처리
      • 경쟁 조건이 발생하지 않도록 함
      • 진입하게 되면 임계 영역을 잠금
    • 경쟁 조건이 발생하더라도 안전하게 처리
      • 복합적인 진입 조건 검사
      • 임계 영역 문제 해결을 위한 요구 조건 만족시킴
  • Lock 변수에 공동으로 접근하면 똑같이 임계 영역 진입에 대한 문제가 발생 할 수 있습니다.
  • 고전적인 소프트웨어 해결책 : 피터슨 알고리즘, 데커 알고리즘 - CPU가 여러개일때는 동작 안함
  • 임계 영역을 Lock으로 보호 (CPU, 하드웨어 수준에서 Lock을 건다)
    • Lock을 획득한 프로세스만 임계 영역으로 진입 허용
    • 잠겨져 있지 않으면 Lock을 잠그고 임계 영역에 진입
  • Lock을 원자적으로 처리하는 하드웨어 명령어
    • 중간에 인터럽트 되지 않는 명령어(non-preemptive)
    • TestAndSet() : 한 워드의 내용을 확인하고 수정하는 연산을 원자적으로 처리
    • Swap() : 두 워드에 내용을 서로 교환하는 연산을 원자적으로 처리

세마포어 (Semaphore)

프로세스의 동기화 기법으로 공유된 자원의 여러 프로세스가 동시에 접근하는 것을 막는 것

  • 기능
    • wait(S) : lock 획득
    • signal(S) : lock 해제
  • 세마포어 구현의 문제
    • Busy waiting 문제 - lock의 해제를 기다리는 동안 빈 반복문을 계속 도는걸 반복하기 때문에 Context Switching이 발생
      • 프로세스가 Lock을 기다리는 동안 계속 순환(spin) 실행됨
        • 짧은 Lock을 기다리는 경우, Context Switching 비용을 절약할 수 있음
        • 일반적으로는 CPU를 점유한 상태로 기다리므로 자원 낭비
        • 멀티 프로세서 시스템에 적합한 방법
      • 해결방법
        • block()을 통해서 프로세스를 대기 상태로 전환하고 CPU 스케줄링 실행
  • 세마포어 자체의 임계 영역 문제
    • wait(), signal() 연산의 원자성 보장 문제
    • 싱글 프로세서
      • wait(), signal() 실행 중에 인터럽트를 금지 (OS 수준에서) -> 인터럽트를 막으면 시스템이 동작하지 않을 수 있음
    • 멀티 프로세서
      • 모든 프로세서에서 인터럽트를 금지
      • 어려운 작업이며 성능 감소를 유발
      • 별도의 Lock 기법 필요

뮤텍스 (Mutex)

스레드의 동기화 기법으로 공유된 자원의 여러 스레드가 동시에 접근하는 것을 막는 것

  • 기아 (Starvation) - 무한 대기
    • 프로세스가 세마포어 큐에서 무한히 대기하는 상황
    • 높은 우선순위의 프로세스가 계속 들어오면 무한히 대기만 하는 상황
    • 시간이 지날 수록 우선순위를 높여주는 방법으로 해결 (Aging)
  • 우선순위 역전 (Priority Inversion)
    • 공유 자원에 대한 허가를 기다리는 동안 낮은 우선순위 프로세스와 스케줄링 순서가 뒤바뀌는 상황
    • 해결방법 : 우선순위 상속 프로토콜 -> 상위 우선순위 프로세스를 막고 있는 동안 우선순위를 상속

뮤텍스와 세마포어의 차이

  세마포어 뮤텍스
개수 여러개 하나
변화 뮤텍스로 변경 가능 세마포어로 변경 불가능
소유 X O
해제 세마포어를 가지지 않은 스레드도 해제 가능 뮤텍스를 소유한 스레드만 해제 가능

교착상태 (Deadlock)

서로 Lock을 놓기만을 기다리는 상황으로 두 개 이상의 프로세스가 어떤 사건을 기다리고 있는데, 같이 기다리는 프로세스 중 하나만이 그 사건을 발생시킬 수 있는 상황

[데드락이 발생할 수 있는 상태]

아래 4가지 조건을 모두 만족하지 않으면 교착상태가 발생할 수 있습니다.

  1. 상호 배제 (Mutual exclusion) : 자원은 한 번에 한 프로세스만이 사용할 수 있어야 합니다.
  2. 점유 대기 (Hold and wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 합니다.
  3. 비선점 (No preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 합니다.
  4. 순환 대기 (Circular wait) : 프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 합니다.