So this is the abstraction layer seen by the application that is giving this
illusion of a global virtual memory. This layer is the DSM software
implementation layer that implements this global
virtual memory abstraction. In particular, this DSM
software layer, which exists on every one
of these processors, knows that the point
of access to a page by a processor, who
exactly to contact, as the owner of the page,
to get the current copy of the page. For
instance, let's say that there was a page fault on
this processor one. For a particular portion of the
global address space. That portion of the global address space
is currently not resident here in the physical memory
of processor one. So, there is a page fault over
here and there is cooperation, as I mentioned earlier,
between the operating system and the DSM. So, when
the page fault happens, that page fault is going
to be communicated by the operating system to the DSM
software saying that here is the page fault, you
handle it. What the DSM software is going to do
is, it knows the owner of the page, and
so it's going to contact the owner of the page.
And ask the owner of the page to get the current
copy of the page. So the current copy of the page
resides over here. So the owner, either it itself has the
current copy of the page or it knows which node currently has
the current copy of the page, and so it's going to
send the page over to the node that is requesting it. The
current copy of the page is over here. It's going to
come over to this guy, and recall what I said about ownership
of the pages. The residency of this page doesn't
necessarily mean that this is the owner of the page.
The owner of this page could have been this
node, so the DSM software would have contacted the owner.
And the owner would have said, oh you know
what. That particular place to cut and copy is on
this node. So the DSM software would go to
this note, and fetch this page, and put it into
this processor. So that this processor is happy.
So once the page has been brought in to
the physical memory, then the DSN software contacts the
virtual memory manager and says, I've completed now, processing
the page fault, brought the page that is missing
and put it into a particular location in the
physical memory. Would you please update the page table
for this guy, so that he can resume execution?
Well, then the VM manager gets into action.
And updates to page table for this thread
to indicate that the faulty virtual page is
now mapped to a physical page, and then
the process or the thread can resume its
execution. So this is a way coherence is
going to be maintained by the DSM software. The
cooperation between DSM software and the VM manager.
And the coherence maintenance is happening at the level of individual pages. An
early examples of systems that built software DSM include
Ivy from Yale, Clouds from Georgia Tech
Mirage from UPenn, and Munin from Rice. All of
these are distributed shared memory systems and they all used coherence
maintenance at the granularity of an individual page, and they
used a protocol which is often referred to as a single writer protocol. That
is, I mentioned that the directory associated with the portion
of the virtual memory space managed by each one of these nodes
and the directory has information as to who all are sharing a page at any point
of time. Multiple readers can share a page
at any point of time, but a single writer
is only allowed to have the page at any
point of time. So, if there is the writer
for a particular page, let's say that loose page,
which is now currently in the memory of two
different processors, if this guy wants to write to
this page, then he has to inform through the
DSM software abstraction, inform the owner for this page.
Let's say this guy is the owner for this
page, that I want to write to this page
and at that point the owner is going to invalidate
all copies of that page that exist in the
entire system, so that this guy has exclusive access
to that page so that they can make modifications
to it. So this is what is called single writer
multiple reader protocol. Easy to implement. At the point of
right to a page, what you do is, you go
through the DSM software, contact the owner. And the owner
says, I know who all have copies of the page, I'll
invalidate all of them. Once it has invalidated all the
copies, then the guy who wants to write to that
page can go ahead and write to it, because that'll
be the only copy. Now the problem with the single writer
protocol is that there is potential for
what is called fault sharing. We've talked
about this already in the context of
shared memory multiprocessors. Basically the idea of fault
sharing, or the concept of fault sharing, is that data appears to be shared even
though programmatically, they are not. Let's consider
this page-based coherence maintenance. In the page-based coherence
maintenance, the coherence maintenance that is done by
the software, DSM software, is of the granularity
of a single page. A page may be
4K bytes or 8K bytes,depending on the architecture
we're talking about. And within a page, lots
of different data structures can actually fit. So,
if the coherence maintenance is being done at
the level of an individual page, then we're
invalidating copies of the page in several nodes
in order to allow one guy to make
modifications to some portion of that page. And
that can be very severe in a page based
system due to the coarse granularity of the
coherence information. So for example, this one page may
contain ten different data structures, each of which
is governed by a distinct lock. So far as
the application programmer is concerned. But, even if I get
a lock, which is for a particular data structure that
happens to be in this page. And this guy has
a lock for a different data structure which is also on
the same page. When I get the lock that is
going to manipulate a particular data structure in this page,
and if I want to make modifications for it, I am
going go and invalidate all the other copies. When he wants
to make a change, he's going to come and invalidate my copy of the page. So
the page can be ping-ponging between, between multiple
processes. Even though they are modifying different portions
of the same page, still the coherence granularity
being a page, will result in this page
shuttling back and forth between these two guys,
even though the application program is perfectly well behaved
in terms of using locks to govern
access to different data structures. Unfortunately, all of
those data structures happened to fit within
the same page. Resulting in this fault sharing.
So, page level granularity and single writer
multiple reader protocol don't live happily together. They
will lead to fault sharing. And they will lead to ping ponging of the pages,
due to the fault sharing among the
threads of the application across the entire network.