Go4Expert (http://www.go4expert.com/)
-   Engineering Concepts (http://www.go4expert.com/forums/engineering-concepts/)
-   -   page fault (http://www.go4expert.com/forums/page-fault-t16661/)

huda 25Mar2009 19:12

page fault
I want to know ,if RAM was empty ,is the first request of cpu be page fault or not?

many thanks

xpi0t0s 25Mar2009 21:12

Re: page fault
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.

huda 25Mar2009 22:34

Re: page fault
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

xpi0t0s 26Mar2009 05:12

Re: page fault
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.

huda 27Mar2009 00:41

Re: page fault
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.

xpi0t0s 27Mar2009 18:18

Re: page fault
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.

xpi0t0s 27Mar2009 18:20

Re: page fault
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.

All times are GMT +5.5. The time now is 03:44.