Dekker algoritmusa

T. J. Dekker nevéhez fűződik a kölcsönös kizárási probléma egyik legkorábbi, két folyamatra adott helyes szoftveres megoldása. A problémával Edsger W. Dijkstra is alapvető fontosságú munkákban foglalkozott.

A megoldandó probléma arról szól, hogy két külön szálon akarunk olyan feladatokat futtatni, amelyek valamilyen közös változót használnak, vagy ugyanarra a kimenetre írnak. A lényeg, hogy mindkét szálon futó függvénynek van olyan része, aminél garantálni kell, hogy ha épp az a kódrész fut, akkor a másik szálon nem fog a hasonlóan kölcsönös kizárást igénylő kódrész futni.

Naív implementáció

Dekker algoritmusának implementálásához két mindkét szál által elérhető változóra van szükség:

Adott egy két elemű bool tömb, amelyet mindkét szál eléri: wantsToEnter. Ha wantsToEnter[i] értéke true, akkor az i-edik szál be akar lépni a védett kódrészbe. Kezdetben a tömb mindkét eleme false értékű. (4. sor)
Adott egy egész változó (turn), ami azt jelzi, hogy melyik szál léphet éppen be a védett kódrészbe. Értelem szerint csak a 0 és 1 értéket veheti fel ez a változó. Kezdeti értéke bármelyik lehet, az adott szál fog kezdetben elsőbbséget élvezni. (5. sor)

Hogyan futtatja az id-adik szál a védett kódrészt?

A wantsToEnter[id]-n keresztül jelzi, hogy be kíván lépni a védett kódrészbe. (14. sor)
Megvizsgálja, hogy a másik szál is be kíván-e épp lépni a saját védett kódrészébe. (17. sor) Ha nem, akkor megtörténhet a belépés. (41. sor)
Ha viszont a másik szál is épp használni akarja a védett kódrészt, akkor egy ciklus addig fut, amíg a másik szál wantsToEnter jelölője hamissá nem válik. (17. sor)
A cikluson belül a turn értéken keresztül megvizsgálja az adott szál, hogy ő van-e soron. (20. sor)
Ha nem ő van soron, akkor a belépési szándékot wantsToEnter[id] értékét false-ra állítja. (24. sor) Ezzel a másik szálon futó hasonló függvény ciklusából megtörténhet a kilépés.
Ezután az adott sor addig várakozik, amíg nem ő kerül sorra. Ehhez a turn értékét kell folyamatosan vizsgálni. (27. sor)
Ha ő kerül sorra, akkor visszaállítja a wantsToEnter[id] értékét, így rákényszeríti a másik szálat a várakozásra. (33. sor)
Ezt követően, ha a ciklusfeltétel hamissá válik, akkor beléphet az adott szál a védett kódrészbe.
A védett kódrész végrehajtását követően a másik szál számára lehetővé tesszük a belépést a turn értékének megváltoztatásával. (51. sor)
Végül jelzi az adott szál, hogy ő épp nem akar belépni, ezért a wantsToEnter[id] hamis értéket kap. (54. sor)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <thread>

bool wantsToEnter[2] = { false, false };
int turn = 0;

void Dekker(const int id)
{
    const int other = 1 - id;

    for (int i = 0; i < 5; ++i)
    {
        // 1. Jelzem, hogy be szeretnék lépni
        wantsToEnter[id] = true;

        // 2. Amíg a másik is be szeretne lépni...
        while (wantsToEnter[other])
        {
            // 3. ...megnézem, hogy én vagyok-e soron
            if (turn != id)
            {
                // 4. Nem én vagyok soron:
                //    ideiglenesen visszalépek
                wantsToEnter[id] = false;

                // 5. Megvárom, amíg rám kerül a sor
                while (turn != id)
                {
                    // busy waiting
                }

                // 6. Újra jelzem, hogy be akarok lépni
                wantsToEnter[id] = true;
            }
        }

        // =====================================
        // Kritikus szakasz
        // =====================================

        std::cout << "Thread " << id
                  << " entered critical section\n";

        // Itt dolgozunk a megosztott erőforrással.

        // =====================================
        // Kilépés a kritikus szakaszból
        // =====================================

        // 7. A másik thread következik
        turn = other;

        // 8. Már nem akarok belépni
        wantsToEnter[id] = false;
    }
}

int main()
{
    std::thread t0(Dekker, 0);
    std::thread t1(Dekker, 1);

    t0.join();
    t1.join();
}

Probléma a naív implementációnál

A fenti kód általános értelemben helyesnek tűnhet, C++ programként azonban hibás.

A wantsToEnter tömb elemeit és a turn változót több szál egyszerre olvassa és módosítja. Mivel ezek hagyományos, nem ún. atomi változók, a hozzáférések között data race alakulhat ki.

A C++ memória-modell szerint egy data race a program undefined behavior működését eredményezheti. Ez nem egyszerűen azt jelenti, hogy “nem tudjuk, milyen értéket kapunk”, hanem a fordító semmilyen értelmes többszálú viselkedést nem köteles megőrizni.

Emiatt egy klasszikus, megosztott változókon alapuló Dekker-algoritmust C++-ban nem lehet egyszerű bool és int változókkal implementálni.

`std::atomic` alapú implementáció

A problémára megoldást adhat, ha a érintett változókat atomiként értelmezzük. Ennek érdekében a kódot az alábbi módon kell módosítanunk.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <atomic>
#include <iostream>
#include <thread>

std::atomic<bool> wantsToEnter[2]{ false, false };
std::atomic<int> turn{ 0 };

void Dekker(const int id)
{
    const int other = 1 - id;

    for (int i = 0; i < 5; ++i)
    {
        // Jelezzük, hogy be szeretnénk lépni
        wantsToEnter[id].store(true);

        // Amíg a másik szál is be akar lépni...
        while (wantsToEnter[other].load())
        {
            // ...és nem mi következünk...
            if (turn.load() != id)
            {
                // ...visszalépünk
                wantsToEnter[id].store(false);

                // Megvárjuk, amíg ránk kerül a sor
                while (turn.load() != id)
                {
                    // busy waiting
                }

                // Újra jelezzük, hogy be akarunk lépni
                wantsToEnter[id].store(true);
            }
        }

        // ===== KRITIKUS SZAKASZ =====

        std::cout << "Thread " << id
                  << " entered critical section\n";

        // Itt történne a megosztott adat módosítása.

        // ===== KRITIKUS SZAKASZ VÉGE =====

        // A másik szál következik
        turn.store(other);

        // Már nem akarunk belépni
        wantsToEnter[id].store(false);
    }
}

int main()
{
    std::thread t0(Dekker, 0);
    std::thread t1(Dekker, 1);

    t0.join();
    t1.join();
}

Fontos, hogy ebben az implementációban az atomi műveletek std::memory_order_seq_cst memória-sorrendet használjanak.
A Dekker-algoritmus helyessége nemcsak azon alapul, hogy az egyes változók írása és olvasása atomi legyen, hanem azon is, hogy a két szál a releváns atomi műveleteket megfelelő sorrendben figyelje meg.
A std::memory_order_seq_cst az atomi műveletekre egy, minden szál számára konzisztens globális sorrendet biztosít. Az std::atomic műveletek alapértelmezett memória-sorrendje éppen std::memory_order_seq_cst, ezért a példában ezt nem szükséges külön megadni.
Gyengébb memória-sorrend, például std::memory_order_relaxed használata esetén az egyes atomi hozzáférések továbbra is atomikusak lennének, de ez önmagában már nem elegendő Dekker algoritmusának kölcsönös kizárási garanciájához.

`std::mutex` alapú megvalósítás

Dekker algoritmusa megmutatja, hogyan lehet kizárólag megosztott változók segítségével megvalósítani a kölcsönös kizárást. Modern C++ kódban azonban erre általában nem magát Dekker algoritmusát implementáljuk, hanem a szabványos szinkronizációs primitíveket, például std::mutex-et használunk.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <mutex>
#include <thread>

std::mutex mtx;

void Worker(const int id)
{
    for (int i = 0; i < 5; ++i)
    {
        {
            std::lock_guard<std::mutex> lock(mtx);

            // ===== KRITIKUS SZAKASZ =====

            std::cout << "Thread " << id
                      << " entered critical section\n";

            // Megosztott adatok módosítása.

            // ===== KRITIKUS SZAKASZ VÉGE =====
        } // lock_guard destruktora → unlock()
    }
}

int main()
{
    std::thread t0(Worker, 0);
    std::thread t1(Worker, 1);

    t0.join();
    t1.join();
}

Naív implementáció#

Probléma a naív implementációnál#

std::atomic alapú implementáció#

std::mutex alapú megvalósítás#

Naív implementáció

Probléma a naív implementációnál

`std::atomic` alapú implementáció

`std::mutex` alapú megvalósítás