Process Section 1 and Storage Exercises

College students: Attendance at section is required and recorded for all college students. All college students should fill out this attendance form when attending section. For more on the attendance policy and what to do if you miss section refer to the syllabus here and here.

Extension School students: Extension School students are required to self-report weekly section participation using this participation form. There are two ways to participate in section: (1) attend section live (for most students, this is one of the zoom sections, but local students are welcome to attend in-person sections) OR (2) watch a section recording (Canvas > Zoom > Published Recordings). Both participation methods are equally valid towards your participation grade.

In today’s section, we'll investigate the behavior of a shell to kick off the process control unit and problem set 5. 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.

Command line breakdown

The pset in this unit introduces a bunch of process control system calls through the medium of a shell implementation. A shell is a program responsible for running other programs; it’s the kind of program behind the command line terminal.

You’ll implement many interesting shell features, including complex command lines. So it’s important to understand how complex command lines are built.

• A command line consists of
  • Zero or more conditionals, each of which comprises
    • One or more pipelines, each of which comprises
      • One or more commands.

A command is a basic request to execute a program with some arguments. echo foo, for example, is a command. Pipelines, conditionals, and command lines combine commands to build more complex behaviors.

A precise way to explain command lines is with a BNF grammar. Here’s the shell grammar:

commandline ::= (empty)
          |  conditional
          |  conditional ";" commandline
          |  conditional "&" commandline

conditional ::=  pipeline
          |   conditional "&&" pipeline
          |   conditional "||" pipeline

pipeline ::=  command
          |   pipeline "|" command

command  ::=  word
          |   redirection
          |   command word
          |   command redirection

redirection  ::=  redirectionop filename
redirectionop  ::=  "<"  |  ">"  |  "2>"

The grammar says, for instance, that a commandline is zero or more conditionals, separated (and optionally terminated) by ; or &. It also defines conditionals in terms of pipelines, and pipelines in terms of commands.

EXERCISE. Test your understanding of the command line grammar. What are the conditionals in the following command line?

echo foo & echo bar | grep b && echo hello, there ; echo done < /dev/null

(It might be helpful to underline them.)

1. echo foo (terminated by &)
2. echo bar | grep b && echo hello, there (terminated by ;)
3. echo done < /dev/null (terminated by the end of the command line)

EXERCISE. What are the pipelines in that command line?

1. echo foo
2. echo bar | grep b
3. echo hello, there
4. echo done < /dev/null

EXERCISE. What are the commands in that command line?

1. echo foo
2. echo bar
3. grep b
4. echo hello, there
5. echo done < /dev/null

EXERCISE. What are the redirections in that command line, if any?

There’s only one: < /dev/null

EXERCISE. Can any pipeline span across more than one conditional? Why or why not?

No, this is impossible. The grammar shows that every pipeline that’s part of a valid command line is part of exactly one conditional.

Command line scientists

That helps show how command lines are built, but how do they behave? It’s possible to learn a lot by constructing “experiments”, namely command lines, and observing their behavior on a real shell!

Unix offers a toolbox of utilities useful for command line science.

For example, the behaviors of the && and || conditional operators can be explored with different combinations of programs like false, true, and echo.

# Hypothesis: `A && B` runs `B` iff `A` exits with status 0.
$ true && echo X
X
$ false && echo X
$ sh -c "exit 2" && echo X
# Hypothesis not falsified!


# Hypothesis: `A || B` runs `B` iff `A` does not exit with status 0.
$ true || echo X
$ false || echo X
X
$ sh -c "exit 2" || echo X
X
# Hypothesis not falsified!


# Hypothesis: The `sleep` command exits with status 1.
$ sleep 10 && echo Done
[10 seconds go by, then:] Done
# Hypothesis falsified 😢: it looks like `sleep` exits with status 0.

Indeed, it is true that A && B executes B only when A exits with status 0, and A || B executes B only when A does not exit with status 0!

In these exercises, you’ll attempt to explore more complex shell properties.

EXERCISE. Design command lines that test whether commands that are part of a single conditional are grouped left to right. That is, try and determine whether, given the chain A || B && C, commands are left associative:

1. A || B runs first.
   1. So A runs first.
   2. Then, depending on A’s status, B runs or is skipped.
2. Then, depending on A || B’s status, C runs or is skipped.

Or right associative:

1. A runs first.
2. Then, depending on A’s status, B && C runs or is skipped.

Or something entirely different.

To investigate this question and distinguish different groupings, we need long chains—more than 2 processes—and mixtures of && and ||. (If all the operators are the same, grouping won’t make any difference.) For instance, consider false && true || echo t1. If grouped left to right, as in ( false && true ) || echo t1, this would print t1: the exit status of false && true is 1—the same as false alone—and false || echo t1 prints t1. But grouped right to left, this would not print t1: false && ( true || echo t1 ) doesn’t execute the right-hand grouping.

$ false && true || echo t1
t1
$ true && true || echo t2
$ true && false || echo t3
t3
$ true || true && echo t4
t4
$ true || false && echo t5
t5
$ false || true && echo t6
t6

The above results can be explained by reasoning from left to right. If conditional chains were executed in some other way we would expect different results.

EXERCISE. Design command lines that test whether two-process pipelines, such as A | B, execute A and B concurrently (at the same time) or serially (B does not start until A has completed).

# If the right-hand command started after the left-hand command finished,
# then `foo` would never appear. It appears immediately.
$ yes | echo foo
foo

# If the left-hand command started after the right-hand command finished,
# then the error message would appear after 10 seconds (but it appears immediately).
$ cat /tmp/nonexistentfile | sleep 10
cat: /tmp/nonexistentfile: No such file or directory

EXERCISE. Design command lines that test whether the exit status of a conditional equals the exit status of the last-executed command in that conditional.

Hint. The $? shell variable equals the exit status of the most-recently-executed foreground conditional. For instance:

$ true
$ echo $?
0
$ false
$ echo $?
1
$ sh -c "exit 2"
$ echo $?
2

$ true && false
$ echo $?
1
$ true && sh -c "exit 2"
$ echo $?
2
$ sh -c "exit 3" && true
$ echo $?
3

EXERCISE. Design command lines that test whether the exit status of a pipeline equals the exit status of its rightmost command. (Try to avoid using $?.)

Conditionals can broadly test a command’s exit status (in the sense of “zero or not”).

$ false | false | false | false | true && echo foo
foo
$ false | false | true || echo foo
$ true | true | false && echo foo
$ true | true | false || echo foo
foo

Storage 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-14: Single-slot cache implementation.
• IO-17: Reference strings and hit rates.

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-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).

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.