Chapter6. 동기화 & 상호배제
카테고리: OS
태그: CS
유튜브에 있는 김덕수 교수님의 Operating System 강의를 듣고 정리한 내용입니다.
중간에 등장하는 ppt 내용들은 모두 강의자료를 캡처한 것입니다.
🔧 동기화 (Synchronization)
Multi Programming System
- 여러 개의 프로세스들 존재
- 각 프로세스들은 서로 독립적으로 동작
- 여러 개의 프로세스가 공유 데이터에 접근할 때 문제 발생 가능
- 자원을 효율적으로 요청&배분하기 위해서는 각 프로세스들의 정보 공유가 필요함
용어 정리
- Shared data (or Critical data)
- 여러 프로세스들이 공유하는 데이터
- Critical Section
- 공유 데이터에 접근하는 코드 영역 (code segment)
- Concurrent (병행)
- 여러 개의 프로세스들이 동시에 시스템에 존재
- Synchronization (동기화)
- 프로세스들이 서로 동작을 맞춤
- 프로세스들이 서로 정보를 공유
- Asynchronization (비동기화)
- 프로세스들이 서로에 대해 모름
🔧 상호배제 (Mutual Exclusion)
| 코드 | 실제 기계어 동작 |
|---|---|
|
 |
- 프러세스 pi의 기계어 명령 사이에 프로세서를 뺏기면 결과가 달라질 수 있음
- +1 했는데 +2 결과로 나올 수도.. (add와 store 사이에서 프로세서 pj가 난입)
- 이런 상황을 막기 위해 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막음 → 상호 배제
Mutual exclusion methods
Mutual exclusion primitives
- enterCS() primitive
- Critical section 진입 전 확인
- 다른 프로세스가 critical section 안에 있는지 확인
- exitCS() primitive
- Critical section 벗어날 때 후처리
- Critical section 벗어났음을 시스템에 알림
Requirments for ME primitives
Mutual exclusion primitives가 되기 위해서는 다음 세 가지 조건을 만족해야 함 (쉽지 않다)
- Mutual exclusion
- Critical section(CS)에 프로세스가 있으면 다른 프로세스의 진입을 금지
- Progress
- CS 안에 있는 프로세스 외에는 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨
- CS 밖에서 이래라 저래라 하면 안됨
- Bounded waiting (한정대기)
- 프로세스의 CS 진입을 무한하게 기다리면 안됨
🔧 Mutual exclusion solutions
- SW solution
- Dekker’s algorithm (Peterson’s algorithm)
- Dijkstra’s algorithm
- HW solution
- TestAndSet(TAS) instruction
- OS supported SW solution
- Spinlock
- Semaphore
- Eventcount/sequencer
- Language-Level solution
SW solution
Dekker’s algorithm
- Two process ME를 보장하는 최초의 알고리즘
- flag만으로는 ME의 요구사항을 만족하지 못함
- flag & turn 사용
- Peterson’s algorithm : Dekker’s algorithm 보다 간단하게 구현
Dijkstra’s algorithm
- flag[] 변수
- idle: CS진입 시도하고 있지 않음
- want-in: CS 진입 시도 1단계
- (다른 프로세스가 쓰고있으면 끝날 때까지 계속 체크하면서 대기)
- in-CS: CS 진입 시도 2단계 or CS 내에 있을 때
- n개의 프로세스 상호배제 문제를 해결한 최초의 알고리즘
SW solution의 한계
- ME primitive 실행 중 preemption 방지하기 힘듬
- 느려지고 구현이 복잡
- Busy waiting problem
- 다른 프로세스가 끝날 때 까지 계속 체크
- 비효율적
HW solution
- Test와 set을 한번에 수행하는 기계어
- 기계어 실행 중 inturrupt (preemption)를 하드웨어가 막아줌
- 장점: 구현이 간단
- 단점: Busy waiting problem
OS supported SW solution
Preemption을 OS가 막아준다!
Spinlock
- active = 1: CS 실행중인 프로세스 없음
- active = 0: CS 실행중인 프로세스 있음
- P(S): 내가 쓴다 (자물쇠 잠금)
- V(S): 잘 놀다 갑니다 (잠금 해제)
- Busy waiting problem 여전함
Semaphor
| semaphor | P(), V() |
|---|---|
 |
 |
- 1965년 Dijkstra가 제안
- Busy waiting problem 해결!
- 대부분의 os가 사용
- 음이 아닌 정수형 변수 S
- 초기화, P(), V()로만 접근 가능
- P: Probern (검사)
- V: Verhogen (증가)
- S 하나 당 ready queue 하나 할당
Process synchronization
- 독립적으로 실행하는 프로세스들의 실행 순서 맞추기
- Sync라는 semaphore변수 선언 (CS처럼 다루기)
Producer-Consumer problem
- Producer 프로세스
- 메시지를 생성하는 프로세스 그룹
- Cosumer 프로세스
- 메시지를 전달받는 프로세스 그룹
- 메시지 생산이 끝나기 전에 소비하면 안됨
- buffer를 CS처럼 다룸
Producer-Consumer problem with N-buffers
Reader-Writer problem
- Reader: 데이터 읽기 연산만 수행
- Writer: 데이터 갱신 연산을 수행
- Reader들은 동시에 접근 가능
- Writer끼리 or Reader와 Writer 동시 접근은 상호배제(동기화) 필요
- reader/writer 우선권 부여
- 위 예시는 reader preference solution
Semaphore 특징
- No busy waiting
- 기다려야 하는 프로세스는 block(asleep)상태가 됨
- 계속 확인할 필요 X (대기실에서 편하게 대기)
- Semaphore queue에 대한 wake-up 순서는 비결정적
- Starvation problem 생길 수 있음
- 대기 중인데 계속 새로운 프로세스 들어오면..
Eventcount / Sequencer
- 은행의 번호표 개념
- Sequencer (표 뽑아주는 기계)
- 정수형 변수
- 생성시 초기값 0, 증가만 함
- 발생 이벤트들의 순서 유지
- ticket() 연산으로만 접근 가능
- ticket(S)
- 현재까지 ticket() 연산이 호출된 횟수 반환
- Indivisible operation (os supported)
Primitives
- Eventcount
- sequencer
- read(E), advance(E), await(E) 연산으로만 접근 가능
- read(E)
- 현재 Eventcount 값 반환
- advance(E)
- E ← E + 1
- E 기다리고 있는 프로세스 깨움(wake-up)
- 띵동
- await(E,v)
- v는 정수형 변수
- if(E< v) 이면 E에 연결괸 queue(E)에 프로세스 전달(push) 및 CPU scheduler 호출
- queue: 대기실 & 내 번호 오면 깨워달라고 schedular에 부탁
Producer-Cunsumer problem
Eventcount / Sequencer 특징
- No busy waiting
- No starvation
- FIFO scheduling for Q(E)
- Semaphore 보다 더 low-level control 가능
Monitor
Language-level solution (사용이 쉽다)
| Monitor | Pseudo-code |
|---|---|
 |
 |
- Monitor: 공유 데이터와 critical section의 집합
- 모니터 내에는 항상 하나의 프로세스만 진입 가능
- 공유 데이터는 모니터 내의 프로세스만 접근 가능
- Entry queue (진입 큐)
- 대기중인 Procedures(functions)
- Condition queue (조건 큐)
- 모니터 내의 특정 이벤트를 기다리는 프로세스 대기
- Signal queue (신호 큐)
- 작업이 끝난 프로세스를 반납할 때 release에서 바로 반납할 수 없음 (모니터 내에는 하나의 프로세스만 존재하기 때문)
- signal을 거쳐서 작업이 끝났음을 알리고 반납
댓글 남기기