4.3.0.1 Idle

When run queues are empty, a silly idle shuttle is run. Such shuttle watches for run queue changes and launches a new run queue as soon as needed.

This is mostly an issue for non boot processors, because the \uk{} installs by hand an initial run queue for OS init modules at boot time in the boot processor.

Hence, the implementation of start differs for boot and non-boot processors. On boot processors, nothing special is done. On non-boot processors we start by executing an idle shuttle it. The job is done by the machine dependent start method.

<Start idle shuttle on non-boot processors. >= (<-U)
p_mdep.start(NULL);             // Create and pass an indle shuttle 
                                // for secondary processors. 

\subsubsection{The heartbeat}

Processors scheduling is done using a the hardware clock interrupt. As each processor uses its clock interrupt for scheduling, each processor contains a timer server to re-export virtual clock interrupts.

<Other public methods of off_Processor. >+= (<-U) [<-D->]
inline off_TmrSrv    &get_tmr(void)     {assert(valid()); return p_tmr; }

<Other private members of off_Processor. >+= (<-U) [<-D->]
off_TmrSrv    p_tmr;            // Timer server.

<Start other members of off_Processor according to mdep. >+= (<-U) [<-D->]
p_tmr.protect(get_protection());
{
  off_mdepTmrSrv mtmr;
  p_tmr.start(mtmr,nd.get_server_id());
}

<Off processor dependencies. >+= (U->) [<-D->]
#include <hw/TmrSrv.h>          // for off_TmrSrv

The very first time a run queue slot is allocated, a periodic timer is started to raise clock interrupts.

The timer is started by the start_clk private method.

<Other private methods of off_Processor. >= (<-U)
// Starts the clock (a timer, actually) to interrupt this processor. 
void start_clk(void);

As such a timer is likely to be always set with a fixed period, the timer server provides special code to handle it.

<off_Processor::start_clk implementation. >= (U->)
// Starts the clock (a timer, actually) to interrupt this processor. 
void off_Processor::start_clk(void)
{
  p_tmr.alloc_pclk(OFF_TICKS_PER_QUANTUM);
}

When the timer server alloc_clk is called a periodic timer serviced by the timer server itself is created. The number of clock ticks per quantum is a new system limit.

<Off limits. >= [D->]
// Number of ticks in a quantum. 
const int OFF_TICKS_PER_QUANTUM=1000;

Whenever such timer expires, it calls the current Processor new_quantum method.

<Other public methods of off_Processor. >+= (<-U) [<-D->]
// Starts a new quantum.
void new_quantum(void);

To start a new quantum we must obtain the identifier of the next shuttle to be run, and switch to it.

<off_Processor::new_quantum implementation. >= (U->)
// Starts a new quantum.
void off_Processor::new_quantum(void)
{
  off_Shtl *next;
  <off_Processor::new_quantum local variables. >
  <Obtain a reference to the next shuttle. >
  <Switch to the next shuttle. >
}

Such shuttle is the one the next shuttle in the run queue is yielding to. If such shuttle is running or blocked a new one must be selected.

The run queue is scanned in a round-robin fashion; hence, we maintain a pointer to the current slot (and another to the current shuttle).

<Other private members of off_Processor. >+= (<-U) [<-D->]
natural_t p_curslot;            // Current run queue slot.
off_Shtl *p_current;            // Current shuttle.

<Initialize other aggregate members of off_Processor. >+= (<-U) [<-D->]
p_curslot(0),p_current(NULL),

<Other public methods of off_Processor. >+= (<-U) [<-D->]
// Returns the shuttle being run.
off_Shtl *get_current(void);

<off_Processor::get_current implementation. >= (U->)
// Returns the shuttle being run.
off_Shtl *off_Processor::get_current(void)
{
  return p_current;
}

<Off processor dependencies. >+= (U->) [<-D->]
class off_Shtl;

<Off processor late dependencies. >= (U->)
#include <shtl/Shtl.h>          // for off_Shtl

<Obtain a reference to the next shuttle. >= (<-U)
next=NULL;
count=p_alloc.get_nalloc();
do {
  off_shtl_id_t nextid;
    if (++p_curslot >= p_alloc.get_nalloc())
      p_curslot=0;
    nextid=((*this)+p_curslot)->get_shtl();
    do {
      shtl.make_available(nextid);
      next=shtl+(natural_t)nextid;
      if (next->is_yielding())
        nextid=next->yields_to();
    } while(!next->is_yielding());
} while(count-- && next->is_blocked());
if (!count)
  next=NULL;                    // XXX select idle shuttle then.

<off_Processor::new_quantum local variables. >= (<-U) [D->]
natural_t count;

Once we have a reference to the next shuttle to be run, we switch to it.

<Switch to the next shuttle. >= (<-U)
now=p_current;
p_current=next;
now->switch_to(next);

<off_Processor::new_quantum local variables. >+= (<-U) [<-D]
off_Shtl *now;

\subsection{Time slice allocation}

Time slices are allocated from a RqAllocator which is a subclass of a FixedAllocator instantiated to allocate RunqSlots.

<Off time slice allocator. >= (U->)
// A time slice allocator. 
//
class off_RqAllocator : public off_TFixedAllocator<off_LRunqSlot> {
public: 
  const off_RqAllocator &operator=(const off_RqAllocator &other) { 
    return (*this=other);
  }
  
  <Other public methods of off_RqAllocator. >
private:
  <Other private members of off_RqAllocator. >
};

Defines off_RqAllocator (links are to index).

<Off time slice allocator dependencies. >= (U->) [D->]
#include <klib/FixedAllocator.h> // for off_TFixedAllocator et al.

To support the linked lists used in the fixed allocator, nodes allocated are actually of type LRunqSlot.

<Off linkable run queue slot. >= (U->)
// A linkable run queue slot.
//
class off_LRunqSlot : public DLinkedNode {
public:
  off_RunqSlot l_ts;
  
  // To allow uninitialized run queue slots. 
  off_LRunqSlot(void) : l_ts() {;}

  <Other public methods of off_LRunqSlot. >
};

Defines off_LRunqSlot (links are to index).

<Off time slice allocator dependencies. >+= (U->) [<-D->]
#include <hw/RunqSlot.h>        // for off_RunqSlot

The fixed allocator uses a fixed array of LRunqSlots

<Other private members of off_RqAllocator. >= (<-U) [D->]
off_LRunqSlot r_ts[OFF_NRQS_MAX]; // Run queue slots.  

where OFF_NRQS_MAX is the maximum number of time slices in a run queue, which is a system limit.

<Off limits. >+= [<-D]
const int OFF_NRQS_MAX = 64;    // Max. number of run queue slots. 

Defines OFF_NRQS_MAX (links are to index).

<Off time slice allocator dependencies. >+= (U->) [<-D->]
#include <klib/limits.h>        // ofr OFF_NRQS_MAX

An indexer is also needed.

<Other private members of off_RqAllocator. >+= (<-U) [<-D]
static off_Indexer<off_LRunqSlot> r_idx; // Linked slot indexer.

<Off time slice allocator static members. >= (U->)
off_Indexer<off_LRunqSlot> off_RqAllocator::r_idx; // Linked slot indexer.

<Off time slice allocator dependencies. >+= (U->) [<-D]
#include <klib/Indexer.h>       // for off_Indexer

Now we can state how the slot allocator is created. Only a revocation trigger must be supplied.

<Other public methods of off_RqAllocator. >= (<-U) [D->]
// Creates a run queue slot allocator.
off_RqAllocator(off_Exhausted *r);

<off_RqAllocator::off_RqAllocator implementation. >= (U->)
// Creates a run queue slot allocator.
off_RqAllocator::off_RqAllocator(off_Exhausted *r) :
  off_TFixedAllocator<off_LRunqSlot>(r, (const off_Indexable*)&r_idx,
                                     r_ts,OFF_NRQS_MAX)
{;}

The array of LRunqSlots is initialized when the processor is instantiated using the processor itself as a revocation trigger.

<Initialize p_alloc. >= (<-U)
p_alloc((off_Exhausted*)this)

As of today there is no revocation for time slices.

<Other public methods of off_Processor. >+= (<-U) [<-D->]
// Notifies that run queue is exhausted.
void notify(void) { return; }

Using this allocator, a processor can allocate memory for run time slots.

<Other public methods of off_Processor. >+= (<-U) [<-D->]
// Allocates a run queue slot. 
off_RunqSlot *alloc(boolean_t use_revocation=FALSE);

// Deallocates a run queue slot. 
void free(const off_RunqSlot *rq);

<off_Processor::alloc and free implementation. >= (U->)
// Allocates a run queue slot. 
off_RunqSlot *off_Processor::alloc(boolean_t use_revocation)
{
  off_LRunqSlot *lts;
  assert(valid());
  w_lock();
  lts=p_alloc.allocate(use_revocation);
  w_unlock();
  return (lts)?(&lts->l_ts):(off_RunqSlot*)NULL;
}

// Deallocates a run queue slot. 
void off_Processor::free(const off_RunqSlot *ts)
{
  off_LRunqSlot *lts=(off_LRunqSlot*)(((char*)ts)-(int)&off_LRunqSlot::l_ts);
  assert(valid() && ts);
  w_lock(); 
  p_alloc.deallocate(lts); 
  w_unlock(); 
}

Run queue slots have their own new and delete operators. The operator new receives the processor where the slot should be allocated. Operator new uses its alloc method to find an available slot.

<Other public methods of off_RunqSlot. >+= (<-U) [<-D->]
// Allocate a run queue slot.
void *operator new(size_t s, off_Processor *p,
                   boolean_t use_revocation=FALSE);
// Deallocates this run queue slot.
void operator delete(void *p);

<off_RunqSlot::operator new implementation. >= (U->)
// Allocate a run queue slot.
void *off_RunqSlot::operator new(size_t s, off_Processor *p,
                                 boolean_t use_revocation)
{
  off_RunqSlot *ts=p->alloc(use_revocation);
  (void)s;
  assert(s && p);
  assert(!ts || ts->valid());
  return (void*)ts;
}

The operator delete does what could be expected.

<off_RunqSlot::operator delete implementation. >= (U->)
// Deallocates this run queue slot.
void off_RunqSlot::operator delete(void *p)
{
  off_RunqSlot *ts=(off_RunqSlot*)p;
  assert(ts && ts->valid());
  ((off_Processor*)(ts->get_container()))->free(ts);
}

Run queue slots must be pre-initialized. Pre-initialization is done when the processor is started.

<Start other members of off_Processor according to mdep. >+= (<-U) [<-D]
for (natural_t ts=0; ts< get_nslots(); ts++){
  off_ts_id_t tsid(get_id(),ts);
  (void) new(p_alloc+ts) off_LRunqSlot(tsid,this);
}

Again, we use a tricky new operator.

<Other public methods of off_LRunqSlot. >= (<-U) [D->]
void *operator new(size_t s, off_LRunqSlot *ts) { (void)s; return (void*)ts; }

The LRunqSlot constructor pre-initializes each slot in turn

<Other public methods of off_LRunqSlot. >+= (<-U) [<-D]
off_LRunqSlot(const off_ts_id_t &id, off_Processor *p) : l_ts(id,p) {;}

using a pre-initialization constructor for RunqSlots.

<Other public methods of off_RunqSlot. >+= (<-U) [<-D]
off_RunqSlot(const off_ts_id_t &id, off_Processor *p) :
  off_HWResUnit(id,OFF_MAGIC_RQSLOT,(off_HWCompResource*)p)
{;}

Using the allocator, processors implement these operators to access existing run queue slots.

<Other public methods of off_Processor. >+= (<-U) [<-D->]
//Gets a run queue slot from its distributed or physical address.
inline off_RunqSlot *operator+(vm_offset_t s);

<off_Processor::operator+ implementation. >= (U->)
//Gets a run queue slot from its distributed or physical address.
inline off_RunqSlot *off_Processor::operator+(vm_offset_t s)
{
  return &(p_alloc+s)->l_ts;
}

The implementation uses a redefinition of the operator in the allocator to do it more efficiently.

<Other public methods of off_RqAllocator. >+= (<-U) [<-D]
//Gets a run queue slot from its distributed or physical address.
inline off_LRunqSlot *operator+(vm_offset_t s);

<off_RqAllocator::operator + implementation. >= (U->)
//Gets a run queue slot from its distributed or physical address.
inline off_LRunqSlot *off_RqAllocator::operator+(vm_offset_t s)
{
  return r_ts+s;
}

\subsection{Processor navigation and inspection}

NOTE: XXX Not yet implemented.