Scribe: Phillip Woytowitz
The basic idea here is that with preemptive scheduling (also known as "Round Robin" scheduling), each task that comes in gets a time slot of, lets say, 10 ms. A task gets to run for 10 ms, and once that time interval is finished, another process runs for its 10 ms time slot. Each of the incoming tasks get run in spurts and take their turns.
If A, B, C, and D are incoming tasks, then their execution with preemptive sceduling may look like this:
ABCDABCDACDACDBADAC
What's nice about this is that the average wait time for any task coming in is low.
There are two approaches with regards to Round Robin Sceduling. There is:
The "Rude" Round Robin would be easier to implement since we have a queueing system already in place. The "Polite" Round Robin approach, in addition to being somewhat more difficult to implement, suffers from the possibility of being able to starve its processes.
The main problem with threads in general is that they can share memory and step on each others' toes. As software engineers, the problem we must solve is how to handle synchronization, i.e., how to arrange thread execution such that no one steps on anyone else's stuff. Because by default, threads are unsynchronized and WILL stomp of each others' work.
Let's look at some code for a program that manipulates Bill Gates's bank account:
long long int balance = 0; //big enough for Bill Gates
//now for some primitives
void deposit (long long int amt)
{
balance += amt;
}
bool withdraw(long long int amt)
{
if(amt <= balance)
{
balance -= amt;
return 1;
}
else
return 0;
}
Let's say that thread 1 wants to call withdraw(10000) and thread 2 wants to call deposit(50000). One thing that could go wrong is that we could lose track of the $50 dollar deposit. If we look at the machine code:
bool withdraw(long long int amt)
{
if(amt <= balance) //movq balance, %rax; cmpq %rax, amt
{
balance -= amt; //subq amt, %rax; movq %rax, balance
return 1;
}
else
return 0;
}
The deposit thread can run after the withdraw thread moves its perceived value of balance into its register (movq balance, %rax). By the time it writes back the balance value from its register, it will have returned an outdated one that never saw a $50 dollar deposit! This sort of issue is often referred to as a race condition.
We could try to fix this by declaring balance as a volatile variable, but even this wont prevent the compiler from trying to cache it. Here's an idea:
[[if(amt <= balance)
{
balance -= amt; movq balance %rax]]
Let's try to run this without colliding with another thread
One approach we could take would be to add a machine instruction for every action that want to do that might collide with some other thread (we'll call these actions critical sections). Another option would be to add 2 machine instructions, one to indicate the beginning of the critical senction and one to indicate the end of the critical section. Both can work and both have been used, but the 2nd approach seems more general, so we'll start with this.
Suppose we have these two instructions. Here are some potential problems that can occur while using this approach:
Pipe() is usually a system call. These pipes we're making will live in user space (no kernel involvement). Once we have a our data structures and primitives defined for this pipe, we'll have threads operate on them and figure out where the critical sections are in our code.
enum {N = 1024} //size of a pipe
struct pipe { //1 byte I/O
char buf[N]; //buffer
unintmax_t R, W; //total number of reads and writes
};
void writec( struct pipe *p, char c)
{
while(pipe_full(p)) continue;
p->buf[p->W++%N] = c;
}
char readc( struct pipe *p )
{
while(pipe_empty(p) continue;
return p->buf[p->R++%N];
}
bool pipe_full(struct pipe* p)
{
return p->W - p->R == N;
}
If we have threads operate on this as is. We could probably pinpoint a few bugs. One thing that could happen is that 2 writers may be trying to write to the last byte. Once one reader gets through the pipe_full loop, before he updates the W variable, the other read can also get past the pipe_full loop and write to the buffer, even though it should already be full.
To synchronize our code, we'll bookend critical sections using this datatype and these two primitives:
typedef ... spinlock_t void lock (spinlock_t* l); void unlock (spinlock_t* l);
When we use these primitives to counter race conditions, we must follow a few rules:
The general strategy is going to be:
We must mark our critical sections to be big enough to prevent the race condition, but not so big that it hurts performance. In effect we are obeying a Goldilocks principle.
So how do we right-size a critical section?
Here are some shared writes in our pipe example in the writec function:
And a here is a dependent read:
But just putting the lock around the line p->buf[p->W++%N] = c; won't fix the race condition, for the while loop above it is actually a dependent read from the perspective of another thread. We could place another lock around the while loop, but this violates the bounded wait condition and will kill performance. What we must do to fix this is place the lock around the pipe_full check so that it locks and unlocks on each iteration of the loop:
spinlock_t l;
void writec(struct pipe* p, char c)
{
for(;;)
{
lock(&l);
if(!pipe_full(p))
break; //will maintain the lock needed for the writes
unlock(&l);
}
p->buf[p->w++%N] = c;
unlock(&l);
}
The only problem with this approach is that if we have several threads running different pipes, they'll be bottlenecked by the fact that we have a single lock handling all pipe synchronization. A single lock that handles access to a lot of data is called a coarse-grained lock. To fix this issue, we should use fine-grained locks, where we have more locks each controlling less data. To accomplish this, let's just give each pipe its own lock:
struct pipe {
...
spinlock_t l;
}
and update our existing lock and unlock calls with lock(&p->l) and unlock(&p->l).
So we've achieved fine-grain locking with our piping mechanism, but there's still an issue. If a pipe is full, we'll eat up a lot of our CPU polling for the lock's availability. We could replace the first unlock with a yield(), allowing another thread to get to work.
But now what we really want is a locking primitive that blocks if the resource isn't available. We'll call it a blocking mutex.
typedef ... bmutex_t void acquire( bmutex_t* b) get lock, but wait if already has lock (give up CPU) void try_acquire( bmutex_t* b) void release(bmutex_t* b)
So let's try to implement this:
void acquire( bmutex_t* b){
while(!try_acquire(b)
continue; //but wait... this in effect is still spinning!
}
So how do we build these things? Next time...