一種cfq調度方法
2024-01-22 16:07:15
一種cfq調度方法
【專利摘要】本發明提供一種CFQ調度方法，涉及linux內核I/O調度領域，本發明首先進行組間調度，然後進行組內調度，最後進行隊列內調度；應用程式需要進行密集型I/O操作時，向內核提出請求，內核修改相關標誌，切換組間調度和組內調度方式，同時將隊列內調度時採用的電梯算法界限修改為一個頻繁訪問的區域。當某組的Intense標誌置1時，該組對應的設備優先級最高，減少了組間調度；當某組的Continue標誌置1時，該組的隊列按照I/O請求的區域分為不同隊列，使得I/O密集型請求能夠儘可能地在一個隊列中完成，減少了組內調度；當某組的Continue標誌置1時，隊列內電梯調度算法的運行界限改為head和tail，保證了密集型I/O請求被集中訪問，減少了電梯調度往返的次數。
【專利說明】—種CFQ調度方法
【技術領域】
[0001]本發明涉及Iinux內核I/O調度領域，尤其涉及一種CFQ調度方法。
【背景技術】
[0002]隨著Iinux作業系統的發展，應用程式對高性能1的要求越來越高。自2.6內核以後，Iinux內核的1調度算法增加至4種,其中CFQ (completely fair queueing)調度算法應用最為廣泛。該算法在多進程環境下能夠保證各個進程有公平的調度機會，以及1設備的QoS。但是在I/O密集型請求到來時，該算法的I/O性能會下降。首先，由於CFQ算法將設備分為不同的組，組間調度採用基於權重---時間片的方式，而對於I/O密集型請求，往往是針對單一設備，這時CFQ算法仍然有可能發生組間調度，導致對於某一設備的I/O密集型請求等待。其次，由於CFQ算法對於同組的I/O請求按照進程號分為不同的隊列，而對於密集型I/O請求，不同的進程訪問的I/O地址有一定的連續性，導致CFQ算法為了保證電梯調度的順序而在不同隊列中切換。最後，由於CFQ算法對於同一隊列的I/O請求按照電梯調度，而電梯調度算法對於上下兩個邊界附近的I/O效率較高，中間的效率較低，影響整個隊列的I/O效率。以上為提高Iinux內核的I/O調度效率，適應日益增加的應用程式需求均帶了很大的挑戰，影響了系統I/O吞吐量，進而影響應用程式運行的速度。
【發明內容】
[0003]本發明的目的在於提供一種CFQ調度方法，該方法可以克服密集型I/O請求發生時，舊的CFQ算法的I/O性能下降的難題。
[0004]為了達到上述目的，本發明採用的技術方案為:
一種CFQ調度方法，包括如下步驟:
(I)首先進行組間調度:對於進程提出的I/O請求按照所操作的設備類型分組，各組選擇對應設備類型的I/O操作,各組有對應的權重。每組設置特殊操作標誌Intense,若該標誌置I，則該組權重升為最高直至I/O操作結束。
[0005](2)然後進行組內調度:對於組內的I/O請求，根據特殊操作標誌Continue按照兩種不同的方式操作。若Continue=。，那麼組內I/O請求按照進程號分為不同的隊列；若Continue=I,那麼組內I/O請求按照I/O訪問的地址區域分為不同的隊列。當Continue=O時，head = tail =0。各隊列有對應的優先級。
[0006](3)最後進行隊列內調度:對於同一隊列中的I/O請求，採用電梯調度算法。當特殊操作標誌Continue為I時，電梯調度算法的邊界修改為head和tail。head到tail為電梯算法的一個方向，剩下的區域組成另一個方向。
[0007]上述調度方法中，被調度的1/0請求處於內核態，為了能夠適應密集型1/0操作，對於組間調度和組內調度都設置特殊操作標誌，應用程式需要進行密集型1/0操作時，向內核提出請求，內核修改相關標誌，切換組間調度和組內調度方式，同時將隊列內調度時採用的電梯算法界限修改為一個頻繁訪問的區域。其特點在於當某組的Intense標誌置I時，該組對應的設備優先級最高，減少了組間調度；當某組的Continue標誌置I時，該組的隊列按照I/O請求的區域分為不同隊列，使得I/O密集型請求能夠儘可能地在一個隊列中完成，減少了組內調度；當某組的Continue標誌置I時，隊列內電梯調度算法的運行界限改為head和tail，保證了密集型I/O請求被集中訪問，減少了電梯調度往返的次數。
[0008]上述調度方法步驟(I)的具體步驟為:
步驟a、對於進程提出的I/O請求按照所操作的設備類型分組，各組選擇對應設備類型的I/O操作；
步驟b、組間調度按照權重一時間片方式，每次優先調度時間片最小的組，高權重的組獲得的時間片小；
步驟C、每組設置特殊操作標誌Intense，若該標誌置1，則該組權重升為最高直至I/O操作結束。
[0009]上述調度方法步驟(2)的具體步驟為:
步驟a、根據特殊操作標誌Continue按照兩種不同的方式將組內I/O請求分成不同的隊列
步驟b、若Continue=。，那麼組內I/O請求按照進程號分為不同的隊列，隊列基於進程的優先級，映射為相應時間片調度，高優先級時間片小，每次選擇時間片小的優先調度。此時 head = tail =0 ；
步驟C、若Continue=I,那麼組內I/O請求按照I/O訪問的地址區域分為不同的隊列。含有I/O請求數目最多的區域為訪問熱區，head和tail對應該區域上下界。
[0010]上述調度方法步驟(3)的具體步驟為:
步驟a、隊列內調度採用電梯調度算法；
步驟b、若Continue=I,則電梯調度上下界為head和tail,優先保證訪問熱區I/O請求。
[0011]本發明可以克服Iinux內核使用舊的CFQ調度算法時，對於突發的I/O密集型請求，I/O吞吐量下降的問題，從而提高應用程式的運行效率。
[0012]相比於原來的基於權重-時間片的組間調度方式，本CFQ方法為I/O密集型操作提供特殊操作標誌，從而保證在I/o密集請求發生時，能夠保證發生I/O密集請求的設備在訪問時不被打斷。
[0013]相比於原來的基於優先級-時間片的組內調度方式，本CFQ方法為I/O密集型操作提供特殊操作標誌，從而保證在I/o密集請求發生時，使得對於同一設備的I/O請求能夠被有效地集中到幾個隊列中，減少了由於I/o請求地址不滿足連續性要求而在隊列間調度的次數。
[0014]相比於原來的電梯調度算法，本CFQ方法為I/O密集型操作提供特殊操作標誌，從而保證在I/o密集請求發生時，電梯調度的範圍集中在I/O請求的密集區域，從而保證滿足連續性要求的I/o請求優先得到滿足，減少電梯調度的往返次數。
【專利附圖】
【附圖說明】
[0015]附圖1本發明調度中組間調度示意圖。
[0016]附圖2本發明調度中組內調度示意圖。
[0017]附圖3本發明調度中隊列內調度圖。
【具體實施方式】
[0018]下面參照附圖對本發明的內容進行更加詳細的闡述:
(I)首先如圖1進行組間調度:對於進程提出的I/o請求按照所操作的設備類型分組，各組選擇對應設備類型的I/O操作，即不同的設備有不同的中斷向量。各組有對應的權重，權重越大，時間片越小，得到組間調度的機會越多，所有的組按照時間片排成一顆紅黑樹。如果某一組的特殊操作標誌Intense=I,則該組的I/O請求被優先滿足，方法是將其權重升為最高直至該組I/O請求分配完畢操作。
[0019](2)然後如圖2進行組內調度:對於組內的I/O請求，根據特殊操作標誌Continue按照兩種不同的方式分配隊列。無論哪種方式，組內的隊列按照優先級排成一顆紅黑樹。若Continue=。，那麼組內I/O請求按照進程號分為不同的隊列，優先級為進程優先級，head =tail =0 ;若Continue=I,那麼組內I/O請求按照I/O訪問的地址區域分為不同的隊列，優先級按地址區域中I/O請求的數量排序,數量越多,優先級越高。
[0020](3)最後如圖3進行隊列內調度:對於同一隊列中的I/O請求，採用電梯調度算法。若Continue=。，則隊列中的I/O請求地址的最大值和最小值成為電梯調度的邊界。若Continue=I,則隊列中的head和tail成為電梯調度的邊界電梯調度算法的邊界。其中head和tail中間的I/O請求滿足連續性要求，即平均兩個鄰近的I/O請求地址差值〈5，從而保證密集型I/O請求得到優先滿足。
【權利要求】
1.一種調度方法，其特徵在於，包括如下步驟: (1)首先進行組間調度:對於進程提出的1/0請求按照所操作的設備類型分組，各組選擇對應設備類型的1/0操作，各組有對應的權重；每組設置特殊操作標誌1111:61186，若該標誌置1，則該組權重升為最高直至1/0操作結束； (2)然後進行組內調度:對於組內的1/0請求，根據特殊操作標誌皿6按照兩種不同的方式操作；若0)1^1皿6=0，那麼組內1/0請求按照進程號分為不同的隊列；若00111:111116=1，那麼組內1/0請求按照1/0訪問的地址區域分為不同的隊列；當00111:111116=0時，1168(1 = 1:811 =0 ；各隊列有對應的優先級； (3)最後進行隊列內調度:對於同一隊列中的1/0請求，採用電梯調度算法；當特殊操作標誌0)111:111116為1時，電梯調度算法的邊界修改為11651(1和仏11:11651(1到仏11為電梯算法的一個方向，剩下的區域組成另一個方向。
2.根據權利要求1所述的方法，其特徵在於，被調度的1/0請求處於內核態，為了能夠適應密集型1/0操作，對於組間調度和組內調度都設置特殊操作標誌，應用程式需要進行密集型1/0操作時，向內核提出請求，內核修改相關標誌，切換組間調度和組內調度方式，同時將隊列內調度時採用的電梯算法界限修改為一個頻繁訪問的區域。
3.根據權利要求1所述的方法，其特徵在於， 步驟(1)的具體步驟為: 步驟^對於進程提出的1/0請求按照所操作的設備類型分組，各組選擇對應設備類型的1/0操作； 步驟I組間調度按照權重一時間片方式，每次優先調度時間片最小的組，高權重的組獲得的時間片小； 步驟每組設置特殊操作標誌11^61186，若該標誌置1，則該組權重升為最高直至1/0操作結束； 上述步驟(2)的具體步驟為: 步驟3、根據特殊操作標誌0)1^1皿6按照兩種不同的方式將組內1/0請求分成不同的隊列 步驟I若皿6=0，那麼組內1/0請求按照進程號分為不同的隊列，隊列基於進程的優先級，映射為相應時間片調度，高優先級時間片小，每次選擇時間片小的優先調度；此時 1168(1 = 1:811 =0 ； 步驟0、若皿6=1，那麼組內1/0請求按照1/0訪問的地址區域分為不同的隊列；含有1/0請求數目最多的區域為訪問熱區，1168(1和仏11對應該區域上下界； 上述步驟(3)的具體步驟為: 步驟^隊列內調度採用電梯調度算法； 步驟13、若00111:111116=1，則電梯調度上下界為11621(1和仏11,優先保證訪問熱區1/0請求。
【文檔編號】G06F13/20GK104360965SQ201410744683
【公開日】2015年2月18日 申請日期:2014年12月9日 優先權日:2014年12月9日
【發明者】鄧宇羽 申請人:浪潮電子信息產業股份有限公司