MONEY
We discussed several kinds of computer storage in class, including:
Put those storage technologies in order by latency, slowest first. (An answer might be “DMCR”.)
What is the hit rate for `1 2 3 4 5`? Tell us the eviction algorithm and number of slots you’ve chosen.
0
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.
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);
We discussed several kinds of computer storage in class, including:
Put those storage technologies in order by cost per byte, cheapest first.
DMCr
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?
1 2 3
Which of the following file access patterns might have similar output from the strace utility? List all that apply or say “none.”
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.
Put those storage technologies in order by capacity in bytes on a typical computer, smallest first.
(DMCR)
RCMD
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).
Which of the following file access patterns might have similar output from the strace utility? List all that apply or say “none.”
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.
Which storage technology serves as the underlying storage for each of the following caches? If unsure, explain briefly.
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.
Which of the following file access patterns might have similar output from the strace utility? List all that apply or say “none.”
#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.
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 xx to slot x mod 3xmod3, would have 1 hit (the last 4).
True gets credit only if answer specifies an optimal replacement policy.
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.