Average-case memory usage - algorithm analysis

Question

As the title states im having some difficulties analzying the average-case memory usage of a memory allocator (quick-fit). My goal is to determine the average-case internal fragmentation of an allocated block (using quick-fit memory allocator).

So far i haven't really gotten anywhere, since i dont really know how to analyze the average-case. My first thoughts was, assume you have T(n), that is the memory being wasted when allocating a memory-block of size n(internal fragmentation). Further, assume that the probabilty for allocating a memory-block of size n is P(n), then the average case memory-waste should basically be the sum of T(n1)P(n1)+(Tn2)P(n2)+....+T(nk)P(nk)

The problem is that i don't know T(n) and P(n)..or is it even possible without making any assumptions?

For the worst-case i simply think it is O(n-1)=O(n). Since in the worst case we only have one "quick-list" the one handled by, let say, first-fit. Then the worst possbile scenario is that we only have one big block of size n bytes available for allocation, and the requested memory is only 1byte then n-1 bytes is wasted at most?

I might not make any sense, but any help in making this a bit clearer is appreciated. Thanks

Can you start with an example? Let us assume you have memory of 10 bytes (livin large!). If you allocate 5 bytes, then the remaining 5 bytes are wasted? Or, would that depend on probability of finding a allocation requirement that is less that equal to 5 bytes? — ElKamina
– ElKamina, Commented Jan 19, 2012 at 23:12
Yes, precisely as you said, if we have a 10 byte block, and we only requsted 5 byte, then those remaining 5 bytes are wasted. — me_L_coding
– me_L_coding, Commented Jan 19, 2012 at 23:18

ElKamina · Accepted Answer · 2012-01-19 23:59:57Z

2

Let T(n) be the space wasted when a n size allocation is made. It should be very straightforward to calculate T(n), right? For a block size of b, T(n) = b - (n%b) ?

The second part is more nuanced. It would depend on the distribution of allocation request size. You can probably assume wastage to be uniform, in which case your average waste would be b/2.

Derivation of b/2: Probability of having wastage i is 1/b for any i (uniform assumption). The expected wastage = sum_i Probability_i Wastage_i = 0/b + 1/b+....+ (b-1)/b = (b-1)/2 which is approximately equal to b/2.

edited Jan 19, 2012 at 23:59

answered Jan 19, 2012 at 23:28

ElKamina

7,82730 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

me_L_coding Over a year ago

im not really following you on the secondpart. I agree that an assumption of uniform wastage can be made. But how do you get to b/2? I mean assuming that we have #k quick-lists, and each of these is choosen with the same probability? doesn't that give us (b-(n%b))/k..?

me_L_coding Over a year ago

Thanks alot ElKamina i think i got it now.. :):)

Collectives™ on Stack Overflow

Average-case memory usage - algorithm analysis

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related