Linu進程調(diào)度策略與研究

Linu進程調(diào)度策略與研究Linu進程調(diào)度策略與研究/Linu進程調(diào)度策略與研究摘要多核操作系統(tǒng)已經(jīng)被廣泛應(yīng)用到我們的日常生活，并讓我們的生活更加豐富多彩,系統(tǒng)增加了處理器的數(shù)量，這允許以最大化系統(tǒng)任務(wù)來分配處理器的性能。最初，系統(tǒng)中只有一個處理器,在處理器中不用考慮進程的分布，只要根據(jù)其他標(biāo)準(zhǔn)作出判斷，現(xiàn)在增加了一個非常重要的因素，原標(biāo)準(zhǔn)必須調(diào)整到新的標(biāo)準(zhǔn).而有些CPU在處理器中閑置，有些過載,有必要進行適當(dāng)?shù)恼{(diào)整，以最大限度地提高整個系統(tǒng)的CPU利用率。如何找到這些不平衡在外觀上如何調(diào)整，為了使實施的總時間最小，Cache獲得更多使用，這將是本文的重點，從調(diào)度到優(yōu)化系統(tǒng)的性能。本課題試圖分析Linux內(nèi)核源代碼,調(diào)度工作原理和規(guī)劃進程的流程，在此基礎(chǔ)上改進系統(tǒng)。本文主要討論基于Linux的多芯片SMP的定時進程調(diào)度系統(tǒng)，主要內(nèi)容包括:1.研究進程管理調(diào)度基本原理；2.分析定時任務(wù)調(diào)度系統(tǒng),研究時間片輪轉(zhuǎn)調(diào)度機制及優(yōu)先級計算;3。在ubuntu系統(tǒng)下實現(xiàn)上面的進程調(diào)度程序。關(guān)鍵詞：linux進程調(diào)度分時任務(wù)時間片輪轉(zhuǎn)優(yōu)先級ABSTRACTMulti—coreoperatingsystemshavebeenwidelyusedinourdailylives，andmakeourlivesmorecolorful，thesystemincreasesthenumberofprocessors，whichallowstomaximizethesystemtaskstoallocateprocessorperformance。Initially，thereisonlyoneprocessorinthesystem，intheprocessordonotconsiderthedistributionoftheprocess，aslongastheothercriteriatomakejudgments,nowaddaveryimportantfactor,theoriginalstandardmustbeadjustedtothenewstandard。AndsomeCPUintheprocessoridle，someoverload,itisnecessarytomakeappropriateadjustmentstomaximizetheoverallsystemCPUutilization。Howtofindtheseimbalancesinhowtoadjust，inordertomaketheimplementationofthetotaltimeminimum,Cachegetmoreuse,itwillbethefocusofthisarticle,fromschedulingtooptimizethesystemperformance.ThistopicattemptstoanalyzetheLinuxkernelsourcecode,schedulingtheworkingprincipleandplanningprocessoftheprocess,onthebasisofimprovingthesystem.Thispapermainlydiscussesthemulti-chipSMPtimingschedulingsystembasedonLinux,themaincontentsinclude：1。Researchprocessmanagementschedulingbasicprinciples;1。Analyzethetimingtaskschedulingsystem，studythetimeslicerotationschedulingmechanismandprioritycalculation；3.Underubuntusystemtoachievetheaboveprocessscheduler.KEYWORDS:Linuxprocessschedulingtime—sharingtasktimesheetrotationpriority目錄TOC\o”1-3”\p""\h\z\uHYPERLINK\l”_Toc475091839"摘要IABSTRACTII第1章緒論1HYPERLINK\l”_Toc475091842"1。1課題研究背景及意義 1第2章進程管理及其調(diào)度 42.1基本概念 42.1.2進程在 Linux內(nèi)核中的實現(xiàn)4_Toc475091850"第3章Linux內(nèi)核任務(wù)調(diào)度系統(tǒng)研究 123.1O(n)調(diào)度器 123。2Linux內(nèi)核O(1）調(diào)度器 12第4章Linux內(nèi)核任務(wù)調(diào)度系統(tǒng)研究 15HYPERLINK\l”_Toc475091854"4。1時間片和優(yōu)先級的計算 15_Toc475091856"4。1。2優(yōu)先級的計算過程 154.2定時調(diào)度模型實現(xiàn) 17_Toc475091859”5.1全文總結(jié) 24參考文獻(xiàn) 25_Toc261957737”1.2國內(nèi)外研究現(xiàn)狀針對新的多核平臺的相關(guān)的操作系統(tǒng)方面的研究從起步至今還比較短暫，許多方面需要完善，特別是缺乏比較完備的進程調(diào)度策略。因此，多核平臺下操作系統(tǒng)的進程調(diào)度問題是當(dāng)今比較前沿的一個研究熱點。在本文，我們基于Linux內(nèi)核研究其在多核環(huán)境下的進程調(diào)度問題。盡管相對于其他操作系統(tǒng)的漫長歷史來說，Linux的歷史非常短暫，但Linux在從其問世到現(xiàn)在短短的時間之內(nèi)得到了非常迅猛的發(fā)展，已成為主流的多用戶多任務(wù)的操作系統(tǒng)之一,而且具有良好的特性，特別是其開放性、可靠的安全性及良好的可移植性使其獲得了廣泛的應(yīng)用［5]。Linux及Unix完全兼容并且開放源代碼,也使其成為操作系統(tǒng)的研究人員的不二選擇.從二十世紀(jì)六十年代進程的概念由J.H.Sallexer等人提出以后,人們對進程和任務(wù)的組織及調(diào)度問題的研究一直是一個熱點。Linux操作系統(tǒng)之所以受到好評，是因為它的高效率很大程度上要歸功于其內(nèi)核進程調(diào)度系統(tǒng)的超凡設(shè)計.同時，我們又可以借助其開源特性，將最新的操作系統(tǒng)方面相關(guān)的思想、研究和技術(shù)融合于Linux操作系統(tǒng)中，通過修改其內(nèi)核來個性化定制并進一步完善、優(yōu)化它。近年來,基于Linux的進程調(diào)度研究比較活躍.文獻(xiàn)[8]分析了Linux內(nèi)核的任務(wù)調(diào)度流程,指出Linux內(nèi)核的調(diào)度策略綜合了時間片輪轉(zhuǎn)和可剝奪式優(yōu)先級兩種調(diào)度策略。高珍等人［9］分析了Linux內(nèi)核對SMP的實現(xiàn)方式。安智平、張德運等[10］設(shè)計了進程調(diào)度的Master/Slave模型，并考慮了該模型在Linux環(huán)境下的實現(xiàn)。1。3本文研究內(nèi)容及方法1.研究進程管理調(diào)度基本原理；2.分析定時任務(wù)調(diào)度系統(tǒng)，研究時間片輪轉(zhuǎn)調(diào)度機制及優(yōu)先級計算;3。在ubuntu系統(tǒng)下實現(xiàn)上面的進程調(diào)度程序第2章進程管理及其調(diào)度2.1基本概念2。1.1進程進程（Process）的概念是在上世紀(jì)六十年代被提出的，最初是由MIT的Multics和IBM的TSS/360系統(tǒng)引用。至今人們從各方面對進程做出過許多種定義.主要考慮了：（1）進程的并發(fā)執(zhí)行性（S.E.Madnick，J。T.Donovan)；(2）進程作為獨立的被系統(tǒng)調(diào)度的單位（E.Cohen，D.Jofferson）；（3）進程的抽象性以及任務(wù)調(diào)度時作為系統(tǒng)分配和釋放各種資源的單位（P。Denning）；(4）進程及程序的區(qū)別。程序是行為規(guī)則的集合，程序的運行即體現(xiàn)為進程（E。W。Dijkstra）；（5）進程是具體操作的序列（BrinchHansen）.以上關(guān)于進程的描述，盡管角度不同，但它們在實質(zhì)上是相通的，即進程的動態(tài)執(zhí)行性。因此,進程可被定義為可并發(fā)執(zhí)行的程序?qū)ο嚓P(guān)數(shù)據(jù)的一次具體的執(zhí)行過程，是系統(tǒng)調(diào)配資源的單位。進程的基本特征有:并發(fā)性；動態(tài)性；獨立性；異步性以及結(jié)構(gòu)特征。進程在并發(fā)執(zhí)行過程中總是相互制約的。進程在其活動期間至少具備三種基本狀態(tài),它們是：執(zhí)行狀態(tài)、就緒狀態(tài)和等待狀態(tài).進程的狀態(tài)反映進程執(zhí)行過程的變化。這些狀態(tài)隨著進程的執(zhí)行和外界條件的變化而轉(zhuǎn)換。進程在執(zhí)行期間，可以在三個基本狀態(tài)之間進行多次轉(zhuǎn)換。2。1.2進程在Linux內(nèi)核中的實現(xiàn)進程由操作系統(tǒng)創(chuàng)建。具體到Linux環(huán)境下，系統(tǒng)可以通過調(diào)用fork（）函數(shù)復(fù)制一個現(xiàn)有進程來生成新的進程［13]。調(diào)用fork(）函數(shù)的進程是父進程，復(fù)制出的進程是子進程。fork()函數(shù)返回后，父進程從返回點繼續(xù)執(zhí)行，子進程從返回點獨立運行。fork（）函數(shù)在父進程和子進程的返回值不同.另外，fork()函數(shù)又是通過clone（）函數(shù)實現(xiàn)的。為了使子進程執(zhí)行新的任務(wù)，可以通過exec()相關(guān)函數(shù)裝載新的任務(wù)。最后通過exit(）函數(shù)退出。exit（）函數(shù)的作用是結(jié)束進程及釋放分配給該進程的各種資源。父進程和子進程可以通過相關(guān)函數(shù)實現(xiàn)同步。如wait4（）函數(shù)可用來查詢子進程是否結(jié)束。進程結(jié)束后即成為僵尸進程，由其父進程通過wait（）或waitpid(）函數(shù)進行進一步處理.可以發(fā)現(xiàn),Linux進程之間存在一個明顯的繼承關(guān)系。所有的進程都是PID（進程標(biāo)識值）為1的init進程的后代。內(nèi)核在系統(tǒng)啟動的最后階段啟動init進程。值得說明的是,Linux內(nèi)核通常把進程稱做任務(wù)（task）。并使用類型為task_struct、稱為進程描述符（processdescriptor）的結(jié)構(gòu)來描述進程[14］。該結(jié)構(gòu)定義在〈linux/sched.h>文件中。進程描述符包含一個具體進程的所有信息，主要有：1、進程的狀態(tài)(ProcessState）進程從產(chǎn)生到結(jié)束期間會經(jīng)歷幾種狀態(tài)的改變。進程的狀態(tài)是操作系統(tǒng)決定如何對其調(diào)度的重要屬性。Linux環(huán)境下進程狀態(tài)如表2-1所示。進程的狀態(tài)在不同條件下可以相互轉(zhuǎn)換，如圖2—1所示:2、和進程調(diào)度相關(guān)的信息這些信息一般反映了系統(tǒng)對進程調(diào)度的組織方式，比較重要的如進程的優(yōu)先級,進程是普通進程還是實時進程。相關(guān)字段參見表2-2說明.當(dāng)need_resched字段被設(shè)置時，在“下一次的調(diào)度機會”就調(diào)用調(diào)度程序schedule(）.counter代表進程剩余的時間片，是進程調(diào)度的主要依據(jù)，也可以說是進程的動態(tài)優(yōu)先級，因為這個值在不斷地減少；nice值代表靜態(tài)優(yōu)先級，反映進程擁有的時間片,影響counter值,可以用nice(）函數(shù)改變nice值；policy代表了操作系統(tǒng)該進程的調(diào)度方式，如該進程是按照實時進程的方式被調(diào)度還是按照普通進程的方式被調(diào)度;rt_priority是操作系統(tǒng)對實時進程進行調(diào)度時的重要依據(jù)。表2—3說明了進程的調(diào)度策略類型。只有root用戶能通過sched_setscheduler（）系統(tǒng)調(diào)用來改變調(diào)度策略.3、標(biāo)識符（Identifiers)信息最基本的如進程標(biāo)識符(ProcessIdentifier)，其他如用戶標(biāo)識符（UserIdentifier）、組標(biāo)識符（GroupIdentifier）。4、和進程通信相關(guān)的一些信息(IPC)主要為了使進程在執(zhí)行期間能夠及其他進程進行信息交換.5、進程鏈接信息（Links)相關(guān)信息如表2—4說明.進程通過這些指針可以組織成一顆進程樹。6、和時間以及定時器相關(guān)的信息（TimesandTimers）進程的生存期（lifetime)是指該進程從產(chǎn)生到結(jié)束的這段時間。在此期間，內(nèi)核要詳細(xì)統(tǒng)計并更新進程使用CPU的時間,一般包括用戶態(tài)執(zhí)行時間和系統(tǒng)態(tài)執(zhí)行時間.有了“時間"的概念，可以實現(xiàn)進程的“定時”操作,即判斷系統(tǒng)時間是否到達(dá)某個時刻,是否應(yīng)該執(zhí)行相關(guān)的操作。Linux提供了許多種定時方式，用戶可以靈活使用這些方式來為自己的程序定時.7、和文件系統(tǒng)相關(guān)的信息（）用來存儲進程對文件操作的信息，如訪問文件的文件描述符等等。8、虛擬內(nèi)存相關(guān)信息（VirtualMemory)進程通過自己的mm_struct數(shù)據(jù)結(jié)構(gòu)描述自己獨立的地址空間.9、內(nèi)存頁面管理相關(guān)信息當(dāng)系統(tǒng)內(nèi)實際內(nèi)存分配不足時，Linux內(nèi)核內(nèi)存管理模塊會把某些頁面搬移到硬盤等輔助存儲器。10、對稱多處理器(SMP）信息Linux內(nèi)核對SMP進行了全面的支持.11、和處理器相關(guān)的環(huán)境(上下文)信息（ProcessorSpecificContext）進程調(diào)度過程中需要保存上下文切換時的處理器現(xiàn)場信息。12、及進程相關(guān)的其他信息2。2線程及其實現(xiàn)在傳統(tǒng)的操作系統(tǒng)中，進程是系統(tǒng)進行調(diào)度和資源分配的基本單位，在任一時刻只執(zhí)行一個控制流程,這就是單線程（結(jié)構(gòu)）進程（SingleThreadedProcess）。然而隨著并行技術(shù)、網(wǎng)絡(luò)技術(shù)和軟件設(shè)計技術(shù)的發(fā)展，研究人員提出了多線程（結(jié)構(gòu)）進程(MultipleThreadedProcess）的概念[15]，其思想是把“分配資源”及“被調(diào)度”這兩項功能獨立。進程仍然是操作系統(tǒng)分配資源的獨立單位，可以適當(dāng)避免由于進程被頻繁調(diào)度而在進程間切換；線程來作為操作系統(tǒng)新的調(diào)度單位.可以說，進程實現(xiàn)了程序的并發(fā)執(zhí)行，提高了系統(tǒng)效率；那么線程則可以有效減少系統(tǒng)開銷，使多任務(wù)系統(tǒng)的并發(fā)性能更好.線程作為可被調(diào)度執(zhí)行的獨立實體是進程的組成要素,若某個進程內(nèi)包含有多個線程，那么該進程就是多線程進程。該進程中的線程共享操作系統(tǒng)分配給該進程的各種資源。多線程進程的內(nèi)存布局如圖2-2所示。由于線程具有許多傳統(tǒng)進程所具有的特征，所以,也把線程稱為輕量進程LWP(Light-WeightProcess）。我們期望通過線程在操作系統(tǒng)和程序設(shè)計中來改善系統(tǒng)和應(yīng)用程序的性能。然而，在Linux環(huán)境下，我們并沒有線程這樣的結(jié)構(gòu)。Linux內(nèi)核并沒有對線程做什么特殊的對待，它把線程當(dāng)做進程處理，也沒有特殊的數(shù)據(jù)結(jié)構(gòu)和調(diào)度策略專門為線程服務(wù)。線程同樣用task_struct結(jié)構(gòu)來描述并按照進程的管理和調(diào)度策略來對待.因此，線程在Linux環(huán)境下可認(rèn)為是普通的進程.Linux系統(tǒng)的這種處理方式區(qū)別于MicrosoftWindows、SunSolaris等系統(tǒng)的處理方式。對Linux操作系統(tǒng)而言，線程并不是什么“輕量級進程",而僅僅是共享系統(tǒng)內(nèi)各種資源的一種手段。這一方面簡化了線程的設(shè)計同時在調(diào)度方面，可以不用區(qū)分進程和線程，關(guān)于線程的調(diào)度實際上就是對進程的調(diào)度。第3章Linux內(nèi)核任務(wù)調(diào)度系統(tǒng)研究進程調(diào)度是操作系統(tǒng)的核心功能。從Linux2。4到Linux2.6,內(nèi)核進程調(diào)度程序歷經(jīng)數(shù)次改進（Linux內(nèi)核的修訂及改進是相當(dāng)頻繁的），每一次內(nèi)核調(diào)度程序的改善都使內(nèi)核的性能上升到更高層面。3。1O(n)調(diào)度器O(n）調(diào)度器是指Linux2.4版本內(nèi)核所采用進程調(diào)度程序,基于靜態(tài)優(yōu)先級實現(xiàn).該調(diào)度器為系統(tǒng)內(nèi)所有CPU維護一個全局運行隊列，調(diào)度時每次為該隊列中優(yōu)先級最高的那個進程分配CPU執(zhí)行。進程在產(chǎn)生時會得到一個時間片。當(dāng)進程占有CPU后,其時間片隨著進程的運行逐漸減少至零。當(dāng)該進程的時間片已消耗完，該進程就必須讓出系統(tǒng)分配給它的CPU。當(dāng)所有在運行隊列中的進程的時間片都消耗完后,由內(nèi)核重新分派時間片。O（n）調(diào)度器的性能受全局運行隊列中的任務(wù)數(shù)量約束.就緒進程越多，查找下一個要運行的進程耗時越長。系統(tǒng)的就緒任務(wù)越多,O（n)調(diào)度器的效率就越低。而且，給進程分配多長的時間片才合適也很難判斷。同時，由于系統(tǒng)內(nèi)只有一個全局的運行隊列，該調(diào)度器不適合在多核體系結(jié)構(gòu)下應(yīng)用.任意一個處理器調(diào)度時都需要訪問這個全局唯一的運行隊列,這樣就必須加鎖以控制各處理器因訪問隊列而產(chǎn)生的競爭，而各處理器對鎖的爭用又會產(chǎn)生新的系統(tǒng)性能瓶頸3.2Linux內(nèi)核O(1)調(diào)度器為了改進O(n）調(diào)度器，使系統(tǒng)性能在就緒隊列擁有大量進程的情況下有所提升，Linux內(nèi)核調(diào)度器的設(shè)計者IngoMolnar提出并實現(xiàn)了O(1)調(diào)度器。O(1)調(diào)度器在進程調(diào)度上所需要的時間是恒定的，和就緒隊列的任務(wù)數(shù)沒有關(guān)系。該調(diào)度器效率很高,得到了廣泛應(yīng)用。Linux2.6.23內(nèi)核版本之前各版本均采用O（1)調(diào)度器。該調(diào)度器還被集成到Linux2.4內(nèi)核中以改進調(diào)度性能。運行隊列結(jié)構(gòu)structrunqueue是O（1)調(diào)度器中一個關(guān)鍵的的數(shù)據(jù)結(jié)構(gòu)，它主要用于存儲每個CPU的就緒隊列信息.限于篇幅,本文在此只說明structrunquene最重要的數(shù)據(jù)成員：prio_array_t*active，＊expired。這幾個成員是runqueue中最重要的內(nèi)容。在Linux內(nèi)核中，每個CPU只維護一個和它一一對應(yīng)的就緒隊列rq，但rq又根據(jù)時間片的使用區(qū)分為active和expired兩個隊列。active隊列是就緒隊列中時間片尚未消耗完的就緒進程組成的隊列;expired隊列是就緒隊列中時間片已消耗完的就緒進程組成的隊列。active和expired指針都是prio_array_t類型。由typedefstructprio_arrayprio_array_t;知prio_array_t類型實際上是prio_array類型。數(shù)據(jù)結(jié)構(gòu)prio_array的定義如下：structprio_array｛unsignedintnr_active；unsignedlongbitmap［BITMAP_SIZE］;structlist_headqueue［MAX_PRIO］；｝;其中：BITMAP_SIZE=5，MAX_PRIO=140。MAX_PRIO定義系統(tǒng)擁有的優(yōu)先級個數(shù)，其默認(rèn)值為140。每一個優(yōu)先級在內(nèi)核中都擁有及自己對應(yīng)的運行隊列。同時內(nèi)核還維護一個優(yōu)先級位圖bitmap，其作用是提高查找當(dāng)前系統(tǒng)中擁有最高優(yōu)先級的可執(zhí)行進程時的效率。優(yōu)先級位圖各個位的初值為零,只有當(dāng)某個優(yōu)先級的運行隊列不為空時,響應(yīng)的標(biāo)志位才為1。優(yōu)先級數(shù)組的示意圖如圖3—1所示。第4章Linux內(nèi)核任務(wù)調(diào)度系統(tǒng)研究4。1時間片和優(yōu)先級的計算4.1。1時間片的計算方法在O(1）調(diào)度器中,進程剛被創(chuàng)建時，它的初始時間片從父進程那里繼承得來,為了避免進程通過反復(fù)fork()來竊取時間片,子進程被創(chuàng)建時并不是分配時間片，而是及父進程平分父進程的剩余時間片，即同時父進程的時間片也減少一半。這一過程是在sched_fork（）函數(shù)（sched.c1145）中實現(xiàn)的。內(nèi)核以HZ的頻率發(fā)生時鐘中斷，在其處理函數(shù)中調(diào)用scheduler_tick()函數(shù)將進程的時間片減去一毫秒。一旦普通進程消耗完運行時間片time_slice后，調(diào)度器將調(diào)用task_timeslice()函數(shù)重新計算它的運行時間片，然后把它從CPU上切換下來，將其重新插入到就緒隊列，等待再次被調(diào)度。和Linux2.4不同，2。6調(diào)度系統(tǒng)中，當(dāng)進程時間片用完時，會及時地重算。時間片的遞減和重算工作都是在scheduler_tick()函數(shù)中實現(xiàn)的.在O(1）調(diào)度器中，進程的時間片完全由靜態(tài)優(yōu)先級static_prio決定。由此可見，不同的用戶執(zhí)行相同的程序，在O(1）調(diào)度器中，他們創(chuàng)建的進程將獲得相同的靜態(tài)優(yōu)先級static_prio，由于時間片完全由static_prio決定,所以,不同用戶執(zhí)行相同的程序，他們創(chuàng)建的進程將獲得相同的運行時間片。這樣對高級別的用戶是不公平的.4.1.2優(yōu)先級的計算過程O(1）調(diào)度器在進行進程調(diào)度時是完全根據(jù)進程的動態(tài)優(yōu)先級的大小來確定候選進程的，可見優(yōu)先級是決定進程能否被盡快調(diào)度到的關(guān)鍵因素.因此，優(yōu)先級的計算至關(guān)重要。動態(tài)優(yōu)先級的計算主要由函數(shù)effective_prio()完成,該函數(shù)實現(xiàn)相當(dāng)簡單，總的來說，它是static_prio和sleep_avg的函數(shù)onus是根據(jù)進程的sleep_avg計算出來的對其動態(tài)優(yōu)先級prio的獎勵。普通進程的優(yōu)先級則復(fù)雜的多.Linux2.6中，優(yōu)先級prio的計算不再集中在調(diào)度器選擇next進程時,而是分散在進程狀態(tài)state改變的任何時候。這些時機有：①進程被創(chuàng)建時應(yīng)用程序調(diào)用do_fork(）創(chuàng)建新進程,在完成拷貝父進程task_t結(jié)構(gòu)、初始化某些成員后，do_fork（)調(diào)用wake_up_new_task（）函數(shù)初始化新進程的sleep_avg、interactive_credit等，然后調(diào)用effective_prio(）計算其prio，根據(jù)prio將其插入到就緒隊列中等待被CPU調(diào)度。②休眠進程被喚醒時當(dāng)休眠進程等待的條件滿足時，該進程將被喚醒。此時activate_task（）函數(shù)將調(diào)用recalc_task_prio（)函數(shù)根據(jù)休眠時間來更新進程的prio。③從TASK_INTERRUPTIBLE狀態(tài)中被喚醒的進程被調(diào)度時調(diào)度器在選擇了候選進程后,如果該進程是從休眠狀態(tài)中被喚醒的，調(diào)度器將給該進程一定的sleeg_avg獎勵，調(diào)用recalc_task_prio(）函數(shù)重新計算其prio，然后根據(jù)新prio將其插入就緒隊列中，以利于下次盡早被調(diào)度到。④因時間片耗盡被剝奪CPU時⑤因時間片過長而分段被剝奪CPU時在時鐘中斷處理中調(diào)用scheduler_tick(）函數(shù)，對當(dāng)前進程current執(zhí)行時間片減一操作后，如果發(fā)現(xiàn)普通進程的時間片太長,為了防止該進程長期壟斷CPU，調(diào)度器將其時間片進行分散執(zhí)行：保持時間片長度不變，重算prio，然后根據(jù)新prio調(diào)整它在就緒隊列中的位置等待下次被調(diào)度。在以上五種情況下，內(nèi)核都會直接或間接的調(diào)用effective_prio()函數(shù)（/kernel/sched。c）重新計算進程的動態(tài)優(yōu)先級prio,并根據(jù)計算結(jié)果調(diào)整它在就緒隊列中的位置。4.2定時調(diào)度模型實現(xiàn)使用動態(tài)優(yōu)先級調(diào)度策略和時間片輪轉(zhuǎn)法調(diào)度策略C語言代碼如下：＃include〈stdio。h>＃include〈stdlib。h>#include<unistd。h〉＃include<string.h〉typedefstruct_pcb{intpid；char*pname;intpriority；intneedtime；intruntime；intwaittime;struct_pcb*next;｝PCBNode，＊PCBList,*PCBPointer;PCBListpcbList；voidinputWithPriority（intpcbSize）｛inti；PCBPointerpcbPointer;pcbList=（PCBPointer)malloc（sizeof（PCBNode)）；pcbList—>next=NULL;PCBPointerpcbCursor=pcbList；for(i=0;i<pcbSize；i++)｛pcbPointer=（PCBPointer)malloc(sizeof（PCBNode)）;printf（"建立第％d個進程\n",i）;pcbPointer—>pid=i；/*printf("\t進程名為:");scanf(”％s"，pcbPointer—>pname）;fflush（stdin）;*//＊printf（"\t進程名為:"）;gets（pcbPointer—>pname)；fflush(stdin）;*/printf("\t優(yōu)先級為：")；scanf（”％d”，＆(pcbPointer—〉priority）);fflush(stdin）;printf(”\t服務(wù)時間:”）;scanf（"%d"，&(pcbPointer->needtime）);fflush（stdin)；pcbPointer—〉runtime=0；pcbPointer—〉next=NULL；pcbCursor-〉next=pcbPointer;pcbCursor=pcbCursor-〉next;｝}voidprint4test(）｛PCBPointercursor=pcbList—>next;while(cursor！=NULL）｛printf(”%d\t%s\t％d\t％d\n",cursor—〉pid，cursor—>pname，cursor—>priority,cursor->needtime)；/＊printf(”％d\t％d\n”,cursor->pid,cursor-〉priority);*/cursor=cursor-〉next；｝｝voidprintHorizontalBar(）{inti；for（i=0；i〈=33;i++)printf("-"）;printf(”\n”);}voiddisplay（)｛PCBPointercursor=pcbList-〉next；printHorizontalBar(）；printf（”｜\t運行中\(zhòng)t\t｜\n"）;printHorizontalBar（）；/*printf("\n｜pid\t｜pname\t｜prior\t|ndtime\t｜uptime|\n")；＊/printf(”｜進程號\t｜優(yōu)先級\t|已運行|服務(wù)時間|\n");printf("｜%d\t｜％d\t｜%d\t|％d\t｜\n",cursor-〉pid，cursor—〉priority,cursor-〉runtime，cursor—〉needtime）;printHorizontalBar(）;cursor=cursor-〉next;if（cursor==NULL）return;printf("｜\t阻塞隊列\(zhòng)t|\n”)；printHorizontalBar();while（cursor!=NULL)｛/*printf("｜%d\t|%s\t|%d\t|％d\t｜％d\t｜\n”，cursor—〉pid，cursor—>pname,cursor->priority,cursor->runtime,cursor—〉needtime);*/printf（"|％d\t｜％d\t|%d\t｜％d\t｜\n",cursor—>pid,cursor-〉priority，cursor—>runtime，cursor->needtime);cursor=cursor->next；}printHorizontalBar()；｝voidchangePriority(){PCBPointercursor=pcbList-〉next-〉next；while（cursor!=NULL)｛cursor—>priority*=2;cursor=cursor—〉next；｝}voidsortByPriority()｛PCBPointerhead=pcbList;PCBPointercursor；PCBPointercursorPrev;PCBPointermaxPrev;PCBPointermax;while（head-〉next—>next!=NULL）{for(cursor=head—>next，max=cursor,cursorPrev=head，maxPrev=cursorPrev;cursor!=NULL;cursor=cursor—>next,cursorPrev=cursorPrev—〉next）｛if（cursor->priority〉max—〉priority）{max=cursor；maxPrev=cursorPrev;｝｝maxPrev-〉next=max->next；max—>next=head—>next;head-〉next=max；head=head-〉next；/*print4test（）;*/}}/**動態(tài)優(yōu)先級調(diào)度＊/voidrun(){PCBPointerhead=pcbList；/*PCBPointercursor；*/PCBPointerrunning;while(head-〉next！=NULL)｛sortByPriority（)；running=head-〉next;printf（”\n#=〉第％d個進程正在運行第%d個時間片\n”，running-〉pid，running-〉runtime)；display（)；/＊fflush(stdin)；*//*getchar（);＊/sleep（1）;running-〉runtime++;changePriority(）；if（running-〉runtime〉running—〉needtime){head-〉next=head—>next—〉next;printf("\n＃=〉第%d個進程已結(jié)束\n\n",running-〉pid）;}｝｝/＊＊*時間片輪轉(zhuǎn)*/voidrun2（）{PCBPointerhead=pcbList;/*PCBPointercursor;＊/PCBPointerrunning;while（head->next!=NULL）｛/*sortByPriority()；*/running=head—>next;printf（"\n#=〉第％d個進程正在運行第％d個時間片\n”,running—〉pid，running-〉runtime）；display()；/＊fflush（stdin)；＊//＊getchar（）;*/sleep（1）；running—〉runtime++;/*changePriority();＊/if(running—〉runtime〉running->needtime){head—>next=head->next—>next;printf(”\n#=〉第%d個進程已結(jié)束\n\n",running-〉pid）；}else{head—〉next=head-〉next—〉next;PCBPointercursor=head；while(cursor-〉next!=NULL）{cursor=cursor->next;}cursor—>next=running;running—〉next=NULL；｝}}intmain(intargc，char＊＊argv)｛intpcbSize=0;intchoose=0；printf（"需要建立的進程個數(shù)："）；scanf(”％d",&pcbSize）;fflush(stdin);inputWithPriority（pcbSize);printf（”［動態(tài)優(yōu)先級調(diào)度-1］\n［時間片輪轉(zhuǎn)-2］