OSDev.org

The Place to Start for Operating System Developers
http://f.osdev.org/

Any Semaphore Implementation information pls?

http://f.osdev.org/viewtopic.php?t=17826

Page 1 of 1

Any Semaphore Implementation information pls?

Posted: Wed Aug 20, 2008 1:27 am
by oohayulin
Any Semaphore Implementation information pls?

Or any lock mechanism?

Re: Any Semaphore Implementation information pls?

Posted: Wed Aug 20, 2008 1:43 am
by einsteinjunior
What type of semaphore do you want to implement?Signal/Wait ?

Re: Any Semaphore Implementation information pls?

Posted: Wed Aug 20, 2008 2:39 am
by JamesM
oohayulin wrote:Any Semaphore Implementation information pls?

Or any lock mechanism?
Write one, genius.

Re: Any Semaphore Implementation information pls?

Posted: Wed Aug 20, 2008 10:04 am
by Brendan
Hi,
oohayulin wrote:Or any lock mechanism?
I'm a little bored, so here's some simple unoptimized spinlock code:

Code: Select all

;Acquire the lock
;
;Input
; esi    address of the lock

acquireSpinlock:
.tryLock:
    lock bts [esi],0
    jc .tryLock
    ret

;Release the lock
;
;Input
; esi    address of the lock

releaseLock:
    mov dword [esi],0
    ret
This code is *bad* - it repeatedly locks the bus, so when there's several CPUs spinning any remaining CPUs have to struggle to get any bus bandwidth (which slows them down and means it takes longer for who-ever has the lock to release the lock). Here's some much better spinlock code:

Code: Select all

;Acquire the lock
;
;Input
; esi    address of the lock

acquireSpinlock:
.testLock1:
    bt [esi],0
    jnc .tryLock
.testLock2:
    pause
    bt [esi],0
    jc .testLock2
.tryLock:
    lock bts [esi],0
    jc .tryLock
    ret

;Release the lock
;
;Input
; esi    address of the lock

releaseSpinlock:
    mov dword [esi],0
    ret
This is much better, but it's still not good enough because it doesn't provide any help for debugging complex/messy problems (like deadlocks). Here's some even better spinlock code:

Code: Select all

;Initialize the lock
;
;Input
; esi    address of the lock

initSpinlock:
%ifdef DEBUGGING
    cmp dword [esi+4],0xFEEDFACE
    je CRITICAL_ERROR_attempt_to_initialize_lock_that_was_already_initialized
    mov dword [esi+4],0xFEEDFACE
%endif
    mov dword [esi],0
    ret


;Acquire the lock
;
;Input
; esi    address of the lock

acquireSpinlock:
%ifdef DEBUGGING
    push ebx
    push eax
    mov ebx,[current_thread_ID]
    xor eax,eax
    or ebx,0x80000000
    cmp dword [esi+4],0xFEEDFACE
    je CRITICAL_ERROR_attempt_to_acquire_something_that_isn't_a_valid_lock
.testLock1:
    cmp [esi],eax
    je .tryLock
.testLock2:
    pause
    cmp [esi],eax
    jne .testLock2
.tryLock:
    lock cmpxchg [esi],ebx
    je .gotLock
    cmp eax,ebx
    jne CRITICAL_ERROR_attempt_to_acquire_lock_that_thread_already_has
    xor eax,eax
    jmp .testLock2
.gotLock:
    pop eax
    pop ebx
%else
.testLock1:
    bt [esi],0
    jnc .tryLock
.testLock2:
    pause
    bt [esi],0
    jc .testLock2
.tryLock:
    lock bts [esi],0
    jc .tryLock
%endif
    ret

;Release the lock
;
;Input
; esi    address of the lock

releaseSpinlock:
%ifdef DEBUGGING
    cmp dword [esi+4],0xFEEDFACE
    jne CRITICAL_ERROR_attempt_to_release_something_that_isn't_a_valid_lock
    cmp dword [esi],0
    jne CRITICAL_ERROR_tried_to_free_lock_when_lock_not_acquired
    push ebx
    mov ebx,[current_thread_ID]
    or ebx,0x80000000
    cmp [esi],ebx
    pop ebx
    jne CRITICAL_ERROR_wrong_task_tried_to_free_lock
%endif
    mov dword [esi],0
    ret
This is a good start, as it'll find most common mistakes people make with spinlocks. There are other problems that could be checked for (e.g. trying to do a task switch before releasing locks), and some of the tests might annoy you in strange situations (e.g. when a thread is meant to release a lock that was acquired by a different thread), but it should give you a good idea of what things could be detected.

However, this still isn't that good - the call/ret overhead is silly considering that the routines are so short (especially when you're not debugging). Here's one way to avoid that:

Code: Select all

;Macro to create a pre-initialized spinlock (e.g. in the ".data" section)

%macro SPINLOCK 1
%if ($ & 0x7F) <> 0
%warning Lock not aligned on a 128-byte boundary
%endif
    dd 0
    dd 0xFEEDFACE
%endmacro


;Macro to initialize a lock (e.g. for dynamically allocated locks)

%macro INIT_SPINLOCK 1
%ifdef DEBUGGING
    cmp dword [%1+4],0xFEEDFACE
    je CRITICAL_ERROR_attempt_to_initialize_lock_that_was_already_initialized
    mov dword [%1+4],0xFEEDFACE
%endif
    mov dword [%1],0
%endmacro


;Macro to acquire a lock

%macro ACQUIRE_SPINLOCK 1
%ifdef DEBUGGING
    push ebx
    push eax
    mov ebx,[current_thread_ID]
    xor eax,eax
    or ebx,0x80000000
    cmp dword [%1+4],0xFEEDFACE
    je CRITICAL_ERROR_attempt_to_acquire_something_that_isn't_a_valid_lock
%%testLock1:
    cmp [%1],eax
    je %%tryLock
%%testLock2:
    pause
    cmp [%1],eax
    jne %%testLock2
%%tryLock:
    lock cmpxchg [%1],ebx
    je %%gotLock
    cmp eax,ebx
    jne CRITICAL_ERROR_attempt_to_acquire_lock_that_thread_has_already_acquired
    xor eax,eax
    jmp %%testLock2
%%gotLock:
    pop eax
    pop ebx
%else
%%testLock1:
    bt [%1],0
    jnc %%tryLock
%%testLock2:
    pause
    bt [%1],0
    jc %%testLock2
%%tryLock:
    lock bts [%1],0
    jc %%tryLock
%endif
%endmacro


;Macro to release a lock

%macro RELEASE_SPINLOCK 1
%ifdef DEBUGGING
    cmp dword [%1+4],0xFEEDFACE
    jne CRITICAL_ERROR_attempt_to_release_something_that_isn't_a_valid_lock
    cmp dword [%1],0
    jne CRITICAL_ERROR_tried_to_free_lock_when_lock_not_acquired
    push ebx
    mov ebx,[current_thread_ID]
    or ebx,0x80000000
    cmp [%1],ebx
    pop ebx
    jne CRITICAL_ERROR_wrong_task_tried_to_free_lock
%endif
    mov dword [%1],0
%endmacro
Note: None of the code above has been tested in any way...

Spinlocks are relatively simple. Decent quality semaphore code is left as an exercise for the reader. :)


Cheers,

Brendan

Re: Any Semaphore Implementation information pls?

Posted: Wed Aug 20, 2008 1:35 pm
by kataklinger
Another implementation of spinlocks.

Re: Any Semaphore Implementation information pls?

Posted: Mon Sep 01, 2008 7:30 am
by oohayulin
Brendan, you provide is what I want.

:)

Thank you all guys.

I am not genius. haha.

But no hero, be hero.

Re: Any Semaphore Implementation information pls?

Posted: Mon Sep 01, 2008 12:05 pm
by salil_bhagurkar
Can anybody tell me about a practical implementation of semaphores where there could be more than one users (the value is initialized to -2 giving 2 users and sleeping any more users than 2)... Till now i have only seen sems with initialized value -1 meaning single user...

Re: Any Semaphore Implementation information pls?

Posted: Mon Sep 01, 2008 12:20 pm
by Combuster
on a 486:

Code: Select all

sem_down:
    mov eax, 1
    lock xadd [semaphore], eax ; magix happens here
.wait:
    mov edx, [semaphore+4]
    add edx, user_count
    cmp eax, edx
    jns .wait
    ret

sem_up:
    lock inc [semaphore+4]
    ret

semaphore: dd 0, 0
Go figure how it works :wink:

Re: Any Semaphore Implementation information pls?

Posted: Mon Sep 01, 2008 12:23 pm
by salil_bhagurkar
Okay sorry for my wrong terminology.. By practical implementation, i meant practical application in operating systems.. For example in linux... Some usual application where it is used... Not the code for it...

Re: Any Semaphore Implementation information pls?

Posted: Mon Sep 01, 2008 12:30 pm
by Combuster
a practical application: reader-writer configurations

You have a shared buffer, application A writes to it, Application B reads from it. when A has done writing a block to the buffer, it increases the semaphore. Application B will try to decrease the semaphore. When it can, A must have completed writing a block to the buffer so that B can read it. When it can't decrease it, it will wait for the semaphore (and by that, wait for the next block of data)

Textbook example, I might add.

Re: Any Semaphore Implementation information pls?

Posted: Mon Sep 01, 2008 12:50 pm
by kataklinger
For instance you can have buffer of X work items and best performance are gained if you let only Y threads to execute work in the buffer concurrently. Now you can use semaphore to signal only Y worker threads that are waiting by setting semaphore count to Y when the buffer is full (assuming that the threads know how to split work i.e. they can use their IDs to calculate indices of the items in the buffer...)
All times are UTC-06:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited