| |
This was a similar course, but not exactly the same schedule, syllabus,
or text
Question 1. Virtual Memory - Locality
Virtual memory management assumes a locality model (see Figure 9.15).
- Give FIVE reasons why locality is a reasonable phenomenon.
- Give FIVE examples of situations which violate locality.
- Do real programs exhibit locality? What evidence can you
offer?
I was looking for evidence you understand, "Yes and no."
Question 2. Page Faults
Consider the following page reference string:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.
How many page faults occur for the following page replacement
algorithms assuming one, three, four, five, six, or seven frames?
Assume that all pages are initially used by pages left over from
another process, so your first unique pages will all cost one fault
each. Your answer to parts a) - c) should include a sketch showing pages
resident in memory and those replaced over time, the number of page faults,
and any interesting observations
- LRU replacement
- FIFO replacement
- Optimal replacement
- Do any of your examples exhibit Belady's anomaly? Explain.
- Which page replacement policy would your recommend? Why?
LRU:
3 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 4 5 1 7 2 -
Frame 2: 2 - 6 3 - -
Frame 3: 3 1 2 - 6 1 6
15 faults
4 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - 6 -
Frame 2: 2 - - - - -
Frame 3: 3 5 3 - -
Frame 4: 4 6 7 1
10 faults
5 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - -
Frame 2: 2 - - - - -
Frame 3: 3 6 - -
Frame 4: 4 3 - -
Frame 5: 5 7
8 faults
6 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - -
Frame 2: 2 - - - - -
Frame 3: 3 - - -
Frame 4: 4
Frame 5: 5 7
Frame 6: 6 - -
7 faults, which is the fewest we can have with 7 pages
FIFO:
3 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 4 6 3 - 2 - 6
Frame 2: 2 - 1 2 - 7 1
Frame 3: 3 5 1 6 3
16 faults
4 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - 5 3 - 1
Frame 2: 2 - 6 7 3
Frame 3: 3 2 - 6 -
Frame 4: 4 1 2 -
14 faults
5 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - 6 - -
Frame 2: 2 - - 1 -
Frame 3: 3 2 - -
Frame 4: 4 3 - -
Frame 5: 5 7
10 faults
6 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - 7
Frame 2: 2 - - - - 1
Frame 3: 3 - - 2
Frame 4: 4 3
Frame 5: 5
Frame 6: 6 - -
10 faults
Optimal:
3 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - 3 - -
Frame 2: 2 - - - 7 2 -
Frame 3: 3 4 5 6 - 1 6
11 faults
4 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - 7 1
Frame 2: 2 - - - - -
Frame 3: 3 - - -
Frame 4: 4 5 6 - -
8 faults
5 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - - -
Frame 2: 2 - - - - -
Frame 3: 3 - - -
Frame 4: 4 7
Frame 5: 5 6 - -
7 faults, which is the best we can do
d) No Belady's anomaly.
e) Recommend some variant of LRU. Pure LRU is too expensive, but
several low cost variants perform close to Optimal.
Question 3. File Allocation Table
MS-DOS and older versions of Windows used a File-Allocation Table
(see Figure 11.5) to store allocation of disk blocks in a file.
- What is disk fragmentation?
- Explain why the FAT avoids disk fragmentation.
- Why should we still defragment our hard drives?
a) Wasted space. Internal: File uses only a portion of an allocated
block. External: Free space wholes become too small to be used.
b) We still have INTERNAL fragmentation. There is no external fragmentation
because free blocks may be used, no matter where they are.
c) Splitting hairs, we do not "defragment" our drives, since there
is no fragmentation. The "Disk defragment" program rearranges blocks
for more efficient disk access. It DOES help performance, but it is not
really defragmenting.
Question 4. Pointers in Files
Many storage schemes for placing information on disks include the
extensive use of pointers. You have been asked to perform a security
audit of the file system on a computer system. The system
administrator suspects that the pointer structure has been compromised,
thus allowing certain unauthorized user access to critical system
information stored on the disk. Describe how you would attempt to
determine who is responsible for the security breach and how it was
possible for them to modify the pointers.
- Examine log files. What do you look for?
- Start with the inventory of "critical system information." Look
for inappropriate pointers to it.
- Walk the entire file structure pointers
- File structure consistency checks
- Compare current with backup images. Note differences
- Among differences, where do the links point?
- The file structures are supposed to be controled by the OS.
If there was a beach, there must be either
- an OS defect, or
- OS was circumvented
Look for OS advisories about either possibility
Question 5. Layered Network Architecture
- What are the advantages of using a layered network
architecture?
- What are the disadvantages of using a layered network
architecture?
- On balance, should a network architecture be layered or monolithic?
What evidence can you give?
- Advantages:
- Simplifies design
- Ease of communication and use
- Each layer is written to communicate with its corresponding layer
- Security
- Abstracts and encapsulates lower layers
- Modularity: Can replace one implementation of a layer by another
implementation
- Defects are localized
- Disadvantages:
- Speed
- Message size
- Code size
- Layered or monolithic? Layered.
Evidence? Probably EVERY commercial networking product, even strongly
proprietary ones, are layered.
Question 6. Sharing and Protection
Sharing and protection are conflicting goals. Give FIVE significant
examples of sharing supported by operating systems. For each,
explain what protection mechanisms are necessary to control the
sharing.
Examples include:
- Memory: Bounds registers, virtual memory
- CPU: Scheduling & dispatch
- I/O devices (e.g. disk, printer): Enqueue and manage requests
- Code and data: Virtual memory
- Semaphores: OS awards and controls access
- Files: OS maintains a compacted access matrix
Files are NOT the only resource shared
| |
