代写CS 537: Introduction to Operating Systems Fall 2023: Midterm Exam #2代写C/C++语言

2024.03.26 - 首页 >> CS

CS 537: Introduction to Operating Systems

Fall 2023: Midterm Exam #2

This exam is closed book, closed notes.

No calculators may be used. All cellphones must be turned off and put away.

You have 1 hour 30 minutes to complete this exam.

Write all of your answers on the accu-scan form. with a #2 pencil:

● CANVAS LAST NAME - fill in your last (family) name starting at the leftmost column

● CANVAS FIRST NAME - fill in the first five letters of your first (given) name

● IDENTIFICATION NUMBER - This is your UW Student WisCard ID number

● ABC of SPECIAL CODES - Write your lecture number as a three digit value:

○ 001 (Morning Lecture)

○ 002 (Afternoon Lecture)

○ 010 (Epic Lecture)

These exam questions must be returned at the end of the exam, but we will not grade anything in this booklet.

You may separate the pages of this exam if it helps you.

Unless stated (or implied) otherwise, you should make the following assumptions:

● The OS manages a single uniprocessor (single core)

● All memory is byte addressable

● The terminology lg means log2

● 210 bytes = 1KB

● 220 bytes = 1MB

● Data is allocated with optimal alignment, starting at the beginning of a page

● Assume leading zeros can be removed from numbers (e.g., 0x06 == 0x6).

● Hex numbers are represented with a proceeding “0x”

This exam has 68 questions. Each question has the same number of points.

Good luck!

Part 1. Designate if the statement is True (A) or False (B).

1. Threads that are part of the same process share the same stack.

2. Threads that are part of the same process share the same page table.

3. A context switch between threads of the same process requires flushing the TLB or tracking the ASID.

4. One advantage of multi-threaded programming is parallelism, allowing the program to take advantage of multiple CPUs.

5. Another advantage of multi-threaded programming is with IO-bound workloads since a thread can run the IO-bound instructions, not blocking the other threads.

6. Locks prevent the OS scheduler from performing a context switch during a critical section.

7. A lock implementation should always spin instead of block if it is known that the lock will always be used only on a uniprocessor.

8. A lock implementation on a multiprocessor should always spin instead of blocking if it is known that the lock will be available before the time of a context-switch.

9. A spin-wait type lock can provide fairness across the threads (i.e. threads receive the lock in the order they requested it).

10. When performing thread traces, you can assume locks will be acquired in the order they are requested.

11. Failing to surround a critical section of code with a lock may result in a deadlock situation.

12. A condition variable contains a queue of waiting threads.

13. While not required, it is best practice to hold the mutex lock when calling pthread_cond_wait().

14. While not required, it is best practice to hold the mutex lock when calling pthread_cond_signal().

15. The performance of broadcasting to a condition variable decreases as the number of waiting threads increases.

16. One can safely modify the state associated with a condition variable without holding the mutex lock.

17. When condition variable signaling follows Mesa semantics it is not necessary to recheck the program state when a thread returns from a wait().

18. It is always correct to use broadcast instead of signal when using Mesa semantics.

19. When a thread returns from a cond_wait() it is safe to assume that it holds the corresponding mutex lock.

20. In the attempted solution to the producer/consumer problem using a single condition variable, a

consumer thread may signal another consumer thread to awake which would cause corruption of the data in the buffer.

21. In the solution to the producer/consumer problem with a finite sized circular shared buffer, consuming threads must wait until there is an empty element of the buffer.

22. Semaphores can be used instead of mutex locks and instead of condition variables.

23. A semaphore used as a condition variable is called a binary semaphore.

24. To implement the thread_join operation with a semaphore, the semaphore is initialized to the value of 0 and the thread_exit() code calls sem_wait().

25. Deadlock can be avoided by using semaphores instead of locks for mutual exclusion.

26. A semaphore used to create mutual exclusion is initialized to 1.

27. In the approximate counter algorithm, the threshold parameter that controls the transfer from local to global counter controls the tradeoff between accuracy and performance.

28. Increasing the number of locks that are used to access a thread-safe data structure (like the

hashtable compared to the linked-list example from the book) is guaranteed to increase concurrency and performance.

29. With reader-writer locks as implemented in the textbook, a write thread must wait until all reader threads have released their lock. With many busy reader threads the writer thread may starve.

30. Livelock is when a thread holds a resource but can't acquire the remaining needed resources and so must release the resource it holds.

Part 2. Forks and Threads

Assume the following code is compiled and run on a modern Linux machine. Assume any irrelevant details have been omitted and that no routines, such as fork(), ever fail.

int a = 0;

int main () {

a++;

fork();

a++;

fork();

a++;

if (fork() == 0) {

printf("Hello!\n");

} else {

printf("Goodbye!\n");

}

a++;

printf("a is %d\n",a);

}

31. How many times will the message "Hello!\n" be displayed?

A. 2

B. 3

C. 4

D. 6

E. None of the above

32. What will be the final value of "a" as displayed by the final line of the program?

A. The value of "a" may be printed multiple times in different orders with different values. B. 4

C. 8

D. 13

E. None of the above

The next set of questions looks at creating new threads. For the next questions, assume the following code is compiled and run on a modern Linux machine. Assume irrelevant details have been omitted and that no routines, such as pthread_create() or pthread_join(), ever fail.

volatile int balance = 0;

void *mythread(void *arg) {

int result = 0;

result = result + 200;

balance = balance + 200;

printf("Result is %d\n", result);

printf("Balance is %d\n", balance);

return NULL;

}

int main () {

pthread_t p1, p2;

pthread_create (&p1, NULL, mythread, "A");

pthread_create (&p2, NULL, mythread, "B");

pthread_join (p1, NULL);

pthread_join (p2, NULL);

printf("Final Balance is %d\n", balance);

}

33. How many total threads are part of this process?

A. 1

B. 2

C. 3

D. 4

E. None of the above

34. When thread p1 prints "Result is %d\n", what value of result will be printed?

A. Due to race conditions, "result" may have different values on different runs of the program. B. 0

C. 200

D. 400

E. A constant value, but none of the above

35. When thread p1 prints "Balance is %d\n", what value of balance will be printed?

A. Due to race conditions, "balance" may have different values on different runs of the program. B. 0

C. 200

D. 400

E. A constant value, but none of the above

36. When "Final Balance is %d\n" is printed, what value of balance will be printed?

A. Due to race conditions, "balance" may have different values on different runs of the program. B. 0

C. 200

D. 400

E. A constant value, but none of the above

Part 3. Scheduling Without Locks (assembly code)

For the next questions, assume that two threads are running the following code on a uniprocessor (This is the same looping-race-nolocks.s code from homework simulations). This code is incrementing a variable (e.g. a shared balance) many times in a loop. Assume that the %bx register begins with the value 3, so that each thread performs the loop 3 times. Assume the code is loaded at address 1000 and that the

memory address 2000 originally contains the value 0.

# assumes %bx has loop count in it

.main

.top

# critical section

mov 2000, %ax

add $1, %ax

mov %ax, 2000

# see if we're

# get 'value' at address 2000

# increment it

# store it back

still looping

sub $1, %bx

test $0, %bx

jgt .top

halt

Assume that the scheduler runs the two threads producing the following order of instructions (the first column shows the address of the executed instruction) on the next page.

Thread 0 Thread 1

1000 mov 2000, %ax

1001 add $1, %ax