OS - Synchronization Tools

Synchronization

• Multi-Threads(process) program에서 thread는 자원을 공유하기도 하며, shared data structure에 접근하기도 하고, 실행 순서를 조정하기 때문에 synchronization이 필요하다.

Multi-process program

• message-passing model을 이용하여 구현하는 경우가 일반적

Multi-thread program

• shared memory model을 이용하여 구현하는 경우가 일반적
  • 전역 변수를 선언하면 그것이 곧 shared memory가 되기 때문이다.
  • multi-thread program이 동기화 문제에 더 민감하다.

Withdraw money from a bank account problem

int withdraw(account, amount) 
{
	balance = get_balance(account);
	balance = balance - amount;
	put_balance(account, balance);
	return balance;
}

• 동기화 문제가 발생하면 계좌 잔액이 수행 결과와 다른 결과를 도출하게 된다.

bound-buffer problem

// producer
void producer(data) 
{
	while (count==N);
	buffer[in] = data;
	in = (in+1) % N;
	count++;
}

// consumer
void consumer(data) 
{
	while (count==0);
	data = buffer[out];
	out = (out+1) % N;
	count--;
}

• count 변수의 초기값을 5라고 가정한다.
• producer process가 실행된 후 count++를 수행하기 직전에 context switch가 발생하여 consumer process가 수행된다.
• consumer process가 수행되고 count--를 수행하기 직전 producer process로 context switch한다.
• count++ 가 수행된 후 count에는 6의 값이 저장되고 다시 consumer process를 수행한다.
• count--가 수행될 때 count에는 5가 저장되어 있으므로 수행 결과 count는 4가 되는 동기화 문제가 발생한다.

Synchronization Problem (=Critical section Problem)

• 2개 이상의 thread(or process)가 shared resource를 동기화 과정 없이 접근하여 발생한다.

shared resource

• 계좌, 전역 변수, circular queue, linked list 등의 자료 구조도 될 수 있다.

critical section

• shared data를 사용하는 영역, race condition을 유발하는 영역

Race Condition

• 2개 이상의 thread(or process)가 shared resource를 사용하기 위해 경쟁하는 상황
• race condition을 만족해도 타이밍에 따라 동기화 문제가 발생하지 않을 수도 있다
  • Non-deterministic

Requirements for Synchronization Tools

Mutual Exclusion (상호 배제, 가장 중요)

• critical section에서 동작하는 프로세스가 있으면 이외의 프로세스는 실행되면 안된다.

Progress

• critical section에 동작하는 프로세스가 없는 상태에서 critical section을 사용하고자 하는 프로세스가 있다면 대기의 과정 없이 사용하게 한다.

Bound Waiting (무한히 기다리게 하면 안된다)

• 한 프로세스가 critical section 진입 요청을 한 이후부터 이 요청이 허용될 때까지 다른 프로세스가 critical section에 진입할 수 있는 횟수가 제한되어야 한다.

Synchronization Tools

Locks (low level mechanism)

• OS, Kernel 등 낮은 단계의 동기화 문제를 해결하는데 많이 사용된다.

• lock의 초기 상태는 free상태이며 critical section에 진입하기 전에 lock()를 호출하며 동작이 끝나고 critical section을 빠져나갈 때 unlock()을 호출한다.
  

• 한번에 하나의 thread만이 lock을 가질 수 있다.

Spinlocks

• lock걸린 상황이라면 CPU를 사용하며 무한루프를 돌며 Busy wait한다.
• held = 0인 상태에서 while 조건문을 통과한 직후 interrupt가 발생하면 critical section에 2개의 프로세스가 들어가는 상황이 발생할 수 있다
  • atomic operation을 사용한다.

해결법

Software only algorithms

• bakery algorithm 등이 있지만 복잡도가 높아지고 성능이 좋지 않아 사용하지 않는다.

Hardware atomic instructions

• 쪼개질 수 없는 CPU 명령어를 이용하여 Lock을 구현한다.
• Multi-processor OS에서 사용하는 방식
• test and set

boolean TestAndSet(boolean &target) {
	boolean rv = target;
	target = true;
	return rv;
}

struct lock { int held = 0; }
void lock(struct lock *l) 
{
	while (TestAndSet(l->held));
}
void unlock(struct lock *l) 
{
	l->held = 0;
}

• compare and swap

boolean CompareAndSwap(boolean &a, boolean &b) 
{
	boolean rv = a;
	a = b;
	b = rv;
	return rv;
}

struct lock { int held = 0; }
void lock(struct lock *l) 
{
	key = true;
	while (CompareAndSwap(l->held, key));
}
void unlock(struct lock *l) {
	l->held = 0;
}

Problems with spinlocks

낭비가 매우 심하다

• OS가 짧은 Critical section을 보호하는데 사용한다.
• high-level 동기화 구조를 만들 때 짧은 구간에 primitive하게만 사용되어야 한다.
• 어플리케이션 레벨에서는 busy wating이 아닌 waiting상태나 sleep상태에서 대기해야한다.

Disabling interrupts

• (single CPU / RTOS에서 사용하는 방법)
• critical section에서 interrupt가 동작하지 못하도록 한다.
  • 구현하기 쉬우며, MCU와 같이 작은 CPU에 사용될 수 있다
  • multi-processor에서 사용하지 못하며, critical section이 길어진다면 중요한 이벤트를 놓치거나 지연시킬 수 있는 문제를 발생시킨다.
  • interrupt를 중지할 수 있는 건 kernel뿐이며 그 구간이 길어서는 안되기 때문에 high-level 동기화 문제를 해결하기 위해 primitive로 짧게 사용되어야 한다.

Interrupt를 disable하게 만드는 주체는 CPU

• CPU가 2개 이상이 되면 사용하지 못한다
• compare & swap사용
  

High-level synchronization

• Spinlock(atomic)이나 disabling interrupt는 Primitive하기 때문에 system call 형식으로 제공되어야한다.
  • mutual exclusion을 제외하고 다른 기능을 제공하지 않는다.
• OS에서는 Critical section문제가 발생하면 안되기에 atomic한 방법으로 구현한다.
• high-level 동기화 primitive에서는 block waiters와 critical section을 떠날 때 interrupt enable을 가능하게 해야한다.
  • Semaphores : binary and counting
  • Monitors : mutexes and condition values

Semaphores

• shared data object에 접근하는 프로세스(thread)의 개수를 counting한다
• 사용가능한 Shared data object 수 operation : wait or P (-1)/ signal or V (+1)
• semaphore의 수가 양수라면 shared data가 사용 가능하면 -1을 하며 사용한다.
• semaphore의 수가 0이라면 프로세스는 sleep상태가 된다.
• critical section에 binary semaphore를 사용한다.

Mutex Locks

• spinlock은 OS에서 사용하며, mutex lock은 애플리케이션 레벨에서 사용할 수 있다.
  • busy waiting이 아닌 block상태로 대기한다.
• Binary semaphore와 같은 동작으로 mutex locks를 구현할 수 있다.

Semaphore implementation

typedef struct {
	int value;
	struct process *L;
} semaphore;

wait(semaphore *S) {
	lock(lock); S->value--; unlock(lock);
	if (S->value < 0) {
		add this process to S->list; 
		block(); 
	} 
}
signal(semaphore *S) { 
	lock(lock); S->value++; unlock(lock);
	if (S->value <= 0) {
		remove a process P from S->list; 
		wakeup(P); 
	} 
}

• *L : Semaphore를 기다리는 프로세스 리스트
• lock(), unlock() : OS Spinlock or interrupt disabling

Deadlock and Starvation

Deadlock

• 2개 이상의 프로세스가 동시에 semaphore/mutex에 접근함으로써 하나의 waiting상태의 프로세스로 인해 lock이 무한히 풀리지 않는 경우
  

Starvation (indefinite blocking)

• 프로세스가 semaphore의 queue에서 벗어나지 못하는 상황

Problems with Semaphores

• 본질적으로 shared 전역변수를 사용한다.
  • bad software engineering(코드 이해가 어렵다)
• semaphore와 데이터 제어와의 연결관계가 없다
  • 버그 양산
• semaphore에 대한 사용 제어가 없고 적절하게 사용되지 않을 수 있다
• 스케줄링과 critical section보호에 동시에 사용된다.
  • 개발자가 semaphore를 구현하는 것이 아닌 programming language차원에서 구현한다.
  • Monitors / Critical region

Monitors (JAVA에서만 지원)

• programming language가 shared data를 제어하는 구조를 설립한다.
• 컴파일에 동기화 코드가 추가되며 런타임 시간에 실행된다.
• shared data에 접근하는 함수(procedure)를 만들고 접근시에 함수가 실행된다.

• procedures에서 operations를 수행하는 thread가 특정 상황을 기다리며 waiting될 수 있다

  • condition variable(wait/signal operation) 사용
  • thread가 x상황을 기다리면 condition x의 queue에 들어가 대기하고 critical section에 다른 thread를 추가한다.

• condition variable는 history를 가지지 않으나 semaphore는 history를 가진다.

  • cv는 waiting상태가 없는 경우 signal()이 수행될 경우 아무 동작도 하지 않는다.
  • semaphore는 semaphore를 증가시킨다.
  • cv는 wait()는 단순히 wait하며 semaphore는 semaphore를 감소시킨다.