用C语言写一个多级反馈队列调度算法

下面是一个使用C语言实现多级反馈队列调度算法的示例：

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

#define MAX_QUEUE_SIZE 100
#define MAX_LEVELS 3

typedef struct process {
    int id;
    int burst_time;
    int remaining_time;
    int level;
} process_t;

typedef struct queue {
    int front;
    int rear;
    int size;
    process_t* processes[MAX_QUEUE_SIZE];
} queue_t;

queue_t* create_queue() {
    queue_t* queue = (queue_t*) malloc(sizeof(queue_t));
    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
    return queue;
}

bool is_empty(queue_t* queue) {
    return queue->size == 0;
}

bool is_full(queue_t* queue) {
    return queue->size == MAX_QUEUE_SIZE;
}

void enqueue(queue_t* queue, process_t* process) {
    if (is_full(queue)) {
        printf("Error: Queue is full\n");
        return;
    }
    
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    queue->processes[queue->rear] = process;
    queue->size++;
}

process_t* dequeue(queue_t* queue) {
    if (is_empty(queue)) {
        printf("Error: Queue is empty\n");
        return NULL;
    }
    
    process_t* process = queue->processes[queue->front];
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    queue->size--;
    return process;
}

process_t* create_process(int id, int burst_time, int level) {
    process_t* process = (process_t*) malloc(sizeof(process_t));
    process->id = id;
    process->burst_time = burst_time;
    process->remaining_time = burst_time;
    process->level = level;
    return process;
}

void run_processes(queue_t** queues, int num_queues) {
    int time_quantum[MAX_LEVELS] = {4, 8, 16};
    int current_time = 0;
    int current_level = 0;
    
    while (true) {
        bool all_queues_empty = true;
        
        for (int i = current_level; i < num_queues; i++) {
            if (!is_empty(queues[i])) {
                all_queues_empty = false;
                break;
            }
        }
        
        if (all_queues_empty) {
            break;
        }
        
        process_t* current_process = dequeue(queues[current_level]);
        
        if (current_process != NULL) {
            printf("Time %d: Running process %d from level %d\n", current_time, current_process->id, current_process->level);
            
            if (current_process->remaining_time <= time_quantum[current_level]) {
                current_time += current_process->remaining_time;
                current_process->remaining_time = 0;
            } else {
                current_time += time_quantum[current_level];
                current_process->remaining_time -= time_quantum[current_level];
            }
            
            if (current_process->remaining_time == 0) {
                printf("Time %d: Process %d completed\n", current_time, current_process->id);
                free(current_process);
            } else {
                int next_level = current_level + 1;
                
                if (next_level < num_queues) {
                    printf("Time %d: Process %d demoted to level %d\n", current_time, current_process->id, next_level);
                    current_process->level = next_level;
                    enqueue(queues[next_level], current_process);
                } else {
                    printf("Time %d: Process %d continues in level %d\n", current_time, current_process->id, current_level);
                    enqueue(queues[current_level], current_process);
                }
            }
        }
        
        current_level = (current_level + 1) % num_queues;
    }
}

int main() {
    queue_t* queues[MAX_LEVELS];
    
    for (int i = 0; i < MAX_LEVELS; i++) {
        queues[i] = create_queue();
    }
    
    enqueue(queues[0], create_process(1, 12, 0));
    enqueue(queues[0], create_process(2, 8, 0));
    enqueue(queues[0], create_process(3, 6, 0));
    enqueue(queues[0], create_process(4, 4, 0));
    
    run_processes(queues, MAX_LEVELS);
    
    for (int i = 0; i < MAX_LEVELS; i++) {
        free(queues[i]);
    }
    
    return 0;
}

这个程序使用了一个包含三个队列的多级反馈队列调度算法，每个队列的时间片大小依次为4、8和16，每个队列的优先级依次递减。在主函数中，我们创建了四个进程并将它们加入第一个队列中，然后调用run_processes函数来运行它们。运行过程中，程序会输出每个进程的执行情况，包括进程编号、所在队列、开始时间、结束时间等信息。最后，我们释放了创建的所有队列和进程。