프로세스 동기화 Process Concurrency
뮤추얼 익스클루션 (mutual exclusion) : 한번에 한 프로세스씩 엑세스하는 성질
크리티컬 섹션 (critical section) : 프로그램 코드에서 다른 프로세스와 공유하는 메모리 영역을 접근하는 부분 - 크리티컬 섹션 프로블럼 (critical section problem)
스타베이션 (starvation) : 컴퓨터 자원을 요청했는데 오랫동안 배정되지 않아서 기다리는 것
데드락 (deadlock) : 영원히 스타베이션하는 경우
비지 웨이팅 (busy waiting) : 조건이 성립할 때까지 반복문을 실행하며 기다리는 방법
어토믹 오퍼레이션 (atomic operation) : 크리티컬 섹션을 마치 어셈블리 인스트럭션 한 문장인 것처럼 실행하는 것. (실행 중 중단되지 않음) 인터럽트가 발생하더라도 바로 처리되지 않음.
레이스 컨디션 (race condition) : 크리티컬 섹션 실행 시에만 발생. cpu의 스케줄링에 따라 결과가 달라질 수 있음.
프로그레스 (progress) : 크리티컬 섹션을 실행할 당시, 크리티컬 섹션을 실행하는 다른 프로세스가 없다면 지금 들어가기를 원하는 프로세스가 크리티컬 섹션에 들어갈 수 있도록 구현되어야 한다.
바운디드 웨이팅 (bounded waiting) : 크리티컬 섹션을 실행할 당시, 크리티컬 섹션을 실행하는 다른 프로세스가 있다면 지금 들어가기를 원하는 프로세스는 기다려야 한다. (바운디드 웨이팅이 무한정 지속되면 안 됨)
Critical section problem의 해결책
크리티컬 섹션 내에 오직 한 개의 프로세스만 들어가도록 하려면 다음 세 가지를 모두 만족해야 한다.
- 뮤추얼 익스클루션 (mutual exclusion)
- 프로그레스 (progess)
- 바운디드 웨이팅 (bounded waiting)
Readers / Writers problem
Writer는 크리티컬 섹션 프로블럼과 동일하고
Reader는 크리티컬 섹션에 여러 개가 들어갈 수 있다.
크리티컬 섹션을 어토믹하게 실행하는 법
- 크리티컬 섹션 실행 도중 인터럽트가 발생해 중단되지 않도록 잠시 동안 인터럽트를 비활성화 시킨다.
- 인터럽트가 발생할 수도 있지만 CPU가 발생 여부를 조사하지 않는 것 (인터럽트를 발생하지 못하게 막는 것이 아님)
레이스 컨디션을 방지하는 법
- 크리티컬 섹션을 어토믹 오퍼레이션으로 만들어 뮤추얼 익스클루션하게 실행한다.
- but, 크리티컬 섹션이 클 경우 시간이 오래 걸려 bad.
- 크리티컬 섹션 주변에 담장(fence)을 쳐서 뮤추얼 익스클루션하게 실행한다. (general)
- 이 때, 크리티컬 섹션 자체는 어토믹 오퍼레이션이 아니다. - 인터럽트 가능
- 소프트웨어적 방법
- 코드 앞의 엔트리 섹션 (entry section)과 코드 뒤의 엑시트 섹션 (exit section). but, 프로그레스 만족하지 않음.
- 피터슨 알고리즘 : but, only 2개의 프로세스일 때만 사용 가능.
- 베이커리 알고리즘 : but, 코드가 너무 길고 오래 걸리므로 bad.
- 하드웨어적 방법 : 어토믹 오퍼레이션 이용. OS에 미리 정의되어 매우 빠르게 실행 가능
- 테스트셋 (testset) : 효율적이고 간단하고 빠르다. but, 비지웨이팅을 사용하여 바운디드 웨이팅을 보장해주지 않고, 데드락이 발생 가능하다 (우선순위). bad.
- 세마포어 (semaphore) : 정수형 변수와 자신만의 큐가 같이 만들어지는 특수한 변수이다. 크리티컬 섹션으로 진입 가능하지 않음을 안 순간 blocked 상태로 바뀐다. best. but, 초기값을 컴퓨터 자원의 개수만큼 주어야 하는 점은 어려움
- 셈웨이트 (semWait) : sem-- . 어토믹 오퍼레이션
- 셈시그널 (semSignal) : sem++ . 어토믹 오퍼레이션
- semWait()와 semSignal()이 호출되는 횟수는 반드시 같아야 한다
세마포어는
- 크리티컬 섹션을 어토믹하게 실행하고자 할 때에 이용할 수 있고,
- 프로세스의 실행 순서를 제어할 때에 이용할 수도 있다.
+) 메세지 패싱을 이용한 동기화
데이터를 담은 메세지를 생성하여 send() 시스템 콜을 이용해 커널에게 보낸다. 받고 싶을 때 receive() 시스템 콜을 호출하여 하나 꺼내 갖는다.
- 블록킹 모드 (blocking mode)
- send와 receive가 계속 기다린다.
- 넌블록킹 모드 (non-blodking mode)
- send와 receive가 기다리지 않는다. 없으면 그냥 돌아옴.
프로세스 동기화를 위해서는 논블록킹 센드와 블록킹 리시브를 사용해야 한다.
Readers / Writers problem
wsem : Writer의 뮤추얼 익스클루션을 보장한다.
rsem : 하나의 Reader만이 readcount를 증가시킬 수 있다.
- Reader 들어가요
- Reader가 rsem을 뺀다.
- ++readcount == 1이면 첫 Reader는 크리티컬 섹션을 실행하는 Writer를 확인한다.
- Writer가 있다면 (돌이 없다면) 기다린다.
- Writer가 없다면 wsem을 빼고 rsem을 넣는다.
- +readcount != 1이면 바로 크리티컬 섹션으로 들어간다. (첫 Reader가 아님)
- Reader 나가요
- Reader가 rsem을 뺀다.
- --readcount != 0이면 rsem을 반납하고 끝
- --readcount == 0이면 rsem과 wsem을 모두 반납한다.
