운영체제 25. 병행성 관련 버그

25. 병행성 관련 버그

25.1 비교착 상태 오류

원자성 위반 오류

• 다수의 메모리 참조 연산들 간에 있어 예상했던 직렬성(serializability)이 보장되지 않았다.(즉, 코드의 일부에 원자성이 요구되었으나, 실행시에 그 원자성이 위반되었다.)
• 문제의 해결책은 공유 변수 참조 앞 뒤에 락을 추가해준다. 이 자료구조를 사용하는 모든 코드들이 이 락을 먼저 획득해야 한다.

순서 위반 오류

• 두 개의(그룹의) 메모리 참조 간의 순서가 바뀌었다.(즉, A가 항상 B보다 먼저 실행되어야 하지만 실행 중에 그 순서가 지켜지지 않았다.)
• 오류를 수정하는 방법은 순서를 강제하는 것이다. 이러한 종류의 동기화에는 컨디션 변수가 잘 맞는다. 쓰레드간의 순서가 문제가 된다면 컨디션 변수(또는 세마포어)를 사용하여 해결할 수 있다.

25.2 교착 상태 오류

• 복잡한 락 프로토콜을 사용하는 다수의 병행 시스템에서 교착상태(deadlock)라는 고전적 문제가 발생한다. 락 L1을 갖고 있는 쓰레드1 이 또 다른 락 L2를 기다리는 상황에서 불행하게도 락 L3를 갖고 있는 쓰레드 2가 락 L1이 해제되기를 기다리고 있을 때 교착상태가 발생한다.
• 그래프에서 사이클의 존재는 교착상태 발생 가능성을 의미한다.

교착 상태는 왜 발생하는가

• 코드가 많아지면서 구성 요소 간에 복잡한 의존성이 발생하기 때문이다. 코드상에서 자연스럽게 존재하는 순환 의존성이 교착상태를 야기시키는 것을 방지하기 위해서 대형 시스템의 락 사용 전략의 설계는 매우 신중해야 한다. 또 다른 이유로는 캡슐화(encapsulation)의 성질 때문이다.

교착 상태 발생 조건

• 교착 상태가 발생하기 위해서는 네 가지 조건이 충족되어야 한다.

상호배제(Mutual Exclusion)

• 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권을 주장한다.

점유 및 대기(Hold - and - wait)

• 쓰레드가 자신에게 할당된 자원을 점유한 채로 다른 자원을 대기한다.

비선점(No Preemption)

• 자원을 점유하고 있는 쓰레드로부터 자원을 강제적으로 빼앗을 수 없다.

환형대기(Circular Wait)

• 각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 자원을 갖고 있는 쓰레드들의 순환고리가 있다.

교착 상태의 예방

순환 대기

• 가장 실용적인 교착 상태 예방 기법은 순환 대기가 절대 발생하지 않도록 락에 관련된 코드를 작성하는 것이다. 간단한 방법은 락 획득을 하는 전체 순서(total ordering)를 정하는 것이다.
• 복잡한 시스템에서는 두 개 이상의 락이 존재할 것이고, 모든 락들에 대해서 전체 요청 순서를 정하는 것이 쉽지 않을 수 있다. 물론 불필요할 수도 있다. 이 경우, 교착 상태를 피하기 위해 부분 순서(partial ordering)만을 정의할 수도 있다.

점유 및 대기

• 원자적으로 모든 락을 단번에 획득하도록 하면 예방할 수 있다. 하지만 그러기 위해서는 필요한 락들을 정확히 파악해야 하고 그 락들을 미리 획득해야 한다. 락이 실제 필요할 때 요청하는 것이 아니라 미리 모든 락을 획득하기 때문에 병행성이 저하되는 문제도 있다.

비선점

• 락을 한 번 획득하게 되면 이를 명시적으로 반납하기 전까지는 락을 보유하고 있는 것이 된다. 때문에 여러개의 락을 보유한 상태에서 추가로 락을 요청할 경우 문제 발생의 소지가 있다. pthread_mutex_trylock() 루틴은 락이 획득 가능하면 락을 획득하고 성공을 나타내는 코드를 반환 하거나, 락이 점유되었다는 것을 나타내는 에러 코드를 반환한다. 후자의 경우 락의 획득을 원한다면 나중에 다시 획득을 시도할 수 있다.
• 이 방식은 무한 반복(live lock)이라는 새로운 문제가 생긴다. 두 개의 쓰레드가 계속해서 락을 획득 하려고 시도하지만 두 쓰레드 모두 계속해서 락을 획득하지 못할 수 있다. 이 경우 두 개의 쓰레드는 계속해서 코드를 실행하지만 결과적으로는 진척이 되지는 않기 때문에 무한 반복이라고 불린다. 무한 반복 상황을 해결하기 위한 해법으로 락 획득을 위한 코드를 반복하기 전에 임의의 시간 동안 지원하는 것이다. 그러면 경쟁하는 쓰레드 간의 반복 간섭 확률을 줄일 수 있다.

상호 배제

• 락이 없는(lock-free) 자료 구조 접근법의 아이디어는 간단하다. 강력한 하드웨어 명령어를 사용하면 명시적인 락킹 없이도 접근할 수 있는 자료구조를 만들 수 있다는 것이다.

스케줄링으로 교착 상태 회피하기

• 회피하기 위해서는 실행중인 여러 쓰레드가 어떤 락을 획득하게 될 것인지에 대해 전반적으로 파악하고 있어야 하며 그것을 바탕으로 쓰레드들을 스케줄링하여 교착상태가 발생하지 않도록 그때 그때 보관한다.

발견 및 복구

• 교츅 상태 발생을 허용하고, 교착 상태를 발견하면 복구토록 하는 방법이다. 예를 들어 운영체제가 일년에 한 번 멈춘다고 했을 때 재부팅을 하고 기분좋게 다시 작업을 처리하는 식이다. 교착 상태가 아주 가끔 발생한다면 이 방법도 꽤 유용하다.