자바 단순 핸드폰 버 전 구현 시간 바퀴 알고리즘

타임 휠
시간 라운드 에 관 한 소 개 는 인터넷 에 매우 많 으 니,여 기 는 중복 되 지 않 는 다.
핵심 사상
4.567917.하나의 링 배열 저장 시간 바퀴 의 모든 슬롯(당신 의 시 계 를 보 세 요),각 슬롯 은 현재 시간 바퀴 의 최소 정밀도 에 대응 합 니 다4.567917.현재 시간 바퀴 의 최대 표현 범 위 를 초과 하 는 것 은 상층 시간 바퀴 로 떨 어 질 것 이다.상층 시간 바퀴 의 최소 정 도 는 바로 하층 시간 바퀴 가 표현 할 수 있 는 최대 시간(시 분 초 개념)이다4.567917.각 슬롯 은 하나의 링 링크 에 대응 하여 이 시간 에 수행 해 야 할 임 무 를 저장 합 니 다4.567917.포인터 가 작 동 하도록 스 레 드 가 필요 하고 만기 임 무 를 얻 을 수 있 습 니 다.
다음은 자바 간단 한 핸드폰 버 전 구현
코드 구현
타임 휠 메 인 데이터 구조

/**
 * @author apdoer
 * @version 1.0
 * @date 2021/3/22 19:31
 */
@Slf4j
public class TimeWheel {
 /**
  *         (       )
  */
 private long tickMs;

 /**
  *      (    )
  */
 private int wheelSize;

 /**
  *        
  */
 private long interval;

 private long currentTime;

 /**
  *  
  */
 private TimerTaskList[] buckets;

 /**
  *      
  */
 private volatile TimeWheel overflowWheel;

 /**
  *   timer    delayqueue
  */
 private DelayQueue<TimerTaskList> delayQueue;

 public TimeWheel(long tickMs, int wheelSize, long currentTime, DelayQueue<TimerTaskList> delayQueue) {
  this.currentTime = currentTime;
  this.tickMs = tickMs;
  this.wheelSize = wheelSize;
  this.interval = tickMs * wheelSize;
  this.buckets = new TimerTaskList[wheelSize];
  this.currentTime = currentTime - (currentTime % tickMs);
  this.delayQueue = delayQueue;
  for (int i = 0; i < wheelSize; i++) {
   buckets[i] = new TimerTaskList();
  }
 }

 public boolean add(TimerTaskEntry entry) {
  long expiration = entry.getExpireMs();
  if (expiration < tickMs + currentTime) {
   //   
   return false;
  } else if (expiration < currentTime + interval) {
   //            ,         ,     
   long virtualId = (expiration / tickMs);
   int index = (int) (virtualId % wheelSize);
   TimerTaskList bucket = buckets[index];
   bucket.addTask(entry);
   //  bucket     
   if (bucket.setExpiration(virtualId * tickMs)) {
    //       bucket    
    delayQueue.offer(bucket);
    return true;
   }
  } else {
   //       ,       
   TimeWheel timeWheel = getOverflowWheel();
   return timeWheel.add(entry);
  }
  return false;
 }


 private TimeWheel getOverflowWheel() {
  if (overflowWheel == null) {
   synchronized (this) {
    if (overflowWheel == null) {
     overflowWheel = new TimeWheel(interval, wheelSize, currentTime, delayQueue);
    }
   }
  }
  return overflowWheel;
 }

 /**
  *     
  *
  * @param timestamp
  */
 public void advanceLock(long timestamp) {
  if (timestamp > currentTime + tickMs) {
   currentTime = timestamp - (timestamp % tickMs);
   if (overflowWheel != null) {
    this.getOverflowWheel().advanceLock(timestamp);
   }
  }
 }
}

타이머 인터페이스

/**
 *    
 * @author apdoer
 * @version 1.0
 * @date 2021/3/22 20:30
 */
public interface Timer {

 /**
  *        
  *
  * @param timerTask
  */
 void add(TimerTask timerTask);


 /**
  *     
  *
  * @param timeout
  */
 void advanceClock(long timeout);

 /**
  *        
  *
  * @return
  */
 int size();

 /**
  *     ,        
  */
 void shutdown();
}

타이머 구현

/**
 * @author apdoer
 * @version 1.0
 * @date 2021/3/22 20:33
 */
@Slf4j
public class SystemTimer implements Timer {
 /**
  *      
  */
 private TimeWheel timeWheel;
 /**
  *   Timer        
  */
 private DelayQueue<TimerTaskList> delayQueue = new DelayQueue<>();
 /**
  *         
  */
 private ExecutorService workerThreadPool;
 /**
  *   delayQueue        
  */
 private ExecutorService bossThreadPool;


 public SystemTimer() {
  this.timeWheel = new TimeWheel(1, 20, System.currentTimeMillis(), delayQueue);
  this.workerThreadPool = Executors.newFixedThreadPool(100);
  this.bossThreadPool = Executors.newFixedThreadPool(1);
  //20ms         
  this.bossThreadPool.submit(() -> {
   for (; ; ) {
    this.advanceClock(20);
   }
  });
 }


 public void addTimerTaskEntry(TimerTaskEntry entry) {
  if (!timeWheel.add(entry)) {
   //     
   TimerTask timerTask = entry.getTimerTask();
   log.info("=====  :{}    ,    ============",timerTask.getDesc());
   workerThreadPool.submit(timerTask);
  }
 }

 @Override
 public void add(TimerTask timerTask) {
  log.info("=======      ====task:{}", timerTask.getDesc());
  TimerTaskEntry entry = new TimerTaskEntry(timerTask, timerTask.getDelayMs() + System.currentTimeMillis());
  timerTask.setTimerTaskEntry(entry);
  addTimerTaskEntry(entry);
 }

 /**
  *             
  *
  * @param timeout     
  * @return
  */
 @Override
 public synchronized void advanceClock(long timeout) {
  try {
   TimerTaskList bucket = delayQueue.poll(timeout, TimeUnit.MILLISECONDS);
   if (bucket != null) {
    //    
    timeWheel.advanceLock(bucket.getExpiration());
    //      (    )
    bucket.clear(this::addTimerTaskEntry);
   }
  } catch (InterruptedException e) {
   log.error("advanceClock error");
  }
 }

 @Override
 public int size() {
  //todo
  return 0;
 }

 @Override
 public void shutdown() {
  this.bossThreadPool.shutdown();
  this.workerThreadPool.shutdown();
  this.timeWheel = null;
 }
}

작업 을 저장 하 는 링 링크

/**
 * @author apdoer
 * @version 1.0
 * @date 2021/3/22 19:26
 */
@Data
@Slf4j
class TimerTaskList implements Delayed {
 /**
  * TimerTaskList              root
  */
 private TimerTaskEntry root = new TimerTaskEntry(null, -1);

 {
  root.next = root;
  root.prev = root;
 }

 /**
  * bucket     
  */
 private AtomicLong expiration = new AtomicLong(-1L);

 public long getExpiration() {
  return expiration.get();
 }

 /**
  *   bucket     ,      true
  *
  * @param expirationMs
  * @return
  */
 boolean setExpiration(long expirationMs) {
  return expiration.getAndSet(expirationMs) != expirationMs;
 }

 public boolean addTask(TimerTaskEntry entry) {
  boolean done = false;
  while (!done) {
   //  TimerTaskEntry     list     ,         ,    ,       
   entry.remove();
   synchronized (this) {
    if (entry.timedTaskList == null) {
     //       
     entry.timedTaskList = this;
     TimerTaskEntry tail = root.prev;
     entry.prev = tail;
     entry.next = root;
     tail.next = entry;
     root.prev = entry;
     done = true;
    }
   }
  }
  return true;
 }

 /**
  *   TimedTaskList       timerTaskEntry
  *
  * @param entry
  */
 public void remove(TimerTaskEntry entry) {
  synchronized (this) {
   if (entry.getTimedTaskList().equals(this)) {
    entry.next.prev = entry.prev;
    entry.prev.next = entry.next;
    entry.next = null;
    entry.prev = null;
    entry.timedTaskList = null;
   }
  }
 }

 /**
  *     
  */
 public synchronized void clear(Consumer<TimerTaskEntry> entry) {
  TimerTaskEntry head = root.next;
  while (!head.equals(root)) {
   remove(head);
   entry.accept(head);
   head = root.next;
  }
  expiration.set(-1L);
 }

 @Override
 public long getDelay(TimeUnit unit) {
  return Math.max(0, unit.convert(expiration.get() - System.currentTimeMillis(), TimeUnit.MILLISECONDS));
 }

 @Override
 public int compareTo(Delayed o) {
  if (o instanceof TimerTaskList) {
   return Long.compare(expiration.get(), ((TimerTaskList) o).expiration.get());
  }
  return 0;
 }
}

작업 저장 용기 entry

/**
 * @author apdoer
 * @version 1.0
 * @date 2021/3/22 19:26
 */
@Data
class TimerTaskEntry implements Comparable<TimerTaskEntry> {
 private TimerTask timerTask;
 private long expireMs;
 volatile TimerTaskList timedTaskList;
 TimerTaskEntry next;
 TimerTaskEntry prev;

 public TimerTaskEntry(TimerTask timedTask, long expireMs) {
  this.timerTask = timedTask;
  this.expireMs = expireMs;
  this.next = null;
  this.prev = null;
 }

 void remove() {
  TimerTaskList currentList = timedTaskList;
  while (currentList != null) {
   currentList.remove(this);
   currentList = timedTaskList;
  }
 }

 @Override
 public int compareTo(TimerTaskEntry o) {
  return ((int) (this.expireMs - o.expireMs));
 }
}

작업 패키지 클래스(작업 작업 작업 을 스 레 드 변수 로 전송 할 수도 있 습 니 다)

@Data
@Slf4j
class TimerTask implements Runnable {
 /**
  *     
  */
 private long delayMs;
 /**
  *      entry
  */
 private TimerTaskEntry timerTaskEntry;

 private String desc;

 public TimerTask(String desc, long delayMs) {
  this.desc = desc;
  this.delayMs = delayMs;
  this.timerTaskEntry = null;
 }

 public synchronized void setTimerTaskEntry(TimerTaskEntry entry) {
  //     timetask         TimerTaskEntry  ,     
  if (timerTaskEntry != null && timerTaskEntry != entry) {
   timerTaskEntry.remove();
  }
  timerTaskEntry = entry;
 }

 public TimerTaskEntry getTimerTaskEntry() {
  return timerTaskEntry;
 }

 @Override
 public void run() {
  log.info("============={}    ", desc);
 }
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.