19. Osztott rendszerek és konkurens programozás

Szálkezelés

A szál (thread) a processzor egyfajta szoftveres megfelelője, minimális kontextussal. Ha a szálat megállítjuk, a kontextus elmenthető és továbbfuttatáshoz visszatölthető.

Folyamat: A folyamat (process vagy task) egy vagy több szálat összefogó nagyobb egység. Egy folyamat szálai közös memóriaterületen (címtartományon) dolgoznak, azonban különböző folyamatok nem látják egymás memóriaterületét.

Szál vs. folyamat: A szálak közötti váltáshoz nem kell igénybe venni az OS szolgáltatásait, míg a folyamatok közötti váltásnál ahhoz, hogy a régi és új folyamat memóriaterülete elkülönüljön a memóriavezérlő (MMU) tartalmának jó részét át kell írni, amihez csak a kernel szintnek van joga. A folyamatok létrehozása, törlése és a kontextusváltás közöttük sokkal költségesebb a szálakénál.

Kontextusváltás: A másik folyamatnak/szálnak történő vezérlésátadás az operációs rendszer által, így egy processzor több szálat/ folyamatot is végre tud hajtani. Költséges művelet, mivel a CPU-nak el kell mentenie a folyamat állapotát (regiszterek, program számláló, stb.) és vissza kell állítania a következő folyamatét.

Ütemezés: Az ütemezés lényege az erőforrások (processzoridő, memória) hatékony kihasználása, ezek folyamatok közötti elosztása. Az ütemezés során a folyamatoknak különböző prioritásokat adhatunk, amik alapján az operációs rendszer dönt arról, hogy melyik folyamatot futtatja. Az ütemezés lehet preemptív (a kernel bármikor megszakíthatja a folyamatot) vagy kooperatív (a folyamatoknak maguknak kell megszakítaniuk egymást). Az ütemezés lehet időosztásos (time-sharing) vagy prioritásos (priority-based).

• A preemptív ütemezés során a kernel megszakíthatja a folyamatot, ha egy magasabb prioritású folyamat érkezik. Ezzel a válaszidőt csökkenthetjük, de a kontextusváltás költségesebb, mivel a kernelnek el kell mentenie a folyamat állapotát és vissza kell állítania a következő folyamatét.

• A kooperatív ütemezés során a folyamatoknak maguknak kell időnként visszaadniuk az irányítást az operációs rendszernek (yield), de a válaszidő növekedhet, mivel a folyamatok nem biztos, hogy időben megszakítják egymást.

Gyakori típusai:

• FIFO: Elsőként érkező elsőként kiszolgálás (First In First Out). Az elsőként érkező folyamatot azonnal kiszolgálja a rendszer, a következő folyamat csak akkor indulhat el, ha az előző befejeződött.
• Round Robin: Az időosztásos ütemezés egy változata, ahol minden folyamatnak egyenlő időtartamú időkeretet (time slice) adunk, aminek leteltével a következő folyamatra váltunk.
• EDF: A legközelebbi határidővel rendelkező folyamatot szolgálja ki először (Earliest Deadline First).

Linux kernelben:

• Régebben CFS (Completely Fair Scheduler), 6.6 óta EEVDF (Earliest Eligible Virtual Deadline First).

Race Condition

A race condition akkor fordul elő, amikor két vagy több szál párhuzamosan próbál hozzáférni egy megosztott erőforráshoz, és az erőforrás állapota a szálak közötti verseny miatt megváltozik. Ez hibás működéshez vezethet, mivel a szálak nem garantáltan a várt sorrendben férnek hozzá az erőforráshoz.

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>

int shared_variable = 0;

void* thread_function(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        shared_variable++;
    }
    return NULL;
}
int main() {
    pthread_t thread1, thread2;

    pthread_create(&thread1, NULL, thread_function, NULL);
    pthread_create(&thread2, NULL, thread_function, NULL);

    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    printf("Final value of shared_variable: %d\n", shared_variable);
    return 0;
}

A race condition elkerülésére különböző szinkronizációs mechanizmusokat alkalmazhatunk, mint például:

Atomi műveletek és atomi változók:

• Atomi műveletek: Ezek olyan műveletek, amelyeket a processzor egyetlen lépésben hajt végre, így garantálva, hogy más szálak nem tudják megzavarni őket. Az atomi műveletek használata segít elkerülni a versenyhelyzeteket, mivel biztosítják, hogy a művelet végrehajtása során a változó állapota nem változik meg más szálak által.
• Atomi változók: Ezek olyan változók, amelyek garantálják, hogy a műveletek végrehajtása atomikus módon történik. Az atomi változók használata segít elkerülni a versenyhelyzeteket, mivel biztosítják, hogy a művelet végrehajtása során a változó állapota nem változik meg más szálak által.

Zárak:

• Mutex: Egy kölcsönös kizárás (mutual exclusion) mechanizmus, amely biztosítja, hogy csak egy szál férhessen hozzá az erőforráshoz egy időben.
• RwLock: Egy olvasó-író zár, amely lehetővé teszi, hogy több szál olvashassa az erőforrást egy időben, de csak egy szál írhatja azt.
• Semaphore: Egy számláló alapú szinkronizációs mechanizmus, amely lehetővé teszi, hogy több szál férjen hozzá az erőforráshoz, de korlátozott számú példányban.
• Monitor: Egy magas szintű szinkronizációs mechanizmus, amely a mutex és a feltételes változók kombinációját használja.

Csatornák:

• Channel/BlockingQueue: Egy szinkronizált kommunikációs mechanizmus, amely lehetővé teszi a szálak közötti üzenetküldést és adatátvitelt. A csatornák biztosítják, hogy az adatok biztonságosan és szinkronizált módon kerülnek átadásra a szálak között.

• Feltételes változók: Ezek lehetővé teszik a szálak közötti kommunikációt és szinkronizációt, lehetővé téve a szálak számára, hogy várakozzanak egy adott feltétel teljesülésére.

A race condition megelőzése érdekében fontos, hogy a szálak közötti kommunikációt és erőforrás-hozzáférést gondosan tervezzük meg.

Szinkronizáció

A szinkronizáció célja a párhuzamosan futó szálak közötti koordináció és együttműködés biztosítása. A szinkronizációs mechanizmusok segítenek elkerülni a versenyhelyzeteket és biztosítják, hogy a szálak biztonságosan férjenek hozzá a megosztott erőforrásokhoz.

Szinkronizációs mechanizmusok típusai:

• Atomikus műveletek (Atomic Operations)
• Zárak (Locks)
• Szemaforok (Semaphores)
• Számlálók (Counters)
• Feltételes változók (Condition Variables)
• Csatornák (Channels)
• Szinkronizált adattípusok (Synchronized Data Types)

Deadlock

A deadlock (holtpont) akkor fordul elő, amikor két vagy több szál kölcsönösen várakozik egymásra, és egyikük sem tudja folytatni a végrehajtást. Ez általában akkor történik meg, amikor a szálak különböző erőforrásokat próbálnak megszerezni, és ezek az erőforrások kölcsönösen blokkolják egymást.

public class DeadlockExample {
    private static final Object lock1 = new Object();
    private static final Object lock2 = new Object();

    public static void main(String[] args) {
        Thread thread1 = new Thread(() -> {
            synchronized (lock1) {
                System.out.println("Thread 1: Holding lock 1...");
                try { Thread.sleep(100); } catch (InterruptedException e) {}
                System.out.println("Thread 1: Waiting for lock 2...");
                synchronized (lock2) {
                    System.out.println("Thread 1: Acquired lock 2!");
                }
            }
        });

        Thread thread2 = new Thread(() -> {
            synchronized (lock2) {
                System.out.println("Thread 2: Holding lock 2...");
                try { Thread.sleep(100); } catch (InterruptedException e) {}
                System.out.println("Thread 2: Waiting for lock 1...");
                synchronized (lock1) {
                    System.out.println("Thread 2: Acquired lock 1!");
                }
            }
        });

        thread1.start();
        thread2.start();
    }
}

A deadlock elkerülésére különböző stratégiákat alkalmazhatunk, mint például:

• Erőforrások sorrendje: Az erőforrásokat mindig egy meghatározott sorrendben kérjük el, így elkerülve a kölcsönös várakozást.
• Időkorlátok: Az erőforrások megszerzésére időkorlátokat állíthatunk be, így ha egy szál nem tudja megszerezni az erőforrást, akkor visszaléphet és megpróbálhatja később.
• Deadlock detektálás: A rendszer folyamatosan figyeli a szálak állapotát, és ha deadlockot észlel, akkor megpróbálja feloldani azt (például egy szál leállításával). Ez általában költséges, mivel a rendszernek folyamatosan figyelnie kell a szálak állapotát.

Blokkoló műveletek

A blokkoló műveletek olyan műveletek, amelyek megakadályozzák a szálak további végrehajtását, amíg egy adott feltétel teljesül. Ezek a műveletek általában szinkronizációs mechanizmusokkal (például zárakkal vagy feltételes változókkal) valósulnak meg, de például fájlműveletekre (I/O) való várakozás, vagy a hálózati kommunikáció egyes stádiumai is blokkoló műveleteknek tekinthetők.

~~~ admonish note title="Megjegyzés" Kooperatív multitasking rendszereknél veszélyes lehet, mivel a blokkoló műveletek miatt a rendszer nem tudja hatékonyan kihasználni a processzoridőt. Ez főleg modern coroutine (async/await) alapú konkurens kódokban okozhat problémát, ahol a blokkoló műveletek miatt a szálak/taskok blokkolják az event loopot, és a válaszidő drasztikusan megnőhet. ~~~

Memória (stack és heap) használata szálakban

Minden szálnak saját verem (stack) memóriája van, amely a lokális változók és a függvényhívások tárolására szolgál. A verem mérete általában korlátozott, és a szálak közötti verem megosztása nem lehetséges. A heap memória viszont megosztott a szálak között, és a dinamikusan allokált objektumok tárolására szolgál. A heap memória használata során azonban figyelni kell a versenyhelyzetekre és a szinkronizációra, mivel több szál is hozzáférhet ugyanahhoz az objektumhoz.

A heap memória használata során a következő szempontokat érdemes figyelembe venni:

• Memória allokálás: A heap memóriát dinamikusan allokálhatjuk (pl malloc, realloc), és felszabadíthatjuk (pl free) műveletekkel.
• Memória szivárgás: A heap memória szivárgás akkor fordul elő, amikor a program nem szabadítja fel a már nem használt memóriaterületeket. Ez hosszú távon memóriahiányhoz vezethet. A legtöbb modern programozási nyelvben van beépített memória kezelés, amely segít elkerülni a memória szivárgás leggyakoribb forrásait (pl. garbage collector).
• Szinkronizáció: A heap memória használata során figyelni kell a szinkronizációra, mivel több szál is hozzáférhet ugyanahhoz az objektumhoz. A mutexek és egyéb szinkronizációs mechanizmusok használata segíthet elkerülni a versenyhelyzeteket.

A konkurens programozás nyelvi eszközei

TODO - Figure out what they meant by this

Szinkronizációhoz és kommunikációhoz használható adatszerkezetek

TODO - Figure out what they meant by this