UNIX V6交換區(qū)管理

1、chap4 交換區(qū)管理2015.4.2星期四（單周）2015.4.14星期二（單周）UNIX V6管理交換區(qū) 1.設(shè)置外存交換區(qū)的原因 只有馬上需要執(zhí)行的進(jìn)程保留在內(nèi)存中，其它進(jìn)程可調(diào)出到外存的一個(gè)空間，這個(gè)空間稱為交換區(qū)或者交換文件。 多道程序設(shè)計(jì)有多個(gè)就緒進(jìn)程在內(nèi)存，存在內(nèi)存競(jìng)爭(zhēng)現(xiàn)象。 設(shè)置外存交換區(qū)的原因是提高內(nèi)存利用率。 2.管理交換區(qū)的方法 UNIX V6的管理進(jìn)程通過(guò)定期執(zhí)行交換處理 調(diào)出swap out:將處于阻塞狀態(tài)或執(zhí)行優(yōu)先級(jí)較低的進(jìn)程從內(nèi)存移至外存交換空間。 調(diào)入swap in:當(dāng)外存交換區(qū)的進(jìn)程成為可執(zhí)行狀態(tài)時(shí)，在將其移回內(nèi)存。P82進(jìn)程內(nèi)存映像的交換原則 1.共享正文段

2、調(diào)入內(nèi)存，在外存交換區(qū)必須有一個(gè)備份。 創(chuàng)建一個(gè)代碼段時(shí)，必須在外存交換區(qū)有一個(gè)副本。 創(chuàng)建代碼段：在text數(shù)組中有一個(gè)元素 代碼段總有備份在外存。 2.數(shù)據(jù)段調(diào)入內(nèi)存則釋放在外存的空間；數(shù)據(jù)段調(diào)出內(nèi)存，則釋放在內(nèi)存的空間。 調(diào)出：mfree(coremap,size,aa),aa=proc.p_size 調(diào)入：mfree(swapmap,size,aa) 圖4-2：釋放為虛線橢圓，保留為實(shí)線橢圓。交換區(qū)管理 1.交換空間的管理（補(bǔ)充） 2.進(jìn)程映像傳送進(jìn)程sched()（P83） 3.正文段的處理進(jìn)程xalloc()（P90） 共享代碼段數(shù)據(jù)結(jié)構(gòu)P89 4.數(shù)據(jù)段的調(diào)出進(jìn)程xswap()的

3、分析，作業(yè)。一、外存交換區(qū)的管理 1.策略：為調(diào)出的進(jìn)程分配連續(xù)的交換區(qū)空間。 2.數(shù)據(jù)結(jié)構(gòu) 已分配區(qū)域：進(jìn)程的代碼段，數(shù)據(jù)段 空白區(qū)域swapmap 交換空間不斷分配和釋放，UNIX OS相應(yīng)管理修改swapmap，反映現(xiàn)在空閑存儲(chǔ)空間的使用情況。交換區(qū)空白區(qū)數(shù)據(jù)結(jié)構(gòu)swapmap int swapmapSMAPSIZ 交換區(qū)空白塊一塊512B，內(nèi)存一塊64B。 空白區(qū)域數(shù)據(jù)結(jié)構(gòu) struct map /P76 char *m_size; /塊數(shù) char *m_addr; /空白區(qū)域起始地址 ;3.空白區(qū)的分配和釋放 空白區(qū)的分配malloc() UNIX OS依次查找空白區(qū)數(shù)組swapm

4、ap，找到第一個(gè)能滿足請(qǐng)求交換區(qū)塊數(shù)的元素時(shí)，將該項(xiàng)空間部分或全部分配給進(jìn)程，并修改swapmap。 回收交換區(qū)free() 在釋放交換區(qū)空間時(shí)，UNIX OS根據(jù)起始地址aa，從swapmap中找到相應(yīng)位置，此時(shí)可能存在四種情況： 釋放區(qū)與swapmap中前一項(xiàng)二、UNIX管理外存交換區(qū)的原語(yǔ) 外存交換區(qū)管理函數(shù) sched(),swapper進(jìn)程調(diào)出調(diào)入處理函數(shù)。 xswap()數(shù)據(jù)段調(diào)出處理函數(shù) xalloc()代碼段處理函數(shù) xfree()遞減代碼段參照計(jì)數(shù)器 xccdec() 遞減內(nèi)存進(jìn)程的代碼段參照計(jì)數(shù)器1. sched原語(yǔ) 進(jìn)程數(shù)據(jù)段的長(zhǎng)度P_size=PPDA+nd+ns 進(jìn)程

5、代碼段的長(zhǎng)度p_textp-x_size 若代碼段是共享正文段，已在內(nèi)存則不計(jì)此部分長(zhǎng)度。 0#進(jìn)程優(yōu)先數(shù)PSWP(-100)是最低的，因此0#具有最高優(yōu)先級(jí)。sched原語(yǔ)的5個(gè)標(biāo)號(hào)匯編代碼段 sloop 不存在調(diào)出進(jìn)程 loop ：選擇調(diào)入進(jìn)程，選擇調(diào)出進(jìn)程。 選擇調(diào)入到內(nèi)存的外存交換區(qū)的進(jìn)程，若內(nèi)存空間不足則調(diào)出某一個(gè)進(jìn)程到交換區(qū) 選擇調(diào)出到外存交換區(qū)的進(jìn)程 found1 調(diào)出處理。loop選擇后調(diào)出進(jìn)程到外存交換區(qū)。 xswap()調(diào)出進(jìn)程的數(shù)據(jù)段到交換空間 found2 調(diào)入處理 swap()調(diào)入進(jìn)程的代碼段和數(shù)據(jù)段 swaper 錯(cuò)誤處理Sched原語(yǔ) sched() struct

6、 proc *p1; register struct proc *rp; /rp是進(jìn)程PCB塊的“變量” /proc.p_time是進(jìn)程最近一次在外存交換區(qū)或內(nèi)存的時(shí)間。 register a,n; /n是時(shí)間 goto loop; sloop: runin+; /不存在調(diào)出進(jìn)程。runin是內(nèi)存中有調(diào)出進(jìn)程的標(biāo)志 sleep(&runin,PSWP); /sched休息sched原語(yǔ)的loop：選擇調(diào)入內(nèi)存的進(jìn)程 loop: spl6(); /提高處理機(jī)優(yōu)先級(jí)，防止中斷 for(rp = &proc0; rp p_stat=SRUN & (rp-p_flag&SLOAD)=0 &rp-p_t

7、ime n) p1 = rp; /交換區(qū)進(jìn)程是就緒進(jìn)程SRUN，可能將被CPU執(zhí)行 n = rp-p_time; /找到外存交換空間中停留時(shí)間最長(zhǎng)的進(jìn)程p_timen if(n = -1) /不存在調(diào)入內(nèi)存的進(jìn)程，n沒(méi)有=p_time runout+; /設(shè)置標(biāo)志 sleep(&runout, PSWP); /0#進(jìn)程休息，PSWP=-100，優(yōu)先數(shù)最小 goto loop; spl0(); /處理機(jī)優(yōu)先級(jí)0換出，在外存sched原語(yǔ)p1進(jìn)程申請(qǐng)內(nèi)存空間 rp = p1; /發(fā)現(xiàn)調(diào)入內(nèi)存的進(jìn)程p1 a = rp-p_size; /(1)a是數(shù)據(jù)段長(zhǎng)度 if(rp=rp-p_textp) !=

8、NULL)/(2)p1有代碼段 if(rp-x_ccount = 0) /p1進(jìn)程的代碼段不在內(nèi)存，需調(diào)入 a =+ rp-x_size; /增加進(jìn)程代碼段的地址空間 /a=proc.p_size+text.x_size if(a=malloc(coremap, a) != NULL)/調(diào)用malloc()申請(qǐng)內(nèi)存空間 goto found2;/轉(zhuǎn)到found2處理調(diào)入sched()：選擇調(diào)出到交換區(qū)的進(jìn)程 sp16(); /尋找內(nèi)存中SWAIT或SSTOP狀態(tài)的進(jìn)程作為換出對(duì)象 for(rp=&proc0;rpp_flag&(SSYS|SLOCK|SLOAD)=SLOAD& (rp-p_st

9、at=SWAIT|rp-p_stat=SSTOP) goto found1; /執(zhí)行調(diào)出調(diào)出算法考慮以下因素： （1）某些進(jìn)程不調(diào)出： 系統(tǒng)進(jìn)程proc.p_flag=SSYS 鎖：proc.p_flag=SLOCK （2）首先調(diào)出低優(yōu)先級(jí)阻塞進(jìn)程SWAIT,暫停狀態(tài)進(jìn)程SSTOP （3）若不存在，則調(diào)出高優(yōu)先級(jí)阻塞進(jìn)程SSLEEP，就緒進(jìn)程SRUN中在內(nèi)存時(shí)間最長(zhǎng)的 若無(wú)調(diào)入進(jìn)程且調(diào)出進(jìn)程的p_time2，則不執(zhí)行調(diào)出操作。sched() If(n3) /調(diào)入進(jìn)程在外存交換區(qū)的時(shí)間3秒 goto sloop; /0#阻塞，不執(zhí)行調(diào)入 n=-1;/放寬條件，將SRUN或SSLEEP且在內(nèi)存中最

10、長(zhǎng)時(shí)間的進(jìn)程換出 for(rp=&proc0;rpp_flag&(SSYS|SLOCK|SLOAD)=SLOAD& (rp-p_stat=SRUN|rp-p_stat=SSLEEP)& rp-p_timen) p1=rp; n=rp-p_time;/在內(nèi)存中最長(zhǎng)時(shí)間的進(jìn)程 sched()：found1調(diào)出處理 if(np_flag=&SLOAD;/在內(nèi)存標(biāo)志清除 xswap(rp,1,0); /調(diào)出數(shù)據(jù)段，第二個(gè)參數(shù)=1表示從內(nèi)存釋放進(jìn)程 goto loop;/返回loop再次選擇調(diào)入進(jìn)程sched原語(yǔ)：found2調(diào)入處理 found2:/調(diào)入處理 if(rp=p1-p_textp) !=

11、NULL) /處理p1進(jìn)程的代碼段 if(rp-x_ccount = 0) /在內(nèi)存沒(méi)有p1的代碼段,a是申請(qǐng)的空白區(qū)起始地址 if(swap(rp-x_daddr, a, rp-x_size, B_READ)/(1)調(diào)入p1的代碼段 goto swaper; rp-x_caddr = a; /將代碼段新的信息保存在text中 a =+ rp-x_size; rp-x_ccount+; /內(nèi)存進(jìn)程的參照計(jì)數(shù) sched原語(yǔ)：調(diào)入處理 rp = p1; /調(diào)入p1 if(swap(rp-p_addr, a, rp-p_size, B_READ)/(2)調(diào)入數(shù)據(jù)段。數(shù)據(jù)段和代碼段相鄰 goto s

12、waper; mfree(swapmap, (rp-p_size+7)/8, rp-p_addr); /釋放數(shù)據(jù)段在交換區(qū)的空間 rp-p_addr = a; /將數(shù)據(jù)段新的信息保存在proc rp-p_flag =| SLOAD;/flag標(biāo)志SLOAD在內(nèi)存 rp-p_time = 0;/在內(nèi)存時(shí)間為0 goto loop;/返回loop，尋找是否存在其它調(diào)入進(jìn)程 swaper: panic(swap error); sched原語(yǔ)總結(jié) 0#主要任務(wù)是調(diào)用sched()實(shí)現(xiàn)進(jìn)程的換入與換出，無(wú)事可做時(shí)就去睡眠。 1.當(dāng)它被喚醒去執(zhí)行換入操作時(shí)，則去查看進(jìn)程表中所有進(jìn)程的狀態(tài)，從中找出“就緒

13、且換出”狀態(tài)的進(jìn)程（可能有多個(gè)），把其中換出時(shí)間最久（必須大于2秒鐘）的進(jìn)程作為換入進(jìn)程。再根據(jù)該進(jìn)程的大小，調(diào)用malloc為其申請(qǐng)內(nèi)存。此時(shí)可能： （1）申請(qǐng)內(nèi)存成功，則將進(jìn)程換入 （2）申請(qǐng)內(nèi)存失敗，須先將內(nèi)存中的某些進(jìn)程換出，騰出足夠的內(nèi)存后再將進(jìn)程換入。 當(dāng)sched進(jìn)程成功換入一個(gè)進(jìn)程后，又重復(fù)上述被喚醒后的過(guò)程，陸續(xù)地將一些進(jìn)程換入，直至發(fā)生下述任一情況： （1）所有的“就緒且換出”進(jìn)程已經(jīng)被全部換入； （2）已經(jīng)無(wú)法獲得足夠的內(nèi)存來(lái)?yè)Q入進(jìn)程 每當(dāng)有一個(gè)“就緒”狀態(tài)進(jìn)程被換出，或每到一秒鐘時(shí)，將sched進(jìn)程喚醒。sched原語(yǔ)總結(jié) 換出 系統(tǒng)進(jìn)程不能被換出 被鎖住的進(jìn)程也不能被

14、換出，只是將處于睡眠狀態(tài)的進(jìn)程換出。當(dāng)有多個(gè)這樣的進(jìn)程時(shí)，UNIX系統(tǒng)分別計(jì)算各進(jìn)程的優(yōu)先數(shù)與駐留主存時(shí)間的和，選擇其值最高的進(jìn)程換出。如果內(nèi)存中沒(méi)有阻塞的進(jìn)程，則選擇駐留內(nèi)存時(shí)間已超過(guò)2秒鐘、且駐留時(shí)間最長(zhǎng)的就緒進(jìn)程換出。 當(dāng)無(wú)進(jìn)程可換出時(shí)，sched進(jìn)程將使自己阻塞。 一旦系統(tǒng)中出現(xiàn)進(jìn)入阻塞狀態(tài)的進(jìn)程時(shí)，UNIX便喚醒sched進(jìn)程；即使無(wú)進(jìn)程進(jìn)入睡眠狀態(tài)，時(shí)鐘進(jìn)程也會(huì)每秒鐘喚醒一次sched進(jìn)程。2.xalloc() 進(jìn)程共享代碼段的處理 代碼段通過(guò)text管理。text每個(gè)元素對(duì)應(yīng)一個(gè)代碼段。 每個(gè)進(jìn)程使用的text元素由proc.p_textp設(shè)定，代碼段長(zhǎng)度由user.u_tsiz

15、e表示。text結(jié)構(gòu)體 #define NTEXT 40 struct text int x_daddr;/代碼段在外存交換區(qū)的地址，必須有一個(gè)備份 int x_caddr;/代碼段在內(nèi)存的地址，允許正文段不在內(nèi)存 int x_size; /代碼段長(zhǎng)度 int *x_iptr; /可執(zhí)行文件的inode結(jié)點(diǎn)號(hào) char x_count;/引用代碼段的所有進(jìn)程數(shù)量 char x_ccount;/引用代碼段的在內(nèi)存中的進(jìn)程數(shù)量 textNTEXT; 代碼段 與代碼段有關(guān)的信息必須存放在操作系統(tǒng)的中心部分，為此設(shè)計(jì)了“text”數(shù)組。 共享正文段的每一個(gè)進(jìn)程在其“proc.p_textp”中存放一個(gè)

16、指向相應(yīng)text元素的指針。 正文段存放在可執(zhí)行文件的開(kāi)始部分。共享某一正文段的進(jìn)程開(kāi)始執(zhí)行時(shí)先使所需正文段的一個(gè)副本存放到“交換”區(qū)中。 在共享某一正文段的所有進(jìn)程終止或改換映像后，釋放該正文段所占用的資源。在內(nèi)存中當(dāng)前并無(wú)進(jìn)程引用某正文段時(shí)，釋放它所占用的內(nèi)存資源。一般而言，只要當(dāng)前不存在引用某正文段的進(jìn)程，則釋放它所占用的“交換”區(qū)。 共享某一正文段的進(jìn)程數(shù)以及共享某一正文段其映像在內(nèi)存中的進(jìn)程數(shù)分別由“x_count”和“x_ccount”記錄。例程“xfree”和“xccdec”分別對(duì)這兩個(gè)計(jì)數(shù)器執(zhí)行減1操作，當(dāng)這兩個(gè)計(jì)數(shù)器值分別為0時(shí)，它們也進(jìn)行釋放相應(yīng)資源的操作。(只要使進(jìn)程換出

17、或終止，就調(diào)用xccdec；只要一個(gè)進(jìn)程終止，就調(diào)用xfree。)P89xalloc()(ken/text.c) xalloc(ip) int *ip; /參數(shù)ip：指向代碼文件“方式”(mode)的指針 register struct text *xp; register *rp,ts; if(u.u_arg1=0) / u.u_arg1包含以字節(jié)為單位的正文段長(zhǎng)度 return;xalloc:正文段的調(diào)入 rp=NULL; /記錄text空白項(xiàng) for(xp=&text0;xpx_iptr=NULL) /尋找text未使用的元素 if(rp=NULL) rp=xp; else 已經(jīng)存在的正

18、文段 if(xp-x_iptr=ip) /找到該正文段ip所在項(xiàng) xp-x_count+; /共享正文段的進(jìn)程參照增加一個(gè) u.u_procp-p_textp=xp; /記錄進(jìn)程的代碼段所在地址，將元素分配給進(jìn)程P90 goto out; /轉(zhuǎn)移至“out” if(xp=rp)=NULL) /text數(shù)組中沒(méi)有這一項(xiàng)，而且沒(méi)有空白 panic(“out of text”);在text中保存第一次使用的正文段信息 xp-x_count=1;/正文段第一次使用進(jìn)程數(shù)=1 xp-x_ccount=0;/在內(nèi)存的調(diào)用進(jìn)程數(shù)為0 xp-x_iptr=ip; /代碼段的inode結(jié)點(diǎn) ts=(u.u_ar

19、g1+63)6)&01777 /正文段長(zhǎng)度塊數(shù)，001111111111 /字節(jié)長(zhǎng)度不是邏輯地址 xp-x_size=ts; 從0開(kāi)始在外存交換區(qū)為第一次調(diào)用的代碼段建立備份 if(xp-x_daddr=malloc(swapmap,(ts+7)/8)=NULL) /為代碼段申請(qǐng)外存交換區(qū)。交換區(qū)512B=8*64B panic(“out of swap space”);將正文段讀到數(shù)據(jù)區(qū) expand(USIZE+ts);/進(jìn)程地址空間的數(shù)據(jù)段包含PPDA和正文段 extabur(0,ts,0,0); /調(diào)入代碼段之前，estabur設(shè)置進(jìn)程APR頁(yè)表 /更新用戶進(jìn)程空間將。代碼段調(diào)入到第0塊，因?yàn)閚t=0 u.u_count=u.u_arg1;/長(zhǎng)度字節(jié) u.u_offset1=020; /偏移量：跳過(guò)可執(zhí)行文件的文件頭 u.u_base=0; /從用戶數(shù)據(jù)段地址空間中的0地址單元開(kāi)始讀入 實(shí)際上是ARP0的第一塊 readi(ip); /將代碼段讀到進(jìn)程的當(dāng)前數(shù)據(jù)段將數(shù)據(jù)段(減除PPDA)寫(xiě)到為正文段保留的磁盤(pán)交換區(qū)中 rp=u.u_procp; /在PCB塊中保存新信息 rp-p_flag=|SLOCK; /進(jìn)程標(biāo)志在內(nèi)存 swap(xp-x_daddr,rp-p_addr+USIZE,ts,0); /將數(shù)據(jù)段中的代碼段