Ch 4 Threads F24.pptx

Chapter 4: Threads & Concurrency Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018  Outline  Overview  Multicore Programming  Multithreading Models...

Chapter 4: Threads & Concurrency Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018  Outline  Overview  Multicore Programming  Multithreading Models  Thread Libraries  Implicit Threading  Threading Issues  Operating System Examples Operating System Concepts – 10th Edition 4.2 Silberschatz, Galvin and Gagne ©2018  Objectives  Identify the basic components of a thread, and contrast threads and processes  Describe the benefits and challenges of designing multithreaded applications  Illustrate different approaches to implicit threading including thread pools and fork-join  Describe how the Linux operating systems represent threads Operating System Concepts – 10th Edition 4.3 Silberschatz, Galvin and Gagne ©2018  What is a Thread  A thread is a basic unit of CPU utilization;  It comprises a thread ID, a program counter (PC), a register set, and a stack.  It shares with other threads belonging to the same process its code section, data section, and OS resources, such as open files and signals. Operating System Concepts – 10th Edition 4.4 Silberschatz, Galvin and Gagne ©2018  Multithreaded Application A traditional process has a single thread of control. If a process has multiple threads of control, it can perform more than one task at a time Most modern applications typically are implemented as a separate process with several threads of control 1. An application that creates photo thumbnails from a collection of images may use a separate thread to generate a thumbnail from each separate image. 2. A web browser might have one thread display images or text while another thread retrieves data from the network. 3. A word processor may have a thread for displaying graphics, another thread for responding to keystrokes from the user, and a third thread for performing spelling and grammar checking in the background Operating System Concepts – 10th Edition 4.5 Silberschatz, Galvin and Gagne ©2018  Motivation  Process creation is heavy-weight while thread creation is light-weight  Can simplify code, increase efficiency  Kernels are generally multithreaded Operating System Concepts – 10th Edition 4.6 Silberschatz, Galvin and Gagne ©2018  Single Vs. Multithreaded Processes Operating System Concepts – 10th Edition 4.7 Silberschatz, Galvin and Gagne ©2018  Multithreaded Server Architecture Operating System Concepts – 10th Edition 4.8 Silberschatz, Galvin and Gagne ©2018  Benefits  Responsiveness – may allow continued execution if part of process is blocked, especially important for user interfaces  Resource Sharing – threads share resources of process, which is easier than shared memory or message passing  Economy – cheaper than process creation, thread switching lower overhead than context switching  Scalability – process can take advantage of multicore architectures Operating System Concepts – 10th Edition 4.9 Silberschatz, Galvin and Gagne ©2018  Computing Goals  Parallelism implies a system can perform more than one task simultaneously Contributes to performance  Concurrency supports more than one task making progress contributes to responsiveness  CPU utilization means the proportion of time a CPU is busy or being used Operating System Concepts – 10th Edition 4.10 Silberschatz, Galvin and Gagne ©2018  Different computing use cases  Single-thread with multicore: A single-threaded process can run on only one processor regardless how many CPU cores are available.  CPU utilization is low  Single thread and single core: In a single processor or core, CPU schedulers were designed to provide the illusion of parallelism by rapidly switching between processes,  Such processes were running concurrently, but not in parallel.  Multithread with single core: a single CPU core is time- multiplexed among different the threads Threads belonging to processes can be run concurrently, but not in parallel Operating System Concepts – 10th Edition 4.11 Silberschatz, Galvin and Gagne ©2018  Multicore System with Multithreading  Multicore system refers to having multiple computing cores on a single processing chip where each core appears as a separate CPU to the operating system  Multithreaded programming with multicore system provides a mechanism for more efficient use of these multiple computing cores and improved concurrency Threads may be running in parallel on different processing cores. Operating System Concepts – 10th Edition 4.12 Silberschatz, Galvin and Gagne ©2018  Concurrency vs. Parallelism  Concurrent execution on single-core system:  Parallelism on a multi-core system: Operating System Concepts – 10th Edition 4.13 Silberschatz, Galvin and Gagne ©2018  Multicore Programming Challenges  System designers and application programmers need to make better use of the multiple computing cores Designers of operating systems must write scheduling algorithms that use multiple processing cores to allow the parallel execution. Application programmers have to modify or design new programs that are multithreaded.  Challenges include: Dividing activities Balance Data splitting Data dependency Testing and debugging Operating System Concepts – 10th Edition 4.14 Silberschatz, Galvin and Gagne ©2018  Programming Challenges  Dividing activities: examining applications to find areas that can be divided into separate, concurrent tasks. Ideally, tasks should be independent of one another and thus can run in parallel on individual cores.  Balance: programmers must also ensure that the tasks perform equal work of equal value. a certain task may not contribute as much value to the overall process as other tasks, using a separate execution core then can be worthless  Data splitting: data accessed and manipulated by the divided tasks must be divided to run on separate cores  Data dependency: When one task depends on data from another, programmers must ensure that the execution of the tasks is synchronized to accommodate the data dependency  Testing and debugging: Testing and debugging concurrent programs is inherently difficult because they have multiple execution path to monitor Operating System Concepts – 10th Edition 4.15 Silberschatz, Galvin and Gagne ©2018  Types of Parallelism  Data parallelism – distributes subsets of the same data across multiple cores, same operation on each On a dual-core system, sum operation on elements... [N − 1]. Thread A may run on core 0, sum the elements... [N/2 − 1] while Thread B may run on core 1, sum the elements [N/2]... [N − 1]. The two threads would be running in parallel on separate computing cores.  Task parallelism – distributing threads across cores, each thread performing unique operation Thread A runs on core 0, may perform statistical test 1 on... [N − 1] Thread B runs on core 1, may perfrom statistical test 2 on... [N − 1] The two threads would be running in parallel on separate computing cores.  Operating System Concepts – 10th Edition 4.16 Silberschatz, Galvin and Gagne ©2018  Data and Task Parallelism Operating System Concepts – 10th Edition 4.17 Silberschatz, Galvin and Gagne ©2018  Amdahl’s Law  Amdahl laws Identifies performance gains from adding additional cores to an application that has both serial and parallel components. Let, S is portion of the application that must be performed serially N processing cores  That is, if application is 75% parallel and 25% serial, moving from 1 to 2 cores results in speedup of 1.6 times moving from 1 to 4 cores results in speedup of 2.28 time As N approaches infinity, speedup approaches 1 / S  Serial portion of an application has disproportionate effect on performance gained by adding additional cores  For example, if 50 percent of an application is performed serially, the maximum speedup is 2.0 times, regardless of the number of processing cores we add Silberschatz, Galvin and Gagne ©2018 Operating System Concepts – 10th Edition 4.18  Amdahl’s Law Operating System Concepts – 10th Edition 4.19 Silberschatz, Galvin and Gagne ©2018  User Threads vs. Kernel Threads  Support for threads can be provided in two levels, thread libraries are created to support the creation and manage 1. User threads - management done by user-level threads library Three primary thread libraries:  POSIX Pthreads  Windows threads  Java threads 2. Kernel threads - Supported by the Kernel Examples – virtually all general-purpose operating systems, e.g,:  Windows, Linux, Mac OS X, iOS, Android  Ultimately, a relationship must establish between user threads and kernel threads where user threads are mapped with specific kernel threads Operating System Concepts – 10th Edition 4.20 Silberschatz, Galvin and Gagne ©2018  Relationship of User and Kernel Threads Operating System Concepts – 10th Edition 4.21 Silberschatz, Galvin and Gagne ©2018  Multithreading Models  Many-to-One  One-to-One  Many-to-Many Operating System Concepts – 10th Edition 4.22 Silberschatz, Galvin and Gagne ©2018  Many-to-One  Many user-level threads mapped to single kernel thread  Convenient as it is managed on user space by thread library  Problem: one thread blocking causes all to block  Multiple threads can not run in parallel on multicore system because only one of them is mapped with kernel at a time  Few systems currently use this model, examples: Solaris Green Threads GNU Portable Threads Operating System Concepts – 10th Edition 4.23 Silberschatz, Galvin and Gagne ©2018  One-to-One  Each user-level thread maps to one kernel thread  Advantage: More concurrency or parallelism than many-to- one  Disadvantages: Overhead: For each user-level thread another kernel thread needs to be created Number of threads per process sometimes gets restricted due to overhead  Examples Windows Linux Operating System Concepts – 10th Edition 4.24 Silberschatz, Galvin and Gagne ©2018  Many-to-Many Model  Many to many model multiplexes many user-level threads to a smaller or equal number of kernel threads Example: Windows with the ThreadFiber package. Operating System Concepts – 10th Edition 4.25 Silberschatz, Galvin and Gagne ©2018  Many-to-Many Model  Advantages: developers can create as many user threads as necessary the corresponding kernel threads can run in parallel on a multiprocessor. when a thread performs a blocking system call, the kernel can schedule another thread for execution.  Disadvantages: More difficult to implement Operating System Concepts – 10th Edition 4.26 Silberschatz, Galvin and Gagne ©2018  Two-level Model  Similar to the ‘many to many’ model except that it allows a user thread to be bound to kernel thread Operating System Concepts – 10th Edition 4.27 Silberschatz, Galvin and Gagne ©2018  Thread Libraries  Thread library provides programmer with API for creating and managing threads  Two primary ways of implementing Library entirely in user space:  All code and data structures for the library exist in user space.  So, invoking a function in the library results in a local function call in user space and not a system call. Kernel-level library supported by the OS  code and data structures for the library exist in kernel space.  Invoking a function in the API for the library typically results in a system call to the kernel. Operating System Concepts – 10th Edition 4.28 Silberschatz, Galvin and Gagne ©2018  Three Types of Thread Libraries  POSIX Pthread: threads extension of the POSIX standard may be provided as either a user-level or a kernel- level library.  Windows Thread: The Windows thread library is a kernel- level library available on Windows systems  Java Thread: The Java thread API allows threads to be created and managed directly in Java programs. Since JVM is running on top of a host operating system, the Java thread API is generally implemented using a thread library available on the host system.  on Windows systems, Java threads are typically implemented using the Windows API;  UNIX, Linux, and macOS systems typically use Pthreads. Operating System Concepts – 10th Edition 4.29 Silberschatz, Galvin and Gagne ©2018  Inter-thread data sharing  For POSIX and Windows threading, any data declared globally—that is, declared outside of any function—are shared among all threads belonging to the same process.  Java has no equivalent notion of global data, access to shared data must be explicitly arranged between threads. Operating System Concepts – 10th Edition 4.30 Silberschatz, Galvin and Gagne ©2018  Pthreads  A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization May be provided either as user-level or kernel-level Any data declared globally (declared outside of any function) are shared among all threads belonging to the same process.  Two general strategies for creating multiple threads: Asynchronous threading: once the parent creates a child thread, the parent resumes its execution, so that the parent and child execute concurrently and independently of one another Synchronous threading: the parent thread creates one or more children and then must wait for all of its children to terminate before it resumes Operating System Concepts – 10th Edition 4.31 Silberschatz, Galvin and Gagne ©2018  Pthreads  Pthread refers to the POSIX standard (IEEE 1003.1c) defining an API for thread creation and synchronization  Pthread is about Specification, not implementation API specifies behavior of the thread library, implementation is up to development of the library by the operating systems  Common in UNIX operating systems (Linux & Mac OS X) Operating System Concepts – 10th Edition 4.32 Silberschatz, Galvin and Gagne ©2018  Pthreads Example Operating System Concepts – 10th Edition 4.33 Silberschatz, Galvin and Gagne ©2018  Pthreads Example (Cont.) Operating System Concepts – 10th Edition 4.34 Silberschatz, Galvin and Gagne ©2018  Pthreads Code for Joining 10 Threads Operating System Concepts – 9 th Edition 4. 21 Silberschatz, Galvin and Gagne ©2013 Operating System Concepts – 10th Edition 4.35 Silberschatz, Galvin and Gagne ©2018  Implicit Threading  Growing in popularity as numbers of threads increase, program correctness more difficult with explicit threads  Creation and management of threads done by compilers and run-time libraries rather than programmers  Five methods explored Thread Pools Fork-Join OpenMP Grand Central Dispatch Intel Threading Building Blocks Operating System Concepts – 10th Edition 4.36 Silberschatz, Galvin and Gagne ©2018  Fork-Join Parallelism  Multiple threads (tasks) are forked, and then joined. Operating System Concepts – 10th Edition 4.37 Silberschatz, Galvin and Gagne ©2018  Fork-Join Parallelism  General algorithm for fork-join strategy: Operating System Concepts – 10th Edition 4.38 Silberschatz, Galvin and Gagne ©2018  Fork-Join Parallelism Operating System Concepts – 10th Edition 4.39 Silberschatz, Galvin and Gagne ©2018  Semantics of fork() and exec()  Does fork()duplicate only the calling thread or all threads? Some UNIXes have two versions of fork  exec() usually works as normal – replace the running process including all threads Operating System Concepts – 10th Edition 4.40 Silberschatz, Galvin and Gagne ©2018  Threading Issues  Semantics of fork() and exec() system calls  Signal handling Synchronous and asynchronous  Thread cancellation of target thread Asynchronous or deferred  Thread-local storage  Scheduler Activations Operating System Concepts – 10th Edition 4.41 Silberschatz, Galvin and Gagne ©2018  End of Chapter 4 Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018