Wikiszótár

Peterson-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈpɛtɛrʃonɒlɡoritmuʃ]

Főnév

Peterson-algoritmus

  1. (matematika)

Peterson-algoritmus

A Peterson-algoritmus egy klasszikus, egyszerű és hatékony megoldás a kölcsönös kizárás problémájára, amely két folyamat között szinkronizációt biztosít több szálú (multithreaded) környezetben. Az algoritmust Gary L. Peterson javasolta 1981-ben, és a kritikus szekció biztonságos elérésére használják.


Cél

  • Kölcsönös kizárás: Garantálja, hogy egyszerre csak egy folyamat (vagy szál) léphessen be a kritikus szekcióba.
  • Deadlock elkerülése: Az algoritmus biztosítja, hogy ha egy folyamat nem tartózkodik a kritikus szekcióban, másik folyamat beléphessen.
  • Fairness (igazságosság): Az algoritmus megakadályozza az egyik folyamat végtelen késleltetését.


Működés

A Peterson-algoritmus két globális változót használ: 1. flag tömb: - Jelzi, hogy egy adott folyamat belépni szeretne a kritikus szekcióba. - (flag[i] = ): Az (i)-edik folyamat belépni szeretne. 2. turn változó: - Meghatározza, hogy melyik folyamatnak van előnye a kritikus szekcióba való belépéskor.


Algoritmus lépései

  1. Belépés előkészítése:
    • A folyamat jelzi szándékát a belépésre ((flag[i] = )).
    • Átadja a döntés jogát a másik folyamatnak ((turn = j)).
  2. Belépés várakozással:
    • A folyamat addig vár, amíg a másik folyamat is belépni szeretne ((flag[j] = )), és a másik folyamatnak van előnye ((turn = j)).
  3. Kritikus szekció:
    • Ha a feltételek teljesülnek, a folyamat beléphet a kritikus szekcióba.
  4. Kilépés:
    • A folyamat visszaállítja a saját flag-jét ((flag[i] = )).


Pszeudokód

Két folyamat esetén ((P_0) és (P_1)):

// Globális változók
flag = [False, False]  // Két folyamat szándékjelzője
turn = 0               // A döntés joga

// Folyamat i
while True:
    // Belépés előkészítése
    flag[i] = True
    turn = j  // j az ellenkező folyamat indexe

    // Várakozás a belépésre
    while flag[j] and turn == j:
        pass  // Aktív várakozás

    // Kritikus szekció
    // Ide írjuk a védett műveleteket

    // Kilépés
    flag[i] = False

    // Nem kritikus szekció
    // Ide írjuk a többi műveletet

Tulajdonságok

1. Kölcsönös kizárás biztosítása

A Peterson-algoritmus garantálja, hogy a kritikus szekcióban egyszerre csak egy folyamat tartózkodhat.

2. Deadlock-mentesség

Az algoritmus biztosítja, hogy ha egy folyamat kilép a kritikus szekcióból, a másik folyamat be tud lépni.

3. Éhségmentesség (Starvation-freedom)

A Peterson-algoritmus igazságos: minden folyamat idővel beléphet a kritikus szekcióba, ha szeretne.


Python implementáció

import threading
import time

# Globális változók
flag = [False, False]
turn = 0

# Kritikus szekció
def critical_section(process_id):
    print(f"Folyamat {process_id} belépett a kritikus szekcióba")
    time.sleep(1)  # Szimulált kritikus művelet
    print(f"Folyamat {process_id} kilépett a kritikus szekcióból")

# Peterson-algoritmus
def peterson(process_id):
    global flag, turn
    other = 1 - process_id

    while True:
        # Belépés előkészítése
        flag[process_id] = True
        turn = other

        # Várakozás
        while flag[other] and turn == other:
            pass

        # Kritikus szekció
        critical_section(process_id)

        # Kilépés
        flag[process_id] = False

        # Nem kritikus szekció
        time.sleep(1)

# Két szál (folyamat) szimulációja
thread0 = threading.Thread(target=peterson, args=(0,))
thread1 = threading.Thread(target=peterson, args=(1,))

thread0.start()
thread1.start()

thread0.join()
thread1.join()

Kimenet (példa): 

Folyamat 0 belépett a kritikus szekcióba
Folyamat 0 kilépett a kritikus szekcióból
Folyamat 1 belépett a kritikus szekcióba
Folyamat 1 kilépett a kritikus szekcióból
...

C++ implementáció

#include <iostream>
#include <thread>
#include <atomic>
#include <chrono>

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

void critical_section(int process_id) {
    std::cout << "Folyamat " << process_id << " belépett a kritikus szekcióba" << std::endl;
    std::this_thread::sleep_for(std::chrono::seconds(1));
    std::cout << "Folyamat " << process_id << " kilépett a kritikus szekcióból" << std::endl;
}

void peterson(int process_id) {
    int other = 1 - process_id;

    while (true) {
        // Belépés előkészítése
        flag[process_id] = true;
        turn = other;

        // Várakozás
        while (flag[other] && turn == other) {
            // Aktív várakozás
        }

        // Kritikus szekció
        critical_section(process_id);

        // Kilépés
        flag[process_id] = false;

        // Nem kritikus szekció
        std::this_thread::sleep_for(std::chrono::seconds(1));
    }
}

int main() {
    std::thread t1(peterson, 0);
    std::thread t2(peterson, 1);

    t1.join();
    t2.join();

    return 0;
}

Kimenet (példa): 

Folyamat 0 belépett a kritikus szekcióba
Folyamat 0 kilépett a kritikus szekcióból
Folyamat 1 belépett a kritikus szekcióba
Folyamat 1 kilépett a kritikus szekcióból
...

Előnyök

  1. Egyszerűség:
    • Könnyen implementálható és érthető.
  2. Hatékonyság:
    • Nincs szükség speciális hardverre, csak egyszerű memóriahozzáférésre.
  3. Kölcsönös kizárás:
    • Garantáltan biztosítja.


Hátrányok

  1. Csak két folyamatra működik:
    • Bár általánosítható több folyamatra, ez a verzió csak két folyamatot támogat.
  2. Aktív várakozás (Busy waiting):
    • A folyamatok CPU-t használnak várakozás közben.


Összegzés

A Peterson-algoritmus egy egyszerű és elegáns megoldás a kölcsönös kizárás problémájára két folyamat esetén. Bár hatékonyan használható, a modern rendszerekben inkább más szinkronizációs eszközöket (pl. mutexek) alkalmaznak az aktív várakozás elkerülése érdekében. Ennek ellenére az algoritmus fontos szerepet játszik az elméleti számítástudomány és az operációs rendszerek tanulmányozásában.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Peterson-algoritmus&oldid=3479573”