1、 操作系統(tǒng)原理課程設計實踐報告全套設計加扣 3012250582題 目: Linux2.6進程管理和內存管理的仿真實現(xiàn) 姓 名: 學 院: 信息科技學院 專 業(yè): 計算機科學技術系 班 級: 計科121 學 號: 指導教師: 職稱: 教授 2014年3月 12 日Linux2.6進程管理和內存管理的仿真實現(xiàn)摘要：處理機調度可分為三個級別，分別是高級調度、中級調度和低級調度。高級調度又稱作業(yè)調度，作業(yè)調度的主要功能是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調入內存，并為它們創(chuàng)建進程、分配必要的資源。然后再將新創(chuàng)建的進程插入就緒

2、隊列。進程管理是操作系統(tǒng)中的重要功能，用來創(chuàng)建進程、撤消進程、實現(xiàn)進程狀態(tài)轉換，它提供了在可運行的進程之間復用CPU的方法。在進程管理中，進程調度是核心，因為在采用多道程序設計的系統(tǒng)中，往往有若干個進程同時處于就緒狀態(tài)，當就緒進程個數(shù)大于處理器數(shù)目時，就必須依照某種策略決定哪些進程優(yōu)先占用處理器。Linux2.6調度算法是基于優(yōu)先級的調度，它的算法復雜度為O(1)，也就是說是調度器的開銷是恒定的，與系統(tǒng)當前的負載沒有關系。Linux內核內存管理的一項重要工作就是如何在頻繁申請釋放內存的情況下，避免碎片的產生。Linux采用伙伴系統(tǒng)解決外部碎片的問題。伙伴系統(tǒng)的宗旨就是用最小的內存塊來滿足內核的

3、對于內存的請求。關鍵字：Linux，進程調度，作業(yè)調度，內存管理，伙伴系統(tǒng) 1. 目的和意義通過模擬Linux操作系統(tǒng)的O（1）調度算法與windows操作系統(tǒng)下進程調度策略進行比較。加深對操作系統(tǒng)進程調度方面知識的認識與理解。通過模擬Linux環(huán)境下的內存管理。并將內存分配與作業(yè)調度相結合,使我們對伙伴算法的原理和作業(yè)調度的過程有了詳細的了解。2.理論分析通過對操作系統(tǒng)書，數(shù)據(jù)結構和c/c+程序設計語言書的學習。我們把這次所要做的實驗分為下面幾個部分2.1進程管理Linux2.6的進程管理方面的知識我們參照的是操作系統(tǒng)教程第二章linux2.6O（1）算法章節(jié)的內容。Linux2.6的進程管

4、理保證了無論系統(tǒng)進程數(shù)目怎樣增加，選擇合適進程且為其分配處理器的時間。處理器擁有可運行隊列組和等待隊列組；在每個關鍵的時間點記錄時間，確保正確的響應時間；保證公平性，無進程處于饑餓狀態(tài)。O(1)調度器是以進程的動態(tài)優(yōu)先級 prio為調度依據(jù)的,它總是選擇目前就緒隊列中優(yōu)先級最高的進程作為候選進程 。由于實時進程的優(yōu)先級總是比普通進程的優(yōu)先級高,故能保證實時進程總是比普通進程先被調度。2.2內存管理當作業(yè)到達內存外時按先來先服務的順序申請分配內存，若分配成功作業(yè)進入內存按最短剩余時間優(yōu)先的順序進入CPU開始執(zhí)行；若分配失敗，作業(yè)被阻塞在內存外。等待已進入內存的作業(yè)釋放占有的內存后繼續(xù)申請分配內存

5、。直到所有作業(yè)執(zhí)行完畢。2.2.1作業(yè)調度我們設計的作業(yè)調度采取的是先來先服務策略，按照作業(yè)提交或進程變?yōu)榫途w狀態(tài)的先后次序，分派CPU；當前作業(yè)或進程占用CPU，直到執(zhí)行完或阻塞，才出讓CPU（非搶占方式）。在作業(yè)或進程喚醒后（如I/O完成），并不立即恢復執(zhí)行，通常等到當前作業(yè)或進程出讓CPU。進程調度采取的是最短剩余時間優(yōu)先調度的策略。先來先服務作業(yè)調度策略是根據(jù)作業(yè)到達時間依次進入內存，而最短剩余時間優(yōu)先調度策略是根據(jù)作業(yè)所需剩余時間決定誰先占用cpu。2.2.2 伙伴系統(tǒng)伙伴系統(tǒng)數(shù)據(jù)結構的定義，分配回收算法的定義和解釋我們參照的是嚴蔚敏，吳偉民.數(shù)據(jù)結構:C語言版，該書的第203到20

6、6頁伙伴系統(tǒng)的特征為： 1.把所有的空閑頁框分組為m+1（11）個塊鏈表，每個塊鏈表分別包含大小為2n（n為010的整數(shù)）個連續(xù)的頁框，即1、2、4、6、8、16、32、64、128、256、512和1024個連續(xù)的頁框。2.每個塊的第一個頁框的物理地址是該塊大小的整數(shù)倍?；锇橄到y(tǒng)原理為：任何尺寸2i的空閑塊都可以被分割成兩個尺寸為2i-1的空閑塊，這兩個空閑塊被稱為伙伴，他們可以合并成一個尺寸為2i的空閑塊。4.設計思想4.1進程調度設計思想設置一個優(yōu)先級鏈作為優(yōu)先級隊列頭，一共有140個優(yōu)先級0139.它包含4個節(jié)點信息，status_bit位標志該優(yōu)先級隊列是否為空。pcblink_nu

7、m優(yōu)先級值，next_pcb指向第一個該優(yōu)先級隊列的第一個的進程，next指向下一個優(yōu)先級。每一個優(yōu)先級隊頭都指向一條進程鏈（優(yōu)先級相同）。進程節(jié)點包含 next指向下一個進程。如圖：就緒隊列組4.2內存管理設計思想4.2.1.作業(yè)調度設計思想我們定義了兩個隊列：waitjcb隊列用于存放等待進入內存的作業(yè)readyjcb隊列用于存放已經(jīng)進入內存處于就緒狀態(tài)和正在占用CPU運行的進程內存內 readyjcb隊列 進程1 進程2 進程3 進程4 進程5.作業(yè)1 作業(yè)2 作業(yè)3 作業(yè)4 作業(yè)5內存外 waitjcb隊列 內存內，進程被處理器調度 FIFO策略 先來先服務;即先到達的作業(yè)先進入rea

8、dyjcb最短剩余時間優(yōu)先策略;即以每一個作業(yè)到達時間為準，對readyjcb重新排序，找到最合適的進程調度4.2.2伙伴系統(tǒng)的設計思想系統(tǒng)開始運行時整個內存是一個大小為2m的空閑塊，運行一段時間后被分成若干占用塊和空閑塊。為分配查找方便。我們將所有大小相同的空閑塊建于一張子表中，每個子表是一個雙重鏈表。這樣的鏈表有m+1個。將這m+1個表頭指針用向量結構組織成一個表，最開始只在m子鏈上有一個大小為1024的空閑塊。這就是伙伴系統(tǒng)中的可利用空間表。如下圖：空閑鏈表5.核心數(shù)據(jù)結構說明5.1進程調度數(shù)據(jù)結構typedef struct task_structint pid; /進程號volati

9、le long state; /進程當前狀態(tài) unsigned long flags; /進程狀態(tài)信息，非運行狀態(tài)long prio; /進程優(yōu)先級long counter; /時間片int nice; /交互性值long staticprio; /非實時進程優(yōu)先級int starttimet; /進程啟動時間int needtime; /進程所需時間int runtime; /進程已運行時間 int usetime; /進程已占用cpu時間int entertime; /進程進入CPU的時間int timeslice; /時間片余額struct task_struct *next; pcbn

10、ode,*pcblink;typedef struct pcblink_node /就緒隊列 int pcblink_num; /優(yōu)先級0139 int status_bit; /該就緒隊列是否有進程 1有0無 pcblink next_pcb; /指向該優(yōu)先級隊列的進程;struct pcblink_node *next; /指向下一個優(yōu)先級隊列pcblink_node,*linklist;typedef struct queue /就緒隊列組linklist front; linklist rear;queue;extern pcbnode *current;/指向當前正在運行的進程ext

11、ern pcbnode *newcreate；/指向最新產生的一個進程extern int k；/就緒隊列某個優(yōu)先級的進程數(shù)5.2內存管理數(shù)據(jù)結構5.2.1.作業(yè)調度的數(shù)據(jù)結構struct jcbchar name; /作業(yè)名int id; /作業(yè)號int needtime;/所需時間int cometime; /進入內存時間int prio; /優(yōu)先級int size;/請求分配內存大小site *address;/請求分配內存的首地址jcb *next;int Clock=0;/模擬系統(tǒng)時間int num;/創(chuàng)建的作業(yè)數(shù)jcb *waitjcb=(jcb*)(malloc(sizeof j

12、cb);/內存外的后備作業(yè)隊列jcb *ready;/指向正在CPU中運行的進程jcb *readyjcb=(jcb*)(malloc(sizeof jcb);/內存中就緒和正在運行的進程隊列5.2.2伙伴系統(tǒng)的數(shù)據(jù)結構#define m 10/可利用空間總容量的2的冪次，子表的個數(shù)為m+1typedef struct pageblock/塊信息的數(shù)據(jù)結構 pageblock *front;/前驅指針 pageblock *next;/后驅指針 int tag ;/0空閑。1使用 int kva ;/塊大小 2的k次冪pageblock, *site;typedef struct headno

13、de/表頭向量組織 int nodesize;/該鏈表空閑塊大小 pageblock *first;/該鏈表表頭指針 freelistm+1;/表頭向量類型extern site f; /首地址6.核心函數(shù)及算法流程Main()progressjc();進程調度O（1）算法jcbrun();內存管理init(&a)初始化內存createjcb();創(chuàng)建作業(yè)run()三級調度Output（a）當前內存情況系統(tǒng)框架6.1進程調度函數(shù)void createqueue(queue &Q ); /創(chuàng)建優(yōu)先級0140隊列頭void init(queue &Q); /構造一個空隊列Qvoid createp

14、cb(queue &Q,int number); /創(chuàng)建進程 插入就緒隊列unsigned int task_timeslice(pcbnode *p) ; /計算時間片 void change_state(pcbnode *p); /改變進程狀態(tài)void pcblist_finder(queue Q); /查找就緒位圖 void deletepcb(queue &Q,pcbnode *p); /撤銷進程void addqueue(queue &Q,pcbnode *p); /將進程插入等待就緒組void pcblist_ergodic(queue Q); /所在進程鏈就緒隊列的的遍歷 voi

15、d Oone(queue &A,queue &E,queue &B); / O（1）算法void move_into_cpu(pcbnode *tar); /進入cpu 并處理計算void move_out_cpu(queue &Q,queue &E,pcbnode *tar) ; /離開cpu 有active 和 expired 兩個優(yōu)先級數(shù)組, active 數(shù)組中包含了有剩余時間片的任務,expired 數(shù)組中包含了所有用完時間片的任務。當一個任務的時間片用完了就會重新計算其時間片,并插入到 expired 隊列中,當 active 隊列中所有進程用完時間片時,只需交換指向 active

16、 和 expired 隊列的指針即可算法流程O（1）算法流程圖6.2內存管理函數(shù)及算法流程否是Clock+1否程序運行結束是當所需時間為0，執(zhí)行完畢，從readyjcb隊列撤銷，釋放內存兩個隊列是否均為空占用cpu執(zhí)行，所需時間減1等待作業(yè)所需剩余時間是否最少成功作業(yè)進入內存，從waitjcb隊列撤銷并插入readyjcb隊列失敗作業(yè)請求分配內存否作業(yè)到達時間是否等于clock作業(yè)在waitjcb隊列等待開始隨機產生作業(yè)放入waitjcb隊列設置時鐘clock=0，模擬系統(tǒng)時間是6.2.1.作業(yè)調度的函數(shù)void createjcb()； /創(chuàng)建作業(yè)并插入后備隊列void deletewait

17、(jcb *&p)；/刪除后備隊列中的作業(yè)void deleteready(jcb *p)；/刪除內存中的作業(yè)void print(jcb *w)； /遍歷隊列void inready(jcb *readyjcb,jcb *p)；/將作業(yè)插入到readyjcb隊列void sortready(jcb *readyjcb)；/將作業(yè)按照最短剩余時間進行排序void run()； /作業(yè)調度進程調度算法流程否是Clock+1否是否作業(yè)所需剩余時間是否最少等待否占用cpu執(zhí)行，所需時間減1當所需時間為0，執(zhí)行完畢，從readyjcb隊列撤銷，釋放內存兩個隊列是否均為空程序運行結束是作業(yè)到達時間是否等

18、于clock作業(yè)在waitjcb隊列等待內存是否已滿作業(yè)進入請求分配內存，從waitjcb隊列撤銷并插入readyjcb隊列開始隨機產生作業(yè)放入waitjcb隊列設置時鐘clock=0，模擬系統(tǒng)時間是6.2.2伙伴系統(tǒng)的函數(shù)void init(freelist *a); /初始化空閑鏈表void output(freelist a); /輸出空閑鏈表site allocpages(freelist *avail,int n)/分配內存塊,并返回其首地址void printinsert(site p); / 顯示已分配出去的內存塊信息site buddy(site p); /返回初始地址為p,大

19、小為2的k次方的內存塊，的伙伴塊地址void freepages( freelist *free,site *p); / 回收內存void progressnc(); /內存管理算法流程分配算法查找成功查找失敗開始請求分配大小為n的內存指向子表的第一個空閑塊刪除該空閑塊，子表表頭指向該塊的下一個空閑塊 返回該占用塊的地址返回NULL將該空閑塊的2k （2k-1nsize的內容Int cir; /用于設置時鐘中斷，當cir=0時發(fā)送中斷信號處理之前未處理的進程請求（1）.為了模擬操作系統(tǒng)的并發(fā)環(huán)境，設置一個隨機數(shù) tag tag=0或1，當tag為0時 內存先工作 輸出內存分配情況，然后進程開始

20、發(fā)出分配內存的請求，這時候請求不能得到滿足。Tag=1時 進程先發(fā)送分配請求，內存接受請求開始工作并輸出分配后的空閑鏈表情況；（2）首先給cpu-cir定一個初始值 假設為3；當開始作業(yè)調度時，系統(tǒng)時間clock=0；cir=3;創(chuàng)建時間為0的作業(yè)進入內存并請求分配內存。當循環(huán)一次clock+時，cir-；當cir!=0時此時根據(jù)tag的值來確定 作業(yè)請求能否得到滿足。當tag=0時請求無法得到滿足，進程阻塞無法進入內存。此時另cpu-sizei=jcb-size;當tag=1時請求得到滿足。內存為進程分配空間并輸出內存分配情況；當cir=0時cpu產生時鐘中斷。發(fā)送信號，喚醒沒有滿足內存分配

21、要求的進程，jcb-size=cpu-sizei;并將size的值傳遞給分配內存的算法。 處理完被阻塞的進程后，cir=3,等待產生下一個時鐘中斷現(xiàn)在程序還在調試過程中能否順序運行出來還需要一定的時間。9.實踐心得體會鄭安琪：做了這次課程設計，大大提高了我的編寫代碼能力，和對整體程序框架理解和構思能力。雖然我們在這次課程設計中實現(xiàn)的操作系統(tǒng)的功能比較簡單。但也是我們認真看書，查閱資料的成果。我覺得這樣就是比較有意義了。最開始選這個題目是因為在上學期的實驗中涉及過與進程管理相關的內容。寒假期間我們主要完成的是與進程調度有關的內容。查閱操作系統(tǒng)書本和相關資料后，我對linux2.6的O（1）調度算

22、法有了初步的認識。由于假期小組成員們都在家里。程序的編寫和交流都不是很方便。我對小組成員任務的分工也不是很明確。所以假期的進度十分緩慢。程序的拼接和運行都有很多錯誤。開學來之后，又重新集合了成員們和我寫的代碼重新調試和運行。并且和成員們及時溝通順利才將進程管理部分完成了。開學后的進展就比較快了。任務分工也較為明確。在和老師討論過之后，老師建議我們寫三級調度和模擬CPU運行環(huán)境。關于三級調度部分我們在后期實現(xiàn)了。我負責的是伙伴算法部分，以及作業(yè)調度和伙伴算法結合的部分。關于伙伴算法我最開始看操作系統(tǒng)書上的內容，一直都想不到到底用什么樣的數(shù)據(jù)結構來模擬它的空閑鏈表。后來翻閱了大二上的課本數(shù)據(jù)結構C

23、語言版里面第八章有一章節(jié)就是詳細講解伙伴算法的，同過看書慢慢的領會最后成功寫出來了。還有作業(yè)調度和內存分配的結合，拿到組員寫好的作業(yè)調度程序后，我查閱了關于什么時候進行內存分配什么時候釋放內存。并仔細了解了她所寫的作業(yè)調度的過程并在作業(yè)調度算法中加入了關于內存分配的內容?？偟膩碚f這次課程設計我學到了很多。不像最開始那樣程序運行不出來就非常煩躁。能夠靜下心來寫代碼，改代碼。自己對各方面的知識也有了更全面的了解。施欣逸：通過本次的課程設計，感覺學到了很多。剛開始拿到組長分配的任務的時候，先是看了一遍書本，書上說到的一些時間分配，動態(tài)平衡等專有名詞又不是寫的清楚，只能去網(wǎng)上搜集相關的點來擴充和詳細化

24、書上的概念。然后是把整體的算法分成一個個小塊。從抽象化出每個數(shù)據(jù)結構，建立他們之間的聯(lián)系，到實現(xiàn)過程中可能需要的細節(jié)函數(shù)。本來以為可以借鑒到第一次操作系統(tǒng)實驗，但是并不是同一個思路。操作系統(tǒng)課程設計讓我能更好的掌握各個數(shù)據(jù)結構的使用，自己的感覺還可以。但在和老師，助教交流的過程中，發(fā)現(xiàn)程序還不夠完整。在于并沒有模擬抽象一個可以支撐程序運行的環(huán)境，類似于CPU，時鐘中斷等。不能只停留在算法層面上，程序還需要改進。 在開始答辯的那一周，針對各種程序或者調試的問題，積極的尋找正確的突破點，由此意識到正確的思路對程序的實現(xiàn)有很大幫助。每當調試過程中出現(xiàn)問題時，先確定范圍，再推算一遍。往往能找到之前思考

25、的不周到之處。 當然，雖然這次試驗讓我們學到了很多Linux2.6理論上知識，但是不可否認的是，團隊意識的不可或缺。我們寫程序的能力不是特別的突出，于是在某些部分才更需要思想的交流和碰撞。在每一次的揣摩概念和測試功能之下，稍許完整的程序才可以被寫出來。 周曉梅：這次操作系統(tǒng)課程設計是我目前做過的最大的一個課程設計，一開始老師讓選題的時候，因為知識掌握的不多，所以也很難下手。最終因為第一次實驗是和進程調度有關，對進程了解還算多一點，所以我們小組確定了LINUX2.6進程管理與內存管理的仿真實現(xiàn)這個課題。對于這個課題，我們一開始也不知道怎么開始，頭腦很空。所以寒假期間，我先把操作系統(tǒng)書上關于LIN

26、UX進程管理部分的內容看了幾遍，上網(wǎng)查了一些關于O（1）算法的資料，然后初步開始了我們的課程設計。不過一開始的分工并不是很明確，大家一起寫進程管理部分。組長確定好結構體之后，分給我們一個個小函數(shù)寫，所以進程管理部分我只寫了兩個簡單的函數(shù)。主要的O（1）算法函數(shù)和一些重要函數(shù)都是由另一位組員完成的。寒假因為大家都在家，網(wǎng)上交流畢竟沒有當面交流那么方便，所以寒假我們課程設計的進度很慢，進程管理部分完成的還不是很完整，有很多錯誤。 開學第一周，我們每一天都泡在圖書館，繼續(xù)我們的課程設計。完善進程管理部分，經(jīng)過討論對一些地方進行了修改。并把內存管理伙伴系統(tǒng)開了一個頭。開學第二周，課程設計正式開始了。第

27、一天是匯報進度，第一組就是我們小組，經(jīng)過匯報老師指出了我們的不足，就是分工不明確，沒有結合作業(yè)調度和沒有實現(xiàn)并發(fā)的問題。對于分工的問題，組長回去后就重新進行了分配，進程管理部分，因為大多都是另一位組員做的，所以剩下還未完善的繼續(xù)交由她完成，而我和組長負責內存管理部分。我負責寫作業(yè)調度，組長寫伙伴算法，然后再由組長將兩者連起來。一開始并不知道如何把作業(yè)調度和進程調度結合起來，嘗試了很多，上網(wǎng)找了很多資料。最后只能寫出用一個最簡單的先來先來服務作業(yè)調度和進程調度結合起來。關于并發(fā)環(huán)境的問題，我們也請教了助教，但是目前還是未實現(xiàn)出來?？傊?，這一次課程設計，我最大的收獲就是對O（1）算法和伙伴系統(tǒng)有了

28、更深的理解，對低級調度和高級調度的結合有了更深的理解，代碼的編寫能力也有了一些提高 參考文獻：1費翔林，駱斌.操作系統(tǒng)教程M.北京:高等教育出版社,2014.2;2嚴蔚敏，吳偉民.數(shù)據(jù)結構:C語言版M.北京：清華大學出版社,2007;3應勤,孫興芳.Linux編程實例解析M.北京:清華大學出版社,2009.1;4宋曉宇.C/C+程序設計M.北京:機械工業(yè)出版社,2014.1;5謝長生，葉志斌.Linux內存管理研究DB/OL.2005/2015; 核心代碼：進程調度核心代碼：void pcblist_ergodic(queue Q)/所在進程隊列的遍歷 int i; int j=0;linkl

29、ist q;q=Q.front-next;/指向隊列的頭的下一個指針;pcbnode *p2;coutn-當前就緒隊列組-n;for(i=0;inext_pcb; /p2指向q優(yōu)先級的第一個進程while(p2!=NULL) /遍歷該優(yōu)先級的隊列 cout ID 進程優(yōu)先級 時間片 所需時間 endl;cout pid prio counter needtime next; q=q-next;/指向下一個優(yōu)先級k=j; /全局變量的賦值 coutnext; for(i=0;istatus_bit=1&p-prio=i)/如果當前位已有進程 并且p的優(yōu)先級=此時q隊頭的優(yōu)先級p1=p;p1-ne

30、xt=q-next_pcb;q-next_pcb=p1;if(q-status_bit=0&p-prio=i)/如果當前位沒有進程 并且p的優(yōu)先級=此時q隊頭的優(yōu)先級p1=p;q-next_pcb=p1;q-status_bit=1;/為優(yōu)先級隊頭q的status_bit位置1q=q-next;void deletepcb(queue &Q,pcbnode *p) /刪除該優(yōu)先級隊列的進程linklist q;/各個優(yōu)先級的隊頭鏈 q=Q.front-next;/第一個優(yōu)先級0 while(q) /找到p的優(yōu)先級所對應的優(yōu)先級鏈/如果p的優(yōu)先級=q的優(yōu)先級 就跳出if(q-pcblink_nu

31、m=p-prio) break;q=q-next; /否則找下一個優(yōu)先級q-next_pcb=p-next;/因為產生優(yōu)先級相同的進程可能極小/直接從頭刪除if(q-next_pcb=NULL)q-status_bit=0;/當進程鏈為空，置status_bit為0;#define SCALE_PRIO(v, prio) max(v * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE) /計算時間片長度的函數(shù)#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)unsigned in

32、t task_timeslice(pcbnode *p) /計算時間片 if (p-staticprio staticprio); else /靜態(tài)優(yōu)先級在 121139之間 return SCALE_PRIO(DEF_TIMESLICE, p-staticprio); void Oone(queue &A,queue &E) /O（1）算法pcbnode *r;/進程類型的指針 linklist c;/優(yōu)先級的隊頭鏈while(1)H:pcblist_ergodic(A);/就緒進程隊列的遍歷 if (k=0) /如果遍歷為空的話 退出循環(huán) break;pcblist_finder(A);/

33、找到第一位投入運行的優(yōu)先級進程鏈printf(-n);r=current; /指向該優(yōu)先級下的第一個進程while(r!=NULL) /不為空 投入運行Sleep(1000); /假設CPU上下文切換時間時間為1秒 move_into_cpu(r); /進入CPU處理 cout時間片余額為 : timeslice-所還需時間為: needtimeneedtime=0&r-timeslice0) /進程還在CPU中運行時 新創(chuàng)建進程實行搶占 if(r-needtime=500) /設置特定搶占的條件createpcb(A,1); /創(chuàng)建1個新進程 if(newcreate-prio=r-prio

34、) /原進程優(yōu)先級大（數(shù)值?。┎粨屨紅ime_t t;t=time(NULL); r-runtime=localtime(&t)-tm_hour*3600+localtime(&t)-tm_min*60+localtime(&t)-tm_sec;/當前時間記錄r-usetime=r-runtime-r-entertime;/r已占用CPU的時間=r已運行時間-r進入CPU時間r-needtime=r-needtime-r-usetime;/r還需時間的處理coutn進程號pid的進程繼續(xù)執(zhí)行!endl;else /原進程優(yōu)先級?。〝?shù)值大） 搶占coutn進程號pid的進程搶占CPU執(zhí)行!nee

35、dtime=r-needtime-100; /r所需時間變化r-timeslice-=100;/r時間余額變化if(r-timeslicetimeslice=0;if(r-needtimeneedtime=0;cout時間片余額為 : timeslice-所還需時間為: needtimeneedtimenext=NULL)/若改優(yōu)先級就緒隊列只有當前一個進程 則置位為0 ，/讓出CPU 再次查找下一個置位為1的就緒隊列，current指針指向該就緒隊列進程 move_out_cpu(A,E,r);/讓進程從A隊列組進入E隊列組 pcblist_finder(A);/遍歷A r=current;

36、 else if(r-next!=NULL)/若該優(yōu)先級就緒隊列還有其他進程 則指向下一進程 r=r-next; /若A隊列組沒有進程，則交換A隊列組和E隊列組的指針c=E.front-next;E.front-next=A.front-next;A.front-next=c;內存管理核心代碼：*伙伴系統(tǒng)*/avail0.m為可利用空間表,n為申請分配量,若有不小于n的空閑塊, / 則分配相應的存儲塊,并返回其首地址;否則返回NULL。site allocpages(freelist *avail,int n)int i,k;site pa,pi,prev,suv;for(k=0;k=m&(*

37、avail)k.nodesizem)cout分配失敗!請釋放內存!front;suv=pa-next;if(prev=suv) /如果該子表只有一個空閑快則分配后該子表表為空(*avail)k.first=NULL;else /若該表不止一個空閑塊 則刪去塊paprev-next=suv;suv-front=prev;(*avail)k.first=suv;/該表表頭指針指向PA的下一個塊for(i=1;(*avail)k-i.nodesize=n+1;i+)/剩余塊插入相應2的k-i次冪的空閑鏈表pi=pa+(int)pow(2,k-i);pi-front=pi;pi-next=pi;pi-

38、kva=k-i;pi-tag=0;(*avail)k-i.first=pi;pa-tag=1;/pa被分配給用戶 標志置為1 被占用pa-kva=k-(-i);return pa;/返回pa的首地址site buddy(site p)/起始地址為p,大小為2的k次方的內存塊，其伙伴塊的起始地址if(p-f)%(int)pow(2,p-kva+1)=0)/buddy(p,k)=p+2k 若p%2(k+1)=0return(p+(int)pow(2,p-kva);else /buddy(p,k)=p+2k 若p%2(k+1)=2kreturn(p-(int)pow(2,p-kva);void fr

39、eepages( freelist *free,site *p)/回收算法site s;s=buddy(*p);/s為P的伙伴塊if(s-tag=1)/若P的伙伴塊被占用 /直接插入相應的子鏈if(*free)(*p)-kva.first = NULL) / 若該子鏈表空 (*p)-front=(*p)-next=*p;(*free)(*p)-kva.first=*p;(*p)-tag=0; else / 若該子鏈表不為空 P插在表頭 (*p)-next=(*free)(*p)-kva.first;(*p)-front=(*p)-next-front;(*p)-next-front=(*p);(*p)-front-next=(*p);(*free)(*p)-kva.first=(*p);(*p)-tag=0; while(s-f=0)&stag=0)/若P的伙伴塊S沒有被占用 且S的地址在有效范圍內if(s-next=s-front)/如果該鏈表只有s一個塊(*free)s-kva.first=NULL;/刪除S塊 該子鏈變?yōu)榭誩lse/如果該鏈表還有其他塊 刪除s塊 表頭為s的下一個節(jié)點 s-front-next = s-next; s-next-front =