Question

In this assignment, you will implement a Memory Management System(MMS). Using C Programming Language..... MAKE SURE YOU USE C PROGRAMMING

Your MMS will handle all requests of allocation of memory space by different users (one thread per user) …. HINT(You will use Pthreads and Semaphores).

Your MMS will provide the user with an interface for making memory requests and also for freeing up memory that is no longer needed by the user. One of the jobs of your memory management system is to service user memory requests by matching the size of the request with a large enough space, from which to satisfy the request. Make sure that the size of memory allocated is in bytes and is in a power of 2.

When your MMS gets the request of size size, it will allocate a space of memory with the size size memory chunk that is requested. Write the code and use two functions, one called memory_malloc to allocate memory and the other memory_free to de-allocate the memory. Make sure the know the size of what is being freed. Every time a block of memory is allocated by memory_malloc, store the size of that block allocated (as an integer) somewhere. Note that memory_malloc returns a pointer to the first byte of the block of memory it just allocated. The size of the block allocated will be used when the user calls memory_free to return the block to the free memory blocks. It is a good idea to merge freed memory blocks together to give a block of a larger size in case some user needs it.

First, use a standard malloc (or equivalent) call to allocate a large amount of memory from the system. The specific amount of memory that your system will be able to handle will be determined by parameter MAX_SIZE. This allocated memory will form free memory blocks and allocated blocks of memory to the user are taken from here when memory_malloc is called.

Your memory_malloc should call one of the three functions First-fit, Best-fit, or Worst-fit. To implement these functions please follow the definition of each one of them as seen and explained in class.

Your program should have one command-line argument which specifies the number N of threads (users). When the program starts, it creates N+1 threads which place themselves in a thread pool. N of these threads will be the users that request memory space from your MMS. The MMS is implemented as a separate thread, that is the remaining of the N+1 threads. Make sure to pay attention to thread synchronization issues, if any.

Work in multithreading concept where each thread will request the MMS for some memory space, print on the screen “I am thread # thread-ID going to sleep”, than sleep for some random time and then wakes up and prints on the screen “I am thread #ID, waking up”, and then ask the MMS to release that memory block previously allocated to the thread. Make sure you cover the case where the MMS runs out of memory space. In this case it will choose one or more thread users and treats them as the ones that have the lowest priority and forces them to give up their allocated memory. Make sure that you cover the case where you need to merge freed memory holes together to cover the case where a larger size is needed by some user(s), as described in paragraph-6 above. Make sure that you cover the case where a very large size requested cannot be accommodated by the system. In this case the requesting thread shall be notified with an error notice and the need to request a size no larger than the specified MAX_SIZE that you specify/consider when designing your MMS, and return said thread(s) to the pool of threads, to complete/try again among the other threads in the pool.

Answer 1

//Custom_MMS.c

#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef unsigned char byte;

byte *pool, *pool_ptr, *helper, *helper_ptr;
size_t pool_size, left_space;
const byte SIZE_MARK_MAX = UCHAR_MAX >> 1;

void use_Custom_MMS(size_t size)
{
pool = pool_ptr = (byte *)malloc(size);
helper = helper_ptr = (byte *)calloc(size, 1);
pool_size = left_space = size;
}

void free_Custom_MMS()
{
free(pool);
free(helper);
}

void set_size_mark(size_t size, byte *ptr)
{
if (size <= SIZE_MARK_MAX)
{
*ptr = (size << 1) + 1;
}
else
{
*ptr = 2;
*(size_t *)(ptr + 1) = size;
}
}

size_t get_size_mark(const byte *ptr)
{
if (*ptr & 1)
{
return *ptr >> 1;
}
return *(size_t *)(ptr + 1);
}

int search(size_t size)
{
if (size > pool_size)
{
return 0;
}
byte *start_ptr = helper_ptr;
if (left_space == 0)
{
goto no_left_space;
}
helper_ptr += left_space;
left_space = 0;
while (1)
{
if (helper_ptr == start_ptr)
{
return 0;
}
no_left_space:
if (helper_ptr == helper + pool_size)
{
helper_ptr = helper;
left_space = 0;
}
if (*helper_ptr)
{
left_space = 0;
helper_ptr += get_size_mark(helper_ptr);
}
else
{
++left_space;
++helper_ptr;
}
if (left_space == size)
{
while (1)
{
if (helper_ptr == helper + pool_size || *helper_ptr)
{
break;
}
++left_space;
++helper_ptr;
}
break;
}
}
helper_ptr -= left_space;
pool_ptr = helper_ptr - helper + pool;
return 1;
}

void *mj_malloc(size_t size)
{
if (size > left_space)
{
if (!search(size))
{
return NULL;
}
}
set_size_mark(size, helper_ptr);
byte *ptr = pool_ptr;
pool_ptr += size;
helper_ptr += size;
left_space -= size;
return ptr;
}

void *mj_calloc(size_t len, size_t unit)
{
size_t size = len * unit;
void *ptr = mj_malloc(size);
memset(ptr, 0, size);
return ptr;
}

void mj_free(void *ptr)
{
byte *temp_helper_ptr = (byte *)ptr - pool + helper;
if (*temp_helper_ptr & 1)
{
*temp_helper_ptr = 0;
}
else
{
// OLD
// memset(temp_helper_ptr, 0, sizeof(size_t) + 1);

// NEW
*temp_helper_ptr = 0;
*(size_t *)(temp_helper_ptr + 1) = 0;
}
}

size_t kb_to_b(size_t kb)
{
return 1000 * kb;
}

size_t mb_to_b(size_t mb)
{
return kb_to_b(1000 * mb);
}

size_t gb_to_b(size_t gb)
{
return mb_to_b(1000 * gb);
}

//Custom_MMS.h

#ifndef Custom_MMS_H
#define Custom_MMS_H

#include <stddef.h>

#define malloc mj_malloc
#define calloc mj_calloc
#define free mj_free

void use_Custom_MMS(size_t size);
void free_Custom_MMS();
void *mj_malloc(size_t size);
void *mj_calloc(size_t len, size_t unit);
void mj_free(void *ptr);
size_t kb_to_b(size_t kb);
size_t mb_to_b(size_t mb);
size_t gb_to_b(size_t gb);

#endif

//test.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#ifdef Custom_MMS
#include "Custom_MMS.h"
#endif

enum {ARRAY_LEN = 50000};
int *array[ARRAY_LEN];
long long sum = 0;

int confuse_the_compiler(int n)
{
return n % 10 > 5 ? -n / 2 : n * 2;
}

void start()
{
for (int i = 1; i <= ARRAY_LEN; ++i)
{
for (int j = 0; j < i; ++j)
{
array[j] = (int *)malloc(sizeof(int));
array[j][0] = j + 1;
}
for (int j = i - 1; j >= 0; --j)
{
sum -= j;
int n = confuse_the_compiler(array[j][0]);
if (n != 0)
{
sum += n;
free(array[j]);
}
}
}
}

int main()
{

#ifdef Custom_MMS
use_Custom_MMS(ARRAY_LEN * sizeof(int));
#endif

time_t start_time = clock();
start();
time_t end_time = clock();
printf("\nelapsed time: %.3f\n", (double)(end_time - start_time) / CLOCKS_PER_SEC);
printf("%lld", sum);

#ifdef Custom_MMS
free_Custom_MMS();
#endif

return 0;
}