Semaphore
semaphore는 여러 개의 프로세스가 shared date에 access할 때 사용되는 counter이다.
E. W. Dijkstra가 mutual exclution과 synchronization의 높은 수준의 관리를 위해서 semaphore를 만들었고,
wati와 signal 두 개의 int 변수이다.
- wait : down, P, lock
- signal : up, V, unlock, post
critical section에서가 mutual exclution이 필요한 상황이다. critical section은 같은 코드를 실행하는 여러가지 프로세스가 있을 수 있는 상황에 치명적이므로, 같은 코드를 실행하는 것은 한 번에 하나의 프로세스만 가능하도록 한다. 이와 같은 과정을 semaphore가 구현할 수 있도록 해준다.
예를들어 설명해보자.
은행 DB에 관련된 작업을 하는 두 개의 프로세스 p1와 p2가 있다고 하자.
그림과 같은 순서로 프로세스가 각각 동작한다고 한다면 동작이 꼬여서 5번 동작에서 90을 반환, 6번 동작에서 110을 반환한다.
이와 같은 상황을 race condition이라고 한다. shared data를 제약없이 access하다보면 이와같은 문제가 생긴다.
이를 해결하기 위해 semaphore를 사용하는데, 같은 코드에 대해서 p1값이 들어오면 코드는 critical section으로 연산이 끝날 때 까지 p2값이 들어오지 못한다. 이와 같이 mutual exclusion하게 만드는 작업이 필요하다.
semaphore는 위와 같은 mutual exclusion상황에서 코드에서 실행할 수 있는 프로세스의 최대 개수를 지정한다. 초기값은 1이다.
프로세스가 코드를 실행하기 시작하며 wait 처리를 하면 semaphore가 조정되고, 코드실행이 끝나고 signal을 호출하면 semaphore가 해제된다.
semaphore를 사용하는 형태는 다음과 같다.
wait(&S); /* entry section or gatekeeper */
<critical section>
signal(&S); /* exit section */
<remainder section>
wait와 signal의 pseudocode는 다음과 같다.
void wait(semaphore_t *sp) {
if (sp->value <= 0)
<Add this process to sp->list>
<block>
}
sp->value--;
}wait를 처음 실행시 semaphore의 초기값은 1이므로 vlaue--하고 프로세스를 실행한다.
그 이후 다른 프로세스가 wait를 실행하게 되면 sp가 0보다 작으므로 semaphore의 list(queue)에 대기열로 추가되고, block되어 대기한다.
void signal(semaphore_t *sp) {
sp->value++;
if (sp->list != NULL)
<remove a process from sp->list
and put in ready state>
}먼저 실행되었던 프로세스가 완료되고 signal을 실행하게 되면, semaphore value를 증가시키고 대기열에서 다음 프로세스를 꺼내어 실행시킨다.
wait와 signal을 통해 오직 한 개의 프로세스만이 실행된다. wait와 signal operation은 atomic하므로 실행 도중에 interrupt되거나 하지 않고, 모든 동작이 연결되어 한 번에 실행된다.
semaphore는 여러 semaphore element의 배열로 구성되어있다.
semaphore에도 struct stat과 같은 구조체 semid_ds가 있다.
#include <sys/sem.h>
struct semid_ds {
struct ipc_perm sem_perm;
struct sem *sem_base; /* ptr to array of semphores in set */
ushort_t sem_nsems; /* # of semaphores in set */
time_t sem_otime; /* last-semop() time */
time_t sem_ctime; /* last-change time */
};
struct sem {
ushort_t semval; /* semaphore value, nonegative*/
short sempid; /* PID of last successful semop(), SETVAL, SETALL*/
ushort_t semncnt; /* # awaiting semval > current value */
ushort_t semzcnt; /* # awaiting semval = 0 */
};sem_base는 sem이라는 여러 정보를 가진 semaphore의 배열이다.
sembase의 길이는 sem_nsems이다.
sem_otime은 마지막 semop가 실행된 시간, sem_ctime은 마지막으로 변경된 시간이다.
struct sem은 다음과 같은 값들을 가지고 있다.
- semval : A nonnegative integer representing the value of the semaphore element
semaphore값으로 초기값이 1이어야 mutual exclusion할 수 있다. - sempid :The process ID of the last process to manipulate the semaphore element
가장 마지막에 operation한 pid - semncnt : The number of processes waiting for the semaphore element value to increase.
- semzcnt : The number of processes waiting for the semaphore element value to equal 0
- queue of processes waiting for the value to increase.
프로세스가 대기하는 queue - queue of processes waiting for the value to equal 0
위 그림은 semaphore의 구조이다.
sem_nsems가 sem_base의 길이를 의미하고 값이 2이므로, sem_base의 sem 구조체는 2개 있다.
sem_base의 길이가 4이면 그림의 아래 4개의 semval과 같은 구조일 것이다.
The semget(2) system call
#include <sys/sem.h>
int semget(key_t key, int nsems, int flag);
// Returns: semaphore identifier if OK, -1 on errornsems는 semaphore의 개수이고, key값에 해당하는 semaphore id를 반환한다.
flag의 경우 message queue에서의 msgget과 같다.
#define PERMS (S_IRUSR | S_IWUSR)
int semid;
if ((semid = semget(IPC_PRIVATE, 3, PERMS)) == -1)
perror("Failed to create new private semaphore");IPC_PRIVATE를 통해 생성한 key로 semget하고, 얻은 id를 semid에 저장한다.
example
#include <errno.h>
#include <sys/sem.h>
#include <sys/stat.h>
#define PERMS (S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH | S_IWOTH)
#define SET_SIZE 2
int main(int argc, char *argv[]) {
key_t mykey;
int semid;
if (argc != 3) {
fprintf(stderr, "Usage: %s pathname id\n", argv[0]);
return 1;
}
if ((mykey = ftok(argv[1], atoi(argv[2]))) == (key_t)-1) {
fprintf(stderr, "Failed to derive key from filename %s:%s\n",
argv[1], strerror(errno));
return 1;
}
if ((semid = semget(mykey, SET_SIZE, PERMS | IPC_CREAT)) == -1) {
fprintf(stderr, "Failed to create semaphore with key %d:%s\n",
(int)mykey, strerror(errno));
return 1;
}
printf("semid = %d\n", semid);
return 0;
}argument로 받은 값을 통해 ftok로 키를 생성한다.
생성한 키를 이용하여 semget으로 sem_base의 길이가 2인 semaphore를 open한다.
PERMS에는 u/g/o 모두의 read write권한이 허용되어있고, IPC_CREAT이므로 key에 해당하는 semaphore가 없을 경우 생성한다.
The semctl(2) system call
#include <sys/sem.h>
int semctl(int semid, int semnum, int cmd,…/*union semun arg*/);
// Returns: (see following)semid가 가리키는 semaphore 중에서 semnum에 해당하는 index의 semahpore에게 cmd명령을 수행시킨다.
cmd 명령이 전체 semaphore가 실행해야하는 경우 semnum이 필요없다.
union semun {
int val; /* for SETVAL */
struct semid_ds *buf; /* for IPC_STAT and IPC_SET */
unsigned short *array; /* for GETALL and SETALL */
};segmun은 union(공용체)으로 이루어져 있어, 변수간의 메모리를 공유한다.
cmd에 따라 semun의 변수 중 어떤 것을 사용할 지 결정된다.
SETVAL을 사용할 떄는 val을, IPC_STAT과 IPC_SET을 사용할 때는 semid_ds 구조인 buf를, GETALL과 SETALL을 사용할 때는 array를 사용한다.
SETVAL과 GETVAL명령어는 특정 1개의 semaphore의 값을 set / get한다.
GETALL과 SETALL 명령어는 모든 semaphore의 값을 set / get 한다.
semctl에는 다음과 같은 명령어들이 있다.
| Standard IPC functions (note that the semid_ds structure is defined in <sys/sem.h>) |
|
| IPC_STAT | copy members of semid_ds of semaphore set semid into arg.buf |
| IPC_SET | set permissions of the semaphore set from arg.buf |
| IPC_RMID | remove semaphore set identified by semid |
| Single semaphore operations (these apply to semaphore sem_num, values returned by semctl) |
|
| GETVAL | return value of a specific semaphore element |
| SETVAL | set value of a specific semaphore element to arg.val |
| GETPID | return process ID of last process to manipulate element |
| GETNCNT | return number of processes waiting for element to increment |
| GETZCNT | return number of processes waiting for element to become 0 |
| All semaphore operations | |
| GETALL | return values of the semaphore set in arg.array |
| SETALL | set values of semaphore set from arg.array |
example
#include <sys/sem.h>
int initelement(int semid, int semnum, int semvalue) {
union semun {
int val;
struct semid_ds *buf;
unsigned short *array;
} arg;
arg.val = semvalue;
return semctl(semid, semnum, SETVAL, arg);
/* return semctl(semid, semnum, SETVAL, semvalue); */
}매개변수 semid를 통해 받은 semaphore 중에서 semnum을 통해 특정 semaphore를 지정한다.
지정한 semaphore의 semval값을 SETVAL 명령어를 통해 semvalue로 설정한다.
#include <sys/sem.h>
int removesem(int semid) {
return semctl(semid, 0, IPC_RMID);
}IPC_RMID를 통해 semid에 해당하는 semaphore id를 삭제한다.
The semop(2) system call
#include <sys/sem.h>
int semop(int semid, struct sembuf semoparray[], size_t nops);
// Returns: 0 if OK, -1 on errorsemid가 가리키는 semaphore set에 할당된 각각의 operation들을 실행한다.
semaphore 각각에 들어갈 operation은 semoparray를 통해 받는다. 배열의 크기는 nops이다.
struct sembuf {
unsigned short sem_num; /* member # in set (0, 1, ..., nsems-1) */
short sem_op; /* operation (negative, 0, or positive) */
short sem_flg; /* IPC_NOWAIT, SEM_UNDO */
};semoparray의 자료형인 sembuf는 위와 같은 구조체이다.
sem_num은 어떤 semaphore에 할당할 것인지 semaphore의 번호를 의미한다.
sem_op을 통해 wait나 signal중 어떤 것을 할 지 operation을 설정한다.
sem_op의 값에 따른 operation설정은 다음과 같다.
| sem_op | action |
| > 0 | V(), increase the semaphore to record release of resource add sem_op to semval V(signal) operation 을 설정. resource를 해제한 만큼 semaphore를 증가시킨다. |
| < 0 | P(), decrease the semaphore to record the acquisition of the resource block until semval>=abs(sem_op), semval=semval-abs(sem_op) P(wait) operation 을 설정. resource를 확보한 만큼 semaphore를 줄인다. |
| == 0 | test the semaphore if it is at zero block until semval=0 test 전용 |
void setsembuf(struct sembuf *s, int num, int op, int flg) {
s->sem_num = (short)num;
s->sem_op = (short)op;
s->sem_flg = (short)flg;
return;
}
struct sembuf myop[3];
setsembuf(myop[0], 1, -1, SEM_UNDO);
setsembuf(myop[1], N, 2, SEM_NOWAIT);
setsembuf(myop[2], 2, 0, SEM_UNDO);
if (semop(semid, myop, 3) == -1)
perror(“Failed to perform semaphore operation”);setsembuf함수의 매개변수 s는 sembuf로 operation을 나타내는 구조체이다. num 은 semaphore 번호, op값은 +일 경우 signal, -일 경우 wait이다.
즉 num에 해당하는 semaphore에 op에 해당하는 operation으로 지정하여 sembuf s에 저장한다.
myop 각각에 대해서 setsembuf로 sembuf를 설정하고, semop을 통해서 0,1,2 3개의 semaphore에 설정된 operation이 동시에 atomic하게 실행된다.
example
예제를 통해 mutual exclusion이 구현되는 것을 알아보자.
#include <sys/types.h> /* 세마포 예의 헤더 화일 “pv.h” */
#include <sys/ipc.h> #include <sys/sem.h> #include <errno.h>
#define SEMPERM 0600
#define TRUE 1
#define FALSE 0
typedef union semun {
int val;
struct semid_ds *buf;
ushort *array;
} semun;int initsem (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{ /* 만일 생성되었으면 ... */
semun arg;
arg.val = 1;
status = semctl(semid, 0, SETVAL, arg);
}
if (semid == -1 || status == -1){
perror ("initsem failed");
return (-1);
}
return (semid); /* 모든 것이 잘되었음. */
}semaphore val의 초기값은 1이다. critical section에 프로세스가 들어가면 1감소하고, signal을 호출하고 나오면 1증가한다.
semun union은 semctl의 4번째 매개변수로 사용하는 변수이다. cmd에 따라서 val, buf, array 중 하나를 선택한다.
initsem 함수에서는
이미 semaphore가 존재하는 경우 permission없이 semget으로 semid를 할당받고 초기값 세팅이 필요없다.
semget을 통해 semkey로 semid를 할당받고 semaphore가 생성된 경우 semun의 초기값을 세팅한다.
semid에 -1이 할당되면 실패한 것이고, semid가 정상적으로 들어가면 semid를 return한다.
/* p.c – semaphore p operation
#include "pv.h"
int p (int semid){ /* p.c -- 세마포 p 연산 */
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);
}
return (0);
}/* v.c – semaphore v operation */
#include "pv.h"
int v (int semid){ /* v.c -- 세마포 v 연산 */
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);
}
return (0);
}p는 wait이고, v는 signal이다.
p에서는 sembuf인 p_buf에 sem_num에 0를 저장하고, sem_op에 -1을 저장한다.
wait operation은 semaphore를 1감소시키므로 sem_op에 -1을 저장한다.
semop을 통해 semid에 해당하는 semaphore에 1개의 operation을 지정하여 실행한다.
v에서는 signal이므로 p와 다르게 sem_op에 1을 저장한다.
#inculde "pv.h"
void handlesem (key_t skey);
main(){ /* testsem -- 세마포 루틴을 테스트한다. */
key_t semkey = 0x200;
int i;
for(i = 0; i < 3; i++) if (fork() == 0) handlesem (semkey);
}
void handlesem (key_t skey){
int semid;
pid_t 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);
/* 실제로는 무언가 흥미있는 일을 한다. */
sleep (10);
printf ("process %d leaving critical section\n", pid);
v (semid);
printf ("process %d exiting\n", pid);
exit (0);
}main에서 semkey에 key값을 설정한다.
for문을 통해 3번 fork하면서 child만 handlesem을 실행하고 exit한다.
child는 handlesem에서 첫 번째로 initsem하는 child는 key를 생성하고, 두 세 번째 initsem에서는 key를 get만 진행한다.
p 함수를 먼저 실행하는 child는 resource를 확보하고 semaphore를 1감소시킨다. semaphore는 초기값이 1이므로 1감소되면, 다른 child가 들어올 수 없이 wait한다.
첫 번째 child process가 sleep 동작을 하고 v 함수를 통해 resource를 해제시키면 semaphore를 1증가시켜 다른 프로세스가 들어올 수 있게 된다.
semaphore가 다시 1이되면 두 번째 프로세스가 들어와서 작업을 진행하고, signal하면 wait하던 다음 프로세스가 들어와서 작업을 진행한다.
process 799 before critical section
process 799 in critical section
process 800 before critical section
process 801 before critical section
process 799 leaving critical section
process 801 in critical section
process 799 exiting
process 801 leaving critical section
process 801 exiting
process 800 in critical section
process 800 leaving critical section
process 800 exiting결과를 보면 799, 800, 801 프로세스 순서대로 들어오는 상황에서 799가 critical section으로 들어오면 800, 801은 wait한다. 799프로세스가 critical section에서 나가고 나서 801이 critical section으로 들어와서 작업을 수행한다. 801이 나가면 800번이 critical section으로 들어와서 작업 후 exit한다.
The semop(2) : SEM_UNDO
IPC object는 프로세스가 사용하지 않더라도 따로 처리하지 않으면 살아있다. 따라서 release하지 않은 프로그램의 semaphore가 할당되어있을 가능성이 있다.
예를 들어 p1, p2, p3 프로세스들 중 critical section으로 p1이 먼저 들어와 작업을 하고 p2,p3는 wait하는 과정에서 error로 인해 강제종료되면, p1은 signal하지 않으므로 p2는 계속 wait하는 deadlock에 걸린다.
SEM_UNDO flag는 할당된 semaphore를 release(singal)하지 못하고 프로그램이 종료되더라도 이를 조정하여 undo(복구)한다. (실제로 undo작업은 kernel에서 진행된다)
