Verkeerslicht

In de informatica, een stoplicht is een soort van abstracte gegevens beheerd door een multitasking besturingssysteem om toegang te synchroniseren met gedeelde bronnen tussen taken. Het bestaat uit een integer variabele en van de interface, en een rij processen.

Dit concept werd bedacht door Edsger Dijkstra, en voor het eerst in het besturingssysteem van de.

Bewerkingen op de verkeerslichten

Het getal in de semafoor geeft het aantal middelen van een bepaald type ter beschikking van de taken. Een bijzonder geval veel gebruikt is de binaire semafoor, waar de enige mogelijke waarden zijn 0 en 1. Een verkeerslicht dat alleen de waarden 0 en 1 wordt gedefinieerd mutex.

Een verkeerslicht kan worden gewijzigd door de gebruiker code slechts drie systeem belt:

  • Initialisatie: De seinpaal wordt geïnitialiseerd met een geheel getal en positief.
  • P werking of wachttijd: Het verkeerslicht wordt verlaagd. Indien na de afname, de semafoor een negatieve waarde, wordt de taak opgeschort en wachtrij, klaar om te worden geactiveerd door een andere taak.
  • V operatie of het signaal: Het licht is toegenomen. Als er taken wachtrij, een van de taken in de wachtrij is verwijderd uit de wachtrij en in een staat klaar.

De waarde van de semafoor eenmaal geïnitialiseerd, kan niet meer worden gelezen, zo niet indirect via de primitieven P en V.

De namen P en V, zijn door Dijkstra voorgesteld als de initialen van de Nederlandse woorden "probieren" en "verhogen".

Uitvoering

Deze bewerkingen correct zijn als ze niet worden onderbroken door andere taken.

Veronderstel dat in plaats daarvan twee taken tegelijk uitvoeren van de bewerking P een semafoor de waarde 1. Daarna heeft de eerste taak de semafoor is verlaagd 1-0, gaat de besturing naar de tweede taak, waarbij de semafoor decrementeert van 0 tot -1 en wacht. Op dit punt de controle terug naar de eerste taak die sinds het stoplicht heeft nu een negatieve waarde, wacht. Het resultaat is dat beide taken worden geblokkeerd, terwijl de semafoor met 1 één van de twee taak had kunnen gaan.

Er zijn geavanceerde algoritmen om de operaties op de verkeerslichten onjuiste wijze zonder het gebruik van speciale instructies van de CPU. Aangezien de bewerkingen op semaforen worden uitgevoerd door het besturingssysteem kernel, is het mogelijk en efficiënter doen op speciale instructies.

Een goede uitvoering kan worden bereikt door het uitschakelen van interrupts, waarna de context switches vóór operaties P en V, en onmiddellijk na riabilitandoli. Deze uitvoering heeft het nadeel dat twee aanvullende instructies.

Op sommige processors bestaan ​​onderwijs 'Test-en-set', die atomair een register en voert een voorwaardelijke sprong van de vorige waarde van dat register. Met behulp van deze instructie kunt u bewerkingen op de verkeerslichten veilig en efficiënt uit te voeren.

Intuïtieve betekenis

Intuïtief, de betekenis van de activiteiten is als volgt.

Met de initialisatie staat hoeveel eenheden van een type resource beschikbaar.

Met de operatie P, een taak vragen om een ​​eenheid van de bron behouden. Als units niet beschikbaar zijn, wordt de opdracht in de wacht gezet, alleen worden gewekt wanneer het verzoek zal worden toegewezen aan het apparaat.

Met de V operatie, een taak die vrijgeeft het apparaat niet meer nodig, en waarvoor andere taken mogelijk al wachten.

Voorbeelden van gebruik van verkeerslichten

Wederzijdse uitsluiting

Een zeer eenvoudige gebruik van verkeerslichten moet u wederzijdse uitsluiting in de toegang tot een bron eenvoudige zorgen: in dit geval gewoon gebruik maken van een binaire semafoor. Het alvorens de hulpbron zogenaamde P, en de V heet na gebruik.

Synchronisatie

De primitieven P en V worden gebruikt voor het uitvoeren van twee of threads synchroniseren doet namelijk dat een werkwijze wordt uitgevoerd na uitvoering van een ander proces. Bijvoorbeeld als het proces P2 moet worden uitgevoerd nadat het proces P1, kunt u een semafoor s geïnitialiseerd op 0. Voer de primitieve V aan het einde van het proces P1 en P primitieve begin van het proces P2. Het proces P2 wordt geblokkeerd totdat het proces van P P1 V niet zal lopen, die niet zal hebben afgerond uitvoeren van de code in de plaats voordat V.

Afwachting van de voltooiing van multiple

Een meer complex is het wachten op de voltooiing van de N gelijktijdige operaties.

Bijvoorbeeld, een webbrowser laadt een pagina vier afbeeldingen bevat. Om het tempo van het laden, lanceert 4 draad het laden, een voor elk beeld. Moet weten wanneer alle beelden zijn geladen.

Om dit te doen, initialiseren een seinpaal op 0, lanceert 4 threads, en loopt voor vier keer de P op de semafoor, waarschijnlijk door vergrendeling eigenlijk de eerste van de vier P. De draad, wanneer zij hun taak hebben afgerond, zij het uitvoeren van een V op de semafoor . Deze operatie wakker wordt de rode draad loopt een ander P en bevriest opnieuw. Alleen de laatste V wekt zeker de rode draad.

Producent en consument

Naar een nog complexere is het zogenaamde probleem van de circulaire buffer producent en consument.

Stel je hebt een taak die blokken van gegevens tussen deze apparaten verkrijgt, en ze moeten verhuizen naar een taak die hen wordt weergegeven op het scherm. De eerste taak wordt genoemd "fabrikant", omdat het gegevens verzendt, en de tweede is "consument" genoemd, omdat het de gegevens ontvangt: dit is dezelfde situatie die zich voordoet op het niveau van het besturingssysteem in leidingen en bericht wachtrijen .

De uitwisseling van gegevens tussen de twee taak gebeurt in een circulaire buffer dat N-records bevat. Elke plaat bevat een datablok kunnen worden verkregen uit de inrichting. U wilt er zeker van dat als producent schrijft gegevens naar de buffer, de consument de stappen te lezen, zonder te wachten tot de buffer vol is, maar het vermijden van de volgende situaties:

  • De producent schrijft gegevens in een record door het overschrijven van gegevens nog niet gelezen worden door de consument.
  • De wet van de consument door een record ongeldige gegevens, omdat de fabrikant nog niet heeft geschreven de nieuwe gegevens in die record.
  • De producent en de toegang van de consument tegelijkertijd, niet beide lezen, dezelfde gegevens structuur.

U kunt dit compenseren met drie verkeerslichten, genaamd "mutex", "vol", "leeg".

  • Semaphore "mutex", geïnitialiseerd op 1, garandeert wederzijdse uitsluiting bij de toegang tot de buffer.
  • Het stoplicht "vol", geïnitialiseerd op 0, slaat het aantal records klaar in de buffer, dat wordt geschreven, maar nog niet gelezen, en blokken die probeert te lezen van een lege buffer.
  • Het stoplicht "leeg", geïnitialiseerd op N, slaat het aantal vacatures in de buffer, dat wil zeggen, ruimten waarin u kunt records schrijven zonder overschrijven ongelezen platen en blokken die proberen te schrijven naar een volle buffer.

De taak producent wanneer het een record verworven te worden doorgegeven aan de consument, de volgende stappen:

De consument taak, toen hij nodig heeft om te lezen van de buffer naar een nieuw record weer te geven, voert u de volgende stappen:

De verkeerslichten vandaag

De verkeerslichten zijn nog steeds normaal gebruikt in programmeertalen die geen ondersteuning intrinsiek andere vormen van synchronisatie. Voorbeelden van bekende talen die niet direct ondersteunen andere vormen van synchronisatie zijn C en C ++. De trend in de ontwikkeling van programmeertalen echter naar meer gestructureerde vormen van synchronisatie zoals monitoren en afspraak.

In feite, de verkeerslichten hebben twee belangrijke nadelen:

  • Het is gemakkelijk voor programmeurs om een ​​P te voeren op een seinpaal reeds in het bezit van dezelfde thread, en vergeet de V draaien na het uitvoeren van P.
  • U loopt het risico lopen in een impasse, of tot stilstand gekomen. Bijvoorbeeld, als de taak T1 voert een P op de semafoor S1, terwijl de taak T2 voert een P op de semafoor S2, T1 en voert dan een P uit S2, T2 voert vervolgens een P op S1, heeft een impasse.

Daarom is de belangrijkste theoretici van concurrent programming, inclusief dezelfde Dijkstra, verklaarde verouderde verkeerslichten, zoals programmering techniek, hoewel ze nuttig zijn voor de uitvoering van een hoger niveau constructies kunnen zijn.

(0)
(0)
Commentaren - 0
Geen reacties

Voeg een Commentaar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha