Description
The objective of this assignment is to write and test a program which uses dynamic memory allocation. The program allocates several random sized arrays with integers. For each array it counts the integers that are divisible by a randomly chosen integer and the that which are not. It then computes the ratio of the two numners. The program keeps track of the iteration with the largest ratio and computes a running average of all ratios across iterations. You will also demonstrate that you can use the Valgrind tool to test for memory leaks. Due Date: Monday, September 06, 2021, 11:00 pm Late Due Date with 20% penalty: Tuesday, September 07, 2021, 11:00 pm This document and the README.txt file are available at Canvas (Assignments > HW1) 1. Task Description For this assignment you will be working with two C files: Initiator.c and the Worker.c. It involves dynamically allocating and deallocating random sized arrays. You will use the Valgrind tool to ensure that there are no memory leaks. Initiator: It is responsible for: 1. Setting the seed, whose value is passed as an argument, using srand(). 2. Invoking functions in the Worker. Worker: It is responsible for implementing the following: 1. Dynamically allocate and de-allocate a random sized array for each iteration. 2. Populate elements in the array with random integers. 3. For each iteration, generate a random integer to be used as a divisor. 4. For each element in the array, check if the element is divisible, and if so count it. 5. Calculate the ratio of elements divisible by divisor to elements not divisible by the divisor. —- Number of Divisible Elements /Number of Non-Divisble Elements —- 6. At the end print the iteration number with maximum number of divisible elements. 7. Return the average value of the ratio divisible/not_divisible for all iterations to Initiator Hint: you are computing the total number of divisible items over the total number of iterations All above tasks are implemented in get_running_ratio() and Initiator should call that function in the Worker file. The auxiliary methods that will be needed in the Worker are: 1. int random_in_range(int lower_bound, int upper_bound): This function takes a lower limit (inclusive) and an upper limit (exclusive) and returns a random integer value between them. 2. int get_divisibility_count(int *array, int arraySize, int randomDividend): This function takes the reference to the array, the array size and a divisor as an input. You need to iterate over the elements of the array and check if they are fully divisible by the divisor. Return the number of divisible items. Hints: 1. To generate a random number between an inclusive lower bound and an exclusive upper bound using a random number generator, you can use the following example: int random_in_range(int lower_bound, int upper_bound) { return ((rand() % (upper_bound – lower_bound)) + lower_bound); } CS 370: OPERATING SYSTEMS Fall 2021 Colorado State University 2 All print statements must indicate the program that is responsible for generating them. To do this, please prefix your print statements with the program name i.e. Initiator or Worker. The example section below depicts these sample outputs. Using Valgrind, ensure that there is no memory leak. Copy the Valgrind output indicating no leaks to README file. Then insert a memory leak by commenting out the code responsible for deallocation while ensuring that the program still functions as specified and copy the Valgrind output to README file. Modify the program again so that it does not have a memory leak before submitting it by commenting the memory leak and placing a comment about it stating the below commented code is a memory leak. 2. Task Requirements 1. The Initiator accepts one command line argument. This is the seed for the random number generator. In the Initiator file, the seed should be set for the random number generator based on the command line argument that is provided. The string/char* value received from the command line argument should be converted to integer using atoi() before being used to set the seed using srand() and it should be printed. The Initiator program should invoke the Worker. 2. The Worker initializes maxDivisibleElements and maxCountIteration in get_running_ratio() to 0. These are used to track the maximum number of elements in an array fully divisible by the divisor and the iteration number that the array belongs to. The Worker then uses the random number generator to compute the number of times that it must allocate and de-allocate arrays. The number of iterations should be between 50 (inclusive) and 100 (exclusive, i.e. not including 100). The auxiliary method random_in_range(int lower_bound, int upper_bound) is called for the range specified above. “Random” number generators and seeds The random number generators used in software are actually pseudorandom. The generator is initialized with a “seed” value, then a mathematical formula generates a sequence of pseudorandom numbers. If you re-use the same “seed”, you get that same sequence of numbers again. Other uses of seeding the random number generator Seeding the random number generator is useful for debugging in discrete event simulations particularly stochastic ones. When a beta tester observes a problem in the program, you can re-create exactly the same simulation they were running. It can also be used to create a repeatable “random” run for timing purposes. We will be using different “seeds” to verify the correctness of your implementation. srand(seed); printf(“[InitiatorInitiator]: With seed: %d\n”, seed); float running_ratio = get_running_ratio(); CS 370: OPERATING SYSTEMS Fall 2021 Colorado State University 3 Steps 3 through 7 (enumerated below) are repeated in a loop and the number of times the loop is executed is dependent on the number of iterations that was returned. Print the total number of iterations. 3. In Worker use the random number generator to compute the size of the array between 100 (inclusive) and 150 (exclusive). Use the auxiliary method random_in_range(int lower_bound, int upper_bound. The Worker should allocate the memory in the heap; failure to do so will result in a 75-point deduction. 4. After allocating the array, use the random number generator to populate it with elemnets between 1 (inclusive) and 99 (inclusive) . Again, the auxiliary method random_in_range(int lower_bound, int upper_bound). This auxiliary method is called once for each element. Note the bounds to obtain the random integer are both inclusive. Think about how to use the random_in_range() function to include 99 and not excluded it! 5. The Worker randomly generates a divisor between the range 5 (inclusive) and 15 (exclusive) using the auxiliary method random_in_range(int lower_bound, int upper_bound). Further, the Worker calls get_divisibility_count(int *array, int arraySize, int randomDividend) , by passing it the array, size of the array and the generated divisor. The auxiliary function returns the number of elements fully divisible by the divisor. 6. Once the control returns to get_running_ratio(), we calculate the ratio of the number of elements fully divisible by the divisor to the number of elements not fully divisible by the element. Maintain a running sum of the ratios the final average. 7. Further, the Worker checks if the returned number of divisible elements is greater than the previously stored maximum count (maxDivisibleElements). If it is true, we update the values maxDivisibleElements and maxCountIteration accordingly. 8. Once loop variable has reached its limit, you exit from the loop. In Worker print the iteration number with the largest ratio of divisible/non divisible 9. Return the average value of the ratio divisible/not_divisible for all iterations to Initiator 10. In Initiator print the average ratio. Check your values using provided sample output. Allocating on the heap versus the stack An array is created in the heap by explicitly allocating memory using malloc or similar functions. On the other hand, allocating an array in the stack can be done as follows: int arr[num_of_elem]; If memory is allocated on the heap, it should be released explicitly (e.g. using ‘free’) whereas memory is automatically released for stack variables when they go out of scope – hence the penalty Testing for randomness There exist a number of rigorous tests for randomness for sequences generated by pseudorandom generators. The test here is a rather simple one. printf(“[Worker]: Number of iterations is: %d\n”, totalIterations); _ratio(); CS 370: OPERATING SYSTEMS Fall 2021 Colorado State University 4 3. Files Provided Files provided for this assignment include the description file (this file), a README file. This can be downloaded as a package from the course web site. Please refer to the README.txt file inside the package on how to compile and run the program. You are needed to answer the questions in the README file. 4. Example Outputs: 1. [Initiator]: With seed: 7 [Worker]: Number of iterations is: 77 [Worker]: Iteration with maximum fully divisible elements is 59 [Initiator]: Running ratio: 0.122461 2. [Initiator]: With seed: 23 [Worker]: Number of iterations is: 52 [Worker]: Iteration with maximum fully divisible elements is 46 [Initiator]: Running ratio: 0.134306 Sample Valgrind output: 1. No leaks (with seed 7) ==555803== ==555803== HEAP SUMMARY: ==555803== in use at exit: 0 bytes in 0 blocks ==555803== total heap usage: 78 allocs, 78 frees, 38,872 bytes allocated ==555803== ==555803== All heap blocks were freed — no leaks are possible ==555803== ==555803== For lists of detected and suppressed errors, rerun with: -s ==555803== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 2. With leaks (with seed 7) ==555868== HEAP SUMMARY: ==555868== in use at exit: 37,848 bytes in 77 blocks ==555868== total heap usage: 78 allocs, 1 frees, 38,872 bytes allocated ==555868== ==555868== LEAK SUMMARY: ==555868== definitely lost: 37,848 bytes in 77 blocks ==555868== indirectly lost: 0 bytes in 0 blocks ==555868== possibly lost: 0 bytes in 0 blocks ==555868== still reachable: 0 bytes in 0 blocks ==555868== suppressed: 0 bytes in 0 blocks ==555868== Rerun with –leak-check=full to see details of leaked memory ==555868== ==555868== For lists of detected and suppressed errors, rerun with: -s ==555868== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) CS 370: OPERATING SYSTEMS Fall 2021 Colorado State University 5 5. What to Submit Use the CS370 Canvas to submit a single .zip or .tar file that contains: • All .c and .h files listed below and descriptive comments within, o Initiator.c o Worker.c o Worker.h – This header files declares the methods exposed from Worker.c, so that they can be invoked from the Initiator program • a Makefile that performs both a make build as well as a make clean, • a README.txt file containing a description of each file and any information you feel the grader needs to grade your program, and o Valgrind outputs showing both no memory leaks and a memory leak o Answers for the 5 questions For this and all other assignments, ensure that you have submitted a valid .zip/.tar file. After submitting your file, you can download it and examine to make sure it is indeed a valid zip/tar file, by trying to extract it. Filename Convention: The archive file must be named as: — HW1.<tar/zip>. E.g. if you are John Doe and submitting for assignment 1, then the tar file should be named John-Doe-HW1.tar 6. Grading The assignments much compile and function correctly on machines in the CSB-120 Lab. Assignments that work on your laptop on your particular flavor of Linux/Mac OS X, but not on the Lab machines are considered unacceptable. The grading will also be done on a 100 point scale. The points are broken up as follows: Objective Points Correctly performing Tasks 1-10 (8 points each) 80 points Descriptive comments 5 points Correctly injecting and then fixing the memory leak, and providing copies of Valgrind outputs showing both no memory leaks and a memory leak was detected 5 points Questions in the README file 5 points Providing a working Makefile 5 points Questions: (To be answered in README file. Each question worth 1 point) 1. What is the main difference between Malloc() and Calloc()? 2. When dynamically allocating an integer array, Malloc takes the number of elements as the input? – True/False 3. What happens if memory is not properly freed after using dynamic memory allocation? 4. What is the purpose of the headerfile Worker.h and Why is Initiator.h not necessary? 5. Describe the * and & opperators in the context of pointers and refferences? Deductions: There is a 75-point deduction (i.e. you will have a 25 on the assignment) if you: (1) Allocate the array on the stack instead of the heap. (2) Have memory leak or a segmentation error which cannot be plugged by commenting the memory leak code provided, which is identified by placing a comment just above it. You are required to work alone on this assignment. 7. Late Policy Click here for the class policy on submitting late assignments. CS 370: OPERATING SYSTEMS Fall 2021 Colorado State University 6 Revisions: Any revisions in the assignment will be noted below. Aug 28: Due Date should be Sept 6.
