Synchronization

쓰레드간 자원 분배 : 조심히 다뤄야 한다.

A cooperating process는 시스템에서 다른 프로세스가 실행됨으로써 영향을 주거나 받을 수 있는 것을 의미한다.

cooperating process는 직접적으로 논리적 주소(code, data 둘다)를 공유할수도,

파일이나 메세지를 통해서만 데이터를 공유하도록 허용될수도 있다.

공유 데이터로의 동시적(concurrent) 접근은 data 모순(inconsistency)를 야기할 수 있다.

논리적인 주소 공간을 공유하는 협동 프로세스들의 순차적 실행을 확보하여 데이터 동일성을 유지하는 메커니즘에 대해 논해보자.

(Producer Consumer Problem에 이어짐.)

Disabling Interrupts

가장 기초적인 방법 : CPU가 interrupts에게 반응하는 것을 일시적으로 막는 것

interrupts off : 다른 쓰레드는 작동중인 쓰레드를 선점(preempt)못한다 => 선점은 ‘timer interrupts‘가 관리하니까

interrupts on : 작동중인 쓰레드는 언제든 선점당할 수 있다. => 2개의 C statements 중 하나에게, 심지어 하나한테도..

Pintos 는 “preemptible kernel” 이다. => 커널 쓰레드는 언제든 선점당할 수 있다.

전통적인 UNIX 시스템에서는 “nonpreemptible”이다. => 커널쓰레드는 스케쥴러에게 명시적으로 호출당할때만 선점된다?

원문 : (kernel threads can only be preempted at points where they explicitly call into the scheduler)

preemptible kernels는 좀더 명시적인 synchronization이 요구된다.

위에 것 쓸일 거의없음.

외부(external) interrupt handlers : 잠들수 없고(sleep) 대다수의 다른 synchronization을 사용할수 없음

어떤 외부 interrupts는 disabling interrupts로도 지연될 수 없는데(postponed) 이것들은 non_maskable interrupts(NMIs)

라고 함.

컴퓨터 불 붙거나 응급상황에만 쓴다.. -> pintos에서 안다룸

enum intr_level; //One of INTR_OFF or INTR_ON, interrupts의 enabled,disabled 나타냄
enum intr_level intr_get_level (void) // 최근 interrupt 상태 반환
enum intr_level intr_set_level (enum intr_level level); // interrupts on/off 바꿈, 이전 상태 반환
enum intr_level intr_enalbe (void); // interrupts 킴. 이전 상태 반환
enum intr_level intr_disable (void); // interrupts 끔. 이전 상태 반환

Semaphores(세마포어)

semaphores는 특별한 타입의 변수로서 자동적으로 조작하는 두 오퍼레이터와 함께 있는 비음수 정수값을 가진다.

쉽게 말하면, 세마포어라는 간단한 정수 값을 사용함으로써 동시 프로세스들을 다루는 기술이다. 다음과 같다.

“Down” or “P”(wait()) : 양수(positive)가 될 값을 기다리다가, 감소시킨다.

즉 P(s)는 s가 0이 아니면 P는 s를 감소시키고 즉시 리턴함. 만일 s가 0이면 이 쓰레드는 s가 0이 아닌 값을 가지고, 쓰레드가 V 연산에 의해 재시작 될 때까지 정지된다. 재시작 후에 P 연산은 s를 감소시키고 제어를 호출자에게 돌려준다.

P(Semaphore S) {
    while (s<=0)
        ; //no operation
    S--l
}

“Up” or “V”(signal()) : 값을 증가시킨다(그리고 쓰레드를 기다리는 한개를 깨운다(wake up))

V(Semaphore S){
    S++;
}

즉 V(s)에서 V 연산은 s를 1 증가시킨다. 만일 s가 0이 아닌 값이 되는 것을 기다리면서 P 연산에서 멈춰 있는 쓰레드가 있다면, V 연산은 이 중에서 정확히 한 개의 쓰레드를 시작하고, 그 후에 s를 감소시켜서 자신의 P 연산을 완료한다.

wait(), signal()에서 세마포어의 정수 값에 대한 수정은 불가분하게 작동되어야만 한다. 안 프로세스가 세마포어 값을 변경할 때, 동시에 같은 세마포어 값을 변경할 수 있는 프로세스는 단 하나도 없다.

유일한 요구사항 : V가 정확히 한 개의 대기하는 쓰레드를 재시작해야 한다.

0으로 초기화 된 세마포어는 정확히 한번 발생할 event를 기다리기 위해 사용될 지도 모른다.

다시 말해, 여러 개의 쓰레드가 하나의 세마포어를 기다리고 있을 때, 어떤 것이 V의 결과로 재시작되는지 예측할 수 없다.

예를 들어, 쓰레드 A가 다른 쓰레드 B를 시작시킨다고 가정하자. 또, 쓰레드 A는 B가 보낼 어떤 활동(activity)이 완성되었다는 신호를 기다린다고 가정하자. A는 0으로 초기화된 세마포어를 만들수 있고 B를 시작시킬 때 그 세마포어를 B에게 보낼 수 있다. 그리고 세마포어를 “Down”한다. B가 활동을 끝낼때는 세마포어를 ‘Up’한다. 이건 A가 먼저 “Down”했는지, B가 먼저 “Up”했는지와는 무관하게 작동한다.

예시

struct semaphore sema;

/* Thread A */
void threadA (void) {
    sema_down (&sema);
}

/* Thread B */
void threadB (void) {
    sema_up (&sema);
}

/* main function */
void main (void) {
    sema_init (&sema, 0);
    thread_create("threadA", PRI_MIN, threadA, NULL);
    thread_create("threadB", PRI_MIN, threadB, NULL);
}

이 예시에서 ,threadA는 threadB가 sema_up ()를 호출하기 전에 sema_down()에서 실행을 멈춘다.

1로 초기화 된 세마포어는 전형적으로 자원으로의 접근을 조절하기 위해 사용된다. 코드 블록이 자원을 사용하기 시작하기 전에, 세마포어를 “Down”하고 자원을 다 쓰면 자원을 “up”시킨다.

물론 세마포어는 1보다 큰 값으로 초기화 될 수도 있다. 근데 거의 쓰이지 않는다. Pintos의 세마포어 타입과 오퍼레이션은 include/threads/synch.h에서 선언된다.

struct semaphore; // 세마포어 선언
void sema_init (struct semaphore *sema, unsigned value); //  sema를 주어진 초기값의 새로운 세마포어로 초기화
void sema_down (struct semaphore *sema); // sema에 "down"이나 "p" 실행, positive되길 기다리다가 1만큼 떨군다.
bool sema_try_down (struct semaphore *sema); // 기다리지 않고 "down"이나 "p" 실행
void sema_up (struct semaphore *sema); // sema에 "up" 이나 "V" 실행

line 4 : sema가 성공적으로 감소되면 TRUE를 반환하고, 이미 0이거나 기다리지 않고 감소시킬 수 없으면 FALSE 반환한다. tight loop에서 이 함수를 호출하는 것은 CPU time을 낭비시키니, sema_down()를 사용하거나 다른 접근방식을 찾아라.

(tight loop : 코드가 어떤 지연이나 방해 없이 반복적으로 실행되는 프로그래밍 구조를 뜻함)

line 5 : 어떤 쓰레드들이 sema를 기다리고 있으면, 하나를 깨운다. 대부분의 동기화 원리와 다르게, sema_up()는 external interrupt handler 내부에서 호출될지도 모른다.

세마포어는 내부적으로 disabling interrupt(위 참고)와 thread blocking과 unblocking(thread_block() 과 thread_unblock())으로 만들어 졌다. 각 세마포어는 lib/kernel/list.c에서 linked list 실행에 사용되는 대기 쓰레드 리스트를 가진다.

Mutex

뮤텍스 : 상호 배타성을 제공하는 목적의 바이너리 세마포어.

바이너리 세마포어 : 세마포어는 공유 변수들을 상호 배타적으로 접근하기 위한 편리한 방법 제공한다. 아이디어는 하나의 세마포어 s를 초기값 1로 시작해서 각각의 공유 변수(또는 공유 변수들의 관련 집합과)에 연계하고 그 후에 대응하는 크리티컬 섹션을 P(s)와 V(s) 연산으로 둘러싸는 것이다. 바이너리 세마포어는 이런 방법으로 공유 변수들을 보호하기 위해 이용된 세마포어를 말한다. 값은 항상 0 또는 1이다.

locking : 뮤텍스에서 P 연산 수행

unlocking : 뮤텍스에서 V 연산 수행

Mutex VS Semaphore

세마포어

공유된 자원의 데이터 혹은 Critical Section 등에 여러 Processes나 Threads가 접근하는 것을 막아줌(즉, 동기화 대상이 여럿)
리소스의 상태를 나타내는 간단한 카운터
비교적 긴 시간을 확보하는 리소스에 대해 이용
유닉스 시스템에서 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스의 동기화 등에 사용
세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 기다리도록 해야함

뮤텍스

공유된 자원의 데이터 혹은 Critical Section 등에 단일 Process나 Thread가 접근하는 것을 막아줌(즉, 동기화 대상이 하나)
상호배제(Mutual Exclusion)라고도 함
Critical section을 가진 Thread들의 Running Time이 겹치지 않도록 각각 단독으로 실행되게끔 해줌.
locking 과 unloking 사용
즉, 뮤텍스 개체를 두 쓰레드가 동시에 사용할 수 없음

차이점

차이점	Mutex	Semaphoere
포함관계	뮤텍스는 세마포어가 될 수 없음(상태가 0,1 뿐이라서)	세마포어는 뮤텍스가 될 수 있음
lock 소유	lock 소유 가능, 소유주 책임 있음.	소유할 수 없음
해제	뮤텍스 소유한 쓰레드가 이 뮤텍스 해제 가능	세마포어 소유하지 않은 쓰레드가 이 세마포어 해제 가능
범위와 형태	프로세스 범위, 프로세스 종료 시 자동으로 Clean up	시스템 범위, 파일시스템상의 파일 형태
동기화 대상	오직 1개	하나 이상

하지만 둘의 단점은 Critical section으로 들어가기 전 wait(), 빠져 나올때 signal or release 처리를 직접 해주어야 함.

Counting Semphore

Binary Semaphore(mutex lock)과 다르게 범위 제한 없음. 다양한 instance가 있는 자원에 대한 접근을 제어할 때 사

생산자-소비자(Producer-consumer) 문제

생산자 쓰레드는 아이템들을 생성하고 이들을 제한된 버퍼(Bounded buffer)에 추가한다. 소비자는 이들을 버퍼에서 제거하고 그 후에 이들을 소비한다.

생산자와 소비자 쓰레드는 n개의 슬롯을 갖는 제한된 버퍼를 공유한다. 생산자는 반복적으로 아이템 만들고 버퍼에 삽입. 소비자는 반복적으로 아이템을 버퍼에서 제거, 소모(이용).

아이템들을 추가하고 제거하는 것이 공유 변수들의 갱신과 관련되어 있으므로 버퍼에 접근할 때 상호 배타성을 보장해야함.

뿐만 아니라, 버퍼로의 접근을 스케줄링 해야함

버퍼가 가득 차서 빈 슬롯이 없으면, 생산자는 슬롯이 가능해질 때까지 기다려야 함.

버퍼가 텅 비어서 가용한 아이템이 없다면, 소비자는 아이템이 가용할 때까지 기다려야 함.

counter variable = 0

버퍼에 새 아이템을 추가할때마다 카운터 증가 : counter++

버퍼에서 한 아이템을 제거할때마다 카운터 감소 : counter–

ex. 멀티미디어 시스템

소비자가 해독하고 이들을 화면에 색칠하는 동안에 비디오 프레임들을 인코드할 수 있다.
버퍼의 목적 : 개별 프레임에서 데이터에 관련된 인코딩과 디코딩 시간의 차이로 발생한 비디오 스트림 내의 잡음 제거
버퍼는 생산자에게는 슬롯의 저장소를 제공
소비자에게는 인코드된 프레임의 저장소 제공

첫 문단에서 이어지는 내용

생산자 프로세스는 소비자 프로세스에 의해 소비되는 정보를 생산한다.

예시.

컴파일러는 assembler에 의해 소비되는 assembly code를 생산한다.
바꿔서, assemble는 loader에 의해 소비되는 객체 모듈을 만든다.

생산자 -소비자 문제의 해결책 중 하나는 공유 메모리를 사용하는 것이다.

생산자와 소비자 프로세스들이 동시에 작동하는것을 허락함으로써, 우리는 생산자가 채우고 소비자가 비우는, 사용 가능한 items의 버퍼를 가져야만한다. 이 버퍼는 생산자와 소비자 프로세스들에게 공유되는 메모리 지역에 있다.

생산자가 한 아이템을 생산하는 동안 소비자는 다른 아이템을 소비한다.

소비자가 아직 생산되지 않은 아이템을 소비하지 안도록 하기 위해 생산자와 소비자는 동기화(synchronized)되어야만 한다.

Two kinds of buffers

unbounded buffer : 실질적인 버퍼 크기에 대한 제한을 두지 않는다. 소비자는 새로운 아이템을 기다릴지도 모르지만 생산자는 항상 새 아이템을 만든다.
Bounded buffer : 고정된 버퍼 크기를 가정한다. 이 경우에 소비자는 버퍼가 비었는지 소비자가 기다리거나, 생산자는 버퍼가 꽉 찼는지 기다려야 한다.

Locks

록은 1의 초기 값을 가진 세마포어 같다. 록에서 “up”은 “release”라 불리고, “down”은 “acquire”로 불린다.

세마포어와 비교해서, 록은 제한을 하나 더 가진다. 록의 “owner(소유자)”라고 불리는 lock을 소유한(acquire) 유일한 쓰레드는 그것을 release(해제)하게 된다.(원문 : only the thread that acquires a lock, called the lock’s “owner”, is allowed to release it.) 이 제한이 문제라면, 록 대신 세마포어가 사용되어야 한다는 좋은 소식이다.

pintos에서 록은 “재귀적”이지 않다. 즉, 그 lock을 소유하기를 시도하는 록을 가진 쓰레드에 대한 에러다.(원문 : Locks in Pintos are not “recursive.” that is, it is an error for the thread currently holding a lock to try to acquire that lock.) 록 타입과 함수는 include/threads/synch.h에서 선언된다.

struct lock; // lock 선언
void lock_init (struct lock *lock); // lock을 새 lock으로 초기화한다. 초기에는 누구에게 소유되지 않는다.
void lock_acquire (struct lock *lock); // 최근(current) 쓰레드를 위해 lock을 acquire한다.
bool lock_try_acquire (struct lock *lock); // 기다리지 않고 최근 쓰레드에게 사용될 lock을 acquire하려고 시도.
void lock_release (struct lock *lock); // 최근 쓰레드가 반드시 소유해야하는 lock을 release한다.
bool lock_held_by_current_thread (const struct lock *lock):

line 3: 우선 필요하다면 release할 아무 최근 소유자를 기다린다.

line 4 : 성공적이면 TRUE를 반환하고, lock이 이미 소유되면 FALSE를 반환한다. tight loop에서 이 함수를 호출하는 것은 CPU time 낭비 때문에 나쁜 생각이므로, lock_acquire()를 대신 사용하라.

line 6 : 실행중인 쓰레드가 lock을 소유하고 있으면 TRUE를 반환한다. 임의의 쓰레드가 lock이 있는지 test하는 기능은 없다. 호출자(caller)가 실행하기 전에 답이 바뀔 수 있기 때문이다.

Monitors

모니터는 세마포어나 록보다 높은 형태의 동기화이다. 모니터는 동기화되는 data와 모니터 록이라 부르는 lock, 그리고 하나 이상의 condition variables(조건 변수)로 이루어져 있다. 보호된 데이터에 접근하기 전에, 쓰레드는 우선 모니터 록을 얻어야한다. 이건 “모니터 안에 있다(in the monitor)”라고 불린다. 모니터 안에 있을 때, 쓰레드는 모든 보호받는 데이터에 대해 제어권을 가져서, 자유롭게 조사(examine), 수정(modify) 할 지도 모른다. 보호된 데이터로 접근이 완료되면, 모니터 록을 푼다(release)

조건 변수(condition variables)는 모니터에 있는 코드가 조건이 TRUE가 되길 기다리도록 만든다. 각 조건 변수는 추상적인 조건과 관련되어있다. 예를 들어, “어떤 데이터는 processing에 도착했다” 거나 “ 유저의 마지막 입력(keystroke) 이후 10초가 지나갔다”. 모니터 안에 있는 코드가 조건이 TRUE가 되길 기다릴때, 록을 풀고 조건에 신호가 가길 기다리는 연관된 조건 변수를 “기다린다.” 반면에, 만약 이 조건들중 하나가 TRUE가 되면, 그것은 대기자(waiter) 하나를 깨울 조건에 “신호를 보내거나(signals)” 조건들에게 모두 일어나라고 “방송(broadcast)”한다.

모니터에 대한 이론적인 프레임워크는 C.A.R.Hoare(영국의 컴퓨터학자)가 구성했다. 그들의 실용적인 사용은 후에 Mesa OS에서 정교해졌다. 조건 변수 타입과 함수는 include/threads/synch.h에서 선언된다.

struct condition; // 조건 변수를 선언
void cond_init (struct condition *cond); // 새로운 조건변수로 cond를 초기화
void cond_wait (struct condition *cond, struct lock *lock);
void cond_signal (struct condition *cond, struct lock *lock);
void cond_broadcast (struct condition *cond, struct lock *lock);

line 3 : atomically(원자적으로..? 자동적으로..?) 모니터 록을 풀고 cond가 어떤 다른 코드에게 신호를 받길 기다린다. cond가 신호를 받으면 반환하기 전에 록을 reacquire한다. 록은 이 함수를 호출하기 전에 hold 되야한다. 신호를 보내고 대기자를 깨우는 것은 atomic(?) operation이 아니다. 따라서 전형적으로 cond_wait()의 호출자(caller)는 대기가 끝나면 조건을 재확인하고, 필요하다면, 다시 기다려야 한다. 예시로 다음 section을 보면 된다.

line 4 : 만약 monitor lock lock에 보호받는 cond에 대기중인 어떤 쓰레드가 있다면, 이 함수는 그들중 하나를 깨운다. 기다리는 스레드가 없다면 아무 일 없이 리턴한다. lock는 이 함수 호출 전에 이뤄져야한다.

line 5 : monitor lock lock에 보호받는 cond에 대기중인 모든 쓰레드를 꺠운다. lock은 이 함수 호출 전에 이뤄져야 한다.

monitor type은 모니터 내에 mutual exclusion을 제공하는 프로그래머가 정의한 오퍼레이션 set이다.

또한 모니터 타입은 값이 그 타입의 instance의 state를 결정

Monitor Example

monitor의 고전적인 예시는 하나 이상의 “제작자(producer)” 스레드가 characters(글자)를 쓰고 하나 이상의 “소비자(consumer)” 스레드가 characters(글자)를 읽는 buffer를 다루는 것이다. 이걸 실행하기 위해, 우리는 monitor lock에다가 not_full, not_empty라고 부르는 두 condition variables가 필요하다.

// lock과 condition variables 초기화
char buf[BUF_SIZE]; 			/* Buffer */
size_t n = 0; 					/* 0 <= n <= BUF SIZE : 버퍼 안 글자들 크기 범위 */
size_t head = 0; 				/* 다음 쓸 글자의 buf index */
size_t tail = 0; 				/* 다음 읽을 글자의 buf index */
struct lock lock; 				/* Monitor lock */
struct condition not_empty; 	/* buffer가 비어있지 않을 때 신호 */
struct condition not_full; 		/* buffer가 꽉 차있지 않을 때 신호 */

void put (char ch) {
    lock_acquire (&lock);
    while (n == BUF_SIZE) 				/* buffer가 꽉 차있으면 넣을 수 없음 */
        cond_wait (&not_full, &lock);
    buf[head++ % BUF_SIZE] = ch; 		/* buffer에 ch 넣기 */
    n++;
    cond_signal (&not_empty, &lock); 	/* buffer는 이제 비어있다고 할 수 없음 */
    lock_release (&lock);
}

char get (void) {
    char ch;
    lock_acquire (&lock);
    while (n == 0) 						/* buffer가 비어있다면 읽을 수 없음 */
        cond_wait (&not_empty, &lock);
    ch = buf[tail++ % BUF_SIZE]; 		/* buffer에서 ch 꺼내기 */
    n--;
    cond_signal (&not_full, &lock); 	/* buffer는 이제 꽉 차있다고 할 수 없음 */
    lock_release (&lock);
}

위 코드가 완전히 올바르기 위해서 BUF_SIZE가 반드시 evenly(짝수로) 나누어져서 SIZE_MAX + 1 이 되는 것을 주목해라.

그렇지 않으면, head가 0 근처에서 처음 wrap하다가 실패할 것이다.

실제로, BUF_SIZE는 보통 2의 제곱 형태이다.

(원문 : Note that BUF_SIZE must divide evenly into SIZE_MAX + 1 for the above code to be completely correct. Otherwise, it will fail the first time head wraps around to 0. In practice, BUF_SIZE would ordinarily be a power of 2.)

Optimization Barriers(최적화 장벽)

최적화장벽은 특별한 ¹다. 최적화장벽은 컴파일러가 방벽 너머 메모리의 상태에 대해 가정하는 것을 방지한다. 컴파일러는 장벽 너머의 변수에 대해 또 다시 쓰거나 읽도록 요구하지 않을 것이고, 주소가 발생하지 않은 지역 변수를 제외하고는 장벽을 넘어서 변수의 값을 수정 불가능 하다고 가정하지 않을 것이다. Pintos에서, include/threads/synch.h는 optimization barrier로 barrier()매크로를 정의한다.

최적화 장벽을 사용하는 이유는 또다른 스레드나 interrupt handler 같이 컴파일러의 knowledge(지식?) 없이 데이터가 비동기적으로 변화할 수 있을 때에 있다. devices/timer.c안에 있는 too_many_loops()함수가 예시이다. 이 함수는 시간 측정(timer tick)이 발생하기 전까지 루프(loop)에서 busy-wating에 의해 발생한다.

/* timer tick 기다림 */
int64_t start = ticks;
while (ticks == start)
    barrier();

루프에 최적화 장벽 없으면 컴파일러는 start와 ticks동시에 시작하고 루프가 둘을 절대 직접 바꿀 수 없기 때문에 루프가 절대 종결되지 않을 것이라고 결론짓는다. 그러면 컴파일러는 바람직하지 않게 정의된 무한 루프 안으로 함수를 “최적화(optimize)”한다.

최적화 장벽은 다른 컴파일러의 최적화(optimization)를 피하기 위해 사용될 수 있다. 마찬가지로 devices/timer.c안에 있는 busy_wait() 함수가 예시다. 이 함수는 이 루프를 갖고 있다.

while (loops--> 0)
    barrier ();

이 루프의 목표는 원래 값에서 0으로 점차 계산해 내려감으로서 busy-wait하는 것이다. 장벽 없이, 컴파일러는 이 루프를 전체적으로 삭제할 수도 있다. 왜냐하면 루프가 유용한 output도, 부작용도 없기 때문이다. 장벽은 컴파일러에게 루프 body가 중요한 효과를 가지고 있음을 세뇌시킨다.(The barrier forces the compiler to pretend that the loop body has an important effect.)

마지막으로, 최적화 장벽은 메모리의 읽거나 쓰는 순서를 강제하기 위해 사용될 수 있다.(Finally, optimization barriers can be used to force the ordering of memory reads or writes.) 예를 들어, timer interrupt가 발생할 때마다 global Boolean variable(전역 불리언 변수)timer_do_put이 true라면 전역 변수 timer_put_char안의 글자(character)가 콘솔에 출력된다고 가정해보자. 출력할 x를 설정하는 최고의 방법은 최적화 방벽을 사용하는 것이다. 다음과 같다.

timer_put_char = 'x';
barrier ();
timer_do_put = true;

장벽 없이, 코드는 컴파일러가 operation이 똑같은 순서로 둬야 하는 이유를 찾지 못하면 자유롭게 재조정하기 때문에, buggy(수레?카트?)이다. 이 경우, 컴파일러는 과제(assignment)의 순서가 중요해서 optimizer가 그들의 순서를 바꾸길 허락받은 것을 모른다.그게 실제로 이걸 하는지에 관한 얘기는 없고, 다른 최적화 깃발이나 다른 버전의 컴파일러를 지나치는 것은 다른 동작(behavior)을 만들어 낼 것이다.

또 다른 해결책은 과제(assignment)주위로 disable interrupts 하는 것이다. 이것은 재조정을 방지하진 않지만, interrupt handler가 assignment 사이를 지나는 것은 막는다. 또한 disabling, re-enabling interrupts 에 대한 추가적인 실행 비용도 있다.

enum intr_level old_level = intr_disable ();
timer_put_char = 'x';
timer_do_put = true;
intr_set_level (old_level);

두번째 해결책은 timer_put_char와 timer_do_put을 volatile로 선언하는 것을 표시하는 것이다. 이 키워드는 컴파일러에게 변수들이 외부에서 보일 수 있고 최적화(optimization)의 latitude(구역)을 제한한다. 그러나 volatile는 의미론적으로(semantics) 잘 정의되지 않아서 일반적이고 좋은 방책은 아니다. 기초 Pintos 코드는 volatile을 전혀 사용하지 않는다.

다음 나오는 것은 록(locks)이 interrupts도, 컴파일러가 락이 있는(held) 지역에서 코드를 재조정(reordering) 하는 것도 막지 못했기 때문에 해결책인 코드가 아니다.

lock_acquire (&timer_lock); /* 부정확한 코드임 */
timer_put_char = 'x';
timer_do_put = true;
lock_release (&timer_lock);

컴파일러는 또 다른 소스 파일에서 최적화 장벽의 제한된 형태로써 외부적으로 정의된 어떤 함수의 발동을 treat한다.(다룬다? 치료한다?) 구체적으로, 컴파일러는 외부적으로 정의된 어떤 함수가 정적•동적 할당된 데이터와 주소가 발생한(taken) 어떤 지역 변수들에 접근할지도 모른다고 가정한다. 이것은 보통 명시적(explicit) 장벽이 생략될 수 있다는 것을 의미한다. Pintos가 명시적 장벽이 거의 없는 이유다.

같은 소스파일이나 소스파일이 포함시킨 헤더에서 정의된 함수는 최적화 장벽에 의존할 수 없다. 이것은 정의 전에 함수의 발동에도 적용되는데, 컴파일러가 최적화(optimization) 수행 전에 전체 소스 파일을 읽고 분석(parse)할지도 모르기 때문이다.

Race condition

예시

counter = 5

T0	PRODUCER	EXECUTE	REGISTER1 = COUNTER	{REGISTER1 = 5}
T1	PRODUCER	EXECUTE	REGISTER1 = (REGISTER1) + 1	{REGISTER1 = 6}
T2	CONSUMER	EXECUTE	REGISTER2 = COUNTER	{REGISTER2 = 5}
T3	CONSUMER	EXECUTE	REGISTER2 = (REGISTER2) -1	{REGISTER2 = 4}
T4	PRODUCER	EXECUTE	COUNTER = REGISTER1	{COUNTER = 6}
T5	CONSUMER	EXECUTE	COUNTER = REGISTER2	{COUNTER = 4}

우리는 두 과정들이 동시에 COUNTER 변수를 조작하도록 하였기 때문에 부정확한 상황에 도달하였음

다수의 프로세스들이 같은 데이터에 동시에 접근하여 조작하고 실행의 결과가 접근이 발생하는 특정 순서와 연관된 이러한 상황을

race condition 이라고함

Critical-Section Problem

\[{P_0,P_1,...,P_n}\]

위와 같은 n개 프로세스들로 구성된 시스템을 가정해보자.

각 프로세스는 critical section이라고 불리는 코드가 있는데, 프로세스가 공통변수(common variables)를 바꾸거나, 표(table)를 업데이트하거나, 파일을 쓰거나 하는 등의 코드의 세그먼트에 있다.

한 프로세스가 critical section을 실행할 때는, 다른 어떤 프로세스도 자신의 critical section을 실행할 수 없다.

즉, 두 개의 프로세스는 그들 자신의 critical section을 동시에 실행할 수 없다.

critical-section 문제는 프로세스들을 협동을 위해 사용하는 포로토콜을 고안하기 위함이다.

각 프로세스는 자신의 ciritcal section으로 들어가기 위해 허락을 요청해야만 한다.
이 요청을 수행하는 코드의 section을 entry section 이라고 한다.
critical section은 exit section을 바로 뒤에 둘 수도 있다.
남아 있는 코드는 remainder section 이라고 한다.

전형적인 프로세스의 일반적인 구조

do {
<entry section>

    	critical section

<exit section>

    	remainder section

} while (TRUE);

Critical section problem의 해결책이 만족해야 하는 3가지 조건

Mutual exclusion

프로세스 P가 자신의 critical section을 실행하고 있다면, 다른 어떤 프로세스도 자신의 critical section을 실행할 수 없다..

Progress

ciritical section을 실행하는 프로세스가 없고, 다수의 프로세스들이 자신의 critical section에 진입하길 원한다면, remainder 섹션을 실행하고 있지 않은 프로세스들만이 다음 critical section 진입에 대한 결정에 참여할 수 있고, 이 선택은 무기한하게 지연될 수 없다.
Bounded wating

프로세스가 critical section으로 진입을 요청한 후 부터 요청이 받아들여지기 전 까지 다른 프로세스들이 자신의 critical section에 진입하도록 허가되는 횟수는 bound(limit)가 있다.

Test and Set Lock

synchronization 문제를 해결하는 hardware solution
shared lock variable : 0 or 1
critical section 진입 전에, 프로세스는 lock에 대해 inquire 함.
locked(잠기면), free될 때까지 기다린다.
not locked, lock을 받고 critical section을 실행한다.

TestAndSet ()의 코드 정의

boolean TestAndSet(boolean *target){
    boolean rv= *target;
    *target = TRUE;
    return rv;
}

do { // process p1
while (TestAndSet (&lock));
// do nothing
// critical section
lock = FALSE;
// remainder section
} while(TRUE);

do { // process p2
while (TestAndSet (&lock));
// do nothing
// critical section
lock = FALSE;
// remainder section
} while(TRUE);

실행가능한 최소의 독립적인 코드조각. 컴파일러가 이해하고 실행할 수 있는 모든 구문. ↩

Pintos 1주차 Synchronization

정글일지 25