1. <wbr id="cnjas"><legend id="cnjas"></legend></wbr>

          Linux培訓
          達內IT學院

          400-111-8989

          Linux進程調度

          • 發布:Linux培訓
          • 來源:Linux教程
          • 時間:2016-08-11 14:29

          1. 早期調度算法及其缺陷

          在早期內核版本,Linux的調度算法很簡單。當需要調度時調度函數就掃描整個可運行隊列并計算進程的優先級,從中選出優先級最高的進程以替代當前占用CPU的進程。這種調度方式在設計和實現上非常簡單,只需將可運行進程組織成一個隊列,然后遍歷就可以了。但它有一個非常致命的缺陷,隨著進程數量的增加,掃描所花費的時間也隨之增加。

          2. O(1)算法

          為了解決以前版本的缺陷,2.6版本內核采用了一種較為復雜的調度策略。這種策略解決了進程調度時間隨進程數量增加的問題。它在一個固定時間內找到最佳進程。所以也被稱為O(1)算法。

          2.1與調度相關的數據結構

          進程優先級

          linux中進程的優先級范圍為0~MAX_PRIO-1,其中實時進程優先級范圍是0~MAX_RT_PRIO-1,非實時進程優先為MAX_RT_PRIO~MAX_PRIO,優先級越小表示優先級越高。實時進程的優先級總高于普通進程。

          與調度相關的數據結構

          runqueue

          每個CPU都有一個可運行隊列,調度程序從中選取需要占用CPU的進程。可運行隊列又根據時間片是否用完分為活動進程集合和過期進程集合。分別用active,expired指向他們。runqueue中有這樣一個字段:prio_array_t *active, *expired, arrays[2]。arrays為活動進程和過期進程的兩個集合。

          prio_array_t 結構定義為:

          prio_array_t 結構定義為

          nr_active:鏈表中進程描述符的數量。

          bitmap[BITMAP_SIZE]:優先級位圖。當且僅當某個優先權的進程鏈表不為空時設置相應的位標志。

          2.2 O(1)算法分析

          算法之所以能實現調度時間復雜度為O(1)。主要是在兩個方面進行了改進:

          (1)在早期內核版本中,當所有進程的時間片用完后,調度程序會掃描整個可運行隊列計算進程優先級并根據優先級分配時間片。而O(1)算法采用分散計算時間片的方法。O(1)算法中,過期進程集合中的進程時間片已用完,活動進程集合中進程時間片未用完,當一個進程用完其時間片后,它就會被放入過期進程集合中,在移動之前調度程序會重新對其分配時間片。

          (2)O(1)算法也不需要掃描整個可運行隊列以尋找最佳進程,在O(1)算法中不管是活動進程集合還是過期進程集合,各自都有140個按照優先級所劃分的進程鏈表,并且兩個集合還各有一個優先級位圖用來表示每個優先級鏈表是否為空,當調度程序尋找最佳next進程時,會在活動進程集合中利用優先級位圖從高到低找到第一個為不為0的位,從而對應到相應的進程鏈表,鏈表中的進程具有相同的優先級,取出第一個就是最佳進程也就是優先級最高的進程。當活動進程集合為空時只需交換兩個集合,也就是交換active指針和expired指針就可以了。由于進程的優先級只有140個,所以尋找最佳進程的時間是不會隨著進程數量增加而增加。

          3.schedule分析(2.6.11內核)

          next指向被選中的進程,這個進程將取代當前進程在CPU上執行。如果系統中沒有優先級高于當前進程,那么next會和current相等。不發生任何切換。

          schedule分析

          先禁止搶占,prev指向當前進程,釋放大內核鎖并讓rq指向本地cpu的運行隊列

          .schedule分析

          檢查可運行隊列是否為空,如果為空就調用idle_balance從另外一個運行隊列遷移一些可運行進程到本地運行隊列中

          schedule分析

          檢查活動進程集合中是否為空。若為空則交換活動集合和過期集合。

          schedule分析

          在活動集合中搜索一個可運行的進程。首先搜索優先級位圖第一個非0位,并找到對應的鏈表。將next指向鏈表中第一個進程。

          schedule分析

          根據進程類型及activated值更新進程的平均睡眠時間和動態優先級,activated有以下取值:

          0:進程處于TASK_RUNNING狀態。

          1:進程處于TASK_INTERRUPTIBLE或者TASK_STOPPED狀態,而且正在被系統調用服務例程或內核線程喚醒。

          2:進程處于TASK_INTERRUPTIBLE或者TASK_STOPPED狀態,而且正在被ISR或者可延遲函數喚醒。

          -1:表示從UNINTERRUPTIBLE狀態被喚醒

          UNINTERRUPTIBLE狀態

          如果prev和next是同一個進程不需要切換,否則使用函數context_switch(rq, prev, ext)切換進程,最后調用finish_task_switch(prev)做一些收尾工作。

          調用finish_task_switch(prev)

          預約申請免費試聽課

          填寫下面表單即可預約申請免費試聽!怕錢不夠?可就業掙錢后再付學費! 怕學不會?助教全程陪讀,隨時解惑!擔心就業?一地學習,可全國推薦就業!

          上一篇:Linux環境多線程編程基礎設施
          下一篇:Linux Netlink 基本使用
          • 掃碼領取資料

            回復關鍵字:視頻資料

            免費領取 達內課程視頻學習資料

          • 視頻學習QQ群

            添加QQ群:1143617948

            免費領取達內課程視頻學習資料

          Copyright ? 2021 Tedu.cn All Rights Reserved 京ICP備08000853號-56 京公網安備 11010802029508號 達內時代科技集團有限公司 版權所有

          選擇城市和中心
          黑龍江省

          吉林省

          河北省

          湖南省

          貴州省

          云南省

          廣西省

          海南省

          欧美做爰视频免费播放_做暖全过程免费的视频_性爱免费视频 百度 好搜 搜狗
          <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>