Chapter 3: Memory Management: Early Systems, Flynn and McHoes, Understanding Operating Systems, Second Edition, PWS Publishing Co. (1997)
Lesson B: Mechanics of Paging, Working Set, Segmented Memory Allocation, Segmented/ Demand Paged Memory Allocation, Virtual Memory.
Problems 1, 7, 9, 11, 12
Problem 1. Explain the differences between a page and a segment.
A page is a physical partition of a job. A segment is a logical partition of a job. Boundaries of segments in a job are chosen to correspond to units of logic in a job.
Problem 7. Given that main memory is composed of three page frames for public use and that a program requests pages in the following order: a b a c a b d b a c d
| Page Request | a | b | a | c | a | b | d | b | a | c | d |
| Page Fault at start of time slice | * | * | * | * | * | ||||||
| Page Frame 1 | a | a | a | a | a | a | d | d | d | d | d |
| Page Frame 2 | b | b | b | b | b | b | b | a | a | a | |
| Page Frame 3 | c | c | c | c | c | c | c | c | |||
| Stack .1 (Top): Newest in Memory | a | b | b | c | c | c | d | d | a | a | a |
| Stack .2 | a | a | b | b | b | c | c | d | d | d | |
| Stack .3: Oldest in Memory | a | a | a | b | b | c | c | c | |||
| Stack .4: Swapped Out | a | a | b | b | b |
5 page faults in 11 time steps yields:
success rate of 6/11 = 0.5454 = 55%
failure rate of 5/11 = 0.4545 = 45%
| Page Request | a | b | a | c | a | b | d | b | a | c | d |
| Page Fault at start of time slice | * | * | * | * | * | * | |||||
| Page Frame 1 | a | a | a | a | a | a | a | a | a | a | a |
| Page Frame 2 | b | b | b | b | b | b | b | b | b | d | |
| Page Frame 3 | c | c | c | d | d | d | c | c | |||
| Stack .1 (Top): Most Recently Used | a | b | a | c | a | b | d | b | a | c | d |
| Stack .2 | a | b | a | c | a | b | d | b | a | c | |
| Stack .3: Oldest in Memory | b | b | c | a | a | d | b | a | |||
| Stack .4: Swapped Out | c | c | c | d | b |
6 page faults in 11 time steps yields a
success rate of 5/11 = 0.4545 = 45%
failure rate of 6/11 = 0.5454 = 55%
The First-in First-out yielded a more favorable success rate than the Least-Recently-Used method.
You cannot make a general statement from just one sample.
If you assume that there is a uniform chance of any one of the pages being selected at each time step, independently of what has happened in the past, then the probability of no page fault is 75% from one step to the next step. The chance of a page fault is 25%. This is a Bernoulli trial with P(page fault) = 0.25. The chance of a specific number of page faults over a given number of time steps is distributed according to the Binomial distribution. This identified bounds on performance compared to real job streams. The more you know about the characteristics of a job stream, the better you should be able to do compared to uniform random selection.
| Page Request | a | b | a | c | a | b | d | b | a | c | d |
| Page Fault at start of time slice | * | * | * | * | * | * | |||||
| Page Frame 1 | a | a | a | a | a | a | a | a | a | a | a |
| Page Frame 2 | b | b | b | b | b | d | b | b | b | b | |
| Page Frame 3 | c | c | c | c | c | c | c | d | |||
| Stack .1 (Top): Most Recently Used | a | b | a | c | a | b | d | b | a | c | d |
| Stack .2 | a | b | a | c | a | a | a | b | a | a | |
| Stack .3: Oldest in Memory | b | b | c | c | c | c | b | b | |||
| Stack .4: Swapped Out | b | d | d | d | c |
This approach eliminates the need for a stack. Only the Stack .1 (Top) element is used for decision making. This reduces the amount of memory needed for supporting the memory management technique. It does not require sophisticated coding to implement. It has the same performance statistics as the Least Recently Used algorithm for this specific data set. FIFO gave better results for this data set.
The principle of locality argues against using this Most Recently Used algorithm.
Problem 9. Given that main memory is composed of four page frames for public use, use the following table to answer all parts of this problem:
| Page Frame | Time When Loaded | Time When Last Referenced | Referenced Bit | Modified Bit |
| 0 | 126 | 279 | 0 | 0 |
| 1 | 230 | 280 | 1 | 0 |
| 2 | 120 | 282 | 1 | 1 |
| 3 | 160 | 290 | 1 | 1 |
| Stack Position | Page Frame | Time when Loaded |
| Stack .1 (Top): Newest page frame loaded in memory. | 1 | 230 |
| Stack .2 | 3 | 160 |
| Stack .3 | 0 | 126 |
| Stack .4: Oldest page in memory. | 2 | 120 |
Page frame 1 would be swapped out by FIFO if a need for swapping occurred in the next time step.
| Stack Position | Page Frame | Time when Last Referenced |
| Stack .1 (Top): Most recently referenced page frame loaded in memory. | 3 | 290 |
| Stack .2 | 2 | 282 |
| Stack .3 | 1 | 280 |
| Stack .4: Least recently referenced page frame in memory. | 0 | 279 |
Page frame 0 has the oldest entry in the "Time when last referenced" column. LRU would choose this page frame if a page frame needed to be swapped out.
Page frame 3 has the youngest entry in the "Time when last referenced" column. MRU would choose this page frame if a page frame needed to be swapped out.
There is not enough information given to answer this question.
Problem 11. Given three subroutines of 700, 200, and 500 words each, if segmentation is used then the total memory needed is the sum of the three sizes (if all three routines are loaded). However, if paging is used then some storage space is lost because subroutines rarely fill the last page completely, and that results in internal fragmentation.
Determine the total amount of wasted memory due to internal fragmentation when the three subroutines are loaded into memory using each of the following page sizes:
Let A be the 700 word subroutine. Let B be the 200 word subroutine. Let C be the 500 word subroutine. Let an underscore "_" represent wasted space.
| 100 word boxes | A | A | A | A | A | A | A | _ | B | B | C | C | C | C | C | _ |
200 words of memory are wasted due to internal fragmentation.
| 100 word boxes | A | A | A | A | A | A | A | _ | _ | _ | B | B | _ | _ | _ | C | C | C | C | C |
600 words are lost due to internal fragmentation.
| 100 word boxes | A | A | A | A | A | A | A | _ | _ | _ | _ | _ | B | B | _ | _ | _ | _ | C | C | C | C | C | _ |
1000 words are lost due to internal fragmentation.
| 100 word boxes | A | A | A | A | A | A | A | B | B | _ | _ | _ | _ | _ | C | C | C | C | C | _ | _ |
700 words lost due to internal fragmentation.
Problem 12. Given the following Segment Map Tables for two jobs:
|
|
|||||||||||||||||||||||||
| Job 1 Segment | Memory Location | Job 2 Segment |
| (3 after swap?) | 1024 | (0 after swap?) |
| 3 | 2048 | 0 |
| 0 | 4096 | |
| 1 | 6144 | 1 |
| 4 | 7168 | |
| (4 after swap) | 8192 | |
| 2 | 9216 | 2 |
Observations: There are initially 3 page frames that are used by segments of both jobs. When Job 1 Segment 3 is in memory, Job 2 Segment 0 is not in memory. When Job 1 Segment 1 is in memory, Job 2 Segment 1 is not in memory. When Job 1 Segment 2 is in memory, Job 2 Segment 2 is not in memory. Therefore, these segments cannot be shared.
Job 1 Segments 0 and 4 occupy page frames that are not occupied by any segment of Job 2. These are candidates for remaining in memory when Job 2 is swapped in. Therefore, Job 1 Segments 0 and 4 are possibly shared between Jobs 1 and 2. Since Job 1 Segment 4 is swapped, Job 2 would need to look up the current location of Job 1 Segment 4 to find it. Otherwise, Job 1 Segment 4 cannot be shared with Job 2.
The text's answer book gave an answer corresponding to the question wording, "Which page frames, if any, are shared between the two jobs?" The answer for that wording is: page frames starting at 2048, 6144, and 9216.
|
|
|||||||||||||||||||||||||
or
|
|
|||||||||||||||||||||||||
A swap would affect only one table, not both, since not both jobs occupy the page frame starting at 2048 simultaneously.
This discussion raises the interesting question of how to treat the case of using a system software reentrant routine. That routine would not be included in the segment map tables for independent jobs. A print spooler on a main frame is an example of such software.