[OS] 병행제어

데이터의 접근

Race Condition

• 하나의 공유 데이터를 여럿이 동시에 접근하려고 할 때 생기는 문제

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

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

Solution

• 해결책 커널의 공유 변수 Count 변수를 건드리기 전에 인터럽트 디스에이블하고 끝나면 다시 인에이블하는 방식

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

• PA가 CPU를 잡고 user mode에서 실행이 되다가 시스템 콜을 해서 kernel mode로 들어와서 kernel의 데이터인 counter 변수 값일 증가시키는 와중에 context switch가 발생

3. Multiprocessor에서 shared memory 내의 kernel data

• 방법 1은 많은 오버헤드 발생하게 됨 -> 방법 2가 좋은 방법임

Process Synchronization 문제

• 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있음
• 일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 매커니즘 필요
• Race condition
  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
• race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 함

The Critical-Section Problem

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

Problem

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

Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 P0, P1
• 프로세스들의 일반적인 구조

do{
  entry section
  critical section
  exit section
  remainder section
} while(1);

• critical section에 접근하기 전에 entry section에서 lock 걸고, exit section에서 lock을 해제
• 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있음
  -> synchroniztion variable

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

아래 Algorithm들이 만족해야할 조건들

• Multual Exclusion (상호 배제)
  • 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안됨
• Progress (진행)
  • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 함
• Bounded Waiting (유한대기)
  • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야함

Algorithm 1

do {
  while(turn != 0); /* My turn? */
  critical section
  turn = 1;         /* Now it's your turn */
  remainder section
} while(1);

• critical section에 들어가기 전에 내 차례인지를 체크하다가 차례가오면 critical section에 들어가서 공유 코드를 수행하고 끝나면 차례를 상대방 차례로 바꿔줌
• turn을 둬서 동시에 critical section에 들어가는 문제는 해결하였지만 반드시 순서를 교대로 들어가야(swap-turn) 하는 문제점 발생
  • turn을 내 차례로 바꿔줘야만 critical section에 들어갈 수 있음
  • 상대방이 critical section을 사용하지 않으면 차례가 돌아오지 않음
• 원하든 원하지 안든 무조건 차례가 오면 critical section에 들어가게 됨

Multual Exclusion은 충족하였지만 Progress는 충족하지 못함

Algorithm 2

do {
  flag[i] = true;   /* Pretend I am in */
  while (flag[j]);  /* Is he also in? then wait */
  critical section
  flag[i] = false;  /* I am out now */
  remainder section
} while(1);

• Pi가 flag[i]를 들어서 critical section에 들어가고 싶다는 의사를 표현 후 Pj의 flag[j]의 상태를 확인하고 만약 끝났으면 flag[j] 깃발을 내리게 되고 flag[i]가 들어가게 됨
• 서로 깃발만 들고 있다가 CPU를 뺏겨 서로 양보하는 상황 발생
  • Progress 문제 발생

Multual Exclusion은 충족하였지만 Progress는 충족하지 못함

Algorithm 3 (Peterson’s Algorithm)

do {
  flag[i] = true;   /* My intention is to enter ... */
  turn = j;         /* Set to his turn */
  while (flag[i] && turn == j);  /* wait only if ... */
  critical section
  flag[i] = false;
  remainder section
} while(1);

• 깃발을 통해서 들어가겠다는 의사를 표현하고 상대방이 깃발을 들고 있는지 확인
• 동시에 깃발을 든 상황에서는 turn을 이용해서 정해줌
• Bysy Waiting (= spin lock)
  • CPU와 memory를 사용하면서 기다리는 문제 발생 -> 비효율적

Synchroniztion Hardware

Semaphores

P 연산 : 자원을 획득하는 과정 = lock 과정 V 연산 : 자원을 반납하는 과정 = unlock 과정

Two Types of Semaphores

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

Semaphores

• 일종에 추상 자료형

P(S) : 공유데이터를 획득하는 과정

V(S) : 공유데이터를 반납하는 과정

Deadlock and Starvation

Deadlock

• 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
  • P0입장에서는 Q를 못얻고 P1입장에서는 S를 계속 못 얻는 상황
  • 프로세스들은 P연산으로 자원을 한번에 얻고 V연산으로 한번에 반납을 함
  • P0와 P1은 S와 Q를 동시에 얻어서 동시에 반납
• S와 Q가 1로 초기화된 semaphore

Starvation

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

Classical Problem of Synchronization

• Bounded-Buffer Problem (Producer-Consumer Problem)
• Readers and Writers Problem
• Dining-Philosophers Problem

Bounded-Buffer Problem (Producer-Consumer Problem)

Producer Process에게는 Empty 버퍼가 자원, Consumer Process에게는 Full 버퍼가 자원이다.

Shared data(공유 데이터)

• buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)
  • 공유 데이터에는 lock을 걸어서 동시 접근을 막아야함

Synchroniztion variables

• mutual exclusion -> Need binary semaphore(shared data의 mutual exclusion을 위해)
  • binary semaphore를 통해 자원을 lock/unlock 함
• resource count -> Need integer semaphore(남은 full/empty buffer의 수 표시)
  • counting semaphore를 통해 자원의 수를 셈

Code

• semaphore full = 0, empty = n, mutex(lock/unlock을 위한 변수) = 1

Readers-Writers Problem

• 한 process가 db에 write중일 때 다른 process가 접근하면 안 됨
• read는 동시에 여럿이 접근해도 됨

Solution

• writer가 db에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들을 다 db에 접근하게 해줌
• writer는 대기 중인 reader가 하나도 없을 때 db 접근이 허용된다
• 일단 writer가 db에 접근중이면 reader들은 접근이 금지된다.
• writer가 db에서 빠져나가야만 reader의 접근이 허용된다.

Shared data

• DB 자체
• readcoun : 현재 DB에 접근 중인 Reader의 수

Synchroniztion variables

• mutex : readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용한다.
• db : reader와 writer가 공유 db 자체를 올바르게 접근하게 하는 역할을 한다.

Code

• Shared data
  • int readcount = 0;
  • DB 자체;
• Synchronization variables
  • semaphore mutex = 1, db= 1;
• writer가 먼저 도착했을 지라도 reader가 계속 들어온다면 starvation 문제가 발생할 수 있음

Dining-Philosophers Problem

앞의 solution의 문제점

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

해결 방안

• 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 함
• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 잇게 함
• 비대칭
  • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록함

Code

Monitor

Semaphore의 문제점

• 코딩하기 힘듬
• 정확성(correctness)의 입증이 어려움
• 자발적 협력(voluntary cooperation)이 필요
• 한번의 실수가 모든 시스템에 치명적 영향

Monitor

• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

reference

운영체제 - 이화여자대학교