This is a four-part assignment. The parts are to be submitted to Expertiza under the names cache_vm_opns, cache_vm_infer, free_list_is_OK, and 2_level_page_table. Solutions are due at May 4 at 11:59pm.
This is not a partnership assignment. Hand in your own work.
Consider a computer with the following properties:
Part of a program is swapped in and resumed at the statement labeled seg:
seg: add $t0,$t1,$t2 sll $t0,$t0,2 ...
Assume that the TLB and the cache are empty, seg's virtual address is 0x00404020,
and there is a page table entry mapping virtual page number 0x00404
to physical page number 0x19423.
Using only operations given in the table below, identify the sequence of accesses and updates
to the TLB, the cache, and the page table that result from executing first the add,
then the sll in the program segment just given.
Do this by filling in lines in the file
~cs61cl/code/cache_vm_opns.txt with entries of the form "cache n" or "vm n"
(where n stands
for a number in the table). You won't need all the lines, nor will you need all the operations
in the table.
Submit your cache_vm_opns.txt to Expertiza under the name cache_vm_opns.
| VM operations | Cache operations |
|
|
The program ~cs61cl/code/cache.c produces timing data for accesses of elements in an array. It is similar to though more elaborate than the cache.s program you used earlier in lab. Here is its main loop:
for (index = 0; index < limit; index = index + stride) {
x[index] = x[index] + 1;
}
The surrounding code coordinates the setting of the variables limit and stride and the timing of the loop.
Each loop/stride test is repeated many times and the results are averaged. The same loops are run without the memory access to measure the time taken with loop overhead. The program subtracts the overhead time from the loop time so the results should show the time spent on memory access only.
The program prints three values for each test, labeled as size, stride, and read+write.
The size value refers to the size, in bytes, of the array you are testing with, not the size of the cache. (You'll have to figure out the cache size for yourself.)
The stride value says how many bytes are being skipped at each access. For example, if the stride is 4, bytes 0, 4, 8, 12, ... in the array are being accessed with bytes 1, 2, 3, 5, 6, 7, 9, 10, 11, ... being skipped.
The read+write value is the amount of time needed to make the access to memory, in nanoseconds. You'll have to figure out for yourself whether these times denote hits or misses. As explained above, the calculated times may be exaggerated if the compiler doesn't make equivalent machine code for the two loops that process the array.
The file ~cs61cl/code/nova.results lists the results of a run of a slightly modified cache.c on a computer named nova run by the EECS instructional computing staff in 2002. You are to determine answers to the following questions; place them in a file named cache_vm_infer.txt for submission, and submit the file to Expertiza as cache_vm_infer. Make sure to briefly justify all your claims. You may or may not wish to attempt to answer this list in order.
The K&R code is rather concise; an attempt to modify it might result in bugs due to the code's complexity. Moreover, the users of the storage management functions might have bugs in their own programs, for instance, accidentally freeing a section of memory twice, or overwriting an array. Some of these bugs will result in infinite loops or crashes. With others, the program will keep running, but its internal data structures may be damaged. In this exercise, you will think of ways that the free list of blocks can be damaged, and design a consistency-checking function to reveal them.
In pseudocode, design a C function named freeListIsOK that checks the consistency of the free list managed by the K&R storage management code. Your function should return true if the free list passes all your tests, and false otherwise. Your pseudocode should be written in detail specific enough for another CS 61CL student to immediately be able to translate it to C.
One example of something you would be unable to detect is a missing free block, that is, a block that's been freed that doesn't appear in the free list. Your freeListIsOK function should, however, check that entries in the list are correct, for instance, that the sizes of all blocks other than the first are at least 2, and that the size of the first block is 0. There are at least four other significantly different things to check for. A good place to start is to examine the consequences of overwriting part of a block, or passing an inappropriate argument to free.
Submit your pseudocode in a file named free_list_is_OK.txt, to Expertiza under the name free_list_is_OK.
Page tables require fairly large amounts of memory, as described in the Elaboration on page 500 (page 519 in the third edition) of P&H, even if most of the entries are invalid.
One solution is to use a hierarchy of page tables. The virtual page number, as described in Figure 5.20 on page 494 (Figure 7.20 on page 513 of the third edition), can be broken up into two pieces, a "page table number" and a "page table offset." The page table number can be used to index a first-level page table that provides a physical address for a second-level page table, assuming it resides in memory (if not, a first-level page fault will occur and the page table itself will need to be brought in from disk). The page table offset is used to index into the second-level page table to retrieve the physical page number.
One obvious way to arrange such a scheme is to have the second-level page tables occupy exactly one page of memory. Assuming a 32-bit virtual address space with 4 KB pages and 4 bytes per page table entry, how many bytes will each program need to use to store the first-level page table (which must always be in memory)?
Submit your answer with suitable explanation in a file named 2_level_page_table.txt to Expertiza under the name 2_level_page_table.