[Linux][OS][WIP] synchronization하기

동기화의 필요 이유

Forks and Joins : fork point에 일이 도착하면, n개의 sub-job으로 쪼개져서 n개의 task로 수행된다. n개의 task가 모두 수행될때까지 기다렸다가 끝난다. 

Producer-Consumer: producer가 정보를 만들어서 전달해주기 전까지 consumer은 기다려야 한다

Exclusive use resources: 여러개의 process가 resource에 의존적일 때, 모두 같은 시간에 접근해야 한다. -> 동시성 감소?

 

1. Lock

Lock을 해서 특정 코드 영역에 대한 상호 배타성을 보존하는 방식이다. 

 

lock문제를 해결하기 위한 방법으로는 크게 3가지가 있다. 

 

1. 소프트웨어적인 방법 ex) 피터슨 알고리즘

2. atomic instruction, 하드웨어 명령어 사용

3. 인터럽트 제어로 해결

 

현재 시대에는 2,3 번을 많이 사용하고 있다!!

 

1번) 피터슨 알고리즘

고전적인 방법이라 더 이상 현대OS에서는 자주 사용되지 않지만 알아보도록 하자

 

i, j 프로세스가 있다고 한다. 

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

while문이 하는 역할이 혹시나 다른 애가 쓰고싶어했는지 확인하는것! busy waiting을 한다. 

 

항상 확인해야하는건 두개의 프로세스가 동시에 같은 줄이 시행되도 문제가 없는지???

동시에 시행되어도 turn=j 또는 turn=i 이기 때문에 상관 없다. 

 

 

2번) atomic instruction, 하드웨어 명령어 사용

이 하드웨어적인 서포트에 대해서 조금 더 자세하게 알아보자.

이 서포트는 주로 atomic instruction을 통해 이루어진다.

atomic instruction은 더 이상 쪼개지지 않는 원자적 명령어이다. 

 

예를 들어, 

• test-and-set
• fetch-and-add : 메모리 주소에 있는 값을 특정 값만큼 증가시킨다

int i;
__sync_fetch_and_add(&i, 1);

• compare-and-swap

같은 instruction들이다.

 

하지만, atomic instruction은 복잡한 critical region에서 데이터 충돌을 보호하기에는 부족한 면이 있었다. 

( 예를 들어 inode의 page_tree, page cache같은 경우)

 

단순히 atomic instruction이 아니라, 하나의 thread만이 데이터구조에 접근한다는 보장이 필요했다. 

 

atomic operation이 lock보다 빠르고, deadlock도 없고 정말 좋긴 한데 할 수 있는 연산이 몇가지 없고 복잡한 연산을 하지도 못해서 lock을 써야한다...

2. lock의 예시 - Spinlock

Spinlock은 커널에서 가장 자주 사용되는 lock이다. 

Spinlock의 방식은 busy waiting이라고도 부른다. 

만약 Lock에 접근하려고 하는데 이미 lock이 다른 쓰레드에 의해서 사용되고 있다면 접근하려는 쓰레드는 계속 상태를 확인하면서 기다린다.

기다리는 동안 많은 CPU cycle이 낭비된다. 

 

Linux에서 쓰이는 spinlock 함수들은 다음과 같다. 

spin_lock_init(&lock): 주어진 spinlock_t를 initialize 한다.  
spin_lock(&lock): 주어진 spinlock_t를 획득하려고 한다. 
spin_lock_irq(&lock): local interrupt를 끄고 주어진 주어진 spinlock_t를 획득한다. 

spin_unlock()

 

 

 

 

3. Semaphore

Read Write Semaphore가 대표적인 예제이다.

4. Mutex

Mutex도 Lock의 일종인데, mutex와 다른 lock의 차이점은 다른 lock들은 계속 lock상태를 확인하면서 무한루프를 돌면서 대기중인 반면, mutex는 쓰레드를 재워버린다. busy waiting(Running상태에서 무한루프)과 blocked(waiting으로 상태가 아예 바뀌어버림)의 차이이다. 

 

busy-waiting은 CPU cycle을 낭비하는 반면 blocked는 CPU cycle을 낭비하지 않는다.

 

[출처]

https://jhnyang.tistory.com/41