Fault-tolerant scheduling for real-time embedded control systems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2004-03

AUTHORS

Chun-Hua Yang, Geert Deconinck, Wei-Hua Gui

ABSTRACT

With the increasing complexity of industrial application, an embedded control system (ECS) requires processing a number of hard real-time tasks and needs fault-tolerance to assure high reliability. Considering the characteristics of real-time tasks in ECS, an integrated algorithm is proposed to schedule real-time tasks and to guarantee that all real-time tasks are completed before their deadlines even in the presence of faults. Based on the nonpreemptive critical-section protocol (NCSP), this paper analyzes the blocking time introduced by resource conflicts of relevancy tasks in fault-tolerant multiprocessor systems. An extended schedulability condition is presented to check the assignment feasibility of a given task to a processor. A primary/backup approach and on-line replacement of failed processors are used to tolerate processor failures. The analysis reveals that the integrated algorithm bounds the blocking time, requires limited overhead on the number of processors, and still assures good processor utilization. This is also demonstrated by simulation results. Both analysis and simulation show the effectiveness of the proposed algorithm in ECS. More... »

PAGES

191

References to SciGraph publications

  • 1991-03. Stack-based scheduling of realtime processes in REAL-TIME SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf02944797

    DOI

    http://dx.doi.org/10.1007/bf02944797

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1012297342


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Central South University", 
              "id": "https://www.grid.ac/institutes/grid.216417.7", 
              "name": [
                "College of Information Science & Engineering, Central South University, 410083, Changsha, P.R. China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yang", 
            "givenName": "Chun-Hua", 
            "id": "sg:person.014077631760.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014077631760.17"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "KU Leuven", 
              "id": "https://www.grid.ac/institutes/grid.5596.f", 
              "name": [
                "Electrical Engineering Department, Katholieke Universiteit Leuven, Kasteelpark Arenberg 10, B-3001, Leuven-Heverlee, Belgium"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deconinck", 
            "givenName": "Geert", 
            "id": "sg:person.01022745130.75", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01022745130.75"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Central South University", 
              "id": "https://www.grid.ac/institutes/grid.216417.7", 
              "name": [
                "College of Information Science & Engineering, Central South University, 410083, Changsha, P.R. China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gui", 
            "givenName": "Wei-Hua", 
            "id": "sg:person.014564074022.19", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014564074022.19"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1002/spe.4380170504", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009216296"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00365393", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014288754", 
              "https://doi.org/10.1007/bf00365393"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321738.321743", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015861653"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s1383-7621(99)00009-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021930696"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/29.5.390", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047170661"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/12.477248", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061088279"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/12.57058", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061088580"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/71.584093", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061217622"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/71.798317", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061217875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1986.1676787", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061533420"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tse.1986.6312999", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061787994"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.26.1.127", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064728873"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/empdp.2002.994300", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094548251"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ecbs.2000.839856", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094976658"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004-03", 
        "datePublishedReg": "2004-03-01", 
        "description": "With the increasing complexity of industrial application, an embedded control system (ECS) requires processing a number of hard real-time tasks and needs fault-tolerance to assure high reliability. Considering the characteristics of real-time tasks in ECS, an integrated algorithm is proposed to schedule real-time tasks and to guarantee that all real-time tasks are completed before their deadlines even in the presence of faults. Based on the nonpreemptive critical-section protocol (NCSP), this paper analyzes the blocking time introduced by resource conflicts of relevancy tasks in fault-tolerant multiprocessor systems. An extended schedulability condition is presented to check the assignment feasibility of a given task to a processor. A primary/backup approach and on-line replacement of failed processors are used to tolerate processor failures. The analysis reveals that the integrated algorithm bounds the blocking time, requires limited overhead on the number of processors, and still assures good processor utilization. This is also demonstrated by simulation results. Both analysis and simulation show the effectiveness of the proposed algorithm in ECS.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf02944797", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1320078", 
            "issn": [
              "1666-6046", 
              "1666-6038"
            ], 
            "name": "Journal of Computer Science and Technology", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "19"
          }
        ], 
        "name": "Fault-tolerant scheduling for real-time embedded control systems", 
        "pagination": "191", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "3a96e4d439e09533fbe69d6a9c5fc7d298dbdc0208b575f1a302091bb556ba3d"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02944797"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1012297342"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02944797", 
          "https://app.dimensions.ai/details/publication/pub.1012297342"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T14:32", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000373_0000000373/records_13102_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2FBF02944797"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02944797'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02944797'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02944797'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02944797'


     

    This table displays all metadata directly associated to this object as RDF triples.

    121 TRIPLES      21 PREDICATES      41 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02944797 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N2804966cef354ade9cd373d7f970b7ea
    4 schema:citation sg:pub.10.1007/bf00365393
    5 https://doi.org/10.1002/spe.4380170504
    6 https://doi.org/10.1016/s1383-7621(99)00009-0
    7 https://doi.org/10.1093/comjnl/29.5.390
    8 https://doi.org/10.1109/12.477248
    9 https://doi.org/10.1109/12.57058
    10 https://doi.org/10.1109/71.584093
    11 https://doi.org/10.1109/71.798317
    12 https://doi.org/10.1109/ecbs.2000.839856
    13 https://doi.org/10.1109/empdp.2002.994300
    14 https://doi.org/10.1109/tc.1986.1676787
    15 https://doi.org/10.1109/tse.1986.6312999
    16 https://doi.org/10.1145/321738.321743
    17 https://doi.org/10.1287/opre.26.1.127
    18 schema:datePublished 2004-03
    19 schema:datePublishedReg 2004-03-01
    20 schema:description With the increasing complexity of industrial application, an embedded control system (ECS) requires processing a number of hard real-time tasks and needs fault-tolerance to assure high reliability. Considering the characteristics of real-time tasks in ECS, an integrated algorithm is proposed to schedule real-time tasks and to guarantee that all real-time tasks are completed before their deadlines even in the presence of faults. Based on the nonpreemptive critical-section protocol (NCSP), this paper analyzes the blocking time introduced by resource conflicts of relevancy tasks in fault-tolerant multiprocessor systems. An extended schedulability condition is presented to check the assignment feasibility of a given task to a processor. A primary/backup approach and on-line replacement of failed processors are used to tolerate processor failures. The analysis reveals that the integrated algorithm bounds the blocking time, requires limited overhead on the number of processors, and still assures good processor utilization. This is also demonstrated by simulation results. Both analysis and simulation show the effectiveness of the proposed algorithm in ECS.
    21 schema:genre research_article
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf N4af7a73d06df4a00a35ec7bc568ef43c
    25 Ncd8c87908f4248edb2aef2898ca91e51
    26 sg:journal.1320078
    27 schema:name Fault-tolerant scheduling for real-time embedded control systems
    28 schema:pagination 191
    29 schema:productId N3166f2e4bc5345eaaca5c0a9ee4eb7c3
    30 N74335a13ffa94401b82aca6f1b555e7d
    31 Nee4a3969219a4dfaab9099d81be218d8
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012297342
    33 https://doi.org/10.1007/bf02944797
    34 schema:sdDatePublished 2019-04-11T14:32
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher N1db9a57fa276440487ed461170092068
    37 schema:url http://link.springer.com/10.1007%2FBF02944797
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset articles
    40 rdf:type schema:ScholarlyArticle
    41 N1db9a57fa276440487ed461170092068 schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 N2804966cef354ade9cd373d7f970b7ea rdf:first sg:person.014077631760.17
    44 rdf:rest Nd9333d6b756f4c81bf72841fed441efd
    45 N3166f2e4bc5345eaaca5c0a9ee4eb7c3 schema:name readcube_id
    46 schema:value 3a96e4d439e09533fbe69d6a9c5fc7d298dbdc0208b575f1a302091bb556ba3d
    47 rdf:type schema:PropertyValue
    48 N4af7a73d06df4a00a35ec7bc568ef43c schema:issueNumber 2
    49 rdf:type schema:PublicationIssue
    50 N74335a13ffa94401b82aca6f1b555e7d schema:name doi
    51 schema:value 10.1007/bf02944797
    52 rdf:type schema:PropertyValue
    53 N9712c6895ad648ec9714edd8b8793470 rdf:first sg:person.014564074022.19
    54 rdf:rest rdf:nil
    55 Ncd8c87908f4248edb2aef2898ca91e51 schema:volumeNumber 19
    56 rdf:type schema:PublicationVolume
    57 Nd9333d6b756f4c81bf72841fed441efd rdf:first sg:person.01022745130.75
    58 rdf:rest N9712c6895ad648ec9714edd8b8793470
    59 Nee4a3969219a4dfaab9099d81be218d8 schema:name dimensions_id
    60 schema:value pub.1012297342
    61 rdf:type schema:PropertyValue
    62 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Information and Computing Sciences
    64 rdf:type schema:DefinedTerm
    65 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Artificial Intelligence and Image Processing
    67 rdf:type schema:DefinedTerm
    68 sg:journal.1320078 schema:issn 1666-6038
    69 1666-6046
    70 schema:name Journal of Computer Science and Technology
    71 rdf:type schema:Periodical
    72 sg:person.01022745130.75 schema:affiliation https://www.grid.ac/institutes/grid.5596.f
    73 schema:familyName Deconinck
    74 schema:givenName Geert
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01022745130.75
    76 rdf:type schema:Person
    77 sg:person.014077631760.17 schema:affiliation https://www.grid.ac/institutes/grid.216417.7
    78 schema:familyName Yang
    79 schema:givenName Chun-Hua
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014077631760.17
    81 rdf:type schema:Person
    82 sg:person.014564074022.19 schema:affiliation https://www.grid.ac/institutes/grid.216417.7
    83 schema:familyName Gui
    84 schema:givenName Wei-Hua
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014564074022.19
    86 rdf:type schema:Person
    87 sg:pub.10.1007/bf00365393 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014288754
    88 https://doi.org/10.1007/bf00365393
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1002/spe.4380170504 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009216296
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1016/s1383-7621(99)00009-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021930696
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1093/comjnl/29.5.390 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047170661
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1109/12.477248 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061088279
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1109/12.57058 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061088580
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1109/71.584093 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061217622
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1109/71.798317 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061217875
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1109/ecbs.2000.839856 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094976658
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1109/empdp.2002.994300 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094548251
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1109/tc.1986.1676787 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533420
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1109/tse.1986.6312999 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061787994
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1145/321738.321743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015861653
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1287/opre.26.1.127 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728873
    115 rdf:type schema:CreativeWork
    116 https://www.grid.ac/institutes/grid.216417.7 schema:alternateName Central South University
    117 schema:name College of Information Science & Engineering, Central South University, 410083, Changsha, P.R. China
    118 rdf:type schema:Organization
    119 https://www.grid.ac/institutes/grid.5596.f schema:alternateName KU Leuven
    120 schema:name Electrical Engineering Department, Katholieke Universiteit Leuven, Kasteelpark Arenberg 10, B-3001, Leuven-Heverlee, Belgium
    121 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...