Now given a UID I know that some PFD in the entire cluster has the mapping for
the UID saying what is the physical frame number that corresponds to it if it
happens to be on that node or it's on the disk. That information is contained
in some PFD in the entire cluster. So, if I have a page fault. I convert my VA
to UID then which PFD will I go look
up? I could broadcast to everybody and say, how
do you have it? That will be very efficient.
You don't want to do that, or we can say
that there is some way of magically mapping, given
a UID which node will have the PFD for
me to look up. And find out the backing
physical page. But we don't want to do a static
binding of UID to the node that manages that UID. Because if we make a static
mapping, then it pushes the burden on one
node to take that, if some page has become
really hot and everybody wants to use that.
So what we want to do is distribute this management
function also, just like the age management, we
did not want to concentrate it on a single node.
We want to distribute the management of giving this mapping between UID and
which node has the PFD that. Can tell me information about the missing page. And
that data structure is this Global Cache Directory, GCD. So GCD is a hash table,
it's a cluster-wide hash table, so it's a distributed data structure. And the
rule that GCD performs is given a UID, it
will tell you which node has the PFD that
corresponds to this UID. That's the role of this
data structure, it's a partition hash table, so given
a UID, I can say well. I go to the GCD, and the GCD will say, what is
the PFD that has this UID? Because of the
partition hash table, even though a part of this GCD
is on every node, every node may not be locally able to determine where the PFD
is. Given a UID, it can go, it has to know which GCD it has to
consult. In order to know which node has
the PFD that corresponds to this UID. So,
we need another data structure that tells us,
given a UID, which node has the GCD
that corresponds to this UID. And that is the page ownership directory. So, the
page ownership directory says, given a UID.
Which node has the DCD that corresponds to
this UID. And this data structure the
page ownership directory is replicated on all the
nodes. It's an identical replica that is on all the nodes. So, when I have
a page for it first thing that I'm going to do, is go to my POD and that is.
A replicated data structure and it's completed information, up
to date information. So I go to this POD
and as this question. Given this new id, how
do I find out the global cache directory that
has information about the PFD that can help me
to. Map my virtual address to a physical address.
Remember that we could have simply gone from
here to here, but that would have been a
static mapping, and this one level of indirection
is giving a way by which we don't have
to statically map. A PFD to a UID,
but this intermediate step, allows us to move the
responsibility of hosting a particular PFD to different nodes,
using this intermediary which is a distributive hash table.
I said that this page ownership directory.
Is replicated data structure. Can it change? Well
it can change over time because what this
page ownership directory is saying is the following.
The UID space is something that spans the
entire cluster. If you take the virtual addresses
of all the possibilities of the entire cluster.
That universe of all the virtual addresses is
this UID space because it is being mapped from a a virtual address of a single
process to this UID space and this spans the whole cluster and what we have done
is we have partitioned that UID space. Into set of
regions of ownership and that's what is called the page ownership.
So every known is responsible for a portion of the UID
space and that is this global cache directory. Now
if the LAN never revolves. In other words, if
the set of nodes on the LAN is fixed.
Then the page ownership director also remains the same. But
if nodes, if new nodes are added and deleted
and so on, that's when the page ownership directory
is going to change. And if that happens, then we
have to replicate again, we have to redistribute the page
ownership directly. But this is not something that's going to happen
too often. It's very rare that node is going to come down
or new node is going to be inserted into a
LAN. And therefore this page ownership directory does not change very
often. And that's where it's replicated data structure that you
can believe at every node. But if it changes, there is
also a way of handling that. We'll see that in a
minute. So the path for page fall handling is if you
have a page fall you convert. VA to UID
and once you have this UID then you can go
to your page ownership directory, that's on your note.
And ask the question, please tell me who has the
PFD that corresponds to this UID? And this is
going to tell me oh here is the note that
contains the PFD for the UID that you're looking
for. Then I can go to that PFD and from
that PFD, I can get the page that I am
looking for which might be in that note or it might
say well it's not in my note any more. It's on
the disk. So this is the pack for page four handling.