What does preemptive priority scheduling algorithm mean?

The system assigns the processor to the process with the highest priority for execution. But during its execution, as long as another process with a higher priority appears, the process scheduler will immediately stop the execution of the current process (the original process with the highest priority) and reassign the processor to the newly arrived priority. The highest process.

The operating environment of this tutorial: Windows 7 system, C 17 version, Dell G3 computer.

Preemptive priority scheduling algorithm

In this method, the system assigns the processor to the process with the highest priority for execution. But during its execution, as long as another process with a higher priority appears, the process scheduler will immediately stop the execution of the current process (the original process with the highest priority) and reassign the processor to the newly arrived priority. The highest process. Therefore, when using this scheduling algorithm, whenever a new ready process i appears in the system, its priority Pi is compared with the priority Pj of the executing process j. If Pi ≤ Pj, the original process Pj will continue to execute; but if Pi > Pj, the execution of Pj will be stopped immediately, and process switching will be performed to put process i into execution. Obviously, this preemptive priority scheduling algorithm can better meet the requirements of urgent jobs, so it is often used in real-time systems with strict requirements, as well as batch processing and time-sharing systems with higher performance requirements.

Specific code:

#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;
}

Output example

Input:

Output:

Recommended tutorial: "C#"

The above is the detailed content of What does preemptive priority scheduling algorithm mean?. For more information, please follow other related articles on the PHP Chinese website!