Design and analysis of hard real-time systems Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zp38wf84z

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • First, we study hard real-time scheduling problems where each task is defined by a four tuple (r, c, p, d): r being its release time, c computation time, p period, and d deadline. The question is whether all tasks can meet their deadlines on one processor. If not, how many processors are needed? For the one-processor problem, we prove two sufficient conditions for a (restricted) periodic task set to meet deadlines. The two conditions can be applied to both preemptive and non-preemptive scheduling, in sharp contrast to earlier results. If a periodic task set can meet deadlines under any algorithm which does not idle the processor as long as there are tasks ready to execute, it must satisfy our second condition. We also prove a necessary condition for a periodic task set to meet deadlines under any scheduling algorithm. We present a method for transforming a sporadic task to an equivalent periodic task. The transformation method is optimal with respect to non-preemptive scheduling. With this method, all results on scheduling periodic task sets can be applied to sets of both periodic and sporadic tasks. For the scheduling problem in distributed memory systems, we propose various heuristic algorithms which try to use as few processors as possible to meet deadlines. Although our algorithms are non-preemptive, our simulation results show that they can outperform the heuristic algorithms based on the famous preemptive rate monotonic algorithm in terms of the number of used processors and processor utilization rate. Second, we describe a hard real-time software development environment, called HaRTS, which consists of a design tool and a scheduling tool. The design tool supports a hierarchical design diagram which combines the control and data flow of a hard real-time application. The design diagram is quite intuitive, and yet it can be automatically translated into Ada™ code and analyzed for scheduleability. The scheduling tool schedules precedence-constrained periodic task sets and simulates the task execution with highly animated user interfaces, which goes beyond the traditional way of examining a schedule as a static Gantt chart.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome, 256 Grayscale) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-12-12T18:47:00Z (GMT) No. of bitstreams: 1 ZhuJiang1994.pdf: 7398502 bytes, checksum: 908dff9b2d74b0fc0524013a31dc1fab (MD5)
  • description.provenance : Made available in DSpace on 2012-12-12T18:49:19Z (GMT). No. of bitstreams: 1 ZhuJiang1994.pdf: 7398502 bytes, checksum: 908dff9b2d74b0fc0524013a31dc1fab (MD5) Previous issue date: 1993-11-16
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-12-12T18:49:19Z (GMT) No. of bitstreams: 1 ZhuJiang1994.pdf: 7398502 bytes, checksum: 908dff9b2d74b0fc0524013a31dc1fab (MD5)
  • description.provenance : Submitted by Kirsten Clark (kcscannerosu@gmail.com) on 2012-12-12T18:38:03Z No. of bitstreams: 1 ZhuJiang1994.pdf: 7398502 bytes, checksum: 908dff9b2d74b0fc0524013a31dc1fab (MD5)

Relationships

In Administrative Set:
Last modified: 08/04/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items