操作系統(tǒng)第八章

1、散列結構：散列結構：①基本思想：定義個一個散列函數(shù)基本思想：定義個一個散列函數(shù)hash(key)，使得對于給定的鍵，使得對于給定的鍵key，散列函數(shù)，散列函數(shù)hash(key)將其轉換為將其轉換為key所對應所對應的存儲地址。的存儲地址。即：即：hash(key)=addr(在磁盤或文件中的存放位置在磁盤或文件中的存放位置)②散列沖突散列沖突③解決散列沖突：線性散列法、解決散列沖突：線性散列法、順序探查法順序探查法等。等。線性散列法：線

2、性散列法：hi(k)=(h1(k)di)(modt)di=ai例題：設散列函數(shù)例題：設散列函數(shù)h(n)=(676l126l2l3)(modt)，t＝11，li為鍵為鍵n的第的第i個英文字母序號。鍵表長個英文字母序號。鍵表長11，鍵名為英，鍵名為英文字母。按線性散列法計算將任意文字母。按線性散列法計算將任意7個鍵放入鏈表中所用的計算次數(shù)。這里令個鍵放入鏈表中所用的計算次數(shù)。這里令a＝2，c＝1。解：設解：設7個關鍵字分別為：個關鍵字分別為

3、：zhl，ouy，lwj，yks，lxz，suy，hls則有：則有：h(n)=(767l126l2l3)mod11（1）線性散列法：線性散列法：hi(k)=(h1(k)2i)mod11h(zhl)=(6762626812)mod11＝9h(ouy)=(67615262125)mod11=8h(lwj)=(67612262310)mod11=8h2＝（＝（822）mod11＝1h(yks)=(67625261119)mod11=1h2＝（

4、＝（122）mod11＝5h(lxz)=(67612262426)mod11=6h(suy)=(67619262125)mod11=6h2＝（＝（622）mod11＝10h(hls)=(6768261219)mod11＝8h2＝（＝（822）mod11＝1h3＝（＝（823）mod11＝3二、某虛擬存儲器的用戶編程空間共某虛擬存儲器的用戶編程空間共32個頁面，每頁為個頁面，每頁為1KB，內(nèi)存為，內(nèi)存為16KB。假定某時刻一用戶頁表中已調(diào)

5、入內(nèi)存。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面對應的物理塊號如下表：的頁面對應的物理塊號如下表：則邏輯地址則邏輯地址0A5C（H）所對應的物理地址為）所對應的物理地址為：125C答：0A5C＝0000101001011100頁號為頁號為2，對應塊號為，對應塊號為4，有：物理地址：，有：物理地址：0001，001001011100即：即：125C三、分頁式存儲空間的分配由于塊的大小是固定的，可以用一張位示圖來構成主存分配表。三、分頁式存儲

6、空間的分配由于塊的大小是固定的，可以用一張位示圖來構成主存分配表?，F(xiàn)設主存有現(xiàn)設主存有8192塊，則可用字長為塊，則可用字長為32位的位的256個字作為位示圖。若塊號、字號、位號個字作為位示圖。若塊號、字號、位號（從高位到低位）都是從（從高位到低位）都是從0開始，試問開始，試問4999塊對應的字號和位號；塊對應的字號和位號；129字的字的29位對應位對應哪一塊？哪一塊？答：【參考答案】依題目所給條件，已知位示圖如下所示：499932=1

7、56余1所以4999塊對應的字號為156，位號為1。129字的第29位對應的塊號為：1293229=4157塊），即對應內(nèi)存的第4157塊。四、某頁式存儲器用戶地址空間有四、某頁式存儲器用戶地址空間有32個頁面，每頁個頁面，每頁1KB，主存，主存16KB。假定某時刻為用戶的第。假定某時刻為用戶的第0，1，2，3號頁面號頁面=4；D=5012mod1024=916；因頁號超過頁表長度，該邏輯地址非法。八、某虛擬存儲器的用戶編程空間共某虛擬

8、存儲器的用戶編程空間共32個頁面，每頁為個頁面，每頁為1KB，內(nèi)存為，內(nèi)存為16KB。假定某時刻一用戶頁表中已調(diào)入內(nèi)存。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號和物理塊號的對照表如下：的頁面的頁號和物理塊號的對照表如下：則邏輯地址則邏輯地址0A5C（H）所對應的物理地址是什么？）所對應的物理地址是什么？答：頁式存儲管理的邏輯地址分為兩部分：頁號和頁內(nèi)地址。由已知條件“用戶編程空間共32個頁面”，可知頁號部分占5位；由“每頁為1KB”

9、，1K=210，可知內(nèi)頁地址占10位。由“內(nèi)存為16KB”，可知有16塊，塊號為4位。邏輯地址0A5C（H）所對應的二進制表示形式是：000101001011100，根據(jù)上面的分析，下劃線部分為頁內(nèi)地址，編碼“00010”為頁號，表示該邏輯地址對應的頁號為2。查頁表，得到物理塊號是4（十進制），即物理塊地址為：0100，拼接塊內(nèi)地址1001011100，得01001001011100，即125C（H）。九、九、有一個倉庫，可以存放有一個

10、倉庫，可以存放A和B兩種產(chǎn)品，但要求：兩種產(chǎn)品，但要求：(1)、每次只能存放一種產(chǎn)品（、每次只能存放一種產(chǎn)品（A或B）(2)、NA產(chǎn)品數(shù)量產(chǎn)品數(shù)量B產(chǎn)品數(shù)量產(chǎn)品數(shù)量M。其中，其中，N和M是正整數(shù)。試用是正整數(shù)。試用P、V操作描述產(chǎn)品操作描述產(chǎn)品A與產(chǎn)品與產(chǎn)品B的入庫過程。的入庫過程。解：解：在本題中，我們可以設置兩個信號量來控制A、B產(chǎn)品的存放數(shù)量，sa表示當前允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量，即在當前庫存量和B產(chǎn)品不入庫的情況下，還可以

11、允許sa個A產(chǎn)品人庫sb表示當前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，即在當前庫存量和A產(chǎn)品不入庫的情況下，還可以允許sb個B產(chǎn)品入庫。初始時，sa為M1，sb為N1。當往庫中存放入一個A產(chǎn)品時，則允許存入B產(chǎn)品的數(shù)量也增加1：當往庫中存放入一個B產(chǎn)品時，則允許存入A產(chǎn)品的數(shù)量也增加1。產(chǎn)品A、B的入庫過程描述如下：intmutex=1互斥信號量intsa=M1intsb=N1main()while(1)取一個產(chǎn)品if(取的是A產(chǎn)品)p(sa

12、)p(mutex)將產(chǎn)品入庫v(mutex)v(sb)else取的產(chǎn)品是Bp(sb)p(mutex)將產(chǎn)品入庫v(mutex)v(sa)十、有一頁式系統(tǒng)，其頁表存放在內(nèi)存中。十、有一頁式系統(tǒng)，其頁表存放在內(nèi)存中。(1)(1)、如果對內(nèi)存的一次存取需要、如果對內(nèi)存的一次存取需要1.51.5微秒，問實現(xiàn)一次頁面訪問的存取時間是多少？微秒，問實現(xiàn)一次頁面訪問的存取時間是多少？(2)(2)、如果系統(tǒng)增加有快表，平均命中率為、如果系統(tǒng)增加有快表，

13、平均命中率為85%85%，當頁表項在快表中時，其查找時間忽略為，當頁表項在快表中時，其查找時間忽略為0，問此時的存取時間為多少？，問此時的存取時間為多少？答：a.在分頁存儲管理中當訪問一條指令或數(shù)據(jù)時需要訪問內(nèi)存至少兩次。一次是訪問存放在內(nèi)存中的頁表PMT實現(xiàn)地址變換另一次是訪問所需的數(shù)據(jù)。在分段存儲管理中當訪問一條指令或數(shù)據(jù)時也需要訪問內(nèi)存至少兩次。一次是訪問存放在內(nèi)存中的段表SMT實現(xiàn)地址變換；另一次是訪問所需的數(shù)據(jù)。在段頁式存儲管