ECE 391 / DISCUSSION 5
Threads
Condition Variables
Thread Test Case Walkthrough
MP2 CP3
The Thread Manager’s Data Model
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
02
A thread is a saved execution context plus the state needed to schedule it
READY threads
ready_list
head
A
B
idle
WAITING threads
cv.wait_list
head
C
D
linked through list_next
Remember that threads can only be part of 1 list at a time
What Lives in struct thread?
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
03
The release struct, grouped by purpose
Fields | Purpose |
ctx | Saved s0–s11, ra, and sp. Must be the first member. |
id, state, name | Thread-table index, scheduling state, and debug name. |
stack_anchor, stack_lowest | Stack boundary and allocation base for later reclamation. |
parent | The thread that spawned this one. |
list_next | Links this thread into the ready list or a condition wait list. |
wait_cond, child_exit | Current wait target and this thread’s child-exit condition. |
Inside ctx
s[12] ra sp
Inside stack_anchor
ktp kgp
Spawning and First Execution
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
04
A new thread needs a valid first context before the scheduler can run it
spawn_thread() establishes
A TID, stack, and parent
An initialized child_exit condition
A starting context and entry arguments
READY state and puts new thr on ready list
The first context
First schedule
switch_running_thread
finish_thread_switch
start_thread
entry(...)
spawn_thread() returns to its caller. The child runs when scheduled.
We have 12 + 2 “free” entries to store
Thread States and Queue Membership
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
05
State and queue membership must agree at scheduling boundaries
State | Where is the thread? | How can it progress? |
RUNNING | Current thread in tp | Yield, wait, or exit |
READY | ready_list | Scheduler selects it |
WAITING | A condition’s wait_list | Another thread’s broadcast makes it READY |
EXITED | N/A memory is freed | N/A |
Yield
Still eligible to run again
Wait
Blocked until someone broadcasts
What Does a Condition Variable Contain?
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
06
A condition object identifies a notification and keeps track of its current waiters
struct condition {
const char *name;
struct thread_list wait_list;
};
struct thread_list {
struct thread *head;
struct thread *tail;
};
A queue of sleeping threads
head
W1
W2
W1.list_next = &W2
tail = &W2
Callers use the condition API. thread.c manages these fields.
The condition holds the threads waiting for a notification.
Who Owns a Condition Variable?
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
07
Storage lifetime, waiting, and broadcasting are separate responsibilities
Where the object lives | Who provides its storage? | When is the pointer valid? |
static struct condition uart_cv; | Uart device struct | For the program’s lifetime |
Local test_cond in run() | The caller’s stack frame | While that frame remains alive |
P.child_exit | Parent P’s thread struct | While P’s struct remains allocated |
Users share a pointer
A thread can wait on the object.
Another thread or an ISR can broadcast it.
No exclusive owner
like a lock
A Simple Shared-Condition Example
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
09
The worker waits for ready. Main changes ready and announces the change.
struct event {
int ready;
struct condition changed;
};
Main creates e with ready = 0, initializes
e.changed, and passes &e to worker.
Worker
Main
int pie = disable_interrupts();
while (!e->ready) // the predicate
condition_wait(&e->changed); // the notification
restore_interrupts(pie);
// Continue with the work.
int pie = disable_interrupts();
e.ready = 1; // the durable fact
condition_broadcast(&e.changed); // notify
restore_interrupts(pie);
// The worker rechecks e.ready when it wakes.
Both threads use the same e.changed object. Main keeps e alive until worker exits.
wait_cond and child_exit
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
08
wait_cond points to a condition object. child_exit is a condition object inside the thread.
struct condition *wait_cond;
struct condition child_exit;
Thread W1
wait_cond = &shared
child_exit [object]
Thread W2
wait_cond = &shared
child_exit [object]
shared [condition object]
wait_list: [W1] [W2]
W1 and W2 wait on the same object. Their own child_exit objects are separate.
Which child_exit Does the Parent Wait On?
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
13
P spawned C. P now calls join_thread(C.id), and C has not exited.
Parent P
state = RUNNING
children = { C }
wait_cond = ?
P.child_exit [condition struct]
Child C
state = READY
parent = &P
wait_cond = NULL
C.child_exit [condition struct]
?
Does P wait on &P.child_exit or &C.child_exit?
Which object will C broadcast when it exits?
Join and Exit Use the Parent’s child_exit
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
14
The same object appears on both sides of the interaction
P waits: condition_wait(&P.child_exit);
C broadcasts: condition_broadcast(&C.parent->child_exit);
C.parent == &P so both addresses identify P.child_exit
Step | Parent P | Child C |
1. P joins C | WAITING on P.child_exit | Still able to run |
2. C exits | READY after C’s broadcast | EXITED, then switches away |
3. P resumes | Rechecks C.state, then joins C | Remaining record reclaimed |
While P sleeps: P.wait_cond = &P.child_exit P.child_exit.wait_list: [P]
P.child_exit means “a child of P exited.” P rechecks which child exited.
Thread Test Case Overview: Cont’
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
16
One waiter, two broadcasters, one bystander. All three children of main
One condition, two users
struct condition
test_cond;
_test_thrfn waits on &test_cond
_broadcast_test broadcasts &test_cond
Loop counts
#define WAIT_ITER 5
#define BROADCAST_ITER 4
#define RAND_ITER 10
#define THREAD_YIELD_ITER 100
Main Thread (0)
Thread (1)
Thread (3)
Thread (2)
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
idle omitted throughout: it is always skipped while another thread is ready
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 1 of 72 main: condition_init(&test_cond, "test_cond")
about to initialise test_cond with an empty wait list
main
[ empty ]
[ empty ]
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 2 of 72 main: spawn_thread("test1", ...) -> tid 1
about to create test1 and put it on ready_list
main
[ empty ]
[ empty ]
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 3 of 72 main: running_thread_yield()
main will go to the back of ready_list; test1 runs next
main
[ empty ]
[ test1 ]
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 4 of 72 test1: kprintf("... is waiting ...")
wait 1 of 5 -- test1 prints BEFORE it blocks
test1
[ empty ]
[ main ]
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 5 of 72 test1: condition_wait(test_cond)
test1 will go WAITING with wait_cond = &test_cond
test1
[ empty ]
[ main ]
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 6 of 72 main: condition_broadcast(&test_cond)
will move every waiter to the BACK of ready_list, without switching
main
[ test1 ]
[ empty ]
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 7 of 72 main: kprintf("Broadcasted condition %s\n", ...)
notification 1 of 5
main
[ empty ]
[ test1 ]
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 8 of 72 main: running_thread_yield()
main
[ empty ]
[ test1 ]
Thread test1 is waiting on condition test_cond
Broadcasted condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 9 of 72 test1: kprintf("... has been signaled ...")
test1 has just returned from condition_wait
test1
[ empty ]
[ main ]
Thread test1 is waiting on condition test_cond
Broadcasted condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 10 of 72 test1: kprintf("... is waiting ...")
wait 2 of 5 -- test1 prints BEFORE it blocks
test1
[ empty ]
[ main ]
Thread test1 is waiting on condition test_cond
Broadcasted condition test_cond
Thread test1 has been signaled on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 11 of 72 test1: condition_wait(test_cond)
test1 will go WAITING with wait_cond = &test_cond
test1
[ empty ]
[ main ]
Thread test1 is waiting on condition test_cond
Broadcasted condition test_cond
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 12 of 72 main: spawn_thread("random", ...) -> tid 2
about to create random
main
[ test1 ]
[ empty ]
Thread test1 is waiting on condition test_cond
Broadcasted condition test_cond
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 13 of 72 main: running_thread_yield()
main
[ test1 ]
[ random ]
Thread test1 is waiting on condition test_cond
Broadcasted condition test_cond
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 14 of 72 random: kprintf("... is running ...")
iteration 1 of 10
random
[ test1 ]
[ main ]
Thread test1 is waiting on condition test_cond
Broadcasted condition test_cond
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 15 of 72 random: running_thread_yield()
random
[ test1 ]
[ main ]
Broadcasted condition test_cond
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 16 of 72 main: spawn_thread("test2", ...) -> tid 3
about to create test2
main
[ test1 ]
[ random ]
Broadcasted condition test_cond
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 17 of 72 main: running_thread_yield()
main
[ test1 ]
[ random, test2 ]
Broadcasted condition test_cond
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 18 of 72 random: kprintf("... is running ...")
iteration 2 of 10
random
[ test1 ]
[ test2, main ]
Broadcasted condition test_cond
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 19 of 72 random: running_thread_yield()
random
[ test1 ]
[ test2, main ]
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Thread random is running
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 20 of 72 test2: kprintf("Broadcasting condition %s\n", ...)
test2 prints BEFORE it broadcasts
test2
[ test1 ]
[ main, random ]
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Thread random is running
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 21 of 72 test2: condition_broadcast(test_cond)
notification 2 of 5
test2
[ test1 ]
[ main, random ]
Thread test1 is waiting on condition test_cond
Thread random is running
Thread random is running
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 22 of 72 test2: running_thread_yield()
this yield is what lets test1 re-enter its wait in time
test2
[ empty ]
[ main, random, test1 ]
Thread test1 is waiting on condition test_cond
Thread random is running
Thread random is running
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 23 of 72 main: running_thread_yield() [loop 1 of 100]
main
[ empty ]
[ random, test1, test2 ]
Thread test1 is waiting on condition test_cond
Thread random is running
Thread random is running
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 24 of 72 random: kprintf("... is running ...")
iteration 3 of 10
random
[ empty ]
[ test1, test2, main ]
Thread test1 is waiting on condition test_cond
Thread random is running
Thread random is running
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 25 of 72 random: running_thread_yield()
random
[ empty ]
[ test1, test2, main ]
Thread random is running
Thread random is running
Broadcasting condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 26 of 72 test1: kprintf("... has been signaled ...")
test1 has just returned from condition_wait
test1
[ empty ]
[ test2, main, random ]
Thread random is running
Thread random is running
Broadcasting condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 27 of 72 test1: kprintf("... is waiting ...")
wait 3 of 5 -- test1 prints BEFORE it blocks
test1
[ empty ]
[ test2, main, random ]
Thread random is running
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 28 of 72 test1: condition_wait(test_cond)
test1 will go WAITING with wait_cond = &test_cond
test1
[ empty ]
[ test2, main, random ]
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 29 of 72 test2: kprintf("Broadcasting condition %s\n", ...)
test2 prints BEFORE it broadcasts
test2
[ test1 ]
[ main, random ]
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 30 of 72 test2: condition_broadcast(test_cond)
notification 3 of 5
test2
[ test1 ]
[ main, random ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 31 of 72 test2: running_thread_yield()
this yield is what lets test1 re-enter its wait in time
test2
[ empty ]
[ main, random, test1 ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 32 of 72 main: running_thread_yield() [loop 2 of 100]
main
[ empty ]
[ random, test1, test2 ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 33 of 72 random: kprintf("... is running ...")
iteration 4 of 10
random
[ empty ]
[ test1, test2, main ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 34 of 72 random: running_thread_yield()
random
[ empty ]
[ test1, test2, main ]
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 35 of 72 test1: kprintf("... has been signaled ...")
test1 has just returned from condition_wait
test1
[ empty ]
[ test2, main, random ]
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 36 of 72 test1: kprintf("... is waiting ...")
wait 4 of 5 -- test1 prints BEFORE it blocks
test1
[ empty ]
[ test2, main, random ]
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 37 of 72 test1: condition_wait(test_cond)
test1 will go WAITING with wait_cond = &test_cond
test1
[ empty ]
[ test2, main, random ]
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 38 of 72 test2: kprintf("Broadcasting condition %s\n", ...)
test2 prints BEFORE it broadcasts
test2
[ test1 ]
[ main, random ]
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 39 of 72 test2: condition_broadcast(test_cond)
notification 4 of 5
test2
[ test1 ]
[ main, random ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 40 of 72 test2: running_thread_yield()
this yield is what lets test1 re-enter its wait in time
test2
[ empty ]
[ main, random, test1 ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 41 of 72 main: running_thread_yield() [loop 3 of 100]
main
[ empty ]
[ random, test1, test2 ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 42 of 72 random: kprintf("... is running ...")
iteration 5 of 10
random
[ empty ]
[ test1, test2, main ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 43 of 72 random: running_thread_yield()
random
[ empty ]
[ test1, test2, main ]
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 44 of 72 test1: kprintf("... has been signaled ...")
test1 has just returned from condition_wait
test1
[ empty ]
[ test2, main, random ]
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 45 of 72 test1: kprintf("... is waiting ...")
wait 5 of 5 -- test1 prints BEFORE it blocks
test1
[ empty ]
[ test2, main, random ]
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 46 of 72 test1: condition_wait(test_cond)
test1 will go WAITING with wait_cond = &test_cond
test1
[ empty ]
[ test2, main, random ]
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 47 of 72 test2: kprintf("Broadcasting condition %s\n", ...)
test2 prints BEFORE it broadcasts
test2
[ test1 ]
[ main, random ]
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 48 of 72 test2: condition_broadcast(test_cond)
notification 5 of 5
test2
[ test1 ]
[ main, random ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 49 of 72 test2: running_thread_yield()
this yield is what lets test1 re-enter its wait in time
test2
[ empty ]
[ main, random, test1 ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 50 of 72 main: running_thread_yield() [loop 4 of 100]
main
[ empty ]
[ random, test1, test2 ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 51 of 72 random: kprintf("... is running ...")
iteration 6 of 10
random
[ empty ]
[ test1, test2, main ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 52 of 72 random: running_thread_yield()
random
[ empty ]
[ test1, test2, main ]
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 53 of 72 test1: kprintf("... has been signaled ...")
test1 has just returned from condition_wait
test1
[ empty ]
[ test2, main, random ]
Thread test1 has been signaled on condition test_cond
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 54 of 72 test1: return -> exit_running_thread()
test1 has finished all 5 waits and is about to exit
test1
[ empty ]
[ test2, main, random ]
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
[ none ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 55 of 72 test2: return -> exit_running_thread()
test2 has issued all 4 broadcasts and is about to exit
test2
[ empty ]
[ main, random ]
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
[ test1 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 56 of 72 main: running_thread_yield() [loop 5 of 100]
main
[ empty ]
[ random ]
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 57 of 72 random: kprintf("... is running ...")
iteration 7 of 10
random
[ empty ]
[ main ]
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 58 of 72 random: running_thread_yield()
random
[ empty ]
[ main ]
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 59 of 72 main: running_thread_yield() [loop 6 of 100]
main
[ empty ]
[ random ]
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 60 of 72 random: kprintf("... is running ...")
iteration 8 of 10
random
[ empty ]
[ main ]
Broadcasting condition test_cond
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 61 of 72 random: running_thread_yield()
random
[ empty ]
[ main ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread random is running
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 62 of 72 main: running_thread_yield() [loop 7 of 100]
main
[ empty ]
[ random ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread random is running
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 63 of 72 random: kprintf("... is running ...")
iteration 9 of 10
random
[ empty ]
[ main ]
Thread random is running
Thread test1 has been signaled on condition test_cond
Thread random is running
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 64 of 72 random: running_thread_yield()
random
[ empty ]
[ main ]
Thread test1 has been signaled on condition test_cond
Thread random is running
Thread random is running
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 65 of 72 main: running_thread_yield() [loop 8 of 100]
main
[ empty ]
[ random ]
Thread test1 has been signaled on condition test_cond
Thread random is running
Thread random is running
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 66 of 72 random: kprintf("... is running ...")
iteration 10 of 10
random
[ empty ]
[ main ]
Thread test1 has been signaled on condition test_cond
Thread random is running
Thread random is running
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 67 of 72 random: running_thread_yield()
random
[ empty ]
[ main ]
Thread random is running
Thread random is running
Thread random is running
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 68 of 72 main: running_thread_yield() [loop 9 of 100]
main
[ empty ]
[ random ]
Thread random is running
Thread random is running
Thread random is running
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 69 of 72 random: return -> exit_running_thread()
random has printed 10 times and is about to exit
random
[ empty ]
[ main ]
Thread random is running
Thread random is running
Thread random is running
Thread random is running
[ test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 70 of 72 main: running_thread_yield() [remaining loop iterations]
no other thread is runnable; main simply spins through the rest
main
[ empty ]
[ empty ]
Thread random is running
Thread random is running
Thread random is running
Thread random is running
[ random, test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 71 of 72 main: thread_join(0)
a child has already EXITED, so join will return without waiting
main
[ empty ]
[ empty ]
Thread random is running
Thread random is running
Thread random is running
Thread random is running
[ random, test1, test2 ]
Thread Test Case Overview
GRAINGER ENGINEERING
16
ready_list:
Printed output:
Active thread:
wait list:
exited:
Step 72 of 72 main: run() returns
the test is over
main
[ empty ]
[ empty ]
Thread random is running
Thread random is running
Thread random is running
Thread random is running
[ random, test1, test2 ]
The Full Expected Transcript
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
23
Twenty lines: 1 from main, 5 from test1, 4 from test2, 10 from random
Thread test1 is waiting on condition test_cond
Broadcasted condition test_cond
Thread test1 is waiting on condition test_cond
Thread random is running
Thread random is running
Broadcasting condition test_cond
Thread random is running
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
Thread test1 is waiting on condition test_cond
Broadcasting condition test_cond
Thread random is running
Thread random is running
Thread random is running
Thread random is running
Thread random is running
Who printed what
main
Broadcasted condition test_cond
x 1
test1
Thread test1 is waiting on ...
x 5
test2
Broadcasting condition test_cond
x 4
random
Thread random is running
x 10
The Final Join Uses a Different Condition
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
25
test_cond coordinates the test. main.child_exit is how join_thread() waits.
main.child_exit — the join notification
Lives in struct thread main (embedded)
Waits on it main, inside join_thread()
Broadcasts it each child as it exits
Means “a child of main exited”
What join_thread(0) actually guarantees
It loops until some child exits, then unblocks.
Or exits immediately if one of its children have already finished
A stronger harness joins testtid1, randomtid and testtid2 before test_cond goes out of scope.
Useful Extra Tests
ELECTRICAL & COMPUTER ENGINEERING
GRAINGER ENGINEERING
26
Two waiters on the same condition
Broadcast with an empty wait list, then add a predicate
Explicit joins for every spawned child
Invalid and non-child joins
Break on condition_wait,
condition_broadcast,
yield_running_thread,
join_thread.