如何用C语言实现多级反馈队列调度算法

多级反馈队列调度算法（Multilevel Feedback Queue Scheduling Algorithm）是一种常见的进程调度算法。实现多级反馈队列调度算法的思路是：将进程分成若干级别，每个级别使用不同的时间片大小，优先级较高的进程使用较小的时间片，优先级较低的进程使用较大的时间片，同时，每个级别内部使用先进先出（FIFO）队列进行调度。

在C语言中实现多级反馈队列调度算法，需要定义进程结构体、就绪队列、运行队列等数据结构，同时，使用循环和条件语句实现进程调度的逻辑。具体实现过程包括以下步骤：

1. 定义进程结构体：包括进程名称、进程状态、优先级等属性。

2. 初始化多个就绪队列：根据设定的进程级别，初始化多个就绪队列。可以使用数组或链表等数据结构来存储就绪队列。

3. 将进程加入就绪队列：在进程创建或者进程状态转换时，将进程加入对应的就绪队列。

4. 实现调度函数：根据多级反馈队列调度算法的逻辑，实现调度函数，即选择优先级最高或等级最高的进程进行调度，如果进程未完成，则将该进程插入到合适的下一级就绪队列中，继续等待调度。

5. 实现时间片轮转：在进程使用时间片用完或者进程等待时间过长时，使用时间片轮转（Round-Robin）算法，将该进程插入到下一个就绪队列中，等待调度。

6. 实现进程挂起和恢复：在某些特定情况下，需要将进程挂起或恢复，例如I/O操作等。这个可以通过修改进程状态和队列中进程位置来实现。

总体来说，C语言实现多级反馈队列调度算法需要灵活运用数据结构和逻辑控制，正确处理进程状态和就绪队列，使得系统的进程调度可靠高效。

相关问题

用C语言实现多级反馈队列调度算法，要求设置不少于5个反馈队列，并通过菜单输入反馈队列的个数 优先级、时间片长度，以及其他补充的参数(加分项)。 要求完成以下功能： (1)输入各个进程的进入时间和估计运行时间。 (2)计算各个进程的开始时间、结束时间、周转时间、带权周转时间，平均周转时间、平均带权周转时间，并直观输出显示。 (3)要求动态演示各个进程的运行情况状态 以及各个队列的运行情况。

以下是一个用C语言实现多级反馈队列调度算法的示例代码，其中包括输入进程信息、计算各个进程的运行情况和动态演示的功能：

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

#define MAX_QUEUE_SIZE 100 //每个队列的最大长度

// 进程结构体
typedef struct {
    int pid; // 进程ID
    int arrival; // 到达时间
    int burst; // 估计运行时间
    int start; // 开始时间
    int finish; // 结束时间
    int turnaround; // 周转时间
    float weight_turnaround; // 带权周转时间
    int queue_level; // 进程所在的队列级别
    int remaining; // 剩余运行时间
} Process;

// 队列结构体
typedef struct {
    Process queue[MAX_QUEUE_SIZE]; // 队列数组
    int front, rear; // 队首和队尾指针
    int level; // 队列级别
    int time_slice; // 时间片长度
} Queue;

// 初始化队列
void init_queue(Queue *q, int level, int time_slice) {
    q->front = q->rear = 0;
    q->level = level;
    q->time_slice = time_slice;
}

// 判断队列是否为空
bool is_queue_empty(Queue *q) {
    return q->front == q->rear;
}

// 判断队列是否已满
bool is_queue_full(Queue *q) {
    return q->rear == MAX_QUEUE_SIZE;
}

// 入队操作
void enqueue(Queue *q, Process process) {
    if (is_queue_full(q)) {
        printf("队列已满，无法入队！\n");
        return;
    }
    q->queue[q->rear++] = process;
}

// 出队操作
Process dequeue(Queue *q) {
    if (is_queue_empty(q)) {
        printf("队列为空，无法出队！\n");
        exit(1);
    }
    return q->queue[q->front++];
}

// 获取队首元素
Process get_front(Queue *q) {
    if (is_queue_empty(q)) {
        printf("队列为空，无法获取队首元素！\n");
        exit(1);
    }
    return q->queue[q->front];
}

// 更新进程状态
void update_process_state(Process *process, int time) {
    process->remaining -= time;
    if (process->remaining <= 0) {
        process->finish = time + process->burst - process->remaining;
        process->turnaround = process->finish - process->arrival;
        process->weight_turnaround = (float)process->turnaround / process->burst;
    }
}

// 模拟多级反馈队列调度算法
void mfqs(Process *processes, int n, int queue_num, int *queue_levels, int *time_slices) {
    // 初始化队列
    Queue queues[queue_num];
    for (int i = 0; i < queue_num; i++) {
        init_queue(&queues[i], queue_levels[i], time_slices[i]);
    }

    int time = 0; // 当前时间
    int finished = 0; // 已完成进程数
    int current_queue = 0; // 当前队列编号

    // 不断循环，直到所有进程都完成
    while (finished < n) {
        // 将到达时间小于等于当前时间的进程加入第一个队列
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival <= time && processes[i].remaining > 0) {
                processes[i].queue_level = 0;
                enqueue(&queues[0], processes[i]);
            }
        }

        // 如果当前队列为空，则跳转到下一个队列
        while (is_queue_empty(&queues[current_queue])) {
            current_queue = (current_queue + 1) % queue_num;
        }

        // 取出队首进程
        Process current_process = dequeue(&queues[current_queue]);

        // 更新进程状态
        int time_slice = queues[current_queue].time_slice;
        if (current_process.remaining > time_slice) {
            update_process_state(&current_process, time_slice);
            current_process.queue_level = (current_queue + 1) % queue_num;
            enqueue(&queues[current_process.queue_level], current_process);
        } else {
            update_process_state(&current_process, current_process.remaining);
            finished++;
        }

        // 更新当前时间
        time += time_slice;

        // 打印进程运行情况和队列状态
        printf("时间：%d 进程%d 运行%dms 队列%d\n", time, current_process.pid, time_slice, current_queue);
        printf("队列状态：\n");
        for (int i = 0; i < queue_num; i++) {
            printf("  队列%d：", i);
            for (int j = queues[i].front; j < queues[i].rear; j++) {
                printf(" %d", queues[i].queue[j].pid);
            }
            printf("\n");
        }
    }

    // 计算平均周转时间和平均带权周转时间
    float avg_turnaround = 0;
    float avg_weight_turnaround = 0;
    for (int i = 0; i < n; i++) {
        avg_turnaround += processes[i].turnaround;
        avg_weight_turnaround += processes[i].weight_turnaround;
    }
    avg_turnaround /= n;
    avg_weight_turnaround /= n;

    // 打印每个进程的运行情况和平均周转时间、平均带权周转时间
    printf("\n进程运行情况：\n");
    printf("进程ID 到达时间 运行时间 周转时间 带权周转时间\n");
    for (int i = 0; i < n; i++) {
        Process p = processes[i];
        printf("%4d %8d %8d %8d %16.2f\n", p.pid, p.arrival, p.burst, p.turnaround, p.weight_turnaround);
    }
    printf("平均周转时间：%0.2f\n", avg_turnaround);
    printf("平均带权周转时间：%0.2f\n", avg_weight_turnaround);
}

int main() {
    int n, queue_num;
    printf("请输入进程数：");
    scanf("%d", &n);

    Process *processes = (Process *)malloc(sizeof(Process) * n);

    // 输入进程信息
    for (int i = 0; i < n; i++) {
        printf("请输入进程%d的到达时间和运行时间：", i + 1);
        scanf("%d%d", &processes[i].arrival, &processes[i].burst);
        processes[i].pid = i + 1;
        processes[i].start = processes[i].finish = -1;
        processes[i].turnaround = 0;
        processes[i].weight_turnaround = 0;
        processes[i].remaining = processes[i].burst;
    }

    printf("\n请输入反馈队列的个数：");
    scanf("%d", &queue_num);

    int *queue_levels = (int *)malloc(sizeof(int) * queue_num);
    int *time_slices = (int *)malloc(sizeof(int) * queue_num);

    // 输入队列信息
    for (int i = 0; i < queue_num; i++) {
        printf("请输入第%d个队列的优先级和时间片长度：", i + 1);
        scanf("%d%d", &queue_levels[i], &time_slices[i]);
    }

    // 执行多级反馈队列调度算法
    mfqs(processes, n, queue_num, queue_levels, time_slices);

    // 释放内存
    free(processes);
    free(queue_levels);
    free(time_slices);

    return 0;
}

在这个示例中，我们首先定义了进程结构体和队列结构体，然后实现了队列的初始化、入队、出队等基本操作，并在此基础上实现了多级反馈队列调度算法。在算法的实现过程中，我们不断循环，将到达时间小于等于当前时间的进程加入第一个队列，然后从当前队列中取出队首进程进行运行。如果该进程的剩余运行时间大于时间片长度，则将其放入下一个队列中等待下一次运行；否则，该进程运行结束，将其从队列中删除。在算法执行过程中，我们还实现了动态演示的功能，可以直观地显示各个进程的运行情况状态和各个队列的运行情况。最后，我们计算了每个进程的开始时间、结束时间、周转时间、带权周转时间，并输出了平均周转时间和平均带权周转时间。

用C语言写时间片轮转调度算法和多级反馈队列调度算法

时间片轮转调度算法的C语言实现：

#include <stdio.h>

// 进程控制块结构体
typedef struct PCB{
    int pid;    // 进程ID
    int burst;  // 进程执行时间
    int wait;   // 进程等待时间
    int tat;    // 进程周转时间
    int rt;     // 进程剩余时间
} PCB;

// 时间片轮转调度算法
void RR(PCB *p, int n, int q) {
    int t = 0;  // 记录当前时间
    int done = 0; // 记录已经完成的进程数
    while(done < n) {
        int flag = 0;   // 标记是否有进程在执行
        for(int i = 0; i < n; i++) {
            if(p[i].rt > 0) {   // 判断进程是否还有剩余时间
                flag = 1;   // 标记有进程在执行
                if(p[i].rt > q) {   // 进程还需执行时间大于时间片
                    t += q; // 更新当前时间
                    p[i].rt -= q;   // 更新进程剩余时间
                } else {
                    t += p[i].rt;   // 更新当前时间
                    p[i].wait = t - p[i].burst; // 计算进程等待时间
                    p[i].tat = t;   // 计算进程周转时间
                    p[i].rt = 0;    // 进程已经执行完
                    done++; // 已经完成的进程数+1
                }
            }
        }
        if(flag == 0) break; // 所有进程都已经执行完
    }
    printf("进程ID\t等待时间\t周转时间\n");
    for(int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\n", p[i].pid, p[i].wait, p[i].tat);
    }
}

int main() {
    // 初始化进程控制块
    PCB p[] = {
        {1, 24, 0, 0, 24},
        {2, 3, 0, 0, 3},
        {3, 3, 0, 0, 3}
    };
    int n = sizeof(p) / sizeof(PCB);
    int q = 4;  // 时间片大小
    RR(p, n, q);
    return 0;
}

多级反馈队列调度算法的C语言实现：

#include <stdio.h>

// 进程控制块结构体
typedef struct PCB{
    int pid;    // 进程ID
    int burst;  // 进程执行时间
    int wait;   // 进程等待时间
    int tat;    // 进程周转时间
    int rt;     // 进程剩余时间
    int prio;   // 进程优先级
} PCB;

// 多级反馈队列调度算法
void MFQ(PCB *p, int n, int q1, int q2) {
    int t = 0;  // 记录当前时间
    int done = 0; // 记录已经完成的进程数
    while(done < n) {
        int flag = 0;   // 标记是否有进程在执行
        // 第一级队列，时间片大小为q1
        for(int i = 0; i < n; i++) {
            if(p[i].prio == 1 && p[i].rt > 0) {    // 判断进程是否在第一级队列中
                flag = 1;   // 标记有进程在执行
                if(p[i].rt > q1) {  // 进程还需执行时间大于时间片
                    t += q1; // 更新当前时间
                    p[i].rt -= q1;  // 更新进程剩余时间
                } else {
                    t += p[i].rt;   // 更新当前时间
                    p[i].wait = t - p[i].burst; // 计算进程等待时间
                    p[i].tat = t;   // 计算进程周转时间
                    p[i].rt = 0;    // 进程已经执行完
                    p[i].prio = 2;  // 进程优先级变为第二级
                    done++; // 已经完成的进程数+1
                }
            }
        }
        // 第二级队列，时间片大小为q2
        for(int i = 0; i < n; i++) {
            if(p[i].prio == 2 && p[i].rt > 0) {    // 判断进程是否在第二级队列中
                flag = 1;   // 标记有进程在执行
                if(p[i].rt > q2) {  // 进程还需执行时间大于时间片
                    t += q2; // 更新当前时间
                    p[i].rt -= q2;  // 更新进程剩余时间
                } else {
                    t += p[i].rt;   // 更新当前时间
                    p[i].wait = t - p[i].burst; // 计算进程等待时间
                    p[i].tat = t;   // 计算进程周转时间
                    p[i].rt = 0;    // 进程已经执行完
                    done++; // 已经完成的进程数+1
                }
            }
        }
        if(flag == 0) break; // 所有进程都已经执行完
    }
    printf("进程ID\t等待时间\t周转时间\n");
    for(int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\n", p[i].pid, p[i].wait, p[i].tat);
    }
}

int main() {
    // 初始化进程控制块
    PCB p[] = {
        {1, 10, 0, 0, 10, 1},
        {2, 1, 0, 0, 1, 1},
        {3, 2, 0, 0, 2, 1},
        {4, 1, 0, 0, 1, 1},
        {5, 5, 0, 0, 5, 1},
    };
    int n = sizeof(p) / sizeof(PCB);
    int q1 = 2; // 第一级队列时间片大小
    int q2 = 4; // 第二级队列时间片大小
    MFQ(p, n, q1, q2);
    return 0;
}