操作系统-进程调度--优先级调度算法和时间片轮转算法_时间片轮转流程图

一、实验内容与要求

1. 优先权法、轮转法
   简化假设
   1）进程为计算型的（无I/O）
   2）进程状态：ready、running、finish
   3）进程需要的CPU时间以时间片为单位确定
2. 算法描述
   1）优先权法——动态优先权
   当前运行进程用完时间片后，其优先权减去一个常数。
   2）轮转法
3. 要求
   1）产生的各种随机数的取值范围加以限制，如所需的CPU时间限制在1~20之间。
   2）进程数n不要太大通常取4~8个
   3）使用动态数据结构
   4）独立编程

二、实验流程图

三、实验分析

优先权调度算法
首先，时间片轮转法需要实时根据优先权大小对进程排序，优先级大的进程先运行，所以采用优先队列的数据结构是最合适的。
PCB中还需要存放进程的名称、进程的所需时间、进程的优先权、进程的状态，可以采用结构体，同时还可以自定义进程的排序方式。
初始化时，进程的所需时间范围规定为1-20；又因为每个时间片结束，进程所需时间-1，优先权-3，为使优先级不小于0，规定优先级为60-80；进程的初始状态都为ready。
采用优先级调度算法时，每次先将队首进程状态置为running，然后输出各进程的状态。若此时队首的进程状态都为finish，则代表全部的进程都已经完成，即退出；否则时间片到后，进程所需时间-1，优先权-3，再继续判断进程是否已经完成，若完成，则将进程的优先权置为最小的0后入队，保证在优先队列中，该进程总是在队尾的。
时间片轮转算法
轮转法要注意理解轮转时间片的概念，轮转时间片规定了该进程每次最多可运行的时间片数。
在轮转法中，若已占用的时间片<轮转时间片，那么该进程一直在队首占用CPU运行，采用普通的队列，每次队首出列后，只能在队尾弹入，所以我采用了双端队列的数据结构，这样在占用时间片<轮转时间片的情况下，进程可以直接弹入队首，减少了时间复杂度和空间复杂度。
另外，在轮转法中，进程完成后无法像优先队列那样一直在队尾，所以我另外开了一个队列，存放已完成的进程情况。

四、实验代码

#include <bits/stdc++.h>

using namespace std;

//*************************优先级调度算法****************************//

struct PCB_PSA {
    int id;             //进程名称
    int need_time;      //进程所需时间
    int priority;       //进程的优先级
    string state;       //进程的状态

    //优先队列排序，优先级大的进程先执行
    bool operator<(const PCB_PSA &a) const {
        return a.priority >= priority;
    }
};

int cnt = 1;            //记录时间
int n;                  //进程个数
char c;                 //选择调度算法
priority_queue<PCB_PSA> pcb_PSA;

//进程初始化
void init_PSA() {
    for (int i = 1; i <= n; i++) {
        PCB_PSA t;
        t.id = i;
        t.need_time = rand() % 20 + 1;      //进程所需时间为1~20
        t.priority = rand() % 20 + 60;      //进程优先权为60~80，因为每执行一个时间片优先权-3，优先权很快会变成负数，采用这个范围的话优先权最小为0
        t.state = "ready";                  //进程状态初始化为ready
        pcb_PSA.push(t);
    }
}

//输出当前进程运行情况
void print_PSA() {
    priority_queue<PCB_PSA> temp = pcb_PSA;
    PCB_PSA t;
    cout << endl << "当前时刻：" << cnt++ << endl;
    while (!temp.empty()) {
        t = temp.top();
        temp.pop();
        cout << "进程名称：" << t.id << "\t状态：" << t.state << "\t所需时间：" << t.need_time << "\t优先级：" << t.priority << endl;
    }
}

//优先级调度
void PSA() {
    PCB_PSA t;
    while (1) {
        //将队首进程状态改为running,然后输出进程执行情况
        t = pcb_PSA.top();
        pcb_PSA.pop();
        if (t.state != "finish")t.state = "running";
        pcb_PSA.push(t);
        print_PSA();
        t = pcb_PSA.top();
        pcb_PSA.pop();
        //若队首进程的状态为finish,则进程全部完成,退出。
        if (t.state == "finish")break;
        //时间片到，进程所需时间-1，优先权-3
        t.need_time -= 1;
        t.priority -= 3;
        //若进程所需时间为0，则将优先权置为最小0；否则状态变为ready。
        if (t.need_time == 0) {
            t.state = "finish";
            t.priority = 0;
        } else {
            t.state = "ready";
        }
        pcb_PSA.push(t);
    }
}

//********************************************************************//
//***************************时间片轮转调度算法***************************//

struct PCB_RR {
    int id;                 //进程名称
    int need_time;          //进程所需时间
    int round_time;         //进程轮转时间片
    int hold_time;          //进程占已用时间
    string state;           //进程状态
};
//pcb_finish存放已经完成的进程
deque<PCB_RR> pcb_RR, pcb_finish;


//进程初始化
void init_RR() {
    for (int i = 1; i <= n; i++) {
        PCB_RR t;
        t.id = i;
        t.need_time = rand() % 20 + 1;      //进程所需时间范围为1~20
        t.round_time = rand() % 20 + 1;     //进程轮转时间片为1~20
        t.hold_time = 0;                    //进程占用时间初始化为0
        t.state = "ready";                  //进程状态初始化为ready
        pcb_RR.push_back(t);
    }
}

//输出当前进程运行情况+已完成的进程情况
void print_RR() {
    cout << endl << "当前时刻：" << cnt++ << endl;
    deque<PCB_RR> temp = pcb_RR;
    PCB_RR t;
    while (!temp.empty()) {
        t = temp.front();
        temp.pop_front();
        cout << "进程名称：" << t.id << "\t状态：" << t.state << "\t所需时间：" << t.need_time << "\t轮转时间片：" << t.round_time << endl;
    }
    temp = pcb_finish;
    while (!temp.empty()) {
        t = temp.front();
        temp.pop_front();
        cout << "进程名称：" << t.id << "\t状态：" << t.state << "\t所需时间：" << t.need_time << "\t轮转时间片：" << t.round_time << endl;
    }
}

//轮转时间片
void RR() {
    PCB_RR t;
    while (!pcb_RR.empty()) {
        //将队首进程状态改为running,然后输出当前进程执行情况
        t = pcb_RR.front();
        pcb_RR.pop_front();
        t.state = "running";
        pcb_RR.push_front(t);
        print_RR();
        t = pcb_RR.front();
        pcb_RR.pop_front();
        //时间片到，进程所需时间-1，进程占用时间+1
        t.need_time -= 1;
        t.hold_time += 1;
        //若进程所需时间为0，则进程执行完成，入pcb_finish队列
        //若占用时间=轮转时间片，进程占用时间置0，入队尾
        //否则进程入队首
        if (t.need_time == 0) {
            t.state = "finish";
            pcb_finish.push_back(t);
        } else if (t.hold_time == t.round_time) {
            t.state = "ready";
            t.hold_time = 0;
            pcb_RR.push_back(t);
        } else {
            pcb_RR.push_front(t);
        }
    }
    print_RR();
}

//*********************************************************************//

int main() {
    srand(time(NULL));
    cout << "请输入进程数(4~8个)：";
    cin >> n;
    cout << "请选择调度方法(y：优先权法；n：轮转法)：";
    cin >> c;
    if (c == 'y') {
        init_PSA();
        PSA();
    } else if (c == 'n') {
        init_RR();
        RR();
    }
    return 0;
}
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169