CS/운영체제

프로세스 동기화

yhsim98 2022. 7. 29. 00:52

Process Synchronization(프로세스 동기화)

프로세스 혹은 스레드는 shared data라 불리는 공유 데이터를 가진다.

 

이러한 공유 데이터에 여러 프로세스가 접근할 때 접근 순서에 따라 공유 데이터 결과가 달라질 수 있는데 이것을 Race condition이라 한다.

 

이러한 race condition을 해결하기 위해 나온 개념이 Critical Section Problem이다.

 

프로세스 혹은 스레드에서 공유 데이터에 접근하는 영역을 Critical Section이라 하고, 한 스레드가 Criticial Section에 접근하고 있을 때, 다른 스레드가 접근하지 않도록 한다면 문제가 해결된다는 것이다.

 

이러한 Critical Section problem을 해결하면 자연스럽게 동기화가 이뤄진다는 것이다.

 

이것을 위해서는 Mutual Exclusion, deadlock, starvation을 해결해야 한다.

비동기적과 병행적(Asynchronous and Concurrent P's)

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

Terminologies

  • Shared data(공유 데이터)
    • 여러 프로세스들이 공유하는 데이터
  • Critical section(임계 영역)
    • 공유 데이터를 접근하는 코드 영역
    • 접근 순서에 따라 공유 데이터 결과가 달라질 수 있는데 이것을 Race condition이라 한다
  • Mutual exclusion(상호배제)
    • Race condition을 해결하는 방법
    • 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것

Mutual Exclusion Methods

공유 영역에 들어가기 전 검사하고, 나올 때 알려주면 해결할 수 있다

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

Requirements for ME primitives

코드상에서 경쟁 조건이 발생할 수 있는 특정 부분을 critical section이라 합니다. 이런 critical section 문제를 해결하기 위해서는 몇 가지 조건을 충족해야 합니다.

  • Mutual exclusion(상호배제)
    • Critical section에 프로세스가 있으면 다른 프로세스의 진입을 금지
  • Progress(진행)
    • deadlock 이 발생예방 혹은 회피 등 해결할 수 있어야 한다
    • CS안에 있는 프로세스 외에는, 다른 프로세스가 CS(Critical Section)에 진입하는 것을 방해하면 안됨
    • CS안에서 작업중인 프로세스가 없다면 다른 프로세스가 CS에 접근할 수 있어야 한다
  • Bounded waiting(한정대기)
    • sturbation 현상에 대처할 수 있어야 한다
    • 프로세스의 CS진입은 유한시간 내에 허용되어야 함

Peterson's Algorithm

Dekker's 보다 간단하게 구현

busy waiting 문제가 있다

2개의 프로세스가 동시에 critical section에 접근하고자 하는 문제를 해결

  • Mutex 라고 한다
flag[0] = true
turn = 1
while(flag[1] and turn = 1) do
// 상대가 깃발을 들고 있고 상대턴이면 기다린다, busy waiting
endwhile;

//Critical section

flag[0] = false

N-Process Mutual Exclusion

  • 다익스트라 알고리즘
    • 최초로 n개 해결
    • 2단계를 거쳐서 들어간다
  • SW Solutions
    • 속도가 느리고 구현이 복잡하다
    • ME primitive 실행 중 preemption 될 수 있다
      • 공유 데이터 수정 중은 interrupt를 억제 함으로써 해결 가능
      • overhead 발생
    • Busy waiting
      • inefficient
      • 기다리는데 게속 반복문을 돌며 확인해야 한다
      • CPU를 쓸대없이 소모

Synchronization Hardware

  • TestAndSet (TAS) instruction
    • test와 set을 한번에 수행하는 기계어
    • Machine instruction
      • Atomicity, indivisible
      • 실행 중 interrupt를 받지 않음(Preemption 되지 않음)
    • Busy waiting
      • inefficient
  • 들어가는 순서는 정해지지 않았기 때문에 3개 이상의 경우 Bounded waiting 조건에 위배될 수 있다

OS supported SW solution

os가 지원하는 mutual exclusion solutions

Spinlock

  • 정수 변수 S
    • 1이면 아무도 접근하지 않는 상태, 0이면 누군가 접근한 상태
  • 초기화 연산, P(), V() 연산으로만 접근 가능
    • 위 연산들은 indivisivle(or atomic)연산
      • OS가 atomic 함을 보장해준다
      • 전체가 한 instruction cycle에 수행 됨
    • P()는 프로세스 빼가는거 V()는 넣는거
    • P는 spinlock 변수값이 있으면 감소시키며 통과
      • 없다면 게속 반복문을 돌면서 확인한다
    • V는 나오면서 호출되는데 다시 반납했다고 변수값 증가
  • CPU가 멀티 프로세서 시스템이어야 사용 가능하다 아니면 무한 로딩 길린다
    • cpu내부의 프로세스를 내보낼 코어가 있어야 한다
  • Busy waiting 문제는 여전히 남아있다
  • busy waiting 문제가 무조건 안좋은 것은 아니다

Semaphore

  • 음이 아닌 정수형 변수(S)
    • 초기화 연산, P(), V()로만 접근 가능
      • P (검사)
        • 물건이 있으면 s 감소시키고 큐에 삽입
      • V (증가)
        • 큐에 있으면 팝 하고 s 증가시킴
      • 모두 indivisible 연산
        • os support
        • 전체가 한 instruction cycle에 수행 됨
    • 임의의 S 변수 하나에 ready queue 하나가 할당 됨
  • Binary semaphore, Counting semaphore로 구분된다
    • binary
      • 0 또는 1 두 종류의 값만 갖는다
      • 상호배제나 프로세스 동기화의 목적으로 사용된다
      • Mutex?
    • counting
      • s가 0 이상의 정수값을 가질 수 있는 경우
      • Producer-Consumer 문제 등을 해결하기 위해 사용
  • 작동 방식
    • P : s가 0보다 크면 s를 감소시키고 CS으로 들어감, s가 0이면 큐에 들어가서 기다림
    • V : CS에 들어간 프로세스가 나올 때 사용하는 연산, s를 증가시키고 큐에 프로세스가 있다면 하나 꺼냄
  • busy waiting 문제가 해결됬다
  • semaphore queue에 대한 wake-up 순서는 비결정적이다(누가 깨어날지 모른다)
    • Starvation problem(무한대기문제)

세마포어란 여러 프로세스 혹은 스레드가 critical section에 접근하고자 할 때 동시에 접근하는 것을 막기 위해 사용하는 방법입니다.

쓰레드가 코드를 동작하는 도중 acquire() 명령어가 실행되면 critical section에 접근한다는 뜻입니다. 만약 S가 0보다 크다면 현재 critical section에 접근한 프로세스/스레드가 없다는 뜻이므로 들어갈 수 있고 들어갈 때 s를 감소시킵니다. 만약 s가 0이라면 현재 다른 스레드가 cs에 접근했다는 뜻이므로 큐에 들어가 기다리게 됩니다. 이런 acquire() 동작은 os가 원자성을 보장해주게 됩니다.

cs에 접근한 스레드가 작업을 마치고 나오기 위해 release()라는 명령어를 실행시킵니다. 그러면 s를 증가시키고 큐에 프로세스가 있다면 꺼내고 갑니다.

Semaphore로 해결 가능한 동기화 문제들

  • 상호베제문제
  • 프로세스 동기화 문제
  • 생산자-소비자 문제
  • Reader-writer 문제
  • Dining philosopher problem

등

상호배제 문제(Mutual exclusion)

p와 v를 os가 서포트하며 해결

Process synchronization

  • 프로세스들의 실행 순서 맞추기
    • 프로세스들은 병행적이며, 비동기적으로 수행

producer-consumer problem

유한 버퍼 문제라고도 한다.

유한 버퍼(bounded buffer)

생산자는 생산한 데이터를 소비자에게 직통으로 보내지 않고 생산자와 소비자 사이의 버퍼(buffer)에 저장한다.

생산자와 소비자의 작업 속도에 차이가 있기 때문이다.(생산자가 소비자보다 빠르다)

 

그렇기 때문에 생산자는 데이터를 생산하여 버퍼에 쌓고, 소비자는 버퍼에서 데이터를 소비한다.

 

생산자-소비자 문제란 이렇게 데이터를 버퍼에 저장하고, 소비하는 과정에서 일어날 수 있는 문제를 의미한다.

대표적으로 Critical Section에 문제와 busy waiting 문제가 있다.

  • Critical Section 문제
    • 생산자가 버퍼에 데이터를 쓰는 도중 소비자가 데이터를 읽거나
    • 소비자가 데이터를 읽는 도중 생산자가 데이터를 쓰면 문제가 생길 수 있다

 

  • count
    • 버퍼 영역은 메모리에 있으므로 공간이 한정적이다. 
    • 그래서 count라는 변수를 통해 버퍼의 상태를 공유한다
    • 생산하면 count + 1, 소비하면 count - 1

 

  • 생산자 프로세스
    • 메시지를 생성하는 프로세스 그룹
  • 소비자 프로세스
    • 메세지를 전달받는 프로세스 그룹
  • I/O device가 열심히 생산해서 공유 메모리에 저장하면 프로세스가 가져다 소비한다
  • producer-consumer problem with single buffer
    • buffer 공간이 하나인 경우
    • 소비 semaphore과 생산 semaphore 유지
    • producer경우 소비가 1이면 소비 0으로 생산 1로 만듬
    • consumer경우 생산이 1이면 생산 0으로 소비 1로 만듬
    • 소비나 생산이 각자의 경우 0이라면 q에 넣기
    • 소비자나 생산자의 V가 호출되는(끝나는) 순간 큐에 대기자가 있는지 확인 후 대기자가 있다면 반대쪽 프로세스 재실행
  • producer-consumer problem with n-buffers
    • 소비자 생산자 semaphore 유지하며 한번에 하나의 소비자나 생산자만 돌아가게 함
    • 채워진 buffer 수, 비어있는 buffer 수만큼 각자 semaphore유지

Reader-Writer problem

  • Reader
    • 데이터에 대해 읽기 연산만 수행
    • 한번에 여럿 써도 됨
  • Writer
    • 데이터에 대해 갱신 연산을 수행
    • 한번에 하나만 써야 함(상호배제)
  • Reader Writer 둘 중 한종류만 한번에 쓸 수 있다
  • Reader Writer 우선권 부여해서 해결
    • reader preference solution

Binary semaphore

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

Counting semaphore

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

Eventcount/Sequencer

  • 은행의 번호표와 비슷한 개념
  • No busy waiting
  • No starvation
  • Semaphore 보다 더 low-level control 가능
    • 큐에서 출력순서 같은거
  • Sequencer
    • 정수형 변수
    • 생성시 0으로 초기화, 감소하지 않음
    • 발생 사건들의 순서 유지
    • ticket() 연산으로만 접근 가능
  • ticket(S)
    • 현재까지 ticket() 연산이 호출 된 횟수를 반환
    • Indivisible operation
  • Eventcount
    • 정수형 변수, E
    • 생성시 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에 연결된 Qe(큐, 기다려야 하니까)에 프로세스 전달(push) 및 CPU scheduler 호출

producer-consumer problem

await in은 프로세스 번호체크, out은 남은 프로세서 수 체크

High-level Mechanism(언어적 해결)

Monitor

  • 공유 데이터와 Critical section의 집합
  • Conditional variable
    • wait(), signal() operations
  • Entry queue(진입 큐)
    • 모니터 내의 procedure 수만큼 존재
  • Mutual exclusion
    • 모니터 내에는 항상 하나의 프로세스만 진입 가능
    • languate가 보장해줌
  • Information hiding(정보 은폐)
    • 공유 데이터는 모니터 내의 프로세스만 접근 가능
  • Condition queue(조건 큐)
    • 모니터 내의 특정 이벤트를 기다리는 프로세스의 대기실
  • Signaler queue(신호제공자 큐)
    • 모니터가 항상 하나의 신호제공자 큐가 존재
    • signal() 명령을 실행한 프로세스가 임시 대기
  • 장점
    • 사용이 쉽다
    • Deadlock 등 error 발생 가능성 낮음
  • 단점
    • 지원하는 언어에서만 사용 가능
    • 컴파일러가 OS를 이해하고 있어야 함
      • Critical section 접근을 위한 코드 생성