Classic Concurrency Problems

by | Mar 15, 2017 | Research, Topics in IT


Concurrency in computer systems is a tricky subject. From deadlocks, to race conditions, making sure that your data is in a valid state gets harder the more you focus on having a concurrent system. These problems below show some of these concurrency issues and then shows you the working solution, going around these issues

Cigarette smoker’s problem

The main rules of the Cigarette smoker’s problem are:

  • Three chain smokers have one of three ingredients
  • Assume that this supply is infinite
  • A non-smoking arbiter informs two of the three smokers to give their resources
  • The third Smoker will take these ingredients and then smoke
  • After the Smoker has had a smoke, they will tell the arbiter that the table is empty
  • The arbiter again sees that the table is empty tells two random smokers to provide their ingredients
  • This continues forever.

The main problem with a normal solution is deadlock; a thread can pick up one item that it needs but doesn’t get the chance to pick up the other item due to one of the other threads picking up the item EG. Tobacco Thread Picks up paper and the Paper thread picks up the match.

The main way to solve this is problem is to have threads in between the placement of the objects and the smoker threads, this is to allow the threads to know what items are on the table and not to pick these up if they do not have the corresponding item to create a cigarette. This in essence has created more for the thread to go through to complete its purpose. But in the problem space for the deadlock is preferred than the deadlock.


Dining philosopher’s problem

The main rules for the Philosophers dinner party is as follows:

  • Five philosophers have five forks and are going to eat a meal
  • This meal requires two forks because it is slippery
  • This means that the philosophers need to share these forks
  • Philosophers will have the left fork and will have to check if the right fork is in use
  • The Philosophers However cannot reach over the table to get a fork as they are civilised and know better.
  • A philosopher will see if the forks are in use and if they are not will pick these up to eat
  • When they have finished they will put the forks back so another philosopher can eat

The main problem with the normal solution is a deadlock condition, if all of the philosophers pick up the left fork they do not let go until they have eaten. This however depends on the right fork which is being used by a philosopher as a Left fork.

The main way to solve this problem is to put a throttle on how many philosophers can pick up the Forks at a time. This can be done by introducing a semaphore to block the 5th philosopher until the first one is done. This in essence has throttled the performance and also the Liveness of the program but the alternative of the program deadlocking is preferred.


- Mark Fulton