c有序(稳定)优先级队列

发布时间：2020-12-16 09:56:48 所属栏目：百科来源：网络整理

导读：我正在实现一个玩具调度程序,它读取进程规范的输入文件,如到达时间,总运行时间,然后根据随机io / cpu突发调度进程. 该文件的格式 Arrival time,total CPU time,CPU burst,IO Burst. 现在,当有两个具有相同到达时间的进程时,调度程序必须首先调度该进程,该进

我正在实现一个玩具调度程序,它读取进程规范的输入文件,如到达时间,总运行时间,然后根据随机io / cpu突发调度进程.

该文件的格式

Arrival time,total CPU time,CPU burst,IO Burst.

现在,当有两个具有相同到达时间的进程时,调度程序必须首先调度该进程,该进程首先在文件中提到.

我将文件中的条目保留在优先级队列中.

struct EventComparator{
  bool operator()(const Event* event1,const Event* event2){
    return event1->getTimestamp() >= event2->getTimestamp();
  }   
};  
priority_queue<Event*,vector<Event*>,EventComparator> eventQueue;

其中Event只是一个封装过程参数的对象.

我的问题是,优先级队列不稳定.稳定我的意思是过程的顺序颠倒过来.

假设输入文件有

60 200 5 20

60 20 10 10

40 100 10 40

0 200 40 90

如果我从优先级队列弹出,我期待Line4,第3行,第1行,然后是Line2.但我得到了Line4,Line3,Line2,Line1.

我的问题是,我该怎么做才能获得稳定的优先级队列？

解决方法

>您的比较器不正确. std :: priority_queue的 documentation表示它应该提供严格的弱排序(即,它应该是event1-> getTimestamp()> event2-> getTimestamp(),而不是> =).
>为了使其稳定,您只需将行号存储在Event中,并在event1-> getTimestamp()== event2-> getTimestamp()时进行比较.

像这样的东西：

struct EventComparator {
  bool operator()(const Event* event1,const Event* event2) {
    if (event1->getTimestamp() != event2->getTimestamp()) {
      return event1->getTimestamp() > event2->getTimestamp();
    }
    return event1->getLineNumber() > event2->getLineNumber();
  }   
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!