Implementing a simple garbage collector in C# - Part 4
In this article, we illustrate why allocating memory without deallocating it can be a source of serious issues and headaches for a programmer.
As a simple illustration of how to implement a garbage collection algorithm and to become familiar with the methods involved, we will implement a program with no collection.
1public NoneGarbageCollector()
2{
3 _threads = new List<RuntimeThread>();
4 _heap = new RuntimeHeap(64);
5}
For this strategy and the subsequent ones, we will allocate a heap of 64 characters, and we will consider it impossible to claim additional space from the operating system. In a real-world scenario, the garbage collector typically has the ability to request new memory, but for illustrative purposes, we impose this limitation. It is important to note that this limitation neither hinders nor detracts from the overall understanding.
Implementing the ExecuteInstruction method
This method is nearly the same for all strategies. It processes one instruction at a time, pushing or popping variables on the stack.
1public override void ExecuteInstruction(Instruction instruction)
2{
3 if (instruction.Operation == "CREATE_THREAD")
4 {
5 AddThread(instruction.Name);
6 return;
7 }
8
9 var thread = _threads.FirstOrDefault(x => x.Name == instruction.Name);
10 if (thread == null) return;
11
12 if (instruction.Operation == "PUSH_ON_STACK")
13 {
14 thread.PushInstruction(instruction.Value);
15 }
16 if (instruction.Operation == "POP_FROM_STACK")
17 {
18 thread.PopInstruction();
19 }
20}
Implementing the Allocate method
The Allocate method attempts to find an empty space in the memory and allocates it if there is enough room. If there is insufficient memory, an exception is raised.
1public override int Allocate(string field)
2{
3 var r = AllocateHeap(field);
4 if (r == -1) throw new InsufficientMemoryException();
5
6 return r;
7}
1private int AllocateHeap(string field)
2{
3 var size = _heap.Size;
4 var cells = field.ToArray();
5 var requiredSize = cells.Length;
6
7 // We need to find a contiguous space of requiredSize char.
8 var begin = 0;
9 while (begin < size)
10 {
11 var c = _heap.Cells[begin];
12 if (c.Cell != '\0')
13 {
14 begin++;
15 continue;
16 }
17
18 // Do not continue if there is not enough space.
19 if ((size - begin) < requiredSize) return -1;
20
21 for (var i = begin; i < begin + requiredSize; i++)
22 {
23 _heap.Cells[i].Cell = cells[i - begin];
24 }
25
26 var pointer = new RuntimeHeapPointer(begin, requiredSize);
27 _heap.Pointers.Add(pointer);
28
29 return begin;
30 }
31
32 return -1;
33}
Implementing the Collect method
This method is the simplest part of the problem: precisely, there is nothing to do.
1public override void Collect()
2{
3 return;
4}
Running the program
As one can imagine, this strategy allocates memory until the heap is exhausted. The result is, naturally, an exception being raised.
We can observe in the image below that the program endeavors to allocate memory for "Cascade" (7 chars) but encounters failure due to the availability of only 6 cells.
It is now time to delve into more interesting strategies. In the next article (here), we will spotlight the mark-and-sweep algorithm.