# 공유자원과 임계영역

# 공유 자원(Shared resource)

시스템 안에서 각 프로세스, 스레드가 함께 접근할 수 있는 모니터, 메모리, 파일 등의 자원이나 변수 등을 의미합니다.

공유 자원을 두개 이상의 프로세스가 동시에 읽거나 쓰는 상황을 '경쟁 상태(Race Condition)'라고 합니다. 이러한 공유 데이터에 대한 동시 접근은 데이터의 일관성(Consistency)를 해치는 결과를 낳을 수 있어서, 프로세스 간의 동기화가 필요합니다.

# 임계 영역(Critical Section)

공유 자원에 접근할 때 순서 등의 이유로 결과가 달라지는 Code 영역입니다.
한번에 오직 하나의 프로세스만이 임계영역에 진입하도록 만들어야 합니다.

# 임계 영역 해결의 조건들

상호 배제(Mutual Exclusion)
- 만약 프로세스가 임계영역에 진입해 있다면, 다른 모든 프로세스는 임계영역에 진입할 수 없어야 한다.
융통성(Flexibility)
- 한 프로세스가 다른 프로세스의 일을 방해해서는 안된다.
한정 대기(Bounded Waiting)
- 프로세스가 임계영역에 진입할 때까지 걸리는 시간에 제한이 존재해야한다.
- 어떤 프로세스도 무한대기(Infinite Postpone)하지 않아야한다.
- 특정 프로세스가 임계영역에 진입하지 못하면 안된다.
진행(Progress)
- 만약 어떤 프로세스도 임계영역내에 있지 않고, 임계 영역에 진입하려는 프로세스가 존재한다면, 진입하려는 프로세스들만이 누가 진입할지 결정할 수 있어야 한다.

# 임계 영역의 해결 방법

잠금(lock)이 해결 방법들의 토대가 됩니다. 임계구역에 들어갈 때 잠금을 걸고, 나올 때 잠금 해제와 동시에 동기화 신호를 보내는 방식입니다.

뮤텍스(Mutex)
- 공유 자원을 사용하기 전에 설정하고 사용한 후에 해제하는 잠금입니다.
- 잠금이 설정되면 다른 스레드는 잠긴 코드 영역에 접근할 수 없습니다.
- 뮤텍스는 하나의 상태(잠금 또는 잠금 해제)만을 가집니다.
피터슨 알고리즘
세마포어(Semaphore)
모니터

# 피터슨 알고리즘(Peterson Solution)

게리 피터슨(Gary Peterson)이 제안한 알고리즘
두 프로세스가 동시에 수행되더라도 turn 값에 의하여 진행될 프로세스가 결정됩니다.
임계 영역 해결의 세가지 조건을 모두 만족합니다.
한계
- 프로세스수가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해집니다.
- 또한, 어떤 경우에도 동작함을 보이지 못했습니다.(NP 문제)
- 바쁜 대기를 사용하여 자원을 낭비한다. (while loop)

// 공유 변수(초기화)
  boolean flag[2]; flag[0] = flag[1] = false; 
  int turn;

// 프로세스 1
flag[0] = true;
turn = 1;
while(flag[1] && (turn == 1));
    /** 임계구역 **/
flag[0] = false;
    
// 프로세스 2
flag[1] = true;
turn = 0;
while(flag[0] && (turn == 0));
    /** 임계구역 **/
flag[1] = false;

# 세마포어

일반화된 뮤텍스입니다. 간단한 정수 값과 두가지 함수로 공유 자원에 대한 접근을 처리합니다.

두개의 원자적 연산을 가지는 정수 변수
- 원자적인 연산
  - Wait(), P() : 자신의 차례가 올 때까지 기다리는 함수
  - Signal(), V() : 다음 프로세스로 순서를 넘겨주는 함수
- 세마포어는 2개의 원자적인 연산에 의해서만 접근이 가능합니다.
P는 임계영역에 들어가기 전에, V는 나와서 수행합니다.
P와 V연산은 서로 독립적으로, 그리고 원자적으로 수행됩니다.
- 하나의 Process가 P를 수행하여 세마포어의 값을 수정하는 동안, 다른 Process에서 P나 V를 수행하여 같은 세마포어의 값을 수정하지 못합니다.
순서
1. 임계구역 사용전에 Semaphore(n) 로 초기화를 합니다.
- n은 공유 가능한 자원의 수를 나타낸다. 전역변수 RS를 n으로 초기화 합니다.
- e.g. 프린터가 1대이면 1이고, 2대이면 2가 됩니다.
1. 초기화가 끝난 후 임계구역에 들어가기 전 사용중이라고 표시를 합니다.
  - P(): 잠금을 수행하는 코드
  - RS가 0보다 크면(사용 가능한 자원이 있으면) 1을 감소시키고 임계구역에 진입합니다.
  - RS가 0보다 작으면(사용 가능한 자원이 없으면) 0보다 커질 때 까지 기다립니다.
2. 임계구역을 나올 때 비었다고 표시한다.
  - V(): 잠금 해제와 동기화를 같이 수행하는 코드
  - RS값을 1 증가시키고 세마포어에서 기다리는 프로세스에게 임계구역에 진입해도 좋다는 wake up 신호를 보냅니다. — wake_up()
```
Semaphore(n); // RS = n;

P();
// if RS > 0 them RS = RS - 1
// else block()

/** 임계구역 **/

V();
// RS = RS + 1
// wake_up()
```
구현
- Busy Waiting
  - 임계영역에 집입할 조건이 될 때까지 loop를 돌며 기다리는 방식입니다.
  - 대기 중인 프로세스 중에서 누가 임계영역에 진입할지 결정하지 않습니다.
- Sleep Queue
  - 세마포어의 자료구조에 Sleep Queue를 추가하여, 대기 중인 프로세스를 관리하는 방식입니다.
  - 세마포어의 값이 양수가 되어 임계영역에 진입이 가능하게 되면, Sleep Queue에서 대기 중인 프로세스를 깨워 실행시킵니다.
종류
- 카운팅 세마포어(Counting Semaphore)
  - 여러 개의 값을 가질 수 있는 세마포어
  - 여러 자원에 대한 접근을 제어하는 데 사용됩니다.
  - 세마포어 값은 범위가 정해져 있지 않고, 초기값은 가능한 자원의 수로 정해집니다.
- 바이너리 세마포어(Binary Semaphore)
  - 0과 1만 가질 수 있는 세마포어 입니다.
  - 뮤텍스와 유사하지만 뮤텍스는 리소스에 대한 접근을 동기화하는데 사용되는 잠금 메커니즘이고, 세마포어는 신호를 기반으로 상호 배제가 일어나는 신호 메커니즘입니다.
  - 카운팅 세마포어보다 구현이 간단합니다.

원자적이란?

명령어가 수행되는 동안 방해받지 않는 것.(= Uninterruptible)
System 및 하드웨어가 처리해주기 때문에 가능하다.

# 모니터

공유자원을 숨기고 해당 접근에 대해 인터페이스만 제공하여 공유 자원에 안전하게 접근하도록 하는 방식.

High-level 언어에서의 동기화 방법입니다.(ex. java의 thread, Transaction in Database)
한 순간에 하나의 프로세스만 모니터에서 활동하도록 보장합니다.
세마포어처럼 P와 V 연산에 대한 고려 없이 모니터에 작업요청을 하는 것만으로 동기화를 해결할 수 있습니다.
프로그래머가 동기화 제약 조건을 명시적으로 코드화할 필요가 없습니다.
순서
1. 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
  1. 잠금이나 세마포어를 사용하지 않고 increase() 문을 사용
  2. wait(): 모니터 큐에서 자신의 차례가 올때까지 기다린다. — P()
  3. signal(): 모니터 큐에서 기다리는 다음 프로세스에 순서를 넘겨준다. — V()
2. 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다

# 참고자료

주홍철.면접을 위한 CS 전공지식 노트.서울:길벗,2022.
숭실대학교 김영근 교수님의 운영체제 강의자료(2021)
suyeonme.log (opens new window)

← 스레드 교착상태(Deadlock) →