병행성의 주요 용어 정리
- 경쟁 상태 (Race condition)
- 두개 이상의 쓰레드나 프로세스가 공유 자원을 동시에 접근하려는 상태.
- 상호 배제 (Mutual exclusion)
- 특정 프로세스가 공유자원을 사용하고 있을 경우 다른 프로세스가 해당 공유자원을 사용하지 못하게 하는 조건
- 임계 영역 (Critical Section)
- 공유 자원을 접근하는 프로세스 내부의 코드 영역. 다른 프로세스가 이 영역에 있을 때, 이 프로세스 또한 이 영역을 수행할 수 없다.
- 기아 (Starvation)
- 특정 프로세스가 수행 가능한 상태임에도 불구하고 매우 오랜 기간 동안 스케줄링 되지 못하는 경우.
- 교착 상태 (Deadlock)
- 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상.
- 원자적 연산 (Atomic operation)
- 하나 또는 여러 개의 명령어들로 구성된 함수 또는 액션으로 더 이상 분할할 수 없는 단위. 따라서 다른 어떤 프로세스도 중간 상태를 볼 수 없으며, 연산을 중단 시킬 수 없다. 이 명령어들은 모두 수행되거나 하나도 수행되지 않음이 보장된다. 원자성은 병행 프로세스들에게 고립(isolation)을 보장한다.
Critical Section 문제의 해결을 위한 필요조건
- Mutual Exclusion
- 한 프로세스가 임계영역(Critical section)을 수행하고 있으면, 다른 프로세스는 그 임계영역을 수행 할 수 없다.
- Progress
- 임계영역을 수행하고 있는 프로세스가 없고, 한 프로세스가 임계영역에 진입하려고 하면 즉시 임계영역에 들어갈 수 있어야 한다.
- Bounded Waiting
- 임계영역에 접근하고자 하는 프로세스의 수행이 무한히 미루어져서는 안된다. 즉, 교착상태 및 기아가 일어나지 않아야 한다.
Mutual Exclusion 문제의 해결방안
- 소프트웨어적 해결 알고리즘
- 데커(Dekker) 알고리즘 - 두 프로세스가 동시에 임계 영역에 들어가려고 할 때 하나만 들어가게 하는 알고리즘. 한 프로세스가 이미 임계 영역에 있다면, 다른 프로세스는 전 프로세스가 끝나기를 기다린다. (busy waiting)
- 피터슨(Peterson) 알고리즘 - 데커 알고리즘과 유사하며, 두 프로세스가 동시에 임계영역에 진입하려고 하면 turn 변수가 늦게 수행된 프로세스가 기회를 양보한다.
- 빵집(Bakery) 알고리즘 - 데커/피터슨 알고리즘은 2개의 프로세스에 대해서만 가능하지만, Bakery 알고리즘은 2개 이상의 프로세스에 대해서 사용 가능한 알고리즘이다.
- 하드웨어적 해결 방법
- Test & Set
- Compare & Swap
- 하드웨어적 해결방법의 장점 : 단순하다. 사용하기 쉽다. 여러개의 임계 구역에서 사용 가능하다.
- 하드웨어적 해결방법의 단점 : Busy-waiting이 발생(CPU 활용도 저하), Deadlock이 발생 할 수 있다.
'운영체제' 카테고리의 다른 글
| 교착상태(Deadlock) (0) | 2018.08.28 |
|---|---|
| 세마포어와 뮤텍스 (Semaphores&Mutex) (0) | 2018.08.26 |
| Thread (0) | 2018.08.24 |
| Context Switch (문맥 교환) (0) | 2018.08.23 |
| 프로세스 (개념, 상태, PCB) (0) | 2018.08.23 |