Dados M servidores que manejan múltiples requests con una capacidad computacional infinita y arreglos de tiempo de llegada [] y tiempo de proceso [] de tamaño N que denotan el tiempo de llegada y el tiempo de carga de N requests de la siguiente manera:
- Cada servidor está numerado de 0 a (M – 1) y las requests se dan en orden de tiempo estrictamente creciente.
- Cada solicitud i se asigna a uno de los servidores de la siguiente manera:
- Elija el (i % m) servidor . Si el servidor elegido está libre, asigne la solicitud al servidor.
- De lo contrario, elija el siguiente servidor disponible. Si no hay ningún servidor disponible, se descarta la solicitud.
Teniendo en cuenta que cada servidor puede manejar solo una solicitud a la vez, la tarea es encontrar la carga en cada servidor después de que se procesen todas las requests entrantes dado que la carga en cada servidor es la cantidad de requests que procesa.
Ejemplos:
Entrada : N = 4, M = 3, tiempo de llegada [] = {1, 3, 6, 8}, tiempo de proceso [] = {1, 2, 2, 1} Salida
: 1er servidor -> 2 2do servidor -> 1 3er Servidor -> 1 Explicación: La primera y la cuarta solicitud se asignan al primer servidor. La segunda solicitud se asigna al segundo servidor y la tercera solicitud se asigna al tercer servidor. A continuación se muestra la tabla de transición:
número de solicitud Hora de llegada Tiempo de carga Hora de finalización Servidores disponibles Servidor demandado Servidor asignado 0 1 1 2 0, 1, 2 0 0 1 3 2 5 0, 1, 2 1 1 2 6 2 8 0, 1, 2 2 2 3 8 1 9 0, 1, 2 1 1 Entrada : N = 4, M = 2, tiempo de llegada = {1, 2, 4, 6}, tiempo de proceso = {7, 1, 4, 4}
Salida :
1er servidor -> 1
2do servidor -> 2
Explicación:
la primera solicitud se asigna al primer servidor y la segunda solicitud al segundo servidor.
La tercera solicitud se asigna al segundo servidor. El servidor solicitado para la tercera solicitud es el primer servidor, pero como está ocupado en el momento de la llegada de la solicitud,
se le asigna el segundo servidor.
La cuarta solicitud se descarta porque ambos servidores están ocupados en el momento de su llegada.
A continuación se muestra la tabla de transición:
número de solicitud Hora de llegada Tiempo de carga Hora de finalización Servidores disponibles Servidor demandado Servidor asignado 0 1 7 8 0, 1 0 0 1 2 1 3 1 1 1 2 4 4 8 1 0 1 3 6 4 10 – 1 –
Enfoque: La idea es utilizar una Cola de Prioridad Mínima y un conjunto . La cola de prioridad lleva la cuenta de los servidores ocupados y ayuda a liberarlos tan pronto como estén libres. Set se utiliza para mantener los datos de los servidores disponibles para asignarlos a las requests entrantes. A continuación se muestran los pasos:
- Inicialice una array auxiliar loadOnServer[] que almacenará la carga en cada servidor.
- Repita las requests entrantes y encuentre la hora de finalización de cada solicitud agregando la hora de llegada y el tiempo de proceso en cada solicitud.
- Extrae los servidores ocupados de la cola de prioridad cuya hora de finalización ha superado la hora de finalización actual.
- Si el conjunto de servidores disponibles está vacío, descarte la solicitud actual.
- Ahora, busque (i % m) el servidor en el conjunto utilizando la función de límite inferior y, si el iterador de límite inferior apunta al final del conjunto, elija el primer servidor del conjunto.
- Aumente el contador de la carga en el servidor elegido después del paso anterior.
- Después de los pasos anteriores, imprima todas las tiendas de carga en loadOnServer[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print load on each server
void printLoadOnEachServer(
int m, int loadOnServer[])
{
// Traverse the loadOnServer and
// print each loads
for (int i = 0; i < m; i++) {
cout << i + 1 << "st Server -> "
<< loadOnServer[i] << ".\n";
}
}
// Function for finding the load
// on each server
void loadBalancing(int n, int m,
int arrivalTime[],
int processTime[])
{
// Stores the load on each Server
int loadOnServer[m];
for (int i = 0; i < m; i++) {
// Initialize load on each
// server as zero
loadOnServer[i] = 0;
}
// Minimum priority queue for
// storing busy servers according
// to their release time
priority_queue<pair<int, int>,
vector<pair<int, int> >,
greater<pair<int, int> > >
busyServers;
// Set to store available Servers
set<int> availableServers;
for (int i = 0; i < m; i++) {
// Initially, all servers are free
availableServers.insert(i);
}
// Iterating through the requests.
for (int i = 0; i < n; i++) {
// End time of current request
// is the sum of arrival time
// and process time
int endTime = arrivalTime[i]
+ processTime[i];
// Releasing all the servers which
// have become free by this time
while (!busyServers.empty()
&& busyServers.top().first
<= arrivalTime[i]) {
// Pop the server
pair<int, int> releasedServer
= busyServers.top();
busyServers.pop();
// Insert available server
availableServers.insert(
releasedServer.second);
}
// If there is no free server,
// the request is dropped
if ((int)availableServers.empty()) {
continue;
}
int demandedServer = i % m;
// Searching for demanded server
auto itr
= availableServers.lower_bound(
demandedServer);
if (itr == availableServers.end()) {
// If demanded Server is not free
// and no server is free after it,
// then choose first free server
itr = availableServers.begin();
}
int assignedServer = *itr;
// Increasing load on assigned Server
loadOnServer[assignedServer]++;
// Removing assigned server from list
// of assigned servers
availableServers.erase(assignedServer);
// Add assigned server in the list of
// busy servers with its release time
busyServers.push({ endTime,
assignedServer });
}
// Function to print load on each server
printLoadOnEachServer(m, loadOnServer);
}
// Driver Code
int main()
{
// Given arrivalTime and processTime
int arrivalTime[] = { 1, 2, 4, 6 };
int processTime[] = { 7, 1, 4, 4 };
int N = sizeof(arrivalTime)
/ sizeof(int);
int M = 2;
// Function Call
loadBalancing(N, M, arrivalTime,
processTime);
return 0;
}
1st Server -> 1. 2st Server -> 2.
Complejidad de tiempo: O(N*log M)
Espacio auxiliar: O(M)