Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSCI 4210 — Operating Systems
Homework 3
Multi-threading in C using Pthreads
Overview
• This homework is due by 11:59:59 PM on Wednesday, March 27, 2024.
• This homework is to be completed individually. Do not share your code with anyone else.
• You must use C for this homework assignment, and your code must successfully compile
via gcc with absolutely no warning messages when the -Wall (i.e., warn all) compiler option
is used. We will also use -Werror, which will treat all warnings as critical errors.
• Your code must successfully compile and run on Submitty.
• You must use the Pthread library. Remember, to compile your code, use -pthread to link
the Pthread library.
Homework specifications
In this third assignment, you will use C and the POSIX thread (Pthread) library to implement a
single-process multi-threaded system that solves the knight’s tour problem, i.e., can a knight move
over all squares exactly once on a given board? Sonny plays the knight in our assignment.
In brief, your program must determine whether a valid solution is possible for the knight’s tour
problem on an m × n board. To accomplish this, your program simulates valid moves. And for
each board configuration you encounter, when multiple moves are detected, each possible move is
allocated to a new child thread, thereby forming a tree of possible moves.
You must keep track of a global variable called max_squares that maintains the maximum number
of squares covered by Sonny; when a dead end is encountered in a thread, that thread checks the
max_squares variable, updating it if a new maximum is found.
Further, a global shared array called dead_end_boards is used to maintain a list of “dead end”
board configurations. Child threads add their detected “dead end” boards to the end of this array,
which therefore requires proper synchronization.
Note that a “dead end” does not include a fully covered board, i.e., a full knight’s tour.
A valid move constitutes relocating Sonny the knight two squares in direction D and then one
square 90° from D, where D is up, down, right, or left. Key to this problem is the restriction that
Sonny may not land on a square more than once in its tour. Also note that Sonny starts in
the upper-left corner of the board at position (0, 0).
When a dead end is encountered (i.e., no more moves can be made) or a fully covered board is
achieved, the leaf node thread compares the number of squares covered to the global maximum,
updating the global maximum, if necessary. Once all child threads have terminated for a given
parent thread, the parent thread reports (i.e., returns to its own parent thread) the number of
squares covered. When the top-level main thread joins all of its child threads, it displays the final
maximum result, which is equal to product m× n if a full knight’s tour is possible.
The top-level main thread also displays either all of the “dead end” boards or all “dead end” boards
with at least x squares covered, where x is an optional (third) command-line argument.
Command-line arguments and error handling
There are two required command-line arguments; both are integers n andm, which together specify
that the size of the board is m×n, where m is the number of rows and n is the number of columns
in the board.
As noted above, a third optional command-line argument, x, indicates that the main thread should
display all “dead end” boards with at least x squares covered.
Validate the inputsm and n to be sure both are integers greater than 2. Further, if present, validate
input x to be sure it is a positive integer no greater than m × n. If invalid, display the following
error message to stderr:
ERROR: Invalid argument(s)
USAGE: a.out []
In general, if a system call fails, use perror() to display the appropriate error message on stderr,
then exit the program and return EXIT_FAILURE. If a system or library call does not set the
global errno, use fprintf() instead of perror() to write an error message to stderr. See the
various examples on the course website and corresponding man pages.
Note that error messages must be one line only and use the following format:
ERROR:
2
Dynamic memory allocation
As with the previous two homework assignments, your program must use calloc() to dynamically
allocate memory for the m × n board. More specifically, use calloc() to allocate an array of m
pointers, then for each of these pointers, use calloc() to allocate an array of size n. Of course,
your program must also use free() and have no memory leaks. Note that you do not need to use
realloc() for the individual m × n boards, but you definitely need to use realloc() to expand
the global dead_end_boards array, as necessary.
Given that your solution is multi-threaded, you will need to be careful in how you manage your
child threads and the board; i.e., you will need to allocate (and free) memory for each child thread
that you create.