병행성과 상호배제&상호배제 알고리즘

병행성의 주요 용어 정리

• 경쟁 상태 (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이 발생 할 수 있다.