About queued spinlocks
Queued spinlocks are designed as replacement for standard spinlock as main synchronization mechanism in kernel mode of an OS. They provide better performance on multiprocessor systems by reducing contention of interconnection bus during busy waiting, providing fairness and locality of reference. Standard spinlocks suffers from contention of interconnection between processors caused by usage of a single memory location shared by all processors for spinning. This significant increase traffic between processors is caused by cache coherency protocol. On the other hand, when queued spinlocks are used, each processor uses it's own memory location to spin which avoids memory sharing and ease traffic between processor, in addition to that, memory used for spinning is located on the stack currently used by the processor which further improves performance. Queued spinlocks also guarantee that processors will enter guarded critical section in the same order in which they arrive, which is not the case with standard spinlocks.
Implementation
struct qsl_entry
{
qsl_entry* next;
int state;
};
struct qsl
{
qsl_entry* head;
};
void lock_qsl(qsl* lck, qsl_entry* ent)
{
__asm
{
mov eax, ent
mov ebx, lck
mov [eax], 0
mov edx, eax
mov [eax]qsl_entry.state, 1;
lock xchg [ebx],eax
test eax, eax
jz enter_section;
mov [eax],edx
wait1:
pause
cmp [edx]qsl_entry.state, 1;
je wait1
enter_section:
}
}
void unlock_qsl(qsl* lck, qsl_entry* ent)
{
__asm
{
mov eax, ent
mov ebx, lck
xor ecx, ecx
mov edx, eax
lock cmpxchg [ebx], ecx
je exit_section;
wait2:
pause
cmp [edx], ecx
je wait2
mov eax, [edx]
mov [eax]qsl_entry.state, ecx;
exit_section:
}
}
Using the Code
qsl lock;
int thread_1(void* p)
{
qsl_entry entry;
while( 1 )
{
lock_qsl( &lock, &entry );
printf( "thread " );
printf( "%d", (int)p );
printf( "\n" );
unlock_qsl( &lock, &entry );
}
return 0;
}
int main()
{
CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE)thread_1,
(void*)1, 0, NULL );
CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE)thread_1,
(void*)2, 0, NULL );
getchar();
return 0;
}