Andrew login ID: Full Name:
15-213, Fall 2007 Final Exam
December 13, 2007, 1:00pm-4:00pm
• Make sure that your exam is not missing any sheets. Write your full name and Andrew login ID on the front.
Copyright By PowCoder代写 加微信 powcoder
• Write your answers in the space below each problem. If you make a mess, clearly indicate your final answer.
• The point value of each problem and the total possible is indicated below.
• The problems are of varying difficulty. Pile up the easy points quickly and then go back to the harder problems.
• This exam is OPEN BOOK. You may use any books or notes you like. Calculators are allowed, but no other electronic devices (including cell phones). Electronic communication is strictly forbidden. Good luck!
Do not write below this line
——————————-
Possible Points
Your Score
Page 1 of 18
Problem 1. (16 points):
Consider the following 8-bit floating point representations based on the IEEE-754 format.
• There is one sign bit.
• There are k = 3 exponent bits. The exponent bias is 3. • There are n = 4 fraction bits.
• There is one sign bit.
• There are k = 4 exponent bits. The exponent bias is 7. • There are n = 3 fraction bits.
The rules are like those in the IEEE standard (normalized, denormalized, representation, infinity, and NAN).
A. Let XA be the largest, finite, positive value that can be represented in Format A, and let XB be the largest, finite, positive value that can be represented in Format B.
(a) What is the encoding of XA in Format A? Express your answer as a sequence of 8 bits.
(b) Circle the correct relationship between XA and XB .
XA
B. Let YA be the largest, finite, negative value that can be represented in Format A, and let YB be the largest, finite, negative value that can be represented in Format B.
(a) What is the encoding of YB in Format B? Express your answer as a sequence of 8 bits.
(b) Circle the correct relationship between YA and YB . Remember that YA and YB are both negative. YA
Page 2 of 18
Please complete the table below as follows. For a given format in a given row, the bit representation and value fields should correspond exactly to each other. For Format B in the last four rows of the table (where neither the bit representation nor the value are specified for that format), you should indicate:
• the bit representation that is closest (including any rounding if necessary) to the value for Format A in that same row;
• the value that corresponds exactly to the bit representation that you enter for Format B (which may or may not be equal to the value for Format A in the same row).
If rounding is necessary, you should use the round to even scheme that is the default in the IEEE format. For the value fields, you can give the values either as fractions (e.g., 17 , 7 ), mixed numbers (e.g., 5 1 ) or as an integer times
apowerof2(e.g.,17×2−6 or7×2−1).
Bit Representation
Bit Representation
1 011 1010
1 0111 101
0 101 0011
1 000 1100
Page 3 of 18
Problem 2. (12 points):
Dr. Evil has returned! He has placed a binary bomb in this exam! Once again, Dr. Evil has made the disastrous mistake of leaving behind some of his source code. Can you save all of mankind (or at least your grade on this question), and tell us what this bomb does?
The C source code Dr. Evil forgot to erase:
/* bomb.c: Use new computer technology to blow up exams! — Dr. Evil */ #include
#include
extern long secret_unsolvable_puzzle_fn(long input);
void explode_bomb() {
printf(“You fail! Mwhahahahaha!!!\n”); exit(8);
int main(int argc,char *argv[]) { if(argc != 2) {
printf(“Usage: %s
explode_bomb();
if(secret_unsolvable_puzzle_fn(atol(argv[1])) == 0) explode_bomb();
printf(“Curses, foiled again! You get paid one MEEELLION DOLLARS!\n”);
return 0; }
The IA32 disassembly for the stuff Dr. Evil did erase:
secret_unsolvable_puzzle_fn:
80485d2: 00
pushl %ebp
movl %esp,%ebp
movl 0x8(%ebp),%eax
testl %eax,%eax
je 80485e7
leal (%eax,%eax,1),%edx
cmpl $21314,%edx
ja 80485df
addl %eax,%edx
cmpl $21314,%edx
jbe 80485d5
cmpl $21315,%edx
je 80485e9
xorl %eax,%eax
movl %ebp,%esp
popl %ebp
80485dc: 00
80485e4: 00
76 f6 81 fa
Page 4 of 18
A. Does the function secret_unsolvable_puzzle_fn() contain any of the following (circle either yes or no):
if statements: function calls: recursion:
yes no yes no yes no yes no
B. For each of the following input values, circle whether it defuses or explodes the bomb:
input = 0: input = 1: input = 7105: input = 10657:
defuses defuses defuses defuses
explodes explodes explodes explodes
Page 5 of 18
Problem 3. (9 points):
This problem will test your understanding of the memory layout of C structures and unions in IA-32/Windows assembly code. (Recall that in Windows, 8 byte primitive data types must be aligned upon 8-byte boundaries.) Consider the data structure declarations below. (Note that this is a single declaration which includes several data structures; they are shown horizontally to fit on the page.)
struct s1 { struct s2 a; struct s2 *b; struct s1 *c; double d; int e[5];
struct s2 { char i[7]; union u1 *j; int k;
union u1 { int f;
struct s1 g;
struct s2 *h; };
For each of these four C procedures, fill in the missing offsets in the corresponding IA-32 assembly code immediately below it. (If you give the wrong answer below but write the correct sizes next to the structures above, you might get some partial credit.)
pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%eax movl (%eax),%eax movl %ebp,%esp
int proc1(struct s1 *x) { return x->e[3];
pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%eax movl (%eax),%eax movl (%eax),%eax movl %ebp,%esp
int proc2(struct s2 *x) { return x->j->g.e[1];
pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%eax movl (%eax),%eax movl (%eax),%eax movl (%eax),%eax movl %ebp,%esp
int proc3(union u1 *x) { return x->g.c->b->k;
pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%eax movl (%eax),%eax movl (%eax),%eax movl (%eax),%eax movl %ebp,%esp
int proc4(union u1 *x) { return x->h->j->f;
Page 6 of 18
Problem 4. (9 points):
Consider the C code below:
int fdplay() { int pid;
int fd1, fd2;
fd1 = open(“/file1”, O_RDWR); dup2(fd1, 1);
printf(“A”);
if ((pid = fork()) == 0) {
printf(“B”);
fd2 = open(“/file1”, O_RDWR); dup2(fd2, 1);
printf(“C”);
/* POINT X */
waitpid(pid, NULL, 0); printf(“D”); close(fd1); printf(“E”);
exit(2); }
A. How many processes share the open file structure referred to by fd1 at “POINT X” in the code?
B. How many file descriptors (total among all processes) share the open file structure referred to by fd1 at “POINT X” in the code?
C. Assuming that /file1 was empty before running this code, what are its contents after the execution is complete?
Page 7 of 18
Problem 5. (12 points):
3M decides to make Post-Its by printing yellow squares on white pieces of paper. As part of the printing process, they need to set the CMYK (cyan, magenta, yellow, black) value for every point in the square. 3M hires you to determine the efficiency of the following algorithms on a machine with a 2048-byte direct-mapped data cache with 32 byte blocks.
You are given the following definitions:
struct point_color { int c;
struct point_color square[16][16]; register int i, j;
• sizeof(int) = 4
• square begins at memory address 0
• The cache is initially empty.
• The only memory accesses are to the entries of the array square. Variables i and j are stored in registers.
A. What percentage of the writes in the following code will miss in the cache?
for (i=0; i<16; i++){
for (j=0; j<16; j++) {
square[i][j].c = 0; square[i][j].m = 0; square[i][j].y = 1; square[i][j].k = 0;
Miss rate for writes to square: _______ %
Page 8 of 18
B. What percentage of the writes in the following code will miss in the cache?
for (i=0; i<16; i++){
for (j=0; j<16; j++) {
square[j][i].c = 0; square[j][i].m = 0; square[j][i].y = 1; square[j][i].k = 0;
Miss rate for writes to square: _______ %
C. What percentage of the writes in the following code will miss in the cache?
for (i=0; i<16; i++){
for (j=0; j<16; j++) {
square[i][j].y = 1; }
for (i=0; i<16; i++) {
for (j=0; j<16; j++) { square[i][j].c = 0; square[i][j].m = 0; square[i][j].k = 0;
Miss rate for writes to square: _______ %
Page 9 of 18
Problem 6. (12 points):
This question focuses on the two-level page table structure that IA-32/Linux machines use to translate virtual to physical addresses. The layout of a Page Directory Entry (PDE) and a Page Table Entry (PTE) is shown below on the left, and the contents of physical memory for this problem is shown below on the right:
31 12 11 2 1 0
Physical Base Address (bits 31-12): the 20 most significant bits of either the physical PTE address (if this is a PDE), or the physical page address (if this is a PTE). (Note that this forces both page tables and pages to be 4KB aligned.) Note that if this is a PDE, this address represents where the PTE starts; if it is a PTE, then it represents where the physical page being accessed starts.
Ignore (bits 11-2): not pertinent to this problem.
R/W (bit 1): 0 indicates that we have read-only permission for either the PTE or the page, and 1 indicates that we have permission both to read and write.
P (bit 0): indicates whether the PTE (if this is a PDE) or the page (if this is a PTE) is in physical memory; 1 means that it is in memory; 0 means that it is not.
Assume the following:
• The page size is 4KB.
Physical Memory Contents
Physical Address
Data Value
0x000C8000
0x20000025
0x000C8004
0x08000025
0x000C8008
0x00100025
0x000C800c
0x20000001
0x00100000
0xAD34A645
0x00100004
0x12480007
0x00100008
0x001C0A05
0x0010000C
0x8BEEF407
0x00100010
0xBF072627
0x08000000
0x0002C003
0x08000004
0x01000C25
0x08000008
0x0FA00027
0x0800000C
0x824AF667
0x20000000
0x024C8C05
0x20000004
0x0A4F3407
0x20000008
0x023FD225
0x2000000C
0x198AAE27
Physical Base Address
• All memory accesses are to 4-byte words (using byte addresses, as always).
• The first level of the page table begins at physical address 0x000C8000 (i.e. this is the value of the “PDBR” register in the Pentium III processor).
For the memory accesses on the next page, your mission is to answer the following two questions:
1. Does the access complete normally, or does it result in a fault? Note that there are multiple reasons why an access may result in a fault. If you believe that a fault occurs, explain why.
2. What is the final 4-byte physical address that is accessed in the course of performing this access? If the access completes normally, then this will simply be the physical address upon which the memory operation is performed. If there is a fault, however, then this address will be a 4-byte word within the page table (note that it may be either a PDE or a PTE).
To avoid excessive page turning, the addresses on the next page are:
0x00803CDC (write), 0x00000320 (read), 0x00802127 (write), and 0x00401478 (read).
Page 10 of 18
A. Write to virtual address 0x00803CDC. Final physical address accessed:
Does a fault occur? (yes or no):
If yes, explain why:
B. Read from virtual address 0x00000320. Final physical address accessed:
Does a fault occur? (yes or no):
If yes, explain why:
C. Write to virtual address 0x00802127. Final physical address accessed:
Does a fault occur? (yes or no):
If yes, explain why:
D. Read from virtual address 0x00401478. Final physical address accessed:
Does a fault occur? (yes or no):
If yes, explain why:
Page 11 of 18
Problem 7. (20 points):
In each of the following questions, one or more of the possible answers is correct. Clearly indicate all of the correct answers by writing their letter(s) in the blank at the end of each question.
A. Which of the following x86 instructions can be used to add two registers and store the result without overwrit- ing either of the original values?
(d) None of above
Correct answer(s):
B. The register rax is currently storing a NULL pointer. Which of the following x86 instructions will cause a segmentation fault because of an invalid memory access?
(a) mov (%rax), %rcx (b) lea (%rax), %rcx (c) None of the above
Correct answer(s):
C. In buflab, a buffer was allocated on the stack. When the user ran the program and typed something in, it was written into the buffer. If the user entered more characters than the buffer could fit, they could overwrite additional values on the stack. Which of the following regions of the stack could they directly overwrite in this manner?
(a) The part of the stack with higher (i.e. larger) addresses than the buffer (b) The part of the stack with lower (i.e. smaller) addresses than the buffer
Correct answer(s):
D. A function declares a local variable named my int of type int. Which of the following (if any) is/are dangerous in C?
(a) Returning&myint
(b) Setting the value of a global variable to &my int (c) Printingtheaddress&myinttothescreen
(d) None of the above
Correct answer(s):
Page 12 of 18
E. Aprogrammerwishestocomparethecontentsofastringcalledmystrtothestring“GET”.Heorshewrites the following C code:
if (my_str == "GET") ...
Which of the following apply?
(a) my str is a pointer to the first character of a string in memory
(b) my str is the ASCII value of the first character of a string in memory (c) my str is a register containing all of the characters in the string
(d) “GET” will compile to a pointer to a string in memory
(e) “GET” will compile to the ASCII value for the letter ”G”
(f) “GET” will compile to a register containing the string “GET” represented as an integer (g) The comparison will always work as expected
(h) The comparison will not necessarily work as expected
(i) The comparison itself will cause the program to crash Correct answer(s):
F. The function foo() is declared in a C program as follows: void foo(int int_param, char *str_param);
A programmer calls foo() from within the function bar() as follows: foo(my_int, my_string);
Which of the following is/are true:
(a) If foo() changes the value of int param, the change will propagate back to the calling function
bar(), in other words, the value of my int will also change.
(b) If foo() changes the second character of str param, the change will propagate back to the calling
function bar(), in other words, the second character of my string will also change.
(c) If foo() changes the address of str param to point to a different string, the change will propagate
back to the calling function bar(), in other words, my string will now point to a different string.
(d) None of the above.
Correct answer(s):
Page 13 of 18
G. A programmer has declared an array in a C program as follows:
int my_array[100];
Which of the following give(s) the address of the eighth element in the array (bearing in mind that the first element in the array is at index zero):
(a) my array[7] (b) &my array[7] (c) my array + 7 (d) my array + 28 (e) None of the above
Correct answer(s):
H. A programmer has stored an 8-bit value in memory. The pointer:
char *ptr;
points to the location where it is stored. He or she now wants to retrieve the value and store it into the variable:
int value;
Which of the following (if any) will achieve this properly?
(a) value = ptr;
(b) value = *ptr;
(c) value = (int)ptr;
(d) value = (int *)ptr; (e) value = *(int *)ptr;
(f) None of the above Correct answer(s):
I. In malloclab, we provided code for an implicit list allocator. Many students improved this code by creating a linked list of free blocks. Why did this increase the performance of the allocator?
(a) Traversing a linked list is significantly faster than moving from block to block in the implicit list.
(b) The implicit list had to include every block in memory, but the linked list could just include the free blocks.
(c) The compiler knows how to optimize the code for a linked list by unrolling loops, but wasn’t able to do this for the implicit list.
(d) Having a linked list made coalescing significantly faster.
(e) None of the above.
Correct answer(s):
Page 14 of 18
J. A multithreaded program has two global data structures that will be shared among the threads. The data structures are not necessarily accessed at the same time. Which of the following is/are true (if any)?
(a) If the program has only one semaphore, and threads call P on that single semaphore before using either of the data structures, the code will not work correctly.
(b) Having one semaphore will work, but having two, one per shared data structure, may allow for increased performance.
(c) If the machine has only one processor, only one of the threads can run at a time, so semaphores are not necessary in that case.
(d) None of the above.
Correct answer(s):
Page 15 of 18
Problem 8. (12 points):
Consider the C code below:
void handler (int sig) { printf("s");
exit(7); }
int forker(int x) { int pid, status;
signal(SIGINT, handler); printf("A");
if (x > 0) {
pid = fork();
printf(“B”);
if (pid == 0) {
printf(“C”);
kill(pid, SIGINT);
waitpid(pid, &status, 0); printf(“%d”, WEXITSTATUS(status));
printf(“E”);
exit(4); }
Consider each of the following outputs and circle the ones that could be produced by the code above (after all processes are terminated).
Page 16 of 18
Problem 9. (12 points):
Consider the following three threads and four semaphores:
/* Initialize x */ x = 1;
/* Initialize semaphores */ s1 =
void thread1() void thread2() void thread3() {{{
while (x != 360) { while (x != 360) { while (x != 360) {
x = x * 2; x = x * 3;
x = x * 5;
exit(0); exit(0); exit(0); }}}
Provide initial values for the four semaphores and add P(), V() semaphore operations (using the four semaphores) in the code for thread 1, 2 and 3 such that the process is guaranteed to terminate.
Page 17 of 18
Problem 10. (13 points):
A. Assume that we want to transmit over the network the contents of a structure of the following type. Circle the structure elements that must be put in network byte order to guarantee that the recipient can interpret what it receives correctly.
struct data { int foo;
char name[16];
short bar; };
B. Consider the following segment of network code:
fd = socket (AF_INET, SOCK_STREAM, 0)
connect (fd, &serveraddr, sizeof(serveraddr)); write (fd, data, N);
read (fd, buf, N);
(a) Assume that the socket(), connect(), and write() calls return success. Is the read() call guaranteed to return quickly?
(b) When the read() call returns, how many bytes of buf will have been modified? Indicate either a value or a precise range of values (e.g., “between X and Y ”). (
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com