ECE7995-Fall-2007 Lab Exercise 3 (combined with Assignment 3)
(Deadline is 11:59pm of 12/7/07 (Friday)
In this lab exercise you will have an opportunity to evaluate and compare performance of existing Linux readahead policy and the prefetching policy we designed in Lab2.
(1) Metrics for Performance Evaluation
While the ultimate metric for evaluation of the prefetching efficacy is reduction of execution time of an I/O-intensive program, we cannot use the metric in the exercise. This is because we run our prefetch policy in the UML kernel and execute user benchmark programs on top of the UML kernel. As you know, the entire file system of the UML kernel, i.e. root_fs, is actually a normal file in the host Linux. Without the root privilege in the host Linux, it is cumbersome to evict the cached blocks of a file out of the physical memory (even though you can evict them out of your UML kernel.). If blocks to be prefetched have been cached in the memory, the real I/O time that can be saved by a prefetch policy cannot be accurately measured. Therefore, we use the following three metrics in the lab: number of block misses, number of mis-prefetched blocks, and number of prefetched but not yet requested blocks
1.1 Metric 1: Number of Block Misses
Because we purge a file out of the buffer cache of the UML kernel each time before we start I/O on the file, i.e., evict the file's blocks of the UML kernel, there are not any hits due to caching. However, prefetching can read a block into the buffer cache before it is actually requested by user programs. So when user programs do request the blocks, their accesses may be hits. The number of hits due to prefetching indicates the accuracy of a prefetching policy. In other words, number of block misses indicates the inability of a prfetching policy to predict a user's future requests.
1.2 Metric 2: Number of Mis-prefetched Blocks
Mis-prefetched blocks are the ones that have been prefetched by the kernel but will never be requested by users' programs. These blocks waste the I/O bandwidth and pollute the buffer cache. Number of mis-prefetched blocks indicates the precision of a prefetching policy.
1.3 Metric 3: Number of Prefetched but not yet Requested Blocks
The duration between the time when a block is prefetched and the time when it is actually requested by user programs indicates the space overhead of a prefetching policy. In other words, number of prefetched but not yet requested blocks represents the cache spaces that are needed to carry out the prefetching. We need to minimize the overhead to allow the caching policy to have more spaces at its disposal for a higher hit ratio.
(2) Implementation
First, we need to make sure that all blocks that are to be read from a file are not in the buffer cache of your UML Linux. For this purpose, we have this new sys-call in lab3-fall07.c:
asmlinkage int sys_lab_purge_file_pages(const char __user *path, int path_size).
It removes all the blocks that belong to the file whose name is pointed by 'path' and the length of the file name is 'path_size'. You need to call the sys-call each time you start to test a prefetching policy.
Second, we need a minor change to the 'sys_lab_my_ra_state' sys-call which is implemented in lab2-fall07.c. In the original implementation, the parameter “int *usr_actual” returns the number of blocks that are actually loaded into the UML kernel, possibly including both blocks that requested by user programs and those that are prefetched by the kernel. To distinguish hits by user and readaheads by the kernel in a simplified scenario where only one block is read in a user request, we return the original '*usr_actual' times '-1' if the user requested block is not included in the I/O, which actually indicates a hit by user.
Third, to test the impact of variation of parameters of our policy, specifically two watermarks, on its performance, we change the two constants (SELF_RA_MARK, EXPAND_RA_MARK) into two global variables (g_self_ra_mark, g_expand_ra_mark) and write a sys-call to set new values to the parameters as well as return their original values.
asmlinkage int sys_lab_set_watermarks(int *p_self_ra_mark, int *p_expand_ra_mark)
(3) Your tasks:
You are provided the following files, which you can copy from ‘/home/UML/Lab3-Fall-07’: (NOTE: you may want to backup your original files before you copy.)
(I) kernel files: 'lab2-fall07.c' and 'lab3-fall07.c', which should be copied into ‘./my-source’; 'readahead.c', which should be copied into ‘./mm’; ‘fs.h’, which should be copied to ‘./include/linux’; 'lab-fall07.h', which should be copied into './include/my-linux'.
(II) user-level files: ‘ra2.h’, ‘ra3.h’, ‘trace-my-ra.c’, and ‘read-my-file.c’. These files should be copied into ‘/home’ of your root_fs.
(3.1) Register sys-call 'sys_lab_purge_file_pages' into your kernel
(3.2) Implement sys-call in lab3-fall07.c.
asmlinkage int sys_lab_set_watermarks(int *p_self_ra_mark, int *p_expand_ra_mark)
Here are details you must take care of in your coding (Note that the following description doesn't represent the pseudo code of the implementation. You need to figure out your own control flow)
Ø If a parameter is NULL, do not change its corresponding watermark.
Ø If a parameter is not NULL, store the original value of its corresponding watermark into the address represented by the parameter.
Ø If the value pointed to by any parameter is larger than REGION_SIZE, do nothing and return 0. Otherwise, return 1;
Ø If the value pointed to by a parameter is between 1 and REGION_SIZE, inclusively, store the value to its corresponding watermark.
When you complete the sys-call, register it into your UML kernel.
These sys-calls are used in the user programs. Make sure their registered call numbers match the numbers that you use to call them.
(3.3) Write a user program named as 'purge.c', which accepts a file name and purge all its blocks out of the UML kernel.
(3.4) Write a user program named as 'set-watermarks.c', which accepts two integer numbers and store the numbers to 'g_self_ra_mark' and 'g_expand_ra_mark', respectively, using sys_lab_set_watermarks().
(3.5) Read and run program 'read-my-file.c'
This program can read, one block once, a file that is created by running “crteate-file.c' in four different read-modes: forward, backward, two streams, and random. In the forward mode, a file is read from its first block to the last block of the file, in that order. The backward mode is similar to the forward mode, except that file is read from the last block to the first. In the two-stream mode, reading is alternated between the first half and second half of a file, from the first block to the last one in each half. In the random mode, file blocks are randomly picked for reading and each block is accessed once and only once. For the first three modes, a stride size can be provided to define the offset distance between two successive reads (applicable to each half in the two-stream mode). Here is an example, for a file that contains 10 blocks (blocks are numbered from 1 to 10), the reference sequence for each mode is as follows:
forward:
(stride size = 1) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, (stride size = 2) 1, 3, 5, 7, 9
backward:
(stride size = 1) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 (stride size = 2) 9, 7, 5, 3, 1
two-streams:
(stride size = 1) 1, 6, 2, 7, 3, 8, 4, 9, 5, 10 (stride size = 2) 1, 6, 3, 8, 5, 10
random (a hypothetical sequence):
4, 8, 3, 1, 10, 6, 7, 2, 5, 9
The program also allows user to specify the readahead mode: either the policy used in the stock Linux kernel ('linux') or the policy we designed in lab2 ('mine'). When you run the program without providing a right number of parameters, it will print the command format:
[root@localhost home]# ./read-my-file
command format: ./read-my-file readahead-mode file_name read-mode [stride_size (N/A for mode 3)]
readahead-mode: 0 = linux, 1 = mine
read-mode: 0 = forward, 1 = backward, 2 = two streams, 3 = random
In the command, “stride_size” can be ignored by using its defalt value, which is 1.
The output of the program is of the format “[readahead-mode]- [read-mode]-[g_self_ra_mark (if 'my' readahead-mode) ]-[g_expand_ra_mark(if 'my' readahead-mode)]-[stride(stride_size) (if non-random read-mode)].cuv. As an example, “my-forward-4-16-stride1.cuv” is the output file by using 'read-my-file' to read a file as follows:
[root@localhost home]# ./read-my-file 1 f1.dat 0
(if you haven't set 'g_self_ra_mark' and 'g_expand_ra_mark' to 4 and 16, respectively, you need to run './set-watermarks 4 16.)
In the file, there are four columns: Column 1 is about number of blocks accessed by user program, Column 2 is number of misses, Column 3 is number of misses + number of hits (== number of accessed blocks), Column 4 is number of misses + number of prefetched blocks (== number of accessed blocks + number of prefetched-not-yet-accessed blocks).
For each output file, we can draw three curves in a graph, in which X axis is for number of accessed block, showing the numbers in Column 1, Y axis is for number of blocks. The first curve corresponds to Column 4 (# of missed + # of prefetched), the second curve corresponds to Column 3 (# of accessed blocks or number of hits + number of misses), and the third curve corresponds to Column 2 (# of misses). As an example, the following graph is drawn according to output file “my-forward-4-16-stride1.cuv”, and we name the graph as “my-forward-4-16-stride1”
The graph reveals interesting performance characteristics of a prefetching policy. We know the accuracy of a prefetching policy by looking at how close the third curve (Curve 3) is to the X axis, and we know roughly the precision of a prefetching policy by looking at how close the first curve (Curve 1) is to the second curve (Curve 2). Think why we have the claim.
Before you run 'read-my-file' to read a data file, you need to run 'create-file' to create the data file. You MUST create a file whose size (‘file_size_in_blocks') is larger than 500 blocks and the last two least significant digits of 'file_size_in_blocks' match the last two digits of your accessID, so that you put your fingerprint in your work. For example, if your accessID is ab1234, you can choose your file sizes such as 834, 1234, 2034, etc. You can use MS Excel or gnuplot to draw figures from the ‘*.cuv’ data files. All ‘*.cuv’ data files that are required in the following analysis work to draw graphs must be left their copies at directory /home/output-data in your UML kernel.
(3.6) Draw graphs and analyze performance using the aforementioned three metrics.
(I) Draw and compare graphs “linux-forward-stride1” and “linux-forward-stride2” and explain their differences;
(II) Draw and compare graphs “linux-backward-stride1” and “my-backward-4-16-stride1” and explain their differences;
(III) Draw and compare graphs “my-2streams-4-16-stride1” and “my-2streams-4-16-stride2” and explain their differences;
(IV) Draw and compare graphs “my-2streams-4-16-stride1” and “my-2streams-4-2-stride1” and explain their differences;
(V) Draw and compare graphs “my-rand-4-16” and “my-rand-4-2” and explain their differences.
To submit your work, send me an email before the deadline with subject as “Lab3 submission --- ECE7995-Fall-07”. Attach an MS Word file that describes the work required in Section 3.6. Please include all graphs in the Word file, rather than in separate attachments. Once you notify me that your work is ready to be graded, I’ll enter your directory, build your kernel, and run your user-level programs. Also, each student should be independently complete the work and individually submit his/her work.