CPSC 213 Introduction to Computer Systems
Winter Session 2020, Term 2
Unit 2b – Mar 22
Threads
Overview
‣ Reading • Text: 12.3
‣ Learning Goals
• Write C programs using threads
• Explain the execution of a multi-threaded program given the interleaved output of the threads
• Convert an event-driven C program into a procedure-driven using threads
• Identify the state of a thread
• Explain what happens when a thread is stopped and started by explaining what happens to the thread and what happens on the CPU that was executing it while the thread is stopped
• Describe the process of switching from one thread to another at the instruction level
• Explain the values for thread status and how threads transition from one status to another
• Identify the execution order of a set of threads of different priority using priority-based, round-robin scheduling
• List the benefits and drawbacks of priority-based round-robin scheduling without preemption
• Explain what preemption is, how it is incorporated into round-robin scheduling, and how it is implemented
• Compare real-time scheduling to round-robin scheduling to identify cases where each is useful
2
Issues Introduced by IO Devices
‣ Ordering of program events with IO completion
• diskRead triggers IO controller to start read process
• program has things that can only run after that process completes
‣ Do other things while waiting for IO event
• need multiple independent streams of execution in program • one does read and continues after it completes
• the other does something else in the meantime
‣ Asynchronous Programming • ORDER
– callback function that is called by completion interrupt
• MULTIPLE STREAMS
– one stream continues with return from diskRead WITHOUT the requested block
– the other starts with when the interrupt calls the completion callback function
3
Streams of Control in Asynchronous Program
Correctly ordered by procedure calls and callbacks
But, program order, doesn’t match “logical” order (green)
yetMore() yetAnotherCompletion()
diskISR()
somethingElse() diskRead() blah() main()
yetSomethingElse() diskRead() someOtherCallback()
computeSumAndCallback() diskISR()
blue are procedure calls
red are cause / effect of interrupts
green is logical control flow
What would change about this picture if we had an infinite number of CPUs?
4
Infinite CPUs: We can Poll the IO Device yetMore()
yetAnotherCompletion()
are you done yet? are you done yet? are you done yet? are you done yet? are you done yet?
diskRead() someOtherCallback() computeSumAndCallback()
are you done yet? are you done yet? are you done yet? are you done yet? are you done yet?
diskRead() blah() main()
yetSomethingElse()
somethingElse()
5
WAIT by POLLING WAIT by POLLING
The Virtual Processor
‣ Originated with Edsger Dijkstra in the THE Operating System • in The Structure of the “THE” Multiprogramming System, 1968
“I had had extensive experience (dating back to 1958) in making basic software dealing with real-time interrupts, and I knew by bitter experience that as a result of the irreproducibility of the interrupt moments a program error could present itself misleadingly like an occasional machine malfunctioning. As a result I was terribly afraid. Having fears regarding the possibility of debugging, we decided to be as careful as possible and, prevention being better than cure, to try to prevent nasty bugs from entering the construction.
This decision, inspired by fear, is at the bottom of what I regard as the group’s main contribution to the art of system design.”
‣ Thread (Dijkstra called it a Process)
• a single stream of synchronous execution of a program
– the illusion of a single system (as we assumed for the first part of the course)
• can be stopped and restarted (blocked and unblocked)
– stopped when waiting for an event (e.g., completion of an I/O operation) – restarted with the event fires
• can co-exist with other threads sharing a single CPU (or multiple CPUs)
– a scheduler multiplexes processes over processor
– synchronization primitives are used to ensure mutual exclusion and for waiting and signalling
6
Streams of Control in Asynchronous Program
Correctly ordered by procedure calls and callbacks
But, program order, doesn’t match “logical” order (green)
yetMore() yetAnotherCompletion()
diskISR()
somethingElse() diskRead() blah() main()
yetSomethingElse()
diskRead() someOtherCallback()
computeSumAndCallback() diskISR()
blue are procedure calls
red are cause / effect of interrupts
green is logical control flow
7
Connecting Program- and Logical-Order with Threads
Threads STOP and START (BLOCK and UNBLOCK)
The CPU switches from one thread to another
yetMore() yetAnotherCompletion()
UNBLOCK
yetSomethingElse()
FINISH or YIELD
diskRead() someOtherCallback() computeSumAndCallback()
BLOCK UNBLOCK
START
somethingElse()
FINISH or YIELD
START
diskRead() blah() main()
BLOCK START
8
UThread: A Simple Thread System for C ‣ The UThread Interface file (uthread.h)
void uthread_init (int num_processors);
uthread_t uthread_create (void* (*proc)(void*), void* arg);
void uthread_detach (uthread_t t);
int uthread_join (uthread_t t, void** vp);
uthread_t uthread_self ();
void uthread_yield ();
void uthread_block ();
void uthread_unblock (uthread_t thread);
‣ Explained • uthread_t
• uthread_init
• uthread_create • uthread_yield
• uthread_join
• uthread_detach • uthread_self
• uthread_block
• uthread_unblock
thread id data type
is called once to initialize the thread system
create and start a thread to run specified procedure
temporarily stop current thread if other threads waiting
join calling thread with specified other thread and get return value indicate thread no thread will join specified thread
a pointer to the TCB of the current thread
block current thread
unblock specified thread and make it runnable
9
Start, Stop and Join
‣ Create / Start
‣ forks the control stream
‣ like an asynchronous procedure call
t = uthread_create(foo, NULL);
‣ Join
‣ joining blocks caller until target has finished ‣ join returns result of call that created thread
uthread_join(t, void** rtnValuePtr);
**rtnValuePtr is return value of foo()
‣ Block / Unblock
‣ stop and restart a thread (so that it can wait)
uthread_block(); stop calling thread until it is unblocked
uthread_unblock(t);
restart thread t
10
Assuming Threads can Run in Parallel
main “calls” foo by creating a thread
foo starts
blocks
restarts
unblock (t)
join(t) and block if foo hasn’t finished
restarts
finish/return
unblocks main
Example Program using UThreads
void* ping (void* v) {
int i;
for (i=0; i<100; i++) {
printf ("I"); fflush(stdout);
uthread_yield();
}
return 0; }
void* pong (void* v) {
int i;
give up CPU if there’s another thread that can run (i.e., pong())
for (i=0; i<100; i++) {
printf ("O"); fflush(stdout);
uthread_yield();
}
return 0; }
void ping_pong () {
uthread_t t0, t1;
uthread_init (1);
t0 = uthread_create (ping, 0);
t1 = uthread_create (pong, 0);
uthread_join (t0, 0);
uthread_join (t1, 0);
}
give up CPU if there’s another thread that can run (i.e., ping())
give up CPU to wait for ping() to return and thus its thread to finish
11
Diagram the execution on 1 CPU and on 2 ...
Question 2b.1
‣ The main function creates two threads: foo and bar. Then, while both are running, suppose foo calls uthread_join(bar, NULL). What happens?
A. bar is blocked until foo completes
B. foo is blocked until bar completes
C. main is blocked until bar completes
D. main is blocked until both foo and bar complete E. bar is forced to stop immediately
12
Revisiting the Disk Read
‣ A program that reads a block from disk • want the disk read to be synchronous
read (buf, siz, blkNo); // read siz bytes at blkNo into buf nowHaveBlock (buf, siz); // now do something with the block
• but, it is asynchronous so we have this
asyncRead (buf, siz, blkNo, nowHaveBlock); doSomethingElse ();
‣ As a timeline
• two processors
• two separate computations
asyncRead
CPU
disk controller
do something else while waiting
nowHaveBlock
perform disk read
13
Synchronous Disk Read using Threads
x block √ unblock asyncRead do something else while waiting nowHaveBlock
‣ Create two threads that CPU runs, one at a time • one for disk read
• one for doSomethingElse
‣ Illusion of synchrony
• disk read blocks while waiting for disk to complete
• CPU runs other thread(s) while first thread is blocked • disk interrupt restarts the blocked read
interruptHandler() { unblockWaitingThread();
}
asyncRead (buf, siz, blkNo); blockToWaitForInterrupt (); nowHaveBlock (buf, siz);
14
Recall Asynchronous Disk read
We wanted to do this, but couldn’t because disk reads are asynchronous...
void foo () {
int sumDiskBlock (int aBlkNo) {
char buf [4096];
int sum;
diskRead (buf, 4096, aBlkNo);
for (int i=0; i<4096; i++)
sum += buf [i];
return sum; }
}
printf (“%d\n”, sumDiskBlock (1234));
We implemented it this way in event-driven programming style...
void foo () {
readDiskBlock (1234, printSum);
}
void printSum (char* buf, int n) {
printf ("%d\n", calcSum (buf, n));
}
int calcSum (char* buf, int n) {
int sum=0, i;
for (i=0; i