memory management

Question

Implement a list based memory management system with two
versions of mem alloc using first-fit and best-fit policy respectively. The input consists of multiple
lines. Each line starts with a keyword, which is one of "init", "alloc" or "dealloc". The line starting
with "init" keyword has two numbers, total available memory (a number between 1 and 231 - 1,
and a string "best-fit" or "first-fit". 0 indicates first-fit policy and 1 indicates best-fit policy. The
number after the keyword "alloc" gives the number of memory units for the allocation request. The
line with "dealloc" keyword takes a number. For example, dealloc 1 means that the allocation made
by the first allocation request is being returned. In general, "dealloc" k means that the allocation
made by the kth allocation request, is being returned.

Sample Input.
init 1000 first-fit
alloc 340
alloc 110
dealloc 1
alloc 200
alloc 300
dealloc 2
alloc 205

Sample Output.
(allocated, 0, 200) (allocated, 200,205) (free,405, 50) (allocated,450,300) (free, 750,250)

Vulpes · Answer

This is a bit rushed so I'd check it carefully but it seems to be working OK: using System; using System.Collections.Generic; using System.IO; class Block { public int Start { get; set; } public int Size { get; set; } public int Next { get {return Start + Size;} } public int Number { get; set; } public Block(int start int size int number) { Start = start; Size = size; Number = number; } } enum AllocType { BestFit FirstFit } class MemoryManager { List blocks; int capacity; AllocType allocType; int allocNumber = 0; public MemoryManager(int capacity AllocType allocType) { blocks = new List (); this.capacity = capacity; this.allocType = allocType; } public void Allocate(int size) { if (size > capacity) { Console.WriteLine(Unable to allocate a block of size  + size); return; } allocNumber++; if (allocType == AllocType.FirstFit) { if (blocks.Count == 0 || blocks[0].Start >= size) { Block b = new Block(0 size allocNumber); blocks.Insert(0 b); return; } else if (blocks.Count == 1) { if (blocks[0].Next + size > capacity) { Console.WriteLine(Unable to allocate a block of size  + size); return; } Block b = new Block(blocks[0].Next size allocNumber); blocks.Add(b); return; } else { for(int i = 1; i { if((blocks[i].Start - blocks[i - 1].Next) >= size) { Block b = new Block(blocks[i - 1].Next size allocNumber); blocks.Insert(i b); return; } } if (blocks[blocks.Count - 1].Next + size > capacity) { Console.WriteLine(Unable to allocate a block of size  + size); return; } Block bb = new Block(blocks[blocks.Count - 1].Next size allocNumber); blocks.Add(bb); return; } } else { if (blocks.Count == 0) { Block b = new Block(0 size allocNumber); blocks.Add(b); return; } else { int min = Int32.MaxValue; int index = 0; if (blocks[0].Start >= size) min = blocks[0].Start; if (blocks.Count == 1) { int len = capacity - blocks[0].Next; if (len >= size && min > len) { min = len; index = 1; } } else { for(int i = 1; i { int len = blocks[i].Start - blocks[i - 1].Next; if (len >= size && min > len) { min = len; index = i; } len = capacity - blocks[blocks.Count - 1].Next; if (len >= size && min > len) { min = len; index = blocks.Count; } } } if (index == 0) { Block b = new Block(0 size allocNumber); blocks.Insert(0 b); return; } else if (index { if (blocks[index - 1].Next + size > capacity) { Console.WriteLine(Unable to allocate a block of size  + size); return; } Block b = new Block(blocks[index - 1].Next size allocNumber); blocks.Insert(index b); return; } else { if (blocks[blocks.Count - 1].Next + size > capacity) { Console.WriteLine(Unable to allocate a block of size  + size); return; } Block b = new Block(blocks[blocks.Count - 1].Next size allocNumber); blocks.Add(b); return; } } } } public void Deallocate(int number) { for(int i = 0; i { if (blocks[i].Number == number) { blocks.RemoveAt(i); return; } } Console.WriteLine(No block exists with an allocation number of  + number); } public void Display() { if (blocks.Count == 0) { Console.WriteLine(); return; } string text = ; if (blocks[0].Start > 0) { text += String.Format(({0} {1} {2})
 free 0 blocks[0].Start); } text += String.Format(({0} {1} {2})
 allocated blocks[0].Start blocks[0].Size); for(int i = 1; i { if (blocks[i].Start > blocks[i - 1].Next) { int len = blocks[i].Start - blocks[i - 1].Next; text += String.Format(({0} {1} {2})
 free blocks[i - 1].Next len); } text += String.Format(({0} {1} {2})
 allocated blocks[i].Start blocks[i].Size); } if (blocks[blocks.Count - 1].Next { int len = capacity - blocks[blocks.Count - 1].Next; text += String.Format(({0} {1} {2})
 free blocks[blocks.Count - 1].Next len); } Console.WriteLine(text); } } class Program { static void Main() { var mm = new MemoryManager(1000 AllocType.FirstFit); mm.Allocate(340); mm.Allocate(110); mm.Deallocate(1); mm.Allocate(200); mm.Allocate(300); mm.Deallocate(2); mm.Allocate(205); mm.Display(); Console.ReadKey(); } } The output is: (allocated 0 200) (allocated 200 205) (free 405 45) (allocated 450 300) (free 750 250)