First, you need to count how much of total progress is made, as the loop index does not do this job anymore. Thus you need a separate atomic variable (e.g. tbb::atomic) to safely increment itby different threads.
Second, you need to update the visual element. In general, this can only be done under lock, but you are right that it's not the best idea. However the good thing about the progress bar is that it's not precise; it does not matter if it updates on every iteration or not. Thus you might apply some techniques to reduce lock contention. How often should you update the bar so that it does not appear frozen? If once per 10 or 100 iterations is sufficient, do that (based on the atomic counter of course). Then, if some thread is updating the bar, other threads should not wait; the next update will show total progress anyway. Therefore instead of acquiring a lock, you use try-acquire, and if unsuccessful, just proceed to the next iteration without waiting.
This still will have some performance impact, but hopefully negligible or at least justified enough by the ability for users to see that your program is making progress. I've heard that some program developers got user complains about the parallel version being slower, while in fact it was faster but did not show its progress.
MADakukanov:
