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. Eezktő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. Michaell 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 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 az alábbi programban 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án tartanunk, 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:
1. lista: A 10_rtos_dpp/main.cpp program listája
#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 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, mivel az ARM Cortex-M0 mikrovezérlők esetében használt C microlib programkönyvtár nem rendelkezik beépített hozzáférés védelemmel. 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 kezdeenek 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ő).


3. ábra: A 10_rtos_dpp program futási eredménye


Holtpont esetleges kialakulásakor a kiírás leáll (mi nem tapasztaltunk ilyet, de elvileg nem lehetetlen...). 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 csak 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átom 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:
Ha nem használnánk a szemafort, akkor eszközönként alakulna ki egy-egy várakozási sor. Ekkor előfordulhatna, hogy a legmagasabb prioritású programszál további várakozásra kényszerül, miközben egy másik eszköz várakozási sorából egy alacsonyabb prioritású programszál jut futási lehetőséghez, vagy a másik sor ki is ürül. Aki már késett le vonatot, amiatt, hogy a vasútállomási pénztáraknál rossz sorba állt, bizonyára átérzi ennek a problémának a súlyát.

Hardver követelmények:
2. lista: A 10_rtos_semaphore/main.cpp program listája
#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
}
Megjegyzések:

4. ábra: Az 10_rtos_semaphore program futási eredménye

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:
Az alábbi program az első esetre mutat egy példát: három programszálat szinkronizálunk három szemafor segítségével. Az RGB LED mindig az éppen futó programszál színét mutatja (1: vörös, 2: zöld, 3: kék). A kötött sorrendet itt az biztosítja, hogy mindegyik programszál "fogyasztóként" egy olyan szemaforra vár, amelynek a "termelője" az előtte futó programszál. Természetesen, ahhoz, hogy a staféta elinduljon, "be kell tenni" egy zsetont a rendszerbe, azaz valamelyik szemafort szabadra kell állítani. Itt most az s1 szemafor inicializálásnál állítottuk szabadra a jelzőt (s1 kezdőértéke = 1), a többinél pedig tilosra (s2 és s3 nulla kezdőértékkel lettek inicializálva).

Hardver követelmények:
3. lista: A 10_rtos_3semaphore/main.cpp program listája
#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
}