ECE391 Exam 1, Fall 2021, CONFLICT Wednesday 29 September
• Write your name at the top of each page.
• This is a closed book exam.
• You are allowed TWO 8.5 × 11″ sheet of notes.
Copyright By PowCoder代写 加微信 powcoder
• Absolutely no interaction between students is allowed. • Show all of your work.
• Reference page(s) are attached at the end of the exam. • Don’t (kernel) panic, and good luck!
Name and NetID:
Problem 1 Problem 2 Problem 3 Problem 4 Problem 5
20 points 17 points 22 points 21 points 18 points
Name: 2 Problem 1 (20 points): Short Answer
Part A (4 points): List TWO roles of system software. Please use ONE WORD for each role. We mentioned three such roles in the lecture.
PartB(3points): Thex86usesasinglevectortablecalledtheInterruptDescriptorTable,orIDT,forTHREE types of ”interruptions”. Please list them.
PartC(3points): Assumethefollowingcodeisbeingexecutedonauniprocessor,USINGNOMORETHAN
TWENTY WORDS, explain what are the unnecessary parts of the following code.
spin_lock(&the_lock);
/* critical section code */
spin_unlock(&the_lock);
PartD(4points): Recalltheuser-leveltestharnessprovidedtoyouforMP1(thetestharnessthatsimulatesthe test machine’s environments). USING NO MORE THAN FIFTEEN WORDS EACH, explain one advantage and one disadvantage of developing and using such a harness compared with debugging fully inside the Linux kernel.
ADVANTAGE:
DISADVANTAGE:
PartE(2points): IDENTIFYthebug(s)inthefollowingsnippetofcodeforthedispatcherfunctionfromMP1 and CORRECT the bug(s).
mp1_ioctl:
cmpl $4, 8(%ebp)
ja invalid_cmd
movl 8(%ebp), %eax
jmp *jump_table(,%eax,4)
invalid_cmd:
movl $-1, %eax
Part F (4 points): Assume that in order to access shared data your program needs to acquire a spinlock and a semaphore at the same time. USING NO MORE THAN THIRTY WORDS, explain which primitive should you acquire first and why.
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Name: 4 Problem 2 (17 points): MP1
Parts A, B, C refers to the following function.
Consider a function foo which makes use of a jump table similarly to mp1 ioctl from MP1. The following is a
specification of the function.
int foo(int arg, int cmd);
you can assume that 10 >= arg && arg >= 0
if cmd==0, return arg
if cmd==1, return arg + 1
otherwise, return 0
The following implementation of the function foo has a bug.
movl 8(%esp),%eax
cmpl $1,%eax
ja cmd_invalid
call *jump_table(,%eax,4)
cmd_invalid:
movl $0,%eax
jump_table:
.long bar, baz
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %ecx
movl %ecx, %eax
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %ecx
addl $1, %ecx
movl %ecx, %eax
Name: 5 Problem 2, continued:
Part A (3 points): Suppose you called the function foo in the main function with the following line without fixing the bug.
int result=foo(1, 1);
What is the value stored in result after returning from foo?
PartB(3points): Fixthebugbymodifyingoneline.Indicatethenumberofthelineyouwouldfixandwritethe modified instruction.
Line Number:
Instruction:
Name: 6 Problem 2, continued:
PartC(4points): Afterfixingthebug,youwereaskedtoextendthefunctionalityoffoosothatitsatisfiesthe following specification.
int foo(int arg, int cmd);
if cmd==2, return arg + 7
for any other cmd, behave exactly the same as the previous version of foo
To extend the functionality of foo, you implemented the following function quz and attached it below the implemen- tation of baz.
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %ecx
addl $7, %ecx
movl %ecx, %eax
Besides implementing and attaching quz, what are the two changes you should make in foo? Indicate the line number where you would make the change and the modified instruction.
Line Number:
Instruction:
Line Number:
Instruction:
Name: 7 Problem 2, continued:
Part D, E are independent of the previous parts.
PartD(4points): YourfriendisstrugglingwithanissueonMP1wherethemissilesareflickeringoccasionally. You suspect that the faulty implementation of mp1 addmissile is causing the bug. Place the following steps in the right order so that your friend can resolve the issue(write down the alphabet in the right order).
(a) Copy missile data from the user space to the kernel space (b) Set the head pointer to the new node
(c) Allocate memory for the missile structure
(d) Set the next pointer of the new node to the head
First step:
Second step:
Third step:
Fourth step:
PartE(3points): ConsideranalternativeimplementationofmissilecommandgameasinMP1,butwith10rows, each row being 20 characters wide. That is, the screen has row 0 through row 9 and column 0 through column 19. Suppose you wish to modify the ascii code located at row 6, column 12. If the video memory starts at 0x00000000, what is the memory address you would modify?
Name: 8 Problem 3 (20 points): x86 Assembly
The k-means Clustering algorithm is used widely to partition N data points into k clusters. The algorithm can be divided into two steps that are repeated until desired. They are:
1. Assignment: Assign each data point to a cluster based on a distance metric to the nearest mean 2. Update: Update the mean point for each cluster
The C code below implements the k-means algorithm.
Note that the arrays data, means and assignments are declared globally and visible to all functions.
#define ITERATIONS
#define K 10
#define N 200
// HINT: the packed attribute ensures no extra padding. In other words,
// size of the struct will be the sum of the size of all data
// that are defined in the struct
typedef struct __attribute__((__packed__)) point_t {
uint8_t data;
} point_t;
point_t data[N];
point_t means[K];
int32_t assignments[N];
void kmeans() {
register int32_t i; // register keyword insures the variable
is stored in the register, not on the stack
for (i = 0; i < ITERATIONS; i++) {
assign_clusters();
update_means();
Name: 9 Problem 3, continued:
01. void assign_cluster() {
19. void update_means() {
int32_t i;
uint32_t j, mean_data, count;
for (i = 0; i < K; i++) {
mean_data = 0;
count = 0;
for (j =0;j
dogcoin_amount -= MINE_COST;
num_mining++;
(7)_______________________________________
amount_mined += mine_func();
(8)_______________________________________
(9)_______________________________________
(10)______________________________________
spin_unlock(lock);
return (11)_______________________________;
else if (dogcoin_amount <= 0 &&
(12)_______________________________________){
spin_unlock(lock);
return -1;
spin_unlock(lock);
Problem 5 (18 points): Programmable Interrupt Controller
PartA(6points): Foreachofthefollowingsignalsonaslave8259APICchipinacascadesetupwheretheslave is connected to IR 4 on the master and they each has some devices connected, explain what will happen if each of the following signal gets shorted individually such that it always reads low. In each case only the single signal being considered is malfunctioning and all other signals are working properly. For full points, explain how it will impact the functioning of the devices / other PICs connected. (20 words maximum each)
2. the lowest bit in CAS:
PartB(3points): Benfoundabasketofold8259APICchipsinthebasement.Someofthemareonlypartially working with broken IR pins (Interrupt Request pins). What’s the maximum number of devices we can handle, with a cascade scheme, if we have 4 8259A PIC chips with 8 interrupt ports fully functional, 9 chips with 4 interrupt ports functional and 11 chips with only 2 interrupt ports functional? Write down your calculation if applicable.
Show your work:
Maximum Number:
Part C (3 points): After the calculation, Ben found that he had more devices than the maximum number of devices that his PICs can support. He had an observation: the devices he had all come in pairs, such that both devices in every pair always send interrupts at the exact same time. With this observation, he came up with an idea - solder the interrupt pins of each pair of devices to the inputs of an AND gate and connect the output of the AND gate to the same IRQ pin on one of the PICs in the cascade layout.
Given that both devices in every pair always send interrupts at the exact same time, will Ben’s novel scheme work?
CIRCLE ONE: Yes No
If yes, can you find a way to generalize this idea to support even more devices? e.g., double the number of devices Ben has such that each device can be put in a foursome which always interrupt at the same time within the group of four. If no, explain the reason and include the key signal/mechanism which makes it impossible.
PartD(6points): TwoPICsareputinacascadesetup,bothoperatinginthefixedprioritymode(IR0-IR7,high to low priorities), with the slave connected to the IRQ pin 5 on the master. The table below shows how a list of devices are connected to the PICs.
Mouse Keyboard Printer Network Card Hard Drive Monitor
IR3 on IR5 on IR8 on IR2 on IR7 on IR2 on
Slave Slave Master Slave Master Master
to the system.
At the following timestamps, the devices send interrupts
Mouse 40ms Keyboard 55ms Printer 25ms Network Card 120ms Hard Drive 35ms Monitor 120ms
Assuming each interrupt request takes exactly 20ms to handle, please fill in the table below for the timestamp when the interrupt handling from each device will be finished.
Your answer:
Mouse Keyboard Printer Network Card Hard Drive Monitor
Part of the Linux Kernel Synchronization API Tear off this page, but return it with your exam.
void spin lock (spinlock t* lock);
void spin lock irq (spinlock t* lock);
void spin lock irqsave (spinlock t* lock, unsigned long& flags);
void spin unlock (spinlock t* lock);
void spin unlock irq (spinlock t* lock);
void spin unlock irqrestore (spinlock t* lock, unsigned long flags);
void down (struct semaphore* sem);
void up (struct semaphore* sem);
void read lock (rwlock t* rw);
void read lock irq (rwlock t* rw);
void read lock irqsave (rwlock t* rw, unsigned long& flags);
void read unlock (rwlock t* rw);
void read unlock irq (rwlock t* rw);
void read unlock irqrestore (rwlock t* rw, unsigned long flags);
void write lock (rwlock t* rw);
void write lock irq (rwlock t* rw);
void write lock irqsave (rwlock t* rw, unsigned long& flags);
void write unlock (rwlock t* rw);
void write unlock irq (rwlock t* rw);
void write unlock irqrestore (rwlock t* rw, unsigned long flags);
void down read (struct rw semaphore* sem); void down write (struct rw semaphore* sem); void up read (st
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com