#6. Process Synchronization

concurrent하게 동작: A라는 process가 동작할 때 인터럽트가 어느 때든 올 수 있고 부분적으로만 수행하고 잠시 멈추게 되는 경우가 있을 수 있다. inconsistency가 일어나기에 consistency가 보장될 필요성이 있다.
consumer-producer problem
- 하나는 버퍼를 계속 채우려고, 다른 하나는 비우려고 했을 때(버퍼를 하나씩), 버퍼 counter를 늘리고 줄인다.
- producer 입장에서 버퍼를 채웠을 때 카운터는 증가해야 하고, consumer 입장에서 버퍼를 비웠을 때 카운터는 감소해야 한다.
- Race condition
동시에 여러 개의 프로세스가 동일한 자료를 접근하여 경쟁하는 현상을 말한다.
- Critical Section Problem : Race condition이 일어나지 않기 위해
  - 이 Section에 있는 code는 무조건 아무런 반응없이 한 번에 수행되어야 한다. 스케쥴러가 원하는대로 스케쥴링을 해주지는 않지만, 프로그램에서 이 자원만큼은 접근을 막는 즉, 하나의 프로세스가 이 자원을 관리할 때 다른 프로세스들이 접근을 못 하도록 해주는 것을 말한다.
  - entry section: critical section에 들어간다.
  - exit section: critical section에서 나간다.
  - remainder section: critical이 아닌 다른 section을 처리한다.
  - concurrent 환경에서는 예측이 불가능하여 따로 보호가 필요하다. 공유 자원, 외부 장치, 네트워크 통신에서는 특히 critical section이 필요하다.
동기화 문제
- 공유 자원에 접근하는 concurrent threads가 race condition이 생김
- 디버그 어려움
- 스케쥴러 조절을 못하지만 concurrency를 억제시키는 방법이 있다.
Critical Section Problem 해결책
1. Mutual Exclusion: P1이 critical section에서 돌고 있으면 다른 P들은 critical section에서 수행될 수 없다.
2. Progress: critical section에서 수행되고 있는 P가 없을 때, 이곳에서 수행되길 원하는 P들이 존재, 이 중 하나라도 critical section에서 곧바로 수행되도록 보장되어야 한다.(무제한 연기 No !)
3. Bounded Waiting: P 하나가 cs에 들어가길 원하는데 다른 P들이 들어갔다 나왔다를 반복하여 들어가길 원하는 P가 수행되지 못하는 경우가 생길 수 있기에 starvation을 방지하는 것이 필요하다. (A bound must exit)
Peterson’s solution

// Process i
do {
	flag[i] = true:
	turn = j;
	while(flag[j] && turn == j);
		// critical section
	flag[i] = false;
		// remainder section
} while(true);
// Process j
do {
	flag[j] = true:
	turn = i;
	while(flag[i] && turn == i);
		// critical section
	flag[j] = false;
		// remainder section
} while(true);

다음은 프로세스 i와 j 2개가 임계구역에 들어가는 과정이다.

가정: 최종적으로 turn = i 가 되었다.( 프로세스 i가 임계구역에 진입가능) → Mutual exclusion 만족

Process i에서 turn == j 부분이 False가 되어 임계구역에 진입한다.
임계구역에서 수행 후 flag[i] = False로 바꾸어 프로세스 j가 while문을 빠져나와 임계구역에 들어갈 수 있도록 해준다. → Progress 만족
프로세스 j가 임계구역에 진입하여 작업을 수행한다.
각 프로세스는 처음에 turn을 상대 프로세스의 값으로 바꿔준 후 유지하도록 하여 Bounded waiting을 만족한다.

→ 현대 컴퓨터 구조는 기계어를 수행하기에 올바르게 수행된다는 보장은 없다.

Critical section problem은 공유 자원이 변경되는 동안 interrupt를 발생하지 않도록 하면 해결된다고 생각할 수 있지만, Multiprocessing 환경에서는 불가능하다는 것을 알 수 있다.

이런 환경에서 interrupt를 발생시키지 않으면 메시지가 모든 처리기에 전달되어야 하고 이는 상당한 시간을 소비하고 시스템 효율을 떨어뜨린다. → 현대 기계들은 인터럽트 되지 않는 특별한 Hardware 명령어를 제공하여 이를 간단히 해결한다.

Synchronization Hardware

원자적으로(atomic) 즉, 인터럽트되지 않는 명령어를 사용한다.

Atomic 변수 (인터럽트를 못한다는 것을 명시)
atomic: atomic구문으로 이루어진 구간은 처음부터 끝까지 preemption이 일어날 수 없다.(방해할 수 없다.)
atomic hardware instruction을 구현하는 방법
- acquire lock, release lock
- HW 자체에서 test_and_set 명령어를 구현해준다. (atomic)
```
boolean test_and_set(boolean *target) {
	boolean rv = *target;
	*target = ture;
	return rv;
}
// lock initialization: "false"
do {
	while(test_and_set(&lock)); 
		// critical section
		lock = false;
		// remainder section
} while(true);
```
1. test_and_set(&lock)은 현재의 lock 값(false)을 리턴한다. 단, lock 값은 true로 바뀌어있음. while문에서 빠져나오지 못하면 계속 true의 값을 가진다.(atomic) → Mutual exclusion 만족
2. lock의 초기값이 false이기에 처음에 임계구역에 진입한다.
3. 작업이 끝나면 lock을 false로 바꾸어주어 다른 프로세스가 while문을 빠져나올 수 있게 한다. → Progress 만족
- compare_and_swap 명령어 (atomic)
```
void compare_and_swap(int *value, int expected, int new_value) {
	int temp = *value;
	
	if(*value == expected) {
		*value = new_value;
	}
	return temp;
}
// lock initialization: "0"
do {
	while(compare_and_swap(&lock, 0, 1) != 0); 
		// critical section
		lock = 0;
		// remainder section
} while(true);
```
1. compare_and_swap(&lock, 0, 1)은 lock의 원래 값을 리턴한다. 단, lock이 0일 때만 1로 변경된다. 처음에 0인 lock의 값이 1로 바뀌어지고 임계구역으로 들어가면 이후 진입하려는 프로세스들은 1만 리턴하기에 while문을 빠져나오지 못한다. → Mutual exclusion 만족
2. 임계구역에 진입한 프로세스가 작업을 수행한 뒤 lock을 0으로 바꾼다.
3. 기다리던 프로세스가 while문을 빠져나오면서 임계구역에 진입한다. → Progress 만족

하지만 위 명령어 모두 Bounded waiting을 아직 만족하지 못한다. 한 프로세스가 lock의 값을 바꾸자마자 다시 진입이 가능하기 때문이다.

explicit하게 어떤 프로세스에게 양보를 할지 명시해야 한다.
lock은 풀렸으면 들어가서 수행하자라는 식이기에 보장은 못 한다.

Peterson’s solution

Synchronization Hardware