1. Problem

가. Race Condition

Race Condition은 여러 프로세스가 동시에 공유 데이터를 수정하려고 할 때 발생하는 문제이다. 최종 데이터 값이 어떤 프로세스가 마지막으로 실행되는지에 따라 달라질 수 있어 데이터 불일치(data inconsistency) 가 발생할 위험이 있다. 이를 방지하기 위해, 동기화 메커니즘이 필요하다.

나. Critical-section Problem

Critical-section Problem이란 여러 프로세스가 공유 자원에 접근할 때 발생하는 문제로, 동기화 없이 동시에 접근하면 Race Condition이 발생하여 데이터 불일치 문제가 생길 수 있다. 이를 해결하기 위해 프로세스는 진입(Entry Section) → 임계 구역(Critical Section) → 종료(Exit Section) → 나머지(Remainder Section)의 구조를 따르게 된다.

do {
	entry section
	critical section
	exit section
	remainder section
} while (TRUE);

- Entry Section: 프로세스가 Critical Section에 들어가기 전에 동기화로 접근 제어

- Critical Section: 공유 자원을 사용하는 핵심 코드가 실행되며, 여러 프로세스가 동시에 접근하면 데이터 불일치가 발생할 수 있기 때문에 반드시 보호해야 함

- Exit Section: 프로세스가 Critical Section에서 나올 때 다른 프로세스가 진입할 수 있도록 Signal 또는 Unlock 수행

- Remainder Section: Critical Section을 사용하지 않는 일반적인 코드가 실행

Critical Section 문제를 해결하지 않으면 여러 프로세스가 동시에 공유 데이터를 변경하며 불일치가 발생할 수 있으므로, 이를 방지하기 위해 Semaphore, Mutex, Monitor 등 동기화 기법이 필요하다.

2. Semaphore

가. Introduction

1) Semaphore 개요

Semaphore란 공유 자원에 대한 동기화 기법 중 하나이다. 정수 변수 S을 사용하여 접근을 제어한다. 다음과 같이 주요 연산 두 가지가 있다.

- wait()(P 연산): semaphore 값을 감소시키고, 자원 사용을 시도
- signal(V 연산): semaphore 값을 증가시키고, 대기 중인 프로세스를 깨움

P(S) { 
	while (S <= 0)
		; 		// noop
	S--;
}
// Semaphore 값이 양수면 감소시키고 진입, 0이면 대기(wait)

V(S) { 
	S++;
}
// Semaphore 값을 증가시켜 자원을 해제(signal)

2) Semaphore을 사용한 자원 획득

공유 자원을 획득하는 과정은 다음과 같다.

① Semaphore 값을 확인하여 자원 사용 가능 여부 검사
② Semaphore 값이 양수라면, 자원을 사용할 수 있고, Semaphore 값 1 감소
③ Semaphore 값이 0이라면, 자원이 사용 중이므로 프로세스 대기

3) Semaphore을 사용한 자원 해제

공유 자원을 해제하는 과정은 다음과 같다.

① 자원 사용이 끝나면, Semaphore 값을 1 증가하여 자원 반환
② 대기 중인 프로세스가 있다면, 이를 깨워서 자원을 사용할 수 있도록 함

나. POSIX Semaphore

1) sem_open()

sem_open() 함수는 이름이 있는 semaphore를 생성하고 초기화하는 역할을 한다.

#include <fcntl.h>
#include <sys/stat.h>
#include <semaphore.h>

sem_t *sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
	Returns: the address of the new semaphore if OK, SEM_FAILED on error

- name: semaphore의 식별자
- oflag: 예를 들어, O_CREAT 옵션을 사용하면 semaphore가 존재하지 않을 경우 새로운 semaphore 생성
- mode: 새로운 semaphore에 대한 접근 권한
- value: 새로운 세마포어의 초기 값

※ pthread 옵션을 사용하여 POSIX thread와 함께 링크할 수 있음

2) sem_wait()

sem_wait() 함수는 semaphore 값을 감소시켜 공유 자원 접근을 제어하는 역할을 수행한다.

#include <semaphore.h>

int sem_wait(sem_t *sem);
int sem_trywait(sem_t *sem);
int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout);
				 Returns:  0 on success; -1 on error

- semaphore 값이 0보다 크면 감소하고 즉시 반환
- semaphore 값이 0이면, 해당 프로세스는 대기 상태(blocking)로 전환

※ 비동기(wait 없이 즉시 반환) 버전
- sem_trywait(): sem_wait()과 동일하지만, 즉시 semaphore 감소가 불가능하면 에러 반환
- sem_timedwait(): sem_wait()과 유사하지만, 특정 시간만큼 대기 후 실패할 수 있음

3) sem_post()

sem_post() 함수는 semaphore 값을 증가시키고 대기 중인 프로세스를 깨운다.

#include <semaphore.h>

int sem_post(sem_t *sem);
				 Returns:  0 on success; -1 on error

값이 0인 경우, 대기 중인 프로세스를 깨워 실행 가능하게 만든다.

4) sem_unlink()

sem_unlink() 함수는 이름이 있는 semaphore을 삭제한다.

#include <semaphore.h>

int sem_unlink(const char *name);
				 Returns:  0 on success; -1 on error

5) Example Code

	/* 생략 */
	sem_t *mysem; 
	if((mysem = sem_open("mysem", O_CREAT, 0777, 1)) == NULL) { 
		perror("Sem Open Error"); 
		return 1; 
	}
	while(1) { 
		sem_wait(mysem);
        
        // critical section
		fd = open(countFile,O_RDWR);
		lseek(fd, 0, SEEK_SET); 
		read(fd, (void *)&count, sizeof(count)); 
		printf("Read Data %d\n",count); 
		count++; 
		lseek(fd, 0, SEEK_SET); 
		write(fd, (void *)&count, sizeof(count));		
		sleep(1); 
		close(fd);
        // critical section
        
		sem_post(mysem); 
	}

다. System V Semaphore

1) semget()

semget() 함수는 세마포어 집합을 생성하거나 가져오는 함수이다.

#include <sys/sem.h>

int semget(key_t key , int nsems , int flag );
				Returns: semaphore ID if OK, -1 on error

- key: semaphore 식별 키
- nsems: semaphore 개수
- flag: semaphore 생성 옵션

semflg 옵션으로 IPC_CREAT | IPC_EXCL을 사용하면, semaphore가 이미 존재할 경우 생성이 실패한다. 이는 O_CREAT | O_EXCL과 비슷한 개념이다.

※ 사용 예시

int semid; 
  
if ((semid = semget((key_t)100, 1, 0600 | IPC_CREAT | IPC_EXCL)) == -1) { 
	if (errno == EEXIST) { 
	semid  = semget((key_t)100, 1, 0); 
	} 
} else { 
	/* initialize the semaphore value with semctl( ) */ 
} 

2) semctl()

semctl() 함수는 semaphore을 제어한다.

#include <sys/sem.h>

int semctl(int semid , int semnum , int  cmd , ... /* union semun arg  */); 				
				Returns: non-negative if OK, -1 on error

- semid: semahore ID
- semnum: semaphore 집합 내 인덱스
- cmd: 제어 명령어
☞ SETVAL: 특정 semaphore 값을 설정
☞ IPC_RMID: semaphore 집합 제거

※ 사용 예시: semaphore 초기화

union semun arg; 
  
arg.val = 1; 
semctl(semid, 0, SETVAL, arg);

※ 사용 예시: semaphore 제거

union semun arg; 

semctl(semid, 0, IPC_RMID, arg);

3) semop()

semop() 함수는 semaphore 값을 변경하는 함수이다.

#include <sys/sem.h>

int semop(int semid , struct sembuf semoparray[ ], size_t nops );				
					Returns: 0 if OK, -1 on error

- semid: semaphore ID.
- semoparray[]: 수행할 semaphore 연산 구조체 배열
- nops: 수행할 연산 개수

가) semop()의 P 연산

int p(int semid)
{
        struct sembuf pbuf;

        pbuf.sem_num = 0;		// first semaphore
        pbuf.sem_op = -1;		// want to enter critical section.
        pbuf.sem_flg = SEM_UNDO;	// will be automatically undone 
				// when the process terminates

        if (semop(semid, &pbuf, 1)==-1) {
                printf("p() operation is failed\n");
                return 0;
        } else {
                return 1;
        }
}

나) semop()의 V 연산

int v(int semid)
{
        struct sembuf vbuf;

        vbuf.sem_num = 0;		
        vbuf.sem_op = 1;	// adds this value to the semaphore value(semval).
        vbuf.sem_flg = SEM_UNDO;

        if (semop(semid, &vbuf, 1)==-1) {
                printf("v() operation is failed\n");
                return 0;
        } else {
                return 1;
        }
}

라. Example

- Code

#include <sys/ipc.h>
#include <sys/sem.h>
…

int p(int semid)
{
	struct sembuf pbuf;

	pbuf.sem_num = 0;
	pbuf.sem_op = -1;
	pbuf.sem_flg = SEM_UNDO;

	if (semop(semid, &pbuf, 1)==-1) {
		printf("p() operation is failed\n");
		return 0;
	}
    else {
		return 1;
	}
}

int v(int semid)
{
	struct sembuf vbuf;

	vbuf.sem_num = 0;
	vbuf.sem_op = 1;
	vbuf.sem_flg = SEM_UNDO;

	if (semop(semid, &vbuf, 1)==-1) {
		printf("v() operation is failed\n");
		return 0;
	}
    else {
		return 1;
	}
}

int initsem(key_t skey)
{
	int status = 0, semid;

	if ((semid = semget(skey, 1, IPC_CREAT | IPC_EXCL | 0666)) == -1) {
		if (errno = EEXIST)
			semid = semget(skey, 1, 0);
	}
    else
		status = semctl(semid, 0, SETVAL, 1);

	if (semid == -1 || status == -1) {
		printf("initsem is failed\n");
		exit(1);
	}
    else
		return semid;
}

void handlesem(key_t skey)
{
	int semid, pid = getpid();

	if((semid = initsem(skey)) < 0)
		exit(1);

	printf("\nprocess %d before critical section\n", pid);

	p(semid);
    
    // critical section
	printf("\nprocess %d is in critical section\n", pid);
	sleep(5);	
	printf("\nprocess %d is leaving critical section\n", pid);
    // critical section
	
    v(semid);

	printf("\nprocess %d is exiting\n", pid);
	exit(0);
}

int main(int argc, char **argv)
{
	key_t semkey = 0x200;

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

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

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

- Result

<참고 자료>
- 광운대학교 컴퓨터정보공학부 시스템프로그래밍 강의, 김태석(2020)