<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-172

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Abha Moitra and M. Joseph, Determining Timing Properties of Infinite Real-Time Programs (January 1, 1991).

Abstract

This paper describes a method for determining whether timing deadlines over the commands of a real-time program will be satisfied during execution. A program is assumed to consist of a fixed number of nonterminating processes, each having a simple cyclic structure. Processes may contain nondeterministic commands and may intercommunicate synchronously or asynchronously. Each command has an execution time which takes any value from a non-empty real interval. There are infinitely many possible executions of such a program, and each execution is of infinite length. And if the program P has n processes, it may be implemented on any system with m processors, 1 2 m 2 n. We show how this set of executions can be reduced to a finite set, R-Exe-m(P) of finite length executions, and then prove that any deadline that is violated in any infinite execution will be violated in one of these finite executions. Thus the feasibility of executing the infinite program P on m processors can be determined by examination of the set R-Exe-m(p) of executions of P.

<%@ include file="hardcopy.html" %> <%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>