C++ 使用Round Robin调度计算服务器负载

Round Robin调度用于CPU调度，我们有M个服务器和N个请求。每个请求都有到达时间和处理时间。我们需要使用Round-Robin调度来找出每个服务器的负载，为此我们将使用C++编程语言和优先队列和集合实现一段程序。

示例

让我们通过一个输入输出示例来理解这个问题 –

输入

int arrival_time[] = { 1, 2, 4, 6 };
int process_time[] = { 6, 1, 2, 2 };
int servers = 2;

输出

1 Server has load of: 1
2 Server has load of: 3

解释

首次加载将获取第一个请求，并在第7个单元结束，期间第二个服务器将获取在第2、4和6秒到达的所有请求。

方法

在这个方法中，我们将定义一些辅助函数，以便简化一些工作。

• 首先，在主函数中，我们将在数组中获取输入，并通过将输入传递给该函数来调用该函数。

• 在被调用的函数中，我们将定义一个优先队列，该队列将定义当前正在繁忙的服务器的释放时间。

• 我们将定义一个集合，用于存储空闲服务器的索引，以及一个用于存储服务器负载的数组。

• 最初，所有服务器都是空闲的，所以我们将它们添加到可用集合中。

• 我们将使用for循环遍历请求，并在每次迭代中使用while循环删除所有现在空闲的服务器。

• 对于当前的请求，结束时间将是到达时间加上处理时间，因此如果没有可用的服务器，则忽略该请求。

• 否则，我们将查找服务器i％totalServer是否存在，如果不存在，则获取第一个空闲的服务器。

• 我们将将选择的服务器标记为不可用，并将其简单地添加到优先队列中，时间等于进程结束时间。

• 还要增加当前服务器的负载，通过调用打印函数来打印负载。

让我们实现代码 –

例子

#include <bits/stdc++.h>
using namespace std;

// function to get and print of each given server 
void printLoad(int size, int load[]){
   // traversing over the array to get the loads
   for (int i = 0; i < size; i++) {
      cout << i + 1 << " Server has load of: "
      << load[i] << endl;
   }
}
// function to get the load which is on each server 
void getLoad(int reqSize, int arrival_time[], int process_time[], int serversSize){
   // array to store the load on each server
   int load[serversSize];
   // initialse it with 0
   memset(load, 0, sizeof(load));
   // creating priority queue to get the busy servers using the minimum version because we need the one which release early 
   priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >busy_servers;
   // defining set to get the data of the servers which are available 
   set<int> available_servers;
   // initially all the servers are free so we are going to add them to set
   for(int i = 0; i < serversSize; i++){
      available_servers.insert(i);
   }
   // going through all the requests using the for loop 
   for(int i = 0; i < reqSize; i++){
      // end time will be the sum of both arriaval time and process time 
      int end_time = arrival_time[i] + process_time[i];
      // remove all the servers that are not busy from the priority queue 
      while (busy_servers.empty() == false and busy_servers.top().first <= arrival_time[i]){
         // release the server 
         pair<int, int> cur = busy_servers.top();
         busy_servers.pop();
         // insert released server to available server 
         available_servers.insert(cur.second);
      }
      // if all the severs are busy, current request is ignored 
      if(available_servers.empty() == true){
         continue;
      }
      int demanded_server = i % serversSize;
      // search the demanded server 
      auto itrator = available_servers.lower_bound(demanded_server);
      if(itrator == available_servers.end()){
         // if demanded server is busy then choose the first free server 
         itrator = available_servers.begin();
      }
      int assigned_server = *itrator;
      // increase the load on the assigned server
      load[assigned_server]++;
      // remove the assigned server from available servers adding it to the busy servers 
      available_servers.erase(assigned_server);
      busy_servers.push({ end_time, assigned_server});
   }
   // calling the function to print the load on the server 
   printLoad(serversSize, load);
}
int main(){
   // given inputs 
   int arrival_time[] = { 1, 2, 4, 6 };
   int process_time[] = { 6, 1, 2, 2 };
   int n = 4;
   int servers = 2;
   // calling to the function to get the required data; 
   getLoad(n, arrival_time, process_time, servers);
   return 0;
}

输出

1 Server has load of: 1
2 Server has load of: 3

时间和空间复杂度

上述代码的时间复杂度为O(N*log(M))，其中N是请求的数量，M是服务器的数量。由于使用了优先队列，因此获得了对数因子。

上述代码的空间复杂度为O(M)，因为我们使用了一些额外的空间来存储服务器的负载和优先队列。

结论

在本教程中，我们实现了一个使用轮询搜索算法来找到服务器负载的程序。我们实现了一个程序，其时间复杂度为O(N*log(M))，因为我们既使用了优先队列，也使用了哈希集合来分别获取空闲服务器和空闲严重。这增加了空间复杂度到O(M)。