Joe Seighs awesome rw-spinlock with a twist; the beauty of eventcounts...

68 views
Skip to first unread message

Chris M. Thomasson

unread,
Apr 26, 2009, 12:58:56 AM4/26/09
to
You can use an eventcount to add conditional blocking behavior to the
spinlock... Here is pseudo-code sketch of the algorithm:
_________________________________________________________________________
class rwmutex {
enum constant {
READ_ACCESS = 0x10000,
WRITE_ACCESS = 1
};


atomic_word m_next; // = 0
atomic_word m_current; // = 0
eventcount m_waitset;


bool prv_check_read(atomic_word ticket) {
return (ticket == (LOAD(&m_current) % READ_ACCESS);
}


bool prv_check_write(atomic_word ticket) {
return (ticket == LOAD(&m_current));
}

public:
void rdlock() {
atomic_word ticket = FETCH_ADD(&m_next, READ_ACCESS) % READ_ACCESS;
while (! prv_check_read(ticket)) {
eventcount::key_type eckey = m_waitset.get();
if (prv_check_read(ticket)) return;
m_waitset.wait(eckey);
}
}


void rdunlock() {
FETCH_ADD(&m_current, READ_ACCESS);
m_waitset.broadcast_relaxed();
}

public:
void wrlock() {
atomic_word ticket = FETCH_ADD(&m_next, WRITE_ACCESS);
while (! prv_check_write(ticket)) {
eventcount::key_type eckey = m_waitset.get();
if (prv_check_write(ticket)) return;
m_waitset.wait(eckey);
}
}


void wrunlock() {
FETCH_ADD(&m_current, WRITE_ACCESS);
m_waitset.broadcast_relaxed();
}
};
_________________________________________________________________________


I am going to code this up in Relacy to verify it. I will keep you posted...


;^)


Chris M. Thomasson

unread,
Apr 26, 2009, 5:51:48 PM4/26/09
to

"Chris M. Thomasson" <n...@spam.invalid> wrote in message
news:RB4Jl.66320$Ji5....@newsfe21.iad...

> You can use an eventcount to add conditional blocking behavior to the
> spinlock... Here is pseudo-code sketch of the algorithm:
> _________________________________________________________________________
> [...]

> _________________________________________________________________________
>
>
>
>
> I am going to code this up in Relacy to verify it. I will keep you
> posted...
>

Here is the algorithm in Relacy:

http://relacy.pastebin.com/f788663a2

It works. However, Relacy is showing that if I use relaxed signaling on the
eventcount, it will deadlock. Therefore, I used fenced signaling and
everything in okay.

Reply all
Reply to author
Forward
0 new messages