[OS] 운영체제(5장) 프로세스 동기화 - 1
1. 배경
협력 프로세스(Cooperating process)
- 다른 프로세스의 실행을 영향을 주거나 받는 프로세스
- 서로 비동기적으로 수행하면서 데이터를 공유할 수 있음
공유 방법
- 직접 공유 : 논리 주소 공간(메모리) 공유
- 간접 공유 : 파일 또는 메시지를 경유
공유 데이터에 대한 병행/병렬 접근은 데이터 일관성을 보장하지 못할 수 있음 → data inconsistency
병행/병렬 실행 환경
- CPU 스케줄링 : 한 프로세스가 일부만 실행한 상태에서 다른 프로세스로 스케줄될 수 있음
- 인터럽트 : 프로그램의 어떠한 지점에서도 인터럽트가 가능
- 병렬 실행 : 여러 개의 프로세스가 동시에 실행됨(코어가 여러개 있으면 병렬 실행 가능)
데이터 일관성 유지
협력 프로세스들이 바른 순서로 실행(orderly execution)하는것을 보장하는 메커니즘이 필요
생산자-소비자 문제-공유 데이터 사용
유한 버퍼를 사용한 생산자-소비자 문제
경쟁 조건(race condition)
- 여러 개의 프로세스가 공유 자료를 접근하여 조작하고
- 그 실행 결과가 자료 접근 순서에 영향을 받는 상황 → non-deterministic 결과
경쟁 조건에서의 가능한 결과
3가지 결과가 가능함
병행 접근(Concurrent Access)
단일 프로세서 시스템에서
선점(preemptive) 스케줄링을 사용할 때에, 경쟁 조건이 발생할 수 있음 (비자발적 CPU 작업 교체)
병렬(Parallel) 접근
다중 프로세서 시스템에서
스케줄링 알고리즘에 관계없이, 경쟁 조건이 발생할 수 있음
2. 임계 구역(Critical-Section) 문제
프로세스(쓰레드)가 공유 자원을 변경할 수 있는 코드 부분
- 공유 자원 - 공유 변수, 테이블, 파일 등
임계 구역 문제
프로세스들이 임계 구역에서 경쟁조건이 발생하지 않도록 서로 협력하기 위해 사용할 수 있는 프로토콜을 설계하는 것 → 프로세스 동기화와 조정
임계 구역 문제의 해결책
프로세스의 일반 구조
3가지 필요조건
- 상호배제(Mutual Exclusion)
- 진행(Progress)
- 한정 대기(Bounded Waiting)
가정
- 프로세스들의 상대 속도를 가정하지 않음.
- 프로세스들은 0이 아닌 속도로 실행됨
상호 배제(Mutual Exclusion)
프로세스가 자신의 CS에서 실행 중이라면 다른 프로세스들은 자신의 CS에서 실행될 수 없음
동시에 두 개 이상의 프로세스가 임계 구역(CS)에서 실행될 수 없음
진행(Progress)
CS에서 실행되는 프로세스가 없고, 자신의 CS로 진입하려는 프로세스가 있다면
- 나머지 구역(remainder section)에서 실행하지 않는 프로세스들 만이 CS에 진입하는 프로세스 결정에 참여하고
- 이 선택이 무한히(indefinitely) 지연될 수 없음 → progress
◼ CS 밖에서 수행중인 프로세스는 다른 프로세스를 block할 수 없음
한정 대기(Bounded Waiting)
프로세스가 CS 진입을 요청한 후에 요청이 허용될 때까지 다른 프로세스가 CS 진입이 허용되는 횟수에 제한이 있어야 함
어떤 프로세스도 CS 진입을 영원히 기다리지 않아야 함
커널에서의 경쟁조건과 선점/비선점 커널
커널에서의 경쟁 조건
커널에서 여러 개의 커널 모드 프로세스(루틴)이 활성화될 수 있으며 커널 자료구조를 공유할 수 있음 → 경쟁조건 발생 가능
커널은 경쟁조건이 발생하지 않도록 설계해야 함.
임계 구역을 다루기 위한 운영체제 커널의 두 가지 방식
- 선점형(preemptive) 커널 – 커널모드에서 프로세스가 선점되는 것을 허용
- 경쟁조건이 발생하지 않도록 설계해야 함
- SMP 시스템에서는 특히 어려움
- 비선점형(nonpreemptive) 커널 – 커널모드에서 프로세스가 선점되는 것을 허용하지 않음
- 경쟁조건이 발생하지 않도록 다음 상황까지 프로세스를 계속 실행 (1) 커널 모드 종료 (2) 봉쇄(block) (3) 자발적 양보(yield)
3. Peterson의 해결안
Peterson 알고리즘
임계 구역 문제에 대한 고전적인 소프트웨어 기반 해결방안
- 두 프로세스에 대해서만 적용 가능 (P0, P1)
동기화 변수
프로세스들의 동작을 동기화하는 데 사용하는 공유 변수
Peterson 알고리즘에서의 동기화 변수
int turn; (initially turn=0)
boolean flag[2]; (initially, flag[0]=flag[1]=false)
- if (turn==i) then Pi can enter its critical section (Pi 차례)
- if (flag[i] == true) then Pi ready to enter its critical section (Pi 준비)
if flag[0] is true and flag[1] is false → P0’s turn (하나만 CS 진입 요청) if both flag[0] and flag[1] are true → Pturn’s turn (둘 다 CS 진입 요청)
Peterson 알고리즘
Process Pi 의 구조 (다른 프로세스: Pj, j = 1 – i )
세 필요조건을 충족
- 상호 배제 – 둘 다 진입 불가 (turn에 의해서 하나만 진입 가능)
- 진행 – 상대장의 flag가 false이면 바로 CS진입, 두 flag 모두 true이면 turn이 0 또는 1의 값을 가지므로 둘 중 하나는 CS로 진입
- 한정대기 – 상대방의 수행이 끝나면 flag가 false가 되므로 CS진입. 상대방 flag가 다시 true가 되어도, turn을 넘겨주므로 CS 진입
임계 구역을 구현하는 소프트웨어 알고리즘
2 프로세스 알고리즘
- Peterson 알고리즘
- Dekker 알고리즘 (Exercise 5.10/6.2)
n-프로세스 알고리즘 → 훨씬 복잡
- Eisenberg and McGuire 알고리즘 (Exercise 5.11/6.3)
- Dekker 알고리즘의 확장
- Bakery 알고리즘 – Lamport
알고리즘 방식은 실제로 널리 사용되지 않음
- 매우 복잡함
- 정확성(올바르게 동작함)에 대한 증명이 복잡함
댓글남기기