расскажи как работает данный код. Здесь используется алгоритм параллельного…
- User
расскажи как работает данный код. Здесь используется алгоритм параллельного программирования FCFS
#include <stdio.h> #include "mpi.h" #include #include <Windows.h> #include "math.h" #include "stdlib.h" #include
using namespace std;
#define n 2 #define ochmax 7 #define lmax 20
int main(int* argc, char** argv) { SetConsoleCP(1251); SetConsoleOutputCP(1251);
int size, rank; if (MPI_Init(argc, &argv) != MPI_SUCCESS) return 1; if (MPI_Comm_size(MPI_COMM_WORLD, &size) != MPI_SUCCESS) { MPI_Finalize(); return 2; } if (MPI_Comm_rank(MPI_COMM_WORLD, &rank) != MPI_SUCCESS) { MPI_Finalize(); return 3; } srand(time(NULL)); int balance = 100; int mag[ochmax][n]; int z[n]; int* p, * nmag, kmax = size - 1; int pr = 1; p = nmag = *mag; MPI_Status status; //определим начальные значения для банка и для клиентов if (!rank) { p = nmag = *mag; balance = 100; kmax = size - 1; } if (rank) { z[0] = rand() % 2; z[1] = (rand() % 100) * rank; } //основной жизненный цикл for (int l = 0; l < lmax; l++) { if (!rank) cout << l + 1 << " day!" << endl; MPI_Barrier(MPI_COMM_WORLD); if (!rank) //bank { kmax = size - 1 - (p - nmag) / 2; for (int i = 0; i < kmax; i++) { MPI_Recv(z, n, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status); if (z[0]) { balance += z[1]; pr = 1; MPI_Send(&pr, 1, MPI_INT, status.MPI_SOURCE, 0, MPI_COMM_WORLD); cout << "bank takes " << z[1] << "$ from client " << status.MPI_SOURCE << "!" << endl; } else { if (z[1] > balance - 5) { *p = status.MPI_SOURCE; p++; *p = z[1]; p++; cout << "bank can not give " << z[1] << "$ to client " << status.MPI_SOURCE << "!" << endl; } else { balance -= z[1]; pr = 1; MPI_Send(&pr, 1, MPI_INT, status.MPI_SOURCE, 0, MPI_COMM_WORLD); cout << "bank gives " << z[1] << "$ to client " << status.MPI_SOURCE << "!" << endl; } } } //work with queue int flag = 1; //cout << balance - 5 << endl; while ((p != nmag) && flag) { cout << "the queue is not empty! queue`s lenght = " << (p - nmag) / 2 << "!" << endl; int m = *nmag; int sum = *(nmag + 1); if (sum < balance - 5) { balance -= sum; pr = 1; MPI_Send(&pr, 1, MPI_INT, m, 0, MPI_COMM_WORLD); cout << "bank gives " << sum << "$ to client " << m << "!" << endl; //sdvig of queue for (int j = 0; j < (p - nmag) / 2; j++) { *(nmag + j * n) = *(nmag + j * n + 2); *(nmag + j * n + 1) = *(nmag + j * n + 3); } p -= 2; } else { break; } } for (int j = 0; j < (p - nmag) / 2; j++) { int m = *(nmag + j * 2); pr = 0; MPI_Send(&pr, 1, MPI_INT, m, 0, MPI_COMM_WORLD); } if ((p - nmag) / 2 == ochmax) { cout << "bank is a bankrupt!" << endl; for (int j = 0; j < (p - nmag) / 2; j++) { int m = *(nmag + j * 2); pr = -1; MPI_Send(&pr, 1, MPI_INT, m, 0, MPI_COMM_WORLD); } break; } } else //clients { if (pr == -1) break; else { if (pr) { MPI_Send(z, n, MPI_INT, 0, 0, MPI_COMM_WORLD); if (z[0]) cout << "client " << rank << " puts " << z[1] << "$ in the bank!" << endl; else cout << "client " << rank << " takes " << z[1] << "$ from the bank!" << endl; } MPI_Recv(&pr, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status); if (pr) { z[0] = rand() % 2; z[1] = (rand() % 100) * rank; } } } } MPI_Finalize(); system("pause"); return 0;}
- Assistant
The provided C++ code is a simulation of a banking system using MPI (Message Passing Interface) for parallel programming. The code models a simple bank and multiple clients interacting over several iterations (days). The bank processes deposit and withdrawal requests from clients, and if it cannot immediately fulfill a withdrawal request due to insufficient funds, it places the request in a queue to be processed later using the First-Come-First-Serve (FCFS) algorithm. Here's a detailed explanation of how the code works.
Overview
- Bank: Implemented by the process with rank 0.
- Clients: Implemented by all processes with rank greater than 0.
- Transactions: Clients can either deposit or withdraw money.
- Queue: If the bank cannot immediately fulfill a withdrawal request, it adds it to a queue.
- FCFS Algorithm: The bank processes queued withdrawal requests in the order they were received.
Key Constants
#define n 2 // Number of elements in the transaction array `z` #define ochmax 7 // Maximum queue length (if reached, the bank goes bankrupt) #define lmax 20 // Maximum number of iterations (days)Initialization
-
MPI Setup: The program initializes MPI and determines the number of processes (
size) and the rank of each process (rank). -
Bank Initialization (Rank 0):
balance: The bank's initial balance is set to 100.mag: A 2D array representing the transaction queue, with a maximum size ofochmaxtransactions.pandnmag: Pointers used to manage the queue (mag).
-
Client Initialization (Ranks > 0):
- Each client generates a random transaction:
z[0]: A random value (0 or 1) indicating withdrawal or deposit.0for withdrawal,1for deposit.z[1]: A random amount between 0 and 99 multiplied by the client's rank (ensuring unique amounts per client).
- Each client generates a random transaction:
Main Loop (Simulating Days)
The simulation runs for
lmaxiterations (days).Bank Process (Rank 0)
-
Announce Day:
cout << l + 1 << " day!" << endl; -
Receive Transactions from Clients:
- The bank calculates
kmax, the expected number of incoming requests, adjusted for the current queue length:kmax = size - 1 - (p - nmag) / 2; - For each expected request, the bank:
- Receives a transaction
zfrom any client:MPI_Recv(z, n, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status); - Checks if the transaction is a deposit or withdrawal:
- Deposit (
z[0] == 1):- Adds the amount to the balance.
- Sends a confirmation to the client.
- Logs the transaction.
- Withdrawal (
z[0] == 0):- If the requested amount is greater than
balance - 5, the bank cannot fulfill it immediately.- Adds the request to the queue (
mag). - Logs that the bank cannot fulfill the request.
- Adds the request to the queue (
- Otherwise, the bank processes the withdrawal:
- Subtracts the amount from the balance.
- Sends a confirmation to the client.
- Logs the transaction.
- If the requested amount is greater than
- Deposit (
- Receives a transaction
- The bank calculates
-
Process Queue Using FCFS:
- While the queue is not empty and the bank has enough balance:
- Retrieves the first transaction from the queue.
- If the bank has sufficient balance to fulfill the request:
- Processes the withdrawal.
- Sends a confirmation to the client.
- Removes the transaction from the queue by shifting the remaining transactions forward.
- If the bank cannot fulfill the request, it breaks out of the loop (since it processes requests in order).
- While the queue is not empty and the bank has enough balance:
-
Notify Clients with Pending Requests:
- For clients still in the queue, the bank sends a message indicating the request is pending (
pr = 0).
- For clients still in the queue, the bank sends a message indicating the request is pending (
-
Bankruptcy Check:
- If the queue reaches its maximum length (
ochmax), the bank declares bankruptcy:- Sends a bankruptcy notice (
pr = -1) to all clients in the queue. - Breaks out of the main loop.
- Sends a bankruptcy notice (
- If the queue reaches its maximum length (
Client Processes (Ranks > 0)
-
Check for Bank Status:
- If the bank is bankrupt (
pr == -1), the client exits the loop.
- If the bank is bankrupt (
-
Transaction Handling:
- If the previous transaction was processed (
pr == 1or initialpr == 1):- Sends the transaction
zto the bank:MPI_Send(z, n, MPI_INT, 0, 0, MPI_COMM_WORLD); - Logs the transaction attempt.
- Sends the transaction
- Receives a response from the bank:
- A positive response (
pr == 1) means the transaction was processed. - A pending response (
pr == 0) means the transaction is still in the queue. - A negative response (
pr == -1) indicates the bank is bankrupt.
- A positive response (
- If the previous transaction was processed, the client generates a new random transaction for the next day.
- If the previous transaction was processed (
Data Structures and Variables
balance: The bank's current balance.mag: The queue represented as a 2D array where each transaction consists of the client's rank and the requested amount.pandnmag: Pointers to manage the queue.ppoints to the end of the queue, andnmagpoints to the start.z[n]: Array holding the transaction details for each client:z[0]: Transaction type (0for withdrawal,1for deposit).z[1]: Transaction amount.
pr: Status code sent between the bank and clients:1: Transaction processed.0: Transaction pending in the queue.-1: Bank is bankrupt.
FCFS Implementation
- Withdrawal requests that cannot be immediately fulfilled are added to the end of the queue.
- The bank processes the queue at the end of each day, attempting to fulfill as many requests as the balance allows.
- Requests in the queue are processed in the order they were received, exemplifying the FCFS algorithm.
Important Code Sections
Adding a Withdrawal Request to the Queue
if (z[1] > balance - 5) { *p = status.MPI_SOURCE; // Store client rank p++; *p = z[1]; // Store requested amount p++; cout << "bank cannot give " << z[1] << "$ to client " << status.MPI_SOURCE << "!" << endl; }Processing the Queue
while ((p != nmag) && flag) { cout << "the queue is not empty! queue's length = " << (p - nmag) / 2 << "!" << endl; int m = *nmag; // Client rank at front of the queue int sum = *(nmag + 1); // Requested amount if (sum < balance - 5) { balance -= sum; pr = 1; MPI_Send(&pr, 1, MPI_INT, m, 0, MPI_COMM_WORLD); cout << "bank gives " << sum << "$ to client " << m << "!" << endl; // Shift the queue for (int j = 0; j < (p - nmag) / 2; j++) { *(nmag + j * n) = *(nmag + j * n + 2); *(nmag + j * n + 1) = *(nmag + j * n + 3); } p -= 2; } else { break; } }Client Receiving Bank Response
MPI_Recv(&pr, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status); if (pr == -1) { break; // Bank is bankrupt } else if (pr) { // Transaction was processed, generate a new transaction z[0] = rand() % 2; z[1] = (rand() % 100) * rank; }Program Termination
- The program terminates when:
- The maximum number of days (
lmax) is reached. - The bank declares bankruptcy.
- The maximum number of days (
- Clients check for the bankruptcy signal (
pr == -1) to exit their loops.
Additional Notes
- Synchronization: The
MPI_Barriercall ensures all processes start each day simultaneously. - Randomness: The use of
rand()provides variability in transaction types and amounts. - Potential Issues:
- The code lacks proper error checking for certain MPI calls.
- The use of pointers and manual memory management can be error-prone; modern C++ practices recommend using containers like
std::vector. - The code assumes a small number of processes due to the use of
rand() % 100and multiplication byrankfor transaction amounts.
Compiling and Running the Code
To compile and run this MPI program:
-
Compilation:
mpicxx -o bank_simulation your_program.cppReplace
your_program.cppwith the filename containing the code. -
Execution:
mpirun -np <number_of_processes> ./bank_simulationReplace
<number_of_processes>with the desired total number of processes (bank + clients).
Conclusion
This code demonstrates the implementation of a simple bank-client interaction model using MPI for parallel processing. The FCFS algorithm is applied to manage a queue of withdrawal requests that the bank cannot immediately fulfill. The bank processes queued requests in the order they were received whenever it has sufficient funds, showcasing how FCFS works in a parallel computing context.