This exam is open-book, open-notes, open-computer, open-Internet,
and closed-other-people.
(12 points) Suppose we have a collection of processes, each of which does
ten iterations of the following sequence: wait 1 second for file input, and
then do 2 seconds of computation. Furthermore, suppose context switches
take 10 milliseconds. Assuming a round-robin scheduling algorithm, answer
each of the following questions for 1 process, 2 processes, and 10 processes,
and for quantum sizes of 100 milliseconds and 500 milliseconds (yes, that's
six cases). Assume that all processes are ready to run at time zero.
- What is the CPU efficiency? (That is, the percentage of time
the CPU is doing the "do 2 seconds of computation" part of some
process.)
- What is the throughput? (That is, the number of jobs
completed per time unit of your choice.)
- What is the average time to completion for all the processes.
- What are the morals of the story? More precisely, what can you
say about the relative merits of smaller and larger quanta, and of more
or fewer processes?
(12 points) Scheduling in Linux. You're going to need to
dig through some code, but you might also consider using the web to
get some help.
- Which fields of the task_struct type (see sched.h) are involved
in scheduling?
- Summarize the scheduling algorithm used by Linux. Where
relevant, provide references to the code (file names and
line numbers).
- Does the scheduling algorithm include anything to cause
quick scheduling of processes that have been blocked waiting for input
that has now arrived? If so, describe relevant parts of the
algorithm. If not, sketch a plan to add this feature.
(8 points) Questions about fork(). Don't just answer the questions; provide
some evidence for your answers.
- Suppose your program is called with a command like "yourprogram | wc", and
then yourprogram calls fork(), and both the parent and the child print to
standard output. Which process or processes, if any, send data to wc?
- Suppose your program opens a file for reading and then calls fork().
If both the parent and the child read from the open file, do their read
operations interfere with each other?
- Same question as the previous one, but this time, suppose the file is open
for writing.
(8 points) Suppose we are using a 2-level page table system in
which logical addresses are 32 bits long, each second-level page table
entry takes up exactly 32 bits, and each second-level page table
takes up exactly one page. Suppose further
that the page size is 8KB, and the paging system supports LRU page replacement.
- Show a diagram of the second-level page table entries.
What assumptions about physical RAM does this system make?
- How big is the top-level page table?
- Assuming that exactly one second-level page table is in
memory and exactly half of its entries are valid, how many
bytes of memory in our virtual address space actually reside
in physical memory?
(2 points) I've got some extra professional development
money I need to spend in the next month, and I want to spend it
on computer books. What's your favorite computer-related book? (It's
okay if I already own it--I'm also curious about what books you like.)
(12 points) Take a look at the program
badpingpong.c. This program is trying
to use signals to cause the child and the parent to print alternating
messages to stdout. The parent prints a message and then signals the
child, then the child catches the signal, prints a message, and signals
the parent, etc. Unfortunately, when I compile and run this program,
it doesn't work.
- Try running badpingpong.c and watching the parent and child
processes using top. (Once top
is running, you can type a capital A to sort the processes by
age, which brings the badpingpong processes to the top of the
list.) What happens? Are the two
processes busy waiting or blocked? How can you tell?
- Add some code that will help you determine which process
gets scheduled first after the fork. Who goes first?
- Use the information you've accumulated so far to explain
why this program isn't working.
- Consider badpingpong2.c,
which is a slightly changed version of badpingpong.c. This
one attempts to fix the order in which the processes get to
do stuff, but it still has a problem. Run this program,
describe its behavior, and explain why it is failing.
- Go back to the original badpingpong.c, delete the pause()
and kill() calls, and add two semaphores. Change the code to perform
down and up operations on the semaphores in such a way that pingpong
works, and it doesn't matter which process goes first. Call
this bestpingpong.c, submit it via HSP, and submit a hard
copy of the whole thing.