[OS] IPC

JUJU·2024년 3월 27일

OS

목록 보기

4/12

✏️ IPC

IPC: Inter Process Communication의 약자로, 프로세스 사이에 데이터를 교환하는 메커니즘을 가리킨다.

IPC의 방식은 유닉스 프로그래밍을 학습할 때 알아보았다.
IPC를 사용하면 프로세스간 데이터를 공유하는 등의 상호작용이 가능해진다.
문제는, IPC를 하는 중에, 즉 프로세스간 통신을 할 때 Race Condition이 발생할 수 있다는 것이다.

Race Condition이란, 둘 이상의 프로세스가 공유 자원에 동시에 접근하여 예상치 못한 결과를 초래하는 상황이다.

✏️ Race Condition

두개의 process(또는 Thread)가 동일한 shared Memory에 접근하려고 할 때 Race Condition이 발생한다.

A와 B가 동시에 0x07(Critical Region)에 write
뭐가 기록될까?
몰라
➜ 경쟁상황

■ 해결조건

동시에 들어가려고 하면 한명만 들어가게 하고, 끝나면 알려주도록 하자.

【 Race Condition 해결의 조건 】

Mutual Exclusion(상호 배제):
동시에 들어가려고 하면 한 명만 들어간다. 동시에 Critical Region에 들어갈 수 없다.
Progress(진행):
Critical Region에 아무도 안들어가 있으면 들어가야 한다.
Bounded Waiting:
기다리면 언젠가는 들어갈 수 있어야 한다.
자꾸 늦게 도착한 애가 먼저 들어가면 안된다.
CPU의 속도는 상관이 없어야 한다.

✏️ Busy Waiting

Race Condition의 해결 조건인 Mutual Exclusion을 성취하기 위해, Busy Waiting 방식을 사용해보자.

Busy Waiting이란?

특정 조건이 만족될 때까지 CPU를 계속 사용하며 대기하는 방식이다.

Busy Waiting 방식의 대표 사례들을 하나씩 살펴보자.

여기서 Lock이란, Race Condition을 해결하기 위한 공유 변수를 뜻한다.

Lock 변수가 0이면 Critical Region에 프로세스가 없다는 뜻이다.

Lock 변수가 1이면 Critical Region에 프로세스가 있다는 뜻이다.

들어갈 때 Lock 변수를 0 ➜ 1로 바꾸고 진입, 나올 때 1 ➜ 0으로 바꾸고 나옴

Lock만으로는 Race Condition을 해결할 수 없다.
따라서, Lock을 응용한 방식들을 사용한다.

■ Disabling interrupts

➜ Critical Region에 진입한 직후 모든 인터럽트를 막아버리고, 나올 때 다시 열어준다.

완벽한 솔루션인가?

mutual exclusion OK
progress OK
bounded Waiting NO

인터럽트를 비활성화하면 한 프로세스가 임계 구역을 점유하고 있는 동안 다른 프로세스는 무한정 대기해야 한다.

■ Strict alternation

공유 변수

turn = i
Critical Reigion: 공유변수 V 접근

while(TRUE){
	while(turn != i);
    V++ // Critical Region
    turn = j
}

turn이 가리키는 애가 들어간다.
turn != 자신이면 들어갈 수 없음

turn이 i가 될 때까지 roop를 돈다.
i가 되면 루프를 나와서 Critical Region에 들어간다.

나올 때 turn을 j로 바꿔준다.

완벽한 솔루션인가?

mutual exclusion OK
progress NO
bounded Waiting NO

1명만 Critical Region에 계속 접근하는 경우
➜ i가 쓰고 j로 바꿈. turn이 i가 될 때까지 기다리는데, 바꿔주는 사람이 없음

■ Dekker's solution

Lock 응용

turn이 가리키는 프로그램이 들어감

공유 변수

flag[i] = FALSE;
flag[j] = FALSE;
turn = i;
Critical Reigion: 공유변수 V 접근

// 사용을 원하는 경우 실행
flag[i] = TRUE; 
while(flag[j]) { // j도 쓰고 싶다면?
	if(turn == j) {	// j의 턴이면 양보할게
    	flag[i] = FALSE;
        while (turn == j); // j가 끝날 때까지 대기
        flag[i] = TRUE;
    }
} 

V++ // Critical Region

// 사용이 끝난 후
flag[i] = FALSE;
turn = j;

i가 들어가고 싶으면 flag를 TRUE로 바꿈
j의 flag를 봄.
j가 false먄 Critical Region 진입
나올 때 flag를 false로 하고 turn을 j로 바꿈

서로 같이 들어가려고 하면?
turn이 가리키는 애가 먼저 들어가자.

완벽한 솔루션인가?

Mutual Exclusion OK
Progress OK
Bounded Waiting OK

■ Peterson's Solution

Dekker를 조금 바꿈

turn이 가리키는 프로그램이 양보

공유 변수

flag[i] = FALSE;
flag[j] = FALSE;
turn = i or j;
Critical Reigion: 공유변수 V 접근

flag[i] = TRUE; // 나 쓰고 싶어
turn = i; // 근데 같이 들어갈거면 내가 양보할게

while(flag[j] && turn == i); 
// j의 flag가 꺼져 있으면 바로 들어감
// j의 flag가 켜져 있고 turn이 i면 양보함

V++; // Critical Region

flag[i] = FALSE // 사용 끝

i가 사용하고 싶으면 flag[i] = TRUE + turn = i로 (같이 들어가고 싶으면 내가 양보할게)

turn은 i 아니면 j임 (동시에 i,j일 수는 없음)
초기 turn 값이 j이고, i와 j가 동시에 들어가고 싶어한다 가정

flag[i] = TRUE
turn = i
i는 while을 빠져나와서 critical region에 들어감

작업을 마치고 flag를 false로

완벽한 솔루션인가?

mutual OK
progress OK
Bounded Waiting OK

⚠️ 코드 하나만 바꿔도 작동하지 않으므로 주의
ex) turn의 위치만 바꿔도 mutual 안됨

Peterson Solution에서 Turn은 항상 양보여야 한다.

실제 코드로 작성하면 작동할까?

Peterson Solution은 이론적으로 성공적인 솔루션이다.
하지만, 실제 코드로 작성하면 잘 작동하지 않는다.

그 이유는, CPU가 자주 쓰는 변수를 레지스터에 저장하기 때문이다.

turn이 CPU의 레지스터에 잡힌다.
turn 값은 레지스터에서 변경하고 메모리에는 적지 않는다.
따라서, 실제로는 Mutual Exclusion이 안된다.

해결방법

volatile 이라는 키워드를 작성해서 변수를 선언해야 한다.
해당 변수를 변경하면 레지스터에서 변경한 후에 반드시 메모리에 작성한다.

⚠️ Dependency가 없으면 슈퍼스칼라로 동시에 명령이 실행되기 때문에 Mutual Exclusion이 안될 수도 있다.
➜ Barrier를 사용한다.

⚠️ 위의 솔루션들은 Process가 2개일 때만 작동, 3개부터는 작동 안함

➜ Bakery Algorithm을 사용한다.

■ Bakery Algorithm

3개 이상의 Process에서도 작동하는 솔루션이다.

빵집 알고리즘: 번호표를 받음
우연히 똑같은 번호표를 받으면?
PID를 보고 작은애가 먼저 들어가자.

전제 조건

Definition of (a,b) < (c,d)
a < c면 true
a == c일때 b < d 이면 true

공유 변수

choosing[0] ~ choosing[n-1] = FALSE
number[0] ~ number[n-1] = 0
Critical Reigion: 공유변수 V 접근

choosing[i] = TRUE; // 번호표 받고 싶어

number[i] = max(number[0], number[1], ... , number[n-1]) + 1; // 번호표 할당
choosing[i] = FALSE; // 번호표 받았어

for(t=0;t<n;t++){ // 내 번호표와 n-1개의 번호표 비교
	if(t == i) continue; // 내 번호면 패스
    
    while(choosing[t]) // t번째 프로세스가 번호표 뽑는 중이면 대기
    
    while((number[t] != 0) && ((number[t],t) < (number[i],i))); // 번호표 비교 + PID 비교
}
// 내 번호가 가장 작으면 빠져 나옴

V++; // Critical Region 진입

number[i] = 0; // 번호표 0으로 반납

choosing true-> 번호표 받고 싶어

number-> 번호표

내 번호표가제일 작을 때까지 기다림
number[0]~num[n-1]까지 보면서 루프
나랑 같은게 있어?
-> PID까지 비교
-> PID가 작은 프로세스가 먼저 사용

완벽한 솔루션인가?

mutual OK
progress OK
Bounded Waiting OK

임계 구역에 이런 방식으로 들어가는거는 너무 복잡해!
-> 새로운 명령을 하나 만들자.

■ TSL instruction

소프트웨어적으로 해결하는게 너무 어려워서 만든 하드웨어적 해결 방법
CPU에 만드는 명령어이다.

// 새로운 명령어 정의
enter_region:
	TSL REGISTER, LOCK // lock을 읽어서 레지스터에 저장하고, (메모리)lock을 1로 설정 해둠
    CMP REGISTER, #0 // lock(레지스터)이 0인가?
    JNE enter_region // IF NOT EQUAL, 1이라는 뜻 == 누군가 쓰고있다는 뜻
    // 따라서 enter_region으로 돌아가 루프를 돈다.
    RET // 임계구역 진입

leave_region:
	MOVE LOCK, #0 // (메모리)lock에 0을 저장
    RET // 리턴

핵심은 TSL 명령어이다!

Test와 Set을 atomic하게 동시에 실행하는 명령이다.
lock을 레지스터에 저장하고, (메모리)lock을 1로 설정하는 명령이다.
하나의 연산이므로, 연산 중간에 process switch 할 수 없다.

TSL instruction의 다른 버전인 XCHG instruction도 존재한다.

// 새로운 명령어 정의
enter_region:
	MOVE REGISTER, #1 // 레지스터에 1 저장
    XCHG REGISTER, LOCK // 레지스터의 값과 lock 변수의 값을 변경
    CMP REGISTER, #0 
    JNE enter_region 
    RET

XCHG를 사용하면 Lock을 0과 1이 아닌 다른 수로 저장할 수 있다.

✏️ Lock-free Data Structure

스레드 2개 정도까진 TSL로 Lock을 써도 되는데 스레드가 수십개가 되면 스레드가 계속 기다려야 하는 상황이 발생함.
➜ 대기 없이 공유 변수를 바꾸자!
공유 변수를 바꾸기 직전에 내가 가진 값과 비교해서, 누군가 먼저 바꾸었는지 체크하자

■ Compare-And-Swap

Lock-free 자료구조를 구현하기 위해 CPU 안에 Compare-and-Swap이라는 명령어를 만든다.

void CAS(int *sharedVar,int oldValue,int newValue)
// 이 명령을 실행할 때 lock 시그널을 뿌려서 다른 프로세스가 접근할 수 없게 만든다.

CAS 명령어를 사용해서 새로운 함수를 정의한다.

int AtomicAdd(int *sharedVar, int add){
	int old;
    do{
    	old = *sharedVar;
    } while(!CAS(*sharedVar, old, old + add))
    return old;
}

위 함수의 실행 과정은 다음과 같다.

sharedVar가 가리키는 변수 값을 읽는다.
해당 값을 old에 저장한다.
CAS명령어 실행
- old와 공유변수의 값이 같은지 비교한다.
만약 값이 다르다면, 다른 스레드가 그 사이에 변경한 것이다.
- false 반환
값이 같다면, old+add 값을 공유변수에 저장한다.
- true 반환

Lock을 사용하지 않아도 된다.

■ ABA Problem

CAS를 사용하다보니까 계속 오류가 나는 문제가 발생한다.
왜 그럴까?
➜ ABA Problem

ABA Problem은 공유 객체에 대한 변화를 감지하지 못해서 발생하는 문제이다.

CAS 명령어를 사용한 LinkedList 연산을 보자.

thread1: CAS(&head, A, B)
A node를 delete하고 B로 head를 바꾸려 한다.
thread1은 현재 head를 A, next를 B로 저장하고 있을 것이다.

위의 연산을 어셈블리로 바꾸면 Push B, Push A, Push @head, Call CAS 이런식으로 동작한다. push와 CAS 명령 사이에 다른 Thread가 접근한다면 어떻게 될까?

thread2: pop(A), pop(B), push(A)
thread2는 그 사이에 A와 B를 pop하고, 다시 A를 push하는 명령을 수행한다.

다시 thread1으로 돌아와서, thread1은 CAS 명령을 마무리하기 위해, head가 A가 맞는지 체크한다.
thread2가 A를 다시 push했기 때문에 head는 A가 맞다. 하지만, 다음 노드는 B가 아닌 C이다.

이것이 바로 ABA Problem이다.

해결책은 &head의 포인터 뿐만 아니라 카운터값도 보는 것이다.

✏️ Sleep And Wakeup

Busy Waiting은 Critical Region에 들어갈 수 있을 때까지 루프를 돈다.
➜ CPU 낭비
Busy Waiting은 우선 순위 역전 문제가 발생할 수 있다.

∴ Critical Region에 들어갈 수 없으면 Sleep 하고, 들어갈 수 있을 때 다른 프로세스에서 깨워주자.

Sleep:
호출자를 block 상태로 만든다.
Wakeup:
인수로 준 프로세스를 깨워서 ready 상태로 만든다.

■ Producer-Consumer Problem

Producer: 큐에 아이템을 넣음
Consumer: 큐에서 아이템을 꺼내옴

Sleep and Wakeup으로 이 문제를 해결해보자.

// 공유변수
#define N 100
int count = 0 // 큐에 있는 아이템의 개수

//Producer

int item;

while(TRUE){
	item = produce_item();
    if(count == N) sleep(); // 큐가 꽉차면 프로듀서는 슬립
    insert_item(item); // 큐에 아이템을 넣음
    count++; // 큐에 존재하는 아이템 수를 하나 증가시킴
    if(count == 1) wakeup(consumer); // 0에서 1로 증가시켰다면 컨슈머를 깨워야 함
}

//Consumer

int item;

while(TRUE){
    if(count == 0) sleep(); // 소비할 게 없으면 sleep, 누군가 깨워줄 것이다.
    item = remove_item(); // 일어나서 큐에서 아이템 가져옴
    count = count - 1; // 큐에 존재하는 아이템 수 하나 감소
    if(count == N-1) wakup(producer); // count가 99라는 뜻은, 방금전까지 큐가 full이었단 뜻. 일 안하고 있는 producer 깨움
    consume_item(item) // print
}

⚠️ Producer와 Consumer가 영원히 Sleep하는 상황이 발생 가능하다.

해결 방법

Mutual Exclusion과 Synchronization이 필요함

Critical Region(위의 예시에서 count)에 들어갈 수 있는 프로세스는 하나
프로세스끼리 정보를 공유한다. (상태 공유 ready인지 block인지)

✏️ Semaphore

Semaphore는 다익스트라가 제안한 새로운 변수 타입이다.

Semaphore 변수는 Lock 변수보다 high level의 개념이다.
Semaphore는 방법이나 기법이 아니다. 그저 변수일 뿐이다!
집중해야 할 것은 Sempahore를 연산하는 방법인 PV 연산이다.

Semaphore 변수는 커널에 저장되어 있다.
System Call을 통해 접근 가능하다.
Semaphore 변수의 PV 연산은 Atomic하다.

■ PV 연산

Semaphore 변수를 컨트롤하는 PV 연산에 대해서 알아보자.
Sleep And Wakeup 기법을 사용한다.

// 예시 Semaphore 변수
struct semaphores[
	int count; // 임계구역에 동시에 들어갈 수 있는 프로세스 수
    QueueType queue;
}

// p 연산 (down)
// wait(semaphore s)과 동일
// count 값을 하나 낮춘다.

void down(semaphore s){
	s.count--; // 임계 구역에 들어가고 싶어
    if(s.count < 0) {
    	// 이 코드가 실행 된다는 것은, 임계 구역에 들어갈 수 있는 프로세스 수가 다 찼다는 뜻.
        sleep();
    }
}

/*
또는 이러한 정의도 가능하다.

void down(semaphore s){
	if(s.count > 0)
    	s.count--; 
    else
    	sleep();
}
*/

// v 연산 (up)
// signal(semaphore s)과 동일
// count 값을 하나 증가시킨다.

void up(semaphore s){
	s.count++; // 임계 구역 다 썼어
    if(s.count <= 0) {
    	// 이 코드가 실행 된다는 것은, 임계 구역에 들어가고 싶은 프로세스가 대기중이라는 뜻
        wakeup(대기중인 프로세스);
    }
}

/*
또는 이러한 정의도 가능하다.

void up(semaphore s){
	if(한 개 이상의 프로세스 대기중)
    	wakeup
    else
    	s.count++;
*/

up 연산을 할 때, 대기 중인 프로세스가 있다면 그 프로세스를 깨운다.
이 때, 깨워주는 프로세스는 세마포어를 증가시키지 않는다.

어차피 깨어난 프로세스가 임계구역에 들어갔다 나올 때 증가시킬 것이다.

PV 연산은 Atomic 하다.
Semaphore 변수를 사용해서 동기화를 제공할 수 있다.
PV 연산을 사용해서 Mutual Exclusion을 제공할 수 있다.
Down ➜ Critical Region ➜ UP

■ Producer-Consumer Problem

Semaphore를 사용해서 Producer-Consumer 문제를 해결해보자.

공유 변수

#define N 100
semaphore mutex = 1; // Mutual Exclusion 용 세마포어
semaphore empty = N; // 큐 내부 빈 공간 수
semaphore full = 0; // 큐 내부 아이템 수

Producer

void producer() {
	while(TRUE) {
    	item = produce_item();
        
        down(&empty); 
        // empty에 접근, 아이템 넣을 예정이니 하나 내림.
        // 0이면 빈 공간이 존재하지 않으므로 sleep됨
        
        down(&mutex); 
        // mutex에 접근, 임계지역에 들어가기 위해 하나 내림
        // 0이면 누가 큐를 사용중인 거니 sleep됨
        
        insert_item(item); // 임계지역
        
        up(&mutex);
        // 임계 지역 나옴
        // 대기하고 있는 프로세스가 있으면 깨워줌, 이 경우 본 프로세스는 mutex를 증가시키지 앟음
        // 어차피 대기하고 있는 프로세스가 실행 끝낸다음에 mutex를 증가시킬거임
        
        up(&full);
        // full에 접근, 아이템 넣었으니 하나 올림
        // 대기하고 있는 프로세스가 있으면 깨워줌, 이 경우 본 프로세스는 full을 증가시키지 앟음
        // 어차피 대기하고 있는 프로세스가 실행 끝낸다음에 full을 증가시킬거임
    
}

Consumer

void consumer() {
	while(TRUE) {
    	down(&full);
        down(&mutex);
        
        item = remove_item();
        
        up(&mutex);
        up(&empty);
        
        consume_item();
    }
}

Mutual Exclusion과 Synchronization을 다 확보한 solution이다.

Mutual Exclusion -> mutex 세마포어가 담당
Synchronization -> empty, full 세마포어가 담당

✏️ Mutex

Mutex is a simplified version of the Semaphore

Semaphore를 사용하려면 시스템 호출을 써야한다.
따라서 전혀 다른 프로세스끼리 동기화가 가능하다.

하지만, 시스템 호출은 운영체제에 부탁해야 하므로 속도가 느리다!

하나의 프로세스에서 여러 쓰레드끼리 상호작용 할 때 Semaphore를 사용할 수 있지만, Mutex가 더 빠르다.
하지만, Mutex 연산은 동기화는 하지 못한다.

■ 특징

Mutex 타입 변수는 0과 1만 값으로 가질 수 있다.
Mutex 변수가 0이다
== Unlock 상태
== 임계 구역 사용 가능
Mutex 변수가 1이다
== lock 상태
== 임계 구역 사용 불가

Mutual Exclusion만 하고 sleep wakeup은 하지 않는다.

-> condition 변수를 사용
-> sleep & wakeup을 매개시켜주는 변수

■ 연산

Mutex도 결국엔 변수일 뿐이다.
집중해야 할 것은 Mutex를 어떻게 다룰 것인지이다.

Mutex를 사용해서 Mutual Exclusion을 달성해보자.

mutex_lock:
	TSL REGISTER, MUTEX // MUTEX를 읽어서 레지스터에 저장하고, (메모리)MUTEX 1로 설정 해둠
    CMP REGISTER, #0 // MUTEX(레지스터)가 0인가?
    JNE ok // unlock 상태면 ok로 점프
    CALL thread_yield // 0이 아니면, 다른 스레드가 MUTEX를 쓰는중
    // 본 스레드는 ready로 감. 스케줄링 시간이 지나 다시 Running이 되었을 때 재시도 할 수 있음
    JMP mutex_lock // 재시도
    
ok: RET // 임계 구역 들어가게 리턴

mutex_unlock:
	MOVE MUTEX, #0 // (메모리) MUTEX에 0 저장
    RET

TSL의 enter_region이랑 똑같은거 아닌가?

enter_reion은 Busy Waiting이다!
mutex_lock은 임계 구역에 못들어가면 yield(양보) 해서 CPU를 다른 스레드가 쓰게 해준다.

✏️ Monitors

Monitors는 Mutual Exclusion과 Conditional Synchronization을 제공하는 ADT이다.
(추상화된 데이터 형식인데, 객체라고 이해하면 편하다)

Semaphore는 사용이 어려워..
➜ 컴파일러가 Mutual Exclusion을 제공해줬으면 좋겠다!

컴파일러는 Monitor를 통해 Mutual Exclusion을 제공한다.

■ 특징

Monitor 객체 안에는 메소드와 Condition 타입의 변수가 존재한다.
한 순간에 하나의 프로세스만이 모니터의 메소드를 실행할 수 있다.
프로세스가 공유 자원에 접근 하는 방법은, 모니터 내의 메소드를 통하는 방법 밖에 없다.

class Monitor {
	condition full, empty;
    int count;
    
    public synchronized void producer( ... );
    public synchronized void consumer( ... );
}

// ADT인 Monitor를 자바 클래스로 구현한 것이다.
// synchronized가 붙은 메소드는 동시 실행 불가하다.
// 따라서, 상호배제는 컴파일러 수준에서 가능하다.
// 동기화는 구현해주어야 한다.

Monitor의 producer(), Consumer() 메소드는 동시에 실행될 수 없다.
즉, 상호배제는 컴파일러 수준에서 가능
⚠️ sleep & wakeup은 만들어줘야 한다.

■ Condition 변수

Semaphore의 PV 연산 없이 Producer-Conumer Problem 같은 문제를 Monitor로 해결하고자 한다.

Mutual Exclusion은 컴파일러가 보장한다.(Mutex)
큐가 꽉차서 Producer 프로세스를 막아야 하는 문제가 발생하면 어떡하지?

세마포어에서는 down(&empty) 을 사용해서 꽉 찬 상태면 sleep시켰다.
Monitor에서는 Condition 타입의 변수에 연산을 적용해서 Sleep & Wakeup을 구현한다.

Condition 타입 변수는 값을 담기위한 용도가 아니라, 프로세스를 변수에서 대기하게 만드는 용도로 사용한다.
Condition 타입 변수 empty와 full이 존재한다고 가정하자.

Condition empty;
Condition full;

Semaphore 타입 변수에 적용할 수 있는 PV 연산이 있듯이, Monitor의 Condition 타입 변수에는 wait, signal 연산이 존재한다.

wait(c); // 호출한 프로세스를 조건 변수 C에서 대기하도록 만든다.
signal(c); // 변수 c에서 대기중인 프로세스가 있으면 wait()를 호출한 프로세스 중 하나를 실행
// 모니터 객체를 사용하는 프로세스는 1개이어야 하므로, signal()을 호출한 프로세스는 바로 모니터에서 나간다.

Sleep & Wakeup 구조와 비슷하지만, Race Condition은 발생되지 않는다.
컴파일러가 Mutual Exclusion을 보장한다!

■ Hoare's Monitor

ADT, 즉 추상적인 Monitor 개념을 실제로 구현한 예시들을 살펴보자.

Hoare's Monitor는 깨워준 프로세스가 block 되고, 깨어난 프로세스가 바로 실행된다.

깨어났다는 것은 if문으로 걸었던 조건이 사라졌다는 것

public synchronized void producer(val){
	// --------- Critical Region -----------
    // 하지만, synchronized로 Mutual Exclusion이 보장되기 때문에 신경쓸 필요 없음
    
	if(count == N)
    	cwait(notfull); 
    // cwait 메소드로 인해 block 상태가 됨
    // 나중에 깨어나면 if문 조건이 사라졌다고 판단하고 아래의 로직 실행
    
    buffer[nextin] = val; // 원형 큐에 데이터 저장
    nextin = (nextin + 1) % N // 원형 큐의 다음 위치로 이동
    count++;
    csignal(notempty); // notempty condition으로 자고 있던 프로세스 깨워줌
}

만약, 깨워준 프로세스가 계속 실행한다면, 실행하는 동안 조건이 훼손될 가능성이 있음
∴ 대부분의 경우 Hoare 거를 사용함

■ Lampson & Redell's Monitor

Lampson & Redell's Monitor는 깨워준 프로세스가 계속 실행하고 깨어난 프로세스는 while문으로 계속 조건 검사

public synchronized void producer(val){
	while(count == N)
    	cwait(notfull);
    ...

✏️ Message Passing

producer Consumer를 Message Passing으로도 구현할 수 있다.
Mutual Exclusion 뿐만 아니라 정보 교환도 된다.

send(threadId(dest), message)
receive(threadId(src), message)

send는 Nonblocking - 전달하고 자기 할 일 하면됨
receive는 blocking - 받고 처리해야됨
: 제일 많이 씀

■ Addressing

threadId 대신 pid를 지정하고 싶어.
근데 pid는 동적으로 할당되는 거라서 불가능하다.

-> indirect Addressing (메일 박스)
Port 번호로 send, receive

indirect Addressing은 1 to 1, n to 1, 1 to n, n to n 가능

Producer-Consumer

Consumer는 producer한테 빈 메시지 100개 보냄

✏️ Barrier

여러개 명령이 동시에 실행됨
mfence 같은 특별한 명령
앞에 명령이 모두 쓰인 다음에 뒤에 명령을 실행해라.

REFERENCE

📚 Modern Operating Systems, Third Edition - Andrew S. Tanenbaum

JUJU

개발자 지망생

이전 포스트

[OS] Processes and Threads

다음 포스트

[OS] IPC

OS

✏️ IPC

✏️ Race Condition

■ 해결조건

✏️ Busy Waiting

Busy Waiting이란?

■ Disabling interrupts

■ Strict alternation

공유 변수

■ Dekker's solution

공유 변수

■ Peterson's Solution

공유 변수

실제 코드로 작성하면 작동할까?

해결방법

⚠️ 위의 솔루션들은 Process가 2개일 때만 작동, 3개부터는 작동 안함

■ Bakery Algorithm

3개 이상의 Process에서도 작동하는 솔루션이다.

전제 조건

공유 변수

■ TSL instruction

TSL instruction의 다른 버전인 XCHG instruction도 존재한다.

✏️ Lock-free Data Structure

■ Compare-And-Swap

■ ABA Problem

CAS 명령어를 사용한 LinkedList 연산을 보자.

✏️ Sleep And Wakeup

■ Producer-Consumer Problem

⚠️ Producer와 Consumer가 영원히 Sleep하는 상황이 발생 가능하다.

해결 방법

✏️ Semaphore

■ PV 연산

■ Producer-Consumer Problem

공유 변수

✏️ Mutex

■ 특징

■ 연산

TSL의 enter_region이랑 똑같은거 아닌가?

✏️ Monitors

■ 특징

■ Condition 변수

■ Hoare's Monitor

■ Lampson & Redell's Monitor

✏️ Message Passing

■ Addressing

Producer-Consumer

✏️ Barrier

REFERENCE

[OS] Processes and Threads

[OS] Scheduling

0개의 댓글

관련 채용 정보