okayoki

읽는자 쓰는자 문제

The Readers and Writers Problem

데이터베이스 접근을 모델링한다

다수의 프로세스가 데이터베이스에서 동시에 읽는것은 허용되지만, 한 프로세스가 데이터베이스를 갱신하고 있다면 다른 프로세스는 읽는 경우라도 데이터베이스에 접근할 수 없다.

이 문제를 해결하기 위해, 최초의 독자는 데이터베이스를 접근하기 위해 세마포어 db를 down한다.

뒤따라 오는 독자들은 카운트 rc를 증가시킨다. 독자가 일을 마치면 rc를 감소시키고 마지막 독자를 세마포어 db에 대해 up을 수행하여 대기중인 작가가 있으면 작가가 다음 코드로 진입할 수 있게 한다.

typedef int semaphore;
semaphore mutex = 1;		// rc에 대한 접근제어
semaphore db = 1;		// db에 대한 접근제어
int rc = 0;

void reader(void){
    while(TRUE){
    	down(&mutex);		// rc에 대한 접근제어 획득
        rc = rc+1;
        if( rc==1 ) down(&db);	// 첫번째 reader라면 db down
        up(&mutex);		// rc에 대한 접근제어 박탈
        
        read_data_base();
        
        down(&mutex);		// rc에 대한 접근제어 획득
        rc = rc-1;
        if( rc==0 ) up(&db);	// 마지막 reader가 읽고나면 db up
        up(&mutex);		// rc에 대한 접근제어 박탈
        
        use_data_read();
    }
}

void writer(void){
    while(TRUE){
    	think_up_data();
        
        down(&db);		// db에 대한 접근제어 획득
        write_data_base();	// db에 데이터 기록
        up(&db);		// db에 대한 접근제어 박탈
    }
}

이 방법에도 문제가 존재한다.

적어도 하나의 독자가 이미 존재하는 한 새로운 독자는 '언제나' 진입이 허용된다.

-> 작가는 독자가 존재하지 않을 때까지 대기하게 된다. 독자의 작업이 끝나기 전에 새로운 독자가 계속해서 도착한다면 작가는 데이터베이스에 절대 접근할 수 없게 된다.

=> 작가가 기다리는 도중 독자가 도착하면 독자는 바로 진입이 허용되는 것이 아니라, 작가 뒤에 수행되도록 대기하도록 해야 한다. -> 작가는 이미 존재하는 독자들은 대기해야 하지만, 작가 이후에 도착한 독자들은 대기하지 않아도 된다.

이 방법의 단점은 병행성이 떨어져 성능이 나빠질 수 있다는 것이다.

-> Courtois et al. 은 작가에게 우선권을 주는 해결책을 제시했다.

# 식사하는 철학자 문제

Dijkstra가 제시. dining philosopher problem.

https://ko.wikipedia.org/wiki/%EC%8B%9D%EC%82%AC%ED%95%98%EB%8A%94_%EC%B2%A0%ED%95%99%EC%9E%90%EB%93%A4_%EB%AC%B8%EC%A0%9C

#define N 5

void philosopher(int i){
	while(TRUE){
    	think();
        take_fork(i);
        take_fork((i+1)%N);
        eat();
        put_fork(i);
        put_fork((i+1)%N);
    }
}

take_fork는 지정된 포크를 사용할 수 있을 때까지 기다린다.

다섯 명의 철학자가 모두 동시에 왼쪽 포크를 집는 상황에서 아무도 오른쪽 포크를 잡을 수 없는 문제가 발생한다.

왼쪽 포크를 집고, 오른쪽 포크를 사용할 수 있는지 검사하고, 사용할 수 없으면 왼쪽 포크를 내려놓도록 코드를 수정하더라도 문제는 발생한다. 모든 철학자가 동시에 왼쪽 포크를 집고, 오른쪽 포크를 사용할 수 없음을 알고 다시 왼쪽 포크를 내려놓음을 반복하게 될 수 있다.

이런 식으로, 모든 프로그램이 무기한 계속 실행하지만 아무런 진전도 없는 경우를 기아(starvation)이라 한다.

교착상태가 기아가 없도록 하려면 think 호출 이후, 포크를 집고, 포크를 놓는 상황을 이진 세마포어로 보호해야한다.

포크를 집기 전에 철학자는 mutex를 down한다. 포크를 집은 후 철학자는 mutex를 up한다.

이 해답에는 실용적인 문제가 발생한다. 이 상황에서 한 번에 한 철학자만 식사할 수 있다. (두 명의 철학자가 식사 가능함에도 불구하고.)

state라는 배열을 사용해서 철학자가 식사 중인지, 생각하고 있는지, 포크를 집으려고 시도하는지 추적한다.

철학자는 오직 이웃이 식사중이 아닌 경우에만 식사중인 상태가 될 수 있다.(양 옆 포크를 모두 사용해야하므로)

프로그램이 철학자 한 명 당 세마포어 배열을 사용하므로 이제 필요한 포크가 사용 중이면 배고픈 철학자는 대기하게 된다.

#define N			5
#define LEFT			(i-N-1)%N		// 현재 철학자의 왼쪽 이웃
#define RIGHT			(i+1)%N			// 현재 철학자의 오른쪽 이웃

#define THINKING		0
#define HUNGRY			1
#define EATING			2

typedef int semaphore;
int state[N];						// 각 철학자의 상태 저장
semaphore mutex = 1;
semaphore s[N];						// 철학자 당 하나씩 가지는 세마포어

void philosopher(int i){
    while(TRUE){
        think();
        take_forks(i);		// 두 개의 포크를 동시에 잡을 수 없으면 대기
        eat();
        put_forks(i);		// 두 개의 포크를 동시에 놓는다.
    }
}

void take_forks(int i){
    down(&mutex);
    state[i] = HUNGRY;
    test(i);					// 두 개의 포크를 집으려고 시도한다.
    up(&mutex);
    down(&s[i]);
}

void put_forks(int i){
    down(&mutex);
    state[i] = THINKING;
    test(LEFT);				// 왼쪽, 오른쪽 이웃이 포크를 집을 수 있는 상황인지 체크
    test(RIGHT);
    up(&mutex);
}

void test(int i){
	if( state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING ){
    	// 주어진 철학자가 배가 고프고, 좌우 이웃이 식사중이 아니어야 포크를 둘 다 집을 수 있다.
    	state[i] = EATING;
        up(&s[i]);
    }
}

I/O장치와 같은 제한된 개수의 자원을 배타적으로 접근하기 위해 경쟁하는 프로세스들을 모델링하는데 유용하다.

여러 개의 프로세스들이 다수의 스레드를 가지고 있을 때 프로세스와 스레드라는 두 개의 병렬성이 존재.

이러한 시스템에서 스케줄링은 사용자 레벨 스레드 또는 커널 레벨 스레드가 지원되는지에 따라 다르다.

1. 사용자 레벨 스레드

커널은 스레드의 존재를 인식하지 못하므로 커널은 항상 하던대로 프로세스 A를 선택.

할당 시간만큼 A에게 CPU의 제어를 넘긴다.

A내부의 스레드 스케줄러는 어느 스레드를 실행시킬지 결정한다.

스레드를 다중 프로그래밍 하기 위한 클록 인터럽트가 존재하지 않으므로 이 스레드는 자신이 원하는 만큼 실행할 수 있다.

이 스레드가 프로세스에게 할당된 할당 시간을 모두 소비하면 커널은 다른 프로세스를 선택하여 실행한다.

사용자 레벨 스레드 스케줄링의 유일한 제약 : 너무 오래 실행되는 스레드를 중단시킬 수 있는 클록 인터럽트가 없다는 것.

2. 커널 레벨 스레드

커널은 어떤 스레드를 선택하여 실행한다. 커널은 스레드가 어느 프로세스에 속하는지 고려하지 않지만, 커널이 원한다면 고려할 수 있다. 스레드는 할당 시간을 부여받고 이 시간을 초과하면 강제로 중단된다.

사용자 레벨 스레드와 커널 레벨 스레드 사이의 차이 : 성능

사용자 레벨 스레드에서 스레드 문맥 교환 : 몇 개의 기계어로 수행. 빠르다.

커널 레벨 스레드에서 스레드 문맥 교환 : 메모리 맵을 바꾸고 캐시를 무효화하는 몇 배나 오래 걸리는 완전한 문맥교환

=> 동등하게 중요한 두 개의 스레드가 있고, 하나는 방금 대기하게 된 스레드와 동일한 프로세스에 속하고, 다른 하나는 다른 프로세스에 속한다면 동일한 프로세스에 존재하는 스레드로 문맥교환하는 것을 선호한다.

커널 레벨 스레드에서 한 스레드가 I/O에 대해 대기하는 경우, 이것이 해당 프로세스 전체를 중단시키지는 않는다.

사용자 레벨 스레드에서는 해당 프로세스가 중단됨.

사용자 레벨 스레드는 응용에 특화된 스레드 스케줄러를 사용할 수 있다. -> 작업 스레드가 종종 디스크 I/O를 위해 대기하는 환경에서 병렬성을 극대화시킨다.( 런타임 시스템이 모든 스레드가 무슨 일을 하는지 알 때 )

커널 레벨 스레드에서 커널은 스레드가 무슨 일을 하는지 절대 알 수 없다.