1. 공유 자원(Sahred Resource)

💡 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일등을 말한다. 공유 자원은 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다. 따라서 프로세스들의 공유 자원 접근 순서를 정하여 예상치 못한 문제가 발생하지 않도록 해야한다.

1.1 경쟁 조건(Race Condition)

• 2개 이상의 프로세스가 공유 자원을 병렬적으로 읽거나 쓰는 상황
• 경쟁 조건이 발생하면 공유 자원 접근 순서에 따라 실행 결과가 달라질 수 있다.

1.2 임계 구역(Critical Section)

• 공유 자원 접근 순서에 따라서 실행 결과가 달라지는 프로그램의 영역
• 임계구역에서는 프로세스들이 동시에 작업하면 안된다.
  • 어떤 프로세스가 임계구역에 들어가면 다른 프로세스는 기다려야하며 임계구역의 프로세스가 나와야 들어갈 수 있다.
• 전역 변수 뿐만 아니라 하드웨어 자원을 사용할 때도 적용되는 개념이다.
  • e.g. 프린터 1대를 여러명이 동시에 사용하는 경우 프린터는 임계구역이 된다.

1.3 임계 구역 해결 조건

1. 상호 배제(Mutual Exclusion)
   1. 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다.
2. 한정 대기(Bounded Wating)
   1. 어떤 프로세스도 무한대기(Infinite Postpone)하지 않아야한다. 특정 프로세스가 임계구역에 진입하지 못하면 안된다.
3. 진행의 융통성(Progress Flexibility)
   1. 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다.

2. 임계 구역 해결 방법

💡 가장 단순한 방법은 잠금(lock)을 이용하는 것이다. 임계구역에 들어갈 때 잠금을 걸고, 나올 때 잠금 해제와 동시에 동기화 신호를 보낸다.

2.1 피터슨 알고리즘

• 게리 피터슨(Gary Peterson)이 제안한 알고리즘
• 변수 turn은 두 프로세스가 동시에 lock을 설정하여 임계구역에 못들어가는 상황에 대비하는 장치
  • 두 프로세스가 동시에 lock을 설정했더라도 turn을 사용하여 다른 프로세스에게 양보

한계

• 임계구역 해결의 세가지 조건을 모두 만족하지만 프로세스수가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해진다.
• 바쁜 대기를 사용하여 자원을 낭비한다. (while loop)

// 공유 변수
boolean lock1 = false;
boolean lock2 = false;
int turn = 1;

// 프로세스 1
lock1 = true;
turn = 2;
while(lock2 == true && turn == 2);
/*** 임계구역 ***/
lock1 = false;

// 프로세스 2
lock2 = true;
turn = 1;
while(lock1 == true && turn == 1);
/*** 임계구역 ***/
lock2 = false;

2.2 데커 알고리즘

• 테오도뤼스 데커(Theodorus Dekker)가 제안한 알고리즘
• 하드웨어의 도움 없이도 임계구역 문제를 해결할 수 있다.

한계

• 임계구역 해결의 세가지 조건을 모두 만족하지만 프로세스수가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해진다.
• 바쁜 대기를 사용하여 자원을 낭비한다. (while loop)

// 공유 변수
boolean lock1 = false;
boolean lock2 = false;
int turn = 1;

// 프로세스 1
lock1 = true;
while(lock2 == true) {
	if(turn == 2) {
		lock1 = false;
		while(turn == 2);
		lock1 = true;
	}
}
/*** 임계구역 ***/
turn = 2;
lock1 = false;

// 프로세스 2
lock2 = true;
while(lock1 == true) {
	if(turn == 1) {
		lock2 = false;
		while(turn == 1);
		lock2 = true;
	}
}
/*** 임계구역 ***/
turn = 1;
lock2 = false;

2.3 세마포어 알고리즘

• 에츠허르 데이크스트라(Edsger Dijkstra)가 제안한 알고리즘
• 앞의 알고리즘과 비교하여 간단하고 사용이 쉬우며, wakeup 신호를 사용하기 때문에 바쁜 대기를 하지 않아도 된다.
• P()와 V()의 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고 완전히 실행되게 해야한다.
  • P()나 V()내부 코드가 실행되는 도중 다른 코드가 실행되면 상호 배제와 한정 대기 조건을 보장하지 못하기 때문

한계

• 잘못된 사용으로 인해 임계구역이 보호받지 못할 수 있다.
  • 사용자가 고의로 세마포어를 사용하지 않거나 사용중에 실수를 한 경우
  • 즉 직접 변수에 접근하여 조작하기 때문에 위험하다.

순서

1. 임계구역 사용전에 Semaphore(n) 로 초기화를 한다.
   1. n은 공유 가능한 자원의 수를 나타낸다. 전역변수 RS를 n으로 초기화 한다.
   2. e.g. 프린터가 1대이면 1이고, 2대이면 2가 된다.
2. 초기화가 끝난 후 임계구역에 들어가기 전 사용중이라고 표시를 한다.
   1. P(): 잠금을 수행하는 코드
   2. RS가 0보다 크면(사용 가능한 자원이 있으면) 1을 감소시키고 임계구역에 진입한다.
   3. RS가 0보다 작으면(사용 가능한 자원이 없으면) 0보다 커질 때 까지 기다린다.
3. 임계구역을 나올 때 비었다고 표시한다.
   1. V(): 잠금 해제와 동기화를 같이 수행하는 코드
   2. 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()

2.4 모니터

• 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공하여 자원을 보호하고 프로세스간에 동기화를 시킨다.
• 시스템 호출과 같은 개념이다.
• 사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋고 시스템 입장에서는 임계구역을 보호할 수 있어서 좋다.

순서

1. 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
   1. 잠금이나 세마포어를 사용하지 않고 increase() 문을 사용
   2. wait(): 모니터 큐에서 자신의 차례가 올때까지 기다린다. — P()
   3. signal(): 모니터 큐에서 기다리는 다음 프로세스에 순서를 넘겨준다. — V()
2. 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.