Transcript Thread

Threads
Topics
• Thread
– Introduction
– Multithreading models
– Thread libraries
– Threading issues
– Linux Threads
But first…..
• Shell slides I found
Shell Command Line Interpreter
Interactive User
Application
& System
Software
Shell Program
OS System Call Interface
OS
Operating Systems: A
Modern Perspective,
Chapter 2
The Shell Strategy
% grep first f3
read keyboard
fork a process
Shell Process
Process
to execute
command
read file
f3
Operating Systems: A
Modern Perspective,
Chapter 2
Back to Threads
Abstract Machine Entities
• Process: A sequential program in execution
• Resource: Any abstract resource that a
process can request, and which may can
cause the process to be blocked if the
resource is unavailable.
• File: A special case of a resource. A
linearly-addressed sequence of bytes. “A
byte stream.”
Operating Systems: A
Modern Perspective,
Chapter 2
Idea
Algorithms, Programs, and
Processes
Execution Engine
Algorithm
Source
Program
Status Stack
Binary
Program
Data
Process
Operating Systems: A
Modern Perspective,
Chapter 2
Files
Files
Files
Other
Resources
Process Abstraction
Stack
Data
Process
Program
Operating System
Hardware
Processor
Executable
Memory
Operating Systems: A
Modern Perspective,
Chapter 2
Classic Process
• OS implements {process environment} – one
per task
• Multiprogramming enables N programs to be
space-muxed in executable memory, and
time-muxed across the physical machine
processor.
• Result: Have an environment in which there
can be multiple programs in execution
concurrently*, each as a processes
Operating Systems: A
* Concurrently: Programs
Modern Perspective,
Chapter 2
appear to execute simultaneously
Multithreaded Accountant
Invoice
First Accountant
Invoice
Purchase Orders
Invoice
Accountant & Clone
Second Accountant
Separate Processes
Operating Systems: A
Modern Perspective,
Chapter 2
Purchase Orders
Double Threaded Process
Definitions
• A thread is a single execution sequence that
represents a separately schedulable task
A Process with Multiple Threads
Thread (Execution Engine)
Status Stack
Status Stack
Status Stack
Files
Files
Files
Data
Binary
Program
Process
Operating Systems: A
Modern Perspective,
Chapter 2
Other
Resources
Single and Multithreaded Processes
Thread Lifecycle
Thread Specific Data
• 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)
Single and Multithreaded Processes
Thread
Data
Shared vs. Per-Thread State
Modern Process & Thread
• Divide classic process:
Data
Process
Program
…
Thread
Operating System
Operating Systems: A
Modern Perspective,
Chapter 2
Stack
Stack
Thread
Thread
Stack
– Process is an infrastructure in which execution
takes place – address space + resources
– Thread is a program in execution within a
process context – each thread has its own stack
Process Control Blocks
PID
Terminated children
Link
Return code
PID
Terminated children
Link
Return code
PID
Terminated children
Link
Return code
TCB Link
Process Control
Block
Multithreaded Server Architecture
thread
thread
thread
thread
Motivation
• Operating systems need to be able to handle multiple
things at once (MTAO)
– processes, interrupts, background system maintenance
• Servers need to handle MTAO
– Multiple connections handled simultaneously
• Parallel programs need to handle MTAO
– To achieve better performance
• Programs with user interfaces often need to handle MTAO
– To achieve user responsiveness while doing computation
• Network and disk bound programs need to handle MTAO
– To hide network/disk latency
Multicore Programming
• Multicore systems putting pressure on
programmers, challenges include
– Dividing activities
– Balance
– Data splitting
– Data dependency
– Testing and debugging
Thread Abstraction
• Infinite number of processors
• Threads execute with variable speed
– Programs must be designed to work with any schedule
Thread Implementation
• Threads can be implemented in any of several
ways
– User Threads
– Kernel Threads
User Threads
• Threads can be implemented in any of several ways
• User Threads
– Thread management done by user-level threads library
• Multiple user-level threads, inside a UNIX process (early Java)
• Multiple single-threaded processes (early UNIX)
• Three primary thread libraries:
– POSIX Pthreads
– Win32 threads
– Java threads
– Mixture of single and multi-threaded processes and kernel threads
(Linux, MacOS, Windows)
• To the kernel, a kernel thread and a single threaded user process look quite
similar
– Scheduler activations (Windows)
Kernel Threads
• Supported by the Kernel
• Examples
–
–
–
–
–
Windows XP/2000
Solaris
Linux
Tru64 UNIX
Mac OS X
• Mixture of single and multi-threaded processes and kernel threads (Linux,
MacOS, Windows)
– To the kernel, a kernel thread and a single threaded user process look quite
similar
• Scheduler activations (Windows)
Multithreading Models
User Thread – to - Kernel Thread
• Many-to-One
• One-to-One
• Many-to-Many
Multithreading Models
User Thread – to - Kernel Thread
• Many-to-One
• One-to-One
• Many-to-Many
Many-to-One
• Many user-level threads mapped to single
kernel thread
• Examples:
– Solaris Green Threads
– GNU Portable Threads
Many-to-One Model
One-to-One
• Each user-level thread maps to kernel thread
• Examples
– Windows NT/XP/2000
– Linux
– Solaris 9 and later
One-to-one Model
Many-to-Many Model
• Allows many user level threads to be
mapped to many kernel threads
• Allows the operating system to create
a sufficient number of kernel threads
• Solaris prior to version 9
• Windows NT/2000 with the
ThreadFiber package
Many-to-Many Model
Thread Libraries
• Thread library provides programmer with API
for creating and managing threads
• Two primary ways of implementing
– Library entirely in user space
– Kernel-level library supported by the OS
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
Pthreads
• May be provided either as user-level or
kernel-level
• A POSIX standard (IEEE 1003.1c) API for
thread creation and synchronization
• API specifies behavior of the thread
library, implementation is up to
development of the library
• Common in UNIX operating systems
(Solaris, Linux, Mac OS X)
Thread Operations
• pthread_create(func, args)
– Create a new thread to run func(args)
• pthread_yield()
– Relinquish processor voluntarily
• pthread_join(thread)
– In parent, wait for forked thread to exit, then
return
• pthread_exit
– Quit thread and clean up, wake up joiner if any
Helpful links
• http://www.yolinux.com/TUTORIALS/LinuxTut
orialPosixThreads.html
• https://computing.llnl.gov/tutorials/pthreads/
• Best:
http://www.cs.cmu.edu/afs/cs/academic/class
/15492-f07/www/pthreads.html
Threading Issues
• Semantics of fork() and exec() system
calls
• Thread cancellation of target thread
– Asynchronous or deferred
•
•
•
•
Signal handling
Thread pools
Thread-specific data
Scheduler activations
Semantics of fork() and exec()
• Does fork() duplicate only the calling thread or
all threads?
Thread Cancellation
• Terminating a thread before it has
finished
• Two general approaches:
– Asynchronous cancellation terminates
the target thread immediately
– Deferred cancellation allows the target
thread to periodically check if it should
be cancelled
Signal Handling
• Signals are used in UNIX systems to notify a
process that a particular event has occurred
• A signal handler is used to process signals
1. Signal is generated by particular event
2. Signal is delivered to a process
3. Signal is handled
• Options:
– 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 threa to receive all signals for the
process
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 bound to the size of the
pool
Thread Scheduling
Programmer vs. Processor View
Possible Executions
Main: Fork 10 threads
call join on them, then exit
• What other
interleavings are
possible?
• What is
maximum # of
threads running
at same time?
• Minimum?
Two threads call yield
Thread Pitfals
•Race conditions
• Ensuring Thread safe code
•Mutex Deadlock
Race Conditions
While the code may appear on the screen in the
order you wish the code to execute, threads are
scheduled by the operating system and are
executed at random. It cannot be assumed that
threads are executed in the order they are
created. They may also execute at different
speeds. When threads are executing (racing to
complete) they may give unexpected results
(race condition).
Producer
while (true) {
/* produce an item and put in
nextProduced */
while (count == BUFFER_SIZE)
; // do nothing
buffer [in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
count++;
}
Producer
while (true) {
/* produce an item and put in
nextProduced */
while (count == BUFFER_SIZE)
; // do nothing
buffer [in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
count++;
}
Race Condition
• count++ could be implemented as
register1 = count
register1 = register1 + 1
count = register1
• count-- could be implemented as
register2 = count
register2 = register2 - 1
count = register2
• Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}
Thread Safe Code
"thread safe".
• This means that there are no static or global variables which other
threads may clobber or read assuming single threaded operation.
•
If static or global variables are used then protection must be applied
or the functions must be re-written to avoid the use of these
variables.
• In C, local variables are dynamically allocated on the stack.
Therefore, any function that does not use static data or other shared
resources is thread-safe.
• Thread-unsafe functions may be used by only one thread at a time in
a program and the uniqueness of the thread must be ensured. Many
non-reentrant functions return a pointer to static data.
Deadlock
Thread1 has a resource that Thread2 wants
while
Thread2 has a resource that Thread1 wants.
Process Manager Responsibilities
• Define & implement the essential characteristics of a
process and thread
– Data structures to preserve the state of the execution
• Define what “things” threads in the process can reference
– the address space (most of the “things” are memory
locations)
• Manage the resources used by the processes/threads
• Tools to create/destroy/manipulate processes & threads
• Tools to time-multiplex or schedule the process/threads in
the CPU
• Tools to allow threads to synchronization the operation
with one another
• Mechanisms to handle deadlock
• Mechanisms to handle protection
Operating Systems: A Modern
Perspective, Chapter 6