Andrew login ID Full Name CS 15 213 Spring 2003 MAKEUP Final Exam May 7 2003 Instructions Make sure that your exam has 25 pages and is not missing any sheets then write your full name and Andrew login ID 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 114 points The problems are of varying difficulty The point value of each problem is indicated Pile up the easy points quickly and then come back to the harder problems This exam is OPEN BOOK You may use any books or notes you like You may not use a calculator laptop or any other electronic or wireless device Good luck 1 9 2 11 3 10 4 5 5 12 6 8 7 25 8 12 9 15 10 4 11 6 12 9 TOTAL 114 1 of 25 Problem 1 9 points Assume we are running code on an 8 bit machine using two s complement arithmetic for signed integers Short integers are encoded using 4 bits Sign extension is performed whenever a short is cast to an int For this problem assume that all shift operations are arithmetic All constants are ints Fill in the empty boxes in the table below int i 6 unsigned ui i short s 7 unsigned short us s Note TMax denotes the largest positive two s complement int and TMin denotes the minimum negative two s complement int Please use only hex notation i e not binary for Hex Representation Expression Decimal Representation 27 27 16 16 i i 2 ui int s int 6 s int us TMax TMin 2 of 25 Hex Representation Problem 2 11 points Consider the following 7 bit floating point representation based on the IEEE floating point format There is a sign bit in the most significant bit The next 3 bits encode the exponent The exponent bias is 3 The last 3 bits encode the significand The representation encodes numbers of the form V 1 s M 2E where M is the significand and E the integer value of the exponent The rounding mode is round to even Please fill in the table below You do not have to fill in boxes with in them If a number is NAN or infinity you may disregard the M E and V fields below However fill the Description and Binary fields with valid data Here are some guidelines for each field Description A verbal description if the number has a special meaning Binary Binary representation of the number M Significand same as the M in the formula above E Exponent same as the E in 2E V Fractional Value represented Please fill the M E and V fields below with rational numbers fractions rather than decimals or binary decimals Description Binary 0 101 010 1 7 8 1 111 111 1 5 8 1 Farthest from zero Negative Normalized Closest to zero Negative Denormalized 3 of 25 M E V Problem 3 10 points This problem tests your understanding of assembly code control flow and multidimensional array layout Consider the following assembly code for a procedure loopy loopy pushl movl pushl pushl movl movl movl cmpl jge movl L35 leal addl imull incl cmpl jl L33 movl popl popl popl ret ebp esp ebp esi ebx 8 ebp ebx 1 edx 0 ecx ebx ecx L33 arr esi 0 ecx 8 eax ecx eax esi eax 4 edx ecx ebx ecx L35 edx eax ebx esi ebp A For each register listed indicate which C variable s from the C source on the next page i tmp arr n it can hold during the lifetime of the function If the register is not used to hold a variable on the next page then write in none Note that there is not necessarily a one to one correspondence between variables and registers eax ebx ecx edx esi edi ebp 4 of 25 Continued Question 3 cont d B Based on the assembly code fill in the blanks below in loopy s C source code Note you may only use symbolic variables from the source code in your expressions below Do not use register names int arr 5 int loopy int n int i int tmp for i 0 tmp arr 0 return 5 of 25 Problem 4 5 points Consider the following C declarations typedef struct union char d short s u char c double dptr char buf 2 final Using the templates below allowing a maximum of 24 bytes indicate the allocation of data for structs of type final Mark off and label the areas for each individual element arrays and unions may be labeled as a single element Cross hatch the parts that are allocated but not used and be sure to clearly indicate the end of the structure Assume the Linux alignment rules discussed in class final 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 What would the following program print out int main printf d n sizeof final Output 6 of 25 Problem 5 12 points In this problem we will compare the best case and worst case scenarios for a memory access in a virtual memory subsystem You will want to pay careful attention to the following information about the available features of the subsystem No hardware caches besides a Translation Lookaside Buffer are present The system uses a 3 Level Page Table The page directory 1st level page table address is stored as a physical address in a special register on the processor The page directory is always in main memory All page tables store physical addresses The Translation Lookaside Buffer TLB takes 1ns to query An access to main memory given a physical address costs 20ns A page fault costs 6ms After a page fault the page s address translation is inserted into the TLB Assume that the processor restarts the address translation after a page fault 1 What is the best case data lookup time NOTE This is the time that elapses between when the processor presents a virtual address to the memory subsystem and when the word at that address has been loaded stored to from a register Answer ms ns 2 If the second level page table is in main memory what is the worst case data lookup time Assume no individual page faults more than once for example other processes will not interfere with the memory access Answer ms ns 7 of 25 Problem 6 8 points The following problem deals with memory allocation schemes You have seen several ways to manage heap blocks This problem deals with the buddy allocation scheme In the buddy scheme the heap starts out as one large free block During allocation blocks are split in half until a minimum sized block that can satisfy the request is created Each pair created by a split are called buddies A free block can only be coalesced with its buddy For this problem you may ignore block headers …
View Full Document
Unlocking...