page fault

Discussion in 'Engineering Concepts' started by huda, Mar 25, 2009.

  1. huda

    huda New Member

    Joined:
    Jan 22, 2009
    Messages:
    49
    Likes Received:
    0
    Trophy Points:
    0
    hi,
    I want to know ,if RAM was empty ,is the first request of cpu be page fault or not?

    many thanks
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    I can only really answer this with a circular argument: if by "first request" you mean "first request of something that's in the swap file", then yes, a page fault will be generated. If it requests something that isn't in the swap file then you won't get a page fault.

    A page fault occurs when a page the OS wants to load has been moved out to swap, and this is not dependent on memory contents. RAM can be full, empty or anywhere in between; if the data wanted is in swap, then you will get a page fault.

    Emptying RAM won't necessarily move stuff from the swap file back into RAM; it will normally be left there until it's needed.
     
  3. huda

    huda New Member

    Joined:
    Jan 22, 2009
    Messages:
    49
    Likes Received:
    0
    Trophy Points:
    0
    thank you very much ,I have a bit confused regarding swap file

    i will be more clear.
    if I have 4 page memory ,and it was empty at first. there are references from cpu :
    3, 2, 1, 5, 3, 6, 2, 1, 7, 4, 6, 2, 4
    can I consider 3,2,1,5 the first four references are pages fault or not? this is my question specifically
     
  4. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    No. Let's say you want to run a few programs at the same time, and again you've got 4 pages.
    Start program A that uses two pages; memory contains A1 A2 [blank] [blank]
    Start program B that uses 1; memory contains A1 A2 B [blank]
    Start program C that uses 2; memory contains A1 A2 B C1 and it wants to load C2.
    The computer is out of memory, but it has some swap file.
    The oldest page gets swapped out; that's A1. So now memory is [blank] A2 B C1.
    C2 can be loaded, so we then get C2 A2 B C1.

    We haven't had any page faults yet. Now we'll create the first page fault.

    Suppose we now want to activate program A again and specifically we want to use A1. A1 isn't in memory but it is in the swap file. THIS is a page fault.
    So using the "oldest gets swapped out" algorithm again, that's A2, so A2 goes out to swap and memory is C2 [blank] B C1.
    There's now somewhere to put A1 so memory now contains C2 A1 B C1.

    So the program is running through A and gets to the point where it needs A2. A2 is not in memory but it is in the swap file, so we now get our second page fault.
    The oldest is B so this gets swapped out -> C2 A1 [blank] C1.
    And A2 gets swapped in -> C2 A1 A2 C1.

    And now you also see the critical importance of the virtual memory manager and the need to remap addresses. Initially A1 and A2 were loaded into pages 1 and 2. But now they are in pages 2 and 3.


    So now over to your example, where 1-7 are blocks of data stored on the hard disk and memory and swap start out empty.
    Sequence is 3, 2, 1, 5, 3, 6, 2, 1, 7, 4, 6, 2, 4, and we have 4 pages.

    3, 2, 1, 5 - no problem, this all gets loaded into memory. Page faults (PF): 0.
    3 - no problem; 3 is in memory. PF:0
    6 - OK, so we now swap out the least recently used (LRU). 3 was used in the previous step so the oldest is now 2; this gets swapped out and 6 loaded into memory. Still no PF's, and memory now contains 3 6 1 5.
    2 - Page fault, because 2 is not in memory but it is in the swapfile. LRU is 1, swap it out, swap 2 back in, memory contains 3 6 2 5. PF:1 - our first page fault.
    1 - PF:2. LRU is 5; swap that out, swap 1 in; memory contains 3 6 1 5.
    7 - no PF because 7 is not in swap. However we need to shift something out to swap. LRU is 5, 5 out 7 in, memory=3 6 1 7.
    4 - no PF. LRU is 3, swap 3 out and load 4 from disk; memory=4 6 1 7
    6 - in memory, so the only thing the OS needs to do here is to update the "last used" time for 6 to keep the LRU algorithm going.
    2 - PF(3rd); LRU is 1; 1 out, 2 back from swap, memory=4 6 2 7
    4 - no PF, just update block 4's last used time.

    So with 4 pages you get 3 page faults.

    Now suppose there are 5 pages. Same sequence: 3, 2, 1, 5, 3, 6, 2, 1, 7, 4, 6, 2, 4
    3,2,1,5,3,6 - no problem; memory is 3 2 1 5 6; LRU list would read 2 1 5 3 6
    2: in memory so the LRU list is updated to 1 5 3 6 2 (most recent at the end).
    1: in memory, no PF, LRU list 5 3 6 2 1
    7: move LRU(5) to swap, load in 7, memory is 3 2 1 7 6; LRU list is 3 6 2 1 7
    4: move 3 to swap, load in 4, memory is 4 2 1 7 6; LRU list is 6 2 1 7 4
    6: in memory so no PF, just update the LRU list to 2 1 7 4 6
    2: in memory so no PF, just update the LRU list to 1 7 4 6 2
    4: in memory so no PF, just update the LRU list to 1 7 6 2 4

    So there are no page faults at all here because at no point did the CPU request a page that was in swap.

    3 pages
    3, 2, 1: no problem, memory 321, LRU 321.
    5: memory 521; LRU 215; swap contains 3
    3: PF; mem 531; LRU 153; swap contains 2
    6: swap out 1; mem 536; LRU 536; swap contains 21
    2: PF; swap out 5, mem 236; LRU 362; swap 15
    1: PF; swap out 3, mem 216; LRU 621; swap 35
    7: swap out 6, mem 217; LRU 217; swap 356
    4: swap out 2, mem 417; LRU 174; swap 3562
    6: PF: swap out 1, mem 467; LRU 746; swap 3521
    2: PF: swap out 7, mem 462; LRU 462; swap 3517
    4: in memory so just update LRU to 624.

    NB: I may have made a mistake in the above; it's nearly midnight, so if you spot something odd then point it out and I'll double check, fix it if it's wrong or explain it if it is actually correct.
     
  5. huda

    huda New Member

    Joined:
    Jan 22, 2009
    Messages:
    49
    Likes Received:
    0
    Trophy Points:
    0
    thank you very much for all explanations.
    I would like to say , there is no mistake.
    but I want to say something please.
    in fact , I understood well that the first pages are requested by cpu isn't page fault . that is good and what Morris mano agree with you in that in his book (computer system architecture)
    But he stated that when a cpu requests for ex. page 6 as in earlier ex. ,in this case there is a page fault ,and he didn't state if this page in swap file or not.
     
  6. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    This Mano book seems to be more trouble than it's worth. Since the choice of course books is yours to make, can I recommend you shred this one and get something that actually explains things clearly without leaving you confused?


    As I understand it a page fault is when the CPU tries to access something that was loaded into RAM but that has since been moved out to the page file.

    So 6 is not a page fault because it hasn't been loaded into memory yet.

    ...a penny drops...

    ...that is, UNLESS 1-7 are pages that have been loaded into memory by previous operations, and that memory has been cleared (for example by 8 being loaded into memory and taking up all four pages, thus swapping all 1-7 out to swapfile). In that case then not only will 6 be a page fault but the preceding requests for 3, 2, 1, 5 (not 3 because it's already in RAM) will also be page faults.

    So the answer to your opening question, now I know the full context, is Yes,

    and in effect the complete sequence you're asking about is 1-7 iin whatever order, then the hypothetical 8a 8b 8c 8d, unload 8* (so RAM clear at this point), *THEN* 3, 2, 1, 5, 3, 6, 2, 1, 7, 4, 6, 2, 4.
     
  7. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Alternatively if you want to stick with Mano then get a few more books on the same subject and read them as well. A single author's take on a complex technical subject is not enough anyway and in effect when people go to university that's what they want. If all they're getting is a potted form of the Mano book then they can stay at home and read it themselves, and save themselves a whole load of trouble and expense.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice