CS444 Final Exam,
Open books, notes, handouts. Write
on these pages, using the backs if need be (I hope not.) Each problem is worth 30 points. I’ll drop
the lowest-score problem.
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 (for example the program on pg. 120,
or prodcons.c of hw5), suppose the shared buffer can
hold 10 elements. What are the maximum
counts in each of the three semaphores to use all 10 spots, but no more?
c.
Suppose a file
has 100 file data blocks. If it’s a FAT
(File Allocation Table) file, how many disk-block accesses are needed to
determine the last byte in the file if the FAT table is filled in for it? If no information for this file is in the
table?
d.
Suppose a page fault
occurs on a code page for a process. Where
will the OS find the data (program code) for the page? What action by the scheduler will soon happen
for this process?
2.
Deadlocks. Suppose there are two resources R and S, and
three processes A, B, and C, and:
process A
holds T, wants R
process B
holds R, wants S
process C
holds nothing, wants 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 hw5,
and also in Linux, 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 number of A’s that main1 outputs, and main3, which computes as
well as outputting c’s.
int main1()
{
int
sum = 0; int i;
write(TTY1, “aaaaaaaaaaa”, 10);
write(TTY1, “zzz”, 3);
for (i=0;i<100000000;i++)
sum += i*i;
/* suppose this takes 40ms to run */
write(TTY1, “AAAA”,
4);
}
int main2()
{
write(TTY1,”bbbbbbbbbb”,
10);
}
int main3()
{
int sum = 0; int i;
for (i=0;i<100000000;i++)
sum += i*i; /* suppose this takes 40ms to run */
write(TTY1, “cccc”, 4);
}
The
output from the run using hw3’s kernel is simply aaaaaaaaaazzzAAAAbbbbbbbbbbcccc
a.
What output is
showing when main1 exits? (Don’t forget
write-behind)
b.
What output is
showing when main2 exits?
c.
Does process 1
ever block? When or why not?
d.
Does process 3 ever
block? When or why not?
e.
How would this
trio of user programs run under hw5, with its preemptive scheduler? Show the expected debug_log,
with preemptions and ticks showing at well as output. You don’t need to show the ~’s, but may if
you want.
5.
Mutex System Calls.
Suppose we want to add a user-level mutex service to nonpreemptive tiny UNIX (hw3).
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()
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
0x52000 0x00000007
0x52004 0x00001007
0x52008 0x00002007
0x5200c 0x00003007
a.
What is the relationship between VA and PA described here? For what range of VAs?
b.
What Tutor
command would you use to make page 3 read-only?
c.
How would you
change this page table to make an access to VA 0x2056 cause a page fault? (What
new value for what address?)