Penulis
1. Last time we discussed how processes can be independent or work cooperatively.
2. Cooperating processes can be used :
1. Combination of one-to-one + “strict” many-to-many models
2. Cooperating processes can be used :
- To gain speedup by overlapping activities or working in parallel.
- To better structure an application as set of cooperating processes.
- To share information between jobs.
- Each produces work for the next stage that consumes it.
Case for Parallelism
Consider the following code fragment on a dual core CPU :
for(k = 0; k < n; k++)
a[k] = b[k] * c[k] + d[k] * e[k];
Instead :
CreateProcess(fn, 0, n/2);
CreateProcess(fn, n/2, n);
fn(l, m)
for(k = l; k < m; k++)
a[k] = b[k] * c[k] + d[k] * e[k];
1. Consider a web server :
- Get network message from socket
- Get URL data from disk
- Compose response
- Write compose.
2. Server connections are fast, but client connections may not be (grandma’s modem connection)
- Takes server a loooong time to feed the response to grandma
- While it’s doing that it can’t service any more requests
Parallel Programs
1. To build parallel programs, such as :
- Parallel execution on a multiprocessor
- Web server to handle multiple simultaneous web requests
2. We will need to :
- Create several processes that can execute in parallel
- Cause each to map to the same address space. Because they’re part of the same computation
- Give each its starting address and initial parameters
- The OS will then schedule these processes in parallel
Process Overheads
1. A full process includes numerous things :
- An address space (defining all the code and data pages)
- OS resources and accounting information
- A “thread of control”, defines where the process is currently executing. That is the PC and registers
2. Creating a new process is costly.
- All of the structures (e.g., page tables) that must be allocated
3. Context switching is costly.
- Implict and explicit costs as we talked about
Need something more lightweight
1. What’s similar in these processes ?
- They all share the same code and data (address space)
- They all share the same privileges
- They share almost everything in the process
2. What don’t they share ?
- Each has its own PC, registers, and stack pointer
3. Idea : Why don’t we separate the idea of process (address space, accounting, etc.) from that of the minimal “thread of control” (PC, SP, registers) ?
Threads and Processes
1. Most operating systems therefore support two entities :
- The process, which defines the address space and general process attributes
- The thread, which defines a sequential execution stream within a process
2. A thread is bound to a single process.
- For each process, however, there may be many threads.
3. Threads are the unit of scheduling
4. Processes are containers in which threads execute
Multithreaded Processes
Threads vs Processes
Threads
- A thread has no data segment or heap
- A thread cannot live on its own, it must live within a process
- Inexpensive creation
- Inexpensive context switching
- If a thread dies, its stack is reclaimed
Processes
- A process has code/data/heap & other segments
- There must be at least one thread in a process
- Expensive creation
- Expensive context switching
- If a process dies, its resources are reclaimed & all threads die
Conundrum
Can you achieve parallelism within a process without using threads ?
Thread scheduling
A cooperative thread gets to runs until it decides to give up the CPU
main()
{
tid t1 = CreateThread(fn, arg);
…
Yield(t1);
}
fn(int arg)
{
…
Yield(any);
}
Cooperative Threads
- Cooperative threads use non pre-emptive scheduling
- Advantages :
- Simple. Scientific apps
- Disadvantages : For badly written code
- Scheduler gets invoked only when Yield is called
- A thread could yield the processor when it blocks for I/O
Non-Cooperative Threads
- No explicit control passing among threads
- Rely on a scheduler to decide which thread to run
- A thread can be pre-empted at any point
- Often called pre-emptive threads
- Most modern thread packages use this approach
Multithreading models
1. There are actually 2 level of threads :
2. Kernel threads :
- Supported and managed directly by the kernel.
3. User threads :
- Supported above the kernel, and without kernel knowledge
Kernel Threads
Kernel threads may not be as heavy weight as processes, but they still suffer from performance problems :
1. Any thread operation still requires a system call.
2. Kernel threads may be overly general
- To support needs of different users, languages, etc.
3. The kernel doesn’t trust the user
- There must be lots of checking on kernel calls
User-Level Threads
1. The thread scheduler is part of a user-level library
2. Each thread is represented simply by:
- PC
- Registers
- Stack
- Small control block
3. All thread operations are at the user-level:
- Creating a new thread
- Switching between threads
- Synchronizing between threads
Multiplexing User-Level Threads
1. The user-level thread package sees a “virtual” processor(s)
- It schedules user-level threads on these virtual processors
- Each “virtual” processor is implemented by a kernel thread (LWP)
2. The big picture :
- Create as many kernel threads as there are processors
- Create as many user-level threads as the application needs
- Multiplex user-level threads on top of the kernel-level threads
3. Why not just create as many kernel-level threads as app needs ?
- Context switching
- Resources
Many-to-One Model
Thread creation, scheduling, synchronization done in user space. Mainly used in language systems, portable libraries.
- Fast - no system calls required
- Few system dependencies, portable
- No parallel execution of threads - can’t exploit multiple CPUs
- All threads block when one uses synchronous I/O
One-to-one Model
Thread creation, scheduling, synchronization require system calls. Used in Linux Threads, Windows NT, Windows 2000, OS/2
- More concurrency
- Better multiprocessor performance
- Each user thread requires creation of kernel thread
- Each thread requires kernel resources; limits number of total threads
Many-to-Many Model
If U < L? No benefits of multithreading. If U > L, some threads may have to wait for an LWP to run
- Active thread - executing on an LWP
- Runnable thread - waiting for an LWP
A thread gives up control of LWP under the following :
- Synchronization, lower priority, yielding, time slicing
Two-level Model
1. Combination of one-to-one + “strict” many-to-many models
2. Supports both bound and unbound threads
- Bound threads - permanently mapped to a single, dedicated LWP
- Unbound threads - may move among LWPs in set
3. Thread creation, scheduling, synchronization done in user space
4. Flexible approach, “best of both worlds”
5. Used in Solaris implementation of P threads and several other Unix implementations (IRIX, HP-UX)
User-Level vs. Kernel Threads
User-Level :
- Managed by application
- Kernel not aware of thread
- Context switching cheap
- Create as many as needed
- Must be used with care
Kernel-Level :
- Managed by kernel
- Consumes kernel resources
- Context switching expensive
- Number limited by kernel resources
- Simpler to use
Key issue : Kernel threads provide virtual processors to user-level threads, but if all of kernel threads block, then all user-level threads will block even if the program logic allows them to proceed.
Example User Thread Interface
t = thread_fork(initial context)
create a new thread of control
thread_stop()
stop the calling thread, sometimes called thread_block
thread_start(t)
start the named thread
thread_yield()
voluntarily give up the processor
thread_exit()
terminate th calling thread, sometimes called thread_destroy
Key Data Structures
Multithreading Issues
Semantics of fork() and exec() system calls
1. Thread cancellation
- Asynchronous vs. Deferred Cancellation
2. Signal handling
- Which thread to deliver it to?
3. Thread pools
- Creating new threads, unlimited number of threads
4. Thread specific data
5. Scheduler activations
- Maintaining the correct number of scheduler threads
Thread Hazards
int a = 1, b = 2, w = 2;
main() {
CreateThread(fn, 4);
CreateThread(fn, 4);
while(w) ;
}
fn() {
int v = a + b;
w--;
}
Concurrency Problems
A statement like w-- in C (or C++) is implemented by several machine instructions :
load reg, #w
add reg, reg, -1
store reg, #w
Now, imagine the following sequence, what is the value of w ?
load reg, #w
______________
______________
______________
add reg, reg, -1
store reg, #w
______________
load reg, #w
add reg, reg, -1
store reg, #w