面试题：Python任务调度的优先级处理

Question

假设你正在使用Python开发一个任务调度器，要求支持任务优先级。请设计一个数据结构和调度算法，使得高优先级的任务能够优先执行，并且在Python中实现一个简单示例。同时分析该实现可能存在的性能瓶颈及优化方向。

Answer 1

数据结构设计

可以使用heapq模块实现的优先队列（最小堆）来存储任务，每个任务包含优先级和任务函数。堆的特性可以保证每次取出的任务都是优先级最高的（这里把优先级数值小的视为高优先级）。

调度算法

1. 将任务及其优先级放入优先队列。
2. 每次从优先队列中取出优先级最高的任务并执行。

Python示例代码

import heapq


class TaskScheduler:
    def __init__(self):
        self.task_queue = []

    def add_task(self, priority, task):
        heapq.heappush(self.task_queue, (priority, task))

    def run_tasks(self):
        while self.task_queue:
            priority, task = heapq.heappop(self.task_queue)
            print(f"Executing task with priority {priority}")
            task()


# 示例任务
def task1():
    print("Task 1 executed")


def task2():
    print("Task 2 executed")


scheduler = TaskScheduler()
scheduler.add_task(2, task1)
scheduler.add_task(1, task2)
scheduler.run_tasks()

性能瓶颈及优化方向

1. 性能瓶颈：
   • 任务添加和删除操作：每次添加和删除任务时，heapq的操作时间复杂度为$O(log n)$，当任务数量非常大时，这可能会成为性能瓶颈。
   • 任务执行时间：如果某个高优先级任务执行时间过长，会导致其他任务等待时间过长。
2. 优化方向：
   • 减少堆操作：可以批量处理任务，减少每次操作堆的次数。例如，积攒一定数量的任务后再统一添加到堆中。
   • 任务超时机制：为任务设置执行超时时间，避免单个任务长时间占用资源，影响其他任务执行。
   • 多线程/多进程：对于I/O密集型任务，可以使用多线程；对于CPU密集型任务，可以使用多进程，并行执行任务以提高整体效率。