《操作系統(tǒng)原理》 (2)ppt課件

1、l 操作系統(tǒng)概述l 進(jìn)程管理l 存儲(chǔ)管理l 文件系統(tǒng)與I/O操作系統(tǒng)給計(jì)算機(jī)一個(gè)靈敏的大腦、一個(gè)強(qiáng)壯的心臟和突出的個(gè)性 孰優(yōu)？q(quoting Linus Torvalds):q . message passing as the fundamental operation of the OS is just an exercise in computer science masturbation. It may feel good, but you dont actually get anything DONE.qMonolithic：內(nèi)核中一切的子系統(tǒng)運(yùn)轉(zhuǎn)在一樣的特權(quán)級(jí)(privilege

2、d mode，擁有一樣的地址空間，通訊采用常規(guī)C函數(shù)調(diào)用的方式。系統(tǒng)調(diào)用是一個(gè)復(fù)雜的過程系統(tǒng)調(diào)用往往經(jīng)過軟中斷的方式實(shí)現(xiàn)系統(tǒng)調(diào)用在為運(yùn)用程序提供操作系統(tǒng)效力的同時(shí)，也實(shí)現(xiàn)了對(duì)計(jì)算機(jī)資源和運(yùn)用程序的維護(hù)nProcess - a program in executionn text section, data section, stack, current activity n進(jìn)程是資源擁有的根本單位進(jìn)程是資源擁有的根本單位(unit of resource ownership)nCPU、存儲(chǔ)空間，及其他資源、存儲(chǔ)空間，及其他資源I/O設(shè)備、文件等設(shè)備、文件等n進(jìn)程控制塊進(jìn)程控制塊PCB及其管理及

3、其管理n進(jìn)程的形狀：進(jìn)程的形狀：running,ready,blocked,stopped,zombien qThread an execution path in a processqThread the unit of dispatchingq 進(jìn)程中的線程共享進(jìn)程資源，但擁有私有堆棧及進(jìn)程中的線程共享進(jìn)程資源，但擁有私有堆棧及線程控制塊線程控制塊(TCB，存貯存放器值、優(yōu)先級(jí)及其他線，存貯存放器值、優(yōu)先級(jí)及其他線程形狀信息程形狀信息)q中心級(jí)線程中心級(jí)線程KLT：kernel-level threadq運(yùn)用程序經(jīng)過運(yùn)用程序經(jīng)過API調(diào)用中心線程管理例程調(diào)用中心線程管理例程(kernel

4、thread facility)來管理：來管理：q 需求進(jìn)展方式切換需求進(jìn)展方式切換q是是OS調(diào)度的根本單位調(diào)度的根本單位q線程阻塞不會(huì)導(dǎo)致整個(gè)進(jìn)程的阻塞線程阻塞不會(huì)導(dǎo)致整個(gè)進(jìn)程的阻塞q在多處置器環(huán)境下，內(nèi)核可使線程在不同的處置器上在多處置器環(huán)境下，內(nèi)核可使線程在不同的處置器上運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)qE.g. windows threadq用戶級(jí)線程用戶級(jí)線程ULT：user-level threadq由運(yùn)用程序本人經(jīng)過線程庫(kù)由運(yùn)用程序本人經(jīng)過線程庫(kù)(thread library)來管理來管理：線程創(chuàng)建、終止、線程間通訊，線程調(diào)度與切換：線程創(chuàng)建、終止、線程間通訊，線程調(diào)度與切換qOS感知不到感知不到ULT

5、的存在的存在q線程阻塞會(huì)導(dǎo)致整個(gè)進(jìn)程的阻塞線程阻塞會(huì)導(dǎo)致整個(gè)進(jìn)程的阻塞q實(shí)際上講，在任何實(shí)際上講，在任何OS下都可以實(shí)現(xiàn)下都可以實(shí)現(xiàn)q無法利用多處置器無法利用多處置器#include #include int sum;void *runner(void *param);main(int argc, char *argv) pthread_t tid; pthread_attr_t attr; pthread_attr_init(&attr); /初始化線程屬性為缺省屬性 pthread_create(&tid,&attr,runner,argv1); /創(chuàng)建線程 pth

6、read_join(tid,NULL); /等待線程tid終了 printf(“sum=%dn,sum);void *runner(void *param) int upper=atoi(param); int i; sum = 0; if (upper 0) for ( i = 1; i =upper; i+) sum +=i; pthread_exit(0);三、并發(fā)控制：互斥與同步三、并發(fā)控制：互斥與同步并發(fā)并發(fā)Concurrent 與并行與并行Parallel q臨界資源臨界資源(critical resource)q一次只能由一個(gè)進(jìn)程訪問的資源一次只能由一個(gè)進(jìn)程訪問的資源q臨界區(qū)臨界

7、區(qū)(critical section)q訪問臨界資源的代碼段稱為臨界區(qū)訪問臨界資源的代碼段稱為臨界區(qū)CSq互斥互斥(mutual exclusion)q在一個(gè)時(shí)辰最多只需一個(gè)進(jìn)程在臨界區(qū)在一個(gè)時(shí)辰最多只需一個(gè)進(jìn)程在臨界區(qū)q同步同步(synchronization)q協(xié)調(diào)需求訪問臨界資源的進(jìn)程，否那么會(huì)導(dǎo)致協(xié)調(diào)需求訪問臨界資源的進(jìn)程，否那么會(huì)導(dǎo)致race condition競(jìng)爭(zhēng)條件競(jìng)爭(zhēng)條件q如：兩進(jìn)程如：兩進(jìn)程 p0,p1，都經(jīng)過下面的代碼訪問一個(gè)共享的存儲(chǔ)單，都經(jīng)過下面的代碼訪問一個(gè)共享的存儲(chǔ)單元元:qShared variable:int total : = 0 ;qp0,p1:qq int

8、 count;qfor (count=1; count =50; count+)q total = total + 1 ;qqtotal能夠的結(jié)果？能夠的結(jié)果？q最大值？最小值？最大值？最小值？q留意留意total是兩個(gè)進(jìn)程都可以訪問的共享存儲(chǔ)單元，不同于普是兩個(gè)進(jìn)程都可以訪問的共享存儲(chǔ)單元，不同于普通程序中的全局變量通程序中的全局變量q兩個(gè)前提：兩個(gè)前提：q對(duì)處置器數(shù)及各進(jìn)程的相對(duì)運(yùn)轉(zhuǎn)速度不會(huì)是零速度不應(yīng)該對(duì)處置器數(shù)及各進(jìn)程的相對(duì)運(yùn)轉(zhuǎn)速度不會(huì)是零速度不應(yīng)該有任何假設(shè)有任何假設(shè)q進(jìn)程在臨界區(qū)停留的時(shí)間是有限的進(jìn)程在臨界區(qū)停留的時(shí)間是有限的q三個(gè)必需：三個(gè)必需：q互斥互斥(mutual excl

9、usion)q有空讓進(jìn)有空讓進(jìn)(progress)，假設(shè)沒有進(jìn)程在臨界區(qū)，那么應(yīng)該讓懇求，假設(shè)沒有進(jìn)程在臨界區(qū)，那么應(yīng)該讓懇求進(jìn)入臨界區(qū)的進(jìn)程中的一個(gè)立刻進(jìn)入進(jìn)入臨界區(qū)的進(jìn)程中的一個(gè)立刻進(jìn)入q有限等待有限等待(bounded waiting)，懇求進(jìn)入臨界區(qū)的進(jìn)程不會(huì)無盡，懇求進(jìn)入臨界區(qū)的進(jìn)程不會(huì)無盡頭的等待即不會(huì)有饑餓景象頭的等待即不會(huì)有饑餓景象1.軟件方法忙等待軟件方法忙等待Shared variablesboolean flag2; /initially flag 0 = flag 1 = turn; /initially turn=i;Process Pido fl

10、agi := true;while (turn i) while (flag j ) ; turn := i ;flag i = false; while (1);此算法正確嗎？此算法正確嗎？Peterson算法：算法直觀，只能處理二個(gè)進(jìn)程同步 P0: do flag0:=true; /希望進(jìn)入 turn := 1; /給對(duì)方一次時(shí)機(jī) while flag1 and turn = 1 donothing; /假設(shè)對(duì)方先懇求那么等待 flag0:= false; while (1)2. 利用硬件支持利用硬件支持中斷屏蔽中斷屏蔽(interrupt disable)代價(jià)大，無法做到程序的交叉執(zhí)行代

11、價(jià)大，無法做到程序的交叉執(zhí)行interleave)多處置環(huán)境下無法實(shí)現(xiàn)多處置環(huán)境下無法實(shí)現(xiàn)特殊機(jī)器指令特殊機(jī)器指令Test and Set InstructionExchange Instruction優(yōu)點(diǎn)：適宜多處置器環(huán)境、簡(jiǎn)單優(yōu)點(diǎn)：適宜多處置器環(huán)境、簡(jiǎn)單缺陷：必需忙等待缺陷：必需忙等待(busy waiting)、能夠?qū)е吗囸I、能夠?qū)е吗囸IqOS提供的安裝，用于進(jìn)展進(jìn)程提供的安裝，用于進(jìn)展進(jìn)程/線程的同步與互斥線程的同步與互斥q數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造(s)qcount:integer;=0表示可用資源數(shù)，表示可用資源數(shù)，0，其絕對(duì)值表示掛起進(jìn)程，其絕對(duì)值表示掛起進(jìn)程數(shù)，初始化非負(fù)數(shù)，初始化非負(fù)q

12、queue:list of process；正在等待該類資源的進(jìn)程；正在等待該類資源的進(jìn)程q進(jìn)程只能經(jīng)過進(jìn)程只能經(jīng)過OS提供的提供的wait和和signal兩個(gè)操作原語訪問信號(hào)量?jī)蓚€(gè)操作原語訪問信號(hào)量qWait(s):等待資源等待資源q s.count = s.count 1;q if s.count 0 then beginq place this process in s.queue;q block this process;q end;qSignal(s):釋放資源釋放資源q s.count = s.count +1;q if s.count =0 then beginq remove

13、a process P from s.queue;q place process P on ready list;q end;信號(hào)量信號(hào)量full，初始化為，初始化為0,表示緩沖區(qū)中可消費(fèi)的資源數(shù)表示緩沖區(qū)中可消費(fèi)的資源數(shù)mutex，初始化為，初始化為1,用于對(duì)緩沖區(qū)的互斥操作用于對(duì)緩沖區(qū)的互斥操作empty, 初始化為緩沖區(qū)的長(zhǎng)度初始化為緩沖區(qū)的長(zhǎng)度N，表示緩沖區(qū)中空閑單元，表示緩沖區(qū)中空閑單元數(shù)數(shù)Producer: repeat produce; wait(empty);wait(mutex); append; signal(mutex) ;signal(full); foreverCon

14、sumer: repeat wait(full); wait(mutex); take; signal(mutex);signal(empty);consume forever例：有n個(gè)進(jìn)程P1，P2，Pn向容量為M的緩沖區(qū)寫數(shù)據(jù)，每個(gè)進(jìn)程一次寫1個(gè)數(shù)據(jù)，當(dāng)緩沖區(qū)寫滿時(shí)，另一個(gè)讀進(jìn)程Pr一次將M個(gè)數(shù)據(jù)全部讀完，如此反復(fù)。請(qǐng)用信號(hào)量處理這些進(jìn)程的同步互斥問題。答：此題中需求定義下述變量和信號(hào)量：data_type bufferM; /* data_type對(duì)應(yīng)于所需求的數(shù)據(jù)類型，如int、float等 */int in=0； /* 用來指示下一個(gè)可存放數(shù)據(jù)的緩沖區(qū) */semaphore emp

15、ty=M; /* 對(duì)應(yīng)空閑的緩沖區(qū) */semaphore full=0; /* 對(duì)應(yīng)緩沖區(qū)中的數(shù)據(jù) */semaphore mutex=1; /* 用來實(shí)現(xiàn)Pi進(jìn)程對(duì)變量in的互斥訪問 */進(jìn)程Pi可描畫為：Pi() while(1) wait(empty); wait(mutex); 向緩沖區(qū)bufferin中寫數(shù)據(jù)； in=(in+1)%M; signal(mutex); signal(full); 進(jìn)程Pr可描畫為：Pr() int i; while(1) for(i=0;iM;i+) wait(full); wait(mutex); 取出緩沖buffer0到bufferM-1中的數(shù)據(jù)

16、；signal(mutex); for(i=0;iM;i+) signal(empty); 例：有一個(gè)倉(cāng)庫(kù)，可以存放A和B兩種產(chǎn)品，但要求：1每次只能存入一種產(chǎn)品A或B；2-NA產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量M。其中，N和M是正整數(shù)。試用信號(hào)量來同步產(chǎn)品A與產(chǎn)品B的入庫(kù)過程。答：此題中，首先需求設(shè)置一個(gè)初值為1的互斥信號(hào)量mutex，以保證每次只存入一種產(chǎn)品。另外，為了保證“-NA產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量M，還需設(shè)置信號(hào)量SA，表示倉(cāng)庫(kù)中目前可再存放的A產(chǎn)品的數(shù)量，其初值為M-1；SB，表示目前還可再存放的B產(chǎn)品的數(shù)量，其初值為N-1。A產(chǎn)品入庫(kù)的過程可描畫為： B產(chǎn)品入庫(kù)的過程可描畫為：while(1)

17、while(1)wait(SA); /* 還可放A產(chǎn)品？ */ wait (SB); /* 還可放B產(chǎn)品？ */wait(mutex); wait(mutex);將A產(chǎn)品放入倉(cāng)庫(kù)； 將B產(chǎn)品放入倉(cāng)庫(kù)；signal(mutex); signal(mutex);signal(SB); /*可放B產(chǎn)品數(shù)增1*/ signal(SA); /*可放A產(chǎn)品數(shù)增1*/ n四、并發(fā)控制：死鎖問題四、并發(fā)控制：死鎖問題1.死鎖死鎖deadlock系統(tǒng)中存在一個(gè)進(jìn)程集合，該集合中的每個(gè)進(jìn)程都占用系統(tǒng)中存在一個(gè)進(jìn)程集合，該集合中的每個(gè)進(jìn)程都占用了一定數(shù)量的資源，并且在等待被集合中的其他進(jìn)程占了一定數(shù)量的資源，并且在

18、等待被集合中的其他進(jìn)程占用的資源用的資源例：某系統(tǒng)由一樣類型的例：某系統(tǒng)由一樣類型的8個(gè)資源組成，假設(shè)資源可被個(gè)資源組成，假設(shè)資源可被3個(gè)個(gè)進(jìn)程共享，每個(gè)進(jìn)程最多可懇求進(jìn)程共享，每個(gè)進(jìn)程最多可懇求3個(gè)資源，問該系統(tǒng)能否個(gè)資源，問該系統(tǒng)能否會(huì)發(fā)生死鎖？會(huì)發(fā)生死鎖？ nMutual exclusion：互斥nHold and wait：堅(jiān)持等待，懇求資源時(shí)擁有其他資源nNo preemption：非剝奪，進(jìn)程占有的資源只能由進(jìn)程本人釋放，不會(huì)被別的進(jìn)程剝奪nCircular wait：循環(huán)等待(假設(shè)各類資源的資源數(shù)為1，那么一定死鎖)n間接預(yù)防：阻止Mutual exclusion, Hold a

19、nd wait及No preemption都滿足n直接預(yù)防：阻止circular wait的發(fā)生。n一種可行的方法：有序懇求法對(duì)一切資源類別編號(hào)，進(jìn)程懇求資源按序進(jìn)展。n例：哲學(xué)家就餐問題，筷子編號(hào)，先拿編號(hào)小的、再拿大的。n進(jìn)程懇求資源時(shí)，決議能否應(yīng)該滿足n必需預(yù)先知道每個(gè)進(jìn)程需求的各類資源數(shù)nBankers algorithm，銀行家算法n根本思想，假設(shè)新的形狀是平安的safe，那么滿足它nSafe state：從此形狀出發(fā)，存在某種執(zhí)行順序平安序列,safe sequence，可以使一切進(jìn)程執(zhí)行終了。n平安形狀只是暫時(shí)平安，假設(shè)以后資源分配不當(dāng)，也會(huì)導(dǎo)致死鎖；不平安形狀不一定就死鎖。形狀

20、形狀a是平安的是平安的(a) (b) (c) (d) (e)(a) (b) (c) (d) 形狀形狀b是不平安的是不平安的nP4 沒有獲得資源，打上標(biāo)志沒有獲得資源，打上標(biāo)志n置置 W = (0,0,0,0,1)nP3懇求的資源懇求的資源 = W. 給給P3打標(biāo)志，并置打標(biāo)志，并置 W = W + (0,0,0,1,0) = (0,0,0,1,1)n算法無法找到滿足條件的進(jìn)程，終止。所以系統(tǒng)發(fā)生死鎖，算法無法找到滿足條件的進(jìn)程，終止。所以系統(tǒng)發(fā)生死鎖，P1和和P2 是死鎖進(jìn)程是死鎖進(jìn)程R1 R2 R3 R4 R5P1P2P3P4Request Allocated AvailableR1 R2

21、R3 R4 R5R1 R2 R3 R4 R50 1 0 0 10 0 1 0 10 0 0 0 11 0 1 0 11 0 1 1 01 1 0 0 00 0 0 1 00 0 0 0 00 0 0 0 1n當(dāng)發(fā)生死鎖時(shí)，如何恢復(fù)死鎖n Abort all deadlocked processes. Abort one process at a time until the deadlock cycle is eliminated. In which order should we choose to abort?n Priority of the process.n How long pro

22、cess has computed, and how much longer to completion.nResources the process has used.nResources process needs to complete.nHow many processes will need to be terminated. nIs process interactive or batch? nSelecting a victim minimize costn Rollback return to some safe state, restart process for that

23、state.Starvation same process may always be picked as victim, include number of rollback in cost factor.1. CPU約束進(jìn)程與約束進(jìn)程與I/O約束進(jìn)程約束進(jìn)程進(jìn)程的執(zhí)行是進(jìn)程的執(zhí)行是CPU burst與與I/O burst交替的過程交替的過程CPU約束進(jìn)程：大量時(shí)間作計(jì)算，少量約束進(jìn)程：大量時(shí)間作計(jì)算，少量I/OI/O 約束進(jìn)程：大量的約束進(jìn)程：大量的I/O，少量時(shí)間作計(jì)算，少量時(shí)間作計(jì)算2. 調(diào)度準(zhǔn)那么調(diào)度準(zhǔn)那么(criteria)3. 調(diào)度方式調(diào)度方式(decision mode)Non

24、-preemptive非搶占式非搶占式進(jìn)程一旦被調(diào)度，那么執(zhí)行至終了或不能繼續(xù)執(zhí)進(jìn)程一旦被調(diào)度，那么執(zhí)行至終了或不能繼續(xù)執(zhí)行如由于發(fā)起行如由于發(fā)起I/O操作而等待操作而等待Preemptive搶占式搶占式當(dāng)一個(gè)新的進(jìn)程到達(dá)時(shí)當(dāng)一個(gè)新的進(jìn)程到達(dá)時(shí)當(dāng)有進(jìn)程從阻塞變?yōu)榫途w時(shí)當(dāng)有進(jìn)程從阻塞變?yōu)榫途w時(shí)進(jìn)程從中心態(tài)前往到用戶態(tài)時(shí)如中斷、系統(tǒng)調(diào)進(jìn)程從中心態(tài)前往到用戶態(tài)時(shí)如中斷、系統(tǒng)調(diào)用前往時(shí)用前往時(shí)注：此搶占非指內(nèi)核搶占注：此搶占非指內(nèi)核搶占4. 常用調(diào)度算法常用調(diào)度算法FCFS(first come first served)先來先效力，直至終了先來先效力，直至終了(nonpreemptive)RR:Ro

25、und robin時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)(time slice,preemptive)時(shí)間片到時(shí)，將進(jìn)程放入就緒隊(duì)列的末尾，然后從時(shí)間片到時(shí)，將進(jìn)程放入就緒隊(duì)列的末尾，然后從隊(duì)列頭部取出一個(gè)進(jìn)程運(yùn)轉(zhuǎn)隊(duì)列頭部取出一個(gè)進(jìn)程運(yùn)轉(zhuǎn)公平的調(diào)度戰(zhàn)略，不會(huì)導(dǎo)致進(jìn)程饑餓公平的調(diào)度戰(zhàn)略，不會(huì)導(dǎo)致進(jìn)程饑餓Priority scheduling：基于優(yōu)先級(jí)的調(diào)度：基于優(yōu)先級(jí)的調(diào)度存在問題：饑餓低優(yōu)先級(jí)進(jìn)程能夠永遠(yuǎn)得不到執(zhí)存在問題：饑餓低優(yōu)先級(jí)進(jìn)程能夠永遠(yuǎn)得不到執(zhí)行行處理方法：老化處理方法：老化 Aging 隨著時(shí)間的推移，進(jìn)隨著時(shí)間的推移，進(jìn)程的優(yōu)先級(jí)可以提升程的優(yōu)先級(jí)可以提升(即進(jìn)程的優(yōu)先級(jí)可以是動(dòng)態(tài)即進(jìn)程的優(yōu)先級(jí)

26、可以是動(dòng)態(tài)的的)n分區(qū)：將內(nèi)存劃分為假設(shè)干個(gè)分區(qū)，每個(gè)分區(qū)存放一個(gè)進(jìn)程，以分區(qū)：將內(nèi)存劃分為假設(shè)干個(gè)分區(qū)，每個(gè)分區(qū)存放一個(gè)進(jìn)程，以支持多道程序支持多道程序(multi-programming)，nFixed partitioning:固定大小的分區(qū)，分區(qū)內(nèi)部會(huì)出現(xiàn)碎塊固定大小的分區(qū)，分區(qū)內(nèi)部會(huì)出現(xiàn)碎塊(internal fragment)nDynamic partitioning:動(dòng)態(tài)分區(qū)，按照進(jìn)程大小決議分區(qū)大小，動(dòng)態(tài)分區(qū)，按照進(jìn)程大小決議分區(qū)大小，不存在內(nèi)部碎塊，但有外部碎塊不存在內(nèi)部碎塊，但有外部碎塊external fragment)，涉及放，涉及放置算法置算法(placement a

27、lgorithm)：first fit,best fit, next fitOSprocess 5process 8process 2OSprocess 5process 2OSprocess 5process 2OSprocess 5process 9process 2process 9process 10Buddy system常用于空閑內(nèi)存管理常用于空閑內(nèi)存管理n假設(shè)一次TLB訪問時(shí)間為 ,一次存儲(chǔ)器訪問時(shí)間為1n TLB命中率為，那么平均存取時(shí)間EAT為：nEAT = (1 + ) + (2 + )(1 )n= 2 + 頁(yè)表的實(shí)現(xiàn)方式：頁(yè)表的實(shí)現(xiàn)方式： 頁(yè)表分級(jí)頁(yè)表分級(jí) Hash頁(yè)表頁(yè)

28、表 倒置頁(yè)表倒置頁(yè)表n進(jìn)程的虛地址空間進(jìn)程的虛地址空間(virtual address space)n由進(jìn)程的邏輯地址組成的地址空間。由進(jìn)程的邏輯地址組成的地址空間。n虛地址空間可以遠(yuǎn)大于系統(tǒng)的物理內(nèi)存。虛地址空間可以遠(yuǎn)大于系統(tǒng)的物理內(nèi)存。n虛擬存儲(chǔ)器虛擬存儲(chǔ)器(virtual memory)：邏輯地址訪問的：邏輯地址訪問的存儲(chǔ)器存儲(chǔ)器n決議何時(shí)將進(jìn)程的邏輯頁(yè)面裝入內(nèi)存決議何時(shí)將進(jìn)程的邏輯頁(yè)面裝入內(nèi)存nDemand paging按需調(diào)頁(yè)：發(fā)生缺頁(yè)時(shí)，才將頁(yè)按需調(diào)頁(yè)：發(fā)生缺頁(yè)時(shí)，才將頁(yè)面裝入。面裝入。nPrepaging預(yù)?。侯A(yù)先將某些頁(yè)面裝入內(nèi)存。預(yù)?。侯A(yù)先將某些頁(yè)面裝入內(nèi)存。nOS分配給進(jìn)程

29、的物理內(nèi)存不夠用時(shí)，需求頁(yè)交換分配給進(jìn)程的物理內(nèi)存不夠用時(shí)，需求頁(yè)交換nOptimal：最優(yōu)化方法，選擇未來最久不會(huì)被訪問的頁(yè)換：最優(yōu)化方法，選擇未來最久不會(huì)被訪問的頁(yè)換出出n需求預(yù)先知道頁(yè)訪問序列需求預(yù)先知道頁(yè)訪問序列n不能夠?qū)崿F(xiàn)，只是作為一個(gè)評(píng)判規(guī)范不能夠?qū)崿F(xiàn)，只是作為一個(gè)評(píng)判規(guī)范nFIFO：最先裝入的被換出：最先裝入的被換出nLRU:最久未運(yùn)用的頁(yè)被換出最久未運(yùn)用的頁(yè)被換出(基于基于locality景象，很有效景象，很有效)nClock policy，時(shí)鐘算法。，時(shí)鐘算法。LRU算法不易實(shí)現(xiàn)，用時(shí)鐘算算法不易實(shí)現(xiàn)，用時(shí)鐘算法近似模擬法近似模擬n每頁(yè)設(shè)置一個(gè)每頁(yè)設(shè)置一個(gè)reference

30、bit，為，為1表示在時(shí)鐘指針循環(huán)一表示在時(shí)鐘指針循環(huán)一周內(nèi)被訪問過；周內(nèi)被訪問過；n查找交換頁(yè)：查找交換頁(yè)：n 指針掃描，假設(shè)指針掃描，假設(shè)reference bit =1,置為置為0,否那么該頁(yè)否那么該頁(yè)就是交換對(duì)象。就是交換對(duì)象。nBeladys Anomaly(belady異態(tài)異態(tài)):內(nèi)存大，反而缺頁(yè)率高內(nèi)存大，反而缺頁(yè)率高n進(jìn)程執(zhí)行時(shí)缺頁(yè)率過高，使得系統(tǒng)忙于頁(yè)面換進(jìn)換進(jìn)程執(zhí)行時(shí)缺頁(yè)率過高，使得系統(tǒng)忙于頁(yè)面換進(jìn)換出，因此執(zhí)行效率低。提高效率的可行方法：出，因此執(zhí)行效率低。提高效率的可行方法：n優(yōu)化頁(yè)調(diào)入與交換算法；優(yōu)化頁(yè)調(diào)入與交換算法；n添加物理內(nèi)存；添加物理內(nèi)存；n減少進(jìn)程數(shù)；減少進(jìn)

31、程數(shù)；n提供更快速的交換設(shè)備。提供更快速的交換設(shè)備。n任務(wù)集任務(wù)集working set,進(jìn)程近期訪問的頁(yè)面的集合進(jìn)程近期訪問的頁(yè)面的集合n為防止抖動(dòng)，應(yīng)該使得進(jìn)程獲得足夠的內(nèi)存以使進(jìn)為防止抖動(dòng)，應(yīng)該使得進(jìn)程獲得足夠的內(nèi)存以使進(jìn)程的任務(wù)集在內(nèi)存中程的任務(wù)集在內(nèi)存中n計(jì)算任務(wù)集的算法計(jì)算任務(wù)集的算法七、抖動(dòng)七、抖動(dòng)(thrashing)n實(shí)現(xiàn)虛擬存儲(chǔ)的重要手段實(shí)現(xiàn)虛擬存儲(chǔ)的重要手段n擴(kuò)展內(nèi)存，使系統(tǒng)可以運(yùn)轉(zhuǎn)比物理內(nèi)存大的程序。擴(kuò)展內(nèi)存，使系統(tǒng)可以運(yùn)轉(zhuǎn)比物理內(nèi)存大的程序。n交換空間交換空間swap spacen交換文件，文件系統(tǒng)下的一個(gè)文件如交換文件，文件系統(tǒng)下的一個(gè)文件如windows下的下的頁(yè)

32、面文件頁(yè)面文件n交換設(shè)備如交換設(shè)備如linux的的swap分區(qū)分區(qū)n后者比前者的讀寫效率高后者比前者的讀寫效率高n交換設(shè)備的管理交換設(shè)備的管理n數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造n交換設(shè)備上的空間信息；交換設(shè)備上的空間信息；n頁(yè)表項(xiàng)上標(biāo)識(shí)頁(yè)面在交換區(qū)中的信息。頁(yè)表項(xiàng)上標(biāo)識(shí)頁(yè)面在交換區(qū)中的信息。nLinux中的中的Swap cache：提高交換設(shè)備的存取效率：提高交換設(shè)備的存取效率 1.文件系統(tǒng)文件控制塊FCB目錄空閑磁盤空間管理文件系統(tǒng)性能n文件控制塊FCB)npermissions, dates, ownershipnsize, Data blocks indexesUNIX/Linux 文件控制塊i-node(index node:索引節(jié)點(diǎn)n目錄：存儲(chǔ)目錄下文件名字及屬性如FCB信息qTwo ways of handling long file names in directoryq(a) In-lineq(b) In a heapAn example of ho