author | wenzelm |
Thu, 20 Dec 2007 21:12:02 +0100 | |
changeset 25735 | 4d147263f71f |
parent 25704 | df9c8074ff09 |
child 25775 | 90525e67ede7 |
permissions | -rw-r--r-- |
23961 | 1 |
(* Title: Pure/ML-Systems/multithreading_polyml.ML |
2 |
ID: $Id$ |
|
3 |
Author: Makarius |
|
4 |
||
25704 | 5 |
Multithreading in Poly/ML 5.1 (cf. polyml/basis/Thread.sml). |
23961 | 6 |
*) |
7 |
||
8 |
open Thread; |
|
9 |
||
25704 | 10 |
signature MULTITHREADING_POLYML = |
11 |
sig |
|
12 |
val ignore_interrupt: ('a -> 'b) -> 'a -> 'b |
|
13 |
val raise_interrupt: ('a -> 'b) -> 'a -> 'b |
|
14 |
structure TimeLimit: TIME_LIMIT |
|
15 |
end; |
|
16 |
||
17 |
signature BASIC_MULTITHREADING = |
|
18 |
sig |
|
19 |
include BASIC_MULTITHREADING |
|
20 |
include MULTITHREADING_POLYML |
|
21 |
end; |
|
22 |
||
24208 | 23 |
signature MULTITHREADING = |
24 |
sig |
|
25 |
include MULTITHREADING |
|
25704 | 26 |
include MULTITHREADING_POLYML |
24208 | 27 |
end; |
28 |
||
23961 | 29 |
structure Multithreading: MULTITHREADING = |
30 |
struct |
|
31 |
||
24072
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
32 |
(* options *) |
24069 | 33 |
|
24119 | 34 |
val trace = ref 0; |
35 |
fun tracing level msg = |
|
36 |
if level <= ! trace |
|
23981 | 37 |
then (TextIO.output (TextIO.stdErr, (">>> " ^ msg () ^ "\n")); TextIO.flushOut TextIO.stdErr) |
38 |
else (); |
|
23961 | 39 |
|
23981 | 40 |
val available = true; |
23973 | 41 |
val max_threads = ref 1; |
42 |
||
43 |
||
24069 | 44 |
(* misc utils *) |
45 |
||
24208 | 46 |
fun cons x xs = x :: xs; |
24069 | 47 |
|
24208 | 48 |
fun change r f = r := f (! r); |
24069 | 49 |
|
50 |
fun inc i = (i := ! i + 1; ! i); |
|
51 |
fun dec i = (i := ! i - 1; ! i); |
|
52 |
||
24208 | 53 |
fun show "" = "" | show name = " " ^ name; |
54 |
fun show' "" = "" | show' name = " [" ^ name ^ "]"; |
|
55 |
||
56 |
||
57 |
(* thread attributes *) |
|
58 |
||
59 |
fun with_attributes new_atts f x = |
|
60 |
let |
|
61 |
val orig_atts = Thread.getAttributes (); |
|
62 |
fun restore () = Thread.setAttributes orig_atts; |
|
63 |
in |
|
64 |
Exn.release |
|
24214
0482ecc4ef11
(un)interruptible: pass-through original thread attributes;
wenzelm
parents:
24208
diff
changeset
|
65 |
(*RACE for fully asynchronous interrupts!*) |
0482ecc4ef11
(un)interruptible: pass-through original thread attributes;
wenzelm
parents:
24208
diff
changeset
|
66 |
(let |
24208 | 67 |
val _ = Thread.setAttributes new_atts; |
24214
0482ecc4ef11
(un)interruptible: pass-through original thread attributes;
wenzelm
parents:
24208
diff
changeset
|
68 |
val result = Exn.capture (f orig_atts) x; |
24208 | 69 |
val _ = restore (); |
70 |
in result end |
|
71 |
handle Interrupt => (restore (); Exn.Exn Interrupt)) |
|
72 |
end; |
|
73 |
||
24668 | 74 |
|
75 |
(* interrupt handling *) |
|
76 |
||
24297
a50cdc42798d
improved treatment of global interrupts: Thread.EnableBroadcastInterrupt, redefine ignore/raise_interrupt;
wenzelm
parents:
24291
diff
changeset
|
77 |
fun uninterruptible f x = with_attributes |
a50cdc42798d
improved treatment of global interrupts: Thread.EnableBroadcastInterrupt, redefine ignore/raise_interrupt;
wenzelm
parents:
24291
diff
changeset
|
78 |
[Thread.EnableBroadcastInterrupt false, Thread.InterruptState Thread.InterruptDefer] f x; |
24208 | 79 |
|
24297
a50cdc42798d
improved treatment of global interrupts: Thread.EnableBroadcastInterrupt, redefine ignore/raise_interrupt;
wenzelm
parents:
24291
diff
changeset
|
80 |
fun interruptible f x = with_attributes |
a50cdc42798d
improved treatment of global interrupts: Thread.EnableBroadcastInterrupt, redefine ignore/raise_interrupt;
wenzelm
parents:
24291
diff
changeset
|
81 |
[Thread.EnableBroadcastInterrupt true, Thread.InterruptState Thread.InterruptAsynchOnce] f x; |
24208 | 82 |
|
24668 | 83 |
fun ignore_interrupt f = uninterruptible (fn _ => f); |
84 |
fun raise_interrupt f = interruptible (fn _ => f); |
|
85 |
||
24688
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
86 |
|
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
87 |
(* execution with time limit *) |
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
88 |
|
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
89 |
structure TimeLimit = |
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
90 |
struct |
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
91 |
|
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
92 |
exception TimeOut; |
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
93 |
|
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
94 |
fun timeLimit time f x = |
24668 | 95 |
uninterruptible (fn atts => fn () => |
96 |
let |
|
97 |
val worker = Thread.self (); |
|
24688
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
98 |
val timeout = ref false; |
24668 | 99 |
val watchdog = Thread.fork (interruptible (fn _ => fn () => |
24688
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
100 |
(OS.Process.sleep time; timeout := true; Thread.interrupt worker)), []); |
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
101 |
|
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
102 |
(*RACE! timeout signal vs. external Interrupt*) |
24668 | 103 |
val result = Exn.capture (with_attributes atts (fn _ => f)) x; |
24688
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
104 |
val was_timeout = (case result of Exn.Exn Interrupt => ! timeout | _ => false); |
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
105 |
|
24668 | 106 |
val _ = Thread.interrupt watchdog handle Thread _ => (); |
24688
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
107 |
in if was_timeout then raise TimeOut else Exn.release result end) (); |
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
108 |
|
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
109 |
end; |
24668 | 110 |
|
24069 | 111 |
|
23961 | 112 |
(* critical section -- may be nested within the same thread *) |
113 |
||
114 |
local |
|
115 |
||
24063 | 116 |
val critical_lock = Mutex.mutex (); |
117 |
val critical_thread = ref (NONE: Thread.thread option); |
|
118 |
val critical_name = ref ""; |
|
119 |
||
23961 | 120 |
in |
121 |
||
122 |
fun self_critical () = |
|
123 |
(case ! critical_thread of |
|
124 |
NONE => false |
|
125 |
| SOME id => Thread.equal (id, Thread.self ())); |
|
126 |
||
23991 | 127 |
fun NAMED_CRITICAL name e = |
23961 | 128 |
if self_critical () then e () |
129 |
else |
|
24214
0482ecc4ef11
(un)interruptible: pass-through original thread attributes;
wenzelm
parents:
24208
diff
changeset
|
130 |
uninterruptible (fn atts => fn () => |
24208 | 131 |
let |
132 |
val name' = ! critical_name; |
|
133 |
val _ = |
|
134 |
if Mutex.trylock critical_lock then () |
|
135 |
else |
|
136 |
let |
|
137 |
val timer = Timer.startRealTimer (); |
|
138 |
val _ = tracing 4 (fn () => "CRITICAL" ^ show name ^ show' name' ^ ": waiting"); |
|
139 |
val _ = Mutex.lock critical_lock; |
|
140 |
val time = Timer.checkRealTimer timer; |
|
141 |
val _ = tracing (if Time.> (time, Time.fromMilliseconds 10) then 3 else 4) (fn () => |
|
142 |
"CRITICAL" ^ show name ^ show' name' ^ ": passed after " ^ Time.toString time); |
|
143 |
in () end; |
|
144 |
val _ = critical_thread := SOME (Thread.self ()); |
|
145 |
val _ = critical_name := name; |
|
24214
0482ecc4ef11
(un)interruptible: pass-through original thread attributes;
wenzelm
parents:
24208
diff
changeset
|
146 |
val result = Exn.capture (with_attributes atts (fn _ => e)) (); |
24208 | 147 |
val _ = critical_name := ""; |
148 |
val _ = critical_thread := NONE; |
|
149 |
val _ = Mutex.unlock critical_lock; |
|
150 |
in Exn.release result end) (); |
|
23961 | 151 |
|
23991 | 152 |
fun CRITICAL e = NAMED_CRITICAL "" e; |
23981 | 153 |
|
23961 | 154 |
end; |
155 |
||
23973 | 156 |
|
24208 | 157 |
(* scheduling -- multiple threads working on a queue of tasks *) |
158 |
||
159 |
datatype 'a task = |
|
160 |
Task of {body: unit -> unit, cont: 'a -> 'a, fail: 'a -> 'a} | Wait | Terminate; |
|
23973 | 161 |
|
24214
0482ecc4ef11
(un)interruptible: pass-through original thread attributes;
wenzelm
parents:
24208
diff
changeset
|
162 |
fun schedule n next_task = uninterruptible (fn _ => fn tasks => |
23973 | 163 |
let |
164 |
(*protected execution*) |
|
165 |
val lock = Mutex.mutex (); |
|
24672 | 166 |
val protected_name = ref ""; |
24063 | 167 |
fun PROTECTED name e = |
23973 | 168 |
let |
24144 | 169 |
val name' = ! protected_name; |
23981 | 170 |
val _ = |
171 |
if Mutex.trylock lock then () |
|
172 |
else |
|
24144 | 173 |
let |
174 |
val _ = tracing 2 (fn () => "PROTECTED" ^ show name ^ show' name' ^ ": waiting"); |
|
175 |
val _ = Mutex.lock lock; |
|
176 |
val _ = tracing 2 (fn () => "PROTECTED" ^ show name ^ show' name' ^ ": passed"); |
|
177 |
in () end; |
|
24069 | 178 |
val _ = protected_name := name; |
23973 | 179 |
val res = Exn.capture e (); |
24069 | 180 |
val _ = protected_name := ""; |
23973 | 181 |
val _ = Mutex.unlock lock; |
182 |
in Exn.release res end; |
|
183 |
||
24072
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
184 |
(*wakeup condition*) |
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
185 |
val wakeup = ConditionVar.conditionVar (); |
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
186 |
fun wakeup_all () = ConditionVar.broadcast wakeup; |
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
187 |
fun wait () = ConditionVar.wait (wakeup, lock); |
24291 | 188 |
fun wait_timeout () = ConditionVar.waitUntil (wakeup, lock, Time.now () + Time.fromSeconds 1); |
24072
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
189 |
|
24214
0482ecc4ef11
(un)interruptible: pass-through original thread attributes;
wenzelm
parents:
24208
diff
changeset
|
190 |
(*queue of tasks*) |
23973 | 191 |
val queue = ref tasks; |
24072
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
192 |
val active = ref 0; |
24119 | 193 |
fun trace_active () = tracing 1 (fn () => "SCHEDULE: " ^ Int.toString (! active) ^ " active"); |
24072
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
194 |
fun dequeue () = |
23973 | 195 |
let |
23981 | 196 |
val (next, tasks') = next_task (! queue); |
23973 | 197 |
val _ = queue := tasks'; |
24072
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
198 |
in |
24208 | 199 |
(case next of Wait => |
200 |
(dec active; trace_active (); |
|
201 |
wait (); |
|
202 |
inc active; trace_active (); |
|
203 |
dequeue ()) |
|
204 |
| _ => next) |
|
24072
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
205 |
end; |
23973 | 206 |
|
24208 | 207 |
(*pool of running threads*) |
23973 | 208 |
val status = ref ([]: exn list); |
24208 | 209 |
val running = ref ([]: Thread.thread list); |
210 |
fun start f = |
|
211 |
(inc active; |
|
212 |
change running (cons (Thread.fork (f, [Thread.InterruptState Thread.InterruptDefer])))); |
|
213 |
fun stop () = |
|
214 |
(dec active; |
|
215 |
change running (List.filter (fn t => not (Thread.equal (t, Thread.self ()))))); |
|
216 |
||
217 |
(*worker thread*) |
|
218 |
fun worker () = |
|
24072
8b9e5d776ef3
dequeue: wait loop while PROTECTED -- avoids race condition;
wenzelm
parents:
24069
diff
changeset
|
219 |
(case PROTECTED "dequeue" dequeue of |
24208 | 220 |
Task {body, cont, fail} => |
24214
0482ecc4ef11
(un)interruptible: pass-through original thread attributes;
wenzelm
parents:
24208
diff
changeset
|
221 |
(case Exn.capture (interruptible (fn _ => body)) () of |
24208 | 222 |
Exn.Result () => |
223 |
(PROTECTED "cont" (fn () => (change queue cont; wakeup_all ())); worker ()) |
|
23981 | 224 |
| Exn.Exn exn => |
24208 | 225 |
PROTECTED "fail" (fn () => |
226 |
(change status (cons exn); change queue fail; stop (); wakeup_all ()))) |
|
227 |
| Terminate => PROTECTED "terminate" (fn () => (stop (); wakeup_all ()))); |
|
23973 | 228 |
|
229 |
(*main control: fork and wait*) |
|
230 |
fun fork 0 = () |
|
24208 | 231 |
| fork k = (start worker; fork (k - 1)); |
24063 | 232 |
val _ = PROTECTED "main" (fn () => |
233 |
(fork (Int.max (n, 1)); |
|
24208 | 234 |
while not (List.null (! running)) do |
235 |
(trace_active (); |
|
236 |
if not (List.null (! status)) then (List.app Thread.interrupt (! running)) else (); |
|
24291 | 237 |
wait_timeout ()))); |
23973 | 238 |
|
24208 | 239 |
in ! status end); |
23973 | 240 |
|
25704 | 241 |
|
242 |
(* serial numbers *) |
|
243 |
||
244 |
local |
|
245 |
||
246 |
val serial_lock = Mutex.mutex (); |
|
247 |
val serial_count = ref 0; |
|
248 |
||
249 |
in |
|
250 |
||
251 |
val serial = uninterruptible (fn _ => fn () => |
|
252 |
let |
|
253 |
val _ = Mutex.lock serial_lock; |
|
254 |
val res = inc serial_count; |
|
255 |
val _ = Mutex.unlock serial_lock; |
|
256 |
in res end); |
|
257 |
||
23961 | 258 |
end; |
259 |
||
25735 | 260 |
|
261 |
(* thread data *) |
|
262 |
||
263 |
val get_data = Thread.getLocal; |
|
264 |
val put_data = Thread.setLocal; |
|
265 |
||
25704 | 266 |
end; |
24688
a5754ca5c510
replaced interrupt_timeout by TimeLimit.timeLimit (available on SML/NJ and Poly/ML 5.1);
wenzelm
parents:
24672
diff
changeset
|
267 |
|
25704 | 268 |
structure BasicMultithreading: BASIC_MULTITHREADING = Multithreading; |
269 |
open BasicMultithreading; |