Second Chance Algorithm – Page Replacement – Operating System

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. @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. 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

  3. 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

  4. 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 ??

  5. 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

  6. @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.

  7. 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)

  8. 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

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

  10. A cleaner implementation in Java:
    http://raadthinks.blogspot.com/2016/05/lru-least-recently-used-page.html

  11. 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.

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

  13. in this type of algorithm we set the arrival time of the original victim to the current time……
    thus your method is wrong………
    please look into it

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

  15. 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.

  16. 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.

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

  18. 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

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

  20. 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

  21. 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

  22. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *