운영체제에서 병행성을 위해 제공되는 기법
세마포어, 모니터, 메세지 전달
세마포어
두개 이상의 프로세스가 간단한 형태의 신호 이용해서 협력
신호 보내고 받기 위해 세마포어라 하는 특수 변수 사용
세마포어 s를 통해
- 신호 전송하기 위해서 semSignal(s) 사용
- 신호 수신하기 위해서 semWait(s) 수행
해당 신호가 전달되지 않았다면 전달될때까지 수행 보류
세가지 연산
-
초기화
음이 아닌 값으로 ( 이만큼 수의 프로세스가 사용가능하다!) -
semWait()
세마포어 값을 감소시킴 ( 사용하겠다!)
음수가 되면 semWait() 호출한 프로세스는 블록됨
음수가 아니면 계속 수행 가능 -
semSignal()
세마포어 값 증가시킴 ( 사용 다 했다!)
양수가 아니면 semWait() 연산에 의해 블록된 프로세스들을 깨움
Psudo code
struct semaphore {
int count;
queueType queue;
}
void semWait(semaphore s)
{
s.count--;
if (s.count < 0) {
요청한 프로세스를 s.queue에 연결
요청한 프로세스를 블록 상태로 전이시킴
}
}
void semSignal(semaphore s)
{
s.count++;
if (s.count <= 0) {
s.queue에 연결되어 있는 프로세스를 큐에서 제거
프로세스의 상태를 수행 가능으로 전이시키고 ready queue에 연결
}
}이진 세마포어 (binary semaphore or mutex)
보다 제한된 버전
오직 0과 1만 유지
연산
-
초기화
0이나 1로 -
semWaitB()
세마포어 값 확인
0이면 블록
1이면 값을 0으로 바꾸고 프로세스 계속 수행 -
semSignalB()
세마포어 값 증가시킴 ( 사용 다 했다!)
양수가 아니면 semWait() 연산에 의해 블록된 프로세스들을 깨움
코드
struct binary_semaphore {
enum {zero, one} value;
queueType queue;
}
void semWaitB(binary_semaphore s)
{
if (s.value == 1)
s.value = 0;
else {
요청한 프로세스를 s.queue에 연결
요청한 프로세스를 블록 상태로 전이시킴
}
}
void semSignal(binary_semaphore s)
{
if (s.queue is empty())
s.value = 1;
else {
s.queue에 연결되어 있는 프로세스를 큐에서 제거
프로세스의 상태를 수행 가능으로 전이시키고 ready queue에 연결
}
}이진 세마포어 특징
이진 세마포어 vs 카운팅 세마포어 = 범용 세마포어
범용 세마포어와 이진 세마포어 모두 블록된 프로세스 관리를 위해 큐 사용
어떤것을 먼저 깨워주나
- 선입선출
- 가장 오래 블록돼있던 프로세스 먼저 꺠워줌 -> 강성 세마포어
장점
- 기아 X
- 직관적이며 구현도 편리
- 큐 제거 순서 명시안한 세마포어 -> 약성 세마포어
강성 세마포어
예시
- 프로세스 A,B,C는 프로세스 D의 결과에 의존
- D가 데이터 생성하면 A,B,C가 소비
- 세마포어 s는 D의 생성결과가 존재하는지 여부 나타냄
- s=1이면 D가 생성한 데이터 하나
- s=-1이면 D의 데이터 생성을 기다리며 블록된 프로세스가 하나 있다는 의미
d가 생성한 하나의 데이터 있다고 가정, A 스케줄링
| 처리기 | 블록 | 수행가능 | 세마포어 |
|---|---|---|---|
| A | B,D,C | 1 | |
| B | D,C,A | 0 | |
| D | B | C,A | -1 |
| C | A,B,D | 0 | |
| A | C | B,D | -1 |
| B | C,A | D | -2 |
| D | C,A,B | -3 |
세마포어를 이용한 생산자/소비자 문제
요구조건 : 버퍼 접근이 중첩되서는 안됨
한 시점에서 생산자나 소비자 프로세스들 중 하나만 버퍼에 접근할 수 있어야 함
공유버퍼 b
in에다가 데이터 넣고
out에서 데이터 사용
out은 in보다 작을때만 데이터 사용 가능
코드
producer:
while(true){
b[in] = v;
b++;
}
consumer:
while(true){
while(in<=out)
//대기
w = b[out];
out++;
}이진 세마포어 생산자/소비자 문제
int n;
binary_semaphore s = 1;
binary_semaphore delay = 0;
void producer(){
while(true){
produce();
semWaitB(s);
//임계영역 시작
append(); //만든 데이터 달기
n++;
if(n == 1)
semSignalB(delay); // 소비자에게 버퍼 데이터 채워졌음을 알려줌
semSignalB(s);'//돌려줌
//
}
void consumer(){
while(true){
semWaitB(s);
take();
n--;
semSignalB(s);
consume();
if(n==0)
semWaitB(delay);
}
}
맨 처음 데이터 하나 있어서 가능함...
consumer에서 하나 소비하고 semWaitB(delay)걸리고
생산자가 하나 생산할 때 까지는 대기함
문제가 발생...
while loop가 한번 도는 사이에 scheduling이 발생하지 않을 것이라는 보장 없음
ex) 소비자의 semSignalB(s)와 if(n==0)사이에 생산자에게 스케줄링이 일어난다면..?
하나의 소비자라면 문제 없겠지만 여럿이라면 문제 발생함!
해결 1. 보조 변수 사용 (임계 영역 내에서)
전역 변수를 사용한다면 생산자가 짧은 시간 사이 전역변수 n 값을 바꿔 놓을 수 있으므로 지역변수에 값을 줘서 임계영역 이후 지역변수 값과 매칭한다!
void consumer(){
int m // 지역변수
semWaitB(delay);
while(true){
semWaitB(s); // 임계영역
take();
n--;
m=n;
semSignalB(s); // 끝
consume();
if(m==0) // 생산자가 n을 생산했다 하더라도 대기상태에 들어가게 된다!
semWaitB(delay);
}
}해결 2. 범용 세마포어를 사용한다
이진 세마포어의 여러 생산자 접근시 문제점이 범용이면 해결된다
n은 유효한 데이터 수
s는 임계영역 보호
semaphore n=0;
semaphore s=1;
void producer() {
while (true)
{
produce();
semWait(s); //사용 시작
append();
semSignal(s); // 사용 끝
semSignal(n); // 소비자 호출
}
}
void consumer() {
while (true)
{
semWait(n); // 대기
semWait(s); // 사용 시작
take();
semSignalB(s); // 사용 끝
consume();
}
}
void main() {
parbegin(producer, consumer);
}패턴
생산자 : 생산하고 임계영역 안에서 넣어주고 소비자 불러주고 임계영역 닫는다
소비자 : 생산자 불러줄때까지 대기하고
임계영역 열고 가져오고 임계영역 닫고 소비한다
유한 버퍼를 이용한 생산자 소비자 문제
순환 큐로 구현된 버퍼 구조
생산자 : 가득 찬 버퍼에서 데이터 추가할 때 블록
Producer
while(true){
while((in +1)%n == out){
}
b[in] = v;
in ++;
}
Consumer
while(true){
while(in<=out){}
w = b[out];
out = (out+1)%n;