Assignment IV; due to May 4-5, 2009:

1. Write a memory allocator simulator that implements a dynamic partitioning placement algorithm;
   • You can choose any one of the first-fit, next-fit, best-fit, worst-fit algorithms,
   • Processes do not grow or shrink,
   • No compaction is performed by the memory allocator,
   • You should keep the holes and processes in the data structures such as;
     • a bitmap,
     • or a linked-list,
     • or a doubly linked-list,
     • or just a list (an array).
   • You may need to make use of a searching algorithm to find a big enough room for the new process. You can use any of the searching algorithm. Your search algorithm will be important in the improvement of the efficiency (such that keeping the list of holes sorted by size or will it really improve?),
   • You should also supply a mechanism to deallocate processes. When a process terminates, the memory allocated to that process is returned to the holes. You should take care to combine (coalesce) holes that are adjacent to each other and form an larger contiguous hole.
   • Explain all design policies, the data structures and search algorithms etc. used clearly in the readme.txt file,
   • You will have an input file containing;
     • total size of the memory,
     • processes,
     • placements (allocation, deallocation),
     • first column is for the placement operation and second one is for the process id and third one (if applicable) is for the memory size to allocate.

       MemorySize     //initialize memory size
       A  pid size    //allocate this process with that amount memory
       D  pid         //deallocate memory for this process
       

   • Make error checking for allocation (such that not having big enough room).
   • Report the current state of the memory if any placement happens both to a file output.txt and to stdout such as

     *********************************
     An Allocation Happened starting at location 12345 with size 67.
     Memory Size=16384 bytes, allocated= 384, free= 16000.
     There are currently 20 holes and 13 active processes.
     Holes:
     1: starting at= 0, size= 123
     .
     .
     .
     20: starting at= 12412, size= 3972
     Processes:
     1: id= 4, starting at= 124, size= 23
     .
     .
     .
     13: id= 30, starting at= 12345, size= 67
     

   • Have separate data structures for the holes and processes,
   • An input file may look as follows;

     16384
     A 1 234 
     A 2 567
     A 3 89
     D 1
     A 4 118
     D 3
     A 5 11 
     D 2
     D 5
     D 4
     .
     .
     .
     

     You are given 10 lines. You should have 30 process and 50 lines at least. You should complete the file.
   • Take care about the processes that are attempted to deallocate without allocation (because of having no room). At that situation, you should try to allocate this process first, then at the next first deallocation operation you should deallocate this process either.
   • What is the highest ratio of the external fragmentation at the end of the simulation? (Assume that the holes less than 10 bytes are wasted)