looking for help with a multithreading simulation

[Bluuz]

I'm relatively new to C and have to write code that simulates this scenario, which is a modification of the consumer producer problem.

The topic is multithreading and avoiding deadlocks.

 

You have 3 different producers producing unique materials into a buffer.

You have "m" number craftsmen and "n" tools that take those raw materials to make goods. Each craftsman is required to be in the possession of two tools before he is allowed to craft a good. A good is identified by the components that were used to create it. (material A + material B = good AB) These goods are then deposited into an output buffer.

 

Any idea how I would go about this? Being new to a language was difficult enough, but I feel overwhealmed, having to deal with threads and processes.

 

 

[Ciccioo]

what does the program actually have to do? how should the execution be? inputs? outputs? which environment are you working in? (windows, linux, mac)

 

in any case, you should have at least a basic knowledge about threads handling, semaphores and mutexes, so you could use a quick read at something like this if you're in a UNIX environment

[MikeD]

This seems like the philosopher's dinner problem.

 

I assume the 3 producers means there are 3 threads...? Or are there "m" producers? Either way, each producer is a thread.

There is some information missing but here's what I would do:

I would have a list of materials, a list for the outputs and an array of tools.

Each tool must have a lock that represents possession by a producer.

The lists of materials and outputs would have a single lock so that there is only one thread accessing any at any given time (either removing or adding). (To simplify you could keep a pointer to the end of the list so that you don't have to iterate over every item every time.)

Allocation and creation of outputs by each thread need not be protected, only addition to the shared list. 

 

Let me know if this helps or if there is something that you did not understand.

 

EDIT: fixed spacing. If it's still weird, there is some problem with my browser, maybe?

Edited March 8, 2014 by MikeD

[BrightCandle]

The key to solving the philosophers dining problem is to take locks on the tools explicitly and hold onto them while trying to acquire other tools, if unable to get them all then replace them all back. So you can't block on the locks you need to try and acquire them all and if you can't you back off and give all the tools/locks back and go to sleep for a little while to allow others the chance to get the tools. You should always try to acquire the tools in the same order if possible.

[Bluuz]

what does the program actually have to do? how should the execution be? inputs? outputs? which environment are you working in? (windows, linux, mac)

 

in any case, you should have at least a basic knowledge about threads handling, semaphores and mutexes, so you could use a quick read at something like this if you're in a UNIX environment

I'll be working on Linux. 

The goal of the program is to simply simulate the scenario and be able to pause and count how many goods there are.

[Bluuz]

This seems like the philosopher's dinner problem.

 

I assume the 3 producers means there are 3 threads...? Or are there "m" producers? Either way, each producer is a thread.

There is some information missing but here's what I would do:

I would have a list of materials, a list for the outputs and an array of tools.

Each tool must have a lock that represents possession by a producer.

The lists of materials and outputs would have a single lock so that there is only one thread accessing any at any given time (either removing or adding). (To simplify you could keep a pointer to the end of the list so that you don't have to iterate over every item every time.)

Allocation and creation of outputs by each thread need not be protected, only addition to the shared list. 

 

Let me know if this helps or if there is something that you did not understand.

 

EDIT: fixed spacing. If it's still weird, there is some problem with my browser, maybe?

Let's say I have created three threads that insert items into a buffer. Thread 1 inserts item A, thread 2 inserts B, and thread 3 inserts C. How could I coordinate them so that the input buffer would look like CBACBACBA. In other words, how do I know or control when a thread will execute?

[MikeD]

Let's say I have created three threads that insert items into a buffer. Thread 1 inserts item A, thread 2 inserts B, and thread 3 inserts C. How could I coordinate them so that the input buffer would look like CBACBACBA. In other words, how do I know or control when a thread will execute?

HA! That was basically my third Operating Systems graded group homework (except we wanted to increment and print a counter)!

 

First of all, you can do that with just one function that is the same for all threads. Each thread can have an identifier and some other information like which item does it insert.

Then, you have to choose a synchronization mechanism to control the access to the code that is actually going to do something. We had semaphores in that particular one.

Finally you need to check if it is your turn to do something and, if it is, do it.

 

Now, the software engineer's job comes in figuring out how to order these last steps without causing deadlocks, starvation or any other undesirable behavior.

[Bluuz]

HA! That was basically my third Operating Systems graded group homework (except we wanted to increment and print a counter)!

 

First of all, you can do that with just one function that is the same for all threads. Each thread can have an identifier and some other information like which item does it insert.

Then, you have to choose a synchronization mechanism to control the access to the code that is actually going to do something. We had semaphores in that particular one.

Finally you need to check if it is your turn to do something and, if it is, do it.

 

Now, the software engineer's job comes in figuring out how to order these last steps without causing deadlocks, starvation or any other undesirable behavior.

Assignments tend to be recycled. I have another requirement is that I have to be able to dynamically pause the simulation (print the status of the buffers and list how many of each good has been made) and be able to start it up again. If I had to guess, I'd need a separate thread to handle user input that will block other threads when it detects the user has typed something on the keyboard. Is that correct?

[MikeD]

Assignments tend to be recycled. I have another requirement is that I have to be able to dynamically pause the simulation (print the status of the buffers and list how many of each good has been made) and be able to start it up again. If I had to guess, I'd need a separate thread to handle user input that will block other threads when it detects the user has typed something on the keyboard. Is that correct?

 

Yes, that will work. But , again, be careful with the locks. You don't want to be in the middle of adding something to the list and then interrupt everything and traverse it.

[Bluuz]

This seems like the philosopher's dinner problem.

 

I assume the 3 producers means there are 3 threads...? Or are there "m" producers? Either way, each producer is a thread.

There is some information missing but here's what I would do:

I would have a list of materials, a list for the outputs and an array of tools.

Each tool must have a lock that represents possession by a producer.

The lists of materials and outputs would have a single lock so that there is only one thread accessing any at any given time (either removing or adding). (To simplify you could keep a pointer to the end of the list so that you don't have to iterate over every item every time.)

Allocation and creation of outputs by each thread need not be protected, only addition to the shared list. 

 

Let me know if this helps or if there is something that you did not understand.

 

EDIT: fixed spacing. If it's still weird, there is some problem with my browser, maybe?

 

The key to solving the philosophers dining problem is to take locks on the tools explicitly and hold onto them while trying to acquire other tools, if unable to get them all then replace them all back. So you can't block on the locks you need to try and acquire them all and if you can't you back off and give all the tools/locks back and go to sleep for a little while to allow others the chance to get the tools. You should always try to acquire the tools in the same order if possible.

How would I make the threads prioritize one tool over another? 

Also, the wikipedia page http://en.wikipedia.org/wiki/Dining_philosophers_problem%C2'> 4 different solutions to the problem. However, my scenario does not involve the "Philosophers" being restricted to only picking up forks that are adjacent to themselves, they have access to every fork on the table. Would that open up the possibilities for more ways to solve the problem?

[Ciccioo]

if you have n tools, i can think of two ways: the first one involves n semaphores, the second one just one

in both cases, you create a aquireTool(craftsman, tool) function which is locked by a mutex during its whole execution

first way:

store the tools in an array of n elements, also store an array of n booleans which determine the availability of the related tool. when you aquire it or relase it, you keep the semaphore up to date

second way:

you store the tools in a list. when a craftsman wants to aquire a tool, you remove the tool from the list and add that node to the craftman's tools list. the only "semaphore" here is the mutex that controls the access to the function

if a tool is already aquired, the other craftsmen won't be able to aquire it because it's not in the tools list anymore

this second method is a bit slower and a little less obvious, but it also stores the state of every craftsman (which tools he aquired) so it might come handy if the system gets a bit more complex

[MikeD]

in both cases, you create a aquireTool(craftsman, tool) function which is locked by a mutex during its whole execution

store the tools in an array of n elements, also store an array of n booleans which determine the availability of the related tool.

 

 

 

 

This is a more "critical section" oriented solution, but since you have many tools I would opt for a data oriented synchronization scheme.

If you use a lock to control access to that function you restrict potential parallelism since every thread has to wait their turn even if they end up picking different tools.

Also, when I think about tools, craftsmen or even threads I think about objects (structs in C) that can hold individual locks and other information for each entity, making storing and sharing information easier than having multiple separate structures. Just a thought, though. And I agree that the solution with the array is better than with lists since with a list you could only have one lock and with an array you can have a semaphore for each tool (object).