[OS] Process Synchronization

Process Synchronization (프로세스 동기화)

= Concurrency Control (병행 제어)

데이터의 접근

컴퓨터 시스템안에서 데이터가 접근되는 패턴 추상화

ㅡ> 데이터가 저장된 곳에서 data를 읽어와서 연산하고 다시 원래 위치에 저장

 

이 패턴때문에 process synchronization 문제가 발생한다.

데이터를 읽기만 하면 문제가 없지만, 데이터를 수정하고 다시 저장하기 때문에

누가 먼저 읽었냐에 따라 결과가 달라질 수 있다

Race Condition

왼쪽 오른쪽 박스가 data를 읽어가고

각자 연산결과를 저장하면

늦게 저장하는쪽의 결과만 저장된다.

 

■ Race Condition

ㅡ> 여러 주체가 하나의 자원에 동시에 접근하려고 함

ㅡ> ex) 멀티프로세서, 공유메모리, 시스템콜 등

OS에서 race condition은 언제 발생하는가?

1. Interrupt handler VS kernel

커널이 count 값을 증가시킬 때,

메모리에서 레지스터로 load하고 증가시키고 store을 한다.

근데 load상태에서 interrupt가 들어와서 handler가 count 값을 감소시키고 문맥이 돌아온다.

그러면 원래 문맥은, 예전 count값을 이미 load한 상태이기 때문에, 그 값을 수정하고 store한다.

ㅡ> 결국 인터럽트 결과는 반영이 안된다 (P)

 

(S) : 중요한 변수 처리중엔 인터럽트를 disable 시킴 ▶ 이 작업이 끝날 때까지는 인터럽트 처리 루틴으로 보내지 않음

단점 : 무작정 막으면  비효율적일 수 있음

2. preempt a process running in kernel?

프로세스 A에서 커널모드 작업중에 타임아웃으로

프로세스 B에게 CPU가 넘어가고 거기서도 커널모드 작업하고

다시 프로세스 A로 넘어가서 커널모드 작업을 완료함

그러면 프로세스A의 커널모드 작업만 저장됨

 

해결책 : 커널모드에서 수행 중일 때는 CPU를 뺏기지 않는다

(preempt = 선점)

단점 : 할당시간이 정확하게 지켜지지는 않게 됨

3. Multiprocessor

CPU가 데이터에 접근할 때 lock을 걸어서, 다른 CPU가 접근 못하게 함

 

방법1

ㅡ> 커널 전체에 lock을 걸어서 하나의 CPU만 커널에 접근 (비효율적)

방법2

ㅡ> 사용하는 data에만 lock을 검

정리

Race Condition 예시

The Critical-Section Problem

■ criticla section

ㅡ> 공유데이터에 접근하는 코드

 

하나의 프로세스가 criticla section에 있으면

다른 프로세스가 critical section에 들어가지 못하도록 해야된다

프로그램적 해결법

프로그램적 해결법의 충족 조건

Mutual Exclusion

ㅡ> 상호 배제

ㅡ> 하나가 들어가있으면 다른건 못들어감

 

Progress

ㅡ> 진행

ㅡ> 아무도 안들어가있으면 들어가게 해줌

 

Bounded Waiting

ㅡ> 유한 대기

ㅡ> 너무 오래 기다리는 starvation 현상 방지

ㅡ> ex) 3개의 프로세스가 있을 때 2개의 프로세스만 번갈아 들어가는 상황 방

Initial Attempt to Solve problem

critical section ㅡ> 공유데이터 접근하는 부분

remainder section ㅡ> 접근 x 

exit section ㅡ> critical section에 들어가기 전에 lock을걸고, 끝난 후에 lock을 푸는 부분

 

 

이제부터 lock을 걸고 푸는 알고리즘을 살펴보자

알고리즘1

 

■ 프로세스가 2개가 있다고 가정 (P0, P1)

 

■  위는 P0을 위한 코드이다.

P1을 위한 코드는 위에서 숫자만 바꾸면 된다

 

■  turn이 어떤 숫자의 프로세스 턴인지를 알려준다.

 

■ 자기turn이 아닌 동안에 계속 저 while문이 무한하게 돌아간다

그리고 자기 turn이 됏을 때, while문을 빠져나가 critical section에 진입한다.

critical section에서 빠져나오면 turn을 바꿔준다.

 

■ 단점

상호배제는 만족하나, progress는 만족하지 않는다.

(아무도 critical section에 없어도, 진입하지 못하는 문제)

반드시 교대로 들어가게 설계가 되어있어서, 상대가 들어갔다 나와야 turn이 돌아온다.

그런데 상대가 critical section을 사용하지 않는 경우, 나에게 turn이 돌아오지 않는다.

알고리즘2

■ 프로세스마다 각각 flag를 가지고 있다.

flag는 critical section을 사용하겠다는 의중이다.

 

■ 먼저, 내가 사용하겠다는 깃발을 든 뒤,

상대가 깃발을 들고있나 체크한다. (들고있으면 무한루프로 대기)

상대가 깃발을 내렸으면 그때 critical section에 진입한다.

 

■ 단점

내가 깃발을 들 때, 상대에게 CPU가 넘어갔을 때

상대도 깃발을 들고 진입 못하는 교착상태가 발생한다

알고리즘3 (피터슨 알고리즘)

flag와 turn을 둘 다 사용한다.

 

상대가 깃발도 들고, 실제 상대의 turn일 때는 기다린다.

둘 중 하나라도 만족하지 않으면 내가 critical section으로 진입한다.

 

장점

ㅡ> mutual exclusion, progress, bounded waiting을 모두 만족한다.

 

단점

ㅡ> busy waiting (= spin lock)

ㅡ> lock을 걸어둔 동안, 다른 프로세스가 while문을 돈다(spin). 즉, CPU낭비

하드웨어적 해결법

critical section문제는

들어갈 때 lock걸고 나올때 unlock하는 간단한 문제인데

코드가 복잡해지는 이유는, 고급언어의 문장 하나가 여러개의 instruction으로 구성되어 있기 때문이다.

intruction이 여러개다 보니, 읽고 쓰는 중간에 CPU를 빼앗길 수 있고, 그런경우 생기는 문제를 방지하려다보니 코드가 복잡해진다.

 

읽고 쓰는게 하나의 instruction으로 처리가 되면, ciritcal section 문제는 쉽게 해결이 된다.

하드웨어적으로 test_and_set이라는 instruction이 그런 역할을 한다.

읽고 쓰는 중간에 CPU를 뺏겨서 문제가 되는건데, 읽고 쓰는 것을 한번에 처리하는 instruction이 제공돼서 문제가 해결되는 것이다.

Test_and_set(a)

ㅡ> 변수 a의 값을 읽는 동시에, 값을 True로 교체한다.

 

while문 안에서, 잠금이 false면 critical section에 진입하는 동시에 true로 바꿔서 잠궈버린다

Semaphores

Semaphores

ㅡ> 추상 자료형 (구현은 숨기고, 기능과 동작만 설명)

ㅡ> 공유자원을 획득하고 반납하는 기능

ㅡ> Semaphore S라고 선언하면, S에는 integer 값이 들어갈 수 있음 ▶변수값이 공유자원의 수

ㅡ> P연산 : 획득

ㅡ> V연산 : 반납

ㅡ> P연산과 V연산은 atomic하게 수행 (동기화 문제x)

ㅡ> 여기서도 busy-waiting문제는 발생 ▶ 자원이 없을때 P연산은 while문만 돌다가 끝남

 

예를들어, 자원이 5개 있으면

자원을 획득할때 P연산을 해서 자원이 4개가 된다.

V로 반납하면 다시 5개가 된다.

Critical Section of n Processes

세마포어로 critical section 문제를 해결

ㅡ> 진입할때 P연산 나올때 V연산

[busy-wait의 대안] Block & Wakeup Implementation

공유자원이 없을 때

spin-lock을 시키는게 아니라

sleep-lock을 시켜서 CPU낭비를 멈춘다.

 

공유자원이 없으면 프로세스를 block시켜서 세마포어 큐에 넣는다.

 

P연산

ㅡ> 공유자원이 없는경우 변수값을 음수로 만들면서 block 상태로 들어간다.

 

V연산

ㅡ> 반납했는데 변수값이 음수면, block상태인 프로세스가 있다는 뜻이므로, wakeup 해준다.

 

 

정의는 저렇게 길게 되어있지만

실제로는 atomic하게 실행되어야 한다 (커널에서 특별관리)

busy-wait VS block/wakeup

일반적으로 block/wakeup이 더 효율적

 

하지만, Block/Wakeup에도 오버헤드가 있기 때문에

Critical Section의 길이가 매우 짧은 경우, Busy-wait 방식이 나을 수도 있다.

Two Types of Semaphores

세마포어 변수값이 0 or 1인 경우

ㅡ> Binary 세마포어

ㅡ> Mutex의 역할 (상호 배제)

 

변수값이 0이상의 정수값

ㅡ> Counting 세마포어

Deadlock and Semaphores

세마포어는 주의사항이 있다

 

S하고 Q를 둘 다 획득해야 일을 할 수 있는 상황을 가정해보자

ㅡ> 예시) 하드디스크 A에서 B로 복사하는 상황. A와 B 둘다 필요함

 

P0하고 P1이 위와같은 상황이고,

S와 Q는 각각 1개씩 있다고 해보자

그럼 P0이 S를 가지고, P1이 Q를 가지면 서로를 영원히 기다린다

ㅡ> Deadlock 

 

 

(S) 순서를 정함

ㅡ> S를 얻은뒤에 Q를 얻어야 된다고 순서를 정해놓는다

ㅡ> 그럼 P0이 S를 가지고 있으니 P1은 Q를 얻지 않는다.

동기화의 고전적 문제

Bounded-Buffer Problem (생산자-소비자 문제)

 

■ Bounded Buffer

ㅡ> 버퍼의 크기가 유한하다

 

■ 공유데이터

ㅡ> Buffer

ㅡ> 빈/꽉찬 Buffer의 위치 포인터 등

 

■ 동기화 변수

ㅡ> Binary Semaphore : 공유데이터의 상호배제를 위함

ㅡ> Counting Semaphore : full/empty Buffer의 갯수를 표시하기 위함

 

■ 생산자, 소비자

ㅡ> 생산자는 버퍼를 채우고, 소비자는 버퍼를 비운다

 

ex) 영상 처리 시스템

생산자 : 카메라는 영상을 프레임 단위로 생성(생산)하여 공유 버퍼에 저장
소비자 : 저장된 프레임을 꺼내 화면에 표시하거나 분석

 

 

■ 동기화

ㅡ> Producer가 data를 집어넣을 때, lock을 건채로 집어넣고 lock을 푼다

ㅡ> Consumer가 data를 꺼낼 때, lock을 걸고 꺼낸뒤 lock을 푼다

 

■ Buffer가 유한해서 생기는 문제

ㅡ> Buffer가 꽉차면 Producer가 일을 못하고 기다려야 한다

ㅡ> Consumer가 data를 꺼내가서 빈 Buffer가 생길 때까지 기다린다

ㅡ> 반대로 텅 비었을 땐, Consumer가 기다려야 한다

수도코드

<변수>

full, empty ▶ 빈/꽉찬 버퍼 갯수 알려줌

mutex  ▶ lock/unlock 기능

 

<연산>

ㅡ> P(세마포어): 세마포어 값을 감소시킵니다. ▶ 값이 0보다 크면 감소하고, 그렇지 않으면 대기합니다.

ㅡ> V(세마포어): 세마포어 값을 증가시킵니다. ▶ 대기 중인 프로세스가 있으면 이를 깨웁니다.

 

 

현재 코드는 전체 버퍼를 잠그는 방식으로, 구현이 간단하고 데이터 무결성을 보장하지만 동시성(Concurrency)을 희생합니다.
슬롯 단위 잠금을 사용하면 더 높은 동시성을 달성할 수 있지만, 구현의 복잡도가 증가합니다.
구현 복잡성과 성능 요구사항에 따라 적합한 방식을 선택하면 됩니다.

Readers and Writers Problem

주로 DB에서 발생하는 문제를 다룬다

 

■  2종류 프로세스

ㅡ> Reader : 읽는 프로세스

ㅡ> Writer : 쓰는 프로세스

 

■  공유데이터

ㅡ> DB

ㅡ> readcount 

 

■  문제

ㅡ> Writer는 lock을 걸어야 하지만, Read는 여럿이 동시에 해도 된다

ㅡ> Read가 도착하면 읽게 해주고, Writer가 도착하면 lock을 걸어야 한다

수도코드

 

Writer

ㅡ> 변수db를 통해 쓰는작업에 lock을 건다.

 

Reader

ㅡ> 최초의 Reader(readcount ==1)만 db에 lock을 건다 

ㅡ> readcount도 공유자원이기 때문에, mutex로 다른 Reader가 들어오지 못하게 lock을 걸고 작업한다

 

Starvation

ㅡ> Reader가 계속 DB에 접근하면 Writer는 기아가 된다

ㅡ> Reader가 읽는동안 늦게온 Reader가 합류하고.. 더 늦게온 Reader가 또 합류하고.. 

Dining-Philosophers Problem

 

철학자

ㅡ> 생각 or 식사 

 

식사

ㅡ> 왼쪽과 오른쪽의 젓가락을 둘 다 집어야된다.

ㅡ> 젓가락은 공유자원 ▶ 한쪽이라도 못집으면 식사x

문제점

■ 1. Deadlock (교착 상태)

ㅡ> 모두가 동시에 왼쪽의 젓가락을 들어버리면 모두가 굶는다

 

■ 2. Starvation

철수의 왼쪽 사람이 젓가락을 내려놓을때까지 기다린다

철수의 왼쪽 사람이 내려놓으니 철수의 오른쪽사람이 젓가락을 집어버려서 굶는다

Deadlock 해결책

3가지 방법

(1) 4명의 철학자만 테이블에 앉게 하기

(2) 젓가락 2개를 모두 집을 수 있을 때만 젓가락을 집게 하기

(3) 짝수 철학자는 왼쪽 젓가락부터, 홀수 철학자는 오른쪽 젓가락부터 집도록 하기

 

(2)번 방법↓

 

젓가락을 모두 잡을 수 있을 때만 집는 코드

But, 위에서 배운 세마포어랑 구조가 좀 다름

ㅡ> 보통 세마포어는 공유자원의 숫자를 양수로 초기화하고, 사용권한을 얻었을 때 P연산을 함

ㅡ> 근데 여기서는 self를 0으로 초기화하고, test를 만족해야 self에 V연산을 해줘서 P연산을 가능케 함

ㅡ> 모니터 코드를 세마포어로 변환한 것이라 그럼

 

test()

ㅡ> 젓가락을 집을 수 있는지 확인

ㅡ> 조건을 만족하면 self값을 1 올림

 

pickup()

ㅡ> test()를 통과했으면, self의 값이 양수여서 P연산으로 젓가락 얻음

ㅡ> 통과못했으면 self의 값이 0이어서, P연산을 하지 못하고 대기상태가 됨

 

putdown()

ㅡ> 좌우의 철학자에 대한 test()를 해줌

ㅡ> 그러면 대기상태였던 좌우의 철학자가 젓가락을 얻게 됨

Monitor

코드가 복잡해지면서

코딩 실수를 해버리면

나중에 버그를 잡기가 어렵다 (발견이 어렵다)

 

그래서 대안으로 Monitor라는 동기화 방법도 있다

모니터

ㅡ> 커널이 아닌, PL(프로그래밍언어) 수준에서 해결 

ㅡ> 즉, high-level synchroniztion construct

모니터안에다가 공유데이터와, 그것에 접근하는 프로시저를 구현해놓고

프로시저를 통해서만 공유데이터에 접근할 수 있게 만든

 

하나의 프로세스만 모니터에 접근하고, 나머지는 queue에 대기하는 구조

ㅡ> 개발자가 직접 Lock을 걸 필요가 없어짐

ㅡ> 그림에선 조건 대기열이 모니터 안에 있지만, 실제로는 모니터 밖에서 기다린다고 생각하면 된다

 

 

■  Condition variable

ㅡ> 공유자원이 있으면 접근하게 해주고, 없으면 대기하게 하기 위한 변수

ㅡ> x라는 자원이 없으면 x.wait()을 통해 조건 대기열에서 기다리게 된다

ㅡ> x.signal()이 실행되면 대기열에 있는 것을 깨운다

Bounded Buffer Problem

Dining Philosophers problem

pickup()

ㅡ> test를 돌려서 조건이 만족하면 eating상태가 됨

ㅡ> 조건을 불만족해서 eating이 아니라면 wait상태로 들어감

 

test()

ㅡ> 조건을 만족하면 eating상태로

ㅡ> wait상태에서 test를 돌렸을 수도 있으니 스스로에게 signal 보냄

 

pudown()

ㅡ> thinking상태로 들어가면서, 양옆의 철학자들이 wait상태일 수도 있으니 test를 대신 돌려줌

세마포어 vs 모니터

■ 세마포어

ㅡ> 개발자가 직접 자원 관리와 상호 배제를 코딩 (low-level)

ㅡ> P(), V()같은 저수준 연산으로 컨트롤

■  모니터

ㅡ> 이미 구현된 상호 배제와 조건 동기화 메커니즘을 사용 (high level)

ㅡ> wait()와 signal() 같은 고수준 함수만 사용

 

■ 

모니터로 구현하면

개발자가 직접 lock을 걸 필요가 없다

(모니터 내부에 구현되어 있음)

■ 

세마포어는 자유도가 높아서 유연하지만

코드가 복잡해서 실수하면 데드락이나 경쟁 상태가 발생하고

버그를 잡기도 어렵다