Szemaforok
A fejezet tartalma:A szemafor
A szemafor olyan absztrakt adattípus, amit az osztott erőforrások egy készletéhez való hozzáférés szabályozásához, illetve programszálak szinkronizálásához használnak a többszálú környezetekben. Megalkotása Edsger Dijkstra holland matematikusnak, a programozás egyik úttörőjének nevéhez fűződik.
1. ábra: A szemafor, mint az osztott erőforrások egy készletéhez való hozzáférés szabályozója
A programozási szakirodalomban többnyire külön említik a bináris szemaforokat (amelyek értéke csak 1 vagy 0 lehet), s ezeket tévesen a mutexekkel azonosítják. Ezektől megkülönböztetve említik a számláló szemaforokat, melyek értéke 1-nél nagyobb is lehet, s ugyancsak tévesen a mutexek általánosításának tekintik. Michael Barr írása (Mutexes and Semaphores Demystified) megemlíti, hogy a mutexek és szemaforok fogalmának összekeverése történelmi eredetű, s egyszerű analógia segítségével tisztázza, hogy mi a különbség köztük:
- A mutex egy olyan kulcs, amelyet az operációs rendszer ad, hogy a programszál zárolni tudja egy erőforráshoz való hozzáférést a programfutás egy kritikus szakaszán. Ahhoz hasonlítható, mint a benzinkútnál a mosdó kulcsa, amelyből csak egy van. Aki a kulcsot megkapja, használhatja a mosdót, majd visszaszolgáltatja a kulcsot. Ha a kulcs éppen ki van adva, a többi vendég sorban áll a kulcsért. Ehhez hasonlóan a mutex használata is arra szolgál, hogy sorbarendezze a konkurens hozzáférési igényeket. Ha csak ennyi volna a mutex, akkor valóban azonosíthatnánk a bináris szemaforral, amelynek 1 értéke az erőforrás szabad, 0 értéke pedig a foglalt állapotnak fele meg. A mutex azonban ennél többet nyújt: van tulajdonosa (ownership – csak az a szál szabadíthatja fel, amelyik zárolta), és az operációs rendszer az implementációjában automatikusan kezeli a prioritásinverzió problémáját is.
- Ez az egyszerű hozzáférés-védelmi modell azonban a sokak által tévesen feltételezett módon nem skálázható több, azonos erőforrás esetére pusztán a számláló szemafor bevezetésével. A fenti analógiát folytatva: tegyük fel, hogy két egyforma mosdónk van, és a számláló szemafor értéke mutatja a szabad kulcsok számát. Ha a vendég elvesz egy kulcsot (csökkenti a szemafort), a szemafor alapján még nem tudja, melyik konkrét mosdó szabad. A szemafor önmagában tehát csak a szabad kapacitást számlálja, de nem oldja meg a több azonos erőforrás megosztását – ehhez kiegészítő adatszerkezetre (pl. egy szabad erőforrásokat nyilvántartó sorra vagy tömbre) is szükség van.
- A szemaforok rendeltetésszerű felhasználása valójában a szálak közötti jelzési
feladatok elvégzése:
- Termelő-fogyasztó (Producer-Consumer) minta: Míg a mutexet mindig ugyanaz a szál szabadítja fel, amelyik zárolta, a szemafornál a műveleteket különböző szálak is végezhetik. Az egyik szál (a termelő) növeli a szemafor értékét – jelezve például, hogy elhelyezett egy új adatot egy FIFO pufferben –, míg a másik szál (a fogyasztó) várakozik a szemaforra, majd az adat beolvasásakor csökkenti annak értékét.
- Eseményjelzés megszakításból (ISR): A szemafor kitűnően használható arra is, hogy egy megszakításkiszolgáló rutina (ISR) jelezzen egy várakozó programszálnak. Mivel az ISR nem "tulajdonosa" semminek, mutexet nem kezelhetne, de a szemafor értékét biztonságosan növelheti – értesítve a szálat arról, hogy pl. az ADC végzett a méréssel, vagy a DMA átvitte az előírt adatblokkot.
A Semaphore objektumosztály tagfüggvényei
Az osztott erőforrások egy készletéhez való hozzáférést szabályozó szemaforok létrehozása és kezelése a Semaphore objektumosztály segítségével végezhető, tagfüggvényeit az alábbi táblázatban foglaltuk össze. Az mbed-rtos-ban implementált Semaphore objektumosztály ún. számláló szemaforokat kezel, amelyek értékének nincs felső határa (csak a számábrázolásból eredő int32_t típushoz tartozó fizikai korlát).| Függvénynév |
Funkció |
|---|---|
| Semaphore név(szám) |
Létrehoz egy "név" nevű szemafor
objektumot és inicializálja a megadott számmal (a szám a kezdetben
rendelkezésre álló erőforrások száma). |
| wait(time) |
Várakozik, amíg a szemaforral
kezelt erőforrások valamelyike elérhetővé válik, majd lefoglalja
(eggyel csökkenti a szemafor értékét). Ha a szemafor nulla (nincs
elérhető erőforrás), a várakozás alapértelmezetten korlátlan ideig
tarthat, vagy a time
paraméterben ezredmásodpercekben megadott idő leteltekor időtúllépéssel
kilép a várakozásból. |
| release() |
Felszabadítja (eggyel növeli a
szemafor értékét) a korábban wait() metódussal
lefoglalt szemafort. |
Mintapélda: Étkező filozófusok - a könnyű út
Az előző fejezetben ismertetett "étkező filozófusok" problémján csavarunk egyet:
az alábbi programban a probléma eredeti feltételeit megváltoztatva egy egyszerűsítő könnyítést
alkalmazunk: a filozófusok nem csak a tányérjuk melletti pálcikákat vehetik fel, hanem bármelyik
két szabad pálcikát! Mivel így nem kell nyilvántartanunk, hogy melyik erőforrás szabad, mutexek
helyett elég lesz egy szemafor is, amelyben nyilvántartjuk, hogy hány erőforrás van még szabadon.Hardver követelmények:
- FRDM-KL25z kártya
#include "mbed.h"
#include "rtos.h"
Semaphore s(5); //a pool of 5 chopsticks
Mutex stdio_mutex; //Mutex required for Cortex-M0
Timer mytime;
void notify(const char* name) {
stdio_mutex.lock();
printf("%s acquired two chopsticks %8.1f\n\r", name,mytime.read());
stdio_mutex.unlock();
}
void test_thread(void const* args) {
while (true) {
Thread::wait(1000+rand()%500); //Thinking
s.wait();
s.wait();
notify((const char*)args);
Thread::wait(500+rand()%500); //Eating
s.release();
s.release();
}
}
int main (void) {
mytime.start();
Thread t2(test_thread, (void *)"Philosopher 2");
Thread t3(test_thread, (void *)"Philosopher 3");
Thread t4(test_thread, (void *)"Philosopher 4");
Thread t5(test_thread, (void *)"Philosopher 5");
test_thread((void *)"Philosopher 1");
}
A 10_rtos_dpp_easy projekt Makefile állománya:
PROJECT := 10_rtos_dpp_easy
DEVICES := KL25Z
GCC4MBED_DIR := ../..
GCC4MBED_TYPE := Release
MBED_OS_ENABLE := 1
NEWLIB_NANO := 1
NO_FLOAT_SCANF := 1
NO_FLOAT_PRINTF := 1
include $(GCC4MBED_DIR)/build/gcc4mbed.mk
A programban a filozófusokat egy-egy programszállal modellezzük, az 5 db pálcika foglaltságát pedig egy 5-ig számláló szemafor tartja nyilván.
A stdio hozzáfárás védelméhez szükségünk van egy mutexre is. A kiíratásokat ezért csak a notify() függvény hívásán keresztül végezzük.
A mytime absztrakt időzítő arra szolgál, hogy mellékesen a futó időt is kijelezzük. Ennek segítségével az eseményeket egy időskálán is elhelyezhetjük.
A programszálak törzsét az előző fejezet végén bemutatott mintaprogramhoz hasonlóan ugyanaz a függvény képezi. A "filozófusaink" tehát csak neveikben különböznek, illetve a véletlenszám generálásnak köszönhetően különböző időpontokban kezdenek gondolkodni, vagy étkezni.
Étkezéskor két pálcikát kell megszerezni, ezért kétszer csökkentjük az s szemafor értékét az s.wait() függvényhívással. Ennek megfelelően étkezés végén is kétszer növeljük a szemafor értékét (mindkét pálcikát letesszük...) az s.release() függvényhívással. A szemafor kezdeti értékét a konstruktor meghívásakor állítjuk be 5-re.
A programban a gondolkodási idő 1 - 1,5 másodperc, az étkezés pedig 0,5 - 1 másorpec közötti véletlen időtartamú.
A program futási eredménye az alábbi ábrán látható. Minden kiírás arról értesít bennünket, hogy valamelyik filozófus megszerezte az evőeszközöket és elkezdett étkezni a jobboldali oszlopban megadott időpontban (a program indításától eltelt idő másodpercben értendő).
2. ábra: A 10_rtos_dpp_easy program futási eredménye
Holtpont esetleges kialakulásakor a kiírás leáll (mi nem tapasztaltunk ilyet, de elvileg lehetséges...). A kiéheztetés pedig abban nyilvánulna meg, hogy valamelyik programszál huzamosabb ideig nem fér hozzá az evőeszközökhöz. Ilyet sem tapasztaltunk, de a fenti program több vonatkozásban is tökéletesítésre szorulna. Mivel célunk itt csupán a szemafor használatának bemutatása volt, az étkező filozófusok problémakörét nem igyekszünk teljeskörűen kimeríteni.
Mintapélda: Megosztott erőforrások kezelése
Ahogy a bevezető részben már említettük, egy szemafor önmagába nem elegendő két, vagy több egyforma megosztott erőforrás hozzáférésének védelmét ellátni, tehát a számláló szemafor nem tekinthető a mutex általánosításának. Az előző mintapéldában csak azért volt elegendő egy szemafor, mert csupán a szabad erőforrások számát tartottuk nyilván, azza nem törődtünk, hogy konkrátan melyik szabad.Az alábbi pédában három programszál verseng két erőforrás valamelyikének használatáért, s természetesen tudni akarjuk, hogy mikor, melyik programszál melyik erőforráshoz fért hozzá. A szabad erőforrások számát most is egy sem nevű szemafor segítségével tartjuk nyilván, a két erőforrás foglaltságát illetve a hozzáférés kizárólagosságát egy-egy mutex (m1 és m2) használatával adminisztráljuk. A foglalások eredményét kiíratjuk, ezért a szokásos módon az stdio hozzáférésének védelméhez is szükségünk lesz egy mutexre (stdio_mutex).
Ha egy programszálnak sikerült hozzáférési jogot szereznie, akkor még ki kell derítenie, hogy a két erőforrás közül melyik szabad. Ehhez a mutex objektum trylock() metódusát fogjuk használni, amelyik nem várakozik, hanem egy logikai értékkel jelzi, hogy sikeres volt-e a foglalás. Ha az első próbálkozásunk sikertelen volt, akkor a másik erőforrásnak kell szabadnak lennie, ezért ott már bátran használhatjuk a lock() metódust.
Mi itt a szemafor szerepe, ha az erőforrások tényleges lefoglalását úgyis egy-egy mutex segítségével végezzük? Elsősorban az, hogy a beérkező kérelmeket sorbarendezze. Ennek két haszna van:
- Nem fordulhat elő, hogy az egyik erőforrásra többen is várakoznak, miközben a másik erőforrás szabadon áll.
- A szemafor egyetlen várakozási sorából az ütemezőnek lehetősége
van arra, hogy mindig a legmagasabb prioritású programszálat engedje
tovább.
Hardver követelmények:
- FRDM-KL25z kártya
#include "mbed.h"
#include "rtos.h"
Semaphore sem(2); //manges two tokens
Mutex m1, m2; //two mutexes for two resources
Mutex stdio_mutex; //Control shared access to printf
DigitalOut led1(LED1); //Red LED
DigitalOut led2(LED2); //Green LED
DigitalOut led3(LED3); //Blue LED
DigitalOut ledarray[]= {led1,led2,led3}; //Just needed for indexing the objects...
Timer mytime;
void notify(int tid, int res) {
stdio_mutex.lock();
if(res > 0) {
printf("Task %d: acquired << resource %d. at %8.1f\n\r",tid,res,mytime.read());
} else {
printf("Task %d: released >> resource %d. at %8.1f\n\r",tid,-res,mytime.read());
}
stdio_mutex.unlock();
}
void mythread(void const* args) {
while (true) {
Thread::wait(500+rand()%500);
ledarray[(int)args-1]=0; //LEDx on
sem.wait(); //Wait for token
if(m1.trylock()) { //Try to lock mutex #1
ledarray[(int)args-1]=1; //LEDx off
notify((int)args,1);
Thread::wait(1000+rand()%500);
notify((int)args,-1);
m1.unlock();
} else {
m2.lock(); //Wait for mutex #2
ledarray[(int)args-1]=1; //LEDx off
notify((int)args,2);
Thread::wait(1000+rand()%500);
notify((int)args,-2);
m2.unlock();
}
sem.release(); //Release token
}
}
int main (void) {
led1 = 1;
led2 = 1;
led3 = 1; //Switch off all LEDs
mytime.start(); //Start timer
Thread t2(mythread,(void *)2U); //Define and run thread2
Thread t3(mythread,(void *)3U); //Define and run thread3
mythread((void const*)1U); //Run thread1
}
A 10_rtos_semaphore projekt Makefile állománya: a programban lebegőpontos kiírást végzünk, ezért szükséges a NO_FLOAT_PRINTF := 0 beállítás.
PROJECT := 10_rtos_semaphore
DEVICES := KL25Z
GCC4MBED_DIR := ../..
GCC4MBED_TYPE := Release
MBED_OS_ENABLE := 1
NEWLIB_NANO := 1
NO_FLOAT_SCANF := 1
NO_FLOAT_PRINTF := 0
include $(GCC4MBED_DIR)/build/gcc4mbed.mk
- A led1, led2, led3 objektumok a FRDM-KL25Z kártyánál az RGB LED színkomponenseit jelentik. Indexelhető kezelésükhöz egy tömbbe rendeztük ezeket az egyébként független objektumokat.
- Az RGB LED mindig az éppen a sem.wait()-ben várakozó programszál színét (1: vörös, 2: zöld, 3: kék) jelzi ki.
3. ábra: Az 10_rtos_semaphore program futási eredménye
A kiírt eredményeket idővonalon is ábrázolhatjuk. Bármely függőleges időszeletet nézzük, sosem fut 2-nél több feladat egyszerre, tehát az erőforrás foglalás az elvárt módon történik.
4. ábra: A terminálon kiírt eredmények idődiagramon ábrázolva
Mintapélda: Futási sorrend biztosítása
A szemaforok tipikus felhasználásai a programszálak szinkronizálására szolgálnak. Ilyen lehet például:- A programfutás sorrendiségének biztosítása - ahol a programszálak úgy adogatják egymásnak a szemafor zsetonokat, mint a staféták a váltóbotot a váltófutásnál.
- Randevú (rendezvous) - ahol a szemaforok azt biztosítják, hogy két programszál egy adott pontban várja be egymást.
- Sorompó (barrier) - ahol az a cél, hogy több párhuzamosan futó programszál egy adott pontban várja be egymást.
Hardver követelmények:
- FRDM-KL25z kártya
#include "mbed.h"
#include "rtos.h"
Semaphore s1(1); //allow task1 to run
Semaphore s2(0); //s2 has no token at start
Semaphore s3(0); //s3 has no token at start
DigitalOut led1(LED1); //Red LED
DigitalOut led2(LED2); //Green LED
DigitalOut led3(LED3); //Blue LED
void thread1(void const* args) {
while (true) {
s1.wait();
led1 = 0; //Red LED ON
Thread::wait(500+rand()%500);
led1 = 1; //Red LED OFF
s2.release();
}
}
void thread2(void const* args) {
while (true) {
s2.wait();
led2 = 0; //Green LED ON
Thread::wait(500+rand()%500);
led2 = 1; //Green LED OFF
s3.release();
}
}
void thread3(void const* args) {
while (true) {
s3.wait();
led3 = 0; //Blue LED ON
Thread::wait(500+rand()%500);
led3 = 1; //Blue LED OFF
s1.release();
}
}
int main (void) {
led1 = 1; led2 = 1; led3 = 1; //Switch off all LEDs
Thread t2(thread2); //Define and run thread2
Thread t3(thread3); //Define and run thread3
thread1(NULL); //Run thread1
}
A 10_rtos_3semaphore projekt Makefile állománya:
PROJECT := 10_rtos_3semaphore
DEVICES := KL25Z
GCC4MBED_DIR := ../..
GCC4MBED_TYPE := Release
MBED_OS_ENABLE := 1
NEWLIB_NANO := 1
NO_FLOAT_SCANF := 1
NO_FLOAT_PRINTF := 1
include $(GCC4MBED_DIR)/build/gcc4mbed.mk