segmentation memory-management

grade-util.cpp

#include "grade_util.hpp"
#include "mem.hpp"

Segment* mk_segments(RawSegment* segs, int size) {
	if (size == 0)
		return nullptr;

	Segment** head = new Segment*;
	Segment** next_seg = head;
	Segment* last_seg = nullptr;

	for (RawSegment* p = segs+size-1; p >= segs; p--) {
		head = next_seg;
		Segment* new_seg = new Segment;
		new_seg->pid = p->pid;
		new_seg->start = p->start;
		new_seg->size = p->size;
		new_seg->next = last_seg;

		if (last_seg != nullptr) {
			last_seg->prev = new_seg;
		}

		*head = new_seg;

		next_seg = &((*head)->prev);
		last_seg = *head;
	}
	
	return *head;
}

bool comp_list(Segment* list1, Segment* list2, int size) {
	while ( (list1 != nullptr) && (list2 != nullptr) ) {
		if ( 
			list1->pid != list2->pid ||
			list1->start != list2->start ||
			list1->size != list2->size 
		   )
			return false;
		list1 = list1->next;
		list2 = list2->next;
	}
	return (list1 == nullptr) && (list2 == nullptr);
}

grade-util.hpp

#pragma once

#include "mem.hpp"

struct RawSegment {
	int pid;
	unsigned int start;
	unsigned int size;
};

Segment* mk_segments(RawSegment* segs, int size);

bool comp_list(Segment* list1, Segment* list2, int size);

grade.cpp

#include <iostream>

#include "mem.hpp"
#include "grade_util.hpp"

const int ALLOCATE_TC = 7;
const int DEALLOCATE_TC = 4;

std::pair<unsigned int, unsigned int> alloc_in[ALLOCATE_TC] = {{1, 5}, {0, 3}, {2, 6}, {3, 4}, {0, 2}, {4, 6}, {5, 3}};

unsigned int dealloc_in[DEALLOCATE_TC] = {0, 1, 3, 2};

RawSegment alloc_out[ALLOCATE_TC][10] = { 
	{{1, 0, 5}, {-1, 5, 45}}, 
	{{1, 0, 5}, {0, 5, 3}, {-1, 8, 42}},
	{{1, 0, 5}, {0, 5, 3}, {2, 8, 6}, {-1, 14, 36}},
	{{1, 0, 5}, {0, 5, 3}, {2, 8, 6}, {3, 14, 4}, {-1, 18, 32}},
	{{1, 0, 5}, {0, 5, 3}, {2, 8, 6}, {3, 14, 4}, {0, 18, 2}, {-1, 20, 30}},
	{{1, 0, 5}, {0, 5, 3}, {2, 8, 6}, {3, 14, 4}, {0, 18, 2}, {4, 20, 6}, {-1, 26, 24}},
	{{1, 0, 5}, {0, 5, 3}, {2, 8, 6}, {3, 14, 4}, {0, 18, 2}, {4, 20, 6}, {5, 26, 3}, {-1, 29, 21}} 
};

int alloc_out_sz[ALLOCATE_TC] = {2, 3, 4, 5, 6, 7, 8};

RawSegment dealloc_out[DEALLOCATE_TC][10] = {
	{{1, 0, 5}, {-1, 5, 3}, {2, 8, 6}, {3, 14, 4}, {-1, 18, 2}, {4, 20, 6}, {5, 26, 3}, {-1, 29, 21}},
	{{-1, 0, 8}, {2, 8, 6}, {3, 14, 4}, {-1, 18, 2}, {4, 20, 6}, {5, 26, 3}, {-1, 29, 21}},
	{{-1, 0, 8}, {2, 8, 6}, {-1, 14, 6}, {4, 20, 6}, {5, 26, 3}, {-1, 29, 21}},
	{{-1, 0, 20}, {4, 20, 6}, {5, 26, 3}, {-1, 29, 21}}
};

int dealloc_out_sz[DEALLOCATE_TC] = {8, 7, 6, 4};

double test_allocate() {
	double grade = 0;

	Segment* head = new Segment{.pid = -1, .start = 0, .size = 50, .prev = nullptr, .next = nullptr};
	Segment* correct_head;


	for (int i = 0; i < ALLOCATE_TC; i++) {
		allocate(&head, alloc_in[i].first, alloc_in[i].second);

		correct_head = mk_segments(alloc_out[i], alloc_out_sz[i]);
		bool test_passed = comp_list(correct_head, head, alloc_out_sz[i]);
		if (!test_passed) {
			std::cout << "Error in test case ALLOCATE_" << i << "\n";
			std::cout << "\tExpected list:\n\t\t";
			dump(std::cout, correct_head);
			std::cout << "\n\tGot:\n\t\t";
			dump(std::cout, head);
			std::cout << "\n";
		}

		grade += test_passed;
	}
	return (grade/ALLOCATE_TC);
}

double test_deallocate() {
	double grade = 0;

	Segment* head = mk_segments(alloc_out[ALLOCATE_TC-1], alloc_out_sz[ALLOCATE_TC-1]);
	Segment* correct_head;

	for (int i = 0; i < DEALLOCATE_TC; i++) {
		correct_head = mk_segments(dealloc_out[i], dealloc_out_sz[i]);

		deallocate(head, dealloc_in[i]);
		bool test_passed = comp_list(correct_head, head, dealloc_out_sz[i]);
		if (!test_passed) {
			std::cout << "Error in test case DEALLOCATE_" << i << "\n";
			std::cout << "\tExpected list:\n\t\t";
			dump(std::cout, correct_head);
			std::cout << "\n\tGot:\n\t\t";
			dump(std::cout, head);
			std::cout << "\n";
		}
		grade += test_passed;
	}
	return (grade/DEALLOCATE_TC);
}

int main() {
	double allocate_score = test_allocate();
	double deallocate_score = test_deallocate();

	std::cout << "Allocate score = " << 100*allocate_score << "%\n";

	std::cout << "Deallocate score = " << 100*deallocate_score << "%\n";

	std::cout << "Total (out of 100) = " << (allocate_score+deallocate_score)*50 << "%\n";
}

makefile

CXX = g++

all: build
build:
	"mkdir" -p "bin"
	$(CXX) -Wall mem.cpp -o bin/mem
grade:
	"mkdir" -p "bin"
	$(CXX) -D GRADING -Wall grade.cpp mem.cpp grade_util.cpp -o bin/grade
	bin/grade
run: build 
	bin/mem
archive:
	git archive --format=zip -o ejust-csc121-lab3.zip lab3

.PHONY: clean
clean: rm *.o *.exe

mem.cpp

#include <iostream>
#include "mem.hpp"
using namespace std;

// Return the allocated segment. If no place found, return nullptr
Segment* allocate(Segment** head, unsigned int pid, unsigned int size) {
	Segment* H = *head;
	int The_Memory(50), start(50), totalsize(50);
	while (H->next != nullptr)
	{
		H = H->next;
	}
	if (H->prev == NULL)
	{
		H->start = 0;
		if (int(size) > totalsize)
		{
			return nullptr;
		}
	}
	else if (size > H->size)
	{
		return nullptr;
	}
	H->pid = pid;
	H->size = size;
	Segment* segm2 = new Segment;
	H->next = segm2;
	segm2->next = nullptr;
	segm2->prev = H;
	start = H->start + size;
	The_Memory = totalsize - start;
	segm2->pid = -1;//means empty
	segm2->start = start;
	segm2->size = The_Memory;

	return *head;
}

// Free all segments allocated to process
void deallocate(Segment* head, unsigned int pid) {
	Segment* H = head;
	while (head->next != nullptr)
	{
		if (head->pid == (int)pid)
		{
			head->pid = -1;
		}
		head = head->next;
	}
	while (H->next != nullptr)
	{
		while (H->pid == H->next->pid)
		{
			H->size += H->next->size;
			H->next = H->next->next;
		}
		H = H->next;
	}
}

// For debugging/testing
// You can use this to print a list as follow: dump(std::cout, list_head)
//
// DO NOT EDIT
void dump(std::ostream& o, Segment* head) {
	while (head != nullptr) {
		o << "(" << ((head->pid == -1) ? "H" : "P") << ", " << head->start << ", " << head->size << ") " << "--> ";
		head = head->next;
	}
	o << "NULL";
}

#ifndef GRADING // Don't delete
int main() {
	// You don't need to write anything here, but you can use it to try out your program
	cout << "hello world";
	return 0;
}

#endif // Don't delete

mem.hpp

#pragma once 

#include <ostream>

struct Segment {
	int pid; // if pid = -1, then the Segment represents a hole, otherwise the Segment is allocated to the process with the pid
	unsigned int start;
	unsigned int size; // size in bytes
	Segment* prev;
	Segment* next;
};

Segment* allocate(Segment** head, unsigned int pid, unsigned int size);

void deallocate(Segment* head, unsigned int pid);

void dump(std::ostream& o, Segment* head);

task.md

CSC 121 - Sheet 3 - Problem 4

Your task is to implement memory management system using linked lists. You have two functions to implement: allocate and deallocate, both functions lie in mem.cpp. Your implementation should match the behaviour described in the next section.

The memory is represented as a linked list, and each segment in the memory is represented as a node in this list. The following is the definition of the Segment:

struct Segment {
	int pid; // if pid = -1, then the Segment represents a hole, otherwise the Segment is allocated to the process with the pid
	unsigned int start;
	unsigned int size; // size in bytes
	Segment* prev;
	Segment* next;
};

The definition lies in the file mem.hpp. It's important that you don't modify this definition.

Illustration

Assume the size of the memory is 50 B. At first, the memory is empty, so the list is as follows:

[Hole, start = 0, size = 48]

If we call the function allocate(*list, 1, 8) (allocate 8 bytes to process 1), the memory should be modified to be:

[Process 1, start = 0, size = 8] -> [Hole, start = 8, size = 40]

If at any point the memory was:

[Hole, start = 0, size = 4] -> [Process 4, start = 4, size = 2] -> [Hole, start = 6, size = 16] -> [Process 4, start = 22, size = 16] -> [Hole, start = 38, size = 10]

And then we call allocate(*list, 7, 16), you should find the first hole big enough to take 16 bytes, and take space from it:

[Hole, start = 0, size = 4] -> [Process 4, start = 4, size = 2] -> [Process 7, start = 6, size = 16] -> [Process 4, start = 22, size = 16] -> [Hole, start = 38, size = 10]

In this case, the hole was exactly the same size we wanted, so we allocated the whole hole to the process. If we then call deallocate(*list, 4), the list should be as follows:

[Hole, start = 0, size = 6] -> [Process 7, start = 6, size = 16] -> [Hole, start = 22, size = 26]

Notice that we deleted the segments allocated to process 4, and merged them with adjacent holes (if they exist). If we finally call deallocate(*list, 7), we will have this list:

[Hole, start = 0, size = 48]

Notice that the new hole was merged with both the left and the right holes.

Tips

• You can call dump(std::cout, head) to print the list starting at head

Setting Up Your Development Environment

You will need to have git, make, and gcc on your machine before you go on with the task. The installation process differs based on the operating system you're using. This document contains instructions for Windows and Linux. If you use MacOS, you will have to do your own research.

Windows

First, make sure you have Windows PowerShell installed. We will use scoop package manager to install the programs. Feel free to use another package manager if you wish, but the instructions are tailored for scoop.

To install scoop, run the following commands on powershell:

Set-ExecutionPolicy RemoteSigned -Scope CurrentUser
irm get.scoop.sh | iex

You might have some of them installed. To make sure, run each command on powershell and see if the output indicates that you have it. For example, this is the output if you run git when it's not installed:

git : The term 'git' is not recognized as the name of a cmdlet, function, script file, or operable program. Check the spelling of the name, or if a path was included, verify that the path
is correct and try again.
At line:1 char:1
+ git
+ ~~
    + CategoryInfo          : ObjectNotFound: (git:String) [], CommandNotFoundException
    + FullyQualifiedErrorId : CommandNotFoundException

Use the following command to install the programs:

scoop install git make gcc

If everything goes fine, you're done with the installation phase.

Linux

This will differ based on the distro you're using, but there is a chance that you have all these programs installed by default on your machine, so before proceeding with the installation, try using them first and see if they exist.

For Ubuntu, run:

sudo apt-get install build-essential git

For Arch, run:

sudo pacman -S base-devel git

For other distros, the process is roughly the same.

Clone the Project

First, you need to clone (create a local copy) the project:

git clone https://github.com/salmanjnr/ejust-csc121-lab.git

This will create a folder with the name ejust-csc121-lab in your current directory. Go into the directory with the following command:

cd ejust-csc121-lab

Then run the following command:

git checkout lab3

Compile and Run

To compile and run you project, enter the command make run in Windows PowerShell.

To test your program, run the command make grade. This will compile your program and test it over predefined testcases and output your score. The same test cases will be used to grade your project, so make sure you get an acceptable score before submission.

Submission

After finishing the lab, run the following commands:

git add .
git commit -m "Lab 3 done"
make archive

This will create a file named ejust-csc121-lab3.zip in the project directory. This is the file that you will submit.