edf算法c语言实现

EDF（Earliest Deadline First）算法是一种实时调度算法，它的核心思想是按照任务的最后期限来进行调度，即最先到期的任务先执行。下面是一个简单的EDF算法的C语言实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_TASKS 10

typedef struct {
    int id; // 任务ID
    int release_time; // 任务发布时间
    int deadline; // 任务最后期限
    int execution_time; // 任务执行时间
} task_t;

int edf_schedule(task_t tasks[], int n) {
    int current_time = 0;
    int i, j, min_deadline, min_deadline_index;
    int is_completed[MAX_TASKS] = {0}; // 标记任务是否已完成

    for (i = 0; i < n; i++) {
        min_deadline = INT_MAX;
        min_deadline_index = -1;

        // 找到最先到期的未完成任务
        for (j = 0; j < n; j++) {
            if (!is_completed[j] && tasks[j].deadline < min_deadline) {
                min_deadline = tasks[j].deadline;
                min_deadline_index = j;
            }
        }

        // 如果没有未完成的任务，则退出循环
        if (min_deadline_index == -1) {
            break;
        }

        // 执行任务
        current_time += tasks[min_deadline_index].execution_time;

        // 标记任务已完成
        is_completed[min_deadline_index] = 1;

        printf("Task %d is completed at time %d.\n", tasks[min_deadline_index].id, current_time);

        // 如果当前时间已经超过任务最后期限，则调度失败
        if (current_time > tasks[min_deadline_index].deadline) {
            return -1;
        }
    }

    return 0;
}

int main() {
    task_t tasks[MAX_TASKS] = {
        {1, 0, 5, 2},
        {2, 1, 4, 1},
        {3, 2, 6, 3},
        {4, 4, 7, 2},
        {5, 5, 9, 3}
    };

    int n = sizeof(tasks) / sizeof(task_t);

    if (edf_schedule(tasks, n) == -1) {
        printf("EDF scheduling failed.\n");
    } else {
        printf("EDF scheduling succeeded.\n");
    }

    return 0;
}

这个实现中，我们首先定义了一个task_t结构体来表示任务，包括任务ID、发布时间、最后期限和执行时间。然后我们定义了一个edf_schedule函数来进行EDF调度。在这个函数中，我们首先初始化当前时间为0，并定义一个is_completed数组来标记任务是否已完成。然后我们循环遍历所有任务，每次找到最先到期的未完成任务，并执行它。如果当前时间已经超过任务最后期限，则调度失败。最后，如果所有任务都被完成，则调度成功。