083. 编写代码实现简单的操作系统调度算法

在操作系统中，调度算法用于决定哪个进程或线程应该获得CPU资源。常见的调度算法包括先来先服务（FCFS）、最短作业优先（SJF）、轮转调度（RR）和优先级调度等。以下将分别实现这些简单的调度算法。

1. 先来先服务（FCFS）调度算法

先来先服务（FCFS）调度算法是最简单的调度算法，按照进程到达的顺序进行调度。

示例代码：FCFS调度算法

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

typedef struct {
    int processID;
    int arrivalTime;
    int burstTime;
    int completionTime;
    int waitingTime;
    int turnaroundTime;
} Process;

void fcfsScheduling(Process processes[], int n) {
    int currentTime = 0;
    for (int i = 0; i < n; i++) {
        processes[i].completionTime = currentTime + processes[i].burstTime;
        processes[i].waitingTime = currentTime - processes[i].arrivalTime;
        processes[i].turnaroundTime = processes[i].completionTime - processes[i].arrivalTime;
        currentTime = processes[i].completionTime;
    }
}

void printProcesses(Process processes[], int n) {
    printf("PID\tArrival\tBurst\tCompletion\tWaiting\tTurnaround\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\t%d\t%d\t%d\n",
               processes[i].processID,
               processes[i].arrivalTime,
               processes[i].burstTime,
               processes[i].completionTime,
               processes[i].waitingTime,
               processes[i].turnaroundTime);
    }
}

int main() {
    Process processes[] = {
        {1, 0, 5},
        {2, 1, 3},
        {3, 2, 8},
        {4, 3, 6},
        {5, 4, 2}
    };
    int n = sizeof(processes) / sizeof(processes[0]);

    fcfsScheduling(processes, n);
    printProcesses(processes, n);

    return 0;
}

2. 最短作业优先（SJF）调度算法

最短作业优先（SJF）调度算法选择具有最短执行时间的进程进行调度。

示例代码：SJF调度算法

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

typedef struct {
    int processID;
    int arrivalTime;
    int burstTime;
    int completionTime;
    int waitingTime;
    int turnaroundTime;
} Process;

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

void sjfScheduling(Process processes[], int n) {
    qsort(processes, n, sizeof(Process), compare);

    int currentTime = 0;
    for (int i = 0; i < n; i++) {
        processes[i].completionTime = currentTime + processes[i].burstTime;
        processes[i].waitingTime = currentTime - processes[i].arrivalTime;
        processes[i].turnaroundTime = processes[i].completionTime - processes[i].arrivalTime;
        currentTime = processes[i].completionTime;
    }
}

void printProcesses(Process processes[], int n) {
    printf("PID\tArrival\tBurst\tCompletion\tWaiting\tTurnaround\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\t%d\t%d\t%d\n",
               processes[i].processID,
               processes[i].arrivalTime,
               processes[i].burstTime,
               processes[i].completionTime,
               processes[i].waitingTime,
               processes[i].turnaroundTime);
    }
}

int main() {
    Process processes[] = {
        {1, 0, 5},
        {2, 1, 3},
        {3, 2, 8},
        {4, 3, 6},
        {5, 4, 2}
    };
    int n = sizeof(processes) / sizeof(processes[0]);

    sjfScheduling(processes, n);
    printProcesses(processes, n);

    return 0;
}

3. 轮转调度（RR）算法

轮转调度（RR）算法是一种时间片轮转调度算法，每个进程轮流获得一定时间的CPU资源。

示例代码：RR调度算法

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

typedef struct {
    int processID;
    int arrivalTime;
    int burstTime;
    int remainingTime;
    int completionTime;
    int waitingTime;
    int turnaroundTime;
} Process;

void rrScheduling(Process processes[], int n, int timeQuantum) {
    int currentTime = 0;
    int completed = 0;
    while (completed < n) {
        for (int i = 0; i < n; i++) {
            if (processes[i].arrivalTime <= currentTime && processes[i].remainingTime > 0) {
                if (processes[i].remainingTime <= timeQuantum) {
                    currentTime += processes[i].remainingTime;
                    processes[i].remainingTime = 0;
                    processes[i].completionTime = currentTime;
                    processes[i].waitingTime = currentTime - processes[i].arrivalTime - processes[i].burstTime;
                    processes[i].turnaroundTime = currentTime - processes[i].arrivalTime;
                    completed++;
                } else {
                    processes[i].remainingTime -= timeQuantum;
                    currentTime += timeQuantum;
                }
            }
        }
    }
}

void printProcesses(Process processes[], int n) {
    printf("PID\tArrival\tBurst\tCompletion\tWaiting\tTurnaround\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\t%d\t%d\t%d\n",
               processes[i].processID,
               processes[i].arrivalTime,
               processes[i].burstTime,
               processes[i].completionTime,
               processes[i].waitingTime,
               processes[i].turnaroundTime);
    }
}

int main() {
    Process processes[] = {
        {1, 0, 5, 5},
        {2, 1, 3, 3},
        {3, 2, 8, 8},
        {4, 3, 6, 6},
        {5, 4, 2, 2}
    };
    int n = sizeof(processes) / sizeof(processes[0]);
    int timeQuantum = 2;

    rrScheduling(processes, n, timeQuantum);
    printProcesses(processes, n);

    return 0;
}

4. 优先级调度算法

优先级调度算法根据进程的优先级进行调度，优先级高的进程先获得CPU资源。

示例代码：优先级调度算法

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

typedef struct {
    int processID;
    int arrivalTime;
    int burstTime;
    int priority;
    int completionTime;
    int waitingTime;
    int turnaroundTime;
} Process;

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

void priorityScheduling(Process processes[], int n) {
    qsort(processes, n, sizeof(Process), compare);

    int currentTime = 0;
    for (int i = 0; i < n; i++) {
        processes[i].completionTime = currentTime + processes[i].burstTime;
        processes[i].waitingTime = currentTime - processes[i].arrivalTime;
        processes[i].turnaroundTime = processes[i].completionTime - processes[i].arrivalTime;
        currentTime = processes[i].completionTime;
    }
}

void printProcesses(Process processes[], int n) {
    printf("PID\tArrival\tBurst\tPriority\tCompletion\tWaiting\tTurnaround\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\t%d\t%d\t%d\t%d\n",
               processes[i].processID,
               processes[i].arrivalTime,
               processes[i].burstTime,
               processes[i].priority,
               processes[i].completionTime,
               processes[i].waitingTime,
               processes[i].turnaroundTime);
    }
}

int main() {
    Process processes[] = {
        {1, 0, 5, 2},
        {2, 1, 3, 1},
        {3, 2, 8, 3},
        {4, 3, 6, 2},
        {5, 4, 2, 1}
    };
    int n = sizeof(processes) / sizeof(processes[0]);

    priorityScheduling(processes, n);
    printProcesses(processes, n);

    return 0;
}

5. 总结

通过实现简单的操作系统调度算法，可以理解调度的基本原理和方法。这些算法虽然简单，但在某些场景中仍然有用。对于需要高效率和公平性的调度，可以进一步研究更复杂的调度算法，如多级反馈队列调度等。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)