Programming Project: Multithreaded Programming Solution

$30.00 $24.90

Description

Part A – Introduction to Parallel Programming (45 points)

The office supply superstore, StapleMax, has commissioned you to create a new inventory management program for them. There are 20 different files that contain the sales (in chronological order – one product per line) for each of 20 different salespeople. Write a multithreaded program (in the file staplemax.cpp) that deducts each item from the current inventory on the store shelves as it is sold (i.e., as you read it from the file). If the sale reduces the inventory of that item to 0, that salesperson must immediately restock that item on the self before selling any more items. Restocking should only occur for a particular item when it runs out; never restock any item if there are still some of it on the shelves.

After the store closes for the day (i.e., all the files have been read & processed fully), the inventory program should print out how many items are currently on the shelves at close, and how many total sales transactions have been made (which should be the same as the total number of lines in all files). If you have done things correctly, the following should be true of your final values:

  • No items have 0 inventory on the shelves

  • All the final values are deterministic

  1. That is, they are the same every time you run the program

    • (assuming you use the same input files)

  1. They are also the same that everyone else in the class gets

    • (assuming they also implemented theirs correctly)

  1. You may not show your code to any classmates or look at their code, but you’re welcome to compare the final values you get with your classmates to see if you get the same thing

The shelf capacities for the items are as follows. Your program should start with the shelves full, and restore an item to this value when restocking the item. You are free to hard code these values in your program if you wish.

  • pen = 100

  • paper = 200

  • toner = 40

  • laptops = 15

The files are named sales1.txt, sales2.txt, …, and sales20.txt. They are available from the directory:

/home/fac/lillethd/cpsc3500/projects/sales_data

Additional Requirements

  • The program should create 20 threads, each thread should process a different input file.

  • Your program must read the files from the directory

/home/fac/lillethd/cpsc3500/projects/sales_data

o Do not assume the input files are in the current directory. However, you may assume they are in the directory named just above and hardcode that directory.

o The directory and file names must be hard-coded into the program. Do NOT prompt the user for this information.

  • Unless an error occurs, the only output the program should produce is the final shelf inventory for each product and the total number of sales (that’s 5 different numbers in total). Do NOT print out the individual sales from each file.

o You may have debug output while you work on it, of course; this restriction only applies to the final version that you submit.

  • Your program must use appropriate data structures and loops to avoid redundant code. Code that is the same (except for one variable) line 20 times in a row (such as 20 lines that are all pthread_create calls) will be penalized.

  • Only the shelf inventory should be global variables! You must properly pass parameters into the thread function and use pthread_join to get the return value. Using a global variable for this purpose will result in a minimum 12-point penalty.

o You may also declare constants as global, though, if it’s necessary to avoid replicating the same constant in different places.

o You may, and in fact will have to declare any synchronization structs as global as well – i.e., pthread_mutex_t)

  • You must use pthreads to implement the threading. You are not permitted to use the threading features present in C++ 11.

  • A Makefile is not required for this part of the assignment. The submission program requires the code to be in the file staplemax.cpp. It will compile your file using this command:

g++ staplemax.cpp -std=c++11 -lpthread -o staplemax

Error Checking

  • If a pthread function returns an error, abort the program with an error message.

  • You must check all pthreads functions, as well as any other system calls you make, for errors and then handle any errors appropriately. Failure to check all function calls for errors will result in lost points.

  • Remember that you can use the ‘man‘ command on cs1 to learn about any system function, including how it reports errors and what the possible error conditions are.

  • Assumptions

  • Each input file will contain at least one line. Beyond this, you cannot make any assumptions on how long the input file is.

  • You may assume that each line only contains the name of one of the four products noted in the description.

  • You can ‘cat‘ one of the files, or open it in a text editor, to see an example of its structure:

cat /home/fac/lillethd/cpsc3500/projects/p3a/sales1.txt

Part B – Synchronization Programming (55 points)

In part B of this assignment, you will implement that classic problem, “Dining Philosophers” and then implement a solution to the problem.

  1. In section 1 (sections1.c) you will implement the Dining Philosophers problem. Since the point of Dining Philosophers is to demonstrate deadlock, your code for section 1 should result in a deadlock.

  1. After finishing section 1, copy your code to sections2.c and implement a solution to the Dining Philosophers problem in sections2.c – that is, make it so that deadlock is prevented, while also keeping the original program behavior.

Implementation Instructions

To assist with debugging and testing, you will be using a tool called MDAT (short for Multithreaded Debugging and Testing) designed for students who are learning to implement synchronization.

To start, copy all of the files from:

/home/fac/lillethd/cpsc3500/projects/threading

The only files you are permitted to modify are:

sections1.c: Contains sectionInitGlobals(), an initialization function that will be run once (useful for initializing any shared variables, for example), and a function that implements a philosopher. Each thread will run the sectionRunPhilosopher() function once and then terminate.

sections2.c: Identical to sections1.c except that it is used for section 2.

It is helpful to look at main.cpp to see how the different threads are set up. Towards the end

file, you will see threadStart(), the actual start _routine that is passed to

pthread_create. threadStart() then calls your sectionRunPhilosopher()

implementation. However, note that you are not allowed to modify main.cpp!

Further use of MDAT is described in the MDAT Guide.

The MDAT Guide will explain that you must implement your code in C, not C++, and describes some of the key differences. One thing it overlooks that you may want to use, however, is that instead of using new/delete to allocate/deallocate dynamic (heap) memory, you must use the malloc/free functions. As with other functions, you can run ‘man malloc‘ and ‘man free‘ to learn more about these functions. The big difference is that instead of giving the type that you’d like to allocate as you do with new, malloc simply takes the number of bytes you want to allocate as an argument. The sizeof operator (e.g., sizeof(int) gives the number of bytes used for an int) is often used in conjunction with malloc.

Section 1: Implementing Dining Philosophers

If you need to review the Dining Philosophers problem, you may review your notes from class

or read the Wikipedia article:

https://en.wikipedia.org/wiki/Dining_philosophers_problem

You need to implement the sectionsRunPhilosopher() function so that each philosopher performs some number of rounds (passed in by the second function parameter), and in each round they will first eat then think. As you see in the starter code, eating is performed by calling the eat() function and thinking is performed by calling the think() function.

You also need to implement some representation for the chopsticks. A philosopher must hold the chopstick to their left and the chopstick to their right in order to eat (i.e., before calling the eat() function). They may set the chopsticks down after eating (i.e., after the eat() function returns) – they are not required to hold any chopsticks in order to think.

(The Wikipedia article refers to “forks”, while I call them “chopsticks” – the behavior is the same either way, and you can call them whichever you want in your code, so long as you implement the correct behavior. I just don’t personally think needing two forks makes as much sense…)

If you have implemented Dining Philosophers correctly, then MDAT should report that your program deadlocks much of the time (but not necessarily every time – that is the nature of race conditions!). Running more rounds will increase the chance of deadlock, while running more threads (philosophers) will decrease the chance of deadlock – it may be interesting for you to take a moment and think about why that is.

MDAT will also detect other problematic situations. Your Dining Philosophers implementation must avoid these other error conditions – if you get a VIOLATION message and it is not reporting a deadlock, then you have a bug. Here are some of the other situations it may detect:

  • Two different philosophers who require the same chopstick are eating at the same time (implying that they are both holding the same chopstick at the same time)

  • A philosopher is starting to eat when they are already eating or the last thing they did was eating. (They should instead alternate between eating and thinking.)

  • A philosopher is starting to think without having first eaten. (This may happen if they think twice in a row, or if the first thing they do is thinking, before they

eat.) Remember, never think on an empty stomach! 😉

  • A philosopher eats more times than the specified number of rounds says they should.

  • A philosopher eats fewer times (by the end of their thread) than the specified number of rounds says they should.

Section 2: Solving Dining Philosophers

You should start by copying your sections1.c code to sections2.c – you will be implementing a solution to the deadlock in sections2.c but you want to keep the original deadlocking version in sections1.c

cp sections1.c sections2.c

Now modify your sections2.c code to solve the deadlocking problem (while preserving the rest of the original behavior). If your implementation is successful, MDAT should not report any VIOLATION messages at all.

You may have noticed that the Wikipedia article describes not only how the Dining Philosopher problem works, but also some solutions to it.

  1. You are welcome to use any correct solution. I recommend that “Resource Hierarchies” may be the easiest one to implement, but you are free to do one of the others if you prefer – as long as you get it working correctly.

  2. You are free to read textual descriptions of Dining Philosophers and its solutions on Wikipedia or anywhere else you find them. (It’s a well-known problem, so it should be easy to find.) However, you may not read any code examples – do not search for them, and do not read them if you run across them by accident. You may read text only, not code. Also, you may discuss solutions with your classmates, but may not describe specific code in detail nor show your code or look at any one else’s’ code.

Additional Requirements

  • Your implementation may only use the MDAT synchronization functions. MDAT only supports locks and semaphores and their basic operations.

  • You are not allowed to modify code outside sections1.c and sections2.c. The submission script will compile your code using the original Makefile and original copies of the provided code, ignoring modifications made outside these files.

Error Checking

No error checking is needed for this part of the assignment.

Submitting your Program

For part A, your program must reside in a single file named staplemax.cpp. For part B, the only files to be submitted are sections1.c and sections2.c. All three files must be in the same directory before submitting (none of the other files are necessary).

On cs1, run the following script in the directory with the three files listed above:

/home/fac/lillethd/cpsc3500/submit/submit_threading

This will copy the files associated with this assignment to a directory that can be accessed by the instructor. Please be sure to name the files correctly or the submission program will not work.

The submission script will attempt to compile your programs (both parts). Your programs (both parts) must properly compile or the submission program will reject your program. Programs that fail to compile will not be graded. Only the last assignment submitted before the due date and time will be graded. Late submissions are not accepted and result in a zero, unless you use sufficient free passes.

The submission script will give you a clear all-caps “SUCCESSFUL” or “FAILED” message, so there should be no ambiguity. (If you do not see either of those, please contact the instructor ASAP.)