Que signifie l'algorithme de planification prioritaire préemptive ?

Le système alloue le processeur au processus ayant la priorité d'exécution la plus élevée. Mais lors de son exécution, tant qu'un autre processus avec une priorité plus élevée apparaît, le planificateur de processus arrêtera immédiatement l'exécution du processus en cours (le processus d'origine avec la priorité la plus élevée) et réaffectera le processeur à la priorité nouvellement arrivée. .

L'environnement d'exploitation de ce tutoriel : système Windows 7, version C++17, ordinateur Dell G3.

Algorithme de planification prioritaire préemptive

De cette manière, le système alloue le processeur au processus ayant la priorité d'exécution la plus élevée. Mais lors de son exécution, tant qu'un autre processus avec une priorité plus élevée apparaît, le planificateur de processus arrêtera immédiatement l'exécution du processus en cours (le processus d'origine avec la priorité la plus élevée) et réaffectera le processeur à la priorité nouvellement arrivée. . Par conséquent, lors de l’utilisation de cet algorithme de planification, chaque fois qu’un nouveau processus prêt i apparaît dans le système, sa priorité Pi est comparée à la priorité Pj du processus en cours d’exécution j. Si Pi ≤ Pj, le processus d'origine Pj continuera à s'exécuter ; mais si Pi > Pj, l'exécution de Pj sera immédiatement arrêtée et une commutation de processus sera effectuée pour mettre le processus i en exécution. De toute évidence, cet algorithme de planification prioritaire préemptive peut mieux répondre aux exigences des tâches urgentes, il est donc souvent utilisé dans les systèmes en temps réel avec des exigences plus strictes, ainsi que dans les systèmes de traitement par lots et en temps partagé avec des exigences de performances plus élevées.

Code spécifique :

#include <iostream>#include <string>#include <vector>using namespace std;using std::cout;struct PCB
{    // 进程名
    string name;    // 到达时间
    int arrivetime;    // 运行时间
    int runtime;                
    // 仍需运行时间
    int resttime;    // 开始时间
    int starttime;    // 完成时间
    int endtime;    // 运行次数
    int runcount;    // 周转时间
    int zhouzhuangtime;    // 带权周转时间（周转时间/运行时间)
    double weightzhouzhuangtime;    // 优先级（静态）
    int priority;

    PCB *next;
};// 进程数int num_process;// 记录所有进程的总时间int totaltime;// 记录所有进程的总带权周转时间double weighttotaltime;

PCB *createPCB()
{    int i;    // 定义队首、队尾
    PCB *head, *rear;    // 初始化
    head = rear = NULL;    // 临时指针变量
    PCB *p;    cout<<"请输入进程数量：";    cin>>num_process;    for(i = 0; i < num_process; i++)
    {        // 初始化一个空间给进程
        p = new PCB;        cout<<"请依次输入第"<<i+1<<"个进程的信息（进程名、优先级、到达时间、运行时间）："<<endl;        cin>>p->name>>p->priority>>p->arrivetime>>p->runtime;
        p->resttime = p->runtime;
        p->runcount = 1;
        totaltime += p->runtime;
        p->starttime = 0;
        p->endtime = 0;
        p->zhouzhuangtime = 0;
        p->weightzhouzhuangtime = 0;
        p->next = NULL;        // 存入链表中
        if(rear == NULL)
        {
            head = p;
            rear = p;
        }        else
        {
            rear->next = p;
            rear = p;
        }

    }    return head;
}// 链表插入排序PCB *insertSort(PCB *head)
{    /*
        1、先在原链表中以第一个节点为一个有序链表，其余节点为待定节点；
        2、从待定节点中取节点，插入到有序链表中相应位置；
        3、实际上只有一条链表，在排序中，实际只增加了一个用于指向剩下需要排序节点的头指针。
    */
    PCB *first;// 为原链表剩下用于直接插入排序的节点头指针
    PCB *t; // 临时指针变量：要插入的节点
    PCB *p; // 临时指针变量：要插入的位置
    PCB *q; // 临时指针变量：指向原链表

    first = head->next;
    head->next = NULL; // 只含有一个节点的链表的有序链表

    while(first != NULL) // 遍历剩下的无序链表
    {        // 无序节点在有序链表中找插入位置p
        for(t = first, q = head; (q != NULL) && (q->arrivetime < t->arrivetime); p = q, q = q->next);        // 无序链表中的节点离开，以便插入到有序链表中
        first = first->next;        if(q == head)// 插入在第一个节点之前
        {
            head = t;
        }        else// p是q的前驱
        {
            p->next = t;
        }
        t->next = q;// 完成插入动作
    }    return head;
}// 获取当前时间段内的进程数量int getCurrentNumOfProcess(PCB *head, int time)
{    int count = 0;
    PCB *t;// 临时指针变量，指向链表
    t = head;    while(t != NULL && t->arrivetime <= time)
    {
        count++;
        t = t->next;
    }    return count;
}// 删除当前节点PCB* deletePCB(PCB *head, PCB *t)
{
    PCB *p, *q;
    p = head;
    q = p->next;    // 删除节点是头节点
    if(t == head)
    {
        head = head->next;
    }    else 
    {        while(q != t)// 跳出循环之后q为该节点，p为前一节点
        {
            p = p->next;
            q = p->next;
        }        if(t->next == NULL)// 删除节点是尾节点
            p->next = NULL;        else
            p->next = q->next;
    }    // 删除
    free(t);    return head;
}// 在头节点后的count个节点中选择优先数最大的返回PCB *findMaxPriority(PCB *head, int count)
{    int max;
    PCB *p, *q, *f;
    q = head;
    max = q->priority;
    f = q;    while(count > 0)
    {        if(q->priority > max)
        {
            max = q->priority;
            f = q;
        }
        count--;
        q =q->next;
    }    return f;

}/* 
    输出a时间内的特定输出格式,当某一时间段内没有进程工作时，进程名称为0
    进程名称.进程工作时间，进程与进程间以|分隔
    输入：1 3 2 8
          2 2 1 7
          3 6 3 12
    输出：[0.1|2.1|1.1|3.12|1.7|2.6|0.172]
*/void print(vector<PCB> vec_output, int a)
{    for(int i = 0; i < vec_output.size(); i++)
    {        cout<<"******************************************"<<endl;        cout<<"进程名："<<vec_output[i].name<<endl;        cout<<"到达时间："<<vec_output[i].arrivetime<<endl;        cout<<"开始运行时间: "<<vec_output[i].starttime<<endl;        cout<<"结束运行时间: "<<vec_output[i].endtime<<endl;        cout<<"此次运行时间："<<vec_output[i].endtime - vec_output[i].starttime<<endl;        cout<<"******************************************"<<endl;        cout<<endl;        cout<<endl;
    }    // 输出周转时间信息,只有进程结束了才输出
    int i;    for(i = 0; i < vec_output.size()-1; i++)
    {        bool flag = true;        for(int j = i+1; j < vec_output.size(); j++)
        {            if(vec_output[j].name == vec_output[i].name)
            {
                flag = false;                break;
            }
        }        if(flag)
        {            cout<<"进程"<<vec_output[i].name<<"的周转时间为："<<vec_output[i].zhouzhuangtime<<endl;            cout<<"进程"<<vec_output[i].name<<"的带权周转时间为: "<<vec_output[i].weightzhouzhuangtime<<endl;            cout<<endl;            cout<<endl;
        }
    }    cout<<"进程"<<vec_output[i].name<<"的周转时间为："<<vec_output[i].zhouzhuangtime<<endl;    cout<<"进程"<<vec_output[i].name<<"的带权周转时间为: "<<vec_output[i].weightzhouzhuangtime<<endl;    cout<<endl;    cout<<endl;    // 输出平均周转时间信息
    cout<<"平均周转时间："<<totaltime/(double)num_process<<endl;    cout<<"平均带权周转时间："<<weighttotaltime/(double)num_process<<endl;    cout<<endl;    cout<<endl;    cout<<a<<"个时间单位内的执行顺序为："<<endl;    cout<<"[";    if(vec_output[0].starttime > 0)
    {        cout<<"0."<<vec_output[0].starttime<<"|";
    }    if(vec_output[vec_output.size() - 1].endtime < a)
    {        for(int i = 0; i < vec_output.size(); i++)
        {            cout<<vec_output[i].name<<"."<<vec_output[i].endtime - vec_output[i].starttime<<"|";            // 补全从开始到结束之间没有进程运行项
            if(i+1 < vec_output.size() && vec_output[i].endtime != vec_output[i+1].starttime)
            {                cout<<"0."<<vec_output[i+1].starttime - vec_output[i].endtime<<"|";
            }
        }        cout<<"0."<<a-vec_output[vec_output.size()-1].endtime<<"]"<<endl;
    }    else if(vec_output[vec_output.size() - 1].endtime == a)
    {        for(int i = 0; i < vec_output.size()-1; i++)
        {            cout<<vec_output[i].name<<"."<<vec_output[i].endtime - vec_output[i].starttime<<"|";            // 补全从开始到结束之间没有进程运行项
            if(i+1 < vec_output.size() && vec_output[i].endtime != vec_output[i+1].starttime)
            {                cout<<"0."<<vec_output[i+1].starttime - vec_output[i].endtime<<"|";
            }
        }        cout<<vec_output[vec_output.size()-1].name<<"."<<vec_output[vec_output.size()-1].endtime - vec_output[vec_output.size()-1].starttime<<"]"<<endl;
    }    else
    {        for(int i = 0; i < vec_output.size(); i++)
        {            if(vec_output[i].endtime <= a)
            {                cout<<vec_output[i].name<<"."<<vec_output[i].endtime - vec_output[i].starttime<<"|";                // 补全从开始到结束之间没有进程运行项
                if(i+1 < vec_output.size() && vec_output[i].endtime != vec_output[i+1].starttime)
                {                    cout<<"0."<<vec_output[i+1].starttime - vec_output[i].endtime<<"|";
                }
            }            else
            {                cout<<vec_output[i].name<<"."<<a - vec_output[i].starttime<<"]"<<endl;                return;
            }
        }
    }
}void PCB_MAIN(PCB *head)
{
    head = insertSort(head);    int time = 0;// 模拟时间变量
    int count;// 当前时间内运行的进程数量
    PCB *q;    vector<PCB> vec_out;//输出
    PCB temp;    while(head != NULL)
    {
        count = getCurrentNumOfProcess(head, time);        if(count == 0)
            time++;        else
        {            /************************************************************************/
            /* 抢占式                                                               */
            /************************************************************************/
            // 找出优先数最大的线程
            q = findMaxPriority(head, count);            if(q->runcount == 1)// 该进程第一次运行
            {
                q->starttime = time;                // 输出信息
                temp = *q;
                temp.endtime = 0;
                temp.next = NULL;                if(vec_out.size() != 0 && vec_out[vec_out.size()-1].endtime == 0)
                {
                    vec_out[vec_out.size()-1].endtime = temp.starttime;
                }
                vec_out.push_back(temp);
            }
            ++time;
            ++q->runcount;
            --q->resttime;            if(q->resttime == 0)// 该进程运行结束
            {                // 记录结束时间
                q->endtime = time;                // 计算周转时间
                q->zhouzhuangtime = time - q->arrivetime;                // 计算带权周转时间
                q->weightzhouzhuangtime = q->zhouzhuangtime/(double)q->runtime;
                weighttotaltime += q->weightzhouzhuangtime;                // 输出信息
                temp = *q;
                temp.starttime = 0;
                temp.next = NULL;                if(vec_out[vec_out.size()-1].name == temp.name)
                {
                    vec_out[vec_out.size()-1].endtime = temp.endtime;
                    vec_out[vec_out.size()-1].zhouzhuangtime = temp.zhouzhuangtime;
                    vec_out[vec_out.size()-1].weightzhouzhuangtime = temp.weightzhouzhuangtime;
                }                else
                {
                    temp.starttime = vec_out[vec_out.size()-1].endtime;
                    vec_out.push_back(temp);
                }                // 删除该进程
                //deletePCB(q);
                head = deletePCB(head, q);
            }
        }
    }    // 输出200时间单位内的执行顺序
    print(vec_out, 200);
}int main()
{
    PCB *head = NULL;
    head = createPCB();
    PCB_MAIN(head);    return 0;
}

Exemple de sortie

Entrée :

Sortie :

Tutoriel recommandé : "C# "

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!