💡 데이터의 접근
데이터는 저장되는 곳(Memory)과 실행되는 곳(CPU)이 별도로 존재
1. 데이터는 스토리지에 저장
2. 실행되는 곳으로 이동
3. 연산 실행
4. 연산 결과를 다시 스토리지에 저장

✅ Execution Box : CPU, 컴퓨터 내부, 프로세스
✅ Storage Box : Memory, 디스크, 프로세스의 주소공간

Race Condition

• Storage-box를 공유하는 Execution-box가 여럿 있는 경우
  
  [사진 출처 - 이미지 속]

즉!

• 여러 프로세스들이 동시에 데이터에 접근하는 상황에서,
  어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황

➡️ 데이터의 불일치 문제를 발생시킬 수 있음

언제 발생?

• kernel 수행 중 인터럽트 발생 시
• Process 가 system call을 하여 kernel mode로 수행중인데,
  context switch 가 일어나는 경우
• Multiprocesser에서 shared memory 내의 kernel data

무슨소리냐구~?~?~??
하나씩 살펴보자

1. kernel 수행 중 인터럽트 발생

• 의도된 동작 :
  count++, count--로 본래 값으로 돌아와야 함
  
  
• 의도와 다른 동작 :
  기존 값이 10이라고 하자.
  1️⃣ 커널의 Load가 수행되어 10이 load됨.
  2️⃣ interupt 발생
  3️⃣ 10 → 9
  4️⃣ 의도대로라면 9에서 1을 더해야 하지만,
  이미 1️⃣번에서 10이라는 값이 로드되었기 때문에
  10+1 == 11 이 저장됨.

Kernel address space 공유

kernel 사이의 context switch 상황임.
즉, 둘다 커널 코드 == 같은 address space를 공유하기 때문에 일어난 문제

Soultion

커널 모드의 수행이 끝나기 전에는 인터럽트를 받지 않도록 하는 방법(disable/enable)으로 해결!

2. Process가 system call을 하여 kernel mode로 수행중인데, context switch가 일어나는 경우

• 두 프로세스의 주소공간에서는 데이터를 공유하지 않음
• ‼️ 하지만 system call 하는 중에는 커널 주소공간의 데이터에 접근하게 됨
  == share
• 이 작업 중간에 CPU를 preempt 해가면 race condition이 발생하는 것!

Solution

커널 모드에서 수행중일 때는 CPU를 preempt 하지 않는다.
커널 모드에서 사용자 모드!로 돌아갈 때 preempt

3. Multiprocesser에서 shared memory 내의 kernel data

• 어떤 CPU가 마지막으로 count 값을 store했는가에 따라
  결과값이 달라짐
• Multiprocessor의 경우 interrupt enable/disable로 해결 되지 않음.
  (각 CPU가 독립적으로 움직이니까)

Solution

1. 한번에 하나의 CPU만 커널에 들어갈 수 있게 함
   ➡️ 비효율적임. 사용❌
   ➡️ 두 프로세서가 다른 데이터에 대해 접근한거면, 사실상 race condition 발생하지 않기 때문
2. 커널 내부에 있는 각 공유 데이터에 접근할 때마다
   그 데이터에 대해 lock/unlock

✏️ 정리하자면

• 공유 데이터의 동시 접근은 데이터 불일치를 야기시킬 수 있음.
• 따라서 데이터의 일관성 유지를 위해
  협력 프소세스 간의 실행순서를 정리해주는 매커니즘이 필요하다.
• race condition 상황에서 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에따라 달라진다.
• 이러한 race condition을 막기 위해서 concurrent process는 동기화(synchronize)되어야 한다.

The Critical-Section Problem

❓ Critical Section
코드 상에서 Race condition이 발생할 수 있는 특정 부분
== 공유 데이터를 접근하는 코드 부분

➡️ 하나의 프로세스가 critical section에 있을 때,
다른 모든 프로세스는 critical section에 들어갈 수 없어야 함.

문제 해결 조건

모든 프로세스의 수행 속도는 0보다 크다.
프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
고 가정함

1. Mutual Exclusion (상호배제)
   프로세스 P1이 critical section 부분을 수행 중이면,
   다른 모든 프로세스들은 그들의 critical section으로 들어가지 ❌
   
   
2. Progress (진행)
   아무도 critical section에 있지 않은 상태에서,
   critical section으로 들어가고자 하는 프로세스가 있다면 들어가게 해줌
   
   
3. Bounded Waiting (한정대기)
   프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지
   다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 함
   → 기다리는 시간이 무한하면 ❌

Solution

• 두개의 프로세스 P0, P1가 있다고 가정

do {
	entry section
    critical section //shared variable 접근 부분
    exit section
    remainder section
} while(1);

➡️ 프로세스들은 수행의 동기화 == 상태공유 를 위해
몇몇 변수를 "공유"할 수 있다
이렇게 공유할 수 있는 변수를 synchronzation variable이라고 함

Algorithm 1

현재 Critical Section에 들어갈 프로세스가 어떤 프로세스인지를 하나의 변수로 나타내어 일치하는 프로세스만 진입하도록 하자!

//P0의 turn의 값은 0
P1의 turn 값은 1 이라고 하자. 
do {
	while(turn != 0); // P0 : My turn??
    critical section 
	turn = 1;         // P0 : Now It's your turn!
    remainder section
} while(1);

이 알고리즘은
프로세스가 반드시 한번씩 교대로 들어가야 함
현재 프로세스(P0)가 변수 turn의 값을 다음 프로세스 값(P1)으로 바꿔줘야만! 다음 프로세스 들어갈 수 있음.

Ex.
P0의 remainder section 수행 시간이 매우 길어서 여전히 remainder section에서 수행 중이고,
P1이 수행을 한번 마치고 다시 Critical Section으로 진입하려고 한다면
turn == 0이기 때문에 진입할 수 없다.
(P0이 turn값을 1로 바꿔줘야하거든~)
➡️ Critical Section에 아무런 프로세스가 존재하지 않는 상황!


즉!!
⭕️ Mutual exclusion 은 만족하지만
❌ Progress는 만족하지 못함

Algorithm 2

특정 프로세스가 Critical Section에 진입할 준비가 되었다는 것을 나타내는 변수를 두어,
다른 프로세스가 Critical Section에 진입하려고 한다면 현재 프로세스는 기다리는 방법

do {
	flag[0] = true;		// Pretend I'm in
	while(flag[1]); 	//  Is he also in? then wait. .
    critical section 
    
	flag[0] = false;	//I'm out
    remainder section
} while(1);

두 프로세스가 flag = true까지만 수행하고 나면 두 프로세스 모두 무한히 Critical Section에 진입하지 못하고 기다리는 상황이 발생

즉, 얘도
⭕️ Mutual exclusion 은 만족하지만
❌ Progress는 만족하지 못함

Algorithm 3 -Peterson's Algorithm

알고리즘 1과 2를 합쳐놓은 개념
turn 변수와 flag 변수를 동시 사용

do {
	flag[0] = true;	// P0 들어가고자 함
    turn = 1;	// P1 turn
	while (flag[1] && turn == 1);	// P1이 들어가고자 하고, P1 차례라면 
    								// P0는 wait
    critical section
    flag[0] = false;
    remainder section
} while(1);

• P0은 flag[0] = true로 바꾸면서 Critical Section에 진입하고자 함
• 그리고 turn = 1로 바꿔주면서 P1이 들어가게 한다.
• 만약 P1이 들어가고 싶고 (flag[1] == true),
  현재 P1이 Critical Section에 들어가 있으면 (turn == 1)
  기다린다.
  그렇지 않으면 P0이 들어간다. 
• 그리고나서 Critical Section을 빠져나오면 들
  어가고 싶지 않다고 flag[0] = false로 바꿔준다. 

⭕️ Mutual Exclusion,
⭕️ Progress,
⭕️ Bounded waiting
모두 만족함

하지만 문제는 있음!
‼️ Busy Waiting
계속 CPU와 메모리를 사용하면서 기다림

그러면!
이 복잡한 코드 구현들이 하드웨어/소프트웨어 측면에서 어떤 지원들이 제공될까?

Synchronization Hardware

하드웨어적으로 현재 상태를 확인하고 변경하는 test & modify를
atomic(하나의 operation인것처럼)하게 수행할 수 있도록 지원하는 경우,
앞의 문제는 간단히 해결!
(많은 시스템들은 이러한 하드웨어적인 지원을 제공하고 있음)

이전까지의 알고리즘들은 데이터를 읽고 쓰는 것을 하나의 명령어로 처리할 수 없기 때문에 복잡해진 것
➡️ 메모리에서 데이터를 읽으면서 쓰는 것까지 하나의 명령어로 동시에 수행이 가능하다면 코드가 훨씬 간결해짐

이는 Test_and_Set을 이용하여 아래와 같이 구현됨

// Synchronization Variable
boolean lock = false; 

do {
	while (Test_and_Set(lock));	// busy waiting
    critical section	// lock -> TRUE. false 전까지 계속 수행
    lock = false;	// SET
    remainder section
}

하지만
‼️ 이러한 하드웨어적인 명령어는 bounded waiting 조건을 만족하지 못하는 단점 있음

Semaphores

추상 자료형

왜 사용함?
lock/unlock 방식을 간단하게 프로그래머에게 제공할수도 있음
공유자원을 획득하고 반납하는 것을 세마포어로 처리 가능

Busy Waiting 방식 구현

✅ 비효율적

Semaphores S

• 정수 값 == 공유 자원의 개수
• 아래의 두 가지 amtomic 연산

• P(S) - 공유자원 획득

	while (s<=0) do no-op; // wait
	S--;
	// if S is positive, decrement & enter.
	// otherwise, wait until positive (busy-wait)

• V(S) - 공유자원 반납

S++;

Block-Wakeup 방식

Block
프로세스가 "suspend" 되고
이 프로세스의 PCB를 세마포어에 대한 wait queue 에 넣음

Wake up
block된 프로세스를 wakeup
이 프로세스의 PCB를 ready queue오 옮김

Semaphores S

• 정수 값
  ➡️ 여기서는 "상황임"
  ➡️ 음수 : 자원을 기다림
  양수 : 자원을 기다리지 않고 누가 쓰고 있음
  즉, 누군가 깨워야할 것이 있는지 없는지를 판단하는데 사용함

• P(S) - 공유자원 획득

S.value--;	
    if (S.value < 0) {
    	add this process to S.L;	// wait queue에 linked list 연결
        block();	// suspend
    }

• V(S) - 공유자원 반납

	S.value++;
    if (S.value <= 0) {
    	remove a process P from S.L;
        wakeup(P);
    }

Busy Waiting VS Block-Wakeup

일반적으로 Block-Wakeup 방식이 더 좋긴 한데,,,
그렇다고 무조건은 아님!

왜?
Block-Wakeup 방식은 오버헤드가 발생함.

즉. Critical section의 길이가 매우 짧은 경우!
Block-Wakeup의 오버헤드가 busy-wait 오버헤드보다 커질 수도 있음

Semaphore 종류

• Counting semaphore
  도메인이 0 이상인 임의의 정수값
  → resource counting에 사용
• Binary semaphore
  0 or 1 값만 가질 수 있음
  → mutual exclusion(lock/unlock)에 사용
  
  

Deadlock & Starvation

세마포어의 문제 상황

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상 (상호교차적)
➡️ 반드시 starvation 유발함

• S, Q: 1로 초기화된 semaphore
  

P0는 S를 잡고 한없이 Q를 기다리고
P1은 Q를 잡고 한없이 S를 기다림

(사실 이 경우, 자원의 순서만 맞춰주면 됨
P1의 자원 순서를 Q→S에서 S→Q로)

Starvation

자원을 얻지 못해서 무한히 기다림

여기서는
특정 프로세스들만 자원을 공유하면서 다른 프로세스들은 자원을 쓰지 못하는 상황을 의미!

Process Synchronization의 고전적 문제

세가지가 있음

• Bounded-Buffer Problem
• Readers-Writers Problem
• Dining-Philosophers Problem

자세히 살펴보장!

Bounded-Buffer Problem

‼️ 문제 상황

생산자 스레드들과 소비자 스레드들이 있고, 사이에 공유 버퍼가 있다고 가정하자!

만약

• 둘 이상의 생산자가
  비어있는 버퍼를 동시에 보고 데이터를 만들어 넣는다면 문제가 발생할 수 있음
• 둘 이상의 소비자가
  동시에 동일한 버퍼의 데이터를 사용한다면 문제가 발생할 수 있음

➡️ 따라서, 동시에 버퍼에 접근할 수 없도록 락을 걸어줘야 한다.

또,

• 버퍼가 꽉 찬 상태에서 생산자는 반드시 소비자가 버퍼의 데이터를 사용하기를 기다려야 하고,
• 버퍼가 빈 상태에서 소비자는 생산자가 버퍼를 채우기를 기다려야 한다.

해결

✅ 여기서 세마포어를 사용하자.

1. binary semaphore
   producer와 consumer가 동시에 공유 buffer 접근 막기 위해
   공유 buffer 전체에 lock/unlock을 걸어 배타적 접근
   
   
2. integer semaphore
   buffer가 비었을 때 producer or consumer가 내용을 만들거나
   꺼내갈 buffer가 없으면 가용자원의 개수 count

Readers-Writers Problem

한 프로세스가 데이터를 수정(Write)하는 작업을 수행할 때 다른 프로세스가 접근하면 안 되고,
읽는(Read) 작업은 여러 프로세스가 동시에 수행 가능하도록 하는 문제

이를 위해

• 데이터에 대해 하나의 lock을 사용하게 되면
  ⭕️ 데이터의 일관성은 지킬 수 있으나,
  ❌ 여러 프로세스가 동시에 읽을 수 있음에도 불구하고 한 프로세스만 읽도록 강제하는 것이므로 비효율적 

해결

• 현재 수정(Writer)하려고 하는 프로세스가 없다면,
  대기 중인 모든 Reader 들의 접근을 허용하고,
• Writer는 대기 중인 Reader가 하나도 없는 경우
  접근하도록 함!
• Writer가 접근 중이면 Reader들은 접근할 수 없도록!

→ 만약 n개의 reader가 기다리고 있다면, 제일 처음 reader만 wrt 세마포어에 넣고 나머지 n-1개의 reader는 mutex 세마포어 큐에 넣어둠으로써 효율성을 높여줌

Starvation

위 해결 방법은 Starvation의 가능성이 있음.
계속해서 reader가 들어오거나 writer가 들어오는 경우 한쪽이 계속 수행되지 않을 수 있기 때문
➡️ 이는 큐에 우선순위를 부여한다거나, 일정 시간이 지나면 자동으로 write or read가 되도록 하여 해결 가능~~~

Dining-Philosophers Problem

참 재밌는 이름이지요~

• 5명의 철학자가 원탁에 둘러앉아있고, 젓가락은 5개만
• 각 철학자는 식사를 하기를 원하고, 철학자가 식사를 하기 위해서는 양쪽 젓가락을 모두 집어야 함

💡 해결방법 1

// initially all values are 1
// 동시에 둘이 젓가락을 잡을 수 X. 무조건 한 명만.
semaphore chopsticks[5];	


do {
	P(chopstick[i]);
    P(chopstick[(i+1) % 5];		// 요로케 양 옆 젓가락 확보
    ...
    eat();						// 밥 먹기 
    ...
    V(chopstick[i]);			
    V(chopstick[(i+1) % 5];		// 두 젓가락 놓음
    ...
    think();
    ...
} while(1);

➡️ 이웃한 두 철학자가 동시에 먹는 경우가 없다는 것이 보장

위 알고리즘의 문제

• Deadlock
  만약 모든 철학자가 식사를 하기를 원해서 각자 왼쪽에 있는 젓가락을 들었다면, 더 이상 아무런 작업도 수행할 수 없음

💡 위 문제점 해결방법!

• 4명의 철학자만이 테이블에 동시에 앉도록!
• 젓가락을 두 개 집을 수 있을 때만 젓가락을 집도록!
• 짝수/홀수 철학자는 왼쪽/오른쪽 젓가락을 먼저 집도록!
  하는 방법으로 해결가넝~

// 상태. 공유 변수
enum { thinking, hungry, eating } state[5];	
// 다섯 명의 철학자가 젓가락을 두 개 다 잡을 수 있어서 잡을 권한을 줄것인가 여부. 
semaphore self[5] = 0;	 // 0 => 없음 / 1 => 있음
// lock
semaphore mutex = 1;	



Philosopher i:
	do {
    	pickup(i);
        eat();
        putdown(i);
        think();
    } while(1);
    



void putdown(int i) {
	P(mutex);
    state[i] = thinking;
    test((i+4) % 5);
    test((i+1) % 5);
    V(mutex);
}

void pickup(int i) {
	P(mutex);	// lock
    state[i] = hungry;
    test(i);
    V(mutex);
    P(self[i]);
}


// i가 젓가락 두 개를 다 잡을 수 있는 상태인지 test
void test(int i) {
	// (i+4) % 5 : 왼쪽 철학자 eating X
    // (i+1) % 5 : 오른쪽 철학자 eating X 
    // hungry : 내가 지금 배고픈 상태
	if (state[(i+4) % 5] != eating && state[i] == hungry && state[(i+1) % 5] != eating) {
    	state[i] = eating;
        V(self[i]);	// 젓가락 잡는 권한 부여
    }
}

---

Reference

KOCW 공개강의 (2014-1. 이화여자대학교 - 반효경)
[운영체제(OS)] 6. 프로세스 동기화(Process Synchronization)
[운영체제] 6. Process Synchronization