Due

Objectives

• to write low level code that manages threads
• to write high level code that manages threads
• to use thread synchronization methods

Introduction

For example, when using three threads to factor 1000, the first thread removes 1000 from the queue and factors it into 25 and 40, which it places back on the queue. The second thread then takes 25 off the queue while the third thread takes off 40. The second thread almost immediately factors 25 into 5 and 5, which it places back on the queue. Now the first thread can take one 5 off the queue while the second thread takes the other 5 off the queue. Those threads will output 5 since 5 is prime. Meanwhile, the third thread has been attempting to factor 40 and will eventually find factors 5 and 8. Now 5 and 8 go back on the queue where they will be retrieved by the first and second threads. Eventually 8 gets factored into 2 and 4, and 4 gets factored into 2 and 2 and then all the prime factors have been found.

(This is admittedly an overly complex way to find prime factors. It is intended to be a reasonable approximation of what some usefully multithreaded programs would do. For example, a web crawler might have a queue of URLs instead of a queue of numbers. The threads would take a URL off the queue, download the HTML code from that URL, parse the HTML to discover the links, and put those links back on the queue.)

The given code has two problems: threads wait for items to be added to an empty queue using a busy loop; and the threads have no way of knowing whether the queue is empty because other threads haven't produced smaller factors yet or if the queue is empty because all the prime factors have been found.

Assignment

Add code to the wait, notify, and notifyAll methods already outlined in object.cpp. Calling wait on an object should block the calling thread until notify or notifyAll is called on the same object. notify should unblock one arbitrarily chosen thread that is waiting on that object while notifyAll should unblock all threads that are waiting on that object. All three of these methods are most easily written by delegating their responsibilities to new methods added to the Thread and Scheduler classes. You will also have to add a blocked queue to the scheduler. The blocked queue should keep track of what threads are waiting and what objects they are waiting on. wait should suspend the thread that calls it and add that thread to the blocked queue. notifyAll should examine the blocked queue and move any threads that are waiting on the object to the ready queue; notify should move one such thread if one exists. wait will have to use assembly code that will look very much like the code for yield. The main difference will be that you will have call a new Scheduler method at the end of the new assembly code in place of the call to Scheduler::threadYielded in yield. That method should be passed two parameters: the address of the thread and the address of the object it is waiting on.

Once wait, notify, and notifyAll have been written, modify the code in IntQueue to make use of them. When a thread attempts to get an item from an empty queue, it should block on the queue. When a thread adds an item to the queue, it should wake up a thread that is waiting on that queue.

Finally, add additional code to IntQueue that will allow the threads to terminate once all prime factors have been found. One way to do this is to keep track of how many threads are currently processing numbers from the queue. This count would increase after each successfull dequeue and would decrease once the number dequeued has been factored or output. When the count is decreased to zero, you can wake up all threads waiting on the queue. When a thread is woken up and finds that the queue is empty and there are no threads processing numbers, it can exit.

Files

• thread.h
• thread.cpp
• thread_asm.asm
• scheduler.h
• scheduler.cpp
• scheduler_asm.asm
• factorizer.h
• factorizer.cpp
• object.h
• object.cpp
• intqueue.h
• intqueue.cpp
• pf_main.cpp

You can build the program with the commands

nasm -f elf thread_asm.asm
nasm -f elf scheduler_asm.asm
g++ -o p1.x thread_asm.o scheduler_asm.o thread.cpp scheduler.cpp factorizer.cpp object.cpp intqueue.cpp pf_main.cpp

Advice

The STL queue class is probably not suitable for the blocked queue since you can't iterate through an STL queue. You can use list instead.

Start by writing the Scheduler methods that will manipulate the queue of blocked threads. Test these methods before you tackle the assembly language code required for wait. For example, I wrote methods blockThread(Thread*, Object*), wakeupOne(Object*), wakeup(Object *), and printQueues() in my Scheduler class. Testing them with the code

int main(int argc, char **argv)
{
  // NamedThread is a simple subclass of Thread that stores a name so we
  // can print it in printQueues

  Thread *a = new NamedThread(std::string("a"));
  Thread *b = new NamedThread(std::string("b"));
  Thread *c = new NamedThread(std::string("c"));
  Thread *d = new NamedThread(std::string("d"));

  // NamedObject is a simple subclass of Object that stores a name so we
  // can print it in printQueues

  Object *o1 = new NamedObject(std::string("1"));
  Object *o2 = new NamedObject(std::string("2"));

  Scheduler::blockThread(a, o1);
  Scheduler::blockThread(b, o2);
  Scheduler::blockThread(c, o1);
  Scheduler::blockThread(d, o1);

  // all four threads will be blocked

  Scheduler::printQueues();
  std::cout << std::endl;

  Scheduler::wakeupOne(o1);
 
  // one thread (a) is ready, the rest are still blocked

  Scheduler::printQueues();
  std::cout << std::endl;

  Scheduler::wakeup(o1);

  // now three threads (a, c, d) are ready and b is still blocked

  Scheduler::printQueues();
  std::cout << std::endl;

  Scheduler::wakeup(NULL);

  // same as before

  Scheduler::printQueues();
  std::cout << std::endl;
}

READY QUEUE: 0 items
BLOCKED QUEUE
a waiting on 1
b waiting on 2
c waiting on 1
d waiting on 1
 
READY QUEUE: 1 items
BLOCKED QUEUE
b waiting on 2
c waiting on 1
d waiting on 1
 
READY QUEUE: 3 items
BLOCKED QUEUE
b waiting on 2
 
READY QUEUE: 3 items
BLOCKED QUEUE
b waiting on 2

Object's wait method can contain just the statement

Thread::block(this);

• move the address of the running thread (the one we are trying to block) from currentThread into a register (just like Thread::yield does);
• save its parameter (which at this point is 4 bytes above the top of the stack and is the address of the object the thread is blocking on) in another register;
• push the four callee-save registers (just like Thread::yield does); and
• invoke Scheduler::blockThread by pushing the address of the object followed by the address of the thread and then calling the method by its mangled name.

Grading

Your finished code should also be as efficient as possible. Avoid busy loops and avoid unblocking threads unnecessarily.

Submissions