Semafor (datalogi)

Fra Wikipedia, den frie encyklopædi

Indenfor datalogi er en semafor en speciel heltalsvariabel. En tælle-semafor er en tællervariabel, som altid kan tælles op, men som kun kan tælles ned, hvis den har en værdi, der er større end nul. Hvis en proces i et program forsøger at tælle længere ned end nul, vil processen blive blokeret indtil en anden proces forøger tælleren. En binær semafor kan kun antage værdierne 0 og 1. En binær semafor kaldes også en mutex, hvilket er en sammentrækning af mutual exclusion, gensidig udelukkelse. En semafor kan anvendes i datalogi som det basale synkroniseringsprimitiv i den datalogiske disciplin parallelprogrammering.

Semaforer kræver understøttelse i computerens styresystem. Styresstemet sørger for, at de rette processer tvinges til at vente indtil der er sket den nødvendige optælling. Semaforer stilles typisk til rådighed via et programbibliotek som libc. Læsning og ændring af semaforens værdi er en atomar operation. Det indebærer, at hvis en proces har læst en semafor med værdien 1 i forbindelse med en nedtælling, så er der ikke andre, der kan komme til at læse denne værdi før nedtællingen er gennemført. Det same gælder, når der tælles op.

Indholdsfortegnelse 1 Historie 2 Eksempel på anvendelse 2.1 Baglås 3 Se også

[redigér] Historie

Semaforer blev første gang beskrevet og brugt af Edsger Dijkstra. Han beskrev først den binære semafor og beskrev den generelle udgave senere. Dijkstra formulerede også en række abstrakte problemstillinger, som kræver snkronisering. Blandt problemstillingerne er De spisende filosoffer og producent-forbrugerproblemet.

[redigér] Eksempel på anvendelse

Semaforer kan bruges når man vil lave kritiske sektioner i et program. En kritisk sektion er en del af et program, som ikke må bruges af flere brugere samtidigt. Med pseudokode kunne det se sådan ud: (Det antages at semaforen sem har startværdien 1 inden proces A og B startes)

Proces A:

ned( sem )
a = x
a = a + 3
x = a
op( sem )

Proces B

ned( sem )
b = x
b = b - 5
x = b
op( sem )

Semaforen sikrer, at opdateringerne fra de to processer ikke blandes sammen. Uden semaforer kunne der ske følgende:

1. x læses i proces A
2. x læses i proces B
3. a = a + 3
4. x sættes til a i proces A
5. b = b - 5
6. x sættes til b i proces B

Resultatet bliver, at den første opdatering går tabt. Med semaforer ville der i stedet ske følgende:

1. Semaforen tælles ned i proces A
2. Beregningen påbegndes i proces A
3. Semaforen tælles ned i proces B.
4. Da semaforen er nul, kan nedtællingen ikke gennemføres, og proces B må vente
5. Beregningen gøres færdig i proces A
6. Semaforem tælles op i proces A
7. Proces B får mulighed for at fortsætte og semaforen tælles ned igen
8. Proces B gennemfører beregningen
9. Semaforen tælles op i proces B

Semaforen sikrer, at de to opdateringer sker hver for sig, men rækkefølgen kan ikke garanteres.

[redigér] Baglås

Hvis semaforer ikke bruges korrekt, kan der opstå situationer, hvor programmerne går i baglås. Det kan ske, hvis forskellige processer bruger forskellige semaforer, men ikke bruger dem i samme rækkefølge. Eksempel:

Proces A

ned(sem1)
.
ned(sem2)
.
.
op(sem2)
op(sem1)

Proces B

ned(sem2)
ned(sem1)
.
.
op(sem1)
op(sem2)

Systemet kan gå i baglås på følgende måde:

1. Proces A tæller sem1 ned
2. Proces B tæller sem2 ned
3. Proces B venter på sem1
4. Proces A venter på sem2
5. Både A og B venter og systemet er gået i baglås.

Løsningen er, at sørge for, at de involverede processer alle tæller semaforerne ned i samme rækkefølge og tæller dem op i modsat rækkefølge.

[redigér] Se også

• Monitor – en anden synkroniseringsmulighed