    16. Виртуальная память 

    В этом разделе мы реализуем «большой» вектор из N элементов типа Е на базе 
точно такого же «большого» вектора из N элементов типа В и еще одного 
«маленького» вектора из п элементов типа Е, где п <?. N. Однако сначала 
поясним причины возч пикновения этой на первый взгляд странной задачи. 

    250 ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И   ИХ  РЕАЛИЗАЦИИ 

    Память современных ЭВМ состоит из нескольких компонент, физически по 
разному реализованных и работающих о разными скоростями. Любая ЭВМ имеет 
внутреннюю, так называемую оперативную память, которая является вектором 
элементов специального типа байт. Байт состоит из 8 элементов типа да/нет, 
называемых битами, и может иметь 28 = 256 различных состояний, которые обычно 
нумеруются от 0 до 255. Таким образом, байт можно считать объектом типа 0 .. 255. 
    Кроме оперативной, ЭВМ имеет обычно внешнюю, более медленную память, 
которая является вектором элементов типа блок. Блок — это вектор элементов 
типа байт с индексом, как правило, от 1 до 512. В этом разделе для нас 
существенно только то, что внешняя память имеет на порядок больший объем и на 
порядок меньшую скорость работы, чем оперативная. 
    Кроме оперативной и внешней памяти современные ЭВМ часто имеют еще 
компоненту памяти, называемую кэш (от англ, cache — запас) — также вектор 
элементов типа байт. Кэш является на порядок более быстрой памятью и имеет на 
порядок меньший объем, ;»ем оперативная. 
    Разумеется, если при работе программы необходимо хранить объем информации, 
превышающий суммарный объем всех видов памяти используемой ЭВМ, то ситуация 
предельно проста: на данной ЭВМ данную программу выполнить нельзя. Точно так 
же программу нельзя выполнить, если скорость работы самой быстрой памяти не 
обеспечивает нужную скорость выполнения программы. [Чаще, однако, встречается 
промежуточная ситуация: суммарный .объем памяти достаточен и скорость работы 
быстрой памяти удовлетворительна, но вся необходимая информация одновременно в 
быструю память не помещается. 
    Поскольку  в  каждый  отрезок времени  программа  обычно работает  не со  
всеми  данными,   а  лишь  с некоторой  их  частью,  то можно  попытаться  
разместить   эти   активно   используемые  данные в быстрой памяти. Тогда на 
данном отрезке времени скорость выполнения программы будет определяться 
скоростью работы быстрой памяти.   Разумеется,   в процессе   выполнения   
программы   активно используемые данные изменяются. Поэтому для обеспечения  
быстрой работы данные нужно регулярно перераспределять между быстрой памятью и 
медленной. Возникает вопрос: как это делать? Ответ, который   излагается   в   
настоящем   разделе,   таков:   будем   писать программы,   не   используя   
явно   ни маленькую   быструю   память (вектор элементов типа Е с индексом от 
0 до п— 1), ни большую медленную,   Вместо   этого   используем   в   
программе   исполнителя «Виртуальная  (от  англ,  virtual — воображаемая)   
память»   (вектор элементов типа Е с индексом от О AQ N sa.l), считая, что его сио. 

    /16. ВИРТУАЛЬНАЯ ПАМЯТЬ 251 

    рость работы близка к скорости работы быстрой памяти. Сам этот большой 
быстрый вектор реализуем на базе большой медленной памяти, используя для 
ускорения работы маленькую быструю. 
    Естественно, что на. самом деле обеспечить высокую скорость работы 
исполнителя «Виртуальная память» можно только в том случае, если 
перераспределения данных между быстрой и медленной памятью будут происходить 
существенно реже, чем обращения к элементам, уже имеющимся в быстрой памяти. А 
это зависит не только от реализации виртуальной памяти, но и от того, как она 
используется. Если, например, последовательно использовать нулевой, 
первый,.,., N—1-й элементы виртуальной памяти, то( какова бы ни была ее 
реализация, скорость работы,будет такой же, как скорость медленной памяти. 
Таким образом, реализация исполнителя «Виртуальная память» должна учитывать 
характер его использования. 
    Рассмотрим  две  постановки  и  два  решения  этой задачи: 
    а) оперативная память рассматривается как большая медленная, а кэш — как 
ускоритель (тип Е=байт). Реализация должна быть предельно простой (она 
«запаивается» в аппаратуру) и обеспечивать быструю работу как минимум при 
многократном чтении V(B произвольном порядке) п любых подряд идущих элементов; 
    б) оперативная память (точнее, некоторая ее часть, называв-мая пулом — от 
англ, pool — общий фонд) рассматривается как быстрая маленькая, т. е. как 
ускоритель, а основным хранилищем элементов служит внешняя (или, как ее еще 
называют, вторичная) память. Хотя элементом оперативной памяти является байт, 
а эле< ментом вторичной — блок, мы для простоты будем считать, что они состоят 
из элементов одного типа — из блоков. Виртуальная память должна работать с 
блоками и обеспечивать быструю работу и при чтении, и при записи любых (не 
обязательно идущих подряд) п элеч ментов. 
    Кроме основных базовых структур в реализациях разрешается использовать 
«небольшие» (из п элементов) векторы объектов типа да/нет, чисел и ссылок. 
    Поскольку изменение элемента виртуальной памяти — потенциально более 
долгая операция, чем его использование, то доступ к элементу вектора разделим 
на две операции — чтение и запись —• л будем реализовывать исполнителя 
«Виртуальная память» со еле* дующей системой предписаний: 
    1. начать работу 
    2. элемент с индексом <вх : 1>     :Е 
    3. записать <вх : Е>; в элемент с индексом <вх : 1} 
    4. кончить работу 

    252	ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И   ИХ  РЕАЛИЗАЦИИ 

    Замечание. Обычно мы формулируем требования к реализациям до их создания. 
На практике это не всегда так — довольно часто сначала придумывается 
интересная реализация, а потом выясняется, что она может существенно помочь 
при решении тех или иных задач. 
    Кэш-память. Пусть стоит задача реализовать воображаемый (виртуальный) 
большой быстрый вектор (назовем его «Кэш память») элементов типа Е (Е=байт) с 
индексом от 0 до N — 1 на базе маленького быстрого вектора «Кэш» с индексом от 
0 до п — 1 и большого медленного вектора «Память» с индексом от 0 до N—-1. 
Идея реализации очень проста: будем хранить элементы виртуального вектора в 
соответствующих элементах вектора «Память», а вектор «Кэш» используем в 
качестве ускорителя. Для этого отобразим множество индексов 0 . . N — 1 
хеш-функцией h(i)=imodn в множество 0 ,. п — 1. При записи элемента с индексом 
1 будем записывать его и в память, и в элемент кэш с индексом h(i)i При чтении 
элемента сначала посмотрим, не находится ли этот элемент уже в векторе «Кэш». 
Если да, то к памяти обращаться вообще не будем (за счет чего и должны 
получить выигрыш в скорости). Если же элемента в кэш нет, то прочтем его из 
памяти и одновременно поместим в кэш в элемент с ин
    В ЭВМ устройства «кэш» и «память» конструируются так, что при всяком 
чтении из памяти или записи в память элемент попадает в кэш автоматически, 
образно говоря, по «параллельным проводам». Таким образом, работа с кэш не 
требует никакого дополнительного времени по сравнению с работой с памятью. 
Если, однако, требуемый элемент уже есть в кэш, то при его чтении обращения к 
памяти не происходит. За счет этого среднее быстродействие ЭВМ. повышается в 
1,5 — 2 раза, 

    исполнитель Кэш память . СП: 
    1. начать работу ,     2. элемент с индексом (вх : 1)      : Е 
    3. записать (вх : Е) в элемент с индексом (вх : i) 
    4. кончить работу 
    4. константы: 
    .      N = 65636 .      п.= 2048 
    типы: 
    индеко. 
    

    16   ВИРТУАЛЬНАЯ ПАМЯТЬ' 263 
    

    кэш_индекс = 0 ..  п — 1 объекты: 
    Индекс в памяти : вектор индекс (кэш-индекс) используемые исполнители: 
    Кэш       : вектор Е (кэш-индекс) 
    Память : вектор Е (индекс) 
    конец описаний 
    программа начать работу . дано        : . получить: 
    i	Кэш.начать работу 
    ;	Индекс в памяти.начать работу 
    .	Память.начать работу 
    .	цикл V кекэш_индекс выполнять 
    .	,    Кэш (k) := Память (k) 
    .	.    Индекс в памяти (k) := k 
    .	конец цикла 
    конец программы	
    программа элемент с индексом (вх: i: индекс): Е . дано        : . получить: 
    .	k := i mod n 
    .	если Индекс в памяти (k) 
    .	.     Ksm (k) :— Пимить (i) 
    .	,    Индекс п ни коп и (k) :«• 1 
    .	конец гели 
    .	отигт :••- Кэш (k) 
    конец программы	; 
    программа записать (вх:е:Е) в . дано        : . получить: 
    i   TO 
    'SSgWWKCOM 
    ':.)<      ( 
    ,   k := i mod n .   Кэш (k) := e .   Индекс в памяти (k) .    Память (i) 
:= e конец программы 
    программа кончить работу . дано       ; 


    254 ГЛ. 3. СТРУКТУРЫ ДАННЫХ  И ИХ  РЕАЛИЗАЦИИ 


    , получить: 
    .   Кэш. кончить работу .   Индекс в памяти. кончить работу .   Память. 
кончить работу 
конец программы 
    конец исполнителя 

    Напомним, что реализация кэш-памяти дает выигрыш, если в каждый конкретный 
момент времени активно читается небольшое ;(на превосходящее кэш) множество 
рядом расположенных элементов вектора, В этом случае все они попадают в кэш, и 
при работе с ними память трогать не приходится. Если, однако, поочередно 
работать всего лишь в двумя алементами вектора, индексы которых отличаются на 
п, то придется постоянно обращаться к Иамяти, и никакого ускорения по сравнению 
просто о работой $ памятью не будет. 
    Виртуальная память. Решим теперь задачу б). Здесь у нас тип Е — это блок, 
маленький быстрый вектор «Пул» — это некоторая часть оперативной памяти ЭВМ, 
большой медленный вектор «Вторичная память» — это некоторая область во внешней 
памяти. Будем считать, что пул является обычным вектором, а исполнитель 
«Вторичная память», по сути также являющийся ве 
    ктором, имеет следующую систему предписаний; 
    1. начать работу 
    2. прочесть блок <в« 1 1 1 номер блока) в <вых : е : блок) 
    3. записать <вх : е ; блок) в блок <вх : i i номер блока) 
    4. кончить работу 
    Постановка этой задачи образно изображена на рис. 16.1. Исполнитель 
«Вторичная память» изображен мальчиком на стремянке. Приведенная выше 
реализация кэш-памяти в точности повторяет эту картину в миниатюре! вместо 
блоков — байты, вместо пула — кэш, вместо вторичной памяти — память, 
    Ниже мы будем использовать знак # (который считается такой же буквой, как 
А, В, С и др.) в качестве альтернативы для слова «индекс», т. е, имена вида 
«фблока» будем читать и использовать как «индекс блока», 
    исполнитель Виртуальная память » СП: 
    ,      1, начать работу 
    л     2, элемент с индексом (вх : i)     \ E 
    > ..„ 3. записщь (uxiesE) в элемент с индексом (вхП) 
    ".     —поместить блок (вх:1) в пул (вых!к) 
    — освободить блок пула {вых: к) .      4. кончить работу 
    **	t 
    .	константы: 
    .	N                   «= 2048 
    .	п                   =   128 
    «	длина блока=  512 | байт 
    • 
    .	типы: 
    .	фблока          =0 .. N — 1 | во вторичной памяти 
    .	фблока пула = 0 .. п — 1 
    ,	Е = блок   = вектор байт (0 .. длина блока — 
    

    ' 16. ВИРТУАЛЬНАЯ ПАМЯТЬ 253 

    вторичная память 
    клоки 
    вторичной 
    памяти 

    РИС.   16.1 

    Идеи реализации. Реализуем исполнителя «Виртуальная память» (вектор блоков 
с индексом O..N — 1) на базе ряда объектов в памяти и исполнителя 
^Вто?ичн_ая___память», KOTOpjgu^ является точно таким же вектором блоков, 
только очень медленным. В процессе работы информация из некоторых блоков 
вторичной памяти располагается в буферном пуле. Если при обращении к тому или 
иному блоку виртуальной памяти этот блок уже находится в пуле, т.о 
производятся требуемые действия с соответствующим блоком пула, Если же блрка в 
пуле нет, то он в пул помещается, При 

    256	1'Л. 3. СТРУКТУРЫ  ДАННЫХ И  ИХ РЕАЛИЗАЦИИ этом какой-то другой блок 

может быть «вытолкнут» из пула обратно во вторичную  память   (рис,  16.1).  В 
конце  работы  все  блоки пула, «выталкиваются» обратно во вторичную память, 
    Таким образом, действия, производимые при имитации работы • блоками 
виртуальной памяти, можно- разделить на чтение/запись блоков в пуле и/или во 
вторичной памяти и на работу с ограниченным множеством пар (индекс блока в 
пуле, индекс блока во вторичной памяти) для всех находящихся в пуле блоков. 
(Число пар в этом множестве ограничено числом блоков пула.) В соответствии с 
технологией «сверху вниз» введем для работы с этим множеством промежуточного 
исполнителя «Множество пар» и «передо-жим на него» анализ наличия или 
отсутствия блока виртуальной памяти в пуле, определение индекса выталкиваемого 
блока пула, определение по индексу блока его индекса в пуле и т, п,з 
    . используемые исполнители: 
    .   Множество пар 
    .   Пул: вектор элементов типа Ее индексом  типа фблока   пула 
    .    Вторичная память 
    * 
    конец описаний | —--————-—-—————_-——_—-программа начать работу . дано      
  : . получить: 


    15. ВИРТУАЛЬНАЯ ПАМЯТЬ 

    .   Множество пар.начать работу 
    .   Пул.начать работу 
    .    Вторичная память.начать работу 
    конец программы 
    программа элемент с индексом (вх: i: фблока): Е 
    . дано        : 
    . получить: 
    '. "поместить блок (ex:i> в пул (вых:к> .   ответ :=» Пул (k) конец программы 
    Введенная здесь локальная программа «поместить блок в пул» должна 
поместить 1-й блок виртуальной памяти в пул (если его ?ам не было раньше) и 
выдать в выходном параметре k индекс соответствующего блока пула. 
    программа записать <вх:е:Е> в элемент с индексом <»ж:1> 0 дано        : i: 
ф блока , получить; 
    .   поместить блок (вх: 1} в пул {вых: k) .   Пул(к) := е конец программы 
    программа поместить блок <вх: i) в пул (вых: k) 
    , дано        :  I: ф блока 
    . получить: k: ф блока пула 
    .	k := Множество пар.индекс блока в пуле (ex:i) 
    .	если k = неопр то |блока в пуле нет 
    .	.    освободить блок пула (вых : k) 
    .	.    Вторичная память.прочесть блок (ex:i) в (вых:Пул (k)) 
    .	.     Множество пар.добавить пару (ex:k,i)                   * 
    .	конец если 
    конец программы 
    Предписание «Множество пар.индекс блока в пуле» должно вырабатывать в 
качестве значения либо индекс блока пула, в котором расположен i-й блок 
виртуальной памяти, либо неопр, если 1-го блока виртуальной памяти в данный 
момент в пуле нет (т, е. в Множестве пар не существует пары вида (k, i) с 
данным i). 
    программа освободить блок пула (вых:к) 
    . дано        : 
    . получить: k: фблока пула	;   .V;' 
    .   Множество пар.вытолкнуть пару (вых:1<,1) 
    .   если IT^неопр то [блок пула был занят 
    .    .     Вторичная память.записать (вх : Пул (k)) в блок (ex:i) 
    .    конец гош 
    Конец iipoi рпммм 
    Мы предполагаем, что предписание «Множество па р. вытолкнуть пиру» либо 
удаляет какую-то пару (k, i) из множества, выдавая поличины k и i в качестве 
выходных параметров наружу, либо выдает пару вида (k, неопр), где k —индекс 
свободного блока пула (множество пар при этом не меняется). Кроме того, будем 
предполагать (это понадобится в программе «кончить работу»), что при 
применении п раз подряд предписания «вытолкнуть пару» получаются все п 
различных значений к, 
    программа кончить работу . дано       : . получить: 
    цикл п раз | т. е. число блоков пула раз 


     9    А. Г. Кушниревко, Г. В. Лебедев 
    258 ГЛ. 3. СТРУКТУРЫ  ДАННЫХ   И  ИХ  РЕАЛИЗАЦИИ 


    .	«   выполнять 
    .	«     освободить блок пула (вых:1с) 
    .	конец цикла 
    ,	Вторичная память.кончить работу 
    .	Пул.кончить работу 
    ,	Множество пар.кончить работу 
    Конец программы 
    конец исполнителя 
    | =, = =, = = = = = = = -_-=1 = =,=, = =, = « = = = --=, ==
    Прежде чем двигаться дальше, т. е. в соответствии с технологией «сверху 
вниз» реализовывать промежуточного исполнителя «Множество пар», заметим, что в 
приведенной реализации при выталкивании блока виртуальной памяти из пула он 
всегда записи-вается во вторичную память. Очевидно, что если содержимое блока 
не менялось, то в этом нет необходимости. Поскольку запись блока во вторичную 
память — весьма длительная операция, изменим реализацию так, чтобы блоки пула 
записывались во вторичную память только тогда, когда это действительно нужно, 
т. е. когда содер-жимое блока менялось. Для хранения информации об изменениях 
в блоках добавим в реализацию исполнителя «Виртуальная память» глобальный 
объект были изменения : вектор да/нет (ф блока пула) в  изменим  реализацию   
программ   «записать»,  «поместить  блок»  и 
    «освободить блок»: 
    Программа записать (их: е: Е) в элемент с индексом (вх:!) 
    . дано       : i: ф блока 
    . получить: 
    .   поместить блок (вх: 1) в пул (вх: k) .   Пул(к) :== е .   были 
изменения (k) := да конец программы 
    программа поместить блок (ix:i) в пул (вых:1е) 
    . дано       :  i: Ф блока 
    . получить: k: ф блока пула 
    .	k := Множество пар.индекс блока в пуле (вх: i) 
    .	если k = неопр то |блока в пуле нет 
    .	.    освободить блок пула (вых : k) 
    .	.    Вторичная память, прочесть блок (вх: i) в (вых: Пул (k)) 
    .	.    Множество пар.добавить пару (flx:k,i) 
    .	.    были изменения (k) := нет 
    в   конец если конец программы 
    программа освободить блок пула (вых i k) 
    . дано        i 
    . получить: k:^ блока пула 


    Дв,  ВИРТУАЛЬНАЯ ПАМЯТЬ 259 


    .   Множество пар.вытолкнуть пару (ebixlk,i) 
    .   если 1^неопр и были изменения (k) то 
    ,    .    Вторичная память.записать (вх|Пул(^) в блок (BXI!) 
    ,    конец если 
    конец программы 
    * 
    Второй шаг декомпозиции. Займемся теперь реализацией исполнителя 
«Множество пар>, Система предписаний этого исполнителя выглядит так: 
    исполнитель Множество пар . СП: 
    1. начать работу 
    2. вытолкнуть пару (вых ! k! ф блока пула, 1: ф блока) .     3. добавить 
пару (вх: k i Ф блока пула, 4 i ф блока) .     4. индекс блока в пуле (вх i i 
IФ блока)  i ф блока пула 
    б. кончить работу 
    константы: 
    N п 
    = 2048 •   128 
    ТИПЫ! 
    Ф блоки         •• 0 ,, N — i пуле -•>  0 о   п — 
    Поскольку число nap (k, I) не превосходит числа блоков -в пуле п k 
соответствуют индексам блоков пула, то простейшее решение состоит в том, чтобы 
хранить информацию о парах (k, i) в гло-Сильном объекте 
    индекс блока ; вектор фблока {фблока пула), 
    и именно в индекс блока (k) записать 1, если пара (k, 1) есть в множестве 
пар, и неопр, если пары {k, i) с данным k в множестве нет. Простейшая 
стратегия выталкивания, удовлетворяющая тре-Гхшанию «за п выталкиваний — все п 
различных значений k», состоит в том, чтобы последовательно выталкивать блоки 
сначала v k «=> О, затем о k = 1, k = 2, ,.,, k =» п —1, потом опять о 

    260 ГЛ. 3, СТРУКТУРЫ   ДАННЫХ  И   ИХ  РЕАЛИЗАЦИИ 

    k = О, k =« 1 и т. д. Заметим, что если при всяком добавлении-пары (k, i) 
k содержит индекс только что вытолкнутого блока (а в реализации Виртуальной 
памяти это так), то применение этой стратегии приводит к выталкиванию из пула 
«самого старого» блока — того, который находится в пуле дольше всех. Для 
реализации этой стратегии достаточно хранить индекс последнего вытолкнутого 
блока пула и перемещать его по «кольцу» 0.. п — 1 при очередном выталкивании. 
Мы будем хранить этот индекс в глобальном объекте 
    фвытолкнутого блока : фблока пула. 
    Таким   образом,   продолжение   реализации   исполнителя   «Множество 
пар» выглядит так: 
    . объекты: 
    . индекс блока : вектор ф блока (ф блока пула) 
    . ф вытолкнутого блока : ф блока пула 
    конец описаний |—______—___ ——___—__—___—_ 
    программа начать работу == ф вытолкнутого блока : = п—1 программа 
вытолкнуть пару (вых:k:ф блока пула, 1:фблока) . дано . получить: 
    18. ВИРТУАЛЬНАЯ ПАМЯТЬ ?31 
    .   k := (ф вытолкнутого блока-f- l)mod n 
    .    i  := индекс блока (k) 
    .   индекс блока (k) := неопр 
    .   41= вытолкнутого блока ;= k 
    конец программы 
    программа добавить пару <вх: k: ф блока пула, 1:ф блока) . дано       : 
индекс блока (k) = неопр . получить: 
    .   индекс блока (k) := 1 конец программы 
    программа индекс блока в пуле (вх: i: ф блока): ф блока пула 
    . дано   : 
    . получить: ответ = неопр | если блока i в пуле нет 
    .        или индекс блока (ответ)•= i 
    .	цикл V k & ф блока пула пока индекс блока (k) =?& L 
    ,	. выполнять 
    .	.     ничего не делать 
    .   конец цикла .    ответ := k конец программы 
    программа кончить работу конец исполнителя ]=, = = = , 
    ничего не делать 


    Хеш-реализация виртуальной памяти, Приведенная выше реала* дация 
виртуальной памяти (а точнее, исполнителя «Множество пар») обладает одним 
недостатком — анализ наличия или отсут* ствия нужного блока в пуле, а также 
определение его индекса и пуле (предписание «Множество пар.индекс блока в 
пуле») яв« ляется массовой операцией, так как осуществляется последова-1 
тельным перебором всех номеров блоков пула, От этого недостатка можно 
избавиться, если поспольмоваться идеями хеширования, т. е, не_некпт1> индекс 
блокп п нули, п вычислять его по индексу блока D пямнтн. Поедем комстянту 
    р «= п | число хеш-значений и глобальные объекты 
    хсш_таблица : вектор фблока пула (0  ..  р—1) вглед.в пред: псктор ф блока 
пула (ф блока пула) 
    Лмилш пишет» и определение месторасположения блока I и пуле изменим 
следующим образом: все множество блоков, нахо* дншнхся в пуле, разобьем на 
подмножества, соответствующие раз* личным значениям хеш-функции h(i)=imodp. 
Номера блоков пуля п каждом подмножестве провяжем ссылками «@слсд» ц «•пред» о 
отдельные кольца. Индекс какого-нибудь элемента кол 
    ь» ЦП (т.е. номер блокп пул») .члпшпсм п хеш-таблица(h), где h--* йНЯЧеине 
Хеш функции дли данного ко.'П.ци. Если для некоторого 
    •МЙИРНИИ  ll и  пуле  иг г (vicmon с таким  значением хеш-функции, то 
    •лгмгмгу  хеш таблицы  с  индексом  h  присвоим значение неопр; 
    исполнитель Множество пар 
    i (.11: 
    ,  1. начать работу 
    ,  2. вытолкнуть пару (вых : k : ф блока пула, J: ф блока) 
    ,  3. добавить пару (вх : k i ф блока пула, 1: ф блока) 
    ,  4. индекс блока в пуле (вх : i: ф блока) : ф блока пула 
    •  5. кончить работу 
    константы: 
    N п 
    Р = 2048 = 128 = п | число хеш-значений 


    262 ГЛ, 3, СТРУКТУРЫ ДАННЫХ  И  ИХ РЕАЛИЗАЦИИ 


    типы: 
    ф блока    ' ф блока пула• 
    О 
    а. 
    •N-1 п—1 
    .    объекты: 
    индекс блока : вектор ф блока (ф блока' пула); .      ф вытолкнутого блока 
S ф блока пула .     хеш_таблица :вектор ф блока пула (0' ., р — 1) 
    @след, ©пред! вектор фблока пула (фблока пула)1 
    конец описаний |———————- — — — - ——— ——————---——• 
    программа яанать- работу ==. ф^вимлкнутого' блеща s=* а— 1: программа 
вытолкнуть- пару фшх: k:.Ф блока пула,, 1:;ф-блока), . дано        : . получить: 
    ,	k := (41= вытолкнутого блока + 1) mod n 
    .	i :=» индекс блока (k) 
    .	индекс блока (k): := неопр; 
    ,	Ф вытолкнутого блока := k 
    В новой реализации, однако, в случае, если внгшишвается ванятый блок (i ф_ 
неопр), надо исключит* его из- соожветстдауютвп* кольца: 
    . если t *f= неопр то 
    !, .    связать (@npeA(k), @след(^) 
    а также, если блок в кольце один' нлн если блоков несколько, но в 
хеш-таблице записан индекс именно этого1 блока, —> модифицироч вать хеш-таблицу: 
    . .    h := i mod p . .    выбор 
    ..    .   при ©след(k) = k	^ хеш _таблица ('h)):«; неопр 
    . .    ,   при хеш_таблица (ih)'-"o;k =>хеш_таблица (1ф:,= Фвлед (k) 
    . .    конец выбора 
    . конец если 
    конец программы 
    программа добавить пару (вх: k: Ф блока пула, i! ф блока) 
    . дано        : индекс блока (k) = неопр 
    . получить; 
    индекс блока (k) :=» I 


    16. -ВИРТУАЛЬНАЯ  ПАМЯТЬ	?6i 

    Кроме   того,   новый   блок   надо   вставить  .в  -соответствующее 
кольцо, если оно было  (т. е, если хеш-таблица (h) ф неопр),, .либо 
сформировать из блока .новое .кольцо, если такого кольца не было? . h := i mod 
p	• . kl: *='хеш_таблица!('п1) 
    . если kl = неопр	' . .   то | блоков с хеш_значением h раньше не было . . 
     связать <k,k) . .    хеш_таблица( h) := k . .   иначе | вставляем блок в 
старое кольцо» . .     связать (@пред(Ы), k   > . .     связать (k,            
     kl)                                         „ 

    В этот момент все уж« сделано. Мы, однако, ускорим еща мпопжрнтпио 
cifipmm'iimi к одному и тому же блоку в случае, если блок и кольцо ни один, 
Для «того воспользуемся тем, что в хеш-тпблпце может быть записал индекс 
любого элемента кольца, а попок начинается именно е этого элемента. Таким 
образом, если и хеш-таблицу записать индекс нового, только что прочитанного 
блока, то информация о блоках ъ пуле останется корректной, а при повторном 
обращении к атому блоку искать в кольце не при-дгггя - мы ершу получим 
индекс требуемого 'блока. Поэтому на-rraiiicM пци 
    . . хсш_таблнца (h) := k . конец если конец программы 
    ирогримна индекс .блока в пуле .(•*-:-1: фблока}: фблока пула 
    -----       .: 
    ь: от»*т — н»оп|> (если блока I в-пуле нет или индикс блика (ответ)=i 
    В новой -реализации для получения ответа достаточно лросмот» |in*  только  
елеменаы  кольца  с «вответствующим значением  хеш« функции.  Определим  
сначала индекс  k первого элемента  кольца! , h : - - Ч mod p , 1>        
хеш_таблица (h)   иерь   надг>  просмотреть  само  кольцо  в  поисках  
требуемого 0;ini..i   С учетом того, что кольцо может быть пусто  (в этом слу* час 
I  • • неопр), поиск блока можно записать так: , гит It /^неопр то (есть блоки  с таким  
значением  хеш-функции . ,    kl := k 
    , .    цикл пока индекс блока (k)^! и @след (k)=^=k2 , .    ,     выполнять 


    264	ГЛ. 3. СТРУКТУРЫ ДАННЫХ  И  ИХ РЕАЛИЗАЦИИ 


    » •     k :=» ©след (k) . .    конец цикла 
    . .    если индекс блока (k)=?M то k i«« неопр конец если . конец если 
    .     утв: k = неопр | если i-ro блока нет в пуле .	или индекс блока (k) 
*= i , ответ := k конец программы 
    Использованная выше локальная подпрограмма «связать» реализуется, как обычно: 
    программа связать (exika.kb) «™«=» ©следка) := kb', 
    @ пред (kb) := ka 
    программа кончить работу «== ничего не делать конец исполнителя | ^,-, = 
__^ = =. = = = =» = = = =, = = =,=,=, = «. = =.--===.= =. 

    Поскольку число хеш-значений совпадает с максимальным чис-лом блоков в 
пуле, то можно надеяться, что в кольце, как правило, будет один-два элемента 
(если, например, работать с п подряд расположенными блоками вторичной памяти, 
то в каждом кольце будет по одному элементу). Так как число хеш-значений 
является константой, то его легко увеличить, например положить равным 2п, В 
последнем случае в каждом кольце, как правило, будет всего один элемент (или 
не будет элементов вовсе) и поиск элемента будет мгновенным. 
    Замечание. Слова «виртуальная память», вообще говоря, означают любую 
реализацию вектора на вазе других структур данных. Приведенные выше реализации 
в этом классе задач не единственные — широко распространенными и практически 
используемыми являются, например, реализации многих (например, 256) 
динамических векторов, ограниченных в совокупности на базе одного большого 
вектора, или реализации «большого разреженного» вектора с индексом от 0 до N — 
1 на базе «маленького» вектора с индексом от 0 до п—1, где п -с N. Слова 
«разреженный» означают, что, хотя в большом векторе N элементов, в каждый 
момент времени не более п из них отлично от некоторой константы еО. Как и 
выше, тип элементов здесь — это обычно байт или блок, а в реализациях кроме 
«основных» базовых структур используются «небольшие» вспомогательные векторы, 
элементами которых являются нисла или.ссылки, 

    ЗАДАЧИ И УПРАЖНЕНИЯ 

    Во всех реализациях ниже кроме указанных базовых структур можно 
использовать также «небольшие» вектора чисел и ссылок, если это понадобится. 

    17. ПРОСТЕЙШАЯ ФАЙЛОВАЯ СИСТЕМА	265 

    1. Реализуйте большой разреженный вектор элементов типа Б на базе 
маленького вектора элементов типа Е. 
    2. Реализуйте исполнителя «р динамических векторов блоков» ип Case одного 
вектора блоков. 
    3. Реализуйте исполнителя «р динамических векторов блоков» ип би.чс 
быстрого маленького буферного пула блоков И исполнителя «Вторичная память». 
    4. Модифицируйте исполнителя «Виртуальная память» так, чтобы он работал не 
с байтами, а с элементами типа Е, где тип Е ==, нектор байт (1..длина) и 
величина «длина» делит величину «длина блока». 
