At 11:26 3/28/95, Paul Close wrote:
>> What I propose instead is the following, which is an extension to the
>> existing locking mechanism (that is, I think it can be incorporated into
>> the shlock code without any interface changes). Basicly, when a process
>> creates its temporary lock file, name the file "Q.<time>.<pid>.<filename>"
>> (this is why I say it won't work on systems limited to 14-character
>> filenames) instead of simply "L.<pid>" the way it is in the old scheme.
>> Then, just as now, try to hard link "L.<filename>" to this temporary file.
>> If the link succeeds (which it normally will, on a lightly-loaded system),
>> you now own the lock, without really having done any more work than before
>> (you had to construct a slightly more complex filename, but that's all).
>
>If a number of requests come in in the same second, a simple ordering no
>longer holds. As long as the code is aware that this might happen, it
>should be okay. For example, pid 123 and 456 might try at the same time,
>and 456 wins. This means that Q.time.123.file is waiting on
>Q.time.456.file, which won't be obvious to subsequent queue joiners. They
>won't know whether they're waiting on 123 or 456.
Why not? I don't think it has to enforce an absolutely strict ordering,
just a more-or-less correct ordering; that would be more fair than what
happens now (where it's essentially random). As long as all processes
agree on the ordering (that it's by time, and then by pid if time is the
same), there shouldn't be any problem.
>> John Rouillard proposed a different queued locking mechanism a few days
>> ago. I haven't analyzed the proposal in great depth, but two things struck
>> me as problematic about it. First, it appears to require maintaining the
>> queue as a file, and locking the queue file (using the existing shlock
>> mechanism) when you want to update it; this seems to me to simply move the
>> simultaneous-access problem from the main file to the queue file. Second,
>> it appears to require renaming a bunch of files every time the queue
>> changes, to reflect processes moving up in the queue; this seems like it
>> could cause a lot of unnecessary filesystem activity.
>
>John's scheme uses a quick spin lock to maintain a file which has a very
>small critical region. Therefore, sleeping is not necessary: if you can't
>get the lock, you retry immediately. I think your scheme needs this too.
>
>I'm a little confused by John's step (2) where he examines each lock in turn
>to see if it fails or not. It seems like Brent's scheme of signalling the
>next in line works better. It also seems unnecessary to do all the
>filesystem work John's scheme implies. A simple rotary queue should suffice
>(i.e. there's a head and a tail to the queue; you get the lock when you're
>the head, not when your number is 000).
Yeah, that's one of the things I really disliked about that scheme; all the
shuffling of filenames as processes moved up in the queue. I think that,
under normal conditions (that is, where nothing ahead of the process in the
queue dies), we want a process to be able to simply sleep until its turn
comes up; it shouldn't have to do anything to maintain its place in the
queue. If every process waiting has to wake up every time _any_ process
clears a lock, you're going to get a lot of thrashing as processes swap in
and out just to update their place in the queue.
>Maybe the best ideas from both can be implemented.
Yes, I hope so. Like I said, though, I really don't have time to do the
work; the idea just came to me in the shower one morning (literally!), and
I wanted to write it down for other folks to look at (and maybe implement)
while it was still all in my head.
-Brent
----------------------------------------------------------------------
For info about the Internet Security Firewalls Tutorial and a schedule
of upcoming dates, please send email to Tutorial-Info@GreatCircle.COM
----------------------------------------------------------------------
Brent Chapman Great Circle Associates
Brent@GreatCircle.COM 1057 West Dana Street
+1 415 962 0841 Mountain View, CA 94041
|
|
