Deadlock is a condition in which two (or more) processes are each waiting for a resource that is controlled by another, causing a situation where no process will ever be able to run. This can happen when a viable locking scheme is not used and there is no mediation policy (or when a programmer has a major goof).
Livelock is described as processes that constantly change state in relation to one another in such a way that no progression occurs.
TAKEN VERBATIM FROM WIKIPEDIA.ORG (because they explain it so well)
http://en.wikipedia.org/wiki/Dining_philosophers_problem
"In 1971, Edsger Dijkstra set an examination question on a synchronization problem where five computers competed for access to five shared tape drive peripherals. Soon afterwards the problem was retold by Tony Hoare as the dining philosopher's problem.
Five philosophers spend their time eating and thinking. The college where they live has a dining table with a large bowl of spaghetti in the center of the table. There are five plates at the table and five forks set between the plates.
Eating the spaghetti requires the use of two forks (often, the problem is explained with chopsticks instead of forks, because it is easier to understand requiring two chopsticks to eat spaghetti than two forks) which the philosophers pick up one at a time. The philosophers never speak to each other which creates a dangerous possibility of deadlock in which every philosopher holds a left fork and waits perpetually for a right fork (or vice versa).
Originally used as a means of illustrating the problem of deadlock, this system reaches deadlock when there is a 'cycle of ungranted requests'. In this case philosopher P1 waits for the fork grabbed by philosopher P2 who is waiting for the fork of philosopher P3 and so forth, making a circular chain.
Starvation (and the pun was intended in the original problem description) might also occur independently of deadlock if a philosopher is unable to acquire both forks due to a timing issue. For example there might be a rule that the philosophers put down a fork after waiting five minutes for the other fork to become available and wait a further five minutes before making their next attempt. This scheme eliminates the possibility of deadlock (the system can always advance to a different state) but still suffers from the problem of livelock. If all five philosophers appear in the dining room at exactly the same time and each picks up their left fork at the same time the philosophers will wait five minutes until they all put their forks down and then wait a further five minutes before they all pick them up again.
The lack of available forks is an analogy to the locking of shared resources in real computer programming, a situation known as concurrency. Locking a resource is a common technique to ensure the resource is accessed by only one program or chunk of code at a time. When the resource the program is interested in is already locked by another one, the program waits until it is unlocked. When several programs are involved in locking resources, deadlock might happen, depending on the circumstances. For example, one program needs two files to process. When two such programs lock one file each, both programs wait for the other one to unlock the other file, which will never happen."
Atomic operations are a set of operations that are guaranteed to run to completion without interruption or else wholly fail and leave no modifications. For situations where a single variable needs to be tested and possibly modified, some assembly instructions have been developed (the common ones are test-and-set and compare-and-swap). Using a single assembly instruction to perform a task guarantees that the operation will not be interrupted. Another approach is to lock a critical section in the code so that only one process has access to it at a time. Some common locking methods are described next.
A semaphore is a counter associated with a data structure, which must be checked before access can occur. Incrementing and decrementing of the counter are done with atomic methods down() and up(). If a process wishes to access the data structure, it must first perform a down() on the semaphore. The semaphore is decremented, and if the new value is less than 0, the process is blocked. If the new value is greater than or equal to zero the access may occur. Similarly, when a process is done accessing the data structure, it performs and up() on the semaphore. If the up() increases the counter from a value less than 0 to 0, a blocked process is awakened to access the data structure.
Spin locks are similar to semaphores, except that when a process finds that the lock is locked, it spins in a tight loop constantly polling until the lock is unlocked.
Mutexes are a kind of semaphore that only have the value 0 or 1. These can be used to guarantee exclusion to a resource (such as a data structure).
Current Topics
Transactional memory
Transactional memory is a new technique that aims to simplify the task of locking critical regions of code. Instead of using other (sometimes complicated) locking mechanisms, transactions only require that the critical region be delimited with pragmas that denote the code in between as atomic--either the entire section commits, or no changes are made. In general, a transactional section of code is executed and values are stored into a speculative cache that mirrors the actual system cache (other implementations have the updated values and addresses stored in logs). If any values (variables, structures, etc) change outside of the transaction that were referenced by the transaction, the entire transaction is forced to abort and begin again. If the transaction makes it to the end without any dependencies changing, all of the memory operations are committed. Transactions are best suited in situations where exclusive access is required and is very likely to occur, but cannot be guaranteed (such as in a section of kernel code in an SMP configuration). One tradeoff with transactions is that to negate overhead costs, transactions need to be sufficiently large in size, however, transactions that are too large are likely to have dependency faults.