Computer Operating System - Chapter 4: Threads & Concurrency

Overview
■ Multicore Programming
■ Multithreading Models
■ Thread Libraries
■ Implicit Threading
■ Threading Issues
■ Operating System Examples

63 trang xuanthi 30/12/2022 2540

Download

Bạn đang xem 20 trang mẫu của tài liệu "Computer Operating System - Chapter 4: Threads & Concurrency", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

computer_operating_system_chapter_4_threads_concurrency.pdf

Nội dung text: Computer Operating System - Chapter 4: Threads & Concurrency

Chapter 4: Outline ■ Overview ■ Multicore Programming ■ Multithreading Models ■ Thread Libraries ■ Implicit Threading ■ Threading Issues ■ Operating System Examples Operating System Concepts 2 Silberschatz, Galvin and Gagne ©2018
Motivation ■ Most modern applications are multithreaded ■ Threads run within application ■ Multiple tasks with the application can be implemented by separate threads, for example: ● Update display ● Fetch data ● Spell checking ● Answer a network request ■ Process creation is heavy-weight while thread creation is light-weight ● Can simplify code, increase efficiency ■ Kernels are generally multithreaded Operating System Concepts 4 Silberschatz, Galvin and Gagne ©2018
Multicore Programming ■ Multicore or multiprocessor systems putting pressure on programmers, challenges include: ● Dividing activities ● Balance ● Data splitting ● Data dependency ● Testing and debugging ■ Parallelism implies a system can perform more than one task simultaneously ■ Concurrency supports more than one task making progress ● Single processor / core, scheduler providing concurrency Operating System Concepts 8 Silberschatz, Galvin and Gagne ©2018
Multicore Programming ■ Types of parallelism ● Data parallelism – distributes subsets of the same data across multiple cores, same operation on each ● Task parallelism – distributing threads across cores, each thread performing unique operation Operating System Concepts 10 Silberschatz, Galvin and Gagne ©2018
Multithreading Models ■ Many-to-One ■ One-to-One ■ Many-to-Many Operating System Concepts 14 Silberschatz, Galvin and Gagne ©2018
One-to-One Model ■ Each user-level thread maps to one kernel thread ■ Creating a user-level thread creates a kernel thread ■ More concurrency than many-to-one ■ Number of threads per process sometimes restricted due to overhead ■ Examples ● Windows ● Linux Operating System Concepts 16 Silberschatz, Galvin and Gagne ©2018
Two-level Model ■ Similar to Many-to-Many model, except that it allows a user-level thread to be bounded to kernel thread Operating System Concepts 18 Silberschatz, Galvin and Gagne ©2018
Pthreads ■ May be provided either as user-level or kernel-level ■ A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization ● Specification, not implementation ● API specifies behavior of the thread library, implementation is up to development of the library ■ Common in UNIX operating systems (Linux & Mac OS X) Operating System Concepts 20 Silberschatz, Galvin and Gagne ©2018
Java Threads ■ Java threads are managed by the JVM ■ Typically implemented using the threads model provided by underlying OS ■ Java threads may be created by: ● Extending Thread class ● Implementing the Runnable interface ● Standard practice is to implement Runnable interface Operating System Concepts 26 Silberschatz, Galvin and Gagne ©2018
Java Executor Framework ■ Rather than explicitly creating threads, Java also allows thread creation around the Executor interface: ■ The Executor is used as follows: Operating System Concepts 28 Silberschatz, Galvin and Gagne ©2018
Thread Pools ■ Create a number of threads in a pool where they await work ■ Advantages: ● Usually slightly faster to service a request with an existing thread than create a new thread ● Allows the number of threads in the application(s) to be bounded to the size of the pool ● Separating task to be performed from mechanics of creating task allows different strategies for running task 4 i.e., Tasks could be scheduled to run periodically ■ Windows API supports thread pools: Operating System Concepts 32 Silberschatz, Galvin and Gagne ©2018
Fork-Join Parallelism ■ Multiple threads (tasks) are forked, and then joined Operating System Concepts 34 Silberschatz, Galvin and Gagne ©2018
OpenMP ■ Set of compiler directives and an API for C, C++, FORTRAN ■ Provides support for parallel programming in shared- memory environments ■ Identifies parallel regions – blocks of code that can run in parallel #pragma omp parallel ■ Create as many threads as there are cores ■ Run the for loop in parallel Operating System Concepts 40 Silberschatz, Galvin and Gagne ©2018
Grand Central Dispatch (Cont.) ■ Two types of dispatch queues: ● serial – blocks removed in FIFO order, queue is per process, called main queue 4 Programmers can create additional serial queues within program ● concurrent – removed in FIFO order but several may be removed at a time 4 Four system-wide queues divided by quality of service: o QOS_CLASS_USER_INTERACTIVE o QOS_CLASS_USER_INITIATED o QOS_CLASS_USER_UTILITY o QOS_CLASS_USER_BACKGROUND Operating System Concepts 42 Silberschatz, Galvin and Gagne ©2018
Intel Threading Building Blocks (TBB) ■ Template library for designing parallel C++ programs ■ A serial version of a simple for loop ■ The same for loop written using TBB with parallel_for statement: Operating System Concepts 44 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 46 Silberschatz, Galvin and Gagne ©2018
Signal Handling (Cont.) ■ Where should a signal be delivered for multithreaded? ● Deliver the signal to the thread to which the signal applies ● Deliver the signal to every thread in the process ● Deliver the signal to certain threads in the process ● Assign a specific thread to receive all signals for the process Operating System Concepts 48 Silberschatz, Galvin and Gagne ©2018
Thread Cancellation (Cont.) ■ Invoking thread cancellation requests cancellation, but actual cancellation depends on thread state ■ If thread has cancellation disabled, cancellation remains pending until thread enables it ■ Default type is deferred ● Cancellation only occurs when thread reaches cancellation point 4 i.e., pthread_testcancel() 4 Then cleanup handler is invoked ■ On Linux systems, thread cancellation is handled through signals Operating System Concepts 50 Silberschatz, Galvin and Gagne ©2018
Thread-Local Storage ■ Thread-Local Storage (TLS) allows each thread to have its own copy of data ■ Useful when you do not have control over the thread creation process (i.e., when using a thread pool) ■ Different from local variables ● Local variables visible only during single function invocation ● TLS visible across function invocations ■ Similar to static data ● TLS is unique to each thread Operating System Concepts 52 Silberschatz, Galvin and Gagne ©2018
Operating System Examples ■ Windows Threads ■ Linux Threads Operating System Concepts 54 Silberschatz, Galvin and Gagne ©2018
Windows Threads (Cont.) ■ The primary data structures of a thread include: ● ETHREAD (executive thread block) – includes pointer to process to which thread belongs and to KTHREAD, in kernel space ● KTHREAD (kernel thread block) – scheduling and synchronization info, kernel-mode stack, pointer to TEB, in kernel space ● TEB (thread environment block) – thread ID, user-mode stack, thread- local storage, in user space Operating System Concepts 56 Silberschatz, Galvin and Gagne ©2018
Linux Threads ■ Linux refers to them as tasks rather than threads ■ Thread creation is done through clone() system call ■ clone() allows a child task to share the address space of the parent task (process) ● Flags control behavior ■ struct task_struct points to process data structures (shared or unique) Operating System Concepts 58 Silberschatz, Galvin and Gagne ©2018
Summary (Cont.) ■ There are several challenges in designing multithreaded applications. They include dividing and balancing the work, dividing the data between the different threads, and identifying any data dependencies. Finally, multithreaded programs are especially challenging to test and debug. ■ Data parallelism distributes subsets of the same data across different computing cores and performs the same operation on each core. Task parallelism distributes not data but tasks across multiple cores. Each task is running a unique operation. ■ User applications create user-level threads, which must ultimately be mapped to kernel threads to execute on a CPU. The many-to- one model maps many user-level threads to one kernel thread. Other approaches include the one-to-one and many-to-many models. Operating System Concepts 60 Silberschatz, Galvin and Gagne ©2018
Summary (Cont.) ■ Threads may be terminated using either asynchronous or deferred cancellation. Asynchronous cancellation stops a thread immediately, even if it is in the middle of performing an update. Deferred cancellation informs a thread that it should terminate but allows the thread to terminate in an orderly fashion. In most circumstances, deferred cancellation is preferred to asynchronous termination. ■ Unlike many other operating systems, Linux does not distinguish between processes and threads; instead, it refers to each as a task. The Linux clone() system call can be used to create tasks that behave either more like processes or more like threads. Operating System Concepts 62 Silberschatz, Galvin and Gagne ©2018