Assignment: Chapter 2 & Chapter 3
(Problem 1): If a program has 471 bytes and will be loaded into page frames of 100 bytes each, and the instruction to be used is at byte 132, answer the following questions:
a. How many pages are needed to store the entire job?
b. Compute the page number and the exact displacement for each of the byte addresses where the data is stored. (note: page numbering starts at zero).
a) 471/100 + 1=5
b) To store page number: 3 bits
To store offset:7 bits
(Problem-2): Given that main memory is composed of only three page frames for public use and that a seven-page program (with Pages a, b, c, d, e, f, g) that requests pages in the following order:
a, c, a, b, a, d, a, c, b, d, e, f
(a). Using the FIFO page removal algorithm, indicate the movement of the pages into and out of the available page frames (called a page trace analysis). Indicate each page fault with an asterisk (*). Then compute the failure and success ratios.
(b). Increase the size of memory so it contains four page frames for public use. Using the same page requests as above and FIFO, do another page trace analysis and compute the failure and success ratios.
Given that main memory is composed of three page frames for public use and that a seven-page program (with pages a, b, c, d, e, f, g) requests pages in the following order: a, b, a, c, d, a, e, f, g, c, b, g
|Total faults: 10||Failure: 10/12||83.33e %|
Total faultless: 2 Success: 2/12 16.66e%
|Total faults: 9||Failure: 9/12||75 %|
Total faultless: 3 Success: 3/12 25%
(Problem 1): Given the following information:
a. Use the best-fit algorithm to indicate which memory blocks are allocated to each of the three arriving jobs.
b. Use the first-fit algorithm to indicate which memory blocks are allocated to each of the three arriving jobs.
a) For the best fit algorithm, allocates the smallest free partition which meets the requirement without wasting much memory. So Job A needs 57k so it can fit in any block of the four. but it takes Block 3 so that much memory is not wasted.
Job B needs 920k it cannot fit in both Block 2 and block 1, but it has to use two blocks to fit. Even so much memory is wasted so it fits in Block 2 and takes remaining from other block.
Job C also fits in block 3
Job D can fit in Block 1 and 2 but it fits in block 1 as block 2 is used.
b) For the first fit algorithm, means pick the first block that meets the requirement.
For Job A, it takes first block 1
Job B it takes block 2 but does not fit so it has to wait for Job A
Job C it takes block 3 as per the requirement.
Job D it takes Block 4 but does not fit so it has to wait for other blocks as Job A or Job C to finish which has free space and then fits.
(Problem-2): Next-fit is an allocation algorithm that starts by using the first-fit algorithm but keeps track of the partition that was last allocated. Instead of restarting the search with Block 1, it starts searching from the most recently allocated block when a new job arrives. Using the following information:
Indicate which memory blocks are allocated to each of the three arriving jobs, and explain in your own words what advantages the next-fit algorithm could offer.
For Job A it takes for the block 1 and uses it 100k in it and then takes for block 2 for remaining to fit in it. The unused memory in block 2 would be 410k.
For job C it takes block 2 and uses 275k and the remaining memory of the block 2 is 85k
For job D, it takes block 2 which has 85k and uses it and then moves to block 3 uses it and for remaining 95k it moves to block 4 and uses 95k thus leaving 500k remaining unused in block 4.
The advantage of next fit is such that, when a new job is called it searches from the remaining block of memory so that much space is saved rather than wasting some amount of space in each block. Thus speed also is improved in next fit since if memory is released that is earlier in the heap for an application, it will check for that block first and fits there.