[OS] Critical-Section solution
- Objection
- critical section 이란?
- critical section problem 을 해결하기위한 software solution
- critical section problem 을 해결하기위한 hardware solution
1) critical section 이란?
- shared data 를 공유하는 모든 프로세스들이 자원에 접근하기 위해 모두 경쟁한다.
- 이 때 critical section 이라고 하는 어떠한 code segment 라고 하는 data 에 접근하고자 하는 프로세스들이 있다.
- 어떠한 프로세스가 이 critical section 을 접근했을 때 다른 어떠한 프로세스들도 접근 할 수 없다.
- critical section problem 의 요구사항
- Mutual exclution
-> 공유자원에는 한번에 하나의 프로세스만이 자원을 사용할 수 있어야 함.
- Progress
-> 아무도 공유자원에 접근하고 있지 않을 때 어떠한 프로세스라도 접근할 수 있어야 함.
- Bounded Waiting
-> 어떠한 프로세스라도 공유자원을 사용하고자 할때 무한정 기다리지 않아야 한다.
2) critical section problem 을 해결하기위한 software solution
- critical section 주변을 fence 를 치는 방법으로 해결
- critical section 직전에 fence 를 닫겠다고 표시하는 "entry section" 만들기
- critical section 직후에 fence 를 열겠다고 표시하는 "exit section" 만들기
- entry section 에서 검사를 통해 fence 안에 어떠한 프로세스도 없다면 critical section 접근 가능.
3) critical section problem 을 해결하기위한 hardware solution
- interrupt 의 처리를 뒤로 미루기 위해 atomic operation 방법 사용
- critical section 을 atomic 하게 실행하는 것이 아니라 entry section 을 atomic 하게 실행시켜 entry section 에서만 interrupt 의 처리를 지연시키는 방법.
- entry section 은 코드를 길게 구현하지 않음.
- solution 1 : Test and Set instruction
- 이 위의 코드에서 두번째 while 문이 entry section 이다.
- 이 section 에서는 interrupt 가 걸릴 수 없으며, 그 다음 section 인 critical section 은 atomic 하게 실행되지 않으므로 interrupt 가 걸릴 수 있다.
- 어떠한 프로세스가 critical section 안에서 interrupt 가 걸린 후 context switch 가 일어나면 다른 어떠한 프로세스라도 critical section 으로 접근 불가.
-> 이 상황에서는 entry section 에서 busy waiting 을 하다가 context switch 됨.
- Test and Set instruction 의 장점
- 몇개의 processer 구조라도 적용할 수 있다.
- 간단해서 확인이 쉽다.
- 여러개의 critical section 에서도 사용 가능하다.
- Test and Set instruction 의 단점
- busy-waiting 을 하게 됨.
-> 기다리기 위해서만 CPU time 사용 ( 낭비 )
- bounded waiting 이 보장되지 않을 수 있음.
-> 확률은 매우 적지만 이론상 발생 가능 ( 실제 OS 에서는 무시하는 추세 )
- Deadlock 발생 가능
- solution 2 : Semaphore : test and set instruction 의 단점을 보완하는 solution
-> 긴 문장 ( bakery algorithm ) 이나 busy wait ( test and set ) 를 안해도 됨.
-> busy wait 가 아닌 진입할 수 없는 상황이라면 block 상태로 바뀜. ( CPU 를 다른 프로세스에게 넘겨줌. )
- entry section 으로 "semWait (s)" 함수 사용
- exit section 으로 "semSignal (s)" 함수 사용
- 함수의 인자로 사용되는 "s" 는 전역변수로 반드시 초깃값을 정의해주어야 함. ( 대부분 1로 정의 )
- semaphore 역시 critical section 은 atomic 하게 실행되지 않음. ( Interrupt 걸릴 수 있음 )
- 하지만 entry, exit section 은 atomic 하게 실행
