Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題
ラウンドロビンスケジューリングと呼ばれる処理方法では、CPU がプロセスを順番に処理します。
各プロセスは最大 q ms(これをクオンタムと呼びます)だけ処理が実行されます。
q ms だけ処理を行っても、まだそのプロセスが完了しなければ、そのプロセスは列の最後尾に移動し、CPU は次のプロセスに割り当てられます。
例えば、クオンタムを 100 msとし、次のようなプロセスキューを考えます。
A(150) - B(80) - C(200) - D(200)
まずプロセス A が 100 ms だけ処理され残りの必要時間 50 ms を保持しキューの末尾に移動します。
B(80) - C(200) - D(200) - A(50)
次にプロセス B が 80 ms だけ処理され、時刻 180 ms で終了し、キューから削除されます。
C(200) - D(200) - A(50)
次にプロセス C が 100 ms だけ処理され、残りの必要時間 100 ms を保持し列の末尾に移動します。
D(200) - A(50) - C(100)
このように、全てのプロセスが終了するまで処理を繰り返します。
ラウンドロビンスケジューリングをシミュレートするプログラムを作成してください。
・入力される値
入力の形式は以下の通りです。
最初の行に、プロセス数を表す整数 n とクオンタムを表す整数 q が1つの空白区切りで与えられます。
・期待する出力
プロセスが完了した順に、各プロセスの名前と終了時刻を空白で区切って1行に出力してください。
・条件
僕が作成、提出したコードは、以下のとおりです。
/* ALDS1_3_B Queue http://judge.u-aizu.ac.jp/ 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<stdio.h> typedef struct{ char name[11]; int time; }queue; int main(void){ int n,q; scanf("%d %d",&n,&q); int size=2*n; queue Queue[size]; int pre=0,rear=0,cnt=0; for(rear=0;rear<n;++rear){ scanf("%s %d",Queue[rear].name,&Queue[rear].time); } while(pre!=rear){ if(Queue[pre].time<=q){ cnt+=Queue[pre].time; printf("%s %d\n",Queue[pre].name,cnt); }else{ cnt+=q; Queue[pre].time-=q; Queue[rear]=Queue[pre]; rear=(rear+1)%size; } pre=(pre+1)%size; } return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
ALDS1_3_B Queue