about summary refs log tree commit diff stats
path: root/062scheduler.cc
blob: ca22caae28665a54200b326b28d8708e2fb92fbb (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
//: For convenience, some instructions will take literal arrays of characters (strings).
//:
//: Instead of quotes, we'll use [] to delimit strings. That'll reduce the
//: need for escaping since we can support nested brackets. And we can also
//: imagine that 'recipe' might one day itself be defined in mu, doing its own
//: parsing.

:(scenarios load)
:(scenario string_literal)
recipe main [
  1:address:array:character <- copy [abc def]  # copy can't really take a string
]
+parse:   ingredient: {name: "abc def", value: 0, type: 0, properties: ["abc def": "literal-string"]}

:(scenario string_literal_with_colons)
recipe main [
  1:address:array:character <- copy [abc:def/ghi]
]
+parse:   ingredient: {name: "abc:def/ghi", value: 0, type: 0, properties: ["abc:def/ghi": "literal-string"]}

:(before "End Mu Types Initialization")
Type_number["literal-string"] = 0;

:(after "string next_word(istream& in)")
  if (in.peek() == '[') {
    string result = slurp_quoted(in);
    skip_whitespace(in);
    skip_comment(in);
    return result;
  }

:(code)
string slurp_quoted(istream& in) {
  assert(!in.eof());
  assert(in.peek() == '[');
  ostringstream out;
  int size = 0;
  while (!in.eof()) {
    char c = in.get();
//?     cout << c << '\n'; //? 1
    out << c;
//?     cout << out.str() << "$\n"; //? 1
    if (c == '[') ++size;
    if (c == ']') --size;
    if (size == 0) break;
  }
  return out.str();
}

:(after "reagent::reagent(string s)")
//?   cout << s[0] << '\n'; //? 1
  if (s[0] == '[') {
    assert(s[s.size()-1] == ']');
    // delete [] delimiters
    s.erase(0, 1);
    s.erase(s.size()-1, s.size());
    name = s;
    types.push_back(0);
    properties.push_back(pair<string, vector<string> >(name, vector<string>()));
    properties.back().second.push_back("literal-string");
    return;
  }

:(scenario string_literal_nested)
recipe main [
  1:address:array:character <- copy [abc [def]]
]
+parse:   ingredient: {name: "abc [def]", value: 0, type: 0, properties: ["abc [def]": "literal-string"]}

:(scenario string_literal_and_comment)
recipe main [
  1:address:array:character <- copy [abc]  # comment
]
+parse: instruction: copy
+parse:   ingredient: {name: "abc", value: 0, type: 0, properties: ["abc": "literal-string"]}
+parse:   product: {name: "1", value: 0, type: 2-5-4, properties: ["1": "address":"array":"character"]}
# no other ingredients
$parse: 3
n>"void run_current_routine(long long int time_slice)") long long int ninstrs = 0; while (Current_routine->state == RUNNING && ninstrs < time_slice) :(after "Running One Instruction") ninstrs++; //: now the rest of the scheduler is clean :(before "struct routine") enum routine_state { RUNNING, COMPLETED, // End routine States }; :(before "End routine Fields") enum routine_state state; :(before "End routine Constructor") state = RUNNING; :(before "End Globals") vector<routine*> Routines; long long int Current_routine_index = 0; long long int Scheduling_interval = 500; :(before "End Setup") Scheduling_interval = 500; Routines.clear(); :(replace{} "void run(recipe_ordinal r)") void run(recipe_ordinal r) { run(new routine(r)); } :(code) void run(routine* rr) { Routines.push_back(rr); Current_routine_index = 0, Current_routine = Routines.at(0); while (!all_routines_done()) { skip_to_next_routine(); assert(Current_routine); assert(Current_routine->state == RUNNING); trace(9990, "schedule") << current_routine_label() << end(); run_current_routine(Scheduling_interval); // Scheduler State Transitions if (Current_routine->completed()) Current_routine->state = COMPLETED; // End Scheduler State Transitions // Scheduler Cleanup // End Scheduler Cleanup } } bool all_routines_done() { for (long long int i = 0; i < SIZE(Routines); ++i) { if (Routines.at(i)->state == RUNNING) { return false; } } return true; } // skip Current_routine_index past non-RUNNING routines void skip_to_next_routine() { assert(!Routines.empty()); assert(Current_routine_index < SIZE(Routines)); for (long long int i = (Current_routine_index+1)%SIZE(Routines); i != Current_routine_index; i = (i+1)%SIZE(Routines)) { if (Routines.at(i)->state == RUNNING) { Current_routine_index = i; Current_routine = Routines.at(i); return; } } } string current_routine_label() { ostringstream result; const call_stack& calls = Current_routine->calls; for (call_stack::const_iterator p = calls.begin(); p != calls.end(); ++p) { if (p != calls.begin()) result << '/'; result << get(Recipe, p->running_recipe).name; } return result.str(); } :(before "End Teardown") for (long long int i = 0; i < SIZE(Routines); ++i) delete Routines.at(i); Routines.clear(); Current_routine = NULL; //: special case for the very first routine :(replace{} "void run_main(int argc, char* argv[])") void run_main(int argc, char* argv[]) { recipe_ordinal r = get(Recipe_ordinal, "main"); assert(r); routine* main_routine = new routine(r); // pass in commandline args as ingredients to main // todo: test this Current_routine = main_routine; for (long long int i = 1; i < argc; ++i) { vector<double> arg; arg.push_back(new_mu_string(argv[i])); current_call().ingredient_atoms.push_back(arg); } run(main_routine); } //:: To schedule new routines to run, call 'start-running'. //: 'start-running' will return a unique id for the routine that was created. //: routine id is a number, but don't do any arithmetic on it :(before "End routine Fields") long long int id; :(before "End Globals") long long int Next_routine_id = 1; :(before "End Setup") Next_routine_id = 1; :(before "End routine Constructor") id = Next_routine_id; Next_routine_id++; //: routines save the routine that spawned them :(before "End routine Fields") // todo: really should be routine_id, but that's less efficient. long long int parent_index; // only < 0 if there's no parent_index :(before "End routine Constructor") parent_index = -1; :(before "End Primitive Recipe Declarations") START_RUNNING, :(before "End Primitive Recipe Numbers") put(Recipe_ordinal, "start-running", START_RUNNING); :(before "End Primitive Recipe Checks") case START_RUNNING: { if (inst.ingredients.empty()) { raise_error << maybe(get(Recipe, r).name) << "'start-running' requires at least one ingredient: the recipe to start running\n" << end(); break; } if (!is_mu_recipe(inst.ingredients.at(0))) { raise_error << maybe(get(Recipe, r).name) << "first ingredient of 'start-running' should be a recipe, but got " << debug_string(inst.ingredients.at(0)) << '\n' << end(); break; } break; } :(before "End Primitive Recipe Implementations") case START_RUNNING: { routine* new_routine = new routine(ingredients.at(0).at(0)); new_routine->parent_index = Current_routine_index; // populate ingredients for (long long int i = 1; i < SIZE(current_instruction().ingredients); ++i) { new_routine->calls.front().ingredient_atoms.push_back(ingredients.at(i)); reagent ingredient = current_instruction().ingredients.at(i); canonize_type(ingredient); new_routine->calls.front().ingredients.push_back(ingredient); } Routines.push_back(new_routine); products.resize(1); products.at(0).push_back(new_routine->id); break; } :(scenario scheduler_runs_single_routine) % Scheduling_interval = 1; recipe f1 [ 1:number <- copy 0 2:number <- copy 0 ] +schedule: f1 +run: 1:number <- copy 0 +schedule: f1 +run: 2:number <- copy 0 :(scenario scheduler_interleaves_routines) % Scheduling_interval = 1; recipe f1 [ start-running f2 1:number <- copy 0 2:number <- copy 0 ] recipe f2 [ 3:number <- copy 0 4:number <- copy 0 ] +schedule: f1 +run: start-running f2 +schedule: f2 +run: 3:number <- copy 0 +schedule: f1 +run: 1:number <- copy 0 +schedule: f2 +run: 4:number <- copy 0 +schedule: f1 +run: 2:number <- copy 0 :(scenario start_running_takes_ingredients) recipe f1 [ start-running f2, 3 # wait for f2 to run { jump-unless 1:number, -1 } ] recipe f2 [ 1:number <- next-ingredient 2:number <- add 1:number, 1 ] +mem: storing 4 in location 2 :(scenario start_running_returns_routine_id) recipe f1 [ 1:number <- start-running f2 ] recipe f2 [ 12:number <- copy 44 ] +mem: storing 2 in location 1 //: this scenario will require some careful setup in escaped C++ //: (straining our tangle capabilities to near-breaking point) :(scenario scheduler_skips_completed_routines) % recipe_ordinal f1 = load("recipe f1 [\n1:number <- copy 0\n]\n").front(); % recipe_ordinal f2 = load("recipe f2 [\n2:number <- copy 0\n]\n").front(); % Routines.push_back(new routine(f1)); // f1 meant to run % Routines.push_back(new routine(f2)); % Routines.back()->state = COMPLETED; // f2 not meant to run # must have at least one routine without escaping recipe f3 [ 3:number <- copy 0 ] # by interleaving '+' lines with '-' lines, we allow f1 and f3 to run in any order +schedule: f1 +mem: storing 0 in location 1 -schedule: f2 -mem: storing 0 in location 2 +schedule: f3 +mem: storing 0 in location 3 :(scenario scheduler_starts_at_middle_of_routines) % Routines.push_back(new routine(COPY)); % Routines.back()->state = COMPLETED; recipe f1 [ 1:number <- copy 0 2:number <- copy 0 ] +schedule: f1 -run: idle //:: Errors in a routine cause it to terminate. :(scenario scheduler_terminates_routines_after_errors) % Hide_errors = true; % Scheduling_interval = 2; recipe f1 [ start-running f2 1:number <- copy 0 2:number <- copy 0 ] recipe f2 [ # divide by 0 twice 3:number <- divide-with-remainder 4, 0 4:number <- divide-with-remainder 4, 0 ] # f2 should stop after first divide by 0 +error: f2: divide by zero in '3:number <- divide-with-remainder 4, 0' -error: f2: divide by zero in '4:number <- divide-with-remainder 4, 0' :(after "operator<<(ostream& os, unused end)") if (Trace_stream && Trace_stream->curr_label == "error" && Current_routine) { Current_routine->state = COMPLETED; } //:: Routines are marked completed when their parent completes. :(scenario scheduler_kills_orphans) recipe main [ start-running f1 # f1 never actually runs because its parent completes without waiting for it ] recipe f1 [ 1:number <- copy 0 ] -schedule: f1 :(before "End Scheduler Cleanup") for (long long int i = 0; i < SIZE(Routines); ++i) { if (Routines.at(i)->state == COMPLETED) continue; if (Routines.at(i)->parent_index < 0) continue; // root thread if (has_completed_parent(i)) { Routines.at(i)->state = COMPLETED; } } :(code) bool has_completed_parent(long long int routine_index) { for (long long int j = routine_index; j >= 0; j = Routines.at(j)->parent_index) { if (Routines.at(j)->state == COMPLETED) return true; } return false; } //:: 'routine-state' can tell if a given routine id is running :(scenario routine_state_test) % Scheduling_interval = 2; recipe f1 [ 1:number/child-id <- start-running f2 12:number <- copy 0 # race condition since we don't care about location 12 # thanks to Scheduling_interval, f2's one instruction runs in between here and completes 2:number/state <- routine-state 1:number/child-id ] recipe f2 [ 12:number <- copy 0 # trying to run a second instruction marks routine as completed ] # recipe f2 should be in state COMPLETED +mem: storing 1 in location 2 :(before "End Primitive Recipe Declarations") ROUTINE_STATE, :(before "End Primitive Recipe Numbers") put(Recipe_ordinal, "routine-state", ROUTINE_STATE); :(before "End Primitive Recipe Checks") case ROUTINE_STATE: { if (SIZE(inst.ingredients) != 1) { raise_error << maybe(get(Recipe, r).name) << "'routine-state' requires exactly one ingredient, but got " << inst.to_string() << '\n' << end(); break; } if (!is_mu_number(inst.ingredients.at(0))) { raise_error << maybe(get(Recipe, r).name) << "first ingredient of 'routine-state' should be a routine id generated by 'start-running', but got " << inst.ingredients.at(0).original_string << '\n' << end(); break; } break; } :(before "End Primitive Recipe Implementations") case ROUTINE_STATE: { long long int id = ingredients.at(0).at(0); long long int result = -1; for (long long int i = 0; i < SIZE(Routines); ++i) { if (Routines.at(i)->id == id) { result = Routines.at(i)->state; break; } } products.resize(1); products.at(0).push_back(result); break; } //:: miscellaneous helpers :(before "End Primitive Recipe Declarations") RESTART, :(before "End Primitive Recipe Numbers") put(Recipe_ordinal, "restart", RESTART); :(before "End Primitive Recipe Checks") case RESTART: { if (SIZE(inst.ingredients) != 1) { raise_error << maybe(get(Recipe, r).name) << "'restart' requires exactly one ingredient, but got " << inst.to_string() << '\n' << end(); break; } if (!is_mu_number(inst.ingredients.at(0))) { raise_error << maybe(get(Recipe, r).name) << "first ingredient of 'restart' should be a routine id generated by 'start-running', but got " << inst.ingredients.at(0).original_string << '\n' << end(); break; } break; } :(before "End Primitive Recipe Implementations") case RESTART: { long long int id = ingredients.at(0).at(0); for (long long int i = 0; i < SIZE(Routines); ++i) { if (Routines.at(i)->id == id) { Routines.at(i)->state = RUNNING; break; } } break; } :(before "End Primitive Recipe Declarations") STOP, :(before "End Primitive Recipe Numbers") put(Recipe_ordinal, "stop", STOP); :(before "End Primitive Recipe Checks") case STOP: { if (SIZE(inst.ingredients) != 1) { raise_error << maybe(get(Recipe, r).name) << "'stop' requires exactly one ingredient, but got " << inst.to_string() << '\n' << end(); break; } if (!is_mu_number(inst.ingredients.at(0))) { raise_error << maybe(get(Recipe, r).name) << "first ingredient of 'stop' should be a routine id generated by 'start-running', but got " << inst.ingredients.at(0).original_string << '\n' << end(); break; } break; } :(before "End Primitive Recipe Implementations") case STOP: { long long int id = ingredients.at(0).at(0); for (long long int i = 0; i < SIZE(Routines); ++i) { if (Routines.at(i)->id == id) { Routines.at(i)->state = COMPLETED; break; } } break; } :(before "End Primitive Recipe Declarations") _DUMP_ROUTINES, :(before "End Primitive Recipe Numbers") put(Recipe_ordinal, "$dump-routines", _DUMP_ROUTINES); :(before "End Primitive Recipe Checks") case _DUMP_ROUTINES: { break; } :(before "End Primitive Recipe Implementations") case _DUMP_ROUTINES: { for (long long int i = 0; i < SIZE(Routines); ++i) { cerr << i << ": " << Routines.at(i)->id << ' ' << Routines.at(i)->state << ' ' << Routines.at(i)->parent_index << '\n'; } break; } //: support for stopping routines after some number of cycles :(scenario routine_discontinues_past_limit) % Scheduling_interval = 2; recipe f1 [ 1:number/child-id <- start-running f2 limit-time 1:number/child-id, 10 # padding loop just to make sure f2 has time to completed 2:number <- copy 20 2:number <- subtract 2:number, 1 jump-if 2:number, -2:offset ] recipe f2 [ jump -1:offset # run forever $print [should never get here], 10/newline ] # f2 terminates +schedule: discontinuing routine 2 :(before "End routine States") DISCONTINUED, :(before "End Scheduler State Transitions") if (Current_routine->limit >= 0) { if (Current_routine->limit <= Scheduling_interval) { trace(9999, "schedule") << "discontinuing routine " << Current_routine->id << end(); Current_routine->state = DISCONTINUED; Current_routine->limit = 0; } else { Current_routine->limit -= Scheduling_interval; } } :(before "End routine Fields") long long int limit; :(before "End routine Constructor") limit = -1; /* no limit */ :(before "End Primitive Recipe Declarations") LIMIT_TIME, :(before "End Primitive Recipe Numbers") put(Recipe_ordinal, "limit-time", LIMIT_TIME); :(before "End Primitive Recipe Checks") case LIMIT_TIME: { if (SIZE(inst.ingredients) != 2) { raise_error << maybe(get(Recipe, r).name) << "'limit-time' requires exactly two ingredient, but got " << inst.to_string() << '\n' << end(); break; } if (!is_mu_number(inst.ingredients.at(0))) { raise_error << maybe(get(Recipe, r).name) << "first ingredient of 'limit-time' should be a routine id generated by 'start-running', but got " << inst.ingredients.at(0).original_string << '\n' << end(); break; } if (!is_mu_number(inst.ingredients.at(1))) { raise_error << maybe(get(Recipe, r).name) << "second ingredient of 'limit-time' should be a number (of instructions to run for), but got " << inst.ingredients.at(1).original_string << '\n' << end(); break; } break; } :(before "End Primitive Recipe Implementations") case LIMIT_TIME: { long long int id = ingredients.at(0).at(0); for (long long int i = 0; i < SIZE(Routines); ++i) { if (Routines.at(i)->id == id) { Routines.at(i)->limit = ingredients.at(1).at(0); break; } } break; } //:: make sure that each routine gets a different alloc to start :(scenario new_concurrent) recipe f1 [ start-running f2 1:address:shared:number/raw <- new number:type # wait for f2 to complete { loop-unless 4:number/raw } ] recipe f2 [ 2:address:shared:number/raw <- new number:type # hack: assumes scheduler implementation 3:boolean/raw <- equal 1:address:shared:number/raw, 2:address:shared:number/raw # signal f2 complete 4:number/raw <- copy 1 ] +mem: storing 0 in location 3