CPSC 213, Winter 2013, Term 2 ¡ª Final Exam Solution
Date: April 14, 2014; Instructor: Mike Feeley
1 (5 marks) Variables and Memory. Consider the following C code with three global variables, a, b, and c, that
are stored at addresses 0x1000, 0x2000, 0x3000, respectively.
void foo() { a[0] = 1; b[0] = 2;
int a[1];
int b[1];
int* c;
c = a;
c[0] = 3;
c = b;
*c = 4;
}
Describe what you know about the content of memory following the execution of foo() on a 32-bit Big Endian processor. List only memory locations whose address and value you know. List each byte of memory separately using theform¡°byte_address: byte_value¡±.Listallnumbersinhex.
0x1000: 0
0x1001: 0
0x1002: 0
0x1003: 3
0x2000: 0
0x2001: 0
0x2002: 0
0x2003: 4
0x3000: 0
0x3001: 2
0x3002: 0
0x3003: 0
2 (8 marks) Global Variables. Consider the following C declaration of global variables.
int a;
int *b;
int c[10];
Recalling that & is the C get address operator, which of the following can be computed statically? Justify your answers. 2a &b
Yes; address of global variables is static.
2b &b[4]
No; address of element of dynamic array is dynamic.
2c &c[4]
Yes; address of element of static array using static index is static.
Now answer this question.
2f Givetheassemblycodethecompilerwouldgeneratefor¡°c[a] = *b;¡±.Uselabelsforstaticvalues.
ld $b, r0
ld (r0), r0
ld (r0), r0
ld $c r1
ld $a, r2
ld (r2), r2 str0,(r1,r2,4)
# r0 = &b
# r0 = b
# r0 = *b
# r1 = &c[0] = c
# r2 = &a
# r2 = a #c[a]=*b
3 (8 marks) Instance Variables and Local Variables. Consider the following C declaration of global variables.
struct X { int a; int b;
};
struct X c; struct X* d;
Which of the following can be computed statically? Justify your answers.
3a &c.a
Yes; address of element of static struct variable is static.
3b &d->a
No; address of element of dynamic struct variable is dynamic.
3c (&d->a) – (&d->b)
Yes; the difference between the address of two element of the same struct is static.
Now answer this question.
3d Givetheassemblycodethecompilerwouldgeneratefor¡°d->b = c.b;¡±.
4 (10 marks) Write Assembly Code. Give the assembly code the compiler would generate to implement the following C procedure, assuming that arguments are passed on the stack. Just this procedure. Use labels for static values. Comment every line of your code.
int computeSum (int* a) { int sum=0;
while (*a>0) {
sum = add (sum, *a); a++;
}
return sum;
}
ld $c, r0 # r0 = &c.a
ld 4(r0), r0 # r0 = c.b
ld $d, r1 # r1 = &d
ld (r1), r1 # r1 = d
st r0, r(r1) # d->b = c.b
2
computeSum: deca r5 # allocate callee portion of stack frame
deca r5
st ld ld
L0: ld bgt
br
L1: deca r5
deca r5
st r0, (r5)
st r2, 4(r5) # save *a¡¯ on stack as argument 1
r6, 4(r5) # save return address on stack
$0, r0 8(r5), r1 (r1), r2 r2,L1
# r0 = sum¡¯ = 0
# r1 = a
# r2 = *a¡¯
#gotoL1if*a¡¯>0
# goto L2 if *a¡¯ <= 0
# allocate caller portion of add¡¯s stack frame
L2
# save sum on stack as argument 0
gpc $6, r6
j add
inca r5
inca r5
inca r1
br L0
L2: ld 4(r5), r6 # restore return address from stack
inca r5 # deallocate callee portion of stack frame
inca r5
j (r6) # goto return address (return from call)
# r6 = return address
# sum = add (sum, *a¡¯)
# deallocate caller portion of add¡¯s stack frame
# a¡¯++
# goto L1
5 (12 marks) Read Assembly Code. Consider the following SM213 code.
X: deca r5
deca r5
st r6, 4(r5)
ld $0, r1
st r1, 0(r5)
ld 12(r5), r2
ld 16(r5), r3
not r3
inc r3
# allocate callee portion of stack frame #
# save return address on stack
# r1=0=i¡¯
# s=0
# r2=a
# r3=n
#
# r3=-n
# r4=i¡¯
# r4=i¡¯ -n
beq r4, L2
bgt r4, L2
ld (r2,r1,4), r4 # r4 = a[i¡¯]
L0: mov
add r3, r4
deca r5
st r4, 0(r5)
gpc $2, r6
j *12(r5)
inca r5
ld $1, r4
and r0, r4
beq r4, L1
ld 0(r5), r4
add r0, r4
st r4, 0(r5)
L1: inc r1
br L0
L2: ld 0(r5), r0
ld 4(r5), r6
inca r5
inca r5
j (r6)
# allocate caller portion of stack frame for call
# save a[i¡¯] on stack as first argument
# compute return address
# r¡¯ = f(a[i¡¯])
# deallocate caller portion of call¡¯s stack frame #r4=1
# r4=r¡¯ &1
# goto L1 ifr¡¯&1==0
# r4=s
# s¡¯+=+ r¡¯
# s=s+ r
# i++
# goto L0
# r0=s
# return return address from stack
# deallocate callee portion of stack frame #
# return s
r1, r4
# goto L2
# goto L2
if i¡¯==n if i¡¯>n
5a Add a comment to every line of code. Where possible use variables names and C pseudo code in your comments to clarify the connection between the assembly code and corresponding C statements.
3
5b GiveanequivalentCprocedure(i.e.,aprocedurethatmayhavecompiledtothisassemblycode).
int p (int (*f)(int), int* a, int n) { int s = 0;
for (int i = 0; i < n; i++) { int r = f (a [i]);
if (r & 1)
} }
s += r;
return s;
6 (3 marks) Programming in C. Consider the following C code. int* b;
void set (int i) { b [i] = i;
}
Is there a bug in this code? If so, carefully describe what it is.
Yes; this code does not provide the caller with a way to ensure that the procedure does not overflow the array b. The proceduresetshouldhaveanadditionalparameternandtheassignment¡°b [i] = i¡±shouldbepredicatedbythe ifstatement¡°if (i < n¡±
7 (6 marks)
Programming in C. Consider the following C code.
int* one () { int loc = 1;
return &loc;
}}
void two () { int zot = 2;
}
7a Isthereabuginthiscode?Ifso,carefullydescribewhatitis.
7b Whatisthevalueof¡°*ret¡±attheendofthree?Explaincarefully.
2, because the local variable zot will occupy the same memory location as the local variable loc did.
8 (12 marks) Static and Dynamic Procedure Calls.
8a ProcedurecallsinCarenormallystatic.MethodinvocationsinJavaarenormallydynamic.Carefullyexplain
the reason why Java uses dynamic method invocation and what benefit this provides to Java programs.
8b CarefullyexplainanimportantdisadvantageofdynamicinvocationinJavaorotherlanguages.
8c DemonstratetheuseoffunctionpointersinCbywritingaprocedurecalledcomputethat:
1. has three arguments: a non-empty array of integers, the size of the array, and a function pointer;
void three () {
int* ret = one(); two();
Yes; one returns the address of a local variable and three saves it in the variable ret and thus ret is a dangling pointer. Luckily the code does not dereference this dandling pointer and so the code would execute okay. But adding a statement of the form *ret to three would be a serious problem.
Polymorphism requires the use of dynamic method invocation. Java, like other object-oriented programming languages, provide polymorphism as a way to allow code to be parameterized by the procedures it calls, not just the data it operates on. For example, the statement ¡°a.foo()¡± calls the version of foo that is implemented by a¡¯s actual type, which is determined dynamically.
Its slower, because the procedure call requires an additional memory access, to read the target address of the dynamic jump from memory (e.g., from the jump table).
4
2. computes either the array min or max depending only on the value of the function pointer argument; 3. contains a for loop, no if statements, and one procedure call (per loop).
Give the C code for compute, the two procedures that it uses (i.e., that are passed to it as the value of the function-pointer argument), and two calls to compute, one that computes min and the other that computes max (be sure to indicate which is which).
int compute (int* a, int n, int (*f)(int,int)) { int s = a[0];
for (int i=1; i
}
int min (int a, int b) { return a
c = c – 1;
success = 1;
}
spinlock_unlock (s);
} }
void inc() { spinlock_lock (s);
c = c + 1; spinlock_unlock (s);
}
mutex_t mx;
cond_t notZero;
void dec() { lock (mx);
while (c == 0)
wait (notZero)
c–;
unlock (mx);
}
void inc() { lock (mx);
c++;
signal (notZero);
unlock (mx);
}
Re-implement the program to eliminate all busy waiting using monitors and condition variables. You may make the changes in place above or re-write some or all of the code below.
12c Assumethatmonitorsareimplementedinsuchawaythatathreadinsideofamonitorispermittedtore-enter that monitor repeatedly without blocking (e.g., when bar calls zot, which calls foo, foo is permitted to enter monitor x). Indicate whether the following procedures could cause deadlock in multi-threaded program that contained them (and other procedures as well). Explain why or why not. If they could, say whether you could eliminate this deadlock by only adding additional monitors or additional monitor enter or exits (you may not remove monitors). If so, show how.
void foo () { monitor_enter (x); monitor_exit (x);
}
void bar () {
monitor_enter (x);
zot ();
monitor_exit (x);
}
void zot () {
monitor_enter (y);
foo ();
monitor_exit (y);
}
7
Yes it can deadlock, because if, for example, one thread calls bar and another calls zot, the first thread could be holding x while waiting for y and the other could be holding y while waiting for x, and thus the threads would be deadlocked. You can fix this by ensuring that threads always acquire locks in the same order. For example, to ensure that lock x is always acquired before lock y, add monitor_enter(x) to the beginning of zot and monitor_exit(x) to the end.
Note that in this version of the course the term monitor enter and monitor exit where used in place of lock and unlock.
8