Scheduler definition

Scheduler definition

Document formatted by vherva at Fri Apr 24 11:23:51 1998 on the host schemestation. This document is produced by the SchemeStation project during the Tik-76.115 course.

1 Introduction

The purpose of the SCHEMESTATION scheduler is to provide an interface to executing multiple agents in "parallel" - to provide VM time slicing. The scheduler decides whose turn it is to be executing on the VM and how many instructions are allowed to be executed before changing the VM context (agent, that is).

2 Scheduling policy

The default scheduling policy is pure round-robin; each agent is executed for a time quantum specified as priority (as many instructions as the priority specifies; e.g. if priority is 100, 100 instructions are executed) one after another in a fixed order so that no artifical ordering of agents is made.

This scheduling policy can be altered through external interface to the scheduler: it is possible to register callback functions to enforce another scheduling policy. The callbacks are:

  • Scheduler item insert
  • Scheduler item remove
  • Get next item to execute
  • Inform the status of the previous execution

Another service that the scheduler offers is status information of the agents; during the initialization of the scheduler a callback is registered so that when the status of an agent changes, this callback is executed with the new status as a parameter.

3 Implementation definition

The scheduler implementation is based on a list which holds the currently active agents and another list where the "dead" agents reside before they are released from outside the scheduler. The list implementation itself is of no particular importance - it could be replaced with another anytime, as long as the interface and the semantics do not change.

The scheduler list holds all necessary information for each agent to be executed independently by the scheduler. For statistics the number of executed instructions is stored as well as the status and identifier of the particular agent.

Due to the persistence feature in the SCHEMESTATION, the scheduler must be able to save its state to a file and read the state back so that it can continue operations without any notable changes after the restoration of the stored state.

4 Interface

4.1 Datatypes of the external interface

Each scheduler item must have these attributes set in order for the scheduler to be able to execute the code of the item

4.1.1 Note

The heap, registerset and byte_code are stored where they are allocated (instantiated) before passign them to the scheduler; they are not copied by the scheduler. This means that the responsibility of the release of these items is on the scheduler, unless it is removed from outside with the scheduler_remove().

The data structure that is to be passed to the scheduler for every item inserted is: 

typedef struct {
  Heap heap; /* heap */
  Registerset *registers; /* pointer to registerset */
  Bytecode *byte_code; /* pointer to byte code */
  uint32 priority; /* time slice size */
} SchedulerItem;



typedef uint32 SchedulerID;



typedef enum 
{
  SCHEDULER_STATUS_VIRGIN, /* Unused entry */
  SCHEDULER_STATUS_RUNNING, /* Item in a run queue */
  SCHEDULER_STATUS_RUNNING_NOEXCEPTIONS, /* Item in a run queue, with exceptions disabled */
  SCHEDULER_STATUS_BLOCKING, /* Item is blocking */
  SCHEDULER_STATUS_DEAD /* Item has died; not yet released */
} SchedulerItemStatus;

Two definitions, 

SCHEDULER_MAX_PRIORITY
and 
SCHEDULER_DEFAULT_PRIORITY
are also available for priority determination. In case the provided priority is zero or greater than 
SCHEDULER_MAX_PRIORITY
, the priority is set to 
SCHEDULER_DEFAULT_PRIORITY
.

4.2 External interface functions

4.2.1 Insert item to scheduler

 

 Status scheduler_insert(IN SchedulerItem *item,
                         OUT SchedulerID *id);



 PRECOND(NULL != item);
 PRECOND(NULL != id);

Each scheduler item receives a unique id so it can be accessed later (until it is removed / has faced an (in)voluntary death / has been migrated somewhere else)

RETURN VALUES:

  • id - scheduler item identification

4.2.2 Remove scheduler item

 

 Status scheduler_remove(IN SchedulerID id,
                         OUT SchedulerItem *item);



 PRECOND(NULL != item);

This removes the scheduler item, eg. for an agent migration or termination

RETURN VALUES:

  • item - current state of execution of the agent

4.2.3 Deliver a message to a scheduler item

 

 Status scheduler_message(IN SchedulerID id,
			    IN LinearizedHeap *message);



 PRECOND(NULL != message);

4.2.4 Execute items in scheduler

 

 Status scheduler_execute(IN uint32 instr_count,
                          OUT Bool *no_agents);



 PRECOND(NULL != no_agents);

RETURN VALUES:

  • no_agents - True if scheduler has no active agents to run

© SchemeStation project 1997-1998 [Back to the document index]