From 0ca56ed853c3d9bc8c26d1b014d8b665363fc2d0 Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Thu, 15 Sep 2016 01:01:58 -0700 Subject: 3355 --- html/073wait.cc.html | 314 +++++++++++++++++++++++++++++++++++---------------- 1 file changed, 215 insertions(+), 99 deletions(-) (limited to 'html/073wait.cc.html') diff --git a/html/073wait.cc.html b/html/073wait.cc.html index 926c6b29..b99b8cc5 100644 --- a/html/073wait.cc.html +++ b/html/073wait.cc.html @@ -16,6 +16,7 @@ body { font-size: 12pt; font-family: monospace; color: #eeeeee; background-color .Constant { color: #00a0a0; } .cSpecial { color: #008000; } .traceContains { color: #008000; } +.SalientComment { color: #00ffff; } .Comment { color: #9090ff; } .Delimiter { color: #800080; } .Special { color: #c00000; } @@ -40,18 +41,22 @@ body { font-size: 12pt; font-family: monospace; color: #eeeeee; background-color :(scenario wait_for_location) def f1 [ - 1:number <- copy 0 + 10:number <- copy 34 start-running f2 - 2:location <- copy 1/unsafe - wait-for-location 2:location - # now wait for f2 to run and modify location 1 before using its value - 3:number <- copy 1:number + 20:location <- copy 10/unsafe + wait-for-reset-then-set 20:location + # wait for f2 to run and reset location 1 + 30:number <- copy 10:number ] def f2 [ - 1:number <- copy 34 + 10:location <- copy 0/unsafe ] -# if we got the synchronization wrong we'd be storing 0 in location 3 -+mem: storing 34 in location 3 ++schedule: f1 ++run: waiting for location 10 to reset ++schedule: f2 ++schedule: waking up routine 1 ++schedule: f1 ++mem: storing 1 in location 30 //: define the new state that all routines can be in @@ -60,9 +65,8 @@ WAITING, :(before "End routine Fields") // only if state == WAITING int waiting_on_location; -int old_value_of_waiting_location; :(before "End routine Constructor") -waiting_on_location = old_value_of_waiting_location = 0; +waiting_on_location = 0; :(before "End Mu Test Teardown") if (Passed && any_routines_waiting()) { @@ -94,30 +98,61 @@ waiting_on_location = old_value_of_waiting_location = 0} } -//: primitive recipe to put routines in that state +//: Primitive recipe to put routines in that state. +//: This primitive is also known elsewhere as compare-and-set (CAS). Used to +//: build locks. :(before "End Primitive Recipe Declarations") -WAIT_FOR_LOCATION, +WAIT_FOR_RESET_THEN_SET, :(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "wait-for-location", WAIT_FOR_LOCATION); +put(Recipe_ordinal, "wait-for-reset-then-set", WAIT_FOR_RESET_THEN_SET); :(before "End Primitive Recipe Checks") -case WAIT_FOR_LOCATION: { +case WAIT_FOR_RESET_THEN_SET: { if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'wait-for-location' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + raise << maybe(get(Recipe, r).name) << "'wait-for-reset-then-set' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); break; } if (!is_mu_location(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "'wait-for-location' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + raise << maybe(get(Recipe, r).name) << "'wait-for-reset-then-set' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); } break; } :(before "End Primitive Recipe Implementations") -case WAIT_FOR_LOCATION: { - int loc = ingredients.at(0).at(0); +case WAIT_FOR_RESET_THEN_SET: { + int loc = static_cast<int>(ingredients.at(0).at(0)); + trace(9998, "run") << "wait: *" << loc << " = " << get_or_insert(Memory, loc) << end(); + if (get_or_insert(Memory, loc) == 0) { + trace(9998, "run") << "location " << loc << " is already 0; setting" << end(); + put(Memory, loc, 1); + break; + } + trace(9998, "run") << "waiting for location " << loc << " to reset" << end(); Current_routine->state = WAITING; Current_routine->waiting_on_location = loc; - Current_routine->old_value_of_waiting_location = get_or_insert(Memory, loc); - trace(9998, "run") << "waiting for location " << loc << " to change from " << no_scientific(get_or_insert(Memory, loc)) << end(); + break; +} + +//: Counterpart to unlock a lock. +:(before "End Primitive Recipe Declarations") +RESET, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "reset", RESET); +:(before "End Primitive Recipe Checks") +case RESET: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'reset' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + break; + } + if (!is_mu_location(inst.ingredients.at(0))) { + raise << maybe(get(Recipe, r).name) << "'reset' requires a location ingredient, but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + } + break; +} +:(before "End Primitive Recipe Implementations") +case RESET: { + int loc = static_cast<int>(ingredients.at(0).at(0)); + put(Memory, loc, 0); + trace(9998, "run") << "reset: *" << loc << " = " << get_or_insert(Memory, loc) << end(); break; } @@ -126,17 +161,18 @@ put(Recipe_ordinal,:(before "End Scheduler State Transitions") for (int i = 0; i < SIZE(Routines); ++i) { if (Routines.at(i)->state != WAITING) continue; - if (Routines.at(i)->waiting_on_location && - get_or_insert(Memory, Routines.at(i)->waiting_on_location) != Routines.at(i)->old_value_of_waiting_location) { - trace(9999, "schedule") << "waking up routine\n" << end(); + int loc = Routines.at(i)->waiting_on_location; + if (loc && get_or_insert(Memory, loc) == 0) { + trace(9999, "schedule") << "waking up routine " << Routines.at(i)->id << end(); + put(Memory, loc, 1); Routines.at(i)->state = RUNNING; - Routines.at(i)->waiting_on_location = Routines.at(i)->old_value_of_waiting_location = 0; + Routines.at(i)->waiting_on_location = 0; } } -//: primitive to help compute locations to wait for -//: only supports elements inside containers, no arrays or containers within -//: containers yet. +//: Primitive to help compute locations to wait on. +//: Only supports elements immediately inside containers; no arrays or +//: containers within containers yet. :(scenario get_location) def main [ @@ -275,166 +311,219 @@ def main [ ] +mem: storing 11 in location 21 -//: also allow waiting on a routine to block -//: (just for tests; use wait_for_routine below wherever possible) +//: allow waiting on a routine to complete -:(scenario wait_for_routine_to_block) +:(scenario wait_for_routine) def f1 [ + # add a few routines to run 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 + 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 [ - 10: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 to block ++run: waiting for routine 2 +schedule: f2 -+schedule: waking up blocked routine 1 ++schedule: f3 ++schedule: f2 ++schedule: waking up routine 1 +schedule: f1 -# if we got the synchronization wrong we'd be storing 0 in location 11 -+mem: storing 34 in location 11 +# 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 -int waiting_on_routine_to_block; +int waiting_on_routine; :(before "End routine Constructor") -waiting_on_routine_to_block = 0; +waiting_on_routine = 0; :(before "End Primitive Recipe Declarations") -WAIT_FOR_ROUTINE_TO_BLOCK, +WAIT_FOR_ROUTINE, :(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "wait-for-routine-to-block", WAIT_FOR_ROUTINE_TO_BLOCK); +put(Recipe_ordinal, "wait-for-routine", WAIT_FOR_ROUTINE); :(before "End Primitive Recipe Checks") -case WAIT_FOR_ROUTINE_TO_BLOCK: { +case WAIT_FOR_ROUTINE: { 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(); + raise << maybe(get(Recipe, r).name) << "'wait-for-routine' 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(); + raise << maybe(get(Recipe, r).name) << "first ingredient of 'wait-for-routine' 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: { +case WAIT_FOR_ROUTINE: { 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"; + 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 stop running. +// 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; routine* waiter = Routines.at(i); - if (!waiter->waiting_on_routine_to_block) continue; - int id = waiter->waiting_on_routine_to_block; + 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) { 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'; + 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_to_block = 0; + waiter->waiting_on_routine = 0; } } } -//: allow waiting on a routine to complete +//:: helpers for manipulating routines in tests +//: +//: Managing arbitrary scenarios requires the ability to: +//: a) stop the current routine (`switch`) +//: b) restart a routine (`restart`) +//: c) tell when a routine is blocked +//: +//: A routine is blocked either if it's waiting or if it explicitly signals +//: that it's blocked (even as it periodically wakes up and polls for some +//: event). +//: +//: Signalling blockedness might well be a huge hack. But Mu doesn't have Unix +//: signals to avoid polling with, because signals are also pretty hacky. -:(scenario wait_for_routine) +:(before "End routine Fields") +bool blocked; +:(before "End routine Constructor") +blocked = false; + +:(before "End Primitive Recipe Declarations") +CURRENT_ROUTINE_IS_BLOCKED, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "current-routine-is-blocked", CURRENT_ROUTINE_IS_BLOCKED); +:(before "End Primitive Recipe Checks") +case CURRENT_ROUTINE_IS_BLOCKED: { + if (!inst.ingredients.empty()) { + raise << maybe(get(Recipe, r).name) << "'current-routine-is-blocked' should have no ingredients, but got '" << inst.original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case CURRENT_ROUTINE_IS_BLOCKED: { + Current_routine->blocked = true; + break; +} + +:(before "End Primitive Recipe Declarations") +CURRENT_ROUTINE_IS_UNBLOCKED, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "current-routine-is-unblocked", CURRENT_ROUTINE_IS_UNBLOCKED); +:(before "End Primitive Recipe Checks") +case CURRENT_ROUTINE_IS_UNBLOCKED: { + if (!inst.ingredients.empty()) { + raise << maybe(get(Recipe, r).name) << "'current-routine-is-unblocked' should have no ingredients, but got '" << inst.original_string << "'\n" << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case CURRENT_ROUTINE_IS_UNBLOCKED: { + Current_routine->blocked = false; + break; +} + +//: also allow waiting on a routine to block +//: (just for tests; use wait_for_routine above wherever possible) + +:(scenario wait_for_routine_to_block) def f1 [ - # 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 + 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 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 + 10:number <- copy 34 ] +schedule: f1 -+run: waiting for routine 2 -+schedule: f2 -+schedule: f3 ++run: waiting for routine 2 to block +schedule: f2 -+schedule: waking up routine 1 ++schedule: waking up routine 1 because routine 2 is blocked +schedule: f1 -# if we got the synchronization wrong we'd be storing 0 in location 20 -+mem: storing 34 in location 20 +# 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; +int waiting_on_routine_to_block; :(before "End routine Constructor") -waiting_on_routine = 0; +waiting_on_routine_to_block = 0; :(before "End Primitive Recipe Declarations") -WAIT_FOR_ROUTINE, +WAIT_FOR_ROUTINE_TO_BLOCK, :(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "wait-for-routine", WAIT_FOR_ROUTINE); +put(Recipe_ordinal, "wait-for-routine-to-block", WAIT_FOR_ROUTINE_TO_BLOCK); :(before "End Primitive Recipe Checks") -case WAIT_FOR_ROUTINE: { +case WAIT_FOR_ROUTINE_TO_BLOCK: { if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'wait-for-routine' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end(); + 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' should be a routine id generated by 'start-running', but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); + 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: { +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 = 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'; + 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(); break; } :(before "End Scheduler State Transitions") -// 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. +// 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) continue; - int id = waiter->waiting_on_routine; + 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 && 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'; + if (waitee->id != id) continue; + if (waitee->state != RUNNING || waitee->blocked) { + trace(9999, "schedule") << "waking up routine " << waiter->id << " because routine " << waitee->id << " is blocked" << end(); waiter->state = RUNNING; - waiter->waiting_on_routine = 0; + waiter->waiting_on_routine_to_block = 0; } } } @@ -498,6 +587,7 @@ put(Recipe_ordinal,if (Routines.at(i)->id == id) { if (Routines.at(i)->state == WAITING) Routines.at(i)->state = RUNNING; + Routines.at(i)->blocked = false; break; } } @@ -518,6 +608,32 @@ def f [ 1:number/raw <- copy 1 ] # shouldn't crash + +:(scenario restart_blocked_routine) +% Scheduling_interval = 1; +def main [ + local-scope + r:number/routine-id <- start-running f + wait-for-routine-to-block r # get past the block in f below + restart r + wait-for-routine-to-block r # should run f to completion +] +# function with one block +def f [ + current-routine-is-blocked + # 8 instructions of padding, many more than 'main' above + 1:number <- add 1:number, 1 + 1:number <- add 1:number, 1 + 1:number <- add 1:number, 1 + 1:number <- add 1:number, 1 + 1:number <- add 1:number, 1 + 1:number <- add 1:number, 1 + 1:number <- add 1:number, 1 + 1:number <- add 1:number, 1 + 1:number <- add 1:number, 1 +] +# make sure all of f ran ++mem: storing 8 in location 1 -- cgit 1.4.1-2-gfad0