實現多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。使用不同的流程不會給你帶來任何好處，反而增加開銷。