⃝c Jonatan Schroeder – Not to be copied, used, or revised without the explicit written permission of the copyright owner.
[4] 1. Variables and Memory. Consider the following C code containing global variables a, b, c, and d that is executed on a big endian, 32-bit processor. Assume that the address of a is 0x1000 and that the compiler allocates the variables contiguously, in the order they appear, wasting no memory between them other than what is required to ensure that they are properly aligned, and assuming that int’s and pointers are 4-bytes long. With this information, you can determine the value of certain bytes of memory following the execution of foo().
int a;
unsigned char b;
signed char c;
int d;
void foo() {
b = 0xff;
c = 0xff;
a = b;
d = c; }
List the address and value of every memory location whose address and value you know. If a value of a memory location is not known, write X. List all numbers in hex.
1000: 0x00
1001: 0x00
1002: 0x00
1003: 0xff
1004: 0xff
1005: 0xff
1008: 0xff
1009: 0xff
100a: 0xff
100b: 0xff
[6] 2. Global Variables. Assume you are given the following global variables a, and b.
int a[3] = {5, 4, 3};
int *b;
[4] a.
Give the SM213 assembly code for the following statements. Comments are not required.
b =a+1;
*b = a[2] – 1;
ld $a, r0
inca r0
ld $b, r1
st r0, (r1)
ld 4(r0), r2
dec r2
st r2, (r0)
[2] b. What are the contents of array a after the code is finished? Solution: a={5,2,3}
[7] 3. Instance and Local Variables. Assume two global variables item and size, have been declared.
struct A {
int length;
int width;
int height;
};
int size;
struct B {
struct A data;
int id;
struct B* next;
};
struct B *item;
[2] a. Give assembly code for the C statement below. Comments are not required.
item->id = 213;
ld $item, r0
ld (r0), r0
ld $213, r1
st r1, 12(r0)
[5] b. Give assembly code for the C statement below. Comments are not required.
size = item->next->data.length +
item->next->data.width +
item->next->data.height;
ld $item, r0 # &item
ld (r0), r0 # item
ld 16(r0), r0 # item->next
ld 0(r0), r1 # item->next->data.length
ld 4(r0), r2 # item->next->data.width
add r1, r2
ld 8(r0), r1 # item->next->data.height
add r1, r2
ld $size, r1 # &size
st r2, (r1) # update
[15] 4. Reading Assembly Code. The following procedure uses the call/return conventions de- scribed in class, where we use r0 for return values, r5 for the stack pointer, and r6 for the return address.
page 2
foo: deca r5 #
st r6, (r5) #
ld 8(r5),r1# bgtr1,POS # ld $0, r0 # brEND #
POS:dec r1 # ld 4(r5),r2# inca r2 # ld $-8,r3 # add r3,r5 # st r2, (r5) # st r1,4(r5)# gpc $6, r6 # jfoo # ld $8, r3 # add r3, r5 #
ld 4(r5),r2# ld (r2), r3 # beqr3,END # bgtr3,END # inc r0 #
END: ld (r5), r6 #
inca r5 #
j (r6) #
[4] a. Carefully comment every line of code above. [8] b. Convert the assembly code into C.
int foo(int a[], int n) {
if (n <= 0) return 0;
int r = foo(a + 1, n - 1);
if (*a < 0) r++;
return r; }
[3] c. What is the purpose of the code above? Give the simplest plain English description you can.
Solution : It counts the number of negative values in an array.
page 3
page 4
[6] 5. C Pointers and Functions Determine the output for the following C code by writing, in each box on the right, the value printed by the corresponding instruction on the left. Assume that the address of a is 0x1000, b is 0x2000, and c is 0x3000. You may print the results in decimal or hexadecimal, but if presenting in hexadecimal it should be preceded by 0x.
1 void foo() {
2 int a=1;
3 int b=2;
4 int*c=&a;
5 int** d = &c;
6
7 a=b;
8 b=3;
9 printf("%d\n",
10 printf("%d\n",
11
12 int old_b = b;
13 bar(&a, &b);
14 int new_b = b;
15 printf("%d\n",
16
17 a=5;
18 zee(*d);
19 printf("%d\n",
20 printf("%d\n",
21 printf("%d\n",
22 }
23
24 void bar(int *x,
25 int temp = x;
26 x = y;
c); // ..................... *c); // .....................
(new_b - old_b)); // ....
a); // ..................... *c); // ..................... *d); // .....................
int *y) {
27 y = temp;
28 }
29
30 void zee (int *x) {
31 *x = *x * 2;
32 }
page 5
[6] 6. For each of the following pieces of code, what is typically printed as a result of calling function foo? Is there any memory leak, dangling pointer or illegal memory access?
[3] a.
int one() {
int a = 110;
return &a; }
void two() {
int a = 213;
}
void foo() {
int *course_num = one();
two();
printf("CPSC %d is the best!\n", *course_num);
}
void bar(int *a) {
printf("in bar: %d\n", a[0]);
a = NULL;
}
void foo() {
int *a = malloc(sizeof(int) * 4);
a[0] = 3;
bar(a);
printf("in foo: %d\n", a[0]);
free(a);
}
[3] b.
[10] 7. Static Control Flow. Give the SM213 assembly for the lowest procedure shown below. Assume the caller of lowest’s prologue was implemented correctly (so r5 is pointing to the right place). Similar to code used elsewhere this term, assume that we use r0 for return values, r5 for the stack pointer, and r6 for the return address, and that arguments are passed through the stack. Comments are encouraged, but not required.
int lowest(int a[], int n) {
int r = a[0];
while (--n > 0) {
if (a[n] < r)
r = a[n];
}
return r; }
lowest:
ld 0(r5), r1
ld 4(r5), r2
ld (r1), r0
LOOP: dec r2
bgt r2, IN
br OUT
IN: ld (r1, r2, 4), r3
mov r3, r4
not r4
inc r4
add r0, r4
bgt r4, UP
br LOOP
UP: mov r3,r0 br LOOP
OUT: j (r6)
[9] 8. Dynamic Control Flow. The following procedure uses the call/return conventions de- scribed in class, where we use r0 for return values, r5 for the stack pointer, and r6 for the return address.
rep: decar5 # st r6,(r5)#
ld 4(r5), r0 #
L0: ld 8(r5), r1 # bgtr1,L1 # brEND #
L1: dec r1 #
st r1, 8(r5) # deca r5 # st r0,(r5)# gpc$2,r6 # j 12(r5) # inca r5 # brL0 #
L2: ld (r5), r6 #
page 6
inca r5 #
j (r6) #
[3] a. Carefully comment every line of code above. [6] b. Convert the assembly code into C.
int rep(int val, int n, int (*f)(int)) {
while (n > 0) {
n–;
val = f(val);
}
return val; }
[5] 9. IO Devices. Based on your knowledge of how I/O devices communicate with the CPU, for the following I/O operations, select which mechanism is better suited to transfer the information between the parties in the transaction.
a. The CPU wants to get the current time of day from a clock device.
⃝ CPU sends PIO request with result obtained by polling
⃝ CPU sends PIO request with result obtained via DMA
⃝ CPU interrupts the clock’s controller
⃝ Clock device stores time in memory area shared with CPU
⃝ Clock device regularly interrupts CPU with new time, stored by CPU for future
access
b. A scanner needs to send an acquired image to the CPU for processing.
⃝ CPU polls scanner controller for image
⃝ Scanner controller uses PIO to notify CPU
⃝ Scanner controller saves data in pre-arranged memory address and interrupts CPU
⃝ Scanner controller interrupts CPU, then CPU uses PIO to obtain data directly
from scanner
⃝ Scanner controller interrupts CPU, including the image as part of the interrupt
process
c. A touchscreen monitor needs to notify the CPU that the user touched on a particular position on the screen.
⃝ CPU periodically requests for last touched position
⃝ Monitor controller uses PIO to notify CPU
⃝ Monitor controller stores location in memory, CPU periodically checks memory
for new touch
⃝ Monitor controller interrupts CPU, which runs a pre-determined interrupt handler
⃝ Monitor controller changes a pre-determined register with the position of the last
touch
page 7
d. The CPU decides to turn off the Num Lock indicator on the keyboard. ⃝ CPU sends PIO request to the keyboard device
⃝ CPU changes a specific register associated to the indicator
⃝ CPU changes a specific memory location in main memory associated to the indi-
cator
⃝ CPU interrupts the keyboard controller requesting a change in indicator values
⃝ CPU halts until the user hits the Num Lock key
e. A USB controller needs to notify the CPU that a new device has been connected.
⃝ CPU notifies the USB controller via PIO
⃝ USB controller interrupts the CPU, which runs a pre-determined interrupt handler
⃝ USB controller changes a memory location in main memory that is periodically
checked by the CPU
⃝ USB controller increments the value of a device counter register
⃝ CPU periodically requests the USB controller’s status, which changes when a
device is connected
page 8
page 9
[20] 10. You would like to help your TAs organize their office hours, so you decided to create a system to streamline student assistance. In this system, both students and TAs run as individual threads. The goal of the system is to allow each student to be paired with an available TA. Students that need assistance call function register, which will block until a TA is available, then return the TA ID. Similarly, TAs loop calling attend_student, which will return the ID of a student in need, blocking if no student currently needs help. Once the assistance is complete, the student thread proceeds with different functions, while the TA thread calls attend_student again to signal another student.
The code below provides the basic structure of the code. What you are to do is to provide synchronization to the code, using semaphores. In particular, your code must:
• Block a student until a TA becomes available.
• Block a TA until a student requires assistance.
• EnsurethateachstudentalwaysreceivestheIDoftheTAassignedtoitandvice-versa (i.e., if TA X receives the ID of student Y, then student Y receives the ID of TA X). Note that this requires:
– MutualexclusionsothattwoTAsortwostudentsdonotaccessthecriticalsection simultaneously (one TA and one student should be able to access it at the same time);
– A barrier that ensures that a student only obtains the current TA ID after it has been updated, and vice-versa.
• Ensure that no race conditions or deadlocks are caused by this functionality.
Your code may not use polling. It is also not required to handle queue jumping. You may use as many semaphores as you need, as well as additional variables you may need to provide synchronization.
For reference, prototypes for functions you may use in your implementation are listed below. Note that the prefix uthread_ was removed for simplification.
sem_t sem_create (int initial_value);
void sem_wait (sem_t);
void sem_signal (sem_t);
int current_student_ID;
int current_TA_ID;
// Declare all semaphores and variables below
void initialize() {
// Initialize all semaphores and variables below
}
int register(int student_ID) {
int my_TA;
current_student_ID = student_ID;
my_TA = current_TA_ID;
return my_TA;
}
page 10
int attend_student(int TA_ID) {
int my_student;
current_TA_ID = TA_ID;
my_student = current_student_ID;
return my_student;
}
page 11
int current_student_ID;
int current_TA_ID;
sem_t avail_ta;
sem_t avail_student;
sem_t mutex_ta;
sem_t mutex_student;
sem_t ta_updated;
sem_t student_updated;
void initialize() {
// Initialize all data structures you may use below
avail_ta
avail_student
mutex_ta
mutex_student
ta_updated
student_updated = sem_create(0);
}
int register(int studentID) {
int myTA;
sem_signal(avail_student);
sem_wait(avail_ta);
sem_wait(mutex_student);
current_student_ID = studentID;
sem_signal(student_updated);
sem_wait(ta_updated);
myTA = current_TA_ID;
sem_signal(mutex_student);
return myTA;
}
int attend_student(int taID) {
int myStudent;
sem_signal(avail_ta);
sem_wait(avail_student);
sem_wait(mutex_ta);
= sem_create(0);
= sem_create(0);
= sem_create(0);
= sem_create(0);
= sem_create(0);
page 12
current_TA_ID = taID;
sem_signal(ta_updated);
sem_wait(student_updated);
myStudent = current_student_ID;
sem_signal(mutex_ta);
return myStudent;
}
page 13