- Published on
OS : 프로세스 동기화 상호배제
- Authors
- Name
- Bora Choi
동기화(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에 수행됨
- 위 연산들은 indivisible(or atomic)연산
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(증가)
- 초기화 연산,p(),v()로만 접근 가능
- 임의의 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 접근을 위한 코드 생성