【操作系统】进程调度算法-FCFS-SJF-RR 操作系统

目录
进程调度的概念
引起进程调度的原因
进程调度算法
先来先服务算法(FCFS)
短作业优先算法(SJF)
时间片轮转算法(RR)
进程调度源码
程序源码
运行结果
进程调度的概念首先我们简洁明了的说, 进程调度就是决定内存中的就绪队列中的那个进程将获得处理机, 进程调度是操作系统中必不可少的一
种调度, 因为我们在电脑上运行的进程很多, 我们在运行进程的还会有新进程到来, 那么操作系统就会采用一系列的调度算法来为
进程分配cpu, 使各个进程都正常运行, 本文中我们说三种算法, 即先来先服务, 短作业(进程)优先,还有时间片轮转算法.
注: 进程调度有抢占式和非抢占式, 我们说的是非抢占式, 有新的进程到来并不会暂停当前正在运行的进程.
引起进程调度的原因 1. 正在执行的进程执行完毕
2. 执行中的进程因为提出某种请求暂停执行
3. 时间片完成
4. 进程阻塞
5. 到来了优先级高的进程
进程调度算法先来先服务算法(FCFS)

按照进程进入内存的时间进行先后排序选取下一个要执行的作业/进程, 先来到的先分配CPU
具体思路:
我们给所有进程按照到达时间进行排序, 然后依次进行执行(非抢占式), 执行完成之后, 如果当前有进程到来, 则执行下
一个进程,如果没有下一个进程到来则等待, 更新当前系统执行的总时间, 把等待时间也要算进去.
特点:
1. 容易实现, 但是效率不高
2. 只考虑进程的等候时间, 没有考虑进程服务时间的长短, 对于短小的进程不利, 等待时间可能会远远大于服务时间.

文章图片

短作业优先算法(SJF)

对于已经到达的进程, 选取一个服务时间最短的进行调度.
具体思路:
因为第一个到达的进程一定是先运行的, 所以我们还是按照到达时间进行排序, 这样有一个好处, 我们慢慢说, 首先开始
运行第一个进程, 然后下一个进程要运行的是已经到达的进程中服务时间最短的, 那我们就从第二个开始向后搜索, 如果当前
进程到了并且没有运行, 就把它的服务时间保存起来, 依次向后搜索, 最终找到已经到达的进程中服务时间最短的, 但是还有
一个情况, 同上面一样, 当前进程运行完成之后没有别的进程到来怎么办, 这个时候我们不用管后来的进程服务时间的长短了,
下一个肯定要运行即将到来的第一个进程, 那么这个时候我们用时间排序就派上用场了, 我们直接搜索第一个没有被运行的
进程即可, 因为已经到来的进程肯定已经运行完了, 所以不用管了, 这个时候同上面一样总时间就要变成下一个要到来的进程
的到达时间, 因为处理机在等待, 这个时间要加上, 然后直到把所有的进程运行完.
特点:
1. 跟上面差不多, 容易实现, 但是效率不高
2. 对于一个早来的但是服务时间很长的进程很不利, 很长时间内不能调度, 容易出现"饥饿"现象

文章图片

时间片轮转算法(RR)

时间片轮转算法就是给一个时间片, 每个进程只能运行这么长时间, 如果到了时间运行完了就从内存中的就绪队列中删除
如果时间片到了但是没有运行完, 就把这个进程挂到就绪队列队尾
具体思路:
我们先给一个时间片, 然后跟上面一样, 第一个到达的进程肯定先运行, 所以我们还是先按照到达时间进行排序, 然后让
第一个进程开始运行, 将第一个进程push进就绪队列中, 然后我们还是记录当前系统运行的总时间, 在一个时间片之内, 如果
运行完成了就pop出队, 当然在运行的过程中还可能有别的进程进来, 所以我们要保存当前进程运行的总时间, 如果有进程到
来, 直接push入队, 如果当前进程没有运行完成并且就绪队列里面没有别的进程, 那就再分配时间片继续运行, 一直没有就一
直运行, 如果就绪队列里面有别的进程, 那就将这个进程挂到就绪队列队尾, 运行下一个. 如果当前进程运行完了并且就绪队
列里面没有别的进程, 这个时候所有的进程并没有全部入过队, 我们就要判断, 如果全部入过了就结束, 如果没有全部如果就
等待, 总时间一直累加, 直到有进程进来了, 最终运行完成.
特点:
1. 每个进程有平等的机会可以获得CPU
2. 时间片要合适, 如果偏大: 性能退化, 如果偏小: 进程调度频繁, 增加系统开销

文章图片

进程调度源码

ps : 进程的一些时间属性
1. 到达时间: 一个进程到达内存的时间.
2. 服务时间: 这个进程需要运行的时间.
3. 完成时间: 这个进程被CPU调度完成之后的完成时间.
4. 周转时间: 这个进程从进入内存到被执行完的时间,周转时间 = 完成时间 - 到达时间.
5. 带权周转时间: 带权周转时间越小, 证明对这个进程越有利, 带权周转时间 = 周转时间 / 服务时间.

程序源码
链接: github源码

pcb.h

#pragma once #include #include #include #include #include using namespace std; typedef struct Pcb { char name; float arr_time; //到达时间 float ser_time; //服务时间 float fin_time; //完成时间 float tur_time; //周转时间 float b_tur_time; //带权周转时间 float run_time = 0; //运行时间 bool flag_run = false; //执行标志 bool flag_push = false; //入队标志 }Pcb; void Input(vector& pcb, int &n) { cout << "请输入进程数量: "; cin >> n; cout << endl; pcb.resize(n); for (int i = 0; i < n; ++i) { cout << "请输入进程" << i + 1 << "的进程名, 到达时间, 服务时间: "; cin >> pcb[i].name >> pcb[i].arr_time >> pcb[i].ser_time; } }void Output(vector& pcb, int n, float tur_sum, float b_tur_sum) { float avg_tur_sum = tur_sum / n; float avg_b_tur_sum = b_tur_sum / n; cout << endl; cout << "id|arr|ser|fin|tur|b_tur |" << endl; for (int i = 0; i < n; ++i) { printf("%c | %6.2f | %6.2f | %6.2f | %6.2f | %6.2f | \n", pcb[i].name, pcb[i].arr_time, pcb[i].ser_time, pcb[i].fin_time, pcb[i].tur_time, pcb[i].b_tur_time); } cout << endl; printf("平均周转时间 : %6.2f\n", avg_tur_sum); printf("平均带权周转时间 : %6.2f\n", avg_b_tur_sum); cout << endl; }bool ForArr(Pcb& a, Pcb& b) { return a.arr_time < b.arr_time; }void Time_BubbleSort(vector& pcb, int n) { sort(pcb.begin(), pcb.end(), ForArr); }//先来先服务 void FCFS(vector& pcb, int &n) { Input(pcb, n); Time_BubbleSort(pcb, n); float tur_sum = 0.0; float b_tur_sum = 0.0; float Time = 0; //运行总时间 for (int i = 0; i < n; ++i) { if (i == 0) { pcb[0].fin_time = pcb[0].ser_time; Time = pcb[0].fin_time; } else { if (pcb[i].arr_time > Time) { //如果前一个进程运行完成下一个进程没有到达 Time = pcb[i].arr_time; } pcb[i].fin_time = pcb[i].ser_time + Time; //更新一下程序运行的总时间 Time = pcb[i].fin_time; } pcb[i].tur_time = pcb[i].fin_time - pcb[i].arr_time; tur_sum += pcb[i].tur_time; pcb[i].b_tur_time = pcb[i].tur_time / pcb[i].ser_time; b_tur_sum += pcb[i].b_tur_time; } Output(pcb, n, tur_sum, b_tur_sum); }//短作业优先 void SJF(vector& pcb, int n) { Input(pcb, n); //先按照到达时间排序 Time_BubbleSort(pcb, n); float Time = 0; bool flag_have = false; float tur_sum = 0.0; float b_tur_sum = 0.0; //一次运行一个进程 //第一个进程一定先运行 pcb[0].fin_time = pcb[0].ser_time; pcb[0].flag_run = true; pcb[0].tur_time = pcb[0].fin_time - pcb[0].arr_time; pcb[0].b_tur_time = pcb[0].tur_time / pcb[0].ser_time; Time = pcb[0].fin_time; tur_sum += pcb[0].tur_time; b_tur_sum += pcb[0].b_tur_time; for (int i = 1; i < n; ++i) { flag_have = false; //找出当前数组中还没有运行的第一个pcb //不会存在全部运行过的情况, 因为上面的for循环是n - 1次, 所以肯定刚好把下标从1 ~ n - 1的访问完 int Min_ser = 0; for (int index = 1; index < n; ++index) { if (!pcb[index].flag_run) { Min_ser = index; break; } } //找到之后, 从第一个节点开始向后访问, 判断有没有到达时间小于Time的 //有 : 再找出服务时间最小的 for (int j = 1; j < n; ++j) { if ((pcb[j].arr_time < Time) && (!pcb[j].flag_run)) { flag_have = true; if (pcb[j].ser_time < pcb[Min_ser].ser_time) Min_ser = j; } }//没有: 当前进程就是到达时间最小的, 直接运行它, Min_ser不用变 if (!flag_have) { Time = pcb[Min_ser].arr_time; }//计算当前进程的各个时间 pcb[Min_ser].fin_time = Time + pcb[Min_ser].ser_time; pcb[Min_ser].tur_time = pcb[Min_ser].fin_time - pcb[Min_ser].arr_time; pcb[Min_ser].b_tur_time = pcb[Min_ser].tur_time / pcb[Min_ser].ser_time; pcb[Min_ser].flag_run = true; Time = pcb[Min_ser].fin_time; tur_sum += pcb[Min_ser].tur_time; b_tur_sum += pcb[Min_ser].b_tur_time; } Output(pcb, n, tur_sum, b_tur_sum); }void RR(vector& pcb, int n, int time) { //输入 Input(pcb, n); //先按到达时间排序 Time_BubbleSort(pcb, n); queue pq; //第一个一定先运行 //先将pcb[0]push进去 pcb[0].flag_push = true; pq.push(pcb[0]); int q = time; //时间片 float Time = 0; //程序的运行时间 bool flag_all = false; //是否全部入队 while ((!pq.empty()) || (!flag_all)) { --q; ++Time; //如果有进程到达, 入队 //如果已经全部入过队了, 就不用判断了, 省时间 if (!flag_all) { for (int i = 1; i < n; ++i) { if ((pcb[i].arr_time == Time) && (!pcb[i].flag_push)) { pcb[i].flag_push = true; pq.push(pcb[i]); if (pq.size() == n) flag_all = true; break; } } //判断是否所有的进程都进入了队列, 作用是当有一个进程执行完但是后面有进程没有到达时 //要一直++Time for (int i = 0; i < n; ++i) { if (pcb[i].flag_push = false) flag_all = false; } }//队列不为空就去访问 //队列为空有两种情况: //1. 所有进程运行完了 //2. 当前进程运行完了, 但是下一个没有到达, 这个不用管, 会继续while循环 if (!pq.empty()) { //自身的完成时间+1 ++pq.front().run_time; //如果运行完了, 队首出队, 换下一个运行 if (pq.front().run_time == pq.front().ser_time) { pq.front().fin_time = Time; for (int i = 0; i < n; ++i) { if (pcb[i].name == pq.front().name) { pcb[i] = pq.front(); break; } } pq.pop(); q = time; } else { //没有运行完 //后面还有别的进程, 挂到队尾, 运行的下一个进程 if (!pq.empty() && pq.size() > 1) { if (q == 0) { q = time; pq.push(pq.front()); pq.pop(); } } } } //一个进程运行完但是另一个没有进来, 时间片会轮完, 所以要更新 if (q == 0) q = time; } float tur_sum = 0; float b_tur_sum = 0; //计算后面每一个的各个时间 for (int i = 0; i < n; ++i) { pcb[i].tur_time = pcb[i].fin_time - pcb[i].arr_time; tur_sum += pcb[i].tur_time; pcb[i].b_tur_time = pcb[i].tur_time / pcb[i].ser_time; b_tur_sum += pcb[i].b_tur_time; } Output(pcb, n, tur_sum, b_tur_sum); }

main.cpp

#include "pcb.h" void menu() { cout << "************进程调度算法**********" << endl; cout << "*********1. 先来先服务算法********" << endl; cout << "*********2. 短作业优先算法********" << endl; cout << "*********3. 时间片轮转算法********" << endl; cout << "**************0. 退出************" << endl; cout << "请选择算法:"; }void start() { int choose; while (1) { menu(); cin >> choose; if (choose == 0) { break; } else if (choose == 1) { //先来先服务算法 vector pcb; int n = 0; FCFS(pcb, n); } else if (choose == 2) { //短作业优先算法 vector pcb; int n = 0; SJF(pcb, n); } else if (choose == 3) { //时间片轮转算法 vector pcb; int n = 0; int time = 0; cout << "请输入时间片大小: "; cin >> time; RR(pcb, n, time); } else { cout << "-_-输入错误, 请重新输入-_- " << endl; } } }int main() { start(); system("pause"); return 0; }

运行结果