Re: Most elegant solution to Reader/Writer Problem with Objective-C?
Re: Most elegant solution to Reader/Writer Problem with Objective-C?
- Subject: Re: Most elegant solution to Reader/Writer Problem with Objective-C?
- From: Daryn <email@hidden>
- Date: Thu, 19 Jun 2003 00:50:25 -0500
Hi Lachlan,
I doubt this is the most elegant, or possibly even correct, but perhaps
this will get you going in the right direction or inspire someone else.
This is completely untested code that I quickly wrote in mail...
enum { READER,WRITER,GO };
- (id)init {
if (self = [super init]) {
mutex = [[NSLock alloc] init];
queue = [[NSMutableArray alloc] init];
readers = 0;
writing = NO;
}
return self;
}
- (void)queueForRead {
[mutex lock];
id lock = nil;
if (writing || [queue count]) {
lock = [[NSConditionLock alloc] initWithCondition:READER];
[queue insertObject:lock atIndex:0];
} else {
// increment now since we aren't going to block
++readers;
}
[mutex unlock];
// wait on lock if queued
if (lock) {
[lock lockWhenCondition:GO];
[lock release];
}
// do whatever
[self doRead];
[mutex lock];
// tell the next writer to go if we are the last pending reader
if (!--readers && [queue count]) {
writing = YES;
[[queue lastObject] unlockWithCondition:GO];
[queue removeLastObject];
}
[mutex unlock];
}
- (void)queueForWrite {
[mutex lock];
id lock = nil;
if (readers || writing || [queue count]) {
lock = [[NSConditionLock alloc] initWithCondition:WRITER];
[queue insertObject:lock atIndex:0];
} else {
// set now since we aren't going to block
writing = YES;
}
[mutex unlock];
// wait on lock if queued
if (lock) {
[lock lockWhenCondition:GO];
[lock release];
}
// do whatever
[self doWrite];
[mutex lock];
writing = NO;
BOOL done = NO;
// drain the queue until empty or a writer is seen
while (!done && !writing && [queue count]) {
lock = [queue lastObject];
switch ([lock condition]) {
case WRITER:
// writer can go if no readers
if (!readers) {
writing = YES;
} else {
done = YES;
}
break;
case READER:
// let all the readers go
readers++;
break;
default:
NSLog(@"And you may ask yourself, well, how did I get here?"); }
if (!done) {
[lock unlockWithCondition:GO];
[queue removeLastObject];
}
}
[mutex unlock];
}
On Wednesday, June 18, 2003, at 10:56 PM, Lachlan Deck wrote:
Hi all,
I'm doing a presentation for Uni tomorrow and I'm trying to whip up
some examples.
What would be the most elegant solution in Objective-C to solving the
Reader/Writer problem (i.e., allow multiple reader threads to run
concurrently should there be no writer(s); allow at most one writer,
blocking other threads) using, for example the below algorithm?
Thanks very much!
Any examples would be great, but one which does the following would be
even better: (or if there's a better algorithm that would be great
too)...
Readers:
a) concurrent readers activity (i.e., if no writers - go ahead.
Incrementing/Decrementing count on entering and exiting of sections).
b) if (waiting writers) new readers join a new queue instance that
corresponds to a single writer in the queue.
Writers:
c) at most one writer activity exclusive of any other threads (i.e.,
if no readers or writers - go ahead).
d) if active readers or active writer, this writer is placed as the
key at the end of the queue (with any subsequent readers entering
joining the list associated with this writer) and awakes when it is
the at the head of the queue and there are no active readers. When it
finishes, the waiting readers associated with it in the queue are
signalled to proceed (when they finish the next writer goes and so we
go on...)
So we have the following,
- A count of active readers
- A bool for an active writer
- A queue that maintains a list of waiting threads where:
+ Each entry in the queue represents a waiting writer (so the queue
count is the waiting writer count (less 1 if activeWriter is true))
+ Each writer in the queue is associated (or mapped) with a list of
waiting readers. i.e., as each readers 'enters', if there are waiting
writers, it is added to a list with other waiting readers (associated
with the last waiting writer in the queue).
Thanks muchly.
with regards,
--
Lachlan Deck
email@hidden
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.
Daryn
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.