본문 바로가기

별걸다하는 IT/운영체제 OS

[운영체제]세마포어(semaphore) 완전 쉬운 이해! wait(), signal(), 이진, 계수형

반응형

운영체제 완전 정복 목차~!

semaphore의 유래~! 세마포어란?

Semaphore는 깃발이라는 뜻입니다.

옛날에는 기찻길에서 깃발 표식으로 파란색이 걸려있으면 지나가도 되고 빨간색이 걸려있으면 섰다가 다른 기차가 지나가면 지나가게끔 하는 용도로 깃발을 사용했어요 이 깃발을 semaphore라고 부릅니다. 

 

즉 저 겹치는 기찻길 부분이 두 기차가 공유하는 critical section인거죠! 저 기찻길에서도 critical section을 지나가도 된다 안된다를 알려주는 단어로 쓰인거랍니다.

 

lock의 경우는, 0 또는 1이였죠! 

그런데 세마포어는 shared data의 개수를 의미합니다. 그래서 0 또는 1 또는 2 또는.. 등이 될 수 있어요. 이 그림에서는 공유자원이 한 개이므로 (저 겹쳐지는 기찻길!) semaphore의 값은 0 또는 1일거예요. 어떤 기차가 지나가고 있으면 내가 사용할 수 없으니 0이고 비어있으면 1의 값을 가지게 되는거죠. (이렇게 0 또는 1의 값만 갖는 세마포어를 binary semaphore라고 합니다)

 

위처럼 누가 쓰면 0이 되고 안쓰면 1이 되는, 즉 0과 1만 갖는 binary semaphore는 Lock하고 작동 원리가 반대예요. 0하고 1이 왔다갔다 하는 것은 똑같지만, 세마포어는 초기화가 1이고 누가 사용하면 0인데, Lock은 누가 사용했을 경우 1이니까요!

0과 1뿐만 아니라,2 ,3, 4 등의 값들 또한 가질 수 있는, 즉 도메인이 제한 없는 counting semaphore의 예시를 하나 들어볼까요?

 

자 서버에 프린터가 다섯 대가 물려있어요. 사용자가 프린트를 사용하려고 서버에 요청합니다. 그러면 공유자원 즉 프린터가 5개가 있으니까 5로 설정이 되는거예요. 그리고 프린터를 사용자가 사용할때마다 하나씩 감소하는겁니다. 그러다가 사용할 프린터가 없어지면 세마포어는 0이되고 누군가가 프린터를 다 쓰고 반환하면 세마포어가 다시 1이 증가하겠죠? 이런식으로 생각하면 됩니다. 다시 말하지만 여기서 세마포어는 단순히 변수예요. 공유자원의 개수를 나타내는 변수요!

 

Counting semaphores can be used to control access to a given resource consisting of a finite number of instances. The semaphore is initialized to the number of resources available. 

카운팅 세마포어는 자원이 몇 개로 한정되었을 때, 이 자원에 접근하는 걸 컨트롤 하는데 사용됩니다. 그리고 세마포어는 사용가능한 자원의 개수로 초기화됩니다.

 

semaphore 접근 함수- wait(), signal()

그럼 자원을 어떻게 사용하고 반납하나요? 이를 위해 제공되는 함수가 wait()하고 signal()입니다.

별 거 아니고 그냥 사용하면 -1이 되고 반납할 때 +1 해주는 함수예요. 다만 세마포어 자체가 공유자원이 되면 안되니까 쪼개지지 않는 함수로 구성됩니다. shared data를 보호하려고 지금 세마포어를 사용하는데 세마포어 자체가 shared data가 되면 말이 안되니까요 ㅎㅎ 두 줄로 구성되지 않고 무조건 끼어들 틈이 없게 atomic하게! 한 번에 수행시켜줘야 한다는 것. (앞에 포스팅을 차근차근 다 읽어봤으면 이해할 수 있을 것이라고 생각해요!) 따라서 전 시간에 구현했던 spin lock하고 interrupt disable/enable하는 방법 가지고 세마포어를 구현해줍니다. 

 

A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() and signal(). The wait() operation was originally termed P (from the Dutch probern, "to test"); signal() was originally called V (from verhogen, "to increment").

세마포어 변수 S는 결국 초기화를 제외하면 atomic operation인 wait()와 signal()로만 접근 가능한 정수 타입의 변수예요. 이 두 함수는 p또는 v라고 많이 얘기를 하기도 합니다. (p는 네덜란드어 "테스트하다"라는 단어의 probern에서 유래됐고 signal은 "증가하다"라는 뜻의 verhogen 단어에서 유래됐대요) 근데 이게 미국으로 건너가면서 영어로 표현할 때에는 -1하는 함수를 wait, +1하는 함수로 signal로 불리게 됐어요.

 

shared data를 사용하려고 봤는데 shared data가 없어! 그럼 기다려야하니까 이 함수의 이름을 wait이라고 지었고, 

지금 비어있는 shared data가 있다! 그럼 안기다리고 사용하는거죠 (-1)

그런데 만약 semaphore의 값이 0이야. 그러면 남은게 하나도 없다는 뜻이니까 기다려야한다고 해서 어쨋든 이름이 wait입니다.

 

다 쓰고 나서는 세마포어 값을 +1시켜주면 돼죠?! 내가 지금 다 쓴 이 shared data를 누군가 쓰려고 기다릴 수 있어요. 그래서 개한테 나 다썼으니 너 써! 신호를 보내줘야 하겠죠? 그래서 이 함수가 signal()!

 

 

재밌는 그림이 하나 있네요

앞의 설명을 다 읽었으면 

이 그림을 이해하는 것은 어렵지 않을 거예요!

간단하게 재미로 보고 넘어갑시다. ㅎㅎ

 

 

 

 

 

 

 

 

 

 

세마포어 구현, wait과 signal 함수의 구현

이 방법이 어플리케이션 프로세스나 스레드가 사용할 수 있는 방법입니다. 구현은 어떻게 할까요?

 

 

전체적인 구조는

들어갈 때 wait, 나갈 때 signal이였죠? 

 

그러므로 그림을 보면 critical section에 들직전에 wait로 세마포어 1 감소, critical section바로 이후에 signal을 해줘서 세마포어 값을 증가해줍니다. 

 

당연히 시작 전에는 세마포어를 초기화해줍시다. 여기서 세마포어를 구조체로 구현해줬어요. 세마포어를 의미하는 변수에 기다리는 프로세스를 관리하기 위해 프로세스 리스트를 플러스로 가지고 있습니다.

 

typedef struct
{
  int value;
  struct process *list;
} semaphore;

여기서 mutex는 단순히 변수 이름입니다. mutual exclusion 상호배제 약자로 쓰인거예요. S로 해도 되고, a로 해도 되고 변수 이름은 뭘로 하든 상관 없습니다. 책에서는 mutex라고 그냥 이름을 지어준거예요. (괜시리 헷갈리게 ㅎㅎㅎ) 저는 헷갈리니까 세마포어를 S라고 이름을 짓겠습니다.

wait(S) : if(S.value == 0){ // 공유자원을 남들이 다 쓰고 있어서 0개이면
    add this process to S.list; // 기다려야 하니까 프로세스를 wait상태로 놓고 큐(S.list)에 집어 넣습니다.
    block; //기다리기 못 들어가~~ 입장 거부!
}
lock(lock); // 세마포어자체가 공유자원이 되니까 lock처리 해주기 
S.value--; //총 자원개수에서 하나를 빼기!
unlock(lock); // lock 해제

//////////////////////////////////
wait(S) : //이번 wait는 -1까지 나올 수 있어요 
 lock(lock); // 세마포어자체가 공유자원이 되니까 lock처리 해주기 
 S.value--; //일단 쓰려고 하니까 일단 자원을 하나 빼. 다 사용중이라 0개이면 마이너스가 되겠죠?
 unlock(lock); // lock 해제
 if(S.value<0){ //마이너스 일 경우 0개였다는거니까
    block this process // 못들어가게 하기
    add this process to S.list //기다리는 중이니 큐에 집어넣어줍니다.
 }

이번에는 signal함수를 구현해볼게요 

signal(S): lock(lock); //세마포어 동시 접근 막기
  S.value++; //안전해졌으면 세마포어 값 하나 증가! 자원 해제하는거니까
  unlock(lock); //완료했으면 해제
  if (S.value>0){ //만약 공유 자원이 최소 하나 이상 있으면
    remove a process P from S.list; // 아까 대기에서 기다리고 있던 P 차례가 왔으니까
    //대기 리스트에서 제거해준 후
    wakeup(P); //P보고 이제 너 써 라고 불러줍니다. 
  }
///////////////////////////////
signal(S): lock(lock); //세마포어 동시 접근 막기
  S.value++; //안전해졌으면 세마포어 값 하나 증가! 자원 해제하는거니까
  unlock(lock); //완료했으면 해제
  if (S.value = 0){ //-1이 기준이으까 얘는 0이 되겠죠
    remove a process P from S.list; 
    wakeup(P);
 }

wakeup(P)는 P프로세스를 ready queue에다가 집어 넣는 일을 말해요.

lock과 unlock을 value++에 해준 이유?

사실 value ++;이나 value--;는 atomic한 명령이 아닙니다. (여기서 atomic한 명령이라는건 컴퓨터 가장 낮은 단일 언어일 때 한 사이클에 이루어지는 명령을 말해요 쉽게 말해 어셈블리어 명령어 생각하면 됩니다.)

value++; --> 한 줄 이라고 생각해서 한 번에 처리되는 명령이라고 생각하기 쉬운데 사실 이 명령은 세 개의 명령으로 이루어졌여요.

count++처럼 하나 증가시키는 이 명령어는 사실,

 실메 메모리에 있는 변수 값을 레지스터에다가 넣고, 레지스터를 1 증가시킨 후, 

다시 이 변수에다가 집어넣어주는 

3 절차의 명령으로 구성되어 있어요. 

 

count--도 마찬가지입니다.

 

즉, atomic instruction이 아니다? = 이 사이에서 얼마든지 인터럽트가 발생 될 가능성이 있다 = context switching이 발생할 수 있다. = 동시 접근을 허용할 수도 있다. 공유자원 충돌 문제가 날 수 있다는거예요!

따라서 우리는 value++;이나 value--; 연산을 하기 전에 lock()처리를 해준 겁니다. single CPU일 때 사용하는 interrupt disable, enable 방법으로 lock처리를 해줄 수 있겠죠. 이 value++; (3줄 짜리 명령어)가 실행되는 동안에는 잠깐 인터럽트가 밀려도 큰 지장이 없겠죠! 그래서 이를 이용한 lock과 unlock을 테두리에 둘러서 발생할 수 있는 문제를 막아줍니다. 

multiple CPU일 때는 test and set으로 구현해도 좋아요. 명령어 3개 실행되는 동안 busy waiting하는 건 CPU를 크게 낭비하는 것이 아니니까요. 즉 wait과 signal안에 있는 lock과 unlock은 운영체제가 세마포어를 구현하기 위해 짧은 critical section 구간에만 사용하는 방법입니다.

 

Furthermore, we have limited busy waiting to the critical sections of the wait() and signal() operations, and these sections are short (if properly coded, they should be no more than about ten instructions). 

wait과 signal에 있는 임계영역에 제한된 busy waiting이 발생하지만 이 구역은 짧습니다. (만약 제대로 코딩했다면 10개 명령어보다 많진 않을 테니까요) 

Thus, the critical section is almost never occupied, and busy waiting occurs rarely, and then for only a short time. 

따라서 busy waiting은 거의 발생하지 않고 발생하더라도 진짜 짧은 시간동안만 발생해요. (당연하죠? 세 개 명령어 수행하는 거 기다리는데 걸려봤자 얼마나 기다리겠어요) 즉 임계영역은 거의 차지되지 않습니다.

An entirely different situation exists with application programs whose critical sections may be long (minutes or even hours) or may almost always be occupied. In such cases, busy waiting is extremely inefficient

근데 만약 어플리케이션 프로그램의 임계영역이 길거나 맨날 차지되고 있는 경우는 완전 다른 상황입니다. busy waiting을 사용하는 방법은 극대로 비효율적이죠 

 

반응형
  • 굿굿 2019.11.25 19:02

    설명을 정말 쉽게 써놓으셨어요 감사드립니다. 마지막 부분에서 busy waiting 방식 보다 개선된 방식은 어떤게 있을까요??

  • 2020.04.20 16:45

    비밀댓글입니다

    • IT 양햄찌(jhnyang) 2020.04.20 17:35 신고

      세마포어는 공유자원의 개수가 1개가 아닌 다수일 수 있기 때문에 1이 아닌 그 외의 양수 값이 올 수 있습니다. 음수가 되면 자원을 사용하려고 기다리고 있는 프로세스들이 사용할 수가 없겠죠. 사실 어떻게 제어하는지 원리만 안다면 범위를 어떻게 잡는가는 개발자의 권한입니다.

  • 2020.04.27 14:32

    비밀댓글입니다

    • IT 양햄찌(jhnyang) 2020.04.27 14:56 신고

      안녕하세요. 주인장입니다. mutual exclusion은 상호배제로 남들과 자원을 절대 공유하지 않는걸 말합니다. (mutual exclusion: https://jhnyang.tistory.com/3 참조)
      'mutual exclusion을 세마포어로 구현 = mutex를 세마포어로 구현'이 되므로 초기값을 1로 세팅해줘야 하는 겁니다. 세마포어는 공유자원이 한개가 아니라 여러개가 될 수 있지만 뮤텍스는 공유자원이 단 하나라 남들과 공유하지 않기 때문이죠.

  • tovantablack 2020.08.17 08:32 신고

    와 설명 존잼,, bb

  • 학생 2020.12.22 15:27

    여기 포스팅해주신 방법에 무한정 대기상태가 없다는 것을 증명해주실 수 있으신가요? 처음 읽어본 거라 머릿속에서 잘 안 그려지네요 ㅎㅎ

    • IT 양햄찌(jhnyang) 2020.12.28 01:44 신고

      무한정 대기 상태가 없다는 말은 한 프로세스만 계속 임계영역(cs)에 들어가지 않고 다른 프로세스 또한 모두 기회를 가질 있게 하는걸 말해요. 마지막 남은 한 자원을 한 프로세스(A)가 차지해 임계영역(cs)에 들어가 수행되고 있다고 합시다. 그 와중에 다른 프로세스(B)가 요청을 하면 wait에 걸리고 list에 대기하게 되죠. 이 프로세스(B)는 무한정 대기 하지 않고 들어가 있는 프로세스 중 하나(A)라도 cs가 끝나고 signal이 수행되는 순간 리스트로부터 불러집니다. 무한정으로 도는 while의 상태는 다른 프로세스에 의해 결정됩니다. 그리고 어떤 프로세스라도 동시에 요청이 있거나 그런거 아니면 방해 없이 cs를 차지해서 수행할 수 있죠. 무한정대기가 없다는 말은 한 프로세스가 계속 cs를 차지해 다른프로세스가 기회를 얻지 못하면 안되고, 어떠한 프로세스도 자원을 차지하려고 하지 않는 상태에서 어떤 프로세스가 자원을 차지하려고 할 때 그 프로세스는 방해받지 말아야 하는걸 뜻합니다. 그러므로 세마포어는 무한정대기가 없습니다. 연말이라 답변이 늦었네요 이해하는데 도움이 되셨음 좋겠습니다.

  • 🧚‍♀️ 욘 2021.04.06 17:47 신고

    쉽고 명확한 설명 감사합니다.

  • 지나가는대학생 2021.04.25 01:01

    이해하기 쉽게 잘 설명해주시네요...사랑합니다..ㅠ

  • 교수님이해가안가요 2021.05.25 01:35

    와 진짜 진짜 너무 갑사합니다 .... 답답해 죽는 줄 알았어요 복받으세요 ㅠㅠㅠㅠㅠㅠ

  • 2021.06.01 00:46

    비밀댓글입니다

  • 대학생 2021.09.18 06:26

    감사합니다!! 진짜 너무 잘 읽었어요!! 제일 잘 이해되게 설명해 주셔서 여기서 드디어 이해하고 갑니다ㅜㅜ 복받으세요!