multithreading and strtok
You should consider not using strtok or strtok_r at all. It's trivial to write your own functions similar to these but better-tailored to the exact way you want to use them, and of course have the caller store all the state and pass a pointer to the state for thread-safety/reentrancy.
As for your question about using a semaphore (or other locking primitive) around calls to strtok, that will not help if you just put it around the actual call. You'd have to hold the lock during the whole process of parsing the string to protect the internal state of strtok. I believe this is what many people refer to as locking code in place of data and it's generally considered A Bad Thing.
You'll need to use strtok_r.
In some non-standard implementations (most prominently Microsoft's), strtok stores its values in TLS (thread-local storage), so it should be fine to use in multiple threads at the same time. However, you cannot split your tokenization for one and the same string across multiple threads.