[Xen-devel] [OSSTEST PATCH 18/21] starvation: Infrastructure for jobs which are delaying their flights

[Ian Jackson <ian.jackson@xxxxxxxxxxxxx>]

Provide hostalloc_starvation_* in Osstest::Executive, and a comment
saying what we are going to do.  And provide a demo utility which
prints the effect of some particular runvar value on a range of
situations.

Signed-off-by: Ian Jackson <Ian.Jackson@xxxxxxxxxxxxx>
---
 Osstest/Executive.pm         | 70 ++++++++++++++++++++++++++++++++++++++++++++
 mg-hostalloc-starvation-demo | 53 +++++++++++++++++++++++++++++++++
 2 files changed, 123 insertions(+)
 create mode 100755 mg-hostalloc-starvation-demo

diff --git a/Osstest/Executive.pm b/Osstest/Executive.pm
index a9f9ac78..e741f529 100644
--- a/Osstest/Executive.pm
+++ b/Osstest/Executive.pm
@@ -22,6 +22,7 @@ use warnings;
 
 use Osstest;
 
+use Carp;
 use POSIX;
 use IO::File;
 use File::Copy;
@@ -55,6 +56,8 @@ BEGIN {
                       alloc_resources alloc_resources_rollback_begin_work
                       resource_check_allocated
                       executive_resource_shared_mark_ready
+                      hostalloc_starvation_parse_runvar
+                     hostalloc_starvation_calculate_X
                       duration_estimator
                       db_pg_dsn opendb opendb_state
                       db_schema_updates_applied db_schema_updates_intree
@@ -1053,6 +1056,73 @@ END
     logm("$restype $resname shared $sharetype marked ready");
 }
 
+# hostalloc_maxwait_starvation
+#
+# $r{hostalloc_maxwait_starvation} is either "never" or
+# comma-separated list of assignments:
+#    <var>=<value>
+# where <var> is C, A, L or Xh and <value> is
+# a floating point number.
+#
+# terms:
+#  calculated or observed values:
+#    X   wait factor, ratio between amount of time
+#        to allow for slow jobs, compared to other jobs
+#    W   number of jobs waiting - strictly, jobs in states
+#          preparing queued running
+#    D   number of jobs done - strictly, other states
+#  tuning parameters:
+#    Xt  X when D=9 W=1, ie cancel one job out of ten
+#    Xh  X when D=1 W=1, ie cancel one job out of two
+#    I   length of time this expected delay must have
+#        persisted before we abandon this job
+#   C,A  tuning parameters relating X to W and D (see below)
+#
+# we calculate:
+#    X = C + L * W^A / D^B
+# where C, A are specified
+#   and L, B are calculated from C, A, Xh, Xt
+#
+# and then we are willing to allow each job to take
+#    X * (time spent for done jobs) + I
+#
+# default values are
+#    C = 1.3
+#    A = 1
+#    Xt = 5
+#    Xh = 200
+#    I = 3600   (seconds)
+
+sub hostalloc_starvation_parse_runvar ($) {
+    my ($r_hostalloc_maxwait_starvation) = @_;
+    # returns \%p hashref to be fed to hostalloc_starvation_calculate_X
+    # caller may inspect elements of %p
+    # if was `never' then !%p
+    $r_hostalloc_maxwait_starvation //= '';
+    return { } if $r_hostalloc_maxwait_starvation eq 'never';
+    my %p = ( C => 1.3, A => 1, Xt => 5, Xh => 200, I => 3600 );
+    foreach (split /,/, $r_hostalloc_maxwait_starvation) {
+       m/=/ or die "$r_hostalloc_maxwait_starvation ?";
+       exists($p{$`}) or die "$r_hostalloc_maxwait_starvation $` ?";
+       $p{$`} = $' + 0.0;
+    }
+    # Xh = C + L * 1^A / 1^B         =>   L = Xh - C
+    # Xt = C + L * 1^A / 9^B
+    # Xt = C + (Xh - C) * 1^A / 9^B  =>   B = log_9[ Xh - C) / (Xt - C) ]
+    $p{L} = $p{Xh} - $p{C};
+    $p{B} = log(($p{Xh} - $p{C}) / ($p{Xt} - $p{C})) / log(9);
+    logm("hostalloc_maxwait_starvation: ".
+        join ' ', map { "$_=$p{$_}" } sort keys %p);
+    return \%p;
+}
+
+sub hostalloc_starvation_calculate_X ($$$) {
+    my ($p, $W, $D) = @_; # => X, undef meaning "forever"
+    return undef unless %$p and $D;
+    confess unless $W > 0 && $D > 0;
+    return $p->{C} + $p->{L} * $W**$p->{A} / $D**$p->{B};
+}
+
 #---------- duration estimator ----------
 
 sub duration_estimator ($$;$$) {
diff --git a/mg-hostalloc-starvation-demo b/mg-hostalloc-starvation-demo
new file mode 100755
index 00000000..7944cc24
--- /dev/null
+++ b/mg-hostalloc-starvation-demo
@@ -0,0 +1,53 @@
+#!/usr/bin/perl -w
+
+use strict;
+BEGIN { unshift @INC, qw(.); }
+
+use strict;
+use POSIX;
+use Osstest::Executive;
+use Data::Dumper;
+
+die unless @ARGV>=1;
+
+our ($rv) = $ARGV[0]; # $r{hostalloc_starvation};
+shift @ARGV;
+
+my $p = hostalloc_starvation_parse_runvar($rv);
+
+my $l = 8;
+
+my @ts = qw(1 2 3 5 10 20 33 66 100 200 333);
+
+foreach my $w (qw(332 99 32 9 3 2 1)) {
+    printf "W=%3d |", $w;
+    foreach my $t (@ts) {
+       my $d = $t - $w;
+       print " | ";
+       if ($d <= 0) {
+           printf "     %${l}s", '';
+       } else {
+           my $x = hostalloc_starvation_calculate_X($p, $w, $d);
+           printf "%3d%% ", 100.0*$w/$t;
+           if (defined $x) {
+               printf "%${l}.2f", $x;
+           } else {
+               printf "%${l}s", 'never';
+           }
+       }
+    }
+    print "\n";
+}
+
+print "\n";
+print "       ";
+foreach my $t (@ts) {
+    printf " |      %${l}s", sprintf "T=%3d", $t;
+}
+print "\n";
+
+foreach (@ARGV) {
+    m/,/ or die $!;
+    my $x = hostalloc_starvation_calculate_X($p, $', $`);
+    printf "D=%3d W=%3d X=%${l}.2f\n", $`, $', $x;
+}
-- 
2.11.0


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/xen-devel