操作系统实验一: 进程调度

实验1 进程调度（2学时）

一、实验目的
通过实验加强对进程调度算法的理解和掌握。
二、实验内容
编写程序实现基于优先级的时间片轮转调度算法。
三、实验要求
1、假定系统有5个进程，每个进程用一个进程控制块PCB来代表，
其中：
进程名：作为进程的标识，假设五个进程的进程名分别为p1，p2，p3，p4，p5。
指针：进程按顺序排成循环链表，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出第一个进程的进程控制块首地址。
要求运行时间：假设进程需要运行的单位时间数。
已运行时间：假设进程已经运行的单位时间数，初值为0。
状态：可假设有两种状态，就绪状态和结束状态。进程的初始状态都为就绪状态。
2、每次运行所设计的处理器调度程序调度进程之前，为每个进程随机确定它的要求运行时间和优先级（数值越大，优先级越高）。
3、进程调度依据优先级进行，优先级随着时间动态增加，每经过一个时间片，优先级加1。
4、此程序是模拟处理器调度，因此，被选中的进程并不实际启动运行，而是执行
已运行时间+1
来模拟进程的一次运行，表示进程已经运行过一个单位时间。
5、在所设计的程序中应有显示语句，能显示每次被选中的进程名以及运行一次后进程队列的变化。

#include 
#include 
#include 
#include 
#include 
using namespace std;

struct PCB{
    string name; // 进程名
    int prio; // 优先级
    int requ_time; // 要求运行时间
    int fini_time; // 已运行时间
    bool state; // 进程状态
    PCB* next; // 指向下一个进程的指针
    void init（string name）{ // 进程初始化
        this->name = name;
        prio = rand（）%10+1; // 随机优先级
        requ_time = rand（）%20+1; // 随机要求运行时间
        fini_time = 0; // 已运行时间初始化为0
        state = false; // 进程状态为false 表示还没完成，处于就绪状态; 为true 表示已经完成，处于结束状态
    }
};
PCB p[6];
PCB* it;

bool cmp（PCB A PCB B）{ // 对进程的排序函数
    if（A.state==false && B.state==false）{ // 都处于就绪状态，如果优先级相等，则还需要完成时间短的排在前面，否则优先级高的排在前面
        if（A.prio == B.prio） return （A.requ_time-A.fini_time）<（B.requ_time-B.fini_time）;
        return A.prio>B.prio;
    }else{ // 如果有进程处于完成状态，则处于就绪状态的排在前面
        if（A.state==false） return true;
        else if（B.state==false） return false;
        else return A.prio>B.prio;
    }
}

bool check（）{ // 检查是否所有进程都完成了，都完成了返回true还有没完成的返回false
    bool ret = true;
    it = &p[1];
    for（int i=1; i<6; i++）{
        if（it->state == false） { // 仍有没完成的
            ret = false;
            break;
        }
        it = it->next;
    }
    return ret;
}

void change（）{ // 对于重新排序完的链表，修改他们的指针
    for（int i=1; i<6; i++）{
        p[i].next = &p[i+1];
    }
    p[5].next = &p[1];
}

void print（）{ // 打印进程状态
    it = &p[1];
    cout << “进程名“ << “\t“ << “优先级“ << “\t“ << “要求运行时间“ << “\t“ << “已运行时间“ << “\t“ << “进程状态“ << endl;
    for（int i=1; i<6; i++）{
        cout << it->name << “\t“ << it->prio << “\t“ << it->requ_time << “\t\t“ << it->fini_time << “\t\t“ << it->state << endl;
        it = it->next;
    }
}

int main（）
{
    srand（time（NULL））; // 随机的种子
    p[1].init（“p1“）; p[2].init（“p2“）; p[3].init（“p3“）; p[4].init（“p4“）; p[5].init（“p5“）; // 初始化每一个进程
    change（）;
    cout << “进程初始状态为: “ << endl;
    print（）;
    sort（p+1p+6cmp）; // 按照优先级对进程重新排序
    change（）;
    cout << “经过优先级排序后，进程循环链表为: “ << endl;
    print（）;
    int now = 0; // 当前运行的时间
    while（check（） == false）{ // 如果仍然有没完成的进程， CPU继续运行
        now++; // 时间+1
        it = &p[1]; // it是处于链表第一个的地址，代表处于就绪状态的进程且优先级最高
        it->fini_time++; // 执行
        if（it->fini_time == it->requ_time） { // 该进程完成
            it->state = true; // 更改为完成状态
            cout << “在经过“ << now << “个时间片后 “ << it->name << “进程运行完毕！“ << endl;
            cout << “此时进程状态：“ << endl;
            print（）;
        }
        it = it->next; // 指向下一个进程
        for（int i=2; i<6; i++）{
            if（it->state == true） break;
            it->prio++; // 除了当前的进程，其他处于就绪状态的进程优先级+1
			it = it->next;
        }
        sort（p+1p+6cmp）; // 按照优先级重新排序
        change（）; // 更改指针
    }
    cout << “********在经过“ << now << “个时间片后，全部进程运行完毕! ***********“ << endl;
    print（）;

    return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        3356  2018-04-27 08:05  main.cpp
     文件       33792  2018-04-25 15:15  实验1.doc