一種基於並行應用階段檢測的虛擬時間片調度方法及系統與流程

2023-06-06 03:04:21

本發明屬於虛擬化計算技術領域，更具體地，涉及一種基於並行應用階段檢測的虛擬時間片調度方法及系統。

背景技術：

隨著多核架構和虛擬化技術的快速發展，眾多學術機構和企業開始嘗試將不同的應用負載放到雲端來運行，其中就包含並行應用。為了提高資源的利用率，虛擬化技術可以將多個獨立的應用負載整合到同一個物理硬體系統中，然而這將會導致遠超物理cpu數量的虛擬cpu被運行在這些物理cpu上，這種資源的過載現象使得並行應用在運行過程中受到嚴重的性能損失。

眾所周知，一個並行應用在運行過程中，計算階段和通信階段交替執行，通常情況下通信階段的同步開銷對整體性能有著很重要的影響。並行應用的同步方法可以用幾種方式實現，例如在共享內存多線程模型中使用鎖或在分布式內存模型中使用消息傳遞接口(messagepassinginterface，mpi)。

在一個多線程應用中，高性能低開銷的自旋鎖(spinlock)或者屏障(barrier)通常被用來解決多個線程訪問同一資源時的競爭問題。在原生作業系統中，自旋鎖的使用是為了保護較短的臨界區，當自旋鎖已經被佔用時，其他試圖獲取此鎖的線程將會忙等待直到鎖被釋放；當一個線程獲取自旋鎖後，作業系統將會禁用搶佔以避免臨界區代碼的執行被打斷。然而在虛擬化環境中，一個持有自旋鎖的線程可能會由於虛擬機cpu(即vcpu)調度被虛擬機監控器(virtualmachinemonitor，vmm)搶佔，此時等待獲取鎖的vcpu將會忙等待很長的時間直到持有鎖的vcpu被再次調度並釋放此鎖，這將會導致大量的cpu資源被浪費，嚴重影響了並行應用的性能。在使用屏障的多線程應用中也存在類似的問題。例如，openmp中使用屏障進行同步的線程將會在被阻塞之前自旋指定的次數(默認值為300000)。在過載的虛擬化環境下，即使一個線程已經到達屏障，但如果其他線程被vmm搶佔，那麼該線程也得忙等待很長時間直到其他線程也到達此屏障，這將會使同步點被大幅延後並嚴重影響並行應用的性能。

在使用消息傳遞編程模型的並行應用中，多機上進程間的同步需要通過網絡消息的收發來進行，例如，一個虛擬機上運行的消息發送進程在執行發送操作時，必須收到其他虛擬機中消息接收進程的確認信息後才能發送消息。當應用程式需要進行大量的通信操作並處於過載的虛擬化環境中時，消息收發例程會給內核的網絡協議棧和i/o復用機製造成很大的壓力，具體來說，網絡協議棧和i/o復用機制在內核實現中使用的自旋鎖也會被vmm搶佔，從而造成cpu資源的浪費和應用程式性能的損失。

針對並行應用在虛擬化環境下的性能問題，目前的方法包括軟體優化方法和硬體優化方法。軟體優化方法是通過優化vcpu調度算法來提升性能，典型的軟體優化方法包括協同調度和平衡調度，協同調度是通過侵入式的方法獲取虛擬機內部自旋鎖的使用情況來判斷應用程式的類型，若是並行應用則將虛擬機的vcpu同時在各個物理cpu上進行調度，進而提升同步效率。然而這種方法打破了虛擬化層的透明性，並且對於像使用openmp庫的多線程應用來說，由於自旋發生在用戶態而非內核態，所以vmm很難感知到應用的類型，所以協同調度對這類應用不適用。平衡調度是把一個虛擬機的所有vcpu分派到不同的物理cpu隊列上運行，這就增大了所有vcpu被同時調度的概率，進而提升了並行應用的性能。然而當虛擬cpu數量遠多於物理cpu數量時，同一虛擬機所有vcpu被同時調度的概率大大降低，性能提升非常有限；再者，如果vcpu的分派策略使用不恰當，將會造成負載的不均，進而損害應用的性能。針對硬體優化方法，較新的intel處理器上集成的ple機制和amd處理器上集成的pf機制能夠在檢測到虛擬機上有大量的自旋等待時將vcpu強制調度出去，然而這種機制只能被用到全虛擬化系統中，對半虛擬系統不適用。為了解決上述問題，本發明試圖探尋一種更通用的調度方法，不管應用程式的同步需求在用戶態還是在內核態，不管整個系統是全虛擬化還是半虛擬化，都能使得並行應用的性能得到大幅提升。

技術實現要素：

針對現有技術的以上缺陷或改進需求，本發明提供了一種基於並行應用階段檢測的虛擬時間片調度方法及系統，可以根據並行應用的不同執行階段自適應地調節虛擬機的時間片，從而更好地滿足並行應用的計算和通信需求並能夠顯著提升其性能。由此解決現有技術中針對並行應用在虛擬化環境下的性能問題。

為實現上述目的，按照本發明的一個方面，提供了一種基於並行應用階段檢測的虛擬時間片調度方法，包括：

s1、對於每個虛擬機，採集當前採樣周期t內所述虛擬機中各虛擬cpu的緩存缺失信息，依據所述緩存缺失信息統計所述虛擬機的緩存缺失率，其中t為第一預設值；

s2、計算所述虛擬機的緩存缺失率相對於所述虛擬機的n個歷史採樣周期的平均緩存缺失率的變化率，確定所述虛擬機中運行的並行應用處於計算階段還是通信階段，其中，n為第二預設值；

s3、確定所述並行應用所處的執行階段後，採取與所述執行階段對應的時間片調度策略。

優選地，步驟s1包括如下子步驟：

s1.1、對於每個虛擬機，採集當前採樣周期t內所述虛擬機中各虛擬cpu的三級緩存缺失次數和指令執行數量，將所述各虛擬cpu的三級緩存缺失次數求和得到所述虛擬機的總體緩存缺失次數，將所述各虛擬cpu的指令執行數量求和得到所述虛擬機的總體指令執行數量；

s1.2、由公式miss_ratecurr＝α×總體緩存缺失次數/總體指令執行數量，計算所述虛擬機在當前採樣周期t內的緩存缺失率，其中α為第三預設值。

優選地，步驟s2包括如下子步驟：

s2.1、採用滑動窗口保存所述虛擬機在n個歷史採樣周期內的採樣數據，其中，所述採樣數據包括虛擬cpu的緩存缺失次數和指令執行數量；

s2.2、根據所述窗口中的採樣數據計算所述窗口的平均緩存缺失次數與平均指令執行數量，並由公式miss_ratewindow＝α×平均緩存缺失次數/平均指令執行數量，計算所述窗口的平均緩存缺失率；

s2.3、由公式計算所述虛擬機在當前採樣周期t內的緩存缺失率與所述窗口的平均緩存缺失率的相對變化；

s2.4、若δ在[1-ε，1+ε]之間，則表示所述並行應用進入穩定狀態，並根據所述虛擬機在當前採樣周期t內的緩存缺失率確定所述並行應用處於計算階段還是通信階段，其中ε為第四預設值；

s2.5、若δ不在[1-ε，1+ε]之間，則表示所述並行應用不再處於穩定狀態，將所述窗口中的數據全部移除並重置所述窗口大小。

優選地，所述根據所述虛擬機在當前採樣周期t內的緩存缺失率確定所述並行應用處於計算階段還是通信階段，包括：若miss_ratecurr大於θ，則確定所述並行應用處於計算階段，若miss_ratecurr不大於θ，則確定所述並行應用處於通信階段，其中θ為第五預設值。

優選地，步驟s3包括如下子步驟：

s3.1、若所述並行應用處於通信階段，則判斷上個採樣周期的虛擬機時間片是否大於預設軟邊界；若所述並行應用處於計算階段，則相對於上個採樣周期線性增加虛擬機時間片作為當前採樣周期的虛擬機時間片；

s3.2、若上個採樣周期的虛擬機時間片大於所述預設軟邊界，則相對於上個採樣周期採用指數式減小方法減小虛擬機時間片作為當前採樣周期的虛擬機時間片，否則，判斷上個採樣周期的虛擬機時間片是否大於預設硬邊界；

s3.3、若上個採樣周期的虛擬機時間片大於所述預設硬邊界，則相對於上個採樣周期線性減小虛擬機時間片作為當前採樣周期的虛擬機時間片，否則將當前採樣周期的虛擬機時間片設置為所述預設硬邊界。

按照本發明的另一方面，提供了一種基於並行應用階段檢測的虛擬時間片調度系統，包括：

採樣模塊，用於對於每個虛擬機，採集當前採樣周期t內所述虛擬機中各虛擬cpu的緩存缺失信息，依據所述緩存缺失信息統計所述虛擬機的緩存缺失率，其中t為第一預設值；

檢測模塊，用於計算所述虛擬機的緩存缺失率相對於所述虛擬機的n個歷史採樣周期的平均緩存缺失率的變化率，確定所述虛擬機中運行的並行應用處於計算階段還是通信階段，其中，n為第二預設值；

調度模塊，用於確定所述並行應用所處的執行階段後，採取與所述執行階段對應的時間片調度策略。

優選地，所述採樣模塊包括：

第一計算模塊，用於對於每個虛擬機，採集當前採樣周期t內所述虛擬機中各虛擬cpu的三級緩存缺失次數和指令執行數量，將所述各虛擬cpu的三級緩存缺失次數求和得到所述虛擬機的總體緩存缺失次數，將所述各虛擬cpu的指令執行數量求和得到所述虛擬機的總體指令執行數量；

第二計算模塊，用於由公式miss_ratecurr＝α×總體緩存缺失次數/總體指令執行數量，計算所述虛擬機在當前採樣周期t內的緩存缺失率，其中α為第三預設值。

優選地，所述檢測模塊包括：

存儲模塊，用於採用滑動窗口保存所述虛擬機在n個歷史採樣周期內的採樣數據，其中，所述採樣數據包括虛擬cpu的緩存缺失次數和指令執行數量；

第三計算模塊，用於根據所述窗口中的採樣數據計算所述窗口的平均緩存缺失次數與平均指令執行數量，並由公式miss_ratewindow＝α×平均緩存缺失次數/平均指令執行數量，計算所述窗口的平均緩存缺失率；

第四計算模塊，用於由公式計算所述虛擬機在當前採樣周期t內的緩存缺失率與所述窗口的平均緩存缺失率的相對變化；

檢測子模塊，用於在δ在[1-ε，1+ε]之間時，表示所述並行應用進入穩定狀態，並根據所述虛擬機在當前採樣周期t內的緩存缺失率確定所述並行應用處於計算階段還是通信階段，其中ε為第四預設值；

重置模塊，用於在δ不在[1-ε，1+ε]之間時，表示所述並行應用不再處於穩定狀態，將所述窗口中的數據全部移除並重置所述窗口大小。

優選地，所述檢測子模塊，具體用於在δ在[1-ε，1+ε]之間時，表示所述並行應用進入穩定狀態，若miss_ratecurr大於θ，則確定所述並行應用處於計算階段，若miss_ratecurr不大於θ，則確定所述並行應用處於通信階段，其中θ為第五預設值。

優選地，所述調度模塊包括：

第一判斷模塊，用於在所述並行應用處於通信階段時，判斷上個採樣周期的虛擬機時間片是否大於預設軟邊界；

第一調度子模塊，用於在所述並行應用處於計算階段時，相對於上個採樣周期線性增加虛擬機時間片作為當前採樣周期的虛擬機時間片；

第二調度子模塊，用於在上個採樣周期的虛擬機時間片大於所述預設軟邊界時，相對於上個採樣周期採用指數式減小方法減小虛擬機時間片作為當前採樣周期的虛擬機時間片；

第二判斷模塊，用於在上個採樣周期的虛擬機時間片不大於所述預設軟邊界時，判斷上個採樣周期的虛擬機時間片是否大於預設硬邊界；

第三調度子模塊，用於在上個採樣周期的虛擬機時間片大於所述預設硬邊界時，相對於上個採樣周期線性減小虛擬機時間片作為當前採樣周期的虛擬機時間片，否則將當前採樣周期的虛擬機時間片設置為所述預設硬邊界。

總體而言，通過本發明所構思的以上技術方案與現有技術相比，能夠取得下列有益效果：

(1)本發明從並行應用的自身特點出發，通過緩存缺失來檢測應用程式的不同執行階段並採取相應的調度策略，一方面可以維持虛擬化層的透明性，另一方面同時考慮到了並行應用內核態和用戶態的同步需求，能夠適用於各種類型的並行應用。

(2)本發明採用軟體優化的方法，通過修改vmm的調度算法來提升並行應用的性能，不僅適用於半虛擬化環境，同時也適用於全虛擬化環境，具有較強的通用性。

(3)本發明在單節點上進行緩存採樣分析與時間片調節，當節點數量增加時，仍然能夠根據應用特徵進行自適應的調節，具有很高的擴展性

(4)本發明能夠大幅提升並行應用在虛擬化環境下的運行效率，從而使得傳統環境下的高性能計算任務遷移到雲端變為可能，進而節省了用戶的成本。

附圖說明

圖1是本發明實施例公開的兩種不同類型的並行應用在虛擬化環境下的應用環境圖；

圖2是本發明實施例公開的一種基於並行應用階段檢測的虛擬時間片調度方法的流程示意圖；

圖3是本發明實施例公開的一種並行應用階段檢測的流程示意圖；

圖4是本發明實施例公開的一種時間片調節的流程示意圖；

圖5是本發明實施例公開的一種功能模塊圖。

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對本發明進行進一步詳細說明。應當理解，此處所描述的具體實施例僅僅用以解釋本發明，並不用於限定本發明。此外，下面所描述的本發明各個實施方式中所涉及到的技術特徵只要彼此之間未構成衝突就可以相互組合。

本發明針對並行應用在虛擬化環境下的性能問題，提出了一種通過檢測並行應用執行階段來動態調節時間片的方法。通過減小時間片能夠顯著降低並行應用的同步開銷，並且不同類型的並行應用在運行過程中的一個共同特點是：緩存缺失和同步開銷的變化存在一種此消彼長的關係，這恰好能夠刻畫出並行應用的特點，即計算階段和通信階段交替執行。利用這一特點，本發明可以根據並行應用的不同執行階段自適應地調節虛擬機的時間片，從而更好地滿足並行應用的計算和通信需求並能夠顯著提升其性能。

如圖1所示，虛擬化環境下典型的並行應用分為兩種，圖1(a)為一種單虛擬機中的共享內存型多線程應用，多個線程間通過同步來對共享資源進行互斥訪問；圖1(b)為另一種虛擬集群中多虛擬機之間的mpi並行應用，多機上運行的進程間通過消息傳遞來進行同步。虛擬機監控器vmm位於物理機和客戶機作業系統之間，負責管理和控制虛擬機在真實物理硬體下的運行，vmm中的vcpu調度器負責將vcpu調度到不同的物理cpu隊列中，每個vcpu都以一個固定的時間片運行。本發明在原有調度器的基礎上通過檢測並行應用的不同執行階段來動態調節虛擬機時間片，達到提高並行應用性能的目的。

如圖2所示為本發明實施例公開的一種基於並行應用階段檢測的虛擬時間片調度方法的流程示意圖，在圖2所示的方法中包括以下步驟：

s1、對於每個虛擬機，採集當前採樣周期t內虛擬機中各虛擬cpu的緩存缺失信息，依據緩存缺失信息統計虛擬機的緩存缺失率，其中t為第一預設值；

s2、計算虛擬機的緩存缺失率相對於虛擬機的n個歷史採樣周期的平均緩存缺失率的變化率，確定虛擬機中運行的並行應用處於計算階段還是通信階段，其中，n為第二預設值；n優選取值為5。

s3、確定並行應用所處的執行階段後，採取與執行階段對應的時間片調度策略。大體上，在通信階段降低時間片的長度，在計算階段增加時間片的長度，使得並行應用的計算和通信需求都可以得到充分的滿足。

作為一種可選的實施方式，步驟s1具體包括以下子步驟：

s1.1、對於每個虛擬機，採集當前採樣周期t內虛擬機中各虛擬cpu的三級緩存缺失次數和指令執行數量，將各虛擬cpu的三級緩存缺失次數求和得到虛擬機的總體緩存缺失次數，將各虛擬cpu的指令執行數量求和得到虛擬機的總體指令執行數量；t優選為1ms。

s1.2、由公式miss_ratecurr＝α×總體緩存缺失次數/總體指令執行數量，計算虛擬機在當前採樣周期t內的緩存缺失率，其中α為第三預設值，α是一個伸縮常量，用來將miss_ratecurr放大到指定數量級，以避免在vcpu調度器中進行開銷較大的浮點運算；α優選取值為104。

如圖3所示為本發明實施例公開的一種並行應用階段檢測的流程示意圖，步驟s2具體子步驟如下：

s2.1、採用滑動窗口保存虛擬機在n個歷史採樣周期內的採樣數據，其中，採樣數據包括虛擬cpu的緩存缺失次數和指令執行數量；

s2.2、根據窗口中的採樣數據計算窗口的平均緩存缺失次數與平均指令執行數量，並由公式miss_ratewindow＝α×平均緩存缺失次數/平均指令執行數量，計算窗口的平均緩存缺失率；

s2.3、由公式計算虛擬機在當前採樣周期t內的緩存缺失率與窗口的平均緩存缺失率的相對變化；

s2.4、若δ在[1-ε，1+ε]之間，則表示並行應用進入穩定狀態，則可以將窗口中的最先加入的數據移除並將新採樣的數據加入窗口，並根據虛擬機在當前採樣周期t內的緩存缺失率確定並行應用處於計算階段還是通信階段，其中ε為第四預設值，ε在本發明中可以被經驗性地設定為0.3；

其中，可以採用以下方式確定並行應用處於計算階段還是通信階段：若miss_ratecurr大於θ，則確定並行應用處於計算階段，若miss_ratecurr不大於θ，則確定並行應用處於通信階段，其中θ為第五預設值，優選地，θ在本發明中為一經驗值0.1％。

s2.5、若δ不在[1-ε，1+ε]之間，則表示並行應用不再處於穩定狀態，將窗口中的數據全部移除並重置窗口大小。

如圖4所示，當確定並行應用的具體執行階段後就可以在不同階段採取差異化的時間片調節策略，步驟s3的具體子步驟如下：

s3.1、若並行應用處於通信階段，則判斷上個採樣周期的虛擬機時間片是否大於預設軟邊界；若並行應用處於計算階段，則相對於上個採樣周期線性增加(例如每次增加100ms)虛擬機時間片作為當前採樣周期的虛擬機時間片；

s3.2、若上個採樣周期的虛擬機時間片大於預設軟邊界，則相對於上個採樣周期採用指數式減小方法減小虛擬機時間片作為當前採樣周期的虛擬機時間片(例如，每次調節時間片都較上次減小三倍)；否則，判斷上個採樣周期的虛擬機時間片是否大於預設硬邊界；

s3.3、若上個採樣周期的虛擬機時間片大於預設硬邊界，則相對於上個採樣周期線性減小(例如每次減小100ms)虛擬機時間片作為當前採樣周期的虛擬機時間片，否則將當前採樣周期的虛擬機時間片設置為預設硬邊界。

由於時間片被減小到小於預設軟邊界時，考慮到此時應用程式可能會對緩存缺失的變化比較敏感，此時採取較為保守的時間片調節方法，線性減小虛擬機的時間片；為防止無限制地減小時間片，本發明採取預設硬邊界控制時間片調節的下界；優選地，預設軟邊界可以被指定為1ms，預設硬邊界可以被設定為0.3ms。

如圖5所示為本發明實施例公開的一種功能模塊圖，在圖5所示的系統中包括：

採樣模塊，用於對於每個虛擬機，採集當前採樣周期t內虛擬機中各虛擬cpu的緩存缺失信息，依據緩存缺失信息統計所述虛擬機的緩存缺失率，其中t為第一預設值；

檢測模塊，用於計算虛擬機的緩存缺失率相對於虛擬機的n個歷史採樣周期的平均緩存缺失率的變化率，確定虛擬機中運行的並行應用處於計算階段還是通信階段，其中，n為第二預設值；

調度模塊，用於確定並行應用所處的執行階段後，採取與執行階段對應的時間片調度策略。

其中，採樣模塊、檢測模塊以及調度模塊可以用於執行實施例1中步驟s1至s3所述的方法，具體描述詳見實施例1對所述方法的描述，在此不再贅述。

本領域的技術人員容易理解，以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精神和原則之內所作的任何修改、等同替換和改進等，均應包含在本發明的保護範圍之內。