LRU page replacement algorithm

Prob. How many page faults will occur with a reference string 0,1,7,2,3,2,7,1,0,3?
There are four frames which are initially empty.
Use
  1. LRU Page replacement algorithm
Sol.


LRU Page replacement algorithm:


LRU stands for least recently used.
It replaces the page that has been referenced for longest time.
In FIFO Page replacement algorithm problem is, it may replace heavily used pages.

0172327103


Above table is an example of page frame, which is empty initially. And first page is 0.


So 0 will get added here, but there will be a page fault.


What is a page fault?
The page which is requested by the program is not present in the RAM, that means there is a page fault.


0 was not present in the page frame so there was a page fault.

0172327103
0
F


The next page is 1 and there is space for two more pages.So 0 will remain there and 1 will get added there.And again there will be a page fault.

0172327103
00
1
FF


The next page is 7, which is not in the page frame, but there is place for one more page, so 0 and 1 will remain there and 7 will get added. And there will be a page fault.

0172327103
000
11
7
FFF

The next page is 2, which is not in the page frame, but there is place for one more page, so 0, 1 and 7 will remain there and 2 will get added. And there will be a page fault.

0172327103
0000
111
77
2
FFFF


I have given red color when there is a page fault, and black color for rest of the pages, and green color for page hits.


Now the page frame is full, and the next page is 3 which is not there in the page frame. So we need to remove one page from the page frame, so we can add 3 there.


Now see in the table below,


2 is most recently used page, than 7 and than 1 and than 0.
So 0 will get removed, and 3 will get added there. And there will be a page fault because 3 was not present in the page frame. And 1, 7, and 2 will remain there.


The next page is 2, which is already present in the page frame. This is known as page hit.


What is page hit ?
The page which is requested by the program is already present in the RAM/page frame is known as page hit.


0172327103
000033
11111
7777
222
FFFFFH

The next page is 7, which is already present in the page frame. This is known as page hit.

0172327103
0000333
111111
77777
2222
FFFFFHH
The next page is 1, which is already present in the page frame. This is known as page hit.

0172327103
00003333
1111111
777777
22222
FFFFFHHH
The page frame is full, and the next page is 0 which is not there in the page frame. So we need to remove one page from the page frame, so we can add 0 there.


Now see in the table below,


1 is most recently used page, than 7 and than 2 and then 3.
So 3 will get removed, and 0 will get added there. And there will be a page fault because 0 was not present in the page frame. And 1, 7, and 2 will remain there.


The page frame is full, and the next page is 3 which is not there in the page frame. So we need to remove one page from the page frame, so we can add 3 there.


Now see in the table below,


0 is most recently used page, than 1 and than 7 and then 2.
So 2 will get removed, and 3 will get added there. And there will be a page fault because 3 was not present in the page frame. And 0, 1, and 7 will remain there.




Total pages present in the pages is = 10.

0172327103


Total page faults = 07.

FFFFF


FF


Total page hits = 03






HHH



Operating Systems:

EasyExamNotes.com covered following topics in Operating Systems.
    A list of Video lectures

    Python Programming ↓ 👆
    Java Programming ↓ 👆
    JAVA EasyExamNotes.com covered following topics in these notes.
    JAVA Programs
    Principles of Programming Languages ↓ 👆
    Principles of Programming Languages
    EasyExamNotes.com covered following topics in these notes.

    Practicals:
    Previous years solved papers:
    A list of Video lectures References:
    1. Sebesta,”Concept of programming Language”, Pearson Edu 
    2. Louden, “Programming Languages: Principles & Practices” , Cengage Learning 
    3. Tucker, “Programming Languages: Principles and paradigms “, Tata McGraw –Hill. 
    4. E Horowitz, "Programming Languages", 2nd Edition, Addison Wesley

      Computer Organization and Architecture ↓ 👆

      Computer Organization and Architecture 

      EasyExamNotes.com covered following topics in these notes.

      1. Structure of desktop computers
      2. Logic gates
      3. Register organization
      4. Bus structure
      5. Addressing modes
      6. Register transfer language
      7. Direct mapping numericals
      8. Register in Assembly Language Programming
      9. Arrays in Assembly Language Programming

      References:

      1. William stalling ,“Computer Architecture and Organization” PHI
      2. Morris Mano , “Computer System Organization ”PHI

      Computer Network ↓ 👆
      Computer Network

      EasyExamNotes.com covered following topics in these notes.
      1. Data Link Layer
      2. Framing
      3. Byte count framing method
      4. Flag bytes with byte stuffing framing method
      5. Flag bits with bit stuffing framing method
      6. Physical layer coding violations framing method
      7. Error control in data link layer
      8. Stop and Wait scheme
      9. Sliding Window Protocol
      10. One bit sliding window protocol
      11. A protocol Using Go-Back-N
      12. Selective repeat protocol
      13. Application layer
      References:
      1. Andrew S. Tanenbaum, David J. Wetherall, “Computer Networks” Pearson Education.
      2. Douglas E Comer, “Internetworking with TCP/IP Principles, Protocols, And Architecture",Pearson Education
      3. KavehPahlavan, Prashant Krishnamurthy, “Networking Fundamentals”, Wiley Publication.
      4. Ying-Dar Lin, Ren-Hung Hwang, Fred Baker, “Computer Networks: An Open Source Approach”, McGraw Hill.