세마포어(Semaphore)는 에츠허르 데이크스트라가 고안한, 두 개의 원자적 함수로 조작되는 정수 변수로서, 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법으로 사용된다. 이는 철학자들의 만찬 문제의 고전적인 해법이지만 모든 교착 상태를 해결하지는 못한다
구성
세마포어 S는 정수값을 가지는 변수이며, 다음과 같이 P와 V라는 명령에 의해서만 접근할 수 있다.
(P와 V는 각각 test와 increment를 뜻하는 네덜란드어 Proberen과 Verhogen의 머릿글자를 딴 것이다.)
P는 임계 구역에 들어가기 전에 수행되고, V는 임계 구역에서 나올 때 수행된다. 이 때 변수 값을 수정하는 연산은 모두 원자성을 만족해야 한다. 다시 말해, 한 프로세스(또는 스레드)에서 세마포어 값을 변경하는 동안 다른 프로세스가 동시에 이 값을 변경해서는 안 된다.
적용
방법 1) 최초 제시된 방법은 바쁜 대기(busy waiting)을 이용한 방법이다.
P(S) {
while S <=0
; // 아무 것도 하지 않음 (반복문)
S--;
}
V(S) {
S++;
}
이 방법은 임계 구역에 들어갈 수 있을 때까지 빈 반복문을 수행하기 때문에, 단일처리기 다중프로세스 환경에서 처리기 효율이 떨어진다. 또한 대기 중인 프로세스들 중 어느 것을 먼저 임계 구역에 진입시킬지를 결정할 수 없다.
방법 2) 최초 방법의 단점을 보완한 방법으로서 재움 큐를 활용하여 프로세스를 재우는 방식이다.
P(S) {
S--;
if S < 0
// 이 프로세스를 재움 큐에 추가 (잠 듬)
}
V(S) {
S++;
if S <= 0
// 재움 큐로부터 프로세스를 제거 (깨어남)
종류
1) 계수 세마포어
- 계수 세마포어(counting semaphore)에서는 초기값은 가능한 자원의 수로 정해지며, 세마포어 값의
범위는 정해져 있지 않다.
2) 이진 세마포어
이진 세마포어(binary semaphore)에서는 세마포어 값으로 0 또는 1을 가진다. 계수 세마포어보다
간단히 구현할 수 있으며, Test and Set 등 하드웨어가 지원하는 기능을 이용하여 구현하기도 한다.
또한, 이진 세마포어를 이용하여 계수 세마포어를 구현할 수도 있다.
약점
P함수와 V함수의 동작은 독립적이기 때문에 잘못 사용하는 경우, 문제가 발생한다.
P - 임계 구역 - P : 현재 프로세스가 임계 구역에서 빠져나갈 수 없게 된다. 또한 다른 프로세스들은 임계 구역에 들어갈 수 없으므로 교착 상태(Deadlock)가 발생한다.
V - 임계 구역 - P : 2개 이상의 프로세스가 동시에 임계구역에 들어갈 수 있으므로 상호 배제(Mutual Exclusion)를 보장할 수 없게 된다.
고급 언어에서 동기화를 제공해야 한다.
SUBJECT: semaphore란 ?
Description :
o 세마포어 (semaphore)란 (1) ?
- 동기화의 일반적인 방법인 세마포어 방법은 세마포어라는 정수 변수
(integer variable), 프로세스 대기열(process waiting queue),
P와 V의 두 명령으로 구성된다. 초기 상태의 변수값은 자원의 수와 같으며
대기열은 비어 있다. P명령은 변수의 값을 하나 줄인 후,
변수의 값이 0보다 작으면 프로세스를 대기열로 집어 넣는다.
반대로 0보다 크면 그 프로세스는 계속 진행된다.
V명령은 변수의 값을 하나 증가시킨다. 그 결과가 0보다 크면 프로세스는
계속되며 0보다 작으면 대기열의 프로세스 하나를 준비 상태로 만들고,
프로세스의 수행은 계속된다. 결국 변수의 값은 음수일 경우는 대기 중인
프로세스의 수를 나타내며, 양수이면 사용 가능한 자원의 수를 가리킨다.
위에서 동기화란 프로세스의 실행을 시간에 따라 순서적으로 처리하는 것을
동기화라 한다.
o 세마포어 (semaphore)란 (2) ?
- 다익스트라(E.J.Dijkstra)가 제안한 동시에 정보를 공유하여 수행되는
두 개 이상의 프로그램이나 프로세스에서 활동(activity)의 위치(coordination)를
설정해 주는 데 사용되는 동기화를 위한 기본 조작. 이는 두개 이상의
프로세스에 의해 공유되는 고유변수로 정의되는데, 보통의 방법으로는
다룰 수 없고 항상 P와 V라는 연산을 통해서만 액세스할 수 있다.
세마포어 sem이란 다음과 같은 연산이 허용된 정수형 변수를 말한다.
(P와 V란 이름은 wait와 signal이란 말의 네덜란드어에서 나온것으로
이때 signal이란 물론 UNIX의 signal호출과는 다르다.)
두 연산은 모두 원자화되어야 한다. 즉 sem을 변경할수 있는 프로세스는
한 순간에 오직 하나 뿐이다.
------------------------------------------------------------------------------------------------
| 컴퓨터가 여러 프로그램을 동시에 수행하는 다중 프로그래밍 시스템에서는 프로세스들간의 상호 |
| 배제와 동기화를 위한 기본적인 연산이 필요하다. 세마포어는 다익스트라가 제안한 프로세스 |
| 동기화를 위한 구조로, 이는 여러 프로세스들에 의해 공유되는 변수로 정의된다. |
| 그런데 이 변수는 보통의 방법으로는 액세스할 수 없고 오직 P와 V라는 연산으로만 다룰 수 있다. |
| P와 V연산의 정의는 다음과 같다. |
| |
| procedure P(S) --> 최초 S값은 1임 |
| while S=0 do wait --> S가 0면 1이 될때까지 기다려야 함 |
| S := S-1 --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함 |
| end P |
| |
| procedure V(S) --> 현재상태는 S가 0임 |
| S := S+1 --> S를 1로 원위치시켜 해제하는 과정. 이제는 다른 프로세스가 |
| end V 들어 올수 있음 |
| |
| P와 V는 쪼갤수 없는 단일 연산이다. |
| 즉 한 프로세스가 P나 V를 수행하고 있는 동안에는 프로세스가 인터럽트를 당하지 않는다. |
| 이제 P와 V를 사용하면 다음과 같이 위험지역(cirtical section)에 대한 상호배제를 구현할수 있다. |
| |
| P(S); |
| ----------------- |
| | 위 험 지 역 | |
| ----------------- |
| V(S); |
| |
| 최초에 S의 값은 1이다. 위와 같은 위험지역을 포함하는 두개의 프로세스 A와 B가 있다고 하자. |
| A와 B는 서로 독립적으로 수행되지만, 두 프로세스가 동시에 위험 지역으로 들어가서는 안된다. |
| 위와 같이 세마포어를 사용하면 P(S)를 먼저 수행하는 프로세스가 S를 0으로 해놓고 위험지역에 |
| 들어가므로 나중에 도착하는 프로세스는 P에서 더이상 진행되지 못하고 기다리게 된다. |
| 먼저 들어갔던 프로세스가 V(S)를 해주어야 비로서 P(S)에서 기다리던 프로세스가 위험지역에 |
| 들어갈 수 있고 따라서 상호배제가 실현된다. |
| 위의 예는 이진 세마포어 (binary semaphore)로, 단지 하나의 프로세스만이 위험지역에 들어갈 수 |
| 있도록 한다. 한편 S의 초기값을 N으로 하면 최대 N개의 프로세스가 P(S)를 통과할 수 있게 |
| 되는데 이러한 경우에는 계수 세마포어 (counting semaphore)라 하며 자원 할당에 사용한다. |
------------------------------------------------------------------------------------------------
UNIX 시스템 V에서 구현된 세마포어는 이러한 개념에 기초했지만 보다
일반적인(그리고 아마도 보다 복잡한)기능을 제공한다.
우선 semget과 semctl을 살펴보자.
<사용법>
#include
#include
#include
key_t key;
int sem_id, nsems, permflags, command;
int retval, sem_num;
union semun {
int val;
struct semid_ds *stat;
ushort *array;
} ctl_arg;
.
.
.
sem_id = semget(key, nsems, perflags);
retval = semctl(sem_id, sem_num, command, ctl_arg);
semget 호출은 msgget(get message queue)과 유사하다. 인수 nsems는
세마포어 집합에 필요한 세마포어의 갯수를 나타낸다.
따라서 UNIX 세마포어 연산은 세마포어 하나만이 아니라 한 집합 전체를
다루게 된다. 이로 인해서 나머지 세마포어 루틴에 대한 인터페이스가
복잡해진다.
semget호출이 성공하면 세마포어 집합 식별자라는 메시지 큐 식별자와 유사한
역할을 하는 것이 돌아온다. C 언어의 관습을 따라서 세마포어 집합에 대한
첨자는 0부터 nsems-1까지 있을 수 있다.
집합 내의 각 세마포어는 다음과 같은 값들을 갖게 된다.
. semval : 세마포어의 값으로서 항상 양수가 지정된다.
여기에 값을 새로 지정하려면 반드시 세마포어 시스템 호출을
통해야하며 프로그램에서 일반 자료형의 변수와 같이 직접
접근 할 수는 없다.
. sempid : 세마포어에 접근했던 최근의 프로세스의 프로세스 식별번호이다.
. semncnt : 세마포어의 값이 현재보다 증가하기를 기다리는 프로세스의 갯수
. semzcnt : 세마포어의 값이 0으로 되기까지 기다리는 프로세스의 갯수
정의에서 알 수 있듯이 함수 semctl은 msgctl보다 훨씬 복잡하다.
sem_id는 유효한 세마포어 식별자라야 한다.
command는 msgctl에서와 같이 수행해야 할 정확한 기능을 명시한다.
이 기능에는 세가지 유형이 있다. IPC_STAT와 같은 표준 IPC기능,
단일 세마포어만을 다루는 기능, 세마포어의 전체를 다루는 기능이 그것이다.
가능한 모든 기능을 다음과 같이 정리하였다.
semctl(semaphore control operations) 기능 코드
-----------------------------------------------------------------------------
표준 IPC기능 (semid_ds구조는 sem.h에 정의되어 있다.)
-----------------------------------------------------------------------------
IPC_STAT 상태정보를 ctl_arg.stat에 저장한다.
IPC_SET ctl_arg.stat에 저장된 형태로 소유권과 사용 허가권을 지정한다.
IPC_RMID 시스템에서 해당 세마포어의 집합을 삭제한다.
-----------------------------------------------------------------------------
단일 세마포어 연산 (이들은 retval에게 넘어온 값 sem_unm을 사용한다.)
-----------------------------------------------------------------------------
GETVAL 세마포어의 값 semval을 돌려준다.
SETVAL 세마포어 값을 ctl_arg.val로 지정한다.
GETPID sempid의 값을 돌려준다.
GETNCNT semncnt를 돌려준다.
GETZCNT semzcnt를 돌려준다.
-----------------------------------------------------------------------------
전체 세마포어 연산
-----------------------------------------------------------------------------
GETALL 모든 senvals의 값을 ctl_arg.array에 저장한다.
SETALL ctl_arg.array의 값을 사용하여 모든 semvals값을 지정한다.
-----------------------------------------------------------------------------
sem_num 인수는 semctl의 단일 세마포어 기능에서 특정 세마포어를 지정해준다.
마지막 인수인 ctl_arg는 세가지 구성 요소의 결합이다.
이들 구성 요소들은 각각 semctl의 세가지 기능에 대응한다.
semctl은 세마포어의 초기값을 지정할 때 요긴하게 사용된다.
이 기능은 semget에는 없음에 주의하라.
따라서 semget과 semctl은 두개 모두 있어야 한다.
다음에 예로서 제시하는 함수는 프로그램이 단일 세마포어를 생성할때나
이에 대한 세마포어 집합 식별자를 얻고자 할 때 사용될 수 있다.
세마포어가 생성되는 경우에는 semctl을 사용하여 초기값을 부여하게 된다.
/* initsem -- semaphore initialization */
#include "pv.h"
initsem(semkey)
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 /* if created... */
status = semctl(semid, 0, SETVAL, 1);
if ((semid == -1 || status == -1) {
perror("initsem failed");
return (-1);
}else
return semid; /* all okay */
}
include 화일 pv.h는 다음과 같다.
/* semaphore example header file */
#include
#include
#include
#include
extern int errno;
#define SEMPERM 0600
#define TRUE 1
#define FALSE 0
세마포어 연산 : semop 호출
- semop 호출 semop은 기본적인 세마포어 연산을 실제로 수행하는 시스템호출이다.
이때 semop은 메뉴얼의 항목이 아니라 실제 함수 이름이다.
사용법
#include
#include
#include
int retval, sem_id;
struct sembuf op_array[SOMEVALUE];
.
.
retval = semop(sem_id, op_array, SOMEVALUE);
sem_id는 세마포어 집합 식별자로서 이전에 semget호출을 통해 값이 지정되어야
한다. op_array는 sembuf구조의 배열로서 sembuf구조는 sem.h에 정의되어 있다.
SOMEVALUE는 임의의 정수형 상수이다.
각각의 sembuf구조 변수는 세마포어에 대해 수행할 연산을 지정한다.
다시 강조하거니와 semop함수가 세마포어 집합에 대해 수행하는 일련의 연산들은
모두 원자화 되어야 한다. 즉, 그중의 한 연산이라도 수행할 수 없다면 전체 연산
이 모두 수행되지 말아야 한다. 이 경우에는 특별히 명시되지 않는한,
모든 연산이 한번에 수행될수 있을때까지 프로세스의 수행이 중지된다.
sembuf구조를 좀더 자세히 보면 다음과 같이 구성되어 있다.
--------------------------------------------------------------------
| struct sembuf { |
| short sem_num; /* semaphore # */ |
| short sem_op; /* semaphore operation */ |
| short sem_flg; /* operation flags */ |
--------------------------------------------------------------------
sem_num는 집합 내의 세마포어에 대한 첨자를 저장한다. 만약 집합의 원소가
하나뿐이라면 sem_num의 값은 0이어야 한다. sem_op는 함수 semop이 수행해야
하는 기능을 정수로서 나타낸다.
여기에는 세가지 경우가 있다.
경우 1 : sem_op가 음수일때
이 경우에는 앞서 소개했듯이 일반적인 세마포어 명령 P()와 같이 수행된다.
이를 의사 코드(pseudo-code)로 나타내면 다음과 같다
(ABS는 변수의 절대값을 나타낸다)
if (semval >= ABS(sem_op)){
set semval to semval-ABS(sem_op)
} else {
if ((sem_flg&IPC_NOWAIT))
return-1 immediately
else{
wait until semval reaches or exceeds
ABS(sem_op), then subtract
ABS(sem_op) as above
}
}
기본 개념은 함수 semop에서 sem_num이 가리키는 세마포어의 값 semval을
조사하는 것이다.
semval의 값이 충분히 크다면 즉시 하나 감소시킨다. 아니면 semval이 충분히
커질 때까지 프로세스의 수행을 중단시킨다. 그러나 sem_flg의 IPC_NOWAIT
플래그의 값이 1로 되어 있으면 sem_op은 즉시 -1을 되돌려주고 errono값을
EAGAIN으로 한다.
경우 2 : sem_op이 양수일 때
이때는 보통의 V()연산과 유사하다. 즉 sem_op의 값을 해당 semval에 더해준다.
이때 해당 세마포어의 값이 증가하기를 기다리는 프로세스들이 깨어나게 된다.
경우 3 : sem_op이 0일때
이 경우는 semval을 변환시키는 것이 아니라 값이 0이 될때까지 기다린다.
semval이 0이 아니고 sem_flg의 IPC_NOWAIT가 1인 경우에 semop는 즉시 오류
값을 돌려주게 된다.
SEM_UNDO 플래그
- 이것은 sembuf구조의 구성요소 sem_flg에 있는 플래그의 하나이다.
이는 프로세스의 수행이 끝났을 때 시스템이 수행된 연산을 자동적으로
취소하도록 지시한다. 수행된 일련의 연산을 추적하기 위하여 시스템은
세마포어에 semadj라는 정수를 대응시킨다.
이때 semadj변수는 프로세스마다 할당되어야 함에 주의해라.
따라서 서로 다른 프로세서는 동일한 세마포어에 대해 독립적인 semadj값을
유지하게 된다. SEM_UNDO의 값을 1로 하고서 semop연산을 수행하면
semadj값에서 sem_num값을 뺀다.
이때 sem_num의 부호가 중요한데 이는 sem_num의 값이 양수인가 음수인가에
따라 semadj의 값이 감소하거나 증가하기 때문이다. 프로세스의 수행이 끝나면
시스템은 semadj값을 해당 세마포어에 더해줌으로써 지금까지의 모든
semop호출 효과를 상쇄시킨다. 일반적으로 볼때 프로세스가 지정한 값이
해당 프로세스의 종료 후에도 효력을 갖지 않는다면 SEM_UNDO가 사용되어야만
한다.
세마포어의 예
- 이제 initsem루틴으로 시작한 예를 완성해 보자. 여기서는 전통적인 세마포어
연산을 P()와 V()로 구현하여 이를 중심으로 삼았다. 우선 P()를 보자.
/* pc -- semaphore p operation */
#include "pv.h"
p(semid)
int semid;
{
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);
} else
return(0);
}
이때 SEM_UNDO를 사용했음에 주의하라. V()는 다음과 같다.
/* v.c -- semaphore v operation */
#include "pv.h"
v(semid)
int semid;
{
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);
} else
return(0);
}
이제 비교적 간단한 이들 루틴으로 상호 배제를 구현해보자.
다음의 프로그램을 살펴보자.
/* testsem -- test semaphore routines */
#include "pv.h"
main()
{
key_t semkey = 0x200;
if(fork() == 0)
handlesem(semkey);
if(fork() == 0)
handlesem(semkey);
if(fork() == 0)
handlesem(semkey);
}
handlesem(skey)
key_t skey;
{
int semid, 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);
/* in real life do something interesting */
sleep(10);
printf("process %d leaving critical section\n", pid);
v(semid);
printf("process %d exiting\n", pid);
exit(0);
}
testsem은 세개의 자식프로세스를 생성하고 , 이들은 p()와 v()를 사용하여
임계 영역에는 한 순간에 둘 이상이 들어있지 못하도록 한다.
한 컴퓨터에서 testsem을 수행시킨 결과는 다음과 같다.
process 799 before critical section
process 800 before critical section
process 801 before critical section
process 799 in critical section
process 799 leaving critical section
process 799 exiting
process 801 in critical section
process 801 leaving critical section
process 801 exiting
process 800 in critical section
process 800 leaving critical section
process 800 exiting
o Critical secion 란 ?
- 다중 프로그래밍 운영체제에서 여러 프로세스가 데이타를 공유하면서 수행될 때
각 프로세스에서 공유 데이타를 액세스하는 프로그램 코드 부분을 가리키는 말.
공유데이타를 여러 프로세스가 동시에 액세스하면 시간적인 차이 때문에 잘못된
결과를 만들어 낼 수 있기 때문에 한 프로세스가 위험 부분을 수행하고 있을 때,
즉 공유 데이타를 액세스하고 있을 때는 다른 프로세스들은 절대로 그 데이타를
액세스하지 못하도록 하여야 한다.
o Mutual exclusion (상호 배제)란(1) ?
- 프로세스의 상호 교신에 대한 기본적인 조치는 공용 부분을 여러 프로세스가
동시에 사용하는 것을 배제하는 것이었다. 시스템의 어떠한 자원을 한 시점에서
한개의 프로세스만이 사용할 수 있도록 하는 것을 상호배제라 한다. 또한,
프로그램에서 이러한 자원을 사용하거나 혹은 그 내용을 변경하는 부분을
위험부분 (critical section)이라 하며, 둘 이상의 프로그램에서 이 위험
부분이 동시에 수행되지 않도록 하는 것이 상호 배제의 기능이다.
o Mutual exclusion (상호 배제)란(2) ?
- 다중 프로그래밍 시스템에서 여러 프로세스가 하나의 공유 데이타를 액세스하면서
작업을 할 때, 한 프로세스가 그 데이타를 액세스할 때는 다른 프로세스들은
그것을 사용하지 못하도록 하는 운영체제의 기능.
예를 들어 한 프로세스가 어떤 화일에 데이타를 쓰고 있을 때 다른 프로세스가
그 화일을 지원버린다면 많은 문제가 발생할 것이다. 상호 배제는 한번에
한 프로세스만이 공유 데이타를 액세스할 수 있도록 해 주는 것으로,
다중프로그래밍 시스템의 운영체제가 꼭 갖추어야 할 기능이다.
Revision History
작성일자 : 96.10.10
작성자 : 이진수
