round-robin 是一种使用在 进程 和 网络分配 计算中的算法。
以 进程分配为例：
假设我们的time slot ( 单次运行进程的最长时间) 是100 ms, 如果 job1 一共需要消耗250 ms来运行， 那么 round-robin 分配器就会暂停 job1 在其运行100 ms之后， 然后分配给其他的进程， 并且将 job1 剩下的内容放到队列中排队，直到 job1 运行结束。
| process name | arrival time | execute time |
|---|---|---|
| p0 | 0 | 250 |
| p1 | 50 | 170 |
| p2 | 130 | 75 |
| p3 | 190 | 100 |
| p4 | 210 | 130 |
| p5 | 350 | 50 |
以上的图中表示 进程 0 － 5 的到达时间和运行完成的总时间。
运行队列如下。
| 时间 | 队列 | 解释 |
| 0 | p0 | 时间0的时候, p0 到达 |
| 100 | p1 p0 | 当运行100ms的时候，应该分配给下一个进程，p1在0～100内到达，p0剩下150 ms需要执行 |
| 200 | p0 p2 p3 p1 | 当运行200ms的时候，新进程 p2 和 p3 在100～200内 到达，p1 剩下70ms， |
| 300 | p2 p3 p1 p4 p0 | 当运行300ms的时候，新进程p4 在200～300 内到达，p0 剩下 50ms |
| 375 | p3 p1 p4 p0 p5 | 当从300ms到375ms的时候，进程p2完成，那么我们将结束它，进而按照队列继续工作，注意把在300 ～ 375内到达的p5放进进程队列中 |
| 475 | p1 p4 p0 p5 | p3结束， 回归下队列中的进程。p1 70ms, p4 130ms p0 50ms p5 50ms |
| 545 | p4 p0 p5 | p1结束 |
| 645 | p0 p5 p4 | p4剩下30ms |
| 695 | p5 p4 | p0结束 |
| 745 | p4 | p5结束 |
| 775 | p4结束 | |
public static void roundrobin_algo(int[] arrtime, int[] exetime, int timeslot) {
if (arrtime == null || exetime == null || arrtime.length != exetime.length) {
system.out.println("error!");
}
queue queue = new linkedlist();
int index = 0;
int totalwaittime = 0; //所有进程的等待总时间
int currenttime = 0; //当前时间
int visitedtimes = 0; //cpu访问次数
while (!queue.isempty() || index < arrtime.length) {
if (!queue.isempty()) {
visitedtimes ;
process tempp = queue.poll();
//waiting time in total
totalwaittime = currenttime - tempp.arrtime;
//update the currenttime
currenttime = math.min(tempp.exetime, timeslot);
//add the process which arrived before the end of this process finished.
for (; index < arrtime.length && arrtime[index] < currenttime; index ) {
queue.add(new process(arrtime[index], exetime[index]));
}
//add the rest of current process into process queue
if (tempp.exetime > timeslot) {
queue.add(new process(currenttime, tempp.exetime - timeslot));
}
} else {
queue.add(new process(arrtime[index], exetime[index]));
currenttime = arrtime[index];
index ;
visitedtimes ;
}
}
system.out.println("total wait time among the process: " totalwaittime);
system.out.println("total cpu visited times: " visitedtimes);
} let me know, if you found any issues.