[OS] 6. 프로세스 동기화

신명철·2022년 5월 31일
0

OS

목록 보기
24/27

Race Condition

  • Storage Box를 공유하는 Execution Box가 여럿이면 Race Condition의 가능성이 있음
    • e.g) Memory <-> CPU : MultiProcessor system
    • e.g) Address Space <-> Process : 공유 메모리 사용중인 프로세스들 or 커널 내부 데이터에 접근하는 루틴들 간/ 커널모드 수행중인데 다른 커널모드가 인터럽트로 들어와서 다른 루틴을 수행하는 경우
  • 언제 발생하는가 ?
      1. kernel 수행 중 인터럽트 발생 시
      • kernel 수행 중 count++하고 있는데 interrupt가 들어와서 count-- 를 수행함
      • 위와 같은 경우, count = 0 일 것이라고 생각하지만 사실은 1 증가시킨것만 반영됨 => interrupt의 수행이 반영되지 않는 상황이 발생
      • interrupt를 보류하는 방법으로 해결함
      1. Process가 system call 해서 kernel mode로 수행중인데 context switch가 일어나는 경우
      • kernel mode 수행중인 process가 할당시간이 끝나서 다른 process로 CPU가 넘어가버림
      • 다른 CPU가 kernel mode로 같은 데이터를 건드림
      • 이 경우에서도 +2가 아니라 Process A의 +1만 반영됨
      • kernel mode 수행 중일때는 CPU를 preempt하지 않고, user mode로 빠져나갈 때 빼앗는 방법으로 해결함
      1. Multiprocessor에서 shared memory 내의 kernel data
      • CPU의 순서에 따라서 결과가 달라지게 됨
      • 위의 두 예시처럼 interrupt를 잠시 미루는 방법으로는 해결할 수 없음
        1. lock을 걸어서 한 번에 하나의 CPU만 커널에 들어갈 수 있도록 함 -> 비효율적
        1. 커널 내부의 shard data 에 그 data에 대한 lock/unlock을 걸어 해결 -> 효율적

프로세스 동기화 문제

  • 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.
  • 일관성 유지를 위해서 협력 프로세스 간의 실행 순서를 정해주는 매커니즘이 필요함
  • Race Condition
    • 여러 프로세스들이 동시에 공유 데이터에 접근하려는 상황
    • 마지막에 사용한 프로세스에 따라서 최종 연산 결과가 달라짐
  • Race Condition을 막기위해 concurrent process는 동기화되어야 함

사용자 프로세스 P1 수행중 timer interrupt가 발생해 context switch가 일어나 P2가 CPU를 잡으면 문제가 생기는가?
두 프로세스는 독립적인 데이터를 사용하기에 문제가 생기지 않음. 문제가 생기는 경우는 (1)두 프로세스가 공유 데이터에 접근하거나 (2)커널 내 공유 데이터에 접근하는 경우에만 문제가 생김.


Critical-Section 문제

[P1]
X = X + 1 // critical section
...
[P2]
X = X - 1 // critical section
...
  • n 개 프로세스가 공유 데이터를 동시에 사용하기를 원하는 상황
  • 각 프로세스의 code segment에는 공유 데이터에 접근하는 코드critcal section이 존재
  • 즉, 프로세스의 code는 critical section 이거나, 아니거나 두 개로 구분할 수 있음

프로그램적 해결법 충족조건

  1. Mutual Exclusion(상호 배제)
    • 프로세스가 critical section 부분을 수행중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다
  2. Progress(진행)
    • 아무도 critical section에 있지 않은 상황에서 들어가고자 하는 프로세스가 있다면 critical section에 들어가게 해줘야 한다
  3. Bounded Waiting(한정된 대기)
    • 프로세스가 critical section 에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수는 한계가 있어야 한다.

S/W 해결법

Peterson's Algorithm

  • 위 충족조건을 모두 만족하는 알고리즘
  • Busy Waiting(= spin lock) 발생 => while문을 돌면서 CPU와 memory를 쓰며 wait

H/W 지원

  • a의 값을 (1)읽고, (2)1로 설정 하는 것을 test & set이라는 하나의 instruction으로 수행

  • HW 적으로 Test & Modify 를 atomic 하게 수행할 수 있도록 지원하면 앞의 문제(spin lock)는 간단히 해결할 수 있음
  • a가 0이면 lock을 걸고(1로 설정) critical section에 들어감
  • a가 1이면 누군가 lock을 걸어놓은 상태기 때문에 대기함

Semaphore

  • 추상 자료형임
    • Object와 Operation으로 구성됨, 실제로 존재하는 것이 아닌 논리적인 개념
  • Semaphore는 2가지 연산으로 이루어져 있음
    • P(S): Semaphore 획득 -> 공유자원 접근
    • V(S): Semaphore 반납
    • P(S)와 V(S)는 atomic하게 이루어져야 함
  • 하지만 Busy waiting 는 효율적이지 못함(= spin lock)
  • block & wakeup 방식으로 개선할 수 있음(=sleep lock)

Block & Wakeup 방식

typedef struct{
	int value;			// semaphore
    struct process *L;	// process wait queue
}Semaphore;
  • Semaphore를 위와 같이 정의함
  • block & wakeup
    • block: 커널은 block을 호출한 프로세스를 suspend 시키고 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
    • wakeup(P): block된 프로세스 P를 wakeup 시키고 이 프로세스의 PCB를 ready queue로 옮김
  • P(S), V(S) 연산은 다음과 같이 정의 됨
    • S 가 음수면 -> 누군가는 기다리고 있다, 양수면 -> 자원의 여분이 있다

Binary Semaphore(=mutex)

  • 0 or 1 만 가질수 있는 semaphore
  • 주로 mutual exclusion(lock/unlock)에 사용함

Semaphore 주의점

  • Deadlock
    • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상이 발생
    • S와 Q를 1로 초기화된 semaphore라고 가정하면 상대방이 주기만을 기다리며 영원히 기다리게 됨
    • 자원을 얻는 순서를 정해두는 등의 방법을 사용해야 함(e.g Q는 S를 얻은 다음에 얻을 수 있다)
  • Starvation
    • 프로세스가 suspend된 이유에 해당하는 semaphore queue에서 빠져나갈 수 없는 현상
    • 특정 프로세스들만 자원을 공유하고, 나머지 프로세스들은 자원을 공유하지 못하는 현상

Semaphore의 고전적 동기화 문제

  1. Bounded-Buffer Problem (생산자-소비자 문제)
  2. Readers and Writers Problem
  3. Dining-Philosophers Ploblem (식사하는 철학자 문제)

1. Bounded-Buffer Problem

  • Producer, Consumer 두 가지 프로세스가 존재한다.
    • Producer: full buffer 생산, empty buffer 소비
    • Consumer: full buffer 소비, empty buffer 생산
  • Semaphore는 두 가지 역할을 해야 함
      1. shared data 각각에 lock을 걺 (binary semaphore)
      1. consumer를 위해 가용 자원의 갯수를 세야 함 (integer semaphore)

2. Readers and Writers Problem

  • 한 프로세스가 DB(shared data)에 write 중일 때 다른 프로세스가 접근하면 안됨(P(db), V(db))
  • read는 동시에 여럿이 해도 됨
  • reader의 P(mutex), V(mutex)는 readcount를 위한 lock임
  • 최초의 reader인 경우 write를 막아줘야 하기 때문에 lock을 걸어주고, 마지막으로 읽는 reader가 이 lock을 unlock함
  • writer는 reader들의 작업이 다 끝날 때까지 기다리기 때문에 만약 reader의 작업이 끝나기 전에 새로운 reader들이 연속적으로 들어온다면 starvation문제가 발생할 수 있음

3. Dining-Philosophers Ploblem (식사하는 철학자 문제)

  • 철학자는 밥을 먹기 위해 양쪽의 젓가락을 들어야만 함 -> 젓가락(shared data)에 대해서 lock을 걺
  • Deadlock 문제가 발생함 -> 모두 왼쪽 젓가락만 잡게 된다면 아무도 밥을 먹을 수 없게 됨
    • 해결 방안
        1. 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 함
        1. 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집게 함
        1. 비대칭 (짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 함)
  • 젓가락을 잡을 수 있는지를 나타내는 semaphore(self), 자신과 옆 철학자의 상태를 변환하는 semaphore(mutex)
  • test(): 둘 다 잡을 수 없으면 젓가락을 내려놓음

  • Semaphore 는 다음과 같은 문제점이 있음
    • 코딩하기 힘듦
    • 정확성의 입증이 어려움
    • 자발적인 협력이 필요함
    • 한번의 실수가 모든 시스템에 치명적임
    • e.g) P(mutex) 연속 두 번 호출, V(mutex)를 P(mutex)보다 먼저 호출

Monitor

  • Monitor는 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유 보장을 위한 high-level synchronization construct임
  • 공유 데이터를 Monitor라는 내부의 procedure를 통해서만 접근하게 함
  • 모니터 내에서는 한번에 하나의 프로세스만이 활동할 수 있음
  • 프로그래머가 명시적으로 lock/unlock 할 필요가 없음
  • 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable을 사용함
  • condition variable은 waitsignal 연산에 의해서만 접근할 수 있음
    • x.wait(): 다른 프로세스가 x.signal() 하기 전까지 suspend 됨
    • x.signal(): suspend된 하나의 프로세스를 resume 한다.

출처 : http://www.kocw.net/home/search/kemView.do?kemId=1046323

profile
내 머릿속 지우개

0개의 댓글