操作系統(tǒng)2002--存儲(chǔ)管理(1)

1、基本概念基本概念單個(gè)分區(qū)的存儲(chǔ)管理單個(gè)分區(qū)的存儲(chǔ)管理多個(gè)分區(qū)的存儲(chǔ)管理多個(gè)分區(qū)的存儲(chǔ)管理分頁式存儲(chǔ)管理分頁式存儲(chǔ)管理分段式存儲(chǔ)管理分段式存儲(chǔ)管理虛擬存儲(chǔ)管理虛擬存儲(chǔ)管理一、基本概念內(nèi)存儲(chǔ)器內(nèi)存儲(chǔ)器（簡(jiǎn)稱內(nèi)存、主存、物理存儲(chǔ)器）（簡(jiǎn)稱內(nèi)存、主存、物理存儲(chǔ)器） 處理機(jī)能直接訪問的存儲(chǔ)器。用來存放系統(tǒng)處理機(jī)能直接訪問的存儲(chǔ)器。用來存放系統(tǒng)和用戶的程序和數(shù)據(jù)，其特點(diǎn)是存取速度快，存和用戶的程序和數(shù)據(jù)，其特點(diǎn)是存取速度快，存儲(chǔ)方式是以新?lián)Q舊，斷電信息丟失。儲(chǔ)方式是以新?lián)Q舊，斷電信息丟失。外存儲(chǔ)器外存儲(chǔ)器（簡(jiǎn)稱外存、輔助存儲(chǔ)器）（簡(jiǎn)稱外存、輔助存儲(chǔ)器） 處理機(jī)不能直接訪問的存儲(chǔ)器。用來存放用處理機(jī)不能直接

2、訪問的存儲(chǔ)器。用來存放用戶的各種信息，存取速度相對(duì)內(nèi)存而言要慢得多戶的各種信息，存取速度相對(duì)內(nèi)存而言要慢得多，但它可用來長(zhǎng)期保存用戶信息。在文件系統(tǒng)中，但它可用來長(zhǎng)期保存用戶信息。在文件系統(tǒng)中介紹。介紹。存儲(chǔ)器分類存儲(chǔ)器分類指導(dǎo)思想：利用輔存（如磁盤、磁帶等）提指導(dǎo)思想：利用輔存（如磁盤、磁帶等）提供的大容量存儲(chǔ)空間，存放準(zhǔn)備運(yùn)行的程序供的大容量存儲(chǔ)空間，存放準(zhǔn)備運(yùn)行的程序和數(shù)據(jù)，當(dāng)需要時(shí)或主存空間允許時(shí)，隨時(shí)和數(shù)據(jù)，當(dāng)需要時(shí)或主存空間允許時(shí)，隨時(shí)將它們讀入主存儲(chǔ)器。將它們讀入主存儲(chǔ)器。信息的二級(jí)存儲(chǔ)信息的二級(jí)存儲(chǔ)CPU主主 存存輔輔 存存磁磁 盤盤磁磁 帶帶存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)通

3、用寄存器通用寄存器高速緩存高速緩存主存主存硬盤硬盤大容量存儲(chǔ)器大容量存儲(chǔ)器存儲(chǔ)容量增大存儲(chǔ)容量增大單位容量的價(jià)格增加單位容量的價(jià)格增加存儲(chǔ)管理存儲(chǔ)管理內(nèi)存的物理組織內(nèi)存的物理組織物理地址物理地址： 把內(nèi)存分成若干個(gè)大小相把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)單元給等的存儲(chǔ)單元，每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為內(nèi)一個(gè)編號(hào)，這個(gè)編號(hào)稱為內(nèi)存地址（物理地址、絕對(duì)地存地址（物理地址、絕對(duì)地址、實(shí)地址），存儲(chǔ)單元占址、實(shí)地址），存儲(chǔ)單元占8位，稱作字節(jié)（位，稱作字節(jié)（byte）。）。物理地址空間物理地址空間： 物理地址的集合稱為物理物理地址的集合稱為物理地址空間（主存地址空間）地址空間（主存地址空間）

4、，它是一個(gè)一維的線性空間，它是一個(gè)一維的線性空間。程序的邏輯結(jié)構(gòu)程序的邏輯結(jié)構(gòu)程序地址程序地址：用戶編程序時(shí)所用的地址（或稱邏輯地址：用戶編程序時(shí)所用的地址（或稱邏輯地址 、虛地址虛地址 ），基本單位可與內(nèi)存的基本單位相同，也可以），基本單位可與內(nèi)存的基本單位相同，也可以不相同。不相同。程序地址空間程序地址空間（邏輯地址空間、虛地址空間）（邏輯地址空間、虛地址空間）: :用戶的程用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從序地址的集合稱為邏輯地址空間，它的編址總是從0 0開始開始的，可以是一維線性空間，也可以是多維空間。的，可以是一維線性空間，也可以是多維空間。存儲(chǔ)管理的功能存儲(chǔ)管理的

5、功能主存空間的分配和回收主存空間的分配和回收：一個(gè)有效的存儲(chǔ)分配機(jī)制，應(yīng)在用：一個(gè)有效的存儲(chǔ)分配機(jī)制，應(yīng)在用戶提出需求時(shí)提供快速響應(yīng)，為之分配相應(yīng)的的存儲(chǔ)空間；戶提出需求時(shí)提供快速響應(yīng)，為之分配相應(yīng)的的存儲(chǔ)空間；在用戶作業(yè)不再需要它時(shí)，及時(shí)回收，以供其它用戶使用在用戶作業(yè)不再需要它時(shí)，及時(shí)回收，以供其它用戶使用地址轉(zhuǎn)換地址轉(zhuǎn)換：存儲(chǔ)管理必須能夠配合硬件完成用戶程序中所使：存儲(chǔ)管理必須能夠配合硬件完成用戶程序中所使用的邏輯地址到程序?qū)嶋H執(zhí)行時(shí)所使用的物理地址之間的轉(zhuǎn)用的邏輯地址到程序?qū)嶋H執(zhí)行時(shí)所使用的物理地址之間的轉(zhuǎn)換工作，以保證處理器的正確執(zhí)行。換工作，以保證處理器的正確執(zhí)行。主存空間的擴(kuò)充主

6、存空間的擴(kuò)充：借助虛擬存儲(chǔ)技術(shù)或其它交換技術(shù)，達(dá)到：借助虛擬存儲(chǔ)技術(shù)或其它交換技術(shù)，達(dá)到在邏輯上擴(kuò)充主存容量，亦即為用戶提供主存物理空間大得在邏輯上擴(kuò)充主存容量，亦即為用戶提供主存物理空間大得多的地址空間，以至使得用戶感覺他的作業(yè)是在這樣一個(gè)大多的地址空間，以至使得用戶感覺他的作業(yè)是在這樣一個(gè)大的存儲(chǔ)器中運(yùn)行。的存儲(chǔ)器中運(yùn)行。主存空間的共享和保護(hù)主存空間的共享和保護(hù)：共享主存指的是多個(gè)作業(yè)共同使用：共享主存指的是多個(gè)作業(yè)共同使用主存中的某個(gè)區(qū)域，以提高主存利用率。主存的保護(hù)指的是主存中的某個(gè)區(qū)域，以提高主存利用率。主存的保護(hù)指的是確保多道程序都能在各自分配到的主存區(qū)域內(nèi)工作，互不干確保多道程序

7、都能在各自分配到的主存區(qū)域內(nèi)工作，互不干擾，防止一道程序破壞其它作業(yè)的信息，特別要防止破壞系擾，防止一道程序破壞其它作業(yè)的信息，特別要防止破壞系統(tǒng)程序。統(tǒng)程序。重定位重定位絕對(duì)地址絕對(duì)地址：主存中每個(gè)物理存儲(chǔ)單元的編號(hào)稱為：主存中每個(gè)物理存儲(chǔ)單元的編號(hào)稱為“絕對(duì)地址絕對(duì)地址”或或“物理地址物理地址”，它們可以被存儲(chǔ)控制部件所識(shí)別。，它們可以被存儲(chǔ)控制部件所識(shí)別。邏輯地址邏輯地址：源程序經(jīng)編譯后得到的目標(biāo)程序總是以：源程序經(jīng)編譯后得到的目標(biāo)程序總是以0 0為起始地為起始地址，其它地址都是以此順序安排下來，都是相對(duì)于址，其它地址都是以此順序安排下來，都是相對(duì)于0 0這個(gè)起始這個(gè)起始地址的，這種地址

8、稱為地址的，這種地址稱為“邏輯地址邏輯地址”。名空間名空間：我們把再一個(gè)用高級(jí)語言編寫得源程序中由程序員建：我們把再一個(gè)用高級(jí)語言編寫得源程序中由程序員建立得符號(hào)名字空間稱為立得符號(hào)名字空間稱為“名空間名空間”。地址空間地址空間：把源程序經(jīng)編譯后得到的目標(biāo)程序所限定的地址范：把源程序經(jīng)編譯后得到的目標(biāo)程序所限定的地址范圍稱為這個(gè)程序的圍稱為這個(gè)程序的“地址空間地址空間”。存儲(chǔ)空間存儲(chǔ)空間：主存中一系列物理單元的集合稱為存儲(chǔ)空間。：主存中一系列物理單元的集合稱為存儲(chǔ)空間。顯然，地址空間是邏輯地址的集合，存儲(chǔ)空間是絕對(duì)地址或物顯然，地址空間是邏輯地址的集合，存儲(chǔ)空間是絕對(duì)地址或物理地址的集合，一個(gè)

9、是邏輯的概念，一個(gè)是物理的實(shí)體。理地址的集合，一個(gè)是邏輯的概念，一個(gè)是物理的實(shí)體。重定位重定位：一個(gè)作業(yè)的邏輯地址向物理地址的轉(zhuǎn)換，：一個(gè)作業(yè)的邏輯地址向物理地址的轉(zhuǎn)換，稱為重定位（也稱為地址映射）。稱為重定位（也稱為地址映射）。編程或編譯時(shí)確定地址映射關(guān)系編程或編譯時(shí)確定地址映射關(guān)系：編程時(shí)確定虛：編程時(shí)確定虛實(shí)地址的關(guān)系是指在用機(jī)器指令編程時(shí)，程序?qū)嵉刂返年P(guān)系是指在用機(jī)器指令編程時(shí)，程序員直接按物理內(nèi)存地址編程，這種程序在系統(tǒng)中員直接按物理內(nèi)存地址編程，這種程序在系統(tǒng)中是不能做任何移動(dòng)的，否則就會(huì)出錯(cuò)。是不能做任何移動(dòng)的，否則就會(huì)出錯(cuò)。靜態(tài)重定位靜態(tài)重定位： 地址變換過程發(fā)生在程序裝入時(shí)，

10、地址變換過程發(fā)生在程序裝入時(shí)，且由重定位裝入程序完成。采用這種重定位方式且由重定位裝入程序完成。采用這種重定位方式時(shí)，系統(tǒng)的存儲(chǔ)分配只能采用靜態(tài)分配策略。時(shí)，系統(tǒng)的存儲(chǔ)分配只能采用靜態(tài)分配策略。動(dòng)態(tài)重定位動(dòng)態(tài)重定位：地址變換過程發(fā)生在程序執(zhí)行過程：地址變換過程發(fā)生在程序執(zhí)行過程中訪問每條指令和數(shù)據(jù)時(shí)連續(xù)進(jìn)行，且由硬件重中訪問每條指令和數(shù)據(jù)時(shí)連續(xù)進(jìn)行，且由硬件重定位機(jī)構(gòu)來實(shí)現(xiàn)。采用這種重定位方式時(shí)，系統(tǒng)定位機(jī)構(gòu)來實(shí)現(xiàn)。采用這種重定位方式時(shí)，系統(tǒng)的存儲(chǔ)分配可以采用動(dòng)態(tài)分配策略。的存儲(chǔ)分配可以采用動(dòng)態(tài)分配策略。LOAD 1, 50012345LOAD 1, 550012345010050070005

11、000510055005700靜態(tài)重定位靜態(tài)重定位LOAD 1, 5001234501005005007005005000LOAD 1, 5001234505000510055005700+動(dòng)態(tài)重定位動(dòng)態(tài)重定位在裝入作業(yè)時(shí)，不進(jìn)行地址轉(zhuǎn)換，而是直接把作在裝入作業(yè)時(shí)，不進(jìn)行地址轉(zhuǎn)換，而是直接把作業(yè)裝入到分配的主存區(qū)域中。在作業(yè)執(zhí)行過程中，業(yè)裝入到分配的主存區(qū)域中。在作業(yè)執(zhí)行過程中，每當(dāng)執(zhí)行一條指令時(shí)，都由硬件的地址轉(zhuǎn)換機(jī)構(gòu)每當(dāng)執(zhí)行一條指令時(shí)，都由硬件的地址轉(zhuǎn)換機(jī)構(gòu)將指令中的邏輯地址轉(zhuǎn)換成物理地址，地址轉(zhuǎn)換將指令中的邏輯地址轉(zhuǎn)換成物理地址，地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行時(shí)完成的。工作是在作業(yè)執(zhí)行時(shí)完成的

12、。存儲(chǔ)保護(hù)存儲(chǔ)保護(hù) 在多道程序設(shè)計(jì)的環(huán)境下，系統(tǒng)中有系統(tǒng)在多道程序設(shè)計(jì)的環(huán)境下，系統(tǒng)中有系統(tǒng)程序和多個(gè)用戶程序同時(shí)存在，如何保證用戶程序和多個(gè)用戶程序同時(shí)存在，如何保證用戶程序不破壞系統(tǒng)程序，用戶程序之間不相互干程序不破壞系統(tǒng)程序，用戶程序之間不相互干擾？這就是存儲(chǔ)保護(hù)所要解決的問題擾？這就是存儲(chǔ)保護(hù)所要解決的問題常用的存儲(chǔ)保護(hù)有兩種：常用的存儲(chǔ)保護(hù)有兩種： 上、下界寄存器保護(hù)上、下界寄存器保護(hù) 基址、限長(zhǎng)寄存器保護(hù)基址、限長(zhǎng)寄存器保護(hù)上下界寄存器保護(hù)上下界寄存器保護(hù)下界寄存器下界寄存器 存放程序裝入內(nèi)存后的開始地址（首址）存放程序裝入內(nèi)存后的開始地址（首址）上界寄存器上界寄存器 存放程序裝入

13、內(nèi)存后的末地址存放程序裝入內(nèi)存后的末地址判別式：判別式：下界寄存器下界寄存器 物理地址物理地址 上界寄存器上界寄存器例題：例題： 有一程序裝入內(nèi)存的首地址是有一程序裝入內(nèi)存的首地址是500500，末地址是，末地址是15001500，訪問內(nèi)存的邏輯地址是，訪問內(nèi)存的邏輯地址是500500、345345、10001000。 下界寄存器：下界寄存器：500500 上界寄存器：上界寄存器：15001500 邏輯地址裝入內(nèi)存的首地邏輯地址裝入內(nèi)存的首地 物理地址物理地址1 1、500500500 500 1000 500 1000 1000 500 1000 150015002 2、345345500

14、500 845 500 845 845 500 845 150015003 3、10001000500 500 1500 500 1500 1500 500 1500 15001500二、一個(gè)分區(qū)的存儲(chǔ)管理二、一個(gè)分區(qū)的存儲(chǔ)管理采用靜態(tài)分配和靜態(tài)重定位方式。采用靜態(tài)分配和靜態(tài)重定位方式。OS常住部分常住部分用戶程序用戶程序空閑區(qū)空閑區(qū)fence覆蓋覆蓋 所謂覆蓋是指一個(gè)作業(yè)的若干程序段所謂覆蓋是指一個(gè)作業(yè)的若干程序段（或數(shù)據(jù)段）間或幾個(gè)作業(yè)的某些部分間共（或數(shù)據(jù)段）間或幾個(gè)作業(yè)的某些部分間共享某主存空間。覆蓋技術(shù)要求程序員提供一享某主存空間。覆蓋技術(shù)要求程序員提供一個(gè)清楚的覆蓋結(jié)構(gòu)，即程序員要

15、把一個(gè)程序個(gè)清楚的覆蓋結(jié)構(gòu)，即程序員要把一個(gè)程序劃分成不同的程序段，并規(guī)定好它們的執(zhí)行劃分成不同的程序段，并規(guī)定好它們的執(zhí)行和覆蓋的次序。操作系統(tǒng)則根據(jù)程序員提供和覆蓋的次序。操作系統(tǒng)則根據(jù)程序員提供的覆蓋結(jié)構(gòu)，完成程序段之間的覆蓋。的覆蓋結(jié)構(gòu)，完成程序段之間的覆蓋。A（20k）C（30k）F（30k）程序結(jié)構(gòu)程序結(jié)構(gòu)B（50k）D（20k）E（40k）020k50k70k90k100kABCDEF020k20k70k70k100k20k50k50k70k50k90k程序的覆蓋結(jié)構(gòu)程序的覆蓋結(jié)構(gòu)交換交換 交換方式是由操作系統(tǒng)把那些在內(nèi)存中處于等交換方式是由操作系統(tǒng)把那些在內(nèi)存中處于等待狀態(tài)的進(jìn)

16、程換出內(nèi)存，而把那些處于就緒狀態(tài)的待狀態(tài)的進(jìn)程換出內(nèi)存，而把那些處于就緒狀態(tài)的進(jìn)程換入內(nèi)存進(jìn)程換入內(nèi)存操作系統(tǒng)操作系統(tǒng)用戶區(qū)用戶區(qū)進(jìn)程進(jìn)程P1進(jìn)程進(jìn)程P2換出換出換入換入三、多個(gè)分區(qū)的存儲(chǔ)管理三、多個(gè)分區(qū)的存儲(chǔ)管理固定分區(qū)固定分區(qū) 固定分區(qū)管理方式是預(yù)先把可分配的主存固定分區(qū)管理方式是預(yù)先把可分配的主存空間分割成若干個(gè)連續(xù)區(qū)域，每個(gè)區(qū)域的大小空間分割成若干個(gè)連續(xù)區(qū)域，每個(gè)區(qū)域的大小可以相同，也可以不同。一旦分好，則每個(gè)分可以相同，也可以不同。一旦分好，則每個(gè)分區(qū)的大小固定，不再變化，且分區(qū)的個(gè)數(shù)也不區(qū)的大小固定，不再變化，且分區(qū)的個(gè)數(shù)也不再改變。再改變。q 固定分區(qū)固定分區(qū)q 可變分區(qū)可變分區(qū)

17、q 可重定位分區(qū)可重定位分區(qū)作作業(yè)業(yè)1作作業(yè)業(yè)2作作業(yè)業(yè)3操作系統(tǒng)操作系統(tǒng)分區(qū)分區(qū)1分區(qū)分區(qū)2分區(qū)分區(qū)3CPU當(dāng)前運(yùn)行作當(dāng)前運(yùn)行作業(yè)所在分區(qū)業(yè)所在分區(qū)2bc上限寄存器上限寄存器下限寄存器下限寄存器abcdOS常住部分常住部分J1J2J3 032k48k16k80k144k256k32k64k112k 分分區(qū)區(qū)號(hào)號(hào) 起起始始地地址址 長(zhǎng)長(zhǎng)度度 狀狀態(tài)態(tài) 作作業(yè)業(yè)名名 1 32k 16k 1 J1 2 48k 32k 1 J2 3 80k 64k 1 J3 4 144k 112k 0 固定分區(qū)順序分配的算法流程是是查看分區(qū)表查看分區(qū)表的第的第I個(gè)表目個(gè)表目已分配？已分配？分區(qū)長(zhǎng)度分區(qū)長(zhǎng)度xkI為分

18、區(qū)表最為分區(qū)表最后一個(gè)表目后一個(gè)表目置表目中置表目中狀態(tài)位為狀態(tài)位為1裝入作業(yè)裝入作業(yè)J無法分配，作業(yè)無法分配，作業(yè)J等待等待是是作業(yè)作業(yè)J申請(qǐng)申請(qǐng)xk主存主存否否是是否否I = 0I = I + 1否否地址轉(zhuǎn)換：可采用靜態(tài)重定位方式地址轉(zhuǎn)換：可采用靜態(tài)重定位方式存儲(chǔ)保護(hù)措施：存儲(chǔ)保護(hù)措施：CPUCPU 下界下界上界上界內(nèi)存內(nèi)存尋址錯(cuò)尋址錯(cuò)尋址錯(cuò)尋址錯(cuò)地址地址是是是是否否否否采用固定分區(qū)方式的問題：主存利用率不高。改采用固定分區(qū)方式的問題：主存利用率不高。改進(jìn)的方法：進(jìn)的方法：劃分分區(qū)時(shí)按分區(qū)的大小順序排列。劃分分區(qū)時(shí)按分區(qū)的大小順序排列。根據(jù)經(jīng)常出現(xiàn)的作業(yè)的大小和頻率劃分分區(qū)。根據(jù)經(jīng)常出現(xiàn)的

19、作業(yè)的大小和頻率劃分分區(qū)。按作業(yè)對(duì)主存的需求量排成多個(gè)作業(yè)。按作業(yè)對(duì)主存的需求量排成多個(gè)作業(yè)。操作系統(tǒng)操作系統(tǒng)分區(qū)分區(qū)1分區(qū)分區(qū)2分區(qū)分區(qū)3作業(yè)隊(duì)列作業(yè)隊(duì)列2作業(yè)隊(duì)列作業(yè)隊(duì)列1作業(yè)隊(duì)列作業(yè)隊(duì)列3L1L2L3可變分區(qū)可變分區(qū) 所謂可變分區(qū)是指，系統(tǒng)并不預(yù)先所謂可變分區(qū)是指，系統(tǒng)并不預(yù)先劃分幾個(gè)固定分區(qū)。分區(qū)的建立是劃分幾個(gè)固定分區(qū)。分區(qū)的建立是在在作作業(yè)的處理過程中進(jìn)行的，其大小隨作業(yè)業(yè)的處理過程中進(jìn)行的，其大小隨作業(yè)的主存需求量而決定。在這種管理方式的主存需求量而決定。在這種管理方式下，系統(tǒng)中任一時(shí)刻分區(qū)的大小及個(gè)數(shù)，下，系統(tǒng)中任一時(shí)刻分區(qū)的大小及個(gè)數(shù)，都是不固定而可改變的。都是不固定而可改變

20、的?？勺兛勺兎謪^(qū)管理的數(shù)據(jù)結(jié)構(gòu)分區(qū)管理的數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)操作系統(tǒng)J1J3400k01000k2000k2300k2560k始始址址 長(zhǎng)長(zhǎng)度度 標(biāo)標(biāo)志志 400 600 J1 2000 300 J3 空空 始始址址 長(zhǎng)長(zhǎng)度度 標(biāo)標(biāo)志志 1000 1000 未未分分配配 2300 260 未未分分配配 空空 已分配區(qū)表已分配區(qū)表空閑區(qū)表空閑區(qū)表分區(qū)的分配算法分區(qū)的分配算法最優(yōu)適應(yīng)算法最優(yōu)適應(yīng)算法：將空閑分區(qū)按其存儲(chǔ)空間的大小，從?。簩⒖臻e分區(qū)按其存儲(chǔ)空間的大小，從小到大順序組成鏈。每次查找從鏈?zhǔn)组_始，第一個(gè)滿足要到大順序組成鏈。每次查找從鏈?zhǔn)组_始，第一個(gè)滿足要求的空閑分區(qū)將被分配求的空閑分區(qū)將被分

21、配最壞適應(yīng)算法最壞適應(yīng)算法：空閑分區(qū)按其空間大小，從大到小組成：空閑分區(qū)按其空間大小，從大到小組成鏈。每次查找從鏈?zhǔn)组_始，第一個(gè)滿足要求的空閑分區(qū)鏈。每次查找從鏈?zhǔn)组_始，第一個(gè)滿足要求的空閑分區(qū)將被分配將被分配最先適應(yīng)算法最先適應(yīng)算法：空閑分區(qū)按其在存儲(chǔ)空間中的地址，以：空閑分區(qū)按其在存儲(chǔ)空間中的地址，以遞增順序組成鏈。每次查找從鏈?zhǔn)组_始，第一個(gè)滿足要遞增順序組成鏈。每次查找從鏈?zhǔn)组_始，第一個(gè)滿足要求的空閑分區(qū)將被分配求的空閑分區(qū)將被分配下次適應(yīng)算法下次適應(yīng)算法：是最先適應(yīng)算法的一種改進(jìn)。空閑分區(qū)：是最先適應(yīng)算法的一種改進(jìn)?？臻e分區(qū)的鏈接順序同最先適應(yīng)算法，但它是一個(gè)循環(huán)鏈。每次的鏈接順序同最

22、先適應(yīng)算法，但它是一個(gè)循環(huán)鏈。每次為存儲(chǔ)請(qǐng)求查找合適的空閑分區(qū)時(shí)，總是從上次查找結(jié)為存儲(chǔ)請(qǐng)求查找合適的空閑分區(qū)時(shí)，總是從上次查找結(jié)束的地方開始。束的地方開始。空閑分區(qū)空閑分區(qū)1空閑分區(qū)空閑分區(qū)2free空閑分區(qū)空閑分區(qū)n按分區(qū)的大小從小到大鏈接按分區(qū)的大小從小到大鏈接空閑分區(qū)空閑分區(qū)1空閑分區(qū)空閑分區(qū)2free空閑分區(qū)空閑分區(qū)n按分區(qū)的大小從大到小鏈接按分區(qū)的大小從大到小鏈接最優(yōu)適應(yīng)算法最優(yōu)適應(yīng)算法最壞適應(yīng)算法最壞適應(yīng)算法空閑分區(qū)空閑分區(qū)1空閑分區(qū)空閑分區(qū)2free空閑分區(qū)空閑分區(qū)n按分區(qū)的地址從低到高鏈接按分區(qū)的地址從低到高鏈接空閑分區(qū)空閑分區(qū)1空閑分區(qū)空閑分區(qū)2free空閑分區(qū)空閑分區(qū)n按

23、分區(qū)的地址從低到高鏈接按分區(qū)的地址從低到高鏈接最先適應(yīng)算法最先適應(yīng)算法下次適應(yīng)算法下次適應(yīng)算法分區(qū)的回收分區(qū)的回收a 回收區(qū)下面回收區(qū)下面鄰接空閑區(qū)鄰接空閑區(qū)b 回 收 區(qū) 上回 收 區(qū) 上面面鄰接空閑區(qū)鄰接空閑區(qū)c 回收區(qū)上、回收區(qū)上、下鄰接空閑區(qū)下鄰接空閑區(qū)d 回收區(qū)不鄰回收區(qū)不鄰接任何空閑區(qū)接任何空閑區(qū)回收區(qū)回收區(qū)使用區(qū)使用區(qū)空閑區(qū)空閑區(qū)地址轉(zhuǎn)換地址轉(zhuǎn)換：一般可采用動(dòng)態(tài)重定位方式，基址寄：一般可采用動(dòng)態(tài)重定位方式，基址寄存器的內(nèi)容加上邏輯地址（相對(duì)地址）就可得到存器的內(nèi)容加上邏輯地址（相對(duì)地址）就可得到絕對(duì)地址（物理地址）。絕對(duì)地址（物理地址）。存儲(chǔ)保護(hù)存儲(chǔ)保護(hù)：將邏輯地址（相對(duì)地址）與

24、限長(zhǎng)寄存：將邏輯地址（相對(duì)地址）與限長(zhǎng)寄存器的內(nèi)容進(jìn)行比較，如邏輯地址（相對(duì)地址）大器的內(nèi)容進(jìn)行比較，如邏輯地址（相對(duì)地址）大于限長(zhǎng)寄存器的值，表明地址越界。于限長(zhǎng)寄存器的值，表明地址越界。 地址越界地址越界CPUCPU內(nèi)存內(nèi)存邏輯地址邏輯地址是是否否限長(zhǎng)限長(zhǎng)基址基址物理地址物理地址例題：在可變分區(qū)管理中，有那些分區(qū)分配算法？各有何優(yōu)缺點(diǎn)？例題：在可變分區(qū)管理中，有那些分區(qū)分配算法？各有何優(yōu)缺點(diǎn)？最優(yōu)適應(yīng)算法最優(yōu)適應(yīng)算法 空閑分區(qū)按空間大小的順序從小到大鏈接在一起。系統(tǒng)在查找空閑分區(qū)按空間大小的順序從小到大鏈接在一起。系統(tǒng)在查找空閑分區(qū)時(shí)，總是從最小的一個(gè)開始。其實(shí)質(zhì)是，在系統(tǒng)中尋找與空閑分區(qū)

25、時(shí)，總是從最小的一個(gè)開始。其實(shí)質(zhì)是，在系統(tǒng)中尋找與要求大小最接近的空閑分區(qū)。要求大小最接近的空閑分區(qū)。優(yōu)點(diǎn)：如果存在有在正好滿足所要求大小的空閑分區(qū)，則必然被選優(yōu)點(diǎn)：如果存在有在正好滿足所要求大小的空閑分區(qū)，則必然被選中，或者只對(duì)比要求稍大的空閑分區(qū)進(jìn)行劃分，而絕不會(huì)劃分一個(gè)中，或者只對(duì)比要求稍大的空閑分區(qū)進(jìn)行劃分，而絕不會(huì)劃分一個(gè)更大的空閑分區(qū)。更大的空閑分區(qū)。缺點(diǎn)：尋找一個(gè)較大空閑區(qū)時(shí)花費(fèi)的時(shí)間較多；回收時(shí)把回收的空缺點(diǎn)：尋找一個(gè)較大空閑區(qū)時(shí)花費(fèi)的時(shí)間較多；回收時(shí)把回收的空閑區(qū)插入到鏈中合適的位置較為費(fèi)時(shí)；系統(tǒng)中，小的空閑區(qū)較多。閑區(qū)插入到鏈中合適的位置較為費(fèi)時(shí)；系統(tǒng)中，小的空閑區(qū)較多。最

26、壞適應(yīng)算法最壞適應(yīng)算法 空閑分區(qū)按空間大小的順序從大到小鏈接在一起。系統(tǒng)在查找空閑分區(qū)按空間大小的順序從大到小鏈接在一起。系統(tǒng)在查找空閑分區(qū)時(shí)，總是從最大的一個(gè)開始。空閑分區(qū)時(shí)，總是從最大的一個(gè)開始。優(yōu)點(diǎn)：克服了最優(yōu)適應(yīng)算法留下許多小的碎片的不足優(yōu)點(diǎn)：克服了最優(yōu)適應(yīng)算法留下許多小的碎片的不足缺點(diǎn)：保留大的空閑區(qū)的可能性減小了，而且分區(qū)的回收也和最優(yōu)缺點(diǎn)：保留大的空閑區(qū)的可能性減小了，而且分區(qū)的回收也和最優(yōu)適應(yīng)算法一樣復(fù)雜。適應(yīng)算法一樣復(fù)雜。最先適應(yīng)算法最先適應(yīng)算法 空閑分區(qū)按其在內(nèi)存中位置的順序從低地址到高地址鏈接在一起，空閑分區(qū)按其在內(nèi)存中位置的順序從低地址到高地址鏈接在一起，即每個(gè)后繼空閑

27、區(qū)的起始地址總是比前面的大。系統(tǒng)在查找空閑分區(qū)即每個(gè)后繼空閑區(qū)的起始地址總是比前面的大。系統(tǒng)在查找空閑分區(qū)時(shí)，按照空閑區(qū)的鏈的順序，依次查詢，直到找到第一個(gè)滿足要求的時(shí)，按照空閑區(qū)的鏈的順序，依次查詢，直到找到第一個(gè)滿足要求的空閑區(qū)為止。其實(shí)質(zhì)是，盡可能利用存儲(chǔ)器的低地址部分，盡量保存空閑區(qū)為止。其實(shí)質(zhì)是，盡可能利用存儲(chǔ)器的低地址部分，盡量保存高地址部分的空閑區(qū)。高地址部分的空閑區(qū)。優(yōu)點(diǎn)：當(dāng)需要一個(gè)較大的分區(qū)時(shí)，容易得到滿足。優(yōu)點(diǎn)：當(dāng)需要一個(gè)較大的分區(qū)時(shí)，容易得到滿足。缺點(diǎn)：在回收一個(gè)分區(qū)時(shí)，需要花費(fèi)較多的時(shí)間查找鏈表，以確定插缺點(diǎn)：在回收一個(gè)分區(qū)時(shí)，需要花費(fèi)較多的時(shí)間查找鏈表，以確定插入位置

28、。入位置。下次適應(yīng)算法下次適應(yīng)算法 空閑分區(qū)按其在內(nèi)存中位置的順序從低地址到高地址鏈接在一起，空閑分區(qū)按其在內(nèi)存中位置的順序從低地址到高地址鏈接在一起，與最先適應(yīng)算法不同的是，每次查找都是從上次查找結(jié)束的位置開始。與最先適應(yīng)算法不同的是，每次查找都是從上次查找結(jié)束的位置開始。其實(shí)質(zhì)是，空閑分區(qū)可以比較均勻的分布在內(nèi)存中。其實(shí)質(zhì)是，空閑分區(qū)可以比較均勻的分布在內(nèi)存中。缺點(diǎn)：尋找一個(gè)較大空閑區(qū)時(shí)花費(fèi)的時(shí)間較多；回收時(shí)把回收的空閑缺點(diǎn)：尋找一個(gè)較大空閑區(qū)時(shí)花費(fèi)的時(shí)間較多；回收時(shí)把回收的空閑區(qū)插入到鏈中合適的位置較為費(fèi)時(shí)。區(qū)插入到鏈中合適的位置較為費(fèi)時(shí)。例題：對(duì)下圖所示的分區(qū)分配情況（其中，陰影部分表

29、示已占用例題：對(duì)下圖所示的分區(qū)分配情況（其中，陰影部分表示已占用分區(qū)，空白部分表示空閑分區(qū)），若要申請(qǐng)一塊分區(qū)，空白部分表示空閑分區(qū)），若要申請(qǐng)一塊40KB40KB的分區(qū)：的分區(qū)： 100KB100KB80KB10KB90KB50KB60KB100KB180KB190KB280KB330KB390KB20KB101KB410KB511KB 對(duì)于最優(yōu)適應(yīng)分配算法得到的空閑分區(qū)的首地對(duì)于最優(yōu)適應(yīng)分配算法得到的空閑分區(qū)的首地址是址是 ：A A、110KB B110KB B、190BK C190BK C、330BK D330BK D、410BK410BK 若要使被分配得到的空閑分區(qū)的首地址最大，若要使

30、被分配得到的空閑分區(qū)的首地址最大，則應(yīng)采取的分配策略是則應(yīng)采取的分配策略是 ：A A、最先適應(yīng)分配算法、最先適應(yīng)分配算法 B B、最優(yōu)適應(yīng)分配算法、最優(yōu)適應(yīng)分配算法C C、最壞適應(yīng)分配算法、最壞適應(yīng)分配算法D D、單一連續(xù)區(qū)的分配算法、單一連續(xù)區(qū)的分配算法100KB0KB100KB80KB10KB90KB50KB60KB100KB180KB190KB280KB330KB390KB20KB101KB410KB511KB60KBFREE80KB90KB101KB最優(yōu)適應(yīng)分配算法得到的空閑分區(qū)的首地址最優(yōu)適應(yīng)分配算法得到的空閑分區(qū)的首地址為為330KB 330KB 申請(qǐng)一塊申請(qǐng)一塊40KB40KB的

31、分區(qū)的分區(qū)60KBFREE80KB90KB101KB330KB100KB190KB410KB80KBFREE90KB60KB101KB100KB190KB330KB410KB101KBFREE90KB80KB60KB410KB190KB100KB330KB最優(yōu)適應(yīng)分配算最優(yōu)適應(yīng)分配算法的空閑分區(qū)鏈。法的空閑分區(qū)鏈。第一個(gè)滿足要求第一個(gè)滿足要求的空閑分區(qū)首地的空閑分區(qū)首地址為：址為：330BK最先適應(yīng)分配算最先適應(yīng)分配算法的空閑分區(qū)鏈。法的空閑分區(qū)鏈。第一個(gè)滿足要求第一個(gè)滿足要求的空閑分區(qū)首地的空閑分區(qū)首地址為：址為：100BK最壞適應(yīng)分配算最壞適應(yīng)分配算法的空閑分區(qū)鏈。法的空閑分區(qū)鏈。第一個(gè)滿

32、足要求第一個(gè)滿足要求的空閑分區(qū)首地的空閑分區(qū)首地址為：址為：410BK 可見，只有采用最壞分配算法時(shí)，得到可見，只有采用最壞分配算法時(shí)，得到的首地址最大，為的首地址最大，為410KB410KB。答案為。答案為C C。100KB0KB100KB80KB10KB90KB50KB60KB100KB180KB190KB280KB330KB390KB20KB101KB410KB511KB采用多重分區(qū)的管理方法能夠?qū)崿F(xiàn)主存的共享采用多重分區(qū)的管理方法能夠?qū)崿F(xiàn)主存的共享。 所謂多重分區(qū)技術(shù)指的是系統(tǒng)中設(shè)置了多對(duì)（一般不所謂多重分區(qū)技術(shù)指的是系統(tǒng)中設(shè)置了多對(duì)（一般不超過超過3 34 4對(duì)）界地址寄存器，并且在

33、為每個(gè)作業(yè)分配主存對(duì)）界地址寄存器，并且在為每個(gè)作業(yè)分配主存時(shí)，可按界地址寄存器對(duì)的個(gè)數(shù)分配多個(gè)不相鄰接的空閑時(shí)，可按界地址寄存器對(duì)的個(gè)數(shù)分配多個(gè)不相鄰接的空閑分區(qū)。分區(qū)。操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)A（0分區(qū)）分區(qū)）作業(yè)作業(yè)B（0分區(qū)）分區(qū)）作業(yè)作業(yè)C作業(yè)作業(yè)A（1分區(qū)）分區(qū)）作業(yè)作業(yè)B（1分區(qū)）分區(qū)）空閑區(qū)空閑區(qū)多重分區(qū)分配多重分區(qū)分配10002000下界下界上界上界0分區(qū)寄存器對(duì)分區(qū)寄存器對(duì)50005500下界下界上界上界1分區(qū)寄存器對(duì)分區(qū)寄存器對(duì) 在共享主存空間時(shí)，每個(gè)作業(yè)即可訪問自在共享主存空間時(shí)，每個(gè)作業(yè)即可訪問自己所在的分區(qū)，也可訪問公共區(qū)域。但應(yīng)注意，己所在的分區(qū)，也可訪問公共區(qū)域

34、。但應(yīng)注意，對(duì)公共區(qū)域的訪問是受限的。一般地說，使用對(duì)公共區(qū)域的訪問是受限的。一般地說，使用共享信息（即訪問公共區(qū)域）只能采用共享信息（即訪問公共區(qū)域）只能采用“讀讀”或或“執(zhí)行執(zhí)行”的方式。的方式。操作系統(tǒng)操作系統(tǒng)共享程序共享程序J1J2J3可重定位分區(qū)可重定位分區(qū) 為了消除外部零頭，進(jìn)一步提高主存的利用為了消除外部零頭，進(jìn)一步提高主存的利用率，定時(shí)的（或在主存空間緊張時(shí)）把主存中的率，定時(shí)的（或在主存空間緊張時(shí)）把主存中的作業(yè)作業(yè)“搬家搬家”，集中在主存的一端，另一端就將，集中在主存的一端，另一端就將產(chǎn)生一個(gè)較大的空閑區(qū)。這種技術(shù)稱為存儲(chǔ)器的產(chǎn)生一個(gè)較大的空閑區(qū)。這種技術(shù)稱為存儲(chǔ)器的“緊縮

35、緊縮”（或稱移動(dòng)）。采用了緊縮技術(shù)的多個(gè)（或稱移動(dòng)）。采用了緊縮技術(shù)的多個(gè)分區(qū)的管理方法就是可重定位分區(qū)管理方法。分區(qū)的管理方法就是可重定位分區(qū)管理方法。采用緊縮（移動(dòng)）技術(shù)時(shí)應(yīng)注意的問題：采用緊縮（移動(dòng)）技術(shù)時(shí)應(yīng)注意的問題：1 1、移動(dòng)會(huì)增加系統(tǒng)的開銷、移動(dòng)會(huì)增加系統(tǒng)的開銷2 2、移動(dòng)是有條件的、移動(dòng)是有條件的操作系統(tǒng)操作系統(tǒng)J1（200k）J2（100k）400kJ3（200k）300kJ4（400k）200k操作系統(tǒng)操作系統(tǒng)J1（200k）J2（100k）J3（200k）J4（400k）900k操作系統(tǒng)操作系統(tǒng)J1（200k）J2（100k）J3（200k）J4（400k）900kA 起

36、始分配起始分配B 移動(dòng)移動(dòng)600kD 移動(dòng)移動(dòng)200k操作系統(tǒng)操作系統(tǒng)J1（200k）J2（100k）J3（200k）J4（400k）900kC 移動(dòng)移動(dòng)400k采用移動(dòng)技術(shù)時(shí)應(yīng)盡量減少移動(dòng)的作業(yè)數(shù)和信采用移動(dòng)技術(shù)時(shí)應(yīng)盡量減少移動(dòng)的作業(yè)數(shù)和信息量。息量。一種可行的方法：改變作業(yè)裝入主存的方式一種可行的方法：改變作業(yè)裝入主存的方式操作系統(tǒng)操作系統(tǒng)J1J2J3J4空閑區(qū)空閑區(qū)操作系統(tǒng)操作系統(tǒng)J1J3J4J2空閑區(qū)空閑區(qū)A 一頭裝入一頭裝入B 兩頭裝入兩頭裝入 當(dāng)作業(yè)當(dāng)作業(yè)J1J1完成后，它所占的分區(qū)成為空閑區(qū)，這完成后，它所占的分區(qū)成為空閑區(qū)，這樣，主存中就有兩個(gè)空閑區(qū)。若有新作業(yè)樣，主存中就有兩

37、個(gè)空閑區(qū)。若有新作業(yè)J5J5進(jìn)入系統(tǒng)，進(jìn)入系統(tǒng)，要求的內(nèi)存容量大于任何一個(gè)空閑區(qū)，但不超過兩個(gè)要求的內(nèi)存容量大于任何一個(gè)空閑區(qū)，但不超過兩個(gè)空閑區(qū)之和。此時(shí)需移動(dòng)作業(yè)，以將兩個(gè)空閑區(qū)合并空閑區(qū)之和。此時(shí)需移動(dòng)作業(yè)，以將兩個(gè)空閑區(qū)合并為一個(gè)較大的空閑區(qū)。為一個(gè)較大的空閑區(qū)。操作系統(tǒng)操作系統(tǒng)空閑區(qū)空閑區(qū)J2J3J4空閑區(qū)空閑區(qū)操作系統(tǒng)操作系統(tǒng)空閑區(qū)空閑區(qū)J3J4J2空閑區(qū)空閑區(qū)A 一頭裝入一頭裝入B 兩頭裝入兩頭裝入向上移動(dòng)三個(gè)作業(yè)向上移動(dòng)三個(gè)作業(yè)向上移動(dòng)一個(gè)作業(yè)向上移動(dòng)一個(gè)作業(yè)四、頁式存儲(chǔ)管理四、頁式存儲(chǔ)管理1 1、問題的提出、問題的提出 分區(qū)存儲(chǔ)管理的主要問題是碎片問題。分區(qū)存儲(chǔ)管理的主要問題

38、是碎片問題。 在采用分區(qū)存儲(chǔ)管理的系統(tǒng)中，會(huì)形成一些非在采用分區(qū)存儲(chǔ)管理的系統(tǒng)中，會(huì)形成一些非常小的分區(qū)，最終這些非常小的分區(qū)不能被系統(tǒng)中常小的分區(qū)，最終這些非常小的分區(qū)不能被系統(tǒng)中的任何用戶（程序）利用而浪費(fèi)。的任何用戶（程序）利用而浪費(fèi)。 造成這樣問題的主要原因是用戶程序裝入內(nèi)存造成這樣問題的主要原因是用戶程序裝入內(nèi)存時(shí)是整體裝入的，為解決這個(gè)問題，提出了分頁存時(shí)是整體裝入的，為解決這個(gè)問題，提出了分頁存儲(chǔ)管理技術(shù)。儲(chǔ)管理技術(shù)。2 2、基本原理、基本原理 所謂分頁，就是把主存存儲(chǔ)空間按大小一所謂分頁，就是把主存存儲(chǔ)空間按大小一定的塊劃分，稱為物理塊、或頁框（定的塊劃分，稱為物理塊、或頁框（

39、page page frameframe），同時(shí)，按同樣的尺寸去劃分作業(yè)的），同時(shí)，按同樣的尺寸去劃分作業(yè)的地址空間，形成一個(gè)個(gè)相等的頁面，稱為邏輯地址空間，形成一個(gè)個(gè)相等的頁面，稱為邏輯頁或虛頁。頁或虛頁。 為了便于利用硬件進(jìn)行地址的轉(zhuǎn)換工作，為了便于利用硬件進(jìn)行地址的轉(zhuǎn)換工作，頁面大小通常是頁面大小通常是2 2的冪次方，分頁的過程對(duì)用的冪次方，分頁的過程對(duì)用戶是透明的。戶是透明的。01234560123456作業(yè)的地址空間作業(yè)的地址空間頁表頁表主存中的物理塊主存中的物理塊分頁存儲(chǔ)管理的基本做法：分頁存儲(chǔ)管理的基本做法：（1 1）等分主存：把主存劃分成相同大小的存儲(chǔ)塊，）等分主存：把主存劃分

40、成相同大小的存儲(chǔ)塊，成為塊（或稱為頁架）。對(duì)特定計(jì)算機(jī)，塊的大成為塊（或稱為頁架）。對(duì)特定計(jì)算機(jī)，塊的大小通常是固定不變的。小通常是固定不變的。（2 2）用戶邏輯地址的分頁：把用戶的邏輯地址空）用戶邏輯地址的分頁：把用戶的邏輯地址空間（虛擬地址空間）劃分成若干個(gè)與塊大小相同間（虛擬地址空間）劃分成若干個(gè)與塊大小相同的部分（稱為頁），并依次編號(hào)。的部分（稱為頁），并依次編號(hào)。（3 3）邏輯地址表示：一般從基地址）邏輯地址表示：一般從基地址“0”0”開始編開始編址（相對(duì)地址）。每個(gè)相對(duì)地址用一對(duì)數(shù)字（址（相對(duì)地址）。每個(gè)相對(duì)地址用一對(duì)數(shù)字（p,dp,d）表示，其中表示，其中p p是頁號(hào)，是頁號(hào)，d

41、 d是頁內(nèi)位移。是頁內(nèi)位移。如用如用A A表示相對(duì)地址，頁面大小為表示相對(duì)地址，頁面大小為L(zhǎng) L，則，則LAINTp LMODAd)(（4 4）主存分配原則：系統(tǒng)以塊為單位把主存分）主存分配原則：系統(tǒng)以塊為單位把主存分給作業(yè)或進(jìn)程（它們不一定是相鄰和連續(xù)的）。給作業(yè)或進(jìn)程（它們不一定是相鄰和連續(xù)的）。（5 5）頁表：系統(tǒng)為每個(gè)進(jìn)程設(shè)立一個(gè)頁面映象）頁表：系統(tǒng)為每個(gè)進(jìn)程設(shè)立一個(gè)頁面映象表（簡(jiǎn)稱頁表），使頁和塊建立的一一對(duì)應(yīng)的關(guān)表（簡(jiǎn)稱頁表），使頁和塊建立的一一對(duì)應(yīng)的關(guān)系。系。頁表應(yīng)包括如下信息：頁表應(yīng)包括如下信息： 頁號(hào)頁號(hào) 塊號(hào)：指頁面裝入系統(tǒng)的第幾號(hào)塊塊號(hào)：指頁面裝入系統(tǒng)的第幾號(hào)塊 狀態(tài)：表

42、示該頁是否在主存中（以狀態(tài)：表示該頁是否在主存中（以IBM4300IBM4300為為例：斷開、連接、可尋址）例：斷開、連接、可尋址）另外還可能有的其它信息：修改位（修改過否）、另外還可能有的其它信息：修改位（修改過否）、訪問位（有幾個(gè)進(jìn)程訪問）、引用位（最近被引訪問位（有幾個(gè)進(jìn)程訪問）、引用位（最近被引用過否）、外存地址等。用過否）、外存地址等。（6 6）分頁系統(tǒng)中的地址結(jié)構(gòu)：通常將地址域分成）分頁系統(tǒng)中的地址結(jié)構(gòu)：通常將地址域分成兩部分，一部分表示地址所在的頁號(hào)，另一部分表兩部分，一部分表示地址所在的頁號(hào)，另一部分表示頁內(nèi)地址。至于它們各占幾位，則主要取決于頁示頁內(nèi)地址。至于它們各占幾位，則

43、主要取決于頁的大小。的大小。（7 7）頁面尺寸應(yīng)是）頁面尺寸應(yīng)是2 2的冪：目的在于不經(jīng)運(yùn)算即可得到的冪：目的在于不經(jīng)運(yùn)算即可得到p p和和d d。頁號(hào)頁號(hào)p頁內(nèi)地址頁內(nèi)地址d07 819 2031例子：假定頁的大小為例子：假定頁的大小為1KB1KB，指令的地址域長(zhǎng)度為，指令的地址域長(zhǎng)度為1616位，位，則邏輯地址則邏輯地址41014101的頁號(hào)、頁內(nèi)地址可以這樣來確定：的頁號(hào)、頁內(nèi)地址可以這樣來確定：10210241KB邏輯地址邏輯地址02122224101的機(jī)內(nèi)表示形式為：的機(jī)內(nèi)表示形式為：0 00 10 00 115 14 13 12 11 10 9 8 7 6 5 4 3 2 1 00

44、 00 00 00 1可立即得到頁號(hào)為可立即得到頁號(hào)為4 4，頁內(nèi)地址為，頁內(nèi)地址為5 5計(jì)算機(jī)類型頁面字節(jié)數(shù)IBM AS/400VAX 系列NS32032Intel 80386Motorola 6803051251251240964096兩級(jí)和多級(jí)頁表兩級(jí)和多級(jí)頁表：現(xiàn)代大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持：現(xiàn)代大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間。在這樣的環(huán)境下，頁表就非常大的邏輯地址空間。在這樣的環(huán)境下，頁表就會(huì)變得非常大，本身就要占用非常大的內(nèi)存空間。會(huì)變得非常大，本身就要占用非常大的內(nèi)存空間。頁面大小的選擇頁面大小的選擇：頁面大小一般是由機(jī)器的地址：頁面大小一般是由機(jī)器的地址結(jié)構(gòu)所決定的

45、，亦即由硬件決定的。頁面的大小結(jié)構(gòu)所決定的，亦即由硬件決定的。頁面的大小通常在通常在12922之間，即在之間，即在512512字節(jié)到字節(jié)到4KB4KB之間。之間。目前常見的幾種計(jì)目前常見的幾種計(jì)算機(jī)中所選用的頁面大小如下所示：算機(jī)中所選用的頁面大小如下所示：解決的辦法：解決的辦法：1 1、對(duì)頁表所需的內(nèi)存空間，采用離散的分配辦法；、對(duì)頁表所需的內(nèi)存空間，采用離散的分配辦法；2 2、只將當(dāng)前需要的部分表項(xiàng)調(diào)入內(nèi)存。、只將當(dāng)前需要的部分表項(xiàng)調(diào)入內(nèi)存。兩級(jí)頁表的邏輯地址結(jié)構(gòu)：兩級(jí)頁表的邏輯地址結(jié)構(gòu)：p1P2d3122 2112 110外層頁號(hào)外層頁號(hào)外層頁內(nèi)地址外層頁內(nèi)地址頁內(nèi)地址頁內(nèi)地址兩級(jí)頁表結(jié)

46、構(gòu)：兩級(jí)頁表結(jié)構(gòu)：外部頁表外部頁表第第0頁頁表頁頁表第第1頁頁表頁頁表第第n頁頁表頁頁表內(nèi)存空間內(nèi)存空間具有兩級(jí)頁表的地址變換機(jī)構(gòu)具有兩級(jí)頁表的地址變換機(jī)構(gòu)p1P2d外層頁號(hào)外層頁號(hào)外層頁內(nèi)地址外層頁內(nèi)地址頁內(nèi)地址頁內(nèi)地址外部頁表寄存器外部頁表寄存器外部頁表外部頁表物理地址物理地址頁表頁表+bd對(duì)于具有更大存儲(chǔ)容量的計(jì)算機(jī)系統(tǒng)，可能需要采對(duì)于具有更大存儲(chǔ)容量的計(jì)算機(jī)系統(tǒng)，可能需要采用同樣的原理建立更多級(jí)的頁表用同樣的原理建立更多級(jí)的頁表3、存儲(chǔ)空間的分配和回收、存儲(chǔ)空間的分配和回收 對(duì)于存儲(chǔ)空間的管理，最簡(jiǎn)單的辦法是建立對(duì)于存儲(chǔ)空間的管理，最簡(jiǎn)單的辦法是建立一張一張“位示圖位示圖”，其中每一位

47、對(duì)應(yīng)一個(gè)物理塊，其中每一位對(duì)應(yīng)一個(gè)物理塊，用用1 1和和0 0分別表示對(duì)應(yīng)的物理塊已占用或空閑。另分別表示對(duì)應(yīng)的物理塊已占用或空閑。另外再增加一個(gè)字節(jié)記錄當(dāng)前系統(tǒng)中空閑塊的總數(shù)。外再增加一個(gè)字節(jié)記錄當(dāng)前系統(tǒng)中空閑塊的總數(shù)。假定主存有假定主存有256256個(gè)物理塊，則可用字長(zhǎng)為個(gè)物理塊，則可用字長(zhǎng)為3232位的位的8 8個(gè)字作為位示圖：個(gè)字作為位示圖：空閑塊數(shù)空閑塊數(shù)字長(zhǎng)字長(zhǎng)32位位8個(gè)字個(gè)字1為已分配為已分配0為空閑為空閑增 加 的增 加 的 1個(gè)字節(jié)個(gè)字節(jié) 在進(jìn)行物理塊的分配時(shí)，可按下述公式計(jì)算物理在進(jìn)行物理塊的分配時(shí)，可按下述公式計(jì)算物理塊的塊號(hào)：塊的塊號(hào)：塊號(hào)塊號(hào) = = 字號(hào)字號(hào) 字長(zhǎng)

48、字長(zhǎng) + + 位號(hào)位號(hào) 在進(jìn)行物理塊的回收時(shí)，假定被回收的物理塊在進(jìn)行物理塊的回收時(shí)，假定被回收的物理塊的塊號(hào)為的塊號(hào)為i i，則在位示圖中的對(duì)應(yīng)位置為：，則在位示圖中的對(duì)應(yīng)位置為：字號(hào)字號(hào) = i / = i / 字長(zhǎng)字長(zhǎng) 位號(hào)位號(hào) = i mod = i mod 字長(zhǎng)字長(zhǎng)4 4、地址轉(zhuǎn)換、地址轉(zhuǎn)換 將得到的邏輯地址分成兩個(gè)部分：頁號(hào)和將得到的邏輯地址分成兩個(gè)部分：頁號(hào)和 頁內(nèi)地址；頁內(nèi)地址； 根據(jù)頁號(hào)查找頁表，得到對(duì)應(yīng)的物理塊號(hào)；根據(jù)頁號(hào)查找頁表，得到對(duì)應(yīng)的物理塊號(hào)； 根據(jù)得到的物理塊號(hào)和頁內(nèi)地址，計(jì)算出根據(jù)得到的物理塊號(hào)和頁內(nèi)地址，計(jì)算出 實(shí)際的物理地址（絕對(duì)地址）實(shí)際的物理地址（絕對(duì)地

49、址） CPUPdf邏輯地址邏輯地址物理地址物理地址頁表頁表內(nèi)內(nèi)存存P操作系統(tǒng)操作系統(tǒng)第一步第一步第二步第二步第三步第三步fd頁號(hào)頁號(hào)塊號(hào)塊號(hào)02142638例題：例題： 在采用頁式存儲(chǔ)管理的系統(tǒng)中，某作業(yè)在采用頁式存儲(chǔ)管理的系統(tǒng)中，某作業(yè)J J的邏輯的邏輯地址空間為地址空間為4 4頁（每頁頁（每頁20482048字節(jié)），且已知該作業(yè)的字節(jié)），且已知該作業(yè)的頁面映像表如下圖。試借助地址變換圖（即要求畫頁面映像表如下圖。試借助地址變換圖（即要求畫出地址變換圖）求出有效邏輯地址出地址變換圖）求出有效邏輯地址48654865所對(duì)應(yīng)的物所對(duì)應(yīng)的物理地址。理地址?？刂萍拇嫫骺刂萍拇嫫骺刂萍拇嫫黜摫淼刂讽摫?/p>

50、地址2769012324686769主主 存存13057頁號(hào)塊號(hào)021426384865 - 2，764物理地址：物理地址：6204876413057需要考慮的問題：需要考慮的問題：1 1、頁表放在哪里？、頁表放在哪里？ 多數(shù)的系統(tǒng)是在系統(tǒng)表格區(qū)專門開辟一個(gè)集中多數(shù)的系統(tǒng)是在系統(tǒng)表格區(qū)專門開辟一個(gè)集中的頁表空間。在建立頁表之前先向系統(tǒng)請(qǐng)求分配的頁表空間。在建立頁表之前先向系統(tǒng)請(qǐng)求分配頁表空間。頁表空間。2 2、對(duì)系統(tǒng)性能有何不利影響？、對(duì)系統(tǒng)性能有何不利影響？ 由于由于CPUCPU存取一次數(shù)據(jù)至少要訪問兩次內(nèi)存存取一次數(shù)據(jù)至少要訪問兩次內(nèi)存（間接尋址對(duì)內(nèi)存的訪問多于兩次），因此計(jì)算（間接尋址對(duì)

51、內(nèi)存的訪問多于兩次），因此計(jì)算機(jī)存取內(nèi)存信息的時(shí)間至少比原來多了一倍。機(jī)存取內(nèi)存信息的時(shí)間至少比原來多了一倍。地址變換過程為：地址變換過程為： 在在CPUCPU給出地址變換機(jī)構(gòu)后，由地址變換機(jī)構(gòu)自動(dòng)地將頁號(hào)給出地址變換機(jī)構(gòu)后，由地址變換機(jī)構(gòu)自動(dòng)地將頁號(hào)p p送入快表，并將此頁號(hào)與快表中的所有頁號(hào)同時(shí)進(jìn)行比較。若送入快表，并將此頁號(hào)與快表中的所有頁號(hào)同時(shí)進(jìn)行比較。若其中由與此相匹配的頁號(hào)，則表明所要訪問的頁表項(xiàng)在快表中，其中由與此相匹配的頁號(hào)，則表明所要訪問的頁表項(xiàng)在快表中，于是可直接讀出該頁所對(duì)應(yīng)的物理塊號(hào)，并送物理地址寄存器。于是可直接讀出該頁所對(duì)應(yīng)的物理塊號(hào)，并送物理地址寄存器。如在快表中未找到對(duì)應(yīng)的頁表項(xiàng)，還需看訪問內(nèi)存中頁表的結(jié)如在快表中未找到對(duì)應(yīng)的頁表項(xiàng)，還需看訪問內(nèi)存中頁表的結(jié)果，如找到，則從頁表中讀出物理塊號(hào)送地址寄存器；同時(shí)還果，如找到，則從頁表中讀出物理塊號(hào)送地址寄存器；同時(shí)還需將次頁表項(xiàng)填入快表中的一個(gè)寄存器單元，即修改快表，以需將次頁表項(xiàng)填入快表中的一個(gè)寄存器單元，即修改快表，以保存最近訪問過的頁表項(xiàng)保留在快表中。保存最近訪問過的頁表項(xiàng)保留在快表中。5 5、快表、快表 為了提高地址變換速度，可在地址變換機(jī)構(gòu)中，增設(shè)一個(gè)為了提高地址變換速度，可在地址變換機(jī)構(gòu)中，增設(shè)一個(gè)具有并行查詢能力的特殊高速緩沖存