fast-pathed mutex with eventcount for the slow-path...

42 views
Skip to first unread message

Chris Thomasson

unread,
Oct 30, 2006, 6:39:34 PM10/30/06
to
Refer to my eventcount algorithm for more information:

http://groups.google.com/group/comp.programming.threads/browse_thread/thread/31e9cb7082285aa7


Here is how to create a mutex that only needs an atomic store to unlock. If
there are no waiters, then no atomic operations are executed... Alex T.
should approve? His windows mutex used xchg to unlock itself...


class mutex {
typedef int state_t;
enum flags_e { LOCKED = 0x80000000, UNLOCKED = 0 }

state_t m_state; // init to 0
eventcount m_waiters;

// version 1
public:
void ver1_lock() {
while(ATOMIC_BTS(&m_state, LOCKED)) {
m_waiters.wait(m_waiters.get());
}
}

void ver1_unlock() {
ATOMIC_STORE(&m_state, UNLOCKED);
m_waiters.signal(); // no atomic op in the fast-path
}


// version 2
public:
void ver2_lock() {
while(ATOMIC_BTS(&m_state, LOCKED)) {
eventcount::count_t waits = m_waiters.get();
if(ATOMIC_BTS(&m_state, LOCKED)) {
m_waiters.wait(waits);
}
}
}

void ver2_unlock() {
ATOMIC_STORE(&m_state, UNLOCKED);
m_waiters.signal(); // no atomic op in the fast-path
}


// version 3
public:
void ver3_lock() {
while(ATOMIC_BTS(&m_state, LOCKED)) {
eventcount::count_t waits = m_waiters.get();
if(ATOMIC_BTS(&m_state, LOCKED)) {
m_waiters.wait(waits);
}
}
}

void ver3_unlock() {
if (ATOMIC_SWAP(&m_state, UNLOCKED)) {
m_waiters.signal(); // no atomic op in the fast-path
}
}
};


which one do you think is better?


;^)


Joe Seigh

unread,
Oct 30, 2006, 7:50:49 PM10/30/06
to
Chris Thomasson wrote:
> Refer to my eventcount algorithm for more information:
>
> http://groups.google.com/group/comp.programming.threads/browse_thread/thread/31e9cb7082285aa7
>
>
> Here is how to create a mutex that only needs an atomic store to unlock. If
> there are no waiters, then no atomic operations are executed... Alex T.
> should approve? His windows mutex used xchg to unlock itself...
>
>
> class mutex {
> typedef int state_t;
> enum flags_e { LOCKED = 0x80000000, UNLOCKED = 0 }
>
> state_t m_state; // init to 0
> eventcount m_waiters;
>
> // version 1
> public:
> void ver1_lock() {
> while(ATOMIC_BTS(&m_state, LOCKED)) {
> m_waiters.wait(m_waiters.get());

Race condition here. You need to test condition
after get() and befor wait() like below

> }
> }
>
> void ver1_unlock() {
> ATOMIC_STORE(&m_state, UNLOCKED);
> m_waiters.signal(); // no atomic op in the fast-path
> }
>
>
> // version 2
> public:
> void ver2_lock() {
> while(ATOMIC_BTS(&m_state, LOCKED)) {
> eventcount::count_t waits = m_waiters.get();
> if(ATOMIC_BTS(&m_state, LOCKED)) {
> m_waiters.wait(waits);
> }
> }
> }
>
> void ver2_unlock() {
> ATOMIC_STORE(&m_state, UNLOCKED);
> m_waiters.signal(); // no atomic op in the fast-path
> }
>
>
> // version 3
> public:
> void ver3_lock() {
> while(ATOMIC_BTS(&m_state, LOCKED)) {
> eventcount::count_t waits = m_waiters.get();
> if(ATOMIC_BTS(&m_state, LOCKED)) {
> m_waiters.wait(waits);
> }
> }
> }
>
> void ver3_unlock() {
> if (ATOMIC_SWAP(&m_state, UNLOCKED)) {
> m_waiters.signal(); // no atomic op in the fast-path
> }
> }
> };
>
>
>
>
> which one do you think is better?
>

Why does version 3 unlock swap? You don't have a wait bit
defined in the lock. Or does ATOMIC_BTS act like test and
set?


--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

Chris Thomasson

unread,
Oct 30, 2006, 10:51:10 PM10/30/06
to
"Joe Seigh" <jsei...@xemaps.com> wrote in message
news:uL-dne6rg5gIANvY...@comcast.com...

> Chris Thomasson wrote:
>> Refer to my eventcount algorithm for more information:

[...]

>> Here is how to create a mutex that only needs an atomic store to unlock.
>> If there are no waiters, then no atomic operations are executed... Alex
>> T. should approve? His windows mutex used xchg to unlock itself...

[...]

>> which one do you think is better?

[...]

>> // version 1
>> public:
>> void ver1_lock() {
>> while(ATOMIC_BTS(&m_state, LOCKED)) {
>> m_waiters.wait(m_waiters.get());
>
> Race condition here. You need to test condition
> after get() and befor wait() like below

[...]

Yup; a waiter can get missed by an unlock! Not sure why I waited like that,
anyway I am always up for a good game of spot the bug!

;^)


> Why does version 3 unlock swap?

Humm, I don't know... The atomic operation is doing nothing, it won't cause
problems but its wasteful... Anyway, I cut-and-pasted the wrong section of
another algorithm! The unlock function for version 3 is was supposed to
define the following flags:


enum flags_e { LOCKED = 0x80000000, WAITERS = 0x80000001, UNLOCKED = 0 }


and the lock function:


void ver3_lock() {
while(ATOMIC_BTS(&m_state, LOCKED)) {
eventcount::count_t waits = m_waiters.get();

if(ATOMIC_SWAP(&m_state, WAITERS) & LOCKED){
m_waiters.wait(waits);
}
}
}


and the unlock function:


void ver3_unlock() {
state_t local = m_state;
ATOMIC_STORE(m_state, UNLOCKED);
state_t cmp = ATOMIC_LOAD(&m_state);
if (local & WAITERS || cmp & WAITERS) {
m_waiters.signal();
}
}


I don't think there are any race-conditions here... Humm...

;^)


Reply all
Reply to author
Forward
0 new messages