[운영체제] Process Synchronization (2)

Initial Attempts to Solve Problem

 

공유 데이터를 접근하기 이전에 lock을 걸어 여러 프로세스가 동시에 들어가는 것을 막음. 

코드를 넣어서 critical section 해결하는 알고리즘 존재.

---

프로그램적 해결법의 충족 조건

 

- Mutual Exclusion 상호 배제  : 프로세스가 진행 중일 때 다른 프로세스가 critical section에 들어가지 않게 함.

- Progress 진행 : 아무도 critical section에 들어가지 않은 상태라면 프로세스가 critical section에 들어갈 수 있도록 해야 함.

- Bounded Waiting 유한 대기 : 기다리는 시간이 유한해야 함. 프로세스가 진행 중일 때 다른 프로세스가 들어가는 횟수를 제한. (지나친 starvation 피하기 위함.)

---

알고리즘 1

int turn : critical section에 들어가는 차례

Process P0 코드 (프로세스 P1도 이와 동일)

int turn;
turn = 0;
do {
	while(turn!=0):
    	// critical section
	turn = 1;
    	// remainder section
} while(1);

p0 입장에서 본인 입장에서 기다림. turn이 0으로 바꾸는 순간(p1이 1에서 0으로 바꿔줌.)

critical section 실행 후 나올 때 turn을 1로 바꿔줌. (상대방 차례로 바꿔줌.)

 

=> 들어가 있는 프로세스가 turn을 바꿔줘야 다른 프로세스가 들어갈 수 있기 때문에 progress 측면을 충족하지 못한 알고리즘

 

 

알고리즘 2

boolean flag : 본인이 critical section에 들어가고자 하는지

// 프로세스 Pi와 Pj

boolean flag[i] = false;
boolean flag[j] = false;

do {
	flag[i] = true;
    while(flag[j]) 
    	// critical section
		flag[i] = false;
        // remainder section
} while(1);

본인의 flag를 true로 만듬 -> 상대방 flag를 체크해서 true라면 기다리고, false라면 먼저 들어가서 critical section 실행 -> 실행 후 flag를 false로 바꿈.

 

=> 깃발만 들고 두 프로세스가 들어가지 않은 상태. 깃발을 내려놓는 행위는 나오는 행위에서 false로 처리함.

 둘다 true인 경우 아무도 critcal section을 실행하지 않는 상태. Mutual Exclusion 충족 X.

 

 

알고리즘 3 (Peterson's Algorithm)

알고리즘 1과 2 복합

// 프로세스 Pi, Pj
do {
    flag[i] = true;
    turn = j;
    while(flag[j] && turn ==j) {
    	// critical section
        flag[i] = false;
        // remainder section
    }
} while(1);

 상대방의 flag가 true이고 상대방의 차례라면? critical section 을 실행하고 flag를 false로 바꾸고 빠져나옴.

 

=> 3가지 프로그램적 해결법을 충족함. but Busy Waiting(spin lock) 문제 발생 (계속 CPU와 메모리를 쓰면서 wait)

 

 

Synchronization Hardware

하드웨어적으로 Test & modify를 atomic 하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결.

데이터를 메모리에서 읽는 동시에 쓰는 것이 하나의 instruction으로 가능하다면 쓰는 도중에 빼앗기지는 않을 것.

-> lock을 걸고 푸는 것이 해결될 수 있음.

 

Test_and_set(boolean lock) {
    // lock check -> if(!lock) -> lock 걸고 들어감.
    // lock check -> if(lock) -> 기다림.
}

boolean lock = false;

// Process Pi
do {
	while(Test_and_Set(lock) {
    	// critical section
        lock = false;
        // remainder section 
    }
}

값을 읽는 작업과 set하는 과정을 atomic 하게 실현된다면 lock이 실행 됨.