LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Linux Forums > Linux - Newbie
User Name
Password
Linux - Newbie This Linux forum is for members that are new to Linux.
Just starting out and have a question? If it is not in the man pages or the how-to's this is the place!

Notices


Reply
  Search this Thread
Old 05-26-2013, 12:00 AM   #1
jimwarlock
LQ Newbie
 
Registered: Apr 2013
Posts: 11

Rep: Reputation: Disabled
2 and 3 Level Page Table Question


Hello everyone.

I'm trying to revise for my upcoming exams and am struggling with some questions on the topic of page tables.

Here's the questions:

System with 1GB physical memory with a 42-bit virtual address space. Using a 4KB page size.
A process is currently using 18 MB of code segment (program codes and static data) starting at address virtual memory address 0, 40 MB of heap segment (dynamic data) starting immediately after the code segment, and 70 MB of stack segment at the located at highest virtual memory address.
How much main memory is needed for the page table while working with this process, if the system is using
(a) 2-level page table?
(b) 3-level page table?

I'm unsure if the question is worded badly or im just getting a bit lost.

Note: I'm looking for a bit of insight and explanation here. I realise this place is about learning and that's exactly what im trying to do.

Thank in advance for any help
 
Old 05-27-2013, 08:51 AM   #2
eklavya
Member
 
Registered: Mar 2013
Posts: 622

Rep: Reputation: 136Reputation: 136
Have you read this before?
http://www.cse.unsw.edu.au/~cs9242/0...ures/08-vm.pdf

Take a look at this too.
http://stackoverflow.com/questions/1...vel-page-table
 
Old 05-27-2013, 09:14 AM   #3
jimwarlock
LQ Newbie
 
Registered: Apr 2013
Posts: 11

Original Poster
Rep: Reputation: Disabled
Just flicked through those now.
I'm thinking my question has a typo, and it shouldn't say 42-bit virtual address space and instead say 32.

I see the similarities in the second link question, however its unclear to me what it assumed there, ie the question isn't really explained.

I'm just trying to get a breakdown of my question.
 
Old 05-27-2013, 09:26 AM   #4
jimwarlock
LQ Newbie
 
Registered: Apr 2013
Posts: 11

Original Poster
Rep: Reputation: Disabled
My (limited) understanding reads the questions like this.

Each page table is 4KB in size, with a 32-bit address space required for each page. ie every 4KB page takes up 32-bit of main memory in addressing space.
Am I on the right track here??

I'm also confused with the significance of each block of data being designated virtual addresses. Does that affect the amount of main memory used or is it just extra information?
 
Old 05-27-2013, 09:42 AM   #5
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190
If we are talking about actual 32 bit x86 (rather than some hypothetical architecture) the two common layouts (with and without PAE) are:

With PAE:
The top of the structure is a "Page Directory Pointers Table". That table has 4 eight-byte entries, each of which gives the page directory for one quarter of the address space. In your example, with top and bottom of the 32-bit address space used, the first and last of those four pointers must point to valid page directories.
Each page directory has 512 eight-byte entries for page tables.
Each page table has 512 eight-byte entries for pages.

Without PAE:
The top of the structure is a single page directory
The page directory has 1024 four-byte entries for page tables.
Each page table has 1024 four-byte entries for pages.

Quote:
Originally Posted by jimwarlock View Post
Each page table is 4KB in size, with a 32-bit address space required for each page. ie every 4KB page takes up 32-bit of main memory in addressing space.
Am I on the right track here??
Not quite. First error is that an entry may be 32-bits or 64-bits depending on whether PAE (what you instructor is calling "3-level") is enabled. Second error is that you need to allocate entire page tables and entire page directories. So counting entries is wrong. Figure out how many page tables and how many page directories you need and add up all that memory.

Quote:
How much main memory is needed for the page table
I find that phrase ambiguous. Maybe it means "page tables" so you would ignore the page directories and Page Directory Pointers Table. But more likely it means "page table structure" including the page directories and even the 32 byte Page Directory Pointers Table.

Quote:
I'm also confused with the significance of each block of data being designated virtual addresses. Does that affect the amount of main memory used
Because you work with whole page tables and whole page directories, the alignment matters.

In the 3-level structure, each page directory can map 1GB of virtual space. You want to map far less than 1GB virtual, so ignoring the designated addresses you would think one page directory is enough. But the designated addresses make you need a small part of each of two different page directories. You can't have part of a page directory, so if you need part of one you must have the whole thing.

In the 2-level structure, you need 14.5 page tables for the initial 58MB and you need 17.5 page tables for the final 70MB. If there were no addresses designated you could add 14.5 to 17.5 to get the number of page tables needed. But with the designated address those two half page tables can't be merged.

Last edited by johnsfine; 05-27-2013 at 09:56 AM.
 
Old 05-27-2013, 09:57 AM   #6
jimwarlock
LQ Newbie
 
Registered: Apr 2013
Posts: 11

Original Poster
Rep: Reputation: Disabled
Thanks for the reply.

In referring to the "how much main memory is needed for the page table", that's the question i was given. So i've no idea about that.

Im assuming the PAE explanation will be used to work out part a, and without PAE will help work out part b?

Im confused as to the correlation between the 18, 40 and 70MB of data and the page tables.
Im after the main memory that is being used whilst all of this is being processed, so is that the address space that they will use?

My biggest issue here is what exactly im trying to work out
 
Old 05-27-2013, 10:22 AM   #7
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190
Quote:
Originally Posted by jimwarlock View Post
Im assuming the PAE explanation will be used to work out part a, and without PAE will help work out part b?
Other way around.

Quote:
Im after the main memory that is being used whilst all of this is being processed, so is that the address space that they will use?

My biggest issue here is what exactly im trying to work out
I think you are trying to compute the amount of memory used by the "page table structure" meaning the total size of all page tables plus the total size of all page directories plus the size of the Page Directory Pointers Table if you have one.

Quote:
Im confused as to the correlation between the 18, 40 and 70MB of data and the page tables.
In 2-level every aligned/contiguous 4MB of process code/data needs a page table.

In 3-level every aligned/contiguous 2MB of process code/data needs a page table.

Normally you would need to think about what "starting immediately after" really means about the contiguity of the 18MB and 40MB chunks. Taken literally, it would mean you can treat them as one 58MB chunk. But in real systems, that "immediately" would not be taken quite literally. In this example, it turns out not to matter whether you take that "immediately" literally. You get the same answer whether the 18MB and 40MB are separate or together as a 58MB.

You would get a different answer if all three were together, but you are specifically told the 70MB chunk is at the opposite end of the address space.

Last edited by johnsfine; 05-27-2013 at 10:31 AM.
 
Old 05-27-2013, 10:29 AM   #8
jimwarlock
LQ Newbie
 
Registered: Apr 2013
Posts: 11

Original Poster
Rep: Reputation: Disabled
So that would mean

18 + 40 + 70 = 128MB of total data

In level 2

128/4 = 32 page tables

Each page table is 4KB long
so, 32 * 4 = 128KB total page table space

That doesn't seem right to me... what am i missing?

Really appreciate this btw
 
Old 05-27-2013, 10:34 AM   #9
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190
You ignored "aligned/contiguous" in my post above.

While you were ignoring that and replying, I added a bit more detail.

Quote:
Originally Posted by johnsfine View Post
You would get a different answer if all three were together, but you are specifically told the 70MB chunk is at the opposite end of the address space.

Last edited by johnsfine; 05-27-2013 at 10:39 AM.
 
Old 05-27-2013, 10:36 AM   #10
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190
Quote:
Originally Posted by jimwarlock View Post
That doesn't seem right to me... what am i missing?
You are missing the higher levels and missing the two half page tables wasted in the 2-level layout for this example.
 
Old 05-27-2013, 10:38 AM   #11
jimwarlock
LQ Newbie
 
Registered: Apr 2013
Posts: 11

Original Poster
Rep: Reputation: Disabled
so then
you've two blocks, 58 and 70MB

58/4 = 14.5 page tables, round up to 15
70/4 = 17.5 page tables, round up to 18

Each page table is 4KB long
so, 15 * 4 = 60KB
and, 18 * 4 = 72KB

132KB of page table address space
 
Old 05-27-2013, 10:44 AM   #12
johnsfine
LQ Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep: Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190Reputation: 1190
I'm not certain of the instructor's intent, but my best guess is:
Code:
2-level:
  15 page tables for the first 58MB
+ 18 page tables for the last 70MB
+  1 page directory
= 34 * 4096 = 139264 bytes

3-level
  29 page tables for the first 58MB
+ 35 page tables for the last 70MB
+  2 page directories
+ 32 bytes for the Page Directory Pointers Table
= 66*4096+32 = 270368 bytes.
 
Old 05-27-2013, 10:54 AM   #13
jimwarlock
LQ Newbie
 
Registered: Apr 2013
Posts: 11

Original Poster
Rep: Reputation: Disabled
this hugely helpful john.

I think i get it now haha. That makes sense to me anyway.

I'm going to run this past my instructor. But this is great.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
[SOLVED] a question about the page table and the physical address corone Linux - Kernel 4 07-29-2011 01:00 AM
Storing Page Table , Process Table prabagaranvt Linux - Kernel 1 06-22-2011 08:35 PM
access paging table memory using another page table via MMU? valpa Linux - Kernel 8 08-26-2008 04:26 PM
Question about Linux level 1/Level 2 jobs inara72 Linux - Newbie 2 04-09-2008 09:14 PM
three- level page table in linux 2.6 mehrotraamit-2 Linux - Newbie 1 11-15-2005 11:19 AM

LinuxQuestions.org > Forums > Linux Forums > Linux - Newbie

All times are GMT -5. The time now is 12:02 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration