並行処理における二次記憶スケジューラの最適化

• Item type: SIG Technical Reports(1)
• 公開日: 1988-03-15
• タイトル: 並行処理における二次記憶スケジューラの最適化
• タイトル / 言語: en
• タイトル: An Optimal Secondary Storage Scheduler for Transaction Processing
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学工学部
• 著者所属: 九州大学工学部
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Communication Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Communication Engineering, Kyushu University
• 著者名: 掛下, 哲郎; 上林, 弥彦
• 著者名(英): Tetsuro, Kakeshita; Yahiko, Kambayashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 従来行われている並行処理方式の評価は、データアクセス時間が一定であるという仮定をおいていた。しかし、仮想記憶管理を行う計算機システムにおいては、必要データが主記憶上に存在するかどうかによってデータアクセス時間が大幅に変化する。本稿では、この点に着目して最適な直列可能スケジューラに関する考察を行う。主な成果は、次の2点である。(1)データの変更を考慮した上で、必要主記憶容量と二次記憶アクセス回数の線形結合からなるコスト関数を最小化するページングアルゴリズムを示した。(2)上記のアルゴリズムを用いる最適な直列可能スケジューラは、P=NPでない限り、多項式アルゴリズムでは実現できないことを示した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Most of the work on the performance evaluation of concurrency control algorithms assumes that the data access time is invariant. In a virtual memory environment, however, the access time depends largely on whether the data is in main memory. From this viewpoint, this paper characterizes optimal serializable schedulers. Two main results are: (1) A paging algorithm, which takes data updates into consideration and minimizes a linear cost function consisting of the memory size and the number of secondary storage I/O; and (2) A proof which shows that, unless P=NP, no polynomial time algorithm can realize an optimal cost scheduler which uses the paging algorithm described above.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 1988, 号 21(1987-DBS-064), p. 1-8, 発行日 1988-03-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会