Peterson의 해법과 TSL, XCHG를 사용한 해결책 모두 문제를 해결하지만 바쁜 대기를 필요로 한다는 단점이 있다.
* 우선순위 역전 문제(priority inversion problem)
높은 우선순위를 가진 프로세스 H, 낮은 우선순위를 가진 프로세스 L이 있다. 특정 순간에 L이 임계구역에 진입하고 나서 H가 실행이 가능한 준비 상태가 되어 H가 수행되면서 임계구역에 진입하기 위해 바쁜 대기를 수행한다. H가 수행중이므로 L은 스케줄 되지 않아서 임계구역을 빠져나올 수 없다. 따라서 H는 무한루프에 빠진다.
#슬립과 깨움
sleep : 호출자를 블록 상태로 만드는 시스템 호출. 다른 프로세스가 호출자를 깨워줄 때까지 블록 상태에 머문다.
wakeup : 깨울 프로세스를 가리키는 인자 하나를 가지고 있다.
* 생산자 소비자 문제
생산자와 소비자 두 프로세스가 고정된 크기의 버퍼를 공유한다.
생산자 : 정보를 버퍼에 저장
소비자 : 버퍼에서 정보를 꺼내온다
생산자가 새로운 아이템을 버퍼에 넣으려고 하는데 버퍼가 가득 차 있을 때 문제 발생
-> 생산자가 잠들고 소비자가 아이템을 하나 제거할 때 생산자를 깨워준다.
소비자가 아이템을 버퍼에서 가져오려는데 버퍼가 비어있을 때 문제 발생
-> 소비자는 잠들고 생산자가 버퍼에 아이템을 넣을 때 소비자를 깨워준다.
#define N 100
int count = 0; // 버퍼 내 아이템의 개수
void producer(void){
int item;
while(TRUE){
item = produce_item();
if(count==N) sleep(); // 버퍼에 아이템 가득차있으면 sleep
insert_item(item); // 버퍼에 아이템을 삽입
count = count+1;
if( count==1 ) wakeup(customer); // 아이템이 하나 있으면 소비자 깨움
}
}
void customer(void){
int item;
while(TRUE){
if( count==0 ) sleep(); // 버퍼에 아이템이 없으면 sleep
item = remove_item(); // 버퍼에서 아이템 꺼냄
count = count-1;
if( count==N-1 ) wakeup(producer); // 버퍼에 빈 공간 생기면 생산자 깨움
consume_item(item);
}
}! count에 대한 접근에 제한이 없기 때문에 경쟁조건이 발생한다.
ex) 버퍼가 비어있고, 소비자가 count값을 읽어서 0임을 알았다. 이 순간 스케줄러는 소비자의 '수행을 중지'시키고 생산자를 수행하기 시작한다. 생산자는 아이템을 버퍼에 추가하고 count를 증가시켜 1이 되었다. 이전에 count값이 0이었으므로 생산자는 소비자가 sleep상태일 것이라고 생각하여 wakeup(consumer)를 실행한다.
불행하게도 소비자는 아직 잠든 상태가 아니므로 wakeup(customer)실행 이후에 소비자의 sleep()이 실행되어 wakeup시그널이 사라지고 소비자는 영원히 잠들게 된다. 소비자 프로세스의 수행이 없으므로 생산자에 의해 버퍼가 가득차게 되어 생산자도 잠들게 된다.
이 문제의 본질은 아직 잠들지 않은 프로세스에 wakeup 시그널을 전송하면 소실된다는 것이다.
wakeup 시그널 소실을 막기 위해 wakeup waiting 비트를 추가하여 응급처치를 할 수 있지만 근본적인 문제는 남아있다.
# 세마포어
E.W. Dijkstra가 제안한 개념. 정수 변수를 사용하여 미래를 위해 미리 호출한 wakeup 회수를 저장할 것을 제안함.
세마포어(semaphore) : wakeup이 저장되지 않은 0값 또는 하나 이상의 wakeup이 대기 중인 양수 값을 가질 수 있다.
sleep과 wakeup을 일반화 한 down연산과 up연산
down 연산 : 값이 0보다 큰지를 검사한다. 0보다 크면 이 값을 감소시키고(저장된 wakeup 하나 소비) 수행을 계속한다. 만약 이 값이 0이면 프로세스는 down의 수행을 완료하지 않고 즉시 잠들게 된다.
up 연산 : 세마포어의 값을 증가시킨다. 하나 또는 그 이상의 프로세스가 down연산을 완료할 수 없어서 세마포어에서 잠들어있으면 이 중 한 프로세스가 시스템에 의해 선택되여 down 수행을 완료할 수 있다. 프로세스가 잠들어있는 세마포어에 대해 up을 수행하면 세마포어 값은 여전히 0이지만 잠들어 있는 프로세스의 개수는 하나가 감소한다.
-값을 검사하고, 변경하고, 경우에 따라 잠드는 이러한 모든 동작들은 분할할 수 없는 하나의 원자적 행위(atomic action).
세마포어 연산이 시작되면 원자성이 보장되어야 한다. 이 연산이 완료되거나 프로세스가 잠들 때까지 다른 프로세스가 세마포어에 접근할 수 없도록 보장되어야 한다. 원자성은 동기화 문제를 해결하고 경쟁조건 방지를 위해 꼭 필요하다.
* 세마포어를 이용한 생산자-소비자 문제의 해결
#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore full = 0;
semaphore empty = N;
void producer(void){
int item;
while(TRUE){
item = produce_item();
down(&empty); // 버퍼의 빈 자리수--
down(&mutex); // 임계구역에 진입
insert_item(item); // 버퍼에 아이템 삽입
up(&mutex); // 임계구역에서 나옴
up(&full); // 아이템의 개수++
}
}
void consumer(void){
int item;
while(TRUE){
down(&full); // 아이템의 개수--
down(&mutex); // 임계구역 진입
item = remove_item(); // 버퍼에서 아이템 꺼냄
up(&mutex); // 임계구역에서 나옴
up(&empty); // 버퍼의 빈 자리수++
consume_item(item);
}
}세 개의 세마포어 full, empty, mutex를 사용한다.
full : 아이템으로 채워진 슬롯의 개수. 0으로 초기화됨
empty : 빈 슬롯의 개수. 버퍼에 있는 슬롯의 개수로 초기화됨.
mutex : 생산자와 소비자가 동시에 버퍼에 접근하지 못하도록 한다. 1로 초기화됨.
각 프로세스가 임계구역에 진입할 때 down을 수행하고 임계구역을 나오면서 up을 부르면 상호배제가 이루어진다.
Mutex 세마포어는 상호배제를 위해 사용되었다. 한 번에 하나의 프로세스만 버퍼나 관련된 변수를 읽고 쓰도록 보장하는 용도로 사용된다.
Full과 empty세마포어는 동기화(Synchronization)를 위해 사용되었다. 특정 이벤트 순서들이 발생하거나 발생하지 않도록 보장하기 위해 필요하다. ex) 버퍼가 가득 찬 경우 생산자가 정지하도록 하는 것, 버퍼가 빈 경우 소비자가 정지하도록 하는 것을 보장한다.
# 뮤텍스
세마포어의 개수를 세는 능력이 필요 없는 경우 이진 세마포어의 일종인 뮤텍스(mutex)를 사용한다.
공유 자원이나 코드 일부분에 대해 상호배제를 해야 하는 경우 뮤텍스를 사용.
뮤텍스는 unlock(언락)(0), lock(락)(0이 아닌 다른 값) 두 가지 중 한 상태를 가진다.
뮤텍스와 함께 사용되는 두 개의 프로시듀어 mutex_lock, mutex_unlock
mutex_lock : 스레드/프로세스가 임계구역에 접근할 때 호출.
뮤텍스가 현재 언락이면 호출 성공, 임계구역에 진입 가능
뮤텍스가 이미 락 상태이면 스레드는 임계구역에 있는 스레드가 수행을 마치고 mutex_unlock 호출할 때까지 블록된다.
mutex_lock:
TSL REGISTER, MUTEX // MUTEX값 레지스터에 복사, MUTEX 1로 설정
CMP REGISTER, #0 // 이전 MUTEX 값 0인지 비교.
JZE ok // 이전 MUTEX 값 0이었으면 임계구역 진입
CALL thread_yield // 임계구역에 진입하지 못하면 다른 스레드에게 cpu 양보
JMP mutex_lock
ok: RET
mutex_unlock:
MOVE MUTEX, #0
RETmutex_lock은 락을 획득하지 못하면 thread_yield를 호출하여 다른 스레드에게 cpu를 양보한다. => 바쁜 대기 존재x
mutex_lock과 mutex_unlock 모두 커널을 호출하지 않는다.
* Pthread에서 뮤텍스
Pthread는 스레드를 동기화하기 위해 사용할 수 있는 다수의 함수들을 제공한다.
| Thread Call | Description |
| Pthread_mutex_init | 뮤텍스 생성 |
| Pthread_mutex_destroy | 뮤텍스 파괴 |
| Pthread_mutex_lock | 락 설정, 이미 설정되어있으면 대기 |
| Pthread_mutex_trylock | 락 설정, 이미 락이 설정되어있으면 오류코드와 함께 복귀 |
| Pthread_mutex_unlock | 뮤텍스 언락 |
Pthread는 뮤텍스 이외에도 '조건변수'라는 또 다른 동기화 기법 제공.
조건변수는 어떤 조건이 만족되지 않으면 스레드의 수행을 대기시킨다.
| Thread Call | Description |
| Pthread_cond_init | 조건변수 생성 |
| Pthread_cond_destroy | 조건변수 파괴 |
| Pthread_cond_wait | 다른 스레드가 시그널 보낼때까지 블록(대기한다) |
| Pthread_cond_signal | 다른 스레드에 시그널 보내서 깨운다. |
| Pthread_cond_broadcast | 다수의 스레드에 시그널 보내서 깨운다 |
조건 변수와 뮤텍스는 항상 같이 사용된다.
ex) 어떤 스레드가 뮤텍스를 락하고 자신이 필요한 무엇인가가 만족될 떄까지 조건변수에서 대기한다.
! 조건변수는 과거를 기억해두지 않는다. 블록된 스레드가 없는 조건 변수에 대해 시그널을 보내면 이 시그널은 그냥 사라진다.
#include <stdio.h>
#include <pthread.h>
#define MAX 1000000000
pthread_mutex_t the_mutex;
pthread_cond_t condc, condp; //소비자, 생산자 조건변수
int buffer=0;
void *producer(void *ptr){
int i;
for(i=1; i<=MAX; i++){
pthread_mutex_lock(&the_mutex); // 버퍼 접근 상호배제를 위해
while(buffer!=0)
pthread_cond_wait(&condp, &the_mutex); // 소비자가 아이템 소비할때까지 대기
buffer=i; // 버퍼에 아이템 삽입
pthread_cond_signal(&condc); // 소비자 깨움
pthread_mutex_unlock(&the_mutex);
}
pthread_exit(0);
}
void *consumer(void *ptr){
int i;
for(i=1; i<=MAX; i++){
pthread_mutex_lock(&the_mutex); // 버퍼 접근 상호배제를 위해
while(buffer==0)
pthread_cond_wait(&condc, &the_mutex); // 생산자가 아이템 생산할때까지 대기
buffer=0; // 버퍼에서 아이템 꺼냄
pthread_cond_signal(&condp); // 생산자 깨움
pthread_mutex_unlock(&the_mutex);
}
pthread_exit(0);
}
int main(int argc, char**argv){
pthread_t pro, con;
pthread_mutex_init(&the_mutex, 0);
//조건변수 생성
pthread_cond_init(&condc, 0);
pthread_cond_init(&condp, 0);
//새로운 스레드 생성
pthread_create(&con, 0, consumer, 0);
pthread_create(&pro, 0, producer, 0);
pthread_join(pro, 0); // producer 스레드 끝날때까지 대기
pthread_join(con, 0); // consumer 스레드 끝날때까지 대기
//조건변수 파괴
pthread_cond_destroy(&condc);
pthread_cond_destroy(&condp);
pthread_mutex_destroy(&the_mutex);
}
#모니터
모니터(Monitor) -> 단 하나의 프로세스만 한 순간에 모니터에서 활동할 수 있다.
프로세스가 모니터 프로시듀어를 호출하면 프로시듀어의 최초 명령 몇 개가 다른 프로세스가 이미 모니터에서 활동 중인지를 검사한다. 만약 다른 프로세스가 모니터에서 활동 중이라면 호출한 프로세스는 다른 프로세스가 모니터에서 나올 때까지 중단(suspend)된다.
임계구역을 모두 모니터의 프로시듀어 형태로 만들면 동시에 두 개의 프로세스가 임계구역에서 실행할 수 없다는 것만 이해하는 것으로 상호배제를 달성할 수 있다.
모니터 + 조건변수 + 연산(wait, signal) => 프로세스가 진행할 수 없을 때 대기할 수 있는 방법 구현
모니터 프로시듀어가 더 이상 진행할 수 없음을 인식하면 어떤 조건 변수에 대해 wait를 수행한다. 이 때 호출한 프로세스를 대기하게 만들고, 현재 모니터 진입을 금지당하고 있는 다른 프로세스가 모니터에 진입할 수 있게 만든다.
두 개의 프로세스가 모니터에서 동시에 활동하는 것을 피하기 위해 signal 이후에 어떻게 수행할지에 대한 규칙
1. Hoare : 기존 프로세스를 중단시키고 새로 깨어난 프로세스가 수행되어야 함
2. Brinh Hansen : signal을 수행한 프로세스는 즉시 모니터를 나간다.
3. 제 3의 해법 : signal을 보낸 프로세스가 계속 수행하도록 하고 이 프로세스가 모니터를 빠져나간 후 대기 중에 깨어난 프로세스가 실행하도록 한다.
monitor ProducerConsumer
condition full, empty;
integer count;
procedure insert(item:integer);
begin
if count=N then wait(full); //signal(full) 올때까지 대기(블록)
insert_item(item);
count:=count+1;
if count=1 then signal(empty); //소비자 깨움
end;
function remove:integer;
begin
if count=0 then wait(empty); //signal(empty) 올때까지 대기(블록)
remove = remove_item;
count:=count-1;
if count=N-1 then signal(full); //생산자 깨움
end;
count:=0;
end monitor;
procedure producer;
begin
while true do
begin
item = produce_item;
ProducerConsumer.insert(item);
end
end;
procedure consumer;
begin
while true do
begin
item = ProducerConsumer.remove;
consume_item(item);
end
end;
'computerScience > 운영체제' 카테고리의 다른 글
| 스케줄링 알고리즘의 분류 (0) | 2019.11.28 |
|---|---|
| 스케줄링 알고리즘 (0) | 2019.11.27 |
| 메시지 패싱, 장벽 (0) | 2019.11.27 |
| 경쟁조건, 상호배제 (0) | 2019.11.25 |
| 프로세스 관리_1 (0) | 2019.11.18 |