Section 8

This section begins with using a single-slot cache for reading, which will help you to begin the problem set. Then, we’ll walk through a selection of our storage exercises, which are problems taken from prior exams. Also take the opportunity to ask questions about the problem set and class material.

Terminology: Blocks, slots, and addresses

A cache is a small amount of fast storage that helps speed up access to slower underlying storage. The underlying storage often has larger capacity than the cache, meaning that it can hold more total data. When discussing caches in general, we use these terms:

• A block is a unit of data storage. Both the underlying storage and the cache are divided into blocks. In some caches, blocks have fixed size; in others, blocks have variable size. A cache determines its block size, though in some cases it will use a natural block size taken from the underlying storage.

• Each block of underlying storage has an address. We represent addresses abstractly as integers, though in a specific cache, an address might be a memory address, an offset into a file, a disk position, or even a web page’s URL.

• Each block in the cache is a slot. A slot can either be empty or full. An empty slot has no data, while a full slot contains a cached version of a specific block of underlying storage. A full slot therefore has an associated address, which is the address of that block on underlying storage.

File positions

Standard I/O caches are intended to speed up access to data read and written from file descriptors, which are the Unix representation of data streams and random-access files. System calls like read and write perform the reading and writing. Standard I/O caches can improve performance by reducing the number of system calls performed.

Besides transferring data from or to a file, read and write also affect the file descriptor’s file position. This is a numeric byte offset representing the current position in the file.¹ A read or write system call starts reading or writing at the current file position, and then increments the file position by the number of characters processed.

The kernel maintains all file positions. User processes can only observe or affect a file position by making a system call, such as read, write, or lseek. (lseek system call modifies the file position without transferring data, and is required to read or write a file out of sequential order.)

As a result, successive calls to read progress sequentially through the file. You can see this in the following example.

1. Right before executing read(fd, buf, 1) on a just-opened file (the file position is shown in red):

   

2. After read(fd, buf, 1):

   

3. After read(fd, buf, 2):

   

4. After read(fd, buf, 3):

   

Single-slot cache

A single-slot cache is, as the name suggests, a cache comprising a single slot. The standard I/O cache implemented in most operating systems’ standard I/O libraries has a single slot.

Today in section we’re going to work on a specific single-slot I/O cache design. The purpose is to explain caches and to get you used to thinking in terms of file offsets.

Here’s the representation.

struct io61_fcache {
    int fd;

    // `bufsiz` is the cache block size
    static constexpr off_t bufsize = 4096;
    // Cached data is stored in `cbuf`
    unsigned char cbuf[bufsize];

    // The following “tags” are addresses—file offsets—that describe the cache’s contents.
    // `tag`: File offset of first byte of cached data (0 when file is opened).
    off_t tag;
    // `end_tag`: File offset one past the last byte of cached data (0 when file is opened).
    off_t end_tag;
    // `pos_tag`: Cache position: file offset of the cache.
    // In read caches, this is the file offset of the next character to be read.
    off_t pos_tag;
};

pos_tag refers to the effective file position for users of io61 functions. That is, the next io61_read or io61_write function should begin at the file offset represented by pos_tag. Note that this is often different from the file descriptor’s file position (the value maintained by the kernel)!

EXERCISE. Given the above description of the representation, how can you tell if an io61_fcache is empty (contains no cached data)?

A cache is empty if tag == end_tag. This makes tags work similarly to iterators—a C++ standard library data structure d is empty when d.begin() == d.end().

EXERCISE. What data invariants might apply to this representation?

Here are two that follow immediately from the cache representation (we’ll see more below). These could, and probably should, be encoded as assertions!

• tag <= end_tag.
• end_tag - tag <= bufsize. The cache slot contains space for at most bufsize data bytes.

Example single-slot cache for reading

To demonstrate how this single-slot cache representation might work, we walk through the file position example with a small bufsize of 4 for clarity. The goal of a read cache is to produce results equivalent to a similar series of system calls², so our io61_reads should return the same bytes in the same order as the reads above.

1. The cache is initialized to an empty state, with fd 3, bufsiz 4, and all of tag, pos_tag, and end_tag equal to 0. When the first io61_read request is passed to the cache, it must fill its buffer with a call to read.

   

2. The read succeeds, filling all 4 bytes in cbuf. The end_tag is updated to indicate that the cache is full (contains 4 bytes of file data).

   

3. Now there is enough data in the cache to fulfill the io61_read request. The request starts from the offset corresponding to pos_tag, and must increment pos_tag according to the amount read (just as read updates the kernel’s file position by the amount read).

   

4. The next io61_read request can be satisfied entirely from the cache. No system calls occur, so the kernel’s file position is unchanged.

   

5. 

6. The cache contains just 1 byte of data after pos_tag, so the next io61_read request can only be partially satisfied at first.

   

7. Since short reads and writes are allowed by the specifications of io61_read and io61_write, it would be safe for io61_read to return now, with a short read of 1 byte! This still counts as equivalent to the version with system calls, because the same bytes are being returned in the same order.³

   

8. But it’s probably better to try to return as much data as the user requested. This requires refilling the cache. We update tag before refilling the cache (because the offset of the first cached byte would equal the file position);

   

9. and then, after the read succeeds, update end_tag (because the cache is filled).

   

10. Finally, the last 2 bytes can be returned to the user.

    

EXERCISE. Having worked through an example, can you add any more data invariants for this cache representation?

• tag <= pos_tag <= end_tag. (For later parts of the pset, though, note that after adding support for io61_seek, some people break this invariant: they let pos_tag go outside the range of [tag, end_tag) after an io61_seek call. Since any character that is read or written must access an offset in that range, these people then check whether tag <= pos_tag <= end_tag inside io61_read and io61_write. If pos_tag has gone out of range, these functions must reinitialize the cache before they continue.)
• The cache slot contains end_tag - tag bytes of valid data.
• If tag == end_tag, then the cache slot is empty (contains no valid data).
• If tag <= off < end_tag, then byte cbuf[off - tag] corresponds to the byte of file data at offset off.
• The file descriptor’s file position equals end_tag for read caches of seekable files. (It equals tag for write caches of seekable files.)
• A io61_read or io61_write call should begin accessing the file at the offset equal to pos_tag. Thus, the first byte read by io61_read should come from file offset pos_tag.

These are harder to check with assertions.

Fill read cache

As you implement, remember the invariants: we find the invariants and representation extremely good guidance for a correct implementation.

EXERCISE SS1. Implement this function, which should fill the cache with data read from the file. You will make a read system call.

void io61_fill(io61_fcache* f) {
    // Empty the cache entry, then fill it with new data.
    // The new data is taken from the file starting at file offset `end_tag`
    // (which equals the file position).
    // The cache position equals the first character read.
    // Only called for read caches.

    // Check invariants.
    assert(f->tag <= f->pos_tag && f->pos_tag <= f->end_tag);
    assert(f->end_tag - f->pos_tag <= f->bufsize);

    // Reset the cache to empty.
    f->tag = f->pos_tag = f->end_tag;










    // Recheck invariants (good practice!).
    assert(f->tag <= f->pos_tag && f->pos_tag <= f->end_tag);
    assert(f->end_tag - f->pos_tag <= f->bufsize);
}

SUB-EXERCISE. Which cache tags will need to change in this function, and by how much?

SUB-EXERCISE. Do you need to use memcpy in this function?

This function can change all of tag, pos_tag, and end_tag. It changes tag because the cache is emptied and read starting from end_tag, so the new tag equals the old end_tag. It changes end_tag to reflect the data read. It changes pos_tag to change the cache position.

There is no need for memcpy in this function; it can read data directly into the cache!

void io61_fill(io61_fcache* f) {
    // Fill the read cache with new data, starting from file offset `end_tag`.
    // Only called for read caches.

    // Check invariants.
    assert(f->tag <= f->pos_tag && f->pos_tag <= f->end_tag);
    assert(f->end_tag - f->pos_tag <= f->bufsize);

    /* ANSWER */
    // Reset the cache to empty.
    f->tag = f->pos_tag = f->end_tag;
    // Read data.
    ssize_t n = read(f->fd, f->cbuf, f->bufsize);
    if (n >= 0) {
        f->end_tag = f->tag + n;
    }

    // Recheck invariants (good practice!).
    assert(f->tag <= f->pos_tag && f->pos_tag <= f->end_tag);
    assert(f->end_tag - f->pos_tag <= f->bufsize);
}

Read from read cache (simple version)

EXERCISE SS2. Implement io61_read, assuming that the desired data is entirely contained within the current cache slot.

ssize_t io61_read(io61_fcache* f, unsigned char* buf, size_t sz) {
    // Check invariants.
    assert(f->tag <= f->pos_tag && f->pos_tag <= f->end_tag);
    assert(f->end_tag - f->pos_tag <= f->bufsize);

    // The desired data is guaranteed to lie within this cache slot.
    assert(sz <= f->bufsize && f->pos_tag + sz <= f->end_tag);





}

SUB-EXERCISE. Which cache tags will need to change in this function, and by how much?

SUB-EXERCISE. Do you need to use memcpy in this function?

ssize_t io61_read(io61_fcache* f, unsigned char* buf, size_t sz) {
    // Check invariants.
    assert(f->tag <= f->pos_tag && f->pos_tag <= f->end_tag);
    assert(f->end_tag - f->pos_tag <= f->bufsize);

    // The desired data is guaranteed to lie within this cache slot.
    assert(sz <= f->bufsize && f->pos_tag + sz <= f->end_tag);

    /* ANSWER */
    memcpy(buf, &f->cbuf[f->pos_tag - f->tag], sz);
    f->pos_tag += sz;
}

Read from read cache (full version)

EXERCISE SS3. Implement io61_read without that assumption. You will need to call io61_fill, and will use a loop. You may assume that no call to read ever returns an error.

Our tests do not check whether your IO61 library handles errors correctly. This means that you may assume that no read and write system call returns a permanent error. But the best implementations will handle errors gracefully: if a read system call returns a permanent error, then io61_read should return -1. (What to do with restartable errors is up to you, but most I/O libraries retry on encountering EINTR.)

ssize_t io61_read(io61_fcache* f, unsigned char* buf, size_t sz) {
    // Check invariants.
    assert(f->tag <= f->pos_tag && f->pos_tag <= f->end_tag);
    assert(f->end_tag - f->pos_tag <= f->bufsize);









}

SUB-EXERCISE. Which cache tags will need to change in this function, and by how much?

SUB-EXERCISE. Do you need to use memcpy in this function?

ssize_t io61_read(io61_fcache* f, unsigned char* buf, size_t sz) {
    // Check invariants.
    assert(f->tag <= f->pos_tag && f->pos_tag <= f->end_tag);
    assert(f->end_tag - f->pos_tag <= f->bufsize);

    /* ANSWER */
    size_t pos = 0;
    while (pos < sz) {
        if (f->pos_tag == f->end_tag) {
            io61_fill(f);
            if (f->pos_tag == f->end_tag) {
                break;
            }
        }

        // This would be faster if you used `memcpy`!
        buf[pos] = f->cbuf[f->pos_tag - f->tag];
        ++f->pos_tag;
        ++pos;
    }
    return pos;
}

Exercises

All exercises assume a 64-bit x86-64 architecture unless otherwise stated.

The main subjects of these exercises are:

• IO-19: File system calls.
• IO-20: Types of cache.
• IO-4: Reading straces.
• IO-17: Reference strings and hit rates.
• IO-14: Single-slot cache implementation.

IO-19. File system calls

QUESTION IO-19A. A program makes these system calls:

int fd = open("f.txt", O_WRONLY | O_CREAT | O_TRUNC);
ssize_t nw = write(fd, "CS121 is awesome!", 17); // returned 17

What following series of system calls would ensure that, after all system calls complete, the file f.txt contains the text “CS 61 is terrible” (without the quotation marks)? Minimize the number of bytes written.

The open system call truncates the file, so after the write, the file contains just the 17-byte string. Here’s that string aligned with the string we want:

CS121 is awesome!
CS 61 is terrible

So we want to overwrite 12 with 6 and awesome! with terrible. That requires four system calls that write a minimum of 10 bytes:

lseek(fd, 2, SEEK_SET);
write(fd, " 6", 2);
lseek(fd, 9, SEEK_SET);
write(fd, "terrible", 8);

Or you can just overwrite the whole contents, but that writes more bytes.

lseek(fd, 0, SEEK_SET);
write(fd, "CS 61 is terrible", 17);

QUESTION IO-19B. Which of the following file access patterns might have similar output from the strace utility? List all that apply or say “none.”

1. Sequential byte writes using stdio
2. Sequential byte writes using mmap
3. Sequential byte writes using system calls

None. All those patterns are easy to distinguish; mmap will have no write system calls, stdio will write blocks of 4096 bytes, and only #3 will write bytes.

QUESTION IO-19C. Which of the following file access patterns might have similar output from the strace utility? List all that apply or say “none.”

1. Sequential byte writes using stdio
2. Sequential block writes using stdio
3. Sequential byte writes using system calls
4. Sequential block writes using system calls

1, 2, and 4 will look similar. The stdio cache transforms byte writes to block writes, so 1 and 2 will look similar. Writing blocks using system calls can look similar as well as long as the block size is the same as stdio’s block size.

QUESTION IO-19D. Which of the following file access patterns might have similar output from the strace utility? List all that apply or say “none.”

1. Reverse-sequential byte writes using stdio
2. Reverse-sequential block writes using stdio
3. Reverse-sequential byte writes using system calls
4. Reverse-sequential block writes using system calls

#2 and #4 might look similar if the block writes used the stdio block size. stdio will emit one lseek and one write per block write, resulting in a sequence like this:

lseek(4, 966656, SEEK_SET)              = 966656
write(4, "A\nA's\nAMD\nAMD's\nAOL\nAOL's\nAachen"..., 4096) = 4096
lseek(4, 962560, SEEK_SET)              = 962560
write(4, "\nAllyson's\nAlma\nAlma's\nAlmach\nAl"..., 4096) = 4096

That’s the same as we would expect from system calls for reverse-sequential blocks.

What about reverse-sequential bytes? You may remember that when the stdio library reads bytes in reverse-sequential order, strace shows large read system calls interleaved with many lseeks (try it with r-stdiobyterev):

lseek(3, 970752, SEEK_SET)              = 970752
read(3, "zigzags\nzilch\nzilch's\nzillion\nzi"..., 4096) = 826
lseek(3, 971578, SEEK_SET)              = 971578
lseek(3, 971578, SEEK_SET)              = 971578
lseek(3, 971578, SEEK_SET)              = 971578
lseek(3, 971578, SEEK_SET)              = 971578
...

But stdio writes are different! Use strace on w-stdiobyterev and you’ll see this pattern:

lseek(3, 51199980, SEEK_SET)            = 51199980
write(3, "6", 1)                        = 1
lseek(3, 51199979, SEEK_SET)            = 51199979
write(3, "6", 1)                        = 1
lseek(3, 51199978, SEEK_SET)            = 51199978
write(3, "6", 1)                        = 1
lseek(3, 51199977, SEEK_SET)            = 51199977
write(3, "6", 1)                        = 1
...

#1 and #3, therefore, are likely to have the same strace.

IO-20. Caches Big, Fast, and Cheap

QUESTION IO-20A. We discussed several kinds of computer storage in class, including:

4. Drives (disks and SSDs)
13. primary Memory
3. processor Cache memory
18. Registers

Put those storage technologies in order by latency, slowest first. (An answer might be “DMCR”.)

DMCR. Disks and SSDs are slowest and cheapest per byte and have the largest capacity. Next fastest, more expensive, and smaller is primary memory (DRAM), then cache memory (SRAM), and finally registers.

QUESTION IO-20B. Put those storage technologies in order by cost per byte, cheapest first.

DMCR—the same.

QUESTION IO-20C. Put those storage technologies in order by capacity in bytes on a typical computer, smallest first.

RCMD—the reverse!

QUESTION IO-20D. Which storage technology serves as the underlying storage for each of the following caches? If unsure, explain briefly.

1. Buffer cache
2. Stdio cache
3. Processor cache

1. D. The buffer cache is the operating system’s cache in primary memory of data located on drives.
2. M is the best answer! The stdio cache actually serves to cache data from the buffer cache, which is stored in primary memory.
3. M. The processor cache is the processor’s cache for lines (blocks) of primary memory.

QUESTION IO-20E. True or false? Given a cache with two or more blocks, implementing it as a fully associative cache would always produce as good or better hit rates than a direct-mapped implementation.

False. Consider a cache with 3 slots and the reference string 1 4 2 3 5 4. A fully-associative FIFO cache would have no hits. However, a direct-mapped cache that sent address x to slot x \bmod 3, would have 1 hit (the last 4).

True gets credit only if answer specifies an optimal replacement policy.

QUESTION IO-20F. True or false? Prefetching bytes from a file on disk into the buffer cache can cause the buffer cache to become incoherent.

False: the buffer cache is always coherent.

IO-4. I/O caching and strace

Elif Batuman is investigating several program executables left behind by her ex-roommate Fyodor. She knows these executables perform byte-at-a-time I/O, but she’s not sure what kinds of caches they use. To find out, she runs each executable under strace in the following way:

strace -o strace.txt ./EXECUTABLE files/text1meg.txt > files/out.txt

Help her figure out properties of these programs based on their system call traces.

QUESTION IO-4A. Program ./mysterya:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x8193000
brk(0x81b5000)                          = 0x81b5000
read(3, "A", 1)                         = 1
write(1, "A", 1)                        = 1
read(3, "\n", 1)                        = 1
write(1, "\n", 1)                       = 1
read(3, "A", 1)                         = 1
write(1, "A", 1)                        = 1
read(3, "'", 1)                         = 1
write(1, "'", 1)                        = 1
read(3, "s", 1)                         = 1
write(1, "s", 1)                        = 1
...

List at least one option in each column.

1, Sequential reads; a, No read cache; i, No write cache; D, Other.

Reads are sequential because there are no seeks. Since both reads and writes are happening one byte at a time, it seems very unlikely a cache is involved.

QUESTION IO-4B. Program ./mysteryb:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x96c5000
brk(0x96e6000)                          = 0x96e6000
read(3, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 2048) = 2048
write(1, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 2048) = 2048
read(3, "kad\nAkron\nAkron's\nAl\nAl's\nAla\nAl"..., 2048) = 2048
write(1, "kad\nAkron\nAkron's\nAl\nAl's\nAla\nAl"..., 2048) = 2048
...

List at least one option in each column.

1, Sequential I/O; b OR c, unaligned OR aligned read cache; ii, Write cache; B, Cache size 2048.

Again, there are no seeks, so reads are most likely sequential; but since reads and writes happen in 2048-byte blocks, there are likely both read and write caches with that size block. We don’t know whether the read cache is aligned because the reads are sequential: only non-sequential reads distinguish between aligned and unaligned read caches.

QUESTION IO-4C. Program ./mysteryc:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x9064000
brk(0x9085000)                          = 0x9085000
fstat64(3, {st_mode=S_IFREG|0664, st_size=1048576, ...}) = 0
lseek(3, 1046528, SEEK_SET)             = 1046528
read(3, "ingau\nRheingau's\nRhenish\nRhianno"..., 2048) = 2048
write(1, "oR\ntlevesooR\ns'yenooR\nyenooR\ns't"..., 2048) = 2048
lseek(3, 1044480, SEEK_SET)             = 1044480
read(3, "Quinton\nQuinton's\nQuirinal\nQuisl"..., 2048) = 2048
write(1, "ehR\neehR\naehR\ns'hR\nhR\nsdlonyeR\ns"..., 2048) = 2048
lseek(3, 1042432, SEEK_SET)             = 1042432
read(3, "emyslid's\nPrensa\nPrensa's\nPrenti"..., 2048) = 2048
write(1, "\ns'nailitniuQ\nnailitniuQ\nnniuQ\ns"..., 2048) = 2048
lseek(3, 1040384, SEEK_SET)             = 1040384
read(3, "Pindar's\nPinkerton\nPinocchio\nPin"..., 2048) = 2048
write(1, "rP\ndilsymerP\ns'regnimerP\nregnime"..., 2048) = 2048
...

List at least one option in each column.

2, Reverse sequential reads; c, Aligned read cache; ii, Write cache; B, Cache size 2048

Again a 2048-byte cache is involved. The writes take place sequentially (no seeks on file descriptor 1). However, the read file descriptor is subject to seeks; those seeks start from a high number and uniformly decrease, indicating reverse sequential reads. (Furthermore, the lines written look like reverses of the lines read!) We can assume the read cache is aligned because (1) offsets are aligned to multiples of 2048, and (2) unaligned read caches read redundant data on reverse-sequential access patterns.

QUESTION IO-4D. Program ./mysteryd:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x9a0e000
brk(0x9a2f000)                          = 0x9a2f000
fstat64(3, {st_mode=S_IFREG|0664, st_size=1048576, ...}) = 0
lseek(3, 1048575, SEEK_SET)             = 1048575
read(3, "o", 2048)                      = 1
lseek(3, 1048574, SEEK_SET)             = 1048574
read(3, "Ro", 2048)                     = 2
lseek(3, 1048573, SEEK_SET)             = 1048573
read(3, "\nRo", 2048)                   = 3
...
lseek(3, 1046528, SEEK_SET)             = 1046528
read(3, "ingau\nRheingau's\nRhenish\nRhianno"..., 2048) = 2048
write(1, "oR\ntlevesooR\ns'yenooR\nyenooR\ns't"..., 2048) = 2048
lseek(3, 1046527, SEEK_SET)             = 1046527
read(3, "eingau\nRheingau's\nRhenish\nRhiann"..., 2048) = 2048
lseek(3, 1046526, SEEK_SET)             = 1046526
read(3, "heingau\nRheingau's\nRhenish\nRhian"..., 2048) = 2048
...

List at least one option in each column.

2, Reverse sequential reads; b, Unaligned read cache; ii, Write cache; B, Cache size 2048.

Compare this output with the output of ./mysteryc above: this is the kind of redundant reading typical of an unaligned read cache on a reverse-sequential access pattern.

QUESTION IO-4E. Program ./mysterye:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x93e5000
brk(0x9407000)                          = 0x9407000
read(3, "A", 1)                         = 1
read(3, "\n", 1)                        = 1
read(3, "A", 1)                         = 1
...
read(3, "A", 1)                         = 1
read(3, "l", 1)                         = 1
write(1, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 1024) = 1024
read(3, "t", 1)                         = 1
read(3, "o", 1)                         = 1
read(3, "n", 1)                         = 1
...

List at least one option in each column.

1, Sequential reads; a, No read cache; ii, Write cache; C, (write) cache size 1024.

QUESTION IO-4F. Program ./mysteryf:

open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x9281000
brk(0x92a3000)                          = 0x92a3000
read(3, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 4096) = 4096
write(1, "A", 1)                        = 1
write(1, "\n", 1)                       = 1
write(1, "A", 1)                        = 1
...
write(1, "A", 1)                        = 1
write(1, "l", 1)                        = 1
read(3, "ton's\nAludra\nAludra's\nAlva\nAlvar"..., 4096) = 4096
write(1, "t", 1)                        = 1
write(1, "o", 1)                        = 1
write(1, "n", 1)                        = 1
...

List at least one option in each column.

1, Sequential IO; b OR c, unaligned OR aligned read cache; i, No write cache; A, Cache size 4096.

IO-17. Reference strings and hit rates

QUESTION IO-17A. Write a purely-sequential reference string containing at least five accesses.

There sure are infinite examples! One is 1 2 3 4 5.

QUESTION IO-17B. What is the hit rate for this reference string? Tell us the eviction algorithm and number of slots you’ve chosen.

0/5 (0%). This is the same for all algorithms and numbers of slots, for reactive caches like the ones we used in class!

Parts C and D concern this ten-element reference string:

1 2 1 2 3 4 1 5 1 1

We consider executing this reference string starting with different cache contents.

QUESTION IO-17C. A three-slot LRU cache processes this reference string and observes a 70% hit rate. What are the initial contents of the cache?

It must be 1 2 3. In 3-slot LRU, whatever the initial contents of the cache are, the contents after “4 1 5” will be “4 1 5”, and all of “4 1 5” will miss. (4 will evict 1, because at that point in the string, 1 is least-recently used. Then 1 will evict 2 and 5 will evict 3.) Given that content, “1 1” will hit. So of the last 5 accesses, there will definitely be 3 misses, and the maximum possible hit rate for the whole string is bounded at 70%. The only way to get 70%, rather than a higher or lower rate, is to start with 1 2 3, with which the first 5 accesses will hit.

QUESTION IO-17D. A three-slot FIFO cache with initial contents 4, 1, and 2 (in slots A, B, and C, respectively) processes the reference string and observes a 60% hit rate. Which slot was next up for eviction when the reference string began? (Assume the slots were initially filled in alphabetical order.)

Slot A (the first slot containing 4).

1. If A was next up to be evicted, the cache observes 4 misses and a 60% hit rate.

   	Start	1	2	1	2	3	4	1	5	1	1
   A	4					③			⑤
   B	1	1		1			④
   C	2		2		2			①		1	1

2. If B was next up to be evicted, the cache observes 3 misses and a 70% hit rate.

   	Start	1	2	1	2	3	4	1	5	1	1
   A	4						4		⑤
   B	1	1		1		③
   C	2		2		2			①		1	1

3. If C was next up to be evicted, the cache observes 2 misses and a 80% hit rate.

   	Start	1	2	1	2	3	4	1	5	1	1
   A	4						4		⑤
   B	1	1		1				1		1	1
   C	2		2		2	③

The eviction algorithms we saw in class are entirely reactive: they only insert a block when that block is referenced. This limits how well the cache can perform. A read cache can also be proactive by inserting blocks before they’re needed, possibly speeding up later accesses. This is the essence of prefetching.

In a proactive caching model, the cache can evict and load two or more blocks per access in the reference string. A prefetching policy decides which additional, non-accessed blocks to load.

QUESTION IO-17E. Describe an access pattern for which the following prefetching policy would be effective: When filling a cache with block A, also load block A+1 into another slot.

Sequential access will work well: every other block access will hit the cache.

QUESTION IO-17F. Write a reference string and name an eviction policy and/or cache size for which this prefetching policy would be less effective (have a lower hit rate) than no prefetching at all.

One example that works for any eviction policy is a two-slot cache and an access pattern that alternates between non-sequential blocks. For example, 1 3 1 3 1 3 1 3…. The access to 1 will fill the cache with 1 and 2. The access to 3 will then fill the cache with 3 and 4, evicting 1. And sadly so forth, yielding 0% hit rate.

IO-14. Cache code

Several famous musicians have just started working on the standard I/O problem set. They share the following code for their read-only, sequential, single-slot cache:

struct io61_file {
    int fd;
    unsigned char buf[4096];
    size_t pos;    // position of next character to read in `buf`
    size_t sz;     // number of valid characters in `buf`
};

int io61_readc(io61_file* f) {
    if (f->pos >= f->sz) {
        f->pos = f->sz = 0;
        ssize_t nr = read(f->fd, f->buf, sizeof(f->buf));
        if (nr <= 0) {
            f->sz = 0;
            return -1;
        } else {
            f->sz = nr;
        }
    }
    int ch = f->buf[f->pos];
    ++f->pos;
    return ch;
}

But they have different io61_read implementations. Donald (Lambert)’s is:

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    return read(f->fd, buf, sz);
}

Solange (Knowles)’s is:

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    for (size_t pos = 0; pos < sz; ++pos, ++buf) {
        *buf = io61_readc(f);
    }
    return sz;
}

Caroline (Shaw)’s is:

ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
    if (f->pos >= f->sz) {
        return read(f->fd, buf, sz);
    } else {
        int ch = io61_readc(f);
        if (ch < 0) {
            return 0;
        }
        *buf = ch;
        return io61_read(f, buf + 1, sz - 1) + 1;
    }
}

You are testing each of these musicians’ codes by executing a sequence of io61_readc and/or io61_read calls on an input file and printing the resulting characters to standard output. There are no seeks, and your test programs print until end of file, so your tests’ output should equal the input file’s contents.

You should assume for these questions that no read system call ever returns -1.

QUESTION IO-14A. Describe an access pattern—that is, a sequence of io61_readc and/or io61_read calls (with lengths)—for which Donald’s code can return incorrect data.

io61_readc(f), io61_read(f, buf, 1), …: Any alternation between readc and read is a disaster. This is because Donald’s readc reads a full block of data into the cache, but his read ignores the cache, reading data directly from the kernel. This will read data from the wrong file position.

QUESTION IO-14B. Which of these musicians’ codes can generate an output file with incorrect length?

Solange’s io61_read code never returns end-of-file—she mistakes EOF for a valid return value—so any program that reads a file using her io61_read will think that file has infinite length.

If a program using Donald’s code calls io61_readc once and then switches to io61_read, then they will read too few bytes (since bytes in the readc buffer won’t be returned).

Caroline’s code will always produce the correct length output file.

QUESTION IO-14C. Give a sequence of io61 calls for which Solange’s code will outperform Donald’s, or vice versa, and explain briefly.

Since Solange and Donald share an implementation of io61_readc, any differences will arise from io61_read calls. The basic difference between the implementations is that Solange’s code uses the cache—though in an expensive manner: Solange calls io61_readc rather than memcpy, which would be faster—and Donald’s code makes direct system calls. As a result, Solange’s code will outperform Donald’s on a sequence of io61_read calls with small sizes (such as 1), and Donald’s code will outperform Solange’s on a sequence of io61_read calls with large sizes (such as 4096 or even 10000).

QUESTION IO-14D. Suggest a small change (≤10 characters) to Caroline’s code that could make it perform at least as well as both Solange’s and Donald’s codes on all access patterns. Explain briefly.

Given the reasoning in part C, a good change would be to make direct system calls for large-sized io61_read calls and to use the cache for small-sized io61_read calls. It’s important, though, to use cached data when that data exists. A simple change that accomplishes this is to change the test if (f->pos >= f->sz) to if (f->pos >= f->sz && sz >= 1024) (or 4096, or something similar).