6.5 - Semaphores (p.249)

• Semaphore = Een synchronisatie tool die naast de initialisatie ervan alleen kan worden benaderd via de methodes acquire() en release(). Deze tool bestaat uit integer(s). De semaphore mag maar door een thread tegelijk worden aangepast. (Denk aan een parkeergarage met maar een paar plaatsen.)

• Methodes:

  • Acquire() = Afnemen van een "ticket". Kijken of de waarde van de sempahore nog > 0. Zo ja, de waarde met 1 verminderen.
  • Release() = Teruggeven van een "ticket". De waarde van de sempahore verhogen met 1.

• Soorten semaphores:

  • Counting Semaphore = Kan alle waardes bevatten.
  • Binary Semaphore = (aka mutex locks) Kan aleen de waardes 0 en 1 bevatten.
    • Mutex betekent MUTual EXclusive. (dus beiden kunnen niet 1 of 0 zijn, ze moeten van elkaar verschillen)

• Implementatie:

  • Busy Waiting = Wanneer een process moet wachten tot een ander process uit zijn critical section komt, en dit doet door een loop in zijn entry section .
  • Spinlock = Wanneer een semaphore ervoor zorgt dat een CPU niet efficent kan worden gebruikt omdat de processen vast zitten in busy waiting. ( Een process "spins" terwijl het wacht op een lock.)
    • Op multicore processoren kan dit een voordeel hebben, omdat een spinlock ervoor zorgt dat er geen context switch kan plaatsvinden. Een context switch kost resources/cpu tijd.
    • Wanneer de wait time verwacht wordt kort te zijn wordt de spinlock gebruikt om op een processor een thread te laten "spinnen", en een andere processor de critical section te laten uitvoeren.
  • Andere implementatie:
    • Wanneer een process moet wachten tot een semaphore vrij komt, kan het uit de CPU worden gehaald. De semaphore houdt een lijst/queue bij met processen die geforceerd zijn te wachten.
    • En wanneer de semaphore vrij komt kan dat process weer in de CPU worden geplaatst. (of dit direct gebeurt hangt af van de scheduler)

• Deadlock = Een process is in deadlock wanneer het wacht op een semaphore, en die semaphore alleen kan worden vrijgegeven door een process die ook wacht op een semaphore welke alleen door het andere process kan worden vrijgegeven. ( Kip en het Ei probleem)

• Starvation = Een process is in starvation wanneer deze voor altijd geblokeerd is, en nooit de mogelijkheid krijgt om zijn critical section uit te voeren. Komt voornamelijk voor bij een LIFO (Last In First Out) queue. Bij FIFO krijgt elk process uiteindelijk wel de kans.

• Priority Inversion

  • Priority Inversion = Scheduling probleem wanneer een hoog prioriteit process wacht op een resource dat moet worden vrijgegeven door een laag prioriteit process. En wanneer eventueel het laag prioriteit process terug moet in de ready queue, omdat een medium priorieit process voorrang heeft. Dit zorgt er dan weer voor dat het hoog prioriteit process nog langer moet wachten. (omdat het laag prioriteit process het resource nog vrij moet geven).
  • OPLOSSING!:
  • Priority Inheritance Protocol = Wanneer een hoog prioriteit process moet wachten op een resource van een laag priorieit process, krijgt het laag prioriteit process hetzelfde prioriteit van het hoge prioriteit. Waardoor het medium prioriteit process niet voor kan dringen.