操作系统4种进程调度算法（c语言） |
您所在的位置：网站首页 › 进程调度实验代码c语言 › 操作系统4种进程调度算法（c语言） |
|
目录 FCFS SJF HPF RR FCFS FCFS（First-Come, First-Served）调度算法是一种最简单的进程调度算法，也被称为先来先服务算法。在这种算法中，进程按照它们到达就绪队列的顺序依次执行，即先到达的进程先执行，后到达的进程排队等待。 基本原则是按照进程到达的顺序，逐个地将它们分配给 CPU，直到所有进程都执行完毕。这意味着在FCFS算法中，不考虑进程的执行时间长短或优先级高低，仅仅按照它们进入就绪队列的先后顺序进行调度。 尽管FCFS算法简单，易于理解，但它也有一些缺点。其中一个主要问题是平均等待时间可能较长，尤其是当一些短进程在一些长进程之后到达时。这可能导致低效的利用 CPU 时间，因为较长的进程可能会占用 CPU 较长时间，而其他进程等待的时间较长。 FCFS算法是一种非抢占式调度算法，因为一旦进程开始执行，它将一直运行直到完成，或者直到被更高优先级的进程抢占。 #include #include #include // 定义进程结构体 typedef struct { char name[10]; int enter_time; int running_time; } Program; // 定义就绪队列结构体 typedef struct { Program **programs; int size; int capacity; } ProgramQueue; // 初始化就绪队列 void InitializeQueue(ProgramQueue *queue, int capacity) { queue->programs = (Program **)malloc(capacity * sizeof(Program *)); queue->size = 0; queue->capacity = capacity; } // 将进程加入队列 void EnterQueue(ProgramQueue *queue, Program *program) { if (queue->size < queue->capacity) { queue->programs[queue->size] = program; queue->size++; } } // 从队列中取出进程 Program *PollQueue(ProgramQueue *queue) { if (queue->size > 0) { Program *program = queue->programs[0]; for (int i = 1; i < queue->size; i++) { queue->programs[i - 1] = queue->programs[i]; } queue->size--; return program; } return NULL; } // 执行FCFS调度 void FCFS(Program pro[], int num) { printf("进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n"); // 按照到达时间排序 ProgramQueue queue; InitializeQueue(&queue, num); EnterQueue(&queue, &pro[0]); int time = pro[0].enter_time; int pronum = 1; float sum_T_time = 0, sum_QT_time = 0; while (queue.size > 0) { Program *curpro = PollQueue(&queue); if (time < curpro->enter_time) { time = curpro->enter_time; } int done_time = time + curpro->running_time; int T_time = done_time - curpro->enter_time; sum_T_time += T_time; float QT_time = (float)T_time / curpro->running_time; sum_QT_time += QT_time; printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time); time += curpro->running_time; // 进程模拟执行过程 while (pronum < num && pro[pronum].enter_time programs = (Program **)malloc(capacity * sizeof(Program *)); queue->size = 0; queue->capacity = capacity; } // 将进程加入队列 void EnterQueue(ProgramQueue *queue, Program *program) { if (queue->size < queue->capacity) { queue->programs[queue->size] = program; queue->size++; } } // 从队列中取出进程 Program *PollQueue(ProgramQueue *queue) { if (queue->size > 0) { Program *program = queue->programs[0]; for (int i = 1; i < queue->size; i++) { queue->programs[i - 1] = queue->programs[i]; } queue->size--; return program; } return NULL; } // 按服务时间排序的比较函数 int CompareByRunningTime(const void *a, const void *b) { return ((Program *)a)->running_time - ((Program *)b)->running_time; } // 执行SJF调度 void SJF(Program pro[], int num) { printf("进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n"); // 按照服务时间排序 qsort(pro, num, sizeof(Program), CompareByRunningTime); ProgramQueue queue; InitializeQueue(&queue, num); int time = 0; int pronum = 0; float sum_T_time = 0, sum_QT_time = 0; while (pronum < num || queue.size > 0) { while (pronum < num && pro[pronum].enter_time 0) { Program *curpro = PollQueue(&queue); int done_time = time + curpro->running_time; int T_time = done_time - curpro->enter_time; sum_T_time += T_time; float QT_time = (float)T_time / curpro->running_time; sum_QT_time += QT_time; printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time); time += curpro->running_time; } else { time = pro[pronum].enter_time; } } printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n", sum_T_time / num, sum_QT_time / num); } int main() { int num = 3; // 假设有3个进程 // 初始化进程数组 Program pro[num]; strcpy(pro[0].name, "P1"); pro[0].enter_time = 0; pro[0].running_time = 5; strcpy(pro[1].name, "P2"); pro[1].enter_time = 1; pro[1].running_time = 3; strcpy(pro[2].name, "P3"); pro[2].enter_time = 3; pro[2].running_time = 6; // 调用SJF函数 SJF(pro, num); return 0; } HPF高优先级先执行（High Priority First, HPF）调度算法是一种基于进程优先级的调度策略。该算法根据进程的优先级来决定下一个执行的进程。优先级越高的进程将优先执行，以确保更重要或紧急的任务能够尽快得到处理。 每个进程都被赋予一个优先级值，通常是一个整数。较小的优先级值表示较高的优先级，而较大的值表示较低的优先级。在每个调度点，系统选择具有最高优先级的就绪进程来执行。这确保了具有更高优先级的任务能够更快地获得处理。HPF 调度算法可以是抢占性的或非抢占性的。抢占性的 HPF 允许正在执行的进程被更高优先级的进程中断，以便立即执行更高优先级的任务。当进程到达时，将其插入到就绪队列中，按照优先级进行排序。具有更高优先级的进程将在队列的前部。在每个时间片或事件发生时，选择就绪队列中具有最高优先级的进程执行。执行完毕后，继续选择下一个最高优先级的就绪进程。 需要注意，过度依赖高优先级可能导致低优先级任务长时间等待，产生饥饿（starvation）现象。因此，在设计调度算法时，需要平衡对高优先级任务的服务和对低优先级任务的公平性。 #include #include #include // 定义进程结构体 typedef struct { char name[10]; int enter_time; int running_time; int priority; } Program; // 定义就绪队列结构体 typedef struct { Program **programs; int size; int capacity; } ProgramQueue; // 初始化就绪队列 void InitializeQueue(ProgramQueue *queue, int capacity) { queue->programs = (Program **)malloc(capacity * sizeof(Program *)); queue->size = 0; queue->capacity = capacity; } // 将进程加入队列 void EnterQueue(ProgramQueue *queue, Program *program) { if (queue->size < queue->capacity) { queue->programs[queue->size] = program; queue->size++; } } // 从队列中取出进程 Program *PollQueue(ProgramQueue *queue) { if (queue->size > 0) { Program *program = queue->programs[0]; for (int i = 1; i < queue->size; i++) { queue->programs[i - 1] = queue->programs[i]; } queue->size--; return program; } return NULL; } // 按优先级排序的比较函数 int CompareByPriority(const void *a, const void *b) { return ((Program *)a)->priority - ((Program *)b)->priority; } // 执行HPF调度 void HPF(Program pro[], int num) { printf("进程 到达时间 服务时间 优先级 开始时间 完成时间 周转时间 带权周转时间\n"); // 按照优先级排序 qsort(pro, num, sizeof(Program), CompareByPriority); ProgramQueue queue; InitializeQueue(&queue, num); int time = 0; int pronum = 0; float sum_T_time = 0, sum_QT_time = 0; while (pronum < num || queue.size > 0) { while (pronum < num && pro[pronum].enter_time 0) { Program *curpro = PollQueue(&queue); int done_time = time + curpro->running_time; int T_time = done_time - curpro->enter_time; sum_T_time += T_time; float QT_time = (float)T_time / curpro->running_time; sum_QT_time += QT_time; printf("%s\t%d\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, curpro->priority, time, done_time, T_time, QT_time); time += curpro->running_time; } else { time = pro[pronum].enter_time; } } printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n", sum_T_time / num, sum_QT_time / num); } int main() { int num = 3; // 假设有3个进程 // 初始化进程数组 Program pro[num]; strcpy(pro[0].name, "P1"); pro[0].enter_time = 0; pro[0].running_time = 5; pro[0].priority = 3; strcpy(pro[1].name, "P2"); pro[1].enter_time = 1; pro[1].running_time = 3; pro[1].priority = 1; strcpy(pro[2].name, "P3"); pro[2].enter_time = 3; pro[2].running_time = 6; pro[2].priority = 2; // 调用HPF函数 HPF(pro, num); return 0; } RR轮转调度算法（Round Robin Scheduling）是一种常见的操作系统调度算法之一，它通过给每个进程分配一个时间片（时间量），然后按照轮转的方式依次执行每个进程，直到完成或者时间片用尽。 #include #include #include // 定义进程结构体 typedef struct { char name[10]; int arrival_time; int burst_time; int remaining_time; } Process; // 定义就绪队列结构体 typedef struct { Process **processes; int size; int capacity; } ProcessQueue; // 初始化就绪队列 void InitializeQueue(ProcessQueue *queue, int capacity) { queue->processes = (Process **)malloc(capacity * sizeof(Process *)); queue->size = 0; queue->capacity = capacity; } // 将进程加入队列 void EnterQueue(ProcessQueue *queue, Process *process) { if (queue->size < queue->capacity) { queue->processes[queue->size] = process; queue->size++; } } // 从队列中取出进程 Process *PollQueue(ProcessQueue *queue) { if (queue->size > 0) { Process *process = queue->processes[0]; for (int i = 1; i < queue->size; i++) { queue->processes[i - 1] = queue->processes[i]; } queue->size--; return process; } return NULL; } // 轮转调度函数 void RoundRobin(Process processes[], int num_processes, int time_slice) { printf("进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n"); // 初始化就绪队列 ProcessQueue queue; InitializeQueue(&queue, num_processes); int time = 0; int remaining_processes = num_processes; while (remaining_processes > 0) { for (int i = 0; i < num_processes; ++i) { if (processes[i].arrival_time 0) { // 进程可执行 EnterQueue(&queue, &processes[i]); } } if (queue.size > 0) { Process *current_process = PollQueue(&queue); // 执行进程 int execution_time = (current_process->remaining_time remaining_time : time_slice; printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", current_process->name, current_process->arrival_time, current_process->burst_time, time, time + execution_time, time + execution_time - current_process->arrival_time, (float)(time + execution_time - current_process->arrival_time) / current_process->burst_time); // 更新进程信息 current_process->remaining_time -= execution_time; time += execution_time; // 将未执行完的进程重新加入队列 if (current_process->remaining_time > 0) { EnterQueue(&queue, current_process); } else { --remaining_processes; } } else { // 等待下一个进程到达 time++; } } printf("轮转调度算法完成.\n"); } int main() { int num_processes = 3; int time_slice = 2; // 初始化进程数组 Process processes[num_processes]; strcpy(processes[0].name, "P1"); processes[0].arrival_time = 0; processes[0].burst_time = 5; processes[0].remaining_time = processes[0].burst_time; strcpy(processes[1].name, "P2"); processes[1].arrival_time = 1; processes[1].burst_time = 3; processes[1].remaining_time = processes[1].burst_time; strcpy(processes[2].name, "P3"); processes[2].arrival_time = 3; processes[2].burst_time = 6; processes[2].remaining_time = processes[2].burst_time; // 调用轮转调度函数 RoundRobin(processes, num_processes, time_slice); return 0; }
|
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |