세마포어
- 하드웨어의 문제 : 바쁜 대기(busy waiting, spin waiting)
=> 1965년 Dijkstra의 세마포어 제안 - 두 개 이상의 프로세스들이 임계 영역에 대해 간단한 시그널을 통해서 협력하면서 진입할 수 있도록 하는 기법
- 시그널을 통해 진입하기 때문에 임계 영역에 진입하지 못하게 되는 프로세스는 CPU 사용을 중단하고 블록 상태에서 임계영역의 자원이 반환되도록 대기
=> 바쁜 대기의 문제 해결
세마포어 코드 및 특징
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 list에 연결 */
}
}세마포어 3가지 연산
- 세마포어 초기화
- 세마포어는 음이 아닌 값으로 초기화됨
semWait연산- 세마포어 값을 감소
- 만일 값이 음수가 되면
semWait을 호출한 프로세스는 블록됨 - 음수가 아니면 프로세스는 계속 수행될 수 있음
semSignal연산- 세마포어 값을 증가
- 만약 값이 양수가 아니면(0이거나 음수면)
semWait연산에 의해 블록된 프로세스들을 깨움
세마포어 특징
- 일반적으로 프로세스가 세마포어를 감소시키기 전까지는 그 프로세스가 블록될지 아닐지 알 수 없음
- 프로세스가 세마포어를 증가시키고 블록되어 있던 프로세스를 깨우면 이 두 프로세스 모두 수행 가능 상태가 됨
- 단일처리기 시스템에서 두 프로세스 중에 어떤 프로세스가 먼저 수행될 지 알 수 없음 - 세마포어에서 시그널을 보낼 때, 다른 프로세스가 대기 중인지 여부를 알 필요가 없음
- 블록되어 있는 프로세스의 개수는 0 또는 1일 수 있음
이진 세마포어
코드
struct binary_semaphore {
/* 0 아니면 1만의 값을 가짐 */
enum {zero, one} value;
queueType queue;
};
void semWaitB(binary_semaphore s)
{
if (s.value == one)
/* s.value가 1이면 0으로 바꾸고 나옴 => 다음에 수행 */
s.value = zero;
else{
/* s.value가 0일 때 수행 */
/* 요청한 프로세스를 s.queue에 연결 */
/* 요청한 프로세스를 블록 상태로 전이시킴 */
}
}
void semSignalB(semaphore s)
{
if(s.queue is empty())
s.value = one;
else {
/* s.queue에서 프로세스 P를 제거 */
/* 프로세스 P의 상태를 실행 가능으로 전이시키고 ready list에 연결 */
}
}연산
- 세마포어 초기화
- 이진 세마포어는 0이나 1로 초기화
semWaitB연산- 세마포어 값을 확인
- 만약 값이 0이면
semWaitB를 호출한 프로세스는 블록 - 만약 값이 1이면, 값을 0으로 변경시키고 프로세스는 계속 수행
semSignalB연산- 블록되어 있는 프로세스가 존재하는지 확인
- 블록되어 있는 프로세스가 존재할 경우 그 프로세스 깨움
- 블록되어 있는 프로세스가 존재하지 않을 경우 세마포어 값을 1로 설정
세마포어 동작 예
생산자(프로세스) : D
소비자(프로세스) : A, B, C
1. s = 1에서부터 자원이 있다고 가정하고 시작
2. A 프로세스가 자원 흭득을 위해 처음 실행
3. A프로세스가 `semWait`을 호출하면 세마포어가 0으로 감소하고 A는 자원흭득 후 수행
4. A가 자원흭득 후 수행하다가 타임아웃 되어 다시 준비 큐로 이동
5. 큐에서 B가 수행되면서 `semWait`을 호출 -> 세마포어가 1 감소
6. 감소된 세마포어는 -1로 바뀐 후 세마포어 값이 음수이기 때문에 B가 블록상태로 전이
7. D가 준비 큐에서 실행되고 자원을 만듦. 이후 임계영역을 나갈 때 `semSignal`을 호출하여 s가 0이 됨
8. s가 0이 되면서 잠자고 있던 B가 수행되고 다시 준비 큐로 들어감
9. D는 시간이 지나서(timeout) 다시 준비 큐로 들어감
10. 다음에 C를 꺼내어 실행.
11. C가 `semWait` 호출하고 세마포어는 음수 값이 되어 C가 블록 큐로 들어감
~ 중간 생략 ~
12. A,B까지 블록 큐에 들어가게 되면 s=-4이 됨
13. D가 들어오고 semSignal 호출
14. C가 준비 큐에 들어가게 되고 s는 -2가 됨
상호 배제
세마포어를 이용한 상호 배제
const int b = /* 프로세스 개수 */
semaphore s = 1;
void P(int i)
{
while (true) {
semWait(s);
/* 임계영역 */
semSignal(s);
/* 임계영역 이후 코드 */
}
}
void main()
{
parbegin (P(1), P(2), ... , P(n))
}parbegin을 통해 n개의 프로세스 실행semaphore s의 값은 1로 초기화하고 코드 실행- 무한 루프를 돌면서 임계 영역 전에서 대기하다 임계영역이 끝나면
semSignal호출
- 세마포어 락의 값은 1로 시작
- 세마포어를 흭득한다 => 락을 건다
- `semWait`을 통해 세마포어의 값 감소시키고 계속 수행
- B는 처음 세마포어의 값이 0이기 때문에 수행시킬 수 없어 세마포어의 값을 1 내리고 락을 걺
- C가 `semWait`하면 1 더 내리고 기다림
- A가 락을 해제하는 `semSignal` 호출
- B가 나와지고 세마포어 흭득 + 권한을 얻고 수행하다가 `semSignal`을 통해 락 해제
- 잠자고 있던 C를 실행하고 C가 다시 락을 걺
생산자/소비자 문제
### 생산자
생산자 :
while(true){
/* 데이터 V를 생산 */
b[in] = V;
in++;
}- 데이터에 대해서 값을 생성
- 버퍼에 값을 기록하고 버퍼의 위치를 증가시킴
소비자
소비자 :
while(true){
while(in <= out)
/* 대기 */
w = b[out]
out = ++;
/* 데이터 w를 소비 */
}- 해당 데이터를 소비
- 데이터가 있으면 계속해서 꺼내면서 소비
무한 버퍼에서 이진 세마포어를 이용한 생산자 소비자 문제 해결 방법 : 부정확한 버전
/* 생산자 소비자 프로그램 */
int n; /* 전역 변수 n => 전역변수의 비교를 통해 조정 */
binary_semaphore s = 1, delay = 0;
/* 생산자의 경우 => 무한루프를 돌면서 데이터 생성 */
void producer()
{
while (true) {
produce(); /* 데이터 생성 */
/* 버퍼의 임계 영역 설정 => s에 대해 LOCK을 만듦 */
semWaitB(s); /* 소비자의 버퍼 사용 방지 위해 버퍼 LOCK*/
append(); /* 버퍼 append */
n++;
if (n==1) semSignalB(delay); /* 소비자에게 버퍼가 채워졌음을 알림 */
semSignalB(s); /* 버퍼 UNLOCK */
}
}
/* 소비자 프로세스의 경우 => */
void consumer()
{
semWaitB(delay); /* 생산자가 생성한 것을 기다림 */
while (true) {
semWaitB(s); /* 생산자의 버퍼 사용 방지 위해 버퍼 LOCK */
take(); /* 버퍼에서 데이터 꺼내기 */
n--;
semSignalB(s); /* 버퍼 UNLOCK */
consume();
if (n==0) semWaitB(delay); /* 생산자에게 버퍼가 비워졌음을 알림 => 기다리는 상태 */
}
}
void main()
{
n = 0;
parbegin (producer, consumer); /* 생산자와 소비자 두 프로세서 모두 실행*/
}
- 실행되는 코드들의 나열
- 5-6번 라인, 9-10번 라인, 13-14번 라인에서 문맥 교환이 이루어짐
- 2-5번까지 LOCK
- s에 대해서 LOCK - 표에서 흰색 영역은 세마포어에 의해 보호되는 임계영역을 나타냄
- 11번 라인에서 n을 증가시키고 14번 라인에서 n이 0인지를 검사 -> 임계영역의 코드가 아니기 때문에 n을 뒤에서 감소시킴
- 14번 라인에서 검사가 n을 증가시키고 검사하기 때문에 해당 코드가 실행하지 않아 -만 시키기 때문에 버퍼에 존재하지 않은 데이터를 소비하게 됨
- 보호되지 않은 영역에서 n을 읽었기 때문
무한 버퍼에서 이진 세마포어를 이용한 생산자 소비자 문제 해결 방법: 정확한 버전
int n;
binary_semaphore s = 1, delay = 0;
void producer()
{
while (true) {
produce();
semWaitB(s);
append();
n++;
if (n==1) semSignalB(delay);
semSignalB(s);
}
}
void consumer()
{
int m; /* 지역변수 선언 */
semWaitB(delay);
while (true) {
semWaitB(s); /* 생산자의 버퍼 사용 방지 위해 버퍼 LOCK */
take(); /* 버퍼에서 데이터 꺼내기 */
n--;
m = n; /* 소비자의 임계영역 내에 보조변수 m 사용 */
semSignalB(s); /* 버퍼 UNLOCK */
consume();
if (m==0) semWaitB(delay); /* 생산자에게 버퍼가 비워졌음을 알림 => 기다리는 상태 */
}
}
void main()
{
n = 0;
parbegin (producer, consumer); /* 생산자와 소비자 두 프로세서 모두 실행*/
}무한 버퍼에서 범용 세마포어를 이용한 생산자 소비자 문제 해결 방법
semaphore n = 0, s = 1,
void producer()
{
while (true) {
produce(); /* 데이터 생성 */
semWaitB(s); /* s에 대해 락 걸기 */
append(); /* 큐에 넣기 */
semSignal(s)
semSignal(n); /* 데이터가 있다는 사실을 알림 */
}
}
void consumer()
{
while (true) {
semWait(n); /* semWaitB(s)와 순서가 바뀌면 교착상태가 발생할 가능성이 있음 */
semWaitB(s); /* 데이터를 꺼내기 위한 버퍼 LOCK */
take(); /* 버퍼에서 데이터 꺼내기 */
semSignalB(s); /* 버퍼 UNLOCK */
consume();
}
}
void main()
{
parbegin (producer, consumer); /* 생산자와 소비자 두 프로세서 모두 실행*/
}생산자와 소비자 문제에서 유한 크기의 원형 큐로 구현한 버퍼 구조
producer:
while (true) {
/* 데이터 V를 생산 */
while ((in + 1) % n == out)
/* 대기 */
b[in] = V;
in = (in + 1) % n;
}
consumer:
while (true) {
while(in == out)
/* 대기 */
w = b[out];
out = (out+1) % n
/* 데이터 w를 생산 */
}
- 일반적인 원형 큐 자료구조와 같이 끝까지 들어가게 되면 다시 처음으로 돌아감
- 큐의 개수가 정해져 있음
- **큐의 공간보다 넘치게 생산할 수 없음**
- 큐의 **공간을 확인하는 세마포어** 필요
유한 버퍼에서 범용 세미포어를 이용한 생산자 소비자 문제 해결 방법
/* 유한 버퍼를 사용하는 생산자 소비자 프로그램 */
const int sizeofbuffer = /* 버퍼 사이즈 */
semaphore s = 1, n = 0, e = sizeofbuffer; /* 큐에 넣을 수 있는 공간 확인용 */
void producer()
{
while (true){
produce();
semWait(e); /* e: 버퍼에서 빈 공간의 수 */
semWait(s); /* 버퍼에 대해서 LOCK */
append();
semSignal(s);
semSignal(n);
}
}
void consumer()
{
while (true) {
semWait(n);
semWait(s);
take();
semSignal(s);
semSignal(e); /* 버퍼가 비기를 기다리는 생산자 깨워주는 코드 */
consume();
}
}
void main()
{
parbegin(producer, consumer)
}세마포어 구현
Compare and Swap 명령어 이용
semWait(s)
{
/* 밑에 있는 코드들이 상호 배제를 확인하는 코드 */
while (compare_and_swap(s.flag, 0, 1) == 1)
/* 대기 */
/* 임계 영역의 진입 */
a.count--;
if (a.count < 0) {
/* 요청한 프로세스를 a.queue에 연결 */
/* 요청한 프로세스를 블록 상태로 전이시키고 s.flag를 0으로 설정 */
}
/* 임계 영역 나옴 */
s.flag = 0;
}
semSignal(s)
{
while (compare_and_swap(s.flag, 0, 1) == 1)
/* 대기 */
/* 임계 영역 진입 */
s.count++;
if (s.count <= 0) {
/* s.queue에 블록된 프로세스를 큐에서 제거 */
/* 전이시키고 준비 큐에 연결 */
}
/* 임계 영역 나옴 */
s.flag = 0;
}인터럽트 금지 이용
semWait(s)
{
인터럽트 금지;
s.count--;
if (s.count < 0) {
/* 요청한 프로세스를 s.queue에 연결 */
/* 요청한 프로세스를 블록 상태로 전이시킴(또한 인터럽트 허용) */
}
else
인터럽트 허용;
}
semSignal(s)
{
인터럽트 금지;
s.count++;
if (s.count <= 0) {
/* s.queue에 블록된 프로세스를 큐에서 제거 */
/* 전이시키고 준비 큐에 연결 */
}
인터럽트 허용;
}
문이과 통합형 인재(人災)