在具有虛擬存儲地址的數據處理系統中進行頁面置換的裝置和方法
2023-05-20 00:43:36
專利名稱:在具有虛擬存儲地址的數據處理系統中進行頁面置換的裝置和方法
本發明是關於數據處理系統，特別是有關採用虛擬地址技術與主存單元相互聯繫的多CPU數據處理系統。
近代數據處理系統通常採用分層次的存儲器結構。能為一個數據處理系統所訪問的大部分數據均存儲在諸如磁帶、磁碟或其它能存儲大量數字信息的海量存儲介質上。一般由於這些介質的存取速度太慢，無法實現CPU對所存數據的直接尋址。通常，一個作為主存的存儲單元均能用快速存取技術實現存取，它存儲了數據處理系統所需的數據部分。(雖然與本發明無直接關係，但一般數據處理系統中均包含有用來存儲對CPU有直接聯繫的數據的更快速的存儲器，並裝置在CPU內。處理器內的存儲單元多被用作緩衝器或高速緩衝存儲器。)藉助於作業系統，每個處理器均可訪問全部與數據處理裝置相關聯的有用數據，在需要時可利用這些數據。實際上由於適用於處理器的數據的規模，由海量存儲裝置檢索所需的數據成了處理工作進程中的一個不利的因素。數據處理系統所直接需要的一些數據被存儲在主存單元中，但是將所有這些數據存放在主存單元中是不現實的，因而將這些數據分成稱之為頁面的數據塊，並以它作為進入主存單元的單元實體。
在虛擬存儲器技術中，數據處理單元開始工作時，作業系統在主存單元中指定可用的空間。主存單元空間將針對數據處理工作的需要而被分配給程序、表格和數據處理系統工作所需的部分作業系統。存儲器中的這一區域並不包含如象通常作為被存儲在主存單元中的數據的剩餘部分的可置換的存儲信息。存儲單元的其餘部分則被分成相等的塊區，用以存儲一些對數據處理系統重要的有關數據信息組元。這些信號組元稱之為頁面。與每一頁面相應的是一個被稱之為頁面解說符的有關信號表中的一組數據信號。作業系統可以引用這些頁面解說符。該頁面解說符識別或指定有關頁解說符的位置。頁解說符包含有關虛擬或符號地址的信息。數據處理系統的處理器則將它們變換存放原始信息的實際或物理地址。每一頁解說符還涉及有關狀態信息方面的信號。該頁面解說符還包括一個稱為鏈節(Linker)的存儲單元中的數據信號，它可以用來按照一種予定的確定頁面順序的算法來指定頁面的次序。
在數據處理系統初始化之後，處理器將需要一組數據信號。軟體程序將為所需的數據信號組從符號地址提供有關的物理地址信息。有關這些參數的信息被存儲在頁解說符中。相應的信息被送入頁面解說符的鏈節部分，並指明其為頁面序列中的首位。在增加其它頁面時，鏈節信息即標明該頁面在此序列中的順序。當所有的頁面均佔有數據後，處理器繼續要求訪問一個新的數據，則需要一個已存有數據的頁面中的舊數據被新數據所替換，本發明就是有關這種這種頁面數據替換的實現措施。
由鏈節信息可以確定頁面序列中的下一個可能的頁面。根據鏈節信息，可識別與該頁面相關的頁解說符，此頁解說符可進入處理器。處理器在現有技術的軟體控制下來檢驗頁解說符中的狀態信號值，並根據此信號值來確定該頁面中的數據是否可予替換。例如，一個經常採用的狀態信號，它涉及數據置換的最佳決策經驗，以置換那些目前最少會用到的數據。為了實現這種針對目前最少應用情況的策備，必然在處理過程中要付出難以承受的額外代價。典型的做法是按照予定的過程，將「用過的數據」信號移到別處，而當要用到與某一頁面有關的該數據時，再將此「用過的數據」置入頁解說符。在這種情況下，軟體過程可以確定該數據已經在某一既定的時間周期內被用過。
此外，與頁面相關的還有其它狀態信號。由於狀態信號的多樣性，因而對相關數據組的置換作出決定的軟體過程也可能複雜化，需要進行數量相當可觀的處理操作。
當控制數據處理系統工作的程序所需要的信號組沒有存儲在主存儲器中時，則要調用置換算法。在現有技術中，此置換算法是由軟體處理來完成，這時需要對數個狀態信號加以分析。在確定欲置換的頁面數據時，要停止對該頁解說符的訪問，以防止所應用的數據在此過程中發生變化。一種防止在此訪問期間使數據發生變化的技術就是給該存儲器的部分存儲裝置設置存儲「閉鎖」，這種存儲器的閉鎖阻止了對主存或其它被選定部分的訪問。這種技術對保證處理器所用的數據的正確是有效的，但由於軟體置換算法的執行速度較慢，因而可能嚴重影響整個數據處理系統的運行性能。(正如這一技術領域：
的專業技術人員將清楚地看到，這種存儲閉鎖一般要涉及到很多存儲區域，因而既使並沒有對某一正在作置換算法分析的存儲地址進行訪問，也會影響其運行性能。)為了消除執行置換算法期間主存儲器的限制部分，採取了可以在進行置換時無需部分限制主存的措施。根據這種技術，在對某一存儲地址進行了置換頁面的選擇之後，即確定在執行該置換算法期間其頁面標題的狀態信號有否發生變化，但這種技術方案使得數據處理系統更加複雜化。
因此，需要一種能確定存儲器中的現存數據被數據處理系統所要求的新的數據所置換的適宜的存儲地址的技術。
本發明的一個目的是提供一個較完善的數據處理系統。
本發明的另一個目的是提出一種按照以與一組數據相關的狀態數據為基礎的予定標準，在數據處理系統的主存儲器中進行該數據組置換的技術。
本發明的另一個目的是提供一種分析法或者一組狀態信號，而無需應用軟體過程來進行分析。
按照本發明，上述的以及其它的目的的實現是依賴於給數據處理系統提供一個指令，此指令將根據原先的狀態信號而產生新的狀態信號，同時保證對主存單元的影響減到最小的程度。在一個頁面置換過程期間，就將下一個與欲檢驗其置換可行性的頁面相關的解說符傳送給處理器。與該指令的執行相關聯的是，其置換驗定算法是一個作為結果狀態信號值的表。頁解說符的狀態信息被用來在此指令表中選取一個合適的表值。被選出的結果狀態信號指明其相應的頁面數據是否應被置換，並且此選出的狀態信號也被用來指定處理器所需的其它操作。所選出的狀態信號被存放在解說符及主存儲器中。參照附圖閱讀了下面的說明後將會領略本發明的上述及其它特點。
附圖的簡介圖1為可採用本發明的數據處理系統的方框圖;
圖2為將主存儲器分成多個存儲單元組的示意圖;
圖3a為說明頁面解說符表與頁表之間關係的示意圖;圖3b是說明頁解說符中畢特位的分配位置;圖3c說明頁解說符中狀態信號的標誌;
圖4為替換指令的畢特位的位置圖;
圖5a說明轉換表中的表值;圖5b為該轉換表的應用舉例;
圖6為執行替換指令的執行單元中的裝置的方框圖;
圖7為說明由軟體過程來實現替換指令的流程圖;
圖8是說明為限制訪問而將主存儲器劃分成區段的情況。
現在參照圖1來說明一個應用本發明的數據處理系統。該數據處理系統包括至少一個處理器(圖中的處理器10和11)，一個主存儲器15，至少一個外圍接口裝置(圖中的外圍接口裝置12和13)以及系統總線19。在圖1表示的數據處理系統中，主存儲器存儲了處理器要處理的數據信號。在系統初始化時，主存儲器15中，主存儲器的存儲空間被分成多個區域，每一區域存儲一個予先設定的邏輯信號值。此外，主存儲器中還有一定的區域留給文件，這些文件可以被處理器訪問。對於多個處理器使用一個共用的主存儲器的系統稱為「緊密耦合」系統。
現在參照圖2以圖示方式來說明主存儲器的編排方法。一般是在數據處理系統初始化期間來建立這一編排格式。區段21通常留給作業系統、程序以及數據處理系統所需的表格用。主存儲器的其餘存儲單元被分成一些被稱之為頁面的主存單元組。圖2中示出了第1號到第Q號頁面。顯然，圖2所示的是主存儲器存儲單元配置的一種理想狀態。一般說來，區域21將被分別擴散到整個主存裝置中，頁面的編號是任意的，最好它僅指定主存裝置中的一個物理地址。
下面參照圖3a、3b和3c來說明對本發明來說特別重要的表的一種編排方式。在圖2中，是在數據處理系統初始化期間來建立一個頁面解說符31的。每一頁面解說符與圖2所示的頁面23到23中的一個相關聯。頁面解說符的目的(如同它與本發明的系統)是為了識別目前存儲在相應頁面中數據的物理地址。這一任務是藉助指向頁表34以及特別是指向與目前存儲在頁面中的數據相關的頁解說符35的一個指針來完成的。此頁面解說符還包括一組說明該頁面相對其它頁面間的順序的存儲地址。當一頁面中的數據被置換時，實現頁面間序列化的鏈節保證在具有剛被替換的數據的頁面被檢驗之前，主存儲器中其它所有頁面要先被檢驗。圖3b表示了圖3a中所示的頁解說符35的結構。頁解說符包括有處在0-3畢特位置上的狀態信號37和處在4-23畢特位置的識別頁面的頁面號。圖3c揭示了最佳實施方案中的狀態位的識別。
其中第一位是有效位，指明當數據頁存於主存儲器中的一頁面中時，該頁面中的數據。第二位是應用位，在每次相應的頁面中的數據被訪問時即被置1。第三位是變更位，表示該頁面的數據與從該頁面提取的數據之間的差別。第4位的狀態位現在留著將來再解釋。
圖4為執行置換算法的指令的結構。第一個16畢特標明指令操作碼。第二個16畢特以及可能附加的16畢特數據信號組提供頁面解說符指針。最後的四組16畢特容納轉換表。
圖5a表示按最佳實施方案實現的轉換表表值。該表值以16進位數表示。實際的轉換如圖5b所示，它表明頁解說符的狀態信號是如何被置換算法所變更。
下面以圖6來說明執行該指令的裝置，在一處理器的執行機構中，指令寄存器61裝有指令操作碼所確定的數據信號。指令寄存器中的這些數據信號被送至解碼和控制裝置62。解碼和控制裝置又將這些信號送至尋址裝置63。在解碼及控制裝置62的控制下，檢索到並存儲在工作寄存器60中的寄存器64的頁解說符的狀態信號被用作為尋址信號，對與指令有關的轉換表尋址。由該狀態信號通過尋址裝置63所找到的表值給出將被存放在頁解說符中的新的狀態信號。信號分析單元66被用來指明已識別出一置換頁面，並啟動存儲該頁面中所需的信息頁的程序。
圖7為用於對頁解說符進行識別以確定有關頁面是否予以替換的流程圖。例如，如要執行圖4中所述的指令，在步驟700程序開始後，就選擇了下一頁解說符。這一選擇是由圖3a所示的鏈節存儲單元34來確定的。在最佳實施例中，鏈節選定不必經置換算法檢驗的頁解說符。對需進行檢驗的頁解說符的選擇，在步驟702由主存儲器檢索出構成該頁解說符部分內容的狀態信號。步驟703進行有效位信號分析，如果此有效位信號為負值，那麼在步驟704中該頁解說符不變化，並且程序回到步驟701以選取下一頁解說符。當此有效位信號是正值時，在步驟705應用信號被檢驗。當檢驗出該應用信號為正值時，在步驟706，其應用比特位位置變為負值，此新狀態信號被存放到主存儲器中適當的頁解說符位置，然後程序回到步驟701去選擇下一個欲檢驗的解說符，當應用信號為負值時，則在步驟707對修改後的狀態信號進行檢驗，當被修改後的狀態信號是正值時，則在步驟708，修改過的畢特位變為負值，同時發出指令將此數據送入與得出該頁面數據的數據相一致的頁面中。如果修改後的狀態信號是負值，則相應的頁面就是適於替換的頁面。步驟709將狀態信號全部變為負值，並將這些值存放到頁解說符中的恰當位置。該頁解說符變為無效，頁面中的數據為所需數據頁所置換。該頁解說符通過步驟710被修改來表示存儲在該頁面中的新數據。頁解說符在頁面順序中的置換通過頁面解說符中的鏈節和頁面中的數據的置換就完成了，即步驟711。
再參照圖8，在最佳實施方案中，主存儲器由A、B兩個控制器來控制。每一個存儲控制器控制一半存儲單元。在每一個控制器中，有關存儲單元區域都被分為多個區段83。對每個區段的訪問可由相應的存儲控制器來控制。因此，例如當某一個存儲單元正處於變更過程時，控制器即可阻止對該特定區段的訪問而不必限制對與該存儲控制器相應的整個區域的訪問。由於成本和複雜的原因，對單個存儲區域的訪問控制則很少採用。由於這個原因，限制對某一特定存儲單元的訪問導致了要限制對多個存儲單元的訪問，而任何對訪問的限制都會對數據處理系統的性能帶來潛在的影響。
本發明提出了一種確定頁替換算法的有效辦法來解決處理器在存儲單元的內容有可能變化時對主存儲器進行訪問的問題。這時，在執行該算法時保留的主存部分只保留一段較為短暫的時間，藉此來使得對數據處理系統的影響減至最小的程度。它與可能長時間限制對主存部分區段的訪問的軟體過程不同，一頁面是否適於置換是依靠一個指令來決定的，此指令中與該頁面相關的狀態信號被用來確定一個表的入口地址信號，此表與該指令相關聯，該指令的入口可在相當短的時間內被確定。這些新的或最終得出的狀態信號可以及時存放到頁解說符中。因為這個新的狀態信號禁止相應的頁面被利用，因此可以不再採用限制對包含有該頁面解說符的主存區段訪問的存儲器結構。這一過程所需的時間很短，從而大大減小了對主存儲器可達性的影響，也就大大減小了對數據處理系統的性能的影響。
在軟體過程中完成一種算法的重要特點在於過程的靈活性。例如，如果希望對一狀態信號作不同的說明，可對此過程的步驟作相應的改變，就可達到改變其說明的效果。可清楚地看到，在本發明中由於一組狀態信號指向該指令的區域，因而仍保留了上述的靈活性。藉助改變信號組合，就可維持其靈活性。
上述的說明用以說明該最佳實施方案的運行，這並不限制本發明的範圍。本發明的範圍僅由下面的權利要求
來限定。根據前面的討論，熟悉本技術領域：
的人員將會很容易地想到許多屬於本發明主題範圍內的方案。
權利要求
1.一個數據處理系統，其中的多個存儲單元的每一個都具有與之相關聯的多個狀態信號，用來對所說的狀態信號進行一種算法處理而確定獲得的新的狀態信號的裝置包括一個用於執行所說的算法的指令，該指令中存儲有所說的新的狀態信號；一個用於存放所說的狀態信號的第一存儲單元；一個用於所說的新的狀態信號於一個表中的第二存儲單元；和尋址裝置，響應於所說的指令，利用所說的被存儲的狀態信號來對所說的表結構中的項進行尋址，一種所說的被存儲的狀態信號和所說的實現所說算法的表結構項目之間的關係。
2.用於確定權利要求
1的新狀態信號的裝置，其中所說的狀態信號與一數據的頁面相對應，所說的算法判別何時一數據頁面可用一新的數據頁面來置換。
3.用於確定權利要求
2的新狀態信號的裝置，進一步還包括按照所選取的新的狀態信號來以一新的數據頁面置換與所說的被存儲的狀態信號相關的所說的數據頁面的裝置。
4.用於確定權利要求
2的新狀態信號的裝置，其中第一個所說的狀態信號涉及所說的相應的數據頁面的應用，第二個所說的狀態信號涉及所說的相應的數據頁面的修改。
5.在一數據處理系統中，一個確定所說的數據系統的主存儲器何時進行頁面置換的方法，包括有下列步驟由主存儲中檢索第一指令執行所說的置換決定，所說的第一指令具有一組與之相關的狀態信號;將所說的第一指令狀態信號組存入一個表中;檢索出一個與所選頁面相關的頁解說符;利用與所說的頁解說符相關的狀態信號來訪問所說的指令狀態信號表中的一項;和判別何時所說的被訪問的指令狀態信號組指出所說的相應頁面可以置換。
6.確定何時置換頁面的方法的權利要求
5，進一步還包括以所說的解說符中的所說的指令表值來置換所說的狀態信號的步驟。
7.確定何時置換頁面的方法的權利要求
5，進一步還包括當所檢索的頁解說符不適於置換時，檢索一個在最長的時間間隔內來檢驗其置換性的解說符的步驟。
8.確定何時置換頁面的方法的權利要求
5，進一步還包括將所說的狀態信號與所說的頁面的應用，正確性和變更相關聯的步驟。
9.一個具有將數據存儲在主存儲器中的頁面的數據處理系統，其中在一處理器中用來確定何時一頁數據信號何時能被置換的裝置包括有與所說處理器相關聯的用於檢索一個指令的檢索裝置，所說的指令包含有許多項，其中所說的許多項被存放在所說的處理器中，所說的檢索裝置至少檢索一與所說的數據信號頁之一相關的解說符的一個予定欄位，其中所說的解說符的予定欄位被存放在所說的處理器中;尋址裝置，按照所說的存儲的予定欄位來選擇解說符的欄位來組成一地址欄位，所說的尋址裝置是利用所說的地址欄位來尋找一予定的項目，所說的予定項目為一置換解說符欄位;和判定裝置，用來按照所說的置換欄位的內容給所說的處理器提供一指明何時一數據信號頁可被置換的信號。
10.權利要求
9中的頁置換裝置進一步包括有將所說解說符中的置換欄位存儲到主存儲器的裝置。
11.權利要求
9的頁置換裝置，其中所說的檢索裝置在當所說的判定裝置指明該頁面欄位不能被置換時，至少檢索一個下一個解說符的一個予定欄位。
12.權利要求
11的頁置換裝置，其中所說的下一個解說符是指已經在最長的時間間隔內沒有一個所說的欄位被置換的解說符。
13.權利要求
9中的頁置換裝置，其中至少一個所說的欄位包含有多個狀態信號，所說的狀態信號中的一個表示所說的數據信號頁的應用。
14.權利要求
10中的頁置換裝置，其中所說的存放所說的解說符的主存儲器的部分，在指令作用期間不能被所說的數據處理系統的其餘部分利用。
15.在一數據處理系統中，一個用於使處理器確定一被選的頁面能否被置換而無需軟體程序作用的指令包括一個第一欄位;一個第二欄位，所說的第一欄位使得該處理器檢索並存儲至少一個與所說頁面相關解說符的第一欄位，一個被所說的第二欄位指明的所說解說符的存放區域;和一個含有多項的第三欄位，所說的第三欄位存放在所說的處理器中，所說的第一欄位使得所說的處理器選擇指令項目的一個，所說的被選擇的指令項目確定何時所說的相應頁面應被置換。
16.權利要求
15中的確定頁面置換的指令，其中所說的被選擇的指令項目為一置換所說的第一解說符字符的置換欄位，所說的置換欄位和所說的解說符一起被存放在所說的主存儲器中。
17.權利要求
15的確定頁面置換的指令，其中所說的第一解說符欄位包括有多個指明頁面狀態的邏輯信號。
18.權利要求
17的確定頁面置換的指令，其中所說的狀態信號可指明所說頁面中數據的正確性，可指明所說頁面的應用，並可指明所說頁面的修改。
19.權利要求
15的確定頁面置換的指令，其中所說的指令項目被存放在一存儲機構中，所說的第一欄位使得所說的處理器根據所說的第一解說符欄位中的邏輯信號來選擇所說的存儲機構中的一個地址。
專利摘要
在一預採用虛擬地址的多處理器，多程序的數據處理系統中，提供以一種用於在主存儲器中選擇一待被處理器所要求的邏輯信號組成的新頁所置換的頁面的裝置和方法。本發明提供了一個單指令提供，即利用包含在一個頁解說符中的狀態信號以在一個綜合狀態信號表中的一個表值進行導址。利用該狀態信號與該表中的表值間的關係來完成這一算法。
文檔編號G06F12/12GK87104487SQ87104487
公開日1988年2月17日 申請日期1987年5月30日
發明者維克託·M·莫爾甘蒂, 詹姆斯·B·蓋耶 申請人:霍尼韋爾資料系統有限公司導出引文BiBTeX, EndNote, RefMan