Project 1 hint of the week: If you're getting really bizarre memory errors in your project, and you've changed around classes in header files or added header files into existing code files, try running make depend before running make again. It may be that some of your code isn't being automatically recompiled, and so different code has different ideas about what a class looks like.
You should be covering this material in lecture tomorrow. But here's a really condensed version, since it may help you with the project.
Recall that Nachos only uses a single processor, so disabling interrupts is enough to guarantee atomicity. This is what you'll want to use in the first part of the project, implementing locks and condition variables. For everything else, you'll be using locks and condition variables, and not dealing with interrupts directly again.
In lecture last time, we saw that locks can be used to prevent concurrent access to the same data structures from multiple threads. The locks you implement should be blocking—if another thread holds the lock already, you should put the current thread to sleep rather than spinning in a loop. The existing code for semaphores should give you a good idea how to do this.
(An aside on semaphores: they should also be covered in lecture soon, but they're fairly simple. A semaphore is much like a lock, except that it has a count of the number of times it can be acquired before blocking. With the counter set to 1, a semaphore is just like a lock, except that we don't require the same thread to release the lock as acquired it. How might this be useful?)
Let's try to implement a properly-synchronized list class. This is based on the code from synchlist.cc in Nachos:
void
SynchList::Append(void *item)
{
lock->Acquire();
list->Append(item);
lock->Release();
}
void *
SynchList::Remove()
{
void *item;
lock->Acquire();
// Wait until the list is non-empty
while (list->IsEmpty()) {
lock->Release();
currentThread->Yield();
lock->Acquire();
}
item = list->Remove();
lock->Release();
return item;
}
This code should work, but is inefficient. Consider what happens if the list is empty, one thread calls Remove(), and no other thread adds data to the list for a long time.
Note that Remove() is waiting for a condition to become true—that the list is not empty. A condition variable is a synchronization primitive used in situations like this. We'll use a condition variable to wait until the empty-ness of the list has changed, rather than using a busy-wait. Whenever another thread does something that might affect the condition we're waiting for, it has to say so by calling Signal() on the condition variable. Our code will look like this now:
void
SynchList::Append(void *item)
{
lock->Acquire();
list->Append(item);
listEmpty->Signal(lock);
lock->Release();
}
void *
SynchList::Remove()
{
void *item;
lock->Acquire();
// Wait until the list is non-empty
while (list->IsEmpty()) {
listEmpty->Wait(lock);
}
item = list->Remove();
lock->Release();
return item;
}
The semantics of Wait() are: sleep until some other thread calls Signal() or Broadcast() on the same condition variable, and then continue running. Multiple threads could have called Wait() on the same condition variable; the difference between Signal() and Broadcast() is that the first will only wake up one such thread, and the second will wake up all threads. If no threads are waiting, then these functions do nothing—the condition variable does not "remember" that Signal() was called in the past the next time a thread tries to Wait().
Note that we hold the lock to the list data structure (the data structure we're using the compute the wait condition, list->isEmpty()). Wait() will automatically release this lock when going to sleep, so another thread can acquire it, and Wait() will automatically reacquire the lock after waking up, so that we don't have to. This is why we need to specify a lock with all the condition variable methods.
Note that we put Wait() inside a while-loop in our code. We do this because we are not guaranteed that the condition is true when Wait() returns. (Why? What could happen without the loop?) Think of waking up from Wait() as a hint, nothing more. A good way to reason about correctness here is that inserting extra Signal()s at random places or changing Signal() to Broadcast() shouldn't affect the behavior of your code, just its performance.
We'll briefly cover transactional memories in discussion. This is a hot research area in computer architecture, and provides a nice, easy alternative to using explicit locks—though there aren't yet any computers you can buy that have it. Jeremy Lau has some notes up with more details about it.
If we have time, we may discuss some of these questions in discussion. Feel free to think about them ahead of time, though don't worry if you don't have the chance.