多级反馈队列调度算法的基本思想是:当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度。当轮到该进程执行时,如能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行,以此类推,用链表指针实现。给出c语言代码
时间: 2024-03-24 09:38:48 浏览: 133
多级反馈队列调度C语言
以下是一个使用链表指针实现多级反馈队列调度算法的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_TIME_SLICE 4
typedef struct Process {
int pid; // 进程ID
int arrival_time; // 到达时间
int burst_time; // 执行时间
int remaining_time; // 剩余执行时间
int queue_level; // 队列级别
struct Process *next; // 指向下一个进程的指针
} process;
// 将进程插入队列尾部
void enqueue(process *p, process **rear) {
if (*rear == NULL) {
*rear = p;
} else {
process *temp = *rear;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = p;
}
}
// 将队列头部进程出队
process *dequeue(process **front, process **rear) {
process *p = *front;
if (*front == NULL) {
*rear = NULL;
} else {
*front = (*front)->next;
}
return p;
}
int main() {
process *processes = NULL;
int n, i, j, time = 0, flag = 0;
int time_quantum[MAX_PROCESS_NUM] = { 0 }; // 时间片
int queue_level_num = 3; // 队列数
process *queues[queue_level_num] = { NULL }; // 队列数组
printf("请输入进程数:");
scanf("%d", &n);
// 输入每个进程的信息
for (i = 0; i < n; i++) {
process *p = (process *) malloc(sizeof(process));
printf("请输入进程%d的到达时间和执行时间:", i);
scanf("%d %d", &p->arrival_time, &p->burst_time);
p->pid = i;
p->remaining_time = p->burst_time;
p->queue_level = 0;
time_quantum[i] = MAX_TIME_SLICE; // 初始化时间片
enqueue(p, &processes); // 将进程加入到进程列表中
}
// 多级反馈队列调度算法
while (flag < n) {
// 将到达时间小于等于当前时间的进程加入第一级队列
process *p = processes;
while (p != NULL) {
if (p->arrival_time <= time && p->queue_level == 0) {
enqueue(p, &queues[0]);
p->queue_level = 1;
}
p = p->next;
}
// 遍历所有队列,执行队列中的进程
for (i = 0; i < queue_level_num; i++) {
process *front = queues[i];
process *rear = queues[i];
// 如果队列为空,跳过
if (front == NULL) {
continue;
}
// 取出队列头部进程
process *p = dequeue(&front, &rear);
// 执行该进程
if (p->remaining_time <= time_quantum[p->pid]) {
time += p->remaining_time;
p->remaining_time = 0;
printf("进程%d在时间%d时执行完毕\n", p->pid, time);
flag++;
} else {
time += time_quantum[p->pid];
p->remaining_time -= time_quantum[p->pid];
printf("进程%d在时间%d时执行完一个时间片\n", p->pid, time);
// 将该进程加入下一级队列
p->queue_level++;
enqueue(p, &queues[p->queue_level]);
}
// 更新队列头尾指针
queues[i] = front;
if (rear != NULL) {
rear->next = NULL;
}
}
}
// 释放进程列表中的所有进程
process *p = processes;
while (p != NULL) {
processes = p->next;
free(p);
p = processes;
}
return 0;
}
```
注意事项:
1. 在使用链表指针实现多级反馈队列调度算法时,需要为每个进程定义一个 `next` 指针,以便将其加入到队列中或从队列中移除。
2. 在每个进程被加入队列时,都将其 `queue_level` 属性设为 0,即初始加入第一级队列。随着进程被调度,其 `queue_level` 属性逐渐增加,直到完成执行。
3. 在代码实现中,使用了一个数组 `time_quantum` 来保存每个进程的时间片,以便在进程被调度时能够正确地选择执行时间。
阅读全文