Date: Sat, 1 Feb 1997 15:39:07 -0700 (MST) From: Terry Lambert <terry@lambert.org> To: leo@prosun.first.gmd.de (Matthias L. Jugel) Cc: netdev@roxanne.nuclecu.unam.mx, smp@freebsd.org Subject: Re: lockfree datastructures Message-ID: <199702012239.PAA06784@phaeton.artisoft.com> In-Reply-To: <9702011117.AA01923@prosun.first.gmd.de> from "Matthias L. Jugel" at Feb 1, 97 12:17:40 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> Hi folks, > > a friend of mine forwarded me your interest in lock free data structures. [ ... ] > Ok, I hope the papers give you a clue about the problem. From experience > and discussion with our own OS builders I get the impression that for > most problems a CAS or CAS2 (Compare-And-Swap) is sufficient compared to > the proposed methods explained in the papers above. > > I'd be very interested in any problems and solutions you have in mind, > because I am working on the subject in my PhD studies. If someone could > give me a more detailled description of the problems you want to solve > using non-blocking techniques. Realize that I'm probably only speaking for the people who I have discussed these issues with, and who happened to agree with me. 8-). We are primarily interested in maximizing work concurrency in a symmetric multiprocessing environment. One big issue that is not addressed by lock free data structures is the continuing need for interprocessor synchronization of these structures in the SMP environment. Effectively, any CAS or CAS2 system implementing interprocessor resource locking must block during IPI-based cache data invalidation to propagate the act of synchronization. We haven't discussed this thoroughly yet, but it seems that implementing a lock tree hierarchy using intention modes would allow us to compute transitive closure over the graph swiftly, and only need to implement IPI-based cache data invalidation when accessing system wide resources. Combining this technique with Dynix-style per-CPU resource pools which are filled/drained to global resource pools seems to yield the minimum amount of inter-CPU synchorinization issues. A difficultly in doing per CPU pools with a SLAB or modified zone allocator, is that of process migration. If a process allocates a resource on one processor, and subsequently migrates to another, then frees the resource, we have the cache invalidation issue all over again before the original CPU realizes the resource has been freed for reuse. Further, we must be careful to avoid issues of cache line overlap, so that a modification of one object on one processor does not write non-current data into the adjacent object because the object adjacency boundry is interior to a single cache line that will be written back as a unit. This is made even more difficult because we want the resulting design to be able to be "tuned" for varying processor architectures -- not just Intel -- and we don't have direct knowledge of the cache interactions for object adjacency on all of the potential architectures we will want to run on. Tenatively, we have discussed per pool notification queues that can be written by the other processor to queue a "free" event at the time the object is freed. The processing of these events is then delayed until the number of free items in the pool hits the low watermark that would cause it to go back to the global pool to obtain more. At that time, we must undertake an IPI synchronization in any event, but then we could process the "free" event queues for us from each other processor for each resource. If we get enough resources back to satisfy the refill quota for the low watermark event, then we can return without obtaining objects from the global pool. Otherwise, we may have to obtain from the global pool anyway. One bad consequence of this type of approach is that pools will tend to "run hot"... that is, they will tend to have a higher apparent usage than they actually have, and depending on the watermarking seperation, the refill/drain amounts, and the average object persistence once allocated, we may in fact have up to 50% of the number of items between the post-refill amount and the midway point for the high/low watermark free but considered to be in use. Any suggestions would, of course, be appreciated... Regards, Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199702012239.PAA06784>