logo
Published on

OS : 프로세스 동기화 상호배제

Authors
  • avatar
    Name
    Bora Choi
    Twitter

동기화(Process Synchronization)

  • 다중 프로그래밍 시스템
    • 여러 개의 프로세스들이 존개
    • 프로세스들은 서로 독립적으로 동작
    • 공유 자원 또는 데이터가 있을 때, 문제 발생 가능
  • 동기화 (Synchronization)-
    • 프로세스들이 서로 동작을 맞추는 것
    • 프로세스들이 서로 정보를 공유하는 것

Asynchronous and Concurrent P's

  • 비동기적(Asynchronous) : 프로세스들이 서로에 대해 모른
  • 병행적(Concurrent) : 여러 개의 프로세스들이 동시에 시스템에 존재 병행 수행중인 비동기적 프로세스들이 공유 자원에 동시 접근할 때 문제가 발생할 수 있음

Terminologies

  • Share data(공유 데이터) : 여러 프로세스들이 공유하는 데이터
  • Critical section(임계 영역) : 공유 데이터를 접근하는 코드 영역(code segment)
  • Mutual exclusion(상호 배제) : 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것

Mutual exclusion(상호 배제)

Mutual exclusion primitive

  • enterCS() primitive
    • Critical section 진입 전 검사
    • 다른 프로세스가 critical section안에 있는지 검사
  • exitCS() primitive
    • Critical section을 벗어날 때의 후처리 과정
    • Critical section을 벗어남을 시스템이 알림

Requirements for ME primitives

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

Mutual Exclusion Solutions

  • SW solutions

    • Dekker's algorithm(Peterson’s Algorithm)
    • Dijkstra's algorithm, Knuth's algorithm, Eisenberg and McGuire's algorithm, Lamport's algorithm
  • HW solution

    • TestAndSet(TAS) instruction
  • OS supported SW solution

    • spinlock
    • semaphore
    • eventcount/ sequencer
  • Language-Level solution

    • Monitor

SW solutions

Dekker's Algorithm

  • Two process ME을 보장하는 최초의 알고리즘
  • turn 과 flag를 사용

Peterson's Algorithm

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

N-Process Mutual Exclusion

  • 다익스트라 Dijkstra
    • 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결
    • 실행 시간이 가장 짧은 프로세스에 프로세서 할당하는 세마포 방법, 가장 짧은 평균 대기시간 제공
  • 크누스 Kuth
    • 이전 알고리즘 관계 분석 후 일치하는 패턴을 찾아 패턴의 반복을 줄여서 프로세스에 프로세서 할당
    • 무한정 연기할 가능성을 배제하는 해결책을 제시했으나, 프로세스들이 아주 오래 기다려야함
  • 램포트 lamport
    • 사람들로 붐비는 빵집에서 번호표 뽑아 빵 사려고 기다리는 사람들에 비유해서 만든 알고리즘(Bakery algorithm)
    • 준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하어 그 중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당함
  • 핸슨 Brinch Hansen
    • 실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것
    • 대시시간과 실행 시간을 이ㅛㅇ하는 모니터 방법
    • 분산 처리 프로세서 간의 병행서 제어 많이 발표

Dijkstra's Alorithm

Dijkstra 알고리즘의 flag[] 변수

flag[] 값의미
idle프로세스가 임계 지역 진입을 시도하고 있지 않을때
want-in프로세스의 임계 지역 진입 시도 1단계일 때
in-CS프로세스의 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을때

SW solutions

  • SW solution들의 문제점
    • 속도가 느림
    • 구현이 복잡함
    • ME primitive 실행 중 preemption 될 수 있음 : 공유 데이터 수정 중은 interrupt를 억제함으로서 해결 가능 - overhead 발생
    • Busy waiting : Inefficient

HW solution

Synchronization Hardware

  • TestAndSet(TAS) instruction
    • Test 와 Set을 한번에 수행하는 기계어
    • Machine instruction
      • Atomicity, Indivisible
      • 실행중 interrupt를 받지 않음(preemption 되지 않음)
    • Busy waiting : Inefficient

ME with TAS Instruction

TAS라는 기계어를 통해 ME 구현 가능 ⇒ 3개 이상의 프로세스의 경우, Bounded waiting 조건 위배

N-Process mutual exclusion

기존 TAS 에 waiting이라는 변수를 만듦. 대기 중인 프로세스가 없으면 다른 프로세스의 진입 허용, 대기 프로세스가 있으면 다음 순서로 임계 영역에 진입

HW solution

장점 구현이 간단

단점 Busy waiting : inefficient

Busy waiting 문제를 해소한 상호배제 기법

⇒ Semaphore : 대부분의 OS들이 사용하는 기법

OS supported SW solution

Spinlock

  • 정수 변수
  • 초기화, P(),V() 연산으로만 접근 가능
    • 위 연산들은 indivisible(or atomic)연산
      • OS support
      • 전체가 한 instruction cycle에 수행됨
P(S){
  while(S<=0 ) do
  endwhile;
  S = S-1;
}

V(S){
  S = S+1;
}
  • 멀티 프로세서 시스템에서만 사용가능
  • Busy waiting

Semaphore

  • 1965년 Dijkstra가 제안
  • Busy waiting 문제 해결
  • 음이 아닌 정수형 변수(S)
    • 초기화 연산,p(),v()로만 접근 가능
      • P:Probern(검사)
      • V:Verhogen(증가)
  • 임의의 S변수 하나에 ready queue하나가 할당 됨

Binary semaphore

  • S가 0과1 두 종류의 값만 갖는 경우
  • 상호배제나 프로세스 동기화의 목적으로 사용

Counting semaphore

  • S가 0이상의 정수값을 가질 수 있는 경우
  • Producer-Consumer 문제 등ㅇ르 해결하기 위해 사용
    • 생산자-소비자 문제

연산

  • 초기화 연산

    • s 변수에 초기값을 부여하는 연산
  • P()연산, v()연산

    모두 indivisible 연산

    • os support 보장
    • 전체가 한 instruction cycle에 수행 됨
  • No busy waiting

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

    • Starvation problem

Eventcount/Sequencer

  • 은행의 번호표와 비슷한 개념

Sequencer

  • 정수형 변수
  • 생성시 0으로 초기화, 감소하지 않음
  • 발생 사건들의 순서 유지
  • ticket() 연산으로만 접근 가능

ticket(s)

  • 현재까지의 tikect()연산이 호출된 횟수를 반환
  • Indivisible operation

Eventcount

  • 정수형 변수
  • 생성시 0으로 초기화, 감소하지 않음
  • 특정 사건의 발생 횟수를 기록
  • read(E), advance(E), await(E,v) 연산으로만 접근 가능

read(E)

  • 현재 Eventcount 값 변환

advance(E)

  • E <- E+1
  • E를 기다리고 있는 프로세스를 깨움(wake-up)

await(E,v)

  • V는 정수형 변수
  • if(E<v)이면 E에 연결된 Q에 프로세스 전달(push) 및 CPU scheduler 호출

Eventcount/Sequencer

  • No busy waiting
  • No starvation
    • FIFO scheduling for Q
  • Semaphore 보다 더 low-level control이 가능

High-level Mechanism

  • language-level constructs
  • Object-Oriented concept과 유사
  • 사용이 쉬움
    • Monitor
    • Path expressions
    • Serializers
    • Critical region, conditional critical region

Monitor

  • 공유 데이터와 critical section의 집합
  • Conditional variable : wait(), signal() operations

Monitor의 구조

  • Entry queue (진입 큐)
    • 모니터 내의 procedure 수만큼 존재
  • Mutual exclusion
    • 모니터 내에는 항상 하나의 프로세스만 진입 가능
  • Information hiding(정보 은폐)
    • 공유 데이터는 모니터 내의 프로세스만 접근 가능
  • Condition queue (조건 큐)
    • 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기
  • Signal queue(신호제공자 큐)
    • 모니터에 항상 하나의 신호제공자 큐가 존재
    • signal() 명령을 실행한 프로세스가 임시 대기

Monitor의 장단점

장점

  • 사용이 쉽다
  • Deadlock 등 error 발생 가능성이 낮음

단점

  • 지원하는 언어에서만 사용 가능
  • 컴파일러가 OS를 이해하고 있어야 함
    • Critical section 접근을 위한 코드 생성