[Operating System] Synchronization Tools (1)

hina·2023년 7월 10일

Operating System

목록 보기

6/9

Motivation

Process들은 concurrently하게 실행될 수 있다.
-> 언제든지 중단될 수 있으며, 완벽하게 실행 완료되지 못할 수 있다.
-> CPU나 자원을 놓고 process간에 경쟁이 이루어진다.

공유된 데이터에 대한 동시적인 접근은 데이터 불일치를 일으킬 수 있다.
데이터의 일관성을 유지하기 위해서는 협력하는 프로세스의 순서대로 실행되도록 보장하는 매커니즘이 필요하다.

Example: the consumer-producer problem

새로운 버퍼를 생성한 후, 생성자는 버퍼를 증가시키며 소비자는 버퍼를 감소시킨다.
counter = 0

producer

while (true) {
		/* produce an item in next produced */
		while (counter == BUFFER_SIZE);
			// while 문 내 활동 없음. 버퍼가 가득 차면 여기 갇힌다.
		buffer[in] = next_produced;
		in = (in + 1) % BUFFER_SIZE;
		counter++:
}

consumer

while (true) {
		while (counter == 0);
			// counter가 비면 소비할 게 없으므로 여기 갇힌다.
		next_consumed = buffer[out];
		out = (out + 1) & BUFFER_SIZE;
		counter--;
		/* consume the item in next consumed */
}

Motivation - Race Condition

counter++ 의 실제 구현

   register1 = counter 
   register1 = register1 + 1
   counter = register1

counter-- 의 실제 구현

   register2 = counter 
   register2 = register2 - 1
   counter = register2

두 함수가 동시에 실행되면 코드가 한 줄씩 각각 수행되며, context switch가 코드 한 줄마다 일어날 수 있다.
이 경우, 사용자가 원하는 결과와 다르게 나타날 수 있다. -> 데이터 불일치 문제
1. producer execute: register1 = counter (register1 = 5)
2. producer execute: register1 = register1 + 1 (register1 = 6)
3. consumer execute: register2 = counter (register2 = 5)
4. consumer execute: register2 = register2 - 1 (register2 = 4)
5. producer execute: counter = register1 (counter = 6)
6. consumer execute: counter = register2 (counter = 4)

interleaving: 어떤 명령의 흐름 속에 다른 명령, 혹은 프로세스가 섞여서 수행되는 현상

이 경쟁 상태를 막기 위해서는 특정 시간에 한 프로세스만 공유 데이터를 사용하도록 해야 한다.

Critical Section Problem

여러 프로세스가 하나의 시스템에서 동작할 때, 각 프로세스는 critical section(임계 영역)이라는 code segment를 가진다.
- 한 프로세스가 자신의 임계 영역에서 실행 중일 때, 다른 프로세스는 그 임계 영역에서 실행할 수 없다.

Code 4 section
- entry section: 임계 영역에 들어가기 위해 허락을 받기 위한 코드
- critical section: entry section에서 허가를 받아 프로세스가 들어오면 실제 연산을 수해하는 영역
- exit section: 임계 영역에서 연산이 끝난 뒤 임계영역 바깥으로 탈출한다.
- remainder section: 임계 영역과 독립적으로 연산을 수행하는 구간. 이때의 연산은 임계 영역 내부 동작에 아무런 영향을 끼치지 않는다.
  
  critical section은 하나의 프로세스만 독점해서 사용할 수 있으므로, 최대한 짧고 간결하게 작성하는 것이 좋다.

Solution to Critical Section Problem

임계 영역 문제를 해결하기 위해 보장되어야 하는 세 가지 조건
1. Mutual Exclusion (상호 배제): 한 프로세스가 임계 영역에서 실행 중일 때, 다른 프로세스는 해당 임계 영역에서 실행할 수 없다.
2. Progress (진행): critical section 안이 비어 있을 때, 들어갈 누군가를 정하는 selection이 미뤄지지 않고 바로 이루어져야 한다.
3. Bounded Waiting (한정 대기): entry section에 진입하면 제한된 시간 안에 critical section에 진입할 수 있어야 한다.
  => 이 세 가지 조건을 모두 만족해야 임계 영역 문제를 해결했다고 할 수 있다.

💡 Progress vs. Bounded Waiting
- progress: 아무도 없으면 누군가는 임계영역에 들어가야 한다. → deadlock 해결 조건
- bounded waiting: 요청하면 제한시간 내에 임계영역으로 들어가야 한다. → starvation 해결 조건
→ progress를 만족해도 bounded waiting을 만족하지 못할 수 있다.

Critical Section Handling in OS

운영체제를 구현하는 코드 (Kernel code)는 여러가지 race condition에 노출된다.
example
fork() system은 next_available_pid 를 호출한다. 이는 다음에 누군가가 fork() 하면 그때 부여할 pid를 미리 저장하고 있는 공유자원이다.

두 프로세스가 동시에 fork() 하고, 동시에 next_available_pid 에 접근하여 pid가 같은 두 자식 프로세스가 생기는 문제가 발생한다.
- Preemptive: 프로세스가 커널 모드에 진입하여 실행되는 중간에 선점되어 context switching이 일어날 수 있다.
- non-preemptive: 커널 모드에 진입한 뒤 스스로 종료할 때까지 외부 접근이 불가능하다. 당연히 race condition이 발생하지 않는 구조이지만, starvation 문제가 있고 성능이 느리다.

Peterson's Solution

임계 영역 문제를 해결하기 위한 소프트웨어 측면의 해결법
load and store와 같은 기계어 명령이 atomic하다는 가정 하에 두 개의 프로세스는 두 개의 변수를 공유한다.
int turn : 누가 임계영역에 들어갈 것인지 나타냄
bool flag[2] : true이면 critical에 들어가겠다는 request, 실행 중임을 나타낸다.

Process Pi와 Pj가 존재할 때, Pi의 알고리즘

do {
		/* entry section */
		flag[i] = true;
		turn = j;
		while (flag[j] && turn == j); << j의 차례일 경우 루프 내에서 대기

			/* critical section */

		/* exit section */
		flag[i] = false;

			/* remainder section */

} while (true);

Peterson's Solution은 3가지 조건을 증명할 수 있다.

producer & consumer with Peterson's Solution

void* producer(void* param)
{
	for (int k = 0; k < 10000; ++k)
	{
		/* entry section */
		flag[0] = true;
		turn = 1;

		while (flag[1] && turn == 1)
			;

		/* critical section */
		counter++;

		/* exit section */
		flag[0] = false;

		/* remainder section */
	}
	pthread_exit(0);
}

void* consumer(void* param)
{
	for (int k = 0; k < 10000; ++k)
	{
		/* entry section */
		flag[1] = true;
		turn = 0;

		while (flag[0] && turn == 0)
			;

		/* critical section */
		counter--;

		/* exit section */
		flag[1] = false;

		/* remainder section */
	}
	pthread_exit(0);
}

Peterson's Solution은 현대 컴퓨터 구조에서 완벽한 작동이 보장되지 않는다.
- 프로세서나 컴파일러가 최적화를 위해 읽기 및 쓰기 연산을 재배치할 수 있다. 이때, 연산의 종속성이 없다면 두 연산의 순서를 바꿔버릴 수도 있다. 이 경우, Peterson's solution은 예상대로 작동하지 않을 수 있다.

Critical Section with Disable/Enable Interrupts

간단한 해결 방법이다.
- entry section: disable_interrupt() 호출 -> 인터럽트를 막고 CPU의 점유 보장
- exit section: enable_interrupt() 호출
그러나, 이 방법은 과한 방법이다.

Hardware Instruction: test_and_set

atomic hardware instruction을 지원한다.
- atomic: 쪼개질 수 없음. 중간에 어느 것도 개입할 수 없음을 의미
- 메모리의 값을 test하고 set하는 과정을 한꺼번에 한다.

bool test_and_set (bool *target) {
	bool rv = *target;
	*target = true;
	return rv;
}
// return 값: target의 상태. return 값과 관계없이 이 함수 호출 후 target의 값은 1

Solution using test_and_set

bool 형 변수 lock을 공유한다. lock은 false로 초기화

do {
	// entry section
	while (test_and_set(&lock)) ; // do nothing
		
		/* critical section */

	// exit section
	lock = false; // critical setcion을 마치고 false로 바꾸기 전까지 다음에 들어온 것들은
								// 무한루프에 빠져 있다.
		/* remiander section */
} while (true);

test_and_set(&lock) 후 lock의 값은 항상 1이고, return 값은 original 값이므로, 처음 들어오면 바로 while문을 통과해 critical section으로 갈 수 있다.

Solution with Bounded Waiting

do {
	waiting[i] = true;
	while(waiting[i] && test_and_set(&lock)); // 처음 진입하면 바로 while 문 통과
	waiting[i] = false;

		/* critical section */

	j = (i+1) % n; // 현재 번호 뒤부터 탐색한다.
	while ((j != i) && !waiting[j]) // j가 i랑 같지 않고, j는 기다리고 있지 않으면
		j = (j+1) % n; // 다음 칸을 본다.
	if (j == i) lock = 0; // 한바퀴 다 돈 상태 -> lock을 초기화하여 들어오는 대로
												// 위의 while문 바로 통과 가능한 상태
	else waiting[j] = false; // j만 한정하여 while 문 통과 가능
	
		/* remainder section */

} while (true);