That brings us to a new coherence protocol,
which is multiple writer protocol. So, the idea
is we want to maintain coherence information still
at the granularity of pages. Because that is
the granularity at which the operating system operates,
and therefore, the DSM can be integrated with
the operating system if the granularity of the
coherence maintenance is at the level of a page.
But, at the same time, we want to allow
multiple writers to be able to write to the
same page, recognizing that an application programmer may have
packed lots of different data structures within the same
page. So we are going to see how the
multiple writer coherence protocol works, and in particular we're
going to use that in concert with these lazy
release consistency. The background for what I'm going to describe
is covered in the paper that is assigned for
you, which is the Treadmarks paper. I encourage you
to read that paper to get all the details.
But here, I'm going to give you a high
level view of how LRC is integrated with multiple writer protocol in the
Treadmarks system. So the processor P1 acquires a lock and makes
modifications. This notation that I'm using is to indicate that these pages,
X, Y, and Z, actually they are data structures
that are being modified, but we are maintaining coherence
of the level of pages so we'll say that
the data structures that we're modifying within this critical section
are contained in pages X, Y and Z, and
so those are the pages that are being modified within
this critical section when processor P1 executes this piece
of code. Now the operating system has no knowledge of
the association between the lock, L, and the
pages that have been modified. All that it
knows, is that within the critical section these
are the pages that were modified. That's what the
operating system knows. And what we're going to
do is, we're going to create a diff
of the changes that were made to the pages x, y and z in this critical section.
So we know at the beginning of this critical
section what the contents of the page x, y and
z is. And at the end of this critical
section we're going to find out what is the difference
that has been made, or what are the changes
that have made and compute the diffs between the original
page, and the modified page. Xd, Yd and Zd
are the diffs to pages X, Y, and Z respectively
as a result of executing this critical
section. So, the coherence protocol we are going
to use is LRC, or lazy release consistency. So the next time the same lock L
is requested by some other process of
P2 we're going to first invalidate the pages
we know were modified by the previous lock
holder, because this is information that is available
to the DSN that at the point of unlock it knows that these were the pages that
were modified by this critical section. It doesn't know what part of the pages
are modified. That's contained in the diffs. But it knows that pages X, Y, and
Z are associated with this lock L, and
therefore, when P2 makes the lock request L,
the DSN is going to first invalidate. If copies of pages x, y, and z are locally
resident in the processor P2, then the DSM software is going to invalidate
those pages x, y, and z at the point of lock acquisition. That's consistent with
the lazy release consistency model. So, once
we've invalidated these pages, then you can allow
this guy to get the lock and start
getting into its critical section. Now once it is
in the critical section, it can do whatever it
wants. But if it tries to access page X,
at that point we know that page is invalid
because we've done that at the beginning of this
critical section, invalidated page X. And at this point,
the DSM software also knows that the previous lock
holder has the modifications that need to be
made to the original page to get the current
version of the page. The current version of
the page is with some owner for this page.
I mentioned this ownership based protocol in the
DSM software. So the DSM software knows who the
owner of the page is. From the owner of the page I can get the original content
of X. I'll do that, but I'll also go and get the diff that is created by the
execution of the previous critical section by the previous lock holder. So the
DSM software brings at the point of access to X, Xd and the original version
of the page from the owner of the page, it can then create the current version
of the page for use by P2.