[CS][OS] Semaphore

Semaphore

• key를 얻고 반납하는 과정과 비슷하다.
• 정수형 변수 s(semaphore), P 연산, V 연산

void wait(s){
	while s<= 0;
    s--;
}
void signal(s){
	s++;
}

s값에 접근하는 프로세스 1개 - binary semaphore
s값에 접근하는 프로세스 n개 - counting semaphore

• 작업 순서를 정할 수 있다 (왜> P1이 s를 반납하고 나와야만 P2가 진입할 수 있기 때문)
• s값이 음수 일 때 대기하고 있는 프로세스의 수 = |s값|
• busy waiting 존재 (s값이 음수이거나 0이면 while문에서 계속 돈다) => CPU 자원 낭비
• busy waiting 해결 -> block and wakeup ready queue에서 대기한다.
  - Ready queue에 들어가 스케줄링 알고리즘에 따라 선택되어 critical section에 진입한다. (context switching overhead 존재)
• 따라서 Critical region이 짧으면 busywating <-> 길면 Block and wakeup
• semaphore 문제점
  - deadlock & starvation
  • Priority inversion

Deadlock & Starvation

deadlock
프로세스가 서로의 signal을 기다리게 되면서 모두 무한정 대기 (둘이 서로가 가진 자원을 wait하게됨 + 보유한 자원 비선점형으로 놓지않음 + 사이클 존재 + 상호배제 => deadlock)

starvation
block and wakeup 방식에서 ready queue에서 대기하고 있는 프로세스 중 하나를 선택하는 스케줄링 과정에서 선택되지 못하면 실행되지 못하는 프로세스가 생김 (starvation은 LIFO(얘는 자료구조지 스케줄링 알고리즘이 아님)에서만 발생하는게 아니다, 스케줄링 알고리즘으로 인하여 발생하는 것이지 스케줄링 알고리즘 (FIFO는 FCFS구조이지만 FIFO = 큐(자료구조)는 Priority(우선순위큐)에서 쓰인다.))

Priority Inversion(우선순위 역전)(예전에 잡스운체 강조 포인트)

우선순위 역전 현상, 우선 순위가 낮은 프로세스 때문에 우선순위가 높은 프로세스가 실헹되지 않는 현상 (우선 순위 1 제일 높고 4가 제일 낮음(가정), 예를 들어 우선순위 4인 프로세스 B가 수행중에 Semaphore 0으로 돌리고 CS에 들어감, 이때 우선순위 1인 프로세스가 Critical Section에 들어가려하지만 while문에 의해 busywaiting하는 상황 그럼 B가 나올때 까지 A는 못들어가고 중간에 우선순위 2인 프로세스로 context switching되어 A는 여전히 CS에 들어가지 못하는 상황)

세마포어나 뮤텍스는 사용을 잘못할 경우 에러가 발생할 수 있다. 모니터는 프로그램이 제공하는 기능으로 자바에서 심플한 동기화 툴로 알려져있다.
다음시간에..