Detecting race conditions in parallel programs that use one semaphore View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1993

AUTHORS

Hsueh -I Lu , Philip N. Klein , Robert H. B. Netzer

ABSTRACT

We address a problem arising in debugging parallel programs, detecting race conditions in programs using a single semaphore for synchronization. It is NP-complete to detect races in programs that use many semaphores. For the case of a single semaphore, we give an algorithm that takes O(n1.5p) time, where p is the number of processors and n is the total number of semaphore operations executed. Our algorithm constructs a representation from which one can determine in constant time whether a race exists between two given events. More... »

PAGES

471-482

Book

TITLE

Algorithms and Data Structures

ISBN

978-3-540-57155-1
978-3-540-47918-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57155-8_272

DOI

http://dx.doi.org/10.1007/3-540-57155-8_272

DIMENSIONS

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


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/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0604", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Genetics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Brown University, 02912, Providence, RI, USA", 
          "id": "http://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912, Providence, RI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh -I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Brown University, 02912, Providence, RI, USA", 
          "id": "http://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912, Providence, RI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Klein", 
        "givenName": "Philip N.", 
        "id": "sg:person.0701364100.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0701364100.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Brown University, 02912, Providence, RI, USA", 
          "id": "http://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912, Providence, RI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Netzer", 
        "givenName": "Robert H. B.", 
        "id": "sg:person.015172024763.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015172024763.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1993", 
    "datePublishedReg": "1993-01-01", 
    "description": "We address a problem arising in debugging parallel programs, detecting race conditions in programs using a single semaphore for synchronization. It is NP-complete to detect races in programs that use many semaphores. For the case of a single semaphore, we give an algorithm that takes O(n1.5p) time, where p is the number of processors and n is the total number of semaphore operations executed. Our algorithm constructs a representation from which one can determine in constant time whether a race exists between two given events.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Santoro", 
        "givenName": "Nicola", 
        "type": "Person"
      }, 
      {
        "familyName": "Whitesides", 
        "givenName": "Sue", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57155-8_272", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57155-1", 
        "978-3-540-47918-5"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "parallel programs", 
      "race conditions", 
      "number of processors", 
      "semaphores", 
      "semaphore operations", 
      "constant time", 
      "algorithm", 
      "processors", 
      "synchronization", 
      "NPs", 
      "representation", 
      "program", 
      "time", 
      "number", 
      "operation", 
      "one", 
      "total number", 
      "conditions", 
      "cases", 
      "events", 
      "race", 
      "problem"
    ], 
    "name": "Detecting race conditions in parallel programs that use one semaphore", 
    "pagination": "471-482", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1034688863"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57155-8_272"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57155-8_272", 
      "https://app.dimensions.ai/details/publication/pub.1034688863"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_448.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-57155-8_272"
  }
]
 

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/3-540-57155-8_272'

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/3-540-57155-8_272'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57155-8_272'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-57155-8_272'


 

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

111 TRIPLES      23 PREDICATES      48 URIs      41 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57155-8_272 schema:about anzsrc-for:06
2 anzsrc-for:0604
3 schema:author Nd2d8393b6e1b4ec5a6761c6cef993a72
4 schema:datePublished 1993
5 schema:datePublishedReg 1993-01-01
6 schema:description We address a problem arising in debugging parallel programs, detecting race conditions in programs using a single semaphore for synchronization. It is NP-complete to detect races in programs that use many semaphores. For the case of a single semaphore, we give an algorithm that takes O(n1.5p) time, where p is the number of processors and n is the total number of semaphore operations executed. Our algorithm constructs a representation from which one can determine in constant time whether a race exists between two given events.
7 schema:editor N10720471ce304617b3b7d076b12a7aa2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N127f51f8e66342a6ad02ee37917b6891
12 schema:keywords NPs
13 algorithm
14 cases
15 conditions
16 constant time
17 events
18 number
19 number of processors
20 one
21 operation
22 parallel programs
23 problem
24 processors
25 program
26 race
27 race conditions
28 representation
29 semaphore operations
30 semaphores
31 synchronization
32 time
33 total number
34 schema:name Detecting race conditions in parallel programs that use one semaphore
35 schema:pagination 471-482
36 schema:productId Nb2f0e8c9669e4bd180bb9c5f88c981ee
37 Nd388fa57013849d9ad52cf5b27d4f858
38 schema:publisher N496f81da25c841d2aa253d6d1ae677db
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034688863
40 https://doi.org/10.1007/3-540-57155-8_272
41 schema:sdDatePublished 2022-05-10T10:54
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher Ne3b22558a14e49dd8d672df4d9b04c27
44 schema:url https://doi.org/10.1007/3-540-57155-8_272
45 sgo:license sg:explorer/license/
46 sgo:sdDataset chapters
47 rdf:type schema:Chapter
48 N10720471ce304617b3b7d076b12a7aa2 rdf:first N334383bbeae1481382f8c50942f8e425
49 rdf:rest Na33ea11c1b634174bd54db52d3cb3829
50 N127f51f8e66342a6ad02ee37917b6891 schema:isbn 978-3-540-47918-5
51 978-3-540-57155-1
52 schema:name Algorithms and Data Structures
53 rdf:type schema:Book
54 N334383bbeae1481382f8c50942f8e425 schema:familyName Dehne
55 schema:givenName Frank
56 rdf:type schema:Person
57 N37aa77e234334df196b0c8383b60eaf9 schema:familyName Sack
58 schema:givenName Jörg-Rüdiger
59 rdf:type schema:Person
60 N496f81da25c841d2aa253d6d1ae677db schema:name Springer Nature
61 rdf:type schema:Organisation
62 N6919e75243ea414f832eac3d0ca1b072 schema:familyName Santoro
63 schema:givenName Nicola
64 rdf:type schema:Person
65 N7ab9835184ab48e78ef518ff4d3195dc rdf:first sg:person.015172024763.29
66 rdf:rest rdf:nil
67 Na33ea11c1b634174bd54db52d3cb3829 rdf:first N37aa77e234334df196b0c8383b60eaf9
68 rdf:rest Ne5dd477e2585439a8280efbc5880f5ff
69 Nab84f1d32faf4df2966db292b3ae942b rdf:first Nc821733431e64dcdba3103fcf1cb4161
70 rdf:rest rdf:nil
71 Nb2f0e8c9669e4bd180bb9c5f88c981ee schema:name dimensions_id
72 schema:value pub.1034688863
73 rdf:type schema:PropertyValue
74 Nb316ae15d03f4e1590a31911bbb3daa1 rdf:first sg:person.0701364100.14
75 rdf:rest N7ab9835184ab48e78ef518ff4d3195dc
76 Nc821733431e64dcdba3103fcf1cb4161 schema:familyName Whitesides
77 schema:givenName Sue
78 rdf:type schema:Person
79 Nd2d8393b6e1b4ec5a6761c6cef993a72 rdf:first sg:person.013345515575.46
80 rdf:rest Nb316ae15d03f4e1590a31911bbb3daa1
81 Nd388fa57013849d9ad52cf5b27d4f858 schema:name doi
82 schema:value 10.1007/3-540-57155-8_272
83 rdf:type schema:PropertyValue
84 Ne3b22558a14e49dd8d672df4d9b04c27 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 Ne5dd477e2585439a8280efbc5880f5ff rdf:first N6919e75243ea414f832eac3d0ca1b072
87 rdf:rest Nab84f1d32faf4df2966db292b3ae942b
88 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
89 schema:name Biological Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:0604 schema:inDefinedTermSet anzsrc-for:
92 schema:name Genetics
93 rdf:type schema:DefinedTerm
94 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.40263.33
95 schema:familyName Lu
96 schema:givenName Hsueh -I
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
98 rdf:type schema:Person
99 sg:person.015172024763.29 schema:affiliation grid-institutes:grid.40263.33
100 schema:familyName Netzer
101 schema:givenName Robert H. B.
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015172024763.29
103 rdf:type schema:Person
104 sg:person.0701364100.14 schema:affiliation grid-institutes:grid.40263.33
105 schema:familyName Klein
106 schema:givenName Philip N.
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0701364100.14
108 rdf:type schema:Person
109 grid-institutes:grid.40263.33 schema:alternateName Department of Computer Science, Brown University, 02912, Providence, RI, USA
110 schema:name Department of Computer Science, Brown University, 02912, Providence, RI, USA
111 rdf:type schema:Organization
 




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


...