Schedule threades while maintaining synchronaization - java

Question

TLDR I'm having an hard time synchronizing multi-threaded system.

I Have implemented a Multi-threaded, shared-taxi simulator (with adjustable speed) that contains a weighted graph (where the weights are the time in milliseconds it takes to cross an edge) that represents a road map, and users Taxi and Passenger (each contains location and starting time).

The operation of the simulator is created by the following threads:

1. EventManager: initiates real-time activities (taxi and passenger) according to their starting time.
2. MatchMaker: runs a matching algorithm between taxis and passengers.
3. Taxis: each taxi runs on a separate thread that calculates the current location of the taxi, pickup order, and searches for shortest paths.

The problem is that over time, time differences between different threads are accumulating, which in turn causes the simulator to be inaccurate. For example, a Taxi may be in a location that should have taken x time to get to, while the simulator's time is at y ( y >> x ). My guess is that the time differences may be the result of CPU timing or delays in the movement of the taxi caused by long calculations and concurrency-related methods (e.g., wait() and synchronized()).

How can I make sure all of the threads work at the same rate? Should I add a delay to get them to synchronize? Or maybe add a Timer somewhere?

---

And for the implementation of the main components (I've removed irrelevant parts to keep the question clean) of some of the threads:

To move a Taxi I'm iterating over it's path, and calling sleep() with the weight of the edge (divided by the simulator's speed to make the entier system work at the same rate) in each iteration:

List<Edge> path;

@Override
public void run(){
        Iterator<Edge> itr = path.iterator();
        
        while(itr.hasNext()){
                currEdge = itr.next();
                sleep(currEdge.getWeight());
        }
}

private void sleep(long ms) {
        try {
            Thread.sleep(sleepTime / Simulator.getSpeed());
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
}

And the EventManager is timing new events by sleep between the event's time-stamps:

Queue<Users> events;

@Override
public void run(){
        User nextEvent;
        
        while(!events.isEmpty()){
                nextEvent = events.poll();
                simulator.start(nextEvent);
                
                sleep(nextEvent);
        }
}

private void sleep(User curr) {
        if(!events.isEmpty()){
                long timeToNextEvent = events.peek().getStartTimeInMS() - curr.getStartTimeInMS();
                try {
                        Thread.sleep(timeToNextEvent / Simulator.getSpeed());
                } catch (InterruptedException e) {
                        e.printStackTrace();
                }
        }
}

Answer 1

I'm not sure if this answer makes sense, but if your problem can be modeled as a Discrete Event Simulation (DES), I would advise you to use a simulated system clock. I have used and also built a couple of DES systems, and in all of them the simulated time was maintained by a queue where the elements were sorted according to the event time. Real time between two events were of course instantaneous.