More Web Proxy on the site http://driver.im/

research-article

Towards optimal priority assignments for the transactional event handlers of P-FRP

Authors:

Chaitanya Belwal,

Albert M. K. ChengAuthors Info & Claims

RACS '13: Proceedings of the 2013 Research in Adaptive and Convergent Systems

Pages 428 - 433

https://doi.org/10.1145/2513228.2513263

Published: 01 October 2013 Publication History

Abstract

Priority-based Functional Reactive Programming (P-FRP) is a new functional programming formalism for real-time systems. P-FRP allows static priority assignment and guarantees real-time response by preempting lower priority tasks. Due to the state-less nature, preempted tasks are aborted and restarted after higher priority tasks have completed execution. Therefore, the rate-monotonic (RM) priority assignment is not optimal in P-FRP, and it has been unknown whether an optimal fixed priority assignment can even exist for such an execution model. In this paper, we first present the priority assignment characteristics of P-FRP. We then discuss the priority assignment in a task set with two tasks. We derive the conditions when the RM priority assignment is optimal and show that at least one of RM or utilization-monotonic (UM) is the optimal for the task set with two tasks. We prove the optimal priority assignment for a general P-FRP system having more than two tasks exists when the period of the task is a multiple of others. Experimental results using task sets of different sizes are also presented.

References

[1]

Z. Wan and P. Hudak, "Functional reactive programming from first principles," in In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2000, pp. 242--252.

Digital Library

[2]

"Functional reactive animation."

[3]

J. Peterson, G. D. Hager, and P. Hudak, "A language for declarative robotic programming," in In International Conference on Robotics and Automation, 1999, pp. 1144--1151.

[4]

J. Peterson, P. Hudak, A. Reid, and G. D. Hager, "Fvision: A declarative language for visual tracking," in Proceedings of the Third International Symposium on Practical Aspects of Declarative Languages, ser. PADL '01, 2001, pp. 304--321.

Digital Library

[5]

"Haskell," http://www.haskell.org.

[6]

R. M. Sivasankaran, J. A. Stankovic, D. Towsley, B. Purimetla, and K. Ramamritham, "Priority assignment in real-time active databases," The VLDB Journal, vol. 5, no. 1, pp. 019--034, Jan. 1996.

Digital Library

[7]

Z. Wan, W. Taha, and P. Hudak, "Real-time frp," in in the International Conference on Functional Programming (ICFP 01. ACM, 2001, pp. 146--156.

Digital Library

[8]

R. Kaiabachev, W. Taha, and A. Zhu, "E-frp with priorities," in Proceedings of the 7th ACM & IEEE international conference on Embedded software, ser. EMSOFT '07, 2007, pp. 221--230.

Digital Library

[9]

M. Swaine, "It's time to get good at functional programming," 2008. {Online}. Available: \url{http://www.drdobbs.com}

[10]

C. Belwal and A. Cheng, "An extensible framework for real-time task generation and simulation," in Embedded and Real-Time Computing Systems and Applications (RTCSA), 2011 IEEE 17th International Conference on, vol. 1, aug. 2011, pp. 259--263.

Digital Library

[11]

J. Ras and A. M. K. Cheng, "Response time analysis for the abort-and-restart event handlers of the priority-based functional reactive programming (p-frp) paradigm," in Proceedings of the 2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, ser. RTCSA '09, 2009, pp. 305--314.

Digital Library

[12]

C. Belwal and A. M. K. Cheng, "Determining actual response time in p-frp," in Proceedings of the 13th international conference on Practical aspects of declarative languages, ser. PADL'11, 2011, pp. 250--264.

Digital Library

[13]

C. Belwal, A. M. K. Cheng, and Y. Wen, "Time petri nets for schedulability analysis of the transactional event handlers of p-frp," in Proceedings of the 2012 ACM Research in Applied Computation Symposium, ser. RACS '12, 2012, pp. 257--262.

Digital Library

[14]

C. Belwal and A. M. K. Cheng, "Schedulability analysis of transactions in software transactional memory using timed automata," in Proceedings of the 2011IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications, ser. TRUSTCOM '11, 2011, pp. 1091--1098.

Digital Library

[15]

M. Herlihy, J. Eliot, and B. Moss, "Transactional memory: Architectural support for lock-free data structures," in Computer Architecture, 1993., Proceedings of the 20th Annual International Symposium on, may 1993, pp. 289--300.

Digital Library

[16]

S. F. Fahmy, B. Ravindran, and E. D. Jensen, "Response time analysis of software transactional memory-based distributed real-time systems," in Proceedings of the 2009 ACM symposium on Applied Computing, ser. SAC '09, 2009, pp. 334--338.

Digital Library

[17]

J. Manson, J. Baker, A. Cunei, S. Jagannathan, M. Prochazka, B. Xin, and J. Vitek, "Preemptible atomic regions for real-time java," in Proceedings of the 26th IEEE International Real-Time Systems Symposium, ser. RTSS '05, 2005, pp. 62--71.

Digital Library

[18]

Y. Wen, A. M. K. Cheng, and C. Belwal, "Worst case response time for real-time software transactional memory," in Proceedings of the 2012 ACM Research in Applied Computation Symposium, ser. RACS '12, 2012, pp. 459--460.

Digital Library

[19]

J. Anderson, S. Ramamurthy, and K. Jeffay, "Real-time computing with lock-free shared objects," in Real-Time Systems Symposium, 1995. Proceedings., 16th IEEE, dec 1995, pp. 28--37.

Digital Library

[20]

C. L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," J. ACM, vol. 20, no. 1, pp. 46--61, Jan. 1973.

Digital Library

Cited By

Murphy JShivkumar BPritchard AIraci GKumar DKim SZiarek L(2018)A survey of real‐time capabilities in functional languages and compilersConcurrency and Computation: Practice and Experience10.1002/cpe.490231:4Online publication date: 23-Oct-2018
https://doi.org/10.1002/cpe.4902

Index Terms

Towards optimal priority assignments for the transactional event handlers of P-FRP
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

Feasibility Interval for the Transactional Event Handlers of P-FRP
TRUSTCOM '11: Proceedings of the 2011IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications

declarative approach for modeling and building safety-critical embedded systems. Recently, Priority-based FRP (P-FRP) was introduced as a formalism that guarantees real-time response. Due to the state-less nature of execution of functional programs, P-...
Feasibility interval for the transactional event handlers of P-FRP

Functional Reactive Programming (FRP) is a resource aware declarative approach for modeling and building safety-critical embedded systems. Recently, Priority-based FRP (P-FRP) was introduced as a formalism that guarantees real-time response. Due to the ...
Time petri nets for schedulability analysis of the transactional event handlers of P-FRP
RACS '12: Proceedings of the 2012 ACM Research in Applied Computation Symposium

Priority-based FRP (P-FRP) is a functional programming formalism for reactive systems that guarantees real-time response. Preempted tasks in P-FRP are aborted and have to restart when no higher priority tasks are present in the execution queue. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

RACS '13: Proceedings of the 2013 Research in Adaptive and Convergent Systems

October 2013

529 pages

ISBN:9781450323482

DOI:10.1145/2513228

Conference Chairs:
Ching Y. Suen
Concordia University, Canada
,
Amir Aghdam
Concordia University, Canada
,
Minyi Guo
Shanghai Jiao Tong University, China
,
Program Chairs:
Jiman Hong
Soongsil University, Korea
,
Esmaeil Nadimi
University of Southern Denmark, Denmark

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing
ACCT: Association of Convergent Computing Technology

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

RACS'13

Sponsor:

SIGAPP
ACCT

RACS'13: Research in Adaptive and Convergent Systems

October 1 - 4, 2013

Quebec, Montreal, Canada

Acceptance Rates

RACS '13 Paper Acceptance Rate 73 of 317 submissions, 23%;

Overall Acceptance Rate 393 of 1,581 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
51
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Murphy JShivkumar BPritchard AIraci GKumar DKim SZiarek L(2018)A survey of real‐time capabilities in functional languages and compilersConcurrency and Computation: Practice and Experience10.1002/cpe.490231:4Online publication date: 23-Oct-2018
https://doi.org/10.1002/cpe.4902

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents