다중 프로그래밍 시스템에는 여러개의 프로세스들이 존재한다.
프로세스들은 서로 독립적(동시적)으로 동작하는데, 이때 공유자원이나 데이터가 있으면 문제가 발생 할 가능성이 생긴다.
동기화(synchronization)
시스템을 동시에 작동시키기 위해 프로세스들이 서로 정보를 공유하는 것
동기화가 필요한 이유
공유 데이터에 프로세스가 동시에 접근하면 Data Inconsistency(데이터 불일치)가 발생할 수 있다.
Data Consistency(데이터의 일관성)을 유지하기 위한 메커니즘을 동기화라고 한다.
이러한 상태에 도달하는 것은 여러 개의 프로세스가 동시에 내 잔고를 조작하도록 허용했기 때문!
이와 같이 동시에 여러 개의 프로세스가 동일한 자료에 접근하여 조작하고,
그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상태(race condition)라고 한다.
이러한 경쟁 상태가 발생하지 않도록 해야하고 진입하게 되면 임계 영역으로 잠궈야 한다.(Lock)
임계영역(Critical Section)
공유 데이터를 접근하는 코드 영역
임계 영역 문제를 해결하기 위한 3가지 조건
1. Mutual exclution (상호 배제)
- 하나의 프로세스가 임계 영역에 존재하다면, 다른 프로세스는 임계 영역에 접근할 수 없어야 한다.
- 즉, 한번에 두개 이상의 프로세스 접근 X
2. Progress (진행)- 임계 영역에 프로세스가 존재하지 않을 경우, 다른 프로세스가 접근할 수 있도록 해야한다.
- 임계 영역에 접근하고자 하는 프로세스가 하나가 아니라면 어느것이 들어갈지 결정해주어야한다.
3. Bounded Waiting (한정 대기)- 다른 프로세스의 기아(Starvation)를 방지하기 위해 한번 임계 구역에 들어간 프로세스는 다음 임계영역에 들어갈 때 제한을 두어야 한다.
Mutual exclution Methods
enterCS()
임계 영역 진입 전 다른 프로세스가 임계 영역 안에 있는지 검사
화장실 들어가기 전에 노크!! 같은 느낌...
exitCS()
임계영역을 벗어날때 시스템이 알려줌
저 끝났어요. 다음 분 들어오세요!! 같은 느낌...
Mutual exclution Solutions
SW Solution
Dekker's Algorithm
Two Process ME을 보장하는 최초의 알고리즘
플래그와 턴 변수를 사용하여 두 프로세스가 서로의 상태를 확인하고, 임계 구역에 들어갈 수 있는지 판단
f0 ← false
f1 ← false
turn ← 0 // or 1
p0: p1:
f0 ← true f1 ← true
while f1 { while f0 {
if turn ≠ 0 { if turn ≠ 1 {
f0 ← false f1 ← false
while turn ≠ 0 { while turn ≠ 1 {
} }
f0 ← true f1 ← true
} }
} }
// 임계 구역 // 임계 구역
... ...
// 나머지 구역 // 나머지 구역
turn ← 1 turn ← 0
f0 ← false f1 ← falsePeterson's Algorithm
Dekker의 알고리즘을 개선하여 더 간결하고 이해하기 쉽게 만든 알고리즘
Dijkstra's Algorithm
프로세스 n개의 상호배제 문제를 해결한 알고리즘
SW Solution의 문제점
1. 속도가 느리고, 구현이 복잡하다.
2. 상호배제 실행 중 preemption 될 수 있다.
3. Busy waiting : 기다리는데 바쁘다 -> 비효율적이다.
HW Solution
TestAndSet instruction
실행중에 인터럽트를 받지않음 -> preemption 되지 않음
3개 이상의 프로세스의 경우, Bounded Waiting 조건 위배..
그럼 N개의 프로세스는..?
HW Solution의 문제점
Busy Waiting!
Busy Waiting 문제를 해소한 상호배제 기법 -> 세마포어
OS Solution
Spinlock
임계 구역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식
초기화 P(), V() 연산으로만 접근 가능
P()는 자물쇠를 거는거, V()는 자물쇠를 푸는거라고 생각하면 쉬움
들어갈때 잠구고 나올때 풀기,,
스핀락의 문제
한 스레드가 Lock을 오랫동안 소유하고 있다면 기다리는 스레드들은 계속해서 무한루프만 돌고있는 상태가 된다. 즉 굉장히 비효율적이다.
그래서 멀티 프로세서 시스템에서만 사용 가능
Semaphore
세마포어(Semaphore)는 음이 아닌 정수형 변수(S)
초기화 연산 P(), V() or wait(), signal()
임의의 S 변수 하나에 ready queue가 할당 됨
S는 물건 수로 생각
스핀락과 다르게 ready queue에서 기다림
세마포어는 Counter의 개수에 따라
1개의 경우 이진 세마포어(Binary Semaphore)
S가 0과 1 두종류의 값만 갖는 경우
상호배제나 프로세스 동기화의 목적으로 사용
2개 이상의 경우 카운팅 세마포어(Counting Semaphore)
S가 0이상의 정수값을 가질 수 있는 경우
생산자-소비자 문제 등을 해결하기 위해 사용
Semaphore로 해결 가능한 동기화 문제들
-
상호배제 문제 (Mutual exclusion)
스핀락은 임계 구역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 기다리지만 세마포어는 대기실에서 기다리면서 대기 -
프로세스 동기화 문제 (Process synchronization)
프로세스들의 실행 순서 맞추기
sync라는 세마포어 변수
pj가 물건을 들고있었다라고 가정했을때, 프로세스 i는 물건이 반납될때까지 P(sync)에서 대기. j는 V(sync) 지나면서 물건 반납 -
생산자-소비자 문제
생산자 프로세스 : 메시지를 생성하는 프로세스 그룹
소비자 프로세스 : 메세지를 전달받는 프로세스 그룹
single buffer일때
single buffer이기 때문에 공간이 1인 경우이다.
물건을 놓고 있을때는 가져가면 안되고 물건을 꺼내가는 중에는 놓을 수 없다.
한번에 한명만 접근 가능
consumed, produced라는 변수 생성
메시지를 생산해서 넣으려고할때 buffer가 비었는지 확인
생산자
P(consumed) -> consumed가 1인지 체크하고 1이면 0으로 변경 후. 물건을 놓기
V(produced) -> 0에서 1로 바꾸면서 생산됐다고 알려줌
소비자
P(produced) -> 물건이 생산됐는지 확인 0이라면 생산이 안된거니깐 대기실에서 기다림 1이라면 안으로 들어가면서 0으로 변경
V(consumed) -> 물건 소비하고 1로 변경
- Reader-writer 문제
- Dining philosopher 문제
...
High-level Mechanism
프로그래밍 언어가 상호배제를 서포팅하기 때문에 사용이 쉽다.
Monitor (모니터)
공유 데이터와 Critical section의 집합
Condition Variable
wait(). signal()
사각형 안이 모니터이고, Critical data와 Critical sections을 모아놓은 방이라고 생각해보자.
책방인데 한번에 한명만 들어올 수 있는 책방이라고 생각했을때
Critical data는 사고 싶은 책, Critical sections은 카운터
모니터의 구조
Entry queue (진입 큐)
• 모니터 내의 procedure 수만큼 존재
Mutual exclusion -> Language가 보장
• 모니터 내에는 항상 "하나의 프로세스"만 진입 가능 (책방에는 한명만)
Information hiding (정보 은폐)
• 공유 데이터는 모니터 내의 프로세스만 접근 가능
Condition queue (조건 큐)
• 모니터 내의 "특정 이벤트"를 기다리는 프로세스가 대기
Signaler queue (신호제공자 큐)
• 모니터에 항상 "하나의 신호제공자 큐"가 존재
• signal() 명령을 실행한 프로세스가 임시 대기
