[운영체제/OS] Mutual Exclusion with Busy Waiting

mutual exclusion(상호 배제)
: 한 프로세스가 공유 변수나 파일을 사용 중이면 다른 프로세스들은 똑같은 일을 수행하지 못 하도록 막아 race condition을 회피하는 것
busy waiting(바쁜 대기)
: 변수가 특정 값이 될 때까지 계속해서 검사하는 것

1. lock variable(락 변수) 사용

• 개념: 소프트웨어 해법으로, 0으로 초기화된 단일 공유 변수인 lock을 사용
• 과정
  - critical region에 진입하려는 프로세스가 lock을 검사하여 0이면 1로 설정 후 critical region에 진입
  - lock이 1이면 프로세스는 lock이 0이 될 때까지 기다림
• 한계: race condition 발생 가능

2. strict alternation(엄격한 교대)

• 개념: busy waiting과 spin lock을 통해 ciritical region에 진입하고, 변경할 프로세스 순번을 나타냄
  - spin lock: busy waiting을 사용하는 lock 변수
• 과정
  - process 0과 process 1이 있다고 가정
  - spin lock(turn)이 0이면 process critical region에 진입할 차례이므로 process 1을 무한 loop
  - process 0이 ciritical region에서 빠져 나오면 spin lock을 1로 설정
  - process 1이 무한 루프에서 빠져나와 critical region에 진입하고 빠져나오면 spin lock을 0으로 설정
• 한계
  - 프로세스가 연속해서 critical region에 진입할 수 없음
  - 한 프로세스가 다른 프로세스보다 상당히 느리면 많은 시간이 걸림
  
  
  

3. Perterson's Solution

• 개념: spin lock과 동시에 critical region 진입에 대한 프로세스의 관심을 나타내는 interseted 배열을 사용
• 과정
  - 프로세스가 critical region에 진입하기 전에 enter_region 함수를 호출하고, 빠져나오면서 leave_region 함수 호출

#define FALSE 0
#define TRUE 1
#define N 2		// process 수

int turn;
int interested[N];

void enter_region(int process) {	// process는 0이나 1임
	int other;
    other = 1 - process;
    interested[process] = TRUE;
    turn = process;
    while(turn == process && interested[other] == TRUE) // busy waiting
}

void leave_region(int process) {
	interested[process] = FALSE;
}

4. TSL(Test and Set Lock) instruction

• 개념: 하드웨어 해법으로, TSL 명령어를 사용하여 lock 변수에 접근할 때 스케줄링이 발생하지 않도록 함
• 과정
  - lock 변수의 값을 읽어 register에 저장 후 lock 변수를 1로 set
  - register에 저장된 값이 0이면 critical region에 진입
  - register에 저장된 값이 1이면 busy waiting

enter_region:
	TSL REGISTER, LOCK	| copy lock to register and set lock to 1
    CMP REGISTER, #0	| was lock zero?
    JNE enter_region	| if it was non zero, lock was set, so loop
    RET		| return to caller, critical region entered
    
leave_region:
	MOVE LOCK, #0	| store a 0 in lock
    RET		| return to caller

5. Busy Waiting의 한계

• 단순한 loop에 CPU 낭비
• 우선 순위 역전 문제(priority inversion problem) 발생