作業系統進程調度之分時，優先，分時優先

• 2021 年 5 月 25 日
• 筆記
• C&C++, 作業系統

process.h

//
// Created by youlingdada on 2021/5/9.
//

/**
 * 模擬進程調度
 */
#include <iostream>
#include <queue>
#include <cstring>
#include <fstream>

#ifndef DEMO_PROCESS_H
#define DEMO_PROCESS_H
#endif //DEMO_PROCESS_H

#define PRO_NUMBER 8   // 進程數量
#define TIME_PAGE 2  // 時間片大小

using namespace std;

// 進程的狀態
enum STATUS {
    PRO_WAIT,   // 等待
    PRO_READY,   // 準備
    PRO_RUN,    // 運行
    PRO_FINISH  // 完成
};


// 進程
typedef struct {
    int id;
    int priority;  // 優先順序
    int cup_time;      // 佔用cpu的時間
    int all_time;      // 整個進程所需要的時間
    int arrived_time;  // 進程到達時間
    int remain_time;   // 進程剩餘時間
    int finish_time;   // 進程完成時間
    STATUS status;     // 進程狀態
} Process;


// 仿函數 設定優先等待隊列的比較規則 按時間先後排序
typedef struct {
    bool operator()(Process process1, Process process2) {
        return process1.arrived_time > process2.arrived_time;
    }
} functional_wait_queue;

//仿函數 設定優先就緒隊列的比較規則 按優先順序排序
typedef struct {
    bool operator()(Process process1, Process process2) {
        return process1.priority > process2.priority;
    }
} functional_priority_queue;

// 普通就緒隊列
queue<Process> pro_ready_queue;  // 就緒隊列
priority_queue<Process, vector<Process>, functional_priority_queue> pro_ready_priority_queue; // 優先隊列

int os_time;  // 系統時間

priority_queue<Process, vector<Process>, functional_wait_queue> pro_wait_queue;


// 初始化函數 給等待隊列賦予初值
void init(const string &init_data_path) {
    os_time = 0;
    Process pro;
    ifstream in;
    in.open(init_data_path);
    while (pro_wait_queue.size() < PRO_NUMBER) {
        in >> pro.id;
        in >> pro.priority;
        in >> pro.all_time;
        in >> pro.arrived_time;
        pro.cup_time = 0;
        pro.remain_time = pro.all_time;
        pro.finish_time = 0;
        pro.status = PRO_WAIT;
        pro_wait_queue.push(pro);
    }
}

// 進程進入就緒隊列
void ready(Process &pro);

// 進程運行
void run(Process &pro);

// 進程結束
void finish(Process &pro) {
    if (pro.remain_time == 0) {
        pro.status = PRO_FINISH;
        pro.finish_time = os_time;
        cout << pro.id << " complete and finish time is " << pro.finish_time << endl;
    }
}

// 進程生命周期函數
void pro_run();

// 如果進程運行完了,後面的進程還沒有到,直接將os_time調到下一個進程到達時間
void first() {
    if (!pro_wait_queue.empty()) os_time = pro_wait_queue.top().arrived_time;
}

// 結果輸出到文件
void output_to_file(const char *output_data_path);

分時調度

//
// Created by youlingdada on 2021/5/9.
//

#include "process.h"

using namespace std;

void ready(Process &pro) {
    pro.status = PRO_READY;
    pro_ready_queue.push(pro);
}

void run(Process &pro) {
    pro.status = PRO_RUN;

    if (pro.remain_time < TIME_PAGE) {
        pro.cup_time += pro.remain_time;
        os_time += pro.remain_time;
        pro.remain_time = 0;
    } else {
        os_time += TIME_PAGE;
        pro.cup_time += TIME_PAGE;
        pro.remain_time -= TIME_PAGE;
    }

    cout << pro.id << " run and remain time is " << pro.remain_time << "----- os time is : " << os_time << endl;
    pro.status = PRO_WAIT;
}


void pro_run() {
    Process temp, pro;
    temp.status = PRO_FINISH;
    while (true) {
        if (pro_wait_queue.empty() && pro_ready_queue.empty() && temp.status == PRO_FINISH) break;

        while (!pro_wait_queue.empty() && os_time >= pro_wait_queue.top().arrived_time) {
            pro = pro_wait_queue.top();
            ready(pro);
            pro_wait_queue.pop();
        }

        if (temp.remain_time > 0 && temp.status == PRO_WAIT) ready(temp);
        if (pro_ready_queue.empty()) first();

        if (!pro_ready_queue.empty())temp = pro_ready_queue.front();
        else exit(0);

        run(temp);
        finish(temp);

        pro_ready_queue.pop();
    }
}

int main() {
    init("init_data.txt");
    pro_run();
    cout << "over" << endl;
}

非搶佔式的優先順序調度

//
// Created by youlingdada on 2021/5/9.
//

/**
 * 非搶佔式的優先
 */

#include "process.h"

void ready(Process &pro) {
    pro.status = PRO_READY;
    pro_ready_priority_queue.push(pro);
}

void run(Process &pro) {
    pro.status = PRO_RUN;
    pro.remain_time = 0;
    pro.cup_time = pro.all_time;
    os_time += pro.all_time;
}


void pro_run() {
//    定義兩個進程變數
    Process temp, pro;

    while (true) {
//        如果進程全部完成的情況,就跳出循環
        if (pro_wait_queue.empty() && pro_ready_priority_queue.empty() && temp.status == PRO_FINISH) break;

        while (!pro_wait_queue.empty() && os_time >= pro_wait_queue.top().arrived_time) {
            pro = pro_wait_queue.top();
            ready(pro);
            pro_wait_queue.pop();
        }

        if (pro_ready_priority_queue.empty()) first();

        temp = pro_ready_priority_queue.top();
        run(temp);

        finish(temp);
        pro_ready_priority_queue.pop();

    }

}

int main() {
    init("init_data.txt");
    pro_run();
    cout << "over" << endl;
}

分時優先調度

//
// Created by youlingdada on 2021/5/10.
//

#include "process.h"

void ready(Process &pro) {
    pro.status = PRO_READY;
    pro_ready_priority_queue.push(pro);
}

void run(Process &pro) {
    pro.status = PRO_RUN;

    if (pro.remain_time < TIME_PAGE) {
        pro.cup_time += pro.remain_time;
        os_time += pro.remain_time;
        pro.remain_time = 0;
    } else {
        os_time += TIME_PAGE;
        pro.cup_time += TIME_PAGE;
        pro.remain_time -= TIME_PAGE;
    }

    cout << pro.id << " run and remain time is " << pro.remain_time << "----- os time is : " << os_time << endl;
    pro.status = PRO_WAIT;
}


void pro_run() {
    Process temp, pro;
    temp.status = PRO_FINISH;
    while (true) {
        if (pro_wait_queue.empty() && pro_ready_priority_queue.empty() && temp.status == PRO_FINISH) break;

        while (!pro_wait_queue.empty() && os_time >= pro_wait_queue.top().arrived_time) {
            pro = pro_wait_queue.top();
            ready(pro);
            pro_wait_queue.pop();
        }

        if (os_time >= TIME_PAGE && temp.remain_time > 0 && temp.status == PRO_WAIT) ready(temp);
        if (pro_ready_priority_queue.empty()) first();

        if (!pro_ready_priority_queue.empty()) temp = pro_ready_priority_queue.top();
        else exit(0);


        run(temp);
        finish(temp);

        pro_ready_priority_queue.pop();
    }
}

int main() {
    init("init_data.txt");
    pro_run();
    cout << "over" << endl;
}

輸入數據init_data.txt 文件

1 1 5 0
2 1 7 4
3 2 5 2
4 2 7 1
5 2 5 0
6 4 7 1
7 3 5 0
8 2 7 1