세마포어

이주희·2022년 12월 8일
0

운영체제에서 병행성을 위해 제공되는 기법
세마포어, 모니터, 메세지 전달

세마포어

두개 이상의 프로세스가 간단한 형태의 신호 이용해서 협력
신호 보내고 받기 위해 세마포어라 하는 특수 변수 사용

세마포어 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 스케줄링

처리기블록수행가능세마포어
AB,D,C1
BD,C,A0
DBC,A-1
CA,B,D0
ACB,D-1
BC,AD-2
DC,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;

0개의 댓글