Lecture 15: Caching and Remote Procedure Calls

Keaton Boyle / 15 March 2013

Caching Policy

We cache at multiple levels of memory, and we want the stuff we need soonest to have the fastest access time. We can order our storage according to speed in the following heirarchy, starting from the fastest:

We'll focus on RAM vs. disk.

We've already dealt with how things are done mechanically, the interesting question now is one of policy. It's a high level question that's largely independent of hardware as long as we assume a basically sequential-access disk and random-access memory. We need to be able to decide, when our physical memory is full and we need to pull a page from virtual memory which page we throw out of physical memory.

In other words, the fundamental question of caching policy is:

Who should be the victim?

The answer is different in different situations. Let's think about the following scenarios:

Suppose we have completely random access to virtual memory

It doesn't matter! We can choose any page to be the victim. But this supposition is pretty rare in practice. We typically see locality of reference. (Note: this "doesn't matter" answer also assumes that every file on disk has an equal cost of access.)

Suppose we have locality of reference

If we generally reference things near to us, there are a bunch of different heuristics that we use to choose which file to kick out of physical memory.

Here's a simple one:

First in First Out (FIFO)

The first page that got in is the first one to go. How do we check if our heuristic is any good? We could run it on a bunch of applications, but really all we need are the applications' "reference strings," or lists of virtual page accesses. Then we'll count the number of page faults and choose a heuristic that's fast and produces very few page faults.

Suppose we have 5 virtual pages and 3 virtual pages, with the access reference string of virtual pages 0 1 2 3 0 1 4 0 1 2 3 4.

What would this like under FIFO? (the numbers are physical pages, the letters are virtual pages, and * indicates a page fault)

Reference
string:
012301401234
A ?0*003*334*44444
B ??1*110*00002*3*3
C ???2*221*111111

This gives us a total of 9 page faults. 3/4 of our accesses were page faults. Not optimal.

How can we do better?

Well of course one option is just to buy more memory! An additional two pages would bring our number of page faults down to 5, one for each page of virtual memory. Let's look at what happens if we buy only 1 additional page though...

Reference
string:
012301401234
A?0*00004*44443*3
B??1*111110*0004*
C???2*222221*111
D????3*333332*22

That gives us 10 page faults! More than we had with less physical memory. This is strange and rare, but can happen occasionally. We call this Belady's Anomaly, where more memory actually makes things worse.

So not only is buying more memory expensive and limited, we can't even guarantee that it'll improve things! Hmmm... Well if we had a magic oracle, what would we do? We'd simply want to pick the page that isn't needed for the longest. That's basically what we want, right? So let's pretend that we're a magic computer that knows the reference string ahead of time. Then what kind of performance would we get? Let's try it, picking the page that is not needed for the longest.

Reference
string:
012301401234
A?000000000222
B??1111111113*3
C???2*3*334*44444

7 faults, well that's pretty darn nice. It'd be pretty cool if we could always have that... well we actually do have a bit of that in registers when we have a long string of non-branching compiled code. We know exactly what memory we'll need when! But that doesn't work so well for RAM and disk. So what's a good approximation to our oracle? How about kicking out the page that was used least recently? Let's try that.

Least Recently Used (LRU)

Reference
string:
012301401234
A?0*003*334*442*22
B??1*110*000003*3
C???2*221*111114*

Whoops! That's 10 page faults, hmmm. Usually LRU is better than FIFO, but occasionally we get exceptions. Oh well, moving on...

How do we actually implement this without attaching a timestamp or something to every single page? The hardware guys would not be pleased with that... What we end up using is a super low resolution clock. A single bit to indicate if a file has been accessed within some small amount of time in the past. Basically the system sets the permissions on all the pages to 000, so that attempted access to the pages will trap. On that trap, we flip the clock bit and every once in a while we reset all the clock bits to 0.

Cool! Now let's move on to a different problem.

Different Costs for Different Places on the Disk

If we're writing or reading from a sequential storage device like a hard disk, there are different costs associated with accessing different parts of the disk because the disk head takes longer to get to different places depending on where it currently is. A simple model is just that the cost of an I/O is proportional to the distance, i.e.:

cost ∝ |j-i|

Where j is the position of the read/write head and i is the spot we want to access.

Now let's suppose again that access to the disk is completely random. What's the average cost of an I/O? The average cost to read if the head is at the end is 1/2, the average cost to read if the head is in the middle is 1/4. We need to sum up these probabilities over all possible head positions:

average cost = 01[ h2/2 + (1-h)2/2] dh = 1/3

But this assumes first-come-first-serve (FCFS), serving every request in order and moving the disk arm to wherever it needs to be to serve that request, no matter where it is at the moment or where other requests are in the queue. Generally we have a queue of requests, which is kind of like being able to look into the future in our examination of caching. We should make use of this information to stop moving our disk head back and forth so often! But how...

Shortest Seek-Time First (SSTF)

If we just get whatever bit of the disk is closest to us, we're blazingly fast!

But the starvation problem is a real one. If one process is constantly queueing requests on one side of the disk, a process making requests for things faraway on the disk will never get helped. Can't have that. What about...

The Elevator Algorithm

It's like SSTF, but we always keep going in the same direction on the disk if there are still any requests in that direction.

Other possibilities...

To fix the fairness problem with the Elevator Algorithm, we usually do something like the Circular Elevator Algorithm. Basically at the end of the disk, we seek back to the lowest-addressed request on the disk. We lose some throughput because of that, but we get significantly more fairness.

Another option is to somehow combine SSTF and FCFS, by serving a chunk of requests with SSTF and then moving onto the next chunk.

And now for something completely different...

Distributed Systems and Remote Procedure Calls (RPC)

Up until now, we've focused on virtualization as the primary means to enforce modularity. Things are nicely layered to keep systems from interfering with one another. But another approach to modularity is distribution. Instead of doing something kernel mode vs. user mode we could have something like a server vs. a client, talking to one another over a network.

In a sense, we have a caller client who communicates, over the network, with a callee server. But unlike the caller-callee relationship that exists with something like a system call, in a client-server relationship the two parties don't have a shared address space. The kernel would have been able to see what was in the user's address space; the server can only see what the client has sent it over the network.

As always, this has its pluses and minuses:

We don't have call-by-reference. We can't "pass a pointer." If we're dealing with lots of data, we need to send all the data over the network.

Furthermore, clients and servers might disagree on things like architectures, number formats, all sorts of stuff. So we need to establish some sort of network protocol to provide a standard for communication and to specify how we represent data on the wire. For example, as it turns out we use 32-bit big-endian 2's-complement form for integers.

There's still the problem of reducing complex objects that point all over the place into a single serial stream of bytes that we can put on a wire. That serializing and ordering process we call marshalling. The client takes a complex data objects, puts it nicely into an ordered packet of bytes, sends it across the wire, and then the server unmarshalls it, reforming the complex data object in a way that works for the server. Voila!

Remote Procedure Calls

Remote Procedure Calls (RPC) are a common pattern of organizing the client-server relationship. To the client, calling the server looks like a simple function call. Say we want to get the weather in some location and we're connected to a server that can serve forecasted high temperature in Fahrenhiet if you provide it with a zip code. We'd want to be able to do something like this on the client side:


int temp = get_temp(90024);

And on the server we'd want to be able to write some function that just returns that value...


int get_temp(int zip)
{
  // lookup zip code, find high temp, etc.
  return temp;
}

We can usually do something that sort of acts like this, but we'll have to package it all up with a bunch of other things that take care of, for example, the marshalling of the zip integer into proper network format, the setting up of the connection with the weather server, sending the actual data, receiving the response and storing it in temp, all that good stuff. This packaging can usually be done for us with some automated code generation, which is great! Once we specify the necessary parameters and return types and such, we can effectively simulate the client/server relationship with function calls.

Trouble with RPC

All sorts of things can go wrong when we're on the network though, so the RPC framework has a lot to worry about. Messages can get corrupted, messages can be lost, messages can be duplicated, there are all sorts of problems. So how do we address this? Say a client tries to delete a file on the server with an RPC version of unlink(). What if the client doesn't receive any sort of "return value" from the server? We won't know if the server never received the message or received it and rejected the request or received it and accepted the request but somehow the resonse got lost... 'Tis a tough problem to solve. Some potential ways to deal with this:

Keep sending the request!
If we don't receive a response after a little while, re-send the request. Then wait a little longer and resend again. And then again. When (if) we finally get a response, we will know that the request has been received at least once. But this could be problematic if multiple unlinks were called when, say, another client may have recreated the file in between successive calls. Not a perfect solution.
Return an error if we don't get a response
If we don't receive a response to our first request after a little while, return an error. When this call returns, we will know that the request could have been received at most once. It may or may not actually have been received, because we don't know if the dropped message was coming to or from the server. Again, not a perfect solution.
Combination?
Ideally we'd have a combination of the two that somehow produces an exactly once RPC, but this is pretty darn difficult to implement...

Anyway, what are some things we use RPC's for? One example is the X-Window protocol, common for serving graphic interfaces over the network. The client side calls things like draw_pixel(x, y, r, g, b, a) or draw_triangle(x1, y1, x2, y2, x3, y3, r, g, b, a) and the other side should take those requests and draw them on the server screen. What this means is lots of requests going to the server and we'd be dead if we want this to be any sort of realtime application and the client is waiting for a server response after drawing each pixel. That's why we do things like pipelining, where we issue a bunch of requests and receive their responses asynchronously. It's parallel sending and receiving, and it allows for much faster communication. More on that in the next lecture...