프로세스 동기화란,
여러개의 프로세스가 하나의 자원에 동시에 접근하게되면 일관성을 유지할 수 없다.
이렇게 공유되는 데이터에 접근하는 코드를 critical section 이라고 한다.
이 문제점을 해결하기위해 프로세스 동기화가 필요하다.
해결 방법 : critical section에 하나의 프로세스만 접근 가능하도록
임계구역(Critical Section 해결 조건)
- Mutual Exclusion(Mutex, 상호배제)
- 특정 프로세스가 critical section을 점유하고 있으면 다른 프로세스가 접근 불가
- Progress
- critical section에 누구도 점유하고 있지않을때에는 critical section을 점유할 수 있다면 그 즉시 바로 점유한다.
- Bounded Waiting(유한 대기)
- 기아현상을 방지하기위해 critical section을 점유하기위해 무한점대기하는 상황을 막아야한다.
이 문제를 해결하기 위한 방법
1. 자신의 차례가 올때까지 대기
- P0가 먼저 critical section을 점유
- critical section다 수행하고 turn 1로 변경후 remainder section 진행(진행했던 부분을 기억)하고 다시 turn 0이 될때까지 대기
- P1이 turn 1을 확인하고 critical section 점유
1,2,3 과정을 반복
하지만 P1이 turn 1 을 확인했지만 critical section 을 점유하지 않는다면 critical section을 비어있게되는 문제가 발생
2. critical section를 점유할 것인지를 결정하도록 진행(배열을 사용해서 점유 의지를 저장)
- flag[0]=true 설정
- flag[0]=true : P0이 critical section 점유할 의지가 있다를 의미
- flag[1]을 확인하고 true라면 P1이 critical section 점유
- flag[0]=true 일때까지 critical section 점유
- flag[0]=true 이면 P0이 critical section 점유
1,2,3,4 반복
하지만 데드락 발생 가능 : 모든 프로세스가 동시에 critical section 에 접근하려 한다면 서로 못들어가는 상황 발생(둘다 들어가고자 하는 의지가 있지만 다른 프로세스의 flag 가 true 라면 들어가지 못하기때문)
3. Peterson Algorithm(1번 방법 + 2번 방법)
- flag[0]=true로 설정 후 turn은 1로 설정
- 만약 flag[1]==true && turn==1 이면 1이 critical section점유
- 아니라면 P0가 critical section 점유
- 점유를 마치면 flag[0]=false 설정
프로세스가 들어가고자 하는 의지가 있는 프로세스를 확인하고 turn값이 무조건 하나는 보장되기때문에 critical section이 비어있을 일도 없고 deadlock 현상도 없다.
하지만 Busy Waiting 현상 발생 : 프로세스가 일을 다하고 대기를 하는 시간에도 critical section를 점유해야한다.(P0가 일이 끝나고 P1이 점유하고 싶을때까지 critical section를 점유한다)
4. Lock 을 통한 해결 방법
- P0가 critical section를 점유하고 있다면 P1의 접근을 막는다.
deadlock이 발생할 수 없는 이유는 lock은 원자성을 지키기때문에 반드시 하나에만 lock을 걸어줄 수 있다. 동시에 접근해도 하나에만 락을 걸음
이때 lock의 하나만 점유한다는 것을 보장하기 위해 HardWare를 이용
- HardWare 적인 Test_and_Set(TAS 방식)
HardWare를 이용해서 lock의 현재 true인지 false인지를 저장하고 lock을 true로 설정한뒤 lock의 이전 정보를 리턴해주는 과정을 동시에 실행하는 것이 가능
Mutex vs Semaphores
세마포어란, 멀티 프로그래밍 환경에서 하나의 자원에 대한 접근을 제어하는 방법
- binary semaphores(mutex)
- 하나의 자원을 동기화 시키기 위한 방법
- 단독으로 실행되도록 하는 기술
ex) 화장실 한칸- semaphores
- 여러개의 자원을 동기화시켜주기 위한 방법(counting)
ex) 주차장
설명을 위해 단어 설명
P : wait function(진입을 확인하기위한 코드)
V : signal function(점유가 끝났을 때 쓰는 코드)//initial S=1 P(S): S--; while(S<=) wait; V(S); S++;여기서 S는 접근할 수 있는 resource의 수를 의미합니다.
즉 resource에 접근한다면 S-- 해서 접근 가능한 자원을 줄이고 점유가 끝났을때는 S++하여 접근 가능한 자원을 늘려줍니다.
또한, S==0일때에는 접근할 수 없습니다.
때문에 S가 양수의 경우는 사용할 자원의 개수를 의미하고, 음수의 경우에는 대기하고있는 프로세스의 수를 의미합니다.
대기하고있는 프로세스들을 어떻게 실행시킬까
Block/Wakeup Implementation
-
물론 Peterson Algorithm을 사용해서 구현할 수 있지만 Busy Waiting 문제가 발생할 수 있습니다.
-
추가적으로 busy waiting 문제를 Spin Lock 이라고 합니다.
이에 대한 해결책으로 PCB를 뒤에 매달고서 실행되고 있는 프로세스가 끝나면 다음 프로세스를 깨우는 방식을 사용합니다.
Busy Waiting과 왜 다르냐
-
매달려서 대기하고있는 프로세스들의 thread는 sleep에 들어가 자원을 소모하지 않습니다.
하지만! block/wakeup 은 잠들어 있는 애들을 깨운다 즉, running의 상태를 -> waiting으로, waiting -> ready 로 변경해주는 context-switching 비용이 발생하고 spinLock의 경우 context-switching 비용이 발생하지 않습니다.( 상태를 변경하는 것이 아닌 접근을 못하고 있는 것이기 때문 )때문에, critical section가 짧아서 프로세스 교체가 자주 발생하는 경우라면 busy waiting 기법이 더 효과적일 수 있습니다.
OS 에서 critical section 문제가 발생하는 경우
- interrupt handler와 커널 사이
- kernel에 진입할때 interrupt가 발생하면 의도한 값을 못가져올 수 있음
- 때문에 interrupt 발생하지 못하게 설정되어있음
- kernel이 system call을 수행중일 때 context-switch 발생
- 의도한 값을 못가져옴 때문에 system call에서는 무조건 대기
- Multi Processor
동기화 과정에서 발생하는 문제점
- Bounded-Buffer Problem
- Readers and Writers Problem : scheduling
- Dining-Philosophers Problem : deadlock
- 식사하는 철하자들의 문제
Bounded-Buffer : shared-memory solution
공유 데이터가 버퍼(배열)에 있고 이 자원을 여러 스레드가 공유하는 상황입니다. 이
이 데이터에 접근할 수 있는 객체를 크게 두가지로 나눈다.
- Producer : 데이터를 채우는 역할
- Consumer : 데이터를 소모하는 역할
때문에 Producer는 버퍼가 가득 차있다면 대기해야하고, Consumer는 데이터가 비어있다면 대기해야한다. 이 경우에 실행 순서에 따라 데드락 또는 starvation 이 발생할 수 잇기때문에 이를 해결하기위해서 semaphore를 사용합니다.
이 과정을 Semaphore에 적용하기위해 필요한 변수
- 비어있는 버퍼의 개수(empty)
- 차있는 버퍼의 개수(full)
- Lock(공유버퍼에 락을 걸기위해)
위 그림에서 왼쪽은 Producer, 오른쪽은 Consumer를 의미합니다. - P : 값이 0보다 같거나 작으면 대기
- V : 값을 1 증가
Producer는 비어있는 버퍼의 개수를 확인하고(1 이상이어야함) 자원을 사용한 후 pointer가 다음 buffer를 가리키게 한 후 차있는 버퍼(full)의 값을 1증가한다.
Consumer는 차있는 버퍼의 개수(full)을 확인하고 자원을 사용한 후 empty 를 1 증가한다.
작업을 수행하던 도중 interrupt가 발생해서 공유 자원이 다른 프로세스에게 넘어 갔다면 데이터가 유실될 수 있기 때문에 각각의 자원에 접근할때에는 lock을 걸어준다.
mutex를 적용했을때의 차이가 무엇일까?
semaphore의 차이는 경쟁하는 것이 2개이나 그 이상이냐 아닌가?
Readers and Writers Problem
DB와 같은 공유 데이터 세트에 대한 읽기 및 쓰기 작업과 관련한 문제입니다.
읽기 작업 : 여러 프로세스가 동시에 읽기 작업 수행이 가능합니다.
쓰기 작업 : 한번에 한 프로세스만 쓰기 작업 수행이 가능합니다.
이 두 작업을 조정하기위해 동기화가 필요합니다.
- 두 작업에게 우선순위를 부여하여서 문제를 해결할 수 있습니다.
- 하지만 이렇게 하게된다면 우선순위가 낮은 작업이 기하현상(stavation)에 빠질 수 있기 때문에 공정성을 보장하기 위한 작업이 필요합니다.
- starvation을 방지하기위한 공정성을 제공(일정 시간까지 도착한 reader만 사용가능하도록)
Dining-Philosophers Problem
여러명이 철학자들이 생각하며 식사하는 방식에서 발생하는 문제이다.
1. 각각의 철학자들의 양쪽에 있는 젓가락을 이용해서 식사하고, 식사를 마치면 젓가락을 내려놓고 생각한다.
2. 양쪽의 두개의 젓가락을 들어야만 식사가 가능하고, 한 번에 하나의 젓가락만 잡을 수 있다.
3. 옆 사람이 식사 중이면 젓가락을 잡는 것을 대기한다.
동시에 식사를 진행하게 되면 모두 왼쪽 포크를 쥐고 오른쪽 포크를 잡을 수 있을때까지 대기해야하는 교착 상태가 발생한다.
이 문제를 해결하기위한 동기화 기법은 3가지이다.
- 5명의 자리에 4명이 앉게 한다 -> 한명은 식사 가능
- 한 철학자가 양쪽의 젓가락을 잡을 수 있을때에만 젓가락을 잡을 수 있도록 허용.(즉, Crtical Section 구역에 들어와서 젓가락을 집도록)
- 비대칭 해결법 사용(특정한 철학자들의 젓가락 집는 순서를 반대로 설정한다면 데드락을 방지할 수 있다)
Semaphore의 문제점
- 구현이 복잡하다
- 정확성을 입증하기 어렵다
- 하나의 실수가 모든 시스템에 큰 영향을 미친다.
Monitor
Mutex를 추상화된 데이터로 만들어서 제공합니다. 때문에, 개발자가 직접 코드를 작성할 필요가 없습니다.
모니터(Monitor)는 동기화와 상호 배제를 위한 고수준 추상화 도구로, 여러 스레드가 공유 자원에 안전하게 접근할 수 있도록 도와줍니다.
ex) 도서관(같은 책은 한사람만 읽을 수 있도록 -> 변수를 사용해서 관리)
- 모니터 내에서는 mutext가 보장됩니다.(하나의 프로세스(스레드)만 접근 가능)
- 모니터에 진입하려는 프로세스(스레드)는 진입 큐에서 대기하여야합니다.
- 모니터 내부의 정보는 은닉되어있습니다.
- 특정 조건을 만족할때까지 대기하고 만족했을때에 먼저 모니터에 진입할 수 있게하는 조건 큐를 갖고 있습니다.
mutex와 semaphore와 같이 공유 자원 접근 제어를 제공하고, 추상화하여 프로그래밍 언어 수준에서 제공합니다. 또한, 개발자가 코드를 직접 작성할 필요가 없다는 장점이 있습니다.
