Skip to content

Instantly share code, notes, and snippets.

@cheremin
Last active May 23, 2019 16:18
Show Gist options
  • Save cheremin/e52d6b3d83ae6d77f0750a3fb467318c to your computer and use it in GitHub Desktop.
Save cheremin/e52d6b3d83ae6d77f0750a3fb467318c to your computer and use it in GitHub Desktop.
Waiting time non-monotonicity example (waiting time paradox in queueing systems with vacations) https://dev.cheremin.info/2019/05/waiting-time-paradox-3.html
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.ThreadLocalRandom;
import org.junit.Ignore;
import org.junit.Test;
/** time is always in milliseconds */
public class MysteriousServerTest {
private static final ThreadLocalRandom RND = ThreadLocalRandom.current();
private static final double AVERAGE_INTERVAL_BETWEEN_RATES = 25; //ms/task = 40 tasks/sec
private static final double AVERAGE_SERVICE_TIME = AVERAGE_INTERVAL_BETWEEN_RATES / 5; //=5ms, i.e. utilisation=20%
private static final long BACKGROUND_JOB_TIME = 50; //ms
private static final int REQUESTS_TOTAL = 1_000; //~30-40 sec in total
@Test
public void serverLifeBeforeVasiliy() throws Exception {
final int sleepingTime = 5;
runSimulation(
sleepingTime,
AVERAGE_SERVICE_TIME,
AVERAGE_INTERVAL_BETWEEN_RATES
);
}
@Test
public void vasiliyFirstTry() throws Exception {
final int sleepingTime = 3;
runSimulation(
sleepingTime,
AVERAGE_SERVICE_TIME,
AVERAGE_INTERVAL_BETWEEN_RATES
);
}
@Test
public void vasiliySecondTry() throws Exception {
final int sleepingTime = 0;
runSimulation(
sleepingTime,
AVERAGE_SERVICE_TIME,
AVERAGE_INTERVAL_BETWEEN_RATES
);
}
@Test
// @Ignore
public void tryAll() throws Exception {
for( long sleepingTime = 0; sleepingTime <= 16; sleepingTime++ ) {
runSimulation(
sleepingTime,
AVERAGE_SERVICE_TIME,
AVERAGE_INTERVAL_BETWEEN_RATES
);
}
}
/* ====================== infra ============================================= */
private static void runSimulation( final long sleepingTime,
final double averageServiceTime,
final double averageIntervalBetweenRates ) throws InterruptedException {
System.out.printf(
"avg(between tasks): %.1f ms, avg(service): %.0f ms/task, sleep: %d ms\n",
AVERAGE_INTERVAL_BETWEEN_RATES, AVERAGE_SERVICE_TIME, sleepingTime
);
final ConcurrentLinkedQueue<Request> queue = new ConcurrentLinkedQueue<>();
final Server server = new Server(
queue,
/* backgroundJobTime = */ BACKGROUND_JOB_TIME,
/* sleepingTime = */ sleepingTime
);
final Thread thread = new Thread( server );
thread.start();
for( int requestNo = 0; requestNo < REQUESTS_TOTAL; requestNo++ ) {
final int serviceTime = RND.nextInt( 1, ( int ) ( averageServiceTime * 2 ) - 1 );//serviceTime in [1..2X-1], avg=X
final Request request = new Request( serviceTime );
request.enqueuedAt = System.currentTimeMillis();
queue.offer( request );
//generate exponentially-distributed inter-arrival interval (='poisson arrivals')
final long interArrivalTime = Math.round( -Math.log( RND.nextDouble() ) * averageIntervalBetweenRates );
Thread.sleep( interArrivalTime );
}
//give enough time to finish last tasks, and exit:
Thread.sleep( 1000 );
server.running = false;
thread.join();
}
public static class Request {
private final long serviceTime;
private long enqueuedAt;
private long processedAt;
public Request( final long serviceTime ) {
this.serviceTime = serviceTime;
}
public void doTheNeedful() throws InterruptedException {
Thread.sleep( serviceTime );
this.processedAt = System.currentTimeMillis();
}
public long timeWaited() {
return processedAt - enqueuedAt;
}
}
public static class Server implements Runnable {
private final ConcurrentLinkedQueue<Request> queue;
private final long backgroundJobTime;
private final long sleepingTime;
public Server( final ConcurrentLinkedQueue<Request> queue,
final long backgroundJobTime,
final long sleepingTime ) {
this.queue = queue;
this.backgroundJobTime = backgroundJobTime;
this.sleepingTime = sleepingTime;
}
private volatile boolean running;
@Override
public void run() {
long sumTimeWaited = 0;
double sumTimeWaitedSquared = 0;
int tasksProcessed = 0;
try {
running = true;
while( running ) {
final Request request = queue.poll();
if( request != null ) {
request.doTheNeedful();
final long waited = request.timeWaited();
tasksProcessed++;
sumTimeWaited += waited;
sumTimeWaitedSquared += waited * waited;
} else {
doBackgroundJob();
Thread.sleep( sleepingTime );
}
}
} catch( InterruptedException e ) {
System.err.println( "loop interrupted: exit" );
}
final double avgWaited = sumTimeWaited * 1.0 / tasksProcessed;
final double stdWaited = Math.sqrt( sumTimeWaitedSquared / tasksProcessed - avgWaited * avgWaited );
System.out.printf( "\ttasks: %d, avg(waited): %.1f ms, std(waited): %.1f\n",
tasksProcessed, avgWaited, stdWaited
);
}
private void doBackgroundJob() throws InterruptedException {
final int dice = ThreadLocalRandom.current().nextInt( 50 );
if( dice == 0 ) {// chance 1 of 50 to do some work
Thread.sleep( backgroundJobTime );
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment