The code in listings 3 and 5 is not thread safe. The list could easily become empty between the call to empty() and acquiring the mutex, leading to a race condition. I see two other subtle race conditions as well. I haven't looked at the rest but this density of bugs is enough to convince me that this author doesn't understand multithreaded programming well enough to give advice on the topic.
Other bugs:
1. Assumes that std::list<T>::empty() is an atomic operation.
2. Assumes it's safe to use separate locks for reading and writing, which std::list says nothing about. It probably screws up even in practice for at least the case where you have only one element in the list and two threads execute push() and pop() at the same time.
In fairness to the rest of the article, in Listing 9 the author does protect the call to empty() with (the same) lock and also moves the condition inside of a while loop.
I'm not familiar with the STL implementation, but it seems the pop would need to be coherent with the push in an empty stack. Like if a thread was trying to pop the only entry while another was trying to push, 'intuitively' there'd be a race condition there if STL isn't thread safe (which is the whole point of the article I think).
The probabilistic nature of the data structure lets them get those nice O(lg n) and O(1) expected times without the wide-ranging memory conflicts that slow down concurrent min-heaps. Some more basic info on skiplists for people who aren't familiar with them:
There are much better ways to implement a concurrent queue than the ones shown. Using locks for every single queue/dequeue is a very good way to completely kill performance. A much better alternative is to use hand-over-hand locking, or use CAS for a lock-free implementation.
There are rather basic (producer/consume queues) and as some have pointed out, are buggy. I'd highly suggest looking at Boost's threading library (for an example of an object oriented approach to threading, taking advantage of RAII -- much of it is now standard in C++11), Intel's Thread Building Blocks, Java's built in Concurrency Utilities (java.util.concurrent package), Doug Lea's Fork Join Framework. The a great book on the subject is Maurice Herlihy's The Art of Multiprocessor Programming:
The book is in Java, but C++11 has the required primitives (cross platform compare and set for integral types, a defined memory model) so you could follow allong in C++11.
As Jey has so eruditely pointed out, this advice borders on useless. I've always implemented LL queues as a segment of a list, where each element is protected by it's own mutex wherein each thread may add or remove a node by taking a lock on the first node, then moving to the second node, letting go of the first lock and so on. Although you'll end up holding more than one lock while traversing and three while deleting, this is at the core of powerful ideas like hand-over-hand locking.
Other bugs:
1. Assumes that std::list<T>::empty() is an atomic operation.
2. Assumes it's safe to use separate locks for reading and writing, which std::list says nothing about. It probably screws up even in practice for at least the case where you have only one element in the list and two threads execute push() and pop() at the same time.