[혼공컴운]5주차 동기화와 교착상태

12 동기화

12-1 동기화 개요

동기화란 프로세스의(또는 스레드) 실행순서제어 또는 상호배제를 통해 올바른 실행을 의미한다.

상호배제

공유자원을 동시에 이용하지 못하게 하는 것.

→공유자원의 종류

• 전역변수
• 파일
• 입출력장치
• 보조기억장치

임계구역

공유자원을 접근하는 코드 영역. 보통 공유자원을 읽기만 하면 문제가 되지 않지만 수정을 하는 순간 문제가 발생한다.

레이스컨디션

공유자원에 대한 상호배제가 이루어지지 않은 상태. 데이터레이스라고도 한다.

--- C언어
total++;
--- Assembly
r1 = total;
r1 = r1 + 1;
total = r1;

고급언어는 여러줄의 저급언어(기계어인 명령어)로 변환될 수 있으며 저급언어에서 context switching이 일어나므로 해당 코드가 온전히 실행될 수 있도록 도와주어야한다.

--- C
pthread_mutex_lock
total++;
pthread_mutex_unlock
--- Assem
mutex lock 
r1 = total;
r1 = r1 + 1;
total = r1;
mutex_unlock

다음과 같이 온전히 실행되게 해준다면 저급언어에서 상호배제를 통한 데이터레이스를 방지할 수 있다.

12- 2 동기화 기법

mutex, 세마포어, 모니터

mutex

자물쇠 기능.

pthread_mutex_lock : busy waiting으로 체크한다.

임계구역

pthread_mutex_unlock : 임계구역 열어줌

세마포어 ( Semaphore)

공유자원이 여러 개 존재할 때 사용하기 좋다.

공유자원 이름 : S

임계구역 진입 함수 : wait()

임계구역 반환 함수 : signal()

세마포어는 다음과 같이 busy waiting을 해결할 수 있다.

wait() {
	S--;
	if ( S < 0 ){
		waitQueue.add(this.process);
		sleep()
	}
}

signal(){
	S++;
	if ( S <= 0 ) {
		Process p = waitQueue.popleft()
		wakeup(p) // p를 준비상태로 만든다.
	}
}

세마포어는 프로세스의 동작 순서를 제어할 수도 있다.

모니터

최근에 등장한 동기화 도구. 사실 나도 지금 처음 봄.

• 반드시 인터페이스를 통해 공유자원 접근
• 모니터 안에는 하나의 프로세스만
• 큐에 삽입된 순서로 자원에 접근

wait, signal 함수를 통해 실행을 중단, 재개할 수 있다.

13 교착상태

밥먹는 철학자 문제. 철학자는 스레드고 밥은 자원이다.

13-1 교착상태 개요

어떤 프로세스(스레드)가 실행을 하기 위해 필요한 자원을 무한정 기다리게 되는 상황이다.

교착상태 발생조건

4가지 조건을 모두 만족했을 때 발생!!

• 상호배제(mutual exclusion) : 공유자원을 동시에 이용못하는 것
• 점유와 대기 : 자원을 보유한 채 다른 자원을 기다리는 것
• 비선점 : 자원을 강제로 뺏지 않는 것
• 원형대기 : 프로세스와 요청 및 할당받은 자원의 관계가 원형을 이루는 것.

→ 당연하게도 교착상태를 해결하기 위해서 위의 조건들 중 하나를 부셔야한다. 밥먹는 철학자 문제에서 교착상태를 해결하기 위해서는 무엇을 해야할까??

13-2 교착상태 해결하기

결론부터 말하면 원형조건을 깨는 방법으로 나는 해결했다.

TID % 2 == 0 인 철학자는 왼손포크를

TID % 2 == 1 인 철학자는 오른손포크를 들게 한다.

이렇게 하면 포크경쟁이 일어나게 되고 확정적으로 교착상태가 깨지게 된다.

void	fork_rule(t_philo *philo, t_info *info)
{
	if (!(philo->id % 2))
		pthread_mutex_lock(&(info->fork[philo->left]));
	else
		pthread_mutex_lock(&(info->fork[philo->right]));
	print_philomsg(philo->id, info, "has taken a fork", 0);
	if (!(philo->id % 2))
		pthread_mutex_lock(&(info->fork[philo->right]));
	else
		pthread_mutex_lock(&(info->fork[philo->left]));
	print_philomsg(philo->id, info, "has taken a fork", 0);
}

교착상태 해결 → 발생조건 중 1개라도 부수면 가능!

교착상태 예방

상호배제 제거

→ Read Only 자원이라면 괜찮겠지만 현실적으로 상호 배제를 없애는 것은 말이 안 된다.

점유와 대기 제거

한 명의 철학자가 포크를 둘 다 들거나 아예 안 들거나.

→ 하나의 프로세스가 자원을 다 갖거나 안 갖거나

• 많은 자원을 사용하는 프로세스는 다 갖는 타이밍을 갖기 힘들다. → 기아현상

비선점 제거

RR처럼 Time Slice만큼 CPU자원을 이용하는 경우는 효과적.

하지만 입출력 자원, 예를 들어 프린트자원 같은 경우는 뺏을 수 없게 해야한다. 즉, 범용성이 떨어진다.

원형대기 제거

모든 자원에 번호를 붙이고 낮은 포크에서 높은 포크 순으로 집어들게 한다. 단, 모든 자원에 번호를 붙이는 것은 쉬운 일이 아니다. 그래도 가장 현실적인 방법!

철학자 문제에서 이런 해결법은 자원의 할당이 늦어지는 기아현상을 유발할 수 있다. 따라서 나는 짝수는 왼쪽포크, 홀수는 오른쪽 포크를 경쟁해서 집도록 했다.

교착상태 회피

교착상태가 발생하지 않도록 자원을 분배하는 것.

교착상태 검출 후 회복

교착상태가 발생했을 때 이를 해결하는 방법이다.

선점을 통한 회복

교착상태가 해결될 때까지 프로세스(스레드)에 자원을 할당한다.

종료를 통한 회복

교착상태가 발생한 프로세스를 모두 종료하거나 하나씩 종료하는 방법

 

++숙제

p. 363의 확인 문제 1번

-> 4번

임계구역과 상호배제란

-> 상호배제 : 공유자원 동시에 이용하지 못하게 하는 것.

임계구역 : 공유자원을 접근하는 코드영역