1. Spinlock
// s는 임계영역에 진입하기 위한 권한의 갯수
// P 연산
// s가 1이상이 될 때까지 대기하여 권한을 획득
void P(*s) {
while(*s <= 0);
*s -= 1;
}
// V 연산
// 획득한 권한을 반납
void V(*s) {
*s -= 1;
}
- 초기화, P, V 의 세 가지 연산을 지원
- 위 세 가지 연산은 원자적으로 수행됨을 보장한다.(수행중에 interrupt 당하지 않는다.)
- 임계영역 진입전에 P연산을, 작업 완료후 V연산을 수행하는 것으로 간단하게 상호배제를 구현할 수 있음
- 멀티프로세서 시스템에서만 사용 가능한 방식(P, V연산 실행중에는 interrupt가 발생하지 않기때문)
- Busy Waiting 문제는 여전히 해결되지 않음
2. Semaphore
// P 연산
// 세마포어 값이 1 이상이라면 권한을 획득(s -= 1)하고 임계영역에 접근
// 그렇지 않다면 대기열에 들어가 기다린다
void P(*s) {
if(s > 0)
s -= 1;
else
/* wait in ready_queue */
}
// V 연산
// 작업을 끝낸 뒤 만약 ready_queue에서 대기중인 프로세스가 있다면
// 대기중인 프로세스중 하나를 깨워 실행되도록 해준다.
// 대기중인 프로세스가 없다면 권한을 반납(s += 1)한다.
void V(*s) {
if(/* ready_queue is not empty */)
/* wake up one of waiting processes */
else
s += 1;
}
- Dijkstra 가 고안한 방식
- Spinlock 과 유사하게 초기화, P, V 연산을 지원
- 권한을 획득하지 못한 프로세스는 계속 실행되지 않고 ready_queue에 들어가 block 상태로 대기
- Busy Waiting 문제를 해결함
- 그러나 ready_queue 에서 대기중인 프로세스중 어느것을 먼저 깨울지는 비결정적(기아문제 발생할 수 있음)
- Semaphore의 종류
- Binary Semaphore
- 세마포어 값(s)이 0 또는 1 두 종류의 값만 가지는 경우
- 상호배제와 프로세스 동기화의 목적으로 사용
- 뮤텍스(mutex)가 이에 속한다
- Counting Semaphore
- 세마포어 값(s)이 0 이상의 정수값을 가지는 경우
- 생산자-소비자 문제 등의 해결을 위해 사용
- Semaphore로 해결할 수 있는 문제
- 상호배제(Mutual Exclusion)
- 임계영역 진입전에 P연산을, 작업 완료후 V연산을 수행하여 해결
- 프로세스 동기화(Process Synchronization)
- 세마포어 값을 0으로 초기화
- 먼저 수행되어야할 작업은 P연산 없이 작업을 수행 후 V연산 수행
- 나중에 수행되어야할 작업은 P연산을 수행하여 대기, 먼저 수행되어야할 작업이 완료되어
V연산이 실행되면 세마포어 값이 증가하여 작업을 수 행할 수 있게 됨
- 생산자-소비자(Producer-Cosumer)
// 생산자 프로세스
void Producer() {
while(true) {
/* produce data K */
// 버퍼의 데이터가 소비자에 의해 소비될 때 까지 대기
P(consumed)
// 소비자가 데이터를 가져가면 버퍼에 생성한 데이터를 저장
write(buffer, K)
// 데이터 생성이 완료되었음을 알림
V(produced)
}
}
// 소비자 프로세스
void Consumer() {
while(true) {
// 생산자가 데이터를 생성할 때 까지 까지 대기
P(produced)
// 생산자가 데이터를 버퍼에 저장하면 이를 읽어옴
K = read(buffer)
// 데이터가 소비되었음을 알림
V(consumed)
// 읽어온 데이터 소비
/* consume data(k) */
}
}
}
- 생산자가 데이터를 생산하기전에 소비자가 데이터를 읽으려할 때 생기는 문제
- 생산자 둘이 서로 같은 영역(버퍼 등)에 동시에 데이터를 생성, 저장하려 할 때 생기는 문제
- Single Buffer일 때 사용가능한 방법
- 버퍼가 여러개일 때의 생산자-소비자 문제
// 생산자 프로세스
void Producer() {
while(true) {
/* create data K */
// 다른 작업중인 생산자가 없을 때 까지 대기
P(mutexP)
// 비어있는 버퍼가 생길 때 까지 대기
P(nrempty)
// buffer[in]에 생성한 데이터를 저장하고 in의 위치를 한칸 이동
write(buffer[in], K)
in = (in + 1) % N
// 버퍼 하나가 채워졌음을 알림
V(nrfull)
// 생산자의 작업이 끝났음을 알림
V(mutexP)
}
}
// 소비자 프로세스
void Producer() {
while(true) {
// 다른 작업중인 소비자가 없을 때 까지 대기
P(mutexC)
// 채워진 버퍼가 생길 때 까지 대기
P(nrfull)
// buffer[out]에서 데이터를 읽어오고 out의 위치를 한칸 이동
K = read(buffer[out])
out = (out + 1) % N
// 버퍼 하나가 비워졌음을 알림
V(nrempty)
// 소비자의 작업이 끝났음을 알림
V(mutexC)
}
}
- mutexP : 생산자 뮤텍스
- mutexC : 소비자 뮤텍스
- buffer[0] ~ buffer[n-1] : n개의 버퍼
- in, out : 생산한 데이터를 넣을 위치, 데이터를 소비할 위치
- nrfull : 채워진 버퍼의 수
- nrempty : 비어있는 버퍼의 수
- 환형 큐를 사용하여 문제를 해결
- Reader-Writer
// Reader 프로세스
void Reader() {
while(true) {
/* 읽기작업 진입 전 단계 */
P(mutexR);
// 다른 Reader가 없을 경우
// Writer가 작업을 수행하지 않도록 막아둠
// 다른 Reader가 있을경우 이미 이 작업이 수행됐기에 다시 수행할 필요가 없음
if(nreaders == 0)
P(mutexW);
// Reader의 수 증가
nreaders += 1;
V(mutexR);
/* 읽기 작업 수행 */
/* 읽기작업 완료 후 단계 */
P(mutexR);
// 더이상 다른 Reader가 없을 경우
// Writer가 작업을 수행할 수 있도록 lock을 해제
// 다른 Reader가 남아있을경우 아직 lock을 해제해선 안됨
if(nreaders == 0)
V(mutexW);
// Reader의 수 감소
nreaders -= 1;
V(mutexR);
}
}
// Writer 프로세스
void Writer() {
while(true) {
// 쓰기 작업 진입
P(mutexR);
/* 쓰기 작업 수행 */
// 쓰기 작업 완료
V(mutexR);
}
}
- Writer는 동시에 작업을 수행해선 안됨(상호 배제 보장이 필요)
- Reader의 경우 기본적으로는 여러 작업이 동시에 실행되어도 문제가 없음
- Reader쪽에게 우선권을 주는 Reader Preference 와 Writer에게 우선권을 주는
Writer Preferece 두가지 방법이 있으며 위의 코드는 Reader Preference 기준의 설명
3. Eventcount / Sequencer
- 은행의 번호표와 유사한 개념을 사용한 기법
- Sequencer
- 정수형 변수 S는 지금까지 발생한 사건(실행된 프로세스)의 수를 의미(처음엔 0으로 초기화)
- ticket(S)
- 프로세스는 실행되기 전에 ticket(S) 를 호출하여 자신의 순번(번호표)을 발급받음
- ticket 연산이 수행될 때마다 S값은 1씩 증가
- Eventcount
- 정수형 변수 E는 깨워야할 차례인 사건(다음으로 실행될 프로세스)의 순번을 의미(처음엔 0으로 초기화)
- read(E)
- advance(E)
- E번에 해당하는 프로세스를 깨움(wake-up)
- E를 1 증가시켜 다음에 실행될 순번을 갱신
- await(E, V)
- V는 프로세스가 발급받은 순번
- E < V 일 경우, 즉 자신의 순번이 아직 오지 않았을 경우 E에 연결된 대기열에 프로세스를 삽입
- CPU 스케줄러에 E 값이 V가 됐을 때, 즉 자신의 순번이 왔을 때 깨워줄것을 요청
- Eventcount / Sequence 를 활용한 생산자-소비자 문제 해결
// 버퍼의 갯수는 n개
// 생산자, 소비자의 Sequencer 는 각각 Pticket, Ctikcet
// 생삱자, 소비자의 Evnetcount 는 각각 In, Out
// 생산자 프로세스
void Producer() {
int u;
while(true) {
/* create data K */
// 순번 발급
u = ticket(Pticket);
// 자신의 순번이 올 때까지 대기
await(In, u);
// 데이터를 삽입할 버퍼가 있을 때 까지 대기
// 버퍼의 총 갯수는 n개
// 버퍼가 채워진 횟수는 u개(생산자가 실행된 횟수)
// 버퍼가 비워진 횟수는 Out개(소비자가 실행된 횟수)
// 남은 버퍼의 갯수는 (n - u + Out)개
// n - u + Out > 0, 즉 Out > u - n 이어야 빈 버퍼가 존재하므로
// u - n + 1 까지 기다려야 빈 공간이 생긴다.
await(Out, u - n + 1);
// buffer[u % n]에 데이터를 저장
buffer[u % n] = K;
// 생산자의 작업이 하나 완료되었음을 알림
advance(In);
}
}
// 소비자 프로세스
void Producer() {
int v;
while(true) {
// 순번 발급
v = ticket(Cticket);
// 자신의 순번이 올 때까지 대기
await(Out, v);
// 데이터를 읽을 버프가 있을 때 까지 대기
// In 이 자신의 순번보다 크다면 채워진 버퍼가 있음
await(In, v + 1);
// buffer[v % n] 의 데이터를 읽어옴
K = buffer[v % n];
// 소비자의 작업이 하나 완료되었음을 알림
advance(Out);
}
}
- 프로세스는 대기열에서 순번을 기다리다가 스케줄러에 의해 깨어나기에 Busy Waiting 문제 없음
- Semaphore에서 대기중인 프로세스의 wake-up 순서가 비결정적이기 때문에 생길 수 있었던
기아(starvation) 문제는 발생하지 않음 => 티켓을 발급받은 순번대로 깨우기 때문
- Sequencer 를 통해 프로세스가 실행되는 순서를 컨트롤할 수 있음