Synchronization
여러 threads가 shared resource에 동시에 접근하면 incorrect result를 얻을 수 있다.(race condition)
이러한 문제를 미연에 방지하기 위한 방법을 synchronization이라고 한다.
Race condition
thread가 자원 공유를 할 때의 결과가 non-deterministic(non-reproducable)인 문제l
이 결과는 timing에 의존한다
- Multi-threading : CPU 스케줄러에 의해 'interleaved' 될 수 있다.
- Multi-processor : 다중처리기에서 실행 timing은 CPU가 얼마나 바쁜지에 따라 다르다.
하나의 명령코드는 여러개의 instruction으로 나누어질 수 있다.
하나의 operation이 공유자원에 atomic하게 접근한다는 것을 보장할 수 없기에 상호 배제시킬 필요가 있다.
Critical Section / Mutual Exclusion
critical section : 공유자원에 접근하는 코드
mutual exclusion : race condition을 막기 위해 공유자원에 대한 접근을 atomic하도록 제한한다. 즉 critical section에 한 개의 thread만 접근하도록 보장한다.
만약 모든 thread가 read기능만 수행한다면 race condition은 일어나지 않는다.
Thread synchronization이란
race condition을 회피하기 위해 critical section에 mutual exclusion을 제공하는 mechanism이다."
critical section problem은 다음의 세가지 조건을 만족해야 한다.
1. Mutual exclusion
- 프로세스 P가 critical section에서 실행되는 동안 다른 프로세스들은 그 critical section에 진입할 수 없다.
2. Progress
- critical section에서 실행되고 있는 프로세스가 없을 때, critical section에 진입하려는 프로세스가 있음에도 logic상 진입할 수 없는 상황이 있으면 안된다.
3. Bounded waiting
어떤 프로세스가 critical section에 진입해있을 때, 다른 프로세스들은 waiting상태이다. 이 때, 대기하는 프로세스가 많으면 우선순위가 낮은 프로세스는 무한정으로 대기해야한다. 이런 일이 발생하지 않도록 해야한다.
[Mutual exclusion 위반]
process A가 if조건문에 들어가자마자 Process B가 수행되는 일이 발생하면 상호 배제될 수 없다.
Software approach
[Progress 위반]
turn을 정해서 프로세스마다 상호 배제를 시켜주었다.
하지만 다른 프로세스에서 turn을 넘겨주지 않으면 critical section이 비어있어도 진입할 수 없다.
[Progress 위반]
Peterson's(해결)
사실 가장 간단한 방법은 interrupt를 disable해주는 방법이다.
하지만 interrupt disable하게 되면 context switch를 할 수 없기 때문에 자주 사용하지 않는다.
보통 단일 처리기 환경에서 사용하는 방식이다.
장점 : 간단함
단점 :
1) 시스템 자원 효율적으로 이용하지 못함
2) 보안상의 문제 유발 가능
3) 다중처리기 환경에서 사용될 수 없음(interrupt disable을 레지스터에 저장하기 때문에 처리기마다 처리해야한다.)
Hardware Support : Test-And-Set(TAS)
몇몇 시스템은 lock mechanism을 제공한다.
Test(load) 와 Set(store)을 atomic operation으로 만든다.
Test : 이전 lock 값을 체크한다.
Set : lock을 새로운 값으로 설정한다.
Hardware Support : Compare-And-Swap (CAS)
TAS와 굉장히 비슷하다.(3번라인만 없으면 동일)
TAS는 old 값이 0이든 1이든 new값으로 write하고 test하는데
CAS는 old 값이 0일때만 수행. 실질적인 update라고 할 수 있다.
=> 하드웨어의 지원을 받아 busy waiting기법으로 구현되었다 : spin lock
parbegin : n개의 프로세스(스레드)를 동시에 생성(실행).
critical section으로 가기 위해선 lock,unlock 해야하는데 하드웨어 지원을 받아 CAS기법으로!
이렇게 해결하는 방법을 -> "Spin Lock"
[Spin Lock]
1. mutual exclusion
-> 스핀락은 하나의 thread만 critical section에 들어갈 수 있기에 mutual exclusion 제공한다.
2. fairness
-> 스핀락은 starvation을 유발시킬 수 있다.
3. performance
-> single-processor : lock을 잡고있는 스레드를 제외한 다른 스레드는 CPU cycles 낭비할 수 있다.
-> multi-processor : 마찬가지로 performance 좋진 않으나 다른 프로세서들이 unlock을 해줄 수 있기 때문에 single 프로세서에 비해서는 괜찮은 성능이다.
Spin lock은 하드웨어 지원을 받아 상호배제를 실현할 수 있다.
하지만 starvation 발생할지도 모르고 busy waiting 기법으로 구현될 수 밖에 없기 때문에
single processor일 경우 CPU 낭비가 심하다.
Semaphore
동기화 기법으로, '상호배제'와 '다수의 프로세스가 특정한 조건에서 중단되고 재개하는 실행의 흐름을 제어할 수 있는 condition variable'문제를 해결한다.
세마포어는 두가지방식 모두 사용가능
일반화시킨 동기화 기법
세마포어 구성요소
세마포어 변수, operation(wait,signal)
최초에는 세마포어기법을 표현할 때 P,V로 설명했다.
P : wait(),상호배제 측면에서는 lock() -> try
V : signal(), 상호배제 측면에서는 unlock() -> increase
세마포어 변수는 integer변수이다.
초기 instance 값은 변할 수 있다.
wait,signal operation을 통해 변할 수 있는 상태값이다.
busy waiting기법은 CPU낭비가 심해서 sleep/awake로 구현한다. (물론 busy wait으로 구현될수도있긴함)
sleep/awake 로 구현되었다는 것은 queue를 가진다는 것을 의미한다.
Binary semaphore : 세마포어 변수가 0아니면 1이다. (0은 lock, 1은 unlock) -> 뮤텍스 lock이라고도 불림
이걸 확장해서 general한 버전으로 만든 것이
Counting semaphore or 범용 세마포어
critical section에 진입할 때 semWait()함수를 호출하고
critical section에서 빠져나갈 때 semSignal()함수 호출
<Binary semaphore 슈도코드>
struct binary_semaphore {
enum {zero, one} value; //binary 세마포어 변수는 0 or 1
queueType queue; //queue를 가지고 있다
};
//wait함수
void semWaitB(binary_semaphore s)
{
if (s.value == one) //value가 1이면 사용할 수 있음
s.value = zero; //zero로 바꾸고 나온다
else { //수행중에 또 다른 프로세스가 sem_wait호출하면 자러간다
/* place this process in s.queue */;
/* block this process */;
}
}
//signal함수
void semSignalB(semaphore s)
{
if (s.queue is empty()) //기다리고 있는 프로세스가 없다면
s.value = one;
else { //기다리고 있는 프로세스가 있다면
/* remove a process P from s.queue */;
/* place process P on ready list */;
}
}
<conting semaphore 슈도코드>
struct semaphore {
int count; //무한대로 설정 가능
queueType queue; //queue를 가지고 있다
};
//wait함수
void semWait(semaphore s)
{
s.count--;
//음수가 되면 대기해야하고 block상태로 바뀜
//count가 == -3이라면 3개의 프로세스가 대기하고 있다는 의미
if (s.count < 0)
/* place this process in s.queue */;
/* block this process */;
}
//signal함수
void semSignal(semaphore s)
{
s.count++;
//프로세스 하나를 깨워줌
//starvation을 줄이기 위해 FIFO로 깨우면 strong semaphore
//위를 고려하지 않으면(FIFO가 아닌 것으로 깨우면) 약성 semaphore
if (s.count <= 0)
/* remove a process P from s.queue */;
/* place process P on ready list */;
}
Spin Lock과의 차이점은 queueing을 이용하여 대기하는 프로세스들을 관리할 수 있다는 점!
counting semaphore을 lock이나 unlock으로 사용한다면
반드시 P가 호출된 뒤에 V가 호출된다는 것을 보장해야 한다.
결국 제대로 사용한다면 세마포어변수는 초기값을 넘어서지 않는다.
세마포어의 최종적 구현
세마포어 변수를 위한 상호배제 lock을 구현해야한다 -> 재귀적 구현 막기 위함
(a) spin lock은 세마포어 변수를 위한 lock
(b) interrupt disable/enable기법으로도 구현가능
Deadlock
세마포어를 잘못 사용하면 deadlock에 빠질 수 있다.
P0는 S먼저 wait하고 Q를 wait, P1은 Q를 먼저 wait하고 S를 wait
P0에서 S 잡고있는데 interleaving이 되면 P1은 Q잡고, S는 잡혀있어서 sleep상태가 되고 blocked queue에서 스케줄링되어 다시 P0로 가서 wait(Q)를 하려고 하니 Q도 잡혀있는 상태라 sleep에 빠진다.
이렇게 둘 이상의 프로세스가 분점한 상태에서 서로를 기다리고 있어 더 이상 진행할 수없는 상황을 Deadlock 이라고 한다.
자세한 내용은 뒤에서!
Locks in Linux
- futex
- futex_wait(address, expected)
- futex_wake(address) - Two-Phase locks
- locks에 대한 하이브리드 방식
- first phase : 먼저 spin lock으로 기다리다가
- second phase : 얻지 못하면 sleep lock으로 진행한다. - In Linux
- 어떻게 하면 효율적? 하이브리드한 방식을 사용하자.
- 즉 futex를 사용하여 spin lock과 sleep lock의 장점을 모두 이용하고자 한다.
Condition Variables
multi-threaded program에서 특정 조건에 의해 대기해야 하는 상황(ex. pthread_join)
위 코드는 while문을 돌면서 done == 1 될 때까지 기다려야하기에 busy waiting 할 수 있다.
이러한 문제를 해결하기 위해 condition variable을 사용한다.
실행 순서,흐름을 제어하는 기법
기존 상호배제와는 다른 분야
CV는 waiting queue를 가지고 있다.
두 개의 operation
- waiting on the condition : wait()
- signaling on the condition : signal()
<example>
<join() example>
main시작과 동시에 thread를 만들고 join을 통해 기다린다.
thread_join()을 살펴보자.
특정 조건을 표현하기 위해 변수가 필요하다. -> state variable
state variable은 다른 스레드에서 1로 바꿔주어야 하기에 공유자원일 수 밖에 없고 상호배제가 이루어져야한다.
그래서 condition variable은 항상 mutex로 둘러싸여있다.
condition variable이라는 공유자원을 사용하기 위해 lock을 잡고 들어갔는데 자러간다? 이건 반칙이지..
lock변수를 함께 가지고 자러간다.
그래서 내부적으로 lock을 해제시키고 자러간다. 누군가 깨워주면 다시 lock을 잡고 나온다.
<시나리오 1>
thread-1이 먼저 호출되었다고 가정하면..
동기화 잘 되었다!
<시나리오 2>
동기화 잘 되었다!
Broken Solution
1. looping code가 없을 시(상태변수가 없을 시)
thread-2에서 lock으로 잡고 signal을 보내는데 받는애가 없어서 끝나고 unlock!
그리고 thread-1에서 lock으로 잡고 기다리지만 signal은 이미 지나가버렸다.
계속 기다리고 main thread가 끝나지않는 상황이 발생할 수 있다.
문제발생!
2. lock이 없을 시
thread-1의 if문 다음에 인터럽트가 걸리면 thread-2에서 done을 1로바꾸고 signal보내지만 큐에 없어서 effect가 없다. 그리고 자러간다. 결국 이것도 문제 발생
생산자/소비자 문제(bounded buffer problem)
기본적으로 상호배제가 이루어져야 한다.
생산자코드는 Queue에 집어넣는 put하는 함수이고,
소비자코드는 Queue에서 빼는 get하는 함수이다.
buffer가 empty이면 consumer은 대기해야한다.
Tc1이 먼저 실행을 하다가 c3에서 카운트가 0이라서 자러간다.
다음에 Tp가 실행된다고 하면 p4에서 카운트를 증가시켜서 카운트가 1이된다.
그리고 sleep상태인 Tc1을 깨운다.(깨운다고 바로 수행되는건 아님)
그리고 계속 Tp가 실행되다가 max(count) 1에 걸려서 자러간다.
근데 갑자기 Tc2가 깨어나서 카운트를 가로챈다.
그래서 카운트가 0이되고 Tc2는 끝난다.
이제 그럼 Tc1이 일어낫는데 얘는 카운트가 아직도 1인줄알고 c4를 실행해서 카운트를 가져오려는데 카운트가 없네?
그럼 오류가 발생한다.
그런데 if문이 아니라 while문을 사용하면 한번 더 체킹하기 때문에 오류를 막을 수 있다.
그래서 rechecking코드가 필요하다!
여전히 문제가 있다.
producer와 consumer은 동일한 condition variable을 사용한다.
그렇기 때문에 잘못 깨우는 상황이 발생할 수 있다.
처음에 Tc1이 count가 0이라서 자러간다.
그다음에 Tc2가 수행되고 count 0이라서 자러간다.
그 다음에 Tp가 수행되고 count를 증가시키고 signal을 보내서 Tc1을 깨웠다.
그 다음에 Tc1은 signal을 보내서 Producer을 깨워야하는데 Tc2를 깨워버리게 된다.
Tc2가 일어나서 rechecking을 해보니 count가 여전히 0이어서 다시 잠들게 된다..
이렇게되면 모두 잠들게된다.
그렇기에 producer와consumer을 분리하는 다른 condition variable을 사용해야 한다.
producer : empty가 되기를 기다린다(wait), signal을 보내 fill을 한다.
consumer : fill이 되기를 기다린다.(wait), signal을 보내 empty를 만든다.
생산자와 소비자가 각각 다른 condition variable을 가져야 한다!
이번에는
생산자/소비자 관점에서 본 세마포어
초기값이 핵심이다.
상호배제시켜야 하기에 m의 초기값은 1이다.
fill은 consumer부터 시작하여 data를 기다리기에 초기값은 0이다.
empty는 producer부터 시작하여 빈 슬롯을 기다리기에 초기값은 N이다.
그런데 여기서 문제가 또................... 발생한다.... 제발 그만좀......
세마포어는 lock잡고 자러가면 안된다!
그래서 먼저 풀어주어야한다.
producer에서 sem_post(&m)과 sem_post(&fill)의 위치를 바꿔주고
consumer에서 sem_post(& empty)와 sem_post(&m)의 위치를 바꿔주어야한다.
이렇게!
100퍼센트 완성된 생산자/소비자 문제~~~
[세마포어로 생산자/소비자 문제 해결]
semWait(s),semSignal(s)는 상호배제, s의 초기값은 1
producer의 semWait(e)는 P(e), consumer의 semSignal(e)는 V(e)
producer의 semWait(n)는 V(n), consumer의 semSignal(n)는 P(n)
[buffer가 무한할 때의 세마포를 활용한 생산자/소비자 문제 해결]
buffer가 무한하기에 producer은 제약이 없다. 따라서 p(e)와 v(e)가 필요없다.
'Operating System' 카테고리의 다른 글
| Memory Management (0) | 2021.06.12 |
|---|---|
| Deadlock (0) | 2021.06.11 |
| Thread (0) | 2021.05.16 |
| Multiprocessor scheduling (0) | 2021.05.16 |
| Process Scheduling 2 (0) | 2021.05.10 |
