数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律学使用循环轮询调度算法计算服务器负载
循环轮询调度算法用于 CPU 调度，我们给定 M 个服务器和 N 个请求。每个请求都有一个到达时间和处理时间。我们必须使用循环轮询调度算法找到每个服务器上的负载，为此我们将使用优先级队列和集合在 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)。
693 次浏览
