병행 프로세스와 상호배제

병행 프로세스

병행 프로세스

마치 프로세스 여러 개를 동시에 실행하는 것처럼 보이게 빠른 속도로 프로세스들을 번갈아 실행하는 것을 말한다.
시분할 시스템과 동일한 정의이지만, 병행 프로세스는 말 그대로 프로세스 그 자체를 의미한다. 병행되어(동시에 실행되는 것처럼 보이는) 프로세스를 말한다.

병행 프로세스의 종류

• 독립 프로세스
  다른 프로세스에 영향을 주고받지 않는 완전한 독립적인 프로세스를 의미한다.
• 협력 프로세스
  동일한 목표를 가진 다른 프로세스와 상호작용하며 수행되는 프로세스를 의미한다.
  ex- A 프로세스: 파일 읽기 B 프로세스: 파일 쓰기

병행 프로세스의 문제점

• 공유 자원을 상호 배타적으로 사용해야함. 한순간에 프로세스 하나만 사용해야함.
• 병행 프로세스간에 협력이나 동기화가 되어 있어야 함. 상호배제 또한 동기화의 한 형태.
• 프로세스간에 데이터를 교환할 수 있도록 통신되어야함.
• 교착상태를 해결해야함.

fork 와 join

• fork : 병행 프로세스를 2개 만든다.
• join : 병행 프로세스 2개를 하나로 결합한다.

상호배제와 동기화

상호배제(mutual exclusion, Mutex, 뮤텍스)

공유자원을 사용하는 프로세스가 있으면 다른 프로세스는 해당 자원을 사용하지 못한다.
둘 이상의 프로세스가 동시에 임계영역에 들어가는 것을 막는 것.

동기화(Process Synchronization)

공유자원을 동시에 사용 못하도록 제어하는 방법.
프로세스들이 서로 동작을 맞춰보고 정보를 공유하는 행위.
상호배제를 보장하지만, 교착 상태와 기아 상태가 발생할 수 있다.
여러개의 프로세스가 동작할 때 서로 동기화가 되어있지않으면 데이터에 일관성을 잃게 된다.

비동기적(Asynchronous)

프로세스들이 서로에 대해 모름.
병행 수행중인 비동기적 프로세스들이 공유자원에 동시 접근 할 때 문제가 발생할 수 있다.

임계 영역

• 임계 자원
  두 프로세스가 동시에 사용할 수 없는 공유 자원.
• 임계 영역
  임계 자원에 접근하고 실행하는 코드 부분.
  프로세스가 공통 변수를 읽고 테이블을 갱신하고 파일을 수정하는 등 공유 데이터에 접근할 때 임계 영역에 있다고 함.
  

임계 영역의 조건

• Mutual Exclusion(상호배제)
  하나의 프로세스가 critical section 코드를 실행 중 일때는 다른 모든 프로세스는 critical section 코드를 실행할 수 없어야 함.
• Progress(진행)
  임계 영역에 어떤 프로세스가 들어갈지 결정해야함. 아무도 critical section에 있지 않은 상태인데 어떤 프로세스가 critical section에 들어가고 싶어하면 들어가게 해줘야 함.
• Bounded Waiting(유한 대기)
  임계 영역을 무한정 기다리는 상황을 방지하기위해 임계 영역에 한 번 들어갔던 프로세스는 다음 차례까지 제한을 둠. 프로세스가 critical section에 들어가려고 요청을 보내면 일정 시간이 지나면 반드시 들어가야함. 계속해서 기다리게 하면 안됨.

경쟁 상태(Race Condition)

여러 프로세스가 동시에 공유 데이터로 접근할 때 순서에 따라 결과가 달라지는 현상. 여러 주체가 하나의 데이터에 접근하려 할 때 서로 경쟁하는 상태를 의미.

상황별 경쟁 상태 해결책

• 상황 1. 커널이 작업하는 중 인터럽트가 발생해 인터럽트 작업 내용이 저장 안되는 현상.
  해결책 1. 커널에서 작업 중일때 발생하는 인터럽트는 작업이 완료되면 인터럽트를 수행함.
• 상황 2. 프로세스가 시스템 콜을 하여 커널 모드로 작업 중인데 할당 시간이 끝나 context switch가 일어난 경우
  해결책 2. 커널 모드에서 수행 중일때는 CPU를 preempt(선점) 하지 않음.
• 상황 3. CPU가 여러개 있는 환경에서 여러 CPU가 같은 데이터에 접근한 경우
  해결책 3. 먼저 데이터에 접근한 CPU가 해당 데이터을 lock함. 또는 한번에 하나의 CPU만 커널에 들어갈 수 있음.

상호 배제 해결 방법

• SW solutions
  Dekker’s algorithm (Peterson’s algorithm)
  Dijkstra’s algorithm, Knuth’s algorithm, Eisenberg and McGuire’s algorithm, Lamport’salgorithm
• HW solution
  TestAndSet(TAS) instruction
• OS supported SW solution
  Spinlock
  Semaphore
  Eventcount/sequencer
• Language-Level solution
  Monitor

Two-Process의 상호배제 해결방법

데커의 알고리즘(Dekker's Algorithm)

2개의 프로세스 상호 배제 문제를 해결한 최초의 알고리즘.
while문을 통해 계속해서 임계 영역 진입 조건을 확인함.
flag : True이면 임계 영역에 진입하고 싶다는 의미.
turn : 임계 영역에 들어갈 프로세스 순서

알고리즘 해석

1. flag를 통해 임계영역에 진입하고 싶다는 의사를 표현.
2. 다른 프로세스들 중 flag가 True인 프로세스가 없다면 임계영역에 진입.
3. flag가 True인 프로세스가 있다면, turn을 확인해 자신의 turn일 경우 진입.
4. 자신의 turn이 아니면 while문을 돌면서 대기.
   

피터슨의 알고리즘(Peterson’s algorithm)

데커 알고리즘을 조금 더 간단하게 구현.
turn을 서로 양보해 가장 늦게 양보한 프로세스가 늦게 들어간다.
즉, 먼저 도착한 프로세스가 먼저 진입한다.

N-Process의 상호배제 해결방법

다익스트라(Dijkstra's Algorithm)

최초의 N개의 프로세스의 상호배제 문제를 해결함.
실행 시간이 가장 짧은 프로세스에 프로세서를 할당하는 세마포어 방법.
가장 짧은 평균 대기시간을 제공.
idle : 프로세스가 임계 영역 진입을 시도하고 있지 않을 때.
want-in : 임계 영역 진입 1단계일 때.
in-CS : 임계 영역 진입 2단계 및 임계 영역 내일 때.

알고리즘 해석

1. flag가 want-in이 되면 임계 영역에 진입하고 싶다는 의사 표현. 임계 영역 1단계가 됨.
2. turn이 내 순서가 아니라면 지금 순서인 프로세스가 끝나기를 기다렸다가 끝나면 turn을 내 순서로 바꿈.
3. flag가 in-CS가 되면 임계 영역 2단계가 되고 j라는 변수로 카운팅을 시작. 만약 in-CS 상태인 프로세스가 여러개이면, while문을 빠져나와 다시 1번 단계부터 시작.
   즉, in-CS 상태인 프로세스가 나 자신밖에 없어야 임계영역에 진입.
   

크누스(Knuth)

프로세스들이 아주 오래 기다려야함.

램포트(Lamport)

사람들이 붐비는 빵집에서 번호표를 뽑아 빵을 사려고 기다리는 사람들에 비유해서 만든 베이커리 알고리즘.
준비큐에 우선순위를 부여하여 우선순위가 높은 프로세스가 먼저 진입.

핸슨(Brinch Hansen)

대기시간과 실행시간을 이용하는 모니터 방법.

SW solutions 의 문제점

• 속도가 느림
• 구현 복잡함
• 실행 중 선점될 수 있음. 공유 데이터 수정 중에는 interrupt를 억제함으로서 해결이 가능하나 오버헤드가 발생하게 됨.
• Busy Waiting : 기다리는데 바쁜 상태로 기다리는 상태. while문이 계속 돌아가는 문제를 말함. 매우 비효율적.

TestAndSet(TAS) instruction

상호배제문제를 하드웨어적으로 해결하는 방법.
Test와 Set을 한번에 수행하는 기계어이기때문에 실행중 interrupt가 일어나도 선점되지않음.

알고리즘 해석

1. lock이 True면 임계영역에 다른 프로세스가 진입한 상황이므로 대기.
2. lock이 False가 되면 임계영역에 진입.
3. 임계영역에서 빠져나오면 j변수를 이용해 대기 중인 프로세스를 찾음.
4. 대기중인 프로세스가 없다면 lock을 false로 바꾸고 다른 프로세스가 진입할 수 있도록 함. 대기 중인 프로세스가 있다면 임계영역에 진입할 수 있도록 함.
   

HW solutions 의 문제점

• 구현이 간단하지만 Busy Waiting 문제를 해결하지 못했다.

Spinlock

S라는 정수형 변수를 사용하는 방식.
P(S), V(S) 연산으로만 임계영역에 접근이 가능함.
OS가 이 연산이 수행되는 동안에는 다른 프로세스가 선점하지 못하도록 보장해줌.
P(S) : 공유 자원을 획득하는 연산.
V(S) : 공유 자원을 반납하는 연산.

알고리즘 해석

1. 프로세스가 P(activate(=S))를 실행하여 activate(=S) 를 0으로 만들어 임계 영역에 진입.
2. 다른 프로세스가 임계 영역에 진입을 시도하지만 activate(=S)가 0인 상태이므로 대기.
3. i번 프로세스가 수행을 마치고 V(activate(=S))를 실행하면 activate(=S)는 다시 1.
4. 이제 j번 프로세스가 임계 영역에 진입.
   

Spinlock 문제점

멀티프로세서 시스템에만 사용 가능.
Busy waiting 문제가 해결되지 못함.

세마포어(Semaphores)

다익스트라가 제안한 방법.
준비 큐(여기서 말하는 큐는 FIFO 형식이 아닌듯..?)에 프로세스를 대기시키는 방식으로 Busy waiting 문제를 해결함.
OS가 이 연산이 수행되는 동안에는 다른 프로세스가 선점하지 못하도록 보장해줌.
S : 음이 아닌 정수형 변수
초기화 연산 : S에 초기값을 부여하는 연산.
P() : 임계 영역에 진입하는 연산.
V() : 임계 영역에 빠져나오는 연산

알고리즘 해석

1. 임계영역에 아무도 없다(S>0)면 S-1을 하고 진입.
2. 만약 임계영역에 다른 프로세스가 있다면 대기 큐(Q)에서 대기.
3. 임계영역에서 빠져나오면 대기 큐(Q)에 프로세스가 있다면 그 프로세스가 임계영역에 진입.
4. 없다면 S+1을 하고 다른 프로세스가 진입할 수 있도록 함.
   

세마포어로 해결가능한 동기화 문제

• 상호배제 문제
• 프로세스 동기화 문제
  프로세스에 순서가 있다면 가장 빠른 순서의 프로세스별로 큐에 들어가기때문에 프로세스들의 실행 순서를 맞출 수 있다.
  
• 생산자-소비자 문제(Producer-Consumer problem)
  생산자 : 메세지를 생성하는 프로세스 그룹
  소비자 : 메세지를 전달받는 프로세스 그룹
  순환큐(Circular Queue)=buffer : 생산한 데이터를 보관하는 곳
  in : 생산자가 메세지를 넣는 지점
  out : 소비자가 메세지를 빼는 지점

  알고리즘 해석

  1. 생산자는 P(nrempty)를 통해 buffer에 공간이 있는지 확인
  2. 공간이 없으면 큐에서 대기
  3. 공간에 메세지를 집어넣고 V(nrfull)를 수행하여 nrfull+1를 하여 채워진 buffer수를 업데이트함.
  4. 소비자는 P(nrfull)를 통해 버퍼에 메세지가 있는지 확인.
  5. 없으면 큐에서 대기.
  6. 있으면 P(nrempty)를 수행하여 nrempty+1를 하여 비어진 buffer수를 업데이트함.
     
• Reader-writer 문제
  Reader : 데이터에 읽기 연산만 수행. Reader들은 동시에 접근 가능
  Writer : 데이터에 갱신 연산 수행. Writer들(또는 Writer-Reader)은 상호배제(동기화)가 필요.
  Reader 또는 Writer에 우선순위를 부여한다.
• 철학자들의 저녁식사 문제(Dining philosopher problem)

세마포어의 문제점

준비 큐에서 대기하고 있는 프로세스 중 누가 먼저 임계영역에 들어갈 것인지에 대한 순서가 결정되지 못함. = 기아문제 발생할 가능성 있음.

Eventcount/Sequencer

은행의 번호표와 비슷한 개념.
Busy watiting을 해결한 개념.
준비 큐가 FIFO이기때문에 기아현상이 발생하지 않음.
세마포어보다 더 low-level를 컨트롤 할 수 있음.
S(equencer) : 정수형 변수. 생성시 0으로 초기화되며 은행의 번호표처럼 절대 감소하지 않음. 그래서 발생 사건들의 순서를 유지할 수 있음. 오직 ticket()연산으로만 접근 가능.
ticket(S) : 현재까지 ticket()연산이 호출된 횟수를 반환. 은행의 번호표와 동일한 개념.
E(ventcount) : 정수형 변수. 생성시 0으로 초기화되며 은행의 번호 알림판처럼 절대 감소하지 않음. 그래서 발생 사건들의 순서를 유지할 수 있음. read(E),advance(E),await(E,v) 연산으로만 접근 가능.
read(E) : 현재 E 값을 반환
advance(E) : E 값을 갖는 프로세스를 깨움.
await(E,v) : if (E<v)이면 큐에서 대기.

모니터(Monitor)

앞서 봐왔던 방식(Low-level)들을 너무 어렵고 복잡해서 사용하기가 어렵고 에러가 발생할 가능성도 있음.
모니터는 사용하는 언어(High-level)가 앞서 봐왔던 방식들을 쉽게 사용할 수 있도록 해줌.
모니터 내에는 항상 하나의 프로세스만 진입 가능함.(이것을 언어가 보장해줌.)
공유 데이터는 모니터 내의 프로세스만 접근 가능함.
Entry queue(진입 큐) : 모니터 내의 함수 만큼 존재
Condition queue(조건 큐) : 모니터 내의 특정 이벤트를 기다리는 프로세스의 대기실
Signaler queue(신호제공자 큐) : 모니터에 항상 하나의 신호제공자 큐가 존재. signal() 명령을 실행한 프로세스가 잠시 대기하는 공간. signal()은 조건 큐에서 대기하고 있는 프로세스를 깨워주는 신호. 이 신호를 받으면 조건 큐에서 대기하고 있는 프로세스가 모니터로 진입한다. 즉 이 큐는 전화부스이고 signal()은 전화를 거는 행위를 의미.

---

입출력의 처리

동기식 입출력(synchronous I/O)

I/O 요청 후 입출력 작업이 완료되어야 다음 작업을 수행할 수 있음.

• 구현 방법 1
  I/O가 끝날때까지 기다림으로서 cpu를 낭비시킴.
  하나의 I/O만 사용할 수 있음.

• 구현 방법 2
  I/O가 요청 후 완료될때까지 해당 프로그램에게서 cpu를 빼앗음
  여러 I/O를 사용할 수 있음.

비동기식 입출력(asynchronous I/O)

I/O가 시작된 후 완료될때까지 기다리지 않고 다음 프로그램에게 cpu를 넘김.

---

컴퓨터에서 데이터에 접근하는 방법

데이터를 저장된 위치에서 연산할 데이터를 읽어와서 연산을하고 그 결과를 다시 데이터가 저장된 위치에 저장함.