Simulation Algorithms
INTRODUCTION ALGORITHMS:
The different policies are handled by developing modules that implements the policies and are called in the algorithm when required. The output that each module produces is the number of page faults under the corresponding policy. The main algorithm then puts these outputs in a tabular form for comparison. The simulator is run for 10000 times and the outputs are arranges in the grid.
Based on the number of page faults that are produces during a run the policy that gives least number of page faults is identified. After the completion of 10000 runs the statistics are collected that shows how many times a particular policy has produced the least number of page faults. The number of times each policy produces least number of page faults are also printed as output. The algorithm is as follows:
1: Repeat Steps 2 to 12 for Count: =1 to 10000
2: Generate random reference string of addresses.
3: Generate number of frames of physical memory randomly.
4: Call ModuleFIFO (Frames, FIFO).
5: Call ModuleOptimal (Frames, OPT).
6: Call ModuleLRU (Frames, LRU).
7: Call ModuleNRU (Frames, NRU).
8: Call ModuleNFU (Frames, NFU).
9: Call ModuleSecondChance (Frames, SC).
10: Call LeastCount(FIFO,LRU,NRU,NFU,SC,MIN)
11: Switch (MIN)
Case 0:
FIFO_Count ++
Case 1:
LRU_Count ++
Case 2:
NRU_Count ++
Case 3:
NFU_Count ++
Case 4:
SC_Count ++
12: Call PrintStatistics().
13: Exit.
MAIN RESULT:
It was observed that FIFO policy has produced least number of page faults for 1094 runs while the LRU policy was good for as much as 3020 times. The optimal policy always produced minimum number of page faults for all the runs so it was not considered during this calculation.
On analyzing the results, it can be seen that the NRU policy has produced minimum page faults for 3053 times. The LRU policy was good for nearly equal number of times. But NRU policy is often considered one of the crudest policies. Although it is easy to understand and implement, its performance is not optimal. But the implementation could be expensive because of the fact that for each page two bits are maintained and the reference bits would be needed to clear for each clock period.
The LRU policy produced nearly equal count thus it can be considered a good candidate for implementing in operating systems. The implementation of this policy is often expensive in case linked list is used to keep the pages. At the back of list is the least recently used page, and at the front is the most recently used page.
The cost of this implementation lies in the fact that items in the list will have to be moved about every memory reference, which is a very time-consuming process. But LRU is considered better than NRU in the fact that it keeps track of page usage over a short period of time, while NRU just looks at the usage in the last clock interval. The performance of FIFO, NFU and Second Chance policies were not so good. After analyzing the results, it can also be observed that each policy behaves differently in different situations.
Different situations lead to different reference strings. In the output of the simulator, this situation is depicted also when the page faults for 27 frames were different for two different runs. The amount of physical memory was same but different reference string was applied. The page faults produced were different.
The FIFO policy produced 7294 and 7316 page faults in these two runs respectively. In the first run the NFU policy produces least page faults (7239) whereas in the next run under 27 frames the Second Chance policy produced minimum page faults (7287) .Thus no policy might be expected to perform good in all situations.
About the Author:
Dr. Vikram Singh combined Manjeet Kaur,JRF/M.C.A
Article Source: ArticlesBase.com - Simulation Algorithms