Thursday, July 22, 2010

MVars in Objective-C

MVars (mutable variables) are a well-known synchronization primitive in the functional programming language Haskell (see here for the API documentation). An MVar is like a box, which can be either empty or full. A thread trying to read from an MVar blocks until the MVar becomes full, a thread writing to an MVar blocks until the MVar becomes empty.

Recently, I had the need for MVars in Objective-C. I’m sure, I could have solved the problem with other synchronization mechanisms from Apple’s API, but as we all know, programmers are too lazy to read API documentation and programming MVars in Objective-C is fun anyway. I started with this simple interface for MVars:

@interface MVar : NSObject {
  @private
    NSCondition *emptyCond;
    NSCondition *fullCond;
    id value;
    BOOL state;
}
// Reads the current value from the MVar, blocks until a value is available.
- (id)take;
// Stores a new value into the MVar, blocks until the MVar is empty.
- (void)put:(id)val;
// Creates an MVar that is initial filled with the given value.
- (id)initWithValue:(id)val;
@end
Here is a trivial nonsense program that uses the MVar interface to solve the producer-consumer problem:
#import "MVar.h"
#define N 1000
@implementation MVarTest
- (void)producer:(MVar *)mvar {
    for (NSInteger i = 0; i < N; i++) {
        [mvar put:[NSNumber numberWithInteger:i]];
    }
}

- (void)consumer:(MVar *)mvar {
    for (NSInteger i = 0; i < N; i++) {
        NSNumber *n = [mvar take];
        // do something with n
    }
}

- (void)main {
    MVar *mvar = [[[MVar alloc] init] autorelease];
    [NSThread detachNewThreadSelector:@selector(producer:)
                       toTarget:self withObject:mvar];
    [self consumer:mvar];
}
@end

Let's come back to the implementation of MVars. The condition variables emptyCond and fullCond signal that the MVar is empty/full. The variable state stores the stateof the MVar (empty/full). With this in hand, the actual implementation of the MVar class is straightforward:

#import "MVar.h"
#import "Common.h";

#define STATE BOOL
#define EMPTY NO
#define FULL YES

@interface MVar ()
@property (nonatomic,retain) id value;
@end

@implementation MVar

// Notifies waiting threads that the state of the MVar has changed.
- (void)signal:(STATE)aState {
    NSCondition *cond = (aState == FULL) ? fullCond : emptyCond;
    [cond lock];
    self->state = aState;
    [cond signal];
    [cond unlock];
}

- (id)take {
    [fullCond lock];
    while (state != FULL) {
        [fullCond wait];
    }
    id res = self.value;
    self.value = nil;
    [fullCond unlock];
    [self signal:EMPTY];
    return res;
}

- (void)put:(id)aValue {
    [emptyCond lock];
    while (state != EMPTY) {
        [emptyCond wait];
    }
    self.value = aValue;
    [emptyCond unlock];
    [self signal:FULL];
}

// Creates an MVar that is initially empty.
- (id)init {
    if ((self = [super init])) {
        self->emptyCond = [[NSCondition alloc] init];
        self->fullCond = [[NSCondition alloc] init];
        [self signal:EMPTY];
    }
    return self;
}

- (id)initWithValue:(id)aValue {
    self = [self init];
    [self put:aValue];
    return self;
}

- (void)dealloc {
    [emptyCond release];
    [fullCond release];
    [value release];
    [super dealloc];
}

@synthesize value;
@end

Please let me know if you find any bugs in the code shown in this article.

Happy hacking and have fun!

Author: Stefan

No comments:

Post a Comment