Problem 1

Evaluate each of the following pieces of Java code to determine what they output. Give your answers in hexadecimal and explain any sign extension, truncation, or zero extension that occurs.

(a)

int a = 0x7f << 12;
System.out.printf("%x", a);

0x7f000

(b)

int a = ((byte)0x7f) << 12;
System.out.printf("%x", a);

int a = 0x0000007f << 12;
System.out.printf("%x", a);

0x7f000

(c)

int a = ((byte)0xae) << 16;
a = a | 0x00ff0000;
System.out.printf("%x", a);

int a = (0xffffffae) << 16;
a = a | 0x00ff0000;
System.out.printf("%x", a);

a = 0xffae0000 | 0x00ff0000;
System.out.printf("%x", a);

0xffff0000

(d)

short s = (short)0xff10;
int x = s << 8;
System.out.printf("%x", x);

int x = 0xffffff10 << 8;
System.out.printf("%x", x);

0xffff1000

(e)

char c = 0xff10;
int x = c >> 4;
System.out.printf("%x", x);

int x = 0x0000ff10 >> 4;
System.out.printf("%x", x);

0xff1

Problem 2

struct Inner {
    char  a;
    short b;
    int   c;
};

struct Outer {
    char        x;
    struct Inner s;
    short        y;
    struct Inner *p;
    char         z;
};

Assume int = 4 bytes, short = 2 bytes, char = 1 byte, pointers = 4 bytes, and natural alignment rules apply.

(a). Draw the Memory Layout of struct Outer, Showing Field Offsets, Any Padding Bytes, and the Alignment Boundaries You Used

(b). What is sizeof(struct Outer)? Explain Briefly

(c). Suppose struct Outer arr[10]; and arr Begins at Address BASE. Give an Address Expression for arr[3].p->c and Indicate Which Components Are Compile-time Constants

Problem 3

struct Node {
    int  a[5];
    char b;
};

struct Container {
    struct Node  n;
    struct Node *p;
};

struct Container  c;
struct Container *cp;
int i;

For each expression below, determine whether the specified expression can be computed entirely statically or whether some part must be computed dynamically. Briefly justify your answer.

(a). &c.n.a[3]

(b). &cp->n.a[2]

(c). &c.p->a[4]

(d). &cp->p->a[i]

Problem 4

struct A { int x[4]; };
struct B { struct A *a; struct A b; };
struct C { struct B *b[3]; };

struct C *c;
int i;

For each expression below, determine how many unique memory locations must be read in order to compute the value of the expression. Exclude instruction fetches. Treat each expression independently.

(a). c->b[2]->a->x[1]

(b). c->b[1]->b.x[3]

(c). (*c->b[0]).a->x[i]

Problem 5

int A[6] = {1, 3, 5, 7, 9, 11};
int *p    = &A[1];
int *q    = &A[4];
int **r   = &p;

*q = *p + 2;
*(p+3) = *q - A[0];
r = &q;
*(*r - 2) = **r + *p;
p = &A[0];
*q = *p + *(p+5);

(a). Draw Memory after Each Assignment Step

(b). Show the Values Stored in A after Each Step and the Final Contents of A

(c). Identify the Memory Location Modified by Each Assignment

Problem 6

void *rc_malloc(int n);
void  rc_keep_ref(void *p);
void  rc_free_ref(void *p);

Classify each module using exactly one of the following labels:

• memory leak
• dangling pointer
• memory leak and dangling pointer
• possible array overflow
• no bug; poor modular structure
• no bug; good modular structure

For each module, briefly justify your classification.

Module alpha

int *alpha_store = NULL;

void alpha_save(int *x) {
    alpha_store = x;
}

void alpha_clear() {
    rc_free_ref(alpha_store);
}

Module beta

int *beta_store = NULL;

void beta_update(int *x) {
    if (beta_store)
        *x += *beta_store;
    beta_store = x;
}

void beta_done() {
    rc_free_ref(beta_store);
}

Module gamma

int *gamma_store = NULL;

void gamma_use(int *x) {
    if (gamma_store)
        *x += *gamma_store;
    gamma_store = rc_malloc(sizeof(int));
    *gamma_store = *x;
}

void gamma_finish() {
    rc_free_ref(gamma_store);
}

(a). Classify and Justify Module Alpha

(b). Classify and Justify Module Beta

(c). Classify and Justify Module Gamma

Problem 7

int zot(int *a, int b) {
    return *a + foo(a[b]);
}

Write SM213 Assembly Equivalent to the Above C Procedure. Assume a is Passed in r0, b is Passed in r1, and the Return Value is Placed in r0

Problem 8

int f(int x) {
    int a = x + 1;
    int b = a + 2;
}

int g() {
    int c = 7;
    f(c);
}

int h() {
    int y;
    return y;
}

g();
h();

Assume no default variable initialization.

(a). What Value Might y Contain when h Runs? Give One Plausible Answer and Explain how It Could Arise

(b). Explain why the Language Does Not Guarantee Any Particular Value

(c). Relate Your Explanation to Stack Allocation and Activation-frame Reuse

Problem 9

int foo(int *a, int b) {
    int *c;
    int  d;
    c = &b;
    bar();
    return *c;
}

Translate the Above C Procedure into SM213 Assembly. Use a Reasonable Activation-frame Layout Consistent with the Course Calling Convention

Problem 10

F0: deca r5
    st   r6, 0(r5)
    deca r5
    st   r2, 0(r5)
    deca r5
    st   r3, 0(r5)
    deca r5
    st   r4, 0(r5)
    mov  r0, r2        # r2 = a
    mov  r1, r3        # r3 = b
    mov  r2, r4
    not  r4
    inc  r4
    add  r3, r4
    beq  r4, L0
    bgt  r4, L0
    ld   $0, r4        # s = 0
L1: mov  r2, r6
    not  r6
    inc  r6
    add  r3, r6        # r6 = b - i
    beq  r6, L2
    bgt  r6, L2
    add  r2, r4        # s += i
    inc  r2            # i++
    br   L1
L2: mov  r0, r2
    inc  r2
    mov  r2, r0
    gpc  $6,  r6
    j    F0
    add  r4,  r0
    br   L3
L0: mov  r2,  r0
L3: ld   0(r5), r4
    inca r5
    ld   0(r5), r3
    inca r5
    ld   0(r5), r2
    inca r5
    ld   0(r5), r6
    inca r5
    j    (r6)

(a). Identify All Parts of the Code (Prologues/Epilogues, Function Calls, Static Control Flow Elements). For All Branch Instructions Write the Machine Code, e.g. 0xA123

(b). Write Equivalent C Code for F0

Problem 11

int copy_pos(int **src, int **dst, int n) {
    int j = 0;
    for (int i = 0; i < n; i++)
        if (*src[i] > 0)
            dst[j++] = src[i];
    return j;
}

The above procedure copies positive integers into another array and returns how many were copied.

Write a More General Procedure copy_if that Abstracts the Filtering Behaviour

Your procedure should:

• take a function pointer parameter that determines whether an element should be copied
• copy only the elements for which the function returns true
• store the selected pointers in dst
• return the number of elements copied

int copy_if(int **src, int **dst, int n, int (*predicate)(int));

Problem 12

void readA(void (*callback)(int));
void readB(void (*callback)(int));

Each procedure starts an asynchronous operation and returns immediately. Later, its callback is invoked with the computed integer result.

Write void foo(); so that the program prints:

result = x * y + x

where x is the value returned by readA and y is the value returned by readB.

Requirements:

• foo must start both asynchronous operations
• your solution must not use polling or spin waiting
• your solution must print exactly once, after both results are available
• you may use global variables if needed

(a). Write the C Code

(b). Briefly Explain how Your Code Guarantees that Printing Happens Only after Both Asynchronous Operations Complete

(c). Suppose readA Returns 4 and readB Returns 7. What is Printed?

Problem 13

Explain the Relationships between Interrupt, Thread, Deadlock, Critical Section, and Condition Variable. Your Answer Must Include at Least One Concrete Scenario that Connects at Least Three of These Terms

Problem 14

Assume multiple CPUs are available, v1 and v2 are global integers initially 0, mx is a mutex, and c1 and c2 are condition variables associated with mx. List all possible orderings of the labeled calls using a format such as a > b > c > d. Only list distinct orderings that can actually occur.

(a). Scenario A

Thread 1:

uthread_mutex_lock(mx);
a();
if (!v1) {
    uthread_cond_wait(c1);
}
b();
uthread_mutex_unlock(mx);

Thread 2:

uthread_mutex_lock(mx);
c();
v1 = 1;
uthread_cond_signal(c1);
d();
uthread_mutex_unlock(mx);

(b). Scenario B

Thread 1:

uthread_mutex_lock(mx);
a();
while (!v1) {
    uthread_cond_wait(c1);
}
b();
v2 = 1;
uthread_cond_signal(c2);
e();
uthread_mutex_unlock(mx);

Thread 2:

uthread_mutex_lock(mx);
c();
v1 = 1;
uthread_cond_signal(c1);
while (!v2) {
    uthread_cond_wait(c2);
}
d();
uthread_mutex_unlock(mx);

Problem 15

Choose one of the following tasks and provide code.

Option 1

Convert the following asynchronous design into a threaded design that creates a worker thread, blocks until the result is available, and then returns the value synchronously.

void read_async(int n, void (*callback)(int));

Option 2

Take a solution that uses a mutex and condition variable and rewrite it using semaphores instead.

State any assumptions you make.