# Second Chance Algorithm – Page Replacement – Operating System

So I am going to need the reference string back, yes please. I need Indian accent Now, what are we going to do is; we are going to use second chance algorithm I think this was the first movie script that I wrote in my life ( with title second chance) All right, let us start with page trace So I am going to show empty frames first As I said, we are going to take a reference bit for each page in the memory so first, 2 goes in nobody goes out, right initially the reference bit is set to 0 (zero) so 2 goes in, nobody goes out and there is a page fault next, we require 3 in the memory there is a space in the frame, so 3 goes in, nobody goes out and there is a page fault reference bit of 2 remains 0 (zero) reference bit of 3 is again initially set to 0 (zero) Now we require 2 again, but 2 is already in the memory So nobody goes in, nobody goes out there is no page fault as nobody goes in nobody goes out. but the important thing to understand here is that; because 2 was referenced again; and there was no page fault, reference bit of 2 is set to : 1 and that of 3, it remains 0 (zero) so whenever a certain page repeats itself causing no page fault, its reference bit is set to 1 Now there is 1 (page no) required and there is an empty frame 1 goes in, nobody goes out, so page fault (only when nobody goes in or out, there is no page fault) reference bit of 2 remains 1 that of 3 remains 0 and as 1 is new, its reference bit is set to 0 next we need 5 now, 5 is not there in the memory 5 needs to come in, so somebody needs to be replaced for that we have three potential candidates 2, 3 and 1 whom do we replace here? good news is, we are using the FIFO variant of the second chance algorithm so usually we will apply the FIFO (first in first out) rule whoever has come first, out of these 2, 3 and 1 will make way for 5 2 has come first so ideally if you are using plain FIFO you should replace 2 but because this is Second Chance Algorithm we have to take one more factor into consideration that factor is; the reference bit value now here, the actual victim is 2 according to FIFO (first in first out) but because 2’s reference bit is set to 1, it gets a second chance and in that case the next victim (i.e 3 here ) falls in line that is 3 FIFO applies without 2 now FIFO applies only to 3 and 1. And in that case 3 as it came first is our victim to be replaced so we replace 3 with 5 so 5 comes in , 3 goes out 2, 5, 1 and as 2 has got its second chance its reference bit is reset to 0 (zero) 5 is the new one, so its reference bit is set to 0 and 1’s reference bit was already 0 so now we again require 2 fortunately 2 is already there in the memory so nobody goes in, nobody goes out so no page fault but there is one more thing to consider because 2 is coming back again, saving us a page fault its reference bit will be set to 1 next we have 4 as 4 is not there in the memory, so 4 needs to come in the memory, that means somebody needs to go who will go? 2, 5 or 1 so this is a FIFO variant, right? so if you only apply FIFO rule, 2 is the oldest but again 2 has got a lifeline 2’s reference bit is set to 1, so it is out of consideration out of 5 and 1 who is oldest? 1 is oldest, so 1 is our victim and will be replaced by 4 and as a result of the second chance, 2’s reference bit is set to 0 (more like a reset) 4 is new in the memory so its reference bit is automatically set to 0 (zero) now we require 5, fortunately 5 is already there so good news for 5, he is going to get rewarded so nobody comes in, nobody goes out hence no page fault and 5 is going to get rewarded with by setting its reference but value as 1 so 5 is now safe from any elimination or replacement so now, what do we require next? 3, is 3 there in the memory? NO so 3 needs to come in, that means somebody needs to go so who will go? out of 2, 5 and 4 if we apply the FIFO rule, 2 needs to go as 2 is the oldest and this time 2 doesn’t have the power of (reference bit value) of 1 2 doesn’t have its reference bit set to 1 so 2 this time, you are not to be ..(SAVED) so 2 goes out and 3 comes in reference bit of 3 is set to 0 (zero) of 5 remains unchanged and that of 4 remains 0 and there is of course a page fault Now we require 2 somebody needs to go out if you apply the plain FIFO, then who is the oldest amongst 3, 5 and 4? 5 is the oldest 5 had come first amongst 3, 5 and 4 but we can not replace 5 because 5 has the power of its reference bit set to 1 now because 5 is out of race, there are only two possible victims 3 and 4 out of which 4 had come in earlier, so 4 will go out 2 will come IN and 4 will go OUT and yes, page fault now 5 has used its second chance, so its reference bit is reset to 0 (zero) 3’s is 0 and 2 is a new entry so its reference bit is 0 and of course there is a page fault now next thing we need is 5 again so there is no page replacement here, so no page fault as a reward for saving us a page fault 5’s reference bit gets set to 1 3’s and 2’s remains same (zero) now next thing we require is 2, good news 2 is already there i.e nobody goes IN, nobody goes OUT so no page fault and as a reward for saving us a page fault, 2’s reference bit is set to 1 unfortunately there is no time now to use that reward point ( as we have exhausted the reference string) and we are done with the page trace If we look at the number of page faults; it is 7 (seven) 7 number of page faults, so you could say it is much better than some of the other page replacement algorithms that we have seen so this is the Second Chance Algorithm of which we studied the FIFO variant of it

## 100 thoughts to “Second Chance Algorithm – Page Replacement – Operating System”

1. BBarters says:

@yousri mami frame 5 is still there because, its reference bit is set to 1….when a frame's reference bit is set to 1, it doesn't get replaced instead its given one more chance at the expense of setting its reference bit to 0 making it eligible for replacement next time.

2. Assassins Bunny says:

hi good job for this video, can you come up with LRU-least used algorithm for the same example TQ

3. Phamster says:

Thank you that helped me out a lot. Very straightforward and comprehensive.

4. AJ says:

thanks bro…helped me alot

5. kazi shohel says:

thanks bro……..

6. Yanuar Tri Aditya Nugraha says:

good thing i've found this! i hope it helps me on OS exam 🙁

7. Valkon says:

Nice video, but what if we have a modified bit also?

8. aminos temo says:

thank you

9. Gumball says:

well explained, thank you

10. Pujan Shah says:

Awesome.

11. Sanika Patwardhan says:

Thank you! Great explanation

12. GoCanucks89 says:

thank you vally much

13. Jeff Penner says:

Very detailed analysis. Thanks for the lesson on second chance (clock) algorithm.

14. Memo you says:

At second 8.21, why we replaced 4 with 2? shouldn't it be replaced with 3 cuz 3 is older than 4? thank you

15. 陳奕甫 says:

why the ninth page 5's reference bit is still set to 1 ? 2 is already set to 3 , doesn't set the 5's reference bit to 0?  sorry about my poor language

16. soham joshi says:

explain properly! suddenly u start off with ref bits and ur scheme.

17. Tara gurung says:

So the reference bit is set to 1 only when there is page hit . ? if there suppose 5 got second chance and after that we have to replace another bit which is completely new and not in the frame. So we go through FIFO in that or which page will get a second chance

18. Atal Pandey says:

Say, all the frames have their reference bit set to 1. Now which one is kicked out ? And what happens to the reference bits of the other frames, the frames that aren't removed ??

19. Jamrock86 says:

my teacher says when a new frame is entered the ref bit is set to one what kind of variation is that if it is right

20. Kishan Chand says:

@BBaters ,in 3'rd last table , search will start from old to new (since it is arranged in FIFO) and among 4,5,and 3 (in previous table) 4 is oldest .search will stop at 4 only.and 5 's R bit will remain 1.

Good job

22. Byeonggon Lee says:

23. Navdeep Singh says:

Only INDIAN accent 🙂 very helpful video Thanks

24. Suraj Mehare says:

very nice explanation which is not given in to few good books.

25. Wicem Khedimallah says:

You are the best teacher !!

26. iqra bhat says:

i can say it z one of the bst video in replacmnts..
thankx a lot sir

27. Magda M says:

Perfectly explained! Thank you!

28. Yash Tamakuwala says:

Thanks a lot Sir. You explained it better than our reference book's explanation.

thank you sir its a very good lecture.

30. MB says:

I think there is a big mistake. When R of B is 1 and you reset it to 0, then you have to move B to the tail of the list (see Book of Tanenbaum Page 212)

31. çağrı Kaymak says:

guys there is a mistake at https://youtu.be/voiL2-nQmlU?t=355 because we put 2 to end of queue so its refererence bit must be still 1 not 0

32. Bock says:

I think there is mistake after time : 7:24 . Since 5 is just referenced bit of 5 should be 0 this time.

34. Rational Spongebob says:

Shit son you in a cave?

35. Awais Ali says:

A cleaner implementation in Java:

36. yavuz kağan topak says:

thank you sir !!!

37. Emelda Mokheseng says:

This was so helpful. Thank you.

38. kirtipal dayma says:

awesome work!!!!!!!!!!!!!11

39. Saroj Maharjan says:

in fifth and sixth iteration …..what if we have 3 and 3 instead of 5 and 2?

40. Lochu'an Chang says:

A big mistake, When a page gets a second chance, its reference bit is cleared, and
its arrival time is reset to the current time.

41. Mazhar Imam Khan says:

Thank you. It was very helpful

42. PlayDis says:

thanks mate 🙂

43. Sanjay Mahaveer says:

very nice explanation!!!

44. Manish Periwal says:

reference bit of 5 when 3 comes in the (9th number) should be set to 0,since there was a page fault.

45. Hesa Hesa says:

thaks very much i am understand this easy

46. Luigi Lantin says:

legit!

47. Ravi Sharma says:

please make playlist for separate video lecture it's awesome

48. Calvin Lau says:

Very clear explanation, good use of visuals. Thank you for this video!

49. Reed Wei Wei says:

I suggest to make ur accent clear.. btw ur the best explanator hahaha!

50. Tutorials says:

51. Lounes Naïma says:

thaanks you are the best!!

what about the time?? Don't it matters?

53. Mike K. says:

Thank you!

54. shivam chauhan says:

awesome description .. and thanks for saving me for my mid sem exam

55. Dhaval Chandarana says:

sir i am getting what u describe in this video. buy my question is can solve below example using same method. SCA.
041424342404142434

56. Sampashree Nayak says:

It's totally wrong. where is the pointer?

57. murat dereköylü says:

great teaching, thank you

58. Xiaoyan Qu says:

When the first "4" comes, why did you bother "2" and check the reference bit ("2" was the "last" in)?

59. SeriousFox says:

What if same page is referenced twice? will the reference bit remain 1?

60. Amlan Deep says:

is this right or wrong…pls confirm me???

61. Asimaes says:

Mejores comentarios
Silvia Barela
Silvia BarelaHace 1 año
en serio?? no me digas…
Responder 1

62. sravanthi sravs555 says:

I think it's wrong

63. Anit Aggarwal says:

in this type of algorithm we set the arrival time of the original victim to the current time……

64. Anurag Gupta says:

The solution is wrong. Refer this for correct one http://www.mathcs.emory.edu/~jallen/Courses/355/Syllabus/9-virtual-mem/SC-replace.html

65. ImperatorM says:

Very Big Mistake. It is not as easy as shown in this video. You have to think in a "clock". After 2 has got his second chance, it went to the end of the Queue, so it is not the "oldest" one, it is the "younges" one.

66. Trương Huỳnh Hòa says:

thanks for this lesson, it's very useful for me in the exam

67. aria faramarzy says:

this is wrong guys ,,, when a page is given a second chance it's arrival time resets and that page becomes the youngest one , and it goes to the end of FIFO Queue.

68. Jacky Wong says:

will the reference bit become 2 or more?

69. Alexa Roye says:

thats is wrong

70. Nandkishor Nangre says:

Explain very well but I found you funny haha

71. Miguel moreno-orta says:

Well put. The words at the bottom helped a lot as well. Thank you for a clean video.#allTheWayFromTexas

72. MR PAUL CREATIONS says:

73. Bedo Calaway says:

Best explanation of second chance on Youtube! Glad I found you 😩

74. Alba Mustafaj says:

This is wrong, at 4:00 2 should go at the end of the table and its R bit should become 0. It shouldn't stay in the beginning of the table you are violating the rule

75. Patrick Castro says:

bacc 2 u

spacchi come la merda …you saved my life dude … india rulz

77. Jeffrey Dilley says:

Nice work, concise, easy to understand! Thank you, as an American I appreciate how well you explain and how clear your english is 🙂

78. Ritikesh Singh says:

What if all pages have 1 as a reference bit ? Please answer

79. Yash Behara says:

good explanation!.. cheers

80. Apostolos Mavropoulos says:

thnks!

81. benaloney says:

Cheers Bud!

82. Linus Castelino says:

What happens when all the candidates have their reference bits set to 1?
For example :
Input – 1 2 3 4 4 3 2 1 5
Frame size – 4

83. Saman Singh says:

There is an error here after 5:05. When Page 4 is to be brought into memory, the pointer that acts as head of round-robin replacement(i.e. from where we start the replacement Algo) points at Page 1 and hence, the reference bit of Page 2 will not be changed since Page 1 will be replaced immediately!

Refer : http://www.mathcs.emory.edu/~cheung/Courses/355/Syllabus/9-virtual-mem/SC-replace.html

84. bashir uddin says:

osam

85. Aman Kumar says:

Thanks! Helped a lot!

Best explanation ever .

87. Hail Kill n Die says:

07:55 … 3 should have gone instead of 4

88. 3CHONPRODUCTIONS says:

89. mihir sharma says:

Sir you did a mistake at the insertion of 3 , bit of 5 will be 0

90. Prem prakash says:

U explained perfectly, thanks.

91. Viplove Mahi says:

Lru approximation is same as sca?

92. ajay singh says:

93. Exotic Me says:

isnt this wrong…?

94. shjimb says:

😄

95. warrior100girl says:

thanks man! Still a chance to pass my OS exam. 😀

96. Md. Golam Sarwar 1604080 says:

very clear to understand

97. AKT only says:

sir you have done a small mistake when 9 th page replacement when 4 will came then 3 will be out bcz 3 is the oldest not 4.

98. ANKITA DEVI says:

tnq sir ji

99. asif nazar says:

Perfect understanding so i appreciate and u r good teacher for the nation

100. skyline 101 says:

confusion starts at 7:06