PoC: passive serialization

Andrey Zonov zont at FreeBSD.org
Tue Jun 17 07:18:37 UTC 2014


Hi,

I'd like to introduce my implementation of passive serialization [1]
(RCU-like algorithm) which based on expired patent #4809168 [2].

This algorithm allows one to access data structures in non-blocking
lock-less manner, but it is not just read-write lock alternative it is
something different.  It is like delayed garbage collector or if you
know what RCU is, passive serialization basically the same (RCU based on
that).  Unlike NetBSD's implementation [3] my version is light-weight,
with no additional locks.  One atomic operation per context switch is
the only overhead.  To demonstrate how it works I converted process
limits to use that mechanism [4].  There is also simple test [5] if you
interested in measurements.  Just configure which type of lock do you
want to use (mutex/rwlock/rmlock/psz), duration (LOOPS) and load
(LENGTH) and run `make -s run' to get numbers.

Any questions, comments or suggestions are welcome.


[1]
http://people.freebsd.org/~zont/patches/psz/0001-Implement-passive-serialization.patch
[2] http://www.google.com/patents/US4809168
[3]
http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/kern/subr_pserialize.c?rev=1.7&content-type=text/x-cvsweb-markup
[4] http://people.freebsd.org/~zont/patches/psz/0002-Lock-less-limits.patch
[5] http://people.freebsd.org/~zont/patches/psz/lock_test/

-- 
Andrey Zonov

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 535 bytes
Desc: OpenPGP digital signature
URL: <http://lists.freebsd.org/pipermail/freebsd-arch/attachments/20140617/3632cd0a/attachment.sig>


More information about the freebsd-arch mailing list