Stack-based scheduling of realtime processes View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1991-03

AUTHORS

T. P. Baker

ABSTRACT

The Priority Ceiling Protocol (PCP) of Sha, Rajkumar and Lehoczky is a policy for locking binary semaphores that bounds priority inversion (i.e., the blocking of a job while a lower priority job executes), and thereby improves schedulability under fixed priority preemptive scheduling. We show how to extend the PCP to handle: multiunit resources, which subsume binary semaphores and reader-writer locks; dynamic priority schemes, such as earliest-deadline-first (EDF), that use static “preemption levels”; sharing of runtime stack space between jobs. These extensions can be applied independently, or together. The Stack Resource Policy (SRP) is a variant of the SRP that incorporates the three extensions mentioned above, plus the conservative assumption that each job may require the use of a shared stack. This avoids unnecessary context switches and allows the SRP to be implemented very simply using a stack. We prove a schedulability result for EDF scheduling with the SRP that is tighter than the one proved previously for EDF with a dynamic version of the PCP. The Minimal SRP (MSRP) is a slightly more complex variant of the SRP, which has similar properties, but imposes less blocking. The MSRP is optimal for stack sharing systems, in the sense that it is the least restrictive policy that strictly bounds priority inversion and prevents deadlock for rate monotone (RM) and earliest-deadline-first (EDF) scheduling. More... »

PAGES

67-99

References to SciGraph publications

Journal

TITLE

Real-Time Systems

ISSUE

1

VOLUME

3

Author Affiliations

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/1402", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Economics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/14", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Economics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Florida State University", 
          "id": "https://www.grid.ac/institutes/grid.255986.5", 
          "name": [
            "Department of Computer Science, Florida State University, 32306-4019, Tallahassee, FL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Baker", 
        "givenName": "T. P.", 
        "id": "sg:person.010417336764.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010417336764.21"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0166-5316(82)90024-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007092087"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-5316(82)90024-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007092087"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321738.321743", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015861653"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00365439", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031745983", 
          "https://doi.org/10.1007/bf00365439"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00365439", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031745983", 
          "https://doi.org/10.1007/bf00365439"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02341920", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035501059", 
          "https://doi.org/10.1007/bf02341920"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02341920", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035501059", 
          "https://doi.org/10.1007/bf02341920"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(80)90123-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045125912"
        ], 
        "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.1147/sj.72.0074", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063185136"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/real.1989.63554", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086198612"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/real.1988.51121", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086251982"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/real.1990.128747", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086301510"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1991-03", 
    "datePublishedReg": "1991-03-01", 
    "description": "The Priority Ceiling Protocol (PCP) of Sha, Rajkumar and Lehoczky is a policy for locking binary semaphores that bounds priority inversion (i.e., the blocking of a job while a lower priority job executes), and thereby improves schedulability under fixed priority preemptive scheduling. We show how to extend the PCP to handle: multiunit resources, which subsume binary semaphores and reader-writer locks; dynamic priority schemes, such as earliest-deadline-first (EDF), that use static \u201cpreemption levels\u201d; sharing of runtime stack space between jobs. These extensions can be applied independently, or together. The Stack Resource Policy (SRP) is a variant of the SRP that incorporates the three extensions mentioned above, plus the conservative assumption that each job may require the use of a shared stack. This avoids unnecessary context switches and allows the SRP to be implemented very simply using a stack. We prove a schedulability result for EDF scheduling with the SRP that is tighter than the one proved previously for EDF with a dynamic version of the PCP. The Minimal SRP (MSRP) is a slightly more complex variant of the SRP, which has similar properties, but imposes less blocking. The MSRP is optimal for stack sharing systems, in the sense that it is the least restrictive policy that strictly bounds priority inversion and prevents deadlock for rate monotone (RM) and earliest-deadline-first (EDF) scheduling.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf00365393", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136406", 
        "issn": [
          "0922-6443", 
          "1573-1383"
        ], 
        "name": "Real-Time Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "3"
      }
    ], 
    "name": "Stack-based scheduling of realtime processes", 
    "pagination": "67-99", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00365393"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "44121646fd7239b5e68210ab35147bb77e3b40423802984e716409456401b1cd"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014288754"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00365393", 
      "https://app.dimensions.ai/details/publication/pub.1014288754"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-15T08:50", 
    "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/0000000374_0000000374/records_119730_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF00365393"
  }
]
 

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/bf00365393'

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/bf00365393'

Turtle is a human-readable linked data format.

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

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

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


 

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

93 TRIPLES      21 PREDICATES      37 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf00365393 schema:about anzsrc-for:14
2 anzsrc-for:1402
3 schema:author N974885ffbe7d40f6b09f9095be778fe0
4 schema:citation sg:pub.10.1007/bf00365439
5 sg:pub.10.1007/bf02341920
6 https://doi.org/10.1016/0020-0190(80)90123-4
7 https://doi.org/10.1016/0166-5316(82)90024-4
8 https://doi.org/10.1109/12.57058
9 https://doi.org/10.1109/real.1988.51121
10 https://doi.org/10.1109/real.1989.63554
11 https://doi.org/10.1109/real.1990.128747
12 https://doi.org/10.1145/321738.321743
13 https://doi.org/10.1147/sj.72.0074
14 schema:datePublished 1991-03
15 schema:datePublishedReg 1991-03-01
16 schema:description The Priority Ceiling Protocol (PCP) of Sha, Rajkumar and Lehoczky is a policy for locking binary semaphores that bounds priority inversion (i.e., the blocking of a job while a lower priority job executes), and thereby improves schedulability under fixed priority preemptive scheduling. We show how to extend the PCP to handle: multiunit resources, which subsume binary semaphores and reader-writer locks; dynamic priority schemes, such as earliest-deadline-first (EDF), that use static “preemption levels”; sharing of runtime stack space between jobs. These extensions can be applied independently, or together. The Stack Resource Policy (SRP) is a variant of the SRP that incorporates the three extensions mentioned above, plus the conservative assumption that each job may require the use of a shared stack. This avoids unnecessary context switches and allows the SRP to be implemented very simply using a stack. We prove a schedulability result for EDF scheduling with the SRP that is tighter than the one proved previously for EDF with a dynamic version of the PCP. The Minimal SRP (MSRP) is a slightly more complex variant of the SRP, which has similar properties, but imposes less blocking. The MSRP is optimal for stack sharing systems, in the sense that it is the least restrictive policy that strictly bounds priority inversion and prevents deadlock for rate monotone (RM) and earliest-deadline-first (EDF) scheduling.
17 schema:genre research_article
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf N70152f58b2584d63bf942621de37f693
21 Nd9a319eb09b3488786aaaf778b2b1619
22 sg:journal.1136406
23 schema:name Stack-based scheduling of realtime processes
24 schema:pagination 67-99
25 schema:productId N7fbcdf725bf1463e9c9095179dcb6390
26 Nccd6d1a80b9946da95c33110f296ea59
27 Ne5b7e5f8415546a6aa4566ee33496b4d
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014288754
29 https://doi.org/10.1007/bf00365393
30 schema:sdDatePublished 2019-04-15T08:50
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N7b00dadf70cd48b9a4cc9703bd9b30cf
33 schema:url http://link.springer.com/10.1007/BF00365393
34 sgo:license sg:explorer/license/
35 sgo:sdDataset articles
36 rdf:type schema:ScholarlyArticle
37 N70152f58b2584d63bf942621de37f693 schema:volumeNumber 3
38 rdf:type schema:PublicationVolume
39 N7b00dadf70cd48b9a4cc9703bd9b30cf schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N7fbcdf725bf1463e9c9095179dcb6390 schema:name doi
42 schema:value 10.1007/bf00365393
43 rdf:type schema:PropertyValue
44 N974885ffbe7d40f6b09f9095be778fe0 rdf:first sg:person.010417336764.21
45 rdf:rest rdf:nil
46 Nccd6d1a80b9946da95c33110f296ea59 schema:name dimensions_id
47 schema:value pub.1014288754
48 rdf:type schema:PropertyValue
49 Nd9a319eb09b3488786aaaf778b2b1619 schema:issueNumber 1
50 rdf:type schema:PublicationIssue
51 Ne5b7e5f8415546a6aa4566ee33496b4d schema:name readcube_id
52 schema:value 44121646fd7239b5e68210ab35147bb77e3b40423802984e716409456401b1cd
53 rdf:type schema:PropertyValue
54 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
55 schema:name Economics
56 rdf:type schema:DefinedTerm
57 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
58 schema:name Applied Economics
59 rdf:type schema:DefinedTerm
60 sg:journal.1136406 schema:issn 0922-6443
61 1573-1383
62 schema:name Real-Time Systems
63 rdf:type schema:Periodical
64 sg:person.010417336764.21 schema:affiliation https://www.grid.ac/institutes/grid.255986.5
65 schema:familyName Baker
66 schema:givenName T. P.
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010417336764.21
68 rdf:type schema:Person
69 sg:pub.10.1007/bf00365439 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031745983
70 https://doi.org/10.1007/bf00365439
71 rdf:type schema:CreativeWork
72 sg:pub.10.1007/bf02341920 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035501059
73 https://doi.org/10.1007/bf02341920
74 rdf:type schema:CreativeWork
75 https://doi.org/10.1016/0020-0190(80)90123-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045125912
76 rdf:type schema:CreativeWork
77 https://doi.org/10.1016/0166-5316(82)90024-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007092087
78 rdf:type schema:CreativeWork
79 https://doi.org/10.1109/12.57058 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061088580
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1109/real.1988.51121 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086251982
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1109/real.1989.63554 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086198612
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1109/real.1990.128747 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086301510
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1145/321738.321743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015861653
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1147/sj.72.0074 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063185136
90 rdf:type schema:CreativeWork
91 https://www.grid.ac/institutes/grid.255986.5 schema:alternateName Florida State University
92 schema:name Department of Computer Science, Florida State University, 32306-4019, Tallahassee, FL, USA
93 rdf:type schema:Organization
 




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


...