[공룡책] 동기화

논리 주소 공간을 공유하는 협력적 프로세스의 질서 있는 실행을 보장하며 이를 통해 데이터의 일관성을 유지하는 다양한 매커니즘을 논의합니다.

임계구역

Critical Section

각 프로세스는 임계구역이라고 부르는 코드 부분을 포함하고 있고,
그 안에서는 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있습니다.

임계구역 문제는 상호배제, 진행, 한정된 대기 세 가지 요구사항을 충족해야 합니다.

1. Mutual Exclusion
2. 프로세스가 Critical Section에서 실행중이라면, 다른 프로세스들은 그들이 가진 Critical Section에서 실행될 수 없습니다.
3. Progress
4. Ciritical Section에서 실행중인 프로세스가 없고 별도의 동작이 없는 프로세스들만 Critical Section 진입 후보로서 참여될 수 있습니다.
5. Bounded Waiting
6. 프로세스가 Critical Section에 진입 신청 후부터 받아들여질 때까지 다른 프로세스들이 Critical Section에 진입하는 횟수는 제한이 있어야 합니다.

상호 배제를 통해 한 번에 하나의 프로세스만 임계구역에서 활성화됩니다.
진행을 통해 임계구역에 어떤 프로세스가 들어갈지 협력적으로 결정합니다.
한정된 대기를 통해 프로그램이 자신의 임계구역에 들어가기 전 대기시간을 제한합니다.

해당 임계구역 문제의 해결책으로 Mutex Lock, Semaphores를 활용할 수 있습니다.

Mutex, Semaphore

• Mutex는 한 스레드나 프로세스에 의해 소유될 수 있는 key를 기반으로 상호를 배제합니다.
• 누군가가 key를 갖고 있다면 다른이는 key를 사용할 수 없고 대기합니다.
• 반납을 해야지만 다시 key를 사용할 수 있습니다.
• Semaphore는 현재 공유자원에 접근할 수 있는 스레드와 프로세스의 수를 변수로 두어 상호를 배제합니다.

화장실로 비유할 수 있습니다.

뮤텍스는 화장실이 하나 뿐인 식당과 비슷합니다.
앞서 입장한 손님이 키를 소유하고, 화장실에서 나올 때 키를 반납합니다.
뒤이어 입장하는 손님들은 키가 반납될 때까지 카운터에서 대기합니다.
이로써 화장실에 동시에 여러명이 존재하는 상황을 막습니다.

세마포어는 화장실의 칸이 여러개인 식당과 비슷합니다.
앞서 입장한 손님들이 화장실 칸에 들어갈 때 전광판에 남은 칸의 개수를 비춥니다.
손님들이 퇴장하면 전광판의 숫자가 오르며
전광판에 숫자 0이 표시되면 손님들은 대기합니다.

카운팅 / 이진 세마포

카운팅 세마포는 가용한 개수를 가진 자원에 대해 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수로 초기화됩니다.
자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가합니다.

이진 세마포는 Mutex라고도 부르며 Mutual Exclusion의 준말입니다.
0과 1 사이 값만 가능하며 다중 프로세스 간 Critical Section 문제를 해결하기 위해 사용합니다.

위 뮤텍스와 세마포 방법은 말로만 들으면 만능 기법이지만 당연히 단점이 존재합니다.

바쁜 대기

Busy Waiting

Critical Section에 진입해야하는 프로세스는 진입 코드를 계속 반복 실행해야하며 CPU 시간을 낭비했습니다.
진입을 실패한 프로세스를 block시킨 뒤 자리가 날 때 다시 깨우는 방식으로 해당 Busy Waiting을 해결합니다.

모니터

고급 언어의 설계 구조물로써 개발자의 코드를 상호배제 하게끔 만든 추상화된 데이터 형태입니다.
공유자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리합니다.

mutex가 보장되며 접근중인 스레드가 wait 상태일 때 새 스레드가 접근할 수 있게 됩니다.
새 스레드는 대기중인 스레드에게 notify할 수 있고 깨어난 스레드는 critical section에 진입할 수 있게 됩니다.

자바에서 싱글톤 패턴을 구현할 때 인스턴스의 생성 여부를 확인하기 위해 synchronized 키워드를 사용하곤 합니다.

데드락: 철학자의 만찬

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

데드락은 교착상태를 뜻합니다.

둘 이상의 프로세스가 Critical Section의 진입을 무한정 기다리고 있는 현상입니다.

만약 프로세스A가 자원1을 사용하는데 자원 2가 필요합니다.

동시에 프로세스B가 자원2를 사용하는데 자원 1이 필요합니다.

서로를 무한정 기다리며 교착상태에 빠지게 됩니다.

공유 자원에서 상호를 배제하다보면 발생할 수 있는 문제입니다.

발생 조건

• Mutual Exclusion: 상호를 배제한 상태 (포크는 동시에 한 철학자만 사용할 수 있다.)
• Hold and Wait: 최소 하나의 자원을 점유하면서 다른 자원까지 탐내는 상태 (포크를 하나 갖고 있지만 다른 포크도 기다린다.)
• No preemption: 이미 할당된 자원을 빼앗을 수 없는 상태 (사용중인 포크를 빼앗을 수 없다.)
• Circular wait: 순환 형태로 자원을 대기하는 상태 (모든 철학자가 포크를 기다린다.)

대처

1. 예방

   • 상호배제 부정: 여러 프로세스가 자원을 공유한다.
   • 점유대기 부정: 프로세스 실행 전 모든 자원을 할당한다.
   • 비선점 부정: 점유중인 자원을 요구하면 반납
   • 순환대기 부정: 자원에 고유번호 할당 후 순서대로 자원 요구

2. 회피

   • 은행원 알고리즘
     프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사

3. 탐지

   • 자원 요청 시 탐지

4. 회복

   • 교착상태를 일으킨 프로세스를 종료하거나 자원을 해제

References

• Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』
• https://worthpreading.tistory.com/90
• 면접질문
• 모니터