[Operating System] Semaphore

Locks

• 쓰레드는 서로 메모리를 공유한다. 따라서 공유변수가있다. 여러 쓰레드가 모두 변수의 값을 read하는 경우 문제가 발생하지 않지만, 특정 쓰레드가 변수의 값을 write하면 동기화 문제가 발생한다.
• 이를 해결하기 위해서는 한 thread가 변수를 write할 때에는 다른 thread가 해당 변수에 접근할 수 없도록 lock을 걸어주는 과정이 필요하다.
• lock~unlock의 구간을 critical section(임계 영역)이라고 한다.
• critical section은 해당 영역 내의 다수의 명령어를 atomic(원자적)하게 실행되도록 보장한다.
• 마지막으로 starvation이 발생하지 않아야 한다.

mutual exclusion (상호 배제)

• critical section에는 어느 시점에서든 반드시 단 1개의 thread만 접근 가능해야 한다는 개념이다.

race condition (경쟁 조건)

• 다수의 thread가 공유 data를 read/write하는 상황이다.임계 영역으로 들어가려고 경쟁하는거

deadlock (교착 상태)

• 다수의 thread가 다른 thread가 어떠한 일을 해 줄 때까지 대기하는 상태로, 모든 thread가 다른 thread의 변화를 기다리며 대기하는 상황이다.

livelock

• 다수의 thread가 단순히 자신의 상태를 변화시키는 작업만 반복적으로 수행하면서 대기하는 상황이다.

상호 배제

• 상호 배제를 위한 세부요구조건이있다.
• 이것은 강제되어야한다.
• 임계영역 밖 어떤 쓰레드도 임계영역내 쓰레드에 간섭해서는안된다.
• 데드락, starvation이 발생하면안된다.
• 임계영역에 아무도 접근하지않을때는 대기하던 쓰레드중 하나가 즉시 임계영역에 접근할 수있어야한다.

mutual exclusion을 구현하기 위한 여러 방법을 살펴보자. 단순화를 위해 binary mutual exclusion으로 가정한다. 즉, 2개의 process만이 존재하는 상황이다.

turn variable

• turn 이라는 boolean 변수를 활용해 TURN==0이면 쓰레드0을 TURN==1이면 쓰레드1을 실행한다.
• 한 쓰레드가 연속적으로 임계영역을 점유하지 못하는 문제가 있따. 0이 임계영역점유하고 나오면 1이 임계영역 점유전까지는 점유할 수 없다.. 1이 임계영역에 접근할 필요가없는 쓰레드라면 0은 무한히대기한다. 데드락.

int turn=0;

// thread 0
void thread0(void){
	while(1){
		while(turn);
		/*
			critical section...
		*/
		turn = 1;
	}
}

// thread 1
void thread1(void){
	while(1){
		while(!turn);
		/*
			critical section...
		*/
		turn = 0;
	}
}

Busy waiting

• lock step 사이에 문맥교환이 발생하는 것을 막기위해 flag를 변경시킨뒤 대기한다. flag의 변경과 while문 사이에 문맥교환이 발생하면 모든 flag가 1이된다. 이경우 모든 쓰레드가 flag를 확인하는 while문을 무한히 수행한다..

int flag[2] = {0, 0};

// thread 0
void thread0(void){
	while(1){
		flag[0] = 1;
		while(flag[1]);
		/*
			critical section...
		*/
		flag[0] = 0;
	}
}

// thread 1
void thread1(void){
	while(1){
		flag[1] = 1;
		while(flag[0]);
		/*
			critical section...
		*/
		flag[1] = 0;
	}
}

BUSY WAITING MODIFIED

• FLAG를 초기화해주는것과 WHILE문의 위치를 바꾸면된다.

BUSY FLAG AGAIN

• 다른 쓰레드의 FLAG를 검사하는 WHILE문 내에서 자신의 FLAG를 일정시간간격으로 TOGGLE한다. 이경우 딜레이 시각내에 문맥교환이 발생하면 다른 쓰레드가 임계영역에 접근가능하다. 하지만 이역시 두 쓰레드의 DELAY가 동시에 발생하는 최악에 경우 LIVELOCK상태에 빠진다.

int flag[2] = {0, 0};

// thread 0
void thread0(void){
	while(1){
		while(flag[1]){
			flag[0] = 0;
			delay(10);
			flag[0] = 1;
		}
		/*
			critical section...
		*/
		flag[0] = 0;
	}
}

// thread 1
void thread1(void){
	while(1){
		while(flag[0]){
			flag[1] = 0;
			delay(10);
			flag[1] = 1;
		}
		/*
			critical section...
		*/
		flag[1] = 0;
	}
}

상호배제를 보장하기 위한 HW 지원

인터럽트 금지

• HW적으로 임계영역 접근이전에 인터럽트를 금지한뒤 임계영역이후에 인터럽트를 활성화함으로써 문맥교환이 발생하지 않도록한다.

// thread 0
void thread0(void){
	while(1){
		interrupt_disable();
		/*
			critical section...
		*/
		interrupt_enable();
	}
}

// thread 1
void thread1(void){
	while(1){
		interrupt_disable();
		/*
			critical section...
		*/
		interrupt_enable();
	}
}

atomic instruction

• 기존 FLAG정책에서 다른 쓰레드 FLAG를 검사하는 WHILE문과 자신 FLAG값 변경하는 명령어 사이에 문맥교환이 발생하는 경우였다. 이를 막기 위해 HW상에서 명령어를 원자적으로 묶어 실행되도록한다. 이를위해 HW는 TESTSET과 EXCHANGE라는 명령어를 제공한다.

int flag[2] = {0, 0};

void thread0_atomic_instruction(void)
{
	while(flag[1]);
	flag[0] = 1;
}

void thread1_atomic_instruction(void)
{
	while(flag[0]);
	flag[1] = 1;
}

// thread 0
void thread0(void){
	while(1){
		thread0_atomic_instruction();
		/*
			critical section...
		*/
		flag[0] = 0;
	}
}

// thread 1
void thread1(void){
	while(1){
		thread1_atomic_instruction();
		/*
			critical section...
		*/
		flag[1] = 0;
	}
}