[Operating System] Chapter 5

이한량·2024년 4월 11일

목록 보기

5/12

1. Critical Section

동시에 실행되는 프로세스나 스레드들이 공유 자원(메모리)에 접근할 때, 한 순간에는 오직 한 개의 프로세스만 그 자원을 사용할 수 있도록 제한하는 코드 영역을 말한다. 여러 프로세스나 스레드가 동시에 같은 자원에 접근하여 변경을 시도할 때, 예측 불가능한 결과나 데이터 손상이 발생할 수 있다. Critical Section은 이를 예방하여 데이터의 일관성과 정확성을 유지한다.

Critical Section 관리는 다음과 같은 원칙이 존재한다.

1). Mutual Exclusion (상호 배제) : Critical Section는 단 하나의 프로세스만이 접근해야한다. 만약 상호 배제가 지켜지지 않으면, 실행 흐름이 프로그래머의 의도와 다르게 흘러갈 수 있으며, 데이터 손상이 발생할 수 있다.

2). Progress (진행) : Critical Section에 접근하고자 하는 프로세스가 없거나, Critical Section 내에 프로세스가 없을 때, 외부에서 대기중인 프로세스들 중 하나를 선택하여 진입시켜야한다.

3). Bounded Waiting (유한 대기) : 어떤 프로세스도 무한히 대기해서는 안된다. 즉, 크리티컬 섹션에 접근을 시도한 프로세스는 적당한 시간 내에 진입할 수 있어야한다.

Algorithms for Mutual Exclusion

1) . First attempt

/* Process 0 */
*
*
while (turn != 0) // trurn이 1일 때 while 루프문에 머물며 대기
	/* do noting */

/* Critical section */
turn = 1; // Critical section에서 빠져나왔기 때문에 프로세스 1에 진입 신호를 줌
*
*

/* Process 1 */
*
*
while (turn != 1) // trurn이 0일 때 while 루프문에 머물며 대기
	/* do noting */

/* Critical section */
turn = 0; // Critical section에서 빠져나왔기 때문에 프로세스 0에 진입 신호를 줌
*
*

이 방식의 문제점은 한 프로세스가 느리게 작동하면, 다른 프로세스도 그 속도에 맞춰야 한다. 또한, 한 프로세스가 작동에 실패하면 다른 프로세스는 영구적으로 차단된다. $\rarr$ Progress를 만족하지 못한다. (busy waiting)

	**Busy Waiting : 프로세스 또는 스레드가 특정 조건이
    충족될 때까지 계속해서 조건을 확인하는 것을 의미한다.
    해당 프로세스는 실제로 유용한 작업을 수행하지 않고,
    반복적으로 조건만을 평가한다.

2). Second attempt

/* Process 0 */
*
*
while (flag[1]) // flag[1] == true $\rarr$ 프로세스 1이 Critical Section에 진입했기 때문에 대기
	/* do noting */

flag[0] = true; // Critical section에 진입하기 전에 프로세스 1에 대기 신호를 줌
/* Critical section */
flag[0] = false; // Critical section에서 빠져나왔기 때문에 프로세스 1에 진입 신호를 줌
*
*

/* Process 1 */
*
*
while (flag[0]) // flag[0] == true $\rarr$ 프로세스 1이 Critical Section에 진입했기 때문에 대기
	/* do noting */

flag[1] = true; // Critical section에 진입하기 전에 프로세스 0에 대기 신호를 줌
/* Critical section */
flag[1] = false; // Critical section에서 빠져나왔기 때문에 프로세스 0에 진입 신호를 줌
*
*

이 방식의 문제는 두 프로세스가 동시에 크리티컬 섹션에 진입할 수 있는 상황이 존재한다. $\rarr$ Mutual Exclusion을 만족하지 못한다.

Third attempt

/* Process 0 */
*
*
flag[0] = true; // Process 0이 크리티컬 섹션에 들어가고자 하는 의사 표시

while (flag[1]) // 현재 Process 1이 크리티컬 섹션에 존재하기 때문에 대기
	/* do nothing */

/* critical section */
flag[0] = false; // 크리티컬 섹션 코드 수행 후 Process 0이 크리티컬 섹션을 빠져나왔음을 의미
*
*

/* Process 1 */
*
*
flag[1] = true; // Process 1이 크리티컬 섹션에 들어가고자 하는 의사 표시

while (flag[0]) // 현재 Process 0이 크리티컬 섹션에 존재하기 때문에 대기
	/* do nothing */

/* critical section */
flag[1] = false; // 크리티컬 섹션 코드 수행 후 Process 1이 크리티컬 섹션을 빠져나왔음을 의미
*
*

이 방식은 상호 배제를 만족하지만, 두 프로세스가 모두 자신의 flag를 true로 설정하고 while문 실행 이전에 서로의 플래그를 확인하게 되면, 두 프로세스 모두 상대방이 중요 구역에 들어갔다고 판단한다. $\rarr$ Bounded Waiting, Progress를 만족하지 못한다.

Fourth attempt

/* Process 0 */

*
*
flag[0] = true; // Process 0이 크리티컬 섹션에 들어가고자 하는 의사 표시

while (flag[1]) {
	flag[0] = false; // Process 1이 크리티컬 섹션에 들어갈 수 있는 기회를 제공함.
    /* delay */
    flag[0] = true; // Process 0이 크리티컬 섹션에 들어가고자 하는 의사 표시
}

/* critical section */
flag[0] = false; // 크리티컬 섹션 코드 수행 후 Process 0이 크리티컬 섹션을 빠져나왔음을 의미
*
*

/* Process 1 */

*
*
flag[1] = true; // Process 1이 크리티컬 섹션에 들어가고자 하는 의사 표시

while (flag[0]) {
	flag[1] = false; // Process 0이 크리티컬 섹션에 들어갈 수 있는 기회를 제공함.
    /* delay */
    flag[1] = true; // Process 1이 크리티컬 섹션에 들어갈 의사가 있음을 표시
}

/* critical section */
flag[1] = false; // 크리티컬 섹션 코드 수행 후 Process 1이 크리티컬 섹션을 빠져나왔음을 의미
*
*

이 방식은 상호 배제를 만족하지만, 두 프로세스가 서로 양보하려고만 할 때 문제가 발생한다. 즉, 둘 중 어느 한 프로세스도 크리티컬 섹션에 진입하지 못하는 상황이 발생할 수 있다. $\rarr$ Progress, Bounded Waiting을 만족하지 못한다.

Dekker's Algorithm

boolean flag [2]; // 2개의 프로세스의 크리티컬 섹션 접근 권한을 설정하기 위한 배열
int turn; // 2개의 프레세스 중 현재 어떤 프로세스가 크리티컬 섹션에 접근할 차례인지 나타내기 위한 변수

void p0() {
	while (true) {
    	flag[0] = true; // p0가 크리티컬 섹션에 진입할 의도가 있음을 나타냄
        
        while (flag [1]) { // 현재 p1도 크리티컬 섹션에 진입하고자 함
        	if (turn == 1) { // 만약 p1이 크리티컬 섹션에 들어갈 차례라면,
            	flag[0] = false; // p1이 크리티컬 섹션에 들어갈 기회를 제공함
                while (turn == 1) /* do nothing */ // turn이 종료될 때까지 p0는 대기
                flag[0] = true; // 다시 p0가 크리티컬 섹션에 진입하고자 하는 의도가 있음을 표현
            }
        }
        
        /* Critical section */
        turn = 1; // p0가 크리티컬 섹션 코드 수행을 끝내고 turn을 p1에 넘김
        flag[0] = false; // p0가 크리티컬 섹션 코드 수행을 끝내고 p1가 크리티컬 섹션에 들어갈 기회를 제공함
        
        /* remainder */
    }
}

void p1() { // 위 p0의 과정과 동일함.
	while (true) {
    	flag[1] = true;
        
        
        while (flag [0]) {
        	if (turn == 0) {
            	flag[1] = false;
                while (turn == 0) /* do nothing */
                flag[1] = true;
            }
        }
        
        /* Critical section */
        turn = 0;
        flag[1] = false;
        
        /* remainder */
    }
}

void main () {
	flag[0] = false;
    flag[1] = false;
    turn = 1; // turn의 초기값 설정. 0과 1 둘 중 어떤 것으로도 설정 할 수 있다.
    parbegin (p0, p1); // 두 프로세스중 어떤 프로세스가 먼저 실행될지는 OS의 스케줄링 알고리즘에 의해 결졍됨
}

Dekker's Algorithm은 Mutual Exclusion, Progress, Bounded Waiting을 모두 만족한다. 하지만, 데커의 알고리즘은 단 두 개의 프로세스에 대해서만 설계되었기 때문에 프로세스가 n개 이상일 때 적합한 알고리즘이 아니다. 또한 Busy Waiting 방식을 사용한 알고리즘이기 때문에 CPU 자원의 효율성이 떨어진다.

Peterson's Algorithm

boolean flag [2];
int turn;

void p0() {
	while (true) {
		flag[0] = true; // p0가 크리티컬 섹션에 들어갈 의사 표현
		turn = 1; // p1에게 크리티컬 섹션 진입 우선권 부여
		while (flag[1] && turn == 1) /* do nothing */ // 현재 p1가 크리티컬 섹션에 존재하는 것으로 판단, p0 대기
        /* critical section */
        
		flag[0] = false; // p0가 크리티컬 섹션에서 빠져나온 후 p1가 크리티컬 섹션에 진입할 기회 제공
		/* remainder */
	}
}

void p1() { // p0 과정과 동일
	while (true) {
		flag[1] = true;
		turn = 0;
		while (flag [0] && turn == 0) /* do nothing */
        /* critical section */
		flag[1] = false;
        
		/* remainder */
	}
}

void main() {
	flag[0] = false;
    flag[1] = false;
    parbegin (p0, p1);
}

Peterson's Algorithm은 한 프로세스가 반복적으로 크리티컬 섹션을 사용하고 접근을 독점하는 경우를 turn 설정을 통해 방지하므로, Mutual Exclusion, Progress, Bounded waiting을 모두 만족한다. 하지만 피터슨 알고리즘 또한 n개 이상의 프로세스의 크리티컬 섹션 문제에 적합하지 않고, Busy Waiting 방식을 사용한다.

2. Semaphore

세마포어(Semaphore)는 다중 프로세스(스레드) 사이에서 공유 자원에 대한 접근을 동기화하는 데 사용되는 변수 또는 추상 데이터 타입이다. 이는 프로그램 내에서 경쟁 상태(Race condition)를 방지하고, 데이터의 일관성을 유지하기 위해 고안되었다.

Binary Semaphore : 0 또는 1만을 값으로 가지는 세마포어. 주로 상호 배제를 목적으로 사용한다.
Counting Semaphore : 0 이상의 값을 가질 수 있는 세마포어로, 동시에 여러 프레세스(스레드)가 리소스에 접근할 수 있도록 한다. 카운팅 세마포어는 크리티컬 섹션에 접근할 수 있는 프로세스의 수를 나타낸다.

Semaphore의 연산

1). semWait : 세마포어 값을 1만큼 감소시킨다. 프로세스(스레드)가 공유 자원을 사용하려 할 때 호출된다.

	1-1). s(semaphore) > 0 : 세마포어 값을 1 감소시키고 호출한 프로세스는 계속해서 실행된다.

	1-2). s == 0 : 호출한 프로세스가 대기 상태로 전환된다.

2). semSiganl : 세마포어 값을 1만큼 증가시킨다. 프로세스(스레드)가 공유 자원의 사용을 완료했을 때 호출된다.

	2-1). s == 0 : 모든 공유 자원이 사용 중임을 의미하거나, 하나 이상의 스레드가 대기 상태라는 것을 나타낸다. siganl 연산으로 인해 대기중이던 프로세스 중 하나가 대기상태에서 깨어난다.

	2-2). s > 0 : 크리티컬 섹션에 들어갈 수 있는 프로세스가 1개 이상이라는 의미이다. 따라서 signal 연산이 일어나더라도 대기중인 스레드를 깨우는 행동은 발생하지 않는다.

3). semInit : 세마포어를 초기화 하는데 사용한다. 세마포어의 초기 값을 설정하므로 세마포어의 성격이 무엇인지 (이진 세마포어, 카운팅 세마포어) 결정할 수 있다.

Semaphore의 특징

1). 프로세스가 semWait 연산을 수행할 때, 프로세스는 세마포어의 현재 값을 알 수 없다. 만약 s == 0이라면, 프로세스는 블록될 것이다. 그러나 s > 0이라면, 프로세스는 세마포어 값을 감소시키고 계속 실행될 것이다. 이는 프로세스가 세마포어 값을 미리 예측할 수 없음을 의미한다.

2). 프로세스가 signal 연산을 수행하면, 대기중이던 프로세스 중 하나가 깨어난다. 그러나 프로세스의 실행 순서는 알 수 없다. 이는 OS 스케줄러에 의해 결정된다.

3 ). 세마포어에 signal 연산을 수행할 때, 실제로 블록된 프로세스가 깨어나게 될지, 아니면 단순히 세마포어의 값만 증가할지는 예측할 수 없다.

세마포어와 관련된 동기화 메커니즘은 복잡하고 예측 불가능성을 내재하고 있다.

Semaphore 구현

1). semaphore

struct semaphore {
	int count; // 세마포어의 현재 값을 나타냄. 이 값은 동시에 자원에 접근할 수 있는 프로세스의 수와 같다.
    queueType queue; // 대기중인 프로세스를 저장하는 큐. 세마포어의 값이 0 이하일 때, 공유 자원에 접근하려는 프로세스는 이 큐에 들어가 대기한다.
};

/* 프로세스가 자원에 접근하고자 할 때 호출한다. */
void semWait(semaphore s) {
	s.count--; // 세마포어의 값 1 감소
    
    if (s.count < 0) { // 세마포어 값이 0보다 작아지면, 이는 모든 공유 자원이 사용중임을 의미하고, 호출한 프로세스는 대기 큐에 추가된다.
    	/* place this process in s.queue */
        /* block this process */
    }
}

/* 프로세스가 자원 사용을 마치고 세마포어를 해제하고자 할 때 호출한다. */
void semSignal(semaphore s) {
	s.count++; // 세마포어의 값 1 증가
    
    if (s.count <= 0) { // 만약 count 값이 0 이하라면, 하나 이상의 프로세스가 대기중임을 의미한다. 대기 큐에서 프로세스 하나를 제거하고, 이 프로세스를 ready 리스트에 추가한다.
    	/* remove a process P form s.queue */
        /* place process P on ready list */
    }
}

2). Binary semaphore

struct binary semaphore {
	enum {zero, one} value; // 세마포어의 현재 상태를 나타내며, zero 혹은 one의 값을 가짐. one == 자원이 사용 가능함, zero == 자원이 사용중.
    queueType queue; // 대기 프로세스를 저장하는 큐
};

/* 프로세스가 세마포어를 통해 자원에 접근하고자 할 때 호출된다. */
void semWaitB(binary semaphore s) {
	if (s.value == one) // 자원이 사용 가능하다면, 자원을 사용하기 위해 value를 zero로 변경함. 이는 해당 프로세스가 자원을 사용하고 있음을 나타냄.
    	s.value = zero;
    
    else { // 만약 value가 이미 zero라면, 다른 프로세스가 자원을 사용중이라고 판단, 이 함수를 호출한 프로세스는 대기 큐에 추가됨.
    	/* place this process in s.queue */
        /* block this process */
    }
}

/* 프로세스가 자원 사용을 마치고 세마포어를 해제하고자 할 때 호출된다. */
void semSignalB(semaphore s) {
	if (s.queue is empty()) // 대기 큐가 비어있다면, value를 one으로 설정하여 자원이 사용 가능한 상태임을 표시함.
    	s.value = one;
        
    else { // 대기 큐에 프로세스가 있다면, 큐에서 프로세스를 하나 제거하고, 이 프로세스를 준비 상태로 전환하여 자원을 사용할 수 있도록 한다.
    	/* remove a process P from s.queue */
        /* place process P on ready list */
    }
}

3. Producer / Consumer

Producer / Consumer 문제.

1). 하나 이상의 생산자(Producer)가 어떤 유형의 데이터를 생성하여 버퍼에 저장한다.

2). 단일 소비자가 이 버퍼에서 항목을 한 번에 하나씩 가져간다.

3). 한번에 한 명의 주체(생산자 혹은 소비자)만 버퍼에 접근할 수 있어야 한다.

버퍼가 가득 찼을 때 생산자가 데이터를 추가하거나, 버퍼가 비어있을 때 소비자가 데이터를 가져가려고 시도하지 않도록 만들어야한다.

Program producer/consumer

1). Incorrect Solution

/* program producer/consumer */
int n; // 버퍼에 있는 항목의 수
binary_semaphore s = 1, delay = 0; // 버퍼 접근 권한을 제어하기 위한 이진 세마포어 s, 버퍼에 데이터가 있을 때 소비자가 데이터를 가져갈 수 있도록 알리기 위한 이진 세마포어 delay

void producer() {
    while (true) {
        produce(); // 데이터 생산
        semWaitB(s); // 버퍼 접근 권한을 얻는다. 만약 s의 값이 0이라면 대기, 1이라면 접근 권한을 얻는다.
        append(); // 데이터를 버퍼에 추가
        n++; // 버퍼에 있는 항목 수 증가
        
        if (n == 1) {
            semSignalB(delay); // delay의 값을 1 증가시켜, 버퍼에 데이터를 추가했음을 알린다.
        }
        semSignalB(s); // s의 값을 1 증가시킨다. 즉, 버퍼 접근 권한을 반환한다.
    }
}

void consumer() {
    semWaitB(delay); // 생산자가 버퍼에 데이터를 추가할 때까지 대기
    while (true) {
        semWaitB(s); // 버퍼 접근 권한을 얻기 위해 대기
        take(); // 버퍼에서 데이터 가져오기
        n--; // 버퍼에 있는 항목 수 감소
        semSignalB(s); // 버퍼 접근 권한 반환
        consume(); // 데이터 소비
        if (n == 0) {
            semWaitB(delay); // 버퍼에 현재 데이터가 없는 상태이므로, 버퍼에 데이터가 추가될 때까지 대기한다.
        }
    }
}

void main() {
    n = 0; // 초기 버퍼 항목 수는 0
    parbegin(producer, consumer); // 생산자와 소비자 동시 시작
}

해당 코드엔 여러가지 문제점이 있다.

이미 버퍼가 가득 차있는 경우, 데이터를 추가하면 안되지만, 생산자가 데이터를 추가하려고 시도할 수 있다. 이때 생산자는 버퍼에 공간이 생길 때까지 대기해야 하지만, 어떻게 대기해야되는지에 대한 구체적인 동작은 명시되어 있지 않다.

소비자가 실행되었을 때 버퍼에 아무 데이터도 없다면, 소비자는 바로 대기 상태에 들어간다. 이때, 만약 생산자가 어떤 이유로 작동하지 않아 버퍼에 데이터를 추가하지 않으면 소비자는 무기한 대기를 하게 된다.

공유 변수 n의 값을 잘못된 타이밍에 읽거나 수정한다면, 실행 흐름이 예측 불가능한 방향으로 흘러갈 수 있다.

2). Correct Solution

/* Program boundedbuffer */
const int sizeofbuffer = /* buffer size */;

/* s : 상호 배제를 위한 세마포어이다.
   n : 버퍼에 현재 들어 있는 항목의 수를 나타내는 세마포어.
   e : 버퍼에 남아 있는 빈 공간의 수를 나타내는 세마포어. */
smaphore s = 1, n = 0, e = sizeofbuffer;

void producer() {
	while (true) {
    	produce(); // 데이터 생산
        semWait(e); // e > 0이라면, 생산자는 버퍼에 빈 공간이 있는 것으로 판단한다. (e--)
        semWait(s); // 현재 버퍼에 접근해있는 다른 스레드가 있는지 확인한다. s > 0이라면, 생산자는 현재 버퍼에 접근할 수 있다. (s--)
        append(); // 버퍼에 데이터를 추가한다.
        semSignal(s); // 버퍼 접근을 완료했다는 것을 의미. (s++) 소비자 스레드가 버퍼에 접근할 권한을 제공한다.
        semSignal(n); // 버퍼에 데이터를 추가했으므로 소비자가 항목을 가져갈 수 있음을 의미한다. (n++)
    }
}

void consumer() {
	while (true) {
    	semWait(n); // 버퍼에 남아있는 항목의 수를 확인한다. n > 0이라면 버퍼에 꺼낼 수 있는 항목이 있다고 판단한다. (n--)
        semWait(s); // 버퍼 접근 권한을 기다린다. (s--) s > 0이라면, 소비자는 현재 버퍼에 접근할 수 있다.
        take(); // 버퍼에서 항목을 꺼내온다.
        semSignal(s); // 버퍼 접근을 완료했다는 것을 의미. (s++) 생산자 스레드가 버퍼에 접근할 권한을 제공한다.
        semSignal(e); // 버퍼에서 항목을 가져왔기 때문에, 버퍼에 빈 공간이 생겼음을 의미한다. (e++)
        consume(); // 데이터 소비
    }
}

void main() {
	parbegin(producer, consumer);
}

만약 위 코드의 생산자 함수에서 semWait(e) 함수와 semWait(s) 함수의 순서를 바꾸면 어떻게 될까?

1). 원래 순서

1-1). 생산자 함수 실행
1-2). semWait(e) 호출 : 버퍼에 빈 공간이 있는지 확인
1-3). semWait(s) 호출 : 버퍼 접근 권한 획득

이 순서로 인해 생산자는 버퍼가 가득 차있을 때 버퍼에 접근할 권한을 얻으려고 시도하지 않는다.

2). 순서 변경

2-1). 생산자 함수 실행
2-2). semWait(s) 호출 : 버퍼 접근 권한 획득
2-3). semWait(e) 호출 : 버퍼에 빈 공간이 있는지 확인

순서를 변경하면, 생산자는 버퍼가 가득 차있을 때 다른 스레드가 버퍼에 대해 접근할 권한을 불필요하게 차단한다.

모든 생산자가 버퍼 접근 권한을 얻고, semWait(e)를 기다리는 상황을 가정해보자. 모든 생산자들은 리소스 s를 획득한채로 리소스 e를 기다리는 상태 (Deadlcok)에 빠지게 된다. 따라서 소비자 스레드가 버퍼에서 데이터를 가져와 버퍼에 공간을 만들 기회가 없다.

이한량

한량 극복 프로젝트

이전 포스트

[Operating System] Chapter 4

다음 포스트

[Operating System] Chapter 5