Description
Goal This assignment has two goals. The first is to explore the use of jump tables to implement switch statements. You will examine snippet B, read a mystery assembly file, and transform C code that uses switch statements into code that uses jump tables and gotos. The second goal is to examine asynchronous I/O programming. You are given a C file that models a simplified disk with an asynchronous read operation, simulated DMA, and interrupts. You are also given two programs that perform a sequence of disk reads in different ways. The first of these programs is completely implemented. It access the disk sequentially, waiting for each request to finish before moving on. The other programs is partly implemented, with the rest left to you. It improves on the sequential version using event-driven programming. You will gain some experience with this style of programming and then compare the runtime performance of the two alternatives. You’ll continue to with this example in Assignment 8, where you will implement a third alternative that uses threads. Groups You may do this assignment in groups of two if you like. If you do, be sure that you both contribute equally to the assignment and that you each work on every part of the assignment. Do not split up the assignment in such a way that one of you does one part and the other does another part. Keep in mind that the core benefit to you of doing the assignment is the learning that happens while you do it. Each assignment is worth only around 1.8% of your grade, but what you learn while doing the assignment goes a long way to determining the other 85%. If you choose to do the entire assignment with a partner, submit one solution via handin and list both of your names, student numbers, and computer-science login ids in the README file. Alternatively, you can also choose to collaborate with another student for a portion of the assignment and have your work marked individually. Do do this, simply submit your own version via handin and list the other student as a collaborator in your README file. Just don’t do this if you and your partner are turning in identical solutions, as we would like to realize marking efficiency where possible. You may have at most one collaborator for the assignment; i.e., you
can not collaborate with one student for one part of the assignment and another student for another part. Code Provided this Week The file www.ugrad.cs.ubc.ca/~cs213/cur/Assignments/a7/code.zip contains the following files that you will use with this assignment • SB-switch.{c,s} and SB_switch.java • A7-1.s • A7-2.c • max.s • test.s • Makefile • disk.{c,h}, queue.{c,h}, uthread.{ch}, and uthread_util.h • sRead.c and aRead.c Part 1: Switch Statements Part 1a: Snippet SB Examine the code for SB-switch. Carefully read the three different implementations in the C file. Run the assembly version in the simulator and observe what happens. Unlike previous assignments you are not required to document anything here. Doing this will help you with Parts 1b and 1c. You are not required to turn in anything for Part 1a. Part 1b: Reading Assembly Code The file A7-1.s contains uncommented assembly code that corresponds to a single C procedure starting at address 0x300 and another procedure that sets up the stack and calls the first procedure. Read this code and run it in the simulator. Comment every line and write an equivalent C program that is a likely candidate for the program the compiler used to generate this assembly file (with the exception of the stack-setup code, which is only for the .s file). Call this program A7-1.c. Note that A7-1.s uses the directive .address instead of .pos; they are equivalent. Part 1c: Implement Switch Statements with Jump Tables The file A7-2.c is a C implementation of CPU.java; i.e., it is a sm213 virtual machine. It has been setup to load and execute two assembly programs include in code.zip: max.s and test.s. It does this by loading the machine representation of the instructions since this program does not include an assembler. It is easy to get the translation from assembly to machine code from the Java simulator (its just to the left of the assembly code, line by line).
Take a look at this so you understand what is going on, but don’t worry about the details of the instructions. They are stored in A7-2.c as constants (i.e., loadMax() and loadTest()). The difference between max.s and test.s is that max does something interesting (it computes the maximum value of an array of integers) and test simply executes each instruction in the ISA once (in order of their op code). For max, the virtual machine prints the value stored in memory at address 0 after max finishes; this is the maximum value of the list that starts at address 4. Notice that it works. Modify the integer array in loadMax so that it computes a different maximum. Your task is to write an equivalent C program called A7-2-jumptable.c that replaces the two switch statements in exec() with gotos using a jump table and label pointers as shown in class. Note that label pointers are a gnu C extension and so some compilers may not support them (all versions of gcc and llvm (the Mac compiler) do support this extension). So, you may need to move to a lab computer to test this your program. Leave cases marked “NYI” empty; i.e., they are cases with an empty body so just implement them that way. To test your program it is sufficient to show either that it computes the correct value for max or that loadTest runs okay. Start with loadMax. If it works; you are done. If not, then switch to loadTest and change every case arm to include a print statement that prints the value of the case label (e.g., “case 2: printf (“2\n”); …”). This will simplify debugging greatly. Then if you show that you print the case labels in the correct order, you are done. Part 2: Asynchronous Programming Background The Simulated Disk The simulated disk is implemented in the file disk.c and its public interface is in disk.h. A disk contains a collection of disk blocks named by a block number. This disk simulates a fixed, per-access read latency of 10 ms (1 ms is 10-3 seconds), which is about the average access time of real disks. This means that it takes the disk 10 ms to process a single read request. However, the disk can process multiple requests in parallel. When it completes a request, it does what a real disk does, it uses a direct-memory transfer (DMA) to copy the disk data into main memory and it delivers an interrupt to the CPU. In this case, of course, the DMA is just a memory-tomemory copy between parts of your program’s memory. And the interrupt is delivered by calling a specified handling procedure you register when you initialize the disk. To initialize the disk using an interrupt handler called interruptServiceRoutine, you call the following procedure at the beginning of your program (all of the provided files already do this). disk_start (interruptServiceRoutine)
To request that the first nbytes of the content of the disk block numbered blockno be transferred into buf you call. disk_scheduleRead (buf, nbytes, blockno) This procedure returns immediately. Then 10ms later, the target data is copied into buf and an interrupted is delivered to you by calling interruptServiceRoutine. The disk completes reads in request order, and calls interruptServiceRoutine for each completion. Now, since the simulated disk doesn’t really store data, it does not transfer anything interesting into buf other than one thing. It write the integer blockno into the buffer so that you can test your code to be sure you have the right disk block. For example if you make the call char buf [100]; disk_scheduleRead (buf, 100, 37); And wait the 10ms for the interrupt, and then examine buf, you will see it unchanged except for the beginning, which will store the number 37. Thus the following expression evaluates to true. *((int*) buf) == 37 Note — and this is important — the interrupt operates just like a regular interrupt. It will interrupt your program at some arbitrary point to run the handler, continuing your program when the handler returns. There are some potentially difficult (and I mean horrible) issues that arise if your program and the handler access any data structures in common or if the handle calls any non-reentrant procedure (e.g., malloc or free). You are provided with the implementation of a reentrant, thread-safe queue that is safe to access from the handler and your program. It is also okay to access the target data buffer (buf) in the handler. Do not access any other data structures in the handler and do not call free from the handler (its okay to call dequeue). You will learn more about this issue in a couple of lectures, but it is not a concern for this assignment (other than to avoid the problem). The disk provides one addition operation that you can call to wait until all pending reads have completed. disk_waitForReads() The Queue The files queue.c and queue.h provide you with a thread-safe, re-entrant implementation of a queue. If you need to enqueue information in your program that is dequeued in the interrupt handler, use this queue. To create a queue named something like prq, for example, you declare the variable like this. queue_t prq; Then before you use the queue you need to initialize it, in main, for example like this. queue_init (&prq);
To add an item pointed to by the variable item (of any type) you do this: queue_enqueue (&prq, item); To get an item (e.g., of type struct Item*), you do this: struct Item* item = queue_dequeue (&prq); Makefiles The provided code contains a file called Makefile that describes how this week’s program should be built. In general, most C projects have a makefile like this. To compile the program sRead, for example, type the following at the command line: make sRead To compile every program just type this: make To remove executables, object files and other derived files type this: make clean Timing the Execution of a Program The UNIX command time can be prepended to any command to time its execution. When the command finishes you get a report of three times: the total elapsed clock time, the time spent in user-mode (i.e., your program code) and the time spent system-mode (i.e., the operating system). The format is otherwise a bit different on different platforms. For example if you type this: time ./sRead 100 You will get something like this on Mac OS when sRead completes: 1.074u 0.010s 0:01.08 100.0% 0+0k 0+0io 0pf+0w And on Linux: real 0m1.100s user 0m1.084s sys 0m0.000s Ignore the user (u) and sys (s) times; they really are approximations. Pay attention only to the real, elapsed time, which is 1.08 s in the Mac example and 1.1 s in the Linux example. You will use this command to assess and compare the runtime performance of the three alternative programs.
Part 2a: Synchronous Reads Examine the program sRead.c, compile it by typing make sRead and run it. You run it from the command line with one argument, the number of reads to perform. For example, to perform 100 reads, you type this: ./sRead 100 Temporarily modify handleRead to assert that the value at the beginning of buf is something other than blockno to confirm that this is really working. For example assert (*((int*) buf) == blockno-1) Now, restore the assert statement and temporarily add a printf statement to handleRead to print number at the beginning of every the buffer something this: printf (“buf = %d, blockno = %d\n”, *((int*) buf), blockno); Again, this is just to convince yourself that this works. Now, remove the printf. Finally, time the execution of the program for executions that read various numbers of blocks. For example time ./sRead 10 time ./sRead 100 time ./sRead 1000 Knowing how the simulated disk and this program perform you should be able to explain why you see the runtime performance you do. Do so, in README.txt; this is QUESTION 1. Part 2b: Asynchronous Reads Now open aRead.c in an editor and examine it carefully. This version of the read program each read should not wait for the disk to complete, as the synchronous version does. Instead, it should schedule each read in run and call handleRead for each of them when their interrupt is delivered. You will receive interrupts in the same order as calls to disk_scheduleRead. So, for example, if you schedule reads for blockno values of 0, 1, and 2, in that order, the first time interruptServiceRoutine runs it will be to tell you that the read for block 0 has completed. The second call will be for block 1 and so on. But note, that the interrupt is just an interrupt. It does not transmit any values; the interrupt service routine has no parameters. So, you will need to remember these somehow. Remember the queue? Compile and test your program the same way that you did for sRead. Measure the runtime performance of aRead for executions that read different numbers of disk blocks as you did with sRead and so that you can directly compare their performance. There is some experimental error and so you should run each case at least three times and take the minimum. The reason for taking the minimum is that this is the most reliable way to factor out
extraneous events that you see as noise in your numbers. Obviously, this is not a good way to determine the expected behaviour of the programs; its just a good way to compare them. Now you know more and have more data. Record the time values you observe for both aRead and sRead for a few different numbers of reads. Be sure to choose meaningful values for this parameter; e.g., at least a small one of around 10 and a large one of around 1000 (though if your system is too slow to run either of these for 1000, choose a smaller number). Explain what you observe: both what and why. The why part is important: carefully explain why one of these is faster than the other. Record your observations and data in README.txt. This is QUESTION 2. Requirements Here is a summary of the requirements for each part of this assignment. 1. Examine the execution of Snippet B. There is nothing to hand in for this step. 2. Add comments to A7-1.s and write A7-1.c. 3. Write A7-2-jumptable.c. 4. Run sRead as described in Part 2a and then measure its runtime performance. Answer QUESTION 1. 5. Complete the implementation of aRead.c. Run it as described in Part 2b and then measure its runtime performance. Answer QUESTION 2. What to Hand In Use the handin program. The assignment directory is a7. 1. A single file called “README.txt” that includes your name, student number, four- or fivedigit cs-department undergraduate id (e.g., the one that’s something like a0b1), and all written material required by the assignment as listed below. 2. If you had a partner for the entire assignment, turn in only one copy of your joint solution under one of your ids and list both student’s complete information in the README.txt file and include the text “PARTNER – MARK JOINTLY”. 3. If, on the other hand, you collaborated with another student for a portion of the assignment, but your solutions are not identical and you want them marked individually, each of you should include the other student’s complete information in your README.txt file, include the text “COLLABORATOR – MARK SEPARATELY”, and turn in copies separately via handin. 4. The files A7-1.s and A7-1.c. 5. The file A7-2-jumptable.c. 6. Your answer to QUESTION 1 in the README.txt file. 7. The file aRead.c. 8. Your answer to QUESTION 2 in the README.txt file.
