Synkroniseringsbarriere

I samtidig programmering sørger en synkroniseringsbarriere for at et visst antall oppgaver har passert et bestemt punkt. Dermed må hver oppgave som ankommer denne barrieren vente til det angitte antall oppgaver har kommet til denne barrieren.

Enbarriere-algoritme

For å oppnå denne første algoritmen for synkroniseringsbarriere trenger du to semaforer og en variabel:

• En semafor MUTEX(initialisert til 1) som beskytter variabelen.
• En semafor ATTENTE(initialisert til 0) brukes til å sette oppgavene på vent.
• En variabel Nb_Att(initialisert til 0) som brukes til å telle antall oppgaver som allerede er kommet til synkroniseringsbarrieren.

Det er også nødvendig å definere konstanten Nsom indikerer antall oppgaver som må ankomme barrieren før den åpnes.

Barriere : P(MUTEX) Nb_Att++ SI Nb_Att==N ALORS POUR I DE 1 à N-1 FAIRE V(ATTENTE) FIN POUR Nb_Att=0 V(MUTEX) SINON V(MUTEX) P(ATTENTE) FIN SI

Begrensninger av algoritmen

Denne første algoritmen er riktig, men den implementerer ikke en syklisk barriere. Hvis oppgavene må synkroniseres flere ganger med en barriere, er det da nødvendig å bruke 2 forskjellige barrierer på en alternativ måte. Følgende scenario viser, ved hjelp av et moteksempel, at den samme barrieren ikke kan brukes omgående:

1. En prosess A blant den første N-1 er satt på pause (av en forebyggende mekanisme ) mellom V (MUTEX) og P (WAIT) og vil ikke gjenoppta kontrollen i en viss tid.
2. Alle prosessene kommer til barrieren. Når den siste prosess, får den VENT er semaforen lik til - (N-2) (fordi en ikke har utført sin P (WAIT) drift ).
3. Den siste prosessen for å ankomme utfører N-1 ganger V (HOLD) og frigjør mutex. WAIT- semaforen er da lik 1.
4. En prosess B går raskt og kommer til den andre synkroniseringsbarrieren.
5. B utfører sperrekoden, og utfører en P (HOLD) . Denne operasjonen blokkerer ikke fordi ATTENTE- semaforen er lik 1 (prosess A har fremdeles ikke utført P (WAIT) til den første barrieren).

Prosess B vil derfor ha krysset den andre synkroniseringsbarrieren før alle andre prosesser har nådd den.

Multi-barriere algoritme

For å avhjelpe problemet nevnt ovenfor og implementere en syklisk barriere, er det nødvendig å innføre en andre semafor som gjør at den siste prosessen kan vente til alle de andre prosessene har utført P (WAIT) før de slippes ut mutex. Må derfor:

• En semafor MUTEX(initialisert til 1) som beskytter variabelen.
• En semafor ATTENTE(initialisert til 0) som gjør det mulig å sette N-1. Oppgaver på vent.
• En semafor PARTI(initialisert til 0) som lar den siste oppgaven bli satt på vent.
• En variabel Nb_Att(initialisert til 0) som brukes til å telle antall oppgaver som allerede er kommet til synkroniseringsbarrieren.

Barriere : P(MUTEX) Nb_Att++ SI Nb_Att==N ALORS POUR I DE 1 à N-1 FAIRE V(ATTENTE) FIN POUR POUR I DE 1 à N-1 FAIRE P(PARTI) FIN POUR Nb_Att=0 V(MUTEX) SINON V(MUTEX) P(ATTENTE) V(PARTI) FIN SI

Så hvis en prosess kjører raskere enn de andre, vil den ikke kunne låse mutex før alle prosessene er borte.

Eksempler på bruk

Synkroniseringsbarrierer kan brukes til

• Garanti at en eller flere oppgaver har utført en bestemt operasjon.

• Vent til et sett med oppgaver er ferdig

Se også

• Artikkelen om semaforer