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)
Üzenetsorok (message queues)
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
A posixos szemafor tipus a sem_t . A következő képpen jelentjük be a sem_name nevű szemafort:
#include <semaphore.h>
sem_t sem_name;
Szemafor értékének inicializálása (sem_init)
#include <semaphore.h>
int sem_init( sem_t *sem, int pshared, unsigned value );
Argumentumok:
·
sem: Szemaforra mutató pointer
·
pshared: flag ami mutatja, hogy
fork eseten megosztjuk a szemafort vagy nem. Linux szalak egyenlore nem tudjak
kezelni
·
value: erre az ertekre szeretnenk
bealitani
Példa sem_init –re:
sem_init(&sem_name, 0, 10); //sem_name szemafort bealitja 10-re
Várakozás szemaforra (sem_wait)
A sem_wait függvény segítségével várakozhatunk egy szemaforra.
Működése:
Ha a szemafor értéke negatív akkor blokkolja a hívó folyamatot, ellenkező esetben csökkenti a szemafor értékét.
Szintaxis:
int sem_wait(sem_t *sem);
Példa:
sem_wait(&sem_name); //amennyiben a sem_name szemafor értéke
pozitív akkor csökkenti
// különben blokkolja a hívó folyamatot.
Szemafor értékének növelése (sem_post)
Működése:
Növeli a szemafor értékét (eggyel).
Amennyiben valamelyik folyamat blokkolva maradt és vár, akkor ez értesíti és felkelti folyamat "felkelti".
Ha több folyamat is várakozik a szemaforra, akkor azt értesiti amelyiknek a prioritása a legnagyobb a rendszerbe.
Szintaxis:
#include <semaphore.h>
int sem_post( sem_t *sem );
Például:
sem_post(&sem_name); //növeli a sem_name szeamfor értékét
1-el,
Szemafor értékének csökkentése blokkolás nélkül (sem_trywait)
Vár egy szemaforra de nem blokkolja.
Ha a szemafor érteke pozitív akkor csökkenti, különben egyszerűen visszatér (return).
Szintaxis:
#include <semaphore.h>
int sem_trywait( sem_t *sem );
Például:
sem_trywait(&sem_name);
Szemafor értékének lekérdezése (sem_getvalue)
Lekérdezi a szemafor értékét.
Szintaxis:
int sem_getvalue(sem_t *sem, int *valp);
Paramétezés:
sem mutató által mutatott szemafor értékét lekéri valp mutató által mutatott int vátozóba.
Példa:
int value;
sem_t sem_name;
sem_getvalue(&sem_name, &value);
printf("A szemafor erteke %d\n", value);
Szemafor törlése(sem_destroy)
A sem_destroy() törli a szemafort. Ajánlatos csak akkor törölni, ha már semmi nem használja az illető szemafort.
Szintaxis:
int sem_destroy(sem_t *sem); //kitörli a sem mutató által
mutatott szemafort
Példa:
sem_destroy(&sem_name)
A szemaforok használatának klasszikus
példája a termelő-fogyasztó problémája,
amit én a következő képpen implementáltam, POSIX szemaforokkal:
header.h
#include
<stdio.h>
#include
<unistd.h>
#include
<string.h>
#include
<stdlib.h>
#include
<sys/types.h>
#include
<sys/ipc.h>
#include
<sys/shm.h>
#include
<sys/sem.h>
#include
<pthread.h>
#include
<semaphore.h>
#define
BUFFER_SIZE 10
#define
SHARED_MEMORY_KEY 1077
#define
SHARED_MEMORY_SIZE 2048
#define
SEMAPHORE_KEY 1077
#define
URES_SZEMAFOR 0
#define TELE_SZEMAFOR
1
typedef
struct{
int buffer[BUFFER_SIZE];
sem_t ures; //ures
helyek szamat jelzo szemafor. kezdetben: BUFFER_SIZE
sem_t tele; //tele
helyek szamat jelzo szemafor. kezdetben: 0.
sem_t pmut; //termelok
mutexe. biztositja,hogy egyszerer csak egy folyamat termeljen.
sem_t cmut; //fogyasztok
mutexe. biztositja,hogy egyszerer csak egy folyamat fogyasszon.
int nextin; //kovetkezo
termeles helye
int nextout; //kovetkezo
fogyasztas helye
} osztottMemoriaTipus;
int
lekerOsztottMemoriaID(){
int shmid = shmget((key_t) SHARED_MEMORY_KEY,
SHARED_MEMORY_SIZE, IPC_CREAT | 0666);
//ha mar van ilyen key alatt letrehozva
if (shmid == -1){
shmid = shmget((key_t) SHARED_MEMORY_KEY,
0, 0);
}
return shmid;
}
void
initSzemaforok(osztottMemoriaTipus* p){
sem_init(&(p->ures),0,BUFFER_SIZE);
sem_init(&(p->tele),0,0);
sem_init(&(p->pmut),0,1);
sem_init(&(p->cmut),0,1);
p->nextin = p->nextout = 0;
}
void
testKiir(int *a,int n){
for (int i=0;i<n;++i){
printf("%d ",a[i]);
}
printf("\n");
}
termelo.c
/*
Lang Mate
Laszlo
*/
#include
"header.h"
void
initOsztottMemoria(osztottMemoriaTipus* p){
//lenullazzuk a buffert (leuritjuk a
futoszalagot)
int i = 0;
for(i=0; i< BUFFER_SIZE; ++i){
p->buffer[i] = 0;
}
}
void
termel(osztottMemoriaTipus* p){
int item = -1;
sem_wait(&(p->ures));
sem_wait(&(p->pmut));
item = rand()%10 + 1;
printf("%d\n",item);
p->buffer[p->nextin] = item;
p->nextin++;
p->nextin %= BUFFER_SIZE;
sem_post(&(p->pmut));
sem_post(&(p->tele));
}
int main(){
int shmid = lekerOsztottMemoriaID();
int t;
srand((unsigned) time(NULL));
osztottMemoriaTipus *p =
(osztottMemoriaTipus*) shmat(shmid,NULL,0);
initOsztottMemoria(p);
initSzemaforok(p);
for(t=0; t<10000; t++){
termel(p);
}
return 0;
}
fogyaszto.c
/*
Lang Mate
Laszlo
*/
#include
"header.h"
void
fogyaszt(osztottMemoriaTipus* p){
int item;
sem_wait(&(p->tele));
sem_wait(&(p->cmut));
item = p->buffer[p->nextout];
printf("%d\n",item);
p->nextout++;
p->nextout %= BUFFER_SIZE;
sem_post(&(p->cmut));
sem_post(&(p->ures));
}
int main(){
int shmid = lekerOsztottMemoriaID();
int t = 0;
osztottMemoriaTipus *p = (osztottMemoriaTipus*)
shmat(shmid,NULL,0);
for(t=0;t<10000;++t){
fogyaszt(p);
}
return 0;
}
A kovetkező makefile-al lehet lefordítani Ubuntu 11.10 alatt:
all: termelo fogyaszto
termelo:
gcc termelo.c -Wall -pedantic
-std=c99 -pthread -o t
fogyaszto:
gcc fogyaszto.c -Wall -pedantic
-std=c99 -pthread -o f
clean:
rm f t
.PHONY: all clean
Osztott memória (shared memory)
Copyright (C) Buzogány László, 2002
About