[시스템프로그래밍] 임계구역과 세마포어에 관하여

Critical Sections(임계 구역)

• 상호 배타적으로 실행되어야 하는 코드 세그먼트
  • 공유 장치(Shared devices)는 한 번에 한 프로세스에서 액세스해야 하므로 배타적 자원(exclusive resources)이라고 불림.

 

코드의 중요한 부분들

Entry Section(진입 구역)

• 공유 변수 또는 다른 자원을 수정할 권한을 요청하는 코드를 포함한다.

Critical Section(임계 구역)

• 공유 자원에 액세스하거나 재진입할 수 없는 코드를 실행하는 코드를 포함한다.

Exit Section(나가는 구역)

• Entry Section이 다음 실행 쓰레드가 임계 구역에 들어갈 수 있음을 알 수 있어야 해서 필요

Remainder Section(나머지 구역)

• 액세스를 해제한 후, 스레드는 실행할 다른 코드가 있을 수도 있다.

 

임계 구역 문제의 해결책

 

상호 배타성(Mutual Exclusion)

• 만약 프로세스 Pi가 자신의 임계 구역에서 실행 중이라면, 다른 프로세스는 자신의 임계 구역에서 실행 중일 수 없다

 

진행(Progress)

• 만약 어떤 프로세스도 자신의 임계 구역에서 실행 중이 아니고 자신의 잔여 구역에서 실행 중이지 않은 프로세스가 자신의 임계 구역에 진입하려고 하는 경우
  • 임계 구역에 들어갈 프로세스를 결정하는 데 참여할 수 있는 것은 자신의 나머지 구역에서 실행 중이지 않은 프로세스뿐이며, 이 선택은 무기한으로 연기될 수 없다.

 

제한된 대기(Bounded waiting) - 프로세스가 자신의 임계 구역에 진입하고 해당 요청이 승인되기 전에 다른 프로세스가 임계 구역에 진입하는 횟수에는 제한이 있어야 한다.

• 각 프로세스는 0이 아닌 속도로 실행된다고 가정한다.
• N 개의 프로세스의 상대 속도에 대한 가정은 없다.

Semaphores

상호 배제 및 동기화의 고수준 관리를 위한 두 가지 원자 연산, wait 및 signal을 가진 정수 변수

 

wait

• S > 0이면 S를 테스트하고 감소시킨다.
• S = 0이면 S를 테스트하고 호출자를 차단한다.

void wait(semaphore_t *sp){
	if( sp->value > 0 ) sp->value--;
	else{
		<add this thread to sp->list>
		<block>
	}
}

 

signal

• S에 대기 중인 스레드가 있다면, S = 0이 되고 대기 중인 스레드 중 하나를 차단 해제한다.
• 대기 중인 스레드가 없으면 S를 증가시킨다.

void signal(semaphore_t *sp){
	if( sp->list != NULL )
		<remove a thread from sp->list>
	else
		sp->value++;
}

 

wait 및 signal은 원자적(atomic)이어야 한다.

Critical section using semaphore 예시

S = 1일 때,

wait(&S);
<critical section>
signal(&S);
<remainder section>

초기에 S가 0이면,

→ wait(&S)는 차단되고 어떤 다른 프로세스가 signal을 호출하지 않으면 데드락이 발생한다.

초기에 S가 8이면, → 최대 여덟 개의 프로세스가 동시에 자신의 임계 구역에서 실행된다.

작업 순서를 강제하는 예제

Process 1 executes:
a;
signal(&sync)

Process 2 executes:
wait(&sync);
b;

프로세스 1이 문장 a를 실행한 후에 프로세스 2가 문장 b를 실행해야 한다.

→ 초기에 sync = 0이면, 프로세스 2는 자신의 대기를 차단하고 프로세스 1이 signal을 호출할 때까지 대기한다.

 

예시 2

Process 1 executes:
for( ; ; ){
wait(&S);
a;
signal(&Q);

Process 2 executes:
for( ; ; ){
wait(&Q);
b;
signal(&S);
}

초기에 S와 Q가 1이면,

• 어느 프로세스가 먼저 wait을 실행할지 모른다.
• 특정 프로세스는 다른 프로세스보다 최대 한 번의 반복만 더 진행된다.

만약 한 세마포어가 1이고 다른 하나가 0이면,

• 프로세스들은 엄격하게 번갈아가며 진행된다.

초기에 S와 Q가 모두 0이면,

• 데드락이 발생한다.

 

예시 3

Process 1 executes:
for( ; ; ){
wait(&Q);
wait(&S);
a;
signal(&S);
signal(&Q);
}

Process 2 executes:
for( ; ; ){
wait(&S);
wait(&Q);
b;
signal(&Q);
signal(&S);
}

초기에 S와 Q가 1이면,

• 결과는 프로세스가 CPU를 얻는 순서에 따라 달라진다.
• 만약 프로세스 1이 CPU를 얻고 wait(&Q)를 실행한 후에 CPU를 잃어버리고 프로세스 2가 들어오면,
  • 두 프로세스는 각자 두 번째 wait 호출에서 차단되고 데드락이 발생한다.

추가 설명

1. 프로세스 1이 CPU를 획득하고 Q에 대해 대기(wait)를 실행
2. 프로세스 2가 CPU를 획득하고 S에 대해 대기를 실행
3. 프로세스 1이 a를 실행한 후 S에 대한 대기를 실행
4. 프로세스 2가 b를 실행한 후 Q에 대한 대기를 실행

이제 두 프로세스는 각각 두 번째 wait 호출에서 차단되었고, 서로가 릴리즈되기를 기다리면서 데드락이 발생

→ 두 프로세스가 서로를 기다리면서 블록되었기 때문에 데드락이 발생

데드락을 피하기 위해서는 두 프로세스가 세마포어를 동일한 순서로 대기하도록 조정해야 한다.

 

POSIX:SEM Unnamed Semaphores

POSIX:SEM 세마포어는 sem_t 타입의 변수

• Named Semaphores와 Unnamed Semaphores가 있다.

구현이 unistd.h에서 _POSIX_SEMAPHORES를 정의하면 해당 구현은 POSIX:SEM 세마포어를 지원합니다.

세마포어 변수의 선언

#include<semaphore.h>

sem_t sem;

 

Initialization/Destroy

#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned value);
int sem_destroy(sem_t *sem);

POSIX:SEM 세마포어는 사용되기 전에 초기화되어야 한다.

sem_init()

• 'sem'에 의해 참조되는 무명 세마포어를 'value'로 초기화한다.
• 'value'는 음수일 수 없다.
• 'pshared'
  • 0이면 세마포어는 세마포어를 초기화한 프로세스의 스레드만 사용할 수 있다.
  • 0이 아니면 'sem'에 액세스할 수 있는 어떤 프로세스든 세마포어를 사용할 수 있다.
• 성공하면 0, 실패하면 -1 및 오류가 발생한 경우 errno가 설정된다.

파괴(destroy)

• unnamed 세마포어를 파괴합니다.
• 성공하면 0, 실패하면 -1 및 오류가 발생한 경우 errno가 설정된다.

 

sem_post, sem_trywait, sem_wait

#include <semaphore.h>
int sem_post(sem_t *sem);
int sem_trywait(sem_t *sem);
int sem_wait(sem_t *sem);

sem_post()

• 클래식한 세마포어 신호(signal)를 구현
• signal_safe하며 , 시그널 핸들러에서 호출될 수 있다.

sem_wait()

• 클래식한 세마포어 대기(wait)를 구현

sem_trywait()

• 세마포어 값을 감소하려고 할 때 세마포어 값이 0인 경우 차단 대신 -1을 반환하고 errno를 EAGAIN으로 설정

위 함수들은 성공하면 0, 실패하면 -1 및 오류가 발생한 경우 errno가 설정된다.

 

sem_getvalue()

#include <semaphore.h>
int sem_getvalue(sem_t *restrict sem, int *restrict sval);

• 세마포어의 값을 검사할 수 있게 해주며, 명명된(named) 또는 무명(unnamed) 세마포어의 값을 확인할 수 있다.
• 세마포어의 상태에 영향을 주지 않고, 'sval'이 참조하는 정수를 세마포어의 값으로 설정한다.
• 'sval'
  • 호출 중 어떤 지점에서 세마포어가 가진 값을 보유하고 있지만, 반환 시점의 값을 반드시 나타내지는 않습니다.
• 성공하면 0, 실패하면 -1 및 오류가 발생한 경우 errno가 설정된다.

#include <errno.h>
#include <semaphore.h>

static int shared = 0;
static sem_t sharedsem;

int initshared(int val) { 
	if (sem_init(&sharedsem, 0, 1) == -1)
		return -1;
	shared = val;
	return 0;
}

int getshared(int *sval) {
	while (sem_wait(&sharedsem) == -1)
		if (errno != EINTR)
			return -1;
	*sval = shared;
	return sem_post(&sharedsem);
}

int incshared() {
	while (sem_wait(&sharedsem) == -1)
		if (errno != EINTR) 
			return -1; 
	shared++;
	return sem_post(&sharedsem); 
}

• getshared() 함수는 변수의 현재 값을 반환한다.
• incshared() 함수는 원자적으로 변수를 증가시킨다.
• 만약 sem_wait()가 신호에 의해 중단된 경우 다시 시작한다.

 

추가설명

이 코드는 POSIX 세마포어를 사용하여 공유 변수를 관리하는 간단한 동기화 메커니즘을 구현한다. 세마포어는 크리티컬 섹션에 대한 동시 액세스를 제어하는 데 사용된다.

1. shared라는 정적 변수와 sharedsem이라는 세마포어가 정의되어 있습니다.
2. initshared(int val) 함수:
   • 세마포어 sharedsem을 초기화하고, 만약 초기화에 실패하면 -1을 반환합니다.
   • 세마포어를 이용하여 공유 변수 shared를 주어진 값 val로 초기화하고, 0을 반환합니다.
3. getshared(int *sval) 함수:
   • 세마포어 sharedsem을 이용하여 크리티컬 섹션에 진입합니다.
   • 세마포어가 대기 중에 EINTR(인터럽트)가 아닌 다른 오류가 발생하면 -1을 반환합니다.
   • 크리티컬 섹션에서 공유 변수 shared의 값을 sval에 저장합니다.
   • 세마포어를 빠져나오고, 세마포어의 포스트(post) 연산을 수행하여 다른 프로세스가 크리티컬 섹션에 진입할 수 있도록 합니다.
4. incshared() 함수:
   • 세마포어 sharedsem을 이용하여 크리티컬 섹션에 진입합니다.
   • 세마포어가 대기 중에 EINTR(인터럽트)가 아닌 다른 오류가 발생하면 -1을 반환합니다.
   • 크리티컬 섹션에서 공유 변수 shared를 증가시킵니다.
   • 세마포어를 빠져나오고, 세마포어의 포스트(post) 연산을 수행하여 다른 프로세스가 크리티컬 섹션에 진입할 수 있도록 합니다.

이 코드는 공유 변수의 안전한 동시 액세스를 보장하기 위해 세마포어를 사용하고 있습니다. 특히, 세마포어를 이용하여 크리티컬 섹션에 대한 상호 배제를 수행하고 있습니다.

 

POSIX:SEM Named Semaphores

• POSIX:SEM 명명된 세마포어는 메모리를 공유하지 않는 프로세스들 간에 동기화를 할 수 있다.
• 명명된 세마포어는 파일과 마찬가지로 이름, 사용자 ID, 그룹 ID, 그리고 권한을 갖는다.
• 만약 이름이 슬래시 (/)로 시작한다면, 해당 이름으로 세마포어를 열어 사용하는 두 프로세스나 스레드는 동일한 세마포어를 참조한다.
  • 슬래시로 시작하지 않는 경우, POSIX는 이름이 동일하게 참조되는 두 프로세스의 결과에 대한 특별한 규정을 하지 않는다.

sem_open()

#include <semaphore.h>
sem_t *sem_open(const char *name, int oflag, …);

명명된 세마포어와 sem_t 값 사이의 연결을 설정한다.

• name: 세마포어를 이름으로 식별하는 문자열
• oflag
  • 함수에 의해 세마포어가 생성되는지 또는 단순히 함수에 의해 액세스되는지를 결정한다.
  • O_CREAT이 설정된 경우,
    • 권한을 나타내는 mode_t 타입의 mode 및 세마포어의 초기값을 나타내는 unsigned 타입의 value라는 두 개의 추가 매개변수가 필요하다.
    • O_EXCL이 설정되지 않고 세마포어가 이미 존재하는 경우, 세마포어는 O_CREAT을 무시합한다.
  • O_CREATE와 O_EXCL이 설정된 경우,
    • 세마포어가 이미 존재하는 경우 에러를 반환합니다.
• 성공하면 세마포어의 주소를 반환하고, 실패하면 SEM_FAILED를 반환하고 errno를 설정한다.

O_CREAT과 O_EXCL에 대한 추가설명

O_CREAT과 O_EXCL는 파일 디스크립터를 오픈할 때 사용되는 플래그들로, sem_open() 함수에서 명명된 세마포어를 생성하거나 액세스할 때 사용됩니다.

1. O_CREAT:
   • O_CREAT 플래그는 파일이 존재하지 않는 경우 새로 생성하도록 지시합니다.
   • 세마포어를 생성할 때 사용되며, 세마포어가 이미 존재하지 않으면 새로 생성됩니다.
   • sem_open() 함수에 O_CREAT 플래그가 설정되면, 추가적인 매개변수로 권한(mode_t 타입의 mode)과 초기값(unsigned 타입의 value)이 필요합니다.
2. O_EXCL:
   • O_EXCL 플래그는 O_CREAT와 함께 사용될 때, 파일이 이미 존재하는 경우 에러를 발생시키도록 합니다.
   • 즉, 파일을 새로 생성하려는데 이미 해당 이름으로 존재하는 경우 에러를 반환합니다.
   • O_CREAT와 O_EXCL이 함께 사용되면, 세마포어가 이미 존재하는 경우 에러를 반환하며, O_EXCL 플래그가 없으면 단순히 해당 세마포어에 대한 연결을 엽니다.

예를 들어, 다음과 같이 사용될 수 있습니다:

sem_t *sem = sem_open("/my_semaphore", O_CREAT | O_EXCL, 0644, 1);

이는 "/my_semaphore"라는 이름의 세마포어를 생성하고, 만약 이미 존재한다면 에러를 발생시키도록 합니다. 권한은 0644이며, 초기값은 1입니다.

 

sem_close()와 sem_unlink()

#include <semaphore.h>
int sem_close(sem_t *sem);
int sem_unlink(const char* name);

• POSIX:SEM은 어떤 명명된 세마포어가 존재하는지 확인하는 방법을 제공하지 않는다.
  • 디렉터리 내용을 표시할 때 해당 세마포어가 나타날 수도 있고 나타나지 않을 수도 있다.
  • 시스템이 재부팅될 때 해당 세마포어가 파괴되거나 파괴되지 않을 수도 있다.
• sem_close()
  • 명명된 세마포어를 닫지만, 세마포어를 시스템에서 제거하지는 않는다.
  • 성공하면 0을 반환하고, 실패하면 -1을 반환하며 errno을 설정한다.
• sem_unlink()
  • 명명된 세마포어를 시스템에서 완전히 제거합니다. 단, 모든 프로세스가 명명된 세마포어를 닫은 후에 이루어져야 합니다.
  • sem_unlink 이후에 같은 이름으로 sem_open 호출하면, 다른 프로세스가 여전히 이전 세마포어를 열어놓은 경우에도 새로운 세마포어에 연결된다.
  • 다른 프로세스가 세마포어를 여전히 열어놓은 경우에도 항상 즉시 반환된다.
  • 성공하면 0을 반환하고, 실패하면 -1을 반환하며 errno을 설정한다.

 

Named Semaphore와 Unnamed Semaphore의 차이

1. 식별성 (Identification):
   • Named Semaphore:
     • 명명된 세마포어는 이름을 가지며 파일 시스템에 등록된다.
     • 프로세스 간에 공유할 때 이름을 사용하여 세마포어에 액세스한다.
   • Unnamed Semaphore:
     • 무명 세마포어는 이름이 없다.
     • 주로 관련 프로세스 또는 스레드 간에만 사용되며, 공유 메모리 영역에서만 접근 가능하다.
2. 접근성 (Accessibility):
   • Named Semaphore:
     • 다른 프로세스나 스레드가 같은 이름을 사용하여 접근할 수 있다.
   • Unnamed Semaphore:
     • 생성한 프로세스 또는 스레드와 그 자식 프로세스 또는 스레드 간에만 접근할 수 있다.
3. 삭제 (Deletion):
   • Named Semaphore:
     • sem_unlink를 통해 명명된 세마포어를 시스템에서 삭제할 수 있다.
     • 삭제 후에도 다른 프로세스가 세마포어에 접근할 수 있다.
   • Unnamed Semaphore:
     • 생성한 프로세스나 스레드가 종료되면 무명 세마포어는 자동으로 파괴된다.
4. 존속성 (Persistence):
   • Named Semaphore:
     • 프로그램 실행을 초과하여 존속된다. 시스템 재부팅 후에도 남아있을 수 있다.
   • Unnamed Semaphore:
     • 프로세스나 스레드의 생존 기간에만 존속된다.
5. 생성 및 접근 방법 (Creation and Access):
   • Named Semaphore:
     • sem_open 함수를 사용하여 생성하고 접근한다.
   • Unnamed Semaphore:
     • sem_init 함수를 사용하여 생성하고, 공유 메모리를 통해 접근한다.
6. 동기화의 범위 (Scope of Synchronization):
   • Named Semaphore:
     • 프로세스 간에 동기화를 제공하며, 이름을 통해 접근 가능하다.
   • Unnamed Semaphore:
     • 프로세스나 스레드 간에 동기화를 제공하며, 생성한 프로세스 또는 스레드와 그 자식 프로세스 또는 스레드 간에만 사용 가능하다.