📌 Synchronization의 필요성
-
2개 이상의 프로세스들이 동시에 수행되고 있을 경우, 이들은 경쟁관계 혹은 협동관계에 있든지 둘 중하나의 관계를 가진다. 프로세스를 수행하기 위해 필요한 공유자원에 접근할 때 한 프로세스가 다른 프로세스에게 영향을 주기 때문에 동기화가 필요하다.
-
여러 프로세스가 공유하는 자원의 일관성을 유지한다.
-
ex) 기차표 예매 : 한 좌석의 기차표는 하나만 존재하지만 예매하려는 사람은 여러명이다. (경쟁)
화장실 사용 : 공유자원의 수는 적은데 이를 사용하고자 하는 사용자는 매우 많은 경우. (경쟁)
교실 청소 : 일을 나누어서 해야함 / 순서도 중요함 (협동)
은행 계좌 문제 -
producer - consumber problem
: producer는 버퍼를 채우고 , consumer은 버퍼를 비운다 -
race condition
: 2개 이상 프로세스가 동작할때 오동작이 일어날 수 있는 환경
📌 Critical Section Problem
-
critical section
: 프로세스가 실행하고 있는 프로그램의 일부로, 다른 프로세스들과 공유하고 있는 데이터를 access하는 부분
: 모든 프로그램은 critical section , non-critical section 으로 나뉨. -
동기화
: events 혹은 프로세스의 수행에 관한 순서 지정을 위한 제약 사항들의 집합.
: 주어진 순차를 위한 제약 사항들을 만족 시키기 위해 프로세스 수행을 지연시키는 것.
: 원하는 결과값을 도출하도록 critical section 문제를 해결한다.
: 프로세스의 실행 순서를 원하는 대로 제어한다.
: busy wait 등과 같은 비효율성을 제거한다.
* critical section problem 해결을 위해선?
-
mutual exclusion (상호 배제)
: 공유 자원에 대한 배타적 접근 - 한 프로세스가 공유 데이터를 사용하고 있으면 그 access가 끝날때까지 기다려야함.
: 경쟁관계에 잘 쓰인다. -
progress
: critical section에서 수행되고 있는 p가 없고, 이곳에서 수행되길 원하는 p들이 존재할때, 이 중 하나라도 critical section에서 곧바로 수행되도록 보장되어야 한다. 무제한 연기되면 안된다.
:적정한 시간 내에 진입과 탈출이 일어나야 함. -
bounded waiting
: 몇번 시도하면 들어갈 수 있어야 함. / 어느 스레드라도 유한 시간 내에 진입해야 함
: starvation, deadlock 발생되면 안됨.
==> 3가지 조건을 만족하도록 동기화 알고리즘을 만들어야 한다.
1. 하나의 공유 변수 이용
: no deadlock , no starvation
: 한 프로세스가 critical section을 오랫동안 수행하지 않는다면, 상대 프로세스가 critical section을 수행할 수 없다 (no progress)
2. Dekker's algorithm
: 2개의 프로세스를 보장하는 최초의 알고리즘
: mutual exclusive, progress, bounded waiting 모두 충족
: 둘중 하나의 프로세스가 매우 빠를 경우 starvation에 대한 여지를 가지고 있음.
3. Peterson's algorithm
: Dekker's algorithm을 간결하게 만든 것
: 3가지 모두 만족
4. Bakery algorithm
: n개의 프로세스들을 대상으로 하는 알고리즘 ex) 은행
== critical section problem은 공유자원이 변경되는 동안 interrupt를 발생하지 않도록 하면 해결된다고 생각할 수 있지만, multiprocessing 환경에서는 불가능하다.
이런 환경에서 interrupt를 발생시키지 않으려면 메시지가 모든 처리기에 전달되어야 하고, 이는 상당한 시간을 소비하고 시스템 효율을 떨어뜨린다.
-> hardware 명령어를 제공하여 해결한다.
📌 Semaphore
- 0이상 정수값을 가지는 변수 / 초기값으로 음이 아닌 값을 가진다.
- atomic 하다 (동시에 변경할 수 없다.)
- P(s) : while (s<=0); s--; -> s가 0보다 크면 하나 줄임
- V(s) : s++;
- 프로세스 작업 순서를 정해줄 수 있게 된다.
1. busy - wait semaphore
: s를 계속 checking 한다 (while)
: spinlock - lock을 기다리는 동안에는 어떤 context switch를 하지 않는다.
: 멀티프로세스 시스템에서는 유용하다. (single에서는 비효율적)
2. blocked - set semaphore
: P(s) - s값이 0이상이 아니면 계속 체킹하는 것이 아니라, set에 들어간다. / s >0 이면 s--;
: V(s) - 기다리는 process들이 있는지 확인 후 , 있으면 그들 중 하나를 깨우고, 기다리는 process들이 없으면 s++;
: 거절당한 프로세스들의 순서를 모른다.
3. blocked - queue semaphore
: blcoked - set semaphore와 동일한데, suspended process들이 set이 아니라, queue(FIFO)에 들어가 기다리는 프로세스를 깨울 때 strongly fair 하다.
📚 fairness 측면에서 분류
-
strongly-fair semaphore
: blocked-queue semaphore -
weakly-fair semaphore
: busy-wait semaphore
📚 binary semaphore vs counting semaphore
: 한가지 유형의 자원이 여러개 존재하는 경우
: ex) 프린터가 5대 이면 semaphore=5
📌 cooperating processes
- V전에 P가 있으면 : 기다렸다가 V가 되면 그때 실행
- P전에 V가 있으면 : 기다리지 않고 바로 실행
- non-critical section은 병렬로 수행되지만, critical section은 직렬로 수행됨.
++ p1 V(s) , p2 P(s) 이면 뭐가 먼저 시작되던 p1->p2 순이다.
📌 semaphore의 문제점
-
deadlock
: semaphore가 2개라고 가정하면, 서로 놔주기를 바랄 때 -> 영원히 일어나지 않음.
(자료 참고) -
여러개의 공유 리소스를 사용하게 되다보면 오류를 일으키기 쉽다.
-
cooperation을 위해서 조건을 맞춘건지, mutual exclusion을 위한건지 구분이 어려움.
📌 producer-consumer problem
- 생산자는 데이터를 만들어 버퍼에 저장하고, 소비자는 버퍼에 있는 데이터를 꺼내 소비하는 프로세스
* infinite buffers (무한한 버퍼 이용)
: 버퍼가 full인지는 체크할 필요가 없다.
* 🌟 bounded buffers (버퍼의 크기가 유한)
: 버퍼에 공간이 있는가?를 체크해야함.
: semaphore를 element, spaces 2개 이용
📌 readers-writers problem
- 여러명이 읽을 수는 있지만 write는 반드시 한번에 한명만 쓸 수 있다.
- write만 P,V 동작하면 된다. read는 필요 없음.
📌🌟 Dining-philosophers problem
: fork를 semaphore로 이용한다. 식사하기 전 반드시 2개의 포크가 준비되어야 한다.
-
문제점
: 모든 철학자가 왼쪽 포크를 들었다고 가정하자. 그러면 5명의 철학자가 5개의 포크를 모두 집어든 상황이다. 그 결과, 남아있는 포크는 더 이상 없고 모든 철학자가 오른쪽 포크를 들기위해 기다리고 있다. 하지만 식사할 수 있는 철학자는 없으므로 아무도 포크를 내려놓지 않고 하염없이 기다리고 있는 deadlock 이 발생한다. -
해결 방안
- 철학자 4명만 테이블에 동시에 앉도록 한다.
- 철학자는 양쪽 포크를 모두 사용가능할 때에만 집을 수 있도록 허용한다.
- 홀수번째 철학자는 왼쪽 포크를, 짝수번째 철학자는 오른쪽 포크를 먼저 집게 한다.
📌🌟 증가와 감소를 경쟁하는 프로세스 a,b
(자료 참고)
- mutex를 semaphore로 한다.
- 만일에 프로세스 B가 고의로 V(mutex)를 빼먹는다면 어떠한 일이 발생할 것인가?
: 프로세스 b가 실행되어 P 연산 후, mutex=0 이 된다. V(mutex)가 없다면 mutex는 영원히 0 이므로 프로세스 a, b 모두 critical section에 들어갈 수 없다.
3, 4 : 자료 참고
📌 Monitors
- semaphore가 condition check 인지, cooperation 인지 헷갈리고 문제가 있으므로 고안해냄.
- P,V를 사용자가 사용하지 않음. monitor에게 시키면 알아서 동작한다.
