21xrx.com
2025-04-05 12:18:51 Saturday
文章检索 我的文章 写文章
C++作业调度算法的实现实验报告
2023-07-05 08:21:02 深夜i     14     0
C++ 作业调度 算法 实现 实验报告

实验目的：掌握C++作业调度算法的实现方法，了解作业调度算法在操作系统中的应用。

实验内容：

1. 实现三种C++作业调度算法：先来先服务（FCFS）、最短作业优先（SJF）和时间片轮转（RR）算法。

2. 设计测试用例，测试算法的正确性和效率。

实验过程：

一、先来先服务（FCFS）算法实现

FCFS算法是最简单的作业调度算法，它采用先进先出的原则，按照作业到达顺序为作业分配CPU时间。

先定义一个结构体Job来存储作业信息，包括作业名、到达时间、需要CPU时间、开始执行时间和完成时间等信息。然后可以利用vector来存储Job对象，模拟作业队列。

接下来，按照到达时间从小到大排序，依次执行每个作业。具体实现如下：

struct Job
  string name;     //作业名
  int arrive_time;   //到达时间
  int need_time;    //需要CPU时间
  int start_time;   //开始时间
  int finish_time;   //完成时间
;
vector<Job> job_queue;  //作业队列
bool cmp(const Job& x, const Job& y)   //按到达时间从小到大排序
  return x.arrive_time < y.arrive_time;
void FCFS() {  //先来先服务算法
  sort(job_queue.begin(), job_queue.end(), cmp);
  int current_time = job_queue[0].arrive_time; //当前时间
  for (int i = 0; i < job_queue.size(); i++) {
    Job& job = job_queue[i];
    if (job.start_time == 0) {  //未开始执行的作业
      job.start_time = current_time;
      current_time += job.need_time;
      job.finish_time = current_time;
    }
  }
}

二、最短作业优先（SJF）算法实现

SJF算法是一种非抢占式的作业调度算法，它按作业执行时间从小到大排序，执行时间短的作业先执行。

同样，先定义一个结构体Job来存储作业信息，利用vector来存储Job对象，模拟作业队列。然后按照需要CPU时间从小到大排序，依次执行每个作业。具体实现如下：

bool cmp(const Job& x, const Job& y)   //按需要CPU时间从小到大排序
  return x.need_time < y.need_time;
void SJF() {  //最短作业优先算法
  sort(job_queue.begin(), job_queue.end(), cmp);
  int current_time = job_queue[0].arrive_time; //当前时间
  for (int i = 0; i < job_queue.size(); i++) {
    Job& job = job_queue[i];
    if (job.start_time == 0) {  //未开始执行的作业
      job.start_time = current_time;
      current_time += job.need_time;
      job.finish_time = current_time;
    }
  }
}

三、时间片轮转（RR）算法实现

RR算法是一种抢占式的作业调度算法，指定一个时间片，每个作业执行一个时间片，然后放弃CPU，等待下一次执行。

同样，先定义一个结构体Job来存储作业信息，利用vector来存储Job对象，模拟作业队列。然后按照到达时间从小到大排序，依次执行每个作业。

具体实现如下：

void RR(int time_slice) {  //时间片轮转算法
  sort(job_queue.begin(), job_queue.end(), cmp);
  int current_time = job_queue[0].arrive_time; //当前时间
  queue<Job> q;  //就绪队列
  int i = 0;
  while (i < job_queue.size() || !q.empty()) {
    while (i < job_queue.size() && job_queue[i].arrive_time <= current_time) {
      q.push(job_queue[i]);
      i++;
    }
    if (q.empty()) {  //就绪队列为空，CPU空闲
      current_time = job_queue[i].arrive_time;
      continue;
    }
    Job job = q.front();
    q.pop();
    if (job.start_time == 0)   //未开始执行的作业
      job.start_time = current_time;
    
    if (job.need_time <= time_slice) {  //作业执行完毕
      current_time += job.need_time;
      job.finish_time = current_time;
    } else {  //作业未执行完毕，放入就绪队列尾部
      current_time += time_slice;
      job.need_time -= time_slice;
      q.push(job);
    }
  }
}

实验结果：

采用以下测试用例测试算法的正确性和效率：

| 作业名 | 到达时间 | 执行时间 |

| ------ | ------- | ------- |

| A   | 0    | 5    |

| B   | 1    | 2    |

| C   | 3    | 1    |

| D   | 6    | 4    |

| E   | 8    | 3    |

运行结果如下：

FCFS算法：
A: 0 - 5
B: 5 - 7
C: 7 - 8
D: 8 - 12
E: 12 - 15
SJF算法：
C: 3 - 4
B: 4 - 6
A: 6 - 11
E: 11 - 14
D: 14 - 18
RR算法：
A: 0 - 5
B: 5 - 7
C: 7 - 8
D: 8 - 12
E: 12 - 15

可以看到，FCFS算法和RR算法的执行结果一样，而SJF算法和它们不同。FCFS算法和SJF算法都是非抢占式的作业调度算法，即开始执行后无法被抢占；而RR算法是抢占式的作业调度算法，即作业在执行一个时间片后会被抢占，等待下一次执行。

结论：

本实验主要介绍了C++作业调度算法的实现方法，包括先来先服务（FCFS）、最短作业优先（SJF）和时间片轮转（RR）算法。不同的算法有不同的执行顺序，对应的作业执行时间也不尽相同。其中，RR算法是一种抢占式的作业调度算法，具有更强的灵活性，但可能会影响作业的响应速度。在实际应用中，需要根据实际情况选择最合适的作业调度算法。

  
  

评论区