    17. Простейшая файловая система 

    В этом разделе мы реализуем новую структуру данных — простейшую файловую 
систему — на базе исполнителя «Диск», Однако прежде чем формально ставить 
основную задачу программи-ромипия, т. е. выписывать системы предписаний 
искомого исполнителя «Простейшая файловая система» (А) и базового исполнителя 
«Диск» (}',), кратко иоиспнм, откуда эта" задача возникла. 
    При работе е илектроино-пычислитсльными машинами (ЭВМ), которые иысгумшот 
у нас в роли Универсальных Выполиителей, возникнет необходимость хранения 
большого количества разнообразии!! информации, в частности, текстов программ. 
До сих пор мы могли считать, что Универсальному Выполнителю можно вручить кипу 
исписанных листов бумаги и далее он автоматически выполнит Аядппную прогрлмму. 
Эта модель, однако, хороша только в том елучие, если УшшерсялышП Пыполнптоль 
является человеком. На лряншне, при рягюто с ;-ЖМ тексты программ должны быть 
закодированы с помощью последовательностей нулей и единиц. Такие 
моглсдопателыюсти можно запомнить, хранить и при необходимо-гтм иоспроизвести, 
например на магнитной ленте подобно 'тому, как прямятся и воспроизводятся на 
магнитофонных кассетах последо-шпг.'и.ности звуков. 
    Использование магнитофона для хранения информации, однако, IIP очень 
удобно; для записи или воспроизведения требуемой ин-ф|||1М1Щии ленту придется 
перематывать к нужному месту, что не п'ими. быстро. Иное дело проигрыватель — 
там иглу можно прямо not i яви rii иуда надо! Поэтому при работе с ЭВМ для 
хранения информации используют специальное устройство, называемое дис' Кпм, 
которое объединяет идеи магнитной записи/воспроизведения ч возможностью 
быстрого доступа к любому месту пластинки. Диск Можно представлять в виде 
покрытой магнитным слоем вращаю

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

    пуст файл или нет и т. п. Поскольку при изменениях файла информация о нем 
также может измениться, то во, .всех предписаниях, меняющих файл, ключ 
jявляeтcя входно-выходным параметром. 
    Предписания 4—13 предназначены для работы внутри файла и являются 
симбиозом предписаний последовательности (встать в начало, прочесть вперед, 
добавить в конец) и стека (добавить в конец, взять из конца). Кроме того,' они 
позволяют читать последовательность в обратном порядке (встать в конец, 
прочесть назад). Фигурирующий в системе предписаний тип 
    «строка» — это 
    запись (длина  :0 ..  132, 
    текст: вектор символ (1  ..   132)) 
    Другими словами, строка — это вектор символов некоторой фиксированной 
длины (например, длины 132) вместе с указанием, какая часть этого вектора 
является информационной. Например, для пустой строки поле «длина» будет иметь 
значение 0, а содержимое поля «текст» неважно. Наоборот, для строки 
максимально возможной длины все содержимое вектора в поле «текст» значимо. 
    От файловой системы требуется, чтобы она использовала место на диске, 
насколько это возможно, экономно, например чтобы пустые строки «почти» не 
занимали места. 
    Так как диск содержит ограниченное количество блоков, то в систему 
предписаний файловой системы включены предписания «можно создать файл» и 
«можно добавить строку», которые выполняют роль предписания «есть свободное 
место». Наличие двух предписаний, одно из которых к тому же имеет параметры, 
вызвано тем, что для создания файла или для добавления той или иной строки 
требуется разное «количество» места, и может оказаться, что одна из этих 
операций невыполнима, а другая выполнима. 
    Исполнителя «Простейшая файловая система» надо реализовать над заданным 
базовым исполнителем «Диск» со следующей системой предписаний: 
    1. начать работу 
    2. записать <вх : В : блок) в блок <вх : k : помер блока) 
    3. прочесть блок (вх : k : номер блока) в <вых i В : блок) 
    4. кончить работу типы: 
    блок = вектор байт(1 ,, 512) 
    байт =- символ 
    номер блока = 0.. 4093 
    Как уже отмечалось, особенность диска в том, что он сохраняет свое 
состояние  мегйду~«кончить»  и   «начать»  работу. 

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

    Обратите внимание, что система предписаний »того исполнителя совпадает с 
системой предписаний исполнителя «Вторичная память» из предыдущего раздела. 
Это связано с тем, что обычно под вторичную память -отводится либо отдельный 
диск, либо некоторая фиксированная часть того же диска, на котором хранятся и 
тексты. Во втором случав файловая система либо не должна трогать отведённую 
под вторичную память область на диске, либо должна обеспечивать реализацию 
вторичной памяти над собой. Мы, однако, этими вопросами заниматься не будем. 
    Основные идеи реализации. Итак, задача состоит в том, чтобы реализовать 
файловую систему на базе диска. Поскольку файлов может быть много, а размеры 
файлов (измеряемые в. блоках) могут меняться в процессе работы, то, чтобы 
избежать массовых операций с блоками, воспользуемся ссылочной реализацией. 
Здесь, однако, нельзя завести кроме диска вспомогательный вектор ссылок — ведь 
содержимое диска без информации о ссылках представляет просто «кучу обрывков 
от разных файлов», а требуется, чтобы файлы сохранялись между концом и началом 
работы фай« лопой системы. Таким образом, ссылки тоже надо хранить где-то ни 
диске. Имеется два естественных решения: 1) собрать все ссылки п хранить их п 
специально выделенном месте диска, например п мпчллс; 2) хранить ссылки прямо 
в том блоке, к которому они ОТНОСЯТСЯ. 
    Мы выберем второе решение и будем в каждом .блоке в пер-и ых 4 байтах 
хранить ссылку на следующий блок, а во вторых А байтах — ссылку на предыдущий. 
Ссылку будем записывать в имде четырехзначного десятичного числа, т. е. с 
помощью цифр от 0 до 0, Например, если следующим за блоком 3544 является влок 
1(17,'), то 1IIIIIIIHCM п пгршлг 4 б;м"|та 3544-го блока число 1673; • мерный 
ОлЛг цифру 1, по нторой — 6, в третий — 7 и в чет-nrpiufi 3. Пели ссылка 
меньше 1000, то дополним ее слева, н& анпчлщими нулями до 4 цифр; например, 38 
запишем как 0038. 
    Как обычно, число траекторий, на которые разбиваются блоки диска, будет 
равно числу файлов, увеличенному на 1 (т. е, на траекторию «свободное 
.место»). В отличие от предыдущих ссылочных решшзаций число траекторий файлов 
здесь не фиксировано, а ме-нистся в процессе работы. Поэтому решим, что 
траектория «свободное место» будет начинаться с нулевого блока (нил свободного 
мест»), а траектории файлов специально выделенных служебных Ллокоп нил иметь 
не будут — следующим за последним блоком и файле будет первый, а предыдущим 
для первого — последний. При выполнении некоторых операций нам понадобится не 
только знать, есть или нет свободные блоки на диске, но и знать, сколько их,_ 
Поэтому введем^ в исполнителе «Простейшая файловая 

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

    система» глобальный объект, в котором будем хранить число сш> бодных 
блоков. Это число, впрочем, между концом и началом работы файловой системы 
тоже надо хранить где-то на диске. Мы будем хранить^ его в нулевом блоке в 
байтах с номерами 9,, 12 'сразу вслед за ссылками. 
    Наконец, надо понять, что же такое ключ файла. Взглянем на производимые   
с  файлом   операции.   У   файла   кроме  содержимого есть начало, конец и 
граница между прочитанной и непрочитанной частью. Примем решение, что ключ  
будет содержать всю эту информацию.   Поскольку   строки   файла   будут   
как-то   располагаться в  блоках траектории файла, то указание па  границу 
между строками — это пара: указание на блок и указание па границу между 
байтами .в  этом  блоке. Мы  будем  границу  между  байтами задавать индексом 
i левого (младшего) байта. Этот индекс удобен тем, что определен  и  для > 
крайних  случаев.   Например,  для  положения перед первой  строкой файла  1 = 
8   (строки  в любом  блоке начинаются  с 9  байта — байты   1..8 заняты 
ссылками).  Таким  образом, решим, что тип ключ будет выглядеть так: ключ = 
запись (первый	блок : номер блока, ./прочитанный блок : номер блока, ,' ^ 
прочитанный байт : номер 'байта, 'последний      блок : номер блока, 
'^последний      байт: номе р байта, число блоков в файле:число блоков) 
    Заметьте, что хранится только номер блока начала файла -=» номер байта 
хранить не надо, так как известно, что. CTJJOKH __файла начинаются^ 9-го 
_байта в первом блоке. Число блоков в файле является полезной информацией, 
которая понадобится нам в дальнейшем. 
    Реализация. Мы решили все основные вопросы, кроме одного —• как же именно 
будут располагаться строки вутри файла. Отложим пока решение этого вопроса и 
реализуем работу с файлами в целом, т. е. работу с файлами как с траекториями блоков, 
    исполнитель Простейшая файловая система . СП: 
    ,      0. инициализировать диск 
    1. начать работу 
    2. можно создать файл 
    3. создать файл (вых : d>: ключ) 
    I да/иет 
    4. файл (вх:ф:ключ) пуст	(да/нет 
    5. можно добавить строку (вх: ф: ключ.вх.! С t строка)  i да/не! 

    ПРОСТЕЙШАЯ ФАЙЛОВАЯ СИСТЕМА 271 

    16. добавить строку в конец файла (вх/вых : ф : ключ, вх : С : строка) 
    j     •«-     добавить {вх : d) символов из (вх : t) в конец (вх/вых : ф) 
t      7. взять строку из конца файла (вх/вых: ф:ключ, ,	вых: С : строка) 
    ,     —       взять (вх: d) символов из конца (вх/вых : ф) в {вых : t) I   
  8. в начале файла (вх: ф : ключ)	•••    : да/нет 
    9. в конце файла (вх: ф : ключ)	: да/нет 
    10. пстлть в начало файла (вх/вых: ф : ключ) 
    11. встать в конец файла (вх/вых: ф: ключ) 
    12. прочесть строку вперед (вх/вых : ф : ключ,вых: С : строка) г     —     
прочесть вперед (вх-.d) символов из (ф) в (вых:1) t    13. прочесть строку 
назад {вх/вых : ф : ключ, вых : О: строка) I     —       прочесть пп:шд (пх : 
d) символов из {ф) в (вых 11) Г    И. удялпть <|шпл (их/них : ф: ключ) 
    t     — захватить блок (вых : k : номер блока) i     — освободить блок 
(вх: k: номер блока) 
    •     — связать (Bx:kl,k2:0 .. макс номер блока на диске) .     — 
установить поле {вх : i) в блоке (вх : k) в (вх : п) 
    •     — прочесть число из поля <i) в (выхчп) 
    •     — iiniiiicim. число (вх : п) в поле (i) .     — число (вх : t) : 0 
..  макс число 
    •     — текст {вх: п): вектор символ (1  ,. длина числа) 
    i    15. кончить работу 
    t 
    ,    константы:	,..   .    . 
    макс номер блока па диске     «=4095 
    число йпПт в Ллпке	—  512 
    мнкс число символом и строке»-   132 
    млкс число	=4095 [т. в. максимум (4095,132) 
    длина  числа	ая      4|т. е. число цифр в   числе 
    обозначения!      - >.   , 
    нил == 0	; 
    @ след        == 1	[начала служебных полей 
    @ пред       == в след + длина числа  ) в любом блоке диска 
    последний служебный байт блока == 2* длина числа 
    Ф свободных == @ пред + длина числа | только в нулевом блоке 
    Другими словами, JB твдгев/ом блоке под служебную информа* 11ию__занять1 
„первые. 1„2„байт (и больше в нулевом блоке ничего нет}, а во всех остальных 
блоках — первые 8 байт, Например, если 

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

    файл состоит из трех блоков  1000, 0038 и 2017, то первые байты этих 
блоков будут содержать следующие символы: 
    блок 1000 
    блок 0038 
    блок 2017 
    0	0	3	3	2	0	1	7	... 
    
    
    2	0	1	7	1	0	0	0	... 
    
    
    1	0	0	0	0	0	3	8	... 
    поле «@след» 
    поле с@аред» 
    .	типы: 
    .	номер символа =»1 .. макс число символов в строке 
    .	строка•• запись (длина:0..макс число символов в строке,   \ 
    .	текст ; вектор символ (номер символа)) 
    .	байт                  «= символ 
    .	номер байта     = 1..число байт в блоке 
    ,	блок                   <= вектор байт (номер байта) 
    .	номер блока     =1..макс номер блока на диске 
    .	число блоков    =0..макс номер блока на диске 
    .	ключ = запись (первый          блок: номер блока, 
    .	прочитанный блок : номер блока, 
    .	прочитанный байт:номер байта, 
    .	последний      блок: номер блока, 
    .	последний      байт: номер байта, 
    .	число блоков в файле:число блоков) 
    • 
    .	объекты: 
    .	первый свободный блок:0..макс номер блока на диске 
    .	число свободных            :число блоков 
    .	буфер                             :блок 
    Наличие объекта буфер требует пояснений. Система предпи-' саний 
исполнителя диск позволяет прочесть или записать блок толь« ко целиком. 
Поэтому для получения любой информации из блока его сначала надо целиком 
прочесть в память. Именно для этого и предназначен объект буфер. При изменении 
части информации в блоке надо сначала весь блок "прочесть в " буфер, потом 
изменить соответствующую часть буфера ""и, наконец, записать весь буфер( на диск. 

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


    . используемые  исполнители: 
    .    Диск 
    конец описаний |- ————— — 
    программа инициализировать диск . дано       : . получить: 
    .	Диск.начать работу 
    .	первый свободный блок := нил 
    .	число свободных             := О 
    .	связать (нил.нил) 
    .	цикл Vk е номер блока реверс выполнять 
    i	.     освободить блок (вх:к) 
    .	конец цикла                                   .,     (   . /( 
    конец программы 
    программа начать работу . дано        : . получить: 
    .   Диск.начать работу	, 
    .   Диск.прочесть блок (пил) в (вых:буфер) 
    .   прочесть число из поля (в след) в (вых: первый свободный блок} 
    .   прочесть число из поля <Ф свободных) в (вых: число свободных) 
    конец программы 
    Программа «прочесть число из поля <вх s i> в <вых s п>» читает 4 (длина 
числа) байта из буфера, начиная с индекса i, и преоб* разует эту символьную 
информацию (последовательность из 4 цифр) и целое число--• ин.'ИИ'ние объекта п. 
    прогрнмм» можно создать файл : да/нет > программа создать файл {вых : ф : 
ключ) . дано       ; можно создать файл . получить: 
    (число свободных > 0) 
    захватить блок {вых; связать (k,k) ф.первый	блок ф.прочитанный блок 
ф.прочитанный байт ф. последний      блок 
    k k 
    последний служебный байт блока := к 
    ,   ф.последний      байт := последний служебный байт блока •   ф.число 
блоков в файле := 1 конец программы 


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


    программа удалить файл (вх/вых: ф: ключ) . дано       : . получить: 
    .   связать (ф.последний блок, первый свободный блок) 
    .    первый свободный блок := ф.первый-блок 
    ,    число свободных.увеличить на ф.число блоков в файле 
    .   связать {нил,ф.первый блок) 
    конец программы 
    программа захватить блок (вых: k: номер блока) . дано       : число 
свободных > О . получить: 
    .   k := первый свободный блок 
    .    Диск.прочесть блок (вх:к) в (вых : буфер) 
    .   прочесть число из поля (@ след) в {вых: первый свободный блок) 
    .    число свободных.уменьшить на 1 
    .   связать (нил,первый свободный блок) 
    конец программы 
    программа освободить блок {вх : k: номер блока) . дано        : . получить: 
    .   связать {k,первый свободный блок) .   первый свободный блок := k .   
число свободных.увеличить на 1 .   связать (нил.к) конец программы 
    программа связать {вх:k_l,k2:0..макс номер блока на диске) 
    . дано        : 
    . получить: [установить ссылки между блоками kl и k2 на днске( 
    .	| а кроме того, если попадется нулевой блок, то 
    .	| записать в него текущее состояние глобального 
    .	| объекта "число свободных" 
    . установить поле (вх:@след) в блоке (вк:Ы) в {вх: k2) . установить поле 
(вх:@пред) в блоке {вх: k2) в {ex:kl) конец программы 
    программа установить поле {вх: i) в блоке {вх: k) в (вх;п) . дано       I  
   k:O..M3KC номер блока на диске, .	i: номер байта, .                    п:0. 
.макс число 
    получить: |в блок k, начиная с байта i, записано число п ,	| в символьном 
виде. Если блок k нулевой, то ,                     | кроме того, надо поле "ф 
свободных" в нулевом .                     | блоке установить в состояние 
объекта (                     |"число свободных"                               


    Ц7, ПРОСТЕЙШАЯ ФАЙЛОВАЯ СИСТЕМА 273 


    .   Диск, прочесть блок {k) в (вых : буфер)	"    ' .    записать число (п) 
в поле (i) 
    если k = нил то 
    .    записать число (число свободных) в пола (^ свободных) 
    конец если 
    .   Диск.записать (вх : буфер) в блок (k) конец программы 
    Таким образом, мы реализовали DCIO работу с блоками. Заметьте, что всякий 
раз, когда число свободных блоков изменяется (по предписаниям «удалить файл», 
«захватить блок», «освободить блок»), измененное число свободных блоков 
записывается и в нулевой блок на диск. Так что после выполнения любого 
вызванного извне предписания файловой системы диск находится в корректном 
состоянии, т. е. содержит всю информацию „о траекториях и числе свободных 
блоков. Поэтому по предписанию «кончить работу» ни-чего делать не надо: 

    программа кончить работу == Диск.кончить работу 

    Глобальные объекты «первый свободный блок» и «число свободных» являются, 
таким образом, просто копией соответствующих полей нулевого блока и введены 
только для оптимизации, чтобы не читать нулевой блок, когда нужно посмотреть 
на эту информацию. 
    Реализуем теперь преобразования чисел в последовательность из 4 цифр и обратно. 

    программа прочесть число из поля (i) в (вых;п) 
    . дано        : i: номер байта	•• 
    . получить: п : 0..макс число 
    .    п := число (буфер (i..i+длина числа)) 
    конец программы 
    программа записать число (вх: п) в поле (1) 
    . дано        :   1: номер байта, 
    ,	п : 0. .макс число 
    . получить: 
    .   буфер (i..i -Ь длина числа) :=» текст (вх:п) конец программы 

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

    Использованная в этих двух программах запись буфер (1.. i + длина числа), 
называемая вырезкой, служит обозначением для части вектора бу* фер, начиная с 
элемента с индексом i и кончая элементом с индексом i + длина числа (т. е. 
состоит из 4 элементов). С этой вырезкой можно работать так, как если бы это 
был отдельный 4-элементный вектор символов; в частности, можно присвоить вы« 
резке значение другого вектора символов из 4 элементов — вектора, который 
вырабатывается в качестве значения предписания «текст», 
    программа число (вх: т):0..макс число	L1           J4 
    , дано       : t: вектор символ (I.. длина числа) 
    . получить!	А-С^;       И/ . 
    .   ответ :=• О 
    •    цикл V 1 е 1.. длина числа выполнять 
    .   .    ответ :=- ответ * 10 + (код (t (i)) — код ("О")) 
    .   конец цикла 
    конец программы 
    Функция код сопоставляет каждому символу целое число —• его код (например, 
букве А — число 65, букве В — число 66 и т. п.). Коды цифр идут подряд, т. е. 
код("1") = код("0")+ 1, код("2")=' '= код("Г')+ 1 и т. п. Таким образом, разность 
    код (t (0) - код ("О") 
    8то и есть значение типа число, соответствующее цифре t(i), 
    Обратное преобразование из числа, являющегося кодом неко< торого символа, 
в сам символ осуществляет функция «символ», Обе эти функции являются 
стандартными (см. приложение 1), 
    программа текст {вх : п) : вектор символ (1.. длина числа) . дано       : 
п:о--макс число 
    • получить: 
    .   s := п 
    .   цикл Vis 1..длина числа реверс выполнять 
    .   ,      ответ (i) := символ (s mod 10) 
    ,   ,     s := частное (s, 10) 
    .   конец цикла 
    конец программы 
    Итак, мы реализовали все программы, работающие с файлами в целом, включая 
и необходимые подпрограммы. Теперь надо pea» лизовать предписания 4—13, 
работающие внутри файла, Некоторые 

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

    из этих предписаний, очевидно, могут быть реализованы на база ключа файла 
вообще без каких-либо действий с диском и без знания расположения строк файла 
в блоках: 
    программа файл {вх : ф : ключ) пуст: да/нет == 
    (ф. последний блок= ф-.первый блок и 
    ф. последний байт = последний служебный байт блока)      •'.. программа 
встать в начало файла (вх/вых : ф : ключ) ==« 
    ф. прочитанный блок := ф. первый блок 
    ф. прочитанный байт : = последний служебный байт блока программа в начале 
файла {вх : ф : ключ) : да/нет == 
    (ф. прочитанный блок = ф. первый блок и 
    ф. прочитанный байт = последний служебный байт блока) программа встать в 
конец файла (вх/вых : ф : ключ) ==». 
    ф. прочитанный блок := ф. последний блок 
    ф. прочитанный байт := ф. последний байт программа в конце файла {вх : ф : 
ключ) : да/нет ==» 
    (ф. прочитанный блок = ф . последний блок и 
    ф. прочитанный байт = ф. последний байт) 
    Осталось реализовать предписания, которые собственно и составляют основу 
работы с файлом: добавление и взятие строк в конце файла, чтение строк вперед 
и йазад, а также анализ, можно ли добавить строку. Таким образом, пора 
разобраться с последним отложенным вопросом и решить, как же именно будут 
храниться строки в блоках. Поскольку в требования к файловой системе входило, 
насколько это возможно, экономное использование места на диске, то будем 
хранить только информационные части строк, т. е. части с индексами от 1 до 
длины строки, а «мусор» — компоненты строк с индексами большими длины строки — 
никуда не записывать. Поскольку, кроме того, надо уметь читать строки и 
вперед, и назад, то длину строки (4 байта в таком же виде, как и ссылки) будем 
записывать на диск _до и после ее информационной части. При этом способе 
пустая строка будет занимать 8 байт на диске: 4 байта длины (т. е. четыре 
символа 0), потом информационная часть, которая в этом случае не занимает ни 
одного байта, и затем еще раз 4 байта длины. 
    Если при чтении строки мы дойдем до границы блока, то следующие байты 
будем читать из начала следующего блока. Другими словами, при выбранном 
способе хранения строк на диске стр_ока_м ож_е 
    В частности, 4 байта для длины строки, о которых говорилось выше, могут 
оказаться в разных блоках. Если граница блока встретится при добавлении строки 
к файлу, то в траекторию файла надо добавить новый блок и продолжать запись в него. 

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

    Вот несколько  примеров   размещения   строк  в   блоках   файла, Файл, 
состоящий из двух строк 
    Я Вас любил, 
    Любовь еще, быть может, 
    размещенный в  блоке с номером  1000   (точки обозначают ошво* лы, 
значения которых неизвестны или неважны)! 
    100(^ООС|0012Я Вас любил,0012)э023Любовь еще, быть может,0023)... 
    файл, состоящий из трех строи 0666 1611011 1986 
    размещенный в блоке с номером 1000: 
    1000100«Ю040666рОО^ОЩ1611011000^000^198^004... 
    С  содержательной   точки  зрения  эта  последовательность  сим« волов 
состоит из следующих групп: 
    вел     @np       di	ti        d|         di           tj          di      
   dj         tj         ds 
    1000	1000	0004	0666	0004	0007	1611011	0006	0004	1986 1 0004 1 ... 
    где @сл, @пр — ссылки на следующий и предыдущий блоки в коль» це блоков 
файла; di. ti—длина и информационная часть 1-й строки текста. 
    Наконец,	приведем        пример           размещения   строки 
"++++А++++А++++" длины 14, переходящей из блока 0038 в блок 1000: 
    блок 0038 
    блок 1000 
    1000 
    001 
    0038 
    программа можно добавить строку {вх: ф : ключ,С : строка): да/нет == 
((число байт в блоке — ф.последний байт) + 
    число свободных * ( число байт в блоке — последний служебный байт блока) ^ 
    С.длина + 2 * длина числа) программа добавить строку в конец файла 
    (вх/вых: ф, вх:: С: строка) 


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


    . дано       ! можно добавить строку (ext ф:ключ,вх: С (строка) , получить; 
    .   t :«= текст (С.длина) 
    . добавить (длина числа) символов из (t)	в конец (ф) . добавить (С.длина) 
символов из (С.текст) в конец (ф) . добавить (длина числа) символов из {t) в 
конец (ф) конец программы 
    программа добавить (вх : d) символов из (вх: t) в конец (вх/вых: ф) . дано 
       : t:вектор элементов типа символ с индексом 1 ..d . получить: 
    .	Диск.прочесть блок (ф.последний блок) в (вых: буфер}1 
    .	цикл V i её l..d выполнять 
    .	.      ф.последний байт.увеличить на 1 
    .	.     если ф.последний байт > число байт в блоке то 
    .	.      .     записать число (первый  свободный  блок)  в   поле (@ след) 
    .	.     .    Диск.записать (вх: буфер) в блок (ф.последний блок) 
    .	.  . захватить блок (вых: k) 
    .	.  . записать число (ф.первый блок) "" в поле (вслед) 
    .	.  . записать число (ф.последний блок) в поле (@ пред) 
    .	.  . ф.последний блок := k 
    .	.  . ф.последний байт := последний служебный бант блока 
    ...	+1 
    .	.  конец если 
    .	.     буфер (ф.последний байт) := t(i) 
    .	конец цикла 
    ,	Диск.чипт-нп. (ох: буфер) п блок (ф.последний блок) 
    КЧМГЦ    |||><1! pUMMbl 
    программа взять строку из конца файла 
    .	(вх/вых : ф, вых : С : строка) 
    . дпно        : файл (вх:ф) не пуст 
    . получить: 
    . объекты : 
    .    t:вектор элементов типа символ с индексом 1..длина числа 
    .   ниить (длина числа) символов из конца (ф) в (вых: t) 
    .   С.длина := число (вх: t) 
    .   нэить (С.длина)         символов из конца (ф) в (вых: С.текст) 
    .   изять {длина числа) символов из конца (ф) в (вых: t) 
    конец программы 


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


    программа взять (их: d) символов из конца (вх/вых: ф) в (вых: t) 
    . дано        : 
    . получить: t:вектор элементов типа символ с индексом l..d 
    .	если в конце файла (вх:ф) то были в конце := да конец если 
    .	Диск.прочесть блок (ф.последний блок) в (вых: буфер) 
    .	цикл V i е l..d реверс выполнять 
    .	.     утв: ф.последний байт > последний служебный байт блока 
    .	,     t (i) :=з буфер (ф.последний байт) 
    .	.     ф.последний байт.уменьшить на 1 
    .	.      если ф.последний байт = последний   служебный   байт   блока 
    .	.  то 
    .	.  t k := ф.последний блок 
    .	.  . прочесть число из поля (@ пред) в {ф.последний блок) 
    .	.  . ф.последний байт := число байт в блоке 
    .	.     .    освободить блок (вх: k) 
    .	.      .    связать (ф.последний блок,ф.первый блок) 
    .	.      ,    Диск.прочесть блок (ф.последний блок) в (вых : буфер) 
    .	.      конец если 
    .	конец цикла 
    .	Диск.записать (вх: буфер) в блок (ф.последний блок) 
    •	если были в конце то встать в конец файла (ф) конец если 
    конец программы 
    программа прочесть строку вперед 
    .	(вх/вых : ф : ключ,вых : С : строка) 
    . дано       : не в конце файла (вх: ф : ключ) 
    . получить: 
    . объекты : 
    .    t: вектор элементов типа символ с индексом 1..длина числа 


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


    .   прочесть вперед (длина числа) символов из (ф) в (t) 
    •    С.длина := число (вх : t) 
    .   прочесть вперед (С.длина)        символов из (ф) в (С.текст) 
    .   прочесть вперед (длина числа) символов из (ф) в (t) 
    конец программы 
    программа прочесть вперед (вх: d) символов из (ф) в (вых i f) 
    . дано       : 
    . получить: t:вектор символ (l..d) 
    ,	Диск.прочесть блок (ф.прочитанный блок) в (вых: буфер) 
    .	цикл V i е l..d выполнять 
    •	.    ф.прочитанный байт.увеличить на 1 
    .	.	если ф.прочитанный байт > число байт в блоке то 
    .	f	t    прочесть число из поля (<Ш след) в (ф.прочитанный блок) 
    .	.	»    ф.прочитанный байт :«= последний служебный байт блока 
    .   .    ,    Диск.прочесть блок (ф.прочитанный   блок) в (вых: буферу 
    •    .    конец если 
    .    ,    t(i) :•= буфер (ф.прочитанный байт) 
    .   конец цикла 
    конец программы 
    программа прочесть строку назад (вх/вых : ф : ключ,вых : С : строка) 
    . дано        : не в начале файла (вх : ф : ключ) 
    . получить:	. 
    . объекты с 
    .   t:вектор элементов типа символ с индексом 1..длина числа 
    .   прочесть назад (длина числа) символов из (ф) в (t) 
    .    С.длина := число (ex:t) 
    .   прочесть назад (С.длина)         символов из (ф) в (С.текст) 
    .    прочесть назад (длина числа) символов из (ф) в (t) 
    конец программы 
    программа прочесть назад (ex:d) символов из (ф) в (вых:1) 
    . дано        : 
    , получить: t: вектор символ (l..d) 
    .	Диск.прочесть блок (ф.прочитанный блок) в (вых : буфер) 
    ,	цикл V i e l..d реверс выполнять 
    ,	.     t (i) := буфер (ф.прочитанный байт) 
    .	.     ф.прочитанный Сшит.уменьшить на 1 
    ,	.      если ф.ирочнпмший байт = последний служебный байт блока 
    .,	.      .то 
    ,	.     .    прочесть число из поля (в пред)  в  (ф.прочитанный блок) 
    ,	.      .     ф.прочитанный байт := число байт в блоке 
    ,	,     .    Диск.прочесть блок (ф.прочитанный блок) в (вых : буфер) 
    ,	.     конец если 
    .	конец цикла конец программы конец исполнителя 
    |- = = = = =, = = = ===» = = = » = =, = =.=,-=_=._.,-

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

    1, Модифицируйте проект так, чтобы в случае, когда нужный Ллок уже 
находится в буфере, он с диска не читался, чтобы изменения информации сначала 
происходили только в буфере и чтобы буфер записывался на диск только тогда, 
когда в этом действи

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

    тельно есть необходимость  (аналогично проекту «Виртуальная пат мять» из 
предыдущего раздела). 
    2. Модифицируйте. проект так, чтобы можно было добавлять и брать строки на 
только в конце, но и в начале файла (т, е. чтоб над файловой Системой можно 
было реализовать и дек тоже), 
    3. Существующий проект работает только с диском фиксированного размера, 
заданного заранее е помощью константы «макс номер блока на диске». 
Модифицируйте проект так, чтобы он работал с диском любых размеров, считывая 
действительное число блоков на диске из специально отведенного для этой цели 
места в нулевом блоке. В предписании «инициализировать» размер диска в блоках 
следует указывать во входном параметре, 
    4. Измените реализацию Простейшей файловой системы так, чтобы попытка 
выполнить любую операцию с файлом после его удаления приводила к отказу. 
    Указание. Добавьте в предписания, у которых ключ файла является входным 
или входно-выходным параметром, какой-нибудь анализ корректности состояния 
ключа, например проверку, что ключ.число блоков в файле > 0. 
    А в программу удаления файла добавьте «разрушение» ключа, т. е. установку 
в некорректное состояние. 
    5. Модифицируйте проект так, чтобы все ссылки хранились одним «куском» в 
начале диска, считывались в память по предписанию «начать работу» файловой 
системы и записывались обратно по предписанию «кончить работу». 
    6. Используя исполнителя «Простейшая файловая система» и, если надо, 
изменяя его, реализуйте исполнителя «Именная файловая система», в которой 
каждый файл имеет имя (вектор символов фиксированной длины, например длины 
12). Между концом и началом работы файловой системы должны сохраняться не 
только сами файлы, но и их имена. При создании или удалении файла в качестве 
входного параметра указывается его имя. Предписания для работы внутри файла 
используют не имя, а ключ (как и в реализации выше); ими можно пользоваться 
только между «начать работу с файлом <вх; имя, вых: ключ)» и «кончить работу с 
файлом <вх: ключ)». Таким образом, ключ существует только .на время, работы с 
файлом и получается по имени файла предписанием «начать работу с файлом». 
(Именно такие файловые системы обычно используются при работе на ЭВМ.) 
    7. Сделайте из буфера буферный пул (т. е. увеличьте его размеры с одного 
блока до нескольких). Реализуйте файловую систему, используя для ускорения ее 
работы идеи реализации виртуальной памяти из предыдущего разделата. 