memory management

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)

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 < blocks.Count; 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 < blocks.Count; 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 <= blocks.Count - 1)

{

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 < blocks.Count; 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})\n", "free", 0, blocks[0].Start);

}

text += String.Format("({0}, {1}, {2})\n", "allocated", blocks[0].Start, blocks[0].Size);

for(int i = 1; i < blocks.Count; i++)

{

if (blocks[i].Start > blocks[i - 1].Next)

{

int len = blocks[i].Start - blocks[i - 1].Next;

text += String.Format("({0}, {1}, {2})\n", "free", blocks[i - 1].Next, len);

}

text += String.Format("({0}, {1}, {2})\n", "allocated", blocks[i].Start, blocks[i].Size);

}

if (blocks[blocks.Count - 1].Next < capacity)

{

int len = capacity - blocks[blocks.Count - 1].Next;

text += String.Format("({0}, {1}, {2})\n", "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)

1 Reply

Know the answer? Post it — somebody with the same question will find it here.

Vulpes13y ago
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 < blocks.Count; 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 < blocks.Count; 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 <= blocks.Count - 1)
{
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 < blocks.Count; 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})\n", "free", 0, blocks[0].Start);
}

text += String.Format("({0}, {1}, {2})\n", "allocated", blocks[0].Start, blocks[0].Size);

for(int i = 1; i < blocks.Count; i++)
{
if (blocks[i].Start > blocks[i - 1].Next)
{
int len = blocks[i].Start - blocks[i - 1].Next;
text += String.Format("({0}, {1}, {2})\n", "free", blocks[i - 1].Next, len);
}
text += String.Format("({0}, {1}, {2})\n", "allocated", blocks[i].Start, blocks[i].Size);
}

if (blocks[blocks.Count - 1].Next < capacity)
{
int len = capacity - blocks[blocks.Count - 1].Next;
text += String.Format("({0}, {1}, {2})\n", "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)