Date: Tue, 1 Apr 1997 16:29:08 -0700 (MST) From: Terry Lambert <terry@lambert.org> To: jkh@time.cdrom.com (Jordan K. Hubbard) Cc: terry@lambert.org, proff@suburbia.net, joe@pavilion.net, gbeach@cybernet.com, hackers@freebsd.org Subject: Re: Internal clock Message-ID: <199704012329.QAA12377@phaeton.artisoft.com> In-Reply-To: <27601.859935739@time.cdrom.com> from "Jordan K. Hubbard" at Apr 1, 97 03:02:19 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> > Are you worried about all of these issues simultaneously? Are you
> > worried about allowing concurrent readers? Implement multiple
> > reader/single writer locking.
>
> You forgot about:
>
> Implement virtual time generator so that Jordan & co can actually get
> around to building the "frozen current" mechanism from hell, with
> duplicate CVS tree and all, along with the new build/relesae system,
> the setup tool, the fancy administration/help system, the new combined
> package/distribution scheme and and and...
>
> So can I have those virtual time generator plans by next week please?
> I'm sort of in a hurry. :-)
You only need 'the "frozen current" mechanism from hell' if you refuse
to consider multiple reader/single writer locking at all. Even then,
you will need to implement on top of a similar framewrok (dropping
the "writer-but-not-actively-committing" lock states from your graph).
Snapshots of the tree are not necessary if you do not let in readers
between the time the commit starts and the commit ends. A buildable
tree is present any time a writer lock is not present, by definition,
if you require that only buildable trees be checked in, and that a
writer lock be held over the checkin itself.
You only need to hold a writer lock across the whole transaction if
you are trying to protect the tree from simultaneous writers. If
all you are trying to do is protect readers from writers, you only
need to hold the lock across the actuall commit itself.
Single writer locking to protect writers from each other is held over
the whole transaction. But you don't need to prevent readers between
the time the transaction starts and the time the actual commit takes
place, since the tree is unstable only *during* the actual commit.
So it's:
committers:
LOCK: SOLE WRITER
...
PROMOTE LOCK: SOLE COMMITTER
UNLOCK: SOLE COMMITTER
readers:
LOCK: Nth READER
UNLOCK: Nth READER
Y wants
----------------------------------------
read write commit
-------- -------- --------
X has | none | grant grant grant
| read | grant grant block(1)(3)
| write | grant block(4) block(1)
| commit | block(2) block block(1)
-------- -------- --------
(1) You would probably want to block additional "read" requests
when there is a blocked commit pending to allow existing
"read" requests to "drain" to allow the commit to go through.
(2) A blocked read request may be treated as a "deny, try again
later".
(3) Depending on prioritization, an in-progress "read" might be
preempted by a pending "commit". This should result in a
"try again later", per note (2), but would require the
cooperation of the user's CVSup and/or CTM mirroring.
(4) Assumes inter-commiter contention is arbitrated by locking
so that one modified tree is not committed on top of another,
resulting in a conjoined ther that is unbuildable.
If you want to implement 'the "frozen current" mechanism from hell',
you can do so by applying the locking system to both trees, with the
following algorithm:
The "frozen" tree only gets "commit" locked (there is no "write"
lock needed, since a "frozen" tree is only refreshed by one "writer",
ever: the mirroring process).
The "commit" tree only gets a "read" lock (or a "commit" lock if
note (3) is implemented, so that a committer can have a write lock
pending upgrade to "commit", and the "frozen" tree is not left in an
indeterminate state) while the mirroring process is running.
Readers and committers operate on their respective trees as if they
were still operating on a single tree; the only difference is that
the contention window is shortened to only occur during "mirroring".
A frozen tree is probably not necessary if CVSup's from the commit
tree are only done by CVSup sites doing mirroring rather than by
individual users (a relatively low load means a relatively small
contention window exists).
---
I can write a simple program to do multiple reader/single writer
locking like this using standard UNIX lock files and reader/writer
counting, if you can't figure it out yourself... it's hardly a
problem "from hell", however.
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?199704012329.QAA12377>