优先数调度算法

操作系统进程相关：优先数调度算法。

问题描述

  1. 假定系统有5个进程，每个进程用一个PCB来代表，PCB的结构为：
    • 进程名（如P1~P5）
    • 指针（按优先数大小把进程连成队列，用指针指出下一个进程PCB的首地址）
    • 要求运行时间（假设进程需要运行的单位时间数）
    • 优先数（赋予进程的优先数，调度时总是选取优先数大的进程先执行）
    • 状态（假设两种状态：就绪和结束，用R表示就绪，用E表示结束。初始状态都为就绪状态）
  2. 开始运行之前，键盘输入为每个进程确定它的“优先数”和“要求运行时间”。
  3. 处理器总选队首进程运行，用动态改变优先数的办法，进程每运行1次，优先数减1，要求运行时间减1。
  4. 进程运行一次后若要求运行时间不为0，则将它加入就绪队列，否则将状态改为“结束”，退出就绪队列。
  5. 若就绪队列为空，结束，否则转到 3 重复。

要求

能接受键盘输入的进程优先数及要求运行时间，能显示每次进程调度的情况，如哪个进程在运行，哪些进程就绪，就绪进程的排列情况。

代码实现

1
#include <iostream>
2
#include <vector>
3
using namespace std;
4
5
// 进程控制块PCB
6
typedef struct PCB {
7
    char name[10]; // 进程名
8
    int runtime;   // 要求运行时间
9
    int priority;  // 优先数（优先数越大优先级越高）
10
    char state;    // 进程状态（R：就绪，E：结束，r：正在运行）
11
} PCB;
12
13
// 进程初始化
14
// 参数：所有进程PCB的开始指针，总进程数
15
void pcb(PCB *p, int n) {
16
    cout << "请输入" << n <<"个进程的名称，运行时间及优先数（如：P1 2 1）：" << endl;
17
    for(int i=0; i<n; i++) {
18
        cout << "Process" << i+1 << ": ";
19
        cin >> p[i].name >> p[i].priority >> p[i].runtime;
20
        p[i].state = 'R'; // 初始化每个进程都为就绪状态
21
    }
22
}
23
24
// 每一调度后各进程状态
25
// 参数：所有进程PCB的开始指针，总进程数
26
void show(PCB *p, int n) {
27
    cout << "进程名 优先数 运行时间 状态" << endl;
28
    for(int i=0; i<n; i++)
29
        printf("%s\t%d\t%d\t%c\n", p[i].name, p[i].priority, p[i].runtime, p[i].state);
30
}
31
32
// 得到最大优先级的进程序号
33
// 参数：所有进程PCB的开始指针，总进程数
34
int max_priority_process(PCB *p, int n) {
35
    int index, max_priority = -100; // 最大优先数进程序号，最大优先数
36
    for(int i=0; i<n; i++) {
37
        if(p[i].state == 'r') // 正在运行
38
            return -1;
39
        else {
40
            // 在就绪队列中找到优先数最大的进程
41
            if(max_priority < p[i].priority && p[i].state == 'R') {
42
                max_priority = p[i].priority;
43
                index = i; 
44
            }
45
        }
46
    }
47
48
    // 优先数最大的进程已运行结束
49
    if(p[index].state == 'E')
50
        return -1;
51
    else
52
        return index;
53
}
54
55
// 进程调度算法
56
// 参数：所有进程PCB的开始指针，总进程数
57
void run(PCB *p, int n) {
58
    vector<string> v; // 进程依次运行顺序
59
60
    int t = 0; // 总运行时间
61
    for(int i=0; i<n; i++)
62
        t += p[i].runtime;
63
    
64
    cout << endl << "*进程初始状态*" << endl;
65
    show(p, n);
66
67
    // 开始运行
68
    for(int j=1; j<=t; j++) {
69
        while(max_priority_process(p, n) != -1)
70
            p[max_priority_process(p, n)].state = 'r'; // 继续运行
71
        
72
        for(int i=0; i<n; i++) {
73
            if(p[i].state == 'r') {
74
                p[i].priority--; // 优先数减一
75
                p[i].runtime--; // 要求运行时间减一
76
77
                printf("\n第 %d 次: 进程 %s, 优先数 %d, 要求运行时间 %d\n", j, p[i].name, p[i].priority, p[i].runtime);
78
                show(p, n); // 本次运行后进程状态
79
80
                string s = p[i].name;
81
                v.push_back(s); // 将该进程放入运行顺序表中
82
83
                // 继续运行与否
84
                if(p[i].runtime == 0)
85
                    p[i].state = 'E';
86
                else    
87
                    p[i].state = 'R';
88
            }
89
        }
90
    }
91
92
    // 输出进程运行顺序
93
    cout << "优先数调度算法调度顺序：" << v[0];
94
    for(int i=1; i<v.size(); i++)
95
        cout << " —> " << v[i];
96
    cout << endl;
97
}
98
99
int main() {
100
    int n; // 总进程数
101
    cout << "**优先数调度算法**" << endl;
102
    cout << "请输入总进程个数：";
103
    cin >> n;
104
105
    PCB *p = new PCB[n]; // 创建进程空间
106
    pcb(p, n); // 初始化进程
107
    run(p, n); // 进程调度
108
109
    delete[] p;
110
    return 0;
111
}