Eroxl's NotesGraph
Practice Final Exam 1 - CPSC 213

Problem 1

Address Value
0x100 0x78
0x101 0x56
0x102 0x34
0x103 0x12

(a). What Integer Value is Stored at Address 0x100 if the Machine is

(i) Little Endian?

0x12345678

(ii) Big Endian?

0x78563412

(b). Evaluate the following Java Code. Give y and z in Hexadecimal and Explain why They Differ

int x = 0xFFFFFF80;
int y = x >> 4;
int z = x >>> 4;

y = 0xFFFFFFF8;
z = 0x0FFFFFF8;

They differ because >> pads based on the sign if the type is signed where as >>> always pads with zeroes.

(c). What is the Value of *(p+1) on a Little-endian Machine? Show the Byte Layout of a in Memory

int a = 0x12345678;
char *p = (char*)&a;

Memory Layout

Address Value
a 0x78
a+1 0x56
a+2 0x34
a+3 0x12 
*(p+1) = 0x56

Problem 2

struct S {
    int a;
    int b;
    int c;
};

struct S arr[5];

Assume sizeof(int) = 4 and arr begins at address 0x200.

(a). Compute the Address of arr[3].b. Show how the Array Index and Field Offset Contribute to the Final Address

sizeof(S) = 12;

&arr[3] = 0x224;

&arr[3].b = 0x224 + 0x4;
          = 0x228;

(b). Suppose Register r1 Contains the Base Address of arr. What Constant Must Be Added to r1 to Access arr[2].c?

= 24 + 8
= 32

(c). Explain Which Parts of the Address Calculation Are Statically Known at Compile time and Which Are Determined Dynamically at Runtime

All the address calculations are known statically at compile time.

Problem 3

int A[5] = {2, 4, 6, 8, 10};
int *p   = &A[1];
int *q   = &A[3];
int **pp = &p;

*p = *q - A[0];
*(*pp + 2) = *p + *q;
pp = &q;
*(*pp - 1) = *(*pp - 1) + **pp;
p = &A[0];
**(&pp) = p;
*(*pp + 4) = *p + *(*pp + 1);

(a). After Each Assignment Statement Executes, Show the Contents of A[0] through A[4], the Values of p, q, and pp, and Identify Which Memory Location Was Modified

Variable Value
A {2, 4, 6, 8, 10}
p &A[1]
q &A[3]
pp &p

*p = *q - A[0];

Variable Value
A {2, 6, 6, 8, 10}
p &A[1]
q &A[3]
pp &p

*(*pp + 2) = *p + *q;

Variable Value
A {2, 6, 6, 14, 10}
p &A[1]
q &A[3]
pp &p

pp = &q;

Variable Value
A {2, 6, 6, 14, 10}
p &A[1]
q &A[3]
pp &q

*(*pp - 1) = *(*pp - 1) + **pp;

Variable Value
A {2, 6, 20, 14, 10}
p &A[1]
q &A[3]
pp &q

p = &A[0];

Variable Value
A {2, 6, 20, 14, 10}
p &A[0]
q &A[3]
pp &q

**(&pp) = p;

Variable Value
A {2, 6, 20, 14, 10}
p &A[0]
q &A[0]
pp &q

*(*pp + 4) = *p + *(*pp + 1);

Variable Value
A {2, 6, 20, 14, 8}
p &A[0]
q &A[0]
pp &q

(b). Give the Final Contents of Array A

A = {2, 6, 20, 14, 8}

Problem 4

struct Inner {
    int x;
    int y;
};

struct Outer {
    int a;
    struct Inner  b;
    struct Inner *p;
};

struct Outer  s;
struct Outer *d;
int *ip;

(a). Can &s.b.y Be Computed Entirely Statically, or Must Some part Be Computed Dynamically? Briefly Justify

Yes it can s is allocated statically and the same with the offsets to b.y.

(b). Can &d->b.y Be Computed Entirely Statically, or Must Some part Be Computed Dynamically? Briefly Justify

No it can't as d is allocated dynamically so the offsets can be static but the base is dynamic.

(c). Can &s.p->x Be Computed Entirely Statically, or Must Some part Be Computed Dynamically? Briefly Justify

No it can't the offset to s.p can be but p is dynamic, the offset to x can be static though but the base p must be dynamically determined.

(d). Can &d->p->y Be Computed Entirely Statically, or Must Some part Be Computed Dynamically? Briefly Justify

It must be computed dynamically but some offsets can be computed statically like the offset from the base of d to p but the base address d is dynamic

Problem 5

struct A {
    int a[3];
};

struct B {
    struct A  x0;
    struct A *x1;
};

struct C {
    struct B  b;
    struct B *c[6];
};

struct C  s;
struct C *d;

(a). How Many Unique Memory Locations Must Be Read to Compute *(s.b.x1->a + 2)? Exclude Instruction Fetches

2

(b). How Many Unique Memory Locations Must Be Read to Compute d->b.x1->a[1]? Exclude Instruction Fetches

3

(c). How Many Unique Memory Locations Must Be Read to Compute d->c[5]->b.x0.a[2]? Exclude Instruction Fetches

3

Problem 6

struct Node {
    int val;
    struct Node* next;
};

struct Node* f() {
    struct Node* a = malloc(sizeof(struct Node));
    a->val = 1;

    struct Node b;
    b.val = 2;
    a->next = &b;

    free(a);
    return a;
}

(a). Identify All Memory-management Errors in the Function above

Setting a->next=&b and free(a) before it is returned.

(b). Explain why Each Error Occurs

b is allocated on the stack of f so when f returns it gets deallocated setting a->next to be b will cause errors as it will point to other memory after f returns. Additionally a is freed before it returns which again is a use after free issue.

(c). Rewrite the Function so that there Are no Errors

struct Node {
    int val;
    struct Node* next;
};

struct Node* f() {
    struct Node* a = malloc(sizeof(struct Node));
    a->val = 1;

    struct Node* b = malloc(sizeof(struct Node));
    b->val = 2;
    a->next = b;

    return a;
}

Problem 7

int g(int *a, int n) {
    int t = a[n - 1];
    return t + 1;
}

int f(int *a, int n) {
    int x = n + 2;
    int y = g(a, x);
    return y + a[0];
}

Assume the call executed is f(A, 3).

(a). Draw the Stack Immediately after g is Called but before g Begins Executing Its Body

Description Value
*a A
n 3
Return Address
x 5
y
*a A
n 5
Return Address

(b). Draw the Stack during Execution of g after Local Variable t Has Been Allocated and Initialized

Description Value
*a A
n 3
Return Address
x 5
y
*a A
n 5
Return Address
t A[4]

(c). For both f and g, Identify Parameters, Local Variables, and return Addresses

f

Parameters:

  • *a
  • n

Local Variables

  • x
  • y

Return Addresses

  • instruction in f's caller

g

Parameters:

  • *a
  • n

Local Variables

  • t

Return Addresses

  • instruction in g's caller

(d). Explain why the return Address for g is Dynamic

It's dynamic because g could be called from multiple different locations in the program this call location must be determined at runtime.

(e). Suppose A Begins at Address 0x1000. Show the Values Passed to g when f(A, 3) Executes

g(0x1000, 5)

(f). State Which Parts of the Activation Records Are Known Statically and Which Are Determined Dynamically

The offsets and sizes of the records can be determined statically but their actual locations in memory and values must be determined dynamically. The return address must also be determined dynamically.

Problem 8

Write SM213 Assembly Equivalent to the following C Function. Assume a Standard Course-style Calling Convention

int sum(int *A) {
    int s = 0;
    for (int i = 0; i < 4; i++)
        s += A[i];
    return s;
}

Problem 9

Write SM213 Assembly Implementing the following Procedure. Assume the Argument is Passed in r0 and the return Value is Placed in r0. Include a Prologue, Epilogue, and Any Local Variable Storage You Need

int f(int x) {
    int y = x + 3;
    return y * 2;
}

f:
	deca r5
	st r6, 0(r5)
	deca r5
	
	ld $3, r2
	
	add r0, r2
	st r2, 0(r5)
	
	shl $1, r2
	mov r2, r0
	inca r5
	ld (r5), r6
	inca r5
	j (r6)

Problem 10

caller:
    deca r5
    st   r6, 0(r5)
    deca r5
    st   r1, 0(r5)
    ld   $arr, r0
    ld   $4,   r1
    gpc  $6,   r6
    j    foo
    ld   0(r5), r1
    inca r5
    ld   0(r5), r6
    inca r5
    j    (r6)

foo:
    deca r5
    st   r6, 0(r5)
    deca r5
    st   r2, 0(r5)
    deca r5
    st   r3, 0(r5)
    ld   $0,   r2
    ld   $0,   r3
L1:
    beq  r1,   L4
    ld   (r0), r4
    bgt  r4,   L2
L3:
    add  r4,   r2
    inca r0
    dec  r1
    br   L1
L2:
    not  r4
    inc  r4
    add  r4,   r3
    br   L3
L4:
    add  r3,   r2
    mov  r2,   r0
    ld   0(r5), r3
    inca r5
    ld   0(r5), r2
    inca r5
    ld   0(r5), r6
    inca r5
    j    (r6)

(a). Identify the Caller Prologue, Caller Epilogue, Callee Prologue, Callee Epilogue, Loop, if/else Structure, Function Call, and return Instruction

Caller Prologue:

deca r5
st   r6, 0(r5)
deca r5
st   r1, 0(r5)
ld   $arr, r0
ld   $4,   r1
gpc  $6,   r6

Caller Epilogue:

ld   0(r5), r1
inca r5

Callee Prologue:

deca r5
st   r6, 0(r5)
deca r5
st   r2, 0(r5)
deca r5
st   r3, 0(r5)

Callee Epilogue:

mov  r2,   r0
ld   0(r5), r3
inca r5
ld   0(r5), r2
inca r5
ld   0(r5), r6
inca r5
j    (r6)

Loop:

L1:
    beq  r1,   L4
    ld   (r0), r4
    bgt  r4,   L2
L3:
    add  r4,   r2
    inca r0
    dec  r1
    br   L1
L2:
    not  r4
    inc  r4
    add  r4,   r3
    br   L3

If / Else Structure:

beq  r1,   L4
ld   (r0), r4
bgt  r4,   L2

L3:
    add  r4,   r2
    inca r0
    dec  r1
    br   L1
L2:
    not  r4
    inc  r4
    add  r4,   r3
    br   L3

Function Call:

gpc  $6,   r6
j    foo

Return Instruction:

mov  r2,   r0
# ...
ld   0(r5), r6
inca r5
j    (r6)

(b). Write Equivalent C Code for foo

int foo(int* arr, int len) {
	int a = 0;
	int b = 0;
	
	while (len != 0) {
		if (arr[0] > 0) {
			b -= arr[0];
			a -= arr[0];
		} else {
			a += arr[0];
		}
		
		arr += 1;
		
		len -= 1;
	}
	
	return a + b;
}

Problem 11

void map(int *dst, int *src, int n, int (*f)(int));
int foldr(int *A, int n, int (*f)(int, int), int base);

map applies f to each element of src and stores the results in dst. foldr is defined by:

foldr(A, n, f, base)
  = base                              if n == 0
  = f(A[0], foldr(A+1, n-1, f, base))  otherwise

(a). Write map

void map(int *dst, int *src, int n, int (*f)(int)) {
	for (int i = 0; i < n; i++) {
		dst[i] = f(src[i]);
	}
}

(b). Write foldr

int foldr(int *A, int n, int (*f)(int, int), int base) {
	if (n == 0) return base;
	
	return f(A[0], foldr(A+1, n-1, f, base));
}

(c). Write int add(int x, int y);

int add(int x, int y) {
	return x + y;
}

(d). Compute foldr({1, 2, 3, 4}, 4, add, 0)

foldr({1, 2, 3, 4}, 4, add, 0); // 1 + 2 + 3 + 4
                                // 10

(e). Re-write the Functions so that instead of only Working on Integers, They also Work on Any Kind of Data

void map(void **dst, void **src, int n, void (*f)(void*));
void* foldr(void **A, int n, void* (*f)(void*, void*), void* base);

void map(void **dst, void **src, int n, void (*f)(void*)) {
	for (int i = 0; i < n; i++) {
		dst[i] = f(src[i]);
	}
}

void* foldr(void **A, int n, void* (*f)(void*, void*), void* base) {
	if (n == 0) return base;
	
	return f(A[0], foldr(A+1, n-1, f, base));
}

Problem 12

int total = 0;

void second(int v) {
    total = total + v;
}

void first(int v) {
    total = total + v;
    diskRead(v + 1, second);
}

int main() {
    diskRead(3, first);
    total = total + 100;
}

(a). Give One Possible order of Execution of the Major Events in This Program, including the Two diskRead Calls, the Callbacks, and the Modification of total in main

diskRead(3, first);
total = total + 100;
total = total + v;
diskRead(v + 1, second);
total = total + v;

(b). Explain why total = total + 100 May Execute before first Runs

Because if the disk read does not finish before the instruction pointer moves total = total + 100 can execute first.

(c). Suppose the First Disk Read Returns 10 and the Second Returns 7. What is the Final Value of total?

total = 100 + 10 + 7
      = 117

(d). Explain how Callback-based Asynchronous Control Flow Differs from Ordinary Sequential Procedure-call Flow

Asynchronous control flow can lead different parts of code to non deterministically run at different times allowing for flow to move in different ways depending on the run where as ordinary sequently procedure call flow will always run from top to bottom sometimes jumping up in the exact same order each time.

Problem 13

Define and Explain the Relationships between the following Terms: Interrupt, Polling, DMA, Thread, and Critical Section. Your Answer Must Describe at Least One Interaction between Two or More of These Concepts in a Real System

  • Interrupt: An interrupt is an external instruction which instantly causes the cpu to jump to another instruction from where the current program counter is.
  • Polling: Process by which some code continuously asks if another resource has finished.
  • DMA: Allows external hardware to directly access and modify / read memory from the cpu.
  • Thread: A thread is some small piece of code that can be run by itself on the CPU.
  • Critical Section: Any code which access a shared resource like memory.

Problem 14

int x = 0;
pthread_mutex_t m;

Thread 1:

lock(m);
x = x + 1;
printf("%d\n", x);
unlock(m);

Thread 2:

lock(m);
x = x + 2;
printf("%d\n", x);
unlock(m);

(a). List All Possible Outputs

1
3

2
3

(b). Explain why the Outputs Are Restricted

Because the locking allows only two possible results either thread 1 acquires the lock first causing thread 2 to pause until it completes or thread 2 acquires the lock first causing the inverse.

(c). Explain what Changes if the Mutex is Removed

If the mutexes were removed there the additions could run together before the prints or the other two outputs before could happen. Additionally write instructions might happen after read instructions leading the values to be clobbered by each other for example we could end up with just 1 or just 2 as the final total.

Problem 15

int ready = 0;

Thread 1:

produce_data();
ready = 1;

Thread 2:

while (ready == 0);

consume_data();

(a). Explain why This Implementation is Inefficient

Because it requires constant polling from thread 2 which uses cpu cycles.

(b). Rewrite the Program Using a Mutex and a Condition Variable

int producer_acquired = 0;
pthread_mutex_t m = uthread_mutex_create();
uthread_cond_t  ready = uthread_cond_create(m);

Thread 1

uthread_mutex_lock(mx);

produce_data();
producer_acquired = 1;
uthread_cond_broadcast(ready);

uthread_mutex_unlock(mx);

Thread 2

uthread_mutex_lock(mx);
while (producer_acquired == 0) {
	uthread_cond_wait(ready);
}

consume_data();
uthread_mutex_unlock(mx);

(c). Explain why Condition Variables Are Useful in This Setting

They allow the data consumption to wait until it's been produced without wasting polling on checking a variable it also stops deadlocks.