[Thread] 동기화와 교착상태

Thread

 

Synchronization

• 동기화(synchronization)

  • 스레드는 자원을 공유하기 때문에 동시에 여러 스레드가 실행되면 공유 자원에 대해 동기화가 발생할 수 있다.
  • 실행 흐름은 순차적으로 진행되지만, 자원은 한정적인데 여러 스레드가 동시 접근해서 사용하려고 하면 문제가 생기게 된다.
  • 공유 메모리에 대해서 한 번에 한 스레드만 공유자원에 접근할 수 있도록 만들어 동기화 문제를 해결할 수 있다.

• 임계영역(critical section)

  • 멀티스레드 프로그램에서 공유 자원이 참조 가능한 코드 영역을 말한다.
  • 한 스레드가 사용 중인 자원은 작업이 끝날 때까지 lock을 걸어서 다른 스레드가 사용할 수 없도록 한다.
  • 자바에서는 임계영역을 지정하기 위해 동기화 메소드와 동기화 블록을 제공한다. 스레드가 동기화 메소드나 블록에 들어가면 lock을 걸어 다른 스레드가 임계영역 내의 코드를 실행하지 못하도록 한다.
  • 다른 동기화 객체보다 빠르고 효율적이다.

• 뮤텍스(mutex)

  • 임계영역과 마찬가지로 공유자원에 여러 스레드가 접근하려고 할 때, lock을 이용해 한 번에 하나의 스레드만 접근하도록 허용하는 것이다.
  • 임계영역은 한 프로세스 내의 스레드에만 사용 가능하지만 뮤텍스는 서로 다른 프로세스에 속한 스레드에도 적용 가능하다.

• 세마포어(semaphore)

  • 한정된 자원을 여러 스레드가 사용하려고 할 때 접근을 제한한다.
  • 다중 스레드 간 공유 자원 접근 순서를 제어하고 공유 자원의 수와 접근 스레드 수에 따라서 보다 유연하게 공유영역으로의 접근을 제어한다.

• 이벤트(event)

  • 특정한 이벤트가 발생했음을 다른 스레드에게 알린다.
  • 스레드의 작업이 종료되면 신호상태로 변경되고, 다른 스레드가 작업하도록 한다.

• waitable timer

  • 특정 시간이 지나면 대기 중인 스레드에게 알린다.
  • 정해진 시간이 지나면 자동으로 신호상태로 변경된다.

 

 

Deadlock

• 교착상태(deadlock)

  • 두 개 이상의 작업이 하나씩 자원을 소지(hold)하고 있으면서 상대방이 가진 자원을 서로 원하고(need) 있는 상태
  • 어떤 작업도 실행되지 못하고 계속 서로 상대방의 작업이 끝나기 만 바라는 무한정 대기상태

• 교착상태 발생 조건

  • 상호배제(Mutual exclusion) : 한 번에 한 프로세스만이 자원을 사용
  • 점유대기(Hold and wait) : 하나 이상의 자원을 소지한 프로세스가 다른 프로세스가 가진 자원을 추가로 얻기 위해 대기
  • 비선점(No preemption) : 자원을 강제적으로 뺏을 수 없고, 사용중인 프로세스가 종료된 후 반환되어야 사용 가능
  • 환형대기(순환대기, Circular wait) : A는 B의 자원을 대기하고, B는 C의 자원을 대기하고, ..., N은 A의 자원을 대기
  • 이 조건을 모두 만족하면 교착상태가 발생하게 된다.
  • 각 조건은 서로 완전히 독립적이지 않고 연관되어있다. 순환대기의 경우 상호배제, 점유대기, 비선점 조건을 만족해야 만족된다.

• 교착상태의 예방

  • 교착 상태 발생 조건 중 하나를 제거함으로써 교착상태가 일어나지 않도록 한다.

  • 자원의 낭비가 심하고 시스템 처리율이 감소될 수 있다.

  • 상호배제 조건의 제거

    • 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.

  • 점유 대기 조건의 제거

    • 수행 전 모든 자원을 할당시켜주고 자원을 점유하고 있지 않을 때에만 자원을 요구하도록 한다.

  • 비선점 조건의 제거

    • 선점 가능한 프로토콜을 만들어준다.
    • 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때는 점유하고 있는 자원을 반납하고난 후 요구한 자원을 기다리게 한다.

  • 환형 대기 조건의 제거

    • 자원 유형에 따라 순서를 매긴다.

• 교착상태의 회피

  • 자원할당 상태(사용 가능한 자원 수, 할당된 자원 수 등)를 검사해 교착상태가 발생하면 피해가도록 한다.

  • 불안전상태이면 교착상태가 일어날 수 있으므로 시스템이 불안전상태가 되면 안정상태가 되도록 회피하는 알고리즘을 수행한다.

  • 자원 할당 그래프 알고리즘(Resource Allocation Graph Algorithm)

    • 교착상태 회피를 위해서 자원할당그래프에 예약간선(claim edge)을 추가
    • 시스템에서 자원이 반드시 미리 예약되어 그래프에 예약간선이 모두 표시되어야 한다.

  • 은행원 알고리즘(Banker’s algorithm)

    • 필요한 자원의 최대 개수를 미리 신고해 프로세스가 자원을 요청했을 때 요청을 수락하여도 안전상태에 머무를 수 있는지 판단 후 요청을 수락한다.
    • 안전상태가 아니게 된다면 다른 프로세스가 끝날 때 까지 요청 수락 대기

• 교착상태의 탐지

  • 자원 할당 그래프를 통해 교착 상태를 발견한다.

• 교착상태의 회복

  • 교착 상태가 일어난 프로세스를 종료

    • 교착 상태의 프로세스를 모두 중지
    • 교착 상태가 제거될 때까지 한 프로세스씩 중지

  • 프로세스에 할당된 자원을 선점

    • 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스로 할당하고, 해당 프로세스는 일시 정지시킨다.
    • 우선 순위가 낮은 프로세스 위주로 자원을 선점할당한다.