From cd9bb850caeca88747a25436fc65c67c6d5cd89a Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Sat, 27 Aug 2016 20:49:03 -0700 Subject: 3266 --- html/073wait.cc.html | 144 ++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 125 insertions(+), 19 deletions(-) (limited to 'html/073wait.cc.html') diff --git a/html/073wait.cc.html b/html/073wait.cc.html index 49bdd7d3..847eafa3 100644 --- a/html/073wait.cc.html +++ b/html/073wait.cc.html @@ -21,6 +21,7 @@ body { font-size: 12pt; font-family: monospace; color: #eeeeee; background-color .Special { color: #c00000; } .Identifier { color: #fcb165; } .Normal { color: #eeeeee; background-color: #080808; padding-bottom: 1px; } +.CommentedCode { color: #6c6c6c; } --> @@ -68,6 +69,11 @@ waiting_on_location = old_value_of_waiting_location = 0false; raise << Current_scenario->name << ": deadlock!\n" << end(); } +:(before "End Run Routine") +if (any_routines_waiting()) { + raise << "deadlock!\n" << end(); + dump_waiting_routines(); +} :(before "End Test Teardown") if (Passed && any_routines_with_error()) { Passed = false; @@ -81,6 +87,12 @@ waiting_on_location = old_value_of_waiting_location = 0} return false; } +void dump_waiting_routines() { + for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->state == WAITING) + cerr << i << ": " << routine_label(Routines.at(i)) << '\n'; + } +} //: primitive recipe to put routines in that state @@ -258,26 +270,112 @@ def main [ ] +mem: storing 11 in location 21 -//: also allow waiting on a routine to stop running +//: also allow waiting on a routine to block +//: (just for tests; use wait_for_routine below wherever possible) + +:(scenario wait_for_routine_to_block) +def f1 [ + 1:number/routine <- start-running f2 + wait-for-routine-to-block 1:number/routine + # now wait for f2 to run and modify location 10 before using its value + 11:number <- copy 10:number +] +def f2 [ + 10:number <- copy 34 +] ++schedule: f1 ++run: waiting for routine 2 to block ++schedule: f2 ++schedule: waking up blocked routine 1 ++schedule: f1 +# if we got the synchronization wrong we'd be storing 0 in location 11 ++mem: storing 34 in location 11 + +:(before "End routine Fields") +// only if state == WAITING +int waiting_on_routine_to_block; +:(before "End routine Constructor") +waiting_on_routine_to_block = 0; + +:(before "End Primitive Recipe Declarations") +WAIT_FOR_ROUTINE_TO_BLOCK, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "wait-for-routine-to-block", WAIT_FOR_ROUTINE_TO_BLOCK); +:(before "End Primitive Recipe Checks") +case WAIT_FOR_ROUTINE_TO_BLOCK: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'wait-for-routine-to-block' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_number(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine-to-block' 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 WAIT_FOR_ROUTINE_TO_BLOCK: { + if (ingredients.at(0).at(0) == Current_routine->id) { + raise << maybe(current_recipe_name()) << "routine can't wait for itself! '" << to_original_string(current_instruction()) << "'\n" << end(); + break; + } + Current_routine->state = WAITING; + Current_routine->waiting_on_routine_to_block = ingredients.at(0).at(0); + trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << " to block" << end(); +//? cerr << Current_routine->id << ": waiting for routine " << ingredients.at(0).at(0) << " to block\n"; + break; +} + +:(before "End Scheduler State Transitions") +// Wake up any routines waiting for other routines to stop running. +for (int i = 0; i < SIZE(Routines); ++i) { + if (Routines.at(i)->state != WAITING) continue; + routine* waiter = Routines.at(i); + if (!waiter->waiting_on_routine_to_block) continue; + int id = waiter->waiting_on_routine_to_block; + assert(id != waiter->id); // routine can't wait on itself + for (int j = 0; j < SIZE(Routines); ++j) { + const routine* waitee = Routines.at(j); + if (waitee->id == id && waitee->state != RUNNING) { + // routine is WAITING or COMPLETED or DISCONTINUED + trace(9999, "schedule") << "waking up blocked routine " << waiter->id << end(); +//? cerr << id << " is now unblocked (" << waitee->state << "); waking up waiting routine " << waiter->id << '\n'; + waiter->state = RUNNING; + waiter->waiting_on_routine_to_block = 0; + } + } +} + +//: allow waiting on a routine to complete :(scenario wait_for_routine) def f1 [ - 1:number <- copy 0 - 12:number/routine <- start-running f2 - wait-for-routine 12:number/routine - # now wait for f2 to run and modify location 1 before using its value - 3:number <- copy 1:number + # add a few routines to run + 1:number/routine <- start-running f2 + 2:number/routine <- start-running f3 + wait-for-routine 1:number/routine + # now wait for f2 to *complete* and modify location 13 before using its value + 20:number <- copy 13:number ] def f2 [ - 1:number <- copy 34 + 10:number <- copy 0 # just padding + switch # simulate a block; routine f1 shouldn't restart at this point + 13:number <- copy 34 +] +def f3 [ + # padding routine just to help simulate the block in f2 using 'switch' + 11:number <- copy 0 + 12:number <- copy 0 ] +schedule: f1 +run: waiting for routine 2 +schedule: f2 ++schedule: f3 ++schedule: f2 +schedule: waking up routine 1 +schedule: f1 -# if we got the synchronization wrong we'd be storing 0 in location 3 -+mem: storing 34 in location 3 +# if we got the synchronization wrong we'd be storing 0 in location 20 ++mem: storing 34 in location 20 :(before "End routine Fields") // only if state == WAITING @@ -310,27 +408,34 @@ put(Recipe_ordinal,->state = WAITING; Current_routine->waiting_on_routine = ingredients.at(0).at(0); trace(9998, "run") << "waiting for routine " << ingredients.at(0).at(0) << end(); +//? cerr << Current_routine->id << ": waiting for routine " << ingredients.at(0).at(0) << '\n'; break; } :(before "End Scheduler State Transitions") -// Wake up any routines waiting for other routines to go to sleep. +// Wake up any routines waiting for other routines to complete. // Important: this must come after the scheduler loop above giving routines // waiting for locations to change a chance to wake up. for (int i = 0; i < SIZE(Routines); ++i) { if (Routines.at(i)->state != WAITING) continue; - if (!Routines.at(i)->waiting_on_routine) continue; - int id = Routines.at(i)->waiting_on_routine; - assert(id != Routines.at(i)->id); // routine can't wait on itself + routine* waiter = Routines.at(i); + if (!waiter->waiting_on_routine) continue; + int id = waiter->waiting_on_routine; + assert(id != waiter->id); // routine can't wait on itself for (int j = 0; j < SIZE(Routines); ++j) { - if (Routines.at(j)->id == id && Routines.at(j)->state != RUNNING) { - trace(9999, "schedule") << "waking up routine " << Routines.at(i)->id << end(); - Routines.at(i)->state = RUNNING; - Routines.at(i)->waiting_on_routine = 0; + const routine* waitee = Routines.at(j); + if (waitee->id == id && waitee->state != RUNNING && waitee->state != WAITING) { + // routine is COMPLETED or DISCONTINUED + trace(9999, "schedule") << "waking up routine " << waiter->id << end(); +//? cerr << id << " is now done (" << waitee->state << "); waking up waiting routine " << waiter->id << '\n'; + waiter->state = RUNNING; + waiter->waiting_on_routine = 0; } } } +//: yield voluntarily to let some other routine run + :(before "End Primitive Recipe Declarations") SWITCH, :(before "End Primitive Recipe Numbers") @@ -339,17 +444,18 @@ put(Recipe_ordinal,case SWITCH: { break; } +//: pick another RUNNING routine at random and wait for it to get a chance +//: there might be a better implementation than this :(before "End Primitive Recipe Implementations") case SWITCH: { int id = some_other_running_routine(); if (id) { assert(id != Current_routine->id); Current_routine->state = WAITING; - Current_routine->waiting_on_routine = id; + Current_routine->waiting_on_routine_to_block = id; } break; } - :(code) int some_other_running_routine() { for (int i = 0; i < SIZE(Routines); ++i) { -- cgit 1.4.1-2-gfad0