CMSC216, Summer 2020, Final Exam
Deadline: Today, Friday, August 7, 5:00 pm (AFTERNOON)
INSTRUCTIONS
• Copy to your ~/216 directory the directory final_exam_summer2020 you will find in exams directory of the grace public account.
• Immediately after copying the directory verify you can submit (check the submit server submission). We will not accept projects
submitted via e-mail.
• Grading: Total pts: 200 pts, 150 pts for release tests, 50 pts for secret tests / style and requirements.
• Your release/secret tests scores may be adjusted after visual inspection of your code has taken place. This process is to ensure
problems’ requirements were met.
• There are no public tests.
• Student tests that you provide will not be graded.
• Everyone must submit a version of the work around 3:00 pm, or earlier, so a copy of your work is in the submit server.
• There is no late period for this assignment. Some students wait until the last minute and then submit one minute after the
deadline and want us to accept their work. To avoid this situation, we will follow this approach: if you wait until the last minute to submit, and your submission is at least one minute late, we will accept it, but with penalty of 35 pts; after 2 minutes late, you will have a 0 in the assignment.
• You have 8 release tokens and you can release-test your project anytime.
• You can only post clarification questions in Piazza. Usually debugging questions are invalid questions to post in Piazza. You can
post questions about compilation problems. Use the Piazza folder final to post your questions; an index of clarifications will
appear in the first message associated with the final piazza folder; check this message often.
• Posting of any kind of code in Piazza, during this assignment period, represents an academic integrity violation and will be
reported as such.
• You may not address questions other students post in Piazza (only TAs and instructors can address questions).
• You must work by yourself.
• You can use class resources (lecture notes, lecture/lab examples, your projects, videos, etc.), but no other resources (e.g., code from
the web).
• Sharing of this assignment solutions (even after the exam) represents an academic integrity violation and will be reported as such.
• Submissions will be checked with cheating detection software.
• If you are an ADS student: The provided time period takes into consideration your time allocation. If you need any other
assistance, contact your instructor. Ignore this entry if you don’t know what an ADS student is.
Specifications
1. In the directory final_exam_summer2020 you will find the following files:
• makefile – Allows you to build several executables. To be on the safe side, execute make clean often.
• multiple_choice.c – Represents multiple choice questions.
• linked_list.c – Where you will implement the linked list code.
• get_sum.c – A program we have provided you, whose executable (get_sum) is used by the process executable (described
next). Do not modify this program.
• process.c – A program dealing with processes that you need to finish implementing (partial implementation provided). The
executable for this program will be generated by executing make process what will generate an executable named process.
The process executable relies on the get_sum executable.
• linked_list_driver.c – Sample driver that illustrates some of the functionality of the linked list code.
• linked_list_driver.output – Expected output for linked_list_driver.c.
• linked_list.h multiple_choice.h – Header files for corresponding .c files. Do not modify these .h files.
• Assembly support files
o pins_arduino.h, serial.c, serial.h (don’t modify)
o process_values_reference.c – Represents the code you need to implement in assembly. o process_values_driver.c – Sample driver.
o process_values.S – Where you will provide your assembly code.
2. Below we provide additional details about the implementation you need to provide.
3. For this assignment you do not need to write student tests, but you are encouraged to do so. You will not receive credit for
student tests you submit.
4. You can create additional files in the final_exam_summer2020 directory.
5. You can use code from provided driver files to develop your own tests.
6. You can add additional auxiliary/support functions; the prototypes for these functions should be specified at the top of the
corresponding .c file (do not modify .h files).
7. Style requirements: good variable names and good indentation. You should always avoid code duplication, but we will
allow it unless a problem specifically asks you to avoid it. You don’t need to add comments to your code (that includes assembly code).
MULTIPLE CHOICE
In the file multiple_choice.c file you will find functions representing multiple choice questions. Add a return statement that returns the character (IN LOWERCASE) that represents your answer. If you return an UPPERCASE character you will not get any credit. The first release test has 0 points and it verifies you have provided an answer (replace ‘N’ with your answer) for each multiple choice question, but not that your answers are correct; the correctness of your answers will be verified by secret tests. There is no make target to build an executable for multiple_choice.c. Each multiple choice question is worth 2 pts (total of 30 pts).
BUS APPLICATION
The structures you will find in linked_list.h support a linked list of Passenger structures. A Bus structure keeps track of the list head (passengers field). A description of each structure is provided below. Implement your code in the linked_list.c file.
#define MAX_LEN 80
typedef struct address {
char *street;
int zip_code;
} Address;
typedef struct passenger {
char *name;
Address *address;
struct passenger *next;
} Passenger;
typedef struct {
int number;
Passenger *passengers;
} Bus;
1. Addressstructure-Representsapassenger’saddress.Anaddresshasastreetfield(string,dynamically-allocated)anda zip_code field (integer).
2. Passenger structure – Represents a passenger. A Passenger has the following fields:
a. name – Points to dynamically-allocated memory that represents a passenger’s name.
b. address – Points to a dynamically-allocated Address structure.
c. next – Represents the next passenger in the linked list that the Bus structure defines.
3. Bus structure – Represents a list of passengers by keeping track of a linked list of passengers using the passengers field. The number field represents the bus number (not the number of passengers).
The functions you need to implement for the bus application are described below. For this assignment you can assume all memory allocations are successful (you don’t need to check whether a malloc or calloc failed). If you use the class memory tool (my_memory_checker_216), make sure you do not add the function calls start_memory_check() and stop_memory_check() to linked_list.c; add them to your student tests. Executing make linked_list_driver will create the executable linked_list_driver associated with the provided driver (linked_list_driver.c).
1. create_passenger – The prototype of this function can be found below. The function allocates dynamic memory for a Passenger structure, for the passenger’s name, for an Address structure and for the street field. The pointer to the new Passenger structure is returned by using the out parameter result. The function initializes the structures with the provided parameter values. About this function:
a. If the result parameter is null no processing will take place and the function will return 0.
b. You can assume all parameters (except result) are valid.
c. The function returns 1 once all the structures have been created and initialized.
d. The structure next field will be initialized to NULL.
int create_passenger(const char *name, const char *street,
int zip_code, Passenger **result) {
2. print_passenger -We have provided this function; do not modify it.
void print_passenger(FILE *output, Passenger *passenger)
3. destroy_passenger -This function frees any dynamically-allocated memory associated with the passenger parameter. You can assume the passenger parameter is not NULL and that the Passenger structure has been created with the above
create_passenger function.
void destroy_passenger(Passenger *passenger)
4. create_bus -This function creates a dynamically-allocated Bus structure and initializes the number field with a copy of the parameter value, and sets the passengers field to NULL. The function returns a pointer to the newly created Bus structure. You
can assume the parameter value is valid.
Bus *create_bus(int number)
5. add_passenger -This function will add a passenger to the list in decreasing alphabetical order using the passenger’s name as the sorting criteria. Adding a passenger requires creating a Passenger structure (using the create_passenger function) and adding the new passenger to the list. If the passenger already is present in the list (if there is a passenger with the same name) no passenger addition will take place and the function will return 0; the function returns 1 when a passenger is added to the list. The function will return 0 and perform no processing if the bus, name and/or street parameters are NULL. Remember that the number field represents the bus’ number, not how many elements are in the list.
int add_passenger(Bus *bus, const char *name, const char *street, int zip_code)
6. print_bus -You must complete the partial implementation we provided. The function prints the elements of the list by calling the function print_passenger.
void print_bus(FILE *output, Bus *bus)
7. destroy_bus – Frees all the dynamically-allocated memory associated with the bus parameter (including the Bus structure that
bus points to). You can assume the parameter is not NULL.
void destroy_bus(Bus *bus)
ASSEMBLY
1. You must implement assembly (avr) code that is equivalent to the C function process_values you will find in the process_values_reference.c file. Your implementation must represent a translation of the provided code; that means your assembly code must be recursive. If you provide code that is not recursive, you will lose significant credit. TAs will inspect your code to make sure your code is recursive. Also, you code must rely on one parameter. Notice this function is not the same used for quiz #4.
2. You must provide your assembly code in the file process_values.S.
3. The provided makefile includes targets similar to the ones you are already familiar with. Those targets are:
a. make process_values_r – will compile the code using the process_values_reference.c file.
b. make process_values_r.run – will run the code using the provided reference code.
c. make process_values_r.gdb – will run gdb on the reference solution.
d. make process_values_s – will compile/assemble your assembly code (process_values.S) along with process_values_driver.c.
e. make process_values_s.run – will run the simulator on the assembly solution.
f. make process_values_s.gdb – will run gdb on the assembly solution.
4. You will get a 0 in this assignment and we may submit an academic integrity case, if you avr-gcc to generate the assembly you are expected to write.
5. You don’t need to provide any comments with your assembly.
6. You only need to implement the process_values function (you don’t need to implement any print array function).
PROCESSES
The provided process.c file has a partial implementation of a program dealing with processes. We have already created a pipe and a child (fork call). Your task it to complete the parent’s code (first part of if statement) and the child’s code (else part of the if statement). The program will read a value representing an integer value, will send that value to a child process and the child process will call the get_sum program using the value provided by the parent. The get_sum program computes the sum of values between 1 and a limit. You can check the program’s functionality by executing the program get_sum and providing a number. To create the get_sum program execute make get_sum. To create the process executable execute make process. The processing associated with the parent and child are described next. Before you continue, take a quick look at the process.c file to familiarized yourself with the macros (#define’s) you need to use.
Parent
The parent will send (using a pipe) to the child the value provided by the user. The value that is sent to the child is a string. After sending the value, the parent will wait for the child to finish. If the child finished abnormally (e.g., seg fault) the parent will print the message defined by the macro FAILED_MESSAGE and exit returning to the shell the value 1. If the program finished normally, the parent will check the exit status returned by the child. The following describes the message the parent process will print (using printf) based on the exit status value returned by the child:
1. If the returned value is 0, the parent will print the message defined by the macro SUCCESS_MESSAGE.
2. If the returned value corresponds to the value defined by the macro INVALID_VALUE_NEGATIVE, the program will print
the message defined by the macro NEGATIVE_MESSAGE.
3. If the returned value corresponds to the value defined by the macro INVALID_VALUE_TOO_BIG, the program will print the
message defined by the macro TOO_BIG_MESSAGE.
4. For any other value, the parent will print the message defined by USAGE_MESSAGE.
After printing the appropriate message, the parent will return to the shell the value 1, except for the first case (when SUCCESS_MESSAGE is printed); in this case the parent will return to the shell the value 0.
Child
The child will execute the program get_sum, using execlp. Data for the program will come from the read end of the pipe. If the execlp call fails, the child will print the message “exec error” and return the code EX_OSERR using err(). Keep in mind that the get_sum program already returns the exit status values the parent relies on.
Additional Information
1. You must only use two processes.
2. You may not modify the program get_sum.c.
3. You must close the appropriate file descriptors (even if your program works, you will lose points for not closing appropriate
resources associated with file descriptors).
4. IMPORTANT: make sure you use the get_sum program and not sum. The sum program exists in grace and does
something unrelated.
This exam brought to you by the phrase “My code works in grace, but not in the submit server”