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": "2021-12-01T19:08", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_241.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 N54013109dba34931a1a8b71574d8b9f5
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 N69279ab693b44872827931bc456c44f7
13 N9b1de209b1d141bb8468946c8816ac05
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 N31c9c46d905e46288364a5d16d4d8d8f
52 N93b04c42e2064a47987152046068c346
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026575044
54 https://doi.org/10.1007/bf01994839
55 schema:sdDatePublished 2021-12-01T19:08
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Neb69ca4960fd4d7789bbd11e8b215f9b
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 N31c9c46d905e46288364a5d16d4d8d8f schema:name dimensions_id
63 schema:value pub.1026575044
64 rdf:type schema:PropertyValue
65 N54013109dba34931a1a8b71574d8b9f5 rdf:first sg:person.011014463413.28
66 rdf:rest Na718c0baf7d74e619eade970ef95bb1c
67 N66c11e03bae74c2d929c14cbed9f5511 rdf:first sg:person.07540250215.50
68 rdf:rest rdf:nil
69 N69279ab693b44872827931bc456c44f7 schema:issueNumber 4
70 rdf:type schema:PublicationIssue
71 N93b04c42e2064a47987152046068c346 schema:name doi
72 schema:value 10.1007/bf01994839
73 rdf:type schema:PropertyValue
74 N9b1de209b1d141bb8468946c8816ac05 schema:volumeNumber 32
75 rdf:type schema:PublicationVolume
76 Na718c0baf7d74e619eade970ef95bb1c rdf:first sg:person.014374171260.51
77 rdf:rest N66c11e03bae74c2d929c14cbed9f5511
78 Neb69ca4960fd4d7789bbd11e8b215f9b schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
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)


...