Szemaforok (semaphores)
Olyan jelek, amelyek megmutatj�k, hogy egy folyamat v�grehajthat-e egy programr�szt vagy sem...
Szemafor adatainak lek�rdez�se,
m�dos�t�sa �s t�rl�se (semctl)
Szemafor �rt�k�nek n�vel�se �s
cs�kkent�se
(semop)
A processzor maxim�lis kihaszn�l�sa �rdek�ben az oper�ci�s rendszerek jelentős r�sze � �gy a Unix is � enged�lyezi a folyamatoknak a p�rhuzamos (egyidőben t�rt�nő) fut�st. Ez a megold�s igen hat�kony, de mi t�rt�nik akkor, ha k�t folyamat egyidőben pr�b�lja el�rni ugyanazt az erőforr�st? Ilyen "�rz�keny" erőforr�sok p�ld�ul a nyomtat� vagy a mem�ria, amelyet egyszerre csak egy folyamat haszn�lhat, k�l�nben a műveletnek előre nem l�that� k�vetkezm�nyei lehetnek.
Kritikus szakasznak nevezz�nk teh�t egy olyan m�dos�t�st a rendszeren, amelyet nem szabad megszak�tani. A kritikus szakasz erőforr�shoz k�t�tt (p�ld�ul a nyomtat�hoz).
A szemaforok lehetőv� teszik a felhaszn�l�k sz�m�ra a folyamatok szinkroniz�l�s�t. �ltal�ban a szemafor egy eg�sz v�ltoz�, amelyhez hozz�rendel�nk egy e0(v) kezdeti �rt�ket, egy e(v) aktu�lis �rt�ket �s egy e0(v) v�rakoz�si sort.
Az al�bbiakban bemutatjuk a legismertebb szinkroniz�ci�s P �s V elj�r�sokat.
P(v)
{
e(v) = e(v) - 1;
if (e(v) < 0)
{
folyamat_allapota = WAIT;
f(v) sorba <- folyamat;
}
}
V(v)
{
e(v) = e(v) + 1;
if (e(v) <= 0)
{
folyamat <- f(v) sorb�l;
kivalasztott_folyamat_allapota = READY;
}
}
A szemafor aktu�lis �llapot�t a k�vetkező k�plet adja:
e(v) = e0(v) + n�V(v) � n�P(v)
ahol:
n�V(v) � a v szemaforon v�grehajtott V elj�r�sok sz�ma,
n�P(v) � a v szemaforon v�grehajtott P elj�r�sok sz�ma.
Teh�t egy kritikus szakasz megval�s�t�sa a k�vetkezők�ppen t�rt�nik: a szemafor kezdeti �rt�ke 1 lesz, a kritikus szakaszt pedig a P �s V elj�r�sok hat�rolj�k k�r�l.
P(v)
kritikus szakasz
V(v)
folyamat t�bbi r�sze
Megjegyezz�k, hogy a P �s V elj�r�s �s �ltat�ban a szinkroniz�l� elj�r�sok feloszthatatlanok (atomi műveletek).
A UNIX System V verzi�ban a szemafor fogalm�t �ltal�nos�tott�k. Ez�rt egy szemafor eset�ben egyid�ben ak�r t�bb műveletet is megadhatunk (a P �s V elj�r�sok m�s-m�s időben h�v�dnak meg a folyamaton bel�l), �s az e(v) �rt�k�nek n�vel�se vagy cs�kkent�se nem felt�tlen�l 1-el kell t�rt�njen. Minden a rendszer �ltal v�grehajtott művelet feloszthatatlan. Teh�t ha a rendszer nem tudja elv�gezni a folyamat �ltal k�rt �sszes műveletet, nem v�gzi el egyiket sem, �s a folyamat v�rakoz�si �llapotba ker�l eg�szen az �sszes művelet v�grehajt�s�ig.
Egy folyamat l�trehozhat egy eg�sz szemafork�teget. A k�tegnek van egy bemenete a szemafort�bl�ban, amely a szemafork�teg fejl�c�t tartalmazza. A folyamathoz rendelt t�bl�zat pontosan annyi elemből �ll, amennyi szemafor tartozik a k�teghez. Minden elem megőrzi az illető szemaforhoz rendelt �rt�ket.
A szemaforok kezel�se nagyon hasonl�t az osztott mem�ria �s az �zenetsorok kezel�s�hez. Ez�rt egy folyamatnak csak akkor van joga hozz�f�rni egy szemaforhoz, ha ismeri a hozz�rendelt kulcsot. Belsőleg a szemafork�teget egy eg�sz sz�mmal azonos�tjuk, ez�rt a folyamat b�rmelyik szemaforhoz hozz�f�rhet
Teh�t minden szemafork�tegnek van egy azonos�t�ja (amely egy pozit�v eg�sz sz�m) �s egy semid_ds t�pus� adatszerkezete.
struct
semid_ds
{
struct ipc_perm sem_perm; /* defini�lja
a jogokat �s a tulajdonost
*/
struct sem *sem_base; /* pointer
az első szemaforra a k�tegből */
int sem_nsens;
/* a k�tegben tal�lhat�
szemaforok sz�ma */
time_t sem_otime;
/* utols� semop() művelet
ideje */
time_t sem_ctime;
/* utols� strukt�ram�dos�t�s
ideje */
};
Egy folyamat csak akkor f�rhet hozz� egy szemafork�teghez ha:
- a folyamat a superuser-�,
- a felhaszn�l� ID-je (uid) megegyezik az sem_perm.cuid-vel vagy az sem_perm.uid-vel �s az sem_perm.mode tartalmazza a k�v�nt jogokat,
- a felhaszn�l� csoportazonos�t�ja (gid) megegyezik az sem_perm.cgid vagy sem_perm.gid �rt�kek egyik�vel �s az sem_perm.mode tartalmazza a k�v�nt jogokat,
- a felhaszn�l� beleesik a "t�bbi felhszn�l�" kateg�ri�ba �s az sem_perm.mode tartalmazza a megfelelő jogokat.
Egy szemaforhoz rendelt adatszerkezet a k�vetkező:
struct
sem
{
ushort semval; /* a
szemafor �rt�ke (semval>=0)
*/
pid_t sempid; /* utols�,
műveletet v�gző folyamat ID-ja
*/
ushort semncnt; /* azon
foly. sz�ma, amelyek a semval n�veked�s�t v�rj�k
*/
ushort semzcnt; /* azon
foly. sz�ma, amelyek a semval=0-t v�rj�k
*/
};
L�trehoz�s (semget)
A semget rendszerf�ggv�ny lehetőv� teszi egy szemafork�teg ID-j�nak a meghat�roz�s�t. Ha a szemafork�teg előzőleg nem l�tezett, a f�ggv�ny l�trehozza azt. F�ggetlen�l att�, hogy a k�teg l�tezett-e vagy sem a folyamatnak ismernie kell a szemaforhoz rendelt kulcsot. A f�ggv�ny alakja:
#include
<sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
int semget(key_t key, int nrsem, int flg);
A f�ggv�ny visszat�r�si �rt�ke az �jonnan l�trehozott vagy egy r�gi szemafor azonos�t�ja, illetve -1 hiba eset�n. A key v�ltoz�ban a szemaforhoz rendelt kulcsot kell megadni, m�g az flg-ben a l�trehoz�si tev�kenys�get �s a hozz�f�r�si jogokat. A kulcsot a szemafort haszn�l� �sszes folyamatnak ismernie kell. Az nrsem argumentum a k�tegben tal�lhat� szemaforok sz�m�t jelenti. Ha egy �j k�teget hozunk l�tre meg kell adnunk a v�ltoz� �rt�k�t, ha viszont egy m�r l�tező k�tegre hivatkozunk az nrsem �rt�ke 0 lesz.
Egy �j szemafork�teg l�trehoz�sa eset�n az flg mezőt a k�vetkező form�ban kell megadni:
IPC_CREAT | IPC_EXCL | hozz�f�r�si_jogok
Ha az IPC_EXCL nincs be�ll�tva, akkor ha m�r l�tezik egy előzőleg l�trehozott k�teg a megadott kulcsra, a program nem jelez hib�t, hanem visszaadja a l�tező k�teg ID-j�t.
P�lda egy szemafork�teg l�trehoz�s�ra:
#define KEY 2003
int
semid;
semid = semget((key_t) KEY, 5, IPC_CREAT | 0666);
Ha csak a szemafork�teg azonos�t�j�ra vagyunk k�v�ncsiak, a semget h�v�sakor adjuk meg a kulcsot, a t�bbi param�ternek pedig 0 �rt�ket.
semid = semget((key_t) KEY, 0, 0);
L�trehoz�skor a t�rs�tott adatstrukt�ra (sem_perm) mezői a k�vetkező inform�ci�kkal t�ltődnek fel:
-
sem_perm.cuid, sem_perm.uid
� a semget f�ggv�nyt megh�v� folyamathoz hozz�rendelt felhaszn�l� ID-ja,
- sem_perm.cgid, sem_perm.uid
� a semget f�ggv�nyt megh�v� folyamathoz hozz�rendelt felhaszn�l�csoport
ID-ja,
- sem_perm.mode � a
semget f�ggv�ny h�v�sakor megadott flg argumentum, amely a hozz�f�r�si
jogokat tartalmazza,
- sem_nsems � a
semget f�ggv�ny h�v�sakor megadott szemaforok sz�ma,
- sem_ctime � az
aktu�lis időt tartalmazza,
- sem_otime � �rt�ke
0.
Előfordulhat, hogy egy szemafork�teghez nincs hozz�rendelt kulcs. Ebben az esetben a k�teg l�trehoz�sakor a semget f�ggv�ny key param�terek�nt az IPC_PRIVATE szimbolikus konstanst kell megadni.
Szemafor adatainak lek�rdez�se, m�dos�t�sa �s t�rl�se (semctl)
A semctl f�ggv�ny a szemafork�tegek szintj�n az inform�ci�k lek�rdez�s�re, m�dos�t�s�ra �s t�rl�s�re haszn�lhat�. Szintaxisa:
#include
<sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
int semctl(int semid, int nrsem, int cmd, union semun arg);
A f�ggv�ny visszat�r�tett �rt�ke az �sszes GET parancs kimeneti �rt�ke, kiv�telt k�pez a GETALL parancs. Minden m�s esetben a f�ggv�ny �rt�ke 0.
A semid param�ter a semget f�ggv�ny �ltal meghat�rozott szemafork�teg azonos�t�ja, m�g az nrsem annak a szemafornak a sz�ma, amelyen v�gre szeretn�nk hajtani a cmd műveletet.
A cmd argumentum teh�t a k�v�nt műveletet hat�rozza meg �s a k�vetkező �rt�keket veheti fel:
- GETVAL � a f�ggv�ny visszat�r�ti a semval �rt�k�t az nrsem �ltal meghat�rozott szemaforban,
- SETVAL � az nrsem �ltal meghat�rozott szemafor semval param�ter�nek �rt�ke arg.val lesz,
- GETPID � a f�ggv�ny visszat�r�ti a sempid �rt�k�t az nrsem �ltal meghat�rozott szemaforban,
- GETNCNT � a f�ggv�ny visszat�r�ti a semncnt �rt�k�t az nrsem �ltal meghat�rozott szemaforban,
- GETZCNT � a f�ggv�ny visszat�r�ti a semzcnt �rt�k�t az nrsem �ltal meghat�rozott szemaforban,
- GETALL � minden szemafor semval �rt�k�t elhelyezi az arg.array t�mbben,
- SETALL � minden szemafor semval �rt�k�t felt�lti az arg.array t�mbben megadott �rt�kekkel,
- IPC_STAT � a semid_ds strukt�ra elemeit lementi az arg.buf t�mbbe,
- IPC_SET � a sem_perm.uid, a sem_perm.gid �s a sem_perm.mode mezők �rt�keit friss�ti az arg.buf t�mbben megadott �rt�kekkel,
- IPC_RMID � a szemafork�teg t�rl�se; a t�rl�s azonnali, teh�t minden ezt a szemafor haszn�l� folyamat egy EIDRM �zenetet kap, �s hib�val le�ll.
Az arg vari�ns t�pus� v�ltoz�, amely a cmd parancs �ltal felhaszn�lt argumentumokat tartalmazza:
union
semun
{
int val;
/* a SETVAL-hoz
*/
struct semid_ds *buf; /* az
IPC_STAT-hoz �s az IPC_SET-hez
*/
ushort *array; /* a
GETALL-hoz �s a SETALL-hoz
*/
}
Szemafor �rt�k�nek n�vel�se �s cs�kkent�se (semop)
A semop f�ggv�ny feladata egy szemafork�teg egy elem�nek n�vel�se �s cs�kkent�se. Szintaxisa:
#include
<sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
int semop(int semid, struct sembuf op[], size_t nrop);
A f�ggv�ny visszat�r�si �rt�ke 0, ha a művelet sikeres volt, ellenkező esetben -1. A semid a semget �ltal meghat�rozott szemafork�teg azonos�t�ja.
Az op egy mutat� nrop darab sembuf t�pus� strukt�r�hoz, ahol:
struct
sembuf
{
ushort sem_num; /* a
k�tegben levő szemaforok sz�ma
*/
short sem_op; /* v�grehajtand�
művelet */
short sem_flg; /* v�grehajt�si
k�r�lm�nyek */
}
Teh�t minden szemafor eset�n a v�grehajtand� műveletet a sem_op mező jelzi. Ha:
- sem_op < 0
a. Ha semvan >= |sem_op|, akkor semval = semval - |sem_op|. Ez biztos�tja, hogy a szemafor �ltal visszat�r�tett �rt�k >= 0.
b. Ha (semval < |sem_op|) & (sem_flg & IPC_NOWAIT) = true, akkor a f�ggv�ny egy hibak�dot t�r�t vissza.
c. Ha semval < |sem_op| �s az IPC_NOWAIT nincs megadva, akkor a folyamat le�ll, am�g a k�vetkezők k�z�l valamely felt�tel nem teljes�l:
- semval >= |sem_op| (egy m�sik folyamat felszabad�t p�r erőforr�st),
- a szemafor t�rlődik a rendszerből; a f�ggv�ny ebben az esetben -1 �rt�ket t�r�t vissza �s errno=ERMID,
- ha egy folyamat egy jel lekezel�se ut�n visszat�r, a semncnt �rt�ke a szemaforban cs�kken, �s a f�ggv�ny -1-et ad vissza (errno=EINTR).
- sem_op > 0
Ekkor semval = semval + sem_op.
- sem_op = 0
a. Ha a semval = 0, akkor a f�ggv�ny azonnal befejeződik.
b. Ha a semval ≠ 0 �s az IPC_NOWAIT be van �ll�tva, akkor a f�ggv�ny -1-et ad vissza �s az errno=EAGAIN.
c. Ha a semval ≠ 0 �s az IPC_NOWAIT nincs be�ll�tva, akkor a folyamat le�ll, ameddig a semval 0 nem lesz, vagy a szemafork�teg megsemmis�l, vagy a folyamat egy jelet kap.
A k�vetkezőkben megn�zz�k, hogyan lehet implement�lni a P �s V elj�r�sokat:
pv.c
static
void semcall(int semid, int op)
{
struct sembuf pbuf;
pbuf.sem_num = 0;
pbuf.sem_op = op;
pbuf.sem_flg = 0;
if (semop(semid, &pbuf, 1) < 0)
err_sys("semop hiba");
}
void
P(int semid)
{
semcall(semid, -1);
}
void
V(int semid)
{
semcall(semid, 1);
}
Az�rt, hogy a P �s a V elj�r�sok műk�d�s�t jobban meg�rts�k tekints�k a k�vetkező p�ld�t.
�rjunk folyamatot, amely h�rom gyereket hoz l�tre. Mindenik gyerek hozz� szeretne f�rni egy k�z�s erőforr�shoz. A kritikus szakasz 10 m�sodpercig tart. (A val�s�gban a kritikus szakasznak sokkal r�videbbnek kell lennie.) A szemafor biztos�tja minden folyamat egy�ni hozz�f�r�s�t a kritikus szakaszban. A tesztprogram a k�vetkező:
#include
<sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include "pv.c"
/* a fent defini�lt P
�s V elj�r�sok */
#define SEMPERM 0600 /* hozz�f�r�si jogok */
void
rut_sem(int semid);
int initsem(key_t semkey);
void
main(void)
{
key_t semkey =
0x200; /* kulcs
*/
int semid, i;
semid = initsem(semkey);
/* szemafor l�trehoz�sa
*/
for (i=0; i<3; i++)
/* 3 darab
gyerekfolyamat l�trehoz�sa
*/
if (fork() == 0)
rut_sem(semid);
/* erőforr�si k�relmek
a gyerekfolyamatokt�l */
}
void
rut_sem(int semid)
/* szemaforok megval�s�t�sa
*/
{
pid_t pid;
pid = getpid();
/* gyerekfolyamat
PID-je */
P(semid);
/* bel�p�s a kritikus
szakaszba */
printf("a %d folyamat kritikus szakaszban van\n", pid);
sleep(random()%5); /* kritikus szakasz; v�rakoz�s */
printf("a %d folyamat elhagyja a kritikus szakaszt\n", pid);
V(semid);
/* kil�p�s a kritikus
szakaszb�l */
exit(0);
/* gyerekfolyamat v�ge
*/
}
int
initsem(key_t semkey)
{
int semid;
/* szemafor l�trehoz�sa
*/
semid = semget(semkey, 1, SEMPERM | IPC_CREAT);
if (semctl(semid, 0, SETVAL, 1) < 0)
err_sys("semctl
hiba"); /* szemaforok
sz�ma = 1 */
return semid;
/* szemafor ID-j�nak
visszat�r�t�se */
}
A k�vetkező tesztesetek is bizony�tj�k, hogy egy bizonyos időpillanatban csak egyetlen folyamat lehet a kritikus szakaszban.
$
a.out
a 790 folyamat kritikus szakaszban van
a 790 folyamat elhagyja a kritikus szakaszt
a 791 folyamat kritikus szakaszban van
a 791 folyamat elhagyja a kritikus szakaszt
a 792 folyamat kritikus szakaszban van
a 792 folyamat elhagyja a kritikus szakaszt
Osztott mem�ria (shared
memory)
Copyright (C) Buzog�ny L�szl�, 2002
Defin�ci�