by Scott Banks for a lecture by Professor Paul Eggert on April 24, 2012
Threads are like processes, but share memory, file descriptors, owner, etc.
Threads do not share: IP, other registers, and stack.
Process Memory +========+ + + + + + + +========+ + + <- Stack for Thread 1 +========+ + + <- Stack for Thread 2 +========+ + + + + + + +========+
+ Speed (more CPUs)
+ Easier, faster, inter-thread communication vs. inter-process communication
+ Threading can be used as a modularization technique
- Race conditions galore, especially concerning shared memory. These are hard to debug.
int pthread_create(pthread_t *ID, const pthread_attr_t *attr, void * (*f)(void *), void *arg);
int pthread_join(pthread_t ID, void *status);
int pthread_exit(void *status);
Typically, # threads > # CPUs
In cooperative multithreading, each thread must yield every now and then. There should be no long-running loops without yielding. The old MacOS used this model of threading.
while(busy(dev)) continue;
This is only suitable for fast devices.
while(busy(dev)) yield();
This is suitable for slower devices, but doesn't scale well to lots of threads.
while(busy(dev)) wait_for_ready(dev);
This scales better to 1,000s of threads, but is more complex.
Timer interrupts for preemptive multithreading
+ No longer require yield()
all over the place
- Threads can no longer assume code without yields is "safe" (bad for real time)
- More race conditions
States of a thread:
Associated with each resource is a queue of threads waiting for it. This is maintained by a "next" field in each thread descriptor.
What happens if a signal occurs in the middle of a syscall?
errno == EINTR
, app must retryaio_read()
to schedule a read requestMain program example:
for(;;){ // Wait for events pselect(...) // Invoke its callback }
+ Fewer race conditions
- One core only
Mechanism - details of clock interrupt, thread descriptor, RETI to resume a thread
Policies - how to decide which to run
Scheduling is important for the CPU, disk arm, network device, etc.
Developed for auto manufacturing!
Auto manufacturing analogy: an order for cars is received at the factory
There is a context switch time: this is the time it takes to switch from one task to another.
Example:
Job | Arrival Time | Run Time | Wait Time | Turnaround Time |
---|---|---|---|---|
A | 0 | 5 | Δ | 5 + Δ |
B | 1 | 2 | 4 + 2Δ | 6 + 2Δ |
C | 2 | 9 | 5 + 3Δ | 14 + 3Δ |
D | 3 | 4 | 13 + 4Δ | 17 + 4Δ |
Avg: | 5.5 + 2.5Δ | 10.5 + 2.5Δ |
The job is run as follows:
ΔAAAAAΔBBΔCCCCCCCCCΔDDDD
Total Time: 20 + 4Δ
Utilization: 20/(20 + 4Δ)
FCFS Characteristics:
Assumes job length is known.
The above example would be run as follows:
ΔAAAAAΔBBΔDDDDΔCCCCCCCCC
Job | Wait Time | Turnaround Time |
---|---|---|
A | Δ | 5 + Δ |
B | 4 + 2Δ | 6 + 2Δ |
C | 9 + 4Δ | 18 + 4Δ |
D | 4 + 3Δ | 8 + 3Δ |
Avg: | 4.25 + .5Δ | 9.25 + 2.5Δ |
Total time: same as before
Utilization: Same as before
SJF Characteristics: