資料結構
網路
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 次瀏覽
