병행성(Concurrency) : 상호배제(Mutual Exclusion)와 동기화(Synchronization)

Goal

• 병행성(Concurrency)의 원리와 주요 용어를 이해할 수 있음
• 경쟁상태(Race Condition)의 문제점에 대해 이해할 수 있음
• 상호배제(Mutual Exclusion)의 필요성을 이해할 수 있음
• 세마포어를 정의하고 동작 방식을 이해할 수 있음
• 모니터를 정의하고 동작 방식을 이해할 수 있음
• 메시지 전달을 이용한 상호배제 기법을 이해할 수 있음

 

병행성 원리

• 병행 처리의 문제점

  • 전역 자원의 공유가 어려움
  • 운영체제가 자원을 최적으로 할당하기 어려움
  • 프로그래밍 오류를 찾아내는 것이 어려움

• 병행성과 관련 있는 주요 용어

  

• 운영체제 고려 사항

  • 다양한 프로세스의 행위를 추적할 수 있어야함
  • 각 프로세스에게 자원을 할당하거나 반납 받을 수 있어야함
  • 한 프로세스가 소유한 자원이나 데이터를 다른 프로세스의 간섭으로부터 보호할 수 있어야함
  • 수행 결과가 프로세스들의 수행 순서와 독립적일 수 있도록 보장해야함

• 자원 경쟁

  • 병렬 프로세스들이 같은 자원을 사용하려고 경쟁하면 충돌이 발생함(I/O 장치, 메모리, 처리기 시간, 클락 등)
  • 프로세스들이 경쟁하면 3가지 제어 문제가 발생함
    1. 상호배제
    2. 교착상태
    3. 기아

 

상호배제

• 요구조건

  • 어느 한 순간에는 오직 하나의 프로세스만이 임계역역에 진입할 수 있음
  • 임계영역이 아닌 곳에서 수행이 멈춘 프로세스는 다른 프로세스의 수행을 간섭해서는 안됨
  • 임계영역에 접근하고자 하는 프로세스의 수행이 무한히 미뤄져서는 안됨. 즉 교착상태 및 기아가 일어나지 않아야함
  • 임계영역이 비어 있을때, 임계영역에 진입하려고 하는 프로세스가 지연되어서는 안됨
  • 프로세서의 개수나 상대적인 프로세스 수행 속도에 대한 가정은 없어야함
  • 프로세스는 유한 시간 동안만 임계영역에 존재할 수 있음

• 해결방법

  • 어느 한 순간에는 오직 하나의 프로세스만이 임계영역에 진입

  

  • 소프트웨어적 접근방법
    • 수행 부하가 높고, 논리적 오류의 위험성이 큼
  • 하드웨어 지원
    • 인터럽트 금지(오버헤드가 큼)
    • 특별한 기계 명령어: Test and Set, Compare and Swap, Exchange
      • 단점 : 바쁜 대기, 기아상태 및 교착상태 발생 가능
  • 세마포어
  • 모니터
  • 메시지 전달

 

대표적인 병행성 기법

 

병행성 기법 - 세마포어

• 정의 : 상호 배제를 운영체제와 프로그래밍 언어 수준에서 지원하는 메커니즘

• 3가지 인터페이스

  1. 초기화 연산(Initialize Operation) : 세마포어 값을 음이 아닌 값으로 초기화
  2. 대기 연산(Wait Operation) : 세마포어 값을 감소시키며, 값이 음수이면 호출한 프로세스는 블록됨 -> 음수가 아니면 프로세스는 계속 수행될 수 있음
  3. 시그널 연산(Signal Operation) : 세마포어 값을 증가시킴. 값이 양수가 아니면 블록된 프로세스를 깨움

• 세마포어 구현

  

  • 임계영역이 아닌 정상적인 실행에서는 프로세스들이 병렬 처리되지만, 임계영역에서는 직렬화됨

• 결론

  • semWait와 semSignal은 원자적으로 구현되어야 함
  • 하드웨어 또는 펌웨어로 구현 가능하며, Dekker’s 또는 Peterson’s 알고리즘 같은 소프트웨어적인 기법으로도 구현 가능

 

생산자/소비자 문제

• 병행 수행되는 생산자와 소비자
• 생산된 item을 버퍼에 저장
• 한 순간에 하나의 생산자 또는 소비자만 버퍼에 접근 가능
• 생산자는 가득 찬 버퍼에 item을 저장하면 안됨. 또한 소비자는 빈 버퍼에서 item을 꺼내면 안됨

 

모니터(Monitor)

• 정의
  • 상호배제를 위한 소프트웨어 모듈(프로그래밍 언어 수준에서 제공)
  • 세마포어처럼 상호 배제 기능 제공하며 사용이 훨씬 쉬움
• 특징
  • 지역 변수는 모니터 내부에서만 접근 가능
  • 프로세스는 모니터 프로시저 중 하나를 호출함으로써 모니터 내부로 진입
  • 한 시점에 단 하나의 프로세스만 모니터 내부에서 수행 가능

 

판독자/기록자 문제

• 정의
  • 병행 수행되는 판독자와 기록자
  • 공유 자원(파일, 데이터베이스)
• 요구조건
  • 여러 판독자들이 공유 데이터를 동시에 읽을 수 있음
  • 한 시점에 오직 하나의 기록자만 공유 데이터를 변경할 수 있음
  • 기록자가 데이터를 변경하고 있는 동안 판독자가 그 데이터를 읽을 수 없음
• 해결방법
  • 세마포어를 이용한 기록자 우선 방법과 판독자 우선 방법
  • 메시지 전달을 이용한 해결 방법