当前位置：首页 > article >正文

调度算法-先来先服务

article 2024/10/12 3:07:11

一、FCFS调度算法概述

**先来先服务（First-Come, First-Served，FCFS）**调度算法是操作系统中最简单、最基本的进程调度算法之一。它按照进程到达就绪队列的先后顺序来调度进程，即先到达的进程先被分配CPU资源进行执行。

1. 工作机制

队列结构：FCFS算法通常使用**先进先出（FIFO）**队列来管理就绪进程。
调度策略：当CPU空闲时，从就绪队列的头部取出第一个进程，将其分配给CPU执行，直到该进程完成或发生阻塞。
不可抢占：一旦进程获得CPU控制权，除非其主动释放（完成或阻塞），否则不会被其他进程抢占。

2. 特点

简单易实现：算法逻辑简单，易于理解和实现。
公平性：所有进程按照到达顺序被调度，没有优先级差别。
等待时间可能较长：短进程可能需要等待前面的长进程完成，导致平均等待时间增加。

二、FCFS算法的优缺点

1. 优点

实现简单：无需复杂的数据结构和调度逻辑。
无饥饿现象：所有进程都会被执行，避免了长时间得不到调度的问题。
适用于批处理系统：在需要顺序执行任务的场景下表现良好。

2. 缺点

平均等待时间长：短进程可能等待长进程完成后才能执行，导致响应时间增加。
缺乏灵活性：无法根据进程的重要性或紧急程度调整调度顺序。
不适合交互式系统：在需要快速响应的系统中，FCFS算法的性能较差。

三、通过编程实现理解FCFS算法

编程实现FCFS调度算法有助于深入理解其工作机制和对系统性能的影响。通过模拟，可以观察到算法在不同场景下的行为，并计算关键性能指标。

1. 数据输入

进程信息：每个进程至少包含以下属性：
- PID：进程标识符，唯一确定一个进程。
- 到达时间（Arrival Time）：进程进入就绪队列的时间。
- 服务时间（Burst Time）：进程需要的CPU执行时间。

2. 处理流程

进程排序：按照到达时间对进程列表进行升序排序。
模拟调度：
- 初始化当前时间current_time为0。
- 遍历排序后的进程列表，对于每个进程：
  - 如果current_time小于进程的到达时间，表示CPU空闲，需要等待进程到达：
  - 记录进程的开始执行时间start_time：
  - 计算进程的完成时间finish_time：
  - 计算周转时间turnaround_time：
  - 计算带权周转时间weighted_turnaround_time：
  - 更新当前时间current_time为进程的完成时间finish_time，为下一个进程的调度做准备。
结果输出：将每个进程的调度信息以表格形式输出，方便分析。

3. 性能指标计算

周转时间（Turnaround Time）：进程从到达到完成所经历的时间。
带权周转时间（Weighted Turnaround Time）：周转时间与服务时间的比值，衡量进程等待的相对时间。
平均周转时间和平均带权周转时间：所有进程的周转时间和带权周转时间的平均值，反映整体系统性能。

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

typedef struct {
    int pid;                // 进程ID
    int arrival_time;       // 到达时间
    int burst_time;         // 服务时间（CPU执行时间）
    int start_time;         // 开始执行时间
    int finish_time;        // 完成时间
    int turnaround_time;    // 周转时间
    float weighted_turnaround_time; // 带权周转时间
} Process;

int compare_arrival_time(const void *a, const void *b) {
    Process *p1 = (Process *)a;
    Process *p2 = (Process *)b;
    return p1->arrival_time - p2->arrival_time;
}

void FCFS_scheduling(Process *processes, int n) {
    qsort(processes, n, sizeof(Process), compare_arrival_time);
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        if (current_time < processes[i].arrival_time) {
            current_time = processes[i].arrival_time;
        }
        processes[i].start_time = current_time;
        processes[i].finish_time = current_time + processes[i].burst_time;
        processes[i].turnaround_time = processes[i].finish_time - processes[i].arrival_time;
        processes[i].weighted_turnaround_time = (float)processes[i].turnaround_time / processes[i].burst_time;
        current_time = processes[i].finish_time;
    }
}

void print_result(Process *processes, int n) {
    int total_turnaround_time = 0;
    float total_weighted_turnaround_time = 0.0;
    printf("PID\t到达时间\t服务时间\t开始时间\t完成时间\t周转时间\t带权周转时间\n");
    for (int i = 0; i < n; i++) {
        total_turnaround_time += processes[i].turnaround_time;
        total_weighted_turnaround_time += processes[i].weighted_turnaround_time;
        printf("%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%.2f\n",
               processes[i].pid,
               processes[i].arrival_time,
               processes[i].burst_time,
               processes[i].start_time,
               processes[i].finish_time,
               processes[i].turnaround_time,
               processes[i].weighted_turnaround_time);
    }
    printf("平均周转时间: %.2f\n", (float)total_turnaround_time / n);
    printf("平均带权周转时间: %.2f\n", total_weighted_turnaround_time / n);
}

int main() {
    int n;
    printf("请输入进程数目: ");
    scanf("%d", &n);
    Process *processes = (Process *)malloc(n * sizeof(Process));
    for (int i = 0; i < n; i++) {
        processes[i].pid = i + 1;
        printf("请输入进程%d的到达时间: ", processes[i].pid);
        scanf("%d", &processes[i].arrival_time);
        printf("请输入进程%d的服务时间: ", processes[i].pid);
        scanf("%d", &processes[i].burst_time);
    }
    FCFS_scheduling(processes, n);
    print_result(processes, n);
    free(processes);
    return 0;
}

代码说明

1. 数据结构定义

typedef struct {
    int pid;                // 进程ID
    int arrival_time;       // 到达时间
    int burst_time;         // 服务时间
    int start_time;         // 开始执行时间
    int finish_time;        // 完成时间
    int turnaround_time;    // 周转时间
    float weighted_turnaround_time; // 带权周转时间
} Process;

使用结构体Process来表示一个进程的各种属性。

2. 进程排序函数

int compare_arrival_time(const void *a, const void *b) {
    Process *p1 = (Process *)a;
    Process *p2 = (Process *)b;
    return p1->arrival_time - p2->arrival_time;
}

使用qsort函数对进程按照到达时间进行排序，需要提供比较函数compare_arrival_time。

3. FCFS调度函数

void FCFS_scheduling(Process *processes, int n) {
    qsort(processes, n, sizeof(Process), compare_arrival_time);
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        if (current_time < processes[i].arrival_time) {
            current_time = processes[i].arrival_time;
        }
        processes[i].start_time = current_time;
        processes[i].finish_time = current_time + processes[i].burst_time;
        processes[i].turnaround_time = processes[i].finish_time - processes[i].arrival_time;
        processes[i].weighted_turnaround_time = (float)processes[i].turnaround_time / processes[i].burst_time;
        current_time = processes[i].finish_time;
    }
}

排序：首先按照到达时间对进程进行排序。
调度：遍历每个进程，按照FCFS算法进行调度，计算各项指标。

4. 结果输出函数

void print_result(Process *processes, int n) {
    int total_turnaround_time = 0;
    float total_weighted_turnaround_time = 0.0;
    printf("PID\t到达时间\t服务时间\t开始时间\t完成时间\t周转时间\t带权周转时间\n");
    for (int i = 0; i < n; i++) {
        total_turnaround_time += processes[i].turnaround_time;
        total_weighted_turnaround_time += processes[i].weighted_turnaround_time;
        printf("%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%.2f\n",
               processes[i].pid,
               processes[i].arrival_time,
               processes[i].burst_time,
               processes[i].start_time,
               processes[i].finish_time,
               processes[i].turnaround_time,
               processes[i].weighted_turnaround_time);
    }
    printf("平均周转时间: %.2f\n", (float)total_turnaround_time / n);
    printf("平均带权周转时间: %.2f\n", total_weighted_turnaround_time / n);
}

累加计算：计算总的周转时间和总的带权周转时间。
输出结果：以表格形式输出每个进程的调度结果。

5. 主函数

void print_result(Process *processes, int n) {
    int total_turnaround_time = 0;
    float total_weighted_turnaround_time = 0.0;
    printf("PID\t到达时间\t服务时间\t开始时间\t完成时间\t周转时间\t带权周转时间\n");
    for (int i = 0; i < n; i++) {
        total_turnaround_time += processes[i].turnaround_time;
        total_weighted_turnaround_time += processes[i].weighted_turnaround_time;
        printf("%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%.2f\n",
               processes[i].pid,
               processes[i].arrival_time,
               processes[i].burst_time,
               processes[i].start_time,
               processes[i].finish_time,
               processes[i].turnaround_time,
               processes[i].weighted_turnaround_time);
    }
    printf("平均周转时间: %.2f\n", (float)total_turnaround_time / n);
    printf("平均带权周转时间: %.2f\n", total_weighted_turnaround_time / n);
}

结果：

进程	开始时间	完成时间	周转时间	带权周转时间
P1	0	5	5	1.0
P2	5	8	6	2.0
P3	8	10	6	3.0

平均周转时间：(5 + 6 + 6) / 3 = 5.67

平均带权周转时间：(1.0 + 2.0 + 3.0) / 3 = 2.0

四、总结

通过编程模拟，我们可以直观地看到FCFS算法对进程调度的影响：

内存分配：动态分配存储进程的数组。
数据输入：从用户输入获取每个进程的到达时间和服务时间。
调度和输出：调用FCFS_scheduling和print_result函数。
内存释放：使用free释放动态分配的内存。
4. 示例分析
示例数据：

进程到达时间服务时间
P1 0 5
P2 2 3
P3 4 2
调度过程：
初始状态：current_time = 0，按到达时间排序后的进程队列为[P1, P2, P3]。
调度P1：
- current_time (0) >= P1.arrival_time (0)，P1开始执行。
- P1.start_time = 0。
- P1.finish_time = 0 + 5 = 5。
- P1.turnaround_time = 5 - 0 = 5。
- P1.weighted_turnaround_time = 5 / 5 = 1.0。
- 更新current_time = 5。
调度P2：
- current_time (5) >= P2.arrival_time (2)，P2开始执行。
- P2.start_time = 5。
- P2.finish_time = 5 + 3 = 8。
- P2.turnaround_time = 8 - 2 = 6。
- P2.weighted_turnaround_time = 6 / 3 = 2.0。
- 更新current_time = 8。
调度P3：
- current_time (8) >= P3.arrival_time (4)，P3开始执行。
- P3.start_time = 8。
- P3.finish_time = 8 + 2 = 10。
- P3.turnaround_time = 10 - 4 = 6。
- P3.weighted_turnaround_time = 6 / 2 = 3.0。
- 更新current_time = 10。
短进程等待长进程：P2和P3的服务时间较短，但由于P1的存在，它们需要等待较长时间。
平均周转时间较高：由于等待时间增加，导致平均周转时间和带权周转时间增大。
改进空间：引出对其他调度算法的探索，如短作业优先（SJF）、最短剩余时间优先（SRTF）等，以改善系统性能。