A Robust POSIX Condition Variable Technique.

A Robust POSIX Condition Variable Technique.

Post by Chris Thom » Mon, 13 Aug 2007 08:16:01


ere is a simple method to implement condition variables that completely
adhere themselves to the Pthread Standard. The condvars are fair, and has
the 100% correct unblocking semantics that calls into
'pthread_cond_broadcast' will be expecting. It has conforming behaviour with
regard to calling 'pthread_cond_destroy' while there are wait generations in
progress. The Standard explicitly states that a condition variable can be
destroyed _immediately_ after all the threads that are blocked on it are
awakened. Any robust implementation of 'pthread_cond_destroy' simply must
take that statement into account if it wants to be able to call it self
_Standard conforming_ in any sense of the term. The method also has correct
built-in initialize once behavior. Finally, the algorithm is based on
lock-based synchronization for the moment for simplicity. This could be made
lock-free but that is a whole other topic. ;^)

The technique is compatible with shared memory for process-wide
synchronization objects that condvars, or some other primitive can use to
implement their internal waitset functionality. Here is extremely brief
pseudo-code:
----------



/* pointer based hashed-locking table API
_________________________________________________*/
extern void hptr_lock(void* const);
extern void hptr_unlock(void* const);




/* a waitset "descriptor"
_________________________________________________*/
struct wset_t {
wset_t *nx; /* linked-list anchor */
sema_t q; /* wait-queue */
int mref; /* master reference-count */
int pref; /* private reference-count */
};


/* obtain the depth of the wait-queue */
#define wset_qdepth(_t) \
((_t)->mref + (_t)-> pref)


/* set references */
#define wset_refinit(_t, _mref, _pref) \
(_t)->mref = (_mref); \
(_t)->pref = (_pref)


/* process-id based hashed-waitset table API */
extern west_t* hptr_wset_cachepop_try(pid_t);
extern west_t* hptr_wset_cachepop_wait(pid_t, void* const);
extern void hptr_wset_cachepush(pid_t, wset_t*);




/* a condition variable
_________________________________________________*/
struct condvar_t {
waitset_t *q; /* wait-queue */
};


/* a simple condvar API. */
int condvar_init(condvar_t *_t, /* attrs */) {
hptr_lock(_t);
_t->q = 0;
hptr_unlock(_t);
return 0;
}


int condvar_broadcast(condvar_t *_t) {
wset_t *wset;

hptr_lock(_t);
wset = _t->q;
if (wset) {
int qdepth = wset_qdepth(wset);

if (qdepth) {
sema_post(wset->q, qdepth);
}

wset->pref += wset->mref;
if (wset->pref) {
wset = 0;
}
}
hptr_unlock(_t);

if (wset) {
/* wset is quiescent, so cache it */
hptr_wset_cachepush(getpid(), wset);
}

return 0;
}


int condvar_signal(condvar_t *_t) {
/* signals and timeouts in further postings. :^) */
return condvar_broadcast(_t);
}


int condvar_destroy(condvar_t *_t) {
/* simply broadcast to destroy the condvar state. */
return condvar_broadcast(_t);
}


int condvar_wait(condvar_t *_t, mutex_t *_extmtx) {
pid_t pid = getpid();
wset_t *wset;


/* grab/acquire waitset */
hptr_lock(_t);
wset = _t->q;

if (! wset) {
/* unlocks-and-relocks hptr_lock(_t)
if needs to block for a waitset: */
_t->q = hptr_wset_cachepop_wait(pid, _t);

/* hptr_lock(_t) is locked,
 
 
 

A Robust POSIX Condition Variable Technique.

Post by Chris Thom » Mon, 13 Aug 2007 08:23:46

> Barring any initial typos is the quick pseudo-code I just sketched, well,

Well, I could only find one single typo so far:

The condvar_broadcast function should look like this:



int condvar_broadcast(condvar_t *_t) {
wset_t *wset;

hptr_lock(_t);
wset = _t->q;
if (wset) {
int qdepth = wset_qdepth(wset);

if (qdepth) {
sema_post(wset->q, qdepth);
}

wset->pref += wset->mref;
if (wset->pref) {
wset = 0;
}


/**************
I FORGOT TO SET A PTR TO NULL!
the following line needs to be added:
___________________________________________________*/
_t->q = 0;


}
hptr_unlock(_t);

if (wset) {
/* wset is quiescent, so cache it */
hptr_wset_cachepush(getpid(), wset);
}





This is the only typo I can find. I have working code, but don't want to
post all of that stuff. I will continue to heavily examine my posted
code-sketch and will make and clearly announce all fixes. That I promise!

 
 
 

A Robust POSIX Condition Variable Technique.

Post by Chris Thom » Mon, 13 Aug 2007 08:36:02

There is one typo where I call a semaphore wait with a pointer to the
waitset instead of the semaphore handle:

sema_wait(wset);


That statement should read as follows:


sema_wait(wset->q);



...Continuing my examination....



If you have any questions, fire away!

:^)
 
 
 

A Robust POSIX Condition Variable Technique.

Post by Chris Thom » Mon, 13 Aug 2007 09:02:36

I found another one.

[...]


/********^^^^^^^^^^^^^^^^^^^^^^^^^^^^***********/

That last line need to read as follows:

wset = _t->q = hptr_wset_cachepop_wait(pid, _t);





[...]




This is going to be 100% bug-free within the hour!
 
 
 

A Robust POSIX Condition Variable Technique.

Post by Ian Collin » Mon, 13 Aug 2007 09:28:03


Let us know when it's finished :)

--
Ian Collins.
 
 
 

A Robust POSIX Condition Variable Technique.

Post by Chris Thom » Mon, 13 Aug 2007 10:59:23


Indeed I will... It seems as though I am having a hard time detecting any
more of the crappy syntax/type errors after I apply all of the fixes I
mentioned. Luckily, the algorithm works well, and I hope that my fixes to
the code-sketch will help an interested reader to better understand it as an
outline of a possible implementation. IMVHO, this technique is a fairly
simple method, therefore I will continue to examine the sketch; anyway, I
owe it to this group: if I post something that has a bug, I want to be the
first one to post the fix! ;^)

Even if the bug is fairly obvious, and the fix is obvious like this one:

http://www.yqcomputer.com/

I still want to post any and all fixes no matter how trivial.
 
 
 

A Robust POSIX Condition Variable Technique.

Post by Chris Thom » Mon, 13 Aug 2007 14:52:40


[...]

Ahhh... I misspelled the typename 'wset_t' with 'west' in the hptr_wset_*
function declarations.