时间片轮转调度算法

操作系统进程相关：时间片轮转调度算法。

问题描述

  1. 假定系统有5个进程，每个进程用一个PCB来代表。PCB的结构为：
    • 进程名（如Q1~Q5）
    • 指针（按优先数大小把进程连成队列，用指针指出下一个进程PCB的首地址）
    • 要求运行时间（假设进程需要运行的单位时间数）
    • 已运行时间（进程已运行的时间单位数，初始值为0）
    • 状态（假设两种状态：就绪和结束，用R表示就绪，用E表示结束。初始状态都为就绪状态）
  2. 运行之前，为每个进程确定它的“要求运行时间”。通过键盘输入这些参数。
  3. 把5个进程按顺序排成循环队列，用指针指出队列连接情况。用一个标志单元记录轮到运行的进程。处理器调度总是选择标志单元指示的进程运行，对所指的进程，将其“已运行时间”加1。
  4. 进程运行一次后，若“要求运行时间”等于“已运行时间”，则将状态改为“结束”，退出队列，否则继续。
  5. 若就绪队列为空，结束，否则转到 3 重复。

要求

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

代码实现

1
#include<iostream>
2
using namespace std;
3
4
// 进程控制块PCB
5
typedef struct PNode {
6
	char name[10];       // 进程名
7
	struct PNode *next;  // 指向下一节点的指针
8
	int All_time;        // 总运行时间
9
	int Run_Time;        // 已运行时间(初始都为0)
10
	char state;          // 进程状态（R：就绪，E：结束）
11
} *Proc;                 // 指向该PCB的指针
12
13
// 初始化就绪队列
14
void Init_pcb(Proc &P, int n) {
15
    int Num = n;
16
    P = (Proc)malloc(sizeof(PNode));   // 进程队列头结点
17
    P->next = NULL;
18
    Proc p = P;
19
    cout << "请依次输入进程信息："<<endl;
20
    while(Num--) {
21
        p = p->next = (Proc)malloc(sizeof(PNode));
22
        cout << "进程名，总运行时间：";
23
        cin >> p->name >> p->All_time;
24
        p->Run_Time = 0;
25
        p->state = 'R';
26
        p->next = NULL;
27
    }
28
    p->next = P->next;
29
}
30
31
// 输出运行中的进程信息
32
void show_info(Proc P) {
33
    Proc p = P->next;
34
    cout << endl;
35
	do{
36
        if(p->state != 'E') {
37
            cout << "进程名:" << p->name << "\t总运行时间:" << p->All_time;
38
            cout << "\t已运行时间" << p->Run_Time << "\t状态:" << p->state << endl;
39
            p = p->next;
40
        }
41
        else p = p->next;
42
    }while(p != P->next); 
43
}
44
45
// 时间片轮转法
46
void Round_Robin(Proc &P, int n, int timeslice) {
47
    int round = 0;    // 轮转数
48
    Proc p = P->next;
49
    while (p->All_time > p->Run_Time) {
50
        round++;
51
        cout << endl << "Round" << round << "--正在运行" << "进程" << p->name;
52
        if(p->All_time - p->Run_Time <= timeslice) // 还需要的时间小于时间片大小时
53
            p->Run_Time = p->All_time;
54
        else	p->Run_Time += timeslice;	// 更新已运行的时间
55
        show_info(P);         // 展示此时就绪队列的进程信息
56
        if(p->All_time == p->Run_Time) { // 该进程结束
57
            p->state = 'E';
58
            n--;
59
            cout << p->name << "进程运行结束，删除！\n";
60
        }
61
        p = p->next;
62
        while(n && p->All_time == p->Run_Time)
63
            p = p->next;      // 跳过已结束的进程
64
    }
65
    cout << endl;
66
}
67
68
int main() {
69
    int n, timeslice; // 总进程数，时间片大小
70
    cout << "**时间片轮转调度算法**" << endl;
71
    cout << "请输入总进程个数：";
72
    cin >> n;
73
    cout << "请输入时间片大小：";
74
    cin >> timeslice;
75
76
    Proc P;
77
    Init_pcb(P, n);	// PCB初始化
78
    cout << "进程初始状态为：";
79
    show_info(P);      // 输出此刻的进程状态
80
    Round_Robin(P, n, timeslice); // 时间片轮转法
81
82
    return 0;
83
}