[2019.06.27] Concurrency : Mutual Exclusion and Synchronization

CPU 하나가 여러개의 프로그램을 동시다발적으로 진행.

하나의 processor (CPU) 에 producer processes와 consumer process가 가동된다.
Producer/Consumer Problem
 하나 이상의 Producer가 data 만들고 buffer에 저장함. 하나의 consumer는 buuffer에서 하나씩 가져옴. 한번에 오직 하나의 consumer or producer 만이 buffer에 접근할 수 있다.
Producer/Consumer : Finite Buffer
 main memory에 shared memory 공간을 할당해 변수들을 저장한다. (shared data) -> 동시에 producers, consumer가 접근할 수 있다.
 - Producer Process

1	item v;
2	while (1) {
3		while (counter == BUFFER_SIZE);
4		b[in] = v;
5		in = (in+1) % BUFFER_SIZE;
6		counter++;
7	}

   4~6 부분은 critical section 이다. critical section은 shared resource에 접급하여 값을 변경하는 statement이다. 다른
  process가 critical section에 있을 때는 실행하지 않는다. -> 한번에 오직 하나의 program 만이 critical section에 있을 수 있다.
 - Consumer Process

1	item w;
2	while (1) {
3		while (counter == 0);
4		w = b[out];
5		out = (out+1) % BUFFER_SIZE;
6		counter--;
7	}

   현재 예시에선 consumer가 하나이다. 그래서 conumser내에서 쓰이는 out이 critical section에 포함되지 않는다.
  여기서 critical section은 5번째 줄이다. counter는 producer와 같이 값을 쓴다.

- Race Condition in a Uni Processor
   IPC using a shared memory
   Race Condition : 다수의 thread 또는 process가 shared data item을 읽고 쓰는 데 실행 타이밍에 따라 되어 경쟁한다.
   예를 들어, counter++;이나 counter--;를 실행할 때 mutual exclusion을 위해서는 atomic하게 실행되어야 한다. 일반적으로는
  한문장 실행하고 interrupt 확인하고, 한 문장 실행하고 interrupt 확인하고 ... 이렇게 실행된다. atomic 하게 실행한다는 것은
  끊김없이 한 문장 끝나고 interrupt이 와도 처리하지 않고 다음 문장을 실행하는 것이다. 
   그러니까 counter++을 lower language로 보면

load register, counter	(register <- counter)
increment register	(register <- register+1)
store register, counter	(counter <- register)

  이렇게 세문장이 나오는데 atomic하게 실행되면 이 세문장이 끊김없이 한 단위로 다 실행이 된다.
   Race Condition의 예시로 위의 Producer, Consumer 코드를 보자면,
  1. Producer가 buffer에 item을 넣고 counter를 5라 했을 때,
     load register, counter   (register <- counter=5)
     increment register       (register = 6)
  2. 이때 time slice 만료되어 (clock interrupt) CPU가 counsumer로 dispatch되었다.
     load reigster, counter   (register <- counter=5)
     decrement register      (register = 4)
     store register, counter (counter = 4)
  3. time slice 만료로 CPU가 다시 producer.
     store register, counter (counter <- 6)
   최종적으로 counter의 값이 4아님 6이다. 이러한 race condition이 일어나지 않으려면 mutual exclusion이 필요하다. (서로
  겹치게 실행되지 않아야 한다.)

- Race Condition 방지
 * critical section을 atomic 하게 실행한다.
   하지만 critical section이 긴 경우에는 그동안 interrupt을 막으므로 문제가 생길 수 있다.
 * critical section 주위에 fence를 만든다.
   atomic하게 실행하는 것이 아니라 겹쳐서 실행하는 것을 막는다. fence 안에 들어갈 수 있는 것은 하나의 process.

- Critical Section Problem
  n 개의 process들이 shared data를 사용하는 경쟁을 한다. 그리고 각 process는 그에 접근할 수 있는 critical section
 코드가 있다. 한 process가 critical section을 실행 중 일때 다른 process는 허용되지 않도록 확실히 해야한다.
  해당 문제가 이루고자 하는 것은 Mutual Exclusion (한 process가 critical section에서 실행 중일 때 다른 process는 접근하지
 못하게 하는 것), Progress (critical section에 process가 없을 때, 원하는 process가 알아서 critical section에 들어가는 것.),
 Bounded Waiting (critical section에 process가 있을 때 기다리는 것) 이다.
  * Software solution : critical section 전에 담장 역할을 하는 entry section, 후에 exit section 코드를 추가한다. process들은
   해당 수행을 동기화 하기 위해 변수를 공유한다. 하지만 코드에 문제점이 있어 Hardware solution 개발.
  * Hardware solution : OS 개발자가 testset이라는 특수한 함수를 만들어 critical section으로 묶고 atomic 하게 실행한다고
   지정함. 오래 걸리지 않음. 그래서 program에서는 critical section 전에 testset을 호출해 담장 역할을 한다 내가 들어갈 수
   있나 없나는 검사한다. 들어오면 critical section을 실행하는 데 이때는 atomic하게 실행하지 않는다. 어차피 하나만 담장을
   통과해서 실행하고 있는 것이기 때문. 하지만 Deadlock이 발생할 수 있다. P1이 critical section에 있는데 time slice 되어 새로
   생긴 P2를 실행하는 데 얘가 우선 순위가 더 높다. 그러면 section에 들어갈 권한은 없지만 CPU는 P2가 계속 가지고 계속
   서로가 기다리게 된다.

- Semaphore : 공유 자원을 써도 되는 지 확인해주는 신호
  Signaling을 위해 semaphore라는 변수가 사용된다.
  semWait(s)는 semaphore s 의 값을 감소시킨다.
  semSignal(s)는 semaphore s의 값을 증가시킨다.
  이 두 함수는 atomic하게 수행된다.
  semaphore를 바구니라 하면 바구니 안에 돌이 있어야 내가 공유 자원을 써도 되는 신호구나 하고 바구니에서 돌을 빼고
 (semWait)쓰면 된다. 다 쓰고 나면 바구니에 돌을 넣느낟. (semSignal) 그래서 돌을 빼려고 했는데 돌이 없으면 blocked 된다.
  semaphore를 쓰면 mutual exclusion, bounded waiting이 제공된다. 또한 P3가 CPU를 가지고 있으면 얘가 critical section에
 들어가는 것을 아무도 막을 수 없다. -> Progress 제공.
  * Synchronization Tool로써의 semaphore
   실행 순서를 맞춰준다. 예를 들어, 내가 항상 A가 끝난 후 B가 실행되도록 한다면 A의 끝에 semSignal(flat), B의 앞에
  semWait(flag)를 하면 B는 semWait가 끝나면 실행되므로 A가 끝나고 semSignal이 실행되기 전까지 실행이 안된다.

- Message Passing
 mutual exclusion을 강화하는 또 다른 방법.
 send(dest, msg), receive(src, msg)