CSci **1: Introduction to Operating Systems
Spring 2024
Project #2: Enhanced Autograder
Instructor: Jon Weissman
Due: 3/20 Midnight
Intermediate Due: 3/15 Midnight
1. Objective
In this project you will extend/enhance your autograder is a number of ways. You will use 1) pipes
(pipe) to communicate information between the autograder and its children (executables), 2) use I/O
redirection (dup2) and random I/O (*seek), 3) use message-passing queues to implement a different
style of execution (msgget, msgsnd, msgrcv, and msgctl), and use alarms to implement true timeouts to detect infinite/blocked cases (alarm, sigaction, setitimer, and sigfillset). You will
also find several string functions handy (sprintf, strchr, strrchr, strlen), as well as
several I/O functions (unlink, getline, fgets, fseek). Read up on all of these system calls.
To simplify matters, we will remove the ‘slow’ event, so only correct, incorrect, crashed, infinite, or
blocked are detected. You will also determine the value of B (batch size) at runtime by setting it to the
CPU count, which you can use /proc/cpuinfo to obtain. Specifically, count the number of times
processor occurs in the file (implement your code for this in the get_batch_size() function in src/
utils.c). This means that the new autograder will not take B as a command-line argument. Instead, it 1
will take in the directory containing the executables to be graded as the 1st argument. The new usage
will look like the following: “./autograder <testdir> <p1> <p2> … <pn>”.
We have provided quite a bit of useful code in utils.h/utils.c that you can use (or ignore). Either way,
there are a few functions that you must fill in within utils.c.
Constraint 1: please try to run your tests on a lightly-loaded machine if possible (type uptime at
the shell to get the CPU load; if it is high, wait or pick another machine).
Constraint 2: you must cleanup any infinite/blocked processes, both within your program
automatically, but also outside your program at the shell in the event of errors. You can use “ps -u
<your_x500>” and “pkill -9 <exe_name>” to kill lingering processes. The pkill function actually
allows pattern matching, so you might find the following command useful: pkill -9 “sol_*”.
Some source code, object code, and test cases will be provided as needed in a downloadable tar file
from Canvas. You may use your own P1 solution as a starting point or our solution.
2. Changing the way information is passed
You will make several changes to your autograder solution. In P2, you will not only modify the
autograder but the template code as well.
Change 1: the current template returned the answer using a return statement. The answer was
limited to 8 bits or 0 .. 255 due to system call restrictions. This could be limiting in a “real” autograder
where the actual answer may far exceed 8 bit values that would be returned. To fix this, you will modify
the template to output its answer to STDOUT. You will also modify the autograder to redirect the
child’s STDOUT to a file named output/<executable_name>.<parameter> (e.g. output/sol.4). To
do this you will use dup2 in the autograder. Be careful to open the file with write access, and call
dup2 in the child only. Once the autograder gets an answer from each child by reading the output file
(or determines an issue with the child), it should remove the output files in the batch using: int
unlink(const char *pathname), e.g. unlink (“output/sol.4”).
You can double check that your get_batch_size() function is working properly by comparing it to “grep processor /proc/cpuinfo | wc -l” 1
2
If you have bugs you may need to remove the output files at the shell.
We strongly recommended that an output file gets generated for each (executable,
parameter) pair in the autograder, EVEN if the event is crashed, infinite, or blocked, for
consistency. But this is up to you. The output contents will be defined for you in the
provided code.
See that Change 1 works before moving to Change 2!
Change 2: the current autograder passed a test parameter within the exec interface. You are to
create three “versions” of the template (and the corresponding) autograder. All three change the input
location only.
(i) pass each input parameter using exec as before (no new changes over Change 1 in this case.)
(ii) have the template read its parameter via STDIN; to do this you will redirect STDIN to a file via dup2
in the autograder similar to Change 1. Be careful to call dup2 in the child only. The file(s) you will
use are first created by the autograder: input/<parameter>.in for each parameter (e.g. input/
4.in, input/7.in, etc.) . The simplest way is to create the files using the autograder command-line
argv[]. You must also open the input file(s) for read access in the child before dup2.
Remove the input files when you are done using unlink. If you have bugs you may need to
remove the input files at the shell (make clean will also clear these files)
(iii) pass the input parameter using a pipe between the autograder and each child.
For all three versions, use the output mechanism of Change 1.
Create all three versions in the same source files (as real C systems programmers would do). Use #ifdef
<version>, #elif <version2, …> #endif in both template.c and autograder.c to select the <version>-
specific code. You may need to do this in several places. Please use EXEC, REDIR, and PIPE, as the version
names. (e.g. #ifdef EXEC …. #endif, #elif REDIR … , #elif PIPE … #endif).
To compile a specific version of the template and/or the autograder: you can run “make <exec|redir|pipe>”. These
targets use the -D flag to specify the version (EXEC, REDIR, or PIPE).
3. A better way for time detection using Alarms
Change 3: Now detect a child process running too long by a timeout. To do this, modify autograder.c
(only) to create an alarm handler via sigaction and start the timer using setitimer (set it to expire
after TIMEOUT_SECS seconds).Remove the older code that detected running too long. When the timer
goes off, children that are still running are classified as either infinite/blocked and so you should kill
them using int kill(pid_t pid, int sig). Remember to still wait for each process. However,
since each process will eventually end, there is now no need to pass WNOHANG to waitpid. So, remove it.
Instead, you will use the information from WEXITSTATUS(status) and WTERMSIG(status) to
determine the results for each child process. One issue that might arise is that the alarm might interrupt
the call to waitpid. In that case, you should retry the call to waitpid. Hint: use the value of errno
EINTR to determine if waitpid was interrupted. You will create separate versions of the
autograder, mq_autograder.c, and the template, template_mq.c in this part.
4. Recast the autograder paradigm using message queues
Change 4: You will implement one more style of passing information, Linux message queues. The
method in which you distribute work will follow the master-worker model. To do this, your autograder
will write a set of “tasks” of the form [tag executable parameter] to a message queue, where tag
corresponds to a specific worker process. First, the autograder will launch all B workers and send a
message to the worker indicating how many messages it will receive so that it can initialize data
structures for storing the information. Then, the autograder should generate and insert all tasks into the
message queue. The workers will read all of the messages intended for them and send an
acknowledgement message to the autograder process. After the autograder process has received
acknowledgements from each worker, it will send a message to each worker to tell them to begin testing
3
executables. At that point, all workers will begin running their (executable, parameter) pairs in batches of
8, sending results to the autograder process after each batch, until all pairs have been tested. The process
of determining the results of each executable should be the same as in src/autograder.c. Remember to
have each child process in the worker create an output file, output/sol.4, output/sol.7, etc., for
each (executable, parameter) pair and redirect output to these files. Don’t forget to remove the
message queue when you are done.
For all versions, the final step is to create a single output file named results.txt. We have
provided a function that does just that: write_results_to_file in src/utils.c.
5. How did the student do on the submission?
The final “ask” is that you implement a function called double get_score(char
*results_file, char *executable_name) that uses random I/O to return the score for a given
executable_name (student) in results.txt. The score for a given executable is the number of
parameters that result in “correct” divided by the total number of parameters tested. You must use
random I/O (*seek) to make this efficient. See the description of this function in include/utils.h for
more information and constraints.
6. Testing
For testing, observe the targets in the Makefile. There are options to compile autograder.c/template.c
for EXEC, REDIR, and PIPE, which correspond to make exec, make redir, and make pipe. The
method for making the test executables is similar to P1. A common workflow might look like the
following:
$ make exec N=20 # Recall that N sets the number of compiled template.c files
$ ./autograder solutions 1 3 5
$ make clean # This cleans up the input/output/solutions directories
For testing Change 4 (Message Queues), a common workflow might look like the following:
$ make mqueue N=20 # mq_autograder will now use the sol_X files instead of mq_sol_X
$ ./mq_autograder solutions 1 3 5
$ make clean
We will try to release more test cases as the assignment deadline approaches, but for now there is a
single test case in the Makefile, namely the target “test1_exec”. The expected output for this test
case for results.txt and scores.txt is located in the expected/ folder. It uses the EXEC mode, but the
results should be the same whether you are using EXEC, REDIR, or PIPE.
$ make test1_exec N=20
7. Intermediate Submission
In one week you will submit a version of your code that implements get_batch_size(), Change 1, and Change 2 -
(i) and (ii) only.
8. Implementation Notes
• Remember to error check all system calls
• Remember to close all open files and pipes
• Remember that all template binaries must be executable (chmod -R +x test/)
9. Deliverables
4
There will be 2 submissions, one intermediate submission due 1 week after the release of the project
and a final submission due 2 weeks after the release.
Intermediate Submission :
Both intermediate and final submissions should contain the following. Please conform with the folder structure
that is provided to you. Your conformance will be graded.
One student from each group should upload a zip file containing the project folders/files detailed
above to Gradescope. When submitting, make sure to add your group members to your submission on
Gradescope. Your README.md file should contain the following information. Please avoid including
hidden files and junk files in your submission. It makes grading harder. Thank you :)
• How to compile the program
• Any assumptions outside this document
• Team id, team member names and x500’s
• Contribution by each member of the team for final submission only
10. Rubric: Subject to change
• 10% README including answers to questions posed in the writeup.
• 15% Intermediate submission [Including README].
• 10% Documentation within code, coding, and style: indentations, readability of code, use of
defined constants rather than numbers. The code should be well commented (need not explain
every line). You might want to focus on the “why” part, rather than the “how”, when you add
comments.
• 65% Test cases: correctness, error handling, meeting the specifications.
You must error check ALL system calls in your autograder.
• A test folder of executables, input parameters to test, a “solution” and the templates will be
provided.
• We will use the GCC version installed on the CSELabs machines to compile your code. Make sure
your code compiles and run on CSELabs.
• Please make sure that your program works on the CSELabs machines e.g., KH 4-250 (cselkh4250-xx.cselabs.umn.edu). You will be graded on one of these machines.
Project Structure Contents
include/ .h header files (utils.h)
lib/ .o library files (utils.o)
src/ .c source files (autograder.c, template.c, mq_autograder.c,
mq_template.c, utils.c)
input/ Contains the <param>.in files during runtime
output/ Contains the <exe>.<param> files during runtime
solutions/ Contains the student executables (sol_X or mq_sol_X)
expected Contains results.txt and scores.txt for specific test cases
Makefile Contains build information used for compiling/testing code
README.md Contains info outlined below
5
11. Miscellaneous
• We will provide an initial package of code, but you will be doing most of the coding.
• To run your program, type autograder <testdir> <p1>< p2> …
• Do not use the system call “system”.
• Said before: KILL all of your stray processes during debugging as needed.
• Any provided binaries are meant for the CSELAB Linux environment. No other binaries will be
distributed.
• ChatGPT or other significant “other” code reuse prohibited. The purpose of this course is to learn by doing,
and not meeting some deadline. If you are unsure about any located online code, contact us.
• On the other hand, locating code snippets that show how system calls can be used is fine.
12. SuggestedWorkplan (preliminary in blue).
• Read the writeup: in parallel look at the code we have given you.
• Implement get_batch_size() to get B at runtime
• Change 1
o output file redirection
• Change 2
o Ensure that version <EXEC> runs as before
o Get (ii) working
▪ write all inputs to input files
o Get (iii) working
• Change 3
o Convert time checking to alarm timers for long-running processes
o Think about what should go in the signal handler and how you are going to
ensure infinite/stuck processes are killed.
• Change 4
o Implement mq_autograder.c and mq_template.c using the knowledge you’ve
picked up from implementing autograder.c
o Think of the message queue as another input method (EXEC, REDIR, PIPE,
MQUEUE). However you don’t need to use any # macros for it.
• Implement get_score() program
請加QQ：99515681 郵箱：99515681@qq.com WX：codehelp
