What is the meaning of the term "thread-safe"?

An easier way to understand it, is what makes code not thread-safe. There's two main issues that will make a threaded application have unwanted behavior.

• Accessing shared variable without locking
  This variable could be modified by another thread while executing the function. You want to prevent it with a locking mechanism to be sure of the behavior of your function. General rule of thumb is to keep the lock for the shortest time possible.

• Deadlock caused by mutual dependency on shared variable
  If you have two shared variables A and B. In one function, you lock A first then later you lock B. In another function, you start locking B and after a while, you lock A. This is a potential deadlock where the first function will wait for B to be unlocked when second function will wait for A to be unlocked. This issue will probably not occur in your development environment and only from time to time. To avoid it, all locks must always be in the same order.

Don't confuse thread safety with determinism. Thread-safe code can also be non-deterministic. Given the difficulty of debugging problems with threaded code, this is probably the normal case. :-)

Thread safety simply ensures that when a thread is modifying or reading shared data, no other thread can access it in a way that changes the data. If your code depends on a certain order for execution for correctness, then you need other synchronization mechanisms beyond those required for thread safety to ensure this.

To complete other answers:

Synchronization is only a worry when the code in your method does one of two things:

1. works with some outside resource that isn't thread safe.
2. Reads or changes a persistent object or class field

This means that variables defined WITHIN your method are always threadsafe. Every call to a method has its own version of these variables. If the method is called by another thread, or by the same thread, or even if the method calls itself (recursion), the values of these variables are not shared.

Thread scheduling is not guaranteed to be round-robin. A task may totally hog the CPU at the expense of threads of the same priority. You can use Thread.yield() to have a conscience. You can use (in java) Thread.setPriority(Thread.NORM_PRIORITY-1) to lower a thread's priority

Plus beware of:

• the large runtime cost (already mentionned by others) on applications that iterate over these "thread-safe" structures.
• Thread.sleep(5000) is supposed to sleep for 5 seconds. However, if somebody changes the system time, you may sleep for a very long time or no time at all. The OS records the wake up time in absolute form, not relative.

Yes and yes. It implies that data is not modified by more than one thread simultaneously. However, your program might work as expected, and appear thread-safe, even if it is fundamentally not.

Note that the unpredictablility of results is a consequence of 'race-conditions' that probably result in data being modified in an order other than the expected one.