[Chapter 6]
I. 동기화
A. 동기화 필요성
1. shared data: 두개이상의 프로세스 혹은 스레드가 동작하는 상황에서 shared data를 접근하 는 경우 프로세스, 스레드 간 동기화가 필요하다.
B. 프로세스 동기화 방법
1. IPC: Interprocess Communication. shared memory를 사용하는 방법과 메세지 큐를 사용하 는 방법이 있다. 메세지 큐는 커널이 관리하며 한 프로세스가 메세지 큐에 send하면 커널 이 다른 프로세스에 시그널을 보내서 데이터를 receive한다. shared memory를 쓰는 경우 커널이 관리해주지 않는다. 개발자들이 룰을 지켜서 shared memory를 사용해야한다. 동 기화 문제는 shared memory를 사용하는 경우 발생한다.
C. 동기화 문제 발생 예제
1. ATM: 두명이 동시에 ATM기에서 돈을 인출한다. ATM기와 서버간 트랜잭션이 발생한다. 잔액 정보(balance)는 shared resource가 되고 이 리소스에 두 명이 동시에 접근한다. 한 쪽의 트랜잭션이 먼저 일어났는데 put_balance를 통해서 서버 데이터베이스를 갱신하기 전에 context switching이 일어났다. 그렇게 되면 나중에 트랜잭션이 일어난 프로세스는 갱 신되지 않은 balance를 가지고 작업을 수행한 후 balance값을 저장하고, 다시 context switching이 일어나 첫번째 트랜잭션의 결과가 저장된다. 결국 두번 인출이 일어났으나 첫 번째 트랜잭션에서 수행한 값으로 덮어씌워진다.
2. Bounded buffer: 원형 큐가 존재하고 Producer는 계속해서 큐에 데이터를 넣고 Consumer는 큐에서 데이터를 빼내는 작업을 한다. Producer는 count가 N(버퍼의 최대크 기)이면 busy waiting하고 Consumer는 count가 0이면 busy waiting한다. count는 shared data가 된다. count++나 count– 어셈블리 코드는 3개의 과정으로 이루어지는데 count에 변경된 값을 저장하기 전에 context switching이 일어난다면 변경되기 이전의 값을 가져가 서 수행하게 되고, ATM예시와 동일하게 의도와 다른 결과가 나올 수 있다.
II. 동기화 툴
A. 동기화 툴의 정의
1. 이렇게 cpu하나에서 돌아가면서 수행되는 프로세스/스레드는 concurrent하다고 한다. concurrent한 프로세스/스레드들이 별다른 장치없이 shared resource에 접근하는 상황을 race condition이라고 한다. race condition일때는 결과가 non-deterministic하다. context switching의 타이밍에 따라서 실행시마다 결과가 다르게 나올 수 있다. 이러한 문 제를 synchronization problem, critical section problem이라고 부른다. 동기화문제 발생 가 능한 코드 구간을 critical section이라고 한다. critical section을 보호하면 동기화 문제를 해결할 수 있고, 동기화 문제를 해결하는 방법을 동기화 툴이라고 부른다.
B. 동기화 툴의 조건
1. Mutual exclusion: 상호배제. 문제가 발생할 수 있는 critical section에 진입하려는 경우 한 번에 한개의 프로세스/스레드만 크리티컬 섹션을 수행해야 한다.
Progress: 크리티컬 섹션에 진입 가능한 상황이면 기다리지 않고 바로 진입한다. 기다리 는 것이 오버헤드를 발생시킬 수 있다.
Bounded waiting: 다른 프로세스/스레드가 shared data를 쓰고 있어서 기다릴 때 무한정 기다리는것이 아니라 언젠가 공유자원에 접근할 수 있는 기회가 와야한다. Starvation이 발생하면 안된다.
C. Lock
1. 정의: 크리티컬 섹션 진입하기 직전 락을 걸어서 다른 프로세스가 접근할수 없도록 하고 작업이 끝나면 unlock해서 다른 프로세스/스레드가 접근할 수 있도록 한다. 아무도 사용하 고 있지 않은 경우 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이 안된다는 문제가 있다.
2. lock의 mutual exclusion 문제 해결방법
software only algorithm: 1,2,3알고리즘과 bakery 알고리즘이 존재하는데 소프트웨어로 구 현하면 오버헤드가 커져 성능이 좋지 않아서 실제로 사용하지 않는다. hardware atomic instructions: cpu instruction하나는 수행하는 중에 인터럽트가 걸리지 않는 다. 락을 풀고 거는 작업을 하나의 instruction으로 구성하면 중간에 context switching이 되는 일이 없다. 하드웨어 dependency가 높아서 cpu제조단계에서 지원되어야 한다. 하드 웨어적으로 구현된 이 하나의 명령어를 Test-and-Set이라고한다.
held가 0인 경우는 false를 반환하므로 critical section을 진입하고 held값은 1로 바뀌어 있 다. held가 1인 경우는 true를 반환하므로 critical section을 진입하지 않고 busy waiting하 며 TestAndSet을 수행한다. 멀티프로세서 환경에서도 잘 동작한다.
TestAndSet이외에 CompareAndSwap 이라는 Instruction도 존재하는데, x86 아키텍쳐에서 사용되며 특정 메모리위치의 값이 주어진 값과 동일하다면 해당 메모 리 주소를 새로운 값으로 대체하는 instruction이다.
disable interrupt: 인터럽트가 걸려서 context switching이 일어나는 것이니 lock을 수행하기 전 인터럽트를 끄면 더 이상 critical section문제가 발생하지 않는다. lock을 걸때 cli (clear interrupt)시스템 콜을 호출하고 unlock 할때는 sti (set interrupt) 시스템 콜을 호출한
다. 크리티컬 섹션이 길 경우 너무 오래 cpu를 점유할 가능성이 있고, 인터럽트를 끄는 기능을 유저 프로세스가 사용할 수 있다면 fairness를 보장할 수 없기 때 문에 spinlock과 동일하게 커널에서만 사용하고 유저 프로세스에는 이를 활용한 higher level 동기화 툴을 제공한다.
코어가 하나인 시스템에서 많이 사용되던 형태로 multiprocessor에서는 잘 동작하지 않을 수 있다.
D. 세마포어
1. 정의: 내부적으로 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형태로 구현해서 관리한다.
2. 종류: 세마포어 값이 1인 것을 바이너리 세마포어라고 하며, 1보다 큰 값을 가지는 것을 카운팅 세마포어라고 한다.
3. 카운팅 세마포어 사용예시: 원격 서버가 구축되어있고 5개의 프린트가 연결되어 최대 5 개의 프린트만 동시에 사용할 수 있다. 서버에서 semaphore를 5로 설정하고 클라이언트 의 요청이 들어왔을때 wait을 통해서 5개가 다 사용중인 상황이면 기다리도록 한다. E. Mutex Lock
1. 정의: mutual exclusion의 약자이다. 바이너리 세마포어와 동일하다.
바이너리 세마포어를 사용하는 경우가 굉장히 많기 때문에 세마포어와 따로 분리해서 구 현해 둔 것이다.
F. Monitor
1. 정의: 세마포어는 사용법이 어려워서 유저가 데드락을 만드는 등의 실수를 할 수 있기 때 문에 프로그래밍 언어 레벨에서 라이브러리로 동기화 툴을 제공하고 컴파일하면 자동으 로 보호되도록 하는것이 좋을것이라는 접근에서 나왔다. Java가 모니터를 지원하는 예시 이다. C/C++을 사용하는 경우는 세마포어를 사용해야한다. 코드에서 모니터를 선언해서 shared로 쓸수 있는 리소스와 리소스를 사용하는 코드를 묶어놓는다. 한 함수가 수행되고 있으면 다른 함수를 수행하지 못하도록 모니터가 차단한다.
2. Conditional Variable: Monitor에서는 함수를 계속 수행하는 게 아니라 IO이벤트 등을 기다 리는 상황에도 다른 함수들을 수행할 수 없는 문제가 발생한다. 이를 해결하기 위해서 conditional variable을 사용해서 특정 상황에 대해 예외적으로 lock을 풀어준다. Conditional Variable은 세마포어와 비슷하게 wait과 signal로 구현되어있는데, 차이점은 세 마포어는 히스토리가 존재하고 모니터에는 존재하지 않는다는 점이다. 세마포어는 0,1,2 와 같이 정수값을 가지지만 conditional variable에는 true/false만 존재한다.