Process Synchronization

Process Synchronization

 

 자원에 대한 프로세스 간 경쟁에서 발생하는 제어문제

- 상호배제(mutual exclusion)

   process synchronization

- 교착상태(deadlock)

- 기아상태(starvation)

  starvation -> solution : aging

  Race Condition

 다수의 프로세스나 스레드가 공유자원을 동시에 읽거나 쓰려고 하는 상태

 Race condition이 발생하면, 최종 수행 결과는 프로세스들의 수행 순서에 따라 달라진다.

  OS에서 race condition은 언제 발생하는가?

 1. Kernel 수행 중 인터럽트 발생 시

    커널모드 running 중 interrupt가 발생하여 인터럽트 처리루틴이 수행 - 양쪽 다 커널 코드이므로 kernel address space 공유. disable/enable interrupt를 통해 커널 데이터 사용시에만(나머지는 상관없다.) interrupt 걸지 않게끔 하는 방법. 

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

    두 프로세스의 address space 간에는 data sharing이 없음. 그러나 system call을 하는 동안에는 kernel address space의 data를 access하게 됨.(share) 이 작업 중간에 CPU를 preempt 해가면 race condition 발생. -> timer가 되도 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않음.(timer 조금 안맞아도 별 영향x) 커널 모드에서 사용자 모드로 돌아갈 때 preempt

 3. Multiprocessor에서 shared memory 내의 kernel data

    어떤 CPU가 마지막으로 count를 store 했나? -> race condition.  multiprocessor의 경우 interrupt enable/disable로 해결되지 않는다. -> 1. 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법(문제: 반대쪽 CPU가 공유 데이터 쓰지 않을건데도 커널에 못들어간다.) -> 2. 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 하는 방법.

 Process Synchronization 문제

 - 공유 데이터의 동시 접근은 데이터의 불일치문제를 발생시킬 수 있다.

 - 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘 필요.

 - race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다.

 The Critical-Section Problem

 - n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우, 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재한다.

 - Problem : 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

  프로그램적 해결법의 충족 조건

 - Mutual Exclusion : 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.

 - Progress : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면, critical section에 들어가게 해주어야 한다.

 - Bounded Waiting : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.(유한대기 - 만약 while문이면 반복으로 계속 커널 왔다 갔다하니 그 횟수를 제한.)

  

  Semaphore

 - Semaphores are a kind of generalized lock

 - Semaphore S : 정수값. 연산 P, V를 가지고 있음. 공유자원을 획득 & 반납.

   1. Integer variable(자원의 개수)

   2. 두 가지 atomic 연산에 의해서만 접근 가능.

   3. 변수 S는 CPU 내에서 3단계에 걸친 업데이트가 아닌 CPU 한 클락에 업데이트 되는 특별한 변수. 

   P 연산 : 락을 거는 부분. 세마포어 변수값(공유자원)을 획득하는 부분.(lock)

   V 연산 : 락을 푸는 부분. 반납하는 부분.(unlock)

   세마포어는 추상자료형이다. - object + operation. 논리적으로 정의.

   Two Types of Semaphores

  - Counting semaphore : 도메인이 0 이상인 임의의 정수 값. 주로 resource counting에 사용. 자원의 갯수가 여러개, 여분의 자원을 세는 용도로 사용.

  - Binary semaphore(=mutex) : 0 또는 1 값만 가질 수 있는 semaphore. 주로 mutual exclusion (lock/unlock)에 사용.

   

  Block/Wake up Implementation

 - Semaphore를 다음과 같이 정의

   typedef struct

   {

int value;     //semaphore

struct process *L;   // process wait queue  (세마포어를 갖지못한 프로세스들의 큐. block 상태.)

   }

 - block : 커널은 block을 호출한 프로세스를 suspend 시킴. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음

 - wakeup(P) : block된 프로세스 P를 wakeup시킴. 이 프로세스의 PCB를 ready queue로 옮김.

   Busy-wait vs Block/wakeup

   Block/wakeup overhead vs Critical section 길이

 - Critical section의 길이가 긴 경우 Block/Wakeup이 적당

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

 - 일반적으로는 Block/wakeup 방식이 더 좋음

   

  Deadlock

 - 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상. ex) 상대 프로세스가 가진 자원을 기다리면서 자신의 자원을 반환하지 않아 서로 기다리는 상태.

  Starvation

 - 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상.

  Classical Problems of Synchronization

 - Producer-Consumer Problem with a bounded buffer

   Producer : 공유버퍼에 공유데이터 입력

   Consumer : 공유버퍼에 공유데이터 출력

   Need synchronization to coordinated producer/consumer - 버퍼가 full인지 empty인지 -> binary 세마포어.  자원이 얼마나 남았는지 -> integer 세마포어

 - Readers and Writers Problem

   데이터를 읽고 쓸때.(DB아니고선 발생할 일 별로 없음.)

   Solution : writer가 DB에 접근허가를 아직 얻지못한 상태에서는 모든 대기중인 reader들을 다 DB에 접근하게 해준다.

                writer는 대기중인 reader가 하나도 없을 때 DB접근이 허용된다.

     writer가 DB에 접근중이면 reader들은 접근이 금지된다.

     writer가 DB에서 빠져나가야만 reader의 접근이 허용된다.

 - Dining-Philosophers Problem

   ex) 밥을 먹으려는데 (다섯명) 숟가락이 네개. 한명은 계속 못먹을수도 있다.

   Philosophers Constraints : Five philosophers(process) sitting at a table. Doing one of two things - eating or thinking. Eat하려면 반드시 양쪽 젓가락을 가져야함.

   모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우, Deadlock 가능성이 있다.

   Solution : 4명의 철학자만 테이블에 동시에 앉을 수 있도록 한다. 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.  비대칭(자원 획득 순서 정해주기) - 짝수 철학자는 왼쪽 젓가락부터 집도록

  

  Semaphore의 문제점

 - 코딩이 힘들다

 - 정확성 입증이 어렵다

 - 자발적 협력이 필요하다

 - 한번의 실수가 모든 시스템에 치명적 영향을 미칠 수 있다.

 ===>  Monitor

 - 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct. 모니터 코드엔 공유 데이터 접근을 위한 프로시저가 정의되어 있다. 프로시저는 동시에 실행이 되지 않게하고, 모니터 안에 다 있기 때문에 굳이 lock을 걸 필요가 없다.

 - 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능하다.

 - 프로그래머가 동기화 제약 조건을 명시적으로 코딩 할 필요가 없다.

 - Condition variable : 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 사용. lock은 필요없으나 자원을 가져오려는 작업은 필요하다. 세마포어 변수와 비슷한 역할, but 값을 가지는 것은 아니다.(카운트x)  wait와 signal 연산에 의해서만 접근이 가능하다.

 x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기전까지 suspend된다. (프로세스->sleep. 세마포어에서의 block)

 x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다. (sleep 상태의 프로세스 -> wake up)