[OSTEP 병행성(concurrency)]병행성 관련 오류

📝서론 

우리는 그동안 교착 상태에 초점을 맞춰서 오류를 해결했다.

핵심 질문 : 일반적인 병행성 관련 오류들은 어떻게 처리하는가?

 

📝비 교착 상태 오류 

원자성 위반 오류 
"다수의 메모리 참조 연산들 간에 있어 예상했던 직렬성이 보장되지 않았다."

 

즉 코드의 일부에 원자성이 요구되었으나, 실행 시에 그 원자성이 위반되었다는 오류이다. 

해결방법은 간단하게도, 락을 추가하여 원자성이 보장되어야 하는 부분에 락 변수를 획득하도록 하면 된다.

 

순서 위반 오류 
"두 개의(그룹의) 메모리 참조 간의 순서가 바뀌었다."

즉, A가 항상 B보다 먼저 실행되어야 하지만 실행 중에 그 순서가 지켜지지 않았다.

해결방법은 또한 간단하다. 순서를 강제하면 된다. 컨디션 변수를 사용하면 된다. 

 

 

📝교착 상태 오류 

앞서 다룬 병행성 관련 오류 외에 복잡한 락 프로토콜을 사용하는 다수의 병행 시스템은 교착 상태 문제가 발생한다.

작업 그래프를 그려보자 그래프에서 사이클(cycle)의 존재는 교착 상태 발생 가능성을 의미한다.

📌 교착 상태는 왜 발생하는가?

 

앞서 본 간단한 예제에서는 스레드 1과 2가 락을 같은 순서로 획득한다면 교착 상태는 절대 발생하지 않는다.

교착 상태는 왜 발생할까?

한 가지 이유는 코드가 많아지면서 구성 요소 간에 복잡한 의존성이 발생하기 때문이다. 

또 다른 이유는 캡슐화의 성질 때문이다.  소프트웨어 모듈화가 개발을 쉽게 하기에 상세한 내용을 감춘다.

하지만 모듈화와 락은 잘 조회되지 않는다. 전에 했던 포스팅처럼 편리하게 사용하는 인터페이스는 내부 작동과 최적화 방법을 모르기에 교착 상태의 위험이 있다. 

 

교착 상태 발생 조건

• 상호 배제(Mutual Exclusion): 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권을 주장한다(예, 쓰레드가 락을 획득함). 
• 점유 및 대기(Hold-and-wait): 쓰레드가 자신에게 할당된 자원(예: 이미 획득한 락)을 점유한 채로 다른 자원(예: 획득하고자 하는 락)을 대기한다.
• 비 선점(No preemption): 자원(락)을 점유하고 있는 쓰레드로부터 자원을 강제적 으로 빼앗을 수 다. 
• 환형 대기(Circular wait): 각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 자원(락)을 갖고 있는 쓰레드들의 순환 고리가 있다.

이 네 조건 중에 하나라도 만족하지 않는다면 교착 상태는 발생하지 않는다.

 

📌 교착 상태의 예방

 

순환 대기 

아마도 가장 실용적인 예방 방법은 순환 대기가 절대 발생하지 않도록 락 코드를 작성하는 것이다.

간단한 방법은 락 획득을 하는 전체 순서를 정하는 것이다. 물론 좀 더 복잡한 시스템의 경우 전체 순서를 정하는 것은 어려울 수 있다. 그렇기에 부분 순서를 제공한다.

 

점유 및 대기

교착 상태가 발생하는 조건인 점유와 대기는 원자적으로 모든 락을 단번에 획득하도록하면 예방할 수 있다.

그러나 이 방식은 문제점이 있다.

• 필요한 락들을 정확히 파악하고, 그 락을 미리 획득해야 한다.
• 미리 모든 락을 획득해 놓기 때문에 병행성이 저하한다.

그렇기에 기본적으로 점유와 대기 예방을 위해 다음과 같이 한다.

• 락 범위를 줄이고
• 락 순서를 정형화하거나
• 타임아웃 락이나 트라이 락(tryLock) 사용 등을 통해 문제 발생 확률을 줄이는 방향으로 설계합니다.

비선점

일반적으로 락을 해제하기 전까지는 락을 보유하고 있는 것으로 보기 대문에 여러 락을 획득하는 것은 문제의 소지가 있다.

그렇기에 많은 쓰레드 라이브러리들이 이 문제를 해결하기 위해 유연한 인터페이스 집합을 제공한다.

• trylock() 루틴
  • 락을 획득하거나 현재 락이 점유된 상태이니 락을 획득하기 원한다면 나중에 다시 시도하라는 것을 알리는 -1 값을 리턴한다.
  • 이 인터페이스를 사용하면 교착 상태 가능성이 없고, 획득 순서에 영향을 받지않는 락 획득 방법을 만들 수 있다.

그렇지만 무한 반복이라는 새로운 문제가 생긴다. 두 스레드가 이 순서대로 시도하기를 반복하면서 락 획득을 실패하는 것이다.

상호 배제

마지막 예방 기법은 상호 배제를 없애는 것이다. 

일반적 코드는 모두 임계 영역을 포함하기에 어려운 일이다. 

그러나 Herlihy는 대기 없는 자료 구조를 구현하여 해결하였다.

과정

1. 각 스레드는 작업을 수행하기 위해 자신만의 지역 복사본을 만듭니다.
2. 작업을 로컬에서 수행한 뒤,
3. CAS 을 사용하여 원자적으로 결과를 적용하려고 시도합니다.
4. 실패하면 다시 로컬 복사본을 만들어서 반복합니다. 

💡 CAS (Compare-And-Swap)란?

"메모리의 어떤 값이 내가 기대한 값과 같으면, 그 값을 내가 지정한 새 값으로 한 번에 바꿔줘."

즉, 현재 값이 예상한 값일 때만 바꾼다.
다른 스레드가 그 사이에 건드렸다면, 실패하고 다시 시도하게 된다.

 

Herlihy의 자료구조는 자신만의 지역 복사본을 이용하여 결과 적용을 시도합니다. 

정리

• 해당 자료구조는 모든 스레드가 무조건 유한 시간 내에 작업을 완료할 수 있는, 가장 강력한 비차단 동기화 기법이다.
• 그러나 알고리즘이 매우 복잡하고 오버헤드가 크기에 대부분 다른 방식을 사용합니다.  

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

어떤 시나리오에서는 교착 상태를 예방하는 대신 회피하는 것이 유용할 때가 있습니다.

회피하기 위해서는 실행 중인 여러 스레드가 어떤 락을 획득할 것인지 전반적으로 파악하고 그것을 바탕으로 스케줄링하여 교착 상태 발생을 회피합니다. 

 

예제를 봅시다. 

 

위 그림은 쓰레드 T1, T2, T3, T4의 락과의 연관관계를 표시합니다.

이 상태에서 똑똑한 스케줄러라면 T1과 T2를 동시 실행하지 않는다면 교착 상태가 발생하지 않는다는 것을 알 수 있다.

 

 

여기서 더 경쟁이 심각해져 T3도 락의 연관성이 많아진다면 한번 봅시다.

위와 같이 된다면 정적 스케줄링은 T1,T2,T3 모두 한 프로세서에서 실행하도록 해야하기 때문에 오버헤드가 매우 커진다.

유명한 예로 다익스트라의 은행원 알고리즘이 있으며 상당히 제한적인 환경에서만 유용한 방법이다. 

 

 

📝요약

📌 병행성 관련 일반 오류

1. 원자성 위반

• 문제: 여러 연산이 원자적으로 수행돼야 하지만 중간에 다른 스레드가 끼어들어 순서가 꼬임.
• 해결: 락(lock) 을 통해 원자성 보장.

2. 순서 위반

• 문제: 특정 연산 A가 항상 B보다 먼저 실행돼야 하지만 순서가 뒤바뀜.
• 해결: 컨디션 변수(Condition Variable) 등으로 순서 강제.

📌 교착 상태 (Deadlock)

📍발생 조건 (4가지 모두 만족 시 발생)

1. 상호 배제: 자원은 한 번에 하나의 스레드만 사용 가능
2. 점유 및 대기: 자원을 점유한 상태에서 다른 자원을 기다림
3. 비선점: 자원을 강제로 회수할 수 없음
4. 환형 대기: 스레드들이 자원을 서로 기다리며 고리를 형성

📌 교착 상태 예방 방법

1. 순환 대기 차단

• 모든 락 획득 순서 고정
  → 전체 또는 부분 순서 정하기

2. 점유 및 대기 방지

• 모든 락을 한 번에 획득 → 하지만 병행성 저하 우려
• 대안:
  • 락 범위 축소
  • tryLock, timeout 락 등 사용

3. 비선점 차단

• tryLock() 등을 통해 락 획득 실패 시 회피 가능
  → 하지만 무한 루프의 위험

4. 상호 배제 제거 (비차단 동기화)

• 대표적 방법: Herlihy의 대기 없는(wait-free) 자료구조
  • 각 스레드가 자신만의 복사본으로 작업
  • 결과를 CAS(Compare-And-Swap) 로 커밋
  • 실패하면 다시 반복

---

📌 스케줄링 기반 교착 상태 회피

• 전체 락 상태와 요청 정보를 바탕으로 스케줄러가 충돌 회피
• 예: T1과 T2가 동시에 실행되지 않도록 함
• 하지만 락이 많아질수록 스케줄링 부담 증가
• 대표 알고리즘: 다익스트라의 은행원 알고리즘
  • 제한적인 환경에서만 실용적

•