數(shù)據(jù)庫系統(tǒng)工程師復習資料-資料下載頁
2025-04-17 01:46本頁面
【正文】 1． 設度為1的結點數(shù)為N1，設度為2的結點數(shù)為N2，設度為0的結點（葉子）數(shù)為N0，則根據(jù)二叉樹的公式：N0+N2=2N2+1，即N0=N2+1。2． SNMP的設計是基于IP之上的無連接的用戶數(shù)據(jù)報協(xié)議，即UDP/IP協(xié)議。海明碼是奇偶校驗的一種擴充。它采用多位校驗碼的方式，在這些校驗位中的每一位都對不同的信息數(shù)據(jù)位進行奇偶校驗，通過合理地安排每個校驗位對原始數(shù)據(jù)進行校驗位組合，可以達到發(fā)現(xiàn)錯誤，糾正錯誤的目的。假設數(shù)據(jù)位有m痊，如何設定校驗位k的長度才能滿足糾正一位錯誤的要求呢？K位的校驗碼可以有2^k個值。顯然，其中一個值表示數(shù)據(jù)是正確的，而剩下的2^k1個值意味著數(shù)據(jù)中存在錯誤，如果能夠滿足：2^k1m+k（m+k為編碼后的總長度），在理論上k個校驗碼就可以判斷是哪一位（包括信息碼和校驗碼）出現(xiàn)問題。編碼步驟如下：（1） 根據(jù)信息位數(shù)，確定校驗位數(shù)，2^r=k+r+1，其中，k為信息位數(shù)，r為校驗位數(shù)。求出滿足不等式的最小r，即為校驗位數(shù)。計算機校驗位公式如下：表13其實可以當成一個公式來套用,如有已經編碼的數(shù)據(jù)1100 1001 ,首先看數(shù)據(jù)的最低位(即右邊第一位),最低位為1,把1填充在公式表的r0位置,接著取出數(shù)據(jù)的次低位數(shù)據(jù)(即右邊的第2位),把它填充到r1位置,我們可以得到表14:表中第二行數(shù)據(jù)為1100 0011，這就是數(shù)據(jù)1100 1001 0111的編碼信息，而表格第三行是1011，這便是校驗位。注意：校驗位rn所在位數(shù)為2^n,其余由信息位填充；信息位下標從1開始，而校驗位下標從0開始。例如：I8對應的第十二位12=2^3+2^2,I7，對應的第十一位11=2^3+2^+2^0,I6對應的第十位10=2^3+2^1,I5對應的第九位9=2^3+2^0，一直寫到I1對應的第三位。校驗位rn由前面位數(shù)寫成2的冪之和中包含2^n的位數(shù)對應的信息位之和構成。例如：r3=I8①I7①I6①I5（其中的1代表加號）注意：其中“①”異或運算。（3）求校驗位。根據(jù)上面我們所說的計算公式可以求出校驗位。（4）求海明碼。2．糾錯步驟（1）根據(jù)海明碼的信息位和校驗位的分布規(guī)則，找出接收到的數(shù)據(jù)的信息位以及校驗位。如有已經編碼的數(shù)據(jù)1100 1001 0111，則可以根據(jù)上表得到編碼的信息為：1100 0011；校驗位為：1011，（2） 接收端對校驗位進行驗證Sn=rn(校驗)+rn(接收)（3） 判斷校正因子是否有錯，并改正。Sn Sn1 Sn2……S0二進制對應的是那位就是那位出錯，將其改正完成糾錯。如1001為第九位，將第九位1變0（或0變1）即可。例題1求信息1011的海明碼。解答：（1）2^r=4+r+1,確定校驗位為3位2^3=4+3+1.（2）列出公式表格。7=4+2+1，6=4+2，5=4+1，3=2+1r2=I4+I3+I2 r1=I4+I3+I1 r0=I4 +I2+I1根據(jù)公式得r2=0,r1=0,r0=1加入表格則海明碼為1010101 PV操作理解析疑（1）定義：P原語的主要操作是：（1）sem減1；（2）若sem減1后仍大于或等于零，則該進程繼續(xù)執(zhí)行；（3）若sem減1后小于零，則該進程被阻塞，在相應隊列中排隊，然后轉向系統(tǒng)的進程調度。V原語的主要操作是：（1）sem加1；（2）若相加結果大于零，則該進程繼續(xù)執(zhí)行；（3）若相加結果小于或等于零，則喚醒一阻塞在該信號量上的進程，然后再返回原進程繼續(xù)執(zhí)行或轉進程調度。典型理解偏差：1。以V原語的2步來做，Sem不就永遠大于0，那進程不就一起循環(huán)執(zhí)行成為死循環(huán)了？2．Sem大于0那就表示有臨界資源可供使用，為什么不喚醒進程？3．Sem小于0應該是說沒有臨界資源可供使用，為什么還要喚醒進程？4．如果是互斥信號量的話，應該設置信號量Sen=1，但是當有5個進程都訪問的話，最后在該信號量的鏈表里會有4個等待，也是說S=—4，那么第一個進程執(zhí)行了V操作使S加1，釋放了資源，下一個應該能夠執(zhí)行，但喚醒的這個進程在執(zhí)行P操作時因S0，也還是執(zhí)行不了，這是怎么回事呢？5．Sem的絕對值表示等待的進程數(shù)，同時又表示臨界資源，這到底是怎么回事？析疑1。P操作對Sem減1的。P、V原語必須成對使用！從而不會造成死循環(huán)。2．Sem大于0的確表示有臨界資源可供使用，而且這個時候沒有進程被阻塞在這個資源上，也就是說沒有進程因為得不到這類資源而阻塞，所以沒有被阻塞的進程，自然不需要喚醒。3．V原語操作的本質在于：一個進程使用完臨界資源后，釋放臨界資源，使Sem加強，以通知其它的進程，這個時候如果Sem0，表明有進程阻塞在該類資源上，因此要從阻塞隊列里喚醒一個進程來“轉手”該類資源。比如，有2個某類資源，三個進程A、B、C、D要用該類資源，最開始Sem=2，當A進入，Sem=1，當B進入Sem=0，表明該類資源剛好用完，當C進入時Sem=—1，表明有一個進程被阻塞了，D進入，Sem=—2。當A用完該類資源時，進行V操作，Sem=—1，釋放該類資源，而這時Sem0，表明有進程阻塞在該類資源上，于是喚醒一個。4．當一個進程阻塞了的時候，它已經執(zhí)行過了P操作，并卡在臨界區(qū)那個地方。當喚醒它時就立即進入它自己的臨界區(qū)，并不需要執(zhí)行P操作了，當執(zhí)行完了臨界萄程序后，就執(zhí)行V操作。5．當信號量Sem小于0時，其絕對值表示系統(tǒng)中因請求該類資源而被阻塞的進程數(shù)目。S大于0時表示可用的臨界次數(shù)。注意在不同情況下所表達的含義不一樣。當?shù)扔?時，表示剛好用完。51 / 51
教學教案相關推薦
鄂ICP備17016276號-1