用c++综合实现:先来先服务调度算法、短 进程优先调度算法、时间片轮转调度算法和优先级调度算法(抢占式)、高响应 比优先调度算法。
时间: 2023-08-05 15:09:40 浏览: 131
以下是用 C++ 综合实现先来先服务调度算法、短进程优先调度算法、时间片轮转调度算法和优先级调度算法(抢占式)、高响应比优先调度算法的示例代码。
先来先服务调度算法:
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int id;
int arriveTime;
int serveTime;
int startTime;
int waitTime;
int finishTime;
bool operator < (const node &b) const{
return arriveTime<b.arriveTime;
}
}a[1005];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].arriveTime>>a[i].serveTime;
a[i].id=i;
}
sort(a+1,a+n+1);
a[1].startTime=a[1].arriveTime;
a[1].finishTime=a[1].startTime+a[1].serveTime;
a[1].waitTime=0;
for(int i=2;i<=n;i++){
if(a[i].arriveTime<=a[i-1].finishTime){
a[i].startTime=a[i-1].finishTime;
}
else{
a[i].startTime=a[i].arriveTime;
}
a[i].finishTime=a[i].startTime+a[i].serveTime;
a[i].waitTime=a[i].startTime-a[i].arriveTime;
}
for(int i=1;i<=n;i++){
cout<<"Process "<<a[i].id<<":\n";
cout<<"Start time: "<<a[i].startTime<<endl;
cout<<"Finish time: "<<a[i].finishTime<<endl;
cout<<"Wait time: "<<a[i].waitTime<<endl;
cout<<endl;
}
return 0;
}
```
短进程优先调度算法:
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int id;
int arriveTime;
int serveTime;
int startTime;
int waitTime;
int finishTime;
bool operator < (const node &b) const{
if(arriveTime!=b.arriveTime){
return arriveTime<b.arriveTime;
}
else{
return serveTime<b.serveTime;
}
}
}a[1005];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].arriveTime>>a[i].serveTime;
a[i].id=i;
}
sort(a+1,a+n+1);
a[1].startTime=a[1].arriveTime;
a[1].finishTime=a[1].startTime+a[1].serveTime;
a[1].waitTime=0;
for(int i=2;i<=n;i++){
int pos=i;
for(int j=i-1;j>=1;j--){
if(a[j].finishTime<=a[i].arriveTime){
break;
}
if(a[j].serveTime<a[pos].serveTime){
pos=j;
}
}
swap(a[i],a[pos]);
if(a[i].arriveTime<=a[i-1].finishTime){
a[i].startTime=a[i-1].finishTime;
}
else{
a[i].startTime=a[i].arriveTime;
}
a[i].finishTime=a[i].startTime+a[i].serveTime;
a[i].waitTime=a[i].startTime-a[i].arriveTime;
}
for(int i=1;i<=n;i++){
cout<<"Process "<<a[i].id<<":\n";
cout<<"Start time: "<<a[i].startTime<<endl;
cout<<"Finish time: "<<a[i].finishTime<<endl;
cout<<"Wait time: "<<a[i].waitTime<<endl;
cout<<endl;
}
return 0;
}
```
时间片轮转调度算法:
```cpp
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
int id;
int arriveTime;
int serveTime;
int startTime;
int waitTime;
int finishTime;
int leftTime;
bool operator < (const node &b) const{
if(arriveTime!=b.arriveTime){
return arriveTime<b.arriveTime;
}
else{
return serveTime<b.serveTime;
}
}
}a[1005];
queue<node> q;
int main(){
int n,timeSlice;
cin>>n>>timeSlice;
for(int i=1;i<=n;i++){
cin>>a[i].arriveTime>>a[i].serveTime;
a[i].id=i;
a[i].leftTime=a[i].serveTime;
}
sort(a+1,a+n+1);
a[1].startTime=a[1].arriveTime;
a[1].finishTime=a[1].startTime+min(a[1].leftTime,timeSlice);
a[1].waitTime=a[1].startTime-a[1].arriveTime;
if(a[1].leftTime<=timeSlice){
a[1].leftTime=0;
}
else{
a[1].leftTime-=timeSlice;
q.push(a[1]);
}
int currentTime=a[1].finishTime;
int cnt=1;
while(!q.empty()||cnt<n){
while(cnt<n&&a[cnt+1].arriveTime<=currentTime){
cnt++;
q.push(a[cnt]);
}
if(q.empty()){
cnt++;
q.push(a[cnt]);
currentTime=a[cnt].arriveTime;
}
node tmp=q.front();
q.pop();
tmp.startTime=currentTime;
tmp.finishTime=currentTime+min(tmp.leftTime,timeSlice);
tmp.waitTime=tmp.startTime-tmp.arriveTime;
currentTime=tmp.finishTime;
if(tmp.leftTime<=timeSlice){
tmp.leftTime=0;
}
else{
tmp.leftTime-=timeSlice;
q.push(tmp);
}
a[tmp.id]=tmp;
}
for(int i=1;i<=n;i++){
cout<<"Process "<<a[i].id<<":\n";
cout<<"Start time: "<<a[i].startTime<<endl;
cout<<"Finish time: "<<a[i].finishTime<<endl;
cout<<"Wait time: "<<a[i].waitTime<<endl;
cout<<endl;
}
return 0;
}
```
优先级调度算法(抢占式):
```cpp
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
int id;
int arriveTime;
int serveTime;
int startTime;
int waitTime;
int finishTime;
int priority;
bool operator < (const node &b) const{
if(arriveTime!=b.arriveTime){
return arriveTime<b.arriveTime;
}
else{
return priority<b.priority;
}
}
}a[1005];
struct cmp{
bool operator () (node x,node y) const{
return x.priority<y.priority;
}
};
priority_queue<node,vector<node>,cmp> q;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].arriveTime>>a[i].serveTime>>a[i].priority;
a[i].id=i;
}
sort(a+1,a+n+1);
a[1].startTime=a[1].arriveTime;
a[1].finishTime=a[1].startTime+a[1].serveTime;
a[1].waitTime=a[1].startTime-a[1].arriveTime;
for(int i=2;i<=n;i++){
if(a[i].arriveTime<=a[i-1].finishTime){
a[i].startTime=a[i-1].finishTime;
}
else{
a[i].startTime=a[i].arriveTime;
}
a[i].finishTime=a[i].startTime+a[i].serveTime;
a[i].waitTime=a[i].startTime-a[i].arriveTime;
}
int currentTime=a[1].finishTime;
int cnt=1;
while(!q.empty()||cnt<n){
while(cnt<n&&a[cnt+1].arriveTime<=currentTime){
cnt++;
q.push(a[cnt]);
}
if(q.empty()){
cnt++;
q.push(a[cnt]);
currentTime=a[cnt].arriveTime;
}
node tmp=q.top();
q.pop();
tmp.startTime=currentTime;
tmp.finishTime=currentTime+tmp.serveTime;
tmp.waitTime=tmp.startTime-tmp.arriveTime;
currentTime=tmp.finishTime;
a[tmp.id]=tmp;
}
for(int i=1;i<=n;i++){
cout<<"Process "<<a[i].id<<":\n";
cout<<"Start time: "<<a[i].startTime<<endl;
cout<<"Finish time: "<<a[i].finishTime<<endl;
cout<<"Wait time: "<<a[i].waitTime<<endl;
cout<<endl;
}
return 0;
}
```
高响应比优先调度算法:
```cpp
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
int id;
int arriveTime;
int serveTime;
int startTime;
int waitTime;
int finishTime;
int priority;
double ratio;
bool operator < (const node &b) const{
if(arriveTime!=b.arriveTime){
return arriveTime<b.arriveTime;
}
else{
return ratio<b.ratio;
}
}
}a[1005];
struct cmp{
bool operator () (node x,node y) const{
return x.priority<y.priority;
}
};
priority_queue<node,vector<node>,cmp> q;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].arriveTime>>a[i].serveTime>>a[i].priority;
a[i].id=i;
a[i].ratio=1.0*a[i].serveTime/a[i].waitTime;
}
sort(a+1,a+n+1);
a[1].startTime=a[1].arriveTime;
a[1].finishTime=a[1].startTime+a[1].serveTime;
a[1].waitTime=a[1].startTime-a[1].arriveTime;
for(int i=2;i<=n;i++){
if(a[i].arriveTime<=a[i-1].finishTime){
a[i].startTime=a[i-1].finishTime;
}
else{
a[i].startTime=a[i].arriveTime;
}
a[i].finishTime=a[i].startTime+a[i].serveTime;
a[i].waitTime=a[i].startTime-a[i].arriveTime;
}
int currentTime=a[1].finishTime;
int cnt=1;
while(!q.empty()||cnt<n){
while(cnt<n&&a[cnt+1].arriveTime<=currentTime){
cnt++;
a[cnt].waitTime=currentTime-a[cnt].arriveTime;
a[cnt].ratio=1.0*a[cnt].serveTime/a[cnt].waitTime;
q.push(a[cnt]);
}
if(q.empty()){
cnt++;
a[cnt].waitTime=0;
a[cnt].ratio=1.0*a[cnt].serveTime;
q.push(a[cnt]);
currentTime=a[cnt].arriveTime;
}
node tmp=q.top();
q.pop();
tmp.startTime=currentTime;
tmp.finishTime=currentTime+tmp.serveTime;
tmp.waitTime=tmp.startTime-tmp.arriveTime;
currentTime=tmp.finishTime;
a[tmp.id]=tmp;
}
for(int i=1;i<=n;i++){
cout<<"Process "<<a[i].id<<":\n";
cout<<"Start time: "<<a[i].startTime<<endl;
cout<<"Finish time: "<<a[i].finishTime<<endl;
cout<<"Wait time: "<<a[i].waitTime<<endl;
cout<<endl;
}
return 0;
}
```
阅读全文