Pamięć skojarzeniowa człowieka. Pamięć skojarzeniowa

V pamięć skojarzeniowa elementy są wybierane nie według adresu, ale według treści. Wyjaśnijmy dokładniej ostatnią koncepcję. W przypadku pamięci z organizacją adresu wprowadzono koncepcję minimalna jednostka adresowalna(MAE) jako fragment danych z indywidualnym adresem. Przedstawmy podobną koncepcję dla pamięć skojarzeniowa, a ta minimalna jednostka pamięci będzie pamięć skojarzeniowa połączenie asocjacyjny ciąg pamięci(Pasek). Każdy StrAP zawiera dwa pola: pole znacznika (znacznik angielski - znacznik, etykieta, atrybut) oraz pole danych. Żądanie odczytu do pamięci asocjacyjnej w słowach można wyrazić w następujący sposób: wybierz wiersz (linie), w którym (w którym) tag jest równy określonej wartości.

Szczególnie zwracamy uwagę, że przy takim zapytaniu możliwy jest jeden z trzech wyników:

1. jest dokładnie jedna linia z podanym tagiem;
2. istnieje wiele linii z określonym znacznikiem;
3. nie ma linii o podanym tagu.

Wyszukiwanie rekordu według atrybutu jest typową czynnością w dostępie do bazy danych, a wyszukiwanie w bazie danych jest często określane jako wyszukiwanie asocjacyjne. Aby przeprowadzić takie wyszukiwanie, musisz wyświetlić wszystkie rekordy i porównać określony znacznik ze znacznikiem każdego rekordu. Można to zrobić, używając do przechowywania rekordów zwykłej pamięci adresowalnej (a jest jasne, że zajmie to dużo czasu - proporcjonalnie do liczby przechowywanych rekordów!). O pamięć skojarzeniowa mówią, kiedy asocjacyjne pobieranie danych z pamięci jest obsługiwane przez sprzęt. Podczas zapisywania do pamięci asocjacyjnej element danych jest umieszczany w StrAP wraz ze znacznikiem właściwym dla tego elementu. W tym celu możesz użyć dowolnego darmowego StrAP. Rozważ odmiany strukturalnej organizacji pamięci podręcznej lub metod wyświetlania pamięć o dostępie swobodnym w pamięci podręcznej.

W pełni asocjacyjna pamięć podręczna

Schemat w pełni asocjacyjnej pamięci podręcznej pokazano na rysunku (patrz rysunek poniżej).

Opiszmy algorytm systemu z pamięcią podręczną. Na początku pracy pamięć podręczna jest pusta. Kiedy podczas próbkowania wykonywane jest pierwsze polecenie, jego kod, a także kilka kolejnych sąsiednich bajtów kod programu, - zostanie przeniesiony (powoli) do jednej z linii pamięci podręcznej, a jednocześnie górna część adresu zostanie zapisana do odpowiedniego znacznika. W ten sposób wypełniana jest linia pamięci podręcznej.

Jeśli kolejne selekcje są możliwe z tego obszaru, zostaną one wykonane już z CACHE (szybko) - "CACHE-hit". Jeśli się okaże, że pożądany przedmiot w pamięci podręcznej nie ma pamięci podręcznej, - "CASH-miss". W takim przypadku następuje dostęp do pamięci RAM (powoli), a jednocześnie zapełniana jest kolejna linia pamięci podręcznej.

W pełni asocjacyjny obwód pamięci podręcznej

Dostęp do pamięci podręcznej jest następujący. Po utworzeniu adresu wykonawczego jego bity wyższego rzędu, które tworzą znacznik, są sprzętowe (szybkie) i są jednocześnie porównywane ze znacznikami wszystkich linii pamięci podręcznej. W tym przypadku możliwe są tylko dwie sytuacje z trzech wymienionych wcześniej: albo wszystkie porównania dadzą wynik negatywny (chyba w pamięci podręcznej), albo pozytywny wynik porównania zostanie zarejestrowany dokładnie dla jednej linii (trafienie w pamięci podręcznej).

Podczas odczytu, jeśli zarejestrowane zostanie trafienie w pamięci podręcznej, dolne bity adresu określają pozycję w linii pamięci podręcznej, z której należy wybrać bajty, a typ operacji określa liczbę bajtów. Oczywiście, jeśli długość elementu danych przekracza jeden bajt, to możliwe są sytuacje, gdy ten element (w częściach) znajduje się w dwóch (lub więcej) różnych wierszach pamięci podręcznej, wtedy czas na pobranie takiego elementu wydłuży się. Można temu przeciwdziałać, wyrównując operandy i instrukcje wzdłuż granic linii pamięci podręcznej, co jest brane pod uwagę przy opracowywaniu translatorów optymalizujących lub podczas ręcznej optymalizacji kodu.

W przypadku braku pamięci podręcznej i braku wolnych wierszy w CACHE, należy zastąpić jedną linię w CACHE inną linią.

Głównym celem strategii zastępowania jest zachowanie w pamięci podręcznej linii, do których najprawdopodobniej będzie można uzyskać dostęp w najbliższej przyszłości, oraz zastąpienie linii, do których dostęp będzie możliwy później lub wcale. Oczywiście optymalnym algorytmem będzie ten, który zastąpi wiersz, do którego uzyskamy dostęp w przyszłości, niż jakikolwiek inny wiersz CACHE.

Niestety taka prognoza jest praktycznie niewykonalna i trzeba używać algorytmów gorszych od optymalnego. Niezależnie od zastosowanego algorytmu zastępczego, musi on zostać zaimplementowany sprzętowo, aby osiągnąć dużą prędkość.

Wśród wielu możliwych algorytmów zastępczych, najczęstsze są cztery, rozpatrywane w kolejności malejącej względnej wydajności. Każdy z nich można zastosować w w pełni asocjacyjnej pamięci podręcznej.

Najbardziej wydajny jest algorytm zastępowania oparty na najstarszym użyciu ( LRU — najrzadziej używany ), która zastępuje linię CACHE, do której nie korzystano najdłużej. Badania wykazały, że algorytm patrzenia wstecz LRU działa dość dobrze w porównaniu z optymalnym algorytmem patrzenia w przyszłość.

Najbardziej znane są dwie metody sprzętowej implementacji tego algorytmu. W pierwszym licznik jest powiązany z każdą linią pamięci podręcznej. W regularnych odstępach czasu do zawartości wszystkich liczników dodawana jest jednostka. Po uzyskaniu dostępu do wiersza jego licznik jest resetowany do zera. W ten sposób największa liczba będzie w liczniku wiersza, do którego nie był używany najdłużej, a ten wiersz jest pierwszym kandydatem do zastąpienia.

Druga metoda jest zaimplementowana za pomocą kolejki, w której w kolejności wypełniania wierszy pamięci podręcznej wprowadzane są odniesienia do tych wierszy. Za każdym razem, gdy uzyskuje się dostęp do wiersza, łącze do niego jest przenoszone na koniec kolejki. W rezultacie za każdym razem jako pierwszy w kolejce znajduje się link do wiersza, do którego nie korzystano najdłużej. To właśnie ta linia jest wymieniana przede wszystkim.

Innym możliwym algorytmem zastępczym jest pierwsze weszło, pierwsze wyszło ( FIFO – pierwszy wszedł pierwszy wyszedł ). Tutaj zastępowany jest ciąg, który najdłużej znajdował się w pamięci podręcznej. Algorytm można łatwo zaimplementować za pomocą wcześniej rozważanej kolejki, z tą tylko różnicą, że po uzyskaniu dostępu do ciągu, pozycja odpowiedniego łącza w kolejce nie zmienia się.

Innym algorytmem jest zastąpienie najrzadziej używanego ciągu znaków (LFU - Least Frequency Used). Linia w pamięci CACHE jest zastępowana najmniejszą liczbą dostępów. Zasadę można zrealizować, przyporządkowując każdemu wierszowi licznik trafień, do którego zawartości dodawany jest jeden po każdym trafieniu. Głównym pretendentem do zamiany jest łańcuch, którego licznik zawiera najmniejszą liczbę.

Najprostszym algorytmem jest arbitralny wybór ciągu do zamiany. Ciąg do zastąpienia jest wybierany losowo. Można to zrealizować np. za pomocą licznika, którego zawartość zwiększa się o jeden z każdym impulsem zegarowym, niezależnie od tego, czy nastąpiło trafienie, czy chybienie. Wartość w liczniku identyfikuje ciąg do zastąpienia.

Oprócz znacznika i bajtów danych, w linii pamięci podręcznej mogą znajdować się dodatkowe pola usług, wśród których przede wszystkim powinien znajdować się bit ważności V (od valid - valid) oraz bit modyfikacji M (od modyfikacji - zmiana, modyfikacja). odnotowany. Gdy następna linia pamięci podręcznej jest wypełniona, V jest ustawiony na stan „prawidłowy”, a M - na stan „niezmodyfikowany”. Jeżeli podczas wykonywania programu zawartość tej linii została zmieniona, to bit M jest przełączany, sygnalizując, że przy wymianie tej linii należy przepisać jej zawartość do pamięci RAM. Jeśli z jakiegoś powodu zmieniła się kopia elementu tego ciągu, przechowywana w innym miejscu (na przykład w pamięci RAM), bit V. do głównej pamięci RAM. Dodatkowo pole usługi może zawierać bity wspierające algorytm LRU.

Szacowanie objętości sprzętu

Typowy rozmiar pamięci podręcznej w nowoczesny system- 8 ... 1024 kbajtów, a długość linii pamięci podręcznej wynosi 4 ... 32 bajty. Dalsza ocena dotyczy pamięci podręcznej 256KB i długości linii 32B, co jest typowe dla systemów z procesorami Pentium i PentiumPro. W tym przypadku długość tagu wynosi 27 bitów, a liczba linii w pamięci podręcznej wyniesie 256K / 32 = 8192. Jest to dokładnie liczba cyfrowych komparatorów kodów 27-bitowych potrzebnych do realizacji powyższej struktury.

Przybliżony szacunek kosztów sprzętu do budowy komparatora cyfrowego daje wartość 10 trans/bit, a całkowita liczba tranzystorów tylko w jednostce komparatora będzie równa:

10*27*8192 = 2 211 840,

czyli około półtora raza mniej niż całkowita liczba tranzystorów w krysztale Pentium. Jest więc jasne, że opisana struktura w pełni asocjacyjnej pamięci CACHE () jest możliwa do zrealizowania tylko przy niewielkiej liczbie wierszy w CACHE, tj. z małym rozmiarem pamięci podręcznej (praktycznie nie więcej niż 32 ... 64 wiersze). Większa pamięć podręczna jest zbudowana według innej struktury.

wielopoziomowa tabela stron wymaga kilku dostępów do pamięci głównej, dlatego zajmuje dużo czasu. W niektórych przypadkach opóźnienie to jest niedopuszczalne. Problem przyspieszenia wyszukiwania rozwiązywany jest na poziomie architektury komputera.

Ze względu na właściwość lokalności większość programów przez pewien czas uzyskuje dostęp do niewielkiej liczby stron, więc tylko niewielka część tabeli stron jest aktywnie wykorzystywana.

Naturalnym rozwiązaniem problemu akceleracji jest wyposażenie komputera w sprzętowe urządzenie do mapowania stron wirtualnych na fizyczne bez dostępu do tablicy stron, czyli posiadanie małej, szybkiej pamięci podręcznej przechowującej niezbędne ten moment część tabeli stron. To urządzenie nazywa się pamięć skojarzeniowa, czasami używany jest termin translacyjny bufor podręczny (TLB).

Jeden wpis w tabeli w pamięć skojarzeniowa(jedno wejście) zawiera informacje o jednej wirtualnej stronie: jej atrybutach oraz ramce, w której się znajduje. Pola te odpowiadają dokładnie polom w tabeli strony.

Ponieważ pamięć skojarzeniowa zawiera tylko niektóre wpisy tabeli strony, każdy wpis TLB musi zawierać pole ponumerowane strona wirtualna... Pamięć nazywa się asocjacyjną, ponieważ jednocześnie porównuje liczbę wyświetlanych strona wirtualna z pasującym polem we wszystkich rzędach tego małego stolika. Dlatego dany widok pamięć jest dość droga. W linii, pole strona wirtualna który pokrywa się z żądaną wartością, zostanie znaleziony numer ramki strony. Typowe wpisy TLB od 8 do 4096. Wzrost liczby wpisów w pamięć skojarzeniowa należy to zrobić biorąc pod uwagę takie czynniki, jak rozmiar pamięci podręcznej pamięci głównej i liczba dostępów do pamięci na instrukcję.

Rozważ działanie menedżera pamięci w obecności pamięć skojarzeniowa.

Informacje o pierwszym wyświetleniu strona wirtualna w fizyczności jest poszukiwany w pamięć skojarzeniowa... Jeśli wymagany wpis zostanie znaleziony, wszystko jest w porządku, z wyjątkiem przypadków naruszenia uprawnień, gdy żądanie dostępu do pamięci jest odrzucane.

Jeśli żądany wpis w pamięć skojarzeniowa nie ma, wyświetlanie odbywa się poprzez tabelę stron. Jeden z wpisów w pamięć skojarzeniowa znaleziono rekord z tabeli stron. Tutaj mamy do czynienia z problemem zastępowania, który jest tradycyjny dla każdej pamięci podręcznej (a mianowicie, które z wpisów w pamięci podręcznej należy zmienić). Projekt pamięć skojarzeniowa powinni uporządkować zapisy w taki sposób, aby można było podjąć decyzję, który ze starych zapisów powinien zostać usunięty po utworzeniu nowych.

Liczba udanych wyszukiwań numeru strony w pamięć skojarzeniowa w stosunku do całkowitej liczby wyszukiwań nazywany jest współczynnikiem trafień (dopasowania) (proporcja, współczynnik). Czasami używany jest również termin „procent trafień w pamięci podręcznej”. Tak więc współczynnik trafień jest częścią linków, które można utworzyć za pomocą pamięć skojarzeniowa... Dostęp do tych samych stron zwiększa współczynnik trafień. Im wyższy współczynnik trafień, tym krótszy średni czas dostępu do danych w pamięci RAM.

Załóżmy, na przykład, że określenie adresu w przypadku braku pamięci podręcznej w tabeli stron i określenie adresu w przypadku trafienia pamięci podręcznej zajmuje 100 ns. pamięć skojarzeniowa- 20 ns. Przy 90% współczynniku trafień średni czas określania adresu wynosi 0,9x20 + 0,1x100 = 28 ns.

Całkiem akceptowalna wydajność współczesnego systemu operacyjnego świadczy o efektywności użytkowania pamięć skojarzeniowa... Wysokie prawdopodobieństwo znalezienia danych w pamięć skojarzeniowa związane z obecnością tych obiektywnych właściwości: lokalizacji przestrzennej i czasowej.

Należy zwrócić uwagę na następujący fakt. Przy zmianie kontekstu procesów należy zadbać o to, aby nowy proces nie „widział” w pamięć skojarzeniowa informacje związane z poprzednim procesem, takie jak jego wyczyszczenie. Więc używając pamięć skojarzeniowa wydłuża czas przełączania kontekstu.

Rozważany dwupoziomowy ( pamięć skojarzeniowa+ tabela stron) schemat translacji adresów to lśniący przykład hierarchia pamięci oparta na zasadzie lokalności, o której była mowa we wstępie do poprzedniego wykładu.

Odwrócona tabela stron

Pomimo wielopoziomowej organizacji przechowywanie wielu dużych tabel stron nadal stanowi problem. Jego znaczenie jest szczególnie istotne w przypadku architektur 64-bitowych, gdzie liczba stron wirtualnych jest bardzo duża. Rozwiązaniem jest użycie odwrócona tabela stron(odwrócona tabela stron). To podejście jest stosowane na maszynach PowerPC, niektórych stacjach roboczych Hewlett-Packard, IBM RT, IBM AS/400 i kilku innych.

Ta tabela zawiera jeden wpis dla każdej ramki strony. Pamięć fizyczna... Istotne jest, aby dla wszystkich procesów wystarczyła jedna tabela. Dlatego do przechowywania funkcji wyświetlania wymagana jest stała część pamięci głównej, niezależnie od architektury bitowej, rozmiaru i liczby procesów.

Pomimo oszczędności w pamięci RAM, użycie odwrócony stół ma znaczną wadę - wpisy w nim zawarte (jak w pamięć skojarzeniowa) nie są sortowane rosnąco według numerów stron wirtualnych, co komplikuje tłumaczenie adresu. Jednym ze sposobów rozwiązania tego problemu jest użycie tablicy mieszającej. wirtualne adresy... Ponadto część adres wirtualny reprezentujący numer strony jest mapowany do tablicy mieszającej za pomocą funkcji mieszającej. Każda strona pamięci fizycznej odpowiada tutaj jednemu wpisowi w tablicy mieszającej i odwrócona tabela stron. Adresy wirtualne które mają tę samą wartość skrótu, są ze sobą połączone. Zwykle długość łańcucha nie przekracza dwóch rekordów.

Rozmiar strony

Projektanci systemów operacyjnych dla istniejących maszyn rzadko mają możliwość wpływania na rozmiar strony. Jednak na re komputery tworzone decyzja dotycząca optymalnego rozmiaru strony jest istotna. Jak można się spodziewać, nie ma jednego najlepszego rozmiaru. Istnieje raczej zestaw czynników, które wpływają na rozmiar. Zazwyczaj rozmiar strony jest potęgą dwójki od 2 9 do 2 14 bajtów.

Pamięć skojarzeniowa

Nazwa parametru	Oznaczający
Temat artykułu:	Pamięć skojarzeniowa
Kategoria (kategoria tematyczna)	Komputery

Tabela stron

Organizacja tabeli stron jest jednym z kluczowych elementów mechanizmów konwersji strony i segmentu na stronę. Rozważmy bardziej szczegółowo strukturę tabeli stron.

Tak więc adres wirtualny składa się z wirtualnego numeru strony (bity wyższego rzędu) i przesunięcia (bity niższego rzędu). Numer strony wirtualnej jest używany jako indeks w tablicy stron, aby znaleźć wpis dla strony wirtualnej. Z tego wpisu w tablicy stron znajduje się numer ramki strony, następnie dodawane jest przesunięcie i tworzony jest adres fizyczny. Ponadto wpis w tabeli strony zawiera informacje o atrybutach strony, w szczególności o bitach bezpieczeństwa.

Głównym problemem efektywnej implementacji tablicy stron jest duży rozmiar wirtualnych przestrzeni adresowych. nowoczesne komputery, które są zwykle określane przez bitowość architektury procesora. Najpopularniejsze są dziś procesory 32-bitowe, które pozwalają na tworzenie wirtualnych przestrzeni adresowych o wielkości 4 GB (dla komputerów 64-bitowych wartość ta wynosi 2**64b).

Obliczmy przybliżony rozmiar tabeli stron. W 32-bitowej przestrzeni adresowej o rozmiarze strony 4K (Intel) otrzymujemy 1M stron, a w 64-bitowej nawet więcej. To. tabela musi mieć 1M wierszy (wejście), a wpis w wierszu składa się z kilku bajtów. Zauważ, że każdy proces potrzebuje własnej tabeli stron (aw przypadku schematu segment-strona, po jednej dla każdego segmentu). Tak więc w tym przypadku tabela stron musi być zbyt duża.

Jednak wyświetlacz powinien być szybki. Mapowanie powinno być szybkie, ponieważ odbywa się przy każdym dostępie do pamięci, ĸᴏᴛᴏᴩᴏᴇ dzieje się w prawie każdej instrukcji maszynowej. Problem ten rozwiązywany jest głównie poprzez implementację pamięci skojarzeniowej.

W celu uniknięcia kluczowego znaczenia posiadania ogromnej tabeli w pamięci przez cały czas i przechowywania tylko kilku jej fragmentów (jest to znowu możliwe w oparciu o właściwość locality), wiele komputerów używa wielopoziomowej tabeli stron.

Rozważ przykład modelu (rysunek 10.4). Załóżmy, że 32-bitowy adres jest podzielony na 10-bitowe pole Ptr1, 10-bitowe pole Ptr2 i 12-bitowe przesunięcie. Przesunięcie 12-bitowe pozwala zlokalizować bajt na stronie 4K (2**12), co daje łącznie 2**20 stron. Jak widać na ryc. 9,4 1024 wierszy w tabeli Najwyższy poziom za pomocą pola Ptr1 odwołują się do 1024 tabel drugiego poziomu, z których każda zawiera również 1024 wierszy. Używając pola Ptr2, każdy wiersz tabeli drugiego poziomu wskazuje konkretną stronę. Celem takiej organizacji jest unikanie ciągłego utrzymywania w pamięci wszystkich tabel drugiego poziomu (a jest ich 1024). Spójrzmy na przykład z okrągłymi liczbami. Załóżmy, że proces wymaga 12M pamięci: 4M na dole pamięci na kod, 4M na dole na dane i 4M na górze pamięci na stos. Między dolną częścią stosu a górną częścią danych znajduje się ogromna przestrzeń 4Gb-12Mb, ĸᴏᴛᴏᴩᴏᴇ niewykorzystana. W tym przypadku potrzebny jest tylko 1 stół najwyższego poziomu i 3 stoły drugiego poziomu. Podejście to naturalnie uogólnia się na trzy lub więcej poziomów tabeli.

Rozważ jeden z wpisów tabeli stron. Jego rozmiar różni się w zależności od systemu, ale najczęstszym przypadkiem są 32 bity. Najważniejszym polem jest numer ramki. Celem stronicowania jest zlokalizowanie tej wartości. Ponadto bit obecności, bity ochrony (na przykład 0 - odczyt / zapis, 1 - tylko do odczytu ...), bity modyfikujące (jeśli są do niego napisane) i bity linków, które pomagają wyróżnić mało używane strony, bity umożliwiające buforowanie. Zauważ, że adresy stron na dysku nie są częścią tablicy stron.

Rysunek 10.4 - Przykład dwupoziomowej tabeli stron.

Jak posiadanie wielu warstw wpływa na wydajność menedżera pamięci? Zakładając, że każdy poziom jest oddzielną tabelą w pamięci, translacja adresów może wymagać wielu dostępów do pamięci.

Liczba poziomów w tabeli stron zależy od konkretnej architektury. Można podać przykłady realizacji stronicowania jednopoziomowego (DEC PDP-11), dwupoziomowego (Intel, DEC VAX), trójpoziomowego (Sun SPARC, DEC Alpha) „a, a także przywoływania” oraz z ustawić liczbę poziomów (Motorola). Procesor MIPS R2000 RISC działa w ogóle bez tablicy stron. Tutaj wyszukiwanie żądanej strony, jeśli ta strona nie znajduje się w pamięci asocjacyjnej, powinno zostać przejęte przez system operacyjny (tzw. stronicowanie zerowego poziomu).

Znalezienie żądanej strony w wielopoziomowej tabeli stron, która wymaga wielokrotnego dostępu do pamięci głównej w drodze do tłumaczenia adresu wirtualnego na adres fizyczny, zajmuje dużo czasu. W wielu przypadkach takie opóźnienie jest niedopuszczalne. Problem ten znajduje również rozwiązanie na poziomie architektury komputera.

Ze względu na lokalizację, większość programów łączy się z niewielką liczbą stron w pewnym okresie czasu, więc tylko niewielka część tabeli stron jest obciążona.

Naturalnym rozwiązaniem jest wyposażenie komputera w urządzenie sprzętowe do mapowania stron wirtualnych na fizyczne bez dostępu do tablicy stron, czyli posiadanie małej, szybkiej pamięci podręcznej przechowującej część tablicy stron, która jest aktualnie potrzebna. To urządzenie jest zwykle nazywane pamięcią asocjacyjną, czasami używa się również określenia rejestry asocjacyjne (czasami bufor translacji (TLB)).

Jeden rekord w tabeli w pamięci asocjacyjnej zawiera informacje o jednej stronie wirtualnej, jej atrybutach oraz ramce, w której się znajduje. Pola te odpowiadają dokładnie polom w tabeli strony.

Mapowanie stron wirtualnych przechowywanych w pamięci asocjacyjnej jest szybkie, ale pamięć podręczna jest droga i ma ograniczony rozmiar.
Opublikowano na ref.rf
Liczba wpisów TLB od 8 do 2048

Przyjęło się nazywać pamięć asocjacyjną, ponieważ w przeciwieństwie do tabeli stron, która jest indeksowana przez wirtualne numery stron, tutaj wirtualny numer strony jest jednocześnie porównywany z odpowiednim polem we wszystkich wierszach tej małej tabeli. Z tego powodu ta pamięć jest droga. Wiersz, którego pole wirtualnej strony pokrywa się z żądaną wartością, zawiera numer ramki strony.

Rozważmy funkcjonowanie menedżera pamięci w obecności pamięci skojarzeniowej. Najpierw szuka strony wirtualnej w pamięci asocjacyjnej. Jeśli strona zostanie znaleziona, wszystko jest w porządku, z wyjątkiem przypadków naruszenia uprawnień, gdy żądanie dostępu do pamięci zostanie odrzucone.

Jeśli strona nie znajduje się w pamięci asocjacyjnej, jest przeszukiwana przez tabelę stron. Jedna ze stron w pamięci asocjacyjnej zostaje zastąpiona znalezioną stroną. W tablicy tak załadowana strona jest oznaczona bitem modyfikacji, który zostanie uwzględniony przy ładowaniu kolejnej pamięci asocjacyjnej z tablicy stron.

Procent przypadków, w których numer strony znajduje się w pamięci asocjacyjnej, jest powszechnie określany jako współczynnik trafień. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, współczynnik trafień - część linków, które powinny być utworzone przy użyciu pamięci asocjacyjnej. Dostęp do tych samych stron zwiększa współczynnik trafień.

Załóżmy na przykład, że 100 ns jest niezbędne do uzyskania dostępu do tablicy stron, a 20 ns do dostępu do pamięci asocjacyjnej. Przy 90% współczynniku trafień średni czas dostępu wynosi 0,9 * 20 + 0,1 * 100 = 28 ns.

Całkiem akceptowalna wydajność nowoczesnych systemów operacyjnych świadczy o efektywności wykorzystania pamięci asocjacyjnej. Wysoka wartość prawdopodobieństwa znalezienia danych w pamięci skojarzeniowej związana jest z obecnością tych obiektywnych właściwości: lokalizacji przestrzennej i czasowej.

Należy zwrócić uwagę na następujący fakt. Podczas przełączania procesów należy upewnić się, że nowy proces nie widzi informacji związanych z poprzednim procesem w pamięci asocjacyjnej, na przykład w celu jego wyczyszczenia. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, użycie pamięci asocjacyjnej wydłuża czas przełączania kontekstów.

Pamięć asocjacyjna - pojęcie i rodzaje. Klasyfikacja i cechy kategorii „Pamięć skojarzeniowa” 2017, 2018.

W eksperymentach skojarzeniowych należy szczególnie podkreślić jedną kwestię, a mianowicie, że warunkiem koniecznym identyfikacji rzetelnego procesu skojarzeniowego jest całkowita bierność podmiotu, maksymalne odłączenie jego woli i myślenia od spontanicznego przepływu idei. W przeciwnym razie zamiast procesu skojarzeniowego otrzymujemy proces aktywnie deterministyczny. Ta okoliczność powinna być szczególnie podkreślona z tego powodu, że rzeczywisty proces skojarzeniowy jest w rzeczywistości procesem spontanicznym, odbywającym się poza działalnością osoby; właśnie w tym charakterze reprezentuje jeden z etapów rozwoju pamięci i jedną z form jej manifestacji. W przypadku pamięci skojarzeniowej mamy do czynienia z pamięcią spontaniczną, spontanicznym procesem mnemonicznym, który nie ma nic wspólnego z pamięcią arbitralną. W tym sensie pamięć skojarzeniowa jest oczywiście bliższa opisanym powyżej prymitywnym formom manifestacji pamięci niż jej specyficznie ludzkim formom.

Spontaniczność tak samo charakteryzuje pamięć skojarzeniową, jak w chwili obecnej zapamiętanie, to jest fiksacja lub zatrzymanie, i wspomnienia, czyli reprodukcje.

Podmiot jest zawsze pod wpływem różnych wrażeń, a często te wrażenia powstają lub znikają niezależnie od jego intencji. Jednak zwykle nie znikają bez śladu. Co prawda te wrażenia nie pozostają na długo w psychice jako przeżycia świadome, ale w samym podmiocie powodują pewne zmiany osobowe. I tak na gruncie tych zmian, gdy powstają odpowiednie warunki, gdy np. jedno z tych wrażeń ponownie zaczyna działać na podmiot, to drugie reaguje zgodnie ze zmianami, które w nim zaszły, czyli doświadczeniami. odpowiadające tej zmianie powstają w jego świadomości.... W ten sposób następuje reprodukcja idei, odczuwana przez podmiot jako produkt oddziaływania spontanicznych wrażeń. Jak widać, reprodukcja tych ostatnich odbywa się również poza aktywną, celową interwencją podmiotu.

Na korzyść tego, że pamięć skojarzeniowa powinna być wyraźnie odróżniona od pamięci arbitralnej, świadczy również fakt, że reprodukcja reprezentacji skojarzeniowych powstaje zawsze tylko pod wpływem jakiegoś drugiego doświadczenia – reprezentacji percepcyjnej. Irytująca reprezentacja lub percepcja są niezbędne do powstania reprezentacji asocjacyjnej. Okoliczność ta dość dobrze charakteryzuje pamięć skojarzeniową jako wciąż niską, zależną formę działania pamięciowego. V ten sens jest bardzo bliska rozpoznania.

Rozpoznanie, jak już wiemy, przebiega następująco: percepcji N. towarzyszy zawsze poczucie zażyłości. Poznałem N., widziałem go. Jeśli jednak doda się do tego jakieś przedstawienie, np. widziałem N. tam i tam (obraz miejsca) lub był w takim a takim kapeluszu (obraz kapelusza), to już mamy do czynienia z pamięć skojarzeniowa, czyli percepcja N. powoduje reprodukcję przedstawień. W tym sensie różnica między rozpoznaniem a pamięcią skojarzeniową polega jedynie na tym, że w przypadku rozpoznania przeszłość ożywa w samej percepcji, nie przekraczając jej granic, natomiast w pamięci skojarzeniowej ta przeszłość nie jest dana w formie jakiejkolwiek wcześniejszej percepcji, ale pojawia się obraz, który jest podawany wielokrotnie, ale już w formie reprezentacji. Poniżej przekonamy się, że na wyższym etapie rozwoju, do odtwarzania reprezentacji pamięci, nie zawsze potrzebny jest bodziec. Istnieje nie tylko mimowolne zapamiętywanie, ale także dobrowolne przywoływanie.

Sposoby organizowania pamięci

Nazwa parametru	Oznaczający
Temat artykułu:	Sposoby organizowania pamięci
Kategoria (kategoria tematyczna)	Komputery

Funkcjonalnie pamięć dowolnego typu zawsze składa się z tablicy pamięci, która przechowuje informacje oraz pomocniczych, dość skomplikowanych bloków, które służą do wyszukiwania w tablicy, zapisu i odczytu (i w razie potrzeby do regeneracji).

Macierz pamięci (ZM) składa się z wielu identycznych elementów pamięci (ZE). Wszystkie GE są zorganizowane w komórki, z których każda jest przeznaczona do przechowywania jednostki informacji w postaci kodu binarnego, którego liczba bitów jest określona przez szerokość próbki. Sposób organizacji pamięci zależy od sposobów umieszczania i wyszukiwania informacji w ZM. Na tej podstawie rozróżnia się pamięć adresową, asocjacyjną i stosową.

PAMIĘĆ ADRESOWA

W pamięci z organizacją adresu umieszczanie i wyszukiwanie informacji w ZM opiera się na wykorzystaniu adresu pamięci jednostki informacji, która w dalszej części, dla zwięzłości, będzie nazywana słowo... Adres to numer komórki 3M, w której znajduje się to słowo. Podczas pisania (odczytu) słowa do ZM polecenie inicjujące tę operację musi wskazywać adres (numer) komórki, pod którą chcesz pisać (odczytywać).

Na ryc. 5.2 pokazuje uogólnioną strukturę pamięci adresowej.

Cykl dostępu do pamięci jest inicjowany sygnałem „Dostęp” docierającym do PCU. Ogólna część cyklu dostępu obejmuje odbieranie adresu dostępu z szyny adresowej (ША) z szyny adresowej (ША) i odbieranie sygnału sterującego „Operacja” w PCU, wskazującego typ żądanej operacji (odczyt lub zapis).

Czytanie. BAV odszyfrowuje adres i wysyła sygnał, który wybiera komórkę 3M określoną przez adres. W ogólnym przypadku BAS może również wysyłać sygnały do ​​dedykowanej komórki pamięci, która konfiguruje komórki ZE do zapisu lub odczytu. Następnie słowo wpisane do komórki jest odczytywane przez wzmacniacze ACC i przesyłane do RgI. Ponadto w pamięci z destrukcyjnym odczytem informacje są regenerowane poprzez wpisanie słowa z RgI przez BUZ do tej samej komórki ZM. Operacja odczytu jest zakończona poprzez wysłanie słowa z RgI do wyjściowej magistrali informacyjnej SHI out.

Nagranie. Oprócz powyższej ogólnej części cyklu dostępu, słowo pisane jest odbierane z szyny wejściowej ShI do RgI. Sam rekord zazwyczaj składa się z dwóch operacji - czyszczenia komórek i samego rekordu. W tym celu BAS najpierw wybiera i czyści komórkę określoną przez adres w РгА. Czyszczenie ogniwa ZM (wprowadzenie stan początkowy) można zrobić na różne sposoby. W szczególności w pamięci z odczytem destrukcyjnym kasowanie może odbywać się sygnałem do odczytania słowa w komórce, gdy BUS jest zablokowany (aby informacja nie dochodziła do RgI). Następnie w wybranej komórce zapisywane jest nowe słowo.

Konieczność operacji czyszczenia komórki przed zapisem, a także operacji odtwarzania informacji podczas odczytu, determinowana jest przez rodzaj zastosowanego GE, metody sterowania, cechy struktury elektronicznej pamięci LSI, stąd te operacje mogą być nieobecne w pamięciach półprzewodnikowych.

PCU generuje niezbędne sekwencje sygnałów sterujących, które inicjują pracę poszczególnych węzłów pamięci. Należy pamiętać, że PCU musi być bardzo złożonym urządzeniem (rodzajem kontrolera sterującego z własną pamięcią podręczną), co nadaje LSI pamięci jako całości specjalne właściwości konsumenckie, takie jak obsługa wielu portów, dostarczanie informacji potokowej itp.

PAMIĘĆ POWIĄZAŃ

W tego typu pamięciach wyszukiwanie informacji odbywa się nie po adresie, ale po jego zawartości. Przyjęło się w tym przypadku rozumieć zawartość informacji nie jako ładunek semantyczny słowa przechowywanego w komórce pamięci, ale zawartość komórki pamięci ZE, ᴛ.ᴇ. bitowa kompozycja nagrań słowo binarne... W tym przypadku żądanie asocjacyjne (funkcja) również jest kod binarny z pewną kompozycją bitową. Wyszukiwanie według cechy asocjacyjnej odbywa się równolegle w czasie dla wszystkich komórek 3M i jest operacją porównywania zawartości bitów rejestru cech z zawartością odpowiadających im bitów komórek pamięci. Aby zorganizować takie wyszukiwanie, wszystkie ZE w SM są wyposażone w procesory jednobitowe, dlatego w wielu przypadkach pamięć tego typu jest uważana za system wieloprocesorowy.

Pamięć w pełni asocjacyjna o dużej objętości jest bardzo kosztownym urządzeniem, dlatego w celu obniżenia kosztów liczba procesorów jednobitowych jest zredukowana do jednego na komórkę pamięci. W tym przypadku porównanie zapytania asocjacyjnego z zawartością komórek pamięci odbywa się sekwencyjnie dla poszczególnych bitów, równolegle w czasie dla wszystkich komórek pamięci.

Przy bardzo dużej ilości pamięci dla pewnych klas problemów wyszukiwanie asocjacyjne znacznie przyspiesza przetwarzanie danych i zmniejsza prawdopodobieństwo awarii komputera. Jednocześnie pamięć asocjacyjna z blokami odpowiednich układów kombinacyjnych pozwala na wykonywanie w pamięci dość złożonych operacji logicznych: wyszukiwanie maksymalnej lub minimalnej liczby w tablicy, wyszukiwanie słów zawartych w określonych granicach, sortowanie tablicy itp.

Należy zauważyć, że wyszukiwanie asocjacyjne może być również zaimplementowane w komputerze ze zwykłą pamięcią adresową poprzez sekwencyjne wywoływanie słów zapisanych w komórkach pamięci do procesora i porównywanie ich z jakąś cechą asocjacyjną (wzorem). Jednocześnie przy dużej ilości pamięci zajmie to dużo czasu. Korzystając z pamięci asocjacyjnej, możliwe jest, bez odczytywania słów z OP do procesora, w jednym wywołaniu określenie liczby słów, które odpowiadają danemu zapytaniu asocjacyjnemu. Umożliwia to w dużych bazach bardzo szybką realizację zapytania typu: ilu mieszkańców regionu nie złożyło zeznania podatkowego itp.

W niektórych wyspecjalizowanych komputerach OP lub jego część jest zbudowana w taki sposób, że pozwala na zaimplementowanie wyszukiwania informacji asocjacyjnych i adresowych.

Uproszczony schemat strukturalny Pamięć asocjacyjna, w której wszystkie ZE ZM są wyposażone w procesory jednobitowe, pokazano na ryc. 5.3.

Najpierw rozważ operację o nazwie kontrola stowarzyszenia... Ta operacja jest wspólna dla operacji odczytu i zapisu, a także ma niezależne znaczenie.

n-bitowe żądanie asocjacyjne, ᴛ.ᴇ, jest wysyłane do RgAP przez szynę informacji wejściowych. bity od 0 do n-1 są wypełnione. W tym samym czasie kod maski wyszukiwania dociera do RgM, podczas gdy n-ty bit RgM jest ustawiony na 0. Wyszukiwanie asocjacyjne jest wykonywane tylko dla zestawu bitów RgAP, które odpowiadają 1 w RgM (niezamaskowane bity RgAP). Należy zauważyć, że dla słów, w których cyfry w cyfrach pokrywają się z niezamaskowanymi cyframi PrAP, KS ustawia 1 dla odpowiednich cyfr PrSv i 0 dla pozostałych cyfr.

Schemat kombinacyjny tworzenia wyniku asocjacyjnej inwersji FS tworzy co najmniej trzy sygnały ze słowa utworzonego w РгСв:

A 0 - brak słów w ZM spełniających cechę asocjacyjną;

A 1 - obecność jednego takiego słowa;

A 2 - obecność więcej niż jednego słowa.

Możliwe są również inne operacje na treści РгСв, na przykład liczenie jednostek, ᴛ.ᴇ. liczenie w pamięci słów, które spełniają skojarzone zapytanie i tym podobne.

Tworzenie zawartości PrCv i 0, a 1, a 2 przez zawartość PrAP, RgM, 3M jest powszechnie nazywane operacją kontroli asocjacji.

Czytanie. Po pierwsze, powiązanie jest monitorowane według atrybutu w RgAP.

A 0 = 1 - odczyt jest anulowany z powodu braku wymaganych informacji;

A 1 = 1 - znalezione słowo jest wczytywane do RgI, po czym jest wydawane do SHI;

A 2 = 1 - czytane jest słowo, które ma np. najmniejszą liczbę spośród komórek oznaczonych 1 w PgSv, po czym jest wydawane do SHI out.

Nagranie. Najpierw zostaje znaleziona wolna komórka (zakładamy, że w zajętym bicie wolnej komórki jest zapisane 0). W tym celu powiązanie jest monitorowane przy РгАП = 111 ... 10 i РгМ = 000 ... 01, ᴛ.ᴇ. N-ty bit РгАП jest ustawiony na 0, a n-ty bit РгМ na 1. W tym przypadku wolna komórka jest oznaczona 1 w РгСв. Do nagrywania wybierz pustą komórkę, na przykład o najniższym numerze. Zapisuje słowo otrzymane od SHI w RgI.

Należy zauważyć, że ten schemat nie pokazuje bloków BUP, BUS, BUZ, które znajdują się w rzeczywistych urządzeniach. Jednocześnie do zbudowania pamięci asocjacyjnej potrzebne są elementy pamięci, które można odczytać bez zniszczenia.

PAMIĘĆ STOSU (SKLEP)

Pamięć stosu, podobnie jak pamięć asocjacyjna, jest bezadresowa. Pamięć stosu musi być zorganizowana zarówno sprzętowo, jak i na regularnej tablicy adresowalnej pamięci.

W przypadku implementacji sprzętowej komórki pamięci stosu tworzą jednowymiarową tablicę, w której sąsiednie komórki są połączone ze sobą łańcuchami bitów transmisji słów (rys. 5.4). W tym przypadku możliwe są dwa rodzaje urządzeń (a, b), których zasady są różne. Rozważ początkowo strukturę na ryc. 5,4 a.

Wpisanie nowego słowa odebranego z SHI następuje do komórki górnej (zerowej), podczas gdy wszystkie wcześniej wpisane słowa (w tym słowo z komórki 0) są przesuwane w dół do sąsiednich komórek, których numery są o jeden więcej. Odczyt możliwy jest tylko z górnej (zerowej) komórki pamięci. Tryb główny to ϶ᴛᴏ czytanie z kasowaniem. W tym przypadku wszystkie pozostałe słowa w pamięci są przesuwane w górę, do sąsiednich komórek o niższych numerach. W takiej pamięci realizowana jest zasada: przyjechał ostatni - pierwszy odszedł... Stosy tego typu są powszechnie określane jako stosy LIFO (Last In - First Out).

W niektórych przypadkach urządzenia pamięci stosu zapewniają również operację prostego odczytu słowa z komórki 0 bez usuwania go i przesuwania pozostałych słów. Używając stosu do zapamiętywania parametrów inicjalizacji kontrolerów dowolnych urządzeń komputerowych, zwykle można odczytać zawartość dowolnej komórki stosu bez jej usuwania, ᴛ.ᴇ. odczytywanie zawartości nie tylko komórki 0.

Mówi się, że pierwsze słowo umieszczone na stosie znajduje się na spód stosu... Mówi się, że ostatnie słowo wysłane (w czasie) na stosie jest w szczyt stosu... Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, komórka N-1 to dół stosu, a komórka 0 to wierzchołek.

Zazwyczaj stos sprzętowy jest wyposażony w licznik stosu Count, pokazujący całkowitą liczbę słów przechowywanych w pamięci (Count = 0 - stos jest pusty). Gdy stos jest pełny, uniemożliwia dalsze zapisy.

Zasada układania w stos organizacji pamięci może być zaimplementowana nie tylko w specjalnie zaprojektowanych urządzeniach. Stosowa organizacja danych jest również możliwa w zwykłej pamięci adresowej z dostępem swobodnym (stos programowy). Aby uporządkować stos LIFO, w tym przypadku potrzebna jest jeszcze jedna komórka pamięci (rejestr), w której zawsze przechowywany jest adres wierzchołka stosu i która jest zwykle wywoływana wskaźnik stosu... Zwykle jeden z wewnętrznych rejestrów procesora jest używany jako wskaźnik stosu. Dodatkowo wymagane jest odpowiednie oprogramowanie. Zasady układania danych w stosy w zwykłej pamięci adresowej ilustruje diagram na rys. 5.5.

W przeciwieństwie do stosu sprzętowego dane znajdujące się na stosie oprogramowania nie poruszają się, gdy nowy numer jest zapisywany lub odczytywany. Każde nowe słowo jest zapisywane w komórce pamięci obok tego zawartego we wskaźniku stosu. Po wpisaniu nowego słowa zawartość wskaźnika stosu jest zwiększana o jeden (patrz rysunek 6.5). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, to nie dane są przenoszone na stosie programu, ale na wierzchołek stosu. Kiedy słowo jest odczytywane ze stosu, następuje proces odwrotny. Słowo jest odczytywane z komórki, której adres znajduje się we wskaźniku stosu, po czym zawartość wskaźnika stosu jest zmniejszana o jeden.

Jeśli nowo załadowane słowa na stosie znajdują się w komórkach pamięci z sekwencyjnie rosnącymi adresami, stos nazywa się bezpośredni. Jeśli adresy maleją sekwencyjnie, to - odwrotny. W większości przypadków używany jest stos odwrócony, co jest związane ze specyfiką sprzętowej implementacji liczników wewnątrz procesora.

Dlaczego ta forma organizacji pamięci jest wygodna? Patrząc w przyszłość, można zauważyć, że każda instrukcja wykonywana w procesorze, w ogólnym przypadku, musi zawierać kod operacji (CPC), adres pierwszego i drugiego argumentu oraz adres wprowadzenia wyniku. Aby zaoszczędzić pamięć i skrócić czas wykonywania instrukcji maszynowej przez procesor, pożądane jest zmniejszenie długości instrukcji. Ograniczeniem dla tej redukcji jest długość niezaadresowanego polecenia, ᴛ.ᴇ. tylko policjant. Właśnie takie instrukcje są możliwe przy organizacji pamięci stosu, ponieważ przy prawidłowym rozmieszczeniu operandów w stosie wystarczy je sekwencyjnie pobierać i wykonywać na nich odpowiednie operacje.

Oprócz omówionej powyżej pamięci stosu LIFO, komputery używają pamięci stosu innego typu, które realizują regułę: pierwszy przyszedł - pierwszy odszedł... Stosy tego typu są powszechnie określane jako stosy FIFO (First In - First Out). Taka pamięć stosu jest szeroko wykorzystywana do organizowania różnego rodzaju kolejek (polecenia, dane, żądania itp.). Uogólnioną strukturę stosu sprzętowego typu FIFO pokazano na rys. 5.4, ​​b.

Podobnie jak w poprzednim przypadku, komórki pamięci stosu tworzą jednowymiarową tablicę, w której sąsiednie komórki są połączone ze sobą łańcuchami transmisji słów bitowych. Zapis nowego słowa odebranego z SHI w odbywa się w górnej (zerowej) komórce, po czym natychmiast przesuwa się w dół i jest rejestrowany w ostatniej niewypełnionej komórce. Jeśli stos przed zapisaniem był pusty, słowo natychmiast trafia do komórki o numerze N-1, ᴛ.ᴇ. na dół stosu. Odczyt jest możliwy tylko z dolnej komórki o numerze N-1 (dolna część stosu). Tryb główny to ϶ᴛᴏ czytanie z kasowaniem. W takim przypadku wszystkie kolejne (pisane) słowa są przesuwane w dół do sąsiednich komórek, których liczba jest o jeden więcej. Gdy stos jest pełny, licznik (Count) uniemożliwia dalsze operacje zapisu na stosie.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, w przeciwieństwie do stosu LIFO, stos FIFO nie przesuwa dołu, ale górę. Słowa zapisywane na stosie FIFO stopniowo przesuwają się od góry do dołu, skąd są odczytywane jako niezwykle ważne, a tempo zapisu i odczytu jest określane przez zewnętrzne sygnały sterujące i nie jest ze sobą powiązane.

Implementacja programowa stosu FIFO nie jest rozważana w tej sekcji, ponieważ jest rzadko używana w praktyce.

Sposoby organizowania pamięci – pojęcie i rodzaje. Klasyfikacja i cechy kategorii „Sposoby organizowania pamięci” 2017, 2018.