Shared data in multithreaded pathfinding engine

Question

Imagine a case where you have lots agents in a big world, who frequently need to calculate the shortest/best path from A to B. In this case it seems natural for me to create a pathfinding engine where each path request is performed in a separate thread. Similar to this example. Requests are stored in a queue, and when there are available threads to perform calculation the request will be taken from the queue and finally moved to a collection of calculated paths.

My problem is: how do you store and update the data that will be shared among all the threads? The threads needs access to some kind of map structure (could be a 2D array), and his data needs to be updated frequently. Using some kind of synchronisation mechanism would be too expensive, since we have several threads frequently reading from the data.

I have come up with two suggestions:

1. Store the map structure as an array of atomics. This seems like a simple and effective solution, however we will give ourself a limitation: we can only use data that can be stored as an atomic type - which in most cases should be OK.
2. Create two buffers containing a copy of the data, and keep a reference count for how many threads are currently using the buffer. First update buffer A, then for each new path request we let the thread read from buffer A. When there are no more threads accessing buffer B (RefCount==0) update buffer B and set it as the new active buffer. With this solution we can use any kind of data structure, but it will (depending on the calculation time) be slightly out of sync - which I believe should not be a big problem for pathfinding. If the calculations take a long time, it will be out of sync anyway.

What are your thoughts? I don't have too much experience in the field, so I'm not sure if there are any "popular" solutions to this problem.

Edit

This is what I ended up with (after reading Kromster's answer):

1. Update the data
2. Take requests out from the queue and start a thread for each request.
3. For each frame: check if all threads have finished.
4. When all threads are done, go back to step 1.

At step 1, all worker threads are idle.

When an agent needs to get a path from A to B, it will call requestPath(from, to), which will return a unique ticket. The ticket has an atomic(modified by pathfinder thread, accessed by agent) indicating whether it is valid or not. When the path has been caluclated, the ticket becomes valid and the agent can call getPath(ticket) to get the path.

Answer 1

I would expect all pathfinders working in threads while the rest of the game is busy with other things unrelated to map changing. So map structure could be locked from updates and be in read-only mode while pathfinders do their work.

Of course such system is handy when you do have several lengthy paths to build on each tick or other tasks that can be parallelized (think at least thousands of non-cache-friendly agents on a map).