CS代考 ECE 391 Final, Fall 2012

ECE 391 Final, Fall 2012

Saturday, Dec 15, 2012

Discussion Section:

• Be sure that your exam booklet has 13 pages.

• Write your net ID at the top of each page.

• This is a closed book exam.

• You are allowed three 8.5× 11″ sheet of notes.

• No other materials are allowed

• Answers to questions must be precise, but need not be
closed form. (E.g., 2 · 3 + 7·11

is acceptable.)

• Absolutely no interaction between students is allowed.

• Show all of your work.

• Don’t panic, and good luck!

NetID: ECE 391, Final Fall 2012

Page Points Score

Page 2 of 13

NetID: ECE 391, Final Fall 2012

Question 1: Short Answer (28 points)
Please answer concisely. If you find yourself writing more than a sentence or two, your answer
is probably wrong.

(a)(2) What is the difference between masking a signal and ignoring it?

(b)(3) In what cases is it useful to force a program to receive a particular signal, even though
the program has asked that the signal be masked out?

(c)(4) When does a signal get generated? Check all that apply.

(d)(2) When does a signal get delivered? Circle best option.

A. During a kill system call

B. After a timer interrupt

C. After any interrupt

D. When the receiving process gets scheduled

Points: /11 Page 3 of 13

NetID: ECE 391, Final Fall 2012

(e)(4) Describe one advantage and one disadvantage of lazy algorithms, such as those used for
demand paging.

(f)(2) Explain what this code does:

movl %cr3,%eax

movl %eax,%cr3

(g)(3) When would you want to use the above code? Explain why.

Points: /9 Page 4 of 13

NetID: ECE 391, Final Fall 2012

(h)(4) When does the CPU set the accessed and dirty flags in the page table? And how are they
used by the operating system?

(i)(2) Which of these is typically the smallest?

A. Rotational latency

B. Seek latency

C. Transfer latency

(j)(2) The use of block groups in EXT2 is primarily to reduce:

A. Rotational latency

B. Seek latency

C. Transfer latency

D. Internal fragmentation

Points: /8 Page 5 of 13

NetID: ECE 391, Final Fall 2012

Question 2: MP3 (11 points)

(a)(5) Your MP3 partner implemented the following system call entry routine:

1 syscall_enter:

4 decl %eax # eax=eax-1

5 cmpl $10,%eax

6 jae badcall

7 cmpl $0,%eax

8 jb badcall

9 pushl %ebp

10 pushl %edi

11 pushl %esi

12 pushl %edx

13 pushl %ecx

14 pushl %ebx

15 call *jump_table(,%eax,4)

16 popl %ebx

17 popl %ecx

18 popl %edx

19 popl %esi

20 popl %edi

21 popl %ebp

22 exit: popfl

24 badcall:

25 movl $-1, %eax

26 jmp exit

You realize that some of the code in here is redundant and can be eliminated. Explain
what you would remove and why. (You may use the next page to continue your answer)

Points: /5 Page 6 of 13

NetID: ECE 391, Final Fall 2012

(b)(2) What’s the best way to avoid synchronization conflicts that may arise when accessing the
MP3 file system?

(c)(4) To implement terminal switching, your partner created a separate buffer for each termi-
nal. When switching terminals, the contents of the screen gets copied into the previous
terminal’s buffer, and the contents of the new terminal’s buffer gets copied onto the screen.

To make this work, you also need to update process page tables of the process during a
terminal switch. Explain what you need to change and why. Be detailed.

Points: /6 Page 7 of 13

NetID: ECE 391, Final Fall 2012

Question 3: Synchronization (14 points)
Below is an implementation of synchronization using wait queues.

char pipe_buf[4096];

unsigned int head, size;

DECLARE_MUTEX(pipe_lock);

DECLARE_WAIT_QUEUE_HEAD(readQ);

DECLARE_WAIT_QUEUE_HEAD(writeQ);

void init_pipe(void) {

down(&pipe_lock);

up(&pipe_lock);

/* read single char */

void write(char c) {

down(&pipe_lock);

DECLARE_WAIT(wait);

while (1) {

/* add self to wait queue */

prepare_to_wait(&writeQ, &wait, TASK_UNINTERRUPTIBLE);

if (size < 4096) /* go to sleep (potentially) */ schedule(); /* remove self from queue */ finish_wait(&writeQ, &wait); pipe_buf[(head + size) % 4096] = c; wake_up(&readQ); /* wake up one sleeping reader */ up(&pipe_lock); Page 8 of 13 NetID: ECE 391, Final Fall 2012 char read(void) { DECLARE_WAIT(wait); down(&pipe_lock); while (1) { /* add self to wait queue */ prepare_to_wait(&readQ, &wait, TASK_UNINTERRUPTIBLE); if (size > 0)

/* go to sleep (potentially) */

schedule();

/* remove self from queue */

finish_wait(&readQ, &wait);

c = pipe_buf[head];

head = (head + 1) % 4096;

wake_up(&writeQ); /* wake up one sleeping writer */

up(&pipe_lock);

(a)(3) There is a critical mistake in how the wait queues are used. What is it?

(b)(2) Why is a while(1) loop used? Explain how a writer could end up going to sleep multiple

(c)(3) wake_up wakes up a single waiting task (i.e., it is similar to notify). What would happen
if wake_up_all (equivalent to broadcast) were used instead?

Points: /8 Page 9 of 13

NetID: ECE 391, Final Fall 2012

(d)(6) Re-implement the scheme using two semaphores. Complete the code below.

char pipe_buf[4096];

int head, size;

DECLARE_MUTEX(pipe_lock);

struct semaphore readsem, writesem;

void init() {

down(&pipe_lock);

sema_init(&readsem, 0);

sema_init(&writesem, 4096);

up(&pipe_lock);

void write(char c) {

char read(void) {

Points: /6 Page 10 of 13

NetID: ECE 391, Final Fall 2012

Question 4: Scheduling (21 points)
Consider the following set of processes:

Process Arrival time Run time

(a)(8) Show the scheduling order of these processes under the following schedulers:

• First-in First-out (FIFO)
• Shortest remaining time first (SRT)
• Round-robin with a quantum of 2 time units (RR)

Assume that the context switch overhead is 0 and, all else being equal, new processes
should be scheduled first. A process arriving at time t can first be scheduled for slot t

Time Slot FIFO SRT RR

(b)(4) Calculate the turnaround time of each process, as well as the average.

Scheduler A B C D Average

Points: /12 Page 11 of 13

NetID: ECE 391, Final Fall 2012

(c)(6) For each scheduler, explain one advantage of using it.

(d)(3) Explain the tradeoff in selecting the round-robin quantum size. In particular, what benefit
do you get from increasing or decreasing the quantum?

Points: /9 Page 12 of 13

You may tear off this page ECE391 Fall 2012

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)
void up(struct semaphore *sem); Increment the semaphore
struct rw_semaphore rwsem; Declare an uninitialized reader/writer semaphore
void init_rwsem(struct rw_semaphore *rwsem); Initialize a reader/write semaphore
void down_read(struct rw_semaphore *rwsem); Obtain the semaphore for reading/
void down_write(struct rw_semaphore *rwsem); writing
void up_read(struct rw_semaphore *rwsem); Release the semaphore after reading/
void up_write(struct rw_semaphore *rwsem); writing

Page 13 of 13

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts