CSE 120 Discussion Notes: Week 3

Reminders

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.

Locks and Condition Variables: A Crash Course

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.

Transactional Memory

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.

Questions to Consider

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.

  1. fork() is very often followed almost immediately by exec() on Unix. How can modern systems reduce the cost of copying all the memory of a process when forking? What might you do on older systems lacking support for virtual memory? For fun, try looking up the vfork() system call.
  2. The Unix C library was mostly developed before threading, and so many functions in it are not thread-safe. What does this mean? What types of problems can come up with using the global variable errno to report errors? How might you fix these problems?
  3. Each thread in a process needs its own stack. If we allocate many local variables on the stack, these stacks might need to be large. If we allocate, say, 8 MB of virtual address space for each thread's stack, and we support up to 2 GB of virtual address space per process, how many threads can we create per process? How might we increase this limit? What does Nachos do?
  4. Early versions of Java made it nearly impossible to write event-driven servers, because I/O was blocking. What effect might this have on the number of threads in a Java server? In light of this, why do you think Java implementations may have largely avoided a 1-to-1 mapping of Java threads onto kernel threads?
  5. What types of trouble could result if it were not necessary to hold a lock before calling Wait() on a condition variable?
  6. How could you extend the synchronized list example to place a limit on the number of elements in the list? A thread calling Append when the list is full should block until an element is removed. How many condition variables are needed?
  7. In the Java language, each object gets a single combined lock/condition variable. In Nachos, we can allocate any number of locks we want per object, and we can have any number of condition variables per lock. What are the advantages and disadvantages of each approach?