Semafor

(eller: semaphore).

Ordet semafor stammer fra det franske ord sémaphore (fra græsk "sema" tegn, og "férein" bære) og betegner en signalmast for optisk telegrafi. Betegnelser for engelske jernbanesignaler og italienske trafiklys er også afledt heraf.

I edb-mæssig sammenhæng betegner semaforer en grundlæggende metode til signalering mellem parallelle processer. Signaleringen bruges til at synkronisere to (eller flere) samarbejdende processer indbyrdes og kan bruges generelt til at implementere interproces kommunikation. Processer har behov for synkronisering i to tilfælde. Det første tilfælde er, når processerne skal have adgang til fælles ressourcer eller fælles variable, hvor det er vigtigt, at kun én proces på et givet tidspunkt arbejder med dem. Det andet tilfælde er, at én proces producerer data, som en anden aftager. Et par signalflag i form af semaforer kan benyttes af processerne til at markere, at en proces er klar til at aftage data, henholdsvis er klar til at aflevere data.

Semaforer blev oprindeligt introduceret af hollænderen E.W. Dijkstra i 1965. Dijkstras semafor blev defineret som en variabel med heltallige værdier. Ordet semafor dækker nu et bredt spektrum af begreber, idet enhver teoretiker og ethvert edb-system har sin variant. De grundlæggende ideer er dog de samme.

Dijkstras semafor kaldes somme tider for en "tællesemafor". Der er defineret to operationer på den, "wait" (også kaldet vent, lock, lås, down, enqueue eller P) og "signal" (også kaldet open, åbn, up, send, dequeue eller V). En proces, der ønsker udelelig adgang til en ressource eller ønsker at vente på en anden proces, kalder 'wait'. Er semaforen ikke låst, dvs. at værdien er positiv, tælles værdien ned, og processen får lov til at gå videre. I modsat fald er det ikke tilladt, og processen stoppes ("blokerer"). Dette vil i mange styresystemer sige, at den stilles i en ventekø, indtil semaforen signaleres, uden at bruge CPU-tid. En proces, der er færdig med de delte ressourcer og ønsker at frigive dem, eller som ønsker at aktivere en anden proces, kalder 'signal'. Er der en eller flere ventende processer, aktiveres netop én. I modsat fald tælles værdien blot op.

Der findes flere semafortyper med forskellige malende navne til forskellige formål. Binære semaforer (to værdier) er velegnede til synkronisering. Tællesemaforer anvendes til at holde styr på mange ens ressourcer (f.eks. buffere). Beskedsemaforer bruges til udveksling af data i buffere. Postkassesemaforer og trafiklyssemaforer er til meget specielle formål.

Semaforer anvendes kun sjældent til interproces kommunikation i højere programmeringssprog. Dette skyldes den store risiko for programmeringsfejl. Desuden er de uegnede i forbindelse med formel bevisførelse for parallelle programmer. Hvert programmeringssprog (og herunder specielt systemprogrammeringssprog) har sin egen konstruktion, ofte implementeret ved hjælp af semaforer; her kan nævnes rendez-vous (i ADA), beskedudveksling (mange programmeringssprog) og monitor (Concurrent Pascal m.fl.). De er alle i princippet "lige stærke", dvs. er ækvivalente, men hver konstruktion er velegnet til bestemte formål.

Til mere maskinel-orienterede formål, herunder realisering af semafor-operationerne, stiller mange computere specielle instruktioner til rådighed. Her kan nævnes muligheden for at slå interrupts fra og til og instruktionen "test-and-set", som udfører en udelelig låsning, baseret på en enkelt bit i arbejdslageret. Disse metoder er ikke konkurrenter til semaforer, men er velegnede til at sikre udelelighed i korte tidsrum, f.eks. ved hentning af status fra ydre enheder, eller til at sikre korrekt implementering af semafor-operationerne. Semaforer bruges så til operationer, der kræver udelelig tilgang i længere perioder.

Se i øvrigt kritiske regioner og shared memory.