강의 주소 : 이화여대 반효경 교수님 운영체제 강의 (2014년)
Chapter 6. Process Synchronization 1 ~ 4
6.1 데이터 접근
컴퓨터 안에서 데이터를 접근하는 패턴
데이터가 저장되어 있는 위치(Memory address Space)에서 데이터를 가져와 연산(CPU Process) 후 그 결과를 Memory에 가져다 놓는다.
위 그림처럼 S-box를 공유하는 E-box가 여럿 있는 경우, Race Condition의 가능성이 있다.
6.2 OS에서 race contition이 발생하는 경우
1. 커널 수행 중 인터럽트 발생
- 커널 코드를 작동하며 커널의 count 메모리 변수를 1 증가시킨다고 하면, CPU는 메모리의 변수 값을 CPU의 레지스터로 불러들이고 그 레지스터 값을 1 증가 시킨 후 그 값을 메모리에 집어넣는다.
- 만약 CPU의 레지스터로 메모리 변수가 로드된 후 인터럽트가 발생하면, 위의 그림처럼 인터럽트 핸들러가 count 변수를 -1 하고 커널로 돌아온다.
- 이 때 커널은 이미 로드된 변수를 이용해 계산을 하기 때문에 결과적으로 -1이 적용되지 않는다.
-> 해결 1. 인터럽트가 넘어와도 하던 일을 모두 끝낼 때까지 인터럽트의 발생을 막는다.
2. 프로세스가 시스템 콜을 해서 커널모드를 수행 중인데, 타이머로 인해 컨텍스트 스위치가 일어나는 경우
-> 해결 1. 프로세스가 커널 모드에 있을 때는 할당시간이 끝나도 CPU를 뺏기지 않고, 유저모드로 돌아올 때 CPU를 뺏을 수 있도록 한다.
3. 멀티프로세서에서 공유메모리 내의 커널 데이터
-> 해결 1. 한 번에 하나의 CPU만이 커널에 들어갈 수 있도록 한다. 비효율적일 수 있음(커널 전체를 lock/unlock)
-> 해결 2. 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 한다.
6.3 Process Synchronization 문제
- 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있음
- 일관성 유지를 위해서는
협력 프로세스간의 실행 순서를 정리해주는 메커니즘 필요
Race condition : 동시에 여러 프로세스가 동일한 자료에 접근해 경쟁하는 현상으로 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.
-> Race condition을 막기 위해서는 concurrent process가 동기화되어야 한다.
6.4 The Critical-Section Problem
Critical-Section(임계 구역) : 각 프로세스의 code segment에 존재하는 공유 데이터를 접근하는 코드
6.5 Initial Attempts to Solve Problem
SW적으로 동기화 문제 해결 시 프로그램 해결법의 충족 요건
Mutual Exclusion(상호 배제) : 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.Process(진행) : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.Bounded Waiting(유한 대기) : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
가정)
1. 모든 프로세스의 수행 속도는 0보다 크다.
2. 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
크리티컬 섹션에 접근하기 전에 다른 프로세스, 스레드가 접근하지 못하도록 엔트리 섹션에 락을 걸어주고, 공유 데이터의 접근이 종료되면 exit 섹션에서 락을 풀어준다.
6.6 Algorithms
1. turn 변수 사용
-
turn은 프로세스 번호로, 자기 차례가 아니면 while문을 돌며 계속 기다린다. 크리티컬 섹션에서 나올 때 다른 프로세스 번호를 넘겨준다.
-> 상호 배제 조건을 만족하지만 진행 조건을 만족하지 못함(반드시 교대로 돌아가기 때문)
2. flag 변수 사용
-
프로세스 2개가 각각 자신의 flag(크리티컬 섹션에 들어가겠다는 의중을 표현한 것)를 가지고 있다.
-
flag를 참으로 만들고(초기의 flag는 false) 상대방의 flag를 확인한 후 크리티컬 섹션에 들어간다. 크리티컬 섹션에서 나올 때는 flag를 거짓으로 해놓는다.
-> 상호 배제 조건을 만족이지만 진행 조건을 만족하지 못함(두 프로세스 모두 끊임 없이 양보하는 상황이 발생할 수 있기 때문)
3. Peterson's Algorithm
/* 프로세스 i와 j가 크리티컬 섹션에 들어가는 과정 */
// Process i
do {
flag[i] = true:
turn = j;
while(flag[j] && turn == j);
// critical section
flag[i] = false;
// remainder section
} while(true);
// Process j
do {
flag[j] = true:
turn = i;
while(flag[i] && turn == i);
// critical section
flag[j] = false;
// remainder section
} while(true);-
turn과 flag 변수를 모두 사용한다.
-
프로세스가 들어갈 때 깃발을 들고 turn을 상대방에게 준다.
-
상대방이 깃발을 들고 있고, turn도 상대방이면 기다린다. 즉, 상대방이 깃발을 내렸거나 turn이 자기 차례이면 크리티컬 섹션에 들어간다.
-
나올 때는 깃발을 내린다.
-> 모든 조건 만족
-> Busy Waiting(= spin lock)의 문제 발생 : 계속 CPU와 Memory를 쓰며 wait
왜 프로세스 동기화 소스가 복잡해지는가?
고급 언어가 여러 개의 instruction으로 구성되어 있어, 라인 하나하나를 체크해주어야 하기 때문이다.
6.7 Synchronization Hardware
하드웨어적으로 동기화 문제 해결
test & set Instruction
- 하드웨어적으로 읽고 쓰는 두 가지 작업을 한 번에 원자적(atomic)으로 수행
- atomic 구문으로 이루어진 구간은 처음부터 끝까지 preemption이 일어날 수 없다.
6.8 Mutex(Mutual Exclusion) Locks
- Critical Section Problem을 해결하기 위한 SW 도구 중 가장 단순한 방법
- lock이 하나만 존재할 수 있는 locking 메커니즘을 따름
- 이미 하나의 프로세스가 크리티컬 섹션에서 작업 중이면 다른 프로세스들은 크리티컬 섹션에 들어갈 수 없도록 함
6.9 Semaphores
Semaphores란?
여러 프로세스나 스레드가 크리티컬 섹션에 진입할 수 있는 Locking 메커니즘
- S : 세마포어 변수로 사용 가능한 자원의 개수 의미
- P(S) : 공유 데이터를 획득하는 연산
- V(S) : 자원을 반납하는 연산
Critical Section에 Semaphores 적용 : Block & Wakeup
프로그래머는 세마포어를 이용해 P, V 연산만 수행하면 된다.
하지만 이 방식은 busy-wait가 발생(P 연산 중 자원이 없을 경우 계속 while문을 돌며 기다림)하므로 효율적이지 못하다. -> Block & Wakeup 방식 구현
- P(S) : 자원이 있으면 자원을 하나 가져오는 연산, 자원이 없을 경우 대기(block)
- V(S) : 자원을 반납하고 대기 상태의 프로세스를 깨워주는 연산(wakeup)
Busy-wait vs Block/wakeup
- 크리티컬 섹션의 길이가 긴 경우 Block/wakeup이 적당
- 크리티컬 섹션의 길이가 매우 짧은 경우 Block/wakeup의 오버헤드가 Busy-wait 오버헤드보다 더 커질 수 있음
- 일반적으로는 Block/wakeup 방식이 더 좋음
2 types of Semaphores
- Counting semaphore
- 도메인이 0 이상인 임의의 정수값
- 주로 resource counting에 사용
- Binary semaphore(=mutex)
- 0 또는 1의 값만 가질 수 있는 semaphore
- 주로 mutual exclusion(lock/unlock)에 사용
Semaphores 사용 시 주의점
- Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
- Starvation : 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
6.10 Classical Problems of Synchronization
세마포어를 이용해 해결하는 고전적인 동기화 문제로 유명한 3가지
1. Bound-Buffer Problem
- Producer 프로세스 : 공유 버퍼에 데이터를 만들어 넣는 역할
- Consumer 프로세스
- 공유 자원 : 버퍼
문제 1. 생산자 여럿이 동시에 도착해 비어있는 버퍼에 동시에 데이터를 집어넣을 때(소비자도 마찬가지) -> 동시에 버퍼에 접근할 수 없도록 락을 걸어주는 용도로 세마포어 변수 사용
문제 2. 버퍼가 가득찬 상태에서 생산자가 또 도착해 버퍼에 데이터를 집어넣을 때 소비자가 도착해 자원을 사용할 때까지 기다림(소비자도 마찬가지) -> 가용자원의 개수를 새는 세마포어 변수 사용
2. Readers and Writers Problem
- Reader 프로세스
- Writer 프로세스
- 공유 자원 : DB
문제 1. 한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근할 때(read는 동시에 여럿이 해도 됨)
-> writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들이 DB에 접근할 수 있도록
-> writer는 대기 중인 reader가 하나도 없을 때 DB 접근 허용
-> writer가 DB에 접근 중이면 reader는 접근 금지(writer가 DB에서 빠져나가야 reader의 접근 허용)
3. Dining-Philosophers Problem
철학자 5명이 원탁에 앉아있다. 철학자들이 식사를 하기 위해서는 양쪽 젓가락을 모두 집어야 한다.
- 공유 자원 : 젓가락
문제 1. Deadlock의 가능성 존재(모든 철학자가 동시에 왼쪽의 젓가락을 들 경우, 아무도 식사를 할 수 없게 됨)
-> 4명의 철학자만이 동시에 테이블에 앉도록
-> 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있도록
-> 비대칭 : 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 잡도록
6.11 Monitor
Semaphore의 문제점
- 코딩이 힘들다.
- 정확성의 입증이 어렵다.
- 자발적 협력이 필요하다.
- 한번의 실수가 모든 시스템에 치명적 영향을 끼친다.
-> 세마포어의 단점을 보완할 수 있는 구조 : Monitor
- 동시 수행중인 프로세스 사이에서 추상 데이터의 안전한 공유를 보장하기 위한 high-level 동기화 구조
- 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.
- 공유 데이터에 접근하기 위해서는
모니터의 내부 Procedure를 통해서만 접근할 수 있으며 동일한 시간에 오직 한 프로세스/스레드만 모니터에 들어갈 수 있다. - 세마포어와의 가장 큰 차이점은
락을 걸 필요가 없는 것이다. 세마포어는 프로그래머가 직접 wait/signal을 사용해 race condition을 해결해야 하지만 모니터는 자체적인 기능으로 해결할 수 있게 된다. - 모니터에 진입하려고 했지만 내부에 프로세스가 들어있어 진입하지 못한 프로세스들은
모니터 큐에서 기다린다. 프로세스가 모니터 내에서 기다릴 수 있게 하도록조건 변수(Condition variable)가 사용된다. - 조건 변수는 wait/signal 연산만으로 사용될 수 있다. 세마포어 변수와 유사하지만
변수가 어떤 값을 가지지 않고 자신의 큐에 프로세스를 매달아 sleep시키거나 큐에서 프로세스를 깨우는 역할만 한다.
