PriorityQueue is a class that implements the Queue interface and extends Java’s collection of priorities
transient Object[] queue; public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true; } private void siftUp(int k, E x) { if (comparator ! = null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; } private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; }Copy the codePoll () {poll (); poll () {poll (); poll () {poll ();
public E poll() { if (size == 0) return null; int s = --size; modCount++; E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; if (s ! = 0) siftDown(0, x); return result; }Copy the codeUnstack removes the first element of the array, but does not subtract the array size by 1, and sets the last position of the array to null, and precedes all elements of the array 1-size-1 by 1 bit. So that’s the concept of priority queues
## Handler mechanism
- Handler: Used to send multiple methods such as Message: sendMessage and implement the handleMessage() method to handle callbacks (you can also use Message or Handler’s Callback for Callback processing).
- Message: Message entity. Messages sent are of type Message.
- MessageQueue: MessageQueue used to store messages. When a message is sent, the message is queued, and Looper retrieves the message from the MessageQueen for processing.
- Looper: Bound to threads, not just the main thread, that are used to process messages. The loop() method is an infinite loop that keeps pulling messages from the MessageQueen for processing.
The Handler mechanism itself is based on the producer-consumer model, where the thread that sends the message is the producer and the thread that processes the message is the consumer (i.e., send/ POST is the producer and handleMessage is the consumer). Its working process is as follows:
private static Message getPostMessage(Runnable r) {
Message m = Message.obtain();
m.callback = r;
return m;
}
Copy the codeMessageQueue class enqueueMessage method source:
boolean enqueueMessage(Message msg, long when) { if (msg.target == null) { throw new IllegalArgumentException("Message must have a target."); } if (msg.isInUse()) { throw new IllegalStateException(msg + " This message is already in use."); } synchronized (this) { if (mQuitting) { IllegalStateException e = new IllegalStateException( msg.target + " sending message to a Handler on a dead thread"); Log.w(TAG, e.getMessage(), e); msg.recycle(); return false; } msg.markInUse(); msg.when = when; Message p = mMessages; boolean needWake; if (p == null || when == 0 || when < p.when) { // New head, wake up the event queue if blocked. msg.next = p; mMessages = msg; needWake = mBlocked; } else { // Inserted within the middle of the queue. Usually we don't have to wake // up the event queue unless there is a barrier at the head of the queue // and the message is the earliest asynchronous message in the queue. needWake = mBlocked && p.target == null && msg.isAsynchronous(); Message prev; for (;;) { prev = p; p = p.next; if (p == null || when < p.when) { break; } if (needWake && p.isAsynchronous()) { needWake = false; } } msg.next = p; // invariant: p == prev.next prev.next = msg; } // We can assume mPtr ! = 0 because mQuitting is false. if (needWake) { nativeWake(mPtr); } } return true; }Copy the codeLooper’s loop method is consuming messages from MessageQueue. Looper’s loop method is consuming messages from MessageQueue.
public static void loop() { final MessageQueue queue = me.mQueue; for (;;) {... Message msg = queue.next(); . try { msg.target.dispatchMessage(msg); dispatchEnd = needEndTime ? SystemClock.uptimeMillis() : 0; } finally { if (traceTag ! = 0) { Trace.traceEnd(traceTag); }}... }}Copy the codeMessageQueue class:
Message next() { // Return here if the message loop has already quit and been disposed. // This can happen if the application tries to restart a looper after quit // which is not supported. final long ptr = mPtr; if (ptr == 0) { return null; } int pendingIdleHandlerCount = -1; // -1 only during first iteration int nextPollTimeoutMillis = 0; for (;;) { if (nextPollTimeoutMillis ! = 0) { Binder.flushPendingCommands(); } nativePollOnce(ptr, nextPollTimeoutMillis); synchronized (this) { // Try to retrieve the next message. Return if found. final long now = SystemClock.uptimeMillis(); Message prevMsg = null; Message msg = mMessages; if (msg ! = null && msg.target == null) { // Stalled by a barrier. Find the next asynchronous message in the queue. do { prevMsg = msg; msg = msg.next; } while (msg ! = null && ! msg.isAsynchronous()); } if (msg ! = null) { if (now < msg.when) { // Next message is not ready. Set a timeout to wake up when it is ready. nextPollTimeoutMillis = (int) Math.min(msg.when - now, Integer.MAX_VALUE); } else { // Got a message. mBlocked = false; if (prevMsg ! = null) { prevMsg.next = msg.next; } else { mMessages = msg.next; } msg.next = null; if (DEBUG) Log.v(TAG, "Returning message: " + msg); msg.markInUse(); return msg; } } else { // No more messages. nextPollTimeoutMillis = -1; } // Process the quit message now that all pending messages have been handled. if (mQuitting) { dispose(); return null; } // If first time idle, then get the number of idlers to run. // Idle handles only run if the queue is empty or if the first message // in the queue (possibly a barrier) is due to be handled in the future. if (pendingIdleHandlerCount < 0 && (mMessages == null || now < mMessages.when)) { pendingIdleHandlerCount = mIdleHandlers.size(); } if (pendingIdleHandlerCount <= 0) { // No idle handlers to run. Loop and wait some more. mBlocked = true; continue; } if (mPendingIdleHandlers == null) { mPendingIdleHandlers = new IdleHandler[Math.max(pendingIdleHandlerCount, 4)]; } mPendingIdleHandlers = mIdleHandlers.toArray(mPendingIdleHandlers); } // Run the idle handlers. // We only ever reach this code block during the first iteration. for (int i = 0; i < pendingIdleHandlerCount; i++) { final IdleHandler idler = mPendingIdleHandlers[i]; mPendingIdleHandlers[i] = null; // release the reference to the handler boolean keep = false; try { keep = idler.queueIdle(); } catch (Throwable t) { Log.wtf(TAG, "IdleHandler threw exception", t); } if (! keep) { synchronized (this) { mIdleHandlers.remove(idler); } } } // Reset the idle handler count to 0 so we do not run them again. pendingIdleHandlerCount = 0; // While calling an idle handler, a new message could have been delivered // so go back and look again for a pending message without waiting. nextPollTimeoutMillis = 0; }}Copy the codeThe loop will continuously ask whether there is any Message that can be processed in MessageQueue. The judgment of processing is based on whether the current system time is greater than or equal to the when attribute of Message. If so, the Message will be removed from the MessageQueue queue. And then return. If not, the thread is blocked and the nativePollOnce method is called with nextPollTimeoutMillis blocking time. When the loop has a message to process, it sends it to the Handler for dispatch
private static void prepare(boolean quitAllowed) { if (sThreadLocal.get() ! = null) { throw new RuntimeException("Only one Looper may be created per thread"); } sThreadLocal.set(new Looper(quitAllowed)); } public static @Nullable Looper myLooper() { return sThreadLocal.get(); }Copy the codeA thread can have N handlers, but only one Looper. How to ensure the uniqueness of Looper is through ThreadLocal
static final ThreadLocal<T> sThreadLocal = new ThreadLocal<T>();
sThreadLocal.set()
sThreadLocal.get()
Copy the codeWhere set,get source code is as follows:
public void set(T value) { Thread t = Thread.currentThread(); ThreadLocalMap map = getMap(t); if (map ! = null) map.set(this, value); else createMap(t, value); } public T get() { Thread t = Thread.currentThread(); ThreadLocalMap map = getMap(t); if (map ! = null) { ThreadLocalMap.Entry e = map.getEntry(this); if (e ! = null) { @SuppressWarnings("unchecked") T result = (T)e.value; return result; } } return setInitialValue(); }Copy the codeThreadLocal is a key-value pair Map that implements the ability to store variables in the current thread. An instance of Looper is stored in a ThreadLocalMap, and its key is the ThreadLocal object itself. ThreadLocalMap is obtained through getMap method, getMap method source:
ThreadLocalMap getMap(Thread t) {return t.htreadlocals; } void createMap(Thread t, T firstValue) { t.threadLocals = new ThreadLocalMap(this, firstValue); } Thread class: public class Thread implements Runnable {ThreadLocal. ThreadLocalMap threadLocals = null; }Copy the codeThe object of ThreadLocalMap, threadLocals, is thread-unique, and looper is thread-unique.
The Handler that we instantiate is based on the main thread. How do child threads instantiate handlers? A few points to note:
- Looper.prepare (instantiate Looper and store it in ThreadLocal)
- Looper.loop (Starts the for loop)
- Looper.quit (Stop loop for, free thread, free memory)
public class HandlerDemoThread extends Thread { private Looper mLooper; @Override public void run() { Looper.prepare(); synchronized (this) { mLooper = Looper.myLooper(); } Looper.loop(); } public Looper getLooper() throws Exception { if (! isAlive()) { throw new Exception("current thread is not alive"); } if (mLooper == null) { throw new Exception("current thread is not start"); } return mLooper; } } class MainActivity : AppCompatActivity() { override fun onCreate(savedInstanceState: Bundle?) { super.onCreate(savedInstanceState) setContentView(R.layout.activity_main) val handlerThread = HandlerDemoThread() handlerThread.start() val handler1 = object : Handler(handlerThread.getLooper()) { override fun handleMessage(msg: Message?) { super.handleMessage(msg) } } handler1.sendMessage(Message.obtain()) } override fun onDestroy() { super.onDestroy() handler1.looper.quit() } }Copy the codeThe Handler must ensure that the current thread is prepared before initialization, i.e. instantiate Looper storage and ThreadLocal. Also start Looper’s loop method to get the transport belt running. It is important to note that since the methods send## and pos## may be executed on different threads, when sending a delay message, a synchronization lock will be applied to enqueueMessage, which will cause the delay to calculate the time is not accurate. The ActivityThread has already started Looper for the main thread. The ActivityThread has already started Looper for the main thread.
The main method of an ActivityThread is the entry to the main method of an ActivityThread. The main method of an ActivityThread is the main method of an ActivityThread.
public static void main(String[] args) { ... Looper.prepareMainLooper(); ActivityThread thread = new ActivityThread(); // The attach method completes the initialization of the Application object, and then calls the Application onCreate() method thread.attach(false); if (sMainThreadHandler == null) { sMainThreadHandler = thread.getHandler(); }... Looper.loop(); throw new RuntimeException("Main thread loop unexpectedly exited"); }Copy the codeHow come the main thread doesn’t call quit? Of course, the logic is not good. When the main thread is closed, the app will be closed. And in the quit method, that is, the final call is MessageQueue quit method, has been verified, the source code is as follows:
void quit(boolean safe) { if (! mQuitAllowed) { throw new IllegalStateException("Main thread not allowed to quit."); } synchronized (this) { if (mQuitting) { return; } mQuitting = true; if (safe) { removeAllFutureMessagesLocked(); } else { removeAllMessagesLocked(); } // We can assume mPtr ! = 0 because mQuitting was previously false. nativeWake(mPtr); } } private void removeAllMessagesLocked() { Message p = mMessages; while (p ! = null) { Message n = p.next; p.recycleUnchecked(); p = n; } mMessages = null; } private void removeAllFutureMessagesLocked() { final long now = SystemClock.uptimeMillis(); Message p = mMessages; if (p ! = null) { if (p.when > now) { removeAllMessagesLocked(); } else { Message n; for (;;) { n = p.next; if (n == null) { return; } if (n.when > now) { break; } p = n; } p.next = null; do { p = n; n = p.next; p.recycleUnchecked(); } while (n ! = null); }}} Message class: void recycleUnchecked() { // Mark the message as in use while it remains in the recycled object pool. // Clear out all other details. flags = FLAG_IN_USE; what = 0; arg1 = 0; arg2 = 0; obj = null; replyTo = null; sendingUid = -1; when = 0; target = null; callback = null; data = null; synchronized (sPoolSync) { if (sPoolSize < MAX_POOL_SIZE) { next = sPool; sPool = this; sPoolSize++; }}}Copy the codeMessageQueue quits the Message queue and the internal parameters of MessageQueue. The loop calls MessageQueue’s next method in Looper. The next method must be set to true before waking up a thread in nativeWake.
. for (;;) {... nativePollOnce(ptr, nextPollTimeoutMillis); synchronized (this) { ................. if (mQuitting) { dispose(); return null; }... }}Copy the codeSince MessageQueue quit has awoken the thread, next continues to change to diapose when mspapers to true, returns null, and returns the direct return loop method when the loop returns null. The loop method ends and the entire thread has to be released. So back to the quit method, so quit frees up both memory and thread;
In a child thread, if a Looper is manually created for it, the quit method should be called to terminate the message loop after everything is done. Otherwise, the child thread will remain in a waiting (blocking) state. If Looper is quit, the thread will terminate immediately. It is therefore recommended to terminate Looper when it is not needed. That is, call the quit method
The thing to note here is that the recycle-unchecked method has this code:
synchronized (sPoolSync) {
if (sPoolSize < MAX_POOL_SIZE) {
next = sPool;
sPool = this;
sPoolSize++;
}
Copy the codeThe logic here is to add the Message from the end of the queue to the Message pool, which has been emptied internally and stripped externally. A Message pool is a memory pool where users create messages. So how do you create messages in this Handler? The concept of memory sharing, or memory overcommitment, is used to prevent frequent instances of Message from causing memory jitter. Obtain an instance of Message by calling the obtain method.
public static Message obtain() { synchronized (sPoolSync) { if (sPool ! = null) { Message m = sPool; sPool = m.next; m.next = null; m.flags = 0; // clear in-use flag sPoolSize--; return m; } } return new Message(); }Copy the code#### think: Why doesn’t the Handler block the main thread? The Handler will sleep the current thread that has fallen into the stack until the sleep time expires. Why doesn’t the Handler block the main thread if it sleeps the thread?
A thread is a piece of executable code. When the executable code completes, the thread life cycle terminates and the thread exits. For the main thread, we do not want to be run for a period of time, and then exit, so how to ensure that it is always alive? The simple way to do this is that executable code can always be executed, and an infinite loop is guaranteed not to exit (binder threads also use an infinite loop, which is different from the way they read and write with binder drivers). Of course, it is not simply an infinite loop, sleeping when there is no message. But that might raise another question: how do you do anything else if it’s an infinite loop? By creating a new thread. Really getting stuck the operation of the main thread is in the callback method onCreate/onStart/onResume operating time is too long, can lead to a frame, even ANR, stars. The loop itself does not result in application.
This again raises the question: is the main thread running in an endless loop particularly CPU intensive?
No, MessageQueue blocks in the nativePollOnce() method of the loop’s queue.next() when the main thread frees CPU resources and goes to sleep until the next message arrives or a transaction occurs. Wake up the main thread by writing data to the pipe end. The epoll mechanism adopted here is an IO multiplexing mechanism, which can monitor multiple descriptors at the same time. When a descriptor is ready (read or write ready), it immediately notifies the corresponding program to carry out read or write operations, which is essentially synchronous I/O, that is, read and write is blocked. Therefore, the main thread is dormant most of the time and does not consume a lot of CPU resources.