A queue is a linear data structure that supports First-In-First-Out (FIFO) operations and is commonly used to decouple producers and consumers. In scenarios with slow production and fast consumption, queues act as buffers to balance the speed discrepancy. LifoQueue is a stack-style queue that follows the Last-In-First-Out (LIFO) principle, making it suitable for use cases such as undo operations. PriorityQueue, on the other hand, sorts elements by priority, which fits scenarios requiring preferential processing like task scheduling.These three types of queues are implemented via the `Queue`, `LifoQueue` and `PriorityQueue` classes respectively, which provide methods such as `put ()` and `get ()`, and are important thread-safe tools in concurrent programming.
For more information about us, you can refer to the cloud document: Freak Embedded Studio Cloud Docs, or visit our wiki:https://github.com/leezisheng/Doc/wik
This document is a learning guide on parallel computing and Python concurrent programming, which covers the core knowledge points including the basic concepts of parallel computing, Python multi-threaded programming, multi-process programming and coroutine programming:
Body Text
1. Basic Concepts and Applications of Queues
A queue is a First-In-First-Out (FIFO) linear list, which is usually implemented with a linked list or an array in practical applications. A queue only allows insertion operations at the rear end (called rear) and deletion operations at the front end (called front). The operation mode of a queue is similar to that of a stack, and the only difference is that a queue only allows new data to be added at the rear end.In Python, queues can be imported via the built-in module queue, and the specific import method is: from queue import Queue, The queue module provides a FIFO data structure suitable for multi-threaded programming, which can be used to safely pass messages or data between producer and consumer threads.
Queue has the following four commonly used methods:
put (): Puts an queue into the item.
get (): Removes an item from the queue and returns the removed item.
task_done (): This method should be called each time an item has been processed.
join (): Blocks all items until they have all been processed.
Here we take the producer-consumer model as an example, where producers send products to a queue and consumers receive products from the queue. The code is as follows:
from threading import Thread, Event
from queue import Queue
import time
import random
class producer(Thread):
# First, we create a producer class.
# Since we use a queue to hold the numbers, we no longer need a list to store them.
def __init__(self, queue):
Thread.__init__(self)
self.queue = queue
def run(self) :
# The producer class produces integers, then puts them into the queue in a for loop
for i in range(10):
item = random.randint(0, 256)
# The producer uses Queue.put(item [,block[, timeout]]) to insert data into the queue.
# Queue is synchronized; it has a built-in locking mechanism before inserting data.
self.queue.put(item)
# Two situations can occur:
# (1) If block is True and timeout is None:
# It may block until a free slot is available. If timeout is a positive integer,
# it blocks until that time and then raises an exception.
# (2) If block is False:
# If the queue has a free slot, the item is inserted immediately; otherwise an exception is raised immediately (timeout is ignored).
# In this example, put() checks whether the queue is full, then calls wait() to start waiting.
print('Producer notify: item N° %d appended to queue by %s' % (item, self.name))
time.sleep(1)
class consumer(Thread):
def __init__(self, queue):
Thread.__init__(self)
self.queue = queue
def run(self):
while True:
# The consumer uses Queue.get([block[, timeout]]) to retrieve data from the queue,
# The queue also uses locking internally. If the queue is empty, the consumer blocks.
item = self.queue.get()
print('Consumer notify : %d popped from queue by %s' % (item, self.name))
# The consumer takes an integer from the queue, then marks it as processed with the task_done() method.
self.queue.task_done()
if __name__ == '__main__':
queue = Queue()
t1 = producer(queue)
t2 = consumer(queue)
t3 = consumer(queue)
t4 = consumer(queue)
t1.start()
t2.start()
t3.start()
t4.start()
t1.join()
t2.join()
t3.join()
t4.join()
The code runs as follows:
The interaction between producers and consumers can be illustrated in the following diagram:
Other methods of Queue include:
join () Method and task_done () Method
Queue.task_done () After completing a task, Queue.task_done () function sends a signal to the queue that the task has been completed.
Queue.join () essentially means waiting until the queue is empty before performing other operations.
If a thread fetches an item from the queue once, but does not call task_done (), then join will be unable to determine whether the queue has been fully processed. If you call join () at the end, it will never return and will hang indefinitely. You can think of it this way: every time you call task_done, one element is removed from the queue. When join is executed at the end, it checks whether the queue length is zero to confirm the queue is finished, then proceeds with the main thread.
2. Slow Production - Fast Consumption
In the scenario of fast production and slow consumption, we can directly use task_done () together with join () to let empty () determine whether the queue has ended. Of course, we can correctly judge whether the queue has been emptied, but for the get method in the thread, if nothing tells it that the queue is empty, get will continue to block. In that case, we need to add a judgment in the get procedure: if empty () holds, break to exit the loop, otherwise get () will still keep blocking.
However, if the speed of producers is comparable to that of consumers, or the production rate is lower than the consumption rate, then it is unreliable to rely on task_done () to decrement the queue count; the queue will frequently be in a state of undersupply and often remain empty, so it is also unreliable to use empty for judgment. This situation will lead to the consequence that join can detect that the queue has finished processing, but threads cannot rely on empty () to determine whether they can exit. We can insert a specific "marker" at the end of each thread in the consumption queue. During consumption, we check whether such a "marker" is obtained; if so, we can determine that the queue has ended, since all production queues have finished and no new entries will be added.
3. Last-In-First-Out Queue LifoQueue
Contrary to the Queue mentioned above, the last data stored is taken out first, while the first data stored is taken out last. This kind of first-in-last-out queue is similar to a stack.
The sample code is as follows:
import queue
import threading
# You can set the queue length; when the queue is full it blocks automatically
q = queue.LifoQueue(5)
def put():
for i in range(3):
q.put(i)
print("数据 %d 被存入到队列中" % i)
q.join()
def get():
for i in range(3):
value = q.get()
print("数据 %d 从队列中取出" % value)
q.task_done()
if __name__ == '__main__':
t1 = threading.Thread(target=put, args=())
t1.start()
t2 = threading.Thread(target=get, args=())
t2.start()
The code output is as follows:
From the operation results, we find that the order in which we write data is in positive sequence, but the order in which we retrieve data is in reverse sequence. This indicates that the most recently stored data comes out last, which is a first-in, last-out queue.
4. Priority Queue (PriorityQueue)
PriorityQueue (priority queue) means that a priority is assigned when data is stored;when fetching data, the one with the highest priority is taken out. When storing data into the priority queue PriorityQueue, the smaller the set value, the higher the priority.(Note: When storing and fetching data using priority, the data in the queue must be of the same type; for example: class grade ranking, height ranking, etc.).
Sample Code:
import queue
q = queue.PriorityQueue()
q.put([1, 'ace'])
q.put([40, 333])
q.put([3, 'afd'])
q.put([5, '4asdg'])
# 1 is the highest priority,
while not q.empty(): # Run when not empty
print(q.get())
q = queue.PriorityQueue()
q.put('我')
q.put('你')
q.put('他')
q.put('她')
q.put('ta')
while not q.empty():
print(q.get())
Output result:
By priority: Whether it is numbers, letters, lists, tuples, etc. (dictionaries and sets have not been tested), data is stored and retrieved based on priority, and the data in the queue must be of the same type, all priority matching is performed according to the order of the ascii code table of the actual data, and Chinese characters follow the unicode table.