synchronization

multi-threaded system에서는 shrared date를 사용하는 경우가 있다. 당연히 multi-process에서도 발생한다.

이 경우 실행 순서 조절과 동기화 처리는 필수이다.

 

synchronization

- shared resources

- coordinate the execution order

만약 synchronization이 되어 있지 않다면 어떤일이 발생할까?

 

race condition

: concurrent thread/process들이 shared data에 경쟁적으로 접근하는 상황

-> context switch를 연산자 단위가 아니라 시간 단위로 나누어서 처리하기 때문에 instruction 순서가 변경되기 때문에 발생한다.

 

이러한 race condition은 non-deterministic, depends on timing이다.

즉 항상 다른 결과를 보여주게 되고 타이밍에 따라 작동이 될수도, 안될수도 있는 심각한 문제를 발생시킨다.

이렇게 동기화 처리를 하지 않아 문제가 생기는 shared data 접근 코드 영역을 critical section이라고 한다.

 

critical section problem

: shared data를 접근하는 코드의 영역인 critical section에서 동기화를 하지 않아 생기는 문제

즉 shared data에 접근하는 영역이 race condition을 발생시키기 때문에 동기화 문제가 발생하는 것이다.

그렇다면 이를 어떻게 해결해야 할까?

 

solution to critical section

1. Mutual Exclusion, 상호배제

: critical section에는 한번에 하나의 process/thread만 접근 가능하다.

 

2. Progress

: shared data를 쓰지 않는 경우에만 사용 가능하다.

 

3. Bounded Waiting

: 누군가 shared data를 쓰고 있다면 wait한다. 이때 무한 대기하는 것이 아니라 시간이 지나면 진입 가능해야 한다.

즉 starvation이 없어야 한다.

 

위 세가지를 모두 만족해야한다.

mechanisms for critical section

Locks: primtive, semantic level

Semaphore: basic

Monitor: high level

Messages

 

 

---

Locks

Lock: critical section에 진입하기 전에는 lock을 걸어준다.

Unlock: critical section에 빠져나오면 lock을 풀어준다.

 

즉 다음과 같이 thread1, thread2가 shared data에 접근하는 코드가 동시에 진행된다고 해보자

이 경우 thread1이 thread2보다 먼저 critical section에 진입하므로 A 시점에서 lock을 확보하게 된다.

thread2는 A가 되었을 때 lock을 확보하고자 하지만 이미 thread1이 lock을 걸어둔 상태이므로 확보가 불가하다. 따라서 thread1이 unlock할 때까지 기다리게 된다.

 

 

Implementing Locks

struct lock
{
	int held = 0;
}

void lock(struct lock *l) 
{
	// busy waiting or spinlock
	while(l -> held == 1)
    		;
	l -> held = 1;
}

void unlock(struct lock *l)
{
	l -> held = 0;
}

lock() 에서는 lock struct의 held값이 1인 경우 무한 루프를 돌며 대기한다.

이렇게 cpu 자원을 사용하며 대기하는 것을 busy waiting 또는 spinlock이라고 한다.

 

하지만 lock의 문제는 따로 있다.

예를 들어 A가 lock을 걸고자 실행한 lock() 함수에서 while문에 진입 하기 전에 interrupt가 걸리게 될 수도 있다. 이 경우 context switch로 B의 코드가 실행되고 A에서 lock을 확보하지 못했으니 held값은 0이므로 critical section에 진입 가능해진다.

즉 synchronization 문제가 또 발생하는 것이다.

따라서 lock 함수는 atomic operation으로 구현되어야 한다. 즉 더 이상 쪼갤 수 없어야 한다.

 

lock solutions

- SW-only algorithms: 오버헤드의 가능성이 있다. 대표적인게 bakery algorithm

- Hardware atomic instructions: cpu에서 하나의 명령어를 묶어서 처리한다. 대표적인게 test-and-set, compare-and-swap

- Disable/re-enable interrupt: context siwtch가 일어나지 않도록 Interrupt를 막는다.

 

 

SW-only algorithms

: sw를 사용하여 문제를 해결하자. 여러 알고리즘이 있지만 교수님께서 수업시간에 중요하다고 강조를 해주셨던 베이커리 알고리즘을 다루고자 한다.

 

bakery Algorithm

: n개의 process들을 위한 알고리즘.

- critical section에 진입하기 전에 번호를 부여받는다. (번호가 작은 순서대로 진입)

- 번호는 오름차순으로 진행된다.

- 같은 번호인 경우 PID가 작은 순서부터 진입한다.

 

이때의 shared data는 다음과 같다.

- boolean choosing [n]: 번호를 받기 위해 신청하는 bool 변수

- int numbers [n]

 

do
{
	// entry section
	choosing[i] = true;
    numbers[i] = max(number[0], number[1], ... , number[n-1]) + 1;
    choosing[i] = false;
    
    for(int j = 0; j < n; j++)
    {
    	while(choosing[j])
        	;
        while(number[j] != 0 && (number[j], j) < (numbers[i], i))
        	;
    }
    // critical section
    
    // exit section
    number[i] = 0;
} while(1);

 

choosing[i] = true로 만들어서 번호를 받을 준비를 한다. 그 후 번호배정은 가장 큰수 + 1을 하게 된다. 그래야 마지막 번호가 되기 때문이다. 번호 배정이 끝나면 choosing[i]를 다시 false로 만들어준다.

 그 후 for문을 돌며 critical section에 접근하는 프로세스의 개수만큼 반복을 하게 된다.

이때 첫번째 while(choosing[j])는 모든 프로세스들이 번호를 부여받았는지 확인하는 것이다. 번호를 부여 받아야 줄을 세울 수 있기 때문이다. 하지만 여기서도 spinlock, 즉 busy waiting이 사용되고 있다.

 두번째 while은 두가지 조건을 체크한다. 먼저 첫번째 조건인 number[j]가 0이 아닌지 검사하는 것은, 0인 경우 아직 번호를 못받은 프로세스가 있다는 뜻이기 때문에 critical section에 진입할 수 없다는 것이다.

 두번째 조건은 (a, b) 의 형태의 조건을 가지고 있다. 이때 a는 부여받은 번호, b는 process id이다. 즉 부여받은 번호가 작은 경우와 부여 받은 번호가 같다면 process id가 작은 경우에만 critical section에 접근할 수 있다는 뜻이고, 이는 앞에서 말했던 실행순서 조절을 위한 것이다.

 그 후 critical section이 끝나 빠져나올 때는 number[i]를 다시 0으로 만들어서 번호를 다시 돌려주게 된다.

 

이 bakery algorithm에서 번호를 부여하는 과정은 FCFS다. 따라서 starvation이 없으므로 fair하다고 할 수 있다.

 

 

Hardware atomic instructions

: test and set

boolean TestAndSet(boolean &target)
{
	boolean a = target;
    target = true;
    return a;
}

// shared data
	boolean lock = false;
    
// process
do
{
	while(TestAndSet(lock))
    	;
    //critical section
    
    lock = false;
} while(1);

 

TestAndSet의 역할은 처음 들어온 target의 bool type을 반환하고 true로 만들어주는 것이다.

하지만 test and set은 bounded waiting을 만족하지 않는다. 왜냐하면 순서를 정해주는 부분이 없기 때문이다. 따라서 fair하지 않다는 단점이 있다. 이는 compare-and-swap 방식도 마찬가지이다.

따라서 compare-and-swap 는 설명 패스!

 

 

Disable/re-enable interrupt

: shared data에 접근할 경우 interrupt를 불가하게 하자

이는 한 프로세스가 계속 cpu 자원을 독점하도록 한다. kernel만 이러한 enable/ disable을 할 수 있기 때문에 multi-processor 환경에서는 매우 비효율적이다. 왜냐하면 모든 프로세스들에게 interrupt를 하지 말라고 계속 신호를 보내야하기 때문이다. 따라서 system 효율이 매우 떨어지기 때문에 안쓴다!

 

그렇다면 Lock방식보다 좀 더 발전된 동기화 기법들은 없을까?

당연히 있다.

이는 다음 포스트에서...