프로세스 동기화 & 상호배제 (Synchronization & Mutual exclusion)

해당 블로그의 내용은 학교에서 배운 내용을 개인적으로 정리한 내용이므로, 잘못된 부분이 있을 수도 있습니다. 

 

프로세스 동기화 (Process synchronization)

• 다중 프로그래밍 시스템
  • 여러 개의 프로세스들이 존재
  • 프로세스들은 서로 독립적으로 동작
  • 공유 자원 또는 데이터가 있을 때, 문제 발생 가능
• 동기화 (Synchronization)
  • 프로세스들이 서로 동작을 맞추는 것
  • 프로세스들이 서로 정보를 공유하는 것
• 비동기적 (Asynchronous)
  • 프로세스들이 서로의 동작에 대한 정보가 없음
• 병행적 (Concurrent)
  • 여러 개의 프로세스들이 동시에 시스템에 존재
• 병행 수행적인 비동기적 프로세스들이 공유 자원에 동시 접근 시 문제 발생 가능!!

 

공유 데이터 (Shared data, or Critical data)

• 여러 프로세스들이 공유하는 데이터

임계 영역 (Critical section)

• 공유 데이터를 접근하는 코드 영역 

상호 배제 (Mutual exclusion)

• 둘 이상의 프로세스가 동시에 임계 영역에 진입하는 것을 막는 것

 

기계어 명령(machine instruction)의 특성

• 원자성(Atomicity), 분리불가능(Indivisible)
• 한 기계어 명령의 실행 도중에는 인터럽트(interrupt) 받지 않음

 

상호 배제 기법 

상호 배재의 기본 요소 (Mutual exclusion primitives)

• enterCS() 
  • 임계 영역 진입 전 검사
  • 다른 프로세스가 임계 영역 안에 있는지 검사
• exitCS()
  • 임계 영역을 벗어날 때의 후처리 과정
  • 임계 영역을 벗어났을 때 시스템이 알림

 

상호 배제의 기본 요구사항 (ME primitives)

• 상호 배제 (Mutual exclusion)
  • 임계 영역(CS)에 프로세스가 있으면 다른 프로세스의 진입을 금지
• 진행 (Progress)
  • CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해 하면 안됨
• 한정 대기 (Bounded waiting)
  • 프로세스의 CS진업은 유한시간(제한시간) 내에 허용되어야 함

두 프로세스의 상호 배제

• Progress 조건 위배
  • 한 프로세스가 어떤 공유 변수에 대해 수정 가능한 권한을 가지고 있고,
    해당 공유 변수에 따라 다른 프로세스의 진행 상태가 결정될 때, 
    해당 프로세스는 다른 프로세스가 임계 영역에 진입하는 것을 의도치 않게 막을 수도 있다. 
  • 이 경우, 위의 경우가 발생하지 않도록 개발자가 코드를 잘 작성하여야 한다. 
• Mutual exclusion 위배
  • 두 프로세스가 동시에 임계 영역으로 진입하는 것을 코드에서 따로 막아놓지 않았을 경우 
    두 프로세스가 동시에 임계 영역으로 진입하게 된다.
• bounded waiting 위배

 

Mutual exclusion solutions

• Low-level 메커니즘
  • SW solutions
    • 대커 알고리즘
    • 다익스트라 알고리즘
  • HW solutions
    • TAS 구조
  • OS supported SW solutions
    • Spinlock
    • Semaphore
    • Eventcount / sequencer
• High-level 메커니즘
  • Language-Level solutions
    • Monitor

SW solutions

 

Dekker's alogorithm

• Two process ME를 보장하는 최초의 알고리즘

 

Peterson's alogorithm

• Dekker's algorithm보다 간단하게 구현

 

N-process mutual exclusion

 

다익스트라

• 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결
• 실행 시간이 가장 짧은 프로세스에 프로세서를 할당하는 세마포 방법
  • 가장 짧은 평균 대기시간 제공

다익스트라 알고리즘의 flag[] 변수

• idle 
  • 프로세스가 임계 지역 진입을 시도하고 있지 않을 때
• wnat-in
  • 프로세스의 임계 지역 진입 시도 1단계일 때
• in-CS
  • 프로세스의 임계 지역 시도 2단계 및 임계 지역 내에 있을 때

 

SW solutions 들의 문제점

• 속도가 느림
• 구현이 복잡함
• ME 기본 요소 실행 중 선점될 수 있음
  • 공유 데이터 수정 혹은 인터럽트를 억제함으로써 해결 가능
    • overhead 발생
• Busy waiting
  • 비효율적

Busy Waiting이란?

• 임계 영역에 들어가고 싶은데, 누가 임계 영역에 존재한다면,
  해당 임계 영역에 프로세스가 있는지에 대한 판별을 무한적으로 반복하여 검사하는 것. 
• 아래의 spinLock도 busy waiting 의 한 종류

HW solutions

 

Synchronization HW

• TestAndSet (TAS) instruction
  • Test와 Set을 한번에 수행하는 기계어
    • CPU레벨에서 지원 
  • Machine instruction
    • Atomically, indivisible
    • 실행 중 인터럽트를 받지 않음 ( 선점이 되지 않음)
  • Busy  waiting
    • 비효율적
• TAS instruction

ME with TAS instruction

• 3개 이상의 프로세스의 경우, bounded waiting 조건 위배
  • TAS 명령어는 기본적으로 busy waiting이 발생하기 때문이다.
    • 반복적으로 타켓 변수를 검사하기 때문

 

N-process 상호 배재 with TAS

 

HW solutions

• 장점
  • 구현이 간단
• 단점
  • Busy waiting
    • 비효율적
• Busy waiting 문제를 해소한 상호배제 기법
  • Semaphore
    • 대부분의 OS들이 사용하는 기법

 

OS supported SW solution

Spinlock

• 정수 변수
• 초기화
  • P(), V() 연산으로만 접근 가능
    • 위 연산들은 indivisible(or atomic) 연산
      • OS support
      • 전체가 한 구조 사이클에 수행됨
• 멀티 프로세서 시스템에서만 사용 가능
  • 싱글 프로세서(CPU)인 경우는 적합하지 않음!
    • 현재 p0이 lock을 가지고 있고, 현재 실행중인 프로세스가 p1라면, p0의 lock을 p1에게 주기 위해서는
      context switching이 필연적으로 일어나게 된다.
• Busy waiting!

 

Semaphore

• 다익스트라가 제안
• Busy waiting 문제 해결
• 음의 아닌 정수형 변수 (S)
  • 초기화 연산, P(), V() 로만 접근 가능
    • P(probern): 검사
      • if S가 0보다 크다면 (S > 0)
        
        • S = S - 1;
      • else if Queue에서 대기
    • V(verhogen): 증가
      • if Queue에 대기 프로세스가 있다면,
        • 그 중에 하나를 깨움
      • else if S = S + 1;
    • 모두 indivisible 연산
      • OS support
      • 전체가 한 구조 사이클(instruction cycle)에 수행 됨
• 임의의 S 변수 하나에 ready queue 하나가 할당 됨
• Binary semaphore
  • S 가 0 또는 1 두 종류의 값만 갖는 경우
  • 상호배제나 프로세스 동기화의 목적으로 사용
• Counting semaphore
  • S가 0 이상의 정수값을 가질 수 있는 경우
  • Producer-Consumer 문제 등을 해결하기 위해 사용
    • *생산자-소비자 문제
• Semaphore in OSs
  • Windows
    • MSDN
  • Unix/Linux
    • Systen V
• Semaphore로 해결 가능한 문제들
  • 상호배제 문제
  • 프로세스 동기화 문제
  • 생산자 - 소비자 문제
  • Reader - writer 문제
  • Dining philosopher 문제
  • 기타
• Process synchronization
  • 프로세스들의 실행 순서 맞추기
    • 프로세스들은 병행적이며, 비동기적으로 수행
• 생산자 - 소비자 문제
  • 생산자 프로세스
    • 메세지를 생성하는 프로세스 그룹
  • 소비자 프로세스
    • 메세지를 전달받는 프로세스 그룹
• 생산자 - 소비자 문제 with Single buffer

• 생산자 - 소비자 문제 with N-buffers

• Reader - Writer 문제
  • Reader
    • 데이터에 대해 읽기 연산만 수행
  • Writer
    • 데이터에 대해 갱신 연산을 수행
  • 데이터 무결성 보장 필요
    • Reader들은 동시에 데이터 접근이 가능
    • Writer들은(Reader와 writer) 동시에 접근 시, 상호배제(동기화) 필요
• Reader - Writer 문제 (reader preference solution)

• No busy waiting 
  • 기다려야 하는 프로세스는 block(asleep) 상태가 됨
• Semaphore queue에 대한 wake-up 순서는 비결정적
  • 기아(Starvation) 문제

 

Eventcount / Sequencer

• 은행의 번호표와 비슷한 개념
• Sequencer
  • 정수형 변수
  • 생성 시 0으로 초기화, 감소하지 않음
  • 발생 사건들의 순서 유지
  • ticket() 연산으로만 접근 가능
  • ticket(S)
    • 현재까지 ticket()연산이 호출된 횟수를 반환
    • Indivisible operation
• Eventcount
  • 정수형 변수
  • 생성 시 0으로 초기화, 감소하지 않음
  • 특정 사건의 발생 횟수를 기록
  • read(E), advance(E), await(E, v) 연산으로만 접근 가능
  • read(E)
    • 현재 Event count 값 반환
  • advance(E)
    • E = E + 1;
    • E를 기다리고 있는 프로세스를 깨움 (wake - up)
  • await(E, v)
    • v 는 정수형 변수
    • if (E < v) 면, E에 연결된 Qe에 프로세스 전달(push) 및 CPU 스케줄러 호출
• 상호 배제

• 생산자 - 소비자 문제

• No busy waiting
• No starvation
  • FIFO(선입선출) 스케줄링 for Qe
• Semaphore 보다 더 low-level control 이 가능

High-level Mechanism

Monitor

• 공유 데이터와 ciriticl section의 집합
• Conditional variable
  • wait(), signal() operations
• Monitor - 구조
  
  • 진입 큐 (Entry queue)
    • 모니터 내의 프로시저(procedure) 수만큼 존재
  • 상호 배제 (Mutual exclusion)
    • 모니터 내에는 항상 하나의 프로세스만 진입 가능
  • 정보 은폐 (Information hidind)
    • 공유 데이터는 모니터 내의 프로세스만 접근 가능
  • 조건 큐 (Condition queue)
    • 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기
  • 신호제공자 큐 (Signaler queue)
    • 모니터에 항상 하나의 신호제공자 큐가 존재
    • signal() 명령을 실행한 프로세스가 임시 대기
  • Monitor - 자원 할당 문제
  • 자원 할당 시나리오
  • 생산자 - 소비자 문제
  • Reader - Writer 문제
    • reader / writer 프로세스들 사이의 데이터 무결성 보장 기법
    • writer 프로세스에 의한 데이터 접근 시에만 상호 배제 및 동기화 필요함
    • 모니터 구성
      • 변수 2개
        • 현재 읽기 작업을 진행하고 있는 reader 프로세스의 수
        • 현재 writer 프로세스가 쓰기 작업을 진행 중인지 표시
      • 조건 큐 2개
        • reader / writer 프로세스가 대기해야 할 경우에 사용
      • 프로시저 4개
        • reader(writer) 프로세스가 읽기(쓰기) 작업을 원할 경우에 호출, 읽기(쓰기) 작업을 마쳤을 때 호출
  • Dining philosopher 문제 
    • 5명의 철학자
    • 철학자들은 아래 두 가지만 반복
      • 생각하는 일
      • 스파게티 먹는 일
    • 공유 자원
      • 스파게티
      • 포크
    • 스파게티를 먹기 위해서는 좌우 포크 2개를 모두 들어야 함

• 장점
  • 사용이 쉽다
  • Deadlock 등 error 발생 가능성이 낮음
• 단점
  • 지원하는 언어에서만 사용 가능
  • 컴파일러가 OS를 이해하고 있어야 함
    • 임계 영역 접근을 위한 코드 생성