운영체제 - 병행프로세스, 상호배제

병행 프로세스 정의

여러 프로세스가 빠르게 번갈아 실행되어 동시에 실행되는 것처럼 보이는 것.

시분할 시스템과 동일한 정의지만, 병행 프로세스는 프로세스 그 자체를 의미.

 

병행 프로세스의 종류

 

1. 독립 프로세스

   프로세스간에 서로 영향을 끼치지 않는 프로세스.

   자원을 공유하지 않음.

2. 협력 프로세스

   동일한 목표를 가진 프로세스 간에 상호작용하며 수행하는 프로세스.

   자원을 공유함.

 

병행 프로세스의 문제점

 

1. 공유 자원을 한 순간에 한 프로세스만 사용하도록 해야 함(상호 배타적).

2. 하나의 기능을 함께 수행하므로 프로세스 간에 동기화를 해주어야 함.

3. 자원을 공유하기 위해 프로세스 간에 통신이 되어야 함.

4. 교착상태를 해결해야 함.

 

동기화

 

프로세스 간에 실행 순서를 정해, 자원의 일관성을 유지하는 것.

상호 배제는 보장하지만, 교착상태와 기아상태가 발생할 수 있음.

 

비동기화

 

프로세스 간에 서로의 존재를 몰라 동시에 자원에 접근할 수 있어 데이터의 일관성을 잃을 수 있음.

 

임계 영역(critical section) 정의

임계 영역에 접근하고 실행하는 코드.

프로세스가 공동 변수를 읽고, 테이블을 갱신하고, 파일을 수정하는 등 공동 데이터에 접근할 때 '임계 영역에 있다.'라고 함.

 

임계 자원

 

한 순간에 한 프로세스만 해당 공유 자원을 할당받을 수 있음.

 

경쟁 상태(race condition)

 

한 개의 공유 자원을 획득하기 위해 여러 프로세스가 서로 경쟁하는 것.

어떤 프로세스가 먼저 자원을 획득하는지에 따라 결과 값이 달라지는 현상.

 

임계 영역의 문제 해결 조건

 

1. 상호 배제

   한 순간에 한 프로세스만 임계 영역에 들어갈 수 있음.

2. 진행

   임계 영역이 비어있고, 임계 영역에 들어가고 싶어 하는 프로세스가 존재한다면, 그 프로세스를 임계 영역에 들어갈 수 있게 해야 함.

3. 유한 대기

   다른 프로세스의 기아 상태를 방지하기 위해, 한 번 들어간 프로세스가 다시 임계 영역에 들어갈 때 제한을 두어야 함.

 

상호 배제 = 뮤텍스

 

한 순간에 한 프로세스만이 임계 영역에 들어갈 수 있음.

경쟁 상태를 해결할 수 있음.

 

상호 배제 방법

 

1. 하나의 프로세스가 임계 영역에 들어가면 임계 영역이 Lock이 되어 다른 프로세스 진입 불가.

2. 임계 영역의 프로세스가 작업을 마치고 나가면, 임계 영역이 Unlock이 되어 다른 프로세스 진입 가능.

※ 즉, 임계 영역이 하나의 덩어리가 되어 중간에 다른 프로세스나 스레드가 진입하지 못합니다. 이를 '원자적으로 실행된다'라고 합니다. 원자적으로 실행되는 또 다른 예는 DBMS의 트랜잭션으로 상호 배제 방법과 비슷합니다.

상호배제

세마포어

 

멀티프로그래밍 환경에서 공유자원에 대한 접근을 제한하는 방법.

추상적인 방법을 말하는 것이지, 실제 코드를 의미하진 않음.

S = 자원의 수

P(S) 연산 = 임계 영역을 진입하는 연산. S가 1 이상이면(획득할 수 있는 자원이 1개 이상이라는 뜻) 임계 영역에 진입.

V(S) 연산 = 임계 영역을 빠져나오는 연산. (자원을 반납하고 대기 중인 프로세스를 깨움)

세마포어의 P연산과 V연산

1. 임계 영역에 아무도 없다면(S>0), S-1을 하고 임계 영역에 진입
2. 만약 임계 영역에 누가 존재한다면(S=0), 대기 큐에서 대기
3. 임계 영역에서 빠져나오면, 대기 큐에 대기 중인 프로세스가 있으면 해당 프로세스가 임계 영역 진입.
4. 대기 큐에 프로세스가 존재하지 않으면 S+1을 하고 다른 프로세스가 진입할 수 있도록 함.

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

 

1. 상호 배제 문제

2. 동기화 문제

3. 생산자-소비자 문제 

4. 철학자들의 식사 문제

 

세마포어의 문제점

 

busy-waiting 문제.

임계 영역에 프로세스가 있는지 확인하기 위해 계속해서 while 문을 수행하여 부하가 발생. = spin lock

 

뮤텍스와 세마포어의 차이점

 

뮤텍스와 세마포어의 가장 큰 차이점은 뮤텍스는 공유자원이 한 개일 때, 세마포어는 공유자원이 한 개 이상일 때 가능.

그렇기 때문에 뮤텍스를 이진 세마포어라고 부르기도 함.

 

모니터

 

상호 배제 문제를 해결하기 위한 소프트웨어 모듈로 프로그래밍 언어 수준에서 제공.

한 시점에 한 프로세스만 모니터 내부에서 실행 가능.

 

교착상태 정의

둘 이상의 프로세스가 서로의 자원을 기다리는 상태.

 

교착상태 발생 원인

 

제한된 자원의 사용률과 효율성을 높이기 위해 병행 처리 기술과 자원 공유에 따른 부작용.

 

교착상태의 예시

 

1. 스풀링 시스템

   스풀 공간의 출력을 완료하지 않은 상태에서 다른 작업이 스풀 공간을 모두 차지했을 경우.

2. 디스크를 공유할 때

   프로세스가 섹터 55 위치를 읽으라고 하여 해당 위치로 이동 중 다른 프로세스가 다른 위치를 읽으라고 하는 현상이 반복적으로 일어나 어느 프로세스의 요구도 수행 못하는 경우.

3. 식사하는 철학자 문제

식사하는 철학자 문제

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

모든 철학자가 3번 상태에 머물러 진행할 수 없음.

양쪽 포크를 모두 잡을 수 있을 때만 포크를 들도록 하면 문제가 해결됨.

 

교착상태 발생 조건

 

아래 4가지 중 하나만 성립되지 않아도 교착상태는 발생하지 않음.

1. 상호 배제 : 한 순간에 한 프로세스만 자원 사용 가능.

2. 비선점 : 한 프로세스가 자원을 사용하고 있으면, 다른 프로세스가 이를 뺏지 못함.

3. 점유와 대기 : 최소한 하나의 자원을 보유한 상태로 다른 자원을 기다려야 함.

4. 순환 대기 : 자원을 원형 형태로 요구하며 대기하고 있어야 함.

교착상태 해결 방법

 

1. 예방 방법

   교착상태 발생 조건의 4가지 중 적어도 하나를 없애는 방법.

   교착상태를 예방할 수 있지만 심각한 자원 낭비가 발생함.

• 상호 배제 방지 : 모든 자원을 획득할 수 있도록 함.
• 비선점 방지 : 자원을 빼앗을 수 있도록 함.
• 점유와 대기 방지 : 필요한 자원을 모두 한 번에 할당 받음. 당장 사용하지 않을 자원까지 할당받아 자원 낭비.
• 순환 대기 방지 : 모든 자원을 순서대로 받을 수 있도록 함. 할당되지 않은 자원이 많아져서 자원 낭비.

2. 회피 방법

   시스템을 계속 감시하여(오버헤드 발생) 교착상태가 발생할 것 같으면 자원 할당을 보류.

   실제로 일어나지 않을 가능성이 있는 작업도 자원 할당이 보류되기 때문에 자원 효율성 하락.

   시스템을 항상 safe state로 유지.

   알고리즘 : 은행가 알고리즘(banker's algorithm)

   그러나, 현실적으로 프로세스의 수, 자원의 수가 고정되어 있어야 하고, 필요한 최대 자원의 수를 미리 알고 있어야 하기 때문에 불가능함.

※ safe state는 교착상태가 절대 일어나지 않는 상태이며 적어도 하나 이상의 safe sequence가 존재합니다. 반대로, unsafe state는 교착상태가 일어날 가능성이 있는 상태입니다.

3. 회복 방법

   주기적으로 교착상태가 발생하는지 확인하며(오버헤드 발생) 교착상태가 발생하면 이를 회복하는 방법.

• 교착상태 탐지 알고리즘 : Graph reduction 알고리즘
• 교착상태 회복 알고리즘 : Process termination 알고리즘, Resource preemption 알고리즘

기아상태 정의

우선순위가 낮아, 필요한 자원을 오랫동안 할당받지 못한 상태.

 

기아상태 해결 방법

 

1. 오래 기다린 프로세스의 우선순위를 높여주면 됨.

2. 요청한 순으로 처리

 

교착상태와 기아상태의 차이

 

교착상태는 프로세스가 다른 자원을 기다리는 '대기' 상태일 때 발생.

기아상태는 프로세스가 CPU를 기다리는 '준비' 상태일 때 발생.

교착상태는 일어날 가능성이 '0%'인 일을 기다림.

기아상태는 일어날 가능성이 있는 일을 기다림.(단지 운이 나빠 오래 기다릴 뿐)