OSDev.org

turdus wrote:cyr1x,OSwhatever: I apologize, our teacher at the university said too much times (names differ on purpose). I thought it's a well known thing, although I wasn't 100% sure, that's why I wrote "physical memory" instead of "frame" on title. Now that I read your comments, I reread the AMD64 and the Intel64 manuals again, and they do not refer physical page as frame. It was my university only thing I guess, sorry. I wonder what it's called in Nelson's book.

EDIT: checked other documents as well, and that's interesting: all that's in my native language refers physical pages as frames consistently (I mean with the english word "frame"). English documents don't, they mix them.

turdus wrote:

FlashBurn wrote:Another problem is, how will you allocate 4mb or 2mb pages?

Write your own page allocator to solve, this has nothing to do with it, as it is a frame allocator (article on physical memory, remember?). It does not solve the problem of woc either. The page allocator rely on a frame allocator, not backwards.

turdus wrote:

Furthermore you make the argument that a maximum of 512 fragments on physical memory is enough.

Stated empirically. It's rare that I see more than 3 fragments. I'm testing it for a while.

turdus wrote:I do not understand your point. "It isn't used for anything else"? Speak for yourself, I would rather use it for storage cache. And 1 page *is* smaller than 2^32*4 bytes.

OSwhatever wrote: Don't apologize to me, I'm just as confused as you are when it comes to the "page" and "frame" ambiguity. Was the "page frame" word a way to solve it?

FlashBurn wrote: I don´t get the difference between frame and page, because they both mean the same to me. Your physical memory manager needs to manage also 2/4mb pages/frames if you want to use them!

Combuster wrote:Which is why there is such a thing as worst case analysis. Your algorithm does not survive the worst case
...algorithm crashes under fragmentation, profit.

XenOS wrote:I guess the point why the stack-based allocator consumes almost no memory is the following: The stack contains only the free pages. So if many pages are free (say, nearly 4 GB), you need a large stack to hold all of them (in this case 4 MB). However, spending lots of memory is not an issue when almost all of your physical memory is free.

Once you allocate memory, you pop more and more entries off the top of the stack. Thus, the memory which holds the top of the stack is not needed anymore and can be deallocated. The only information the stack needs to keep is the location of free pages, and when the number of free pages drops below 1024, the whole stack fits into a single 4 kB page and consumes almost no physical memory.

When you free pages again and the stack needs to grow, simply map freed pages to the top of the stack when necessary.

FlashBurn wrote:If you think your right, prove that you can use 2/4mb pages with a pmm which can only handle 4kb pages.

turdus wrote:

davidv1992 wrote:The fact that it is in the kernel will guarantee that almost everything that isn't used on every interrupt will probably not reside in the cache on first access anyway, so the cache argument is moot

Allocating large amount of frames would. As you pop new values from stack, you're increasing the stack pointer constantly, it's most likely that you will cross a page border sooner or later.

The amount of memory you save because the amount of data on the stack is smaller is moot because that memory isn't used for anything else anyway.

I do not understand your point. "It isn't used for anything else"? Speak for yourself, I would rather use it for storage cache. And 1 page *is* smaller than 2^32*4 bytes.

Furthermore you make the argument that a maximum of 512 fragments on physical memory is enough.

Stated empirically. It's rare that I see more than 3 fragments. I'm testing it for a while.

...in which case your system fails horribly.

Where did you get that from?!? First: you can use more space for fifo, second: if this occurs, it calls defragmenter and/or swapper. If you can't write a swapper of your own, your implementation will fail horribly, I agree on that.

This all combined with the fact that it is a far more complex system than the other two I would strongly recommend against using it.

Don't like it, don't understand it, so don't use it.

turdus wrote:

XenOS wrote:I guess the point why the stack-based allocator consumes almost no memory is the following: The stack contains only the free pages. So if many pages are free (say, nearly 4 GB), you need a large stack to hold all of them (in this case 4 MB). However, spending lots of memory is not an issue when almost all of your physical memory is free.

Once you allocate memory, you pop more and more entries off the top of the stack. Thus, the memory which holds the top of the stack is not needed anymore and can be deallocated. The only information the stack needs to keep is the location of free pages, and when the number of free pages drops below 1024, the whole stack fits into a single 4 kB page and consumes almost no physical memory.

When you free pages again and the stack needs to grow, simply map freed pages to the top of the stack when necessary.

Correct, but you compare the best case (free pages drops below 1024) with the worst case (fragments exceed 512). And you can handle fifo's buffer dynamically as well. The point is that you have to allocate/deallocate memory for stack (4k-4M), while fifo can work on 1 or 2 preallocated pages as well. Let's see a worst case where same amount of memory required:
stack: all memory free, 4M
fifo: contains more than half million fragements, 4M
And the difference is even bigger if it comes to 64 bit. The stack would consume 256G for full RAM (2^48, 256Tb), while fifo can handle all of it in 4M easily. Scalability matters! Do not forget that the free frame stack (as well as fifo) has to be filled in at boot time when almost every frame is free!

turdus wrote:stack: all memory free, 4M

turdus wrote:

FlashBurn wrote:If you think your right, prove that you can use 2/4mb pages with a pmm which can only handle 4kb pages.

Sorry, but are you dumb? Prove that you push 2/4mb pages to your 4k stack?!?

I really do not understand why is it so difficult. The algorithm *DOES NOT* specify block size, it can be anything (as long as hw supports it)! If you want to have different units, you have to write your page allocator (at a higher level on top of this) to support more fifos, just like you'd do with stacks (one for 4k, one for 2/4mb, capisci?).

cyr1x wrote:

turdus wrote:stack: all memory free, 4M

I doubt it. A stack will require no more than a pointer of 4-bytes or 8-bytes in size and on allocation/deallocation a single "virtual" page to map the top of the stack. A stack actually *IS* the most effective way to store free frames.

Code:
       |    asymp.    | resource
       +-------+------+ requirement
       | alloc | free | (memory footprint)
-------+-------+--------------------
ideal  |  Θ(1) | Θ(1) | RR(1)
bitmap |  Θ(n) | Θ(n) | RR(n)
stack  |  Θ(1) | Θ(1) | RR(n)          (RR(bitmap)<RR(stack))

Code:
stack  |  Θ(1) | Θ(1) | 1 pointer    (RR(bitmap) >> RR(stack))