OVERVIEW:

GENERAL IDEA AND GOALS:

The SRMS scheduler application is an implementation in of the Statistical Rate Monotonic Scheduling algorithm devised by Alia K. Atlas and Azer Bestavros in Windows NT. The project's objective is to simulate the Windows NT 4.0 scheduler and distribute processor resources to firm real-time tasks according to the SRMS algorithm.  Included in the project are the SRMS scheduler and job admission controller, a graphical user interface, and an SRMS API that enhances real-time task programming. A secondary goal of the project is to see how NT performs under such conditions given the fact that it has very little built-in support for real-time scheduling.  Up until this project, there has never been a practical implementation of SRMS in an actual operating system. Atlas' SRMS simulator written as a Java applet introduces the major tenets of the algorithm using a simple graphical tool.  Another attempt was also made at a KURT Linux implementation, but that was not totally completed. With these projects as a foundation, the SRMS scheduler application takes the next step at proving the algorithm's effectiveness in yielding a guaranteed quality of service. It is also an attempt to discover what level of predictability and performance Windows NT can achieve in dealing with firm real-time tasks.

HOW IT WORKS:

The SRMS scheduler service is programmed using Microsoft’s Win32 API. Although it is ideally intended to start as an NT system service, for now it runs as just a user process in the NT operating system. Windows NT is priority-based, preemptive scheduler, meaning that the highest-priority thread in the system that is ready to run will always get the processor.  To guarantee as much processor resources as possible to the SRMS service, it is necessary to operate at a priority higher than most other processes in the system. Therefore, the SRMS service and all real-time tasks execute in the highest levels of NT's real-time priority range.  These priority levels are the highest possible levels in the entire operating system, even higher than the priority levels of most NT kernel threads. (Follow this link to Microsoft's Developer Network site for a more detailed description of NT's scheduling priority structure)

Conceptually, the SRMS service consists of three main pieces: a message handler, a quality of service negotiator, and a task scheduler. These three pieces work together in tandem to schedule tasks according to the SRMS algorithm while providing a task with its guaranteed quality of service.  Task threads can theoretically be any thread of execution that conform to the standard SRMS real-time task model. In this project, the sample test tasks used are single-threaded user processes programmed using the specially designed SRMS API to communicate with the SRMS service.   Since the interaction between the service and the real-time task is quite complicated, the programming interface included in this project abstracts these intricacies to ease the job of the real-time programmer wishing to use the service.

As an aid to users, a simple graphical user interface accompanies the service allowing users to modify settings or view the state of the SRMS scheduler and tasks.  Through the GUI, users can modify the NT priority levels of the service and tasks to adjust real-time performance.  Or if real-time tasks are starving non-real-time tasks, users can reserve a portion of processor resources for the rest of the operating system in order to improve the performance of the overall system.  The GUI is equipped with a progress log that details the step-by-step actions of the SRMS service for users to follow along while events occur.  For an even more detailed explanation of the execution history of a real-time task, the interface also has a feature to report the timing statistics for each job of a task.  There are also summary windows, options to start, stop, or terminate the service, an option to manually remove a real-time thread, and a help feature (which will be implemented at a later time).

The SRMS service has two states of execution: started and stopped.  In its initial stopped (unstarted) state, the SRMS scheduler is inactive and the entire service operates in NT's normal priority range.  The normal range is where most applications operate in the NT operating system since they occupy priorities that are lower than the kernel's threads.  During this unstarted state, the service performs no real-time work so executing in the normal range is sufficient.  Usually, work in this state consists of registering tasks that request admittance as real-time tasks in the SRMS system, negotiating quality of service for registered tasks, or processing messages from the service's GUI. Once started, the SRMS scheduler becomes active and immediately boosts the service and any registered real-time tasks up to NT's real-time priority range.  From there, the scheduler portion of the SRMS service mimics the NT scheduler by controlling which real-time task gets scheduled and for how long it executes.  It does this by suspending all real-time tasks that are not running and placing them in indefinite wait states.  It then isolates the one task that will run by placing it in a ready state.   Just prior to releasing the processor, the SRMS scheduler sets a timer interrupt to fire at the next scheduler event, and then it waits on that timer.  Now, the NT scheduler has no choice but to select the isolated real-time task and schedule its job, since it is (assumed to be) the highest priority thread in the system in a ready state.   When the job finishes or the timer finally fires, the SRMS scheduler thread resumes control of the processor because it is now the highest priority thread in the system.   It then performs some record-keeping and determines the next real-time task to schedule.

Tasks are permitted to enter and leave the SRMS system at any time by registering and unregistering themselves.  After registering, tasks request QoS admission with one of two methods.  Borrowing from Atlas' KURT Linux implementation, the SRMS API permits either a blocking or non-blocking call when tasks request QoS admission.  The non-blocking call returns to the task regardless of whether the SRMS scheduler can guarantee the task's requested quality of service, while the blocking call does not return until at least the minimum QoS has been guaranteed.  When a task requests QoS admission, its sends the SRMS service a message indicating whether it wants to use the blocking or non-blocking method.  After receiving the message, the service activates the QoS negotiator, which is another thread dedicated to calculating QoS and allowance values for a new task set.  This thread operates at the same lower priority level as the message handler so that no guaranteed processor resources are stolen from the SRMS scheduler and real-time tasks, which operate at higher priorities.   When a task unregisters, the service again calls the QoS negotiator to recalculate the QoS and allowance values for the new smaller task set, and also to check if any waiting tasks can gain admittance.  When all tasks have unregistered (or upon user request), the SRMS scheduler stops and returns the service to the stopped state.

ABOUT THIS SITE:

This site provides an in-depth analysis of the Windows NT SRMS service.  It describes in great detail how to use the service and how it works internally.  All code references made throughout the site refer directly to the code used to create this project.  More information on how to view this code is provided in the File Descriptions section.  The pages found here are written from the perspective of an experienced C and Win32 programmer who is familiar with the Statistical Rate Monotonic Scheduling algorithm.  Therefore, a general knowledge of all three is recommended in order to fully understand many of the details.  The site is geared towards the reader who is interested in learning more about the Windows NT SRMS service.  It is also directed towards any programmer who may want to test the SRMS service with his or her own real-time task threads, or the programmer who potentially may want to modify or add to the service's code.  Please email the author of this project, Adrian Prezioso, with any questions or comments about the project described herein.

< Back to the SRMS Service Home Page >