It is certainly quite possible to implement a doubly linked list via interlocked operations, but it is not possible to ensure that this algorithm will run on all hardware supported by Windows.
Sent from Surface Pro
From: Tim Roberts
Sent: Friday, September 19, 2014 1:42 PM
To: Windows System Software Devs Interest List
xxxxx@gmail.com wrote:
Hello guys! I’m very grateful for the help everyone on this forum!
Now I try create lock-free double linked list based on ExInterlockedXXXX functions.
I find this sentence to be bizarre. The DDK already has
ExInterlockedInsertHeadList, ExInterlockedRemoveHeadList, etc. However,
those are not lock-free. You have to hand a spin lock to every API.
And that is for a very good reason. You cannot implement a truly
lock-free doubly-linked list. It’s impossible. You have two pointers
to update, so no matter how clever you are, during every update there
will always be a small window during which the pointers are inconsistent.
–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.
NTDEV is sponsored by OSR
Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
OSR is HIRING!! See http://www.osr.com/careers
For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars
To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer