Problemet med läsare-skrivare är ett av de viktigaste problemen inom parallell programmering . Den är formulerad så här:
Det finns ett minnesområde som kan läsas och skrivas. Flera trådar har tillgång till det, medan hur många trådar de vill kan läsa samtidigt, men bara en kan skriva. Hur tillhandahåller man ett sådant åtkomstläge?
Du kan klara dig med en vanlig mutex , men det är inte optimalt - datorminne är vanligtvis utformat så att flera trådar fritt kan läsa och skriva det (enda problemet är att det inte finns någon garanti för att variabeln inte plötsligt kommer att förändras under bearbetningen) . Detta problem har flera alternativ, olika och lösningar. Vem man ska prioritera - läsaren eller skribenten - förblir hos programmeraren.
Medan minnet är öppet för läsning, ge läsarna obegränsad åtkomst. Författare kan vänta så länge de vill.
Så fort minst en författare dök upp släpptes ingen annan in. Alla andra kan vara lediga.
Provlösning [1] :
Globala heltal readcount=0, writecount=0; Globala mutexer mutex1, mutex2, w, r LÄSARE hyresgäst mutex1.enter readcount = readcount + 1 om readcount=1 så w.enter mutex1.leave r. lämna ...läsning... mutex1.enter readcount = readcount - 1 om readcount = 0 så w.leave mutex1.leave FÖRFATTARE mutex2.enter writecount = writecount + 1 om writecount=1 så r.enter mutex2.leave w.enter ...vi skriver... w. lämna mutex2.enter writecount = writecount - 1 om writecount = 0 så r.leave mutex2.leaveUndvik driftstopp. Med andra ord: oberoende av andra trådars handlingar måste läsaren eller skribenten passera spärren på ändlig tid.
Med andra ord, ingen tråd (läsare eller skribent) bör vänta för länge för att skaffa ett lås; lock capture-funktionen bör efter en tid, om låset går sönder, återgå med lock failed- flaggan så att tråden inte är ledig och kan göra andra saker. Ofta är denna tid noll: fångstfunktionen, om fångsten inte är möjlig just nu, återkommer omedelbart.
Globala mutex: no_writers, no_readers, counter_mutex Globala heltal: nreaders=0 Lokala heltal: föregående, nuvarande FÖRFATTARE: no_writers.enter no_readers.enter ... skrivande .... no_writers.leave no_readers.leave LÄSARE: no_writers.enter counter_mutex.enter preve:= nläsare nreaders := nreaders + 1 om prev = 0 så no_readers.enter counter_mutex.leave no_writers.leave ...läsning... counter_mutex.enter nreaderst:= nreaders - 1; currente:= nreaders; om aktuell = 0 då no_readers.leave counter_mutex.leave;C-kod för gcc gcc -o rw -lpthread -lm rewr.c
#include <pthread.h> #include <stdio.h> #inkludera <math.h> #include <stdlib.h> #inkludera <semaphore.h> #define M 4 //num of WR #define N 3 //num of RE unsigned int iter ; //iteration sem_t accessM , readresM , orderM ; //sem. osignerade int- läsare = 0 ; // Antal läsare som kommer åt resursen void * läsare ( void * prem ) { int num1 =* ( int * ) prm ; int i = 0 , r ; för ( i ; i < iter ; i ++ ) { if ( sem_wait ( & orderM ) == 0 ) printf ( "%d Reader %d köade__________W%d \n " , i , num1 , num1 ); // Kom ihåg vår ankomstordning sem_wait ( & readresM ); // Vi kommer att manipulera läsarräknaren if ( läsare == 0 ) // Om det för närvarande inte finns några läsare (vi kom först)... sem_wait ( & accessM ); // ...begär exklusiv tillgång till resursen för läsare läsare ++ ; // Observera att det nu finns ytterligare en läsare sem_post ( & orderM ); // Release order of ankomst semafor (vi har blivit serverad) sem_post ( & readresM ); // Vi är klara med att komma åt antalet läsare för nu printf ( "%d Läsare %d________________W%d fungerar \n " , i , num1 , num1 ); // Här kan läsaren läsa resursen efter behag r = 1 + rand () % 4 ; sömn ( r ); sem_wait ( & readresM ); // Vi kommer att manipulera läsarnas motläsare -- ; // Vi åker, det finns en läsare mindre if ( läsare == 0 ) // Om det inte finns fler läsare som läser just nu... sem_post ( & accessM ); // ...släpp exklusiv åtkomst till resursen sem_post ( & readresM ); // Vi är klara med att komma åt antalet läsare för nu } } void * författare ( void * prem ) { int num2 =* ( int * ) prm ; int j = 0 , r ; för ( j ; j < iter ; j ++ ) { if ( sem_wait ( & orderM ) == 0 ) printf ( "%d Writer %d köade__________P%d \n " , j , num2 , num2 ); // Kom ihåg vår ankomstordning sem_wait ( & accessM ); // Begär exklusiv åtkomst till resursen sem_post ( & orderM ); // Release order of ankomst semafor (vi har blivit serverad) printf ( "%d Writer %d________________P%d \n " , j , num2 , num2 ); // Här kan skribenten modifiera resursen efter behag r = 1 + rand () % 4 ; sömn ( r ); sem_post ( & accessM ); // Släpp exklusiv åtkomst till resursen } } void main () { pthread_t threadRE [ N ]; pthread_t threadWR [ M ]; sem_init ( & accessM , 0 , 1 ); sem_init ( & readresM , 0 , 1 ); sem_init ( & orderM , 0 , 1 ); printf ( "Ange antal iterationer: " ); scanf ( "%d" , & iter ); printf ( "Iter QUEUE/EXECUTION \n " ); int i ; för ( i = 0 ; i < M ; i ++ ) { pthread_create ( & ( threadWR [ i ]), NULL , writer ,( void * ) & i ); } för ( i = 0 ; i < N ; i ++ ) { pthread_create ( & ( threadRE [ i ]), NULL , reader ,( void * ) & i ); } för ( i = 0 ; i < N ; i ++ ) { pthread_join ( trådRE [ i ], NULL ); } för ( i = 0 ; i < M ; i ++ ) { pthread_join ( trådWR [ i ], NULL ); } sem_destroy ( & accessM ); sem_destroy ( & readresM ); sem_destroy ( & orderM ); }Många läsare XOR en författare (XOR-exklusiv eller ) anses ofta vara en invariant av detta problem . Detta är inte sant, eftersom situationen där det varken finns läsare eller författare också är korrekt.
Invarianten kan uttryckas med följande påstående:
författare == 0 ELLER författare == 1 OCH läsare == 0där författare är antalet författare, är läsare antalet läsare.
Ofta är en enkel minnesskyddande mutex suboptimal. Till exempel i ett onlinespel ändras listan över spelrum sällan - när en av spelarna bestämmer sig för att öppna ett nytt rum, till exempel en gång med några sekunders mellanrum. Den läses dussintals gånger på en sekund, och det är ingen mening att rada upp klienter för detta .
Liknande mekanismer (så kallad läs-skrivlåsning ) finns i många programmeringsspråk och bibliotek. Till exempel.