OSDev.org

The Place to Start for Operating System Developers
It is currently Wed Apr 26, 2017 4:04 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 11 posts ] 
Author Message
 Post subject: Managing Used/Free pages
PostPosted: Mon Aug 09, 2004 10:26 pm 
What options besides a bitmap or a stack based approach are common in Operating Systems to store which physcial pages are free or not?


Top
  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Tue Aug 10, 2004 12:06 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 7824
Location: At his keyboard!
Hi,

chris wrote:
What options besides a bitmap or a stack based approach are common in Operating Systems to store which physcial pages are free or not?


There are some implementations that keep track of a linked list of allocated and/or free physical memory ranges.

Free page stacks are the fastest way, but they aren't any good if you need to allocate a block of pages (for ISA DMA for e.g.), or if you use multiple page sizes (2 Mb or 4 Mb, and 4 Kb) because sooner or later you'd need to combine several 4 Kb pages into a larger size. Also you can't keep track of non-RAM areas (BIOS, device memory, etc) with free page stacks. Free page stacks are good because they are fast and require very little overhead to manage (as little as a single pointer to the top page in the stack).

Bitmaps are simple and can be fast (if you keep track of the addresses for the lowest and/or highest free pages). They can also handle multiple page sizes and blocks of pages without much problem. Bitmaps do use more overhead though - 1 byte or 1 bit per 4 Kb page. If you use 1 byte per 4 Kb page then the bitmap (bytemap?) can also handle non-RAM areas.

The linked list approach isn't as fast and can use more overhead (it depends on how fragmented physical memory becomes). It can handle multiple page sizes, blocks of pages and non-RAM areas.

I use a bitmap (1 byte per page) for memory below 16 Mb and free page stacks (up to 512 of them) for free RAM pages above 16 Mb. I've also got a "list of memory areas" which is almost the same as the data you get from "int 0x15 AX=0xE820", and a similar list for NUMA memory ranges. I use 4 Kb pages only.


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Tue Aug 10, 2004 1:50 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
alternatively to 'flat' bitmap, you may have a "summary bitmap". Each entry of the 'summary bitmap' tells you if a slice of page in the "flat bitmap" is completely free, completely used or mixes free & used pages...

Another possible technique is to use the "watermark" allocation: you assume memory has two contiguous region: lowest one is "used" and the upper one is "free". When you need memory, you copy the value of the "free" pointer and increment it by the amount of memory you need. As long as allocated memory needn't to be released, it works pretty fine ;)

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Tue Aug 10, 2004 1:45 pm 
Thanks for you replies.

Brendan wrote:
There are some implementations that keep track of a linked list of allocated and/or free physical memory ranges.


How can a linked list be setup so early at boot (ie. no malloc())?


Top
  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Tue Aug 10, 2004 1:55 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
Note that it's a linked list of *physical pages*. Each free page has naturally 4KB of free space in it, so you simply write at the start of a page the frame number of the next free page in the list and voil?.

When 'allocating' a page, all you have to do is:
1. get the frame number of the 'head' free page from a global var.
2. map this page somewhere in memory
3. read the 'next free frame' number and write it in the global var
4. return the frame number :)

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Tue Aug 10, 2004 2:22 pm 
Whenever you find some sort of array (bitmap) or list (stack, at least you can implement it on top of list classes most times ;) ), see if a tree performs better (similiar to that "summary bitmap")


Top
  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Wed Aug 11, 2004 9:21 am 
Okay, what I use is the AVAIL bits, I can't figure out why I would use them (three bits ;D )
The last bit of the AVAIL bits is used to determine whether it has been used, or not.


Top
  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Wed Aug 11, 2004 2:06 pm 
Pype.Clicker wrote:
Note that it's a linked list of *physical pages*. Each free page has naturally 4KB of free space in it, so you simply write at the start of a page the frame number of the next free page in the list and voil?.

When 'allocating' a page, all you have to do is:
1. get the frame number of the 'head' free page from a global var.
2. map this page somewhere in memory
3. read the 'next free frame' number and write it in the global var
4. return the frame number :)



Ahh, thanks.


Top
  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Thu Aug 12, 2004 3:07 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
DennisCGc wrote:
Okay, what I use is the AVAIL bits, I can't figure out why I would use them (three bits ;D )
The last bit of the AVAIL bits is used to determine whether it has been used, or not.



hmm ?? are you sure we're talking about the same thing, Dennis ? AVL bits in page tables to store frames usage ? so how do you know what frame you could allocate for a page (say virtual address 0x12345000) ? And how will it keep working when you'll have several address spaces ?

** edit ** linked this thread at the FAQ

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Thu Aug 12, 2004 3:27 pm 
I thought we were talking about memory management ;)
Now, I have a simple way, so no virtual memory management.
The original question was:
Quote:
What options besides a bitmap or a stack based approach are common in Operating Systems to store which physcial pages are free or not?

I'm replying on that question...
Quote:
And how will it keep working when you'll have several address spaces ?

I don't know sure what you're talking about, but let me give a try.
The "main" (which the kernel use) page tables covers the whole memory. So, this could be use, IMHO, as a normal way of managing your memory.
I'm not talking about virtual mem. management, I have to think about this!

Then there's process management (which I think IMO you're talking about).
How about creating a new pagedirs with pagetables an placing it at a 4k boundary ?
And those pagetables are referring to the app.

I hope I made myself clear. If I didn't ask me ;)

DennisCGc.


Top
  
 
 Post subject: Re:Managing Used/Free pages
PostPosted: Fri Aug 13, 2004 3:33 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
okay, so you're assuming the existence of a 'kernel process' that will be mapping (preferrably x->x+k) the whole physical memory, right ? (or simply that they'll be enough space in the 'kernel half' of each process to map all physical memory ?)

indeed in that case you could use one of the 'AVL' bits to store the usability information...

However, i think that it will make thing worse than a bitmap, since in a bitmap you can check 32 pages in a row with a single operation (there's at least one page free if dword!=0)

_________________
Image May the source be with you.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 11 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Bing [Bot], StudlyCaps and 12 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group