ThreadMentor: Alarm Clock

Problem

This problem is due to C. A. R. Hoare in his seminal paper, "Monitor: an Operating System Structuring Concept", published in Communications of ACM, Vol. 17 (1974), No. 10, pp. 549-557. Suppose a number of sleeper threads wish to slumber for various number of times. To make sure they will wake up on time to go to work, they use a very primitive alarm clock. It is so primitive that can only wake up the sleeper who is the closest to the clock, and cannot be set hourly. So, the sleepers have the following agreements:

• The alarm clock only wakes up the closest sleeper.
• When a sleeper is up, he wakes up his neighbor and checks if it is the actual time for him to go to work. If it is, he gets up and goes to work; otherwise, he goes back to sleep.

Analysis

There are two important events from the point of view of the sleeper threads and the clock thread. The first event is that when a sleeper thread wishes to sleep, it invokes a method of the monitor. The second is for the clock to use. The clock thread periodically generates a clock tick and invokes a second method to pass this event into the monitor. Within the monitor, sleeper threads are blocked on a condition variable. When a clock tick comes in, a sleeper thread is released. This sleeper thread wakes up his neighbor and checks if this is the time to go to work. If it is not, he goes back to sleep.

Program

The following is the interface of our monitor. Condition variable Wake is for all sleeper threads to wait on. Private variable Now is the current time. This monitor has two methods. Method Slumber() takes an int argument n. This means this sleeper will sleep for n clock ticks. Method ClockTick() is used to receive external clock ticks.

#include "ThreadClass.h"

class AlarmMonitor : public Monitor
{
     public:
          AlarmMonitor(char* Name);   // constructor
          void Slumber(int  n);         
          void ClockTick();

     private:
          Condition Wake;
          int Now;                      // current clock
};

The implementation is not very difficult. Let us examine method ClockTick() first. When a clock tick comes in (i.e., this method is invoked), the current time Now, which is initialized to 0 by the constructor, is increased by 1, and wakes up the first sleeper with Wake.Signal(). Therefore, we may consider method ClockTick() as a clock interrupt handler.

Sleeper threads call method Slumber() when they wish to sleep. The argument n indicates the number of clock ticks. Therefore, the first thing to do is to set the alarm clock, which is equal to the sum of current time Now and the number of clock ticks n. The alarm clock is stored in AlarmCall. Note that AlarmCall is a local variable of method Slumber() rather than a global private variable of the monitor. In this way, every sleeper has his own wake-up time. Once the alarm clock is set, this sleeper thread enters the sleep/wake-up iteration until the current time is no less than the alarm clock time. For each iteration, this sleeper thread waits on condition variable Wake to simulate sleeping. When it is awoke by a signal, it immediately wakes up the next sleeper and checks time again. Hence, all threads waiting on condition variable Wake are released. They will check the time and go back to sleep again if necessary.

Here is a question for you to think over. What is this monitor is of Mesa type? How would you change the program to make it work? On a later page, we will introduce a new condition variable method Broadcast() that can simultaneously wake up all threads that are waiting on a condition variable. Of course, only one of them can run due to the mutual exclusion requirement of a monitor. Will this broadcasting capability simplify the solution?

#include <iostream.h>
#include "ThreadClass.h"
#include "alarmclock-mon.h"

AlarmMonitor::AlarmMonitor(char* Name)
             : Monitor(Name, HOARE), Wake("Wake")
{
     Now = 0;            // reset the clock
}

void AlarmMonitor::Slumber(int  n)
{   
     int  AlarmCall;

     MonitorBegin(); 
     AlarmCall = Now + n;          // wake up after n calls
     while (Now < AlarmCall) {     // not time to wake up
          Wake.Wait();             // goes back to sleep
          Wake.Signal();           // wake up another sleeper
     }                             // so that he could check time
     MonitorEnd();                 
}

void AlarmMonitor::ClockTick()
{
     MonitorBegin();          
     Now++;                   // advance timer
     Wake.Signal();           // cascading wake-up
     MonitorEnd();            
}

Now let us see the thread interface. As discussed earlier, we have two types of threads: clock and sleepers. The clock thread is declared as a DriverThread and the sleeper threads are SleeperThread.

#include "ThreadClass.h"

class DriverThread: public Thread
{
     public:
          DriverThread();     // constructor

     private:
          void ThreadFunc();
          int  iteration;
};

class SleeperThread: public Thread
{
     public:
          SleeperThread(int No, int Iteration);     // constructor

     private:
          void ThreadFunc();
          int  number;
          int  iteration;
};

The structure of these threads is extremely simple. The SleeperThread iterates Iteration times. In each iteration, a "go to work" message is displayed, delays for a while to simulate working, and then goes to sleep by invoking method Alarm.Slumber(number), where number is a number assigned to this sleeper thread. Thus, if a thread receives 3 when it is created, this thread will sleep for 3 clock ticks (i.e., alarm clock goes off three times). The DriverThread iterate indefinitely. In each iteration, it delays for a fix amount of time, and sends out a clock tick (i.e., alarm clock goes off) by invoking method Alarm.ClockTick().

Note that monitor Alarm is declared as a static variable. Hence, it can only be used in this file and is invisible to other files. In this way, we can hide the monitor from other functions.

#include <iostream.h>
#include "ThreadClass.h"
#include "alarmclock-Thrd.h"
#include "alarmclock-mon.h"

static AlarmMonitor Alarm("AlarmClock");

strstream *Filler(int n)
{
     int  i;
     strstream *Space;

     Space = new strstream;
     for (i = 0; i < n; i++)
          (*Space) << ' ';
     (*Space) << '\0';
     return Space;
}

SleeperThread::SleeperThread(int No, int Iteration)
{
     number = No;
     iteration = Iteration;
     ThreadName.seekp(0, ios::beg);
     ThreadName << "SleeperThread" << No << '\0';
}

void SleeperThread::ThreadFunc()
{
     Thread::ThreadFunc();
     strstream *Space;

     Space = Filler(this->number);
     for (int i = 1; i <= iteration; i++) {
          cout << Space->str() << ThreadName.str() 
               << " is going to work" << endl;
          Delay();                 // go to work
          Alarm.Slumber(number);   // sleep
     }
     Exit();
}

DriverThread::DriverThread()
{
     ThreadName.seekp(0, ios::beg);
     ThreadName << "DriverThread" << '\0';
}

void DriverThread::ThreadFunc()
{
     Thread::ThreadFunc();

     while (1) {
          Delay(1);             // Delay for a fixed amount of time
          Alarm.ClockTick();
     }
}

Finally, let us take a look at the main program. It requires two command line arguments. The first one gives the number of sleeper threads and the second provide the number of iterations a sleeper thread must perform. When the i-th sleeper thread is created, the number it receives is i+1, and, consequently, sleeper i sleeps for i+1 clock ticks. Note that the main program does not join with the driver thread. More precisely, when all sleeper threads complete, the main program uses Exit() to terminate, and the driver thread is terminated as a result.

#include <iostream.h>
#include "ThreadClass.h"
#include "alarmclock-Thrd.h"
#include "alarmclock-mon.h"

#define MAX_NUM   20     // max. number of sleeper threads

void main(int argc, char *argv[])
{
     SleeperThread *sleepthread[MAX_NUM];
     int NumberOfThreads;       // total number of threads
     int Iterations;
     int i;


     if (argc != 3) {              // verify user input
          cout << "Usage " << argv[0] << " #-of-Sleeper Threads"
               << " Iterations" << endl;
          exit(0);
     }
     else {
          NumberOfThreads = abs(atoi(argv[1]));
          Iterations      = abs(atoi(argv[2]));
     }

     // create the increment/decrement threads in a random way
     for (i = 0; i < NumberOfThreads; i++) {      // create threads
          sleepthread[i] = new SleeperThread(i + 1, Iterations);
          sleepthread[i]->Begin();
     }

     DriverThread driverthread;
     driverthread.Begin();

     for (i = 0; i < NumberOfThreads; i++)   
          sleepthread[i]->Join();
     Exit();
}