Hi, I have a question regarding one of the dynamic allocation algorithms known a

Question

Hi,

I have a question regarding one of the dynamic allocation algorithms known as Segregated Free Lists;

The question is that:

How the range of the sizes of the seggregated list is chosen? I have found this information: "A common size class scheme is to use sizes that are a power of two apart eg 4 words, 8 words , or 16 words" But I still don't understand :

1-Who decides the range? based on what?

2-what is the difference of choosing 4, 8 or 16 on the performance of the algorithm

I wonder if anyone have an idea, please let me know ASAP

Thanks in advance

Explanation / Answer

How the range of the sizes of the seggregated list is chosen?

As we know the sizes are of two types :

small sizes and large sizes.

small sizes usually opt for separate classes and large size opt for single class that of (two power size).

let us suppose you wish to allocate 4 bytes then the size class will be of 4bytes block. this depends on the requirement of the programmer. how much ever he/ she wishes to grant memory to the program they can grant dynamically.

like p1=malloc(4)

p2=malloc(3)

once you are done you can release the memory using a free method

the above discussed is all about the small size whic has separate class.

now suppose you want to grant memory to a sub module of the program the 2 byte 4 byte will not be sufficient then the memory allocation would be in large size which accepts the whole memory in one class block=2size

Who decides the range? based on what?

The programmer decides the range based on the requirement of memory for running the program.

what is the difference of choosing 4, 8 or 16 on the performance of the algorithm

The performance of the algorithm depends on the efficient reallocation of the freed memory. suppose we made use of the small sizes as discussed above, we freed the memory granted to process p1. after which process p3 requested for memory of 2 bytes.then

here we can observe that the internal memory 2 bytes is available. if there will be another process which requests for 2 bytes while p3 is under processing the that space can be utilized else that 2 byte vacant space goes waste.

let us consider one more scenario

suppose there is one process p4 which requires 5bytes of memory. if we look at the above memory grant chart, we find that the memory is availabe but not in contigious location such that it could be granted to process p4. this means that though the memory is available it cannot be granted instead it is wasted. this is know as internal fragmentation.

similarly for large size blocks the memory ahs to be managed with respect to external fragmentation.

we can conclude that the performance degrades when there will be an internal fragmentation than external fragmentation.

for further queries kindly get back

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.