상호 배제: 하드웨어 지원

상호 배제를 하기 위해 하드웨어의 지원을 받는 경우

1. 인터럽트 금지

• 인터리빙하게 수행될 때 인터럽트가 걸려 다른 프로세스의 내용이 수행
• 단일 CPU의 경우 인터리빙
• 인터럽트를 잠시 금지 -> 인터리빙하게 수행되는 명령어들이 잠시 멈추게 됨

while (true){
/* 인터럽트 금지하는 기계어 명령어 */
/* 임계영역 */
/* 인터럽트 허용하는 기계어 명령어 */
/* 임계영역 이후 코드 */
}

단점

• 부하가 큼
• 외부 이벤트에 대한 처리, 다른 프로세스에 대한 스케줄링, 문맥교환 등 모든 기능 중지 -> 시스템 수행 효율 매우 저하
• 두 개 이상의 CPU에서는 안됨

2. 특별한 기계 명령어

• 멀티프로세스가 메모리를 공유할 경우
• 동일 위치에 대해서 두 개의 프로세스가 동시에 접근하는 것은 허용하지 않는 것이 멀티프로세서 하드웨어의 기본적 특징
  => 동일 메모리 주소 접근은 동시 접근 요청 차단됨
• 상호 배제를 위한 다음을 한번에 수행하는 새로운 명령어 고안
  - 같은 메모리 위치에 대한 읽기와 쓰기(읽기 + 쓰기)
  - 같은 메모리 위치에 대한 읽기와 테스트(읽기 + 테스트)
  => 같은 메모리 위치를 접근하려는 다른 명령어들은 블록됨

Compare & Swap 명령어

/* 하나의 기계 명령어로 지원됨 -> 원자적 수행 */
int compare_and_swap (int *word, int testval, int newval)
{
	int oldval; 
	/* word의 값을 대입복사 */
	oldval = *word 
	/* newval 값을 word의 위치에 set */
	if (oldval == testval) *word = newval; 
	return oldval;
}

/* 상호 배제 예제 프로그램 */
const int n = /* 프로세스 개수 */
/* 공유하는 전역변수 -> 0으로 초기화 */
/* 전역변수가 0일 경우 임계 영역으로 진입 가능 */
int bolt;
void P(int i)
{
	while (true) (
		/* compare_and_swap -> 원자적 수행. bolt가 0이라면 1로 설정 */
		/* bolt가 1일 동안 수행 -> CPU를 계속 점유(busy waiting, spin waiting) */
		while(compare_and_swap(bolt,0,1) == 1)
			/* 대기 */
		/* 임계영역 */
		/* 임계영역에서 빠져나올 경우 반드시 전역변수를 0으로 돌려놔야 함 */
		bolt = 0
		/* 임계영역 이후 코드 */
	)
}
void main()
{
	bolt = 0;
	/* n개의 프로세스를 병렬적으로 수행시킴 */
	parbegin(P(1),P(2), ... , P(n))
}

• compare_and_swap 원자적으로 수행하는 명령어 지원
  - 테스트 하려는 값(testval)
  - 메모리 위치에 저장된 값(*word)
  - 새로운 값(newval)

Exchange 명령어

• 레지스터의 값과 메모리에 들어있는 값을 서로 교체
• IA-32(Pentium), IA-64(Itanium)
  - XCHG 명령어

void exchange (int *register, int *memory)
{
	int temp;
	temp = *memory;
	*memory = *register;
	*register = temp;
}

/* 상호 배제 예제 프로그램 */
int const n = /* 프로세스 개수 */
int bolt;
void P(int i)
{
	while (true) {
		/* 중간에 다른 스레드가 들어와 exchange를 실행해도 keyi와 바꾸어도 전역변수 bolt는 1인 상태이므로 변화가 없음 => bolt가 0이 될 때까지 무한루프 돌면서 임계영역 진입 대기*/
		int keyi = 1;
		/* 임계영역 진입 전 setting */
		/* keyi의 값은 0이 되고 bolt가 1이 됨 */
		do exchange (&keyi, &bolt)
		while (keyi != 0);
		/* 임계영역 */
		/* 임계영역을 벗어나는 setting */
		bolt = 0;
		/* 임계영역 이후 코드 */
	}
}

void main()
{
	/* bolt의 초기값 */
	bolt = 0;
	/* n개의 프로세스 병렬 실행 */
	parbegin(P(1), P(2), ... , P(n))
}

기계 명령어 접근 방법의 특성

장점

• 단일처리기 CPU 뿐만 아니라 멀티프로세서 시스템에서도 사용 가능(공유 메모리를 사용하는 경우)
• 간단하고 검증이 쉬움
• 변수를 여러개 두어 여러 개의 임계영역을 두는 것이 가능

단점

• 바쁜 대기(busy waiting, spin waiting) 사용
  - 임계영역에 진입하고자 기다리고 있는 프로세스는 처리기를 계속 사용
• 기아 발생 가능성
  - 프로세스가 임계영역에서 빠져 나왔을 때 대기하고 있던 프로세스가 여러개라면 하나의 프로세스만이 다시 진입 가능
  - 이 때 프로세스의 특성이나 기다린 대기시간 등을 고려하지 않으므로 무한정 기다리게 되는 프로세스가 생기면 기아 발생
• 교착 상태에 빠질 수 있음
  - 프로세스 P1은 특별한 명령어(compare&swap이나 exchange)를 수행한 후 임계영역 진입
  - P1보다 높은 우선순위의 P2가 생성되고 OS가 P2 프로세스 스케줄
  - P2가 P1과 같은 자원을 쓰려고 시도하면 상호 배제 조건에 의해 실패하고 바쁜 대기 수행
  - 우선순위가 높은 프로세스인 P2가 계속 바쁜 대기를 수행하면서 실행상태이므로 P1이 다시 스케줄링 될 수 없는 상태가 됨