But what makes path finding something that is hard to do in parallel with other processes?
Changes in map state. Doors, water, magma, constructions all change the walkable space.
Which really isn't a problem, because changes that happen while you're calculating a path are dwarfed by the much larger and more often occurrence, of changes that happen after you're done calculating your path. The former only has a handful of frames in which it can happen, the latter has hundreds or even thousands of frames in which it can happen, while the dwarf is walking to their destination. Fortunately, the latter is already covered, if a dwarf runs into an obstacle that wasn't there before, they simply find a new path. And if a new shorter path opens up, they simply ignore it for the rest of the trip, until they look for a new path. Which means the former is covered as well.
There would be instances where it would take part of the map on one frame, and part of it on another, but even without any extra measures to deal with that, there aren't many situations where it would produce a different path than just looking for a path a few frames earlier or later. And the few instances where it does, wouldn't result in much of a change in behavior anyway, just very rarely taking, or not taking, a path they otherwise wouldn't, or would have, where rapidly changing terrain is in place. Say for example, where you have one drawbridge opening, while another is closing at the same time, they might see both as being open, and try to path through that area. But, even if they did that, they would notice it and find a new path as soon as they ran into something which wasn't there when they were thinking about it, just the same as if there was one drawbridge, and it closed after they were done making a path that crossed over it. Just as they do in any other situation where they take a path that changes while they're taking it. I'd say it's too small a difference to worry about much. Although you might want to make sure that it doesn't read out any individual tile which is halfway through being written.