시작하기

프로세스들은 시스템 내의 다른 프로세스들의 실행에 영향을 주거나, 영향을 받을 수 있다. 이렇게 서로에게 영향을 주거나, 받는 프로세스들을 협력적 프로세스라고 한다

협력적 프로세스는 주소 공간을 직접 공유하거나 shared memory / message passing을 통해 데이터를 공유하게 되는데 공유 데이터에 동시에 접근하는 과정에서 데이터에 오류가 일어날 수 있다. -> 데이터의 일관성이 사라진다.

예를 들어 0으로 초기화된 a라는 같은 변수에 접근하여 1을 더하는 두개의 프로세스 p,q가 존재할 때, p에서 a(=0)를 가져와 읽는 순간, context switch가 발생하여 q에서 a(=0)를 가져와 +1 한 값(1)을 a에 저장하고, 다시 context switch가 발생, p에서 이전에 읽었던 a(0) 에 1을 더하는 작업을 계속해서 수행하여 a에 저장(1)하면,
a에 1을 더하는 작업을 p와 q가 각각 한번씩, 총 두번 진행하였음에도 a의 값이 1로 남는 결과가 발생한다.

race condition

위처럼 동시에 여러개의 프로세스가 같은 데이터를 접근, 조작하였을 때, 접근의 순서에 따라 실행 결과가 달라지는 상황을 경쟁상황(race condition)이라고 한다.

해결방법은?
한순간에 하나의 프로세스만이 데이터에 접근하도록 해줘야 한다. 그 방법으로 이용하는 것이 바로 프로세스들의 synchronization(동기화).

CRITICAL SECTION 문제

critical section?

각 process에서 다른 프로세스들과의 shared data에 접근하는 코드의 영역을 critical section(임계영역)이라 한다.

critical section 문제는 프로세스들이 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜을 설계하는 것이다.

section of code

1. entry section : critical section 진입을 요청
2. critical section
3. exit section : critical section 뒤의 code, critical section 진입을 위한 권한을 반환한다.
4. remainder section : 나머지 구역, 1,2,3을 제외한 나머지 코드

critical section 문제의 요구조건

critical section 문제에는 요구조건이 있다. solution들은 아래의 요구조건을 만족시켜야 한다.

1. mutual exclusion(상호배제) : 하나의 프로세스가 임계구역에서 실행되고 있다면 다른 프로세스들은 임계구역에서 실행될 수 없다.

2. progress(진행) : 임계구역에서 실행중인 프로세스가 없을 때, 임계구역으로 진입하려는 프로세스들이 있다면 그 중 하나는 들어갈 수 있어야함. (무한정 대기하는 일이 없어야함)
   -> deadlock 문제 발생 방지

3. bounded waiting(한정된 대기) : 프로세스가 진입 요청을 한 후로부터 대기하는 횟수(다른 프로세스들이 먼저 자신의 임계구역에 진입하는 횟수)를 한정하여야 함. -> starvation이 일어나지 않아야함.

단일 core에서의 해결 방법

단일 core에서는 critical section에서 interrupt가 발생하지 않도록 함으로써 critical section 문제를 해결할 수 있다.

하지만 다중 core에서는? 메시지가 모든 프로세서에 전달되는 과정에서 임계구역으로의 진입을 지연시키고, 시스템 효율성을 떨어뜨린다. 인터럽트 비활성화도 시간이 오래걸린다.

비선점 커널의 경우에는 자발적으로 CPU 제어를 양보할 때까지 계속해서 수행되므로 race condition을 고려하지 않아도 된다. -> 선점형 커널에서만 생각해보자

다중 core에서의 해결 방법

Peterson's solution

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

flag[i] : i가 진입준비가 됐음을 의미한다.
turn = j : j의 진입 가능을 보장한다.
while (flag[j] && turn == j); j가 진입 준비를 마치고 j의 turn이라면 j의 critcial section이 종료될 때까지 기다린다.
flag[i] = false; i의 critical section이 종료됐음을 의미한다.

• 개념적으로 완벽한, 아주 고전적인 solution이다.
• mutual exclusion, progress, bounded waiting, critical section 문제의 요구조건을 모두 만족시킨다.
• 하지만 최신 컴퓨터 아키텍쳐에서는 processor나 컴파일러가 명령순서를 임의로 재정렬할 수 있어 동기화가 잘 작동되지 않을 수 있다.

하드웨어 지원

memory barrier - 메모리 장벽

앞에서 peterson's solution이 최신 컴퓨터 아키텍쳐에서 작동하지 않는 이유는 processor나 컴파일러가 명령순서를 임의로 재정렬할 수 있기 때문이라고 이야기했다.

이러한 명령순서 재정렬을 방지할 수 있는 방법

하드웨어 명령어 사용

많은 현대 기계들이 제공하는 명령어들 중 test_and_set()과 compare_and_swap() (또는 비슷한 기능을 하는) 이라는 특별한 하드웨어 명령어가 있다.

test_and_set은 한 word의 내용을 검사하고 변경하며
compare_and_swap 은 두 word를 받아 교환한다.

위 명렁어들이 특별한 이유는 atomic(원자적) operation이라는 점. interrupt되지 않는 하나의 단위로서, 해당 함수가 실행될 동안에는 절대 interrupt가 되지 않는다.

-> 이러한 원자적 명령어들을 사용하면 각 명령어들은 순차적으로 실행되므로 상호 배제 구현이 가능하다.

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

---

do {
    while (test_and_set(&lock)) 
    	;
    /* critical section */
    
    lock = false;
    
    /* remainder section */
    	
    } while (true);

}

false로 초기화된 lock이라는 변수가 존재할 때,
test_and_set(&lock) 는 바꾸기 전의 값을 return 한다.

만약 lock이 현재 false이면 초기 상태이거나 다른 프로세스가 critical section에 있지 않다는 이야기 -> lock = true를 만들고(test_and_set 함수가 해준다) critical section 코드 작동 -> exit 하면서 lock을 false로 만들어 다른 프로세스의 접근을 허용해준다.

atomic-variable

원자적 연산을 이용하는 방법
역시 상호배제를 보장한다.

하드웨어 기반 해결책은 복잡하고, 응용 프로그래머들은 이용불가하다.

---

뮤텍스 락

mutex : mutual exclusion의 약자

critical section 진입시 lock(key)을 받고(acquire), exit 때 반납(release)

while (true) {
    acquire();
    
    /*critical section*/
    
    release();
    
    ..remainder section
}

acquire() {
    while(!available)
    	; /* busy waiting */
    available = false;
}
release() {
	available = true;
}

busy waiting, spin lock

acquire() 에서 무한 loop가 생긴다. -> busy waiting -> CPU 낭비
이렇게 lock을 사용할 수 있을 때까지 process가 회전하는 lock 유형을 spinlock이라고 한다.

CPU 낭비이긴 한데!! 오히려 다중 core에 환경에선 선호되는 경향이 있다

왜? lock 에서 기다리고 있을땐 context switch가 일어나지 않기 때문에 waiting -> ready queue를 거치는 context switch에 걸리는 시간을 절약하여 접근이 가능할 때 바로 접근해버린다.

deadlock과 starvation은 해결되지 않는다. 2개의 프로세스에만 적용이 가능하다. (lock을 가진채로 죽어버리면 deadlock...)

semaphores

정수변수(S)로, 초기화 또는 두개의 atomic operation(wait-P, signal-V)로만 접근이 가능하다.

wait(S) {
    while (S <= 0)
    	; // busy waiting
    S--;
}

signal(S) {
    S++;
}

binary and counting semaphore

semaphore의 초기화 방법에 따른 구분이다.
binary semaphore는 0또는 1로만 초기화가 가능하다. 한 번에 하나의 process(or thread)만 critical section에 접근 가능한 것. -> mutex 락과 비슷하게 동작한다.

counting semaphore의 경우 값의 제한이 없다. 보통 유한한 개수의 자원에 대한 접근을 제어할 때 사용한다. 자원의 개수로 semaphore를 초기화한다.

use to synchronization problem

S1 -> S2 의 순서로 작동시키고 싶을 때

• 프로세스 1

S1;
signal(s);

• 프로세스 2

wait(s);
S2;

로 설정하고 s = 0으로 초기화하면
process 1은 S1 을 수행하고 s를 1로 갱신하고
process2는 s가 1이 될때까지 기다렸다가 S2를 실행하게 된다.

busy waiting 방지하기

역시 busy waiting이 발생할 수 있다. 하지만 semaphore에는 이를 방지하는 방법도 존재한다.

• wait()이 작동할 때 semaphore이 음수이면 계속해서 while문을 도는 대신 자신을 waiting list에추가한후 waiting 상태로 들어가고, signal()은 waiting list에 있던 프로세스를 restart하여 ready queue로 보내게 되면 busy waiting으로 CPU가 소모되는 것을 방지할 수 있다.

monitor

mutex와 semaphore의 단점을 극복하는 방법이다.
mutex와 semaphore는 발견이 쉽지 않은 타이밍 오류를 야기할 수 있다.

예를 들어, wait과 signal의 순서를 바꾸는 등 프로그래머가 실수를 할 수 있는 것.

그래서 좀 더 높은 레벨의 구조체인 monitor를 사용할 수 있다.

monitor는 abstract data type으로 모니터 내부에서 mutual exclusion이 보장되는 프로그래머가 정의한 일련의 operation set을 포함한다.

뭐 예를 들어

synchronized (object) {
 /* critical section */
}

이런식으로 critical section을 선언해주는 것만으로도 synchronization이 되는 것.

liveness

프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야하는 일련의 속성

무기한 대기가 바로 라이브니스 실패의 한 예이다.

실패1 - deadlock

실패2 - Priority Inversion

높은 우선순위의 프로세스가 낮은 우선순위의 프로세스를 기다리게 되는 상황

running process(process low)보다 우선순위 높은 new process(process high) 등장
-> process low가 lock 에 의해 보호되는 작업을 진행하여 process high의 선점을 막음
-> process low가 끝나고 process high가 실행되는 대신 우선순위가 둘의 중간인 process mid가 먼저 실행되면서 process high가 대기해야 하는 상황 발생!

-> Proiority Inheritance
High process의 priority를 Low priority의 process에게 복제하여 low가 끝나고 mid가 high보다 먼저 실행되는 것을 막기