프로세스들은 서로 협력하며 영향을 주고 받음
이 과정에서 자원의 일관성을 보장해야함! → 프로세스들의 동기화
동기화?
프로세스들의 수행 시기를 맞추는 것
동기화의 의미는 두 가지가 있음
1. 실행 순서 제어
프로세스를 올바른 순서대로 실행
•
reader writer problem
파일에 값을 저장하는 프로세스와 파일에 저장된 값을 읽는 프로세스가 동시에 실행된다면?
⇒ 실행 순서를 제어하도록 동기화
2. 상호 배제
동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하도록 함
•
Bank account problem
계좌에 잔액이 10만원이 남아있을 경우, 현재 잔액에 2만원을 추가하는 프로세스와 현재 잔액에 5만원을 추가하는 프로세스가 동시에 실행된다면?
•
Producer & Consumer problem
물건을 계속해서 생산하는 생산자와 물건을 계속해서 소비하는 소비자가 총합이라는 변수를 공유하고 있다면?
생산자는 총합 + 1, 소비자는 총합 - 1
⇒ 공유가 불가능한 자원의 동시 사용을 피하기 위한 동기화
공유 자원
여러 프로세스 / 스레드가 공유하는 자원
임계 구역 Critical Section
동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
임계 구역에 동시에 접근하면 자원의 일관성이 깨질 수 있음 ⇒ Race Condition (경쟁 상태)
임계 구역에 진입하고자 하면 진입한 프로세스 이외에는 대기해야함
경쟁 상태 Race Condition
여러 프로세스나 스레드가 동기화 메커니즘 없이 동시에 공유 자원에 접근하려는 상황
임계 구역 문제를 해결하는 3가지 조건
아래 3가지 조건을 모두 충족해야한다.
1. 상호 배제 Mutual Exclusion
한 프로세스가 임계 구역에서 동작중이라면 다른 프로세스는 접근할 수 없음
2. 진행 Progress
임계 구역에서 작업중인 프로세스가 없다면 진입하고자 하는 프로세스는 들어갈 수 있어야함
3. 유한 대기 Bounded Waiting
한 프로세스가 임계 구역으로 진입을 요청한 후, 다른 프로세스들이 임계 구역에 진입하는 횟수는 제한이 있어야 함 (임계 구역에 들어오기 위해 무한정 대기해서는 안된다)
동기화 기법
뮤텍스 락
critical section에 진입하는 프로세스는 lock을 획득하고 critical section을 빠져나올 때 lock을 방출함으로써 동시 접근을 막는 방법
화장실이 하나밖에 없는 식당과 같다.
화장실에 가기 위해서는 카운터에서 열쇠를 받아 가야한다.
카운터에 열쇠가 있다면 화장실에 사람이 없다는 뜻이고 열쇠를 이용해 화장실에 들어갈 수 있음.
카운터에 열쇠가 없다면 화장실에 사람이 있다는 뜻, 다른 사용자가 나올 때까지 기다려야함.
•
자물쇠 역할 : 프로세스들이 공유하는 전역변수 lock
•
Critical Section을 잠그는 역할: acquire 함수
프로세스가 임계 구역에 진입하기 전 호출
◦
임계 구역이 잠겨있다면? → 열릴 때까지 임계구역 반복확인 (lock이 false가 될 때까지)
◦
임계 구역이 열려있다면? → 임계 구역 잠그기 (lock을 true로 바꾸기)
•
Critical Section의 잠금을 해제하는 역할: release 함수
◦
임계 구역에서 작업이 끝나고 호출
◦
현재 잠긴 임계 구역을 열기 (lock을 false로 바꾸기)
특징
•
자원을 소유할 수 있고 책임을 가짐
•
상태가 0, 1 뿐이므로 Lock을 가질 수 있고, 소유하고 있는 스레드만이 이 Mutex를 해제할 수 있음
•
프로세스의 범위를 가지며 프로세스 종료될 때 자동으로 Clean up
한계점: 다중처리기 환경에서는 시간적인 효율성 측면에서 적용할 수 없음
세마포어
공유 자원이 여러 개 있는 경우에도 적용 가능한 동기화 방법
종류
•
카운팅 세마포어
가용한 개수를 가진 자원에 대한 접근 제어용으로 사용. 세마포어는 그 가용한 자원의 개수로 초기화
•
이진 세마포어
0 과 1 사이의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용
카운팅 세마포어를 기준으로!
레스토랑의 화장실에는 여러 개의 화장실이 있고 화장실 입구에는 현재 화장실의 빈 칸 개수를 보여주는 전광판이 존재
화장실에 가고싶다면 빈 칸의 개수를 확인하고 빈 칸이 1개 이상이라면 빈칸의 개수를 하나 뺀 다음에 화장실로 입장해야하고 나올 때 빈 칸의 개수를 하나 더해준다.
•
임계 구역에 진입할 수 있는 프로세스의 개수(사용 가능한 공유 자원의 개수) : 전역 변수 S
•
임계 구역에 들어가도 되는지 여부 알려줌: wait 함수
•
임계 구역 앞에서 기다리는 프로세스에 들어가도 된다는 신호 전달: signal 함
특징
•
자원 소유 불가
•
세마포어를 소유하지 않는 스레드가 세마포어를 해제할 수 있음
•
시스템 범위에 걸쳐 있다.
한계점
Busy waiting: 문이 열렸는지 닫혔는지 반복적으로 확인하면서 CPU 사이클을 낭비하게됨
⇒ 사용할 수 있는 자원이 없다면 대기상태
(해당 프로세스의 PCB를 대기 큐에 삽입 → CPU 자원이 필요없음)
사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦
(해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입)
세마포어는 여러개의 프로세스가 접근 가능한 공유자원을 관리하는 방식이고, 뮤텍스가 될 수 있음
뮤텍스는 한 번에 한 개의 프로세스만 접근 가능하도록 관리하는 방식으로 뮤텍스는 세마포어가 될 수 없음
또, 세마포어는 다른 프로세스가 세마포어를 해제할 수 있지만, 뮤텍스는 락을 획득한 프로세스만 락을 반환할 수 있음.
뮤텍스와 세마포어 모두 데이터 무결성을 보장할 수는 없으며 모든 교착상태를 해결하지는 못함.
상호배제를 위한 기본적인 문법이며 여기에 좀 더 복잡한 매커니즘을 적용해 개선된 성능을 가질 수 있도록 하는 것이 중요
모니터
사용자가 다루기에 편한 동기화 도구
모니터 안에는 하나의 프로세스만이 있을 수 있음
공유자원에 접근하고자하는 프로세스를 인터페이스를 위한 큐에 삽입
큐에 삽입된 순서대로 한 번에 하나의 프로세스만 공유 자원을 이용
조건 변수를 프로세스나 스레드의 실행 순서를 제어하기 위해 사용
•
조건변수.wait() : 대기 상태로 변경, 조건 변수에 대한 큐에 삽입
•
조건변수.signal() : wait()으로 대기 상태로 접어든 조건 변수를 실행 상태로 변
교착상태 DeadLock
두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하고 무한히 다음 자원을 기다리게 되는 상태
발생 조건
1.
상호 배제 Mutual exclusion
한 번에 한 프로세스만 자원을 사용할 수 있음
2.
점유 대기 Hold and Wait
최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야함
3.
비선점 No preemption
다른 프로세스가 자원의 사용을 끝낼 때까지 자원을 강제로 빼앗을 수 없음
4.
순환 대기 Circular wait
각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음
해결방법
1.
예방
4가지 조건 중 하나라도 만족되지 않도록 합니다.
•
상호 배제 부정 : 여러 프로세스가 공유 자원을 사용
•
점유 대기 부정: 프로세스 실행 전 모든 자원을 할당
•
비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납
•
순환 대기 부정: 자원에 고유 번호 할당 후 순서대로 자원을 요구
2.
회피: 알고리즘을 데드락이 발생하지 않도록 합니다.
•
은행원 알고리즘
◦
행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
◦
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
◦
안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
•
자원 할당 그래프 알고리즘
◦
자원과 프로세스에 대해 요청 간선과 할당 간선을 적용하여 교착 상태를 회피하는 알고리즘
◦
프로세스가 자원을 요구 시 요청 간선을 할당 간선으로 변경 했을 시 사이클이 생성 되는지 확인한다
◦
사이클이 생성된다 하여 무조건 교착상태인 것은 아니다
▪
자원에 하나의 인스턴스만 존재 시 교착 상태로 판별한다
▪
자원에 여러 인스턴스가 존재 시 교착 상태 가능성으로 판별한다
◦
사이클을 생성하지 않으면 자원을 할당한다
3.
회복: 교착상태가 발생할 때, 해결합니다.
교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
프로세스 종료 방법
•
교착 상태의 프로세스를 모두 중지
•
교착 상태가 제거될 때까지 하나씩 프로세스 중지
자원 선점 방법
•
교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
•
우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점
기아상태(Starvation)
여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때, 특정 프로세스가 영원히 자원 할당이 되지 않는 경우
해결하기 위해서는 우선순위 변경 필요(우선순위를 수시로 변경하거나, 오래 기다린 프로세스의 우선순위를 높여주거나, Queue를 사용)
•
교착상태: 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 상황
•
기아상태: 병행 프로세스에서 프로세스가 실행되는데에 필수적인 자원을 끊임없이 사용하지 못하는 상황