lock-free abstractions for high-end production server software...

[Chris Thomasson]

How many of you are actually using, or thinking of using, lock-free
algorithms in your actual production server software architectures? If you
are using them, or have tested them, I am interested in know what you think?
Once you wade through the patents, can you find anything that works?

[Michael K. O'Neill]

"Chris Thomasson" <cri...@comcast.net> wrote in message
news:JsmdnUDzFL3Khzbb...@comcast.com...

All of the higher-end threading architectures for Winsock already involve
waits for synchronization objects, so there seems to be little benefit in
trying to leverage a lock-free approach on top of that. For example,
WSAEventSelect() models rely on WSAWaitForMultipleEvents, and IOCPs rely on
GetQueuedCompletionStatus.

[Chris Thomasson]

"Michael K. O'Neill" <MikeAT...@nospam.hotmail.com> wrote in message
news:RhRri.32648$C96....@newssvr23.news.prodigy.net...

I was thinking more along the lines of the data-structures that maintain
active state in the server. For instance, a lot of server code I have seen
maintains a list of active per-socket connections. Your going to need
synchronization on the list if its going to be touched by multiple threads.
Some server code needs synchronization on a per-socket structure itself
because they make multiple overlapped operations on the same socket.
Therefore, IMHO, Lock-free algorithms could be used within that context...

Any thoughts?

[Lőrinczy Zsigmond]

> I was thinking more along the lines of the data-structures that maintain
> active state in the server. For instance, a lot of server code I have
> seen maintains a list of active per-socket connections. Your going to
> need synchronization on the list if its going to be touched by multiple
> threads. Some server code needs synchronization on a per-socket
> structure itself because they make multiple overlapped operations on the
> same socket. Therefore, IMHO, Lock-free algorithms could be used within
> that context...
>
> Any thoughts?

Just a question: what the hack a "lock-free algorithm" is?

[Chris Thomasson]

"Lorinczy Zsigmond" <nos...@for.me> wrote in message
news:fa4ajc$1i75$1...@news.t-online.hu...

http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms

[Lőrinczy Zsigmond]

Chris Thomasson wrote:

>> Just a question: what the hack a "lock-free algorithm" is?
>
> http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms

Ah so!
Well, there very special tasks which can be performed without locking
like incrementing a counter, if you are using a special machine
instruction named 'compare and swap' or 'compare and exchange'
eg (IBM System/370):
L R14,fld
again: LR R15,R14
AH R15,=H'1'
CS R14,R15,fld if fld==R14 then fld:=R15 else R14:=fld
BNZ again if fld changed, try again

but it is hardly possible if you want to manipulate complex data
structures like a balanced binary tree

[Chris Thomasson]

"Lorinczy Zsigmond" <nos...@for.me> wrote in message

news:fb9jsi$10q3$1...@news.t-online.hu...

> Chris Thomasson wrote:
>
>>> Just a question: what the hack a "lock-free algorithm" is?
>>
>> http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms
>
> Ah so!
> Well, there very special tasks which can be performed without locking
> like incrementing a counter, if you are using a special machine
> instruction named 'compare and swap' or 'compare and exchange'
> eg (IBM System/370):

[...]

You can also create linked-lists:

http://publibz.boulder.ibm.com/epubs/pdf/dz9zr002.pdf

Appendix A/Multi-Processing Examples/Free-Pool Manipulation

> but it is hardly possible if you want to manipulate complex data
> structures like a balanced binary tree

It is possible to create efficient trees using a marriage between lock-free
and lock-based algorithms. Look here for some info on trees:

http://groups.google.com/group/comp.lang.java.programmer/browse_frm/thread/e7b5fe64cb35d64d

A lock-free reader pattern provides read-access into the tree, and mutexs
cover the writers. You can use a technique called Partial Copy-On-Write
Deferred Reclamation (PDR) to handle the memory management:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/82376b7295e6ce1a

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/e7b5fe64cb35d64d

PDR can be used to describe several different algorithms. Such as:

- Bohem Style (GC)
- Read Copy Update (RCU)
- Safe Memory Reclamation (SMR)
- RCU+SMR
- Atomic Reference Counting (LFRC)
- Virtually Zero-Overhead Object Management (vZOOM)

All of the above can give you good lock-free binary trees. However, some of
the solutions can give reader threads very-high performance low-overhead
access to complex linked data-structures. You can run a query over on
comp.programming.threads if you want to explore this further.