Linu進程調度策略與研究

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