Block replacement algorithm fcs n belady anomaly

Block replacement algorithm in cache memory: FCFS and Belady's Anomaly

1. Block Replacement Algorithms FIFO & Belady's Anomaly Bindu Agarwalla

2. Block Replacement A replacement policy determines, out of all possible candidates, which one should be evicted from the cache upon arrival of a new piece of data. We evaluate an algorithm by running it on a particular string of memory references and computing the number of block misses. The string of memory references is called a reference string . Reference strings can be generated. Artifically (By using a random-number generator). We can trace a given system and record the address of each memory reference.

3. Block Replacement Algorithms First-in, First-out (FIFO) . Optimal. Least Recently used (LRU). For each algorithm, we will calculate The number of Hits. The number of misses. Hit Ratio (The number of Hits / Total number of attempts) The algorithm, that gives the more number of hits, will also increase the system performance by reducing the effective access time.

4. Block Replacement Algorithms Assumptions: Three blocks are given to the process. Initially all three blocks are empty. First-in, First-out (FIFO): When a block must be replaced, the oldest is chosen. Implementation: By using a FIFO Queue: We replace the block at the head of the queue. When a block is brought into memory we insert it at the tail of the queue.

5. First in First Out (FIFO) 7 1 2 3 4 2 3 3 2 1 2 1 7 1 Blocks : 3 Nos

6. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 7 *

7. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 7 7 * *

8. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 7 7 7 * * *

9. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 7 7 7 2 * * * *

10. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 7 7 7 2 2 * * * * Hit

11. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 7 7 7 2 2 2 * * * * Hit *

12. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 7 7 7 2 2 2 2 * * * * Hit * *

13. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 7 7 7 2 2 2 2 4 * * * * Hit * * *

14. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 2 7 7 7 2 2 2 2 4 4 * * * * Hit * * * *

15. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * *

16. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 2 *

17. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 2 2 * Hit

18. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 3 2 2 2 * Hit Hit

19. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 3 3 2 2 2 1 * Hit Hit *

20. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 3 3 2 2 2 2 1 1 * Hit Hit * *

21. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 3 3 2 2 2 2 2 1 1 1 * Hit Hit * * Hit

22. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 3 3 2 2 2 2 2 2 1 1 1 1 * Hit Hit * * Hit Hit

23. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 7 * Hit Hit * * Hit Hit *

24. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 7 7 * Hit Hit * * Hit Hit * *

25. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 3 3 2 2 2 2 2 1 2 2 2 1 1 1 1 1 7 7 7 * Hit Hit * * Hit Hit * * *

26. First in First Out (FIFO).. 7 1 2 3 4 2 3 3 2 1 2 1 7 1 1 1 1 1 3 3 3 3 2 2 7 7 7 2 2 2 2 4 4 4 * * * * Hit * * * * * 3 3 3 3 2 2 2 2 2 1 2 2 2 1 1 1 1 1 7 7 7 * Hit Hit * * Hit Hit * * * HIT = 5 Miss = 15 Hit Ratio = 25% (5/20)

27. Belady's Anomaly As we know, the number of BLOCK misses decreases with the increase in number of available blocks, but for some block- replacement algorithms, the block - misses may increase as the number of allocated blocks increases. This most unexpected result is known as Belady's Anomaly . The FIFO Algorithm suffers from this Anomaly. Consider the following reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

28. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 USING 3 BLOCK S

29. BELADY’S ANOMALY 1 * 1 2 3 4 1 2 5 1 2 3 4 5

30. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 2 1 1 * *

31. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 2 2 1 1 1 * * *

32. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 2 2 2 1 1 1 4 * * * *

33. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 3 2 2 2 1 1 1 1 4 4 * * * * *

34. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 3 2 2 2 2 1 1 1 1 1 4 4 4 * * * * * *

35. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 3 2 2 2 2 2 1 1 1 1 1 1 4 4 4 5 * * * * * * *

36. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 3 2 2 2 2 2 2 1 1 1 1 1 1 1 4 4 4 5 5 * * * * * * * Hit

37. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 4 4 4 5 5 5 * * * * * * * Hit Hit

38. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 3 1 1 1 4 4 4 5 5 5 5 * * * * * * * Hit Hit *

39. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 3 1 1 1 4 4 4 5 5 5 5 * * * * * * * Hit Hit * 4 3 5 *

40. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 3 1 1 1 4 4 4 5 5 5 5 * * * * * * * Hit Hit * 4 4 3 3 5 5 * Hit Total no of misses = 9

41. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 USING 4 BLOCK S

42. BELADY’S ANOMALY 1 * 1 2 3 4 1 2 5 1 2 3 4 5

43. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 2 1 1 * *

44. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 2 2 1 1 1 * * *

45. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 * * * * 4 3 3 2 2 2 1 1 1 1

46. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 * * * * Hit 4 4 3 3 3 2 2 2 2 1 1 1 1 1

47. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 * * * * Hit 4 4 4 3 3 3 3 2 2 2 2 2 1 1 1 1 1 1 Hit

48. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 * * * * * Hit 4 4 4 4 3 3 3 3 3 2 2 2 2 2 2 1 1 1 1 1 1 5 Hit

49. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 * * * * * Hit 4 4 4 4 4 3 3 3 3 3 3 2 2 2 2 2 2 1 1 1 1 1 1 1 5 5 Hit *

50. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 * * * * * * * Hit 4 4 4 4 4 4 3 3 3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 5 5 5 Hit

51. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 * * * * * * * * Hit 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 5 5 5 5 Hit

52. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 2 1 4 * * * * * * * * * Hit 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 5 5 5 5 Hit

53. BELADY’S ANOMALY 1 2 3 4 1 2 5 1 2 3 4 5 3 3 2 2 1 5 4 4 * * * * * * * * * Hit 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 5 5 5 5 Hit * No of Misses=10

54. THANK YOU