| |
Your second midterm examination will appear here.
It will be a 75 minute, closed book exam.
It covers Chapters 8 - 11. Omit Chapters 12 and 13
Expectations:
Questions will be similar to homework questions from the book. You will be
given a choice of questions, e.g., "Write on four out of five questions." I
try to ask questions I think you might hear in a job interview. "I see
you took a class on Operating Systems. What can you tell me about ...?"
If it matters, I will be grading the exam, not the TA. I expect proper English.
See also Dr. Barnard's notes.
He was using a different edition of our text, so chapter and section numbers
do not match, but his chapter summaries are excellent.
Directions:
Read and follow the directions.
- Write on four of the five questions. If you write more
than four questions, only the first four will be graded. You do not get extra
credit for doing extra problems.
- Read the entire exam. If there is anything you do not understand about
a question, please ask at once.
- If you find a question ambiguous, begin your answer by stating clearly
what interpretation of the question you intend to answer.
- Begin your answer to each question at the top of a fresh sheet of
paper. [Or -5]
- Write only on one side of a sheet. [Or -5]
- Be sure your name is on each sheet of paper you hand in.
[Or -5]
Question:
Are you trained somewhere that to write in paragraphs? Yes, that is
often the preferred means, but in many technical circumstances, including this
exam, outlines, enumerations, bullets, and pictures may communicate
more effectively. At the very least, you should answer by question parts:
-
-
-
The shaded, italic boxes represent outlines of solutions or comments. They suggest
what a complete solution might be, but they are not complete solutions.
Grades:
Average score: 76
Range: [39, 99]
Distribution:
Problem 1. Page replacement strategies
17 of 18 students selected. Average score: 22 of 25
In a virtual memory system implemented by paging, when a page fault occurs,
we must bring in a new page. However, usually the operating system must choose
a page to be removed from memory to make room for the newly-referenced page.
- (7 points) Describe each of the following page replacement
strategies:
- First-in, first-out (FIFO) page replacement
- Optimal page replacement
- Least recently used (LRU) page replacement
- Least frequently used (LFU) page replacement
- FIFO: The page selected for replacement is the one which has been in memory the longest
- Optimal: Select the victim so that the run has the fewest page faults.
Not necessarily the page next used furthest in the future
- LRU: Victim is the page with longest time since last access
- LFU: Victim is the page used least frequently
- (6 points) Give at least one advantage (+) and one disadvantage (-) of each of the following page replacement strategies:
- First-in, first-out (FIFO) page replacement
- Optimal page replacement
- Least recently used (LRU) page replacement
- Least frequently used (LFU) page replacement
- FIFO: +: Simple, fair
-: Can be very bad
- Optimal: +: Best performance
-: Impossible to implement
- LRU: +: Good performance
-: Expensive to implement
- LFU: +: Intuitive?
-: Probably remove the page you just brought in
- (12 points) Now, work out a simple example.
Suppose our process is allocated three
(0 - 2) page frames in physical memory.
Suppose our process consists of nine (0 - 8) pages in its virtual
memory
The table shows the order in which pages are referenced in the execution of the program.
Complete the table by showing the number of each page residing in each
frame after each page reference shown under each of the page replacement
strategies
Mark each page fault with an asterisk (*)
For each strategy, how many page faults were generated, including the
three page faults already shown (denoted by *)
| i) First-in, first-out (FIFO) page replacement |
| | Page references: |
0 | 1 | 2 | 0 | 1 |
2 | 3 | 4 | 2 | 5 |
0 | 6 | 0 | 7 | 7 |
8 | 0 | 6 |
| | Frame 0: |
0* | 0 | 0 | | | |
3* | | | | 0* | |
| | | 8* | | |
| | Frame 1: |
| 1* | 1 | | | |
| 4* | | | | 6* |
| | | | 0* | |
| | Frame 2: |
| | 2* | | | |
| | | 5* | | |
| 7* | | | | 6* |
| | Total number of
page faults: | 12 |
| |
| ii) Optimal page replacement |
| | Page references: |
0 | 1 | 2 | 0 | 1 |
2 | 3 | 4 | 2 | 5 |
0 | 6 | 0 | 7 | 7 |
8 | 0 | 6 |
| | Frame 0: |
0* | 0 | 0 | | | |
| | | | | |
| | | | | |
| | Frame 1: |
| 1* | 1 | | | |
3* | 4* | | 5* | | 6* |
| | | | | |
| | Frame 2: |
| | 2* | | | |
| | | | | |
| 7* | | 8* | | |
| | Total number of
page faults: | 9 (Can
select some different victims among pages
never to be used again) |
| |
| iii) Least recently used (LRU) page replacement |
| | Page references: |
0 | 1 | 2 | 0 | 1 |
2 | 3 | 4 | 2 | 5 |
0 | 6 | 0 | 7 | 7 |
8 | 0 | 6 |
| | Frame 0: |
0* | 0 | 0 | | | |
3* | | | 5* | | |
| 7* | | | | 6* |
| | Frame 1: |
| 1* | 1 | | | |
| 4* | | | 0* | |
| | | | | |
| | Frame 2: |
| | 2* | | | |
| | | | | 6* |
| | | 8* | | |
| | Total number of
page faults: | 11 |
Problem 2. Segmentation vs. Paging
18 of 18 students selected. Average score: 19 of 25
Hint: This problem could take forever to write, but then
you would not have time for any other question. I expect about the amount of
detail you might
give if you are asked these questions in the context of a one hour job interview.
(5 points each)
- How does segmentation work?
- How does paging work?
- How segmentation and paging similar?
- How segmentation and paging different?
- Which is better? Why?
- See book. Type of virtual memory, meaning part is in memory, part is on disk,
and there is a mapping between them. Discuss memory translation, segment fault.
Consider a picture.
- See book. Type of virtual memory. Discuss memory translation, page fault.
Consider a picture
- Implement virtual memory, page/segment table, code & data sharing, difficult
to implement without hardware support, processes can use memory non-contiguously
- Pages are all the same size; segments are typically different. That makes
replacing a segment in memory much harder. Programmer controls segments; operating
system controls pages, address translation is more complex with segments because
they have different lengths; segments lead to external fragmentation, pages
may have internal fragmentation (wasted memory space); segments require a limit
register to enforce protection
- Commercially, paging predominates. Most commercial systems that implement
segments do so with segmentation AND paging to avoid external fragmentation.
Problem 3. Virtual disk drive
8 of 18 students selected. Average score: 18 of 25
Hint: Do not make the mistake of thinking I am cheating by asking a Chapter
12 or 13 question. I expect an answer based on what you have learned from the
chapters we have studied, plus your insight.
Consider: "Virtual" is one of the fundamental concepts
of
operating
systems. "Virtual X" is making it look as though you have
X, when in fact you don't. Segmentation and paging implementations
of virtual
memory, for example.
Consider: We know that information stored in memory can be accessed much faster (often
about x 1000) than information stored on a hard disk. That is why we often
cache in memory structures such as recently-accessed directories.
Problem: Many programs (e.g., compilers) spend most of their time reading
and writing files to the disk. Especially, a multi-pass compiler must store
several intermediate files, in addition to the visible source and executable
files. Consider the number of accesses in a typical edit/compile/run cycle.
Opportunity: Most of our machines have quite a bit of memory.
Most of the programs we write in school are not large.
Solution: "Virtual disk drive." Suppose we allocate
a portion of our machine's physical memory to behave as a virtual drive, let's
call it
drive M: (for "memory"). We want it to appear to the user like any other drive,
except that it is 1000 times faster than the hard drive. When we start a session,
we copy
files we will use often from drive C: to drive M:. We do our work (e.g., edit/compile/run)
using the fast drive M:. Of course, when we are done, we will remember
to copy our working files from drive M: back to drive C:
That is how our virtual drive should appear to the user.
- (10 points) Describe how the memory manager portion of
the operating system (that's Chapter 8) might support a virtual disk drive.
- (10 points) Describe how the file system portion of the operating
system (that's Chapter 11) might support a virtual disk drive.
- (5 points) Is this a good idea? Why, or why not?
Hint: I am not asking how the operating system copies files
back and forth. That part was to help you understand what a virtual disk might
be good for. I am asking how the memory manager should set aside and manage
the memory space and how the file manager should handle it.
See problem 11.8. Some earlier versions of MS DOS offered this feature, but it seems to have been removed.
- The memory manager would allocate a block of memory for this purpose. Then
the user, using file system commands, copies selected files to the RAM disk.
Note that it is not associated
with a particular process. The
point is that I want it to look just like a physical disk, except that it is fast.
It has limited size like any disk, so I could not copy more files than it can
hold, just as I cannot for any disk. We don't
want virtual memory,
because the point is to have the contents of the file in memory. We could use
pages
or
segments,
but
we'd
want to lock them
in memory. Yes, there is fragmentation, internal to the RAM drive and external
to the files stored there. Consider: On a normal disk, space not used by files
is external fragmentation, and we consider that a good thing
- free disk space.
- The file system would have to mount() it. Other disk file and directory access
commands would have to be modified to access the memory disk. A modification
of memory-mapped files is one way that could be implemented.
- Probably not in most modern systems. The speed is attractive
for work like repeated edit/compile/run cycles. At one point, I was able to
create a RAM disk, copy my text editor, my compiler, and my program to it,
and edit/compile/run far faster. This scheme assumes we know
better than the operating system what should be kept in memory.
Also, information written
to the virtual disk is only saved to the physical disk when we do it explicitly,
so there is danger of lost work.
On some systems, network access is faster than local disk access. Then
you get better performance NOT using C:
Problem 4. Effective memory access time
16 of 18 students selected. Average score: 19 of 25
Assumptions:
- We are using a virtual memory memory system with paging
- At any point in the execution of our process, some pages are in memory
(and on the paging disk), and some pages are only on the paging disk
- Part of the page table is kept in a Translation Lookaside Buffer (TLB),
and part is kept in memory. [Don't panic; you do not need to know what a
TLB is to answer this question.]
- It takes 20 nanoseconds to access the TLB
- It takes 100 nanoseconds to access memory
- It takes 100,000 nanoseconds to access the disk
- For each memory reference in our program, we first look in the TLB (20
ns)
- 80% of the time, we find in the TLB the frame number in memory where the
desired reference can be found, and we access memory to find it (+ 100 ns)
- 20% of the time, we do not find the desired page in the TLB
- In that case, we must access memory to find the page table (+ 100 ns)
- 90% of that 20% (18% of the total), we find the frame number in memory
where the desired reference can be found, and we access memory to find it
(+ 100 ns)
- In the remaining 2% of the time, we have not found the frame number either
in the TLB or in the in-memory page table because the referenced page is
not in memory. We must go to the disk and retrieve it (+ 100,000 ns)
- In 10% of the cases described in assumption 12, before we can bring the
new page in, we must first copy the "victim" page currently holding that
frame back to the disk (+ 100,000 ns)
- Once the new page is copied from the disk into its page frame in memory,
we must access the referenced memory location (+ 100 ns)
- (2 points) What is the event called described in assumption 9?
- (2 points) What is the event called described in assumption 12?
- (3 points) In assumption 13, why must we sometimes write the victim page
back to the disk?
- (3 points) In assumption 13, why don't we always have to write the victim
page back to the disk?
- (10 points) On average, how many nanoseconds are required to make 1,000
memory references in this system?
- (5 points) If you wish to make the average memory access time faster, which
of these steps will you attack? Why? What operating system changes might improve
that part?
- TLB miss
- Page fault
- Its contents may have changed since it was read (or last written)
- Its contents may not have changed since it was read (or last written)
| Assumption | Time each (ns) | Times of 1000 | Time total (ns) |
| 7 | 20 | 1000 | 20,000 |
| 8 |
100 |
800 |
80,000 |
| 10 |
100 |
200 |
20,000 |
| 11 |
100 |
180 |
18,000 |
| 12 |
100,000 |
20 |
2,000,000 |
| 13 |
100,000 |
2 |
200,000 |
| 14 |
100 |
20 |
2,000 |
| Total |
|
|
2,340,000 |
- Clearly, the cost of disk access dominates the total. You have three alternatives:
- Make disk access faster (reduce the 100,000)
- Fewer page faults (reduce the 20):
Larger memory
Larger working set for this process
Better page replacement strategy
- Fewer write-backs (reduce the 2)
Implement "sneaky write" on dirty bit
More frequent write-back to clear dirty bit
You might also reduce the TLB miss rate:
Larger TLB
Better TLB replacement strategy
Of course, more or faster memory would help, but that's not an OS improvement.
Problem 5. Automatic file open() and close()
13 of 18 students selected. Average score: 16 of 25
Some systems automatically
- Open() a file when it is referenced for the first time and
- Close() a file when the job terminates
- (6 points) List three operating system calls that might
reference a file for the first time
- (6 points) Discuss the advantages of this scheme
- (6 points) Discuss the disadvantages of this scheme
- (7 points) Is it a good idea? Why or why not?
- create(), read(), append(). See Section 10.1.2
delete() or rename() do not need to open a file, although they do open the
directory to which the file belongs.
Not open(). If we do that automatically, it is not called explicitly
Write() is problematic. Write() should follow create(), or else it should
mean to over-write.
CopyFile(), Edit(), Save(), SaveAs(), etc. are application commands, but not
OS calls.
Files opened automatically may be shared exactly as usual.
- Ease of use. Programmer has two fewer things to worry about. File is not
opened until it is needed
- If we explicitly open a file before we access it, the operating system
might choose anticipatory fetch, so that the first block of the file is
already in memory the first time it is accessed, saving time.
Files could be left open, and taking space in operating system tables,
long after it is no longer needed. That could also delay that file
being available to a waiting process (e.g., I want to read a file after you
finish writing it), causing unnecessary delay, and possibly contributing to
starvation or deadlock.
- Probably not. The disadvantages carry more weight to me.
However, there is nothing wrong with supporting both. You can (and should)
open and close files explicitly, but if you are careless on either, the
operating system could do the right thing, even though that carries a
performance penalty.
| |
