DYNAMIC MEMORY MANAGEMENT

In dynamical allocation method the storage for information is allocated from the free memory when it has served its purpose is freed. In dynamic memory management storage for information is allocated from the free memory area as it is needed and retured to free memory when it has served its purpose. The free memory region lies between the permanent storage area of programe and the stack. This region is called heap is used to satisfy a dynamic allocation request. The heap is contained in the data segment

One advantage of using dynamic allocation is that the same memory can be used for several different purposes in the coures of a programe execution.

Another advantage is that its allows the creation of linked list Because memory can be allocated for one purpose and freed when that use has ended, it is possible for another part of the program to use memory for some thing else at a different time . another advantage of dynamically allocated is that it allows the creation of linked lists. We assumed that storage is allocated one node at a time, There are two charecteristic of node that make the previos methods suitable. The first is that nodeof agiven type is of fixed type and second is that the size of each node is fairly small. In some app. However these charecteristic do not apply. For ex. A perticular program might require a large amount of contiguos storage (ex. A large array) it would be impracticle to attempt to obtain such a block one node at a time . similarly , a program may requirestorage block in a large variety of sizes . in such cases a memory management system must be able to process request for variable length blocks . in this section we discuss some system of this type.

There are various strategies being developed for managing the memory dynamically, each one has its own advantage and disadvantage. Stretegies being prevailing are

Compaction:

In this scheme initially memory is one large block of available storage arrive,blocks of memory are allocated sequentially from the first location in memory. A variable free point contains the address of the first location following the last block allocated. In fig . free point equals 950. Note that all memory location between free point and the highest memory address in mem. Are free. When a block is freed, freepoint remain unchanged and no combination of free spaces take place. When a block of size n is allocated, freepoint is increased by n this cont. Until a block of size n is requested and freepoint + n-1 is larger than the highest address in mem. The request cannot be satisfied without further action being taken.

At that point user routiene come to halt and a system compaction routiene is called. Although the algorithm of the previous section was designed to add.uniform modes. It it could be modified to compact memory consisting of blocks of storage as well. Such aroutiene copies all allocated blocks into sequential memorylocation starting at the lowest memory add.thus all the memory block that were inter spersed with allocated blocks are eliminated, and yhe free point is reset to the sum of the sizes of all the allocated blocks . one large block is created at the upper end of the memory and the user request may be filled if there is sufficient space.

When allocated blocks are copied into lower portions of memory, special care must be taken so that pointer values remain correct . ex.the containt of memory location 420 in allocated block contain the add. 340.

First fit:

If it is not desirable to move blocks of allocated storage from area of memory to another, it must be possible to rellocate memory blocks that have been freed dynamically as user processing continues. Each time that a request is made for storage, a free area enough to accomodate thge requested size must be located. The most obvios method for keeping track of the free block s is to use a linear linked list. Each free block contains a field containing the size of the blocks and a field containing a pointer to the next free block. These feilds are in some uniform location( say, the first two wordws ) in the block .if p is the address of the free block , the expression size(p) and the next(p) are used to refer to these two quatities. A global pointer freelock points to the first free block on this list. Let us see how blocks are removed from the free list when storage is requested. We then examine how blocks are added onto this list when they are freed . There are several methods of selecting the free block to use when requesting storage . in the first fit method , the free list is traversed sequentially to find the free block whose size is larger than or equalto the requested amount. Once the block is found , it is removed from the list (if it equal to the size of amount requested ) or is split into two portions ( if it is greater than the amount requested) The first of these portions remain on the list and the second one is alloted . the reason behind allocating second block is that the free list next pointer is at the begining of each free block by leaving that portion on the list the this pointer is need not be copied onto some other location and the next field of the previos block is need not be changed.

Best fit :

The best fit method obtain the smallest free block whose size is greater than or equal to n. An algorithm to obtain uch ablock by traversing the entire free list follows. We assume that memsize is the total no. Of words in memory.

How ever it is also possible for the first fit method to succeed where the best fit method fails . as an ex. Consider the case in which the system begins with the free block of size 110 and 54 and then makes succesive request for 25,70,and 50 words . the fig shows that first fit succeed while best fit fails method does not . the reason is that the remaining unallocated portion of the free blocks are smaller under best fit..

worst fit:

Yet another method of allocating blocks of storage is the worst fit method . in this method a system allocates a portion of the largest free block in the memory. The philosphy behind this method is that by using a small no. Of bery large blocks reapetedly to satisfy the majority of requests many moderately sized blocks will be left unfragmented. Thus , this method is likely to satisfy a largerno. Of requests than the other methods, unless most of the requests are for very large portion of memory. The reason for choosing one method over the other is efficiency. In each of the method search can be made more easier. On the other hand if the available list is maintained in the order of increasing size, a best fit search for a block becomes more efficient . and finally, if the list is main tained in the ordre of decreasing size a worst fit requiers no searchingas the largest size block is first on the list.

improvement in first fit

There are several improvement that can be made in the first fit method. If the size of a free block is only slightly larger than the size of a free block is only slightly larger than the size of a block to be allocated, the portion of the free block that remain free is very small.

External fragmentation

: the phenomenon in which there are many small non contiguos free blocks is called external fragmentation. Because free space is wasted out side allocated blocks.

internal fragmentation

I is one in which free space is wasted within allocated block.the forgoing solution transform external fragmentation into internal fragmentation. The choice of what min. Size to use depend on the pattern of allocation request in the perticular system. It is reasonable to use a min. Size such that only a small percentage ( say 5%) if the allocation request are less than or equal to the size.

Freeing storage block

Thus far nothing has been said about how allocated blocks of storage are freed and how they are combined with contiguos free blocks to form larger blocks of free strorage. The term liberation is used for the process of freeing an allocated block of storage ; an algorithm to implement this process is called liberation algorithm. The free list should be organised to facilitate efficient allocation and liberation. Boundary tag method It is desirable to eliminate all searching during liberation to make the process more efficient. One method of doing this comes at the expense of keeping extra information in all blocks( both free and allocated).

A search is necessary during liberation to determine if the newly freed block may be combined with some existing free block. There is no way of detecting whether such a block exists or which block it is without search . however, if sucha block exists , it must immediately precede or succeed the block being freed. The first address of the block that follows a block of size n at alloc + n. Suppose yhat every block contains a field flag that is true if the block is allocated and false if the block is free. Then by examining flag ( alloc + n), it can be determined whether or not the block immediately following at alloc is free.