Digital Recipe

동기화 본문

컴퓨터 공학/운영체제

동기화

노리터 2012. 1. 30. 22:18

1. 필요성

멀티 프로세서 환경 또는 시분할 방식에서 성능향상을 위해 병렬성(Parallelism)을 활용한다. 병렬성에 따라 시스템 자원의 대부분은 공유될 수 있으며 따라서 동시 접근으로부터 보호되어야 한다. 이를 위해 공유자원은 동기화 방법을 통해 보호할 수 있다.

※ 경쟁 조건 (Race condition)
하나 이상의 프로세스가 동일한 자원을 사용하기를 원하는 것을 말한다.


2. 동기화 방법
   - 대표적으로 스핀 락, 세마포어, 파이프 등이 있다.
   - 데드락 방지가 필요하다.

   ※ 데드락(Deadlock)
   프로세서가 자원을 사용할 수 있을 때까지 기다리지만 논리적으로 더이상 풀리지 않는 상태에 도착한 현상.
   절대 발생하지 않는 일을 무한정 기다린다. 데드락을 방지하기 위해 중첩된 락은 반드시 같은 순서로 잠가야 하며,    기아현상을 방지하고 설계는 최대한 단순하게 한다.
    
   ※ 기아현상(Starvation)
   프로세서가 자원을 사용할 수 있을 때까지 기다리지만 우선순위에서 밀려나 자원 사용이 한없이 늦어지는 현상.
   결과는 데드락과 비슷하나 언젠가는 발생할 수 있는 일을 기다린다.


3. 스핀 락
   - 리눅스에서 가장 일반적인 락(Lock) 방법
   - Busy Loop 방식이다.

   ※ Busy Loop
   기본적으로 하나의 프로세스(Process)는 하나의 프로세서(Processor), 예를 들어 CPU,를 할당받은 후 자신을 수    행하기 위해 필요한 자원을 획득하고자 한다. 이때 자원을 획득할 수 없으면 해당 프로세스는 지속적으로 필요한      자원 획득을 시도하게 된다. 이때 Busy Loop 방식은 필요한 자원을 획득하여 모든 수행이 끝날 때까지 할당받은      CPU를 보유하는 방식을 말한다. 이후 설명하는 세마포어와 다른 방식이며 아래와 같은 특징을 가진다.

   특징
      - 문맥교환이 필요하지 않다. (프로세서를 지속적으로 할당받고 있기 때문임)
      - Busy Loop이기 때문에 CPU 효율성이 떨어진다. ( 하나의 프로세스가 하나의 프로세서를 독점하기 때문.)
      - 자원 획득을 위한 짧은 대기에 효과적이다.
      - SMP(Symmetric multiprocessing) 환경에서만 사용가능하다.
 
4. 세마포어
   - 일정 시점에 제한된 여러 쓰레드의 동시 접근을 허용한다.
   - 바이너리 세마포어(Binary Semaphore)와 카운팅 세마포어(Counting Semaphore)가 있다.
   - 자원획득 실패 시 프로세서를 해제하고 휴면에 들어간다.

    ※ NOT Busy Loop
    세마포어를 사용하는 경우 프로세스가 자원을 획득할 수 없는 경우 할당받은 프로세서를 해제하고 자원획득이 가     능할 때 다시 프로세서를 할당받게 된다. 따라서 단일 프로세서 환경에서 사용가능하며, 프로세서의 효율성이 좋       아진다.
   
    ※ 뮤텍스
    바이너리 세마포어를 말하며, 동시에 2개 이상의 프로세스가 자원을 공유할 수 없다.
    ( 단 1개의 프로세스만 자원획득이 가능하다.) 

   ※ 카운팅 세마포어
   2개 이상의 프로세스가 자원 획득이 가능하다. 하지만 제한을 있다.
   상호배제를 보장하지 않는다. 


5. 리눅스에서의 세마포어 구현
   세마포어에서는 P() 연산과 V() 연산을 사용한다. P()연산은 자원획득을 의미하며 V()연산은 자원해제를 의미한      다. 리눅스에서는 down()연산과 up()연산으로 대체한다.

   - down()
      - 카운트를 1만큼 줄여서 세마포어를 얻는다.
      - 카운트가 0 이상이면 락을 얻고 프로세스가 임계구역으로 진입한다.
      - 카운트가 음수인 경우에는 프로세스가 휴면 된다.

   - up()
      - 임계구역에서의 수행을 마치고 세마포어를 반납한다.
      - 카운트 값을 증가시키고, 세마포어를 기다리며 휴면 중인 프로세스를 깨운다.



6. 리눅스에서 세마포어 구현을 위한 사용하는 구조체

     ※ 세마포어 구조체와 세마포어 집합을 위한 구조체  
     ■ Struct semid_ds
     
      용도
         Semaphore의 집합
      구조
         struct ipc_perm sem_perm : 세마포어의 접근권한
         time_t sem_otime : 최종 semop 호출시간
         time_t sem_ctime : 최종 수정 시간
         unsigned short sem_nsmes : 세마포어 배열에 있는 세마포어의 수
 
      ■ struct sem

      용도
         Semaphore 집합에 포함되는 각 Semaphore
      구조
         unsigned short semval : 세마포어의 값 ( 항상 0이상 )
         pid_t semid : 마지막으로 연산을 수행한 프로세스의 pid

      ※ 세마포어 제어와 연산을 위한 구조체
      ■ struct sembuf
   
      용도
         semop()함수에 사용하는 구조체
      구조
         unsigned short sem_num : array내에서 세마포어의 번호 (0, 1, ..., nsems-1)
         short sem_op : 세마포어의 연산종류 ( 음수, 0, 양수 )
         short sem_flg : 세마포어의 플래그를 세팅, 일반적으로 SEM_UNDO로 세팅. 프로세스 종료시 자동으로 세마포어 해제

      ■ union semun

      용도
         semctl() 함수 등에서 사용
         정의되어 있지 않으므로 코드 상에 구현 필요.
      구조
         int val : SETVAL을 위한 값으로 활용.
         short semid_ds *buf : IPC_STAT, IPC_SET을 위한 버퍼로 사용.
         unsigned short *array : GETALL, SETALL 명령을 위한 배열.
         struct seminfo *__buf : IPC_INFO를 위한 버퍼로 사용.


7. 리눅스에서 세마포어를 위해 사용하는 API 

      ■ int semget( ket_t key, int nsems, int semflg )
         세마포어를 생성
    
      ■ int semctl( int sem_id, int_semnum, int cmd, union semun arg )
         세마포어를 제어한다.
         구조체 semun을 인자값으로 활용한다.
         자세한 옵션은 자세한 자료 참조.

      ■ int semop( int sem_id, struct sembuf *ops, unsinged nsops)
         세마포어를 할당하거나 해제한다.
         구조체 sembuf를 인자값으로 활용한다.


      예시1) 최대 3개의 프로세스가 공유할 수 있는 세마포어를 생성하는 경우
 
      #define MAX_RESOURCE 3
      int semid = 0;
      semid = semget((key_t)123, MAX_RESOURCE, 0666 | IPC_CREAT )

   
      예시 2) semun 구조체의 val 변수에 저장된 값으로 세마포어의 val 값을 초기화하는 경우
      union semun sem_union;
      sem_union.val = MAX_RESOURCE;
      semctl(semid, 0, SETVAL, sem_union);

      추가설명) SETVAL은 sem_union.val 값을 sem.val으로 설정하는 옵션이다.


     예시 3) 하나의 프로세스가 세마포어 1개를 획득하는 경우
      struct sembuf s;
      s.sem_num = 0;
      s.sem_op = -1;     <----- P 연산 수행
      s.sem_flg = SEM_UNDO;
      semop(semid, &s, 1)

      추가설명) V 연산을 하기 위해서는 sem_op 값을 1로 설정하면 된다.




참고자료
[1]  http://blog.naver.com/pinix7700?Redirect=Log&logNo=10107532746 
[2]  http://www.linux4u.co.kr/manpage/semctl.2.html 
[3]  http://blog.naver.com/ods81?Redirect=Log&logNo=50120621761 



2012. 01. 30
Posted By HoSeok Seo

 
Comments