Thursday, December 15, 2011

Dynamic memory allocation in USER Space

Describe dynamic memory allocation functions in USER SPACE.Also discuss issues related to dynamic memory allocation.

1.malloc()
2.calloc()
3.realloc()
4.free()

Also Discuss USER space memory is allocated with respect to OS
1.Allocation of frames using Basic strategy
2.Min number of frames
3.Allocation Algos.

Memory Allocation Concept:--
Memory management on the operating system level is usually a two-tier affair : first an operating system memory manager allocates rather large "chunks" of memory to individual process memory managers and also keeps track of them. Then each process memory manager allocates smaller "chunks" of the memory to its process and keeps track of allocated and free segments: when its process requests deallocation of a segment, it puts that segment on the list of free segments; if running out of memory, it requests another big chunk from the operating system memory manager.

memory allocation is nothing more or less than making an entry in the "accounting book" that this segment is given to this process for keeps, and memory deallocation is an entry that this segment is not needed by this process and hence is "free".

System Heap
The operating system process manager usually keeps track of allocated blocks in a data structure called the BINARY HEAP (a binary tree in which each node is labeled by a label that is smaller than labels of all its descendants), whose purpose is to facilitate fast and efficient searching for a suitable free block. This heap is sometimes referred to as the system heap or free store.
In modern operating systems, the operating system manager is not a part of the process code but instead is engaged by a system call from the process. The appropriate system call is thus particular to each operating system and each hardware platform.

Process Memory
The process memory manager usually keeps a DYNAMIC LIST of free segments. One implication is that, every time your program requests more memory, the process memory manager must search through the list to find a suitable segment; if none is found, more memory must be requested from the operating system memory manager, which must search the system heap for a suitable block. After delivery to the process memory manager, a suitable segment must be carved out from the freshly allocated block. It is therefore impossible to estimate how long it will take to execute a memory allocation request. Even though modern computers and operating systems are very fast, if our program performs a significant number of allocations and deallocations then the attendant yet unpredictable delays may affect the program's performance. These issues must be considered for REAL TIME OS and for all programs where performance is essential.

Process Memory Allocation Functions:-

Malloc()--

#include <stdlib.h>
void *malloc(size_t size); //size_t is unsigned long

The argument size is the size of memory requested in bytes; malloc() either returns NULL if unsuccessful or returns the address (void* is just a plain address) of the beginning of the allocated segment. The segment allocated is properly aligned. Note that malloc() can fail for any of three reasons: if there is not enough memory left for allocation (the free store is depleted); if the size requested exceeds the limit allowed for allocation; or if the process memory manager has somehow been corrupted
malloc() may in fact allocate a bigger segment than requested. You are guaranteed to receive at least as many bytes you have requested, but you may also get more. The reasons concern both the way malloc() works and the way memory and access to it are organized

Precautions:
1.The contents of a segment allocated by malloc() should not be used until it is set by the program to hold some meaningful value or values.
2.Problem regarding allocating an insufficient number of bytes, which results in overflow when storing value(s) requiring more bytes

Calloc()---

#include <stdlib.h>
void *calloc(size_t nelem, size_t elsize);

It blanks (clears) the allocated segment and that the number of bytes allocated is nelem*elsize

Realloc()---

#include <stdlib.h>
void *realloc(void *ptr, size_t size);

It is designed to expand or reduce an already allocated segment. The role of the argument ptr is exactly that - it is a pointer to the segment that we want to expand or reduce, while size stipulates the size in bytes of the expanded or reduced segment.A null value of ptr is interpreted as there being no segment yet to expand or reduce, and then realloc() behaves like malloc().If size is 0, then realloc() works like free() and the segment is deallocated.

Issues with Realloc-----

First,
unless ptr points to a segment previously allocated via malloc(), calloc(), or realloc(), unpredictable problems may occur - including corruption of the process memory manager.

Second,
though it is not a problem to reduce a segment, it may be a problem to expand it. If there is not enough memory available to the right of the segment's end, then realloc() creates a new segment of the extended size somewhere else in the memory, copies the contents of the old segment up to the old size to the new segment, frees the old segment and returns the pointer to the new segment. In essence, while the old segment is being extended, it may or may not move in the memory. For many purposes it does not matter that the extended segment has moved, but any meaningful links to the old segment in the program become dangling pointers.

Free()-----

#include <stdlib.h>
 void free(void *ptr);

The function free() inserts the segment pointed to by ptr back into the list of free segments kept by the process memory manager

NOTE:
  • The dynamic memory allocation should be done prior to the execution of the critical section of the program, so a crash would not cause severe problems;
  • The program should obtain as much dynamic memory as possible at the beginning and then use its own memory manager to manage it
  • The program should have the ability to build the most important dynamic data structures it needs and work with them on disk in a special "error mode" - although this degrades performance, it nevertheless allows execution of the critical section to continue (even though in most cases the virtual memory system of the operating system does exactly that).

    HOW free() is implememnted -------------------------
    When malloc() (or one of the other allocation functions) allocates a block of memory, it grabs a little more than it was asked to grab. malloc() doesn’t return the address of the beginning of this block. Instead, it returns a pointer a little bit after that.At the very beginning of the block, before the address returned, malloc() stores some information, such as how big the block is. (If this information gets overwritten, you’ll have wild pointer problems when you free the memory.)

5 comments:

  1. Although free function does not accept size as a parameter. How does free() function know how much memory to free given just a pointer?

    http://www.geeksforgeeks.org/archives/13219

    ReplyDelete
  2. http://www.cs.cmu.edu/afs/cs/academic/class/15213-f10/www/lectures/17-allocation-basic.pptx

    http://en.wikipedia.org/wiki/C_dynamic_memory_allocation

    ReplyDelete
  3. USER VIEW OF MEMORY-----

    When a process running in user mode requests additional memory,pages are allocated from the list of free page frames maintained by the kernel.THis list is typically populated using a page replacement Algo which contains free pages scattered throughout physical memory.

    Physical memory is divided into fixed size frames and logical memory into blocks of same size called pages.The process is executed by loading its pages into available memory frames

    ReplyDelete
  4. USER LEVEL MEMORY MANAGEMENT in LINUX------
    http://www.informit.com/articles/article.aspx?p=173438

    ReplyDelete
  5. Why don't we use malloc in embedded systems ? How is memory allocated in Embedded systems ?

    Malloc uses variable sized blocks in allocating memory. Using variable sized blocks has the disadvantage of leaving holes in the memory [fragmentation], which may lead to certain memory requests not being satisfied even though there is enough memory in the system. Memory defragmentation is a very costly exercise and not even general purpose machines do it automatically, let alone embedded systems. So, most embedded systems use fixed size blocks for memory allocation. This has the advantage that all the holes that are created in the system are of the same size which is that of the fixed size block. Hence there is no need for defragmentation.

    ReplyDelete