[OS] Semaphore(쎄마포어)

이번 블로그는 앞 주제와 이어집니다!@!

https://sehseh.tistory.com/16

[OS] Critical Section Problem, 쓰레드간 협력

 

그럼 이제 쎄마포어 관점에서 Critical Section Problem을 확인해보자

이전 블로그에서 다뤘던 Critical Section Problem은 둘 이상의 프로세스나 스레드가 공유 자원에 동시 접근할 때 발생하는 것을 방지하는 방법이다. 이 문제를 방지하여 개별적인 연산을 수행하는 것을 Synchornization이라하고 공유 변수를 조작하는 구문은 한번에 하나의 프로세스만 실행하도록하여 임계구역을 정한다. Synchronization을 구현한 방법이 쎄마포어이다.

 

쎄마포어는 공유자원(s)와 2개의 atomic 연산을 지원한다 (P/wait && V/signal)

s: 현재 임계구역에 들어갈 수 있는 자원 수 

• 쎄마포어 1으로 초기화
• 임계구역 들어가기 전 쓰레드는 P(semaphore)나 wait(semaphore) call

s = s – 1
	if(s<0)
	// wait를 호출한 스레드를 block 상태
	else
	// wait를 호출한 스레드를 임계구역으로

 

• 임계구역에서 나오고 나선 V(semaphore)나 signal(semaphore) call

s = s + 1
if(s<=0) //리소스 대기중인 인원이 있음
	// 우선순위 학인해서 wake up

 

 

쎄마포어 value

• positive semaphore : 임계 구역에 들어갈 수 있는 쓰레드 수, waiting X
• negative semaphore : block 상태의 스레드 수
• Binary semaphore : 임계구역 한번에 한 스레드
• Counting semaphore: 초기값이 1보다 큰 경우

 

쎄마포어 구현 예시

 

fullSlot은 머신에 콜라가 들어있는 칸의 수를 말하고 fullSlot이 1 이상일때만 콜라를 뽑을 수 있다. emptySlot은 콜라를 추가로 넣을 수 있는 공간을 말하며 1 이상이어야 콜라를 넣을 수 있다. mutex는 자판기에 동시에 한명만 접근할 수 있도록 Lock하는 역할이다

DeliveryPerson은 emptySlot이 emptySlot에 대해 wait call하면 음수라면 대기하고 0이거나 양수라면 mutex에 대해 wait call

mutex를 획득하면 콜라를 하나 넣고 signall call로 임계구역을 빠져나온다. 그리고 fullSlot에 대해 signal call을 하여 fullSlot을 하나 채움을 알리고 소비자가 콜라를 꺼낼 수 있게 알린다. 

 

쎄마포어 구현

1. busy-wating

• 공유 변수 s의 값을 두고 P(wait), V(signal) 두 원자적 연산으로 임계구역 접근을 제어

하지만 s<=0조건에서 대기 중인 프로세스는 while로 루플를 돌며 계속 조건 검사. 이 상태에서 CPU를 점유한채 아무 일도 하지 않아 CPU 낭비 ㅜㅜ... block된 레디큐가 없다

 

2. disabling interrupt

• 임계구역 들어가기 직전에 인터럽트를 막아 스케줄러가 CPU 제어권을 빼앗지 못하게

한 CPU에서 인터럽트를 꺼도 다른 CPU에서는 영향이 없으므로 멀티프로세서 지원 불가 또한 위와 마찬가지로 block된 레디큐가 존재하지 않고 여전히 busy wating으로 CPU 시간 낭비 

 

3. test$set

 

• RMW(read-modify-write) 구조로 atomic(원자적으로)하게 메모리에서 read하고 새로운 값으로 바꿔서(lock 획득)

“lk”의 초기값은 0

• 만약 lock 해제되면(lk=0)
  tes&set이 lk 값(0)을 읽고 1로 설정하고 0을 반환한다 이때 loop test에 실패하면 (반환값이 0이 아니면) 락 획득
  loop test fails, meaning lock is now busy
• 만약 lock을 건다면(lk=1)
  루프테스트는 다른 사람이 release할때까지 계속됨, 반복루프에서 대기
  test&set이 lk 값(1)을 읽고 1로 설정하고 1을 반환한다

또한 위와 마찬가지로 block된 레디큐가 존재하지 않고 여전히 busy wating으로 CPU 시간 낭비 
그러나 multiprocessor가 가능하다 

 

쎄마포어 in Nachos

https://sehseh.tistory.com/4

[OS] NachOS 환경 설정

 

Semaphores:

• Semaphore::Semaphore( ) — creates a semaphore with specified name & value
• Semaphore::P( ) — semaphore wait
• Semaphore::V( ) — semaphore signal

Locks:

• Lock::Acquire( )
• Lock::Release( )

Condition variables:

• Condition::Wait( )— 기다림
• Condition::Signal( ) — 대기중인 스래드 깨움

 

void
 Semaphore::P()
 {
    IntStatus oldLevel = interrupt->
		 SetLevel(IntOff); // disable interrupts
    while (value == 0) { // sema not avail
		 queue-> // so go to sleep
			 Append((void *)currentThread);
			currentThread->Sleep();
  }
    value--; // semaphore available,
						// consume its value
 (void) interrupt-> // re-enable interrupts
		SetLevel(oldLevel);
 }
 
 
 void
 Semaphore::V()
 {
    Thread *thread;
    IntStatus oldLevel = interrupt->
		 SetLevel(IntOff);
		 thread = (Thread *)queue->Remove();
		  if (thread != NULL) // make thread ready,
													// consuming the V immediately
			 scheduler->ReadyToRun(thread);
		   value++;
			 (void) interrupt->SetLevel(oldLevel);
 }