THE UNIVERSITY OF BRITISH COLUMBIA CPSC 213: FINAL EXAM – December 14, 2017
FullName: ______________________ ExamID: Signature: ______________________ UBC Student #:
Important notes about this examination
1. Copy the last 3 digits of your exam’s serial number from the upper right‐hand corner into the Exam ID box on this page.
2. You have 150 minutes to write this examination. An empty page is provided for you to answer any questions for which you need
extra space. Clearly indicate which question the answer is related to.
3. No notes, books, or any type of electronic equipment is allowed. You can have pen or pencil, eraser, your ID and a bottle of
water on your desk. All other material should be stored in your bag under your desk.
4. The marks allocated to each question are in square brackets alongside the question. Use this information to help you determine
how much time you should spend on each question.
5. No questions are permitted during the exam. If you are unsure about the meaning of a question, write your assumptions.
Student Conduct during Examinations
1. Each examination candidate must be prepared to produce, upon the request of the invigilator or examiner, his or her UBCcard for identification.
2. Examination candidates are not permitted to ask questions of the examiners or invigilators, except in cases of supposed errors or ambiguities in examination questions, illegible or missing material, or the like.
3. No examination candidate shall be permitted to enter the examination room after the expiration of one‐half hour from the scheduled starting time, or to leave during the first half hour of the examination. Should the examination run forty‐ five (45) minutes or less, no examination candidate shall be permitted to enter the examination room once the examination has begun.
4. Examination candidates must conduct themselves honestly and in accordance with established rules for a given examination, which will be articulated by the examiner or invigilator prior to the examination commencing. Should dishonest behaviour be observed by the examiner(s) or invigilator(s), pleas of accident or forgetfulness shall not be received.
5. Examination candidates suspected of any of the following, or any other similar practices, may be immediately dismissed from the examination by the examiner/invigilator, and may be subject to disciplinary action:
i. speaking or communicating with other examination candidates, unless
otherwise authorized;
ii. purposely exposing written papers to the view of other examination
candidates or imaging devices;
iii. purposely viewing the written papers of other examination candidates;
iv. using or having visible at the place of writing any books, papers or other
memory aid devices other than those authorized by the examiner(s); and,
v. using or operating electronic devices including but not limited to telephones, calculators, computers, or similar devices other than those authorized by the
examiner(s)—(electronic devices other than those authorized by the examiner(s) must be completely powered down if present at the place of writing).
6. Examination candidates must not destroy or damage any examination material, must hand in all examination papers, and must not take any examination material from the examination room without permission of the examiner or invigilator.
7. Notwithstanding the above, for any mode of examination that does not fall into the traditional, paper‐based method, examination candidates shall adhere to any special rules for conduct as established and articulated by the examiner.
8. Examination candidates must follow any additional examination rules or directions communicated by the examiner(s) or invigilator(s).
Please do not write in this space:
Question 1: Question 2:
Question 3: Question 4: Question 5: Question 6: Question 7: Question 8: Question 9:
1 236413 048929
.
1 [4 marks] 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; }
Listtheaddressandvalueofeverymemorylocationwhoseaddressandvalueyouknow.Usetheform“address: value”. List every byte on a separate line and 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
2
2 [4 marks] Global Variables. Assume you are given the following global variables a, and b. int a[3] = {5, 4, 3};
int *b;
2a GivetheSM213assemblycodeforthefollowingstatements.Commentsarenotrequired. b = a+1;
*b = 2;
2b Whatarethecontentsofarrayaafterthecodeisfinished? {5, 2, 3}
ld $a, r0
inca r0
ld $b, r1
st r0, (r1)
ld $2, r3
st r3, (r0)
3
3 [6 marks] Instance and Local Variables. Assume two global variables item and size, have been declared.
struct A {
int length;
int width;
int height;
};
struct B *item;
int size;
3a WhatistheoffsetofidinstructB? 12
3b GiveassemblycodefortheCstatement: item->id = 213;
3c GiveassemblycodefortheCstatement: size = item->next->data.height;
struct B {
struct A data;
int id;
struct B* next;
};
ld $item, r0
ld (r0), r0
ld $213, r1
st r1, 12(r0)
ld $item, r0
ld (r0), r0
ld 16(r0), r0
ld 8(r0), r0
ld $size, r1
st r0, (r1)
4
4 [6 marks] C Pointers and Functions Determine the output for the following C Code. Assume that the address of a is 0x1000, b is 0x2000, and c is 0x3000.
[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”, c);
[10] printf(“%d”, *c);
[11]
[12] int old_b = b;
[13] swap(&a, &b);
[14] int new_b = b;
[15] printf(“%d”, (new_b – old_b));
[16]
[17] a = 5;
[18] double_x(*d);
[19] printf(“%d”, a);
[20] printf(“%d”, *c);
[21] printf(“%d”, *d);
[22] }
4a Line[9]:
4b Line[10]:
4c Line[15]:
4d Line[19]:
4e Line[20]:
4f Line[21]:
0
void swap(int *a, int *b) {
int temp = a;
a = b;
b=temp; }
void double_x (int *x) {
*x = *x * 2;
}
0x1000
2
10
10
0x1000
5
5 [12 marks] Reading Assembly Code. The following procedure uses the call/return conventions described in class, where we use r0 for return values, r5 for the stack pointer, and r6 for the return address.
fn: deca r5 # Allocate space for left
deca r5 # Allocate space for ra
st r6, 4(r5) # Save return address in stack ld 8(r5), r0 # r0 = argument n
beq r0, L1 # ifnis0,return0
ld 4(r0), r1 # r1 = n->left
deca r5 # Allocate space for argument st r1, (r5) # Save n->left as argument
gpc $6, r6
j fn
inca r5
st r0, (r5) # Store return address in stack
ld 8(r5), r0 # r0 = argument n
gpc $6, r6
j fn
inca r5
ld (r5), r2 # r2 = left
mov r2, r3
not r3
inc r3
add r0, r3
bgt r3, L0
mov r2, r0
# r3 = left
# r3 = ̃left
# r3 = -left
# r3 = right-left
# if right>left skip next line (r0 is right)
# r0 = left
# increment return value
# Save return address in r6
# Call fn(n->left)
# Free argument space
ld 8(r0), r1 # r1 = n->right
deca r5 # Allocate space for argument
st r1, (r5) # Save n->right as argument
# Save return address in r6
# Call fn(n->right)
# Free argument space
L0: inc r0
L1: ld 4(r5), r6 # Retrieve return address
inca r5
inca r5
j (r6)
# Free space for ra
# Free space for left
# Return
Assumethefunctionabovereceivesapointertoastruct treenode,definedasfollows:
struct treenode {
int value;
struct treenode *left, *right;
};
5a Carefullycommenteverylineofcodeabove.
6
.
5b ConverttheassemblyintoC.
5c Whatisthepurposeofthecodefrompreviouspage?Givethesimplest,plainEnglishdescriptionyoucan. fn returns the height of the binary tree.
int fn(struct treenode *t) {
if (!t) return 0;
int i = fn(t->left), j = fn(t->right);
return i > j ? i + 1 : j + 1;
}
7
6 [4 marks] C Memory Errors. Which statement best describes the following code with respect to potential memory errors?
6a 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);
}
A: There is no bug
B: There is a memory leak
C: There is a dangling pointer
D: There is a possible dangling pointer that could be fixed with reference counting
E: There is a possible memory leak that could be fixed with reference counting
F: There is a memory leak that could be fixed by adding calls to malloc and free()
C
6b void bar(int *a) { printf(“first: %d\n”, a[0]);
a = NULL; }
void foo() {
int *a = malloc(sizeof(int) * 4); a[0] = 3;
bar(a);
printf(“first again: %d\n”, a[0]); free(a);
}
A: There is no bug
B: There is a memory leak
C: There is a dangling pointer
D: There is a possible dangling pointer that could be fixed with reference counting
E: There is a possible memory leak that could be fixed with reference counting
F: There is a memory leak that could be fixed by adding calls to malloc and free()
A
8
7 [8 marks] Procedure Calls. Give the SM213 assembly for the longest procedure shown below. Assume the caller of longest’s prologue was implemented correctly (so r5 is pointing to the right place). Similar to in lecture this semester, assume that we use r0 for return values, r5 for the stack pointer, and r6 for the return address.
struct Rect {
int length;
int width; };
int longest(struct Rect* r) {
if (r->length > r->width)
return r->length;
return r->width;
}
longest: deca r5
st r6, (r5)
ld 4(r5), r1
ld (r1), r1
ld (r1), r2
ld 4(r1), r3
mov r3, r4
not r4
inc r4
add r2, r4
bgt r4, L1
mov r3, r0
br L2
L1: mov r2, r0
L2: ld (r5), r6
inca r5 j (r6)
# allocate space for ra in stack frame # store ra in stack
# r1=&r
# r1=r
# r2 = r->length
# r3 = r->width
# r4 = r->width
#
# r4 = -r->width
# r4 = r->length – r->width
# if r->length > r->width goto L1
# r0 = r->width
# goto L2
# r0 = r->length
# load ra into r6
# deallocate stack frame
# return
9
8 [9 marks] Using Function Pointers. For this problem, assume you have been given two arrays list1 and list2, whichhavebeeninitializedwith5integervalues.Forexample,thefollowingfunctioncallabs2(list1, list2, reset) would change all of the values in one of the lists to 0.
void abs1(int *a, int* b, void(*fn)(int*, int*)) {
for (int i = 0; i < 5; i++) {
fn(&a[i], &b[i]);
}
}
void abs2(int *a, int* b, int(*fn)(int*, int*)) {
for (int i = 0; i < 5; i++) {
b[i] = fn(&a[i], &b[i]);
}
}
int reset (int *a, int *b) {
return 0;
}
8a Writeafunctioncalledfn1,whichwhenpassedasaparametertoabs1,woulddoubleeachofthevaluesin
the first array and place those values in the corresponding positions of the second array.
// Given list1: {1, 2, 3, 4, 5} and list2: {1, 1, 1, 1, 1}
// After function call list2 should contain: {2, 4, 6, 8, 10}.
8b Providethefunctioncalltoabs1sothatlist2containsvaluesthatareeach2xlargerthanlist1.
abs1(list1, list2, fn1);
abs1(____________, ____________, ____________);
void fn1 (int* a, int* b) {
*b = *a + *a;
}
10
.
8c Writeafunctioncalledfn2,whichwhenpassedasaparametertoabs2,woulddoubleeachofthevaluesin the first array and place those values in the corresponding positions of the second array.
// Given list1: {1, 2, 3, 4, 5} and list2: {1, 1, 1, 1, 1}
// After function call list2 should contain: {2, 4, 6, 8, 10}.
8d Writeafunctioncalledfn3,whichwhenpassedasanparametertoabs1,wouldplacethemaximumvalue at matching indices of the two arrays into the second array.
// Given list1: {1, 2, 3, 4, 5} and list2: {4, 1, 2, 7, 3}
// After function call list2 should contain: {4, 2, 3, 7, 5}.
8e Writeafunctioncalledfn4,whichwhenpassedasanparametertoabs2,wouldplacethemaximumvalue at matching indices of the two arrays into the second array.
// Given list1: {1, 2, 3, 4, 5} and list2: {4, 1, 2, 7, 3}
// After function call list2 should contain: {4, 2, 3, 7, 5}.
int fn2 (int *a, int* b) {
return *a + *a;
}
void fn3 (int* a, int* b){
if (*a > *b)
}
*b = *a;
int fn4 (int* a, int* b){
if (*a > *b)
return *a;
return *b; }
11
9 [22 marks] Synchronization. In a science lab, people wanting to visit need to acquire three items: goggles, a coat, and gloves. The system designed to manage these items contains the following code. Note that some parts of the code that are not useful for this question have been removed. You may assume that all mutexes and all arrays have been properly initialized.
uthread_mutex_t goggles_lock;
uthread_mutex_t coat_lock;
uthread_mutex_t gloves_lock;
int goggles[NUM_ITEMS], coats[NUM_ITEMS], gloves[NUM_ITEMS];
int num_goggles = NUM_ITEMS, num_coats = NUM_ITEMS;
int num_gloves = NUM_ITEMS;
int get_goggles() {
int rval = -1;
while (rval == -1) {
uthread_mutex_lock(goggles_lock);
if (num_goggles > 0) {
rval = goggles[–num_goggles];
}
uthread_mutex_unlock(goggles_lock);
}
return rval;
}
void return_goggles(int num) {
uthread_mutex_lock(goggles_lock);
goggles[num_goggles++] = num;
uthread_mutex_unlock(goggles_lock);
}
Functions get coat() and get gloves() are implemented like the get goggles() function. Functions return coat() and return gloves() are implemented similarly to function return goggles(). A visitor will typically acquire all three items (coat, gloves, goggles), perform any relevant tasks in the lab, and then return all three items when they are finished.
9a Whyistheimplementationshownaboveinefficient?
Because it achieves its purpose using busy waiting, which wastes CPU time without making any progress.
12
.
9b Rewrite functions get goggles and return goggles to use condition variables in order to avoid the inefficiency mentioned in the previous question. You may assume that any mutex condition variable you use in your solution is properly initialized in the main function.
int get_goggles() {
int rval;
uthread_mutex_lock(goggles_lock);
while (num_googles == 0)
uthread_cond_wait(goggles_cond);
rval = goggles[–num_goggles];
uthread_mutex_unlock(goggles_lock);
return rval;
}
void return_goggles(int num) {
uthread_mutex_lock(goggles_lock);
goggles[num_goggles++] = num;
uthread_cond_signal(goggles_cond);
uthread_mutex_unlock(goggles_lock);
}
9c Rewritefunctionsget\_gogglesandreturn\_gogglestousesemaphoresinordertoavoidtheinef- ficiency mentioned in the previous question. Assume that any semaphore you create is properly initialized in the main function, but you must indicate its initial value in your answer.
// goggles_sem starts at NUM_ITEMS, mx semaphore starts at 1.
int get_goggles() {
int rval;
uthread_sem_wait(goggles_sem);
uthread_mutex_lock(goggles_lock); // or sem_wait on a mx semaphore
rval = goggles[–num_goggles];
uthread_mutex_unlock(goggles_lock); // or sem_signal on a mx semaphore
return rval;
}
void return_goggles(int num) {
uthread_mutex_lock(goggles_lock);
goggles[num_goggles++] = num;
uthread_mutex_unlock(goggles_lock);
uthread_sem_signal(goggles_sem);
}
13
.
9d Kidsliketogettheirgearinanorderdifferentthanadults.Moreprecisely,thecodeusedtoforeachvisitoris
the following (note: line breaks in the call to printf were only added to make it fit this page):
void *visit_lab(void *param) {
person_t *person = (person_t *) param;
int goggles_no, coat_no, gloves_no;
if (person->age < 12) {
goggles_no = get_goggles();
coat_no = get_coat();
gloves_no = get_gloves();
}
else {
coat_no = get_coat();
gloves_no = get_gloves();
goggles_no = get_goggles();
}
printf("Person %d got into the lab using goggles #%d,
coat #%d, gloves #%d.", person->number,
goggles_no, coat_no, gloves_no);
usleep(random() % STALL);
printf(“Person %d got out of the lab.”, person->number);
return_goggles(goggles_no);
return_coat(coat_no);
return_gloves(gloves_no);
return 0; }
Each visitor runs in a separate thread. Is this code deadlock-free? If it is, explain why. If it is not, give a sequence of operations that will result in a deadlock, and explain how to fix the problem.
No it is not deadlock free.
Consider the case where there are two people, one under the age of 12, and one over the age of twelve.
If the thread with the person under the age of twelve acquires the goggles and is then interrupted, and the person over twelve acquires the coat and gloves, the person over twelve will not be able to progress until the gloves are free, and then person under the age of twelve will not be able to progress until the coat is free. This results in a deadlock.
There are a number of possible fixes. One would be to require all people to put on their gear in the same order, another would be to to add a lock around the whole area of code where a person gets their gear, so only one person can get gear at a time.
14
10 [5 marks] IO Devices. Based on your knowledge of how I/O devices communicate with the CPU, for the following I/O operations, circle what mechanism is better suited to transfer the information between the parties in the transaction.
10a TheCPUwantstogetthecurrenttimeofdayfromaclockdevice.
a. CPU sends PIO request with result obtained by polling
b. CPU sends PIO request with result obtained via DMA
c. CPU interrupts the clock’s controller
d. Clock device stores time in memory area shared with CPU
e. Clock device regularly interrupts CPU with new time, stored by CPU for future access
10b AscannerneedstosendanacquiredimagetotheCPUforprocessing.
a. CPU polls scanner controller for image
b. Scanner controller uses PIO to notify CPU
c. Scanner controller saves data in pre-arranged memory address and interrupts CPU
d. Scanner controller interrupts CPU, then CPU uses PIO to obtain data directly from scanner e. Scanner controller interrupts CPU, including the image as part of the interrupt process
10c AtouchscreenmonitorneedstonotifytheCPUthattheusertouchedonaparticularpositiononthescreen.
a. CPU periodically requests for last touched position
b. Monitor controller uses PIO to notify CPU
c. Monitor controller stores location in memory, CPU periodically checks memory for new touch d. Monitor controller interrupts CPU, which runs a pre-determined interrupt handler
e. Monitor controller changes a pre-determined register with the position of the last touch
10d TheCPUdecidestoturnofftheNumLockindicatoronthekeyboard.
a. CPU sends PIO request to the keyboard device
b. CPU changes a specific register associated to the indicator
c. CPU changes a specific memory location in main memory associated to the indicator d. CPU interrupts the keyboard controller requesting a change in indicator values
e. CPU halts until the user hits the Num Lock key
10e AUSBcontrollerneedstonotifytheCPUthatanewdevicehasbeenconnected.
a. CPU notifies the USB controller via PIO
b. USB controller interrupts the CPU, which runs a pre-determined interrupt handler
c. USB controller changes a memory location in main memory that is periodically checked by the CPU d. USB controller increments the value of a device counter register
e. CPU periodically requests the USB controller’s status, which changes when a device is connected
A, C, D, A, B
15
.
Use this page if you need additional space for any question. Clearly indicate which question you are answering in this page. Alternatively, you may use it for scratch work.
16
.
You may remove this page for reference.
void uthread_init (int num_processors);
uthread_t uthread_create (void* (*proc)(void*), void* arg);
void uthread_detach (uthread_t t);
int uthread_join (uthread_t t, void** vp);
uthread_t uthread_self ();
void uthread_yield ();
void uthread_block ();
void uthread_unblock (uthread_t thread);
uthread_mutex_t uthread_mutex_create ();
void uthread_mutex_destroy (uthread_mutex_t);
void uthread_mutex_lock (uthread_mutex_t);
void uthread_mutex_lock_readonly (uthread_mutex_t);
void uthread_mutex_unlock (uthread_mutex_t);
uthread_cond_t uthread_cond_create (uthread_mutex_t);
void uthread_cond_destroy (uthread_cond_t);
void uthread_cond_wait (uthread_cond_t);
void uthread_cond_signal (uthread_cond_t);
void uthread_cond_broadcast (uthread_cond_t);
uthread_sem_t uthread_sem_create (int);
void uthread_sem_destroy (uthread_sem_t);
void uthread_sem_wait (uthread_sem_t);
void uthread_sem_signal (uthread_sem_t);
17
.
These two tables describe the SM213 ISA. The first gives a template for instruction machine and assembly language and describes instruction semantics. It uses ’s’ and ’d’ to refer to source and destination register numbers and ’p’ and ’i’ to refer to compressed-offset and index values. Each character of the machine template corresponds to a 4-bit, hexit. Offsets in assembly use ’o’ while machine code stores this as ’p’ such that ’o’ is either 2 or 4 times ’p’ as indicated in the semantics column. The second table gives an example of each instruction.
Operation
Machine Language
Semantics / RTL
Assembly
load immediate load base+offset load indexed store base+offset store indexed halt
nop
0d– vvvvvvvv
1psd
2bid
3spd
4sdi
F000
FF00
r[d] ← vvvvvvvv
r[d] ← m[(o = p × 4) + r[s]] r[d] ← m[r[b] + r[i] × 4] m[(o = p × 4) + r[d]] ← r[s] m[r[b] + r[i] × 4] ← r[s] (stop execution)
(do nothing)
ld $vvvvvvvv,rd
ld o(rs),rd
ld (rb,ri,4),rd
st rs,o(rd)
st rs,(rb,ri,4)
halt
nop
rr move add and
inc
inc addr dec
dec addr not
shift
60sd
61sd
62sd
63-d
64-d
65-d
66-d
67-d
7dss
r[d] ← r[s]
r[d] ← r[d]
r[d] ← r[d]
r[d] ← r[d]
r[d] ← r[d]
r[d] ← r[d]
r[d] ← r[d]
r[d] ←!r[d]
r[d] ← r[d]
(if ss is negative)
+ r[s] & r[s] + 1
+ 4
− 1
− 4
<< ss
mov rs, rd
add rs, rd
and rs, rd
inc rd
inca rd
dec rd
deca rd
not rd
shl ss, rd
shr -ss, rd
branch
branch if equal branch if greater jump
8-pp
9rpp
Arpp
B--- aaaaaaaa
pc ← (a = pc + pp × 2)
ifr[r]==0: pc←(a=pc+pp×2) ifr[r]>0: pc←(a=pc+pp×2) pc ← a
br a
beq rr, a bgt rr, a ja
get program counter jump indirect
jump double ind, b+off jump double ind, index
6Fpd
Cdpp
Cdpp
Edi-
r[d]← pc+(o=2×p)
pc ← r[d]+(o = 2×pp)
pc ←m[(o=4×pp)+r[d]] pc ←m[4×r[i]+r[d]]
gpc $o, rd
j o(rd)
j *o(rd)
j *(rd,ri,4)
Operation
Machine Language Example
Assembly Language Example
load immediate load base+offset load indexed store base+offset store indexed halt
nop
0100 00001000
1123
2123
3123
4123
f000
ff00
ld $0x1000,r1
ld 4(r2),r3
ld (r1,r2,4),r3
st r1,8(r3)
st r1,(r2,r3,4)
halt
nop
rr move add and
inc
inc addr dec
dec addr not
shift
6012
6112
6212
6301
6401
6501
6601
6701
7102
71fe
mov r1, r2
add r1, r2
and r1, r2
inc r1
inca r1
dec r1
deca r1
not r1
shl $2, r1
shr $2, r1
branch
branch if equal branch if greater jump
1000: 8003
1000: 9103
1000: a103
b000 00001000
br 0x1008
beq r1, 0x1008
bgt r1, 0x1008
j 0x1000
get program counter jump indirect
jump double ind, b+off jump double ind, index
6f31
c104
d102
e120
gpc $6, r1
j 8(r1)
j *8(r1)
j *(r1,r2,4)
18