面试题：C语言线程池任务动态分配中的负载均衡

基于任务执行时间预估的负载均衡策略

策略阐述：
- 为每个任务预估一个执行时间。可以根据任务的类型、输入数据量等因素来进行预估。例如，如果任务是处理文件，文件大小可以作为预估执行时间的一个参考因素。
- 维护一个任务队列，按照预估执行时间从小到大排序。
- 每个线程从任务队列中按顺序获取任务执行。这样，执行时间短的任务会优先被分配，减少线程空闲时间，实现负载均衡。

C语言代码实现

假设已有一个简单的线程池框架，包含线程池初始化、任务添加、线程启动等基本功能。下面是在该框架中集成上述负载均衡策略的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>

// 定义任务结构体
typedef struct Task {
    void (*func)(void*);
    void *arg;
    int estimated_time; // 预估执行时间
    struct Task *next;
} Task;

// 定义线程池结构体
typedef struct ThreadPool {
    pthread_t *threads;
    Task *task_queue;
    pthread_mutex_t queue_lock;
    pthread_cond_t queue_not_empty;
    int max_threads;
    int stop;
} ThreadPool;

// 初始化线程池
ThreadPool* createThreadPool(int max_threads) {
    ThreadPool *pool = (ThreadPool*)malloc(sizeof(ThreadPool));
    pool->max_threads = max_threads;
    pool->threads = (pthread_t*)malloc(max_threads * sizeof(pthread_t));
    pool->task_queue = NULL;
    pool->stop = 0;

    pthread_mutex_init(&pool->queue_lock, NULL);
    pthread_cond_init(&pool->queue_not_empty, NULL);

    for (int i = 0; i < max_threads; i++) {
        pthread_create(&pool->threads[i], NULL, (void*(*)(void*))[](void* arg) {
            ThreadPool *pool = (ThreadPool*)arg;
            while (1) {
                Task *task;
                pthread_mutex_lock(&pool->queue_lock);
                while (pool->task_queue == NULL &&!pool->stop) {
                    pthread_cond_wait(&pool->queue_not_empty, &pool->queue_lock);
                }
                if (pool->stop && pool->task_queue == NULL) {
                    pthread_mutex_unlock(&pool->queue_lock);
                    pthread_exit(NULL);
                }
                task = pool->task_queue;
                pool->task_queue = task->next;
                pthread_mutex_unlock(&pool->queue_lock);

                (*task->func)(task->arg);
                free(task);
            }
        }, pool);
    }

    return pool;
}

// 添加任务到线程池，按预估执行时间排序插入
void addTask(ThreadPool *pool, void (*func)(void*), void *arg, int estimated_time) {
    Task *new_task = (Task*)malloc(sizeof(Task));
    new_task->func = func;
    new_task->arg = arg;
    new_task->estimated_time = estimated_time;
    new_task->next = NULL;

    pthread_mutex_lock(&pool->queue_lock);
    Task *prev = NULL;
    Task *curr = pool->task_queue;
    while (curr!= NULL && curr->estimated_time < estimated_time) {
        prev = curr;
        curr = curr->next;
    }
    if (prev == NULL) {
        new_task->next = pool->task_queue;
        pool->task_queue = new_task;
    } else {
        prev->next = new_task;
        new_task->next = curr;
    }
    pthread_cond_signal(&pool->queue_not_empty);
    pthread_mutex_unlock(&pool->queue_lock);
}

// 模拟任务函数
void taskFunction(void* arg) {
    int *data = (int*)arg;
    printf("Task with data %d is running\n", *data);
    // 模拟任务执行
    sleep(1); 
}

// 销毁线程池
void destroyThreadPool(ThreadPool *pool) {
    pthread_mutex_lock(&pool->queue_lock);
    pool->stop = 1;
    pthread_cond_broadcast(&pool->queue_not_empty);
    pthread_mutex_unlock(&pool->queue_lock);

    for (int i = 0; i < pool->max_threads; i++) {
        pthread_join(pool->threads[i], NULL);
    }

    pthread_mutex_destroy(&pool->queue_lock);
    pthread_cond_destroy(&pool->queue_not_empty);
    free(pool->threads);

    Task *task = pool->task_queue;
    Task *next;
    while (task!= NULL) {
        next = task->next;
        free(task);
        task = next;
    }
    free(pool);
}

int main() {
    ThreadPool *pool = createThreadPool(3);

    int data1 = 1;
    int data2 = 2;
    int data3 = 3;
    int data4 = 4;

    addTask(pool, taskFunction, &data1, 2);
    addTask(pool, taskFunction, &data2, 1);
    addTask(pool, taskFunction, &data3, 3);
    addTask(pool, taskFunction, &data4, 2);

    sleep(5);
    destroyThreadPool(pool);

    return 0;
}

处理预估不准确带来的影响

动态调整：
- 可以在任务执行完后，记录实际执行时间。如果实际执行时间与预估时间相差较大，可以根据这个差值来调整后续同类型任务的预估时间。例如，可以使用一个加权平均算法，将新的实际执行时间纳入计算，更新预估时间。
任务队列再平衡：
- 定期检查任务队列中任务的实际执行情况。如果发现某些任务的执行时间与预估时间偏差过大，重新对任务队列进行排序，以减少这种偏差对负载均衡的长期影响。
反馈机制：
- 线程可以将任务执行情况反馈给任务分配模块。例如，如果一个线程执行一个预估时间短的任务，但实际执行时间很长，任务分配模块可以根据这个反馈，下次分配任务时更加谨慎，甚至可以对任务进行进一步细分，以更好地平衡负载。

星途面试题库

面试题：C语言线程池任务动态分配中的负载均衡

知识考点

面试题答案

基于任务执行时间预估的负载均衡策略

C语言代码实现

处理预估不准确带来的影响