ラウンドロビンスケジューリングのアルゴリズムをPerlで実装してみた

概要

ラウンドロビン・スケジューリングは、オペレーティングシステムなどにおけるプロセスなどに関するスケジューリング規則のひとつで、単純な部類に分類される一種である。実行可能状態にあるプロセスに、順番にプロセッサを割り当てる。順番に交代する、という意の「ラウンドロビン」が名前の由来である。

原始的なラウンドロビン・スケジューリングは単純で実装が容易であり、優先度をつけたり、他のアルゴリズムと併用しなければ、リソーススタベーションも発生しない。

アルゴリズム

各タスク(またはジョブ)にはタイムスロットあるいは「クォンタム; quantum」が割り当てられる(CPU時間の割り当てであり、例えば100ミリ秒といった長さ)。job1が完了までに250msかかるとき、ラウンドロビンスケジューラは job1 が 100ms 間実行された後で中断し、他のジョブにCPU時間を割り当てる。

他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、job1 にはさらに100msのCPU時間が割り当てられ、ラウンドロビンスケジューラがその実行を中断して別のジョブにCPU時間を割り当てる。再度、他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、job1 が再度実行され、最後まで実行されることになる。

具体例

use strict;
use warnings;
use utf8;
binmode(STDOUT, ":utf8");

&main;

sub main {
    print "プロセス数を表す整数nとクオンタムを表す整数qを入力してください。\n";

    my $input_nq = <STDIN>; 
    chomp($input_nq); 
    my @input_nq_arr = split(/ /, $input_nq);

    my $p_num = $input_nq_arr[0];
    my $quantum = $input_nq_arr[1];

    print "文字列name^iと整数time^iを改行区切りで入力してください。入力完了後、endと入力してください。\n";
    my @input_times_arr;

    while (my $input_name_time = <STDIN>) { 
        last if $input_name_time eq "end\n";
        chomp($input_name_time); 

        my $input_time = substr($input_name_time, 3);
        push (@input_times_arr, $input_time);
    }
    my $result_times = &queue_algorithm($p_num, $quantum, \@input_times_arr);

    for (my $i = 0; $i < $p_num * 2; $i = $i + 2) {
        my @time_name_tmp;
        push (@time_name_tmp, "p".$result_times->[$i], $result_times->[$i + 1]);
        
        my $result_name_time = join(' ', @time_name_tmp); 
        print $result_name_time;
    }
}

sub queue_algorithm {
    my ($p_num, $quantum, $input_times_arr) = @_;
    $\="\n";

    my @input_times_arr = @{$input_times_arr};
    my @result_times;
    my $time = 0;

    for (my $i = 0; $i < $p_num; $i++) {
        if ($input_times_arr[0] > 0 ) {
            my $head_time = shift @input_times_arr; 
            my $sub_time = $head_time - $quantum; 
            push (@input_times_arr, $sub_time);

            if ($sub_time <= 0) {
                $time = $time + $head_time;
                push (@result_times, $i + 1, $time);
            } else {
                $time = $time + $quantum;
            }
        } else {
            my $head_time = shift @input_times_arr; 
            push (@input_times_arr, $head_time);
        }

        if ($i == 4 && ($#result_times + 1 != $p_num * 2)) {
            $i = -1;
        }
    }
    return \@result_times;
}