关于算法:C-抢占时优先级进程调度

45次阅读

共计 6564 个字符,预计需要花费 17 分钟才能阅读完成。

  • 先来先服务
  • 短过程优先算法
  • 优先级调度(抢占)
  • 优先级调度
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct PCB
{
    int id;                          // 过程 id
    double turnaround_time;          // 周转工夫
    double weighted_turnaround_time; // 带权周转工夫
    double wait_time;                // 等待时间
    double start_time;               // 开始工夫
    double coming_time;              // 达到工夫
    double service_time;             // 运行工夫
    double finish_time;              // 实现工夫
    int youxianji;                   // 优先级
    double run_time;                 // 已运行工夫
};

int n;                    // 过程个数
vector<PCB> process_list; // 输出的过程序列
vector<PCB> res;          // 待输入的后果队列

void input_process_count()
{printf("请输出过程数量:");
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        PCB pcb; // pcb 初始化
        pcb.id = i + 1;
        pcb.run_time = 0;            // 初始时已运行工夫为零
        pcb.start_time = -1;         // 为判断是否第一次达到
        process_list.push_back(pcb); // 退出已初始化好的 pcb
    }
}

void input_youxianshu() // 输出优先级
{for (int i = 0; i < n; i++)
    {printf("请输出过程 %d 的优先级:", process_list[i].id);
        scanf("%d", &process_list[i].youxianji);
    }
}

void input_coming_time() // 输出达到工夫
{for (int i = 0; i < n; i++)
    {printf("请输出过程 %d 的达到工夫:", process_list[i].id);
        scanf("%lf", &process_list[i].coming_time);
    }
}

void input_serve_time() // 输出须要服务工夫
{for (int i = 0; i < n; i++)
    {printf("请输出过程 %d 所需工夫", process_list[i].id);
        scanf("%lf", &process_list[i].service_time);
    }
}

int choose_method() // 输出抉择的算法
{
    int select = 0;
    cout << "*****************************************\n";
    cout << "1 \t    先来先服务算法            *******\n";
    cout << "2 \t    短过程优先算法            *******\n";
    cout << "3 \t    优先级调度 (抢占)          *******\n";
    cout << "4 \t    优先级调度 (非抢占)        *******\n";

    cout << "请抉择:";
    cin >> select;
    return select;
}

int cmpByComingTime(PCB a, PCB b) // 依照达到工夫从小到大排序
{return a.coming_time < b.coming_time;}

int cmpByServiceTime(PCB a, PCB b) // 依照须要服务工夫从大到小排序
{return a.service_time > b.service_time;}

void FCFS()
{sort(process_list.begin(), process_list.end(), cmpByComingTime); // 先依照达到工夫排序
    double time = process_list[0].coming_time;                       // 初始化工夫
    for (int i = 0; i < n; i++)
    {PCB pcb = process_list[i]; // 因为曾经依照工夫排序,所以以后为待运行的过程
        // 更新以后过程的信息
        pcb.start_time = time;
        pcb.wait_time = time - pcb.coming_time;
        pcb.finish_time = time + pcb.service_time;
        pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
        pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
        time = pcb.finish_time; // 以以后过程的工夫更新 time
        process_list[i] = pcb;
        res.push_back(pcb); // 退出后果队列
    }
}

void SJF()
{
    int top = 0;
    vector<PCB> short_jobs;                                          // 定义短过程队列 其中数据由大到小
    sort(process_list.begin(), process_list.end(), cmpByComingTime); // 依照达到工夫初始化
    double time = process_list[0].coming_time;                       // 初始化工夫
    while (top < n || !short_jobs.empty())                           // 如果两个对列里依然存在元素
    {if (short_jobs.empty()) // 如果队列未空,则退出以后曾经达到的过程
            short_jobs.push_back(process_list[top++]);

        PCB pcb = short_jobs[int(short_jobs.size() - 1)]; // 取出工夫最短的
        if (pcb.start_time == -1)
            pcb.start_time = time;
        // 更新 pcb 的工夫
        pcb.wait_time = time - pcb.coming_time;
        pcb.finish_time = time + pcb.service_time;
        pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
        pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
        time = pcb.finish_time;

        // 退出到运行完结队列
        res.push_back(pcb);
        short_jobs.pop_back();
        // 如果在上个过程运行期间有过程达到则退出 short_jobs 队列
        for (; top < n && process_list[top].coming_time < time; top++)
        {short_jobs.push_back(process_list[top]);
        }
        // 因为有新的过程退出,所以对 short_jobs 进行排序
        sort(short_jobs.begin(), short_jobs.end(), cmpByComingTime);
    }
}

bool cmpByPriority(PCB a, PCB b) // 依照优先级排序
{if (a.youxianji == b.youxianji)
        return a.coming_time > b.coming_time;
    return a.youxianji < b.youxianji;
}

void PriorityNo() // 非抢占优先级调度
{
    int top = 0; // 定义头指针
    vector<PCB> priority_higher;
    sort(process_list.begin(), process_list.end(), cmpByComingTime);
    double time = process_list[0].coming_time;
    while (top < n || !priority_higher.empty()) // 如果仍有过程未运行完结
    {if (priority_higher.empty()) // 为空则退出新的过程
            priority_higher.push_back(process_list[top++]);

        PCB pcb = priority_higher[int(priority_higher.size() - 1)]; // 取出要运行的过程
        if (pcb.start_time == -1)                                   // 如果是第一次到达则更新工夫
            pcb.start_time = time;

        // 更新 pcb
        pcb.wait_time = time - pcb.coming_time;
        pcb.finish_time = time + pcb.service_time;
        pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
        pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
        time = pcb.finish_time;

        res.push_back(pcb);         // 运行完结则退出 res
        priority_higher.pop_back(); // 并删除已运行完结的过程

        for (; top < n && process_list[top].coming_time < time; top++)
        { // 退出在此期间达到的过程
            priority_higher.push_back(process_list[top]);
        }
        // 因为有新过程退出,进行排序
        sort(priority_higher.begin(), priority_higher.end(), cmpByPriority);
    }
}

void PriorityYes()
{
    int top = 0;
    vector<PCB> priority_higher;
    sort(process_list.begin(), process_list.end(), cmpByComingTime);
    double time = process_list[0].coming_time;  // 初始化工夫
    while (top < n || !priority_higher.empty()) // 如果仍有过程未完结
    {if (priority_higher.empty()) // 如果为空,则退出新的过程
            priority_higher.push_back(process_list[top++]);

        PCB pcb = priority_higher[int(priority_higher.size() - 1)]; // 取出优先级最高的过程运行
        if (pcb.start_time == -1)                                   // 如果是第一次达到,则记录开始工夫
        {
            pcb.start_time = time;
            pcb.wait_time = pcb.start_time - pcb.coming_time;
        }
        if (top < n && process_list[top].coming_time <= time + pcb.service_time - pcb.run_time) // 如果仍有未退出的过程, 并且在运行期间有新的过程达到
        {pcb.run_time += process_list[top].coming_time - time;                // 则先运行间隔下个过程达到的工夫
            time += process_list[top].coming_time - time;                        // 并更新工夫
            priority_higher[priority_higher.size() - 1] = pcb;                   // 更新队列
            priority_higher.push_back(process_list[top++]);                      // 把下一个过程退出
            sort(priority_higher.begin(), priority_higher.end(), cmpByPriority); // 并进行排序
            if (pcb.run_time == pcb.service_time)                                // 如果以后过程的运行工夫曾经够了,则更新 pcb 信息,并删除过程
            {
                pcb.finish_time = time;
                pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
                pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
                res.push_back(pcb);
                priority_higher.pop_back();}
        }
        else // 如果没有新的过程达到, 则将以后过程运行结束
        {
            pcb.finish_time = time + pcb.service_time - pcb.run_time;
            pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
            pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
            time = time + pcb.service_time - pcb.run_time;
            res.push_back(pcb); // 运行结束则退出 res
            priority_higher.pop_back();}
    }
}

bool cmpById(PCB a, PCB b)
{return a.id < b.id;}

void print_schedulInfo()
{printf("过程编号 \t 提交工夫 \t 运行工夫 \t 开始工夫 \t 等待时间 \t 实现工夫 \t 周转工夫 \t 带权周转工夫 \n");
    // cout << res.size() << endl;
    sort(res.begin(), res.end(), cmpById); // 依照 ID 排序
    double start = 0x3f3f3f3f3f, end = 0;
    double allTT = 0, allWTT = 0, runTime = 0;
    for (int i = 0; i < n; i++)
    {PCB pcb = res[i];
        start = min(start, pcb.start_time);     // 失去开始工夫
        end = max(end, pcb.finish_time);        // 所有过程完结工夫
        allTT += pcb.turnaround_time;           // 总的周转工夫
        allWTT += pcb.weighted_turnaround_time; // 总的带权周转工夫
        runTime += pcb.service_time;            // 总的服务工夫
        printf("%8d\t%8.2f\t%8.2f\t%8.2f\t%8.2f\t%8.2f\t%8.2f\t%8.2f\n", pcb.id, pcb.coming_time, pcb.service_time, pcb.start_time, pcb.wait_time, pcb.finish_time, pcb.turnaround_time, pcb.weighted_turnaround_time);
    }

    printf("均匀周转工夫 %.2f\t 均匀带权周转工夫 %.2f\tCPU 利用率 %.2f\t 零碎吞吐量 %.2f\n", allTT / n, allWTT / n, (runTime) / (end - start), (n) / (end - start));
}

int main()
{
    // 4 1 1 1 1 9 8 8.4 8.8 0.2 2 1 0.5
    // 4 2 4 3 1 10 20 30 50 20 30 25 20
    // 4 1 2 3 2 0 2 4 5 7 4 1 4
    input_process_count();        // 输入过程数量
    input_youxianshu();           // 输出优先级数
    input_coming_time();          // 输出达到工夫
    input_serve_time();           // 输出须要服务工夫
    int choose = choose_method(); // 失去用户抉择的数
    // printf("%d\n", choose);
    switch (choose)
    {
    case 1:
        FCFS(); // 先来先服务
        break;
    case 2:
        SJF(); // 短作业优先
        break;
    case 3:
        PriorityYes(); // 优先级抢占式
        break;
    default:
        PriorityNo(); // 优先级非抢占式
        break;
    }
    print_schedulInfo(); // 打印后果
    return 0;
}

正文完
 0