代写CS2850 Assessed Coursework 2

2023-12-30 代写CS2850 Assessed Coursework 2

CS2850 Assessed Coursework 2

This assignment must be submitted by Friday, 5 January 2023, at 10 am.

Feedback will be provided on the date provided in the coursework grid.

Learning outcomes assessed

In this assignment, you will implement a toy model of a dynamic memory allocator. To complete

all the tasks you need to

• declare, define, and update variables and functions in C,

• use pointer arithmetic,

• know how a memory allocator works,

• read from stdin and write to stdout using getchar and printf, and

• allocate and free memory using malloc.

Instructions

Submit this assignment using the Moodle submission link 202324 CS2850 CW2: C mini-project by Fri￾day, 5 January 2023, at 10 am. The submission system allows you to submit a single archive file,

which should contain all your programs. Create a compressed directory, e.g. 202324cs2850.zip,

containing the four C files described in the following sections , step1.c, step2.c, step3.c, and

step4.c. We suggest you write a separate file, functions.c, with all auxiliary functions. To

include it in a task-specific program, e.g. step1.c, by write

1 #include "functions.c"

on top of the file. Your files will be recompiled and run in the submission directory with the compiler

available on the teaching server. Be sure your name or ID does not appear anywhere in your

submission.

Academic misconduct

Coursework submissions are routinely checked for academic misconduct (working together, copying

from sources, etc.). Penalties can range from a 10% deduction of the assignment mark, zero for

the assignment or the case being referred to a Senior Vice-Principal to make a decision (for repeat

offences). Further details can be found here.

Introduction

In this assignment, you write a program that simulates a dynamic memory allocator. The process

address space is represented by an array of characters, memory. Given a size in bytes, len, the

allocator scans the array to find a free memory block of size len and returns the index of the start

of the block. For simplicity, the program maintains an integer array of the same size as memory to

store the sizes of the allocated blocks. The address space is represented by

1

1 struct space {

2 char *memory;

3 int *sizes;

4 int len;

5 };

where memory and sizes are pointers to the first entry of the character and integer arrays and len

is their length. In the dynamic version of the program, the program stores an arbitrary number of

arbitrary sentences entered by a user on standard input. The size of the memory space grows when

needed. At the beginning, the allocator stores all blocks one after the other. When some blocks are

freed, allocating new blocks at the end becomes inefficient. The allocator should search the space

for the first block compatible with the required size. Your implementation should follow the steps

described in the next sections. Save a new C file, step#.c, for each section. Each program should

compile without errors and produce the expected output. After completing a section, test your

implementation with Valgrind. Even if there are no memory leaks, Valgrind may outline hidden

execution errors. Try to understand and fix all of them.

Example. If the initial size of the memory array is 10 and you use an input file, input.txt,

containing the following lines

1 Brian Kernighan

2 CS2850

3 Dennis Ritchie

4 and

5 The C Programming Language

a run of the final program should print

1 0000000000

2

3 0000000000000000000000000000000000000000000000

4 Brian Kernighan++

5 17///////////////00000000000000000000000000000

6 Brian Kernighan++CS2850++

7 17///////////////8///////000000000000000000000

8 Brian Kernighan++ D e n n i s Ritchie++

9 17///////////////0000000016//////////////00000

10 Brian Kernighan++and++ Dennis Ritchie++

11 17///////////////5////00016//////////////00000

12

13 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

14 Brian Kernighan++and++ Dennis Ritchie++The C Programming Language++

15 17///////////////5////00016//////////////28//////////////////////////0000000000000000000000000

16

17 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

on standard output. Note that the program automatically frees the sentence CS2500. The memory

grows when the user enters the sentences Brian Kerninghan and C Programming Language. The

allocator saves the sentence and in the first suitable available space. To print memory and sizes, you

can use printMemory and printSizes provided in the Appendix of this document or in Supporting

code for 202324 CS2850 CW2.

Step 1: Initialization (25 marks)

Create a file with all auxiliary functions called functions.c. On top of it, write the statements

for including unistd.h and stdlib.h. Below those, define the following macros,

1 #define BUSY ’+’

2 #define FREE ’ ’

3 #define BUSYSIZE --1

4 #define FREESIZE 0

2

and the structure defined above. You will use BUSY and FREE to mark the allocated and free entries

of memory and BUSYSIZE and FREESIZE to mark the allocated (non-starting) and free entries of

sizes. The first entry of an allocated block block is marked with the length of the block in sizes.

To complete this section’s task you need to implement 2 functions,

1. initializeMemory, which accepts an integer memSize and a pointer to the memory struct,

mem, as inputs, allocates two blocks of size memSize * sizeof(char) and memSize * sizeof(char)

using malloc, makes memory and sizes point to these blocks, sets len to memSize, initializes

the arrays by marking all entries with FREE and FREESIZE, and print memory and sizes by

calling printMemory and printSizes.

2. cleanMemory, which accepts a pointer to the memory struct, mem, as an input, replace all

entries of memory and sizes with FREE and FREESIZE, print memory and sizes by calling

printMemory and printSizes, and free the allocated memory by calling free.

Test your implementation by compiling and running q1.c in Supporting code for 202324 CS2850

CW2. The output should be

1

2 00000000000000000000000000000000000000000000000000

3

4 00000000000000000000000000000000000000000000000000

5

6 00000000000000000000000000000000000000000000000000

Before proceeding, make sure Valgrind does not detect execution errors or memory leaks.

Step 2: Stack Allocator (25 marks)

In this section, the task is to implement a stack-like allocator and de-allocator. This is different

from the heap-like allocator you will implement in the next section because a new memory block is

always allocated at the end of the previous one. The de-allocator takes the index of the first entry

of the block to be deallocated and removes its content by setting the block entries back to FREE

(in memory) and FREE (in FREESIZE). To complete this section’s task, you need to implement two

functions,

1. int stackAllocator, which accepts an integer nbytes and a pointer to the memory struct,

mem, as inputs, searches for the first entry of sizes marked with FREESIZE, check whether

there are nbytes available entries after it, writes nbytes on that entry of sizes, writes

BUSYSIZE on the nbytes − 1 following entries of sizes, finds the corresponding nbytes

entries in memory and mark them with BUSY, and returns the index of the first entry of the

newly allocated block, and

2. void deallocator, which accepts an integers, p, and a pointer to the memory struct, mem,

as inputs, find the location corresponding to p in sizes, read the block length, nbytes, from

that entry, and sets the nbytes entries of memory starting at p to FREE and the corresponding

nbytes entries of sizes to FREESIZE.

If the first entry marked with FREESIZE in sizes is too close to the end of the array, i.e. if there

are not nbytes entries of sizes marked with FREESIZE after it, stackAllocator should return

mem->len. This allows you to check from the program if the memory has been successfully allocated

before writing on it. The deallocator should not return anything. Test your implementation by

3

compiling and running q2.c in Supporting code for 202324 CS2850 CW2. All string facilities are

given in the appendix or in Supporting code for 202324 CS2850 CW2. The output of the program

should be

1

2 00000000000000000000000000000000000000000000000000

3 Brian Kernighan+++++

4 20//////////////////000000000000000000000000000000

5 Brian Kernighan+++++CS2850+++++

6 20//////////////////11/////////0000000000000000000

7 Brian Kernighan+++++

8 20//////////////////000000000000000000000000000000

9

10 00000000000000000000000000000000000000000000000000

The third sentence, Dennis Ritchie, is not allocated because there is not enough available space.

Check that the program behaves correctly even in such situations by running the binary with

Valgrind.

Step 3: Heap Allocator (25 marks)

In this section, you rewrite the allocator to make it a heap-like allocator, i.e. to let the program

allocate memory in the free space left by previous frees. To complete this section’s task, you need

to implement two functions,

1. int spaceScanner, which takes an integer, nbytes, and a pointer to the memory structure,

mem, as inputs, finds the first entry of sizes that is marked with FREESIZE and has nbytes

entries also marked with FREESIZE after it, and returns the index of the corresponding entry

of memory if the search is successful and mem->len otherwise, and

2. int heapAllocatorQ3, which has the same inputs as stackAllocation, calls spaceScanner

to obtain the start index, p, of a suitable block, sets the nbytes entries of memory after p to

FREE and the corresponding nbytes entries of sizes to FREESIZE, and returns p.

Test your implementation by compiling and running q3.c in Supporting code for 202324 CS2850

CW2with memSize set to 50. The output should be

1 00000000000000000000000000000000000000000000000000

2 Brian Kernighan++

3 17///////////////000000000000000000000000000000000

4 Brian Kernighan++CS2850++

5 17///////////////8///////0000000000000000000000000

6 Brian Kernighan++ D e n n i s Ritchie++

7 17///////////////0000000016//////////////000000000

8 Brian Kernighan++ D e n n i s Ritchie++

9 17///////////////0000000016//////////////000000000

10 Brian Kernighan++and++ Dennis Ritchie++

11 17///////////////5////00016//////////////000000000

12

13 00000000000000000000000000000000000000000000000000

The sentence and is now allocated in the free space once occupied by the sentence CS2850. The

sentence The C Programming Language is not allocated because the memory is not big enough.

You will fix this problem in the next section.

4

Step 4: User interactions (25 marks)

Before making the program interactive, you need a function that increases the size of the memory

if needed. In a real process, this means requiring the intervention of the Operating System (OS)

through a system call. In this toy model, you use mallloc to simulate the OS intervention by

reallocating memory and size. You also have to parse the input sentences and save them into

strings. As you do not want to restrict the length of a user sentence, you need to buffer it into a

dynamically allocated string that grows as new characters arrive. To complete this section’s task,

you need two implement two functions

1. void increaseMemory which takes an integer, nbytes, and a pointer to the memory struc￾ture, mem, as inputs, computes the length of the new memory, newLen, using

1 int newLen = mem-->len;

2 while (newLen -- mem-->len < nbytes)

3 newLen = 2 * (newLen + 1);

saves the content of memory, sizes, and len into three temporary variables, allocates a

new memory space by calling initializeMemory(newLen, mem), copies the content of the

temporary variable into the newly initialized memory, and free the old memory using free,

and

2. int readString, which takes a pointer to a string, i.e. a pointer to a pointer to a character,

s, as an input, calls malloc(1) to allocate a starting string, stores it in *s, gets characters

from the terminal by calling getchar until you reach a new line character or EOF, reallocates

the string to accommodate each new character through

1 len++;

2 *s = malloc(len + 1);

3 char *temp = *s;

4 copyString(temp, s, len);

5 free(temp);

where len is the length of the string before attaching the new character, stores the new

character in the len-th entry of *s, null terminates the final string, and returns 1 if the last

character is a new line character and 0 if the last character is EOF.

To copy the temporary integer array into the newly allocated size array, sizes, write a function,

copyArray(int *old, int *new, int len), by adapting copyString given in the appendix. You

also need to modify heapAllocatorQ3. Instead of returning mem->len if spaceScanner does not

find a suitable free block, the function should call increaseMemory until such a block becomes

available. For example, you can replace the early-return statement of the old implementation with

1 int t0;

2 while ((t0 = spaceScanner(nbytes, mem))== mem-->len) increaseMemory(nbytes, mem

);

Test your implementation by running the following program. Test your implementation by com￾piling and running q4.c in Supporting code for 202324 CS2850 CW2. The deallocator removes

the second sentence of each group of three sentences after the user enters the third one. A sample

output of this program is given in the section called Introduction.

Marking criteria

5

Full marks will be awarded for correct answers to the above questions. Submissions are assessed

on functionality and coding style. Try to write readable, well-formatted and well-commented code.

More importantly, all your programs must be compiled using gcc -Wall -Werror -Wpedantic and

run without errors on linux.cim.rhul.ac.uk. To spot possible execution issues, run the programs

with Valgrind and check that the end of the output is

1 ... == ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Before submitting, test your code with the assignment Moodle Code Checker. Passing all tests,

however, will not guarantee you get full marks. Please use the CS2850 Piazza Forum to post any

specific questions.

Extensions

This assignment is subject to College policy on extensions. If you believe you require an

extension please read the documentation carefully and guidelines here

Extenuating circumstances

If you submit an assessment and believe that the standard of your work was substantially affected

by your current circumstance then you can apply for Extenuating Circumstances. Details on how

to apply for this can be found here. Read the accompanying documentation on the above link

carefully. Please note decisions on Extenuating Circumstances are made at the end of the academic

year.

Late Submission

In the absence of acceptable extenuating cause, late submission of work will be penalised as follows:

1. for work submitted up to 24 hours late, the mark will be reduced by ten percentage marks;

2. for work submitted more than 24 hours late, the maximum mark will be zero.

A Auxiliary functions

Here you can find a possible implementation of the string-handling and printing facilities you need

for this assignment. The code is also available in Supporting code for 202324 CS2850 CW2.

1 void copyString(char *sIn, char *sOut, int len) {

2 int t = 0;

3 while (t < len) {

4 *(sOut + t) = *(sIn + t);

5 t++;

6 }

7 }

8

9 int stringLen(char *s) {

10 int t = 0;

11 while (*(s + t) != ’\0’) t++;

12 return t;

13 }

14

15 void printMemory(struct space *mem) {

16 int i = 0;

6

17 while (i < mem-->len) {

18 printf("%c", *(mem-->memory + i));

19 i++;

20 }

21 printf("\n");

22 }

23

24 void printSizes(struct space *mem) {

25 int i = 0;

26 int c;

27 while (i < mem-->len) {

28 int n = *(mem-->sizes + i);

29 int t = 10000;

30 while (n > 9) {

31 c = n/t;

32 n = n -- c * t;

33 t = t / 10;

34 if (c) {

35 c = c % 10 + ’0’;

36 printf("%c", c);

37 i++;

38 }

39 }

40 c = n % 10 + ’0’;

41 printf("%c", c);

42 i++;

43 }

44 printf("\n");

45 }

The plain text version of all codes in this document is available on the assignment Moodle page

202324 CS2850 CW2: C mini-project.

B Pseudocode

Here you can find the pseudocode of the functions you need to implement in this assignment.

1: function void initializeMemory(int len, struct space *mem)

2: let mem->memory point to a dynamically allocated array of length len* sizeof(char)

3: let mem->sizes point to a dynamically allocated array of length len * sizeof(int)

4: set mem->len to len

5: i ← 0

6: while i is smaller than mem->len do

7: set the i-th entry of mem->memory to FREE

8: set the i-th entry of mem->sizes to FREESIZE

9: i ← i + 1

10: print mem->memory using printMemory

11: print mem->sizes using printSizes

1: function void cleanMemory(struct space *mem)

7

2: i ← 0

3: while i is smaller than mem->len do

4: set the i-th entry of mem->memory to FREE

5: set the i-th entry of mem->sizes to FREESIZE

6: i ← i + 1

7: print mem->memory using printMemory

8: print mem->sizes using printSizes

9: free mem->memory

10: free mem->sizes

1: function int stackAllocator(int nbytes, struct space *mem)

2: t0 ← 0

3: while t0 + nbytes is smaller than mem->len and the t0-th entry of mem->sizes is not

FREESIZE do

4: t0 ← t0 + 1

5: if t0+ nbytes equals mem->len then

6: return mem->len

7: t ← 0

8: while t is smaller than nbytes and t0 + t is smaller than mem->len do

9: set the (t0 + t)-th entry of mem->memory to BUSY

10: set the (t0 + t)-th entry of mem->sizes to BUSYSIZE

11: t ← t + 1

12: set the t0-th entry of mem->sizes to nbytes

13: return t0

1: function void deallocator(t0, struct space *mem)

2: if t0 equals mem->len or is negative then

3: return

4: let nbytes be the value stored in the t0-th location of mem->sizes

5: t ← 0

6: while t is smaller than nbytes do

7: set the (t0 + t)-th entry of mem->memory to FREE

8: set the (t0 + t)-th entry of mem->sizes to FREESIZE

9: t ← t + 1

1: function int spaceScanner(int nbytes, struct space *mem)

2: t0 ← 0

3: s ← 0

4: while s = 0 and t0 is smaller than mem->len do

5: t ← 0

6: while t0+t is smaller than mem->len and the (t0+t)-th entry of mem->sizes is FREESIZE

do

7: t ← t + 1

8

8: if t is larger than nbytes then

9: s ← 1

10: else

11: t0 ← t0 + 1

12: return t0

1: function int heapAllocatorQ3(int nbytes, struct space *mem) (for Q3)

2: t0 ← spaceScanner(nbytes, mem)

3: if t0 = mem->len then

4: return t0

5: t ← 0

6: while t is smaller than nbytes do

7: set the (t0 + t)-th entry of mem->memory to BUSY

8: set the (t0 + t)-th entry of mem->sizes to BUSYSIZE

9: t ← t + 1

10: set the t0-th entry of mem->sizes to nbytes

11: return t0

1: function void increaseMemory(int nbytes, struct space *mem)

2: t ← mem->len

3: while the difference between t and mem->len is smaller than nbytes do

4: t ← 2(t + 1)

5: let s be a pointer to char

6: s ←mem->memory

7: let a be a pointer to int

8: a ←mem->sizes

9: ℓ ←mem->len

10: call initializeMemory with arguments t and mem

11: copy the content of the character array pointed by s into mem->memory using copyString

12: copy the content of the integer array pointed by a into mem->sizes using copyArray

13: free s and a

1: function int heapAllocator(int nbytes, struct space *mem) (for Q4)

2: t0 ←spaceScanner(nbytes, mem)

3: while t0 equals mem->len do

4: increaseMemory(nbytes, mem)

5: t0 ← spaceScanner(nbytes, mem)

6: t ← 0

7: while t is smaller than nbytes do

8: set the (t0 + t)-th entry of mem->memory to BUSY

9: set the (t0 + t)-th entry of mem->sizes to BUSYSIZE

10: t ← t + 1

9

11: set the t0-th entry of mem->sizes to nbytes

12: return t0

1: function int readString(char **s)

2: t ← 0

3: c ← getchar()

4: allocate 1 byte in the heap using malloc

5: let *s point to the newly allocated memory

6: let **s be the null character

7: while c is not a new line character or EOF do

8: p ←*s

9: t ← t + 1

10: allocate a character array of t + 1 bytes in the heap using malloc

11: let *s point to the newly allocated memory

12: copy the content of the character array pointed by p into ∗s

13: free p

14: set the t-th entry of the newly allocated character array to c

15: set the (t + 1)-th entry of the newly allocated character array to the null character

16: c ← getchar()

17: if c is EOF then

18: return 0

19: return 1

10