B The Loadable Scheduler Interface

Appendix B
The Loadable Scheduler Interface

This appendix builds upon material presented in Chapters 4 and 9 . It describes the programming interface provided by the Hierarchical Scheduler Infrastructure (HSI) for implementing loadable schedulers.

B.1 Data Structures

B.1.1 Scheduler Instance

The scheduler instance data structure is used by the HSI to keep track of scheduler instances. Scheduler instance memory is managed by the HSI; the data structure is guaranteed to have been allocated by the time an instance’s I_Init function is called, and will not be deallocated until after its I_Deinit function has returned. The fields of the scheduler instance are shown in Figure B.1. They are used as follows:

Name -- a character array containing a string that uniquely identifies the scheduler; this field is set by the HSI.
Type -- a character array containing a string indicating what guarantees the scheduler requires and provides (not currently used).
CB -- a pointer to a struct of type HLS_CALLBACKS; this field is set by the HSI at instantiation time.
SchedData -- The type of this field, SDHandle, is an alias for void *. This field can be used to point to a scheduler-specific variable. For example, the HLS time-sharing scheduler uses this field to point to a struct containing the ready queue and related data structures.
HLSTimer and HLSDpc -- these fields are for internal use by the HSI and must not be touched by schedulers.

  struct HLS_SCHED_INSTANCE {
    char Name[MAX_NAMELEN];
    char Type[MAX_NAMELEN];
    struct HLS_CALLBACKS *CB;
    SDHandle SchedData;

    // private fields for use only by the HSI
    KTIMER HLSTimer;
    KDPC HLSDpc;
  };

Figure B.1:

Fields of the scheduler instance structure

B.1.2 Virtual Processor

Virtual processors embody parent / child relationships between two schedulers: each scheduler shares one or more virtual processors (VPs) with its parent(s) and with its children. The responsibility for correctly allocating and deallocating memory for VPs lies with the child. That is, before registering a VP with its parent a child must first allocate and initialize it. The fields in a virtual processor, shown in Figure B.2 , are:

Proc -- This field is always set either to the number of the physical processor that has been granted to the VP or to the constant NO_PROC, indicating that the VP is not currently running.
State -- The state of a VP is represented by an enumerated type that may take the value VP_Ready, VP_Waiting, or VP_Running.
TopSched -- A pointer to the scheduler instance that is the parent in a relationship represented by a VP.
BottomSched -- A pointer to the scheduler instance that is the child in a relationship represented by a VP.
UpperData -- The type of this field, TDHandle, is an alias for void *. UpperData may be used to store scheduler-specific per-VP data. For example, the HLS time-sharing scheduler uses UpperData to store a pointer to a structure containing the priority and ready queue entry for a VP.
TopData and BottomData -- These fields are intended to make writing a scheduler more convenient by allowing a top virtual processor to point to the bottom virtual processor that it is currently granting a processor to, and vice versa.

  struct HLS_VPROC {
    PROCT Proc;
    VPROC_STATE State;
    struct HLS_SCHED_INSTANCE *TopSched;
    struct HLS_SCHED_INSTANCE *BottomSched;
    TDHandle UpperData;
    struct HLS_VPROC *BottomData;
    struct HLS_VPROC *TopData;
  };

Figure B.2:

Fields of the virtual processor structure

B.1.3 Scheduler Callbacks

Schedulers, like other device drivers, are event-driven. They must make a collection of function pointers available to the rest of the system in order to receive notifications when events of interest occur. This collection of functions is shown in Figure B.3 ; it also includes a single variable Name. The namespace of schedulers is separate from the namespace of scheduler instances; the HSI keeps track of both kinds of entities. The callbacks can be divided into three categories, identified by a prefix. First, callbacks that are initiated by a scheduler’s child (or potential child) have the prefix “B”. Callbacks from a parent have the prefix “T”. Finally, callbacks from the HSI have the prefix “I”. Most callbacks take a parameter called Self, which is analogous to the implicit self parameter passed to object methods in languages such as C++. The functions that each scheduler provides to the HSI are:

B_RegisterVP -- One scheduler makes this call to another to establish a parent / child relationship. If successful, HLS_SUCCESS should be returned, indicating that the calling scheduler has become a child of the called scheduler.
B_UnregisterVP -- This call, made by a child scheduler, ends a parent / child relationship between two schedulers.
B_VP_Request -- A child scheduler makes this callback to notify its parent that a waiting VP is now ready to be scheduled.
B_VP_Release -- A child scheduler makes this callback to notify its parent that a ready or running VP can no longer use a physical processor.
B_Msg -- This callback allows arbitrary messages to be sent to schedulers; the argument of type MsgHandle is an alias for void *. This function uses the “B” prefix because messages are often sent from a scheduler to its parent (for example, to change the parameters of a CPU reservation), but messages can also originate in the HSI.
T_VP_Grant -- A scheduler instance receives this callback when its parent allocates a physical processor to a virtual processor that is in the VP_Ready state.
T_VP_Revoke -- This callback notifies a scheduler that a physical processor is being revoked from a virtual processor that is currently in the VP_Running state.
I_Init -- This is guaranteed to be the first callback received by a scheduler instance. It should be used to initialize data structures in such a way that when Init returns, the scheduler is ready for VPs to register with it.
I_Deinit -- This callback is guaranteed not to occur while any VPs are registered with a scheduler instance. It gives an instance the opportunity to deallocate dynamic memory before being destroyed.
I_TimerCallback -- This function is called when a scheduler’s timer expires, permitting it to make a scheduling decision.
I_CheckInvar -- This callback gives schedulers the opportunity to ensure that their internal data structures are consistent. It is acceptable to flag an inconsistency by printing a debugging message or by halting the system. CheckInvar will only be called when the hierarchy is in a “stable” state--when it is not in the middle of processing a notification.

  struct HLS_CALLBACKS {
    char *Name;

    // callbacks from children

    HLS_STATUS (*B_RegisterVP) (struct HLS_SCHED_INSTANCE *Parent,
                                struct HLS_SCHED_INSTANCE *Child,
                                struct HLS_VPROC *VP);
    void (*B_UnregisterVP) (struct HLS_VPROC *VP);
    void (*B_VP_Request) (struct HLS_VPROC *VP);
    void (*B_VP_Release) (struct HLS_VPROC *VP);
    HLS_STATUS (*B_Msg) (struct HLS_SCHED_INSTANCE *Inst,
                         struct HLS_VPROC *VP,
                         MsgHandle Msg);

    // callbacks from parents

    void (*T_VP_Grant) (struct HLS_VPROC *VP);
    void (*T_VP_Revoke) (struct HLS_VPROC *VP);

    // callbacks from HSI

    void (*I_Init) (struct HLS_SCHED_INSTANCE *Self,
                    struct HLS_SCHED_INSTANCE *Parent);
    void (*I_Deinit) (struct HLS_SCHED_INSTANCE *Self);
    void (*I_TimerCallback) (struct HLS_SCHED_INSTANCE *Self);
    void (*I_CheckInvar) (struct HLS_SCHED_INSTANCE *Self);
  };

Figure B.3:

Fields of the scheduler callback structure

B.2 Functions Available to Schedulers

The HSI makes a number of functions available to loadable schedulers; their prototypes are shown in Figure B.4 .

  void HLSSetTimer (WNT_TIME Time, struct HLS_SCHED_INSTANCE *Sched);
  WNT_TIME HLSGetCurrentTime (void);

  void *hls_malloc (int size);

  void hls_free (void *mem);

  void HLS_ASSERT (expr);

  void HLSDbgPrint (level, (format, ...));

Figure B.4:

Functions provided to scheduler instances by the HSI

B.2.1 HLSSetTimer

Schedulers may use this function to arrange for a timer callback to arrive in the future. Following Windows convention, negative times are relative and positive times are absolute (setting Time to 0 results in an immediate callback). Currently each scheduler gets only one timer; successive calls to HLSSetTimer result in the timer being reset. The resolution of this timer is tunable and depends on clock interrupt frequency. Currently, it can be assumed to be accurate to approximately 1 ms.

B.2.2 HLSGetCurrentTime

This function returns the current time in 100 ns units. The time is based on the value returned by the rdtsc instruction; this means that reading the time is cheap and precise, but it may not be accurately calibrated with respect to the times used by Windows 2000.

B.2.3 hls_malloc

Allocate a block of memory--the interface is the same as the C library function malloc.

B.2.4 hls_free

Release a block of memory--the interface is the same as the C library function free.

B.2.5 HLS_ASSERT

If expr is false, print the line number, file, and expression of the failing assert to the console. Also attempt to trap to the kernel debugger or, if the debugger is unavailable, halt the system.

B.2.6 HLSDbgPrint

This macro prints a debugging message to the console if HLS_DBG_PRINT_LEVEL is greater than or equal to the level parameter. The arguments (format, ...) are evaluated similarly to the arguments to the C library function printf.

B.3 Constants, Variables, and Types

B.3.1 WNT_TIME

This type is used by HLS to represent time values. It is an alias for the signed 64-bit integer.

B.3.2 HLS_STATUS

This enumerated type is used as a return value by many HLS functions. HLS_SUCCESS is the success value. Failure values include HLS_NOROOM and HLS_INVALID_PARAMETER.

B.3.3 HLS_MAX_PROCS

This integer constant indicates the most processors that a Windows 2000 system could contain. It will probably always be equal to 32.

B.3.4 HLS_MAX_NAMELEN

The maximum length, in bytes, of the name of a scheduler, scheduler type, or scheduler instance.

B.3.5 HLSNumProcs

This integer variable indicates the number of processors currently available in the system. It starts at 1 during boot and increases as more processors are brought online. Schedulers that load after boot time may treat it as a constant. Processors are always numbered 0..HLSNumProcs-1.

B.3.6 HLSCurrentProc

This integer variable is equal to the number of the processor on which scheduler code is currently executing.

B.3.7 NO_PROC

This is an integer constant that a scheduler can sometimes use when a processor number is required, indicating that no particular processor is preferred.

B.3.8 HLS_DBG_PRINT_LEVEL

This integer variable is used to control the amount of debugging information that appears on the console. A value of 0 causes HLS to be completely silent, while 9 is very verbose.

B.4 Functions for Loading and Unloading a Scheduler

The following two functions, unlike all other functions in this appendix, do not pertain to a particular scheduler instance. Rather, they are called by a scheduler device driver as it is being loaded into or unloaded from the Windows 2000 kernel. Schedulers that are built into the kernel should ignore these functions.

B.4.1 HLS_STATUS HLSRegisterScheduler (struct HLS_CALLBACKS *)

Every Windows 2000 device driver provides a DriverEntry callback that is called by the operating system after the driver has been loaded into the kernel address space. When a scheduler is loaded, its DriverEntry function should at some point call HLSRegisterScheduler to inform the HSI of its presence, passing the address of the scheduler’s callback table (described in Section B.1.3) as a parameter.

B.4.2 HLS_STATUS HLSUnregisterScheduler (struct HLS_CALLBACKS *)

Prior to unloading a device driver, Windows 2000 calls the driver’s DriverUnload function. When the driver being unloaded is an HLS scheduler, it should call HLSUnregisterScheduler to notify the HSI of its absence.

[next] [prev] [prev-tail] [front] [up]

Appendix B The Loadable Scheduler Interface