CS3413/Assignment6/code/main.c

246 lines
5.5 KiB
C
Raw Permalink Normal View History

2023-11-16 23:12:14 -04:00
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
// 1 - best fit
// 2 - worst fit
// 3 - first fit
enum Algorithm {
BEST_FIT = 1,
WORST_FIT = 2,
FIRST_FIT = 3
};
enum Algorithm algorithm;
int memSize;
int totalAllocated = 0;
int totalMemAllocated = 0;
int totalFailed = 0;
int totalTerminated = 0;
int totalFreedMemory = 0;
int *memory;
void allocateByIndex(int index, int howMuchToAllocate, int processId) {
for (int i = index; i < index + howMuchToAllocate; ++i) {
memory[i] = processId;
// Statistics
totalMemAllocated++;
}
}
bool doAllocate(int howMuchToAllocate, int processId) {
int FirstFitIndex = -1;
int WorstFitIndex = -1;
int BestFitIndex = -1;
2023-11-16 23:46:54 -04:00
int startIndex = -1;
2023-11-16 23:12:14 -04:00
int size = 0;
2023-11-16 23:46:54 -04:00
2023-11-16 23:12:14 -04:00
int smallestSoFar = memSize;
int biggestSoFar = 0;
for (int i = 0; i < memSize; ++i) {
if (memory[i] == 0) {
2023-11-16 23:46:54 -04:00
if (size == 0) {
startIndex = i;
}
2023-11-16 23:12:14 -04:00
size++;
2023-11-16 23:46:54 -04:00
} else {
if (size >= howMuchToAllocate) {
// On first fit, set the start index
2023-11-16 23:12:14 -04:00
if (FirstFitIndex == -1) {
2023-11-16 23:46:54 -04:00
FirstFitIndex = startIndex;
}
// If the size of the contiguous empty memory is bigger than the largest contiguous empty memory so far, set the index and update the size
if (size > biggestSoFar) {
WorstFitIndex = startIndex;
2023-11-16 23:12:14 -04:00
biggestSoFar = size;
2023-11-16 23:46:54 -04:00
}
// If the size of the contiguous empty memory is smaller than the smallest contiguous empty memory so far, set the index and update the size
if (size > 0 && smallestSoFar > size) {
BestFitIndex = startIndex;
2023-11-16 23:12:14 -04:00
smallestSoFar = size;
}
}
size = 0;
2023-11-16 23:46:54 -04:00
startIndex = -1;
2023-11-16 23:12:14 -04:00
}
}
2023-11-16 23:46:54 -04:00
// Check if the last chunk is the first fit
if (FirstFitIndex == -1 && size >= howMuchToAllocate) {
FirstFitIndex = startIndex;
2023-11-16 23:12:14 -04:00
}
2023-11-16 23:46:54 -04:00
// Check if the last chunk is the smallest
if (size > 0 && smallestSoFar >= size) {
BestFitIndex = startIndex;
}
// Check if the last chunk is the biggest
if (size >= biggestSoFar) {
WorstFitIndex = startIndex;
2023-11-16 23:12:14 -04:00
}
// Since first fit is always set if there is space, we can error on that for any algorithm
2023-11-16 23:46:54 -04:00
if (FirstFitIndex == -1 || howMuchToAllocate > memSize) {
2023-11-16 23:12:14 -04:00
printf("Process %d failed to allocate %d memory\n", processId, howMuchToAllocate);
// Statistics
totalFailed++;
// Early exit because there is no space, so don't touch memory
return false;
}
switch (algorithm) {
case BEST_FIT: {
allocateByIndex(BestFitIndex, howMuchToAllocate, processId);
break;
}
case WORST_FIT: {
allocateByIndex(WorstFitIndex, howMuchToAllocate, processId);
break;
}
case FIRST_FIT: {
allocateByIndex(FirstFitIndex, howMuchToAllocate, processId);
break;
}
default: {
printf("There was an error, the algorithm is uninitialized");
exit(0);
}
}
// Statistics
totalAllocated++;
return true;
}
bool doFree(int processId) {
bool found = false;
for (int i = 0; i < memSize; ++i) {
if (memory[i] == processId) {
memory[i] = 0;
found = true;
// Statistics
totalFreedMemory++;
}
}
if (found) {
// Statistics
totalTerminated++;
} else {
printf("Process %d failed to free memory\n", processId);
// Statistics
// Might not need to be counted as a failed request?
totalFailed++;
}
return found;
}
int calcFinalMemory() {
int total = 0;
for (int i = 0; i < memSize; ++i) {
if (memory[i] == 0) {
total++;
}
}
return total;
}
int getNumberOfChunks() {
int total = 0;
bool inChunk = false;
for (int i = 0; i < memSize; ++i) {
if (memory[i] == 0) {
if (!inChunk) {
inChunk = true;
total++;
}
} else {
inChunk = false;
}
}
return total;
}
int getSmallest() {
int smallestSize = memSize;
int size = 0;
for (int i = 0; i < memSize; ++i) {
if (memory[i] == 0) {
size++;
} else if (smallestSize > size && size != 0) {
smallestSize = size;
size = 0;
}
}
// Check if the last chunk is the smallest
2023-11-16 23:46:54 -04:00
if (smallestSize >= memSize) {
2023-11-16 23:12:14 -04:00
smallestSize = size;
}
return smallestSize;
}
int getBiggest() {
int biggestSize = 0;
int size = 0;
for (int i = 0; i < memSize; ++i) {
if (memory[i] == 0) {
size++;
2023-11-16 23:46:54 -04:00
} else if (size > biggestSize) {
biggestSize = size;
2023-11-16 23:12:14 -04:00
size = 0;
}
}
// Check if the last chunk is the biggest
2023-11-16 23:46:54 -04:00
if (biggestSize <= size) {
2023-11-16 23:12:14 -04:00
biggestSize = size;
}
return biggestSize;
}
int main(int argc, char **argv) {
for (int i = 0; i < argc; i++) {
if (strcmp(argv[i], "-b") == 0) {
algorithm = BEST_FIT;
} else if (strcmp(argv[i], "-w") == 0) {
algorithm = WORST_FIT;
} else if (strcmp(argv[i], "-s") == 0) {
memSize = atoi(argv[i + 1]);
} else if (strcmp(argv[i], "-f") == 0) {
algorithm = FIRST_FIT;
}
}
if (memSize >= 0) {
// Use calloc to initialize memory to 0, which means empty in our case
memory = calloc(memSize, sizeof(int));
} else {
printf("The program requires size\n");
exit(0);
}
char operation;
int id = 1337;
int size;
while (EOF != scanf("%c", &operation)) {
switch (operation) {
case 'N':
scanf(" %d %d\n", &id, &size);
doAllocate(size, id);
break;
case 'T':
scanf(" %d\n", &id);
doFree(id);
break;
case 'S':
printf("Total Processes created %d, Total allocated memory %d, Total Processes\n"
"terminated %d, Total freed memory %d, Final memory available %d, Final\n"
"smallest and largest fragmented memory sizes %d and %d, total failed requests:%d, number of memory chunks: %d\n",
totalAllocated, totalMemAllocated,
totalTerminated, totalFreedMemory, calcFinalMemory(),
getSmallest(), getBiggest(), totalFailed, getNumberOfChunks());
break;
}
}
2023-11-16 23:50:51 -04:00
// Free the memory, just for good measure
2023-11-16 23:51:06 -04:00
free(memory);
2023-11-16 23:12:14 -04:00
return 0;
}