M-RSF: a multilevel feedback queue task scheduling mechanism for Unikernel

DONG Bonan; YANG Qiusong; LI Mingshu

doi:10.11959/j.issn.1000-436x.2024061

您当前的位置：

首页 >

文章列表页 >

M-RSF: a multilevel feedback queue task scheduling mechanism for Unikernel

Papers | 更新时间：2024-06-24

- M-RSF: a multilevel feedback queue task scheduling mechanism for Unikernel
- Journal on Communications Vol. 45, Issue 5, Pages: 54-69(2024)
- 作者机构：
  
  1.中国科学院大学，北京 100049
  2.中国科学院软件研究所基础软件国家工程研究中心，北京 100190
- 作者简介：
- 基金信息：
  
  The Strategic Priority Research Program of Chinese Academy of Sciences(XDA-Y01-01;XDC02010600)
- DOI：10.11959/j.issn.1000-436x.2024061
  CLC： TP302
- Received：27 October 2023，
  
  Revised：2024-02-19，
  
  Published：30 May 2024
- 稿件说明：
移动端阅览
董博南,杨秋松,李明树.M-RSF：面向Unikernel的一种多级反馈队列任务调度机制[J].通信学报,2024,45(05):54-69.

DONG Bonan,YANG Qiusong,LI Mingshu.M-RSF: a multilevel feedback queue task scheduling mechanism for Unikernel[J].Journal on Communications,2024,45(05):54-69.
董博南,杨秋松,李明树.M-RSF：面向Unikernel的一种多级反馈队列任务调度机制[J].通信学报,2024,45(05):54-69. DOI： 10.11959/j.issn.1000-436x.2024061.

DONG Bonan,YANG Qiusong,LI Mingshu.M-RSF: a multilevel feedback queue task scheduling mechanism for Unikernel[J].Journal on Communications,2024,45(05):54-69. DOI： 10.11959/j.issn.1000-436x.2024061.

摘要

Unikernel作为云计算领域的前沿技术，具有启动速度快和资源占用少的特点。但是，在云环境大规模任务调度场景下，目前Unikernel缺少根据其任务特点所定制的调度机制，这阻碍了Unikernel进一步发挥其性能优势。针对此问题，首先总结了Unikernel的任务特点。在此基础上，提出了一种新的面向Unikernel的多级反馈队列调度机制M-RSF及其数学模型，在不影响Unikernel结构特点的前提下，能够更有效地对云环境下Unikernel的任务进行调度。同时，基于对任务特性的深入分析，提出了一种新的负载模型，该负载模型不仅可以准确刻画Unikernel的任务特点，还可以为M-RSF中调度策略的参数设置较合理的取值。最后，对M-RSF调度机制在OSv Unikernel上进行了实现和验证，实验结果表明，M-RSF可以有效减少OSv Unikernel在大规模任务调度时的平均等待时间和平均周转时间，相比于未经改动的OSv Unikernel，平均等待时间和平均周转时间减少达15%以上。

Abstract

Unikernel

as a cutting-edge technology in the field of cloud computing

is characterized by its fast start-up speed and minimal resource usage. However

in the context of large-scale task scheduling in cloud environments

Unikernel currently lacks a customized scheduling mechanism based on its task characteristics

which hinders the further exploitation of its performance advantages. To address this issue

the distinctive task characteristics of Unikernel were initially summarized. Subsequently

a novel multi-level feedback queue scheduling mechanism for Unikernel

referred to as M-RSF

along with its mathematical model

were proposed. Without affecting the structural features of Unikernel

this mechanism could more effectively schedule Unikernel tasks in cloud environments. Meanwhile

a new load model was put forward based on an in-depth analysis of task characteristics. The model not only accurately depicted the task characteristics of Unikernel but also provided a more reasonable value setting for the scheduling policy parameters in M-RSF. Lastly

the implementation and validation of the M-RSF scheduling mechanism on the OSv Unikernel were conducted. Experimental results indicate that M-RSF can effectively reduce the average waiting time and average turnaround time of the OSv Unikernel during large-scale task scheduling

achieving a reduction of more than 15% compared to the unmodified OSv Unikernel.

关键词

Keywords

references

ALAM T . Cloud computing and its role in the information technology [J ] . IAIC Transactions on Sustainable Digital Innovation (ITSDI) , 2020 , 1 ( 2 ): 108 - 115 .

MADHAVAPEDDY A , MORTIER R , ROTSOS C , et al . Unikernels [J ] . ACM SIGARCH Computer Architecture News , 2013 , 41 ( 1 ): 461 - 472 .

GOETHALS T , SEBRECHTS M , ATREY A , et al . Unikernels vs containers: an in-depth benchmarking study in the context of microservice applications [C ] // Proceedings of the 2018 IEEE 8th International Symposium on Cloud and Service Computing (SC2) . Piscataway : IEEE Press , 2018 : 1 - 8 .

AGACHE A , BROOKER M , FLORESCU A . Firecracker: lightweight virtualization for serverless applications [C ] // Proceedings of the 17th Usenix Conference on Networked Systems Design and Implementation . Berkeley : USENIX Association , 2020 : 419 - 434 .

KUENZER S , BĂDOIU V A , LEFEUVRE H , et al . Unikraft: fast, specialized unikernels the easy way [C ] // Proceedings of the Sixteenth European Conference on Computer Systems . New York : ACM Press , 2021 : 376 - 394 .

XAVIER B , FERRETO T , JERSAK L . Time provisioning evaluation of KVM, docker and unikernels in a cloud platform [C ] // Proceedings of the 2016 16th IEEE/ACM International Symposium on Cluster , Cloud and Grid Computing (CCGrid) . Piscataway : IEEE Press , 2016 : 277 - 280 .

LI Z , CHENG J , CHEN Q , et al . RunD: a lightweight secure container runtime for high-density deployment and high-concurrency startup in serverless computing [C ] // Proceedings of 2022 USENIX Annual Technical Conference . Berkeley : USENIX Association , 2022 : 53 - 68 .

IMADA T . MirageOS unikernel with network acceleration for IoT cloud environments [C ] // Proceedings of the 2018 2nd International Conference on Cloud and Big Data Computing . New York : ACM Press , 2018 : 1 - 5 .

ZHANG Y , CROWCROFT J , LI D , et al . KylinX: a dynamic library operating system for simplified and efficient cloud virtualization [C ] // Proceedings of the 2018 Annual Technical Conference . Piscataway : IEEE Press , 2018 : 173 - 186 .

KIVITY A , LAOR D , COSTA G , et al . OSv-optimizing the operating system for virtual machines [C ] // Proceedings of the 2014 Annual Technical Conference . Piscataway : IEEE Press , 2014 : 61 - 72 .

EL-SHARAWY E E . A review on the CPU scheduling algorithms: comparative study [J ] . International Journal of Network Security , 2021 , 21 ( 1 ): 19 - 26 .

SHEN Z M , SUN Z , SELA G E , et al . X-containers: breaking down barriers to improve performance and isolation of cloud-native containers [C ] // Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems . New York : ACM Press , 2019 : 121 - 135 .

RAZA A , UNGER T , BOYD M , et al . Unikernel linux (UKL) [C ] // Proceedings of the Eighteenth European Conference on Computer Systems . New York : ACM Press , 2023 : 590 - 605 .

LI T , BAUMBERGER D , KOUFATY D A , et al . Efficient operating system scheduling for performance-asymmetric multi-core architectures [C ] // Proceedings of the 2007 ACM/IEEE conference on Supercomputing . New York : ACM Press , 2007 : 1 - 11 .

GHAFARI R , KABUTARKHANI F H , MANSOURI N . Task scheduling algorithms for energy optimization in cloud environment: a comprehensive review [J ] . Cluster Computing , 2022 , 25 ( 2 ): 1035 - 1093 .

BRATTERUD A , WALLA A A , HAUGERUD H , et al . IncludeOS: a minimal, resource efficient unikernel for cloud services [C ] // Proceedings of the 2015 IEEE 7th International Conference on Cloud Computing Technology and Science (CloudCom) . Piscataway : IEEE Press , 2015 : 250 - 257 .

LEFEUVRE H , BĂDOIU V A , JUNG A , et al . FlexOS: towards flexible OS isolation [C ] // Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems . New York : ACM Press , 2022 : 467 - 482 .

LANKES S , PICKARTZ S , BREITBART J . HermitCore: a unikernel for extreme scale computing [C ] // Proceedings of the 6th International Workshop on Runtime and Operating Systems for Supercomputers . New York : ACM Press , 2016 : 1 - 8 .

ALHAIDARI F , BALHARITH T Z . Enhanced round-robin algorithm in the cloud computing environment for optimal task scheduling [J ] . Computers , 2021 , 10 ( 5 ): 63 - 75 .

RAZA A , SOHAL P , CADDEN J , et al . Unikernels: the next stage of linux’s dominance [C ] // Proceedings of the Workshop on Hot Topics in Operating Systems . New York : ACM Press , 2019 : 7 - 13 .

ZHAO Y , SUO K , WU X F , et al . Preemptive multi-queue fair queuing [C ] // Proceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing . New York : ACM Press , 2019 : 147 - 158 .

PEMASINGHE S , RAJAPAKSHA S . Comparison of CPU scheduling algorithms: FCFS, SJF, SRTF, round robin, priority based, and multilevel queuing [C ] // Proceedings of the 2022 IEEE 10th Region 10 Humanitarian Technology Conference (R10-HTC) . Piscataway : IEEE Press , 2022 : 318 - 323 .

CHEN K-H , GÜNZEL M , JABLKOWSKI B . Unikernel-based real-time virtualization under deferrable servers: analysis and realization [C ] // Proceedings of 2022 34th Euromicro Conference on Real-Time Systems . Piscataway : IEEE Press , 2022 : 132 - 141 .

OMAR H K , JIHAD K H , HUSSEIN S F . Comparative analysis of the essential CPU scheduling algorithms [J ] . Bulletin of Electrical Engineering and Informatics , 2021 , 10 ( 5 ): 2742 - 2750 .

MOSTAFA S M , AMANO H . Dynamic round robin CPU scheduling algorithm based on K-means clustering technique [J ] . Applied Sciences , 2020 , 10 ( 15 ): 5134 .

BISWAS D , SAMSUDDOHA M , ASIF M R A , et al . Optimized round robin scheduling algorithm using dynamic time quantum approach in cloud computing environment [J ] . International Journal of Intelligent Systems and Applications , 2023 , 15 ( 1 ): 22 - 34 .

KE J C , WU C H , ZHANG Z G . Recent developments in vacation queueing models: a short survey [J ] . International Journal of Operations Research , Citeseer, 2010 , 7 ( 4 ): 3 - 8 .

ZENIL H . A review of methods for estimating algorithmic complexity: options, challenges, and new directions [J ] . Entropy , 2020 , 22 ( 6 ): 612 .

IZURIETA C , BIEMAN J . The evolution of FreeBSD and linux [C ] // Proceedings of the 2006 ACM/IEEE International Symposium on Empirical Software Engineering . New York : ACM Press , 2006 : 204 - 211 .

ADHIKARI S , ABBAS M , CHAKRABORTY M , et al . Analysis of average waiting time and server utilization factor using queueing theory in cloud computing environment [J ] . The International Journal of Nonlinear Analysis and Applications (IJNAA) , 2021 , 12 ( 3 ): 1259 - 1267 .

SHEN G B , LI Q , AI S , et al . How powerful switches should be deployed: a precise estimation based on queuing theory [C ] // Proceedings of the IEEE Conference on Computer Communications . Piscataway : IEEE Press , 2019 : 811 - 819 .

PRADOS-GARZON J , AMEIGEIRAS P , RAMOS-MUNOZ J J , et al . Performance modeling of softwarized network services based on queuing theory with experimental validation [J ] . IEEE Transactions on Mobile Computing , 2021 , 20 ( 4 ): 1558 - 1573 .

GHOMI E J , RAHMANI A M , QADER N N . Applying queue theory for modeling of cloud computing: a systematic review [J ] . Concurrency and Computation: Practice and Experience , 2019 , 31 ( 17 ): e5186 .

MAS L , VILAPLANA J , MATEO J , et al . A queuing theory model for fog computing [J ] . The Journal of Supercomputing , 2022 , 78 ( 8 ): 11138 - 11155 .

ALSULAMI A A , ABU AL-HAIJA Q , THANOON M I , et al . Performance evaluation of dynamic round robin algorithms for CPU scheduling [C ] // Proceedings of the 2019 SoutheastCon . Piscataway : IEEE Press , 2019 : 1 - 5 .

MAHESH KUMAR M R , RAJENDRA B R , NIRANJAN C K , et al . Prediction of length of the next CPU burst in SJF scheduling algorithm using dual simplex method [C ] // Proceedings of the Second International Conference on Current Trends in Engineering and Technology . Piscataway : IEEE Press , 2014 : 248 - 252 .

HELMY T , AL-AZANI S , BIN-OBAIDELLAH O . A machine learning-based approach to estimate the CPU-burst time for processes in the computational grids [C ] // Proceedings of the 2015 3rd International Conference on Artificial Intelligence, Modelling and Simulation (AIMS) . Piscataway : IEEE Press , 2015 : 3 - 8 .

YADAV R , UPADHYAY A . A fresh loom for multilevel feedback queue scheduling algorithm [J ] . International Journal of Advances in Engineering Sciences , 2012 , 2 : 21 - 23 .

SINGH J , DEEPALI G . An smarter multi queue job scheduling policy for cloud computing [J ] . International Journal of Applied Engineering Research , 2017 , 12 ( 9 ): 1929 - 1934 .

CHAHAR V , RAHEJA S . Fuzzy based multilevel queue scheduling algorithm [C ] // Proceedings of the 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI) . Piscataway : IEEE Press , 2013 : 115 - 120 .

Views

903

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Cryptographic service optimization scheduling algorithm for collaborative jobs in cloud environment

Scheduling framework based on reinforcement learning in online-offline colocated cloud environment

Time-based and privacy protection revocable and traceable data sharing scheme in cloud computing

Identity-based provable data possession scheme for multi-source IoT terminal data in public cloud

Secure and verifiable multi-keyword searchable encryption scheme in cloud

Related Author

CAO Xiaogang

LI Fenghua

GENG Kui

LI Zifu

KOU Wenlong

Ling MA

Qiliang FAN

Ting XU

Related Institution

Institute of Information Engineering, Chinese Academy of Sciences

School of Cyber Security, University of Chinese Academy of Sciences

Key Laboratory of Cyberspace Security Defense

College of Software, NanKai University

School of Computer Science, Peking University

AI问答

⁰