Andrew login ID:Full Name:Recitation Section:CS 15-213, Spring 2008Final ExamTue. May 6, 2008Instructions:• Make sure that your exam is not missing any sheets, then write your full name, Andrew login ID, andrecitation section (A–H) on the front.• Write your answers in the space provided below the problem. If you make a mess, clearly indicateyour 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 otherelectronic 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 19Problem 1. (12 points):The following problem concerns virtual memory and the way virtual addresses are translated into physicaladdresses. 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 inboth 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 partof this question, one of the processes will issue a single memory operation (read or write of one byte) toa single virtual address (as indicated in each part). Your job is to figure out which physical addresses areaccessed 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 permis-sions.15 2 1 0Page Table Base Address PPage Directory EntryPage Address U W PPage Table Entry• P = 1 ⇒ Present• W = 1 ⇒ Writable (applies both in kernel and user mode)• U = 1 ⇒ User-modeThe contents of relevant sections of memory is shown on the next page. All numbers are given in hexadec-imal.Page 2 of 19Address Contents0118 23810130 21010160 2281018E 1581019C 120101B8 1A01120A 27011214 27C11228 2741158A 25C11594 254115A8 25011A0A 20411A14 20C11A28 20812106 3FC7210C 3A472118 35872286 3107228C 34472298 30072386 33C7238C 38872398 3247For the purposes of this problem, omitted entries have contents = 0.Page 3 of 19Process 1 is a process in user mode (e.g. executing part of main()) and has page directory base address0x0100.Process 2 is a process in kernel mode (e.g. executing a read() system call) and has page directory baseaddress 0x0180.For each of the following memory accesses, first calculate and fill in the address of the page directory entryand 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 the16-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 11 10 9 8 7 6 5 4 3 2 1 0(a) Address of PDE: 0x(b) Address of PTE: 0x(c) The result of the address translation is (write NONE if the translation does not result in a validaddress):0x(d) The result of the access is (circle EXACTLY one):success / page not present / page not writable / illegal non-supervisor accessPage 4 of 192. Process 2 writes to 0x728F. Scratch space:15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0(a) Address of PDE: 0x(b) Address of PTE: 0x(c) The result of the address translation is (write NONE if the translation does not result in a validaddress):0x(d) The result of the access is (circle EXACTLY one):success / page not present / page not writable / illegal non-supervisor accessIf it’s there and you can see it - it’s real. If it’s not there and youcan see it - it’s virtual. If it’s there and you can’t see it - it’stransparent. If it’s not there and you can’t see it - you erased it!- IBM poster explaining virtual memory, 1978.Page 5 of 19Problem 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 bitsFill in all the blanks in the following table. In the process of converting some numbers to their bit repre-sentations, 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 Value32.125−712048−255.250 1111 0000000 ———-0 0000 0110000 ———-0 1001 1111111 ———-Page 6 of 19Problem 3. (10 points):Consider the following x86-64 assembly function, called foo.foo: # rdi = t, rsi = vpushq %r12pushq %rbppushq %rbx.LCFI2:movq %rdi, %rbxmovq %rsi, %r12testq %rdi, %rdije .L3movl (%rsi), %ebpcmpl 24(%rdi), %ebpjne .L12jmp .L5.L7:cmpl %ebp, 24(%rbx)jne .L12.L5:leal 1(%rbp), %edxmovq 16(%rbx), %raxaddl (%rax,%rdx,4), %ebpmovl %ebp, %eaxjmp .L8.L12:movq %r12, %rsimovq (%rbx), %rdicall footestl %eax, %eaxje .L9movl %ebp, %eaxjmp .L8.L9:movq 8(%rbx), %rbxtestq %rbx, %rbxjne .L7.L3:movl $0, %eax.L8:popq %rbxpopq %rbppopq %r12retPage 7 of 19Fill 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 19Problem 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 <foo+0>: push %ebp0x00001fc6 <foo+1>: mov %esp,%ebp0x00001fc8 <foo+3>: sub $0x8,%esp0x00001fcb <foo+6>: jmp 0x1fe7 <foo+34>0x00001fcd <foo+8>: mov 0xc(%ebp),%eax0x00001fd0 <foo+11>: movzbl (%eax),%edx0x00001fd3 <foo+14>: mov 0x8(%ebp),%eax0x00001fd6 <foo+17>: add %eax,%edx0x00001fd8 <foo+19>: mov 0x10(%ebp),%eax0x00001fdb <foo+22>: mov %dl,(%eax)0x00001fdd
View Full Document
Unlocking...