프로세스 동기화
여러 프로세스가 동시에 실행될 때 발생할 수 있는 문제를 해결하기 위한 기술
공유자원&경쟁상태&임계구역
공유자원
•여러 프로세스가 동시에 접근하여 사용할 수 있는 자원
•파일, 데이터베이스, 메모리 영역 등이 공유 자원의 예시
•프로세스 간에 공유 자원에 대한 접근을 조정하지 않으면 예기치 않은 결과가 발생할 수 있다
경쟁상태
•여러 프로세스가 공유 자원에 동시에 접근하고 수정하려고 할 때 발생하는 상황•경쟁 상태는 동시성 제어 없이 프로세스가 실행되는 경우 예기치 않은 결과를 초래할 수 있다
임계구역
공유 자원에 접근하는 코드 영역=>한 번에 하나의 프로세스만 접근할 수 있도록 보장해야 합니다
경쟁 상태로 인해 여러 프로세스가 동시에 임계 구역에 접근하여 예기치 않은 결과가 발생하는 상황
임계 구역에 대한 상호 배제(Mutual Exclusion)를 제공한다
피터슨 알고리즘
상호 배제 문제를 해결하기 위한 클래식한 프로세스 동기화 알고리즘
프로세스 간의 임계 구역에 대한 안전한 접근을 보장하기 위해 사용
1961년에 피터슨에 의해 제안되었으며, 두 개의 프로세스가 상호 배제를 위해 경쟁하는 경우를 가정
두 개의 프로세스만 경쟁한다고 가정했을때
1.프로세스는 무한 반복문을 실행하며, 임계 구역에 진입하기 전에는 특정 조건을 만족해야 한다
2.두 프로세스는 서로의 동작을 신뢰한다고 가정한다.
피터슨 알고리즘은 두 개의 중요한 변수를 사용한다.
turn: 임계 구역에 들어갈 차례를 가진 프로세스를 나타내는 변수
0 또는 1의 값을 가진다..
flag: 자신의 차례를 원하는 의도를 표시하는 변수
flag 변수는 각 프로세스마다 0 또는 1의 값을 가진다
뮤텍스
•프로세스 동기화를 위해 사용되는 동기화 객체
•상호 배제를 제공하여 임계 구역(critical section)에 대한 안전한 접근을 보장
이진 상태: 잠금(lock) 상태와 잠금 해제(unlock) 상태를 가진다.
잠금 상태에서는 뮤텍스를 소유한 프로세스만 임계 구역에 접근할 수 있으며,
잠금 해제 상태에서는 다른 프로세스가 뮤텍스를 획득하여 임계 구역에 접근할 수 있다.
원자적 연산: 뮤텍스는 원자적(atomic) 연산으로 구현되어야 한다.
즉, 뮤텍스의 잠금(lock)과 잠금 해제(unlock) 연산은 어떤 다른 연산도 중간에 끼어들지 않고 원자적으로 실행되어야 하고,이를 통해 두 개 이상의 프로세스가 동시에 뮤텍스를 획득하는 상황을 방지할 수 있다.
소유 기반: 뮤텍스는 소유 기반(mutex ownership)으로 동작.
즉, 뮤텍스를 획득한 프로세스만이 해당 뮤텍스를 해제할 수 있다.
이를 통해 임계 구역에 대한 접근을 제한하고, 뮤텍스를 잘못 해제하는 상황을 방지한다.
세마포어
프로그래밍과 운영체제에서 동기화를 위해 사용되는 도구
세마포어는 일종의 카운터로서, 두 가지 기본 연산인 P(Proberen)와 V(Verhogen)를 지원
P(Proberen): 세마포어를 얻으려는 프로세스나 스레드가 실행되면 세마포어 값을 1 감소시. 만약 세마포어 값이 0이라면, 해당 프로세스나 스레드는 대기 상태로 전환됨
V(Verhogen): 세마포어 값을 1 증가시킨다
다른 프로세스나 스레드가 대기 중이었다면, 이를 깨우고 실행 가능한 상태로 전환시킨다.
세마포어의 두가지 유형
이진 세마포어(Binary Semaphore): 값이 0 또는 1인 세마포어로, 상호 배제(Mutual Exclusion)에 사용되고,
주로 크리티컬 섹션에 대한 접근을 제어하는 데 사용된다.
뮤텍스(Mutex)라고도 불린다.
카운팅 세마포어(Counting Semaphore): 값이 음수가 아닌 정수인 세마포어로, 한정된 수의 리소스에 대한 접근을 제어하는 데 사용된다
예를 들어, 프로듀서-컨슈머 문제에서 생산된 아이템의 수를 추적하고, 소비자가 소비할 때마다 값을 감소시킴으로써 생산과 소비를 조절할 수 있.
모니터
•상호 배제와 조건 변수(Condition Variable)를 조합한 동기화 도구
•프로그래밍 언어나 운영체제에 내장된 개념으로, 여러 프로세스 또는 스레드 간의 동시 접근을 제어하고 상호작용하는 데 사용된다.
•상호 배제(Mutual Exclusion): 모니터 내부에는 크리티컬 섹션(Critical Section)이 존재하며, 오직 하나의 스레드만이 크리티컬 섹션에 접근할 수 있고, 이를 통해 동시에 여러 스레드가 공유 자원에 접근하는 것을 제어할 수 있다.
•조건 변수(Condition Variable): 모니터는 조건 변수를 사용하여 스레드의 실행 흐름을 제어할 수 있다.
조건 변수는 스레드가 특정 조건을 만족할 때까지 대기하도록 할 수있고,
대기 중인 스레드는 다른 스레드가 조건을 만족시킬 때까지 블록되며,
조건이 충족되면 알림을 받아 실행 가능한 상태로 전환된다.
교착상태
교착상태 정의
여러 프로세스 또는 스레드가 서로가 점유한 자원을 기다리면서 무한히 대기 상태에 빠지는 상황을 말합니다
교착상태 조건
상호 배제(Mutual Exclusion): 자원은 동시에 하나의 프로세스 또는 스레드만이 점유할 수 있어야 한다.
즉, 자원은 동시에 여러 개의 프로세스 또는 스레드에 의해 점유될 수 없다.
점유와 대기(Hold and Wait): 최소한 하나의 자원을 점유한 상태에서 다른 자원을 기다려야 한다 즉, 프로세스나 스레드는 점유한 자원을 반납하지 않고 다른 자원을 기다려야한다.
비선점(No Preemption): 다른 프로세스 또는 스레드가 점유한 자원을 강제로 빼앗을 수 없어야 한다.
자원은 점유한 프로세스 또는 스레드가 명시적으로 반납하기 전까지 유지된다.
순환 대기(Circular Wait): 여러 프로세스 또는 스레드 간에 자원 점유에 대한 순환적인 대기 관계가 형성되어야 한다
즉, 프로세스나 스레드의 체인이 형성되어 각각이 다음 프로세스나 스레드가 점유한 자원을 기다리는 상태여야 한다.
교착 상태 해결방법
예방(Prevention): 예방은 비효율적이고 자원 사용률을 저하시킬 수 있으므로, 실제로는 교착상태의 발생 가능성을 낮추기 위한 설계 원칙을 따른다.
예를 들어, 자원 할당 순서를 일정하게 유지하거나 자원 요청에 대한 우선순위를 정의하는 등의 방법을 사용한다.
회피(Avoidance): 교착상태가 발생할 가능성이 있는지 동적으로 검사하고, 발생 가능성이 있는 상황에서는 자원 할당을 회피하는 방법입이다.
이를 위해 자원 할당 그래프를 생성하고, 안전 상태인지 여부를 판단하여 자원 요청을 승인 또는 거한다.
안전 상태일 때만 자원을 할당하여 교착상태를 회피한다.
은행원 알고리즘이 회피 방법 중 하나이다.
탐지(Detection): 교착상태가 발생하면 이를 감지하여 적절한 조치를 취하는 방법, 감지하기 위해 자원 할당 그래프나 자원 사용 상태를 모니터링하고, 사이클이 형성되어 교착상태가 발생하는지 확인한다.
교착상태가 감지되면 대응 방안을 취하며, 일반적으로 교착상태에 있는 프로세스나 스레드 중 하나를 중단시키거나, 자원을 선점하여 교착상태를 해제한다.
회복(Recovery): 교착상태가 발생했을 때 복구하는 방법이다.
일반적으로 교착상태를 회복하기 위해서는 자원 선점 또는 프로세스나 스레드를 중단시키는 방법을 사용한다. 선점은 자원을 강제로 빼앗아 다른 프로세스나 스레드에게 할당하는 것을 의미하며, 중단은 교착상태에 있는 프로세스나 스레드를 종료시키는 것을 의미한다.
식사하는 철학자문제
•상호 배제와 교착상태 문제를 보여주기 위한 전통적인 동기화 문제
1.다섯 명의 철학자가 원형으로 앉아 식사를 한다
2.각 철학자는 식사를 위해 포크(자원) 두 개를 필요로 한다.
3.철학자는 식사를 하거나 생각을 하는 두 가지 상태를 가진다.
4.철학자는 인접한 두 포크를 사용하여 식사를 할 수 있다.
•교착상태(Deadlock)의 대표적인 예제
모든 철학자가 왼쪽 포크를 잡고 오른쪽 포크를 기다리면서 무한히 대기하는 상황이 발생할 수 있으며,
이러한 교착상태는 각 철학자가 순환적으로 다른 철학자가 점유한 포크를 요청하면서 형성될수 있다
교착상태 4가지 필요조건
- 상호 배타(Mutual Exclusion)
젓가락은 한 번에 한 철학자만 사용할 수 있다. - 점유와 대기(Hold and Wait)
집어든 젓가락은 계속 들은채로 사용중인 반대쪽 젓가락을 기다린다. - 비선점(No Preemption)
이미 누군가 집어든 젓가락을 강제로 뺏을 수 없다. - 환형대기(Circular Wait)
모든 철학자들이 자신의 오른쪽에 앉은 철학자가 젓가락을 놓기를 기다린다.
교착상태 해결(Deadlock)
위의 4가지 조건을 프로그램이 전부 성립하는 일이 없게끔 하면 된다
4가지 중 하나만 어겨도 데드락이 발생하지 않기때문이다
