Storage Section 2: Storage exercises

In today’s section, 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.

Simultaneously enrolled students are responsible for attending section and self-reporting their attendance at www.tinyurl.com/cs61sections.

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