亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        Linux內(nèi)核交互式和非交互式進(jìn)程判別算法的質(zhì)疑

        2010-06-29 06:12:10科,
        關(guān)鍵詞:批處理內(nèi)核隊(duì)列

        張 科, 楊 斌

        (西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院,四川成都610031)

        在Linux2.6.18的內(nèi)核中,調(diào)度程序采用了動態(tài)優(yōu)先級、O(1)調(diào)度算法、時(shí)間片粒度、內(nèi)核搶占點(diǎn)和進(jìn)程分類一系列提高內(nèi)核運(yùn)行效率的算法和策略,使得系統(tǒng)的運(yùn)行更加流暢和高效。內(nèi)核將進(jìn)程分為實(shí)時(shí)進(jìn)程和非實(shí)時(shí)進(jìn)程,在Linux操作系統(tǒng)下運(yùn)行的進(jìn)程默認(rèn)情況下都是非實(shí)時(shí)進(jìn)程,非實(shí)時(shí)進(jìn)程又分為交互式進(jìn)程和批處理進(jìn)程。

        交互式進(jìn)程的定義:進(jìn)程需要和用戶進(jìn)行交互,花大量的時(shí)間等待鍵盤輸入和鼠標(biāo)操作,一旦進(jìn)程接受到輸入,必須被盡快喚醒。通常來說,平均延遲時(shí)間是在50-150ms之間[1]。

        批處理進(jìn)程的定義:進(jìn)程在系統(tǒng)后臺運(yùn)行,不需要用戶的干預(yù),不需要被系統(tǒng)盡快響應(yīng),經(jīng)常被調(diào)度程序降低優(yōu)先級。如程序編譯器,數(shù)據(jù)庫引擎和科學(xué)計(jì)算[1]。

        被內(nèi)核認(rèn)定為交互式進(jìn)程的好處:(1)可以提升進(jìn)程的動態(tài)優(yōu)先級;(2)當(dāng)進(jìn)程的時(shí)間片使用完畢后,調(diào)度程序仍然將該進(jìn)程放到active運(yùn)行隊(duì)列末尾,而不是放到expired隊(duì)列中。這樣就可以保證交互式進(jìn)程如果處在就緒隊(duì)列中,能夠有很高的優(yōu)先級先被執(zhí)行,反映在用戶層面即有很快的響應(yīng)速度。

        1 與交互式進(jìn)程識別相關(guān)的變量和函數(shù)

        1.1 與交互式進(jìn)程判別相關(guān)的變量

        與交互式進(jìn)程判別相關(guān)的變量有:prio:動態(tài)優(yōu)先級;static-prio:靜態(tài)優(yōu)先級;sleep-avg:平均睡眠時(shí)間;bonus:紅利;state:進(jìn)程狀態(tài);time-slice:時(shí)間片;sleep-type:睡眠類型;sleep-time:進(jìn)程阻塞時(shí)的睡眠時(shí)間;runtime:進(jìn)程占用CPU的時(shí)間。

        1.2 與交互式進(jìn)程判別相關(guān)的函數(shù)

        與交互式進(jìn)程判別相關(guān)的函數(shù)有:

        (1)do-fork:創(chuàng)建一個新進(jìn)程,其 prio、static-prio、sleep-avg都延續(xù)父進(jìn)程的值,其 time-slice為父進(jìn)程time-slice的一半。進(jìn)程創(chuàng)建完畢后被放入active運(yùn)行隊(duì)列末尾。

        (2)每當(dāng)系統(tǒng)時(shí)鐘的一個tick產(chǎn)生時(shí),調(diào)用scheduler-tick()函數(shù),將time-slice減1,如果time-slice等于0時(shí),調(diào)用effective-prio函數(shù)重新計(jì)算動態(tài)優(yōu)先級(見動態(tài)優(yōu)先級的計(jì)算公式),調(diào)用task-timeslice重新計(jì)算時(shí)間片,然后調(diào)用TASK-INTERACTIVE來判斷進(jìn)程是否是交互式進(jìn)程(見交互式進(jìn)程的判別公式),如果是則重新添加到active隊(duì)列末尾,否則將進(jìn)程添加到expired隊(duì)列末尾。

        (3)schedule函數(shù)計(jì)算當(dāng)前進(jìn)程的run-time,即當(dāng)前進(jìn)程這次占用CPU的時(shí)間,然后計(jì)算sleep-avg(見平均睡眠時(shí)間的計(jì)算方法),接著將當(dāng)前進(jìn)程切換出CPU,在進(jìn)程優(yōu)先級位圖中查找優(yōu)先級最高的進(jìn)程,判斷該進(jìn)程上次睡眠是否是交互式睡眠,如果是則重新計(jì)算優(yōu)先級recalc-task-prio,然后調(diào)入CPU運(yùn)行。

        (4)當(dāng)進(jìn)程由于等待資源而進(jìn)入阻塞隊(duì)列,當(dāng)資源滿足的時(shí)候,系統(tǒng)通過中斷或者信號處理程序調(diào)用trywake-up函數(shù)將該阻塞的進(jìn)程放入運(yùn)行隊(duì)列,在放入運(yùn)行隊(duì)列之前,要對該進(jìn)程計(jì)算本次睡眠時(shí)間,根據(jù)本次睡眠時(shí)間重新計(jì)算該進(jìn)程的sleep-avg(見平均睡眠時(shí)間的計(jì)算方法)和動態(tài)優(yōu)先級。然后根據(jù)計(jì)算出的動態(tài)優(yōu)先級決定進(jìn)入active中對應(yīng)的優(yōu)先級隊(duì)列。

        計(jì)算進(jìn)程是否是交互式進(jìn)程,以及進(jìn)程能夠進(jìn)入active中的哪個級別的優(yōu)先級隊(duì)列和這4種情況密切相關(guān)。下面具體分析各個參數(shù)的計(jì)算方法。

        2 交互式進(jìn)程同批處理進(jìn)程的區(qū)分算法

        2.1 動態(tài)優(yōu)先級的計(jì)算公式

        式(2)中sleep-avg和bouus的關(guān)系如圖1所示。其中MAX-BONUS=10;MAX-SLEEP-AVG=1000ms該公式的含義為:將平均睡眠時(shí)間分為10個等級,平均睡眠時(shí)間越長,紅利就越高,計(jì)算出的動態(tài)優(yōu)先級也就越高。

        圖1 sleep-avg和bonus的關(guān)系

        2.2 交互式進(jìn)程的判別公式

        當(dāng)進(jìn)程的時(shí)間片使用完畢后,判斷如果進(jìn)程是交互式進(jìn)程,則將進(jìn)程添加到active隊(duì)列末尾。

        其中INTERACT IVE-DELTA為固定值2。

        由式(1)、(3)可得:

        由式(2)、(4)、(5)得出:

        即當(dāng)滿足式(6)的情況下時(shí),那么進(jìn)程就是交互式進(jìn)程。其中static-prio和sleep-avg的關(guān)系如圖2所示。

        由式(5)可見static-prio[100,139]被分為 10個等級,sleep-avg也被劃分為10個等級進(jìn)行對應(yīng)處理。

        可見當(dāng)static-prio在[136,139]之間時(shí),sleep-avg的最大值為1000ms,式(5)不能成立,故當(dāng)靜態(tài)優(yōu)先級在[136,139]之間時(shí),進(jìn)程永遠(yuǎn)不可能被識別為交互式進(jìn)程。

        2.3 平均睡眠時(shí)間的計(jì)算方法

        (1)進(jìn)程從阻塞到運(yùn)行隊(duì)列時(shí)計(jì)算的sleep-avg

        由于進(jìn)程等待資源而產(chǎn)生阻塞,進(jìn)入相應(yīng)的阻塞隊(duì)列。隨著被等待的資源釋放,進(jìn)程被喚醒,重新計(jì)算平均睡眠時(shí)間和動態(tài)優(yōu)先級,重新設(shè)置進(jìn)程狀態(tài)和sleep-type,然后將該進(jìn)程放入相應(yīng)的運(yùn)行隊(duì)列,等待調(diào)度程序調(diào)度。

        在內(nèi)核計(jì)算平均優(yōu)先級的方法如下:

        Linux內(nèi)核中存在一個交互式睡眠的時(shí)間表INTERACTIVE-SLEEP(p),公式為:

        圖2 static-prio和sleep-avg的關(guān)系

        化簡后:INTERACTIVE-SLEEP(p)=25*static-prio-2201。其中INTERACTIVE-SLEEP和static-prio的關(guān)系如圖3所示。

        如果此次的睡眠時(shí)間(即調(diào)度程序?qū)⒃撨M(jìn)程切換出CPU到該進(jìn)程重新進(jìn)入就緒隊(duì)列中的時(shí)間)大于INTERACTIVESLEEP(p),并且 sleep-avg < INTERACTIVE-SLEEP(p),將sleep-avg=INTERACTIVE-SLEEP(p)

        當(dāng)進(jìn)程因?yàn)樽x取硬盤資源而阻塞的時(shí)候,其阻塞狀態(tài)為TASK-UNINTERRUPTIBLE,當(dāng)進(jìn)程被喚醒的時(shí)候,sleeptype設(shè)置為SLEEP-NONINTERACTIVE。

        當(dāng)sleep-type為SLEEP-NONINTERACTIVE狀態(tài)的時(shí)候,如果平均睡眠時(shí)間超過閾值,或此次睡眠時(shí)間和平均睡眠時(shí)間之和超過閾值的時(shí)候,平均睡眠時(shí)間就被置為閾值。但不超過平均睡眠時(shí)間的最大值ls。

        (2)從CPU中切換下來時(shí),平均睡眠時(shí)間的計(jì)算在進(jìn)程被調(diào)度程序切換出CPU時(shí):

        其中CURRENT-BONUS=sleep-avg*MAX-BONUS/MAX-SLEEP-AVG

        可見如果平均睡眠時(shí)間越高(即該進(jìn)程越有可能是交互式進(jìn)程),其運(yùn)行時(shí)間減少得越快,sleep-avg減少得也就越慢,這樣處理的目的是保證進(jìn)程不會從交互式進(jìn)程和批處理進(jìn)程之間頻繁切換。

        這樣 :sleep-avg=sleep-avg+sleep-time-run-time。

        圖3 INTERACTIVE-SLEEP和static-prio的關(guān)系

        3 測試?yán)淘O(shè)計(jì)

        3.1 測試程序功能

        (1)在內(nèi)核中調(diào)度階段、進(jìn)程喚醒階段和時(shí)間片使用完畢階段加入打印信息

        (2)使用驅(qū)動程序打開內(nèi)核中對應(yīng)pid的打印信息

        (3)用戶測試進(jìn)程完成的功能

        打開驅(qū)動,修改內(nèi)核變量,使內(nèi)核只打印該進(jìn)程的內(nèi)核信息。

        遍歷硬盤上某個目錄下的所有文件,并讀取每個文件內(nèi)容,然后將每個文件再寫入磁盤,遍歷完所有文件后退出程序。目的:模擬編譯程序的執(zhí)行過程,判別該進(jìn)程最終是否被內(nèi)核識別出為非交互式進(jìn)程和識別的過程。

        當(dāng)進(jìn)程在shell中執(zhí)行時(shí),shell為其父進(jìn)程,該進(jìn)程被fork時(shí),sleep-avg,static-prio,prio這些都從父進(jìn)程中繼承下來,即與shell的參數(shù)相同,其他參數(shù)測試結(jié)果如表1所示。

        表1 未修改靜態(tài)優(yōu)先級時(shí)進(jìn)程的測試結(jié)果

        測試2:

        當(dāng)進(jìn)程在shell中執(zhí)行時(shí),shell為其父進(jìn)程,該進(jìn)程被fork時(shí),采用setpriority函數(shù)修改進(jìn)程的靜態(tài)優(yōu)先級為136,結(jié)果如表2所示。

        表2 設(shè)定靜態(tài)優(yōu)先級是136的測試結(jié)果

        4 總結(jié)

        根據(jù)測試結(jié)果分析,由于進(jìn)程頻繁訪問硬盤,從硬盤獲取數(shù)據(jù),不斷造成進(jìn)程阻塞,處于TASK-UNINTERRUPTIBLE阻塞狀態(tài),當(dāng)磁盤控制器將讀取的數(shù)據(jù)放入內(nèi)存中時(shí),產(chǎn)生中斷,調(diào)用try-wake-up函數(shù)喚醒進(jìn)程。由于訪問硬盤的時(shí)間比運(yùn)行時(shí)間長,造成sleep-avg的值不斷增大,最終被判定為交互式進(jìn)程。根據(jù)以上的分析:

        (1)當(dāng)進(jìn)程的靜態(tài)優(yōu)先級在[100,135]時(shí),2.6.18內(nèi)核并不能真正區(qū)分交互式進(jìn)程和批處理進(jìn)程。

        (2)當(dāng)進(jìn)程的靜態(tài)優(yōu)先級在[136,139]時(shí),不論進(jìn)程是否真的是交互式進(jìn)程,內(nèi)核一律將之識別為非交互式進(jìn)程處理。

        由于2.6.18內(nèi)核的對交互式進(jìn)程判別的不正確。當(dāng)在編寫頻繁訪問硬盤數(shù)據(jù)的程序時(shí),可以采用setpriority函數(shù)適當(dāng)?shù)亟档驮撨M(jìn)程的優(yōu)先級來保證系統(tǒng)對真正需要交互的進(jìn)程的及時(shí)響應(yīng)。

        如果不降低該進(jìn)程的優(yōu)先級,將會造成比該進(jìn)程優(yōu)先級低的真正的交互式進(jìn)程無法得到運(yùn)行而呈現(xiàn)死機(jī)的狀態(tài)。

        [1]Daniel P.Bovet,Marco Cesati.Understanding the Linux Kernel[M].O'Reilly,2005.

        [2]毛德操,胡希明.Linux內(nèi)核源代碼情景分析[M].浙江:浙江大學(xué)出版社,2001.

        [3]趙炯.Linux內(nèi)核完全剖析[M].北京:機(jī)械工業(yè)出版社,2006.

        猜你喜歡
        批處理內(nèi)核隊(duì)列
        萬物皆可IP的時(shí)代,我們當(dāng)夯實(shí)的IP內(nèi)核是什么?
        強(qiáng)化『高新』內(nèi)核 打造農(nóng)業(yè)『硅谷』
        隊(duì)列里的小秘密
        基于多隊(duì)列切換的SDN擁塞控制*
        軟件(2020年3期)2020-04-20 00:58:44
        基于嵌入式Linux內(nèi)核的自恢復(fù)設(shè)計(jì)
        Linux內(nèi)核mmap保護(hù)機(jī)制研究
        在隊(duì)列里
        豐田加速駛?cè)胱詣玉{駛隊(duì)列
        基于PSD-BPA的暫態(tài)穩(wěn)定控制批處理計(jì)算方法的實(shí)現(xiàn)
        批處理天地.文件分類超輕松
        亚洲一区二区三区免费av在线| 亚洲国产精品日韩av专区| 国产成人免费a在线视频| 国产极品喷水视频| 国产av剧情精品麻豆| 亚洲人精品午夜射精日韩| 日本高清www无色夜在线视频| 欧美日韩免费一区中文字幕| 亚洲一区亚洲二区中文字幕| 最新欧美精品一区二区三区| av潮喷大喷水系列无码| 国产综合第一夜| 亚洲性感毛片在线视频| 国产国语亲子伦亲子| 久久婷婷国产剧情内射白浆| 中文字幕有码在线视频| 91一区二区三区在线观看视频| 美女高潮黄又色高清视频免费| 国产午夜福利精品久久2021| 91极品尤物在线观看播放| 婷婷久久av综合一区二区三区| 欧美黑寡妇特a级做爰| 激情另类小说区图片区视频区 | 漂亮丰满人妻被中出中文字幕 | 精品人伦一区二区三区蜜桃91 | 色婷婷激情在线一区二区三区| 国产av剧情刺激对白| 性色做爰片在线观看ww| 亚洲爆乳大丰满无码专区| 高清不卡av在线播放| 国产乱人偷精品人妻a片| 色妺妺视频网| 按摩师玩弄少妇到高潮hd| 免费久久99精品国产| 久热综合在线亚洲精品| 国产人成无码视频在线1000 | 韩国美女主播国产三级| 精品人妻av一区二区三区| 免费a级毛片无码a∨免费软件| 乱色视频中文字幕在线看| 国产一区二区三区色哟哟 |