동기화
동기화 필요성
•
Shared Data: 두 개 이상의 프로세스 혹은 스레드가 동작하는 상황에서 shared data를 접근하는 경우 프로세스, 스레드 간 동기화가 필요하다.
프로세스 동기화 방법
•
IPC (Interprocess Communication): 공유 메모리를 사용하는 방법과 메시지 큐를 사용하는 방법이 있다. 메시지 큐는 커널이 관리하며, 한 프로세스가 메시지 큐에 send하면 커널이 다른 프로세스에 시그널을 보내서 데이터를 receive한다. Shared memory를 사용하는 경우 커널이 관리해주지 않으며, 개발자들이 규칙을 지켜서 shared memory를 사용해야 한다. 동기화 문제는 shared memory를 사용하는 경우에 발생한다.
동기화 문제 발생 예제
•
ATM: 두 명이 동시에 ATM기에서 돈을 인출한다. 잔액 정보(balance)는 shared resource가 되고 이 리소스에 두 명이 동시에 접근한다. 한쪽의 트랜잭션이 먼저 일어났는데, put_balance를 통해 서버 데이터베이스를 갱신하기 전에 context switching이 일어난다. 나중에 트랜잭션이 일어난 프로세스는 갱신되지 않은 balance를 가지고 작업을 수행한 후 balance 값을 저장하고, 다시 context switching이 일어나 첫 번째 트랜잭션의 결과가 저장된다. 결국 두 번 인출이 일어났으나 첫 번째 트랜잭션에서 수행한 값으로 덮어씌워진다.
•
Bounded Buffer: 원형 큐가 존재하고 Producer는 계속해서 큐에 데이터를 넣고 Consumer는 큐에서 데이터를 빼내는 작업을 한다. Producer는 count가 N(버퍼의 최대 크기)이면 busy waiting하고, Consumer는 count가 0이면 busy waiting한다. count는 shared data가 된다. count++나 count-- 어셈블리 코드는 3개의 과정으로 이루어지는데, count에 변경된 값을 저장하기 전에 context switching이 일어난다면 변경되기 이전의 값을 가져가서 수행하게 되고, ATM 예시와 동일하게 의도와 다른 결과가 나올 수 있다.
동기화 툴
동기화 툴의 정의
•
CPU 하나에서 돌아가면서 수행되는 프로세스/스레드는 concurrent하다고 한다. Concurrent한 프로세스/스레드들이 별다른 장치 없이 shared resource에 접근하는 상황을 race condition이라고 한다. Race condition일 때는 결과가 non-deterministic하다. 이러한 문제를 synchronization problem, critical section problem이라고 부른다. 동기화 문제 발생 가능한 코드 구간을 critical section이라고 한다. Critical section을 보호하면 동기화 문제를 해결할 수 있고, 동기화 문제를 해결하는 방법을 동기화 툴이라고 한다.
동기화 툴의 조건
•
Mutual Exclusion: 상호 배제. 문제가 발생할 수 있는 critical section에 진입하려는 경우 한 번에 한 개의 프로세스/스레드만 크리티컬 섹션을 수행해야 한다.
•
Progress: 크리티컬 섹션에 진입 가능한 상황이면 기다리지 않고 바로 진입한다. 기다리는 것이 오버헤드를 발생시킬 수 있다.
•
Bounded Waiting: 다른 프로세스/스레드가 shared data를 쓰고 있어서 기다릴 때 무한정 기다리는 것이 아니라 언젠가 공유 자원에 접근할 수 있는 기회가 와야 한다. Starvation이 발생하면 안 된다.
Lock
•
정의: 크리티컬 섹션 진입하기 직전 lock을 걸어서 다른 프로세스가 접근할 수 없도록 하고 작업이 끝나면 unlock해서 다른 프로세스/스레드가 접근할 수 있도록 한다. 아무도 사용하고 있지 않은 경우 lock을 걸고 진입할 수 있으며, 누군가 lock을 걸고 있는 상태라면 기다리다가 unlock되는 순간 lock을 걸고 진입한다. 한번에 하나만 실행 가능하고, 비어 있을 때 즉시 접근하고 무한정 기다리지 않으므로 3가지 동기화 툴의 조건을 만족한다. Lock은 low-level mechanism으로 다른 동기화 툴을 구현할 때 사용된다.
Lock이 구현된 방식은 struct lock에 int형 변수 held가 존재하는 형태이다. held 값이 0이면 unlock 상태이고 1이면 lock 상태이다. lock 함수는 held가 0이면 루프를 돌지 않고 held 값을 1로 바꿔준다. held가 1인 경우 아무것도 하지 않는 while문을 무한 반복하며 busy waiting하는데, 이것을 spinlock이라고 한다. Spinlock의 문제점은 CPU 자원의 낭비가 심하다는 것이다. 따라서 유저 프로세스가 spinlock을 사용할 수는 없고 운영체제는 lock을 활용한 동기화 툴을 제공한다. unlock 함수를 수행하면 held를 0으로 초기화해준다.
하지만 held 또한 shared resource인데 보호되어 있지 않아서 lock 자체도 critical section이 되기 때문에 mutual exclusion이 안된다는 문제가 있다.
•
Lock의 Mutual Exclusion 문제 해결 방법:
◦
Software Only Algorithm: 1, 2, 3 알고리즘과 bakery 알고리즘이 존재하는데, 소프트웨어로 구현하면 오버헤드가 커져 성능이 좋지 않아서 실제로 사용하지 않는다.
◦
Hardware Atomic Instructions: CPU instruction 하나는 수행하는 중에 인터럽트가 걸리지 않는다. Lock을 풀고 거는 작업을 하나의 instruction으로 구성하면 중간에 context switching이 되는 일이 없다. 하드웨어 dependency가 높아서 CPU 제조 단계에서 지원되어야 한다. 하드웨어적으로 구현된 이 하나의 명령어를 Test-and-Set이라고 한다.
held가 0인 경우는 false를 반환하므로 critical section에 진입하고 held 값은 1로 바뀌어 있다. held가 1인 경우는 true를 반환하므로 critical section에 진입하지 않고 busy waiting하며 Test-and-Set을 수행한다. 멀티프로세서 환경에서도 잘 동작한다.
◦
Compare-and-Swap: x86 아키텍처에서 사용되며 특정 메모리 위치의 값이 주어진 값과 동일하다면 해당 메모리 주소를 새로운 값으로 대체하는 instruction이다.
◦
Disable Interrupt: 인터럽트가 걸려서 context switching이 일어나는 것이니 lock을 수행하기 전 인터럽트를 끄면 더 이상 critical section 문제가 발생하지 않는다. Lock을 걸 때 cli (clear interrupt) 시스템 콜을 호출하고 unlock할 때는 sti (set interrupt) 시스템 콜을 호출한다. 크리티컬 섹션이 길 경우 너무 오래 CPU를 점유할 가능성이 있고, 인터럽트를 끄는 기능을 유저 프로세스가 사용할 수 있다면 fairness를 보장할 수 없기 때문에 spinlock과 동일하게 커널에서만 사용하고 유저 프로세스에는 이를 활용한 higher level 동기화 툴을 제공한다. 코어가 하나인 시스템에서 많이 사용되던 형태로 멀티프로세서에서는 잘 동작하지 않을 수 있다.
세마포어
•
정의: 내부적으로 lock을 사용해 구현된 higher level synchronization tool이다. 기차의 선로가 하나로 합쳐질 때 사고를 방지하기 위해 신호를 주는 장치에서 따온 이름이다. 세마포어는 정수형 변수 형태로, shared resource를 사용할 수 있는 티켓의 개수라고 생각할 수 있다.
wait을 통해서 세마포어의 값을 1 감소시키고 shared resource에 접근할 수 있으며, 접근이 끝나면 signal을 통해 세마포어의 값을 1 증가시킨다. 세마포어가 1 이상이면 리소스를 사용할 수 있고 0일 때는 프로세스 값이 1 이상이 될 때까지 기다린다.
Critical section에 진입하기 전에 wait을 걸고 나올 때 signal로 티켓을 반환하면서 크리티컬 섹션을 보호하는 데 사용할 수 있다. 세마포어는 프로세스의 선후 관계가 존재할 때 동기화를 맞추기 위해서도 사용한다. A 프로세스에서 먼저 수행되어야 B 프로세스가 수행될 수 있다면 B 프로세스는 wait으로 기다리고 컨텍스트 스위칭되어 A 프로세스가 signal로 티켓을 반환하면 수행될 수 있게 구현된다.
세마포어는 busy waiting이 없다는 장점이 있지만 잘못 사용하면 deadlock과 starvation이 발생할 수 있다. 세마포어는 티켓의 개수를 정수값으로 가지고 있으며, shared data에 접근하기 위해 티켓을 가져가기를 원하는 프로세스들을 linked list 형태로 구현해서 관리한다.
•
종류: 세마포어 값이 1인 것을 바이너리 세마포어라고 하며, 1보다 큰 값을 가지는 것을 카운팅 세마포어라고 한다.
•
카운팅 세마포어 사용 예시: 원격 서버가 구축되어 있고 5개의 프린터가 연결되어 최대 5개의 프린터만 동시에 사용할 수 있다. 서버에서 세마포어를 5로 설정하고 클라이언트의 요청이 들어왔을 때 wait을 통해 5개가 다 사용 중인 상황이면 기다리도록 한다.
Mutex Lock
•
정의: Mutual Exclusion의 약자이다. 바이너리 세마포어와 동일하다. 바이너리 세마포어를 사용하는 경우가 굉장히 많기 때문에 세마포어와 따로 분리해서 구현해둔 것이다.
Monitor
•
정의: 세마포어는 사용법이 어려워서 유저가 deadlock을 만드는 등의 실수를 할 수 있기 때문에 프로그래밍 언어 레벨에서 라이브러리로 동기화 툴을 제공하고 컴파일하면 자동으로 보호되도록 하는 접근에서 나왔다. Java가 모니터를 지원하는 예시이다. C/C++을 사용하는 경우는 세마포어를 사용해야 한다. 코드에서 모니터를 선언해서 shared로 쓸 수 있는 리소스와 리소스를 사용하는 코드를 묶어놓는다. 한 함수가 수행되고 있으면 다른 함수를 수행하지 못하도록 모니터가 차단한다.
•
Conditional Variable: Monitor에서는 함수를 계속 수행하는 게 아니라 I/O 이벤트 등을 기다리는 상황에도 다른 함수들을 수행할 수 없는 문제가 발생한다. 이를 해결하기 위해 conditional variable을 사용해서 특정 상황에 대해 예외적으로 lock을 풀어준다. Conditional Variable은 세마포어와 비슷하게 wait과 signal로 구현되어 있는데, 차이점은 세마포어는 히스토리가 존재하고 모니터에는 존재하지 않는다는 점이다. 세마포어는 0, 1, 2와 같이 정수 값을 가지지만 conditional variable에는 true/false만 존재한다.
