COMP 3713 X2 [2020-2021] – Assignment 4
Due: Monday, March 1, 2021 at midnight
For directions on assignment submission, please see the Syllabus. FOLLOW THE DIRECTIONS IN THE
SYLLABUS!
[20] Question 1 (Non-Programming)
Using one or more mutexes and a condition queue (and any other necessary variables), implement a
function called barrier() that is equivalent to the OpenMP directive ‘#pragma omp barrier’ (what it does
is described below). Write your solution as pseudo-code. Use wait, signal, and broadcast operations for
conditions, and lock and unlock operations for mutexes.
Assume there are N threads. When each thread calls barrier(), it waits until all threads have called
barrier(). Once all N threads have called barrier(), all threads then continue and return from the
barrier() function.

[10] Question 2 (Non-Programming)
Two processes are currently running and are sharing memory. Process 1 opens a file, and saves the
returned file descriptor in the shared memory. Process 2 reads the file descriptor from the shared
memory and tries to read from the file using that file descriptor.
a) Why will this generally not work?
b) Identify the exceptional circumstance in which this will actually work, meaning that Process 2 would
actually read successfully from the correct file.

[35] Question 3 (Programming)
Write a monitor to implement a shared hash table. This hash table will be a mapping from keys, which
are strings of at most 120 characters, to values, which are arbitrary binary data. It will do this in shared
memory, and use a semaphore to coordinate access to the data structure, as discussed in classes on
Shared Memory and Semaphores/Mutexes.

It must implement the following interface:
void *make_hashtable(int num_elements, int max_element_size);
This will construct a hashtable in an anonymous shared memory region (which will allow it to be
shared with child processes).
This shared memory must include at least:
1. An initialized binary semaphore for protecting the data structure;
2. an integer containing the maximum element size;
3. an integer containing the number of elements;
4. an integer value that is the total size in bytes of the shared memory region; and
5. space for num_elements elements, each of which must contain a name (that may
contain up to 120 characters), a 1-byte integer representing whether the element is
free(0) or used(1), a value (which may contain up to element_size bytes), and an integer
telling the value’s current size in bytes.
Initially, all elements must be marked as free. The address of the beginning of the shared
memory must be returned, or NULL should be returned on any failure.
int hash_set(void *hashtable, char *name, void *data, int data_size);
This will set the value of an element in the hashtable.
If a used element exists with the given name, it will set the value of that element to the same as
the data_size bytes pointed to by the data argument, and set the element’s value’s current size
to data_size.
If no currently used element has the same name, then it finds the first free element, marks it as
used, and sets its name, value, and value’s current size in bytes, per the given arguments.
Returns 0 on success. On errors, returns a value specific to the source of error, as follows:
-1 if the hashtable is NULL
-2 if the name is too long or is NULL
-3 if data_size > maximum allowed element size
-4 if no space exists for the element in the hashtable
-99 if an error other than the above occurs.


int hash_delete(void *hashtable, char *name);
Finds an element with the given name in the hashtable, and marks it as free.
Returns 0 on success. On errors, returns a value specific to the source of error, as follows:
-1 if the hashtable is NULL
-2 if the name is too long or is NULL
-5 if the element was not found
-99 if an error other than the above occurs.
int hash_get(void *hashtable, char *name, void **buffer, int *size);
Finds an element with the given name in the hashtable, sets *buffer to a newly allocated piece
of memory containing the contents of the value for the element in the hashtable, and sets * size
to the size of the element’s value in bytes.
Returns 0 on success. On errors, returns a value specific to the source of error, as follows:
-1 if the hashtable is NULL
-2 if the name is too long or is NULL
-5 if the element was not found
-6 if the memory to contain a copy of the element could not be allocated
-7 if size is NULL
-99 if an error other than the above occurs.
void hash_detach(void *hashtable);
Detaches the shared hashtable from the current process’ memory.

Other requirements/notes:
• You must make sure only one process at a time can set, get, or delete elements in the hash
table.
• You may add extra elements in the hashtable if you think it’s useful.
• An element marked as free is considered to not exist. Thus, if set or get find a free element with
the same name, it is not considered to be there. Thus, in this example (assuming the
make_hashtable, hash_set, and hash_delete are all successful):
hash = make_hashtable(100, 1000);
hash_set(hash, "abc", &val, sizeof(val));
hash_delete(hash, "abc");
int result = hash_get(hash, "abc", &buffer, &buffer_size);
result should equal -5.
• Tip: You will be creating a single shared memory chunk to hold this data. On paper, you should
identify the way in which this data will be stored (order of the elements, and their expected
size). This will help you keep track of how your data is organized.
• Tip: To do this well, you will often be doing math on void pointers to determine the location of a
data element in the shared space, and then casting that pointer to a pointer of the correct type
for how you want to use the data.
• Tip: You can look at the monitor example on Acorn as a guide for doing this. You’ll use a binary
unnamed semaphore instead of a mutex for doing this.
• Tip: Every mandatory item in the data structure listed in make_hashtable has a purpose.

[35] Question 4 (Programming)
Extend your ‘memcache’ program from assignment 3 question 4. In addition to the requirements in
assignment 3, question 4, this program must also:
1. During startup, it should create a shared hashtable (that you have developed in question 3),
with space for num_elements elements, whose values may be at most element_size in size.
(Now you know the reason for those command-line parameters).
2. During the controlled shutdown, in addition to cleaning up remaining children and any other
resources, it must detach from the shared hashtable.
3. In the child processes, when handling the connection, it should: (the content that is a repeat of
assignment 3 question 4 is in brown. It’s left in for clarity):
a. Read one line of text from the client. There are three possible formats for this line:
SET
GET
DELETE
where
is a string consisting of only letters (a-z and/or A-Z) and digits (0-9),
and should be at most 120 characters (but might be larger, see below).
is an integer >= 1
b. If one of the above commands is not given, then the process should write a line
containing "ERR INVALID_COMMAND\r\n" to the client, and close the connection.
c. Otherwise, if a string is larger than 120 characters, the process should write a
line containing "ERR NAME_TOO_LONG\r\n" to the client, and close the connection.
d. Otherwise, if a string contains an invalid character, then the process should
write a line containing "ERR BAD_NAME\r\n" to the client, and close the connection.
e. Otherwise, if the is not an integer, or is not at least 1, then the process should
write a line containing "ERR INVALID_SIZE\r\n" to the client, and close the connection.
f. Otherwise, if the is greater than the element_size command-line parameter, then
the process should write a line containing "ERR INVALID_SIZE\r\n" to the client, and
close the connection
g. Otherwise, if the command was the SET command, it should read the next bytes
from the client.
i. If bytes cannot be read, then the process should write a line containing
"ERR TOO_SMALL\r\n" to the client, and close the connection.
ii. Otherwise, the process should try to set the value in the shared hashtable for
the given name and value (the first bytes after the first line of the request
read above in (g)). On success, the process should write a line containing
"OK\r\n" to the client, and close the connection. On error:
If there was not enough space to store the new element, then "ERR
NO_SPACE\r\n" should be written to the client, and the connection closed.
On any other error, "ERR OTHER\r\n" should be written to the client, and the
connection closed.
h. Otherwise, if the command was the GET command, then:
i. The process should attempt to get the value of the element from the hashtable
from the entry with the given name, and the size in bytes of the element.
ii. On success, the process should write a line containing "OK \r\n" to the
client, where is the number of bytes in the element’s value, then write
the bytes of the element’s value, and close the connection.
iii. On error:
If the element was not found, then the process should write "ERR
NOT_FOUND\r\n" to the client and close the connection.
Otherwise, the process should write "ERR OTHER\r\n" to the client and close the
connection.
i. Otherwise, if the command was the DELETE command:
i. The process should attempt to delete the element in the hashtable with the
given name.
ii. On success, the process should write a line containing "OK 1\r\n" to the client,
and close the connection.
iii. On error:
If the element was not found, then the process should write "OK 0\r\n" to the
client and close the connection.
Otherwise, the process should write "ERR OTHER\r\n" to the client and close the
connection.
j. If any other sorts of errors occur while the child process tries to do (a)-(i), it should write
a line containing "ERR OTHER\r\n" to the client, and close the connection.
Additional Requirements:
• Usual programming question requirements apply (e.g. Makefile with ‘make’ and ‘make clean’)
• No zombies allowed!
• If there are any errors in the main (parent) process before the program starts accepting
connections, it should exit and print an appropriate informative error message to stderr.
• If there are any errors in the main (parent) process after the program starts accepting
connections, it should trigger a controlled shutdown, similar to if it received a SIGINT.
Note:
• Assuming your assignment 3 question 4 works reasonably well, and you’ve done question 3
above, these modifications to memcache in this question are not long or complicated.

Bonus [3 points on term]:
As mentioned in class, message queues are used to coordinate activities amongst multiple programs.
POSIX message queues are useful for programs running within a same system, but don’t allow use by
programs running on multiple machines. For computing clusters, MPI is used. For other applications,
message queue servers (such as RabbitMQ) are used. These message queue servers are focused on
allowing communication amongst different, sometimes very different programs, often written even in
different languages.
In this bonus question, you’ll explore how to use a message queue server by installing RabbitMQ in
Ubuntu, and using it to create a pair of programs.
The first program, written in Java, will provide the user a prompt at which the user can type three types
of commands (all terminated with a newline):
1. ‘quit’. If the user enters a quit command, the program will exit.
2. ‘wipe ’. This will send a message using rabbitmq to the second program, asking it to
delete the given file.
3. ‘save ’. This will send a message using rabbitmq to the second program, asking
it to save the webpage given in to the file named .
The second program, written in Python, will watch the queue for messages.
When it receives a request for deleting a file, it will delete the file if it exists.
When it receives a request for saving a webpage to file, it will try to download the page at the given url,
and save it to the given filename.
If it receives a SIGTERM signal, it should shut down after completing its current request (or immediately
if not currently working on a request).
Installing what you need:
To install RabbitMQ (and also likely the required libraries. You may want to check the “getting started”
guide mentioned below if anything else is needed):
sudo apt-get install rabbitmq-server amqp-tools python3-amqp librabbitmq-client-java
You may also have to download and install java.
Submission:
Submit your response to this bonus question in a folder called ‘bonus’. ‘make’ should build the
java program. ‘make run_java’ should run the Java program. ‘make run_python’ should run the
python program.
Tips:
• There’s some useful tutorials for using rabbitmq in different languages at the following site:
https://www.rabbitmq.com/getstarted.html