Midterm 2: Concurrency
Due Mar 25 at 9:15pm Points 134 Ques!ons 45 Available a!er Mar 25 at 7:15pm
Time Limit None Instruc!ons
This exam is open book, open notes.
When you begin the exam, you will need to agree with the following statements:
I understand that this exam must be worked on independently.
During this exam, I may consult personal notes, the OSTEP book, and the lecture slides that were posted on the course web site. I will not communicate or collaborate with any others during the exam in any way; for example:
I will not search for any informa!on on-line (beyond the lecture notes and OSTEP book that have been provided) I will not read or write any on-line shared documents
I will not chat, text, or post any ques!ons or informa!on
I will not ask for, receive, or provide help to others
I will no!fy the instructor if I am aware of others viola!ng this policy.
Unless stated (or implied) otherwise, you should make the following assump#ons:
All memory is byte addressable
The terminology lg means log2
210 bytes = 1KB; 220 bytes = 1MB
Page table entries require 4 bytes
Data is allocated with op#mal alignment, star#ng at the beginning of a page Leading zeros can be removed from numbers (e.g., 0x06 == 0x6)
Hex numbers are represented with a preceding ¡°0x¡±
Assume all code compiles; ignore any syntac#c errors; ignore any capitaliza#on errors.
You have two hours to complete this exam. The exam will “auto-submit” at the deadline if you have not submi”ed your exam before then.
You will see only one ques#on at a #me and cannot go back and change any answers a!er you have submi”ed them.
You should answer ques#ons as wri”en to the best of your ability; we will not further define terms or explain what is meant by a ques#on. If a True/False statement does not make sense, then it is probably False!
If you have a problem during the exam, please post privately to Instructors Only in Piazza.
To help you pace yourself, we want you to know that this exam is similar in length to the Fall 2019 prac#ce exam; this exam is structured approximately as follows:
T/F Ques#ons:
Virtualiza#on: Approx. 20 ques#ons [20 points] Concurrency: Approx. 20 ques#ons [40 points]
Mul#-Part Ques#ons
Fork() and Processes [18 points] Threads [9 points]
Join() Code [14 points] Producer/Consumer Code [16 points] Dining Philosophers Code [18 points]
Good luck!
A”empt History
A”empt LATEST A”empt 1
Time
119 minutes
Score
93 out of 134
Correct!
Ques!on 1
1 / 1 pts
Before beginning this exam, please read and agree to the following statement:
I understand that this exam must be worked on independently.
During this exam, I may consult personal notes and the lecture slides that were posted on the course web site.
I will not communicate or collaborate with others in any way; for example:
I will not search for any informa!on on-line (beyond the lecture notes that have been provided) I will not read or write any shared documents
I will not chat or post any ques!ons or informa!on
I will not ask for, receive, or provide help to others
I will no!fy the instructor if I am aware of others viola!ng this policy.
True False
Correct Answer You Answered
Correct Answer You Answered
You Answered Correct Answer
You Answered Correct Answer
Correct!
Correct Answer You Answered
Correct!
Correct!
Correct!
Correct!
Correct!
Correct Answer You Answered
Correct!
Correct!
Correct!
Correct Answer You Answered
You Answered Correct Answer
Correct!
You Answered Correct Answer
Correct Answer You Answered
Ques!on 2
0 / 1 pts
Ques!on 3
0 / 1 pts
Ques!on 4
0 / 1 pts
Ques!on 5
0 / 1 pts
Ques!on 6
1 / 1 pts
Ques!on 7
0 / 1 pts
Ques!on 8
1 / 1 pts
Ques!on 9
1 / 1 pts
Ques!on 10
1 / 1 pts
Ques!on 11
1 / 1 pts
Ques!on 12
1 / 1 pts
Ques!on 13
0 / 1 pts
Ques!on 14
1 / 1 pts
Ques!on 15
1 / 1 pts
Ques!on 16
1 / 1 pts
Ques!on 17
0 / 1 pts
Ques!on 18
0 / 1 pts
Ques!on 19
1 / 1 pts
Ques!on 20
0 / 1 pts
Ques!on 21
0 / 1 pts
Ques!on 22
2 / 2 pts
Score for this quiz: 93 out of 134 Submi”ed Mar 25 at 9:15pm This a”empt took 119 minutes.
True/False: Virtualizing the CPU and Memory
You will start with approximately 20 ques#ons about virtualizing the CPU and Memory. Each ques#on is worth 1 point.
Designate if each statement is True or False.
When a #mer interrupt is handled, the processor privilege mode is set to kernel mode.
True False
A MLFQ scheduler performs RR within each priority level.
True False
A lo”ery scheduler takes #ckets away from a job each #me that job is scheduled.
True False
With true mul#-tasking, the OS will context-switch between user processes on every #mer interrupt.
True False
When a #mer interrupt occurs, the current values of all hardware registers are saved onto the kernel stack.
True False
A child process is in the ZOMBIE state a!er it has called exit() and before its parent has called wait().
True False
SJF is an example of a scheduling mechanism.
True False
A!er the fork() system call, the parent and child process will share the same address space un#l the child calls exit().
True False
One of the goals of an SJF scheduler is to give a propor#onal share of the CPU to compe#ng jobs.
True False
With a MLFQ scheduler, a process at one priority may preempt a process at the same priority.
True False
Given simple segmenta#on, if the stack segment of a process must grow and there is insufficient free space in physical memory adjacent to the stack segment, the user process can specify a new star#ng loca#on for the stack in physical memory.
True False
With simple linear page tables, given a 32-bit virtual address, 2KB pages, and 8 byte page table entries, each page table could require up to 16MB.
True False
Thrashing can o!en be reduced by decreasing the number of ac#ve processes.
True False
With simple linear page tables, when a user process extends its heap, the OS will allocate more pages for that process.
True False
With simple linear page tables, when the OS creates a new process with some valid virtual addresses between 0x00000000 and 0xffffffff, the OS must allocate a PTE for every page in that full range.
True False
Given simple paging, a 32-bit virtual and physical address, and 4KB pages, it is possible for a page to start in physical memory at physical address 0x80cba000.
True False
If a TLB miss occurs, a vic#m page, that will be replaced in physical memory, must be chosen.
True False
On a context-switch, the contents of the TLB are typically stored by hardware into the kernel stack of a process.
True False
LRU page replacement may have fewer page misses than OPT.
True False
With the base+bounds approach for dynamic reloca#on, the address space of a process must be allocated con#guously in physical memory.
True False
True/False: Concurrency
Congratula#ons: You have finished the True/False ques#ons about Virtualiza#on.
You will now have approximately 20 ques#ons about how Concurrency. Each ques#on is worth 2 points.
Designate if each statement is True or False.
Correct!
Ques!on 23
0 / 2 pts
Correct Answer You Answered
Correct Answer You Answered
You Answered Correct Answer
Correct!
Correct!
Correct!
Correct!
Correct Answer You Answered
Correct!
You Answered Correct Answer
You Answered Correct Answer
Correct!
Correct!
Correct!
Correct!
You Answered Correct Answer
Correct!
You Answered Correct Answer
Ques!on 24
0 / 2 pts
Ques!on 25
0 / 2 pts
Ques!on 26
2 / 2 pts
Ques!on 27
2 / 2 pts
Ques!on 28
2 / 2 pts
Ques!on 29
2 / 2 pts
Ques!on 30
0 / 2 pts
Ques!on 31
2 / 2 pts
Ques!on 32
0 / 2 pts
Ques!on 33
0 / 2 pts
Ques!on 34
2 / 2 pts
Ques!on 35
2 / 2 pts
Ques!on 36
2 / 2 pts
Ques!on 37
2 / 2 pts
Ques!on 38
0 / 2 pts
Ques!on 39
2 / 2 pts
Ques!on 40
0 / 2 pts
Ques!on 41
18 / 18 pts
In this ques#on you will determine the output from an applica#on that calls fork() mul#ple #mes. Assume the following code is successfully compiled and executes with no errors.
volatile int a = 0;
main() {
int b = 0;
if (fork() == 0) {
a++;
printf(“C\n”);
} else {
b++;
printf(“D\n”);
}
if (fork() == 0) {
a++;
printf(“E\n”);
} else {
b++;
printf(“F\n”);
}
printf(“Done\n”);
printf(“a: %d\n”, a);
printf(“b: %d\n”, b);
printf(“a+b: %d\n”, a+b);
}
What will the applica#on print when it is run? If any answer is unknown due to race condi#ons or different scheduling possibili#es, write UNKNOWN. Otherwise, your answers should be simple integers.
1 1
2 2
4
How many #mes will “C” be printed?
How many #mes will “D” be printed?
How many #mes will “E” be printed?
How many #mes will “F” be printed?
How many #mes will “Done” be printed?
What is the minimum value of a that will be printed across all processes? What is the maximum value of b that will be printed across all processes? What is the minimum value of a+b that will be printed across all processes? What is the maximum value of a+b that will be printed across all processes?
Answer 1:
1
Answer 2:
1
Answer 3:
2
Answer 4:
2
Answer 5:
4
Answer 6:
0
Answer 7:
2
Answer 8:
2
Answer 9:
0 2
2 2
2
Ques!on 42
In this ques#on you will determine the output from an applica#on that creates mul!ple threads.
Assume the following code is successfully compiled.
volatile int balance = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void *add(void *arg) {
for (int i = 0; i < 500; i++) {
pthread_mutex_lock(&mutex);
balance++;
pthread_mutex_unlock(&mutex);
}
printf(¡°ADD Balance is %d\n¡±, balance);
return NULL;
}
void *sub(void *arg) {
pthread_mutex_lock(&mutex);
for (int i = 0; i < 200; i++) {
balance--; }
pthread_mutex_unlock(&mutex);
printf(¡°SUB Balance is %d\n¡±, balance);
return NULL;
}
int main(int argc, char *argv[]) {
pthread_t p1, p2;
pthread_create(&p1, NULL, add, ¡°A¡±);
pthread_create(&p2, NULL, sub, ¡°B¡±);
pthread_join(p1, NULL);
pthread_join(p2, NULL);
9 / 9 pts
One of the reasons it is be"er to divide an applica#on into mul#ple threads instead of into mul#ple processes is that the context-switch cost across threads is lower than that across processes.
True False
With a non-determinis#c applica#on, one could get different results (output) when the applica#on is run with the exact same inputs.
True False
If two threads in the same process access the same virtual address, they will read/write the same memory loca#on.
True False
If two threads in the same process access the same general-purpose hardware register, they will read/write the same register.
True False
The OS scheduler knows when a process is spin-wai#ng for a lock.
True False
A #cket lock implementa#on in which a thread t1 calls yield(), when it is not yet t1's turn to acquire the lock, ensures that the thread holding the lock is scheduled instead.
True False
Ticket locks guarantee that no process will starve when wai#ng to acquire a lock.
True False
On a mul#-processor system, if a lock will be held for a very short period of #me, then threads should generally block while they wait for the lock.
True False
Two different condi#on variables can be associated with the same lock (mutex); that is, wait could be called on two different condi#on variables when the same lock is held.
True False
When a semaphore is used as a lock, the value of the semaphore is ini#alized to TRUE.
True False
In a mul#-threaded applica#on with condi#on variables, a!er a thread returns from cond_wait(&cv, &mutex) it can assume that the situa#on it was wai#ng for is now true.
True False
When using a condi#on variable as a lock, the value of the condi#on variable is generally ini#alized to 1 (or true).
True False
Each condi#on variable must have an associated lock (or mutex).
True False
In applica#ons with mul#ple producer and consumer threads opera#ng on a shared array, the number of producers should equal the number of elements in the array.
True False
In applica#ons with mul#ple producer and consumer threads opera#ng on a shared array, the number of producers should equal the number of consumers.
True False
In the Dining Philosophers Synchroniza#on problem, no two neighbors can be THINKING at the same #me.
True False
In the Dining Philosophers Synchroniza#on problem, no two neighbors can be HUNGRY at the same #me.
True False
In applica#ons with mul#ple producer and consumer threads opera#ng on a shared array, each consumer must grab a unique empty element of the array.
True False
Deadlock will always occur if thread A acquires two locks X and Y in the order X, Y and thread B acquires the locks in the order Y, X.
True False
Mul!-Part Ques!ons
Congratula#ons: You have finished all of the True/False ques#ons on this exam.
You will now have five mul#-part ques#ons covering different aspects of concurrency.
Most par#al ques#ons require you to type in an integer or le"er within a box; each of these par#al ques#ons is graded.
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
printf(¡°Final Balance is %d\n¡±, balance);
printf(¡°Final Balance is %d\n¡±, balance);
Correct!
You Answered Correct Answer
Correct!
Correct!
You Answered Correct Answer
Correct!
Correct!
Correct!
Correct!
Correct!
}
What will the applica#on print when it is run? If any answer is unknown due to race condi#ons or different scheduling possibili#es, write UNKNOWN. Otherwise, your answers should be simple integers.
UNKNOWN
UNKNOWN
What will be the ADD Balance printed by the thread performing addi#ons? What will be the SUB Balance printed by the thread performing subtrac#ons?
300
What will be the Final Balance printed by the parent thread?
Answer 1:
UNKNOWN unknown
Unknown
Answer 2:
UNKNOWN Unknown
unknown
Answer 3:
300
Correct!
Correct Answer
Correct Answer
Correct!
Correct Answer
Correct Answer
Correct!
Ques!on 43
4 / 14 pts
In this ques#on, you will explore the behavior of implementa#ons of thread_join() and thread_exit() that may be incorrect. Whether or not the implementa#on could incur problems at run-#me might depend on the exact scheduling of threads.
To understand how the scheduler switches between threads, you must understand the following model. This model is iden#cal to what was presented in previous exams and examples.
Imagine you have two threads, T and S. The scheduler runs T and S such that each statement in the C-language language code (or line of code as wri"en in our examples) is atomic. We tell you which thread was scheduled by showing you either a ¡°T¡± or a ¡°S¡± to designate that one line of C-code was scheduled by the corresponding thread; for example, TTTSS means that 3 lines were run from thread T followed by 2 lines from thread S.
Assume each test of an if() statement requires one scheduler #ck. Assume jumping to the correct code does not take an addi#onal #ck beyond the test (e.g., jumping to the then branch of
an if statement does not take an extra #ck).
Func#on calls that may need to wait for another thread to do something (e.g., mutex_lock() and cond_wait()) may consume an arbitrary number of scheduling #cks and are treated as follow.
For mutex_lock(), assume that the func#on call to mutex_lock() requires one scheduling interval if the lock is available. If the lock is not available, assume the call spin-waits un#l the lock is available (e.g., you may see a long instruc#on stream TTTTTTT that causes no progress for this thread). Once the lock is available, the next scheduling of the acquiring thread causes that thread to obtain the lock (e.g., a!er a thread S releases the lock, the next scheduling of the wai#ng thread T will complete mutex_lock(); note that T must be scheduled for one #ck with the lock released for mutex_lock() to complete).
The rules for cond_wait() are similar. When a thread calls cond_wait(), if the work has not yet been done to complete the wait(), then no ma"er how long the scheduler runs this thread (e.g., TTTTT), this thread will remain wai#ng in the wait() rou#ne. A!er another thread runs and does the work necessary for the wait() rou#ne to complete, then the next scheduling of thread T will cause the wait() line to complete; again, note that T must be scheduled for one #ck with the work completed for wait() to complete).
If the shown schedule results in one thread finishing the shown code, assume the thread con#nues execu#ng code that is not related.
Assume the following code compiles correctly. Assume done is a shared variable and ini#alized correctly. Assume the parent thread has just called thread_join; when it is next scheduled, it will execute p1. Assume the child thread has just called thread_exit; when it is next scheduled, it will execute c1.
void thread_join() {
Mutex_lock(&m); // p1
if (done == 0) // p2
Cond_wait(&c, &m); // p3
Mutex_unlock(&m); // p4
}
void thread_exit() { Mutex_lock(&m); // c1 done = 1; // c2 Mutex_unlock(&m); // c3 Cond_signal(&c); // c4
}
For each of the following schedules of the parent, P, and the child, C, designate one of the op#ons A, B, C or D.
A. Schedule does not yet cause a problem; thread_join or thread_exit not completed
B. Schedule does not trigger any race condi#ons or problems; thread_join and thread_exit ran to
comple#on and the parent successfully waited for the child
C. Schedule caused a problem (Ordering): Parent will return from thread_join() before Child calls thread_exit().
D. Schedule caused a problem (Deadlock): Parent and/or child will be stuck forever in thread_join or thread_exit()
A A
C D D B
A
1. CCCPPPC -
2. CCCCPPP-
3. CCPPPPPCC - 4. PPCCPPPPC - 5. PPCCCPPPP- 6. PPPCCCCPP- 7. PPPCCCPPPC -
Answer 1:
A B
Answer 2:
A B
Answer 3:
C A
Answer 4:
D A
Answer 5:
D A
Answer 6:
B
Answer 7:
A
You Answered
Correct Answer
You Answered
Correct Answer
You Answered
Correct Answer
You Answered
Correct Answer
You Answered
Correct Answer
Correct!
Correct!
Ques!on 44
12 / 16 pts
In this ques#on you will analyze the behavior of a mul#-threaded producer-consumer applica#on.
The following code is intended to be similar to what has been shown in lecture and should be correct; assume it is successfully compiled and run (e.g., ignore any capitaliza#on problems). Everything is correctly ini#alized, including the mutex,
Assume there are 2 producer threads and 2 consumer threads in this applica#on. Assume this code is run with is a shared buffer with 4 elements; a global variable numempty is correctly ini#alized
to 4 and numfull is correctly ini#alized to 0. Assume tmp is a local per-thread variable. The producer rou#ne get_empty() finds an "empty" element in the shared buffer, marks that element as being "in progress", and decrements numempty; mark_full() marks the designated element (tmp) as "full" and increments numfull. The consumer rou#nes of get_full() and mark_empty() do the corresponding (opposite) opera#ons.
The applica#on has been running for some unknown amount of #me and is in an unknown (but correct) state. It is up to you to determine where in the code it is possible for those 4 threads to currently be!
void *producer(void *arg) {
while (1) { // p0
Mutex_lock(&m); // p1
while (numempty == 0) // p2
Cond_wait(&full, &m); // p3
tmp = get_empty(); // p4 -- decr numempty
} }
Mutex_unlock(&m);
fill_buffer(tmp);
Mutex_lock(&m);
mark_full(tmp);
Cond_signal(&empty);
Mutex_unlock(&m);
// p5
// p6
// p7
// p8 -- incr numfull
// p9 // p10
void *consumer(void *arg) {
while (1) { // c0
Mutex_lock(&m); // c1
while (numfull == 0) // c2
Cond_wait(&empty, &m); // c3
tmp = get_full(); // c4 -- decr numfull
Mutex_unlock(&m); // c5
use_buffer(tmp); // c6
Mutex_lock(&m); // c7
mark_empty(tmp); // c8 -- incr numempty
Cond_signal(&full); // c9
Mutex_unlock(&m); // c10
} }
Which of the following are possible loca#ons in the code for the 2 producer threads, named Pa and Pb, and 2 consumer threads, named Ca and Cb?
Enter A for Possible; B for Not Possible.
1. Pa: p3 (cond_wait), Pb: p3 (cond_wait), Ca: c8 (mark_empty), Cb: c6 (use_buffer)
A
2. Pa: p6 (fill_buffer), Pb: p4 (get_empty), Ca: c6 (use_buffer), Cb: c4 (get_full)
3. Pa: p6 (fill_buffer), Pb: p6 (fill_buffer) Ca: c4 (get_full), Cb: c4 (get_full)
A B
A
7. Pa: p6 (fill_buffer), Pb: p6 (fill_buffer), Ca: c8 (mark_empty), Cb: c9 (cond_signal)
B
8. Pa: p3 (cond_wait), Pb: p3 (cond_wait), Ca: c3 (cond_wait), Cb: c3 (cond_wait) B
Answer 1:
A
Answer 2:
A B
Answer 3:
B
Answer 4:
A
Answer 5:
B A
Answer 6:
A
Answer 7:
B
Answer 8:
B
4. Pa: p6 (fill_buffer), Pb: p6 (fill_buffer), Ca: c6 (use_buffer), Cb: c6 (use_buffer)
5: Pa: p1 (mutex_lock), Pb: p1 (mutex_lock), Ca: c1 (mutex_lock), Cb: c1 (mutex_lock)
B
6. Pa: p6 (fill_buffer), Pb: p4 (get_empty), Ca: c6 (use_buffer), Cb: c6 (use_buffer)
A
Ques!on 45
17 / 18 pts
In this ques#on you will explore the Dining Philosophers problem implemented to ensure maximum safety and liveness. The following code is intended to be similar to what has been shown in lecture and should be correct; assume it is successfully compiled and run (e.g., ignore any capitaliza#on problems). Assume all state is ini#alized and shared correctly.
Note that in the C code, square array brackets have been replaced with parentheses due to a Canvas forma&ng limita#on.
sem_t mayEat(5); // an array, each initialized to 0; can't use square brackets in Canvas sem_t mutex; // initialized to 1
int state(5) = {THINKING}; // an array; can't use square brackets in Canvas
take_chopsticks(int i) {
sem_wait(&mutex); // enter critical section
state(i) = HUNGRY; // set an element in the array; image the square brackets...
testSafetyAndLiveness(i); // check if I can run
sem_signal(&mutex); // exit critical section
sem_wait(&mayEat(i));
}
put_chopsticks(int i) {
sem_wait(&mutex); // enter critical section
state(i) = THINKING;
testSafetyAndLiveness(i+1 %5); // check if neighbor can run now
testSafetyAndLiveness(i+4 %5);
sem_signal(&mutex); // exit critical section
}
testSafetyAndLiveness(int i) {
if(state(i)==HUNGRY && state(i+4%5)!=EATING && state(i+1%5)!=EATING) {
state(i) = EATING;
sem_signal(&mayEat(i));
}
}
Assume a system with 6 philosophers (threads numbered 0, 1, 2, 3, 4, 5) that con#nuously alternate between thinking and ea#ng. When a philosopher i is done thinking, they call take_chops#cks(i) and then they eat; when they are done ea#ng, they call put_chops#cks(i) and then they think. This is all they do, all day long, every day.
For the following sequence of calls, what will be the resul#ng state of each philosopher? Assume that each call to take_chops#cks() either runs to comple#on or to the point that it is stuck wai#ng for a semaphore; only at those points will the next call to take_chops#cks() occur in this sequence.
Scenario A: Star#ng with all philosophers in the THINKING state
take_chops#cks(2); take_chops#cks(1); take_chops#cks(0); take_chops#cks(5); take_chops#cks(4);
take_chops#cks(3)
A!er that sequence, what will the state be of each thread? Enter E for Ea#ng, T for Thinking, H for Hungry, or U for Unknown.
E H E H E H
Scenario B: Star#ng with all philosophers in the THINKING state
take_chops#cks(2); take_chops#cks(1); take_chops#cks(5); take_chops#cks(0); take_chops#cks(4);
take_chops#cks(3)
A!er that sequence, what will the state be of each thread? Enter E for Ea#ng, T for Thinking, H for Hungry, or U for Unknown.
H
H
E
E
H
E
Scenario C: Assume that we con#nue Scenario B; that is, a!er the 6 calls to take_chops#cks(i), philosophers start to put down their chops#cks -- but only if they successfully picked them up! In other words, in the following stream of calls to put_chops#cks(i), IGNORE any calls to put_chops#cks(i) that are not possible in this scenario; that is, if philosopher i is s#ll HUNGRY and wai#ng to complete take_chops#cks(i), then it cannot call put_chops#cks(i). Remember that philosophers start this scenario in the same state that they were in at the end of Scenario B.
put_chops#cks(2); put_chops#cks(0);
H E T E H E
Congratula#ons on finishing this exam. You can now be done THINKING and move on to whatever state of being that you choose!
Answer 1:
e
Answer 2:
h
Thread 0: Thread 1: Thread 2: Thread 3: Thread 4: Thread 5:
Thread 0:
Thread 1:
Thread 2:
Thread 3:
Thread 4:
Thread 5:
Thread 0: Thread 1: Thread 2: Thread 3: Thread 4: Thread 5:
Answer 3:
Correct!
Correct!
Correct!
Correct!
Correct!
e
Answer 4:
h
Answer 5:
e
Answer 6:
h
Answer 7:
h
Answer 8:
h
Answer 9:
e
Answer 10:
E h
Answer 11:
h
Answer 12:
e
Answer 13:
h
Answer 14:
e
Answer 15:
t
Answer 16:
e
Answer 17:
h
Answer 18:
Correct!
Correct!
You Answered
Correct Answer
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
e