实现多CPU FCFS算法

Question

我试图实现一个多CPU FCFS算法，但我想不出一种方式来实现作业/进程如何跳转到另一个CPU。

任何人都可以向我解释或给我提示从哪里开始？

这是我到目前为止，我试图实现FCFS算法单个CPU第一：

int n, burstTime[99], waitingTime[99], totalAT[99], aveWT = 0, aveTAT = 0, i, j; 
cout << "Enter total number of processes: "; 
cin >> n; 

cout << "\nEnter Process Burst Time\n"; 
for (i = 0; i<n; i++) 
{ 
    cout << "P[" << i + 1 << "]: "; 
    cin >> burstTime[i]; 
} 

waitingTime[0] = 0; //waiting time for first process is 0 

       //calculating waiting time 
for (i = 1; i<n; i++) 
{ 
    waitingTime[i] = 0; 
    for (j = 0; j<i; j++) 
     waitingTime[i] += burstTime[j]; 
} 

cout << "\nProcess\t\tBurst Time\tWaiting Time\tTurnaround Time"; 

//calculating turnaround time 
for (i = 0; i<n; i++) 
{ 
    totalAT[i] = burstTime[i] + waitingTime[i]; 
    aveWT += waitingTime[i]; 
    aveTAT += totalAT[i]; 
    cout << "\nP[" << i + 1 << "]" << "\t\t" << burstTime[i] << "\t\t" << waitingTime[i] << "\t\t" << totalAT[i]; 
} 

aveWT /= i; 
aveTAT /= i; 
cout << "\n\nAverage Waiting Time: " << aveWT; 
cout << "\nAverage Turnaround Time: " << aveTAT <<endl; 

编辑： 例如，这里有我想要做的，与实现样本输出程序：

Enter number of CPUs: 2 

Enter total number of processes: 6 

Enter Process Burst Time 
P1: [input here] 
P2: [input here] 
P3: [input here] 
p4: [input here] 
p5: [input here] 
p6: [input here] 

Process  Burst Time   Waiting Time     Turn Around Time 
P1   [burst time here] [calculated waiting time here]  [calculated turn around time] 
P2   [burst time here] [calculated waiting time here]  [calculated turn around time] 
P3   [burst time here] [calculated waiting time here]  [calculated turn around time] 
P4   [burst time here] [calculated waiting time here]  [calculated turn around time] 

P5   [burst time here] [calculated waiting time here]  [calculated turn around time] 
P6   [burst time here] [calculated waiting time here]  [calculated turn around time] 


CPUs handling the processes: 
CPU 1: P1, P3, P4 
CPU 2: P2, P5, P6 

Answer 1

有一个简单的方法来并行化的东西。基本思想是将任务分解为独立的块，每个独立的块由独立的线程并行处理。这并不总是最适合的方法，因为在某些情况下，将数据拆分为独立的块也是不可能的。无论如何，我们假设该任务实际上可以并行化。例如，让我们考虑数据的一堆被frobnosticated：

data = input("some large file") 
output = [] 
for i in length(data): 
    output[i] = frobnosticate(data[i]) 

的第一步是将一个任务拆分成块：

chunks = 42 
data = input("some large file") 
chunksize = length(data)/chunks 
output = [] 
for c in chunks: 
    # split off one chunk and frobnosticate it 
    chunk = data[c * chunksize ... (c + 1) * chunksize] 
    tmp = [] 
    for i in chunk: 
     tmp[i] = frobnosticate(chunk[i]) 
    # store results in the output container 
    for i in length(tmp): 
     output[c * chunksize + i] = tmp[i] 

此代码应该将数据分割成大小相等的块，分开处理这些。这里棘手的部分是可能无法创建大小相等的块。另外，你应该确保你不要不必要地复制输入数据，特别是当它很大时。这意味着chunk和tmp应该是代理服务器，而不是容器，它们只能访问data和output中正确位置的数据。第二个内部循环应该基本上不存在！

作为最后一步，您将内部循环的执行移动到单独的线程中。首先，启动一个线程为每个CPU，那么，你等待这些线程完成和检索结果：

chunks = 42 
data = input("some large file") 
chunksize = length(data)/chunks 
output = [] 
threads = [] 
for c in chunks: 
    # split off one chunk and frobnosticate it in a separate thread 
    chunk = data[c * chunksize ... (c + 1) * chunksize] 
    threads[c] = create_thread(frobnosticate, chunk) 
for c in chunks: 
    # wait for one thread to finish and store its results in the output container 
    threads[c].join() 
    tmp = threads[c].get_result() 
    for i in length(tmp): 
     output[c * chunksize + i] = tmp[i] 

用C实现此++不应该是一个问题。您可以使用std::thread运行多个线程，OS将自动分配给不同的CPU。使用不同的流程不会给你带来任何好处，反而增加开销。