sorry,
stack_size=(memory_installed+4095)/4096; is the number of 4kb entries
so the memory needed for the stack if
stack_memory=stack_size * 4;
Page allocation algorithm
-
Dangamoose
RE:Page allocation algorithm
Yes mine is the same system. Except i also support 64bit address pointers in my heaps if more than 4.2Gb is available.
Dangamoose.
Dangamoose.
-
carbonBased
RE:Page allocation algorithm
Yes, the time taken in _either_ approach (if not correctly) is negligable. However, it still is true that a stack is faster... and in my opinion, easier.
About the only thing going for bitmaps are their space conservation.
I did, at one point, propose a hybrid. Instead of using a bit per page, one byte per page would be used. The overall "bitmap" would be 8 times larger, of course, but it would be easier to search through. Some might say that you're wasting 7 bits, but there are certainly uses that could be found for these bits (such as marking them as shared, OS pages (do not swap), etc, etc). I like this system because you have that ability to supply extra information per page, if you want to.
If should also be noted that stack implementations also have spaces for extra information (considering the first 12 bits are unused, as each entry is page aligned). If you decided, some time in the future, that you needed to record extra information using a bitmap method, you'd have to create an entirely new bitmap.
Also... rex mentions that non-static-sized stacks require extra overhead, which I don't really see as being a problem at all. For one, this is a one time occurance... you find the necessary space, allocate it, and you're done. I mean, we are talking about memory management here... allocating memory shouldn't be a problem
And yes, I suppose it certainly is possible that deallocations in a bitmap _could_ be faster then a stack implementation... but it'd have to be quite a good bitmap implementation, and quite a bad stack implementation
In any event, as I originally said, you're totally right... the point about speed is fairly mute. Both methods can be made quickly. Stack's will generally be faster, but bitmaps will generally be smaller.
I think the biggest questions here are:
How much memory are you willing to use? Even with 4GB of memory, less then 0.1% is used by a stack...
What processors do you intend to support? If you're planning on support 386's with 4MB of RAM, perhaps bitmaps are a better choice... with current systems, I'd say stack
How familiar are you with bit operations? And I don't mean simple shifts, etc... there are _MANY_ clever tricks that can be done to save time per allocation/deallocation using a bitmap. The simple "shifts and ands" approach is certainly the slowest way to go.
and... I'm sure there are more... I just can't think of any
Quite honestly, if someone implements a nice, quick, bitmap allocation system, I'd be interested to see it. My OS actually loads (or at least can) the allocation methods at run-time, and (given the permission, of course) I'd be interested to allow both forms of allocation in my OS.
Cheers,
Jeff
About the only thing going for bitmaps are their space conservation.
I did, at one point, propose a hybrid. Instead of using a bit per page, one byte per page would be used. The overall "bitmap" would be 8 times larger, of course, but it would be easier to search through. Some might say that you're wasting 7 bits, but there are certainly uses that could be found for these bits (such as marking them as shared, OS pages (do not swap), etc, etc). I like this system because you have that ability to supply extra information per page, if you want to.
If should also be noted that stack implementations also have spaces for extra information (considering the first 12 bits are unused, as each entry is page aligned). If you decided, some time in the future, that you needed to record extra information using a bitmap method, you'd have to create an entirely new bitmap.
Also... rex mentions that non-static-sized stacks require extra overhead, which I don't really see as being a problem at all. For one, this is a one time occurance... you find the necessary space, allocate it, and you're done. I mean, we are talking about memory management here... allocating memory shouldn't be a problem
And yes, I suppose it certainly is possible that deallocations in a bitmap _could_ be faster then a stack implementation... but it'd have to be quite a good bitmap implementation, and quite a bad stack implementation
In any event, as I originally said, you're totally right... the point about speed is fairly mute. Both methods can be made quickly. Stack's will generally be faster, but bitmaps will generally be smaller.
I think the biggest questions here are:
How much memory are you willing to use? Even with 4GB of memory, less then 0.1% is used by a stack...
What processors do you intend to support? If you're planning on support 386's with 4MB of RAM, perhaps bitmaps are a better choice... with current systems, I'd say stack
How familiar are you with bit operations? And I don't mean simple shifts, etc... there are _MANY_ clever tricks that can be done to save time per allocation/deallocation using a bitmap. The simple "shifts and ands" approach is certainly the slowest way to go.
and... I'm sure there are more... I just can't think of any
Quite honestly, if someone implements a nice, quick, bitmap allocation system, I'd be interested to see it. My OS actually loads (or at least can) the allocation methods at run-time, and (given the permission, of course) I'd be interested to allow both forms of allocation in my OS.
Cheers,
Jeff
-
Dangamoose
RE:Page allocation algorithm
And heres to code...
Basically its to deallocation methods for the case of both bitmaps and stacks.
I've tried to make both routines as small as possible.
And before anyone says anything, yes it is incomplete, you would have more checks in-between the different areas of code but those checks would be peformed for both the deallocators and this is just pointles example code i wrote in 2minutes.
Its obvious to see that the stack deallocator is much smaller than the bitmap, but when saved in a stack, consumes larger amounts of space.
Please tell me if its wrong. I'd love some comments.
; bitmap deallocator...
; assumptions
; eax - contains aligned 4kb pointer
mov ebx, 0x1000 ; 4kb - page size
div ebx ; eax - page number from zero memory
mov ebx, 0x08 ; 8 bits per byte
div ebx ; eax - bit offset to that 4kb bitmap entry
mov ebx, 0x08 ; 8 bits per byte
div ebx ; eax - byte offset into the bitmap, edx - bit offset into bitmap
mov ebx, 0x80 ; 10000000 - 1byte with high bit set
sub edx, 1 ; remove 1bit from the offset
shr ebx, edx ; **** edx number of bits right
; ebx now contains the page bit as 1, all other bits as 0, ready for or'ing
mov ecx, dword [bitmap_base_pntr] ; bitmap base pointer
add ecx, eax ; add byte offset
mov eax, byte [ecx] ; get byte from bitmap
or eax, ebx ; deallocated bit now set as allocated.
; ...and so on...
;--------------------------------
; stack deallocator...
; assumptions
; eax - contains aligned 4kb pointer
mov ebx, dword [heap_base_pntr] ; Get heap base pointer
add ebx, dword [heap_offset] ; add to heap offset
mov dword [ebx], eax ; Move pointer onto stack
add dword [heap_offset], 4 ; add 4(bytes) to offset
; and so on...
Basically its to deallocation methods for the case of both bitmaps and stacks.
I've tried to make both routines as small as possible.
And before anyone says anything, yes it is incomplete, you would have more checks in-between the different areas of code but those checks would be peformed for both the deallocators and this is just pointles example code i wrote in 2minutes.
Its obvious to see that the stack deallocator is much smaller than the bitmap, but when saved in a stack, consumes larger amounts of space.
Please tell me if its wrong. I'd love some comments.
; bitmap deallocator...
; assumptions
; eax - contains aligned 4kb pointer
mov ebx, 0x1000 ; 4kb - page size
div ebx ; eax - page number from zero memory
mov ebx, 0x08 ; 8 bits per byte
div ebx ; eax - bit offset to that 4kb bitmap entry
mov ebx, 0x08 ; 8 bits per byte
div ebx ; eax - byte offset into the bitmap, edx - bit offset into bitmap
mov ebx, 0x80 ; 10000000 - 1byte with high bit set
sub edx, 1 ; remove 1bit from the offset
shr ebx, edx ; **** edx number of bits right
; ebx now contains the page bit as 1, all other bits as 0, ready for or'ing
mov ecx, dword [bitmap_base_pntr] ; bitmap base pointer
add ecx, eax ; add byte offset
mov eax, byte [ecx] ; get byte from bitmap
or eax, ebx ; deallocated bit now set as allocated.
; ...and so on...
;--------------------------------
; stack deallocator...
; assumptions
; eax - contains aligned 4kb pointer
mov ebx, dword [heap_base_pntr] ; Get heap base pointer
add ebx, dword [heap_offset] ; add to heap offset
mov dword [ebx], eax ; Move pointer onto stack
add dword [heap_offset], 4 ; add 4(bytes) to offset
; and so on...