Drupal - How to get rid of Deadlocks and Lock time out type issues?

Read and follow this post; it assumes InnoDB.

In particular, see the part saying to add the following to the settings.php file.

$databases['default']['default']['init_commands'] = array('isolation' => "SET SESSION tx_isolation='READ-COMMITTED'");

The best way to get rid of deadlock errors once and for all is the Asynchronous Prefetch Database Query Cache module.

I can't recommend it enough. Brilliantly written and great performance gains.