blob: fb60ffc8acd0af125f557adaa835a57b89e32562 (
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>Mu - 039wait.cc</title>
<meta name="Generator" content="Vim/7.4">
<meta name="plugin-version" content="vim7.4_v1">
<meta name="syntax" content="cpp">
<meta name="settings" content="use_css,pre_wrap,no_foldcolumn,expand_tabs,prevent_copy=">
<meta name="colorscheme" content="minimal">
<style type="text/css">
<!--
pre { white-space: pre-wrap; font-family: monospace; color: #d0d0d0; background-color: #080808; }
body { font-family: monospace; color: #d0d0d0; background-color: #080808; }
* { font-size: 1em; }
.traceContains { color: #008000; }
.cSpecial { color: #008000; }
.Constant { color: #008080; }
.Comment { color: #8080ff; }
.Delimiter { color: #c000c0; }
.Special { color: #ff6060; }
.CommentedCode { color: #6c6c6c; }
.Identifier { color: #008080; }
-->
</style>
<script type='text/javascript'>
<!--
-->
</script>
</head>
<body>
<pre id='vimCodeElement'>
<span class="Comment">//: Routines can be put in a 'waiting' state, from which it will be ready to</span>
<span class="Comment">//: run again when a specific memory location changes its value. This is mu's</span>
<span class="Comment">//: basic technique for orchestrating the order in which different routines</span>
<span class="Comment">//: operate.</span>
<span class="Delimiter">:(scenario wait_for_location)</span>
recipe f1 [
<span class="Constant">1</span>:number<span class="Special"> <- </span>copy <span class="Constant">0</span>:literal
start-running f2:recipe
wait-for-location <span class="Constant">1</span>:number
<span class="Comment"># now wait for f2 to run and modify location 1 before using its value</span>
<span class="Constant">2</span>:number<span class="Special"> <- </span>copy <span class="Constant">1</span>:number
]
recipe f2 [
<span class="Constant">1</span>:number<span class="Special"> <- </span>copy <span class="Constant">34</span>:literal
]
<span class="Comment"># if we got the synchronization wrong we'd be storing 0 in location 2</span>
<span class="traceContains">+mem: storing 34 in location 2</span>
<span class="Comment">//: define the new state that all routines can be in</span>
<span class="Delimiter">:(before "End routine States")</span>
WAITING<span class="Delimiter">,</span>
<span class="Delimiter">:(before "End routine Fields")</span>
<span class="Comment">// only if state == WAITING</span>
long long int waiting_on_location<span class="Delimiter">;</span>
int old_value_of_waiting_location<span class="Delimiter">;</span>
<span class="Delimiter">:(before "End routine Constructor")</span>
waiting_on_location = old_value_of_waiting_location = <span class="Constant">0</span><span class="Delimiter">;</span>
<span class="Comment">//: primitive recipe to put routines in that state</span>
<span class="Delimiter">:(before "End Primitive Recipe Declarations")</span>
WAIT_FOR_LOCATION<span class="Delimiter">,</span>
<span class="Delimiter">:(before "End Primitive Recipe Numbers")</span>
Recipe_number[<span class="Constant">"wait-for-location"</span>] = WAIT_FOR_LOCATION<span class="Delimiter">;</span>
<span class="Delimiter">:(before "End Primitive Recipe Implementations")</span>
case WAIT_FOR_LOCATION: <span class="Delimiter">{</span>
reagent loc = canonize<span class="Delimiter">(</span>current_instruction<span class="Delimiter">().</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">));</span>
Current_routine<span class="Delimiter">-></span>state = WAITING<span class="Delimiter">;</span>
Current_routine<span class="Delimiter">-></span>waiting_on_location = loc<span class="Delimiter">.</span>value<span class="Delimiter">;</span>
Current_routine<span class="Delimiter">-></span>old_value_of_waiting_location = Memory[loc<span class="Delimiter">.</span>value]<span class="Delimiter">;</span>
trace<span class="Delimiter">(</span>Primitive_recipe_depth<span class="Delimiter">,</span> <span class="Constant">"run"</span><span class="Delimiter">)</span> << <span class="Constant">"waiting for location "</span> << loc<span class="Delimiter">.</span>value << <span class="Constant">" to change from "</span> << Memory[loc<span class="Delimiter">.</span>value]<span class="Delimiter">;</span>
<span class="CommentedCode">//? trace("schedule") << Current_routine->id << ": waiting for location " << loc.value << " to change from " << Memory[loc.value]; //? 2</span>
<span class="Identifier">break</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Comment">//: scheduler tweak to get routines out of that state</span>
<span class="Delimiter">:(before "End Scheduler State Transitions")</span>
for <span class="Delimiter">(</span>long long int i = <span class="Constant">0</span><span class="Delimiter">;</span> i < SIZE<span class="Delimiter">(</span>Routines<span class="Delimiter">);</span> ++i<span class="Delimiter">)</span> <span class="Delimiter">{</span>
<span class="CommentedCode">//? trace("schedule") << "wake up loop 1: routine " << Routines.at(i)->id << " has state " << Routines.at(i)->state; //? 1</span>
if <span class="Delimiter">(</span>Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>state != WAITING<span class="Delimiter">)</span> <span class="Identifier">continue</span><span class="Delimiter">;</span>
<span class="CommentedCode">//? trace("schedule") << "waiting on location: " << Routines.at(i)->waiting_on_location; //? 1</span>
<span class="CommentedCode">//? if (Routines.at(i)->waiting_on_location) //? 2</span>
<span class="CommentedCode">//? trace("schedule") << "checking routine " << Routines.at(i)->id << " waiting on location " //? 2</span>
<span class="CommentedCode">//? << Routines.at(i)->waiting_on_location << ": " << Memory[Routines.at(i)->waiting_on_location] << " vs " << Routines.at(i)->old_value_of_waiting_location; //? 2</span>
if <span class="Delimiter">(</span>Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>waiting_on_location &&
Memory[Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>waiting_on_location] != Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>old_value_of_waiting_location<span class="Delimiter">)</span> <span class="Delimiter">{</span>
trace<span class="Delimiter">(</span><span class="Constant">"schedule"</span><span class="Delimiter">)</span> << <span class="Constant">"waking up routine</span><span class="cSpecial">\n</span><span class="Constant">"</span><span class="Delimiter">;</span>
Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>state = RUNNING<span class="Delimiter">;</span>
Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>waiting_on_location = Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>old_value_of_waiting_location = <span class="Constant">0</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Delimiter">}</span>
<span class="Comment">//: also allow waiting on a routine to stop running</span>
<span class="Delimiter">:(scenario wait_for_routine)</span>
recipe f1 [
<span class="Constant">1</span>:number<span class="Special"> <- </span>copy <span class="Constant">0</span>:literal
<span class="Constant">12</span>:number/routine<span class="Special"> <- </span>start-running f2:recipe
wait-for-routine <span class="Constant">12</span>:number/routine
<span class="Comment"># now wait for f2 to run and modify location 1 before using its value</span>
<span class="Constant">3</span>:number<span class="Special"> <- </span>copy <span class="Constant">1</span>:number
]
recipe f2 [
<span class="Constant">1</span>:number<span class="Special"> <- </span>copy <span class="Constant">34</span>:literal
]
<span class="traceContains">+schedule: f1</span>
<span class="traceContains">+run: waiting for routine 2</span>
<span class="traceContains">+schedule: f2</span>
<span class="traceContains">+schedule: waking up routine 1</span>
<span class="traceContains">+schedule: f1</span>
<span class="Comment"># if we got the synchronization wrong we'd be storing 0 in location 3</span>
<span class="traceContains">+mem: storing 34 in location 3</span>
<span class="Delimiter">:(before "End routine Fields")</span>
<span class="Comment">// only if state == WAITING</span>
long long int waiting_on_routine<span class="Delimiter">;</span>
<span class="Delimiter">:(before "End routine Constructor")</span>
waiting_on_routine = <span class="Constant">0</span><span class="Delimiter">;</span>
<span class="Delimiter">:(before "End Primitive Recipe Declarations")</span>
WAIT_FOR_ROUTINE<span class="Delimiter">,</span>
<span class="Delimiter">:(before "End Primitive Recipe Numbers")</span>
Recipe_number[<span class="Constant">"wait-for-routine"</span>] = WAIT_FOR_ROUTINE<span class="Delimiter">;</span>
<span class="Delimiter">:(before "End Primitive Recipe Implementations")</span>
case WAIT_FOR_ROUTINE: <span class="Delimiter">{</span>
Current_routine<span class="Delimiter">-></span>state = WAITING<span class="Delimiter">;</span>
assert<span class="Delimiter">(</span>scalar<span class="Delimiter">(</span>ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">)));</span>
Current_routine<span class="Delimiter">-></span>waiting_on_routine = ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">);</span>
trace<span class="Delimiter">(</span>Primitive_recipe_depth<span class="Delimiter">,</span> <span class="Constant">"run"</span><span class="Delimiter">)</span> << <span class="Constant">"waiting for routine "</span> << ingredients<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">).</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">);</span>
<span class="Identifier">break</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Delimiter">:(before "End Scheduler State Transitions")</span>
<span class="Comment">// Wake up any routines waiting for other routines to go to sleep.</span>
<span class="Comment">// Important: this must come after the scheduler loop above giving routines</span>
<span class="Comment">// waiting for locations to change a chance to wake up.</span>
for <span class="Delimiter">(</span>long long int i = <span class="Constant">0</span><span class="Delimiter">;</span> i < SIZE<span class="Delimiter">(</span>Routines<span class="Delimiter">);</span> ++i<span class="Delimiter">)</span> <span class="Delimiter">{</span>
if <span class="Delimiter">(</span>Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>state != WAITING<span class="Delimiter">)</span> <span class="Identifier">continue</span><span class="Delimiter">;</span>
if <span class="Delimiter">(</span>!Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>waiting_on_routine<span class="Delimiter">)</span> <span class="Identifier">continue</span><span class="Delimiter">;</span>
long long int id = Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>waiting_on_routine<span class="Delimiter">;</span>
assert<span class="Delimiter">(</span>id != Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>id<span class="Delimiter">);</span>
for <span class="Delimiter">(</span>long long int j = <span class="Constant">0</span><span class="Delimiter">;</span> j < SIZE<span class="Delimiter">(</span>Routines<span class="Delimiter">);</span> ++j<span class="Delimiter">)</span> <span class="Delimiter">{</span>
if <span class="Delimiter">(</span>Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>j<span class="Delimiter">)-></span>id == id && Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>j<span class="Delimiter">)-></span>state != RUNNING<span class="Delimiter">)</span> <span class="Delimiter">{</span>
trace<span class="Delimiter">(</span><span class="Constant">"schedule"</span><span class="Delimiter">)</span> << <span class="Constant">"waking up routine "</span> << Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>id<span class="Delimiter">;</span>
Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>state = RUNNING<span class="Delimiter">;</span>
Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>waiting_on_routine = <span class="Constant">0</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Delimiter">}</span>
<span class="Delimiter">}</span>
<span class="Delimiter">:(before "End Primitive Recipe Declarations")</span>
SWITCH<span class="Delimiter">,</span>
<span class="Delimiter">:(before "End Primitive Recipe Numbers")</span>
Recipe_number[<span class="Constant">"switch"</span>] = SWITCH<span class="Delimiter">;</span>
<span class="Delimiter">:(before "End Primitive Recipe Implementations")</span>
case SWITCH: <span class="Delimiter">{</span>
long long int id = some_other_running_routine<span class="Delimiter">();</span>
if <span class="Delimiter">(</span>id<span class="Delimiter">)</span> <span class="Delimiter">{</span>
assert<span class="Delimiter">(</span>id != Current_routine<span class="Delimiter">-></span>id<span class="Delimiter">);</span>
<span class="CommentedCode">//? cerr << "waiting on " << id << " from " << Current_routine->id << '\n'; //? 1</span>
Current_routine<span class="Delimiter">-></span>state = WAITING<span class="Delimiter">;</span>
Current_routine<span class="Delimiter">-></span>waiting_on_routine = id<span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Identifier">break</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Delimiter">:(code)</span>
long long int some_other_running_routine<span class="Delimiter">()</span> <span class="Delimiter">{</span>
for <span class="Delimiter">(</span>long long int i = <span class="Constant">0</span><span class="Delimiter">;</span> i < SIZE<span class="Delimiter">(</span>Routines<span class="Delimiter">);</span> ++i<span class="Delimiter">)</span> <span class="Delimiter">{</span>
if <span class="Delimiter">(</span>i == Current_routine_index<span class="Delimiter">)</span> <span class="Identifier">continue</span><span class="Delimiter">;</span>
assert<span class="Delimiter">(</span>Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)</span> != Current_routine<span class="Delimiter">);</span>
assert<span class="Delimiter">(</span>Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>id != Current_routine<span class="Delimiter">-></span>id<span class="Delimiter">);</span>
if <span class="Delimiter">(</span>Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>state == RUNNING<span class="Delimiter">)</span>
<span class="Identifier">return</span> Routines<span class="Delimiter">.</span>at<span class="Delimiter">(</span>i<span class="Delimiter">)-></span>id<span class="Delimiter">;</span>
<span class="Delimiter">}</span>
<span class="Identifier">return</span> <span class="Constant">0</span><span class="Delimiter">;</span>
<span class="Delimiter">}</span>
</pre>
</body>
</html>
<!-- vim: set foldmethod=manual : -->
|