CS计算机代考程序代写 x86 data structure compiler js concurrency assembly ECE 391 Exam 1, Spring 2010

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