操作系統(tǒng)基本特征

1、操作系統(tǒng)基本特征1,并發(fā)并發(fā)性是指宏觀上在一段時間內(nèi)能同時運行多個程序，而并行性則指同一時刻能運行多個指令。并行需要硬件支持，如多流水線或者多處理器。操作系統(tǒng)通過引入進程和線程，使得程序能夠并發(fā)運行。2 .共享共享是指系統(tǒng)中的資源可以供多個并發(fā)的進程共同使用。有兩種共享方式：互斥共享和同時共享。互斥共享的資源稱為臨界資源，例如打印機等，在同一時間只允許一個進程訪問，否則會出現(xiàn)錯誤，需要用同步機制來實現(xiàn)對臨界資源的訪問。3 .虛擬虛擬技術(shù)把一個物理實體轉(zhuǎn)換為多個邏輯實體。主要有兩種虛擬技術(shù)：時分復(fù)用技術(shù)和空分復(fù)用技術(shù)，例如多個進程能在同一個處理器上并發(fā)執(zhí)行使用了時分復(fù)用技術(shù)，讓每個進程輪流占有處

2、理器，每次只執(zhí)行一小個時間片并快速切換，這樣就好像有多個處理器進行處理。4 .異步異步是指進程不是一次性執(zhí)行完畢，而是走走停停，以不可知的速度向前推進。系統(tǒng)調(diào)用如果一個進程在用戶態(tài)需要用到操作系統(tǒng)的一些功能，就需要使用系統(tǒng)調(diào)用從而陷入內(nèi)核，由操作系統(tǒng)代為完成?？梢杂上到y(tǒng)調(diào)用請求的功能有設(shè)備管理、文件管理、進程管理、進程通信、存儲器管理等。中斷分類1,外中斷由CPU執(zhí)行指令以外的事件引起，如I/O結(jié)束中斷，表示設(shè)備輸入/輸出處理已經(jīng)完成，處理器能夠發(fā)送下一個輸入/輸出請求。此外還有時鐘中斷、控制臺中斷等。2 .異常由CPU執(zhí)行指令的內(nèi)部事件引起，如非法操作碼、地址越界、算術(shù)溢出等。3 .陷入在用

3、戶程序中使用系統(tǒng)調(diào)用。大內(nèi)核和微內(nèi)核1 .大內(nèi)核大內(nèi)核是將操作系統(tǒng)功能作為一個緊密結(jié)合的整體放到內(nèi)核，由于各模塊共享信息，因此有很高的性能。2 .微內(nèi)核由于操作系統(tǒng)不斷復(fù)雜，因此將一部分操作系統(tǒng)功能移出內(nèi)核，從而降低內(nèi)核的復(fù)雜性。移出的部分根據(jù)分層的原則劃分成若干服務(wù)，相互獨立。但是需要頻繁地在用戶態(tài)和核心態(tài)之間進行切換，會有一定的性能損失。第二章進程管理進程與線程1 .進程進程是操作系統(tǒng)進行資源分配的基本單位。描述進程的基本信息和運行狀態(tài)，所謂的創(chuàng)建進程控制塊(ProcessControlBlock,PCB)進程和撤銷進程，都是指對PCB的操作。2 .線程一個線程中可以有多個線程，是獨立調(diào)度

4、的基本單位。同一個進程中的多個線程之間可以并發(fā)執(zhí)行，它們共享進程資源。3 .區(qū)別擁有資源：進程是資源分配的基本單位，但是線程不擁有資源，線程可以訪問率屬進程的資源。 調(diào)度：線程是獨立調(diào)度的基本單位，在同一進程中，線程的切換不會引起進程切換，從一個進程內(nèi)的線程切換到另一個進程中的線程時，會引起進程切換。系統(tǒng)開銷：由于創(chuàng)建或撤銷進程時，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O設(shè)備等，因此操作系統(tǒng)所付出的開銷遠大于創(chuàng)建或撤銷線程時的開銷。類似地，在進行進程切換時，涉及當前執(zhí)行進程CPU環(huán)境的保存及新調(diào)度進程CPU環(huán)境的設(shè)置。而線程切換時只需保存和設(shè)置少量寄存器內(nèi)容，開銷很小。此外，由于同一進程

5、內(nèi)的多個線程共享進程的地址空間，因此，這些線程之間的同步與通信非常容易實現(xiàn)，甚至無需操作系統(tǒng)的干預(yù)。 通信方面：進程間通信（IPC）需要進程同步和互斥手段的輔助，以保證數(shù)據(jù)的一致性，而線程間可以通過直接讀/寫進程數(shù)據(jù)段（如全局變量）來進行通信。舉例：QQ和瀏覽器是兩個進程，瀏覽器進程里面有很多線程，例如http請求線程、事件響應(yīng)線程、渲染線程等等，線程的并發(fā)執(zhí)行使得在瀏覽器中點擊一個新鏈接從而發(fā)起http請求時，瀏覽器還可以響應(yīng)用戶的其它事件。進程狀態(tài)的切換阻塞狀態(tài)是缺少需要的資源從而由運行狀態(tài)轉(zhuǎn)換而來,但是該資源不包括CPU,缺少CPU會讓進程從運行態(tài)轉(zhuǎn)換為就緒態(tài)。只有就緒態(tài)和運行態(tài)可以相互

6、轉(zhuǎn)換，其它的都是單向轉(zhuǎn)換。就緒狀態(tài)的進程通過調(diào)度算法從而獲得CPU時間，轉(zhuǎn)為運行狀態(tài)；而運行狀態(tài)的進程，在分配給它的CPU時間片用完之后就會轉(zhuǎn)為就緒狀態(tài)，等待下一次調(diào)度。調(diào)度算法需要針對不同環(huán)境來討論調(diào)度算法。1 .批處理系統(tǒng)中的調(diào)度1.1 先來先服務(wù)（FCFS）first-comefirst-serverd。調(diào)度最先進入就緒隊列的作業(yè)。有利于長作業(yè)，但不利于短作業(yè)，因為短作業(yè)必須一直等待前面的長作業(yè)執(zhí)行完畢才能執(zhí)行，而長作業(yè)又需要執(zhí)行很長時間，造成了短作業(yè)等待時間過長。1.2 短作業(yè)優(yōu)先（SJF）shortestjobfirst。調(diào)度估計運行時間最短的作業(yè)。長作業(yè)有可能會餓死，處于一直等待短

7、作業(yè)執(zhí)行完畢的狀態(tài)。如果一直有短作業(yè)到來，那么長作業(yè)永遠得不到調(diào)度。1.3 最短剩余時間優(yōu)先（SRTN）shortestremainingtimenext。2 .交互式系統(tǒng)中的調(diào)度2.1 優(yōu)先權(quán)優(yōu)先除了可以手動賦予優(yōu)先權(quán)之外，還可以把響應(yīng)比作為優(yōu)先權(quán)，這種調(diào)度方式叫做高響應(yīng)比優(yōu)先調(diào)度算法。響應(yīng)比=（等待時間+要求服務(wù)時間）/要求服務(wù)時間=響應(yīng)時間/要求服務(wù)時間這種調(diào)度算法主要是為了解決SJF中長作業(yè)可能會餓死的問題，因為隨著等待時間的增長，響應(yīng)比也會越來越高。2.2 時間片輪轉(zhuǎn)將所有就緒進程按FCFS的原則排成一個隊列，每次調(diào)度時，把CPU分配給隊首進程，該進程可以執(zhí)行一個時間片。當時間片用完

8、時，由計時器發(fā)出時鐘中斷，調(diào)度程序便停止該進程的執(zhí)行，并將它送往就緒隊列的末尾，同時繼續(xù)把CPU分配給隊首的進程。時間片輪轉(zhuǎn)算法的效率和時間片有很大關(guān)系。因為每次進程切換都要保存進程的信息并且載入新進程的信息，如果時間片太短，進程切換太頻繁，在進程切換上就會花過多時間。2.3 多級反饋隊列就緒隊列”a至CPU（時間片:設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)越高的隊列中，為每個進程所規(guī)定的執(zhí)行時間片就越小。當一個新進程進入內(nèi)存后，首先將它放入第一隊列的末尾，按

9、FCFS原則排隊等待調(diào)度。當輪到該進程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入下一個隊列的隊尾。僅當前i-1個隊列均空時，才會調(diào)度第i隊列中的進程運行。優(yōu)點：實時性好，也適合運行短作業(yè)和長作業(yè)。2.4短進程優(yōu)先3.實時系統(tǒng)中的調(diào)度實時系統(tǒng)要一個服務(wù)請求在一個確定時間內(nèi)得到響應(yīng)。分為硬實時和軟實時，前者必須滿足絕對的截止時間，后者可以容忍一定的超時。進程同步1 .臨界區(qū)對臨界資源進行訪問的那段代碼稱為臨界區(qū)。為了互斥訪問臨界資源，每個進程在進入臨界區(qū)之前，需要先進行檢查。/entrysection/criticalsection;

10、/exitsection2 .同步與互斥同步指多個進程按一定順序執(zhí)行；互斥指多個進程在同一時刻只有一個進程能進入臨界區(qū)。同步是在對臨界區(qū)互斥訪問的基礎(chǔ)上，通過其它機制來實現(xiàn)有序訪問的。3 .信號量*信號量(Samaphore)*是-一個整型變量，可以對其執(zhí)行down和up操作，也就是常見的P和V操作。 down:如果信號量大于0，執(zhí)行-1操作；如果信號量等于0,將進程睡眠，等待信號量大于0; up:對信號量執(zhí)行+1操作，并且喚醒睡眠的進程，讓進程完成down操作。down和up操作需要被設(shè)計成原語，不可分割，通常的做法是在執(zhí)行這些操作的時候屏蔽中斷。如果信號量的取值只能為0或者1,那么就成為了

11、互斥量(Mutex),0表示臨界區(qū)已經(jīng)加鎖，1表示臨界區(qū)解鎖。typedefintsamaphore;samaphoremutex=1;voidP1()down(mutex);/臨界區(qū)up(mutex);voidP2()down(mutex);/臨界區(qū)up(mutex);使用信號量實現(xiàn)生產(chǎn)者-消費者問題使用一個互斥量mutex來對臨界資源進行訪問；empty記錄空緩沖區(qū)的數(shù)量，full記錄滿緩沖區(qū)的數(shù)量。注意，必須先執(zhí)行down操作再用互斥量對臨界區(qū)加鎖，否則會出現(xiàn)死鎖。如果都先對臨界區(qū)加鎖，然后再執(zhí)行down操作，考慮這種情況：生產(chǎn)者對臨界區(qū)加鎖后，執(zhí)行down(empty)操作，發(fā)現(xiàn)emp

12、ty=0,此時生成者睡眠。消費者此時不能進入臨界區(qū)，因為生產(chǎn)者對臨界區(qū)加鎖了，也就無法對執(zhí)行up(empty)操作，那么生產(chǎn)者和消費者就會一直等待下去。defineN100typedefintsemaphore;samaphoremutex=1;semaphoreempty=N;samaphorefull=0;voidproducer()while(TRUE)intitem=produce_item;down(empty);down(mutex);insert_item(item);up(mutex);up(full);)voidconsumer()while(TRUE)down(full);

13、down(mutex);intitem=remove_item(item);up(mutex);up(empty);consume_item(item);)4.管程使用信號量機制實現(xiàn)的生產(chǎn)者消費者問題需要客戶端代碼做很多控制，而管程把控制的代碼獨立出來，不僅不容易出錯，也使得客戶端代碼調(diào)用更容易。c語言不支持管程，下面的示例代碼使用了類Pascal語言來描述管程。示例代碼中的管程提供了insert()和remove()方法，客戶端代碼通過調(diào)用這兩個方法來解決生產(chǎn)者-消費者問題。monitorProducerConsumerintegeri;conditionc;procedureinsert(

14、);beginend;procedureremove();beginend;endmonitor;管程有一個重要特性：在一個時刻只能有一個進程使用管程。進程在無法繼續(xù)執(zhí)行的時候不能一直占用管程，必須將進程阻塞，否者其它進程永遠不能使用管程。管程引入了條件變量以及相關(guān)的操作：wait()和signal()來實現(xiàn)同步操作。對條件變量執(zhí)行wait()操作會導(dǎo)致調(diào)用進程阻塞，把管程讓出來讓另一個進程持有。signal()操作用于喚醒被阻塞的進程。使用管程實現(xiàn)生成者-消費者問題monitorProducerConsumerconditionfull,empty;integercount:=0;condi

15、tionc;procedureinsert(item:integer);beginifcount=Nthenwait(full);insert_item(item);count:=count+1;ifcount=1tensignal(empty);end;functionremove:integer;beginifcount=0thenwait(empty);remove=remove_item;count:=count-1;ifcount=N-1thensignal(full);end;endmonitor;procedureproducerbeginwhiletruedobeginitem

16、=produce_item;ProducerConsumer.insert(item);endend;procedureconsumerbeginwhiletruedobeginitem=ProducerConsumer.remove;consume_item(item);endend;進程通信進程通信可以看成是不同進程間的線程通信，對于同一個進程內(nèi)線程的通信方式，主要使用信號量、條件變量等同步機制。1.管道管道是單向的、先進先出的、無結(jié)構(gòu)的、固定大小的字節(jié)流，它把一個進程的標準輸出和另一個進程的標準輸入連接在一起。寫進程在管道的尾端寫入數(shù)據(jù)，讀進程在管道的首端讀出數(shù)據(jù)。數(shù)據(jù)讀出后將從管道中移

17、走，其它讀進程都不能再讀到這些數(shù)據(jù)。管道提供了簡單的流控制機制，進程試圖讀空管道時，在有數(shù)據(jù)寫入管道前，進程將一直阻塞。同樣地，管道已經(jīng)滿時，進程再試圖寫管道，在其它進程從管道中移走數(shù)據(jù)之前，寫進程將一直阻塞。Linux中管道是通過空文件來實現(xiàn)。管道有三種：普通管道：有兩個限制：一是只支持半雙工通信方式，即只能單向傳輸；二是只能在父子進程之間使用；流管道：去除第一個限制，支持雙向傳輸；命名管道：去除第二個限制，可以在不相關(guān)進程之間進行通信。2 .信號量信號量是一個計數(shù)器，可以用來控制多個進程對共享資源的訪問。它常作為一種鎖機制，防止某進程正在訪問共享資源時，其它進程也訪問該資源。因此，主要作為

18、進程間以及同一進程內(nèi)不同線程之間的同步手段。3 .消息隊列消息隊列克服了信號傳遞信息少、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點。4 .信號信號是一種比較復(fù)雜的通信方式，用于通知接收進程某個事件已經(jīng)發(fā)生。5 .共享內(nèi)存共享內(nèi)存就是映射一段能被其它進程所訪問的內(nèi)存，這段共享內(nèi)存由一個進程創(chuàng)建，但多個進程都可以訪問。共享內(nèi)存是最快的IPC方式，它是針對其它進程間通信方式運行效率低而專門設(shè)計的。它往往與其它通信機制（如信號量）配合使用，來實現(xiàn)進程間的同步和通信。6 .套接字套接字也是一種進程間通信機制，與其它通信機制不同的是，它可用于不同機器間的進程通信。經(jīng)典同步問題生產(chǎn)者和消費者問題前面已

19、經(jīng)討論過。1 .讀者-寫者問題允許多個進程同時對數(shù)據(jù)進行讀操作，但是不允許讀和寫以及寫和寫操作同時發(fā)生。一個整型變量count記錄在對數(shù)據(jù)進行讀操作的進程數(shù)量，一個互斥量count_mutex用于對count加鎖，一個互斥量data_mutex用于對讀寫的數(shù)據(jù)加鎖。typedefintsemaphore;semaphorecount_mutex=1;semaphoredata_mutex=1;intcount=0;voidreader()while(TRUE)down(count_mutex);count+;if(count=1)down(data_mutex);/第一個讀者需要對數(shù)據(jù)進行加鎖

20、，防止寫進程訪問up(count_mutex);read();down(count_mutex);count-;if(count=0)up(data_mutex);up(count_mutex);voidwriter()while(TRUE)down(data_mutex);write();up(data_mutex);2 .哲學家進餐問題五個哲學家圍著一張圓周，每個哲學家面前放著飯。哲學家的生活有兩種交替活動：吃飯以及思考。當一個哲學家吃飯時，需要先一根一根拿起左右兩邊的筷子。下面是一種錯誤的解法，考慮到如果每個哲學家同時拿起左手邊的筷子，那么就無法拿起右手邊的筷子，造成死鎖。defineN

21、5defineLEFT(i+N-1)%NdefineRIGHT(i+N)%Ntypedefintsemaphore;semaphorechopstickN;voidphilosopher(inti)while(TURE)think();down(chopstickLEFTi);down(chopstickRIGHTi);eat();up(chopstickRIGHTi);up(chopstickLEFTi);方法是引入一個為了防止死鎖的發(fā)生，可以加一點限制，只允許同時拿起左右兩邊的筷子,互斥量，對拿起兩個筷子的那段代碼加鎖。semaphoremutex=1;voidphilosopher(in

22、ti)while(TURE)think();down(mutex);down(chopstickLEFTi);down(chopstickRIGHTi);up(mutex);eat();down(mutex);up(chopstickRIGHTi);up(chopstickLEFTi);up(mutex);)第三章死鎖死鎖的條件FigureResourci?2Llociiiongraphs(aHol-dinparesource.(b)kequeUirgaresource.(c)Deadlock.1 .互斥2 .請求與保持：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。3 .不可搶占4 .

23、環(huán)路等待死鎖的處理方法1 .鴕鳥策略把頭埋在沙子里，假裝根本沒發(fā)生問題。這種策略不可取。2 .死鎖預(yù)防在程序運行之前預(yù)防發(fā)生死鎖。2.1 破壞互斥條件例如假脫機打印機技術(shù)允許若干個進程同時輸出，唯一真正請求物理打印機的進程是打印機守護進程。2.2 破壞請求與保持條件一種實現(xiàn)方式是規(guī)定所有進程在開始執(zhí)行前請求所需要的全部資源。2.3 破壞不可搶占條件2.4 破壞環(huán)路等待給資源統(tǒng)一編號，進程只能按編號順序來請求資源。3 .死鎖避免在程序運行時避免發(fā)生死鎖。3.1 安全狀態(tài)HasMaxHasMaxHasMaxHasHasMax（可仍）Figure6-9.Demonstradondiacthestat

24、ein(a)Fsafe.圖a的第二列has表示已擁有的資源數(shù)，第三列max表示總共需要的資源數(shù)，free表示還有可以使用的資源數(shù)。從圖a開始出發(fā)，先讓B擁有所需的所有資源，運行結(jié)束后釋放B,此時free變?yōu)?;接著以同樣的方式運行C和A,使得所有進程都能成功運行，因此可以稱圖a所示的狀態(tài)時安全的。定義：如果沒有死鎖發(fā)生，并且即使所有進程突然請求對資源的最大需求，也仍然存在某種調(diào)度次序能夠使得每一個進程運行完畢，則稱該狀態(tài)是安全的。3.2 單個資源的銀行家算法一個小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度，算法要做的是判斷對請求的滿足是否會進入不安全狀態(tài)，如果是，就拒絕請求；否則予以分

25、配。也)(c)Figure6-1LThreeresourceallocationstateK(a)Safe.(b)Safe.(c)Unsafe.上圖c為不安全狀態(tài)，因此算法會拒絕之前的請求，從而避免進入圖c中的狀態(tài)。3.3 多個資源的銀行家算法ResourcesassignedResourcesstillassignedFigure6-12.Thebankersalgorithmwithmultipleresources.上圖中有五個進程，四個資源。左邊的圖表示已經(jīng)分配的資源，右邊的圖表示還需要分配的資源。最右邊的E、P以及A分別表示：總資源、已分配資源以及可用資源，注意這三個為向量，而不是具

26、體數(shù)值，例如A=(1020),表示4個資源分別還剩下1/0/2/0。檢查一個狀態(tài)是否安全的算法如下：查找右邊的矩陣是否存在一行小于等于向量Ao如果不存在這樣的行，那么系統(tǒng)將會發(fā)生死鎖，狀態(tài)是不安全的。假若找到這樣一行，將該進程標記為終止，并將其已分配資源加到A中。重復(fù)以上兩步，直到所有進程都標記為終止，則狀態(tài)時安全的。4,死鎖檢測與死鎖恢復(fù)不試圖組織死鎖，而是當檢測到死鎖發(fā)生時，采取措施進行恢復(fù)。4.1死鎖檢測算法死鎖檢測的基本思想是，如果一個進程所請求的資源能夠被滿足，那么就讓它執(zhí)行，釋放它擁有的所有資源，然后讓其它能滿足條件的進程執(zhí)行。Requestmatrix2001R=10102100

27、CurrentallocationmatrixOO1OC=20010120上圖中，有三個進程四個資源，每個數(shù)據(jù)代表的含義如下：E向量：資源總量A向量：資源剩余量C矩陣：每個進程所擁有的資源數(shù)量，每一行都代表一個進程擁有資源的數(shù)量R矩陣：每個進程請求的資源數(shù)量進程P1和P2所請求的資源都得不到滿足，只有進程P3可以，讓P3執(zhí)行，之后釋放P3擁有的資源，此時A=(2220)。P1可以執(zhí)行，執(zhí)行后釋放P1擁有的資源，A=(4222) ,P2也可以執(zhí)行。所有進程都可以順利執(zhí)行，沒有死鎖。算法總結(jié)如下：每個進程最開始時都不被標記，執(zhí)行過程有可能被標記。當算法結(jié)束時，任何沒有被標記的進程都是死鎖進程。尋找

28、一個沒有標記的進程Pi,它所請求的資源小于等于Ao如果找到了這樣一個進程，那么將C矩陣的第i行向量加到A中，標記該進程，并轉(zhuǎn)回。如果有沒有這樣一個進程，算法終止。4.2死鎖恢復(fù)利用搶占恢復(fù)殺死進程第四章存儲器管理虛擬內(nèi)存頁。這些頁每個程序擁有自己的地址空間，這個地址空間被分割成多個塊，每一塊稱為被映射到物理內(nèi)存，但不需要映射到連續(xù)的物理內(nèi)存，也不需要所有頁都必須在物理內(nèi)存中。當程序引用到一部分在物理內(nèi)存中的地址空間時，由硬件立即執(zhí)行必要的映射。當程序引用到一部分不在物理內(nèi)存中的地址空間時，由操作系統(tǒng)負責將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令。分頁與分段1 .分頁用戶程序的地址空間被劃分為

29、若干固定大小的區(qū)域，稱為“頁”。相應(yīng)地，內(nèi)存空間分成若干個物理塊，頁和塊的大小相等。可將用戶程序的任一頁放在內(nèi)存的任一塊中，實現(xiàn)了離散分配，由一個頁表來維護它們之間的映射關(guān)系。2 .分段上圖為一個編譯器在編譯過程中建立的多個表，有4個表是動態(tài)增長的，如果使用分頁系統(tǒng)的一維地址空間，動態(tài)遞增的特點會導(dǎo)致覆蓋問題的出現(xiàn)。分段的做法是把每個表分成段，一個段構(gòu)成一個獨立的地址空間。每個段的長度可以不同,可以動態(tài)改變。每個段都需要程序員來劃分。3 .段頁式用分段方法來分配和管理虛擬存儲器。程序的地址空間按邏輯單位分成基本獨立的段，而每一段有自己的段名，再把每段分成固定大小的若干頁。用分頁方法來分配和管理

30、實存。即把整個主存分成與上述頁大小相等的存儲塊，可裝入作業(yè)的任何一頁。程序?qū)?nèi)存的調(diào)入或調(diào)出是按頁進行的。但它又可按段實現(xiàn)共享和保護。4 .分頁與分段區(qū)別 對程序員的透明性：分頁透明，但是分段需要程序員顯示劃分每個段。 地址空間的維度：分頁是一維地址空間，分段是二維的。 大小是否可以改變：頁的大小不可變，段的大小可以動態(tài)改變。 出現(xiàn)的原因：分頁主要用于實現(xiàn)虛擬內(nèi)存，從而獲得更大的地址空間；分段主要是為了使程序和數(shù)據(jù)可以被劃分為邏輯上獨立的地址空間并且有助于共享和保護。頁面置換算法在程序運行過程中，若其所要訪問的頁面不在內(nèi)存而需要把它們調(diào)入內(nèi)存，但是內(nèi)存已無空閑空間時，系統(tǒng)必須從內(nèi)存中調(diào)出一個頁面到磁盤對換區(qū)中，并且將程序所需要的頁面調(diào)入內(nèi)存中。頁面置換算法的主要目標是使頁面置換頻率最低（也可以說缺頁率最低）。1 .最佳（Optimal）所選擇的被換出的頁面將是最長時間內(nèi)不再被訪問，通?？梢员ＷC獲得最低的缺頁率。是一種理論上的算法，因為無法知道一個頁面多長時間會被再訪問到。舉例：一個系統(tǒng)為某進程分配了三個物理塊，并有如下頁面引用序列：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,