🥑 배경

• 공유 자료를 병행 접근하면 인터럽트 시점 문제로 자료의 불일치 초래
• 자료의 일관성을 유지하기 위해 병행 실행 중인 프로세스들의 바른 순서 수행을 보장하는 메커니즘 필요

경쟁 상황 (race condition)

• 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황
• 경쟁 상황으로부터 보호하기 위해 한 순간에 하나의 프로세스만이 공유 자료를 조작하도록 보장하는 프로세스들을 동기화

임계구역 문제 (Critical-Section Problem)

• n개의 프로세스는 임계구역(Critical-Section)이라고 부르는 코드 부분 포함
  • 다른 프로세스와 공유하는 변수의 변경, 테이블의 갱신, 파일 쓰기 등의 작업 코드
  • 한 프로세스가 자신의 임계 구역에서 수행하는 동안에는 다른 프로세스들이 그들의 임계구역에 들어 갈 수 없음
• 임계구역 문제는 이 문제를 해결하는 프로토콜을 설계하는 것
• 각 프로세스는 자신의 임계 구역으로 진입하려면 집입 허가 요청을 해야 함
  • 요청 구현 코드 : 진입 구역(entry section), 퇴출 구역(exit section), 나머지 구역(remainder section)

🧏 해결안

임계 구역 문제에 대한 해결안

• 해결안은 세 가지 요구 조건을 충족
  • 상호 배제 (mutual exclusion) : 프로세스 P가 자기의 임계 구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계 구역에서 실행될 수 없음
  • 진행 (progress) : 자기의 임계 구역에서 실행되는 프로세스가 없고, 자신의 임계 구역으로 진입하려고 하는 프로세스들이 있다면 이들 프로세스들 중 임계 구역으로 진입을 선택하고, 이 선택은 무한정 연기될 수 없음
  • 한정된 대기 (bounded waiting) : 프로세스가 자기의 임계 구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계 구역에 진입이 허용되는 횟수에 제한이 있어야 함
• 임계구역을 다루는 두 가지 일반적인 접근법 사용
  • 선점형(preemptive) 커널 : 커널 모드에서 실행되고 있는 프로세스가 선점되는 것을 허용
    • 선점형 커널은 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있기 때문에 더 적합
    • SMP에서는 서로 다른 CPU에 두 프로세삭 동시에 커널 모드일 수도 있어서 선점형 커널 설계가 어려움
  • 비선점형(non-preemptive) 커널 : 커널 모드를 종료 및 봉쇄하여 선점 제한. 경쟁 상황x

피터슨의 해결안(Peterson’s Solution)

고전적인 소프트웨어 기반 해결책 : 두 개의 프로세스로 한정

• load와 store 명령이 원자적(atomic)이라고 가정, 즉 인터럽트가 될 수 없음 : 현재에선 보장x
• 두 프로세스가 공유하는 자료 항목 : int turn, bollean flag[2]
  • 변수 turn : 임계 구역으로 진입할 순번을 나타냄
  • flag배열 : 프로세스가 임계 구역으로 진입할 준비가 되었다는 것을 나타냄

동기화 하드웨어

많은 시스템에서 임계 구역 코드를 지원하는 하드웨어를 제공 : 대부분 락킹 기반

• 단일 처리기 환경에서는 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않음 : 간단!
  • 선점 없이 순서적으로 실행
  • 다중 처리기 환경에서는 비효율 : 인터럽트 불가 메시지를 여러 번 전달은 시간 부담
• 많은 현대 기계들은 특별한 원자적(atomic) 하드웨어 명령어들을 제공
  • 원자적(atomic) = 인터럽트 되지 않음 (non-interruptable)
  • 한 워드(word)의 내용을 검사하고 변경 명령어 (test and set instruction)
  • 두 워드의 내용을 원자적으로 교환 (swap instruction)

락(Lock)을 사용한 임계 영역 문제 해결

• 프로세스는 임계 영역 진입 전에 반드시 락(lock)을 획득
• 임계 영역 나올 때는 락을 방출

🐣 동기화 툴

뮤텍스 락 (Mutex Lock)

• 하드웨어를 기반 해결안들은 응용 프로그래머가 사용하기에는 복잡
• OS 설계자들은 임계 구역 문제를 해결하는 소프트웨어 툴을 구축
• 가장 간단한 방식이 상호 배제(mutual exclusion)를 제공하는 mutex 락
  • 먼저 락을 획득(acquire()) 한 후에 락을 해제(release())하여 임계 영역을 보호
  • 락의 가용 여부를 나타내는 Boolean 변수 사용
  • acquire(), release()의 호출은 원자적이어야 함
  • 임계구역 진입 전 바쁜 대기(busy waiting) 사용 : 스핀락(spinlock) 이라고도 함

세마포 (Semaphore)

• 프로세스들을 동기화 시키는 (multex 락 보다) 좀 더 복잡하 동기화 툴
• 세마포 S는 정수 변수
• 두 개의 표준 원자적 연산 wait()와 signal()로만 세마포 접근
• wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 원자적으로(분리되지 않고) 수행

wait()와 signal()의 정의

세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타내고 이후 자원을 사용하려는 프로세스를 세마포 값이 0보다 커질 때까지 기다림

세마포 사용

• 카운팅 세마포 (counting semaphore) : 제한 없는 영역(domain)을 정수값
• 이진 세마포 (binary semaphore) : 이진 세마포의 값은 0과 1 사이의 값만 가짐, mutex 락과 동일
• 다양한 동기화 문제들을 해결 가능
• S1이 S2 이전에 수행되어야 하는 프로세스 P1과 P2 예

세마포 구현

• 어떤 두 프로세스들도 동시에 같은 세마포를 가지고 wait()와 signal()을 수행하지 않음 보장해야 함 → 구현은 wait, signal 코드가 임계영역에 놓여야 하는 임계 영역 문제 발생
• 바쁜 대기(busy waiting) : 어떠한 특정 공유자원에 대하여 두 개 이상의 프로세스나 스레드가 그 이용 권한을 획득하고자 하는 동기화 상황에서 그 권한 획득을 위한 과정에서 일어나는 현상
• 임계영역 구현 시 바쁜 대기(busy waiting)를 사용하는 경우
  • 구현 코드가 짧음
  • 임계영역의 점유가 드물면 바쁜 대기는 거의 없게 됨
  • 많은 시간을 임계영역에 머물어 있는 응용들에는 적합x
    • 다른 프로세스들이 생산적으로 사용할 수 있는 CPU 시간 낭비
    • 프로세스가 락을 기다리는 동안 루프를 돌기 때문에 이런 유형의 세마포를 스핀락(spinlock)이라고 함
    • 짧은 시간 락을 기다리는 경우 문맥 교환이 필요하지 않아 스핀락 유용
• 바쁜 대기가 없는 세마포 구현
  • 바쁜 대기 대신에 프로세스는 자신을 봉쇄하고(block) 프로세스를 세마포에 연관된 대기 큐(waiting queue)에 삽입
  • 대기 큐와 연관된 세마포의 자료
    • 세마포 값을 나타내는 정수 value
    • 대기 큐를 가리키는 포인터 리스트 list
  • 세마포 관련 연산
    • block() 연산 : 자기를 호출한 프로세스를 중지하고 대기 큐에 삽입
    • wakeup(P) 연산 : 봉쇄된 프로세스 P의 실행 재개, 대기 큐에서 프로세스를 제거하고 준비 완료 큐에 삽입

🦴참고

Operating System Concepts, 10th Ed.