Begreper & formler
Alle nøkkelbegrepene og formlene fra Semaforer, klassiske synkroniseringsproblemer og deadlock, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
Tellerbasert synkroniseringsobjekt som kan brukes både som lås og som signalmekanisme.
Operasjon som reduserer semaforen når den er positiv, ellers blokkerer.
Klassisk producer-consumer-problem der produsenter og konsumenter må koordineres mot en begrenset kø.
Problem der mange lesere kan tillates samtidig, men skrivere krever eksklusiv tilgang.
Klassisk problem som illustrerer hvordan lokal ressursallokering kan gi deadlock.
Situasjon der en gruppe tråder/prosesser venter sirkulært på ressurser og ingen kommer videre.
At en tråd eller prosess nektes fremdrift over svært lang tid, uten nødvendigvis å være i deadlock.
Teller ledige plasser i en bounded buffer. Initialiseres til buffer-størrelsen N. Producer venter på empty (sem_wait) før den legger inn et element.
Teller okkuperte plasser. Initialiseres til 0. Consumer venter på full før den henter ut et element. Producer poster på full etter innsetting.
Initialiseres til 1. Brukes for mutual exclusion på selve buffer-strukturen — sikrer at kun én tråd modifiserer den om gangen. Plasseres innerst rundt buffer-operasjonen.
Tre-semafors løsning: (1) sem_wait(empty)/(full), (2) sem_wait(mutex), (3) operasjon på buffer, (4) sem_post(mutex), (5) sem_post(full)/(empty). Rekkefølgen er kritisk — bytter du wait(mutex) og wait(empty) får du deadlock.
Variant av producer-consumer: kunde-tråd er producer (legger seg i kø), bank-staff er consumer. Bruker fire semaforer (empty, full, mutex, service) der service signaliserer at en kunde er klar til å bli betjent.
Klassisk fallgruve i producer-consumer: hvis sem_wait(mutex) kommer FØR sem_wait(empty) og bufferen er full, holder produsenten mutex mens den venter på empty — consumer kan ikke ta mutex for å hente element → låst.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Semaforens vent-operasjon
Ressurs tas bare hvis telleren er positiv, ellers må tråden vente.
Semaforens signal-operasjon
Frigjør en ressurs og lar eventuelt en blokkert tråd fortsette.
Coffman-betingelsene for deadlock
Alle fire må være til stede samtidig for at deadlock skal være mulig.
Producer-mal (semaforer)
HUSKEREGEL: vent på ressurs FØR mutex, slipp mutex FØR du signaliserer motpart. Rekkefølgen `wait(empty) → wait(mutex)` er kritisk for å unngå deadlock.
Consumer-mal (semaforer)
Speilbilde av producer. Consumer venter på full først, så på mutex, henter element, slipper mutex, og signaliserer at en plass er ledig.
Initialisering for buffer av størrelse N
empty=N (alle plasser ledige), full=0 (ingen elementer), mutex=1 (binær lås). Disse verdiene er testet direkte på eksamen.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Definere P- og V-operasjonene og forklare hvordan en semafor kan brukes både som lås og som signal
- 02Implementere producer-consumer med tre semaforer og begrunne hvorfor sem_wait(empty) må komme før sem_wait(mutex)
- 03Forklare readers-writers og hvordan starvation av skrivere kan oppstå og forebygges
- 04Identifisere Coffmans fire betingelser i et konkret deadlock-scenario og foreslå hvilken som er enklest å bryte