Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, andN-StepSCAN View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1992-12

AUTHORS

Tung-Shou Chen, Wei-Pang Yang, R. C. T. Lee

ABSTRACT

The amortized analysis is a useful tool for analyzing the time-complexity of performing a sequence of operations. The disk scheduling problem involves a sequence of requests in general. In this paper, the performances of representative disk scheduling algorithms,SSTF, SCAN, andN-StepSCAN, are analyzed in the amortized sense. A lower bound of the amortized complexity for the disk scheduling problem is also derived. According to our analysis,SCAN is not only better thanSSTF andN-StepSCAN, but also an optimal algorithm. Various authors have studied the disk scheduling problem based on some probability models and concluded that the most acceptable performance is obtained fromSCAN. Our result therefore supports their conclusion. More... »

PAGES

546-558

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan, ROC", 
            "Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, ROC", 
            "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Tung-Shou", 
        "id": "sg:person.011014463413.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011014463413.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan, ROC", 
            "Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, ROC", 
            "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yang", 
        "givenName": "Wei-Pang", 
        "id": "sg:person.014374171260.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014374171260.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan, ROC", 
            "Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, ROC", 
            "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lee", 
        "givenName": "R. C. T.", 
        "id": "sg:person.07540250215.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01840439", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024603098", 
          "https://doi.org/10.1007/bf01840439"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1992-12", 
    "datePublishedReg": "1992-12-01", 
    "description": "The amortized analysis is a useful tool for analyzing the time-complexity of performing a sequence of operations. The disk scheduling problem involves a sequence of requests in general. In this paper, the performances of representative disk scheduling algorithms,SSTF, SCAN, andN-StepSCAN, are analyzed in the amortized sense. A lower bound of the amortized complexity for the disk scheduling problem is also derived. According to our analysis,SCAN is not only better thanSSTF andN-StepSCAN, but also an optimal algorithm. Various authors have studied the disk scheduling problem based on some probability models and concluded that the most acceptable performance is obtained fromSCAN. Our result therefore supports their conclusion.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01994839", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136252", 
        "issn": [
          "0006-3835", 
          "1572-9125"
        ], 
        "name": "BIT Numerical Mathematics", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "32"
      }
    ], 
    "keywords": [
      "disk scheduling problem", 
      "scheduling problem", 
      "amortized analysis", 
      "disk scheduling algorithm", 
      "sequence of operations", 
      "sequence of requests", 
      "scheduling algorithm", 
      "amortized complexity", 
      "optimal algorithm", 
      "algorithm", 
      "acceptable performance", 
      "probability model", 
      "performance", 
      "requests", 
      "complexity", 
      "SSTF", 
      "tool", 
      "operation", 
      "sequence", 
      "useful tool", 
      "model", 
      "analysis", 
      "scans", 
      "sense", 
      "results", 
      "authors", 
      "disk", 
      "conclusion", 
      "problem", 
      "paper", 
      "representative disk scheduling algorithms", 
      "andN-StepSCAN", 
      "better thanSSTF andN-StepSCAN", 
      "thanSSTF andN-StepSCAN"
    ], 
    "name": "Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, andN-StepSCAN", 
    "pagination": "546-558", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026575044"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01994839"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01994839", 
      "https://app.dimensions.ai/details/publication/pub.1026575044"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:04", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_218.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01994839"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

116 TRIPLES      22 PREDICATES      62 URIs      52 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01994839 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 anzsrc-for:0103
4 schema:author Ncdcb10ae310e4096b96c8f7ceb5434c2
5 schema:citation sg:pub.10.1007/bf01840439
6 schema:datePublished 1992-12
7 schema:datePublishedReg 1992-12-01
8 schema:description The amortized analysis is a useful tool for analyzing the time-complexity of performing a sequence of operations. The disk scheduling problem involves a sequence of requests in general. In this paper, the performances of representative disk scheduling algorithms,SSTF, SCAN, andN-StepSCAN, are analyzed in the amortized sense. A lower bound of the amortized complexity for the disk scheduling problem is also derived. According to our analysis,SCAN is not only better thanSSTF andN-StepSCAN, but also an optimal algorithm. Various authors have studied the disk scheduling problem based on some probability models and concluded that the most acceptable performance is obtained fromSCAN. Our result therefore supports their conclusion.
9 schema:genre article
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf N44c2ca4a530849508cedf97a1695c98a
13 Ncdf722bb2b814fafb909fdbfbfea2d8d
14 sg:journal.1136252
15 schema:keywords SSTF
16 acceptable performance
17 algorithm
18 amortized analysis
19 amortized complexity
20 analysis
21 andN-StepSCAN
22 authors
23 better thanSSTF andN-StepSCAN
24 complexity
25 conclusion
26 disk
27 disk scheduling algorithm
28 disk scheduling problem
29 model
30 operation
31 optimal algorithm
32 paper
33 performance
34 probability model
35 problem
36 representative disk scheduling algorithms
37 requests
38 results
39 scans
40 scheduling algorithm
41 scheduling problem
42 sense
43 sequence
44 sequence of operations
45 sequence of requests
46 thanSSTF andN-StepSCAN
47 tool
48 useful tool
49 schema:name Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, andN-StepSCAN
50 schema:pagination 546-558
51 schema:productId N05528d9d19654bf0bf70bfdccc3a0034
52 Nb025aaa62927447092d27a56e897d510
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026575044
54 https://doi.org/10.1007/bf01994839
55 schema:sdDatePublished 2022-01-01T18:04
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Ndf8ad6ec5fa441b58cef434218a5baf5
58 schema:url https://doi.org/10.1007/bf01994839
59 sgo:license sg:explorer/license/
60 sgo:sdDataset articles
61 rdf:type schema:ScholarlyArticle
62 N05528d9d19654bf0bf70bfdccc3a0034 schema:name doi
63 schema:value 10.1007/bf01994839
64 rdf:type schema:PropertyValue
65 N44c2ca4a530849508cedf97a1695c98a schema:volumeNumber 32
66 rdf:type schema:PublicationVolume
67 N55b61c63fd914ca6ba4cfc882d7d3749 rdf:first sg:person.014374171260.51
68 rdf:rest Ne40e596972bd48988aae4aa64187019d
69 Nb025aaa62927447092d27a56e897d510 schema:name dimensions_id
70 schema:value pub.1026575044
71 rdf:type schema:PropertyValue
72 Ncdcb10ae310e4096b96c8f7ceb5434c2 rdf:first sg:person.011014463413.28
73 rdf:rest N55b61c63fd914ca6ba4cfc882d7d3749
74 Ncdf722bb2b814fafb909fdbfbfea2d8d schema:issueNumber 4
75 rdf:type schema:PublicationIssue
76 Ndf8ad6ec5fa441b58cef434218a5baf5 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 Ne40e596972bd48988aae4aa64187019d rdf:first sg:person.07540250215.50
79 rdf:rest rdf:nil
80 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
81 schema:name Mathematical Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
84 schema:name Applied Mathematics
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
87 schema:name Numerical and Computational Mathematics
88 rdf:type schema:DefinedTerm
89 sg:journal.1136252 schema:issn 0006-3835
90 1572-9125
91 schema:name BIT Numerical Mathematics
92 schema:publisher Springer Nature
93 rdf:type schema:Periodical
94 sg:person.011014463413.28 schema:affiliation grid-institutes:grid.38348.34
95 schema:familyName Chen
96 schema:givenName Tung-Shou
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011014463413.28
98 rdf:type schema:Person
99 sg:person.014374171260.51 schema:affiliation grid-institutes:grid.38348.34
100 schema:familyName Yang
101 schema:givenName Wei-Pang
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014374171260.51
103 rdf:type schema:Person
104 sg:person.07540250215.50 schema:affiliation grid-institutes:grid.38348.34
105 schema:familyName Lee
106 schema:givenName R. C. T.
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50
108 rdf:type schema:Person
109 sg:pub.10.1007/bf01840439 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024603098
110 https://doi.org/10.1007/bf01840439
111 rdf:type schema:CreativeWork
112 grid-institutes:grid.38348.34 schema:alternateName Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC
113 schema:name Department of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan, ROC
114 Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC
115 Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, ROC
116 rdf:type schema:Organization
 




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


...