You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
73 lines
1.9 KiB
73 lines
1.9 KiB
//
|
|
// Created by yzf on 2021/2/17.
|
|
//
|
|
#include <vector>
|
|
#include <algorithm>
|
|
#include <iostream>
|
|
#include <queue>
|
|
#include <utility>
|
|
#include "quantum.h"
|
|
#include "scheduler.h"
|
|
|
|
//最小优先队列的比较方法
|
|
struct cmp{
|
|
bool operator() (std::pair<int,int> l, std::pair<int,int> r){
|
|
return l.first < r.first;
|
|
}
|
|
};
|
|
|
|
|
|
int greedy_scheduler(std::vector<quantum_program>& programs){
|
|
std::sort(programs.begin(),programs.end(),
|
|
[](quantum_program& l, quantum_program& r){return l.bit_useage > r.bit_useage;});
|
|
|
|
//Check
|
|
for(auto p : programs){
|
|
if(p.bit_useage > TOTAL_BITS){
|
|
std::cerr << "Program named " << p.name << " requires " << p.bit_useage
|
|
<< ", which is larger than TOTAL_BITS=" << TOTAL_BITS << std::endl;
|
|
exit(2);
|
|
}
|
|
else{
|
|
break;
|
|
}
|
|
}
|
|
|
|
//Greedily Schedule
|
|
int time=0;
|
|
int occupied=0;
|
|
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, cmp>
|
|
timeline;
|
|
//timeline represents in progress programs, 最小优先队列
|
|
while(true){
|
|
//Release occupied bits
|
|
if(!timeline.empty()){
|
|
auto next = timeline.top();
|
|
timeline.pop();
|
|
time = next.first;
|
|
occupied -= next.second;
|
|
}
|
|
while(!timeline.empty() && timeline.top().first == time){
|
|
auto next = timeline.top();
|
|
timeline.pop();
|
|
occupied -= next.second;
|
|
}
|
|
|
|
for(auto& p: programs){
|
|
while(p.bit_useage <= TOTAL_BITS-occupied && p.repeat_times > 0){
|
|
p.start_points.push_back(time);
|
|
p.end_points.push_back(time+p.time_cost);
|
|
p.repeat_times--;
|
|
|
|
occupied += p.bit_useage;
|
|
timeline.push(std::make_pair(p.end_points.back(), p.bit_useage));
|
|
}
|
|
}
|
|
|
|
if(timeline.empty()){
|
|
break;
|
|
}
|
|
}
|
|
|
|
return time;
|
|
} |