CS 111 Lecture 7 4/24/2012

Threads VS Processes

• Threads are like precesses but they do not have enough resources.
• They share memory, file descriptor, and owner...etc
• They do not share instuction pointer, registers, and stack.

A process contains multithreads.

Pros of using threads:

• + speed ( more CPUs) ¡V we can solve faster
• + easier and faster(Inter Thread Communication > Inter Process Communication)

Cons of using threads:

• - race conditions galare(especially shared memory)
• - hard to debug!

POSIX threads

 int pthread_create(pthread_t *ID, const pthread_t *attr, void*(*f)(void*), void*status); 

 int pthread_join(pthread_t ID, void *status); 

 int pthread_exit(void *status); 

How to control threads?

Typically n threads > n CPUS (We are going to have more threads running than CPUS)

There are two approches

1. A) Cooperative multithreading (ex old Mac OS)


2. B) Preemptive multithreading

Cooperative multithreading

• I/O
- busy waiting

 
     while(busy(dev))
	
	continue;
  
 => This is valid only for fast devices.  

• Polling
-more common approach but it is not good for a lot of threads

     while(busy(dev))

	yield();

 => This does not scale well to lots of threads. 

• Blocking

     while(busy(dev))
	
        wait_for_ready(dev);


=> Pros: scale better to a lot of threads 
   Cons: more complicated 

State of a thread:

1. 1. running ( has a CPU)
2. 2. runnable but not running
3. 3. blocked waiting for resources R(device, pipe, on thread)
so associated with each resource is a queue of threads waiting for it. ( maintained by a next field in each thread descriptor)

Preemptive multithreading

Timer interrupt for preemptive multithreading

• motherboard clock periodically signals CPU
-> every 10 ms(to beat human reaction time)
• CPU traps via the clock interrupt entry in the IDT(Interrupt Descriptor Table)
• kernel has control
• save context of the ¡¥recalcitrant¡¦ thread.
• Can restore some other context

pros: no longer require yield() all over the placecons: threads can no longer assume code without yield() is ¡§safe¡¨(bad for real time)(ie. More race conditions)

Aside on signals

What happen if a signal in middle of syscall?ex) Write(...)

Normal solution

signal delivered only when syscall returns, but this approach is fail because of slow syscalls

• -syscall fails with erron ==EINTR
=>app must retry
• -signal handlers fire in the middle of syscall
=>Kernel must now be able to restore a process, that¡¦s in the middle of a syscall

Event driven programming (inverse of threads)

• divide your program in to callbacks
• each triggered by a event
• callbacks never block so there is no waiting. There is no syscall like read, write, waitpid.
• instead: schedule a request and terminate

aio_read() 

callback invoked when read is done.

	         for(;;){						wait for event                              						pselect(....)							invoke its callback				}

Pros: fewer race conditions
Cons: one core only

Scheduling problem:

we are scheduling a CPU

• -mechanism ¡V details of clock interrupt ,thread decription, decide to when RETI to resume a thread
• -policies ¡V how to decide which to run
(CPU, disk arm, network devices, ¡K.)

scheduling scale

• Long term
- which processes or threads will we admit to the system?
Admission control
• Medium term
- which processes reside in RAM? Which on disk?
• Short term
¡Vwhich threads get a CPU?(as known as the dispatching problem)
We want it to be simple and fast and easy to understand

Scheduling metrics(developed for auto manufacturing)

Statistic:

• Avg(wait time)
• Worstcase(x time)
• utilization : % of CPU devoted to useful work
• throughput: # cars/day

Simple scheduling algorithm : first come first serve (FCFS)

Pros:This favors Long job
Cons:This causes convey effect

Shortest Job First (SJF)

Pros: no convoys effects
Cons: Starvation
-it was not fair!