|
| |
Synchronizing
processes and resources part 1: mutual exclusion
(Author: Klaus G. Muller; kgmuller at users.sourceforce.net)
Resource synchronizations are classified into two categories, mutual
exclusion and producer/consumer.
When resources are shared, but they must only be accessed by one process at a
time, one has a mutual exclusion situation. Examples are road
intersections, tools, or file sharing by reading and writing processes. In these
situations, resources are requested and released by the same process. A process
requesting an unavailable resource must wait (is blocked).
SimPy has constructs for modelling mutual exclusion situations. The typical
SimPy structure for mutual exclusion is:
class Entity1(Process):
def process1(self):
. . .
yield request, self,
sharedResource # try to get resource
do some
processing
# exclusive use of resource
yield release, self,
sharedResource # free resource
. . .
class Entity2(Process):
def process2(self):
. . .
yield request, self,
sharedResource # try to get resource
do some
processing
# exclusive use of resource
yield release, self,
sharedResource # free resource
. . .
sharedResource=Resource(capacity=1)
|
So let's apply this idiom to the following scenario: in an
information system, there is a shared file which is being written to by one
process and read from by another. Reading and writing are mutually exclusive,
i.e. writing can only take place while there is no read access to the file.
Here is a SimPy implementation of this model and its output for a short run:
"""
One reader, one writer accessing a shared file.
"""
from SimPy.Simulation import *
import random
class Reader(Process):
def readproc(self):
while True:
tstart=now()
yield request,self,sharedFile
print "%s Reading from file: %s, having waited %s"%(now(),self.name,now()-tstart)
yield hold,self,random.uniform(1.0,5.0) #exclusive read access
print "%s Reading complete: %s"%(now(),self.name)
yield release,self,sharedFile
class Writer(Process):
def writeproc(self):
while True:
tstart=now()
yield request,self,sharedFile
print "%s Writing to file, having waited %s"%(now(),now()-tstart)
yield hold,self,random.uniform(0.5,7.0) #exclusive write access
print "%s Writing complete"%now()
yield release,self,sharedFile
sharedFile=Resource(capacity=1,name="File")
initialize()
reader=Reader("Reader")
activate(reader,reader.readproc())
writer=Writer("Writer")
activate(writer,writer.writeproc())
simulate(until=20)
OUTPUT:
0 Reading from file: Reader, having waited 0
4.23032952122 Reading complete: Reader
4.23032952122 Writing to file, having waited 4.23032952122
5.06564281243 Writing complete
5.06564281243 Reading from file: Reader, having waited 0.835313291211
8.4775272844 Reading complete: Reader
8.4775272844 Writing to file, having waited 3.41188447197
10.5635026183 Writing complete
10.5635026183 Reading from file: Reader, having waited 2.08597533391
14.371658521 Reading complete: Reader
14.371658521 Writing to file, having waited 3.80815590267
14.9996580982 Writing complete
14.9996580982 Reading from file: Reader, having waited 0.627999577182
18.4997624652 Reading complete: Reader
18.4997624652 Writing to file, having waited 3.50010436707. |
The shared resource (sharedFile) has capacity=1 so that
only one process may use it at given time.
The output shows that reading and writing are mutually exclusive, they
alternate and do not overlap. The wait times show the time for which the
excluded process is blocked.
To show the generality of this approach, let's look at the same scenario, but
with a number nrReaders of read processes and one write process. Again,
writing and reading are mutually exclusive, but several readers may read at the
same time.
To achieve synchronization, again a shared resource instance is used, but now
with a capacity of nrReaders. A reading process must acquire one resource
unit before reading (thus allowing up to nrReaders concurrent readers);
the writing process must acquire all (nrReaders) resource units
before starting to write, thus excluding all readers.
Here is a SimPy implementation of this model for 3 readers and its output:
"""
nrReader readers, one writer accessing a shared file.
"""
from SimPy.Simulation import *
import random
class Reader(Process):
def readproc(self):
while True:
tstart=now()
yield request,self,sharedFile
print "%s Reading from file %s, having waited %s"%(now(),self.name,now()-tstart)
yield hold,self,random.uniform(1.0,5.0) #exclusive read access
print "%s Reading complete: %s"%(now(),self.name)
yield release,self,sharedFile
class Writer(Process):
def writeproc(self):
while True:
tstart=now()
for i in range(nrReaders):
yield request,self,sharedFile
print "%s Writing to file, having waited %s"%(now(),now()-tstart)
yield hold,self,random.uniform(0.5,7.0) #exclusive write access
print "%s Writing complete"%now()
for i in range(nrReaders):
yield release,self,sharedFile
nrReaders=3
sharedFile=Resource(name="File",capacity=3)
initialize()
for i in range(nrReaders):
reader=Reader("Reader%s"%(i+1))
activate(reader,reader.readproc())
writer=Writer("Writer")
activate(writer,writer.writeproc())
simulate(until=20)
OUTPUT:
0 Reading from file: Reader1, having waited 0
0 Reading from file: Reader2, having waited 0
0 Reading from file: Reader3, having waited 0
2.62367166924 Reading complete: Reader2
2.92811912426 Reading complete: Reader1
2.92811912426 Reading from file: Reader2, having waited 0.304447455028
4.03259900443 Reading complete: Reader2
4.70971649056 Reading complete: Reader3
4.70971649056 Reading from file: Reader1, having waited 1.7815973663
6.85096162167 Reading complete: Reader1
6.85096162167 Reading from file: Reader2, having waited 2.81836261725
10.9671422116 Reading complete: Reader2
10.9671422116 Writing to file, having waited 10.9671422116
14.5144357143 Writing complete
14.5144357143 Reading from file: Reader2, having waited 3.54729350275
14.5144357143 Reading from file: Reader1, having waited 7.66347409267
14.5144357143 Reading from file: Reader3, having waited 9.80471922378
17.4979458581 Reading complete: Reader1
17.8904806599 Reading complete: Reader3
17.8904806599 Reading from file: Reader1, having waited 0.392534801751
19.2332049596 Reading complete: Reader2
19.3016055132 Reading complete: Reader1
19.3016055132 Reading from file: Reader3, having waited 1.41112485334 |
Multiple readers can be seen to be accessing the file at the same
time. The writer has exclusive access.
The waiting time for the writing process shows that the writer has to wait
for a significant amount of time before getting access to the file. To model a
scenario where the writer has priority over the readers, thus getting faster
file access, all one has to do is to
 | use a resource with priorities (sharedFile=Resource(. . .,qType=PriorityQ))
, and |
| give the writer requests a higher priority than the reader requests, for
example:
(in writeproc) yield request,self,sharedFile,2
(in readproc) yield request,self,sharedFile,1 |
|
