WIXLIB

Operating System:Chap4 MultithreadedProgrammingNational Tsing-Hua University2016, Fall Semester

OverviewThread Introduction Multithreading Models Threaded Case Study Threading Issues Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab2

Threads A.k.a lightweight process:basic unit of CPU utilization All threads belonging to thesame process share code section, data section,and OS resources (e.g. openfiles and signals) But each thread has its own(thread control block) thread ID, program counter,register set, and a stackChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab3

Motivation Example: a web browser Example: a web server One thread displays contents while the other threadreceives data from networkOne request / process: poor performanceOne request / thread: better performance as code andresource sharingExample: RPC server One RPC request / threadWhen a request is issued,creates (or notifies) a threadto serve the request.Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab4

Benefits of Multithreading Responsiveness: allow a program to continue runningeven if part of it is blocked or is performing a lengthyoperationResource sharing: several different threads of activityall within the same address spaceUtilization of MP arch.: Several thread may be runningin parallel on different processorsEconomy: Allocating memory and resources for processcreation is costly. In Solaris, creating a process is about30 times slower than is creating a thread, and contextswitching is about five times slower. A register setswitch is still required, but no memory-managementrelated work is neededChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab5

Why Thread? Lower creation/management cost vs. ProcessplatformAMD 2.4 GHz OpteronIBM 1.5 GHz POWER4INTEL 2.4 GHz XeonINTEL 1.4 GHz Itanium2 fork()17.6104.554.954.5pthread ter inter-process communication vs. MPIplatformAMD 2.4 GHz OpteronIBM 1.5 GHz POWER4INTEL 2.4 GHz XeonMPI Shared Pthreads Worst Case speedupMemoryMemory-to-CPUBW (GB/sec)BW (GB/sec)1.25.34.4x2.141.9x0.34.314.3x– NTHU LSA Lab6.4INTEL 1.4 GHz Itanium2 Parallel Programming1.8Chapter4 Multithreaded3.6x

Multithcore Programming Multithreaded programming provides a mechanismfor more efficient use of multiple cores andimproved concurrency (threads can run in parallel)Multicore systems putting pressure on systemdesigners and application programmers OS designers: scheduling algorithms use cores to allow theparallel executionChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab7

Challenges in Multicore Programming Dividing activities: divide program intoconcurrent tasks Balance: evenly distribute tasks to cores Data splitting: divide data accessed andmanipulated by the tasks Data dependency: synchronize data access Testing and debuggingChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab8

User vs. Kernel Threads User threads – thread management done by userlevel threads library POSIX PthreadsWin32 threadsJava threadsKernel threads – supported by the kernel (OS)directly Windows 2000 (NT)SolarisLinuxTru64 UNIXChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab9

User vs. Kernel Threads User threads Thread library provides support for thread creation,scheduling, and deletionGenerally fast to create and manageIf the kernel is single-threaded, a user-thread blocks entire process blocks even if other threads are ready torunKernel threads The kernel performs thread creation, scheduling, etc.Generally slower to create and manageIf a thread is blocked, the kernel can schedule anotherthread for executionChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab10

Multithreading ModelsMany-to-One One-to-One Many-to-Many Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab11

Many-to-OneMany user-level threads mapped to singlekernel thread Used on systems that do not support kernelthreads Thread management is done in user space, soit is efficient The entire process will block if a threadmakes a blocking system call Only one thread can access the kernel at atime, multiple threads are unable to run inparallel on multiprocessorsChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab12

One-to-one Each user-level thread maps to a kernel thread There could be a limit on number of kernel threads More concurrency Overhead: Creating a thread requires creating thecorresponding kernel thread Examples- Windows XP/NT/2000- Linux- Solaris 9 and laterChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab13

Many-to-ManyMultiplexes many user-level threads to asmaller or equal number of kernel threads Allows the developer to create as many userthreads as wished The corresponding kernel threads can run in parallelon a multiprocessor When a thread performs a blocking call, the kernelcan schedule another thread for execution.Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab14

Review Slides ( I ) Process context swap? Thread context swap?Benefit of multithreading? Responsive, Economy, resource utilization, resource sharingChallenges of multithreading programming?User threads & kernel threads? Differences?Threading model? Many-to-oneOne-to-oneMany-to-manyChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab15

Case Study Threadlibraries Pthreads Java threads OSexamples WinXP LinuxChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab16

Shared-Memory Programming Definition: Processes communicate or work togetherwith each other through a shared memory spacewhich can be accessed by all processes Many issues as well: Faster & more efficient than message passingSynchronizationDeadlockCache coherenceProgramming techniques: Parallelizing compilerUnix processesThreads (Pthread, Java)Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab17

What is Pthread? Historically, hardware vendors have implementedtheir own proprietary versions of threadsPOSIX (Potable Operating System Interface)standard is specified for portability across Unix-likesystems Similar concept as MPI for message passing librariesPthread is the implementation of POSIX standardfor threadChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab18

Pthread Creation pthread create(thread,attr,routine,arg)thread: An unique identifier (token) for the new thread attr: It is used to set thread attributes. NULL for the default values routine: The routine that the thread will execute once it is created arg: A single argument that may be passed to routine main programpthread join(thread1, *status);Chapter4 MultithreadedOperating System Concepts – NTHU LSA Labfunc(&arg) { pthread create(&thread1, NULL, func1, &arg);thread1return(*status)}19

Example#include pthread.h #include stdio.h #define NUM THREADS 5void *PrintHello(void *threadId) {long* data static cast long* threadId;printf("Hello World! It's me, thread #%ld!\n", *data);pthread exit(NULL);}int main (int argc, char *argv[]) {pthread t threads[NUM THREADS];for(long tid 0; tid NUM THREADS; tid ){pthread create(&threads[tid], NULL, PrintHello, (void *)&tid);}/* Last thing that main() should do */pthread exit(NULL);}Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab20

Pthread Joining & Detaching pthread join(threadId, status) Blocks until the specified threadId thread terminatesOne way to accomplish synchronization between threadsExample: to create a pthread barrierfor (int i 0; i n; i ) pthread join(thread[i], NULL); pthread detach(threadId) Once a thread is detached, it can never be joinedDetach a thread could free some system resourcesChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab21

Java Threads Thread is created by Extending Thread class Implementing the Runnable interfaceJava threads are implemented using a thread libraryon the host system Win32 threads on WindowsPthreads on UNIX-like systemThread mapping depends on implementation of theJVM Windows 98/NT: one-on-one modelSolaris 2: many-to-many modelChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab22

Linux ThreadsLinux does not support multithreading Vrious Pthreads implementation are available foruser-level The fork system call – create a new process and acopy of the associated data of the parent process The clone system call – create a new process anda link that points to the associated data of theparent process Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab23

Linux Threads A set of flags is used in the clone call forindication of the level of the sharing None of the flags is set clone fork All flags are set parent and child share everythingChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab24

Threading Issues Semantics of fork() and exec() system calls.Duplicate all the threads or not?Thread cancellation: Asynchronous or deferred Signal handling: Where then should a signal be delivered? Thread pools: Create a number of threads atprocess startup. Thread specific data: Each thread might need its Scheduler activationsown copy of certain data.Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab25

Semantics of fork() and exec() Does fork() duplicate only the calling threador all threads? Some UNIX system support two versions of fork() execlp() works the same; replace the entireprocess If exec() is called immediately after forking, thenT1P0T2T2T2Operating System Concepts – NTHU LSA LabT2P1T2fork()fork(). .fork()T1P0 . .fork()T1P1 . .Chapter4 Multithreaded . . .fork()T1P0. .duplicating all threads is unnecessary26

Thread Cancellation What happen if a thread determinates before it hascompleted? E.g, terminate web page loadingTarget thread: a thread that is to be cancelledTwo general approaches: Asynchronous cancellationOne thread terminates the target thread immediatelyDeferred cancellation (default option)The target thread periodically checks whether it shouldbe terminated, allowing it an opportunity to terminateitself in an orderly fashion (canceled safely).Check at Cancellation pointsChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab27

Signal Handling Signals (synchronous or asynchronous) are used in UNIXsystems to notify a process that an event has occurred A signal handler is used to process signals1.2.3. Synchronous: illegal memory accessAsynchronous: control-C Signal is generated by particular eventSignal is delivered to a processSignal is handledOptions Deliver the signal to the thread to which the signal appliesDeliver the signal to every thread in the processDeliver the signal to certain threads in the processAssign a specific thread to receive all signals for the processChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab28

Thread PoolsCreate a number of threads in a pool wherethey await work Advantages Usually slightly faster to service a request with anexisting thread than create a new thread Allows the number of threads in the application(s)to be bound to the size of the pool # of threads: # of CPUs, expected # ofrequests, amount of physical memoryChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab29

Reading Material & HWChap 4 Problems 4.2, 4.3, 4.10, 4.12, 4.13Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab30

BackupChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab31

Windows XP Threads Implement the one-to-one mappingEach thread contains The primary data structures of a thread include: A thread IDRegister setSeparate user and kernel stacksPrivate data storage areaETHREAD (executive thread block)KTHREAD (kernel thread block)TEB (thread environment block)Also provide support for a fiber library, that providesthe functionality of the many-to-many model32Chapter4 MultithreadedOperating System Concepts – NTHU LSA Lab

Windows XP ThreadsChapter4 MultithreadedOperating System Concepts – NTHU LSA Lab33