Process Synchronization 문제
Concurrency Control(병행 제어)이라고도 한다. 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 Process Synchronization 문제라고 한다.
일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정리해주는 메커니즘이 필요하다.
데이터 접근 과정
- 데이터가 저장되어 있는 곳 (Storage-Box)
- 연산할 데이터를 Storage-Box에서 Execution-Box로 가져온다
- 데이터를 연산하는 곳 (Execution-Box)
- 연산 결과를 Storage-Box에 반영한다.
S-box를 공유하는 E-box가 여러 개 있는 경우, Race Condition과 Synchronization 문제가 발생할 가능성이 있다.
어떤 E-box가 특정 데이터를 연산하는 동안 같은 데이터에 다른 E-box가 접근하여 또 다른 연산을 하게 된다면 이전의 연산이 반영되지 않을 것이다.
예를 들어 CPU가 여러 개인 multiprocessor system에서 공유 메모리를 사용하거나, 커널 내부 데이터를 접근하는 여러 루틴이 실행되면 이런 문제가 발생할 수 있다.
OS에서의 race condition
✅ Race condition이란?
- 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다
- Race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다.OS에서 race condition은 언제 발생할까? 다음과 같이 세 가지 경우가 있다.
(1) kernel 수행 중 interrupt 발생
커널 모드 running 중 interrupt가 발생하여 interrupt 처리 루틴이 수행되는 경우.
양쪽 모두 커널 코드이기 때문에 kernel address space를 공유하고 있어 같은 데이터가 접근할 수 있다.
위와 같은 경우 count++ 연산이 결과가 아직 저장되지 않았을 때 interrupt가 발생해서 count-- 연산이 진행되었기 때문에 count-- 연산 결과는 원래 데이터에서 1 감소한 값이다.
이때 count++ 연산도 count--연산 결과가 반영되지 않았을 때 가져온 데이터에서 진행되고 있었기 때문에 결과적으로 데이터는 count++ 연산만 수행된 것으로 바뀐다.
이를 해결하기 위해서 kernel에서 데이터를 수정하고 있을 동안은 interrupt를 수행하지 않고 있다가 (즉, 위 그림에서 빨간색 동그라미 사이 구간 동안에는 interrupt를 수행하지 않음) 그 이후에 interrupt를 수행하도록 한다.
(2) Kernel mode에 있는데 CPU를 뺏긴 경우
Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 발생한 경우
위와 같은 경우 Process A에서 user mode를 하다가 system call을 하여 kernel mode로 count++를 수행하고 있는데, Process A에게 CPU를 할당한 시간이 끝나서 time interrupt가 발생하여 CPU가 Process B에게 넘어갔다.
때문에 count++ 연산이 2번 실행되었음에도 불구하고, Process B에서 수정된 데이터 값이 Process A에 반영되지 않아 수정된 데이터 값을 보면 count++연산이 한 번만 실행되어있다.
이런 문제를 해결하기 위해서, 어떤 process가 kernel mode에 있을 때는 time interrupt가 발생해도 이를 바로 처리하지 않고, process가 user mode로 전환된 이후에 time interrupt를 처리하도록 한다.
(3) Multiprocessor에서 shared memory 내의 kernl data
(1), (2)는 모두 CPU는 1개인 상황이기 때문에 CPU가 다른 작업으로 할당되는 것 (interrupt enable/disable)을 막으면 race condition을 해결할 수 있다. 하지만 (3)의 경우 CPU가 여러 개이기 때문에 CPU 할당을 막는 것만으로는 이를 해결할 수 없다.
해결 방법으로는 다음과 같이 두 가지 방법이 있다.
방법1) kernel에 lock 설정/해제
한 번에 하나의 CPU만 kernel에 들어갈 수 있게 하는 방법이다. 항상 하나의 CPU만 kernel을 사용할 수 있기 때문에 처리 속도가 떨어져 비효율적이다.
방법2) data에 lock 설정/해제
CPU에서 데이터를 가지고 갈 때 해당 데이터에 lock을 걸고, 연산 결과가 반영된 뒤에 lock을 해제하는 방법이다.
The Critical-Section Problem
n개의 프로세스가 공유 데이터를 동시에 사용하기 원하는 경우, 각 프로세스의 code segment에는 공유 데이터에 접근하는 코드(critical section)이 존재한다.
하나의 프로세스가 critical section에 있을 때, 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
Synchronization with Software: 프로그램적 해결법의 충족 조건
하나의 프로세스에서만 critical section을 실행하도록 하는 문제를 프로그램적으로 해결하기 위해서는 다음과 같은 조건을 충족해야한다.
(1) Mutual Exclusion (상호배제)
프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
(2) Progress (진행)
아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있ㅡ면 critical section에 들어가게 해주어야 한다.
(3) Bounded Waiting (유한 대기)
프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
이때 다음과 같은 가정이 있다.
- 모든 프로세스의 수행 속도는 0보다 크다
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
다음과 같은 알고리즘을 사용한다.
Algorithm 1
: Synchronization variable(turn)을 사용하여 critical section을 실행할 수 있는 process를 정한다.
이 방법은 Mutual Exclusion을 만족하지만 Progress를 만족하지 못한다.
반드시 다른 process가 실행되어야 차례가 돌아오기 때문에 각 process에서 critical section을 실행하는 빈도 수가 크게 차이나면 아무도 critical section에 없음에도 불구하고 변수가 바뀌지 않아서 critical section을 실행하지 못하는 상황이 발생할 수 있다.
Algorithm 2
: Synchronization variable(flag)을 사용하여 critical section을 실행할 수 있는 process를 정한다.
flag를 통해 현재 critical section을 실행하고 있는 process가 있는지 확인하고, 만약 없다면 flag를 True로 바꾸고 critical section를 실행한다. 실행 후에는 flag를 False로 바꾼다.
이 알고리즘에도 문제가 있다.
flag를 False로 바꾸는 행위는 critical section을 나올 때 하는데, flag를 True로 바꾸는 행위는 critical section을 들어가기 전에 하기 때문에 실제로 critical section을 실행하는 프로세스가 없음에도 불구하고 flag가 True여서 아무도 critical section을 실행하지 못하는 경우가 발생할 수 있다. 즉 Process 조건을 만족하지 못한다.
Algorithm 3: Peterson's Algorithm
: 앞선 알고리즘 1,2에서 사용한 변수 turn과 flag를 모두 사용한다.
다른 프로세스에 대해서 turn와 flag 조건이 모두 일치할 때만 while문을 실행하면서 기다린다.
두 조건 중 하나라도 일치하지 않을 때(turn이 다른 프로세스이지만 프로세스의 flag가 False, 즉 critical section을 실행하지 않아도 되는 경우이거나, turn이 다른 프로세스로 돌아가지 않았지만 flag가 True인 경우)에는 해당 프로세스의 critical section이 실행된다.
정리하자면, 두 개의 프로세스 모두 critical section을 실행해야 할 경우(flag=True)에는 turn 변수를 통해서 서로 번갈아가며 실행될 수 있도록 하고, 그 외의 경우에는 critical section을 실행하고 싶어하는 프로세스에서 먼저 실행하도록 하는 알고리즘이다.
하지만 이 알고리즘도 Busy Waiting(=spin lock)이라는 문제가 발생한다.
특정 조건을 만족하면 다른 프로세스의 turn와 flag값이 바뀔 때까지 CPU와 memory를 사용하면서 while문을 실행하며 기다리게 되기 때문에 비효율적이라는 문제점이 있다.
Synchronization with Hardware
Process Synchronization 문제를 프로그램적으로 해결하는 알고리즘을 살펴보면 생각보다 코드가 길다.
어떤 데이터에 대하여 read와 write를 동시에 할 수 없기 때문이다.
알고리즘을 보면 critical section의 실행 여부를 나타내는 변수에 대하여 write를 하고, 그 후에 데이터를 read하기 때문에 두 instruction 사이에 CPU를 빼앗길 수 있다.
알고리즘 2의 경우에도 flag를 True로 바꾸는 사이에 다른 프로세스의 flag도 True로 바뀌었기 때문에 Process를 만족하지 못했다. 이런 점을 고려하여 코드를 작성하다보니 길어지게 된다.
하지만 하드웨어적으로 test & modify를 atomic하게 (하나의 instruction처럼) 수행할 수 있도록 지원한다면 이 문제는 간단히 해결할 수 있다.
lock이 False이면 True로 바꾸면서 데이터를 읽어오고, flag이 True이면 True로 바꾸고 (사실상 그대로 유지) 이것이 False로 바뀔 때까지 while문을 실행하며 기다린다.
Semaphores
앞의 방식들을 추상화시킨다. 공유 자원을 획득하고 반납하는 것을 semaphores가 해준다.
Semaphore(s)는 정수 값을 가지는 변수이며 방법에 따라 다음과 같은 두 가지 종류로 나뉜다.
(1) counting semaphore
- 도메인이 0이상인 임의의 정수값
- 주로 resource counting에 사용한다 (busy waiting 방식)
(2) binary semaphore
- 0 또는 1 값만 가질 수 있다.
- 주로 mutual exclusion (lock/unlock)에 사용한다. (block & wakeup 방식)
또한 아래 두 가지 atomic 연산에 의해서만 접근 가능하다.
- P(S): 데이터 값을 획득하면서 데이터에 lock을 거는 과정이다. S값이 0이하면 while문을 돌면서 기다리고, 0보다 크면 S값에 -1을 하고 데이터를 가져온다.
- V(S): 데이터 사용 후 반납하면서 데이터에 걸린 lock을 푸는 과정이다. S값을 1 증가시키고 자원을 반납한다.
Q1. P,V 연산은 데이터 습득/반납과 동시에 lock/unlock을 실행하는 연산인가?
Q2. amotic한 연산이란 무엇을 의미하는가? 2가지 이상의 instruction을 동시에 실행한다는 의미인가?
busy waiting 방식
counting semaphore을 사용하기 때문에 semaphore가 0 이상의 임의의 정수값이다.
사용자가 코드를 작성하지 않고 Semaphore에서 제공하는 연산을 통해 간단하게 프로그램적으로 구현할 수 있다는 장점이 있다. 하지만 P 연산에서 S가 0이하일 때는 while문을 돌며 CPU 할당시간을 소모하는 busy waiting(=spin lock) 문제가 발생한다는 문제점이 있다. 이는 Block & Wakeup(=sleep lock) 방식의 구현을 통해 해결할 수 있다.
block & wakeup 방식
block과 wakeup을 다음과 같이 정의한다.
block: 커널은 block을 호출한 프로세스를 suspend 시키고, 이 프로세스의 PCB를 semaphore에 대한 waiting queue에 넣는다.
wakeup(P): block된 프로세스 P를 wakeup 시키고, 이 프로세스의 PCB를 ready queue에 넣는다.
비교
block & wakeup 방식도 프로세스의 상태를 ready/sleep 상태로 바꿔야하기 때문에 overhead가 든다. 일반적으로는 block & wakeup 방식이 더 좋지만, 굳이 critical section의 길이에 따라 어떤 방식을 사용하는 것이 더 효율적인지 비교해보면 다음과 같다.
block & wakeup overhead vs. critical section의 길이
- critical section의 길이가 매우 긴 경우: block & wakeup 방식이 적당하다.
- critical section의 길이가 매우 짧은 경우: block & wakeup overhead가 busy waiting overhead보다 더 커질 수 있다.
Semaphores에서 발생할 수 있는 문제
(1) Deadlock
둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
위의 그림을 보면 P0, P1 두 개의 프로세스가 있고, 자원 S, Q semaphores가 2개 존재하는 상황을 살펴보자. P0에서 semaphore S에 대한 연산이 모두 끝나지 않은 상태에서 P1로 CPU가 넘어가면 아직 P0가 S를 사용하고 있기 때문에 P1은 P(S)를 진행하지 못하게 된다. 그래서 P0가 언제 S를 반환하는지를 살펴보면, Q까지 획득한 뒤에 S와 Q를 반환한다. 하지만 Q는 P1이 S를 획득한 뒤에 반환되기 때문에 두 프로세스 모두 영원히 기다리기만 하게 된다.
이를 해결하기 위해서는 자원 획득 순서를 동일하게 하면 된다.
(2) Starvation
특정 프로세스들만 자원을 독점하고 있어 다른 프로세스는 자원을 얻지 못하고 무한히 기다리는 현상을 말한다.
Dining-Philosophers problem을 통해 deadlock과 starvation을 살펴볼 수 있다.
Classic Problems of Synchronization
1. Bounded-Buffer Problem
Producer-Consumer Problem이라고도 한다.
상황 정리:
Shared data
- buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치)
Synchronization variables
- mutual exclusion -> need binary semaphore (shared data의 mutual exclusion을 위하여)
- resource count -> need integer semaphore (남은 full/empty buffer의 수 표시)위의 그림이 예시인데 상황을 설명해보자면, 버퍼의 크기가 유한한 상황이고, 생산자 프로세스, 소비자 프로세스 이렇게 2가지 프로세스가 있다. 이때 생산자/소비자 프로세스 모두 여러 개가 존재한다.
생산자 프로세스는 데이터를 빈 buffer에 넣고, 소비자 프로세스는 채워져 있는 buffer에서 데이터를 꺼낸다.
buffer가 모든 프로세스가 접근할 수 있는 공유 buffer이기 때문에 여러 생산자/소비자 프로세스가 동시에 도착해서 작업을 하는 경우가 발생할 수 있다.
-> process synchronization 문제를 방지하기 위하여 생산자/소비자 프로세스 모두 작업을 하기 전에 buffer와 데이터에 lock을 걸고 작업이 끝나면 lock을 푸는 과정이 필요하다
또 버퍼가 유한하기 때문에 발생하는 문제도 있다. 버퍼가 다 찬 경우에는 생산자 프로세스는 실행될 수 없다. 반대로 버퍼가 다 비어있는 경우에는 소비자 프로세스가 실행되지 못한다.
-> 가용 자원의 개수를 세는 변수가 필요함.
Q. 카운터 변수가 있는데 왜 굳이 자원 개수를 세는 변수가 필요한지는 잘 모르겠음.
자원의 개수를 세고, 자원을 사용하기 전/후로 lock/unlock을 실행하는 용도로 semaphore가 필요하다.
semaphore를 사용한 수도코드는 다음과 같다.
2.Readers and Writers Problem
DB가 공유 데이터이고, read와 write 프로세스가 있다. read는 동시에 여러 read 프로세스가 실행되어도 되지만 write 프로세스는 한 번에 하나의 프로세스만 실행되어야 한다. read 프로세스가 실행되고 있을 때는 write 프로세스가 실행될 수 없다.
Shared data
- DB 자체
- readcount: 현재 DB에 접근 중인 reader의 수
Synchronization vairables
- mutex: 공유 변수 readcount에 접근하는 코드(critical section)의 mutual exclusion을 보장하기 위하여 사용하는 변수
- db: reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
위 코드대로라면, reader 프로세스가 1 이상인 상황이 계속 유지될 경우 writer 프로세스는 계속 기다리기만 해야 할 것이다. 때문에 starvation이 발생할 수 있다.
3. Dinning-Philosophers Problem
철학자가 하는 일은 생각하기와 밥 먹기. 이를 반복한다. 타이밍은 독립적.
배고파지면 왼쪽에 있는 젓가락을 가지고 밥을 먹는다. 이떄 젓가락은 철학자의 좌우에 각각 1개씩 있다.
젓가락이 공유 자원.
모든 철학자가 동시에 배고파져서 모두 왼쪽 젓가락을 든 경우, deadlock의 가능성이 있다.
해결 방안
- 밥먹을 때만 테이블에 앉을 수 있고, 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
- 비대칭: 짝수(홀수)철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다.
두 번째 해결방안에 대한 코드
Monitor
Semaphore의 단점
- 코딩하기 힘들다
- 정확성(correctness)의 입증이 어렵다
- 자발적 협력(voluntary cooperation)이 필요하다
- 한 번의 실수가 모든 시스템에 치명적인 영향을 미친다
monitor는 프로그래밍 언어 차원에서 semaphore의 문제점을 해결하기 위한 high-level synchronization construct라고 볼 수 있다.
monitor 내부에 공유 변수를 선언하고, 공유 변수에 접근하는 함수 및 초기화 함수도 내부에 정의한다.
semaphore는 process synchronization 문제를 방지하기 위해서 P연산을 통해 데이터에 lock을 거는 작업을 수동으로 해야했지만, monitor는 monitor 내에서 한 번에 하나의 프로세스만이 실행되기 때문에 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다. 즉, 따로 데이터에 lock을 거는 작업을 해줄 필요가 없다.
semaphore에서는 자원의 개수를 count하는 변수도 사용했는데 monitor도 비슷한 기능을 하는 condition variable가 있다.
특정 값을 가졌던 semaphore의 변수와 달리, condition variable은 특정 조건을 만족한 프로세스를 줄 세우는 queue의 역할을 한다. condition variable은 wait와 signal 연산을 통해서만 접근 가능하다.
conditon x, y;
x.wait();
# x.wait()을 invoke한 프로세스는
# 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend한다.
x.signal();
# x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다.
# suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.
semaphore 코드와 비교해보기
