进程调度算法

1.实验目的

多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。

2.实验内容与要求

1． 优先权法、轮转法
简化假设
1） 进程为计算型的（无I/O）
2） 进程状态：ready、running、finish
3） 进程需要的CPU时间以时间片为单位确定
2． 算法描述
1） 优先权法——动态优先权
当前运行进程用完时间片后，其优先权减去一个常数。
2） 轮转法
3.流程图与模块调用

讯享网

4.实验分析

优先权法：整个调度过程随着优先权而进行；优先权高的显进行调度，调度完成后优先级减3；再根据下次优先权高的继续调度；直到所需运行时间减为0。
轮转调度法：整个调度过程按照普通的队列来进行，一个进程调度一次后，插入列尾，或者所需运行时间为0，则弹出队列。
根据情况，实现优先权法采用优先队列，轮转调度法采用普通队列。

5.运行情况

6.实验体会

本次实验通过模拟操作系统进程调度算法，能够更直观和清晰的感受到进程调度这一过程，操作系统是如何在用户“看不到”的情况下实现整个流程的，尽管实际上操作系统在实现该算法时会牵扯到更多的硬件及软件，但对于理解整个进程调度而言，实现算法后，已经能很好的做到了。本次实验，所采用的C++的优先队列及队列，对于实现整个算法而言，使整个流程更简便，实现起来也更容易。

代码如下（C++）

#include <iostream> #include<queue> #include<time.h> #include<stdlib.h> using namespace std; typedef struct { 
    int pid;//进程名 string state;//状态：ready running finish int prio;//优先级 int use_c;//已经占用的CPU时间 int cirtime;//轮转时间 int need_c;//还需CPU时间片数 }PCB; typedef struct node { 
    PCB con; struct node* next; bool operator<(node p)const { 
    return con.prio < p.con.prio; } }Lnode, * Llist;//封装成结点 priority_queue<Lnode>prio;//优先级调度队列 queue<Lnode>cir;//轮转调度队列 //优先级输出 void pri_prio(priority_queue<Lnode>q, Lnode a) { 
    cout << "------进程:" << a.con.pid << "------" << endl; cout << "优先级:" << a.con.prio << endl; cout << "状态:" << a.con.state << endl; cout << "还需cpu片数:" << a.con.need_c << endl; while (!q.empty()) { 
    a = q.top(); q.pop(); cout << "------进程:" << a.con.pid << "------" << endl; cout << "优先级:" << a.con.prio << endl; cout << "状态:" << a.con.state << endl; cout << "还需cpu片数:" << a.con.need_c << endl; } cout << "" << endl; } //轮转输出 void pri_cir(queue<Lnode>q, Lnode a) { 
    cout << "------进程:" << a.con.pid << "------" << endl; cout << "轮转时间上限:" << a.con.cirtime << endl; cout << "已经占用的cpu:" << a.con.use_c << endl; cout << "状态:" << a.con.state << endl; cout << "还需cpu片数:" << a.con.need_c << endl; while (!q.empty()) { 
    a = q.front(); q.pop(); cout << "------进程:" << a.con.pid << "------" << endl; cout << "轮转时间上限:" << a.con.cirtime << endl; cout << "已经占用的cpu:" << a.con.use_c << endl; cout << "状态:" << a.con.state << endl; cout << "还需cpu片数:" << a.con.need_c << endl; } cout << "" << endl; } //优先级调度算法 void priority() { 
    while (!prio.empty()) { 
    Lnode p_t = prio.top();//链首 prio.pop(); p_t.con.state = "running"; Lnode top; if (!prio.empty()) { 
    top = prio.top(); } while (p_t.con.prio >= top.con.prio || prio.empty()) { 
    pri_prio(prio, p_t); p_t.con.prio -= 3; p_t.con.need_c--; if (p_t.con.need_c == 0) { 
    p_t.con.state = "finish"; cout << "已完成:" << p_t.con.pid << endl; break; } } if (p_t.con.state != "finish") { 
    p_t.con.state = "ready"; prio.push(p_t); } } cout << endl; } //轮转调度算法 void circ() { 
    while (!cir.empty()) { 
    Lnode roat = cir.front(); cir.pop(); roat.con.state = "running"; while (roat.con.use_c < roat.con.cirtime) { 
    pri_cir(cir, roat); \ roat.con.use_c++; roat.con.need_c--; if (roat.con.need_c == 0) { 
    roat.con.state = "finish"; cout << "已完成:" << roat.con.pid << endl; break; } } if (roat.con.state != "finish") { 
    roat.con.state = "ready"; roat.con.use_c = 0; cir.push(roat); } } cout << endl; } int main() { 
    cout << "请输入进程数：" << endl; int n; cin >> n; char choose; cout << "是否选择优先权法进行调度？" << endl << "Y or N" << endl; cin >> choose; Lnode q; srand((unsigned)time(NULL));//随机种子 if (choose == 'Y')//优先权 { 
    q.con.state = "ready";//初始值 q.con.cirtime = 1; q.con.use_c = 1; q.next = NULL; for (int i = 1; i <= n; i++) { 
    q.con.pid = i; // cin >> q.con.need_c >> q.con.prio; q.con.need_c = (rand() % (n - 1 + 1)) + 1; q.con.prio = (rand() % (n - 1 + 1)) + 1; prio.push(q); } priority(); } else { 
   //轮转 q.con.state = "ready";//初始值 q.con.prio = 1; q.con.use_c = 0; q.next = NULL; for (int i = 1; i <= n; i++) { 
    q.con.pid = i; q.con.need_c = (rand() % (n - 1 + 1)) + 1; q.con.cirtime = (rand() % (n - 1 + 1)) + 1; cir.push(q); } circ(); } return 0; }