SUBJECT:   semaphore란 ? 

Description :

o 세마포어 (semaphore)란 (1) ?
  - 동기화의 일반적인 방법인 세마포어 방법은 세마포어라는 정수 변수 
   (integer variable), 프로세스 대기열(process waiting queue), 
    P와 V의 두 명령으로 구성된다. 초기 상태의 변수값은 자원의 수와 같으며
    대기열은 비어 있다. P명령은 변수의 값을 하나 줄인 후, 
    변수의 값이 0보다 작으면 프로세스를 대기열로 집어 넣는다. 
    반대로 0보다 크면 그 프로세스는 계속 진행된다. 
    V명령은 변수의 값을 하나 증가시킨다.  그 결과가 0보다 크면 프로세스는 
    계속되며 0보다 작으면 대기열의 프로세스 하나를 준비 상태로 만들고, 
    프로세스의 수행은 계속된다.  결국 변수의 값은 음수일 경우는 대기 중인 
    프로세스의 수를 나타내며, 양수이면 사용 가능한 자원의 수를 가리킨다.  
    위에서 동기화란 프로세스의 실행을 시간에 따라 순서적으로 처리하는 것을 
    동기화라 한다.

o 세마포어 (semaphore)란 (2) ?
  - 다익스트라(E.J.Dijkstra)가 제안한 동시에 정보를 공유하여 수행되는 
    두 개 이상의 프로그램이나 프로세스에서 활동(activity)의 위치(coordination)를
    설정해 주는 데 사용되는 동기화를 위한 기본 조작. 이는 두개 이상의 
    프로세스에 의해 공유되는 고유변수로 정의되는데, 보통의 방법으로는 
    다룰 수 없고 항상 P와 V라는 연산을 통해서만 액세스할 수 있다.  
    세마포어 sem이란 다음과 같은 연산이 허용된 정수형 변수를 말한다. 
   (P와 V란 이름은 wait와 signal이란 말의 네덜란드어에서 나온것으로 
    이때 signal이란 물론 UNIX의 signal호출과는 다르다.) 
    두 연산은 모두 원자화되어야 한다. 즉 sem을 변경할수 있는 프로세스는 
    한 순간에 오직 하나 뿐이다. 

    ------------------------------------------------------------------------------------------------
    | 컴퓨터가 여러 프로그램을 동시에 수행하는 다중 프로그래밍 시스템에서는 프로세스들간의 상호    |
    | 배제와 동기화를 위한 기본적인 연산이 필요하다. 세마포어는 다익스트라가 제안한 프로세스       |
    | 동기화를 위한 구조로, 이는 여러 프로세스들에 의해 공유되는 변수로 정의된다.                  |
    | 그런데 이 변수는 보통의 방법으로는 액세스할 수 없고 오직 P와 V라는 연산으로만 다룰 수 있다.  |
    | P와 V연산의 정의는 다음과 같다.                                                              |
    |                                                                                              |
    |              procedure P(S)   --> 최초 S값은 1임                                             |
    |                  while S=0 do wait  --> S가 0면 1이 될때까지 기다려야 함                     |
    |                  S := S-1   --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함         |
    |              end P                                                                           |
    |                                                                                              |
    |              procedure V(S) --> 현재상태는 S가 0임                                           |
    |                  S := S+1   --> S를 1로 원위치시켜 해제하는 과정. 이제는 다른 프로세스가     |
    |              end V              들어 올수 있음                                               |
    |                                                                                              |
    | P와 V는 쪼갤수 없는 단일 연산이다.                                                           |
    | 즉 한 프로세스가 P나 V를 수행하고 있는 동안에는 프로세스가 인터럽트를 당하지 않는다.         |
    | 이제 P와 V를 사용하면 다음과 같이 위험지역(cirtical section)에 대한 상호배제를 구현할수 있다.|  
    |                                                                                              |
    |              P(S);                                                                           |
    |              -----------------                                                               |
    |              | 위 험 지 역   |                                                               |
    |              -----------------                                                               |
    |              V(S);                                                                           |
    |                                                                                              |
    | 최초에 S의 값은 1이다. 위와 같은 위험지역을 포함하는 두개의 프로세스 A와 B가 있다고 하자.    |
    | A와 B는 서로 독립적으로 수행되지만, 두 프로세스가 동시에 위험 지역으로 들어가서는 안된다.    |
    | 위와 같이 세마포어를 사용하면 P(S)를 먼저 수행하는 프로세스가 S를 0으로 해놓고 위험지역에    |
    | 들어가므로 나중에 도착하는 프로세스는 P에서 더이상 진행되지 못하고 기다리게 된다.            |
    | 먼저 들어갔던 프로세스가 V(S)를 해주어야 비로서 P(S)에서 기다리던 프로세스가 위험지역에      |
    | 들어갈 수 있고 따라서 상호배제가  실현된다.                                                  |
    | 위의 예는 이진 세마포어 (binary semaphore)로, 단지 하나의 프로세스만이 위험지역에 들어갈 수  |
    | 있도록 한다. 한편 S의 초기값을 N으로 하면 최대 N개의 프로세스가 P(S)를 통과할 수 있게        |
    | 되는데 이러한 경우에는 계수 세마포어 (counting semaphore)라 하며 자원 할당에 사용한다.       |
    ------------------------------------------------------------------------------------------------ 

    UNIX 시스템 V에서 구현된 세마포어는 이러한 개념에 기초했지만 보다 
    일반적인(그리고 아마도 보다 복잡한)기능을 제공한다. 
    우선 semget과 semctl을 살펴보자.
    <사용법>
         #include 
         #include 
         #include 
    
         key_t key;
         int sem_id, nsems, permflags, command;
         int retval, sem_num;
         union semun {
               int val;
               struct semid_ds *stat;
               ushort *array;
               } ctl_arg;
                .
                .
                .
         sem_id = semget(key, nsems, perflags);
         retval = semctl(sem_id, sem_num, command, ctl_arg);

     semget 호출은 msgget(get message queue)과 유사하다. 인수 nsems는 
     세마포어 집합에 필요한 세마포어의 갯수를 나타낸다. 
     따라서 UNIX 세마포어 연산은 세마포어 하나만이 아니라 한 집합 전체를
     다루게 된다. 이로 인해서 나머지 세마포어 루틴에 대한 인터페이스가 
     복잡해진다.
     semget호출이 성공하면 세마포어 집합 식별자라는 메시지 큐 식별자와 유사한 
     역할을 하는 것이 돌아온다. C 언어의 관습을 따라서 세마포어 집합에 대한 
     첨자는 0부터 nsems-1까지 있을 수 있다.
     집합 내의 각 세마포어는 다음과 같은 값들을 갖게 된다.
       . semval : 세마포어의 값으로서 항상 양수가 지정된다. 
                  여기에 값을 새로 지정하려면 반드시 세마포어 시스템 호출을 
                  통해야하며 프로그램에서 일반 자료형의 변수와 같이 직접
                  접근 할 수는 없다.
       . sempid : 세마포어에 접근했던 최근의 프로세스의 프로세스 식별번호이다.
       . semncnt : 세마포어의 값이 현재보다 증가하기를 기다리는 프로세스의 갯수
       . semzcnt : 세마포어의 값이 0으로 되기까지 기다리는 프로세스의 갯수
     정의에서 알 수 있듯이 함수 semctl은 msgctl보다 훨씬 복잡하다. 
     sem_id는 유효한 세마포어 식별자라야 한다. 
     command는 msgctl에서와 같이 수행해야 할 정확한 기능을 명시한다. 
     이 기능에는 세가지 유형이 있다. IPC_STAT와 같은 표준 IPC기능,
     단일 세마포어만을 다루는 기능, 세마포어의 전체를 다루는 기능이 그것이다. 
     가능한 모든 기능을 다음과 같이 정리하였다.
                    
                   semctl(semaphore control operations) 기능 코드
   -----------------------------------------------------------------------------
         표준 IPC기능 (semid_ds구조는 sem.h에 정의되어 있다.)
   ----------------------------------------------------------------------------- 
         IPC_STAT  상태정보를 ctl_arg.stat에 저장한다.
         IPC_SET   ctl_arg.stat에 저장된 형태로 소유권과 사용 허가권을 지정한다.
         IPC_RMID  시스템에서 해당 세마포어의 집합을 삭제한다.
   ----------------------------------------------------------------------------- 
         단일 세마포어 연산 (이들은 retval에게 넘어온 값 sem_unm을 사용한다.)
   ----------------------------------------------------------------------------- 
         GETVAL    세마포어의 값 semval을 돌려준다.
         SETVAL    세마포어 값을 ctl_arg.val로 지정한다.
         GETPID    sempid의 값을 돌려준다.
         GETNCNT   semncnt를 돌려준다.
         GETZCNT   semzcnt를 돌려준다.
   ----------------------------------------------------------------------------- 
         전체 세마포어 연산 
   ----------------------------------------------------------------------------- 
         GETALL    모든 senvals의 값을 ctl_arg.array에 저장한다.
         SETALL    ctl_arg.array의 값을 사용하여 모든 semvals값을 지정한다.
   ----------------------------------------------------------------------------- 
    
      sem_num 인수는 semctl의 단일 세마포어 기능에서 특정 세마포어를 지정해준다.
      마지막 인수인 ctl_arg는 세가지 구성 요소의 결합이다. 
      이들 구성 요소들은 각각 semctl의 세가지 기능에 대응한다.
      semctl은 세마포어의 초기값을 지정할 때 요긴하게 사용된다. 
      이 기능은 semget에는 없음에 주의하라.
      따라서 semget과 semctl은 두개 모두 있어야 한다.
      다음에 예로서 제시하는 함수는 프로그램이 단일 세마포어를 생성할때나 
      이에 대한 세마포어 집합 식별자를 얻고자 할 때 사용될 수 있다. 
      세마포어가 생성되는 경우에는 semctl을 사용하여 초기값을 부여하게 된다.

   /* initsem  -- semaphore initialization */
   #include "pv.h"
    initsem(semkey)
    key_t semkey;
    {
          int status = 0, semid ;
          if ((semid = semget(semkey, 1, SEMPERM|IPC_CREAT|IPC_EXCL)) == -1) {
               if (errno == EEXIST)
                   semid = semget(semkey, 1, 0);
          }else   /* if created... */
               status = semctl(semid, 0, SETVAL, 1);

        if ((semid == -1 || status == -1) {
             perror("initsem failed");
             return (-1);
        }else
             return semid;    /* all okay  */
     }  

  include 화일 pv.h는 다음과 같다.
 
    /* semaphore example header file */
    #include 
    #include 
    #include 
    #include 
    extern int errno;
    #define SEMPERM 0600
    #define TRUE 1
    #define FALSE 0 

   세마포어 연산 : semop 호출
 - semop 호출 semop은 기본적인 세마포어 연산을 실제로 수행하는 시스템호출이다.
   이때 semop은 메뉴얼의 항목이 아니라 실제 함수 이름이다.
   사용법 
      #include 
      #include 
      #include 
      int retval, sem_id;
      struct sembuf op_array[SOMEVALUE];
               .
               .
      retval = semop(sem_id, op_array, SOMEVALUE);

   sem_id는 세마포어 집합 식별자로서 이전에 semget호출을 통해 값이 지정되어야 
   한다. op_array는 sembuf구조의 배열로서 sembuf구조는 sem.h에 정의되어 있다.
   SOMEVALUE는 임의의 정수형 상수이다. 
   각각의 sembuf구조 변수는 세마포어에 대해 수행할 연산을 지정한다.
   다시 강조하거니와 semop함수가 세마포어 집합에 대해 수행하는 일련의 연산들은 
   모두 원자화 되어야 한다. 즉, 그중의 한 연산이라도 수행할 수 없다면 전체 연산
   이 모두 수행되지 말아야 한다. 이 경우에는 특별히 명시되지 않는한, 
   모든 연산이 한번에 수행될수 있을때까지 프로세스의 수행이 중지된다.
   sembuf구조를 좀더 자세히 보면 다음과 같이 구성되어 있다.
  
      --------------------------------------------------------------------
      |     struct sembuf {                                              |
      |     short   sem_num;        /* semaphore # */                    |
      |     short   sem_op;         /* semaphore operation */            |
      |     short   sem_flg;        /* operation flags */                |
      --------------------------------------------------------------------
 
   sem_num는 집합 내의 세마포어에 대한 첨자를 저장한다. 만약 집합의 원소가 
   하나뿐이라면 sem_num의 값은 0이어야 한다.  sem_op는 함수 semop이 수행해야 
   하는 기능을 정수로서 나타낸다.
   여기에는 세가지 경우가 있다.

   경우 1 : sem_op가 음수일때

   이 경우에는 앞서 소개했듯이 일반적인 세마포어 명령 P()와 같이 수행된다. 
   이를 의사 코드(pseudo-code)로 나타내면 다음과 같다 
  (ABS는 변수의 절대값을 나타낸다)
 
        if (semval >= ABS(sem_op)){
             set semval to semval-ABS(sem_op)
        } else {
             if ((sem_flg&IPC_NOWAIT))
                     return-1 immediately
             else{
                    wait until semval reaches or exceeds
                    ABS(sem_op), then subtract
                    ABS(sem_op) as above
                  }
           }
   기본 개념은 함수 semop에서 sem_num이 가리키는 세마포어의 값 semval을 
   조사하는 것이다.
   semval의 값이 충분히 크다면 즉시 하나 감소시킨다. 아니면 semval이 충분히 
   커질 때까지 프로세스의 수행을 중단시킨다. 그러나 sem_flg의 IPC_NOWAIT
   플래그의 값이 1로 되어 있으면 sem_op은 즉시 -1을 되돌려주고 errono값을 
   EAGAIN으로 한다.

   경우 2 : sem_op이 양수일 때

   이때는 보통의 V()연산과 유사하다. 즉 sem_op의 값을 해당 semval에 더해준다.
   이때 해당 세마포어의 값이 증가하기를 기다리는 프로세스들이 깨어나게 된다.
    
   경우 3 : sem_op이 0일때

   이 경우는 semval을 변환시키는 것이 아니라 값이 0이 될때까지 기다린다.
   semval이 0이 아니고 sem_flg의 IPC_NOWAIT가 1인 경우에 semop는 즉시 오류 
   값을 돌려주게 된다.
         
   SEM_UNDO 플래그

   - 이것은 sembuf구조의 구성요소 sem_flg에 있는 플래그의 하나이다. 
     이는 프로세스의 수행이 끝났을 때 시스템이 수행된 연산을 자동적으로 
     취소하도록 지시한다. 수행된 일련의 연산을 추적하기 위하여 시스템은 
     세마포어에 semadj라는 정수를 대응시킨다. 
     이때 semadj변수는 프로세스마다 할당되어야 함에 주의해라.  
     따라서 서로 다른 프로세서는 동일한 세마포어에 대해 독립적인 semadj값을 
     유지하게 된다. SEM_UNDO의 값을 1로 하고서 semop연산을 수행하면 
     semadj값에서 sem_num값을 뺀다.
     이때 sem_num의 부호가 중요한데 이는 sem_num의 값이 양수인가 음수인가에 
     따라 semadj의 값이 감소하거나 증가하기 때문이다. 프로세스의 수행이 끝나면 
     시스템은 semadj값을 해당 세마포어에 더해줌으로써 지금까지의 모든 
     semop호출 효과를 상쇄시킨다. 일반적으로 볼때 프로세스가 지정한 값이 
     해당 프로세스의 종료 후에도 효력을 갖지 않는다면 SEM_UNDO가 사용되어야만 
     한다.

   세마포어의 예

   - 이제 initsem루틴으로 시작한 예를 완성해 보자. 여기서는 전통적인 세마포어 
     연산을 P()와 V()로 구현하여 이를 중심으로 삼았다. 우선 P()를 보자.

       /* pc -- semaphore p operation */
       #include "pv.h"
       p(semid)
       int semid;
       {
           struct sembuf p_buf;
           p_buf.sem_num = 0;
           p_buf.sem_op = -1;
           p_buf.sem_flg = SEM_UNDO;
          
           if (semop(semid, &p_buf, 1) == -1) {
               perror("p(semid) failed");
               exit(1);
           } else
               return(0);
        } 

     이때 SEM_UNDO를 사용했음에 주의하라. V()는 다음과 같다.
      
        /* v.c -- semaphore v operation */
        #include "pv.h"
        v(semid)
        int semid;
        {
            struct sembuf v_buf;
            v_buf.sem_num = 0; 
            v_buf.sem_op = 1; 
            v_buf.sem_flg = SEM_UNDO; 
  
            if(semop(semid, &v_buf, 1) == -1) {
                perror("v(semid) failed");
                exit(1);
            } else
                return(0);
         }

     이제 비교적 간단한 이들 루틴으로 상호 배제를 구현해보자.
     다음의 프로그램을 살펴보자.
 
         /* testsem -- test semaphore routines */
         #include "pv.h"
         
         main()
         {
              key_t semkey = 0x200;
              
              if(fork() == 0)
                 handlesem(semkey);

              if(fork() == 0)
                 handlesem(semkey);

              if(fork() == 0)
                 handlesem(semkey);
          }
             
          handlesem(skey)
          key_t skey;
          {
              int semid, pid = getpid();
 
              if((semid = initsem(skey)) < 0)
                  exit(1);
              printf("\nprocess %d before critical section\n", pid);
        
              p(semid);
              printf("process %d in critical section\n", pid);
             
              /* in real life do something interesting */
              sleep(10);
              printf("process %d leaving critical section\n", pid);

              v(semid);
              printf("process %d exiting\n", pid);
              exit(0);
           }
     testsem은 세개의 자식프로세스를 생성하고 , 이들은 p()와 v()를 사용하여 
     임계 영역에는 한 순간에 둘 이상이 들어있지 못하도록 한다. 
     한 컴퓨터에서 testsem을 수행시킨 결과는 다음과 같다.

              process 799 before critical section 
              process 800 before critical section 
              process 801 before critical section 
 
              process 799 in critical section 
              process 799 leaving critical section 
              process 799 exiting 
              process 801 in critical section 
              process 801 leaving critical section 
              process 801 exiting
              process 800 in critical section 
              process 800 leaving critical section 
              process 800 exiting
                



o Critical secion 란 ?

  - 다중 프로그래밍 운영체제에서 여러 프로세스가 데이타를 공유하면서 수행될 때 
    각 프로세스에서 공유 데이타를 액세스하는 프로그램 코드 부분을 가리키는 말.
    공유데이타를 여러 프로세스가 동시에 액세스하면 시간적인 차이 때문에 잘못된 
    결과를 만들어 낼 수 있기 때문에 한 프로세스가 위험 부분을 수행하고 있을 때,
    즉 공유 데이타를 액세스하고 있을 때는 다른 프로세스들은 절대로 그 데이타를
    액세스하지 못하도록 하여야 한다.

o Mutual exclusion (상호 배제)란(1) ?

  - 프로세스의 상호 교신에 대한 기본적인 조치는 공용 부분을 여러 프로세스가 
    동시에 사용하는 것을 배제하는 것이었다. 시스템의 어떠한 자원을 한 시점에서
    한개의 프로세스만이 사용할 수 있도록 하는 것을 상호배제라 한다. 또한, 
    프로그램에서 이러한 자원을 사용하거나 혹은 그 내용을 변경하는 부분을 
    위험부분 (critical section)이라 하며, 둘 이상의 프로그램에서 이 위험 
    부분이 동시에 수행되지 않도록 하는 것이 상호 배제의 기능이다.  

o Mutual exclusion (상호 배제)란(2) ?

  - 다중 프로그래밍 시스템에서 여러 프로세스가 하나의 공유 데이타를 액세스하면서
    작업을 할 때, 한 프로세스가 그 데이타를 액세스할 때는 다른 프로세스들은 
    그것을 사용하지 못하도록 하는 운영체제의 기능.
    예를 들어 한 프로세스가 어떤 화일에 데이타를 쓰고 있을 때 다른 프로세스가 
    그 화일을 지원버린다면 많은 문제가 발생할 것이다. 상호 배제는 한번에 
    한 프로세스만이 공유 데이타를 액세스할 수 있도록 해 주는 것으로, 
    다중프로그래밍 시스템의 운영체제가 꼭 갖추어야 할 기능이다.
  
 
      
Revision History

작성일자 : 96.10.10
작성자 : 이진수

수정일자 :
수정자 :