Name and Student ID: _______________________________
ECE 469: Operating Systems Engineering Midterm
Warning:
the purpose is to give you the impression of likely questions
the number of questions in the actual midterm will be more than this.
¡°I signify that the work shown in the examination booklet is my own and that I have not received any assistance from other students nor given any assistance to other students.¡±
Signature:
For grading purposes only:
Prob.
Max.
Score
I
32
II
12
III
19
IV
11
V
10
VI
16
Total
100
Page 1 of 6
I.
True or False
Classify the following statements as TRUE or FALSE (Fill in the table on the next page with T or F)
(1) Using mutual exclusion ensures that a system avoids deadlock.
(2) Synchronization primitives (e.g., semaphore) on multiprocessors can be implemented in the OS without hardware support.
(3) Deadlocks always result in starvation.
(4) Deadlocks happen more often than non-deadlock concurrency bugs in the real world.
(5) Shortest Remaining Time First is the best preemptive scheduling algorithm that can be implemented in an Operating System.
(6) CPU sees physical memory addresses when executing memory instructions.
Now fill in the following table (on the next page) with T or F:
Fill in the following table below with T or F (no explanation needed, just T or F):
Name and Student ID: _______________________________
1
4
2
5
3
6
Page 2 of 6
Name and Student ID: _______________________________
II. Multiple Choice Questions
Number of correct answers can range from 0 to N. If you get all correct answers, you get 2 points. For each wrong answer you put besides the correct answers, you get -0.5 points. For example, if the correct answer is 1,2 and your answer is 1,2,3, you get 1.5 points. If your answer is 1, then you get 1 point. No explanation is needed or will be scored.
a.
Which of the following ARE NOT goals of CPU scheduling? (1) Maximizing throughput.
(2) Short response time.
(3) Minimizing turnaround time.
(4) Fairness.
b.
Which of the followings are true about TLB?
(1) TLB stores hot page table entries and hot data.
(2) TLB exploits spatial locality of memory accesses.
(3) TLB is usually fully associative.
(4) Hardware maintains the consistency between TLB and memory. (5) With ASID, TLB needs to be flushed on every context switch. (6) The OS is never involved if the TLB access is a hit.
Page 3 of 6
III.
Short Response Questions
a. List two events that may take a process to a ready state. Be brief (within five words per event)!
Name and Student ID: _______________________________
b. What could the output of the concurrent execution of process A and process B be? (State all possible outputs)
/* initialization */ int x=0;
int y=0;
/* Process A */ while(x==0) {do-nothing} printf(¡°a¡±);
y=1;
y=0;
printf(¡°d¡±);
y=1;
/* Process B */ printf(¡°b¡±);
x=1;
while(y==0) {do-nothing} printf(¡°c¡±);
Page 4 of 6
Name and Student ID: _______________________________
IV. Concurrency
Find all of the logic bugs in the following piece of code. Modify the code (in place, cross the line you think is wrong and add your code at the correct place) to fix the bugs.
semaphore mutex = 0;
// returns true if the item was added, false otherwise bool add_item_to_queue(queue_t queue, item_t item) {
wait(mutex);
if (is_full(queue)) {
return false;
}
append_to_queue(queue, item);
signal(mutex);
return true;
}
Page 5 of 6
Name and Student ID: _______________________________
V.
CPU Scheduling
Here is a table of processes and their associated arrival and running times.
Show the scheduling order for these processes under First-In-First-Out (FIFO), Shortest-Job First (SJF), and Round-Robin (RR) with a quantum = 1 time unit. Assume that the context switch overhead is 0 and new processes are added to the head of the queue except for FIFO.
Process ID
Arrival Time
Expected Running Time
Process 1
0
5
Process 2
1
4
Process 3
4
3
Process 4
6
2
Time
FIFO
SJF
RR
0
P1
P1
P1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Page 6 of 6