Andrew login ID Full Name Recitation Section CS 15 213 Spring 2008 Final Exam Tue May 6 2008 Instructions Make sure that your exam is not missing any sheets then write your full name Andrew login ID and recitation section A H on the front Write your answers in the space provided below the problem If you make a mess clearly indicate your final answer The exam has a maximum score of 72 points This exam is OPEN BOOK You may use any books or notes you like No calculators or other electronic devices are allowed Good luck 1 12 2 9 3 10 4 7 5 8 6 6 7 6 8 8 9 6 TOTAL 72 Page 1 of 19 Problem 1 12 points The following problem concerns virtual memory and the way virtual addresses are translated into physical addresses Below are the specifications of the system on which the translation occurs The system is a 16 bit machine words are 2 bytes Memory is byte addressable The maximum size of a virtual address space is 64KB The system is configured with 16KB of physical memory The page size is 64 bytes The system uses a two level page tables Tables at both levels are 64 bytes 1 page and entries in both tables are 2 bytes as shown below In this problem you are given parts of a memory dump of this system running 2 processes In each part of this question one of the processes will issue a single memory operation read or write of one byte to a single virtual address as indicated in each part Your job is to figure out which physical addresses are accessed by the process if any or determine if an error is encountered Entries in the first and second level tables have in their low order bits flags denoting various access permissions 15 Page Table Base Address Page Directory Entry Page Address Page Table Entry 2 1 0 P U W P P 1 Present W 1 Writable applies both in kernel and user mode U 1 User mode The contents of relevant sections of memory is shown on the next page All numbers are given in hexadecimal Page 2 of 19 Address 0118 0130 0160 018E 019C 01B8 120A 1214 1228 158A 1594 15A8 1A0A 1A14 1A28 2106 210C 2118 2286 228C 2298 2386 238C 2398 Contents 2381 2101 2281 1581 1201 1A01 2701 27C1 2741 25C1 2541 2501 2041 20C1 2081 3FC7 3A47 3587 3107 3447 3007 33C7 3887 3247 For the purposes of this problem omitted entries have contents 0 Page 3 of 19 Process 1 is a process in user mode e g executing part of main and has page directory base address 0x0100 Process 2 is a process in kernel mode e g executing a read system call and has page directory base address 0x0180 For each of the following memory accesses first calculate and fill in the address of the page directory entry and the page table entry Then if the lookup is successful give the physical address accessed Otherwise circle the reason for the failure and give the address of the table entry causing the failure You may use the 16 bit breakdown table if you wish but you are not required to fill it in 1 Process 1 writes to 0xC1B2 Scratch space 15 14 13 12 a Address of PDE 0x b Address of PTE 0x 11 10 9 8 7 6 5 4 3 2 1 0 c The result of the address translation is write NONE if the translation does not result in a valid address 0x d The result of the access is circle EXACTLY one success page not present page not writable illegal non supervisor access Page 4 of 19 2 Process 2 writes to 0x728F Scratch space 15 14 13 12 a Address of PDE 0x b Address of PTE 0x 11 10 9 8 7 6 5 4 3 2 1 0 c The result of the address translation is write NONE if the translation does not result in a valid address 0x d The result of the access is circle EXACTLY one success page not present page not writable illegal non supervisor access If it s there and you can see it it s real If it s not there and you can see it it s virtual If it s there and you can t see it it s transparent If it s not there and you can t see it you erased it IBM poster explaining virtual memory 1978 Page 5 of 19 Problem 2 9 points Consider a 12 bit IEEE floating point representation with 1 sign bit 4 exponent bits therefore the bias B 24 1 1 7 7 mantissa bits Fill in all the blanks in the following table In the process of converting some numbers to their bit representations you might have to round up or down If you do put the rounded value in the Rounded Value column If you didn t have to round put a line through that row s Rounded Value cell You should use round to even when rounding is needed Number Bit representation Rounded Value 0 1111 0000000 0 0000 0110000 0 1001 1111111 32 125 71 2048 255 25 Page 6 of 19 Problem 3 10 points Consider the following x86 64 assembly function called foo foo rdi t rsi v pushq r12 pushq rbp pushq rbx LCFI2 movq rdi rbx movq rsi r12 testq rdi rdi je L3 movl rsi ebp cmpl 24 rdi ebp jne L12 jmp L5 L7 cmpl ebp 24 rbx jne L12 L5 leal 1 rbp edx movq 16 rbx rax addl rax rdx 4 ebp movl ebp eax jmp L8 L12 movq r12 rsi movq rbx rdi call foo testl eax eax je L9 movl ebp eax jmp L8 L9 movq 8 rbx rbx testq rbx rbx jne L7 L3 movl 0 eax L8 popq rbx popq rbp popq r12 ret Page 7 of 19 Fill in the blanks of the corresponding C code The function used the data structure Node as defined below struct Node struct Node left struct Node right unsigned int value unsigned int index You may use only the C variable names that are defined not the register names int foo t unsigned int v if t return 0 if return return Page 8 of 19 Problem 4 7 points Consider the following C code and disassembly of function foo int main char src some string char dest 20 foo 44 src dest return 0 void foo int arg1 char arg2 char arg3 while arg2 arg3 arg2 arg1 0x00001fc5 0x00001fc6 0x00001fc8 0x00001fcb 0x00001fcd 0x00001fd0 0x00001fd3 0x00001fd6 0x00001fd8 0x00001fdb 0x00001fdd 0x00001fe0 0x00001fe2 0x00001fe5 0x00001fe7 0x00001fea 0x00001fed 0x00001fef 0x00001ff1 0x00001ff2 foo 0 push ebp foo 1 mov esp ebp foo 3 sub 0x8 esp foo 6 jmp 0x1fe7 foo 34 foo 8 mov 0xc ebp eax foo 11 movzbl eax edx foo 14 mov 0x8 ebp eax foo 17 add eax edx foo 19 mov 0x10 ebp eax foo 22 mov dl eax foo 24 lea 0xc ebp eax foo 27 incl …
View Full Document
Unlocking...