Cola PHP + MySQL

Debe cambiar su pedido para que no haya una ventana de tiempo.

POP del consumidor (cada consumidor tiene un $consumer_id único)

Update queue 
set last_pop = '$consumer_id' 
where last_pop is null 
order by id limit 1;

$job = 
  Select * from queue 
  where last_pop = '$consumer_id' 
  order by id desc 
  limit 1;

Empuje del proveedor

insert into queue 
  (id, last_pop, ...) 
values 
  (NULL, NULL, ...);

La cola se ordena en el tiempo por la columna id y se asigna en POP por el consumer_id.