第 5 章 結論 73
になり，読み書きに要する時間はかえって長大化している．さらに，不揮発性メモリには，
一定回数の書き込みによって素子が破損し，データを格納できなくなる性質がある．SSDの ベンダは，この破損によるデータ容量の低下を隠ぺいするために，利用者に提示する容量を 超えた不揮発性メモリを事前に搭載し，定期的にデータ格納先の不揮発性メモリを切り替え ることで，書き込み回数を平準化している．このような複雑な制御により，SSDの性能は，
ますます向上しづらくなっている．一方で，プロセッサやメモリの性能は，依然として速い 速度で向上しており，外部記憶装置との性能差が今後も拡大することが考えられる．このよ うな状況より，本研究で確立した制御方式は，今後も心地よいサービスの提供に有効である と考える．
第 5 章 結論 74
つことができず，心地よいサービスを提供できない場合がある．本研究では，心地よいサー ビスの提供を目指し，ソフトウェアの動作速度に大きく影響する外部記憶装置を制御して入 出力時間を一定に保つ方式を確立した．今後，計算機によるサービスは，ますます身近にな り，センサやウェアラブルデバイスといった新たなハードウェアが普及すると考えられる．
このような状況においても，利用者に心地よいサービスを提供するために，ソフトウェアの 動作速度に大きく影響するハードウェアを特定し，当該ハードウェアの制御方式を検討して いく必要がある．
謝辞 75
謝辞
本論文をまとめるにあたり，御査読頂き，かつ御助言を賜りました岡山大学 大学院自然 科学研究科 産業創成工学専攻 谷口秀夫 教授，名古屋彰 教授，高橋規一 教授に深く感謝致 します．特に，谷口秀夫 教授には，学部生の頃より15年に渡り懇切丁寧に，ときに厳しく ご指導頂きました．本論文に限らず，研究の進め方，社会人としての姿勢に至るまで幅広く ご指導頂きました．これらのご指導があってこそ，今の私があります．心より感謝申し上げ ます．
岡山大学 自然科学研究科 産業創成工学専攻 山内利宏 准教授には，学部生および博士前 期課程において，文章の書き方や評価の考え方といった基礎を根気良くかつ丁寧にご指導頂 きました．感謝申し上げます。
また，高知工科大学 情報学群 横山和俊 教授，岡山大学 田辺雅則さんには，博士課程後期 において，積極的に議論頂きましたこと，感謝申し上げます。特に，田辺雅則さんには，議 論のみならず，方式の実装においてもご助力頂きました．改めて感謝申し上げます。
岡山大学 自然科学研究科 産業創成工学専攻 乃村能成 准教授，後藤佑介 准教授には，学 部生の頃より積極的に議論頂きましたこと，感謝申し上げます。
最後に，二子を抱えた状況にも関わらず社会人博士の道を選んだことを温かく受け入れ，
かつ献身的に応援してくれた妻に感謝致します．
参考文献 76
参考文献
[1] G. E. Moore, Cramming more components onto integrated circuits, Electronics, Vol.38, No.8, Apr. 1965.
[2] P. Singh, A. Pandey and A. Mekonnen, Varying Response Ratio Priority: A Preemp-tive CPU Scheduling Algorithm (VRRP), Journal of Computer and Communications Vol.03, No.04, Apr. 2015.
[3] S. Ahmed and B. H. Ferri, Prediction-Based Asynchronous CPU-Budget Allocation for Soft-Real-Time Applications, IEEE Transactions on Computers, vol.63, no.9, pp.2343-2355, Sep. 2014.
[4] A. Chandra, M. Adler, P. Goyal and P. Shenoy, Surplus fair scheduling: A Proportional-share cpu scheduling algorithm for symmetric multiprocessors, Pro-ceedings of 4th USNIX Symposium on Operating Systems Design and Implementation (OSDI’00), pp.45-58 Oct. 2000.
[5] P. Goyal, X. Guo, H. M. Vin, K. Jeffay and H. Zhang, A Hierarchical CPU Scheduler for Multimedia Operating Systems, Proceedings of 2th USNIX Symposium on Operating Systems Design and Implementation (OSDI’96), pp.107-122, Oct. 1996.
[6] R. S. Ishwari and G. Deepa, A Priority based Round Robin CPU Scheduling Algo-rithm for Real Time Systems, International Journal of Innovations in Engineering and Technology (IJIET), Vol.1, Issue 3, pp.1-11, Oct. 2012.
[7] C. L. Liu and J. W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of ACM, Vol.20, No.1, pp.46-67, Jan. 1973.
参考文献 77
[8] S. Xi, M. Xu, C. Lu, L. T. X. Phan, C. Gill, O. Sokolsky and I. Lee, Real-time multi-core virtual machine scheduling in Xen, Proceedings of International Conference on Embedded Software (EMSOFT’14), pp. 1-10, Oct. 2014.
[9] P. Balbastre, I. Ripoll and A. Crespo, Minimum Deadline Calculation for Periodic Real-Time Tasks in Dynamic Priority Systems, IEEE Transactions on Computers, vol.57, no.1, pp.96-109, Jan. 2008.
[10] Y. Kinebuchi, M. Sugaya, S. Oikawa and T. Nakajima, Task Grain Scheduling for Hypervisor-Based Embedded System, Proceedings of 10th IEEE International Con-ference on High Performance Computing and Communications (HPCC’08), pp.190-197, Sep. 2008.
[11] J. Lee and K. G. Shin, Preempt a Job or Not in EDF Scheduling of Uniprocessor Systems, IEEE Transactions on Computers, vol.63, no.5, pp.1197-1206, May 2014.
[12] A. Burns, M. Guti´errez, M. Aldea Rivas and M. G. Harbour, A Deadline-Floor In-heritance Protocol for EDF Scheduled Embedded Real-Time Systems with Resource Sharing, IEEE Transactions on Computers, vol.64, no.5, pp.1241-1253, May 2015.
[13] R. Nathuji, A. Kansal and A. Ghaffarkhah, Q-clouds: Managing performance inter-ference effects for QoS-aware clouds, Proceedings of the 5th European conference on Computer systems (EuroSys’10), pp.237-250, Apr. 2010.
[14] 谷口 秀夫， サービス処理時間を調整するプロセスのスケジュール法， 信学論（D）, vol.J81-D-I, no.4, pp.386-392, Apr. 1998.
[15] Y. J. Yu, D. I. Shin, H. Eom and H. Y. Yeom, NCQ versus I/O scheduler: Preventing unexpected misbehaviors, ACM Transaction Storage (TOS), Vol.6, No.1, Mar. 2010.
[16] Y. Son, H. Y. Yeom and H. Han, Optimizing I/O Operations in File Systems for Fast Storage Devices, IEEE Transactions on Computers, Vol.66, No.6, pp.1071-1084, June 2017.
参考文献 78
[17] J. Kim, S. Seo, D. Jung, J. Kim and J. Huh, Parameter-Aware I/O Management for Solid State Disks (SSDs), IEEE Transactions on Computers, Vol.61, No.5, pp.636-649, May 2012.
[18] M. Kesavan, A. Gavrilovska, and K. Schwan, On Disk I/O Scheduling in Virtual Machines, The 2nd Workshop on I/O virtualization (WIOV’10), p6, Mar. 2010.
[19] Y. J. Yu, D. I. Shin, W. Shin, N. Y. Song, J. W. Choi, H. S. Kim, H. Eom, and H.
Y. Yeom, Optimizing the Block I/O Subsystem for Fast Storage Devices, ACM Transactions on Computer Systems (TOCS), Vol.32, No.6, pp1-48, June 2014.
[20] J. Yang, D. B. Minturn and F. Hady, When poll is better than interrupt, Proceedings of 10th USENIX Conference on File and Storage Technologies (FAST’12), pp.1-7, Feb.
2012.
[21] C. Xu, S. Gamage, P. N. Rao, A. Kangarlou, R. R. Kompella and D. Xu, vSlicer:
Latency-aware virtual machine scheduling via differentiated-frequency cpu slicing, Pro-ceedings of 21st International Symposium High-Performance Parallel Distribute Com-puting (HPDC’12), pp.3-14, June 2012.
[22] J. Li, R. Ma, H. Guan and D. S. L. Wei, Accurate CPU Proportional Share and Predictable I/O Responsiveness for Virtual Machine Monitor: A Case Study in Xen, IEEE Transactions on Cloud Computing, Vol.5, No.4, pp.604-616, Oct. 2017.
[23] C. Xu, S. Gamage, H. Lu, R. Kompella and D. Xu, vTurbo: Accelerating Virtual Ma-chine I/O Processing Using Designated Turbo-Sliced Core, the 2013 USENIX Annual Technical Conference (USENIX ATC’13), pp.243-254, June 2013.
[24] E. Seppanen, M. O Keefe and D. Lilja, High performance solid state storage un-der Linux, Proceedings of IEEE 26th Symposium Mass Storage Systtem Technology (MSST’10), pp.1-12, May 2010.
[25] G. Basavaraju, P. K. Kondugari and Shankaraiah, Accelarting the performance of Disk with re-oredering of an input/output requests at virtual machine monitor level,
参考文献 79
Proceedings of IEEE International Conference on Computer Communication and Systems (ICCCS’14), pp.245-247, Aug. 2014.
[26] S. Iyer and P. Druschel, Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O, Proceedings of the eighteenth ACM symposium on Operating systems principles(SOSP’01), pp.117-130, Sep. 2001.
[27] X. Zhang, K. Davis and S. Jiang, Opportunistic Data-driven Execution of Paral-lel Programs for Efficient I/O Services, 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS’12), pp.330-341, May 2012.
[28] S. Byna, Y. Chen, X. Sun, R. Thakur and W. Gropp, Parallel I/O prefetching using MPI file caching and I/O signatures, Proceedings of the 2008 ACM/IEEE Conference on Supercomputing (SC’08), pp.1-12, Nov. 2008.
[29] S. H. Baek and K. H. Park, Prefetching with Adaptive Cache Culling for Striped Disk Arrays, Proceedings of USENIX 2008 Annual Technical Conference (USENIX ATC’08), pp.363-376, June 2008.
[30] B. L. Worthington, G. R. Ganger and Y. N. Patt, Scheduling algorithms for modern disk drives, ACM Sigmetrics Performance Evalution Review, Vol.22, Issue 1, pp.241-251, May 1994.
[31] C. R. Lumb, J. Schindler, G. R. Ganger and D. F. Nagle, Towards higher disk head utilization: extracting free bandwidth from busy disk drives, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation (OSDI’00), Vol.4, No.7, pp.87-102, Oct. 2000.
[32] C. R. Lumb, J. Schindler and G. R. Ganger, Freeblock Scheduling Outside of Disk Firmware, Proceedings of 1st USENIX Conference on File and Storage Technologies (FAST’02), pp.275-288, Jan. 2002.
[33] N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Daivs, M. Manasse, R. Panigrahy,
参考文献 80
Design Tradeoffs for SSD Performance, Proceedings of USENIX 2008 Annual Technical Conference (USENIX ATC’08), pp.57-70, June 2008.
[34] H. Jo, S. Kim, S. Kim, J. Jeong and J. Lee, Request-aware Cooperative I/O Scheduling for Scale-out Database Applications, Proceedings of 9th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage’17), July 2017.
[35] Y. Joo, J. Ryu, S. Park and K. G. Shin, FAST: Quick Application Launch on Solid-State Drives, Journal of Computer Science and Technology, Vol.27, Issue 4, pp.727-743, July 2012.
[36] R. C. Chiang, A. J. Uppal and H. H. Huang, An Adaptive IO Prefetching Approach for Virtualized Data Centers, IEEE Transactions on Services Computing, Vol.10, No.3, pp.328-340, May 2017.
[37] S. Park and K. Shen. FIOS: A Fair, Efficient Flash I/O Scheduler, Proceedings of 10th USENIX Conference on File and Storage Technologies (FAST’12), pp.1-15, Feb.
2012.
[38] Y. Won, J. Jung, G. Choi, J. Oh, S. Son, J. Hwang, and S. Cho. Barrier-enabled IO stack for flash storage, Proceedings of 16th USENIX Conference on File and Storage Technologies (FAST’18), pp.211-226, Feb. 2018.
[39] G. Jiang and Z. Yu, Design and Implementation of I/O Scheduling Algorithm Base on RAID Controller, Proceedings of 2010 International Symposium on Intelligence Information Processing and Trusted Computing (IPTC’10), pp.679-682, Oct. 2010.
[40] M. H. Jo and W. W. Ro, Dynamic Load Balancing of Dispatch Scheduling for Solid State Disks, IEEE Transactions on Computers, Vol.66, No.6, pp.1034-1047, June 2017.
[41] W. Reda, M.Canini, L. Suresh, D. Kosti´c and S. Branithwaite, Rein: Taming Tail Latency in Key-Value Stores via Multiget Scheduling, Proceedings of the Twelfth European Conference on Computer Systems(EuroSys ’17), No.16, pp.95-110, Apr. 2017.
参考文献 81
[42] S. He, Y. Wang, X. Sun, C. Huang and C. Xu, Heterogeneity-Aware Collective I/O for Parallel I/O Systems with Hybrid HDD/SSD Servers, IEEE Transactions on Com-puters, Vol.66, No.6, pp.1091-1098, June 2017.
[43] S. Seelam, R. Romero, P. Teller and B. Buros, Enhancements to linux i/o scheduling, Proceedings of the Linux Symposium. pp.175-192, July 2005.
[44] S. Ibrahim, H. Jin, L. Lu, B. He and S. Wu, Adaptive Disk I/O Scheduling for MapReduce in Virtualized Environment, Proceedings of 2011 International Conference on Parallel Processing (ICPP’11), pp.335-344, Sep. 2011.
[45] N. Ramon, G. Jacobo and C. Toni, Automatic I/O Scheduler Selection Through Online Workload Analysis, Proceedings of the 9th IEEE International Conference on Autonomic and Trusted Computing (ACT2012), pp.431-438, Sep. 2012.
[46] E. Betti, S. Bak, R. Pellizzoni, M. Caccamo and L. Sha, RealTime I/O Management System with COTS Peripherals, IEEE Transactions on Computers, Vol.62, No.1, pp.45-58, Jan. 2013.
[47] S. Kim, H. Kim, J. Lee, and J. Jeong. Enlightening the I/O Path: A Holistic Approach for Application Performance, Proceedings of 15th USENIX Conference on File and Storage Technologies (FAST’17), pp.345-358, Mar. 2017.
[48] F. Blagojevi´c, C. Guyot, Q. Wang, T. Tsai, R. Mateescu and Z. Bandi´c, Priority IO Scheduling in the Cloud, Proceedings of 5th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud’13), pp.1-6, June 2013.
[49] A. Manzanares, F. Blagojevi´c, C. Guyot, IOPriority: To The Device and Beyond, Proceedings of 9th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage’17), pp.23-29, July 2017.
[50] 谷村勇輔，鯉江英隆，工藤知宏，小島功，田中良夫， ユーザによる明示的な予約に基 づき I/O 性能を保証する分散ストレージシステム， 情報処理学会論文誌コンピュー ティングシステム（ACS），Vol.5, No.3, pp.42-56, May 2012.
参考文献 82
[51] J. Bruno, J. Brustoloni, E. Gabber, B. Ozden and A. Silberschatz, Disk scheduling with quality of service guarantees, Proceedings of IEEE International Conference on Multimedia Computing and Systems (ICMCS’99), Vol.2, pp.400-405, June 1999.
[52] N. Li, H. Jiang, D. Feng and Z. Shi, Storage Sharing Optimization Under Constraints of SLO Compliance and Performance Variability, IEEE Transactions on Services Com-puting, Vol.12, No.1, pp.58-72, Jan. 2019.
[53] H. Tan, C. Li, Z. He, K. Li and K. Hwang, VMCD: A Virtual Multi-Channel Disk I/O Scheduling Method for Virtual Machines, IEEE Transactions on Services Computing, Vol.9, No.6, pp.982-995, Nov. 2016.
[54] H. Guan, R. Ma and J. Li, Workload-Aware Credit Scheduler for Improving Net-work I/O Performance in Virtualization Environment, IEEE Transactions on Cloud Computing, Vol.2, No.2, pp.130-142, Apr. 2014.
[55] H. Kim, H. Lim, J. Jeong, H. Jo and J. Lee, Task-aware virtual machine scheduling for I/O performance, Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments (VEE’09), pp.101-110, Mar. 2009.
[56] D. Aragiorgis, A. Nanos and N. Koziris, Coexisting Scheduling Policies Boosting I/O Virtual Machines, Proceedings of the 2011 international conference on Parallel Processing (ICPP’11), Vol.2, pp.407-415, Sep. 2011.
[57] N. Jain and J. Lakshmi, PriDyn: Enabling Differentiated I/O Services in Cloud Using Dynamic Priorities, IEEE Transactions on Services Computing, Vol.8, No.2, pp.212-224, Mar. 2015.
[58] P. E. Rocha and L. C. E. Bona, A QoS aware non-work-conserving disk scheduler, Proceedings of 2012 IEEE 28th Symposium on Mass Storage Systems and Technologies (MSST’12), pp.1-5, Apr. 2012.
[59] S. Yang, T. Harter, N. Agrawal, S. S. Kowsalya, A. Krishnamurthy, S. Al-Kiswany, R. T.
Kaushik, A. C. Arpaci-Dusseau and R. H. Arpaci-Dusseau, Split-level I/O scheduling,
参考文献 83
Proceedings of 25th Symposium on Operating Systems Principles (SOSP’15), pp.474-489, Oct. 2015.
[60] C. Tsai, T. Huang, E. Chu, C. Wei, Y. Tsai, An Efficient RealTime Disk-Scheduling Framework with Adaptive Quality Guarantee, IEEE Transactions on Computers, Vol.57, No.5, pp.634-657, May 2008.
[61] P. Valente and F. Checconi, High Throughput Disk Scheduling with Fair Bandwidth Distribution, IEEE Transactions on Computers, vol.59, no.9, pp.1172-1186, Sep. 2010.
[62] S. Arunagiri, Y. Kwok, P. J. Teller, R. Portillo and S. R. Seelam, FAIRIO: An Al-gorithm for Differentiated I/O Performance, Proceedings of 23rd International Sym-posium on Computer Architecture and High Performance Computing (SBAC-PAD’11), pp.88-95, Oct. 2011.
[63] A. Merchant, M. Uysal, P. Padala, X. Zhu, S. Singhal, and K. Shin. Maestro: Quality-of-Service in Large Disk Arrays, Proceedings of the 8th ACM International Conference on Autonomic computing (ICAC’11), pp.245-254, June 2011.
[64] D.Shue, M. J. Freedman and A. Shaikh, Performance Isolation and Fairness for Multi-Tenant Cloud Storage, Proceedings of 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI’12), pp.349-362, Oct. 2012.
[65] A. L. N. Reddy, J. Wyllie and K. B. R. Wijayaratne, Disk scheduling in a multimedia I/O system, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), Vol.1, Issue 1, pp.37-59, Feb. 2005.
[66] A. Povzner, T. Kaldewey, S. Brandt, R. Golding, T. M. Wong, and C. Maltzahn, Efficient guaranteed disk request scheduling with Fahrrad, Proceedings of Third ACM European Conference on Computer Systems (EuroSys 08), pp.13-25, Apr. 2008.
[67] Y. Peng and P. Varman, Fair-EDF: a latency fairness framework for shared storage systems, Proceedings of the 11th USENIX Conference on Hot Topics in Storage and File Systems (HotStorage’19), pp1-8, July 2019.
参考文献 84
[68] Y. Peng, Q. Liu and P. Varman, Latency Fairness Scheduling for Shared Storage Sys-tems, Proceedings of 2019 IEEE International Conference on Networking, Architecture and Storage (NAS’19), pp.1-8, Aug. 2019.
[69] S. Han, D. Chen, M. Xiong, K. Lam, A. K. Mok and K. Ramamritham, Schedula-bility Analysis of Deferrable Scheduling Algorithms for Maintaining Real-Time Data Freshness, IEEE Transactions on Computers, Vol.63, No.4, pp.979-994, Apr. 2014.
[70] D. Kang, S. Jung, R. Tsuruta and H. Takahashi, Range-BW: I/O Scheduler for Predicable Disk I/O Bandwidth, Proceedings of 2010 2nd International Conference on Computer Engineering and Applications (ICCEA’10), pp.175-180, Mar. 2010.
[71] Q. Zhang, D. Feng, F. Wang and Y. Xie, An Interposed I/O Scheduling Framework for Latency and Throughput Guarantees, Journal of Applied Science and Engineering (JASE), Vol.17, No.2, pp.193-202, Feb. 2014.
[72] A. Povzner, D. Sawyer, and S. Brandt, Horizon: Efficient deadline-driven disk I/O management for distributed storage systems, Processings of 19th ACM International Symposium High Performance Distributed Computer (HPDC’10), pp.1-12, June 2010.
[73] D. L. Moal, D. Molaro and J. Campello, A Real-Time File System for Constrained Quality of Service Applications, 情報処理学会論文誌コンピューティングシステム
（ACS）, Vol.3, No.1, pp.61-76, Mar. 2010.
[74] R. I. Chang, W. K. Shih and R. C. Chang, Real-Time Disk Scheduling for Multimedia Applications with Deadline-Modification-Scan Scheme, Real-Time Systems in The International Journal of Time-Critical Computing Systems, Vol.19, Issue 2, pp.149-168, Sep. 2000.
[75] H. P. Chang, R. I. Chang, W. K. Shih and R. C. Chang, Reschedulable-Group-SCAN scheme for mixed real-time/non-real-time disk scheduling in a multimedia system, Journal of Systems and Software, Vol.59, Issue 2, pp.143-152, Nov. 2001.
参考文献 85
[76] J. Zhang, A. Riska, A. Sivasubramaniam, Q. Wang and E. Riedel, Storage perfor-mance virtualization via throughput and latency control, ACM Transactions on Stor-age (TOS), Vol.2, Issue 3, pp.283-308, Aug. 2006.
[77] Y. Wu, B. Jia and Z. Qi, IO QoS: A New Disk I/O Scheduler Module with QoS Guarantee for Cloud Platform, Proceedings of 2012 4th International Symposium on Information Science and Engineering (ISISE’12), pp.441-444, Dec. 2012.
[78] Z. Yang, H. Fang, Y. Wu, C. Li, B. Zhao and H. H. Huang, Understanding the effects of hypervisor I/O scheduling for virtual machine performance interference, Proceedings of 4th IEEE International Conference on Cloud Computing Technology and Science Proceedings (CloudCom’12), pp.34-41, Dec. 2012.
[79] X. Ding, A. Xiong and C. Yang, Optimation of Xen scheduler for multitasking, Pro-ceedings of 4th International Conference on Software Engineering and Service Science (ICSESS’13), pp.754-757, May 2013.
[80] Y. Kwok, P. J. Teller and S. Arunagiri, 2TL: A Scheduling Algorithm for Meeting the Latency Requirements of Bursty I/O Streams at User-Specified Percentiles, Pro-ceedings of International Conference on Cloud and Autonomic Computing (ICCAC’17), pp.46-57, Sep. 2017.
[81] X. Ling, H. Jin, S. Ibrahim, W. Cao and S. Wu, Efficient Disk I/O Scheduling with QoS Guarantee for Xen-based Hosting Platforms, Proceedings of 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID’12), pp.81-89, May 2012.
[82] X. Ling, S. Ibrahim, S. Wu and H. Jin, Spatial Locality Aware Disk Scheduling in Virtualized Environment, IEEE Transactions on Parallel and Distributed Systems, Vol.26, No.9, pp.2571-2585, Sep. 2015.
[83] 谷口 秀夫，坂口 修， 入出力回数の制御によりサービス時間を調整する制御法， 信学 論（D）, vol.J81-D-I, no.11, pp.1211-1218, Nov. 1998.