프로세스 동기화
프로세스 동기화(Process Synchronization)
- 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것
• 여러 프로세스가 서로 협력해 공유자원을 사용하는 상황에서 경쟁조건(race condition)이 발생하면 공유자원의 신뢰성이 떨어진다. 이를 방지하기 위해 프로세스들이 공유자원을 사용할 때 특별한 규칙을 만드는 것
경쟁조건이란(race condition)?
- 커널 수행 중 인터럽트 발생 시, 커널 수행 중 context switching 발생 시, 멀티 프로세서에서 커널 내부 shared data 동시 접근하는 경우
임계구역 (critical section): 멀티 프로세스에서 race conditon을 해결하기 위해 하나 씩 들어갈 수 있도록 임계구역으로 해결 , 하나의 프로세스가 critical section에 있을 때 다른 프로세스가 못 들어오게 해야 함
임계구역으로 인해 발생하는 문제들 해결하기 위한 조건
1.상호배제
- 이미 한 프로세스가 Critical Section에서 작업 중이면 다른 모든 프로세스는 Critical Section에 진입하면 안 된다.
2.진행
- Critical Section에서 작업 중인 프로세스가 없다면, Critical Section에 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야 한다.
3.한정 대기
- 프로세스가 Critical Section에 들어가기 위해 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 한다. 쉽게 말해, Critical Section에 진입하려는 프로세스가 무한정 기다려서는 안 된다.
피터슨 알고리즘
임계구역에 대한 고전적인 소프트웨어 기반 해결책을 설명, 임계구역 문제를 해결하기 위한 좋은 알고리즘적인 설명을 제공하고 상호 배제, 진행, 한정된 대기의 요구 조건을 중점으로 다루는 소프트웨어를 설계하는데 필요한 복잡성을 잘 설명하는 알고리즘이며 임계구역 문제를 해결하기 위한 3가지 조건을 모두 만족하는 알고리즘
뮤텍스(상호배제):
- 커널 모드 동기화 객체
- 동시 프로그래밍 환경에서 공유 불가능한 자원의 동시 사용을 막기 위해 사용되는 알고리즘
- 임계 구역에서 구현
- Lock을 가진 쓰레드만이 임계구역에 접근할 수 있고, 작업이 끝난 쓰레드는 Unlock하여 lock 반환
세마포어
- 세마포어는 복수개의 스레드가 임계 구역 접근 가능
- Wait ,signal 로 구현
- Wait이 먼저 호출되어 임계 구역에 들어갈 수 있는지, 우선적으로 실행되어야 할 스레드가 실행되는지 확인
- 세마포어는 뮤텍스가 될 수 있지만 그 반대는 안됨
모니터
- 하나의 프로세스 내 다른 스레드 간의 동기화에 사용
- 라이브러리 혹은 프레임워크가 제공(java에 존재)
- Synchronized ,wait(),notify() 등의 키워드로 편하게 동기화 가능
교착상태
교착 상태(Dead Lock)란 ?
- 상호 배제에 의해 나타내는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상
교착 상태 조건
- 상호배제 : 한번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.
- 점유와 대기 : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
- 비선점 : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
- 순환 대기 : 공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.
교착 상태 해결 방법 :
-
예방기법 : 교착 상태 발생 조건 중 하나를 제거하면서 해결한다.(자원 낭비가 심함)
상호배제 부정 : 여러 프로세스가 공유 자원 사용
점유대기 부정: 프로세스 실행전 모든 자원을 할당
비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구 -
회피 기법 : 교착 상태 발생 시 피해나가는 방법
은행원 알고리즘 :
은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
프로세스가 자원을 요구 할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
안정 상태면 자원 할당,아니면 다른 프로세스들이 자원 해지까지 대기 -
발견 기법 : 자원 할당 그래프를 통해 교착 상태를 탐지함, 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생
-
회복 기법 : 교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
교착 상태가 제거될 때까지 하나씩 프로세스 중지
교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당
우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 프로세스 자원 선점
식사하는 철학자 문제
- 5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.
만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면, 모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다. 그런데 모든 철학자들이 그러고 있다. 이 상태에서는 모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 수가 없게 되는데, 이것이 교착(Deadlock)상태이다.
- 해결방법 1: 포크개수 늘리기 - >전부가 포크를 하나씩 집어도 1명은 2개의 포크로 식사를 마치고 이과정을 반복한다.
- 해결방법 2: 홀수 번 철학자, 짝수 번 철학자를 구분 후 홀수 번 철학자 인 경우 포크를 왼쪽,오른쪽 순으로 집어서 밥을 먹고 포크를 왼쪽,오른쪽 순으로 놓는다. 짝수 번 철학자인 경우는 포크를 오른쪽,왼쪽 순으로 집어서 밥을 먹고 포크를 오른쪽 왼쪽 순으로 놓는다.(순환 대기 해결하여 문제 해결)
- 해결방법 3: 각각의 철학자 상태 구분 -> 철학자가 EATING 상태가 되기 위해서 자신이 Hungry상태이고, 자신의 왼쪽,오른쪽 모두 EATING 상태가 아니어야 한다.
Hungry: 철학자가 포크 집기를 원함.(임계 구역 접근을 원함)
Thinking:철학자가 포코 집기를 원치 않음(임계구역 접근을 원치 않음)
Eating: 철학자가 2개의 포크을 집어 밥을 먹는다.(임계구역에 접근함)
