5주차 - Chapter 12~13

Contents

Chapter 12 프로세스 동기화

동시성, 병렬성 프로그래밍에서 발생할 수 있는 문제들

공유 자원과 Critical section, Race condition

• 멀티프로세싱, 멀티스레딩 환경에서 데이터를 주고받는 상황이 있는데, 실행 순서와 자원의 일관성을 보장해야 한다. 이를 위해 동기화 개념이 필요하다.

• 동기화에는 크게 두 가지가 있다.
• 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
• 상호 배제 : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기

• 실행 순서 제어를 위한 동기화
• 같은 자원을 사용하는 두 프로세스가 주어질 때, 한 프로세스는 자원에 값을 쓰고, 다른 프로세스는 자원으로부터 값을 읽어온다. 값을 쓰는 프로세스보다 먼저 값을 읽는 프로세스가 실행되면 안 된다고 했을 때, 값을 쓰는 프로세스가 값을 쓸 때까지 값을 읽는 프로세스는 대기해야 할 것이다. 이처럼 프로세스 간 실행 순서를 제어하여 의도치 않은 실행 결과를 방지하기 위한 목적이 동기화의 목적 중 하나다.

• 상호 배제를 위한 동기화
• 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘이다.
• 다음과 같은 작업을 수행하는 프로세스가 있다고 하자.
• 공유 자원에서 데이터를 가져와서 값을 더하고, 더한 값을 다시 공유 자원에 쓴다.
• 제시한 작업을 다시 세분화하여 나열하면
1. 공유 자원에서 데이터를 가져온다.
2. 가져온 데이터에서 값을 더한다.
3. 더한 값을 공유 자원에 써 업데이트한다.
• 한 번 작업을 수행하려면 세 개의 명령어를 순서대로 실행해야 한다. 그러나, 명령어가 모두 끝나기 전에 context switching이 일어나 다음에 실행할 프로세스의 명령어가 처음부터 실행된다면 어떨까?
• 앞에서 공유 자원을 업데이트해야 했을 프로세스에서 업데이트를 하지 않아서, 뒤에서 처리한 값만 반영될 것이다.
• 동기화를 거치면 앞에 실행될 프로세스의 작업들이 모두 실행될 때까지 뒤에 실행될 프로세스가 대기하며, 작업이 모두 끝나면 그때 context switching을 하여 뒤에 실행될 프로세스가 실행되도록 할 수 있다.

• 동기화하지 않았을 때 발생하는 문제들
• Critical section : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 부분
• Race condition : 프로세스 동기화가 제대로 이루어지지 않아, 두 개 이상의 프로세스가 Critical section을 실행하여 공유 자원과 관련된 오류를 유발하는 상황

프로세스 동기화를 위한 세 가지 원칙

1. Mutual Exclusion (상호 배제) : 한 프로세스가 Critical section을 실행하고 있다면 다른 프로세스는 대기해야 한다.

2. Progress (진행) : Critical section을 그 어떤 프로세스라도 실행하고 있지 않다면, 어느 프로세스라도 이를 실행할 수 있는 상태여야 한다.

3. Bounded Waiting (유한 대기) : Critical section을 무한정 실행하면 안 된다. Critical section을 실행했다면 언젠가는 끝나 다른 프로세스가 실행할 수 있는 상태가 되어야 한다.

동기화 기법들

뮤텍스 락

• 프로세스들이 동시에 접근하면 안 되는 공유 자원에 동시에 접근하지 못하도록 하기 위한, Mutual exclusion의 구현을 위한 동기화 도구

• 공유 자원이 현재 접근 가능한지는 boolean 타입의 lock 변수를 따로 지정하여, 값이 false면 접근 가능하고 값이 true면 접근 불가능하다.

• 실행 흐름
1. 먼저, 프로세스는 공유 자원이 현재 접근 가능한지 확인해야 한다. acquire 함수는 lock 여부를 확인하는 함수인데, 프로세스는 이 함수의 반환값이 false일 때까지 대기한다.
2. false가 되어 공유 자원에 접근할 수 있게 되었다면, acquire 함수는 lock 변수를 true로 바꾸어 다른 프로세스가 공유 자원에 접근할 수 없게 한다. 그 다음에 Critical section을 실행한다.
3. 실행한 이후 그 다음 프로세스가 공유 자원에 접근할 수 있도록 release 명령어를 실행하여, lock 변수를 false로 만든다.

세마포

• 세마포는 다음과 같은 형태로 구현되어 있다.
• Critical section에 진입할 수 있는 프로세스의 개수를 나타내는 전역 변수 S
• Critical section에 진입할지, 기다려야 할지 알려주는 wait 함수 (P 연산)
• Critical section 앞에서 기다리는 프로세스에 이제 진입해도 된다는 신호를 보내는 signal 함수 (V 연산)

• 주로 wait 함수는 Critical section에 진입하려는 프로세스가, signal 함수는 Critical section을 모두 실행하고 퇴장하려는 프로세스가 실행한다.

모니터

• 모니터를 통해 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입하고, 큐에 삽입된 순서대로 하나씩 공유 자원을 이용하도록 한다.

• 공유 자원에는 마찬가지로 한 번에 하나의 프로세스만 접근해야 하므로, 인터페이스 내부에서 공유 자원으로 내보낼 때에는 Mutual exclusion 형식의 동기화를 수행한다.

• 세마포와 마찬가지로, 실행 순서 제어를 위한 동기화 또한 지원한다. 특정 조건을 바탕으로 프로세스를 실행하거나, 일시 중단하기 위해 조건 변수를 사용한다.
• 조건 변수란, 프로세스나 스레드의 실행 순서를 제어하기 위해 사용되는 특수한 변수다.

Chapter 13 교착 상태

교착 상태란?

교착 상태 발생 조건

1. 상호 배제 (Mutual exclusion) : 프로세스가 사용하는 자원은 한 번에 한 프로세스만 사용할 수 있다. 사용 중인 프로세스가 사용을 끝낼 때 다른 프로세스가 사용할 수 있다.

2. 점유와 대기 (Hold and wait) : 어떤 자원을 할당받은 상태에서 다른 자원을 할당받기 위해 기다리고 있는 상태. 교착 상태는 상호 배제와 이 문제와 맞물려 발생할 가능성이 높다.

3. 비선점 (Non-preemptive) : 자원을 사용하는 프로세스가 해당 자원이 필요한 작업을 모두 끝낼 때까지 자원을 사용하고자 하는 다른 프로세스는 기다려야 한다.

4. 원형 대기 (Circular wait) : 프로세스들이 원의 형태로 자원을 할당받기 위해 대기하는 상태. 1~3번의 특징을 모두 갖고 있는 것과 비슷하다.
• 공유 자원을 사용하는 모든 프로세스가 각자 할당받은 자원이 있는데, 한쪽 방향을 기준으로 앞에 있는 프로세스로부터 자원 사용이 다 끝나가기를 기다리고 있다.
• 한편으로는, 뒤에 있는 프로세스에서는 그 앞의 프로세스에서 자원 사용이 다 끝나가기를 기다리고 있다.
• 이러한 양상이 공유 자원을 사용하는 모든 프로세스에서 동시에 일어난다면, 교착 상태가 발생할 가능성이 높다.

교착 상태 해결 방법

교착 상태 예방

1. 자원의 상호 배제 없애기
• 자원의 상호 배제를 없앤다는 것은 곧 모든 자원이 공유 가능한 자원임을 의미한다. 그러나 상호 배제를 없애면 같은 공유 자원을 접근하고자 하는 자원들 간 race condition이 발생한다.
• 따라서, 이 방법은 같은 공유 자원을 접근하는 프로세스들이 없을 때에만 가능하다.

2. 점유와 대기 없애기
• 점유와 대기를 없애면 프로세스가 필요로 하는 자원을 모두 할당한 상태와, 아무것도 할당받지 못한 상태 둘 중 하나로 정해지게 된다.
• 즉, 특정 프로세스에만 자원이 집중되기 때문에 실제로 급히 필요한 프로세스에 자원이 할당되지 못하거나, 프로세스에 자원이 할당되었지만 실질적으로 잘 사용되지 않는 프로세스라면 자원의 활용도가 낮아진다.

3. 비선점 조건 없애기
• 교착 상태가 발생하면, 현재 공유 자원을 이용 중인 프로세스의 공유 자원을 강제로 회수하고, 공유 자원이 필요한 프로세스에 할당하여 해결한다.
• 그러나, 모든 프로세스가 이러한 선점 방식으로 처리되어서는 안 된다. 한 번 자원이 할당되면 반드시 작업이 끝날 때까지 이를 유지해야 하는 프로세스는 선점 방식으로 인해 자원이 실행 도중 회수되면 문제가 발생할 수 있기 때문이다.

4. 원형 대기 조건 없애기
• 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다.
• 어느 한 쪽 끝의 자원이 반대쪽 끝의 자원을 점유하지 않고, 일렬 방향으로 자원을 점유하므로 모든 프로세스가 동시에 공유 자원을 점유할 수 있다.
• 한계
• 컴퓨터 시스템에서의 공유 자원에서는 각 자원마다 번호를 순서대로 붙이기에는 그 구조가 굉장히 복잡하여 쉽지 않다.
• 각 자원에 어떤 번호를 붙이냐에 따라 자원의 활용도가 달라진다.

교착 상태 회피

• 할당할 수 있는 전체 공유 자원의 수와 현재 할당할 수 있는 남은 공유 자원의 수를 비교하여, 필요로 하는 자원의 수가 적은 프로세스부터 많은 프로세스 순으로 공유 자원을 할당하여 교착 상태를 회피한다.

• 안전 상태와 불안전 상태, 안전 순서열
• 안전 상태 (Safe state) : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료할 수 있는 상태
• 불안전 상태 (Unsafe state) : 교착 상태가 발생할 수 있는 상태
• 안전 순서열 (Safe sequence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

교착 상태 검출 후 회복

• 교착 상태 검출 후 회복
• 교착 상태가 발생하면 모든 프로세스에 할당했던 자원을 모두 회수하고, 어느 한 프로세스에 모든 자원을 몰아주어 자원을 필요로 하는 프로세스의 수를 줄여 나가는 회복 방법
• 비선점 스케줄링과 유사

• 프로세스 강제 종료를 통한 회복
• 크게 두 가지 방법이 있다.
1. 교착 상태에 놓인 프로세스들을 모두 강제 종료
→ 실행 중인 프로세스들을 동시에 여럿 강제 종료하기 때문에, 작업 내역이 더 많이 소멸된다.
2. 교착 상태가 회복될 때까지 교착 상태에 놓인 프로세스를 하나씩 강제 종료
→ 교착 상태에 놓인 프로세스를 하나씩 종료하고 교착 상태가 발생하는지 확인하는 과정에서, 오버헤드가 발생한다.
• 두 방법 모두 빠른 회복을 위한 리스크를 감수해야 하므로, 교착 상태 발생을 사전에 발생하거나 발생해도 강제 종료하는 방식으로 교착 상태를 아예 무시하는 타조 알고리즘을 적용하기도 한다.
• 교착 상태는 발생 빈도가 상당히 낮기 때문에, 문제 발생의 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어의 관점에서는 무시하는 방법이 더 효과적일 수 있다.

문제풀이