15-213, Spring 2008
Final Exam Solutions

Q1.
1.
(a) 0x0x0130
(b) 0x210C
(c) 0x3A72 
(d) (Success)

2.
(a) 0x019C 
(b) 0x1214 
(c) 0x27CF
(d) Page not writable


Q2.

0 1100 0000000 : 32
1 0010 0001110 : ------
1 1110 1111111 : -255
+inf
3/512
255/32

Q3.

int foo(struct Node* t, unsigned int* v) {
  if(t == NULL)  return 0;
  if(*v == t->index) {
    return (*v + (t -> value[(*v) +1]));
  }
  return (foo(t->left, v)? *v : foo(t->right, v));
}

Q4.

src: 0x1ff3   
dest: 0xbffff918
arg1: 0xbffff900
arg2: 0xbffff904
arg3: 0xbffff908
return addres: ADDRESS is BFFFF8FC, VALUE (partial credit) is 0xb1fba
old ebp: ADDRESS is BFFFF8F8, VALUE (partial credit) is 0xbffff938

Q5.

A = 5
B = 9
uni = 5208

Q6.

(a)
  (16*1024 byte/cache) * (1 line / 64 byte) = 256 line/cache
  (256 line/cache)*(1 set/4 line) = [64 set/cache]
(b)
  We never read anything twice, so cache size doesn't matter
  Cache can handle 4 "streams", we have only 2 streams
  Doubles are 8 bytes
  Lines are 64 bytes
  So each stream misses 1 time in 8
  So miss rate is 1/8 or 12.5%
(c)
  We never read anything twice, so cache size doesn't matter
  Cache can handle 4 "streams", we have only 1 stream
  Doubles are 8 bytes
  Lines are 64 bytes
  So the stream misses 1 time in 16
  So miss rate is 1/16 or 6.25%

Q7.
 1 = u
2 = s
 3 = r
 4 = u
 5 = c
 6 = e

Q8.

correct: C, D, E, and G

Q9.

(1) yes, if the 2nd thread gets the lock first, it kills itself while holding the lock.
(2) yes, classic deadlock from acquiring locks in different order