As we all know, CPU resources are limited, and the processing speed of a task is not linearly positive with the number of threads. On the contrary, too many threads can lead to frequent CPU switching and poor processing performance. Therefore, the size of the thread pool is usually set in advance, considering the characteristics of the task to be processed and the hardware environment.
When we request a thread from a fixed size thread pool, how does the thread pool handle the request if there are no free resources in the thread pool? Reject the request or queue the request? How are the various processing strategies implemented?
In fact, these problems aren’t that complicated, and the underlying data structure is what we’re going to learn about today, queues.
1. What is a queue?
The queue can be thought of as a queue to buy a ticket, the first to buy first, later people can only stand at the end, not allowed to jump the queue. First come first, this is the classic “queue”.
The stack supports only two basic operations: push () and pop (). Queues are very similar to stacks in that they support very limited operations. The most basic operations are also two: enqueue (), put a data to the end of the queue; Dequeue () takes an element from the head of the queue.
So a queue, like a stack, is a linear table data structure with limited operations.
2. Sequential queue and chain queue
Like stacks, queues can be implemented as arrays or linked lists. Queues implemented in arrays are called sequential queues and queues implemented in linked lists are called chained queues.
3. Loop queues
As the name suggests, the loop queue looks a bit like a ring. The original array had a head and a tail, a straight line. Now, let’s put them end to end in a loop.
If a queue size is 8, head=4 and tail=7, respectively. When a new element, a, is added to the queue, we place the tail at subscript 7, but instead of updating to 8, tail moves back one bit in the loop to subscript 0. By doing this, you can avoid the data movement that sequential queue operations would encounter. However, it is difficult to realize the circular queue, and it is necessary to determine the conditions of empty queue and full queue.
In a sequential queue, tail=n is the criterion for detecting a full queue and head=tail is the criterion for detecting an empty queue. So, for the circular queue, how to determine whether the queue is empty or full?
The empty queue is still head=tail, but the full queue is a bit more complicated. (tail+1) %n=head (tail+1) %n=head (tail+1) %n=head (tail+1) %n=head (tail+1) %n=head
4. Blocking and concurrent queues
Blocking a queue is simply adding blocking operations to the queue. Fetching data from the queue head is blocked when the queue is empty. Because there is no data available at this point, it cannot be returned until there is data in the queue; If the queue is full, the insertion will be blocked until there is a free place in the queue to insert data, and then return.
The above definition is really a “producer-consumer model”. Blocking queues can be used to implement a producer-consumer model.
The producer-consumer model based on blocking queues can effectively coordinate the speed of production and consumption. Data processing can also be improved by coordinating the number of “producers” and “consumers”.
In the case of multi-threading, there will be multiple threads operating queue at the same time, this time, there will be thread safety problem, how to achieve a thread safe queue?
A thread-safe queue is called a concurrent queue. The simplest and direct way to implement it is to add a lock on enqueque () and dequeque (), but the lock granularity is large and the concurrency is low, allowing only one save or fetch operation at a time. In fact, array-based circular queues, using CAS atomic operations, can achieve very efficient concurrent queues. This is why circular queues are more widely used than chain queues.
5. Answer the opening paragraph
What happens when a new task requests a thread resource when there are no idle threads in the thread pool? How are the strategies implemented?
There are two general strategies. The first is the non-blocking approach, which simply rejects the task request. The other is blocking processing, queuing the request, wait until there is an idle thread, take out the queued request to continue processing. So, how do you handle queued requests?
We want to treat each queued request fairly and first come first, so queues are a good data structure for storing queued requests.
The linked queue based on the linked list can realize an unbounded queue that supports infinite queuing, but it may lead to too many requests waiting and the response time of request processing is too long. Therefore, for the response time sensitive system, the infinite queuing thread pool based on linked list implementation is not suitable.
Array-based bounded queues have a limited size, so if the queue size exceeds the queue size, subsequent requests will be rejected. This approach is relatively more reasonable for response time sensitive systems. However, setting up a reasonable queue size is also very delicate. A large queue causes too many waiting requests. A small queue causes insufficient utilization of system resources and maximum performance.
In addition, queues can be applied to any finite resource pool to queue requests, such as database connection pools. In fact, for most resource-limited scenarios, when there are no free resources, requests can be queued through the data structure “queue”.
6. Content summary
The biggest feature of queue is first in, first out. The main operation is queue entry and queue exit. You can do this with arrays or linked lists. Arrays are sequential queues, linked lists are linked queues. There is also a circular queue that looks like a ring. When arrays implement queues, there is movement of data. To solve this problem, we need a circular queue like a ring.
The key to realize the circular queue is to determine the conditions of empty queue and full queue.
In addition, there are several advanced queues, blocking queues, concurrent queues, and the underlying data structure is queues, but with a lot of other functions on top. Blocking queue means queue entry and queue exit operations can block. Concurrent queue means queue operation multi-thread safety.
Data Structures and Algorithms: Recursion