Comp111 Final Exam Review
Open Books and Notes
Final exam: Thu Dec 14, 7-9 PM, Lane 100.
Final exam coverage
- Book chapters 1-8, 9, 11, 12, 14.
- All lectures.
- All assignments.
- All in-class exercises.
Everything after the midterm, including:
and it is difficult not to mention:
- Short-term: run queue.
- Disk scheduling.
- Least-recently used algorithm for resource recovery.
- Little's law and basic queueing theory (M/M/1).
- I/O subsystems
- Block devices
- Block-mode read and write
- Kernel buffering
- Filesystems and Inodes.
- Super-block and logical-to-physical mapping.
- Filesystem integrity.
- Transaction queues and transactional filesystems.
- User identity.
- Filesystem protections.
- Setuid and setgid.
- Control of privilege.
- Common attacks.
- I/O (dup, open, close)
- Creation (fork)
- System calls
- Process state models
Be aware that I can ask you...
Some example problems:
- To repeat an in-class exercise.
- To answer a question about an assignment.
- To answer a question from the midterm again.
- To explain something in the lecture notes.
- In class we have studied the Least-Recently-Used (LRU)
paging strategy for process pages. Another commonly utilized strategy is
Least-Frequently-Accessed (LFA). In this strategy, a counter is
maintained of the number of times each logical page has been accessed
since the beginning of time. Then, the pages with the lowest counts
are swapped out first when physical pages are needed.
- Under what conditions is LFA superior to LRU? Give an example of a
set of processes, and an environment, where the completion time for the
whole set of processes is longer under LRU than under LFA.
- Under what conditions is LFA inferior to LRU?
Give an example of a set of processes, and an environment, where the
completion time for the
whole set of processes is longer under LFA than under LRU.
- Give an example in which LFA and LRU have identical behavior.
- One compromise between LFA and LRU is to keep track of
the total count of accesses Ctotal, and the total
elapsed time Tlifetime for which each logical page
has existed. Divide Ctotal by Tlifetime to
get the frequency F of accesses per unit time, and choose the page
with the lowest such frequency.
How does this strategy compare with LRU and LFA for your examples?
- You are running a server whose purpose is to enable 100
students to complete Comp11 assignments. All students are
logged in at the same time. Each student runs a shell that randomly
accesses 10 pages of text memory and 1 page of data memory.
Each student alternates between editing a file, compiling it,
and running it, leaving the shell and editor running while
compiling and running the assignment. Compiling and running
never occur together. The editor occupies 20 pages of text
memory but primarily runs in a main edit loop on (logical)
page 10, and the program to be edited takes up two pages of
data memory. The compiler takes up 10 pages of text memory
and utilizes four pages of data memory per compilation.
Each compiled assignment occupies one page of (read-only) text and
accesses two pages of data memory.
- At any one time, on average, what is the minimum number of physical
pages one needs in order to avoid thrashing? Justify your answer.
- Suppose each student's typing is exponential with rate λ=2
(characters per second).
Suppose everyone is editing (all 100 students), and that the response
time for typing a character (at any terminal) is observed as an
average of 1/4 second per character. What
is the service rate μ for responding to typed characters?
Please show your work. Hint: model as an M/M/1 queue, as there
is only one processor on the machine.
- You are running a web service with an average response rate (=
arrival rate) of 100 requests/second and the average time to process a
request is 1/2 second. How big should the queue be inside the server
to store pending requests? Hint: use Little's law.
- In a short essay, explain why the transaction queue in a disk needs
to be in the middle, rather than on either side of the platter.
I am designing the final exam to take one hour and be roughly at the
same level as the midterm. There will be at least:
I am designing the exam to take one hour.
I will pick and choose which topics!
- One question on techniques and algorithms (doing an algorithm).
- One question on operating systems design (judgement).
- One question on concepts (essay).
Some tips on taking my exams
- Figure out the domain of the problem. Find it in the notes.
- Index your notes! I won't be asking anything that isn't localized somewhere
in the notes. Finding out where is the difficult part.
- Explore options within the domain before writing down an answer.
- If in doubt about what the question means, ask. There
is no harm in asking.
Some tips on answering my essay questions
- Make up an outline.
- Don't write down anything of which you are not sure
(I grade on a differential scale: valid points - irrelevant/incorrect points).
- Explore all options for the answer.
- Then write the essay.