0

Just a curious question though!

While going through various techniques of memory allocation and management, specially paging in which the fixed size block is assigned to a particular request, everything goes fine until when the process exits the memory leaving behind spaces for non-contiguous allocation for other processes. Now for that case the data structure Page Tables keeps a track of corresponding Page to Frame number.

Can an algorithm be designed in such a way that pages are always allocated after the last allocated page in the memory and dynamically shifting and covering the empty page space that is caused by the freeing process (from somewhere in the middle) at every minute intervals, maintaining a row of contiguous memory at any given time. This may preserve contiguous memory allocation for processes thus enabling quicker memory access.

For e.g:

 ----------                                            ----------
|  Page 1  |   After Page 2 is deallocated            |  Page 1  |
 ----------        rather than assigning               ----------
|  Page 2  |    the space to some other process       |  Page 3  |
 ----------        in a non-contiguous fashion,        ----------
|  Page 3  |     there can be something               |  Page 4  |
 ----------            like this -->                   ----------
|  Page 4  |                                          |          |
 ----------                                            ----------

The point is that the memory allocation can be continuous and always after the last allocated page.

I would appreciate if I am told about the design flaws or the parameters one has to take care of while thinking of any such algorithm.

Ashish K
  • 905
  • 10
  • 27
  • It might help to look at this [related post](http://softwareengineering.stackexchange.com/questions/279049/what-should-be-kept-in-mind-when-writing-a-garbage-collector). Or read [this one](http://stackoverflow.com/questions/6866531/how-to-implement-a-garbage-collector). There is also a [GitHub project](https://github.com/dotnet/coreclr/blob/master/Documentation/botr/garbage-collection.md) devoted to [Gargabe Collection](https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)). – Axel Kemper Mar 30 '17 at 11:41
  • Hi @alex, I would like to know how a code to dynamically shift and cover empty space between allocated pages (empty space due to pages that free the memory after their execution) in the memory region be related to a code to implement a garbage collector? – Ashish K Mar 30 '17 at 11:50
  • Yes, I would could call such a scheme a "moving garbage collector". A garbage collector is quite complex on its own, but a moving one is even more complex. – Axel Kemper Mar 30 '17 at 11:56
  • Ok but I think in case of garbage collector, the memory region is deallocated for the objects that are holding the memory. I say something sort of reallocation here. As in, assume P1, P2, P3 and P4 are aligned in the memory and P2 leaves after job is done. An algo that would align P3 in place of P2 and P4 in place of P3 making P1, P3 and P4 in continuous memory address. Now the next malloc will anyway be after P4 and similar trend is followed if a process exits from the middle. – Ashish K Mar 30 '17 at 12:11

1 Answers1

1

This is called 'compacting' garbage collection, usually part of a mark-compact garbage collection algorithm: https://en.wikipedia.org/wiki/Mark-compact_algorithm

As with any garbage collector, the collection/compaction is the easy part. The hard part is letting the program that you're collecting for continue to work as you're moving its memory around.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87