Software solution과 Hardware solution의 busy waiting 문제를 해결하기 위해
OS의 도움을 받는 문제해결 방식이며 가장 대중적으로 사용하는 방식이다.
Spin Lock
특별한 정수형 변수 S로 표현한다.
초기화, P(), V() 연산으로만 접근 가능하다
위 연산들은 기계어와 같이 atomic, 즉 더이상 쪼갤 수 없는 연산이다. 이는 OS가 보장한다
P(S) // S = 스핀락 변수. 물건의 갯수를 의미 P연산은 물건을 꺼내가는 연산
{
while (S <= 0) do //물건이 없다면 물건이 생길때까지 대기
endwhile;
S <- S-1; //물건이 있다면 이곳에 도착하여 물건을 꺼낸 후 나간다
}
V(S) //V연산은 물건을 집어넣는 연산
{
S <- S+1;
}
Spinlock을 사용한 ME
P연산을 통해 임계지역 진입 시 문을 잠그고, V연산을 통해 문을 열고 나간다
Spinlock은 멀티 프로세서 시스템에서만 사용 가능하다
P, V연산이 끝날때까지 다른 프로세스에게 프로세서를 넘겨주지 않는다는 것을 보장하기 때문에
P()연산이 끝나지 않고 영원히 돌게 된다. (Why? 프로세서가 하나니까)
P()연산이 while문을 사용하는 Busy waiting 방식이므로, 여전히 Busy waiting을 해결하지 못했다
Semaphore
다익스트라가 제안한 Busy Waiting문제를 해결한 방식
기다려야 하는 프로세스는 block(asleep)상태가 된다.
음이 아닌 정수형 변수 S를 사용한다 (S >= 0)
마찬가지로 초기화연산, P(), V()를 사용한다.
P: Probern(검사)
V: Verhogen(증가)
SpinLock과의 차이점은 임의의 S변수 하나에 ready queue 하나가 할당된다
Binary Semaphore
S가 0과 1 두 종류의 값만 갖는 경우.
상호배제나 프로세스 동기화의 목적으로만 사용Counting Semaphore
S가 0 이상의 정수값을 가질 수 있는 경우
Producer-Consumer 문제 등을 해결하기 위해 사용
if(S > 0)
then s <- s - 1; //물건이 있을 때 물건을 꺼내간다
else wait on the queue Qs;//물건이 없을 때 S에 할당된 레디큐에서 기다린다
일을 마쳤을때 호출.
만약 레디큐에 기다리고 있는 작업이 있다면 기다리는 작업 중 하나를 깨워 일을 시킨다
없다면 S를 +1한다
모두 쪼갤 수 없는 atomic연산이며 이는 OS가 지원한다.
전체가 한 instruction cycle에 수행된다.
Semaphore로 해결 가능한 동기화 문제들
1. 상호 배제 문제
2. 프로세스 동기화 문제
3. 생산자-소비자 문제
4. Reader-writer 문제
5. Dining Philosoper 문제
상호 배제 문제
SpinLock과 동일하나, Busy Waiting문제를 해결했다.
프로세스 동기화 문제
프로세스들은 병행적이며, 비 동기적으로 수행된다.
프로세스 Pi는 프로세스 Pj의 Lj지점이 지난 이후 수행되어야 한다고 가정해보면
프로세스 Pi는 Pj가 Lj을 통과할 때 까지 Li지점에서 대기해야 한다.
이를 세마포어로 해결 가능하다
sync라는 세마포어 변수를 하나 두고 0으로 세팅한다.
이 물건은 Pj가 들고 있다고 생각하고, V(sync)에서 반납하도록 구성한다.
Pi는 P(sync)를 통해 물건이 반납될 때까지 ready queue에서 대기한다
V(sync)에서 물건을 반납한 이후 ready queue에서 대기하는 Pi를 깨워준다
생산자-소비자 문제
Producer - Consumer problem
컴파일러, 어셈블러와 같이 데이터를 생산하는 생산자가 데이터를 생산하여 버퍼에 적재하면 소비자가 그 데이터를 가져와 소비한다.
이때 생산자가 데이터를 적재할 때 소비자가 사용하거나,
한 생산자가 데이터를 적재하는 동안 다른 생산자가 적재하는 등의 행위가 발생하지 않기 위해 동기화가 필요하다
버퍼가 1인 경우
consumed : 소비되었는지 확인 = 1
produced : 생산되었는지 확인 = 0
버퍼를 마치 임계구역처럼 한번에 한명만 들어갈 수 있도록 구성한다
생산자는 버퍼의 데이터가 소비되었는지 확인하고(버퍼가 비었는지?) 데이터를 적재하고
소비자는 버퍼의 데이터가 생산되었는지 확인하고(버퍼가 채워져있는지?) 데이터를 사용한다.
생산자가 데이터를 적재하려는데 버퍼가 차있거나, 소비자가 데이터를 사용하려는데 버퍼가 비어있다면
ready queue에서 대기. <- 반대편의 작업(생산 or 소비)이 완료되면 깨워져 작업을 재개한다
버퍼가 n인경우
생산자도 여러명, 소비자도 여러명, 버퍼도 여러개인 상황
nrfull : 채워진 버퍼의 수
nrempty : 비워진 버퍼의 수 (nrfull + nrempty = n)
mutexP :
mutexC :
buffer :
in, out: 물건을 적재할 위치, 꺼낼 위치
버퍼는 여전히 한번에 한명만 들어갈 수 있다.P(mutexP), P(mutexC)로 수행
생산자는 P(nrempty)로 공간이 있는지 검사하고, 소비자는 P(nrefull)로 데이터가 있는지 검사한다.
마찬가지로 공간이 없거나 데이터가 없으면 readyqueue에서 대기
생산자는 생산 이후 데이터를 기다리는 소비자가 있는지 검사, 있다면 깨운 후 nrfull을 +1하고 나오게 되고
소비자는 소비 이후 생산을 기다리고 있는 생산자가 있는지 검사, 있다면 깨운 후 nrempty를 +1하고 나오게 된다
Reader-Writer problem
Reader: 데이터에 대해 읽기 연산만 수행
Writer: 데이터에 대해 갱신 연산만 수행
Reader은 여러명이 한번에 사용 가능하지만 Writer은 한번에 한명만 사용 가능하다
여러명의 Writer이나, Reader와 Writer이 동시에 데이터 접근 시 상호배제(동기화)가 필요하다
해결법으로는 Reader와 Writer 사이에 우선권을 부여하는 방식이며
Reader에 우선권을 부여하는 Reader Preference Solution
Writer에 우선원을 부여하는 Writer Preference Solution가 있다
Reader Preference Solution
Writer은 한명만 쓸 수 있도록 P(wmutex)로 걸고 들어간 후 V(wmutex)로 풀고 나온다
Reader은 2단계로 나누어져있다
첫번째 단계인 읽고 쓰기위한 사전작업은 한명만 가능한데, 이를 첫번째 P(rmutex)와 V(rmutex)로 상호배제한다.
이 단계에서 현재 몇명이 읽고 있는지 확인하는 nreader변수를 체크하여,
읽고있는 사람이 없다면 P(wmutex)를 사용하여 writer가 쓸 수 없게 한다
이후 nreaders +1을 하여 읽는 사람을 한명 추가한다
이후 Perform read operations 부분에서 실제로 데이터를 읽는다
사후작업 역시 한명만 가능하므로 두번째 P(rmutex)와 V(rmutex)로 상호배제한다.
이 단계에서 nreader을 -1해주고, 이때 nreader가 0일때(내가 마지막 독자라면)
V(wmutex)를 통해 쓸 수 있게 풀어준다
이후 V(rmutex)를 통해 사전/사후작업을 풀어주고 빠져나온다
Semaphore의 한계
Semaphore queue에 대한 wake-up 순서는 비결정적이다.
wake up은 one of them. 즉 누가 먼저 깨어날지 모르므로
운이 없는 프로세스는 계속 asleep상태가 된다. (Starvation problem)
