Copyright: Visual Help ® 1993-1994 Firas Bushnaq


Contents

Introduction

The Monotonizer performs Rate Monotonic Analysis. This is a mathematical technique used to prove schedulability of multiple tasks that must share resources. The shareware version is somewhat limited (5 tasks, 3 resources). The registered version (only $299.95 + $5 s/h) can handle hundreds of tasks and dozens of resources.

PS. Note that smaller numeric values means HIGHER PRIORITY!

Registering your copy of The Monotonizer

Procedures

 Entering Task Data

 Inserting and Deleting Tasks

 Adding and Deleting Resources

 Setting RMA Options

 Viewing Detailed Results

 Printing

 Annotating with a Text Note

 Sort Options

 Other Options

 Appy Mathematical Expression

 About A Priori Software

Reference

Keyboard


Registering Your Copy of the Monotonizer

Why Register?

The shareware version is limited to 5 tasks and 3 resources. The registered version has been used to analyze as many as 200 tasks with 20 resources. You also become eligible for technical support and receive a printed manual.

How to Register

Registration is easy. Send a check for $299.95 + 5.00 s/h to

Bruce Douglass
c/o Ohmeda
PO Box 7550
Madison, WI 54707

Bruce Douglass can also be reached in Germany at
Dachsklingeweg 17
Sindelfingen, Germany
Phone: 07031-80-9399

Compuserve: 70673,2715
Internet: 70673.2715@compuserve.com

Compuserve Registration

Registration on Compuserve is even easier! Just type GO SWREG, select the Register Shareware Option, and use SW ID #5611. Compuserve will bill your account automatically!


Entering Task Data

Task data is entered and displayed via a spreadsheet metaphor. Each row corresponds to a single task, while each column is some aspect of the task. There should be no empty rows in the middle of the task sheet. The following columns are defined:

ID

This is an arbitrary number assigned to the task for internal tracking. There is no point in filling this out. You may want to renumber the tasks, and this can be done from the Options Menu.

Task Name

This field is the name of the task. Any name can be used, but task names should be unique, since the results use the task name to indicate which tasks are schedulable.

Period

The periodicity of the task is entered here. The units are arbitrary, but should be consistent with all other time units. For example, the numbers could represent milliseconds. The numbers may include a decimal point. For aperiodic tasks being scheduled by a sporatic server, use the minimum interarrival interval.

Priority

This field shows the Priority of the task. It is a numeric value in which smaller quantities represent higher priorities; e.g. a priority of 10 is higher than one of 100. If you are using the RMS algorithm, select Use RMA Priorities on the RMA Options Dialog (Task form Options Menu). In that case, this entry is ignored and the priority is determined solely by the period (the shorter the period, the higher the priority).

Exec Time

This is a numeric value representing the amount of time the task takes to execute once it has begun.

Deadline

The deadline is a numeric value indicating the period of time by which the task must be complete. It should generally be less than or equal to the period, although this is not always true.

Task Type

Indicates the type of deadline requirement for the task. Available task types include:

•	Hard

•	Soft

•	Firm

This field is currently ignored, but is provided for you to document your task decisions.

Pattern

This field indicates the arrival pattern for the task. Available patterns include:

•	Periodic

•	Aperiodic

•	Bursty

•	Bounded

•	Unbounded

This field is currently ignored, but is provided for you to document your task decisions.

Blocking

This field is the length of time a task may be blocked. It is a numeric value. It can be entered if you want to determine resource blocking yourself. If you add resources, however, you can have The Monotonizer determine the blocking time from the resource usage times. If the RMA Option "User Entered Blocking" is selected then the values from this column are used instead of the resource usage values.

See also

Adding Resources

RMA Options

Start Time

This field is provided so that later task simulation can be added. It currently provides no functionality.

Resources

When you add resources, they are displayed as a column at the right of the spreadsheet, The values in the resource column is the amount of time the task uses the resource. The program will use this to calculate blocking times if the RMA Options Simple Blocking or Priority Ceiling Protocol are selected.


Inserting and Deleting Resources

Inserting Resources

Inserting resources is easy. Resources are added as columns at the right. To add a resource, Select the Edit menu and the Add Resource item. You will be given an opportunity to name the resource. A default name will be provided. Hitting the Enter key will accept the name.

You may not be able to see the resource because it may be off the screen on the right. Use the horizontal scroll bar to scroll to the right to see the resource.

Deleting Resources

Select the resource or resources you wish to delete (they must form a contiguous block if a group is selected). Then select the Edit menu and click on the Delete Resource item.


Setting RMA Options

There are 3 types of RMA Options: Blocking Options, Computational Options, and Task Options. To see or select the options, select the Options menu and the RMA Options. The RMA Options dialog will then be displayed.

Blocking Options

Computational Options

Task Options


Blocking Options

This set of options sets of the program determines and uses blocking. Available options are:

•	Ignore Blocking

This option will assume that regardless of resources and user blocking set, that no task is blocked from execution by a lower priority task.

•	Simple Blocking

This option assumes that a task will be blocked by at most one lower priority task. It finds the task that uses the resource in question the longest (assuming that it isn't the task for which the blocking term is being calculated), and uses the amount of time this task uses that resource as the blocking term for the resource.

•	Priority Ceiling Protocol

PCP, along with highest locker protocol, is a method of ensuring that a high priority task can at most be blocked by a single lower level task. If your scheduling algorithm uses Highest Locker, Priority Inheritance, or PCP, this is the option you should use.

•	User Entered Blocking

If you want to enter the blocking terms yourself and not relying on the resource usage to determine blocking, then you should use this option.  If you use this option, the amount of time resources are used by tasks is ignored in task scheduling computations.

Note: If you have entered values in the Blocking column, and then specify either Simple or PCP blocking, then these values will be overwritten with what The Monotonizer determines as the blocking due to specified resource usage.


Computational Options

The computational options are used to select which mathematical technique is used. The techinque number refers to the method within the SEI Handbook (see references).

•	Program Select Optimal

This option (the default) allows the software to select what it thinks is the most appropriate method. Unless you know the methods and have a specific reason for selecting a different method, you should keep this option set.

•	Global Method

This method uses a single utilization bound for the entire set of tasks. This is the fastest way to get the answer. It is a severe method; a set of tasks that is not determined to be schedulable by this may still be schedulable. If it is shown to be schedulable by this method, it is guarenteed to meet all deadline, provided that the task parameters are accurate. For many tasks, the utilization bound converges to 0.69, but actually sets of tasks are still usually schedulable if their utilization is less than about 0.8 or so. If the computed utilization is in this range, then try again with a more analytical method.

This method assumes that the deadlines are equal to the period, and that responses are assigned rate monotonic priorities, eg. the shorter the period, the higher the priority.

•	Utilization Bound

This method is Technique 2 in the SEI handbook. It is a detailed technique in that the effective utilization for each task is computed, and the schedulability of each task is computed separately.

This method assumes that deadlines are less than or equal to the end of the period for each task, and that all actions for any given task all execute at the same priority.

•	Response Times

This method (technique 5 in the SEI Handbook) computes worst case response times for each task. This method assumes

1 	All actions for any given task execute at the same priority

2 	Deadlines may be greater than the period


Task Options

The Task options refer to the selection of tasks for the analysis, and to the how priorities are selected.

The default is to use all tasks. Alternatively, only selected tasks may be used. To select a contiguous block of tasks, click on any cell in the row for the starting task, and while holding down the Shift key, click on any cell in the second task row. This selects the block of tasks.

Alternatively, you can click on several tasks, one at a time, while holding down the Control key. In this case, the tasks need not form a contiguous block.

If the Use Selected Tasks option is set, then the selected tasks will be used for the analysis.

Use RMA Priorities Checkbox

If this checkbox is set, then the values in the Priority column are ignored, and the priorities are computed from the periods alone. Otherwise, the values in the Priority column are used.

Remember, the smaller the numeric value for priority, the HIGHER the priority!


Inserting and Deleting Tasks

Inserting Tasks

To insert a task at the end of the task list, position the cursor to the end of the list of tasks to a blank row and start typing. If there is no blank row, then you must use the second method, discussed next.

To add tasks in the middle, select a number row rows equal to the number of tasks you want to add. Then select the Edit Menu and Insert Task to insert the blank columns.

The shareware version has disabled the ability to add tasks using the second method.

Deleting Tasks

To delete tasks, select any cell on the row of the task to delete. To delete a set of tasks, you may select one row, hold the shift key down and click on a cell in a different row; this will select all rows in between as well.

Once you have selected the tasks, select the Edit menu and the Delete Task item.


Viewing Detailed Results

The default format for the results is to display the overall results, but not the detailed, task-by-task results. To view the detailed results, select the View Menu and click on the Show Detailed Results menu item.  Detailed results include for each task

•	Task Name

•	Whether the task is schedulable

•	Task Period

•	Task Execution Time

•	Task Deadline

•	Arrival Pattern

•	Task Types

•	Worst case response times


Printing

Printing

Printing may be done on either the main spreadsheet form or the results form. Simply select the File menu from the appropriate form, and select the Print Item. Alternatively, you may enter <ctrl>-P.

Print Preview

A full Print Preview option is provided from both the main task form and the results form. Simply select the File menu and the Print Preview option or press Ctrl-Z.

On the Print Preview dialog, there are buttons to

•	Print

Sends all preview pages to the printer.

•	Clear

Clears all Print Preview pages.

•	Next Page, Previous Page

If there are multiple pages, clicking these buttons takes you to the next page or previous page, respectively.

•	Close

Closes the print preview dialog.

In addition, you can set the zoom level by pulling down the zoom list box, select a different printer from the printer select box, or change orientation of the printer.

If you change the printer or its orientation, it changes the settings for all Windows. .


Annotating with a Text Note

The Options menu, Text Note Item allows you to enter a short description that will appear in the results form when printed. This note may be up to 255 characters in length.

The note may be accessed via Ctrl-N.


Sort Options

This option allows you to sort the tasks by

•	Task Name

•	User Priorty

•	RMA Priority (i.e. Task Period)

•	Resource Usage


Other Options

Ignore Assumption Violations

The program checks that assumptions are met before a method is applied. If you REALLY want to force the program to compute using a specific method anyway, select the Option menu, Ignore Assumption Violations item.

Show Task IDs

The Task ID column can be hidden from view. To do this, select the Option menu, Show Task IDs column.

Renumber Tasks

This option allows renumber of Tasks Ids.

Lock Task Name Column

When many resources are present, the task name column may scroll off the screen. To keep it on the screen, use this option to force the task names to always be displayed. To enter or edit task names, you will have to select this option again to unlock them.


Apply Mathematical Expressions

This feature allows you to apply a mathematical transformation to all selected items in a column. To use it, first, select NUMERIC cells to which to apply the expression, then select the Edit menu, Apply Math Expression item.

The Apply dialog will be displayed. You can enter a mathematical expression to be applied to all selected cells. Clicking on the Apply button forces the transformation, while Cancel aborts the operation.

For example, if you decide that the execute times are all off by a factor of 2 (because you decided to double the speed of the processor),

•	Select the items in the Execute Time column

•	Click on the Edit Menu, Apply Math Expression item

•	Enter "/ 2" (no quotes) in the expression edit box

•	Click on the Apply Button

The Execute times should now all be divided by 2.

Math Expressions


Math Expressions

Math Expressions can be applied to cells using the Apply Math Expression feature (Edit Menu), or they may be entered within the cells themselves. Expressions are written as they are in a normal spreadsheet.

If you are entering the expression in a cell, then preface the expression with an = sign, as in

= 23*3/7

If you are ented expressions in the Apply dialog box, then do not enter the = sign.

Functions include:  sin, cos, atan, sqrt, log, ln as well as the normal operators +, -, /, and *.

Apply Mathematical Expressions


A Priori Software

A Priori Software specializes in

•	Numerical Analysis

•	Statistical Analysis

•	Real Time Analysis and Design for high reliability systems

•	Neural Networks and Fuzzy Logic

A Priori Software also does training and consulting. We can be reached at:

A Priori Software
Compuserve: 70673,2715

In the US
Bruce Powel Douglass
c/o Ohmeda
PO Box 7550
Madison, WI 53707-7550

In Europe
Bruce Powel Douglass
Dachsklingeweg 17
Sindelfingen, Germany
07031-80-9399


Keyboard

Task Form

Task Form File Menu Shortcuts

•	Cntrl-O  Open File

•	Cntrl-S Save File

•	Cntrl-P  Print File

•	Cntrl-Z  Print Preview File

•	Cntrl-X  Exit Program

Task Form Edit Menu Shortcuts

•	Cntrl-C  Copy marked task information to the clipboard

•	Cntrl-T  Cut marked task information to the clipboard

•	Cntrl-V  Paste Clipboard information to Task Spreadsheet

Task Form Format Menu Shortcuts

•	Cntrl-F  Bring up Font Dialog

Task Form Options Menu Shortcuts

•	Cntrl-R  Bring up RMA Options Dialog

•	Cntrl-N  Bring up Task Scenario Note Editor

Task Form Miscellaneous Shortcuts

•	F2    Edit current Task spreadsheet cell


Action

A sequential set of instructions within a task. A task may be composed of multiple actions, each of which is executed sequentially.


Aperiodic

Task arrival pattern which does not occur at regular, predictable intervals. Aperiodic tasks are bounded by the Minimum Interarrival Interval, which should be entered in the Period column for aperiodic tasks.


Blocking

The amount of time a high priority task is prohibited from executing by a lower priority task due to the lower priority task using a resource required for the execution of the higher priority task.


Bounded

Arrival pattern for a task in which there is a minimum interarrival time specified for the task.


Bursty

Arrival pattern for a task in which there is a finite number of events  inducing the task that can occur within a set period of time, but the exact arrival pattern is not known.


Firm

A task timing requirement of an average completion time which is bounded by a hard deadline.


Hard

A task timing requirement in which failure for the task to complete execution by a period of time following the start of the time is a system error or fault.


Irregular

Arrival pattern for a task in which the arrival times differ but are known ahead of time.


Period

An interval of time which defines subsequent invocations of a task.


Periodic

Arrival Pattern for a task which occurs at regular intervals.


Priority Ceiling

A resource allocation policy in which a task is allowed to lock a resource only if its priority is higher than the highest priority of any currently locked resource.


Priority Inheritance

A task which shares a resource assumes or inherits the priority of the highest  priority task that can use that resource, as long as the  first task locks the resource.


Priority Inversion

A system state in which high priority tasks are blocked from execution by lower priority tasks,


Priority

A value assigned to a task or action within a task which controls contention for resources. A higher priority is defined within The Monotonizer as a numerically smaller value; e.g. a priority of 10 will  preempt a task of priority 20.


Resource

A physical or software entity which must be sequentially shared among tasks. It may be a bus, variable, data structure, or CPU.


Response Time

The amount of time from the event invoking a task to the completion of the task's actions.


RMS

Rate Monotonic Scheduling. An algorithm in which the priority of a  task is inversely related to its period, i.e., the longer the period, the lower the task's priority.


Soft

A task timing requirement which specifies the average completion time for the task.


Unbounded

Arrival pattern for a task in which the events starting the task are neither bounded nor bursty.


Utilization Bound

A numeric value computed solely from the number of tasks. If the derived utilization is less than the utilization bound, then the set of tasks is completely schedulable in all cases.