동기화
- 다중 프로그래밍 시스템
- 여러개의 프로세스, 서로 독립적으로 동작(동시)
- 공유 자원, 데이터가 있을 경우 문제 발생 가능
- 동기화 (Synchronization)
- 프로세스들이 서로 동작을 맞추 거나, 정보를 공유
- 비동기적 : 프로세스들이 서로 모름
- 병행적 : 여러개의 프로세스들이 동시에 시스템에 존재
- 병행 수행중인 비동기적 프로세스들이 공유자원에 동시 접근할 때 문제 발생
공유 데이터(cirtical data)
임계 영역(critical section): 공유 데이터를 접근하는 코드 영역
mutual exclusion(상호 배제)
- 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것
📌상호배제 (mutual exclusion) 의 3가지 조건
- critical section에 프로세스가 있으면 진입을 막음
Progress(진행)
- 다른 프로세스가 cs에 진입하는 것을 방해하면 안됨
Bounded waiting(한정 대기)
- 프로세스의 cs 진입은 유한시간내에 허용되어야 함
📌SW Solution (Mutex)
Dekker's Algorithm
Two process ME를 보장하는 최초의 알고리즘
turn 과 flag 변수를 활용함Peterson's Algorithm
Dekker's algorithm 보다 간단하게 구현
N-Process Mutual Exclusion
Dijkstra's algorithm
flag 3단계로 나눔
1 단계 내턴이 아니면 상대턴이 끝나길 기다린 후 내턴으로 가져옴
2 단계 section에 나혼자 있는 지 확인해서 in-cs가 있으면 처음으로 없으면 section으로SW Solution의 문제점
- 속도가 느리고, 구현이 복잡함
- 그냥 기다리지 않고 1,2단계를 반복하면서 돔 (busy waiting)
- 실행 중에도 선점될 수 있음
HW Solution
TestAndSet(TAS) instruction
- Test 와 Set을 한번에 수행 하는 기계어
- 실행 중 interruput를 받지 않음(preemption 되지 않음)
- 하드웨어 쪽에서 preemption이 안되는 것을 보장 해줌
N-Process Mutual Exclusion
- 대기 중인 프로세스를 찾고 내 바로 뒤의 프로세스를 false로 바꿔줌. -> 순서를 보장해줌
장점: 구현이 간단
단점: Busy waiting 존재 -> 세마포어를 통해 해결
(세마포어: 대부분의 os에서 사용하는 기법)
📌OS supported SW solution
Spinlock
- 정수 변수
- 초기화, P(), V() 연산으로만 접근 가능
- 위 연산들은 indivisible(or atomic) 분산불가능 연산 ➡ OS가 Support 해줌
- 전체가 한 instruction cycle에 수행 됨
- P(S(개수)) 연산은 물건을 꺼내는 연산 (물건이 생기기를 기다림), lock
- V(S) 연산은 물건을 넣는 연산, unlock
- 단점: 멀티프로세서 시스템에서만 사용가능, Busy waiting
📌 Semaphore
Dijkstra가 제안, Busy waiting 문제 해결
음이 아닌 정수형 변수(s)
- 초기화 연산, P(), V()로만 접근 가능
- P:Probern(검사), V:verhogen(증가)
- no busy waiting: 기다려야 하는 프로세스는 queue에 asleep 상태가 됨
P(S)
while(S == 0) wait (on the queue, 물건이 없으면 기다림)
S = S-1;
--- 임계 구역 ---
V(S)
if(queue) wake up //queue에 있는 프로세스 실행
else S = S+1임의의 S(semaphore)변수 하나마다 ready queue하나가 할당 됨
해결가능한 동기화 문제들
- 상호배제, 프로세스 동기화, 생산자-소비자, Reader-writer, Dining philosopher 문제 등
Process synchronization
- 프로세스들의 실행 순서 맞추기, 프로세스들을 병행적, 비동기적으로 수행
Binary semaphore
- S가 0과 1 두 종류의 값만 갖는 경우
- 상호배제나 프로세스 동기화의 목적으로 사용
Counting semaphore
- S가 0이상의 정수값을 가질 수 있는 경우
- Producer-Consumer(생산자-소비자) 문제 등을 해결하기 위해 사용
생산자-소비자 문제
- 생산 후 소비자(1:1)에게 넘길 때 임계영역같은 상황이 발생
생산자에서 소비자 쪽이 비었는 지 확인 -> 생산(+ wake up)
소비자에서는 생산이 됐는 지 확인 -> 소비 - N-Buffer 경우
생산자는 소비자가 비었는 지 확인 ➡ buffer가 비었는 지 확인 Buffer에 N만큼 담기(nrfull+1)
소비자 쪽에서 buffer가 있으면 소비하고 buffer 공간+1 해줌(nrempty).
Reader-Writer problem
- Reader 읽기 연산만 수행(N)
- Writer 갱시 연산을 수행(1)
- 데이터의 무결성을 보장이 필요함
- writer 둘 이상 or reader+writer가 동시에 접근 시 상호배제(동기화) 필요
- reader/writer 에 대해 우선권을 부여해서 해결
Eventcount/Sequencer
semaphore에 있는 기아현상(No startvation)을 없애기 위함. + 순서 control이 가능해지면서 low-level control이 가능
은해의 번호표와 비슷한 개념
Sequencer
- 발생 사건들의 순서 유지
- ticket() 연산으로만 접근 가능
ticket(S)
- 현재까지 ticket() 연산이 호출 된 횟수를 반환
- indivisible operation
- await = P
Eventcount
- 특정 사건의 발생 횟수를 기록
- read(E), advance(E), awit(E,v) 연산으로만 접근
read(E): 현재 Eventcount값 반환
advance(E): E = E+1, wake-up V
await(E,v)
- if(E(현재번호) < v(내번호))이면 E에 연결된 Q(대기실)에 프로세스 전달(push) 및 CPU scheduler 호출
현재 내 번호표 차례가 될 때, 공간이 있으면 buffer에 넣기.
📌Language-Level solution
High-level Mechanism
- 사용이 쉬움, Deadlock 등 error 발생 가능성 낮음
- 지원하는 언어에서만 사용 가능, 컴파일러가 OS를 이해하고 있어야 함
Monitor
- 공유 데이터와 Critical section의 조합 (하나의 프로세스만 접근 가능)
- Conditional variable
- Entry queue(진입 큐)
- Mutual exclusion (lang이 보장)
- Information hiding(정보 은폐)
- Contdition queue(조건 큐) : 특정 이벤트를 기다리는 대기실
- Signaler queue(신호 제공자 큐): 시그널을 보내기 위해 잠깐 대기하는 공간
Dining philosopher problem
- 5명의 철학자가 생각, 식사 만 반복
- 식사를 하기 위해서는 좌우 포크 2개를 사용해야함
➡ 2개를 사용할 수 없으면 대기실에 저장, 내차례가 되면 좌우 포크를 한개씩 줄임, 식사를 마치면 포크를 원래 상태로 되돌린 후 식사할 철학자 깨우기
https://youtu.be/EdTtGv9w2sA [Course] Operating System (CPA310) - 운영체제 강의. HPC Lab. KOREATECH
ㅎㅎ