System V 계열 세마포어(semaphore)를 통한 상호배제

http://www.sunyzero.com/zboard/view.php?id=sunycomputer&page=3&sn1=&divpage=1&sn=off&ss=on&sc=on&select_arrange=headnum&desc=asc&no=82

 

Subject		[C] System V 계열 세마포어(semaphore)를 통한 상호배제: 예제있음

[ 세마포어와 상호배제 : System V Semaphore 예제 ] * 글쓴이 : Steven Kim <sunyzero@yahoo.com> * 마지막 고친날짜 : 2003-08-20 * 이 글에 문제가 있거나 오타/이상함이 있는 경우 댓글을 첨언하여 주시면 반영하겠습니다.(if idle...) 1. 개념 세마포어(semaphore)는 상호배제(Mutual Exclusion:MUTEX) 이론을 이용하여 만들어진 운영체제에서 제공하는 기능중의 하나입니다. 세마포어를 처음 주창한 사람이 딕스트라(Dijkstra)인것은 아시죠? shortest path 알고리즘 및 여러가지 이론을 만든 수학자 아저씨...(shortest path에서는 bellman ford algorithm과 가장 많이 쓰이죠. Linear Programming쪽 공부하면 가장 처음에 배우는 앨거리듬이죠) 자 이런 세마포어는 어떤 것일까? 한번 살펴보겠습니다. 실제로 세마포어는 어떤 영역을 한번에 한녀석만 들어갈 수 있게 만든 것입니다. 쉽게 말하면 특정 영역에 A란 녀석이 쓰기를 시도할때 B란 녀석이 다시 쓰기를 하면 다 쓰고 난뒤에 그 내용이 A란 녀석이 쓴 내용인지, 혹은 B란 녀석이 쓴 내용인지 알 도리가 없습니다. 심지어 두개가 섞여버리는 수도 있습니다. 이런 경우를 방지하기 위해서 데이터를 변경할 경우엔 그 변경하는 타이밍에 다른 녀석이 접근하지 못하게 하는게 가장 좋죠. 물론 읽기를 시도할때도 쓰기가 완전히 끝난 다음에 읽도록 하는게 좋겠죠? 실제로 세마포어는 에서 P/V 오퍼레이션에 대한 것은 운영체제 책에 나오므로 읽어봅시다. P는 세마포어의 상태를 Zero로 만들고, V는 다시 양수쪽으로 바꾸게 됩니다. 그렇게 되어 현재 상태가 0 이면 기다리게 되고, 그게 자신의 차례가 되면 바로 전에 임계영역(critical section)에 있던 녀석이 빠져나가면서 V 를 해서 양수를 만들어주어 자신이 진입할 수 있도록 해줍니다. 2. 간단한 세마포어 예제(1) 자 그러면 실제로 사용되는 부분을 봅시다. 아래의 코드를 보면서 생각해봅시다. (여기서 제공하는 것은 가장 많이 사용되는 SysV계열의 세마포어를 기준으로 합니다.) * 설정 - 현재 아래 소스코드가 수행되는 서버는 pre-fork 된 10개의 서버가 동시에 접근가능한 부분이다. - shm_userinfo 는 공유메모리 영역이다. 10개의 서버는 이 영역을 공유한다. - sem_buf.sem_op 는 세마포어에 더할 값이다. -1 이면 P 오퍼레이션(lock)을 수행한다. 1 은 V 오퍼레이션(unlock)을 수행한다. - semop()의 마지막(3번째 파라메터)는 sem_buf 배열의 갯수를 의미한다. [code] ....(생략)....     sem_buf.sem_num = sem_idx;        /* semaphore element index */     sem_buf.sem_flg = SEM_UNDO;        /* SEM_UNDO flag */     sem_buf.sem_op = -1;     semop(sem_id, &sem_buf, 1); /* P operation : decrease */     shm_userinfo->person[i].id = cur_id; /* critical section */          sem_buf.sem_num = sem_idx;     sem_buf.sem_flg = SEM_UNDO;     sem_buf.sem_op = 1;     semop(sem_id, &sem_buf, 1); /* V operation : increase */ ....(생략).... [/code] 위에서 보면 10개의 서버를 간략하게 a, b, c, ... 로 칭할때 a 가 먼저 P 를 걸고 critical section에 진입해서 데이터를 수정하고 있습니다. 이 데이터를 수정하는 도중에 b, c 프로세스가 이 부분에 진입하면서 P 를 걸고 들어오게 됩니다. P 오퍼레이션이 되면서 사용가능한 공간이 없음을 알리기 위해서 세마포어값은 0 이 됩니다. 그런 뒤에 a 가 shm_userinfo 메모리 영역을 수정하고 임계영역을 벗어나게 되면 sem_buf.sem_op = 1 을 넣고, semop() 를 호출하여 세마포어값을 증가시킵니다. 그러면 다음에 신호를 받을 녀석은 0 상태에서 1 이 되고 따라서 자신이 임계영역을 들어갈 수 있는 상태라는 것을 알게됩니다. 따라서 임계영역에 진입하면서 P 를 호출해서 0 을 만들죠. 주의) 세마포어는 위의 shm_userinfo 라는 영역이 동시에 변경되거나 변경되는 도중 읽기가 일어나는 것을 막기 위해서 사용됩니다. 그러므로 실제 상호배제는 특정 영역을 접근하는 것에 있어서 동시성을 배제하는 것이 목적이지, 연산의 순서를 정하는 것은 아닙니다. 3. System V semaphore functions 위에서 간단하게 세마포어의 사용에 대해서 봤으니 실제로 세마포어를 생성하고, 변경하고, 제거하고, 정보를 알아보는 방법도 알아봅시다. 3.1 세마포어 생성: semget 문법 : int semget ( key_t key, int nsems, int semflg ) - 반환값 : 성공: 세마포어에 접근가능한 식별자(semaphore id)를 반환합니다. 이 id로 접근가능합니다.           실패: -1 - key   : 세마포어를 생성할 세마포어 키입니다. 일반적으로 공유메모리와 같이 쓸 경우 키값은 혼동을 피하기 위해서 같이 사용합니다. 단 몇몇 시스템은 같은 키를 사용할 수 없는 경우가 있습니다.           만일 특정키와 중복되지 않는 키를 생성해서 사용하기 위해서는 IPC_PRIVATE를 사용할 수 있습니다(이 경우엔 반환되는 ipc id값을 저장하고 있다가 해당 semid로 접근해야 합니다)         ex) 공유메모리키 : 0x35001000 -> 세마포어 키 : 0x35001000 - nsems : 생성시 세마포어 갯수를 의미합니다. 기존 세마포어에 attach 할 경우엔 이 값은 무시됩니다. - semflg: 생성시 적용할 플래그입니다. 이 플래그들은 OR 연산으로 여러개의 플래그를 적용할 수 있습니다. 일반적으로 이 플래그는 IPC 기본 플래그와 동일합니다. 따라서 공유메모리 메세지큐의 플래그와 동일한 의미를 가집니다. 그리고 플래그들과 별개로 이 semflg의 하위 9비트는 생성권한을 의미합니다. 0777 로 주면 모든 유저가 읽기/삭제/접근이 가능합니다.   + semflg 목록   IPC_CREAT : 세마포어를 생성합니다.   IPC_EXCL  : IPC_CREAT 와 같이 사용할 수 있습니다. 이미 생성되어있는 경우 -1을 반환하고 errno는 EEXIST로 세팅됩니다. 예) 0x44001100 키를 가지고 5개의 배열을 지닌 세마포어를 생성. 생성시 권한은 0660 으로 세팅, IPC_EXCL 플래그가 존재하므로 이미 존재한다면 -1 을 반환하고 errno는 EEXIST로 설정된다. sem_id = semget(0x44001100, 5, IPC_CREAT|IPC_EXCL|0660); 3.2 세마포어 제어: semctl (semaphore control) 문법 : int semctl (int semid, int semnum, int cmd, union semun arg) - 반환값 : 성공: 양수값           실패: -1 - semid : semget() 에서 리턴된 세마포어 식별자(semaphore id) - semnum: 제어할 세마포어 배열의 인덱스 - cmd   : 세마포어 제어 명령 - arg   : 세마포어 제어 명령(cmd)에 따라서 저장되거나 반환되는 세마포어 정보 공용체 arg는 다음과 같다. 이 공용체는 어떤 cmd 를 사용하는가에 따라서 다른 의미로 사용된다. union semun {     int val;                    /* SETVAL을 위한값 */     struct semid_ds *buf;       /* IPC_STAT, IPC_SET을 위한 버퍼 */     unsigned short int *array;  /* GETALL, SETALL을 위한 배열 */     struct seminfo *__buf;      /* IPC_INFO을 위한 버퍼 */ }; cmd 을 위한 값은 다음과 같다. 당연히 이 명령들은 세마포어에 접근가능한 해당권한이 있어야 한다. 읽기명령인 경우는 읽기권한, 변경/삭제인경우는 쓰기 권한이 있어야 한다. IPC_STAT    arg.buf 원소에 semaphore 정보를 복사합니다. 인수 semnum 는 무시된다.             이 struct semid_ds 구조체 아래와 같습니다.         struct semid_ds         {             struct ipc_perm sem_perm;     /* operation permission struct   */             __time_t sem_otime;           /* last semop() time             */             __time_t sem_ctime;           /* last time changed by semctl() */             unsigned long int sem_nsems;  /* number of semaphores in set   */         }; IPC_RMID    세마포어 설정을 즉시 제거하고, 그것의 데이타 구조는 모든 대기중인 프로세스들을 재실행한다.             호출한 프로세스 유효 사용자ID는 수퍼유저나 세마포어설정의 생성, 소유자중의 하나이어야한다.             인수 semnum 는 무시된다. GETALL      arg.array 인수에 설정된 모든 세마포어 위한 semval 를 반환한다.             변수 The argument semnum 는 무시된다. GETNCNT     시스템 호출은 semncnt 의 값을 반환한다. GETPID      세마포어 호출은 sempid 의 값을 반환한다. 세마포어를 호출한 프로세스의 pid를 의미한다. GETVAL      시스템 호출은 설정의 semnum 번째에 해당하는 세마포어 배열의 semval 의 값을 리턴한다. GETZCNT     시스템 호출은 설정의 semnum 번째에 해당하는 세마포어 배열에 semzcnt의 값을 리턴한다.             semzcnt는 현재 블록되어있는 기다리는 프로세스 갯수이다. SETALL      세마포어 인수배열을 사용하여 설정과 관련된 semid_ds 구조체의 sem_ctime, semval 의 값을 새로 설정한다.             기존의 세마포어에 대해서 Undo 엔트리는 모두 소거되고 대기열에서 유휴중인 프로세스들은 semval을 0으로             만들고 기다리게 된다. 인수 semnum은 무시된다. 3.3 세마포어 값 변경 문법 : int semop ( int semid, struct sembuf *sops, unsigned nsops ) - 반환값 : 성공:  0 리턴           실패: -1 리턴 - semid : semget() 에서 리턴된 세마포어 식별자(semaphore id) - sops  : 세마포어 연산을 위한 지시자 구조체, 각 구조체의 의미는 아래와 같다.             short sem_num;  /* semaphore 배열번호: 0 = first */             short sem_op;   /* semaphore operation          */             short sem_flg;  /* operation flags              */ - nsops : sops 배열의 갯수, 변경할 세마포어가 여러개인 경우는 연산을 위한 sops의 배열 갯수를 의미하게 된다. 위에서 세마포어 연산을 위한 struct sembuf *sops 의 각 필드들은 각 의미를 가진다. sem_num : 세마포어 배열번호이다. 연산을 위한 세마포어 배열의 인덱스이다. sem_op  : 세마포어 값(semval)에 더할 값이다. 주로 1, -1 로 되어있다.           -1은 값을 감소시키므로 P 연산에 해당하고, 1 이면 값을 증가시키므로 V 연산에 해당한다. sem_flg : 세마포어 연산을 위한 선택적 플래그, 아래와 같은 의미를 가진다. IPC_NOWAIT : 일반적으로 세마포어는 P 를 호출했을때 세마포어값이 0 이면 사용가능하지 않으므로 현재 임계영역에 있는 프로세스가 끝나고 V를 호출하기까지 블록됩니다. 하지만, IPC_NOWAIT를 설정한다면 errno를 EAGAIN 으로 설정하고 바로 리턴합니다. 말그대로 기다림이 없다는 것입니다. SEM_UNDO : 이 플래그가 세팅되면 해당 프로세스가 종료될때 자동으로 작업을 취소하게 해줍니다. 따라서 어떤 프로세스가 임계영역안에서 죽는 일이 발생한다면 자동으로 해당 작업은 취소되고 다음 프로세스가 P 연산을 걸고 임계영역안으로 진입할 수 있게 됩니다. 예제) 아래는 2개의 세마포어를 바꾸는 작업이다. 실제로 0번째(첫번째 세마포어 배열), 3번째(4번째 세마포어 배열)을 동시에 바꾸는 연산을 수행한다. 또한 sem_op가 -1 이므로 P 연산에 해당하는 작업이 수행된다. struct sembuf semops[2]; semops[0].sem_num = 0; semops[0].sem_op  = -1; semops[0].sem_flg = SEM_UNDO; semops[1].sem_num = 3; semops[1].sem_op  = -1; semops[1].sem_flg = SEM_UNDO; semop(semid, semops, 2); 4. 사용예 아래는 세마포어를 사용하는 실제 예제코드이다. 여러개의 프로세스가 fork()되어서 세마포어를 이용하여 상호배제를 하는 것을 볼 수 있다. 4.1 주의! 아래 예제를 넣을려고 했지만 그냥 소스파일을 올리는 것으로 대신하겠다. 실제로 src/ipc 디렉토리에 들어가서 make 로 컴파일을 하면 sysv_sem, sysv_nosem 두개의 파일이 나온다. 실제 이 파일들은 sysv_sem.c 파일에 세마포어를 사용한것과 사용하지 않은 것으로 컴파일한 것이다. 실행은 아규먼트 인자로서 fork 할 프로세스 갯수를 넣어주면 된다. 또한, 3개 이상 fork() 할 경우 3번째 프로세스는 인위적으로 abort()로 종료시키는데 세마포어 사용시 제대로 SEM_UNDO가 제대로 작동함을 보여주는 것이다. 만일 SEM_UNDO가 없다면 3번째 프로세스가 abort()로 종료되면서 모든 프로세스들은 블록될것이다. PS) 어디에 퍼가서 사용하실때는 원본글의 출처를 밝혀주시기 바랍니다. 혹여 안밝혀도 상관없습니다. 다만 그냥 예의상... ^^* Ref. 배타적인 자원사용에 대한 것을 자세히 공부해두면 좋다. 비동기적 프로세싱이나 커널프로그래밍에서는 이것은 필수다. * TAS(Test-and-Set) operation : atomic한 프로세스로 서로다른 두 함수가 하나의 리소스에 동시적으로 접근할때 먼저 진입한 쪽이 1로 세팅하여 다른 함수가 진입하지 못하게 막는다. 끝나고 나갈때 0으로 돌려주면 다음 함수가 진입한다. 68000 CPU의 경우에는 하드웨어 인스트럭션으로 TAS 를 제공한다. * Spinlock : 배타적으로 다수의 CPU에서 서로 자원의 선점을 위해서 사용되어진다. 커널내부에서 주로 사용한다.