스레드 동기화

4th

📌 4주차 : 프로세스 동기화

• 데드락
• 병행성과 병렬성
• RaceCondition
• 세마포어
• 뮤텍스
• 모니터

스레드 동기화

스레드 동기화의 필요성

• 스레드 동기화: 공유 데이터에 대한 다수 스레드의 동시 접근을 해결하는 방법
• 다수의 스레드가 공유 데이터를 동시에 쓰는 충돌 상황에서 공유 데이터가 훼손되지 않도록 스레드의 실행을 제어하는 기법
• 동기화를 통해 스레드가 공유 데이터에 대해 배타적이고 독점적으로 접근하도록 허용해야한다.

공유 데이터 액세스 문제와 해결방법

• 문제점: 여러 스레드가 공유 데이터에 동시에 쓰기를 수행하면 공유 데이터가 훼손된다.
• 해결책: 스레드 동기화 → 한 스레드가 공유 데이터에 대한 사용을 마칠 때까지 다른 스레드가 접근하지 못하도록 제어

임계구역과 상호배제

• 임계구역: 사용자가 작성한 프로그램 중 공유 데이터에 접근하는 코드 블록
• 상호배제: 임계구역은 반드시 한 스레드만 배타적 독점적으로 실행하도록 관리하는 것을 의미
  • 핵심: 임계구역에 먼저 진입한 스레드가 임계구역의 실행을 끝날 때까지 다른 스레드가 집입하지 못하도록 보장하는 것
• 임계구역 설정은 멀티스레드 응용 프로그램의 개발자의 판단에 따라 이루어짐

상호배제

• 임계구역 전후에 진입코드, 진출코드 있음
• 진입코드: 임계구역에 진입하기 전 필요한 코드 블록, 현재 임계구역을 이미 실행중인 스레드가 있는지 검사하고, 없는 경우 다른 스레드 들어오지 못하도록 조치한다. 들어오려면 들어오려는 스레드 대기시키고, 진입한 스레드 끝날때까지 대기한다.
• 진출코드: 스레드가 임계구역 실행을 마칠 때 실행되어야 하는 코드 블록, 대기중인 스레드 임계구역 진입할 수 있도로 entry 코드에서 취한 조치 해제
• 임계구역 코드: 한번에 한 스레드만 실행하도록 보장, 임계구역은 짧을 수록 좋음

상호배제 구현

• 방법
  • 소프트웨어적: Peterson’s 알고리즘
    • 실제 구현에 잇어 여러 문제를 노출하기 때문에 사용 ㄴ
  • 하드웨어적: 인터럽트 서비스 금지, 원자명령 활용
    • 현재는 원자명령을 활용
• 관건: 임계구역의 entry 코드와 exit 코드를 어떻게 구현하는가

방법1 - 인터럽트 서비스 금지

• 임계구역으로 진입할 때 entry 코드에서 인터럽트 서비스를 금지하고 exit 코드에서 인터럽트 서비스를 허용하는 CPU 명령들을 실행하는 방법 → 스레드 선점되지 않는다.
• cli와 sti
  • cli 명령: CPU 내부의 인터럽트 플래그를 0으로 리셋 → 인터럽트 무시
  • sti 명령: CPU의 인터럽트 플래그를 1로 설정 → 인터럽트 발생시 인터럽트 서비스 루틴 실행
  • 두 가지 문제점
    • 임계구역 실행하는 동안 모든 인터럽트 무시된다
    • 인터럽트 서비스 금지 방법은 단일 CPU 시스템에서는 활용가능, 다중 CPU를 가진 시스템에서는 활용하지 못한다.

방법2 - 원자명령 사용

• 상호배제를 위해 만들어진 CPU 명령
• 원자명령없이 lock 변수를 이용한 상호배제 시도
  • 임계구역들어갈때 lock 변수 1, 나올때 0으로 변경
  • 문제점: entry 코드
    • lock 변수 값을 읽어 들이는 명령과 lock 변수를 1로 바꾸는 명령 사이에 컨택스트 스위치이 발생할때 문제 발생
  • 해결 방법 - 원자 명령 도입
• 위 두 명령어를 하나의 명령으로 만드는 것 → 원자명령, TSL
• TSL ax, lock

멀티스레드 동기화 기법

• 동기화 프리미티브
• 멀티스레드 동기화 방법중 3가지 방법
  • 락 방식 - 뮤텍스, 스핀락
  • wait-signal 방식 - 세마포

뮤텍스

• 잠금/열림중 한 상태를 가지는 락 변수를 이용하여, 한 스레드만 임계구역에 진입시키고 다른 스레드들을 큐에 대기 시키는 방법
• 락 변수: 락을 잠근다, 락을 여다
• lock/unlock 연산
  • lock 연산: 스레드가 임계구역에 들어가기 전 실행하는 entry 코드, 잠겨 있을 경우 현재 스레드를 블록 상태로 만들어 대기 큐에 삽입, 열린 상태라면 락을 잠그고 임계구역 진입
  • unlock 연산: 임계구역 나올때 실행하는 exit 코드, 락을 열림 상태로 바꾸고 대기 큐에 있는 스레드 하나 깨워 준비 상태로 만들기
  • 원자 명령 사용됨
• 뮤텍스: 블록킹 락, 수면 대기 락
• 특징
  • 임계구역의 실행 시간이 짧은 경우에는 비효율적
    • 락이 잠겨있는 경우, 스레드는 대기 큐에 들어가고 락이 풀리면 cpu 얻어서 실행되는데 임계 구역 실행시간이 짧을 경우 락이 잠겨 있는 시간보다 컨텍스트 스위치하는 시간이 더 크기때문에 비효율적

스핀락

• 락 기반이지만 뮤텍스와 다르게 대기 큐가 없다
• 락 변수
• lock/unlock 연산
  • lock 연산: 락이 열려있으면 임계구역 들어가고, 잠겨 있으면 열릴 때까지 락 검사를 무한 반복하고, 락 열리면 즉각 락을 잠그고 임계 구역 들어간다.
  • unlock 연산: 락을 열림으로 변경
  • 원자명령 사용
• 타임 슬라이스가 소진될때 스레드는 컨텍스트 스위치되고, 다시 스케줄되면 다시 락이 풀릴 때까지 검사를 반복
• = 공격적인 뮤텍스, 바쁜 대기 락
• 특징
  • 뮤텍스 기법의 바쁜 대기 모형
  • 단일 CPU를 가진 운영체제에서 스핀락은 비효율적
    • lock이 잠겨있을때 현재 스레드가 계속 락을 검사하는 코드는 의미 없는 검사를 계속 하는 거여서 CPU 낭비가 심하고, 다른 스레드의 실행 기회마저 뺏는 것이다.
    • 반대로 멀티 CPU인 경우, 락을 경쟁하는 스레드들을 서로 다른 코어에서 실행시키면 상당히 효과적
  • 스핀락은 임계구역 코드가 짧아서 락이 빨리 열리는 응용에 매우 효과적
  • 스핀락은 락을 얻기 위해 무한 경쟁하기 때문에 기아 발생할 수 있다.
• 리눅스는 동기화 기법으로 스핀락 사용한다.

뮤텍스와 스핀락은 어떤 경우에 적합할까?

• 락이 잠기는 시간이 긴 응용의 경우 뮤텍스가 효과적, 짧은 경우 스핀락이 효율적
• 단일 CPU일 경우 뮤텍스가 적합, 멀티코어인 경우 스핀락이 효율적
• 뮤텍스는 사용자 응용프로그램에서 주로 이용, 스핀락은 커널 코드나 인터럽트 서비스 루틴에서 주로 사용

세마포

• n개의 자원을 다수의 스레드가 공유하여 사용하도록 돕는 자원 관리 기법
• 자원의 개수 n을 알고, 스레드의 요청을 받아 사용을 허락하고, 자원이 모자랄 때 요청한 스레드는 대기큐에서 잠을 재우며, 자원 사용을 끝낸 스레드가 세마포에게 알리면 세마포가 대기큐에서 잠을 자는 스레드를 깨워 자원을 사용하도록 허락하는 방식
• 구성 요소: 자원, 대기큐, counter 변수, P/V 연산
• counter 변수: 사용가능한 자원의 개수를 나타내는 정수형 변수
  • 변수가 음수이면 자원을 기다리는 스레드의 개수
• P/V 연산
  • P 연산: 스레드에게 자원 사용을 허가하는 과정
    • counter변수 1 감소
  • V 연산: 스레드가 자원 사용이 끝났음을 세마포에게 알리는 과정
    • counter 변수 1 증가
  • 종류
    • 수면 대기 세마포
      • P 연산 중 자원 사용을 허가받지 못한 스레드를 대기큐에서 잠을 재우고, V 연산에서 사용 가능한 자원이 생기게 되면 스레드를 깨워 자원 사용을 허락
    • 바쁜 대기 세마포
      • P 연산에서 가용 자원이 생길 때까지 무한 루프를 돌아 검사하는 방식
      • 대기 큐가 없다
  • = wait/signal 연산: 자원을 사용하려는 스레드 대기하고, 자원 사용끝난 스레드는 대기 스레드에게 알려주기 때문에

이진 세마포

• 카운터 세마포: 자원이 여러 개인 경우
• 이진 세마포: 자원이 1개인 경우
  • 세마포 변수 S: 0 또는 1
  • 대기 큐
  • P 연산: S를 1 → 0 으로 감소, 0보다 작으면 대기큐 잠들게 하기
  • V 연산: S를 1 증가시키고 0보다 크면 그냥 리턴, 0보다 작거나 같으면 대기큐에 있는 스레드 깨우기

동기화 이슈: 우선순위 역전

• 스레드 동기화로 인해 우선순위가 높은 스레드가 순위가 낮은 스레드보다 늦게 실행되는 우선순위 역전이 발생할 수 있다.
• 실시간 시스테에서 높은 순위의 스레드가 오래 대기하는 것은 심각한 문제
• 해결책
  • 우선순위 올림: 스레드가 공유 자원을 소유하게 될 때 우선순위를 일시적으로 미리 정해진 우선순위로 높이는 방법
    • 공유 자원을 소유한 스레드가 다른 스레드에 의해 선점되지 않고 빨리 실행
  • 우선순위 상속: 낮은 순위의 스레드가 공유 자원을 획득하고 실행하는 동안 높은 순위의 스레드가 공유 자원을 요청하면 낮은 순위의 스레드를 우선순위를 요청한 스레드보다 높게 변경하여 실행
  • 두 방법은 모두 구현이 쉽지 않고 오버헤드 존재함

생산자-소비자 문제

• 전형적인 동기화 문제
• 문제점
  1. 입력스레드와 재생 스레드가 버퍼에 동시에 접근하는 경우의 상호배제
  2. 재생스레드가 읽으려고 하는데 버퍼가 비어있는 경우
  3. 입력스레드가 쓰려고하는데 버퍼가 꽉 찬 문제
• 유한한 크기의 공유버퍼에 데이터를 공급하는 생산자와 공유버퍼에서 데이터 읽고 소비하는 소비자가 공유버퍼를 문제없이 사용하도록 생산자와 소비자를 동기화시키는 문제(실행 순서 제어)
• = 유한 버퍼 문제
• 해결책
  • 상호배제 해결: 뮤텍스나 세마포를 이용
  • 비어있는 공유버퍼 문제 해결: 세마포
  • 꽉 찬 공유버퍼 문제 해결: 세마포, 소비자 스레드가 데이터를 읽은 후 생산자 스레드 깨우기

---

교착상태

교착상태 문제 제기

무한 대기와 교착 상태

• 무한적 대기하는 상태

식사하는 철학자 문제

• 5명의 철학자 5개의 포크, 스파게티를 먹기위해서는 2개의 포크가 필요함
• 모든 철학자가 동시에 자신의 왼쪽 포크를 들고 오른쪽 포크를 집으려고 하는 경우 모든 철학자가 자신의 오른쪽 포크를 무한정 기다리게 된다.
• 즉, 영원히 대기하는 교착 상태
• 원인: 환형 요청/대기
  • 대기의 모형이 환형 고리를 형성하고 있으며 스스로 해체할 수 없어서 교착 상태에 빠진 것
• 해결: 환경 요청/대기가 생기지 않게 규칙 변경
  • 나머지 한 철학자만 오른쪽 포크를 먼저 잡은 뒤 왼쪽 포크를 잡도록 규칙 변경

식사하는 철학자와 컴퓨터 시스템

• 철학자 - 스레드
• 포크 - 자원
• 스파게티 - 스레드가 처리할 작업

교착상태

교착상태 정의

• banker’s algorithm research
• = 풀지 못하는 포옹
• 자원을 소유한 스레드들 사이에서 각 스레드는 다른 스레드가 소유한 자원을 요청하여 모든 스레드가 무하정 대기하는 현상
• 커널 코드 내에서는 거의 발생하지 않고, 사용자 응용프로그램 내에서 주로 발생한다.
  • 커널은 교착상태를 고려하여 매우 정교하게 작성되어 있지만 사용자 응용프로그램은 아니다.
  • 그럼에도 교착상태를 막도록 운영하는 컴퓨터 시스템은 거의 없다. → 많은 시간과 비용을 치러야 하기 때문

컴퓨터 시스템에 잠재된 교착상태 유발 요인

• 자원 - 자원은 교착상태의 발생지
  • 소프트웨어/데이터 자원 - 뮤텍스, 스핀락, 세마포, 파일, 데이터베이스, 파일락 등
  • 하드웨어 자원 - 프린터, 메모리, 프로세서 등
• 자원과 스레드 - 한 스레드가 동시에 여러 개의 자원을 필요로 하는 경우
• 자원과 운영체제 - 운영체제는 한 번에 하나씩 자원을 할당
  • 만약 스레드가 운영체제로부터 필요한 자원을 한 번에 모두 할당 받는다면 교착상태 발생하지 않을 수도 있다.
• 자원 비선점 - 할당된 자원은 스레드가 자발적으로 내놓지기 전에 강제로 뺏지 못한다.

교착상태 모델링

• 자원 할당 그래프: 컴퓨터 시스템에 존재하는 자원과 스레드들의 상태를 나타내는 방향성 그래프
  • 꼭짓점: 스레드는 원으로, 자원은 사각형
  • 간선
    • 할당 간선: 자원 → 스레드, 스레드가 자원 소유
    • 요청 간선: 스레드 → 자원, 스레드가 자원 기다림
• 교착 상태가 발생한 자원 할당 그래프의 모양
  • 환형 고리가 나타난다

교착상태 해결

코프만 조건

• 교착상태를 유발할 수 있는 4가지의 필요충분조건 증명
  • 상호 배제: 자원은 한 번에 한 스레드에게만 할당
  • 소유하면서 대기; 스레드가 자원을 소유하면서 다른 자원 대기
  • 강제 자원 반환 불가: 스레드에게 할당된 자우넝르 강제로 빼앗지 못함
  • 환형 대기: 한 그룹의 스레드에게 각 스레드가 다른 스레드가 소유한 자원을 요청하는 환형 고리 형성
  • 한 가지라도 성립되지 않게 된다면 교착상태 빠지지 않게 되는 것

교착상태 해결 방법

1. 예방
   • 하나 이상의 조건이 아예 성립하지 못하도록 시스템을 설계하고 구성하여 교착상태가 발생할 여지가 없도록 예방하는 것
2. 회피
   • 운영체제가 자원을 할당할 때 교착상태에 빠지지 않을 것이라고 확신하는 경우에만 자원을 할당
   • 자원을 할당할때마다 교착상태 가능성을 검사 → 시스템 성능 많이 저하
3. 감지 및 복구
   • 교착상태 감지하는 프로그램 백그라운드 구동시켜 발견하면 교착상태 해체
   • 교착상태 감지 작업 주기로 실행해야해서 부담 크다.
4. 무시
   • 아무런 대비책 없이 교착상태 발생하도록 내버려 두는 방법
   • 기본 철학은 웬만해서 교착상태 발생하지 않으며, 발생할 경우 스레드 종류, 부팅시키기
   • 대부분의 범용 운영체제에서 사용중이다.
   • 타조 알고리즘이라 불림

교착상태 예방

• 교착상태 처음부터 발생하지 않는 시스템 환경으로 만드는 것
• 코프만 4가지 조건중 최소 한 가지 이상 성립못하도록 만들기

1. 상호배제 → 상호배제 없애기
   • 자원이 한 스레드에 의해 독점되지 않게 막기 → 2개 이상의 스레드가 동시에 자원을 사용할 수 있도록 허용 ⇒ 불가능
   • 출력물 엉망, 하나의 락을 동시에 2개 스레드가 점유? 말이 안돼
2. 소유하면서 대기 → 기다리지 않게
   • 스레드가 필요한 자원을 처음부터 모두 가지게하면 된다.
   • 운영체제는 스레드 실행 전에 스레드가 필요한 자원을 모두 알고, 스레드 실행시작과 함께 모든 자원을 할당 → 실행 중에 자원을 요청하여 대기하는 일이 없도록 하는 것
   • 스레드가 자원을 소유한 상태로 새로운 자원을 필요로 하면, 현재 할당한 모든 자원을 반환하고 필요한 모든 자원을 한꺼번에 모두 요청하는 방법
3. 자원 강제 반환 불가 → 자원의 선점 허용
   • 더 높은 순위의 스레드가 자원 요청하면 강제로 자원 뺏기
   • 자원 강제 반환된 스레드가 자원을 다시 사용하게 될때 이전 상태로 되돌아갈 수 있도록 상태를 관리
   • 어려운 방법
4. 환형 대기 → 환형 대기 제거
   • 모든 자원에 번호를 매기고, 스레드에게 반드시 번호 순으로 자원을 할당받게 하는 방법

교착상태 회피

• 자원할당 알고리즘을 이용하여 교착상태를 방지하는 방법
• 자원을 할당할때마다 환형 대기가 발생할 것인지 판단하는 작업이 실행되는 큰 단점
• banker’s 알고리즘
  • 시스템을 안전한 상태와 불안전한 상태로 나누고, 자원을 할당하였을 때 안전한 상태로 갈때만 자원을 할당
  • 각 스레드는 실행 전에 필요한 전체 자원의 수를 운영체제에 알려줘야하는데 아는게 불가능함
  • 실행중인 스레드 개수도 동적으로 변함

교착상태 감지 및 복구

• 교착상태를 감지하는 백그라운드 프로그램을 상시적으로 실행시켜 교착상태를 감지하고 교착상태를 해제하는 방법

1. 자원 강제 선점
   • 교착상태 빠진 스레드중 하나 선택하고 소유 자원 강제 빼앗아 이 자원을 기다리는 다른 스레드에 할당 → 환형 대기 고리 끊기
2. 롤백
   • 교착상태 발생할 것이라고 예측되는 스레드 상태 주기적으로 저장해두었다가, 교착상태 발생하면 가장 최근에 저장해둔 상태로 복구시켜 가장 최근에 실행하던 상태로 돌아가기
   • 주기적으로 스레드들의 상태가 저장되어야 하기 때문에, 스시템의 시간과 저장 공간을 소모 → 시스템 성능 저하
3. 스레드 강제 종료
   • 어떤 스레드를 희생시킬지 결정하는 문제 → 사용자나 시스템 관리자가 흔히 사용하는 방법

• 교착상태 감지 복구 방법도 백그라운드 프로그램이 실행되면서 자원 할당 그래프를 분석하여 교착상태가 있는지 판단 → 시스템 부담, 교착상태 해제방법 시스템 많이 부담

교착상태 무시: 타조 알고리즘

• 교착상태가 발생할 가능성은 극히 적다 → 교착상태를 피하기 위한 비용은 많다 → 굳이 교착상태 예방, 회피, 감지 및 복구를 할 필요가 있을까?
• 현재 대부분의 운영체제는 교착상태를 무시한다.
• 교착상태에 대한 아무런 대책 없이 컴퓨터 시스템을 가동시키고, 교착상태가 의심되면 사용자나 관리자가 시스템을 재시작하거나 의심가는 스레드를 강제종료하는 방법
• 데이터 잃어버리는 손실 발생하나 비용 면에서 더 나은 방법
• 실시간 시스템에서는 타조 알고리즘 부적절

참조

운영체제 책