LLF算法代码c++
时间: 2024-05-30 15:07:37 浏览: 14
LLF算法是一种磁盘调度算法,用于磁盘读写请求的调度。LLF算法的全称是Least Laxity First(最小松弛度优先)算法,其主要思想是将所有磁盘请求按照松弛度排序,然后按照顺序进行调度。松弛度表示一个请求在规定时间内等待的程度。
以下是LLF算法的C++代码实现:
```c++
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,m,now_time,now_pos,num,ans;
struct info{
int l,r,id,pos;
}a[MAXN];
bool operator <(const info& a,const info& b){
return a.l<b.l;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void push(){
while(num<=m&&a[num].l==now_time){
q.push(make_pair(a[num].r,a[num].id));
num++;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].pos);
a[i].id=i;
}
sort(a+1,a+m+1);
push();
while(!q.empty()){
pair<int,int> now=q.top();
q.pop();
if(now.first>=now_time){
ans+=now.first-now_time;
now_time=now.first;
now_pos=now.second;
push();
}
else continue;
while(!q.empty()&&q.top().first==now_time){
pair<int,int> tmp=q.top();
q.pop();
if(a[tmp.second].pos==a[now_pos].pos)now_pos=tmp.second;
else{
ans++;
now_pos=tmp.second;
}
push();
}
}
printf("%d\n",ans+n-now_time);
return 0;
}
```
其中,a[i]表示第i个请求,l表示请求的到达时间,r表示请求的截止时间,pos表示请求访问的磁盘块号。push()函数用于将所有到达时间相同的请求加入优先队列中,即将请求的信息压入优先队列中。主函数部分则使用了一个while循环,每次取出优先队列中最小的松弛度的请求,如果其截止时间在当前时间之后,则将当前时间更新为该请求的截止时间,并计算该请求执行所需的时间。如果当前时间已经超过该请求的截止时间,则该请求无法执行,继续取出下一个最小松弛度的请求。同时,如果当前时间与下一个请求到达时间相同,则需要比较当前正在执行的请求和下一个请求是否访问同一个磁盘块,如果访问不同,则需要将磁头移动到下一个请求所访问的磁盘块,并计算移动所需的时间。如果访问相同,则不需要移动磁头。接着,将所有到达时间相同的请求加入优先队列中,并重复上述步骤,直到所有请求都被执行完毕。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)