Shulou(Shulou.com)06/01 Report--

This article mainly introduces "how to achieve the time round algorithm in Java". In the daily operation, I believe that many people have doubts about how to achieve the time round algorithm in Java. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about "how to realize the time round algorithm in Java". Next, please follow the editor to study!

Consider a scenario where you currently have 1000 tasks and want those 1000 tasks to trigger an action every few minutes. If such a demand is realized, the first idea of many people is to get a timer. But 1000 tasks are 1000 timers, and one timer is a thread. In order to solve this problem, there is a time wheel algorithm.

Time wheel

Time wheel introduction: the time wheel scheme introduces the concept of clock in real life into software design, the main idea is to define a clock cycle (such as 12 hours of the clock) and step size (such as the clock goes once a second). When the pointer takes each step, the task mounted on the current clock scale is obtained and executed.

Core thought

A circular array stores all the slots of the time wheel (see your watch), and each slot corresponds to the minimum precision of the current time wheel.

Those that exceed the maximum range of the current time wheel will be thrown to the upper time wheel, and the minimum accuracy of the upper time wheel is the maximum time that the lower time wheel can express (the concept of hours, minutes and seconds).

Each slot corresponds to a circular linked list that stores the tasks that should be performed at that time.

You need a thread to drive the pointer to get the expired task.

The following is a simple handwritten version of java implementation

Code implementation

Time wheel master data structure

/ * * @ author apdoer * @ version 1.0 * @ date 19:31 on 2021-3-22 * / @ Slf4jpublic class TimeWheel {/ * interval of one slot (minimum scale of time wheel) * / private long tickMs; / * size of time wheel (number of slots) * / private int wheelSize; / * * time span of one round * / private long interval; private long currentTime / * slot * / private TimerTaskList [] buckets; / * upper time wheel * / private volatile TimeWheel overflowWheel; / * A timer has only one delayqueue * / private DelayQueue delayQueue; public TimeWheel (long tickMs, int wheelSize, long currentTime, DelayQueue delayQueue) {this.currentTime = currentTime; this.tickMs = 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);}

Timer interface

/ * timer * @ author apdoer * @ version 1.0 * @ date 20:30 on 2021-3-22 * / public interface Timer {/ * add a new task * * @ param timerTask * / void add (TimerTask timerTask); / * * push pointer * * @ param timeout * / void advanceClock (long timeout); / * * tasks waiting to be executed * * @ return * / int size () / * disable the service, and the rest cannot be executed * / void shutdown ();}

Timer implementation

/ * * @ author apdoer * @ version 1.0 * @ date 20:33 on 2021-3-22 * / @ Slf4jpublic class SystemTimer implements Timer {/ * underlying time wheel * / private TimeWheel timeWheel; / * A Timer has only one delay queue * / private DelayQueue delayQueue = new DelayQueue (); / * * expired task execution thread * / private ExecutorService workerThreadPool / * polling delayQueue to get expired task thread * / 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 pushes a time round this.bossThreadPool.submit (()-> {for (;;) {this.advanceClock (20);}}) } public void addTimerTaskEntry (TimerTaskEntry entry) {if (! timeWheel.add (entry)) {/ / has expired TimerTask timerTask = entry.getTimerTask (); log.info ("= task: {} has expired, ready to execute =", timerTask.getDesc ()); workerThreadPool.submit (timerTask);} @ Override public void add (TimerTask timerTask) {log.info ("= add task start = task: {}", timerTask.getDesc () TimerTaskEntry entry = new TimerTaskEntry (timerTask, timerTask.getDelayMs () + System.currentTimeMillis ()); timerTask.setTimerTaskEntry (entry); addTimerTaskEntry (entry);} / * * push pointer operation to get expired tasks * * @ param timeout interval * @ return * / @ Override public synchronized void advanceClock (long timeout) {try {TimerTaskList bucket = delayQueue.poll (timeout, TimeUnit.MILLISECONDS) If (bucket! = null) {/ / push time timeWheel.advanceLock (bucket.getExpiration ()); / / execute expired tasks (including demotion) 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;}}

Circular linked list of storage tasks

/ * * @ author apdoer * @ version 1.0 * @ date 19:26 on 2021-3-22 * / @ Data@Slf4jclass TimerTaskList implements Delayed {/ * TimerTaskList circular linked list uses a virtual root node root * / private TimerTaskEntry root = new TimerTaskEntry (null,-1); {root.next = root; root.prev = root;} / * * bucket expiration time * / private AtomicLong expiration = new AtomicLong (- 1L) Public long getExpiration () {return expiration.get ();} / * sets the expiration time of bucket. If the setting is successful, it returns true * * @ param expirationMs * @ return * / boolean setExpiration (long expirationMs) {return expiration.getAndSet (expirationMs)! = expirationMs;} public boolean addTask (TimerTaskEntry entry) {boolean done = false While (! done) {/ / if the TimerTaskEntry has been removed in another list, remove it outside the synchronization code block to avoid deadlock until entry.remove (); synchronized (this) {if (entry.timedTaskList = = null) {/ / add to the end of the linked list entry.timedTaskList = this; TimerTaskEntry tail = root.prev; entry.prev = tail; entry.next = root; tail.next = entry Root.prev = entry; done = true;}} return true;} / * remove the specified 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;} / * remove all * / public synchronized void clear (Consumer 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;}}

Container entry for storing tasks

/ * @ author apdoer * @ version 1.0 * @ date 19:26 on 2021-3-22 * / @ Dataclass TimerTaskEntry implements Comparable {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));}}

Task wrapper class (you can also pass in work tasks as thread variables)

@ Data@Slf4jclass TimerTask implements Runnable {/ * delay time * / 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) {/ / if the timetask is already held by an existing TimerTaskEntry, remove an if (timerTaskEntry! = null & & timerTaskEntry! = entry) {timerTaskEntry.remove ();} timerTaskEntry = entry;} public TimerTaskEntry getTimerTaskEntry () {return timerTaskEntry;} @ Override public void run () {log.info ("= {} Task execution", desc) }} at this point, the study of "how to implement the time round algorithm in Java" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.