En semafor er en spesiell variabel (eller abstrakt datatype ) som er den klassiske metoden for å begrense eller tillate tilgang til delte ressurser (for eksempel en systemlagringsressurs eller kildekodevariabler) i et multiprosesseringsmiljø (der flere prosesser vil kjøre samtidig ). De ble oppfunnet av Edsger Dijkstra i 1965 og ble først brukt i THEOS operativsystem [ referanse nødvendig ] .
Anta at et bibliotek har 10 identiske studierom, som skal brukes av én student om gangen. Studenter må be om rom i resepsjonen dersom de ønsker å bruke et studierom. Hvis det ikke er ledige rom, venter studentene i skranken til noen forlater et rom. Når en elev er ferdig med å bruke et rom, skal eleven gå tilbake til skranken og angi at et rom er ledig.
I den enkleste implementeringen vet resepsjonisten kun antall ledige rom som er tilgjengelige, som de bare vet riktig hvis alle studenter faktisk bruker rommet mens de har sjekket inn og returnerer dem når de er ferdige. Når en student ber om et rom, reduserer resepsjonisten dette tallet. Når en student slipper et rom, øker resepsjonisten dette tallet. Rommet kan brukes så lenge du vil, så det er ikke mulig å reservere rom på forhånd.
I dette scenariet representerer lobbytelleren en tellesemafor, rommene er ressursen, og elevene representerer prosesser/tråder. Verdien av semaforen i dette scenariet er i utgangspunktet 10, med alle rom tomme. Når en student ber om et rom, får de tilgang og verdien på semaforen endres til 9. Etter at neste elev kommer, reduseres den til 8, deretter 7, og så videre. Hvis noen ber om et rom og gjeldende verdi av semaforen er 0, blir [ 1 ] tvunget til å vente til et rom er frigitt (når tallet øker fra 0). Hvis et av rommene har blitt frigitt, men det er flere studenter som venter, kan en hvilken som helst metode brukes til å velge hvem som skal okkupere rommet (som FIFO eller myntkast). Og, selvfølgelig, en student må informere resepsjonisten om frigjøring av rommet sitt først etter at han faktisk har forlatt det; ellers kan det oppstå en vanskelig situasjon når eleven er i ferd med å forlate rommet (legger fra seg lærebøkene, osv.) og en annen elev kommer inn i rommet før de forlater.
Semaforer kan bare manipuleres ved å bruke følgende operasjoner ( dette er varm-vente-kode ):
Start(Semaphore s, heltall v) { s = v; }Der semaforvariabelen s vil bli initialisert til en heltallsverdi v.
P(Semaphore s) { hvis(e>0) s = s-1; ellers vente(); }Som vil holde den som styres av semaforen i aktiv standby hvis den har en verdi mindre enn eller lik null.
V(Semaphore s) { if(!blokkerte_prosesser) s = s+1; ellers signal(); }Disse instruksjonene kan endres for å unngå varm venting, slik at P-operasjonen hviler den samme prosessen som utfører den hvis den ikke kan redusere verdien, mens V-operasjonen vekker en prosess som ikke er den som utfører den. På et mer forståelig pseudospråk kalles P-operasjonen vanligvis "vent" eller "vent" og V-operasjonen "signal" eller "signal".
Årsaken til navnene på disse funksjonene, V og P, har sin opprinnelse i det nederlandske språket . «Verhogen» betyr å øke og «Proberen» betyr å prøve, selv om Dijkstra brukte det oppfunnede ordet prolaag [1] , som er en kombinasjon av probeer te verlagen (prøve å redusere). Verdien til semaforen er antall enheter av ressursen som er tilgjengelig (hvis det bare er én ressurs, brukes en " binær semafor " hvis startverdi er 1).
Verifikasjonen og modifiseringen av verdien, samt muligheten for å gå i dvale (blokkering) gjøres sammen, som en enkelt og udelelig atomhandling . Operativsystemet garanterer at når du starter en operasjon med en semafor, kan ingen annen prosess få tilgang til semaforen før operasjonen er fullført eller blokkert. Denne atomiteten er helt avgjørende for å løse synkroniseringsproblemer og unngå raseforhold.
Hvis det er n ressurser, vil semaforen initialiseres til nummer n. Dermed vil hver prosess, når du ber om en ressurs, verifisere at verdien av semaforen er større enn 0; i så fall er det ledige ressurser, så vil det hogge ressursen og redusere verdien av semaforen.
Når semaforen når verdien 0, vil det bety at alle ressursene blir brukt, og prosessene som ønsker å be om en ressurs må vente på at semaforen skal være positiv, det vil si: en av prosessene som bruker ressursene vil er ferdig med det og vil øke semaforen med et signal eller V(er).
Start brukes til å initialisere semaforen før forespørsler på den, og tar et heltall som argument. P -operasjonen, når det ikke er noen tilgjengelig ressurs, stopper utførelsen av å holde seg i aktiv standby (eller sovende) til verdien av semaforen er positiv, i så fall krever den umiddelbart ved å redusere den. V er omvendt operasjon: den gjør en ressurs tilgjengelig etter at prosessen er ferdig med å bruke den. Operasjonene P og V må være udelelige (eller atomiske ), som betyr at hver av operasjonene ikke må avbrytes midt i utførelsen.
V -operasjonen kalles noen ganger å heve semaforen ( opp ) og P - operasjonen er også kjent som å senke semaforen ( ned ), og kalles også signal og vent eller slipp og grip .
For å unngå varm venting kan en semafor ha en tilknyttet prosesskø (vanligvis en FIFO- kø ). Hvis en prosess utfører en operasjon P på en semafor som har en verdi på null, stoppes prosessen og legges til semaforens kø. Når en annen prosess øker semaforen ved å bruke V -operasjonen og det er prosesser i den tilknyttede køen, blir en av dem (den første som kommer inn i en FIFO-kø) poppet og utførelse gjenopptas.
Semaforer brukes for å gi tilgang til ulike deler av programmer (kalt kritiske seksjoner ) der variabler eller ressurser som må aksesseres på en spesiell måte manipuleres. Avhengig av verdien de initialiseres med, har flere eller færre prosesser lov til å bruke ressursen samtidig.
En enkel type semafor er binær , som bare kan ta verdiene 0 og 1. De initialiseres til 1 og brukes når bare én prosess kan få tilgang til en ressurs om gangen. De er i hovedsak de samme som mutex . Når ressursen er tilgjengelig, får en prosess tilgang til og reduserer verdien av semaforen med P-operasjonen. Verdien forblir da på 0, noe som betyr at hvis en annen prosess prøver å redusere den, må den vente. Når prosessen som reduserte semaforen utfører en V -operasjon , begynner en prosess som ventet å bruke ressursen.
For å få to prosesser til å kjøre i en forhåndsbestemt sekvens kan det brukes en semafor initialisert til 0. Prosessen som skal kjøres først i sekvensen utfører V -operasjonen på semaforen før koden som skal kjøres etter den andre prosessen. Dette utfører operasjonen P . Hvis den andre prosessen i sekvensen er planlagt å utføres før den andre, vil å gjøre P hvilemodus til den første prosessen i sekvensen går gjennom V -operasjonen . Denne bruksmåten kalles signalering , og den brukes for én prosess eller utførelsestråd for å la en annen få vite at noe har skjedd.
Trafikklys kan brukes til forskjellige formål, inkludert:
I det følgende eksempelet opprettes og kjøres n prosesser som vil prøve å gå inn i deres kritiske seksjon når de kan, og vil alltid lykkes én om gangen, takket være bruken av semaforen s initialisert til 1. Den har samme funksjon som en lås .
const int n /* antall prosesser */ semaforvariabel s; /* erklæring av heltalls semaforvariabel */ Initialiser (s,1) /* Initialiser en semafor med navn s med verdi 1 */ void P(int i) { mens (sant) { P(er) * I binære semaforer er det riktige å sette en P(er) før du går inn den kritiske delen, for å begrense bruken av denne koderegionen */ /* KRITISK DEL */ V(s) /* Etter den kritiske delen returnerer vi semaforen til 1 slik at en annen prosessen kan bruke det */ /* RESTEN AV KODEN */ } } int main() { Start-prosesser(P(1), P(2),...,P(n)); }