3_Threads

1 .Threads 1 Lecture 3: Threads Learning Goals Describe what a thread is in your own words Describe the role of the Operating System kernel in thread creation Create and use threads in C++ using the C++11 standard std::thread class Describe two methods of thread communication and give a code example Define a race condition and give an example Given code that runs in parallel, identify all possible sequences and outputs Given an application, identify where it might be useful to use separate threads List potential drawbacks or limitations of multiple threads © Paul Davies, C. Antonio Sanchez. Not to be copied, used, or revised without explicit written permission from the copyright owner.

2 .Single-Task vs Multi-Task Threads 2 Single Tasking: a single program (thread) that runs sequentially #include <iostream> int main() { for ( int i= 0 ; i< 10 ; ++i) { std::cout << i << std::endl; } return 0 ; } 55 push %rbp 48 89 e5 mov %rsp,%rbp 48 83 ec 10 sub $0x10,%rsp c7 45 fc 00 00 00 00 movl $0x0,-0x4(%rbp) 83 7d fc 09 cmpl $0x9,-0x4(%rbp) 7f 22 jg 40084d <main+0x37> 8b 45 fc mov -0x4(%rbp),%eax 89 c6 mov %eax,%esi bf 60 10 60 00 mov $0x601060,%edi e8 66 fe ff ff callq be 00 07 40 00 mov $0x400700,%esi 48 89 c7 mov %rax,%rdi e8 a9 fe ff ff callq 4006f0 83 45 fc 01 addl $0x1,-0x4(%rbp) eb d8 jmp 400825 <main+0xf> b8 00 00 00 00 mov $0x0,%eax c9 leaveq c3 retq 55 48 89 e5 48 83 ec 10 c7 45 fc

3 .Single-Task vs Multi-Task Threads 3 Multi Tasking: sections of code can be executed in parallel #include <thread> #include <vector> #include <iostream> void thread_fn( int idx) { std ::cout << "hello thread " << idx << std ::endl; } int main() { std :: vector < std :: thread > threads; for ( int i= 0 ; i< 4 ; ++i) { threads.push_back( std ::thread(thread_fn, i) ); } // wait for all threads to finish for ( auto & thread : threads) { thread.join(); } return 0 ; } thread_fn(0) thread_fn(1) thread_fn(2) thread_fn(3)

4 .What is an Operating System Kernel? A kernel is the heart of an operating system , consists of a collection of applications, services and software system calls that implement Creating processes/threads Mutual exclusion, Process communication, Process synchronisation, Sharing memory, Scheduling and prioritization of processes, Handling the GUI (windows, mouse, keyboard etc.) Dealing with files & directories, networks etc. A kernel provides a set of services and system calls to the host programs that we can access. Threads 4

5 .Creating a Thread (Windows) Threads 5 #include <windows.h> #include <iostream> struct ThreadData { int idx ; }; DWORD WINAPI MyThreadFunction( LPVOID lpParam ) { ThreadData * data = ( ThreadData *)lpParam; std ::cout << "hello thread " << data-> idx << std ::endl; } int main() { const int MAX_THREADS = 4 ; HANDLE threads[MAX_THREADS]; // store thread handles DWORD thread_ids[MAX_THREADS]; // store thread IDs ThreadData data[MAX_THREADS]; // data to pass to thread for ( int i= 0 ; i<MAX_THREADS; ++i) { data[i]. idx = i; // set data // create actual thread threads[i] = CreateThread( NULL , // security attributes 0 , // stack size MyThreadFunction, // function to be executed &data[i], // pointer to a input 0 , // flags that control startup &thread_ids[i] // ouput, receives identifier ); } // wait for threads to finish WaitForMultipleObjects(MAX_THREADS, threads, TRUE , INFINITE ); // close all threads for ( int i= 0 ; i<MAX_THREADS; ++i) { CloseHandle(threads[i]); } return 0 ; }

6 .Creating a Thread (OSX or Linux) Threads 6 #include <iostream> #include <pthread.h> struct ThreadData { int idx ; }; void * MyThreadFunction( void * in ) { ThreadData * data = ( ThreadData *)in; std ::cout << "hello thread " << data-> idx << std ::endl; return NULL ; } int main() { const int MAX_THREADS = 4 ; pthread_t threads[MAX_THREADS]; ThreadData data[MAX_THREADS]; // data to pass to thread for ( int i= 0 ; i<MAX_THREADS; ++i) { data[i]. idx = i; // set data int success = pthread_create( &threads[i], // thread handle NULL , // attributes MyThreadFunction, // function ( void *) &data[i]); // input } // wait for threads to finish for ( int i= 0 ; i<MAX_THREADS; ++i) { pthread_join( threads[i], NULL ); } return 0 ; }

7 .Threads 7 OS Kernel e.g. W indows, Linux , OSX + Multi Core CPU void Thread1 () { Statement A Statement B } void Thread2 () { Statement C Statement D } void Thread3 () { Statement E Statement F } int main () { CreateThread( Thread1 ) ; CreateThread( Thread2 ) ; CreateThread( Thread3 ) ; } Program begins here Three calls to the OS Kernel requesting it to create and schedule 3 threads Scheduling The main () method calls the OS kernel to create 3 threads . The OS schedules them using time slicing if only 1 CPU or core is present, or designates them to run in parallel if more than 1 CPU or core is present, or some combination. The operating system can then perform load balancing to distribute the work as fairly as possible.

8 .Library Abstractions Threads 8 Calling OS kernel functions explicitly is undesirable. It ties our programs to a specific OS, making our code less portable . Some of the details can be abstracted away, wrapped in a library that provides a consistent interface . Many multi-threading capabilities, including inter-thread communication, are now part of the ISO standard C++11 and higher. For features that are not part of the standard, a CPEN333-specific library is provided. https://github.com/cpen333/library

9 .Threads 9 OS Kernel e.g. W indows, Linux , OSX + Multi Core CPU void Thread1 () { Statement A Statement B } void Thread2 () { Statement C Statement D } void Thread3 () { Statement E Statement F } int main () { CreateThread( Thread1 ) ; CreateThread( Thread2 ) ; CreateThread( Thread3 ) ; } Program begins here Scheduling C++11 Standard or CPEN333 Library Translation Layer Library Abstractions

10 .Creating a Thread (C++11 Standard) Threads 10 thread(function , arg0, arg1, ...): constructor taking function and optional args will call function(arg0, arg1, ...) join(): wait for thread to complete detach(): allow thread to continue running when current process terminates Note: if arguments are passed by-reference, they need to be wrapped in a std::ref(…) . Note2: avoid passing in overloaded functions (same name, different parameters), you may get template deduction failures.

11 .Creating a Thread (C++11 Standard) Threads 11 #include <iostream> #include <thread> struct ThreadData { int idx ; }; void MyThreadFunction( ThreadData * data ) { std ::cout << "hello thread " << data-> idx << std ::endl; } int main() { const int MAX_THREADS = 4 ; std :: thread * threads[MAX_THREADS]; ThreadData data[MAX_THREADS]; // data to pass to thread for ( int i= 0 ; i<MAX_THREADS; ++i) { data[i]. idx = i; // set data threads[i] = new std ::thread( MyThreadFunction, // function &data[i] // optional argument(s) ); } // wait for threads to finish for ( int i= 0 ; i<MAX_THREADS; ++i) { threads[i]->join(); delete threads[i]; // clean-up memory threads[i] = nullptr ; } return 0 ; }

12 .Creating a Thread (C++11 Standard) Threads 12 #include <iostream> #include <thread> struct ThreadData { int idx ; }; void MyThreadFunction( const ThreadData & data ) { std ::cout << "hello thread " << data. idx << std ::endl; } int main() { const int MAX_THREADS = 4 ; std :: thread * threads[MAX_THREADS]; ThreadData data[MAX_THREADS]; // data to pass to thread for ( int i= 0 ; i<MAX_THREADS; ++i) { data[i]. idx = i; // set data threads[i] = new std ::thread( MyThreadFunction, // function std ::ref(data[i]) // by-reference argument ); } // wait for threads to finish for ( int i= 0 ; i<MAX_THREADS; ++i) { threads[i]->join(); delete threads[i]; // clean-up memory threads[i] = nullptr ; } return 0 ; } by reference by reference

13 .C++11 Standard Threads Threads 13 Can use any Callable (function, class/struct with bracket-operator, lambda) with any number of arguments Automatically start running on construction Make sure to either detach or join the thread before program ends See q1_threads/basics in course library for examples

14 .Object-Oriented Threads Threads 14 We can create our own thread class that augments std::thread Add new methods for passing messages, etc… The course library introduces a thread_object class class thread_object { public : thread_object(); // constructor, DOES NOT START THREAD void start(); // start thread int join(); // wait for thread to complete, return result void detach(); // detach thread bool terminated(); // checks if thread has terminated protected : virtual int main() = 0 ; // method to override, // called automatically when thread starts, // returns a result };

15 .Object-Oriented Threads Threads 15 #include <iostream > #include <chrono> // thread-based object #include "cpen333/thread/thread_object.h " class CustomThread : public cpen333 :: thread :: thread_object { private : // Override "main" method int main() { for ( int i = 0 ; i < 30 ; ++i) { std ::cout << "I am a CustomThread object” << std ::endl; std :: this_thread ::sleep_for( std :: chrono :: milliseconds ( 200 )); } return 0 ; } }; int main() { // create instance of thread object CustomThread object1, object2, object3; object1.start(); object2.start(); object3.start(); // wait for 2 seconds std :: this_thread ::sleep_for( std :: chrono :: seconds ( 2 )); // wait for everyone to finish int o1 = object1.join() ; std ::cout << "object 1 finished with: " << o1 << std ::endl; int o2 = object2.join() ; std ::cout << "object 2 finished with: " << o2 << std ::endl; int o3 = object3.join() ; std ::cout << "object 3 finished with: " << o3 << std ::endl; return 0 ; }

16 .Thread Granularity Threads 16 Granularity is used to describe the degree of parallelism that exists inside a system . A program (process) could be broken down into a number of parallel executing threads , each representing a traceable path of sequential programming Threads allow a single application to be run on multiple cores within the hardware. In theory we could decompose our system into finer and finer units until almost everything runs in parallel. Designing too much parallelism leads to increases in data dependencies reducing the amount of real world parallelism taking place.

17 .Communication and Synchronization Problems Threads 17 17 Thread Thread Thread Thread Thread Thread Process/Thread Process/Thread Process/Thread Process/Thread Process/Thread Process/Thread Communication Problems Synchronisation Problems More threads more problems. Communication and synchronization issues grow exponentially, scattering data leads to more data dependencies , slowing the system down, leading to data management challenges.

18 .Thread Communication Threads 18 Threads within a single program can share memory Global variables (USUALLY A BAD IDEA) Pointers or references to shared structures or variables (shared memory) Pointers or references to “thread objects” (message passing)

19 .Thread Communication – Shared Memory Threads 19 #include <iostream> #include <thread> // struct storing shared memory struct SharedMemory { int counter ; }; // thread method that accepts shared memory void thread_increment( SharedMemory * shared) { shared-> counter ++; } int main() { const int NUM_THREADS = 1000 ; SharedMemory memory = { 0 }; // initialize memory // start a bunch of threads to increment the shared counter std :: thread * threads[NUM_THREADS]; for ( int i= 0 ; i<NUM_THREADS; ++i) { threads[i] = new std ::thread(thread_increment, &memory); } // wait for all threads to finish for ( int i= 0 ; i<NUM_THREADS; ++i) { threads[i]->join(); delete threads[i]; threads[i] = nullptr ; } // print value of memory std ::cout << memory. counter << std ::endl; return 0 ; }

20 .Thread Communication – Shared Memory Threads 19 #include <iostream> #include <thread> // struct storing shared memory struct SharedMemory { int counter ; }; // thread method that accepts shared memory void thread_increment( SharedMemory * shared) { shared-> counter ++; } int main() { const int NUM_THREADS = 1000 ; SharedMemory memory = { 0 }; // initialize memory // start a bunch of threads to increment the shared counter std :: thread * threads[NUM_THREADS]; for ( int i= 0 ; i<NUM_THREADS; ++i) { threads[i] = new std ::thread(thread_increment, &memory); } // wait for all threads to finish for ( int i= 0 ; i<NUM_THREADS; ++i) { threads[i]->join(); delete threads[i]; threads[i] = nullptr ; } // print value of memory std ::cout << memory. counter << std ::endl; return 0 ; }

21 .Thread Example: QuickSort Threads 21 pivot = array[rand() % size + start_idx]; pivot_idx = partition(array, start_idx, size, pivot); thread1 = QuickSort(array, start_idx, pivot_idx-start_idx); thread2 = QuickSort(array, pivot_idx+1, size-pivot_idx+start_idx-1); thread1.join(); thread2.join(); Thread: QuickSort (array, start_idx, size) How many threads get created (best case)? If a machine has 4 cores, what’s the best possible speed-up factor? What might prevent this?

22 .Race Conditions Threads 22 A race condition is when the the behaviour or output of a program depends on the precise sequence or timings of events. Line A1: x = 5; Line A2: std::cout << x << std::endl; Line B1: x = 7; Line S1: int x = 0; Line S2: std::cout << x << std::endl; Is it possible to get… 0, 5? 5, 7? 7, 7? 5, 5? 0, 7? 7, 5?

23 .Race Conditions A race condition is when the the behaviour or output of a program depends on the precise sequence or timings of events. Q: Will we get the same output every time? Q: What might influence the output? Considering these situations is important when designing concurrent systems. What execution orders are possible and what are the effects of that order? How do we enforce a particular execution order ? – synchronisation .

24 .Threads in Practice Threads 24 Every program has at least one main thread Most graphical programs have a separate thread to control the GUI How many threads? Main program thread GUI Spell-check Backups Save in background