OS_08_1_Synchronization

1. Why Synchronization?

1) Why synchronization?

• cooperating process나 thread를 사용하는 이유
  • resources를 공유하기를 원한다.
  • 일을 빠르게 하기를 원한다.
  • moule방식으로 시스템을 구성하기 위해서
• 하지만, 동시에 shared resources에 접근하는 것은 잘못된 결과로 이어질 수 있다.
  • Program의 state와 output은 process나 thread의 실행 순서에 따라서 달라질 수 있다.

2) Revisiting the Bounded Buffer

item nextProduced;

while(1){
	while(((in+1) % BUFFER_SIZE) == out)
		; /* do nothing */
	buffer[in] = nextProduced;
	in = (in + 1) % BUFFER_SIZE;
}

item nextConsumed;

while(1){
	while (in == out)
		; /* do nothing */
	nextConsumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
}

• 현재의 해결책은 Buffer N개 중 N-1개만을 사용하도록 한다.
• N개의 buffer을 모두 사용하는 더 나은 해결책.
  • 새로운 counter 변수를 사용, 처음엔 0으로 초기화 되어 있는데 새로운 item이 buffer에 추가될 때마다 1씩 증가한다.

3) Bounded Buffer Using a Counter

• Shared buffer using a counter

#define BUFFER_SIZE 10
Typedef struct{
	...
}item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int count = 0;

• in : points to the next free position
• out : points to the first full position

item nextProduced;

while(1){
	while(count == BUFFER_SIZE)
		; /* do nothing */
	buffer[in] = nextProduced;
	in = (in + 1) % BUFFER_SIZE;
	count++;
}

item nextConsumed;

while(1){
	while (count == 0)
		; /* do nothing */
	nextConsumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	count--;
}

• count++, count—는 atomic하게 수행된다.
• atomic operation의 의미는 해당 operation이 interruption 없이 완료된다는 뜻이다.
• ‘count++’를 machine language로 표현하면
  • register1 = count
  • register1 = register1 + 1
  • count = register1
• ‘count—’를 machine language로 표현하면
  • register2 = count
  • register2 = register2 -1
  • count = register2
• 만약 producer와 consumer둘 모두, 동시에 buffer를 업데이트 하려고 시도한다면 assembly language statements가 끼워넣어진다. (interleaved)
• 해당 interleaving은 producer와 consumer process들이 어떻게 schduling 되는지에 따라 다르다.

a) 1st example

• count가 초기에 5이며, interleaving한 경우를 가정

procucer: register1 = count (register1 = 5)
producer: register1 = register1 + 1 (register1 = 6)
consumer: register2 = count (register2 = 5)
consumer: register2 = register2 -1 (register2 = 4)
consumer: count = register2 (count = 4)
producer: count = register1 (count = 6)

• 즉 count의 값은 4또는 6이기에(counsumer가 먼저 종료되면 4, producer가 먼저 종료되면 6), 옳은 값인 5가 아니다.

2. The Critical-Section Problem

1) Race Condition

• Race condition : 여러 프로세스가 shared resource에 동시에 접근하고 수정하는 상황이다.
  • result는 어떤 process가 마지막에 끝나느냐에 따라 다르다.
• race condition을 막기위해, 동시적인 process들은 synchronize 되어야한다.

2) The Critical-Section Problem

• n processe들이 shared resource를 사용하기 위해 경쟁한다.
• 각 process들은 code segment(called critical section)을 가지며, 해당 부분이 접근되어지는 shared resource이다.
• Problem - 어떤 하나의 process가 critical section에 진입했다면, 다른 프로세스 중 아무것도 critical section에 접근하지 못하도록 하여야한다.

3) Requirements for Critical-Section Problem

• 세 가지 요구사항
  • Mutual Exclusion : process A가 critical section에서 실행된다면, 다른 모든 process들은 critical section에 들어갈 수 없다.
  • Progress : critical section에서 실행되고 있는 process가 없다면, 다른 process가 접근할 수 있도록 한다.
  • Bounded Waiting : 어떤 process라도 waiting상태라면 유한 시간 내에는 꼭 critical section에 들어가도록 한다. 즉, critical section 진입 횟수에 한계를 두어 동일한 프로세스가 계속 독점하여 사용할 수 없도록 한다.

4) Typical Approaches to Synchronization

• 일반적으로 process는 다음과 같은 구조를 가진다.

do{
	//entry section
	critical section
	//exit section
	remainder section
} while(1);

• process들은 자신의 action을 동기화 시키기 위해서 공유되는 common variable을 가진다.

3. Synchronization Algorithms

1) Algorithm 1

• Use a shared variable per process
  • boolean flag[2];
    • initially flag[0] = flag[1] = false.
  • flag[i] = ture → Pi ready to enter its critical section

do{
	flag[i] = true;
	while (flag[j]); // 상대방이 true라면 기다린다.
		critical section
	flag[i] = false;
		remainder section
} while (1);

• mutual exclusion을 만족하지만, progress는 만족하지 않는다.
  • Two-process deadlock (두개가 동시에 실행된다면 두 process 모두 true)
  • 두 프로세스의 정확한 timing에 따라 결과가 다름.

2) Algorithm 2

• Shared variables by two processes i and j
  • int turn;
    • initially turn 0
  • turn - i → P1 can enter its cirtical section (assume i = 0, j = 1)
    • 0일때, P0이 들어가고 1일때, P1이 들어간다.
• Process Pi

do{
	while (turn != i);
		critical section
	turn = j;
		remainder section
} while (1);

• mutual exclusion은 만족하지만 progress는 만족하지 않음. 예를 들어 Pi의 remainder section 수행 시간이 매우 길어서 여전히 remainder section에서 수행 중이고, Pj가 수행을 한번 마치고 다시 Critical Section으로 진입하려고 한다면 turn == i이기 때문에 진입할 수 없다. 따라서 Critical Section에 아무런 프로세스가 존재하지 않게 된다
  

3) Algorithm 3 (Peterson’s Algorithm)

• Combined shared variables of algorithms 1 and 2
• Process Pi

do{
	flag[i] = true;
	trun = j;
	while (flag[j] and turn == j);
		critical section
	flag[i] = false;
		remainder section
} while(1);

• 세 개의 요구사항 모두 만족한다. Pi 프로세스에 대해서, Pi는 flag[i] = true로 바꾸면서 Critical Section에 진입하려고 한다. 그리고 turn = j로 바꿔주면서 상대방이 들어가게 한다. 만약 상대방이 들어가고 싶고 (flag[j] == true), 현재 상대방이 Critical Section에 들어가 있으면 (turn == j) 기다린다. 그렇지 않으면 Pi가 들어간다. 그리고나서 Critical Section을 빠져나오면 들어가고 싶지 않다고 flag[i] = false로 바꿔준다. 이 방식으로는 Mutual Exclusion, Progress, Bounded waiting 모두 만족한다. 하지만, Critical Section 진입을 기다리면서 계속 CPU와 메모리를 사용하는 Busy Waiting의 문제점이 있다.
  

4) Example

item nextProduced;

while(1){
	while(count == BUFFER_SIZE)
		; /* do nothing */
	buffer[in] = nextProduced;
	in = (in + 1) % BUFFER_SIZE;
	flag[0] = true;
	turn = 1;
	while (flag[1] and turn == 1);
	count++; //critical section
	flag[0] = false;
}

item nextConsumed;

while(1){
	while (count == 0)
		; /* do nothing */
	nextConsumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	flag[1] = true;
	turn = 0;
	while (flag[0] and turn == 0);
	count--; //critical section
	flag[1] = false;
}

item nextProduced;

while(1){
	flag[0] = true;
	turn = 1;
	while (flag[1] and turn == 1);
	while(count == BUFFER_SIZE)
		; /* do nothing */
	buffer[in] = nextProduced;
	in = (in + 1) % BUFFER_SIZE;
	count++;
	flag[0] = false;
}

item nextConsumed;

while(1){
	flag[1] = true;
	turn = 0;
	while (flag[0] and turn == 0);
	while (count == 0)
		; /* do nothing */
	nextConsumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	count--;
	flag[1] = false;
}

• entire code를 보호할 수 있지만, longer waiting을 야기한다 (blocking)

5) Bakery Algorithm by Lamport

• critical section에 들어가기전에 process는 번호를 할당받는다. 가장 작은 number를 가지고 있는 process가 critical section에 들어간다.
• Pi, Pj가 같은 number을 할당 받고, i<j라면 Pi가 먼저 들어간다.
• 각각의 연속적인 번호는 이전 번호보다 크다. 예를 들어, 1, 2, 3, 3, 3, 3, 4, 5와 같은 순서로 번호가 생성.

a) Partial Code for Bakery Algorithm

• Process Pi
  • 처음에 number[i] = 0

do{
	number[i] = max(number[0], number[1], ..., number[n-1])+1; //이때까지 발급한 번호 중 최대 값을 뽑아줌
	for(j =0 ; j < n ; j++){
		if(i==j) continue;
		while ((number[j] != 0 ) && (number[j] < number[i]));
		while ((number[j] != 0 ) && (number[j] == number[i]) && (j<i));
	} //번호표 순서대로 대기
	critical section
	number[i] = 0; //번호표 반납
	remainder section
} while(1);

• 현재 발급한 번호표 중 가장 큰 값의 + 1를 현재 프로세스에게 할당
• n개의 프로세스의 번호표를 비교하면서 순서가 올때까지 대기한다.
• critical section을 수행 후, 번호표 반납

b) Complete Bakery Algorithm

• Process Pi
  • 초기에는 number[i] = 0

do{
	choosing[i] = true;
	number[i] = max(number[0], number[1], ..., number[n-2]) +1;
	choosing[i] = false;
	for(j = 0 ; j<n; j++){
		if(i==j) continue;
		while(choosing[j]);
		while((number[j] != 0) && (number[j] < number[i]));
		while((number[j] != 0) && (number[j] == number[i]) && (j<i));
	}
	critical section
	number[i] = 0;
	remainder section
} while(1);

• 위의 algorithm은 번호표를 뽑는 과정이 atomic하지 않다.
• chossing 배열을 추가하여, 번호표를 뽑는 과정동안에도 기다리게 한다.

4. Synchronization with Hardware Support

1) Synchronization by Interrupt Disabling

• critical section problem의 간단한 해결책
  • shared variable이 변경되고 있을 때, interrupt가 발생하는 것을 금지시킨다.
  • 현재의 instruction 순서가 preemption(뺏는 것) 없이 실행되도록 허용한다.
  • 다른 명령어가 실행되지 않으므로 shared variable에 예상치 못한 수정이 가해지지 않는다.
• 하지만, 이 해결책은 multiprocessor 환경에서는 실현가능하지 않다.
  • interrupt를 비활성화 하여도, multiple processor가 같은 critical section에서 실행되는 것을 막을 수 없다.
  • multiprocessor 환경에서 interrupt를 비활성화하는 것은, 시간이 많이 걸리는 작업이다.
    • message가 모든 processor들에게 전달이 되어야 하기 때문.

2) Synchronization Hardware: Test-and-Set

• 많은 machine들은 특별한 hardware instruction을 제공한다.
  • word의 내용을 test하고 변경할 수 있도록 허용하는 기능
  • 2개 word의 내용을 atomic하게 swap할 수 있도록 하는 기능
• Test and set instruction → 하나의 instruction으로 설계

boolean TestAndSet(boolean &target){
	boolean rv = target;
	target = true;

	return rv;
}

do{
	while(TestAndSet(lock));
		critical section
	lock = false;
		remainder section
} while(1)

• Shared data:
  • boolean lock = false;
• TestAndSet에서 lock이 false라면, 공유 변수인 lock을 true로 설정하고 자신은 critical section에 들어간다.
• TestAndSet에서 lock이 true라면, true를 return하게 되기에 무한루프에 빠진다.
• 프로세스의 도착 순서와 무관하게 critical section에 들어가는 순서가 정해지기 때문에, bounded waiting이 성립하지 않는다.

2) Synchronization Hardware: Swap

• Atomically swap two variables

void swap(boolean &a, boolean &b){
	boolean temp = a
	a = b;
	b = temp;
}

do{
	key = true;
	while(key == true)
		swap(lock, key);
	critical section
	lock = false;
	remainder section
} while(1)

• Shared data (initialized to false) :
  • boolean lock;
  • boolean waiting[n];
• swap에서 lock과 key를 바꾸기 때문에, key = true를 받고 대기상태이지만, 만약 lock = true라면 무한 대기이다.

3) Bounded Buffer Using Test-and-Set

item nextProduced;

while(user_wants_to_write == 1){
	while(count == BUFFER_SIZE)
		; /* do nothing */
	buffer[in] = nextProduced;
	in = (in + 1) % BUFFER_SIZE;
	while(TestAndSet(lock));
	count++;
	lock = false;
}

item nextConsumed;

while(user_wants_to_read == 1){
	while (count == 0)
		; /* do nothing */
	nextConsumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	while(TestAndSet(lock));
	count--;
	lock = false;
}

• bounded waiting이 보장되지 않는다, 도착 순서에 따라 critical section에 들어가지 않기 때문에.