Lukija-kirjoitusongelma on yksi tärkeimmistä rinnakkaisohjelmoinnin ongelmista . Se on muotoiltu näin:
Siellä on muistialue , jota voidaan lukea ja kirjoittaa. Useilla säikeillä on pääsy siihen, kun taas niin monta säiettä kuin he haluavat lukea samanaikaisesti, mutta vain yksi voi kirjoittaa. Kuinka tarjota tällainen pääsytila?
Tavallisella mutexilla pärjää , mutta tämä ei ole optimaalista - tietokoneen muisti on yleensä suunniteltu niin, että useat säikeet voivat vapaasti lukea ja kirjoittaa sitä (ainoa ongelma on, että ei ole takeita siitä, että muuttuja ei muutu yhtäkkiä käsittelyn aikana) . Tällä ongelmalla on useita vaihtoehtoja, erilaisia ja ratkaisuja. Kenelle antaa etusija - lukijalle vai kirjoittajalle - jää ohjelmoijalle.
Kun muisti on avoinna lukemista varten, anna lukijoille rajoittamaton pääsy. Kirjoittajat voivat odottaa niin kauan kuin haluavat.
Heti kun ainakin yksi kirjoittaja ilmestyi, ketään muuta ei päästetty sisään. Kaikki muut voivat olla käyttämättöminä.
Esimerkkiratkaisu [1] :
Globaalit kokonaisluvut lukumäärä=0, kirjoitusmäärä=0; Globaalit mutexit mutex1, mutex2, w, r LUKIJA r.enter mutex1.enter lukumäärä = lukumäärä + 1 jos lukumäärä=1, niin w.enter mutex1.leave r.leave ...lukeminen... mutex1.enter lukumäärä = lukumäärä - 1 jos lukuluku = 0 niin w.leave mutex1.leave KIRJAILIJA mutex2.enter kirjoitusmäärä = kirjoitusmäärä + 1 jos writecount=1 niin r.enter mutex2.leave w.enter ...me kirjoitamme... w.jätä mutex2.enter kirjoitusmäärä = kirjoitusmäärä - 1 jos kirjoitusmäärä = 0 niin r.leave mutex2.leaveVältä seisokkeja. Toisin sanoen: muiden säikeiden toiminnasta riippumatta lukijan tai kirjoittajan on ylitettävä raja rajallisessa ajassa.
Toisin sanoen minkään ketjun (lukijan tai kirjoittajan) ei pitäisi odottaa liian kauan lukon saamista; lukon sieppaustoiminnon pitäisi jonkin ajan kuluttua, jos lukko epäonnistuu, palata lukko epäonnistui -lipulla , jotta lanka ei ole tyhjäkäynnillä ja voi tehdä muita asioita. Usein tämä aika on nolla: sieppaustoiminto palaa välittömästi, jos sieppaus ei ole juuri nyt mahdollista.
Globaalit mutexit: no_writers, no_readers, counter_mutex Globaalit kokonaisluvut: nreaders=0 Paikalliset kokonaisluvut: edellinen, nykyinen KIRJAILIJA: no_writers.enter no_readers.enter ... kirjoittaminen .... no_writers.leave no_readers.leave LUKIJA: no_writers.enter counter_mutex.enter preve:= nreaders nreaders := nreaders + 1 jos edellinen = 0 niin no_readers.enter counter_mutex.leave no_writers.leave ...lukeminen... counter_mutex.enter nreaderst:= nreaders - 1; currente:= nreaders; jos nykyinen = 0 niin no_readers.leave counter_mutex.leave;C-koodi gcc:lle gcc -o rw -lpthread -lm rewr.c
#include <pthread.h> #include <stdio.h> #include <math.h> #include <stdlib.h> #include <semafori.h> #define M 4 //num of WR #define N 3 //numero RE unsigned int iter ; //iteraatio sem_t accessM , uudelleenosoiteM , järjestysM ; //sem. allekirjoittamattomat int- lukijat = 0 ; // Resurssia käyttävien lukijoiden lukumäärä void * lukija ( void * prem ) { int num1 =* ( int * ) prm ; int i = 0 , r ; for ( i ; i < iter ; i ++ ) { if ( sem_wait ( & orderM ) == 0 ) printf ( "%d Reader %d jonossa__________W%d \n " , i , numero1 , numero1 ); // Muista saapumisjärjestys sem_wait ( & readresM ); // Käsittelemme lukijalaskuria if ( lukijat == 0 ) // Jos lukijoita ei tällä hetkellä ole (tulimme ensin)... sem_wait ( & accessM ); // ...pyytää eksklusiivista pääsyä resurssiin lukijoille lukijoille ++ ; // Huomaa, että nyt on yksi lukija lisää sem_post ( & orderM ); // Vapauta saapumisjärjestys semafori (meitä on palveltu) sem_post ( & readresM ); // Lukijamäärä on toistaiseksi päättynyt printf ( "%d Reader %d________________W%d toimii \n " , i , num1 , num1 ); // Täällä lukija voi lukea resurssin halutessaan r = 1 + rand () % 4 ; nukkua ( r ); sem_wait ( & readresM ); // Me manipuloimme lukijoita laskurilukijoita -- ; // Lähdemme, on yksi lukija vähemmän jos ( lukijat == 0 ) // Jos ei ole enempää lukijoita, jotka lukevat... sem_post ( & accessM ); // ...vapauta yksinoikeus resurssiin sem_post ( & readresM ); // Lukijamäärät ovat nyt käytössämme } } void * kirjoittaja ( void * prem ) { int num2 =* ( int * ) prm ; int j = 0 , r ; for ( j ; j < iter ; j ++ ) { if ( sem_wait ( & orderM ) == 0 ) printf ( "%d Writer %d jonossa__________P%d \n " , j , numero2 , numero2 ); // Muista saapumisjärjestys sem_wait ( & accessM ); // Pyydä yksinoikeutta resurssiin sem_post ( & orderM ); // Vapauta saapumissemafori (meitä on palveltu) printf ( "%d Writer %d________________P%d \n " , j , num2 , num2 ); // Tässä kirjoittaja voi muokata resurssia mielensä mukaan r = 1 + rand () % 4 ; nukkua ( r ); sem_post ( & accessM ); // Vapauta yksinoikeus resurssiin } } tyhjä pää () { pthread_t threadRE [ N ]; pthread_t lankaWR [ M ]; sem_init ( & accessM , 0 , 1 ); sem_init ( & readresM , 0 , 1 ); sem_init ( & orderM , 0 , 1 ); printf ( "Anna iteraatioiden määrä: " ); scanf ( "%d" , & iter ); printf ( "Iter JONO/SUORITUS \n " ); int i ; for ( i = 0 ; i < M ; i ++ ) { pthread_create ( & ( threadWR [ i ]), NULL , kirjoittaja ,( void * ) & i ); } for ( i = 0 ; i < N ; i ++ ) { pthread_create ( & ( threadRE [ i ]), NULL , lukija ,( void * ) & i ); } for ( i = 0 ; i < N ; i ++ ) { pthread_join ( threadRE [ i ], NULL ); } for ( i = 0 ; i < M ; i ++ ) { pthread_join ( threadWR [ i ], NULL ); } sem_destroy ( & accessM ); sem_destroy ( & readresM ); sem_destroy ( & orderM ); }Monet lukijat XOR yksi kirjoittaja (XOR - yksinomainen tai ) pidetään usein tämän ongelman muuttumattomana . Tämä ei pidä paikkaansa, koska tilanne, jossa ei ole lukijoita eikä kirjoittajia, on myös oikea.
Invariantti voidaan ilmaista seuraavalla lauseella:
kirjoittajia == 0 TAI kirjoittajia == 1 JA lukijoita == 0missä kirjoittajat on kirjoittajien määrä, lukijat on lukijoiden määrä.
Usein yksinkertainen muistia suojaava mutex ei ole optimaalinen. Esimerkiksi online -pelissä pelihuoneiden lista muuttuu harvoin - kun joku pelaajista päättää avata uuden huoneen esimerkiksi muutaman sekunnin välein. Se luetaan kymmeniä kertoja yhdessä sekunnissa, eikä ole mitään järkeä järjestellä asiakkaita tätä varten .
Samanlaisia mekanismeja (ns. luku-kirjoituslukitus ) on olemassa monissa ohjelmointikielissä ja kirjastoissa. Esimerkiksi.