6.3 & 6.4 - Peterson`s Solution & Synchronization Hardware (p.245, 246)

Peterson`s Solution

• Klassieke software oplossing voor de critical selection problem.
• Werkt niet op alle architecturen, gebaseerd op hoe deze de load en store functie hebben geimplementeerd.
• Hoe?:
  1. Delen van de variablen: int turn; boolean flag[i];
     • turn = Geeft aan welk process de critical section mag uitvoeren.
     • flag = Array van booleans, waarbij het process aangeeft of hij ready is om zijn critical section uit te voeren.
     • i = Het nummer van het process (bijv het PID)
  2. Stel process 538 wil zijn critical section uitvoeren. Daarnaast is er ook process 777.
  3. In het entry section van process 538 flag[538] = true
  4. Process 538, geeft process 777 de kans om zijn entry section uit te voeren door turn = 777
  5. Stel beide processen voeren stap 4 tegelijk uit, dan blijft er maar een van de twee waardes staan. Dit process mag dan zijn critical section uitvoeren. De uiteindelijke waarde van turn bepaalt dus wie het mag uitvoeren.
• De uiteindelijke code ziet er dus zo uit vanuit process 538:

   do {
        #ENTRY SECTION
            flag[538] = TRUE;
            turn = 777;
            while (flag[777] && turn == 777);
        #CRITICAL SECTION
            do important stuff;
        #EXIT SECTION
            flag[538] = FALSE;
        #REMAINDER SECTION
            do normal stuff;
    } while (TRUE);

• Bewijzen voor de gestelde requirements in de vorige paragraaf.
  1. Mutual Execution
     • Als een process zijn critical section uitvoert en het andere process wil dat ook, dan zal het 2e process worden geblokkeerd door de flagvan het 1e process.
     • Als beide processen op hetzelfde moment de critical section willen uitvoeren, zal het process die als laatste turn = ... uitvoert geblokkeerd worden.
  2. Progress
     • Elk process kan alleen worden geblokkeerd bij de while ALS:
       1. het andere process de critical section wil uitvoeren (dus de flag is gezet van het processnummer)
       2. Het andere process aan de beurt is. (turn is het processnummer)
     • Wanneer dit klopt mag het process de critical section uitvoeren. Wanneer het process hiermee klaar is wordt in de exit section de eigen flag op False gezet waardoor het andere process wordt vrijgemaakt.
     • Dit zorgt ervoor dat maar 1 process teglijk kan worden geblokkeerd, en de pas weer wordt gedeblokkeerd wanneer de critical section is beeindigd...
  3. Bounded Waiting
     • Omdat elk process de turn variabele set naar het processnummer van de ander, laten ze de ander altijd voor gaan. Effectief zorgt dit ervoor dat elk process maar 1 beurt hoeft te wachten.

Synchronization Hardware

• Atomic Operations = Een enkele systeem operatie (evt in Assembly) die niet kan worden geinterrupt.

• Alle oplossingen voor de critical-section problem gebruiken een gereedschap, namelijk een lock.

  • Een process moet eigendom hebben over de lock voordat de critical section wordt uitgevoerd.
  • De entry section bestaat uit het verkrijgen van de lock, de exit section bestaat uit het teruggeven van de lock.
• Oplossing: Voorkomen van het interrupten van een process (preemtive kernel), is moeilijk want de interrupties moeten op alle processoren worden uit gezet. Dit werkt niet goed voor multiprocessor systemen en brengt de timing in de war. (de systeemklok kan worden geupdate met interrupts)
• Oplossing: Het gebruiken van atomic operations voor een lock.