ReaderWriterLock
Verfasst: 15.09.2011 02:03
Hallo Leute,
da hier im Forum immer mehr über Threads und deren Handling untereinander gesprochen wird, habe ich mir gedacht ich trage auch mal etwas dazu bei und biete hiermit ein Interface zur Lösung des Reader-Writer-Problems an.
Die Handhabung ist einfach. Für eine Datenstruktur, auf der aus verschiedenen Threads heraus gelesen und geschrieben werden soll, muss man einfach nur vor und nach jedem Lesen und Schreiben die entsprechenden Methoden aus dem Interface aufrufen und schon können sich keine zwei Threads mehr in die Quere kommen. Es ist immer gewährleistet, dass ein Lese-Thread keine halben Daten liest und dass ein Schreib-Thread noch am Schreiben ist während bereits aus der Datenstruktur gelesen wird.
Hier also zunächst das Interface und nachfolgend ein simples Beispiel mit einer zugegebenermaßen simplen Datenstruktur, nämlich einer LinkedList vom Typ String. Zur Vervollständigung sei noch gesagt, dass man trotzdem bei mehreren Datenstrukturen, die Strings enthalten und die verschiedene ReaderWriterLocks nutzen, die ThreadSafe-Option in den Compiler-Einstellungen aktivieren muss. Für dieses Beispiel ist dies allerdings nicht notwendig.
Womöglich werde ich in Zukunft öfter Beispiele aus dem Bereich der sicheren Thread-Kommunikation bringen. Als nächstes habe ich z.B. an geschwindigkeits-optimierte thread-sichere LinkedLists gedacht.
ReaderWriterLock.pbi
ReaderWriterLock_Example.pb
da hier im Forum immer mehr über Threads und deren Handling untereinander gesprochen wird, habe ich mir gedacht ich trage auch mal etwas dazu bei und biete hiermit ein Interface zur Lösung des Reader-Writer-Problems an.
Die Handhabung ist einfach. Für eine Datenstruktur, auf der aus verschiedenen Threads heraus gelesen und geschrieben werden soll, muss man einfach nur vor und nach jedem Lesen und Schreiben die entsprechenden Methoden aus dem Interface aufrufen und schon können sich keine zwei Threads mehr in die Quere kommen. Es ist immer gewährleistet, dass ein Lese-Thread keine halben Daten liest und dass ein Schreib-Thread noch am Schreiben ist während bereits aus der Datenstruktur gelesen wird.
Hier also zunächst das Interface und nachfolgend ein simples Beispiel mit einer zugegebenermaßen simplen Datenstruktur, nämlich einer LinkedList vom Typ String. Zur Vervollständigung sei noch gesagt, dass man trotzdem bei mehreren Datenstrukturen, die Strings enthalten und die verschiedene ReaderWriterLocks nutzen, die ThreadSafe-Option in den Compiler-Einstellungen aktivieren muss. Für dieses Beispiel ist dies allerdings nicht notwendig.
Womöglich werde ich in Zukunft öfter Beispiele aus dem Bereich der sicheren Thread-Kommunikation bringen. Als nächstes habe ich z.B. an geschwindigkeits-optimierte thread-sichere LinkedLists gedacht.
ReaderWriterLock.pbi
Code: Alles auswählen
;get from http://en.wikipedia.org/wiki/Readers-writers_problem
;---------------------------------------------------------
; int readcount, writecount; (initial value = 0)
; semaphore mutex 1, mutex 2, mutex 3, w, r ; (initial value = 1)
;
; READER
; P(mutex 3);
; P(r);
; P(mutex 1);
; readcount := readcount + 1;
; If readcount = 1 then P(w);
; V(mutex 1);
; V(r);
; V(mutex 3);
;
; reading is done
;
; P(mutex 1);
; readcount := readcount - 1;
; If readcount = 0 then V(w);
; V(mutex 1);
;
;
; WRITER
; P(mutex 2);
; writecount := writecount + 1;
; If writecount = 1 then P(r);
; V(mutex 2);
;
; P(w);
; writing is performed
; V(w);
;
; P(mutex 2);
; writecount := writecount - 1;
; If writecount = 0 then V(r);
; V(mutex 2);
EnableExplicit
Interface ReaderWriterLock
free.i()
beginReading.i()
endReading.i()
beginWriting.i()
endWriting.i()
EndInterface
Structure ReaderWriterLock_S
*vTable
readCount.i
writeCount.i
mutex1.i
mutex2.i
mutex3.i
w.i
r.i
EndStructure
Procedure.i newReaderWriterLock()
Protected *this.ReaderWriterLock_S
*this = AllocateMemory(SizeOf(ReaderWriterLock_S))
If (Not *this)
ProcedureReturn #False
EndIf
InitializeStructure(*this, ReaderWriterLock_S)
With *this
\vTable = ?ReaderWriterLock_vTable
\readCount = 0
\writeCount = 0
\mutex1 = CreateSemaphore(1)
\mutex2 = CreateSemaphore(1)
\mutex3 = CreateSemaphore(1)
\w = CreateSemaphore(1)
\r = CreateSemaphore(1)
EndWith
ProcedureReturn *this
EndProcedure
Procedure.i ReaderWriterLock_free(*this.ReaderWriterLock_S)
With *this
FreeSemaphore(*this\mutex1)
FreeSemaphore(*this\mutex2)
FreeSemaphore(*this\mutex3)
FreeSemaphore(*this\w)
FreeSemaphore(*this\r)
EndWith
ClearStructure(*this, ReaderWriterLock_S)
ProcedureReturn #True
EndProcedure
; P(mutex 3);
; P(r);
; P(mutex 1);
; readcount := readcount + 1;
; If readcount = 1 then P(w);
; V(mutex 1);
; V(r);
; V(mutex 3);
Procedure.i ReaderWriterLock_beginReading(*this.ReaderWriterLock_S)
With *this
WaitSemaphore(\mutex3)
WaitSemaphore(\r)
WaitSemaphore(\mutex1)
\readCount + 1
If (\readCount = 1)
WaitSemaphore(\w)
EndIf
SignalSemaphore(\mutex1)
SignalSemaphore(\r)
SignalSemaphore(\mutex3)
EndWith
EndProcedure
; P(mutex 1);
; readcount := readcount - 1;
; If readcount = 0 then V(w);
; V(mutex 1);
Procedure.i ReaderWriterLock_endReading(*this.ReaderWriterLock_S)
With *this
WaitSemaphore(\mutex1)
\readCount - 1
If (\readCount = 0)
SignalSemaphore(\w)
EndIf
SignalSemaphore(\mutex1)
EndWith
EndProcedure
; P(mutex 2);
; writecount := writecount + 1;
; If writecount = 1 then P(r);
; V(mutex 2);
;
; P(w);
Procedure.i ReaderWriterLock_beginWriting(*this.ReaderWriterLock_S)
With *this
WaitSemaphore(\mutex2)
\writeCount + 1
If (\writeCount = 1)
WaitSemaphore(\r)
EndIf
SignalSemaphore(\mutex2)
WaitSemaphore(\w)
EndWith
EndProcedure
; V(w);
;
; P(mutex 2);
; writecount := writecount - 1;
; If writecount = 0 then V(r);
; V(mutex 2);
Procedure.i ReaderWriterLock_endWriting(*this.ReaderWriterLock_S)
With *this
SignalSemaphore(\w)
WaitSemaphore(\mutex2)
\writeCount - 1
If (\writeCount = 0)
SignalSemaphore(\r)
EndIf
SignalSemaphore(\mutex2)
EndWith
EndProcedure
DataSection ;{ ReaderWriterLock_vTable
ReaderWriterLock_vTable:
Data.i @ReaderWriterLock_free()
Data.i @ReaderWriterLock_beginReading()
Data.i @ReaderWriterLock_endReading()
Data.i @ReaderWriterLock_beginWriting()
Data.i @ReaderWriterLock_endWriting()
EndDataSection ;}Code: Alles auswählen
EnableExplicit
XIncludeFile "ReaderWriterLock.pbi"
; 46 public Static void main(String[] args) {
; 47 Dictionary dictionary = new Dictionary();
; 48 dictionary.set("java", "object oriented");
; 49 dictionary.set("linux", "rulez");
; 50 Writer writer = new Writer(dictionary, "Mr. Writer");
; 51 Reader reader1 = new Reader(dictionary ,"Mrs Reader 1");
; 52 Reader reader2 = new Reader(dictionary ,"Mrs Reader 2");
; 53 Reader reader3 = new Reader(dictionary ,"Mrs Reader 3");
; 54 Reader reader4 = new Reader(dictionary ,"Mrs Reader 4");
; 55 Reader reader5 = new Reader(dictionary ,"Mrs Reader 5");
; 56 writer.start();
; 57 reader1.start();
; 58 reader2.start();
; 59 reader3.start();
; 60 reader4.start();
; 61 reader5.start();
; 62 }
Structure ThreadData
*rwl.ReaderWriterLock
List someData.s()
quit.i
EndStructure
Procedure Writer(*threadData.ThreadData)
With *threadData
While (Not \quit)
\rwl\beginWriting()
If (AddElement(\someData()))
\someData() = "Data: " + Str(ElapsedMilliseconds()) + " - " + Str(Random(1000))
EndIf
\rwl\endWriting()
Delay(100)
Wend
EndWith
EndProcedure
Procedure Reader(*threadData.ThreadData)
With *threadData
While (Not \quit)
\rwl\beginReading()
Debug "someData():"
ForEach \someData()
Debug \someData()
Next
\rwl\endReading()
Delay(100)
Wend
EndWith
EndProcedure
Define threadData.ThreadData
With threadData
\rwl = newReaderWriterLock()
\quit = #False
EndWith
Define.i writer, reader1, reader2, reader3, reader4, reader5
writer = CreateThread(@Writer(), @threadData)
reader1 = CreateThread(@Reader(), @threadData)
reader2 = CreateThread(@Reader(), @threadData)
reader3 = CreateThread(@Reader(), @threadData)
reader4 = CreateThread(@Reader(), @threadData)
reader5 = CreateThread(@Reader(), @threadData)
Delay(2000)
threadData\quit = #True
WaitThread(writer)
WaitThread(reader1)
WaitThread(reader2)
WaitThread(reader3)
WaitThread(reader4)
WaitThread(reader5)
threadData\rwl\free()