九.輸入/輸出保護為了支持多任務，80386不僅要有效地實現(xiàn)任務隔離，而且還要有效地控制各任務的輸入/輸出，避免輸入/輸出沖突。本文將介紹輸入輸出保護。 這里下載本文源代碼。 <一>輸入/輸出保護80386采用I/O特權級IPOL和I/O許可位圖的方法來控制輸入/輸出，實現(xiàn)輸入/輸出保護。 1.I/O敏感指令輸入輸出特權級(I/O Privilege Level)規(guī)定了可以執(zhí)行所有與I/O相關的指令和訪問I/O空間中所有地址的最外層特權級。IOPL的值在如下圖所示的標志寄存器中。 標 志寄存器 BIT31—BIT18 BIT17 BIT16 BIT15 BIT14 BIT13—BIT12 BIT11 BIT10 BIT9 BIT8 BIT7 BIT6 BIT5 BIT4 BIT3 BIT2 BIT1 BIT0 00000000000000 VM RF 0 NT IOPL OF DF IF TF SF ZF 0 AF 0 PF 1 CF I/O許可位圖規(guī)定了I/O空間中的哪些地址可以由在任何特權級執(zhí)行的程序所訪問。I/O許可位圖在任務狀態(tài)段TSS中。 I/O敏感指令 指令 功能 保護方式下的執(zhí)行條件 CLI 清除EFLAGS中的IF位 CPL<=IOPL STI 設置EFLAGS中的IF位 CPL<=IOPL IN 從I/O地址讀出數(shù)據(jù) CPL<=IOPL或I/O位圖許可 INS 從I/O地址讀出字符串 CPL<=IOPL或I/O位圖許可 OUT 向I/O地址寫數(shù)據(jù) CPL<=IOPL或I/O位圖許可 OUTS 向I/O地址寫字符串 CPL<=IOPL或I/O位圖許可 上表所列指令稱為I/O敏感指令，由于這些指令與I/O有關，并且只有在滿足所列條件時才可以執(zhí)行，所以把它們稱為I/O敏感指令。從表中可見，當前特權級不在I/O特權級外層時，可以正常執(zhí)行所列的全部I/O敏感指令；當特權級在I/O特權級外層時，執(zhí)行CLI和STI指令將引起通用保護異常，而其它四條指令是否能夠被執(zhí)行要根據(jù)訪問的I/O地址及I/O許可位圖情況而定(在下面論述)，如果條件不滿足而執(zhí)行，那么將引起出錯碼為0的通用保護異常。 由于每個任務使用各自的EFLAGS值和擁有自己的TSS，所以每個任務可以有不同的IOPL，并且可以定義不同的I/O許可位圖。注意，這些I/O敏感指令在實模式下總是可執(zhí)行的。 2.I/O許可位圖如果只用IOPL限制I/O指令的執(zhí)行是很不方便的，不能滿足實際要求需要。因為這樣做會使得在特權級3執(zhí)行的應用程序要么可訪問所有I/O地址，要么不可訪問所有I/O地址。實際需要與此剛好相反，只允許任務甲的應用程序訪問部分I/O地址，只允許任務乙的應用程序訪問另一部分I/O地址，以避免任務甲和任務乙在訪問I/O地址時發(fā)生沖突，從而避免任務甲和任務乙使用使用獨享設備時發(fā)生沖突。 因此，在IOPL的基礎上又采用了I/O許可位圖。I/O許可位圖由二進制位串組成。位串中的每一位依次對應一個I/O地址，位串的第0位對應I/O地址0，位串的第n位對應I/O地址n。如果位串中的第位為0，那么對應的I/O地址m可以由在任何特權級執(zhí)行的程序訪問；否則對應的I/O地址m只能由在IOPL特權級或更內(nèi)層特權級執(zhí)行的程序訪問。如果在I/O外層特權級執(zhí)行的程序訪問位串中位值為1的位所對應的I/O地址，那么將引起通用保護異常。 I/O地址空間按字節(jié)進行編址。一條I/O指令最多可涉及四個I/O地址。在需要根據(jù)I/O位圖決定是否可訪問I/O地址的情況下，當一條I/O指令涉及多個I/O地址時，只有這多個I/O地址所對應的I/O許可位圖中的位都為0時，該I/O指令才能被正常執(zhí)行，如果對應位中任一位為1，就會引起通用保護異常。 80386支持的I/O地址空間大小是64K，所以構成I/O許可位圖的二進制位串最大長度是64K個位，即位圖的有效部分最大為8K字節(jié)。一個任務實際需要使用的I/O許可位圖大小通常要遠小于這個數(shù)目。 當前任務使用的I/O許可位圖存儲在當前任務TSS中低端的64K字節(jié)內(nèi)。I/O許可位圖總以字節(jié)為單位存儲，所以位串所含的位數(shù)總被認為是8的倍數(shù)。從前文中所述的TSS格式可見，TSS內(nèi)偏移66H的字確定I/O許可位圖的開始偏移。由于I/O許可位圖最長可達8K字節(jié)，所以開始偏移應小于56K，但必須大于等于104，因為TSS中前104字節(jié)為TSS的固定格式，用于保存任務的狀態(tài)。 1.I/O訪問許可檢查細節(jié)保護模式下處理器在執(zhí)行I/O指令時進行許可檢查的細節(jié)如下所示。 (1)若CPL<=IOPL，則直接轉(zhuǎn)步驟(8)；(2)取得I/O位圖開始偏移；(3)計算I/O地址對應位所在字節(jié)在I/O許可位圖內(nèi)的偏移；(4)計算位偏移以形成屏蔽碼值，即計算I/O地址對應位在字節(jié)中的第幾位；(5)把字節(jié)偏移加上位圖開始偏移，再加1，所得值與TSS界限比較，若越界，則產(chǎn)生出錯碼為0的通用保護故障；(6)若不越界，則從位圖中讀對應字節(jié)及下一個字節(jié)；(7)把讀出的兩個字節(jié)與屏蔽碼進行與運算，若結果不為0表示檢查未通過，則產(chǎn)生出錯碼為0的通用保護故障；(8)進行I/O訪問。設某一任務的TSS段如下： TSSSEG SEGMENT PARA USE16 TSS <> ;TSS低端固定格式部分 DB 8 DUP(0) ;對應I/O端口00H—3FH DB 10000000B ;對應I/O端口40H—47H DB 01100000B ;對用I/O端口48H—4FH DB 8182 DUP(0ffH) ;對應I/O端口50H—0FFFFH DB 0FFH ;位圖結束字節(jié)TSSLen = $TSSSEG ENDS 再假設IOPL=1，CPL=3。那么如下I/O指令有些能正常執(zhí)行，有些會引起通用保護異常： in al,21h ;(1)正常執(zhí)行 in al,47h ;(2)引起異常 out 20h,al ;(3)正常實行 out 4eh,al ;(4)引起異常 in al,20h ;(5)正常執(zhí)行 out 20h,eax ;(6)正常執(zhí)行 out 4ch,ax ;(7)引起異常 in ax,46h ;(8)引起異常 in eax,42h ;(9)正常執(zhí)行 由上述I/O許可檢查的細節(jié)可見，不論是否必要，當進行許可位檢查時，80386總是從I/O許可位圖中讀取兩個字節(jié)。目的是為了盡快地執(zhí)行I/O許可檢查。一方面，常常要讀取I/O許可位圖的兩個字節(jié)。例如，上面的第(8)條指令要對I/O位圖中的兩個位進行檢查，其低位是某個字節(jié)的最高位，高位是下一個字節(jié)的最低位。可見即使只要檢查兩個位，也可能需要讀取兩個字節(jié)。另一方面，最多檢查四個連續(xù)的位，即最多也只需讀取兩個字節(jié)。所以每次要讀取兩個字節(jié)。這也是在判別是否越界時再加1的原因。為此，為了避免在讀取I/O許可位圖的最高字節(jié)時產(chǎn)生越界，必須在I/O許可位圖的最后填加一個全1的字節(jié)，即0FFH。此全1的字節(jié)應填加在最后一個位圖字節(jié)之后，TSS界限范圍之前，即讓填加的全1字節(jié)在TSS界限之內(nèi)。 I/O許可位圖開始偏移加8K所得的值與TSS界限值二者中較小的值決定I/O許可位圖的末端。當TSS的界限大于I/O許可位圖開始偏移加8K時，I/O許可位圖的有效部分就有8K字節(jié)，I/O許可檢查全部根據(jù)全部根據(jù)該位圖進行。當TSS的界限不大于I/O許可位圖開始偏移加8K時，I/O許可位圖有效部分就不到8K字節(jié)，于是對較小I/O地址訪問的許可檢查根據(jù)位圖進行，而對較大I/O地址訪問的許可檢查總被認為不可訪問而引起通用保護故障。因為這時會發(fā)生字節(jié)越界而引起通用保護異常，所以在這種情況下，可認為不足的I/O許可位圖的高端部分全為1。利用這個特點，可大大節(jié)約TSS中I/O許可位圖占用的存儲單元，也就大大減小了TSS段的長度。 <二>重要標志保護輸入輸出的保護與存儲在標志寄存器EFLAGS中的IOPL密切相關，顯然不能允許隨便地改變IOPL，否則就不能有效地實現(xiàn)輸入輸出保護。類似地，對EFLAGS中的IF位也必須加以保護，否則CLI和STI作為敏感指令對待是無意義的。此外，EFLAGS中的VM位決定著處理器是否按虛擬8086方式工作。 80386對EFLAGS中的這三個字段的處理比較特殊，只有在較高特權級執(zhí)行的程序才能執(zhí)行IRET、POPF、CLI和STI等指令改變它們。下表列出了不同特權級下對這三個字段的處理情況。 不同特權級對標志寄存器特殊字段的處理 特權級 VM標志字段 IOPL標志字段 IF標志字段 CPL=0 可變(初POPF指令外) 可變 可變 0 不變 不變 可變 CPL>IOPL 不變 不變 不變 從表中可見，只有在特權級0執(zhí)行的程序才可以修改IOPL位及VM位；只能由相對于IOPL同級或更內(nèi)層特權級執(zhí)行的程序才可以修改IF位。與CLI和STI指令不同，在特權級不滿足上述條件的情況下，當執(zhí)行POPF指令和IRET指令時，如果試圖修改這些字段中的任何一個字段，并不引起異常，但試圖要修改的字段也未被修改，也不給出任何特別的信息。此外，指令POPF總不能改變VM位，而PUSHF指令所壓入的標志中的VM位總為0。 <三>演示輸入輸出保護的實例(實例九)下面給出一個用于演示輸入輸出保護的實例。演示內(nèi)容包括：I/O許可位圖的作用、I/O敏感指令引起的異常和特權指令引起的異常；使用段間調(diào)用指令CALL通過任務門調(diào)用任務，實現(xiàn)任務嵌套。 1.演示步驟實例演示的內(nèi)容比較豐富，具體演示步驟如下：(1)在實模式下做必要準備后，切換到保護模式；(2)進入保護模式的臨時代碼段后，把演示任務的TSS段描述符裝入TR，并設置演示任務的堆棧；(3)進入演示代碼段，演示代碼段的特權級是0；(4)通過任務門調(diào)用測試任務1。測試任務1能夠順利進行；(5)通過任務門調(diào)用測試任務2。測試任務2演示由于違反I/O許可位圖規(guī)定而導致通用保護異常；(6)通過任務門調(diào)用測試任務3。測試任務3演示I/O敏感指令如何引起通用保護異常；(7)通過任務門調(diào)用測試任務4。測試任務4演示特權指令如何引起通用保護異常；(8)從演示代碼轉(zhuǎn)臨時代碼，準備返回實模式；(9)返回實模式，并作結束處理。
上傳時間： 2013-12-11
上傳用戶：nunnzhy
經(jīng)典c程序100例==1--10 【程序1】 題目：有1、2、3、4個數(shù)字，能組成多少個互不相同且無重復數(shù)字的三位數(shù)？都是多少？ 1.程序分析：可填在百位、十位、個位的數(shù)字都是1、2、3、4。組成所有的排列后再去 掉不滿足條件的排列。 2.程序源代碼： main() { int i,j,k printf("\n") for(i=1 i<5 i++) ／*以下為三重循環(huán)*/ for(j=1 j<5 j++) for (k=1 k<5 k++) { if (i!=k&&i!=j&&j!=k) /*確保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k) }
上傳時間： 2014-01-07
上傳用戶：lizhizheng88
此為編譯原理實驗報告 學習消除文法左遞規(guī)算法，了解消除文法左遞規(guī)在語法分析中的作用 內(nèi)含 設計算法 目的 源碼 等等.... 算法:消除左遞歸算法為: （1）把文法G的所有非終結符按任一種順序排列成P1,P2,…Pn 按此順序執(zhí)行 （2）FOR i:=1 TO n DO BEGIN FOR j:=1 DO 把形如Pi→Pjγ的規(guī)則改寫成 Pi→δ1γ δ2γ … δkγ。其中Pj→δ1 δ2 … δk是關于Pj的所有規(guī)則； 消除關于Pi規(guī)則的直接左遞歸性 END （3）化簡由（2）所得的文法。即去除那些從開始符號出發(fā)永遠無法到達的非終結符的 產(chǎn)生規(guī)則。
上傳時間： 2015-03-29
上傳用戶：極客
算法介紹 矩陣求逆在程序中很常見，主要應用于求Billboard矩陣。按照定義的計算方法乘法運算，嚴重影響了性能。在需要大量Billboard矩陣運算時，矩陣求逆的優(yōu)化能極大提高性能。這里要介紹的矩陣求逆算法稱為全選主元高斯-約旦法。 高斯-約旦法（全選主元）求逆的步驟如下： 首先，對于 k 從 0 到 n - 1 作如下幾步： 從第 k 行、第 k 列開始的右下角子陣中選取絕對值最大的元素，并記住次元素所在的行號和列號，在通過行交換和列交換將它交換到主元素位置上。這一步稱為全選主元。 m(k, k) = 1 / m(k, k) m(k, j) = m(k, j) * m(k, k)，j = 0, 1, ..., n-1；j != k m(i, j) = m(i, j) - m(i, k) * m(k, j)，i, j = 0, 1, ..., n-1；i, j != k m(i, k) = -m(i, k) * m(k, k)，i = 0, 1, ..., n-1；i != k 最后，根據(jù)在全選主元過程中所記錄的行、列交換的信息進行恢復，恢復的原則如下：在全選主元過程中，先交換的行（列）后進行恢復；原來的行（列）交換用列（行）交換來恢復。
上傳時間： 2015-04-09
上傳用戶：wang5829
Routine mampres: To obtain amplitude response from h(exp(jw)). input parameters: h :n dimensioned complex array. the frequency response is stored in h(0) to h(n-1). n :the dimension of h and amp. fs :sampling frequency (Hz). iamp:If iamp=0: The Amplitude Res. amp(k)=abs(h(k)) If iamp=1: The Amplitude Res. amp(k)=20.*alog10(abs(h(k))). output parameters: amp :n dimensioned real array. the amplitude-frequency response is stored in amp(0) to amp(n-1). Note: this program will generate a data file "filename.dat" . in chapter 2
標簽： dimensione parameters amplitude response
上傳時間： 2013-12-19
上傳用戶：xfbs821
經(jīng)典C語言程序設計100例1-10 如【程序1】 題目：有1、2、3、4個數(shù)字，能組成多少個互不相同且無重復數(shù)字的三位數(shù)？都是多少？ 1.程序分析：可填在百位、十位、個位的數(shù)字都是1、2、3、4。組成所有的排列后再去 掉不滿足條件的排列。 2.程序源代碼： main() { int i,j,k printf("\n") for(i=1 i<5 i++) ／*以下為三重循環(huán)*/ for(j=1 j<5 j++) for (k=1 k<5 k++) { if (i!=k&&i!=j&&j!=k) /*確保i、j、k三位互不相同*/ printf("％d,％d,％d\n",i,j,k) } }
上傳時間： 2013-12-14
上傳用戶：hfmm633
《算法分析與設計》中的 “矩陣連乘程序”給定n個矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1,2 ,…,n-1。由于矩陣滿足乘法的結合律，根據(jù)加括號的如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。
上傳時間： 2015-11-22
上傳用戶：ma1301115706
Floyd-Warshall算法描述 1)適用范圍： a)APSP(All Pairs Shortest Paths) b)稠密圖效果最佳 c)邊權可正可負 2)算法描述： a)初始化：dis[u,v]=w[u,v] b)For k:=1 to n For i:=1 to n For j:=1 to n If dis[i,j]>dis[i,k]+dis[k,j] Then Dis[I,j]:=dis[I,k]+dis[k,j] c)算法結束：dis即為所有點對的最短路徑矩陣 3)算法小結：此算法簡單有效，由于三重循環(huán)結構緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。時間復雜度O(n^3)。 考慮下列變形：如(I,j)∈E則dis[I,j]初始為1,else初始為0，這樣的Floyd算法最后的最短路徑矩陣即成為一個判斷I,j是否有通路的矩陣。更簡單的，我們可以把dis設成boolean類型，則每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”來代替算法描述中的藍色部分，可以更直觀地得到I,j的連通情況。
標簽： Floyd-Warshall Shortest Pairs Paths
上傳時間： 2013-12-01
上傳用戶：dyctj
給定n個矩陣{A1,A2,…,An}，其中Ai與Ai+1是可乘的，i=1,2,…,n-1。考察這n個矩陣的連乘積A1A2…An。由于矩陣乘法滿足結合律，故計算矩陣的連乘積可以有許多不同的計算次序，這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，則可以依此次序反復調(diào)用2個矩陣相乘的標準算法（有改進的方法，這里不考慮）計算出矩陣連乘積。若A是一個p×q矩陣，B是一個q×r矩陣，則計算其乘積C=AB的標準算法中，需要進行pqr次數(shù)乘。
上傳時間： 2016-06-18
上傳用戶：hjshhyy
K-MEANS算法 輸入：聚類個數(shù)k，以及包含 n個數(shù)據(jù)對象的數(shù)據(jù)庫。 輸出：滿足方差最小標準的k個聚類。 處理流程： （1） 從 n個數(shù)據(jù)對象任意選擇 k 個對象作為初始聚類中心； （2） 循環(huán)（3）到（4）直到每個聚類不再發(fā)生變化為止 （3） 根據(jù)每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應對象進行劃分； （4） 重新計算每個（有變化）聚類的均值（中心對象）
上傳時間： 2013-12-20
上傳用戶：chenjjer
