CS444 Practice Final Exam, NAME:___________________________
Open books, notes, handouts.
Write on these pages, using the backs if need be (I hope not.) Each problem is worth 150/6 = 25 points, for
a total of 150 points.
1.
Short answer.
a.
Describe two ways
the kernel code can stop the UART transmitter interrupts from happening while a
program is running on an x86 system.
b.
In user-level
producer consumer using three semaphores as in the program on pg. 130, suppose
the shared buffer can hold 10 elements (N=10).
What are the counts in each of the three semaphores when the shared
buffer is full, the producer is blocked because the buffer is full, and the
consumer is running in consume_item?
a.
Suppose a page
fault occurs on a code page for a process, because that code page is not yet in
memory but is now needed. Where will the
OS find the needed page of data (in this case program code) for the page? What action by the scheduler will soon happen
for this process?
b.
What is the
kernel mutex mechanism we are using in our tiny-Unix (hw2, hw3, hw4) kernels? This mechanism cannot be used with
multi-processor systems. Name another kernel mutex mechanism that does work
with multiprocessors.
2.
Deadlocks. Suppose there are two resources R and S, and
three processes A, B, and C, and:
process
A holds T, requests lock on R
process
B holds R, requests lock on S
process
C holds nothing, requests lock on R and S
Draw the resource allocation
graph and determine if there is a deadlock.
If so, what processes are involved?
If not, show how the processes can “unwind”, i.e., finish execution in
some order.
3. System Call Mechanism. In hw2, hw3, and hw4,
and also in Linux 2.2 on x86, a system call and related execution has the
following steps:
1.
call assembly
language function for system call
2.
load system call
arguments in registers, system call # in EAX
3.
start executing
int $0x80
4.
save EFLAGS, EIP
on stack (also CS)
5.
load EIP from
IDT[0x80]
6.
execute the
assembler syscall handler, save registers
7.
execute the C
syscall handler
8.
execute the
assembler syscall handler body, restore registers
9.
execute the iret
instruction
10. execute the next instruction after the int $0x80
a.
Which steps are
part of the trap cycle of the CPU, (and thus involved in the transition from
user to kernel mode under Linux)?
b.
Which step, when
executed under Linux, involves a transition from kernel mode to user mode?
c.
Which steps, when
executed under Linux, are running in user mode in the CPU?
d.
Which steps, when
executed under Linux, are running in kernel mode in the CPU?
e.
Which step could
contain a call to a device driver (hw’s or Linux)?
f.
Which steps would
also be in a list like this for handling an interrupt? (Replace “syscall” with
“interrupt” in the steps above to answer this.)
4.
Scheduling.
Consider the execution of the hw3 kernel with its non-preemptive scheduler with
the following programs, which are nearly the same as the standard test programs
except for the loop body, the number of A’s that main1 outputs, and the number
of c’s that main3 outputs. The value of
N is the same for main1 and main3.
int
main1()
{
int sum = 0; int i;
write(TTY1, “aaaaaaaaaaa”, 10);
write(TTY1, “zzz”, 3);
for (i=0;i<N;i++)
sum
+= i*i;
write(TTY1, “AAAA”, 4);
}
int
main2()
{
write(TTY1,”bbbbbbbbbb”, 10);
}
int
main3()
{
int sum = 0; int i;
for (i=0;i<N;i++)
sum
+= i*i;
write(TTY1, “cccc”, 4);
}
Note
that the CPU-burning loop is the same in main1 and main3. The output from the
run using hw3’s kernel is simply
*aaaaaa*******ccccaaaaz*zz*******AAAA*bbbbSHUTTING
DOWN
*bbbbbb*
Recall
that the *’s are output in the tick handler by kprintf every 10 ms. Characters take 1 ms to output. The tty
output queue can hold 6 characters.
a.
How long does one
of the CPU-burning loops take to run, in ms?
b.
Which CPU-burning
loop executes first, main1’s or main3’s?
c.
What output is
showing when main3 exits? (Don’t forget
write-behind effects)
d. How many chars are output, before SHUTTING DOWN is
output, from interrupt handler executions that occur during the execution of the
two user-level CPU-burning loops?
e.
Does process 1
ever block? When or why not?
f.
Does process 3
ever block? When or why not?
5.
Mutex System Calls. Suppose we want to add a
user-level mutex service to nonpreemptive tiny UNIX of hw3, which does not have semaphore system
calls.
a.
Suggest an
appropriate set of new system calls for this service. Also give the appropriate names for the
kernel functions that implement each system call.
b.
Explain in what
functions the scheduler functions sleep() and wakeup() or wakeup_one() would be
called.
c.
Would you use cli() and sti() (or set_eflags()) around the call to sleep? Discuss this decision.
6.
x86 Paging. The
first few PTEs of the SAPC’s only page table look like this, after a reboot:
Address Contents
PTE0 0x52000 0x00000007
PTE1 0x52004 0x00001007
PTE2 0x52008 0x00002007
PTE3 0x5200c 0x00003007
a. What
is the relationship between VA and PA described here? For what range of VAs does it hold?
b.
How would you
change this page table to make an access to VA 0x2056 cause a page fault? (What
new value for what address? Or give the Tutor command.
c.
If we access VA
0x3110 by reading the 32-bit quantity there, which PTE is changed, and how?