CPU调度算法-C语言 | CPU Scheduling Algorithms in C

Made by Mike_Zhang

Unfold Operating Systems Topics | 展开操作系統主题 >

Intro

导言

这学期学了操作系统 (Operating Systems) 课程，当中的一大重点是 CPU调度算法 (CPU Scheduling Algorithms) 。此算法有很多种变式，但是其中的逻辑相对固定，因此我用C语言编写了程序来模拟这些算法。这使得我能够对这些算法有更深的理解，同时也能对我自己演算的结果进行验证。

本文将介绍几种CPU调度算法，及其对应的代码和运行示例。
包括以下五种算法：

  • FCFS (First Come First Serve)
  • PR (Priority), preemptive and non-preemptive
  • SJF (Shortest Job First)
  • SRT (Shortest Remaining Time)
  • Round Robin (RR)

0. Talk is Cheap. Show Me the Code.

不废话，上代码。

下文代码的GitHub链接: CPU Scheduling Algorithms

按照惯例，我计划将在UltraFish Plus上开发网页版的CPU调度算法模拟器，如果你对此感兴趣，可以联系我合作开发，感谢。

1. First Come First Serve

FCFS是最直接最简单的算法，即为先到先得。但有容易出现 Convoy Effect，即一个长进程会阻塞其他短进程的执行。

以下为代码的主要部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int totalWaitingTime;
int totalTurnaroundTime;
int* waitingTime;
int* turnaroundTime;
int* completeTime;
int* serviceTime;
int* ganttSequence;
int** waitingQueueSequence;

void FCFS(int* inArrivalTime, int* inBurstTime, int inN) {
    waitingTime = (int*) malloc(sizeof(int)*inN);
    waitingTime[0]=0;

    serviceTime=(int*) malloc(sizeof(int)*inN);
    serviceTime[0]=0;

    turnaroundTime = (int*) malloc(sizeof(int)*inN);
    completeTime = (int*) malloc(sizeof(int)*inN);

    int i;
    for (i=1;i<inN;i++) {
        serviceTime[i] = serviceTime[i-1] + inBurstTime[i-1];
        if (serviceTime[i]<inArrivalTime[i]) {serviceTime[i]=inArrivalTime[i];}
        waitingTime[i] = serviceTime[i] - inArrivalTime[i];
        if (waitingTime[i]<0) {waitingTime[i]=0;}
    }
    for (i=0;i<inN;i++) {
        turnaroundTime[i] = inBurstTime[i] + waitingTime[i];
    }
    for (i=0;i<inN;i++) {
        completeTime[i] = turnaroundTime[i] + inArrivalTime[i];
    }
    for (i=0;i<inN;i++) {
        totalWaitingTime += waitingTime[i];
        totalTurnaroundTime += turnaroundTime[i];
    }
}

以下为运行结果示例:

  • 多项重要的数据会被输出，例如Waiting Time, Turnaround Time, Completion Time, Gantt Chart, Waiting Queue等。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
~$ ./CPU_FCFS
CPU First Come First Serve Scheduling
> Scheduling Considerations:
Process Arrival Burst   Waiting Service T.A.    Complete
1       0       9       0       0       9       9
2       1       5       8       9       13      14
3       2       2       12      14      14      16
4       3       3       13      16      16      19
5       4       6       15      19      21      25
> Completion Time:               25
> Total Waiting Time:            48
> Average Queuing Time:          1.92 
> Average Waiting Time:          9.60 
> Average Turnaround Time:       14.60 
> Gantt Chart: 
t0  t1  t2  t3  t4  t5  t6  t7  t8  t9  t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 
P1  P1  P1  P1  P1  P1  P1  P1  P1  P2  P2  P2  P2  P2  P3  P3  P4  P4  P4  P5  P5  P5  P5  P5  P5  End
> Waiting Queue: 
t0:
t1:     P2 
t2:     P2 P3 
t3:     P2 P3 P4 
t4:     P2 P3 P4 P5 
t5:     P2 P3 P4 P5 
t6:     P2 P3 P4 P5 
t7:     P2 P3 P4 P5 
t8:     P2 P3 P4 P5 
t9:     P3 P4 P5 
t10:    P3 P4 P5 
t11:    P3 P4 P5 
t12:    P3 P4 P5 
t13:    P3 P4 P5 
t14:    P4 P5 
t15:    P4 P5 
t16:    P5 
t17:    P5 
t18:    P5 
t19:
t20:
t21:
t22:
t23:
t24:

2. Priority

Priority调度算法利用每个进程所对应的优先级来决定下一个要执行的进程。优先级高的进程会被优先执行。此算法可以是抢占式(Preemptive) 或非抢占式(Non-preemptive) 的。代码实现了两种算法，以供用户选择。本代码模拟了Linux的Priority调度算法，即优先级数字越小，优先级越高。

以下为代码的主要部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
int* waitingTime;
int* turnaroundTime;
int* completeTime;
int* serviceTime;
int* ganttSequence;
int totalCompleteTime;
int totalWaitingTime;
int totalTurnaroundTime;

// Get the process with the lowest priority in the waiting queue
// in case of tie, the one with the lowest process number will be returned
int getPrio(int* inPr, int* inWait, int num){
    int i;
    int maxPr=-1;
    for (i=0;i<num;i++) {
        if (inPr[i]>maxPr) {
            maxPr=inPr[i];
        }
    }
    int min=maxPr+1;
    int prio=-1;
    for (i=0;i<num;i++) {
        if (inWait[i]==1 && inPr[i]<min)  {
            min=inPr[i];
            prio=i;
        }
    }
    return prio+1;
}

void PR(int* inArrivalTime, int* inBurstTime, int* inPriority, int inN, int isPreemptive) {
    int num = inN;
    int isWaiting[num];
    int burstTime[num];
    int k;
    for (k=0; k<num; k++) {
        burstTime[k]=inBurstTime[k];
        isWaiting[k]=0;
        totalCompleteTime+=inBurstTime[k];
    }
    totalCompleteTime = totalCompleteTime>(inArrivalTime[num-1]+inBurstTime[num-1])?totalCompleteTime:(inArrivalTime[num-1]+inBurstTime[num-1]);
    int currentTime=0; // the clock
    waitingTime = (int*) malloc(sizeof(int)*num);
    waitingTime[0]=0;
    serviceTime=(int*) malloc(sizeof(int)*num);
    serviceTime[0]=0;
    turnaroundTime = (int*) malloc(sizeof(int)*num);
    completeTime = (int*) malloc(sizeof(int)*num);
    ganttSequence = (int*) malloc(sizeof(int)*totalCompleteTime);

    int processInRun=-1;
    int processInArrive;
    while (currentTime<=totalCompleteTime) {
        // complete
        if (processInRun!=-1 && burstTime[processInRun-1]==0) {
            completeTime[processInRun-1]=currentTime;
            turnaroundTime[processInRun-1]=completeTime[processInRun-1]-inArrivalTime[processInRun-1];
            isWaiting[processInRun-1]=0;
            processInRun=-1;
        }
        // arrive
        int i;
        for (i=0;i<num;i++) {
            if (inArrivalTime[i]==currentTime) { // new process arrive
                isWaiting[i]=1;
                if (isPreemptive == 1 && processInRun!=-1 && inPriority[i]<inPriority[processInRun-1]) { // take over
                    isWaiting[processInRun-1]=1;
                    isWaiting[i]=0;
                    processInRun=i+1; // preemptive take over
                }
                break;
            }
        }
        // new run
        if (processInRun==-1) {
            processInRun=getPrio(inPriority, isWaiting, num); // get the boss
            if (processInRun!=-1) {
                isWaiting[processInRun-1]=0;
            }
        }
        // get service time
        if (processInRun!=-1 && inBurstTime[processInRun-1] == burstTime[processInRun-1]) {
            serviceTime[processInRun-1]=currentTime;
        }
        // decrease burst time
        if (processInRun!=-1) {
            burstTime[processInRun-1]--;
        }
        ganttSequence[currentTime]=processInRun;
        currentTime++;
    }
    int i;
    // get waiting time
    for (i=0;i<inN;i++) {
        waitingTime[i]=turnaroundTime[i]-inBurstTime[i];
    }
    for (i=0;i<inN;i++) {
        totalWaitingTime += waitingTime[i];
        totalTurnaroundTime += turnaroundTime[i];
    }
}

以下为运行结果示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
~$ ./CPU_PR  
CPU Priority Scheduling
> [Preemptive PR]
> Scheduling Considerations:
PID     Arrival Burst   PR.     Waiting Service Turn.   Complete
1       0       7       7       23      0       30      30
2       2       1       2       0       2       1       3
3       3       8       6       14      3       22      25
4       4       6       5       8       4       14      18
5       8       8       4       0       8       8       16
> Completion Time:               30
> Total Waiting Time:            45
> Average Queuing Time:          2.81 
> Average Waiting Time:          9.00 
> Average Turnaround Time:       15.00 
> Gantt Chart: 
t0  t1  t2  t3  t4  t5  t6  t7  t8  t9  t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 t26 t27 t28 t29 t30 
P1  P1  P2  P3  P4  P4  P4  P4  P5  P5  P5  P5  P5  P5  P5  P5  P4  P4  P3  P3  P3  P3  P3  P3  P3  P1  P1  P1  P1  P1  End

值得注意的是，FCFS可以被看作非抢占式的PR，并且其中各进程的优先级为其Arrival Time，即Arrival Time越小，优先级越高。因此可以通过修改PR算法来实现FCFS算法。

3. Shortest Job First

SJF可以有效解决FCFS所带来的Convoy Effect问题。其始终有限执行运行时间最少的进程。其也被证明在非抢占式CPU调度算法中拥有最少的Average Waiting Time和Average Turnaround Time。

类似地，SJR也可以通过PR修改而来，其可被看作为非抢占式的PR，并且其中各进程的优先级为其Burst Time，即Burst Time越小，优先级越高。

以下为代码的主要部分:

  • 调用了上文定义的PR()方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void SJF(int* inArrivalTime, int* inBurstTime,int inN){
    int* priority = (int*) malloc(sizeof(int)*inN);
    int* temp = (int*) malloc(sizeof(int)*inN);
    int i;
    for (i=0;i<inN;i++) {
        temp[i]=inBurstTime[i];
    }
    // sort the temp
    int j;
    for (i=0;i<inN;i++) {
        for (j=i+1;j<inN;j++) {
            if (temp[i]>temp[j]) {
                int t = temp[i];
                temp[i]=temp[j];
                temp[j]=t;
            }
        }
    }
    // assign priority
    for (i=0;i<inN;i++) {
        for (j=0;j<inN;j++) {
            if (inBurstTime[i]==temp[j]) {
                priority[i]=j+1;
                break;
            }
        }
    }
    // non-preemptive PR
    PR(inArrivalTime, inBurstTime, priority, inN, 0); 
}

以下为运行结果示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
~$ ./CPU_SJF
CPU Shortest Job First Scheduling
> Scheduling Considerations:
PID     Arrival Burst   Waiting Service Turn.   Complete
1       0       9       0       0       9       9
2       1       5       13      14      18      19
3       2       2       7       9       9       11
4       3       3       8       11      11      14
5       4       6       15      19      21      25
> Completion Time:               25
> Total Waiting Time:            43
> Average Queuing Time:          1.72 
> Average Waiting Time:          8.60 
> Average Turnaround Time:       13.60 
> Gantt Chart: 
t0  t1  t2  t3  t4  t5  t6  t7  t8  t9  t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 
P1  P1  P1  P1  P1  P1  P1  P1  P1  P3  P3  P4  P4  P4  P2  P2  P2  P2  P2  P5  P5  P5  P5  P5  P5  End

4. Shortest Remaining Time

SRT进一步解决了SJF所带来潜在的Convoy Effect问题。其抢占式地运行剩余最少时间的进程。其也被证明在抢占式CPU调度算法中拥有最少的Average Waiting Time和Average Turnaround Time。

类似地，SRT也可以通过PR修改而来，其可被看作为抢占式的PR，并且其中各进程的优先级为其Remaining Time，即Remaining Time越小，优先级越高。

以下为代码的主要部分:

  • 调用了上文定义的PR()方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void updatePriority(int* inPriority, int* inRemainingTime,int inN){
    int* temp = (int*) malloc(sizeof(int)*inN);
    int i;
    for (i=0;i<inN;i++) {
        temp[i]=inRemainingTime[i];
    }
    // sort the temp
    int j;
    for (i=0;i<inN;i++) {
        for (j=i+1;j<inN;j++) {
            if (temp[i]>temp[j]) {
                int t = temp[i];
                temp[i]=temp[j];
                temp[j]=t;
            }
        }
    }
    // assign priority
    for (i=0;i<inN;i++) {
        for (j=0;j<inN;j++) {
            if (inRemainingTime[i]==temp[j]) {
                inPriority[i]=j+1;
                break;
            }
        }
    }
}

void SRT(int* inArrivalTime, int* inBurstTime,int inN){
    priority = (int*) malloc(sizeof(int)*inN);
    updatePriority(priority, inBurstTime, inN);
    // preemptive PR
    PR(inArrivalTime, inBurstTime, priority, inN, 1); 
}

以下为运行结果示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
~$ ./CPU_SRT  
CPU Shortest Shortest Remaining Time Scheduling
> Scheduling Considerations:
PID     Arrival Burst   Waiting Service Turn.   Complete
1       0       9       16      0       25      25
2       1       5       5       1       10      11
3       2       2       0       2       2       4
4       3       3       1       4       4       7
5       4       6       7       11      13      17
> Completion Time:               25
> Total Waiting Time:            29
> Average Queuing Time:          1.71 
> Average Waiting Time:          5.80 
> Average Turnaround Time:       10.80 
> Gantt Chart: 
t0  t1  t2  t3  t4  t5  t6  t7  t8  t9  t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 
P1  P2  P3  P3  P4  P4  P4  P2  P2  P2  P2  P5  P5  P5  P5  P5  P5  P1  P1  P1  P1  P1  P1  P1  P1  End

5. Round Robin

RR使得各进程更公平地分享CPU使用时间，每个进程只被分配到很短的时间(Time Quantum)，并轮流进行，直到满足所需时间。此特性会其用更长的Content Switch时间，更长的Turnaround Time，但是会有更短的响应时间。
有趣的是，当Time Quantum足够长，大于最长进程所需的时间，RR就变为了FCFS。

以下为代码的主要部分:

  • Tie Breaking Rule: the new arrival one will be served first.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
int* waitingTime;
int* turnaroundTime;
int* completeTime;
int* serviceTime;
int* ganttSequence;
int totalCompleteTime;
int totalWaitingTime;
int totalTurnaroundTime;

void RR(int inNum, int inArrivalArray[], int inServeArray[], int inQuantum) {
    int num=inNum;
    Queue* inArriveQueue=newQueue(num); // queue for processes in arriving
    Queue* waitingQueue=newQueue(num); // queue for processes in waiting
    int burstTime[num]; // burst time
    int k;
    for (k=0; k<num; k++) {
        burstTime[k]=inServeArray[k];
        totalCompleteTime+=inServeArray[k];
    }
    totalCompleteTime = totalCompleteTime>(inArrivalArray[num-1]+inServeArray[num-1])?totalCompleteTime:(inArrivalArray[num-1]+inServeArray[num-1]);
    int currentTime=0; // the clock
    int quantum=inQuantum; // the designed quantum
    int currentQuantum=0; // the current quantum
    waitingTime = (int*) malloc(sizeof(int)*num);
    waitingTime[0]=0;
    serviceTime=(int*) malloc(sizeof(int)*num);
    serviceTime[0]=0;
    turnaroundTime = (int*) malloc(sizeof(int)*num);
    completeTime = (int*) malloc(sizeof(int)*num);
    ganttSequence = (int*) malloc(sizeof(int)*totalCompleteTime);
    int* lastEnqueueTime = (int*) malloc(sizeof(int)*num);

    int i;
    for (i=0; i<num; i++) {
        enqueue(inArriveQueue, i+1);
    }
    int processInRun; // store the current process in service
    int processInArrive=front(inArriveQueue); // first process in come
    dequeue(inArriveQueue);
    enqueue(waitingQueue, processInArrive);
    lastEnqueueTime[processInArrive-1]=inArrivalArray[processInArrive-1];

    while(isQueueEmpty(waitingQueue)==-1 || isQueueEmpty(inArriveQueue)==-1) {
        processInRun=dequeue(waitingQueue);
        processInArrive=front(inArriveQueue);
        if (processInRun==-1) {
            currentTime=inArrivalArray[processInArrive-1];
            processInRun=processInArrive;
            dequeue(inArriveQueue);
        }
        // get the service time
        if (burstTime[processInRun-1] == inServeArray[processInRun-1]) {
            serviceTime[processInRun-1]=currentTime;
        }
        // get the waiting time
        if (currentTime-lastEnqueueTime[processInRun-1]>0) {
            waitingTime[processInRun-1]+=currentTime-lastEnqueueTime[processInRun-1];
        }
        // get time duration in this round
        int duration;
        int isQuantumUp;
        if (burstTime[processInRun-1]<=quantum) {
            duration=burstTime[processInRun-1];
            isQuantumUp=0;
        } else {
            duration=quantum;
            isQuantumUp=1;
        }
        // gantt chart
        int j;
        for (j=0;j<duration;j++) {
            ganttSequence[currentTime+j]=processInRun;
        }
        // check arrival in the duration
        if (processInArrive!=-1) {
            int nextArrTime=inArrivalArray[processInArrive-1];
            while (1) {
                if (nextArrTime>currentTime+duration) {
                    break;
                }
                else if (nextArrTime<=currentTime+duration && nextArrTime>currentTime) {
                    enqueue(waitingQueue, processInArrive);
                    lastEnqueueTime[processInArrive-1]=nextArrTime;
                    dequeue(inArriveQueue);
                }
                processInArrive=front(inArriveQueue);
                if (processInArrive==-1) {
                    break;
                }
                nextArrTime=inArrivalArray[processInArrive-1];
            }
        }
        // finish
        if (isQuantumUp==0) {
            burstTime[processInRun-1]=0;
            completeTime[processInRun-1]=currentTime+duration; // get the complete time
            processInRun=0;
        }
        // quantum time up
        if (isQuantumUp==1) {
            burstTime[processInRun-1]-=duration;
            enqueue(waitingQueue, processInRun);
            lastEnqueueTime[processInRun-1]=currentTime+duration;
            processInRun=0;
        }
        currentTime+=duration;
    }
    for (i=0;i<num;i++) {
        turnaroundTime[i] = completeTime[i] - inArrivalArray[i];
    }
    for (i=0;i<num;i++) {
        totalWaitingTime += waitingTime[i];
        totalTurnaroundTime += turnaroundTime[i];
    }
}

以下为运行结果示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
~$ ./CPU_RR 
CPU Round Robin Scheduling (Tie breaking rule: new one first)
> Scheduling Considerations:
PID     Arrival Burst   Waiting Service Turn.   Complete
1       0       9       16      0       25      25
2       1       5       16      4       21      22
3       2       2       6       8       8       10
4       3       3       7       10      10      13
5       4       6       14      13      20      24
> Completion Time:               25
> Total Waiting Time:            59
> Average Queuing Time:          2.46 
> Average Waiting Time:          11.80 
> Average Turnaround Time:       16.80 
> Gantt Chart: 
t0  t1  t2  t3  t4  t5  t6  t7  t8  t9  t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 
P1  P1  P1  P1  P2  P2  P2  P2  P3  P3  P4  P4  P4  P5  P5  P5  P5  P1  P1  P1  P1  P2  P5  P5  P1  End

References

A. Silberschatz, Peter Baer Galvin, and G. Gagne, Operating system concepts. Hoboken (Nj): Wiley, Cop, 2018.

Outro

尾巴

操作系统相关内容的代码会马上继续更新。
最后，希望大家一起交流，分享，指出问题，谢谢！

原创文章，转载请标明出处
Made by Mike_Zhang




感谢你的支持
Operating Systems > CPU Scheduling
#CPU Scheduling #OS
CPU调度算法-C语言 | CPU Scheduling Algorithms in C
https://ultrafish.io/post/cpu-scheduling-algorithms-in-c/
Author
Mike_Zhang
Posted on
May 11, 2023
Licensed under