- 추후에 정리한다.
- 임계영역 문제를 다루는 여러 하드웨어 기반 해결책(TestAndSet(), Swap())이 있지만, 응용프로그래머가 사용하기에는 복잡하다.
- 이 어려움을 해결하기 위해
Semaphore가 사용된다. - 세마포어란,
- Busy Waiting 을 기다릴 필요가 없는
Synchronization tool이다. - 세마포어 S는 integer 변수이다.
- 두 개의 표준 atomic 연산으로 접근이 가능하다 wait(), signal()
- 원래 wait()는 검사하다를 의미하는 네덜란드어 Proberen에서 P라고, signal()은 증가하다를 의미하는 Verhogen에서 V라고 지어졌다.
- wait()과 signal() 연산 시 세마포어의 정수값을 변경하는 연산은 반드시
atomic하게 실행되어야 한다. - 사용하기에 덜 복잡하다.
- Busy Waiting 을 기다릴 필요가 없는
- S--; 연산과 S++; 연산은 반드시 atomic 하다.
Counting semaphore- integer 값이 제한없는 영역을 가진다. ex) 0, 1, ... ,10
Binary semaphore- interger 값이 반드시 0 또는 1이다.
- mutex locks 라고도 불린다.
- wait(mutex) : 임계영역에 들어가기 전에 mutex를 가져감으로써(0) 다른 프로그램들을 대기시키기
- signal(mutex) : 임계영역에서 빠져나올 때 mutex를 되돌려놓음으로써(1) 다른 프로그램들을 진입할 수 있도록 만들기
- 이진 세마포어로 임계영역 문제를 해결하는 방법
- n개의 프로세스가 세마포어, 즉 뮤텍스를 공유받는다.
- 뮤텍스는 1로 초기화된다.
- 예시 코드는 강의슬라이드 참조
- 한 프로세스가 임계영역 이전의 진입구간(entry section)에서 wait(sem)을 실시. 이후 임계구간 진입
- 그 동안 다른프로세스들은 기다린다. 이 때, busy waiting 대신 자기 봉쇄연산을 실행해 세마포어와 관련된 대기 큐에 넣어 스스로를 대기상태로 전환시킬 수 있다.
- 임계구간을 빠져나오는 프로세스는 탈출구간(exit section)에서 signal(sem)을 실시.
- 다른 프로세스들이 임계구간에 진입가능하게 됨. 이 때 봉쇄된 대기 큐의 프로세스들 중 하나를 CPU 스케줄러가 골라 실행시킨다.
- 임계구간 해결책의 세가지 조건을 모두 만족하는가?
- Bounded Waiting은 보장할 수 없다.
- 일반적으로 wait()의 구현방식에 달렸다.
- ex) Linux의 sem_wait()는 bounded waiting 조건을 만족하지 않는다.
- Bounded Waiting은 보장할 수 없다.
- 카운팅 세마포어는 일반적으로 유한 개의 인스턴스로 이루어진 자원에 대한 접근을 제어한다.
- 세마포어는 가용한 자원의 갯수로 초기화 된다.
- 리소스를 사용 하기위해서, 프로세스는 wait() 연산을 수행한다.
- 리소스를 방출 하기 위해서, 프로세스는 signal() 연산을 수행한다.
- 세마포어가 0이면, 모든 자원이 사용되고 있는 것이다.
- 카운팅 세마포어는 임계 영역에 여러개의 프로세스가 동시에 들어가야하는 경우를 고려해서 만들어졌다.
- 예시) 병행 수행중인 프로세스 P1, P2가 있다고 치자.
- P1은 S1을 수행하고, P2는 S2를 수행한다.
- S2는 반드시 S1이 완료된 뒤에 수행되어야한다.
- 세마포어를 사용하여 이 문제를 해결해보자.
- P1에서 S1 수행 후에 signal을 주어야지만 P2의 wait가 풀리고 S2를 실행할 수 있다.
- 동시에 두개의 프로세스가 같은 세마포어에 대해 wait() 과 signal() 연산을 수행하지 않도록 보장해야한다.
- 그러므로, wait과 signal 코드가 임계영역 내에 존재한다는 점에서 구현은 임계영역문제 가 된다.
- 이전 코드는 임계영역 구현에 있어
busy waiting을 사용했다.- 한 프로세스가 임계영역에 있다면, 나머지 프로세스들은 계속 wait code안에서 루프를 돌며 머물러있어야했다.
- 프로세스가 락을 기다리는 동안 회전하기 때문에 이런 타입의 세마포어를
spinlock이라고 부른다. - 단점
- wait()하는 동안 CPU cycle이 낭비된다.
- 가끔은 오히려 이것이 유용할 수도 있다.
- wait()와 signal()사이에 context switch가 일어나지 않는다
- 구현 코드가 짧다
- 임계영역이 짧은 시간동안만 소유된다면 busy waiting이 거의 없다
- 그러나, 응용 프로그램이 임계 영역에서 많은 시간을 보낼수도 있기 때문에 썩 좋은 해결책은 아니다.
-
busy waiting 문제를 해결하기 위해 두 개의 연산 이 사용된다.
- block() - 프로세스를 세마포어에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기상태로 전환한다.
- wakeup() - 대기 큐의 한 프로세스를 제거하고, 레디 큐로 집어넣는다.
- 만약 wait()를 수행할 때 세마포어 값이 양수가 아니라면, 프로세스는 busy waiting하는 대신 스스로를 block한다.
- signal() 연산은 대기중인 프로세스를 깨운다.
-
block()을 사용해 wait를 구현, wakeup()을 사용해 signal을 구현
- 두명 이상의 생산자와 두명 이상의 소비자
- buffer pool에 최대 N개의 아이템을 저장 가능하다.
- 세마포어를 이용한 해결책
- 세마포어
mutex- 1 로 초기화, 임계영역에 진입하기 위한 키. mutex가 없으면 생산자와 소비자가 임계영역에 동시에 접근할 위험이 있다. - 세마포어
full- 0 으로 초기화, 꽉찬 버퍼 수 - 세마포어
empty- N 으로 초기화, 비어있는 버퍼 수
- 세마포어
- 코드
- 생산자
- 버퍼풀 중 하나가 비기를 기다린다 - wait(empty)
- 임계영역에 들어가기 위한 키인 mutex를 받을 때까지 기다린다 - wait(mutex)
- 두 조건이 해결되면 아이템을 버퍼에 저장하고, mutex를 다른 프로세스가 사용할 수 있도록 풀어준 뒤 버퍼 하나에 아이템을 채웠다는 signal을 보낸다.
- 소비자
- 버퍼풀에 아이템이 하나라도 생성될 때 까지 기다린다 - wait(full)
- 임계영역에 들어가기 위한 키인 mutex를 받을 때까지 기다린다 - wait(mutex)
- 두 조건 해결시 아이템을 버퍼에서 소비하고, mutex를 다른 프로세스가 쓸 수 있도록 풀어준 뒤, 버퍼풀에 아이템을 하나 소비했다는 신호를 보낸다 - signal(empty)
- 하나의 데이터베이스(data set) 가 다수의 병행 프로세스 간에 공유된다고 가정하자.
- 독자 - 데이터베이스의 내용을 읽을수만 있고 조작하거나 갱신할 수 없다.
- 저자 - 데이터베이스의 내용을 읽을수도 있고, 갱신할 수 있다.
- 문제점
- 여러 독자 가 동시에 읽는것은 가능하다. 그러나 저자가 진입한다면 단 한명의 저자만이 동시에 공유메모리에 접근할 수있다.
- 공유 데이터
- 데이터베이스
- 세마포어
mutex: 1로 초기화, readcount 갱신시 mutual exclusion 보장 - 세마포어
wrt: 1로 초기화, reader와 writer가 모두 공유 - 정수
readcount: 0으로 초기화, 현재 몇개의 프로세스들이 객체를 읽고 있는지 알려준다.
- 코드
- 독자
- 임계영역에 진입하기 위한 mutex를 받을 때까지 기다린다
- readcount를 올리고, 만약 임계영역에 진입한 첫번째 reader라면 wrt를 잡아두어 reader가 읽고있는 내용을 writer가 갱신하지 못하도록 한다.
- mutex를 풀어주어, 다른 프로세스가 진입할 수 있도록 한다.
- 다른 reader들이 진입하여, 마지막 reader가 진입했을 경우 readcount를 내려 0으로 만들고, wrt를 풀어주어 writer가 데이터베이스의 내용을 갱신할 수 있도록 한다.
- mutex를 풀어준다.
-
저자
- 참조하는 reader가 없는지 확인하여, write할 수 있을 때 까지 기다린다 - wait(wrt)
- 임계영역에 진입하여 Writing을 수행한다
- 임계영역에서 탈출하면 Writing이 끝났음을 signal한다
-
문제
- 기아 문제가 있다.
- 저자에게 기아가 일어날 수 있다
- 저자가 이미 공유 객체를 사용하기 위한 허가를 받지 않은 이상은, 어떤 독자도 기다리지 않기 때문에 독자는 계속해서 진입하고, 저자는 계속해서 기다리게 된다.
- 독자-저자 문제의 변형
- 저자가 준비되면, 저자는 가능한 한 빨리 작성을 수행해야한다.
- 만약 저자가 객체에 접근하는것을 기다리고 있다면, 읽기를 수행할 새로운 독자가 없을수도 있다.
- 이 경우에 독자에게 기아가 일어날 수 있다
- 기아 문제가 있다.
-
중앙에 rice 가 있고, 5명의 철학자들은 thinking 또는 eating 만 할 수 있다.
-
rice : 자원 / thinking : wait / eating : 자원 사용
-
젓가락은 한 짝씩만 있어서, 자기 옆의 1개씩 2개를 집어버리면 그 옆의 사람들은 먹을 수가 없다.
-
이 경우 어떻게 dealock과 starvation을 예방하여 먹을 수 있을까?
- food에다 lock을 걸어버리면?
- resource를 사용할 수 있는 사람은 최대 2사람인데, lock을 걸면 한명밖에 사용할 수 없게 된다.
- 모두가 자기 오른쪽 젓가락을 한 짝씩만 들면?
- deadlock에 걸려 아무도 resource를 사용할 수 없다.
- food에다 lock을 걸어버리면?
-
이 문제는 많은 부류의 병행제어(concurrency-control) 문제 중 하나이다.
-
교착상태와 기아를 발생시키지 않고 여러 스레드에게 여러 자원을 할당할 필요 를 단순하게 표현한 것이다.
-
해결법
- chopstick[5]이라는 세마포어 배열을 만들어 1로 초기화한다.
- 왼쪽 젓가락(chopstick[i])이 비기를 기다렸다가 집어들고, 오른쪽 젓가락(chopstick[(i+1)%5])이 비기를 기다렸다가 집어들고, 젓가락 쌍을 얻었으니 밥을 먹은 뒤 다시 한개씩 내려놓는다(signal)
-
이 해결법은 이웃하는 두 사람이 동시에 먹을수 없음 을 보장한다.
-
그러나, 이 해결법은
deadlock을 유발할 수있다.- 5명의 철학자들이 동시에 배가고파져서 왼쪽 젓가락을 집어들었다고 가정해보자.
- 모든 젓가락을 가져간 상태이다.
- 각 철학자들이 오른쪽 젓가락을 집어드려고 시도해도, 영원히 집어들 수 없다.
-
deadlock을 해결하도록 이 해결법을 보완해보자.- 최대 4명의 철학자가 같이 앉게 한다
- 철학자들은 양쪽 젓가락이 사용가능할 때만 젓가락을 집을 수 있게 한다. 이렇게 하려면 철학자들은 모두 임계영역 안에서만 젓가락을 집어야 한다.
- 비대칭적인 해결책을 사용한다 : 홀수번째 사람들은 왼쪽 젓가락, 짝수번째 사람들은 오른쪽 젓가락을 먼저 집게 한다.
- 세마포어를 오용하지 않도록 주의해야한다.
- 오용 사례
- 먼저, 뮤텍스는 1로 초기화된 세마포어이다.
- signal(mutex) ... wait(mutex)
- 상호배제 조건을 위반한다. wait - CS - signal의 순서가 지켜지지 않으면 임계영역 안에 두개의 프로세스가 존재하게 될 수 있다.
- wait(mutex) ... wait(mutext)
- 교착상태를 유발한다
- wait(mutex)나 signal(mutex) 중 하나, 또는 둘 모두를 누락했을 경우
- 상호배제 조건을 위반하거나 교착상태가 발생한다.
- 이러한 에러들을 해결하기위하여
monitor가 사용된다.
- 프로세스 동기화를 위한 편리하고 효과적인 메커니즘을 제공하는 고레벨 추상화
- 객체지향 언어에서의 클래스같은 추상화된 자료형으로 정의된다.
- 모니터 인스턴스는 여러개의 프로세스들 간에 공유된다.
- 모니터 안에 한번에 하나의 프로세스만이 활성화 될 수 있다.
-
공유 데이터
-
연산들
- 공유데이터는 연산들에 의해서 접근될 수 있다.
-
초기화 코드
-
프로그래머는 이러한 동기화 문제를 코드로 짤 필요가 없다.
-
entry queue 내에 여러개의 프로세스가 존재하고, 한번에 한 프로세스만이 모니터로 들어가서 활성화(공유 데이터 접근)된다.