ECE 391 Exam 1, Spring 2010
Feb 24, 2010, 7–9 p.m.
Name
NetID
• Be sure that your exam booklet has 14 pages.
• Write your netid at the top of each page.
• This is a closed book exam.
• You are allowed one 8.5× 11″ sheet of notes.
• Absolutely no interaction between students is allowed.
• Show all of your work.
• The last page has a reference for the synchronization API
• Don’t panic, and good luck!
1
NetID: 2
Problem 1 26 points
Problem 2 8 points
Problem 3 12 points
Problem 4 18 points
Total 64 points
(You may use the rest of this page as scratch material)
NetID: 3
Problem 1 Short answer questions (26 points)
Answer the questions below and justify your answer. You should not need more than one or two
sentences for explanations.
a Calling conventions (10 points)
i Parameter ordering (4 points)
Consider the following function pro-
totype:
int test(int A, int B, int C);
Draw the parameters saved on the
stack in the correct order, as used
in the C calling convention covered
in class. Why is this order used?
return
address
ESP
increasing m
em
ory addresses
ii Stack vs. registers (4 points)
In assembly linkage, arguments are passed in registers, rather than the stack. Describe one advan-
tage and one disadvantage of this approach, as compared to the C calling convention.
iii System calls (2 points)
System calls pass arguments in registers. Explain why.
NetID: 4
b Version control (4 points)
In this class, you are using the subversion version control system. Please explain two (2) benefits
of using it.
c Concurrency problems (2 points)
Explain the difference between deadlock and livelock.
d Volatile (4 points) What does the volatile keyword in C mean? And why is it not used by
default on all variables?
NetID: 5
e Data sizes (6 points)
An image editing program allows each pixel to have 5-bit red, green, and blue values, as well as an
17-bit alpha (transparency) value for layered images. A programmer uses the following declaration:
struct pixel {
unsigned char red;
unsigned char green;
unsigned int alpha;
unsigned char blue;
};
i (2 points) The programmer computes the size of the data structure using sizeof(struct pixel).
To his surprise, the answer is 12 bytes. Can you explain to him why this is? (Assume you are
working on a 32-bit architecture.)
Suggest some changes that will let the programmer get this size down to:
ii 8 bytes (2 points)
iii 7 bytes (Bonus) (2 points)
iv 4 bytes (2 points)
NetID: 6
Problem 2 Synchronization (8 points)
The driver for your USB rocket launcher1 has been malfunctioning. You trace the problem to the
implementation of an ioctl call, listed below:
1 static int *buf1, *buf2;
2 static spinlock_t buf1_lock = SPIN_LOCK_UNLOCKED;
3 static DECLARE_MUTEX(buf2_mutex);
4
5 int usb_rocket_launcher_telemetry_ioctl() {
6 int i;
7 spin_lock(&buf1_lock); /* must check for valid pointer */
8 if(buf1 == NULL) /* after obtaining lock */
9 return -1;
10 down(&buf2_mutex); /* must check for valid pointer */
11 if(buf2 == NULL) /* after obtaining mutex */
12 return -1;
13 for(i=0; i<10; i++)
14 buf2[9-i]=buf1[i];
15 up(&buf2_mutex);
16 spin_unlock(&buf1_lock);
17 return 0;
18 }
You know from your experience that the buf1 variable is used by both system calls (as above) and
interrupts, and therefore is protected by a spinlock, whereas buf2 is only used in system calls, and
thus is protected by a mutex. Please explain all the errors in this code and how you would fix them.
(Note: you should look for errors related to synchronization only, and not, e.g., syntax errors.)
1Available from ThinkGeek
NetID: 7
Problem 3 Where’s Waldo (12 points)
Where’s Waldo (known outside of North America as Where’s Wally?) is a series of children’s books
that consist of full-page illustrations of hundreds of people in a frenzy of activity. The intent is for
the reader to find a character named Waldo who is hidden in the group. Waldo is always dressed
in a red/white horizontally striped shirt, a bobble red hat, and wears glasses.
Fed up with never finding Waldo as a child, your TA Chris has demanded that you write program
that finds Waldo for him. To help you along, Chris has written code that will take a Where’s Waldo
image and create a singly-linked linked list where each node holds information about each person.
The structure of a linked list node is:
typedef struct {
uint8_t r,g,b; /* RGB components of the hat color */
uint8_t glasses; /* 1 if glasses are present, 0 otherwise */
int32_t position;/* Position of the person relative to the image */
person_t* next; /* Pointer to the next person in the linked list */
} person_t;
The head of this linked list is found in the global variable people_list_head.
Assuming no compiler padding, write a function in x86 assembly to traverse the linked list of people,
determine if a “Waldo” is found, and return the position number. If a “Waldo” is not found, return
-1. To account for fashions of the future, your function should be general and take as an argument
a pointer to a person_t structure that describes Waldo’s attributes. The C function prototype is:
/* whereiswaldo()
* Description: Searches through the linked list of people to find if the
* waldo element is present in the list.
* Input: waldo - person_t struct that has the attributes of the person
* we want to find in the linked list.
* Returns: If the waldo element is found, return its position
* information relative to the image. If not found, return -1.
*/
int32_t whereiswaldo(person_t* waldo);
You can assume that the arguments passed in are valid types (No NULL checking or type checking
required). You may wish to write the function in C first, using the space provided. Your C code
will not be graded, it is for your convenience only.
NetID: 8
#typedef struct {
# uint8_t r,g,b; /* RGB components of the hat color */
# uint8_t glasses; /* 1 if glasses are present, 0 otherwise */
# int32_t position;/* Position of the person relative to the image */
# person_t* next; /* Pointer to the next person in the linked list */
#} person_t;
.global people_list_head
whereiswaldo:
NetID: 9
(you can write your C code here)
NetID: 10
Problem 4 Boy/Girl Locks (18 points)
You must write a lock that guards access to a shared bathroom. The bathroom may be used by
several people at the same time, as long as they are of the same gender; however, mixing genders is
never allowed. The data structure representing the lock has been filled in for you, please complete
the code. Note: your code must allow for multiple people to use the bathroom, as long as they
are of the same gender.
a Implementation (15 points)
#define BOY 0
#define GIRL 1
typedef struct {
spinlock_t lock;
int count[2];
} boygirl_lock_t;
void boygirl_lock_init(boygirl_lock_t *lock) {
}
void boygirl_lock(boygirl_lock_t *lock, int gender) {
}
NetID: 11
void boygirl_unlock(boygirl_lock_t *lock, int gender) {
}
b Starvation (3 points)
Does your implementation allow starvation to occur? Explain.
NetID: 12
NetID: 13
You may tear off this page to use as a reference
Synchronization API reference
spinlock_t lock; Declare an uninitialized spinlock
spinlock_t lock1 = SPIN_LOCK_UNLOCKED; Declare a spinlock and initialize it
spinlock_t lock2 = SPIN_LOCK_LOCKED;
void spin_lock_init(spinlock_t* lock); Initialize a dynamically-allocated spin lock
(set to unlocked)
void spin_lock(spinlock_t *lock); Obtain a spin lock; waits until available
void spin_unlock(spinlock_t *lock); Release a spin lock
void spin_lock_irqsave(spinlock_t *lock, Save processor status in flags,
unsigned long& flags); mask interrupts and obtain spin lock
(note: flags passed by name (macro))
void spin_lock_irqrestore(spinlock_t *lock, Release a spin lock, then set
unsigned long flags); processar status to flags
struct semaphore sem; Declare an uninitialized semaphore
static DECLARE_SEMAPHORE_GENERIC (sem, val); Allocate statically and initialize to val
DECLARE_MUTEX (mutex); Allocate on stack and initialize to one
DECLARE_MUTEX_LOCKED (mutex); Allocate on stack and initialize to zero
void sema_init(struct semaphore *sem, int val); Initialize a dynamically allocated semaphore to val
void init_MUTEX(struct semaphore *sem); Initialize a dynamically allocated semaphore to one.
void init_MUTEX_LOCKED(struct semaphore *sem); Initialize a dynamically allocated semaphore to zero.
void down(struct semaphore *sem); Wait until semaphore is available and decrement (P)
vod up(struct semaphore *sem); Increment the semaphore
NetID: 14
x86 reference
AX
AL
BL
CL
DL
low
31
AH AL
EAX
8 016 15 7
8−bit
AH
BH
CH
DH
high
EAX
EBX
ECX
EDX
ESI
EDI
EBP
ESP
32−bit
AX
BX
CX
DX
SI
DI
BP
SP
16−bit
jb below CF is set
jbe below or CF or ZF
equal is set
je equal ZF is set
jl less SF 6= OF
jle less or (SF 6= OF) or
equal ZF is set
jo overflow OF is set
jp parity PF is set
(even parity)
js sign SF is set
(negative)
movb (%ebp),%al # AL ← M[EBP]
movb -4(%esp),%al # AL ← M[ESP - 4]
movb (%ebx,%edx),%al # AL ← M[EBX + EDX]
movb 13(%ecx,%ebp),%al # AL ← M[ECX + EBP + 13]
movb (,%ecx,4),%al # AL ← M[ECX * 4]
movb -6(,%edx,2),%al # AL ← M[EDX * 2 - 6]
movb (%esi,%eax,2),%al # AL ← M[ESI + EAX * 2]
movb 24(%eax,%esi,8),%al # AL ← M[EAX + ESI * 8 + 24]
movb 100,%al # AL ← M[100]
movb label,%al # AL ← M[label]
movb label+10,%al # AL ← M[label+10]
movb 10(label),%al # NOT LEGAL!
movb label(%eax),%al # AL ← M[EAX + label]
movb 7*6+label(%edx),%al # AL ← M[EDX + label + 42]
movw $label,%eax # EAX ← label
movw $label+10,%eax # EAX ← label+10
movw $label(%eax),%eax # NOT LEGAL!
call printf # (push EIP), EIP ← printf
call *%eax # (push EIP), EIP ← EAX
call *(%eax) # (push EIP), EIP ← M[EAX]
call *fptr # (push EIP), EIP ← M[fptr]
call *10(%eax,%edx,2) # (push EIP), EIP ←
# M[EAX + EDX*2 + 10]
Conditional branch sense is inverted by inserting an “N” after initial “J,” e.g., JNB. Preferred forms in
table below are those used by debugger in disassembly. Table use: after a comparison such as
cmp %ebx,%esi # set flags based on (ESI - EBX)
choose the operator to place between ESI and EBX, based on the data type. For example, if ESI and
EBX hold unsigned values, and the branch should be taken if ESI ≤ EBX, use either JBE or JNA. For
branches other than JE/JNE based on instructions other than CMP, check the branch conditions above
instead.
preferred form
jnz
jne
jnae
jb
jna
jbe
jz
je
jnb
jae
jnbe
ja
unsigned comparisons
6= < ≤ = ≥ >
preferred form jne
jnz
jl
jnge
jle
jng
je
jz
jge
jnl
jg
jnle
signed comparisons