동기화

동기화 필요성

• 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 동기화 툴을 제공한다. 코어가 하나인 시스템에서 많이 사용되던 형태로 멀티프로세서에서는 잘 동작하지 않을 수 있다.

세마포어