Книга: Архитектура операционной системы UNIX

10.3.1 Символьные списки

10.3.1 Символьные списки

Строковый интерфейс обрабатывает данные в символьных списках. Символьный список (clist) представляет собой переменной длины список символьных блоков с использованием указателей и с подсчетом количества символов в списке. Символьный блок (cblock) содержит указатель на следующий блок в списке, небольшой массив хранимой в символьном виде информации и адреса смещений, показывающие место расположения внутри блока корректной информации (Рисунок 10.10). Смещение до начала показывает первую позицию расположения корректной информации в массиве, смещение до конца показывает первую позицию расположения некорректной информации.

Рисунок 10.10. Символьный блок

Ядро обеспечивает ведение списка свободных символьных блоков и выполняет над символьными списками и символьными блоками шесть операций.

1. Ядро назначает драйверу символьный блок из списка свободных символьных блоков.

2. Оно также возвращает символьный блок в список свободных символьных блоков.

3. Ядро может выбирать первый символ из символьного списка: оно удаляет первый символ из первого символьного блока в списке и устанавливает значения счетчика символов в списке и указателей в блоке таким образом, чтобы последующие операции не выбирали один и тот же символ. Если в результате операции выбран последний символ блока, ядро помещает в список свободных символьных блоков пустой блок и переустанавливает указатели в символьном списке. Если в символьном списке отсутствуют символы, ядро возвращает пустой символ.

4. Ядро может поместить символ в конец символьного списка путем поиска последнего символьного блока в списке, включения символа в него и переустановки адресов смещений. Если символьный блок заполнен, ядро выделяет новый символьный блок, включает его в конец символьного списка и помещает символ в новый блок.

5. Ядро может удалять от начала списка группу символов по одному блоку за одну операцию, что эквивалентно удалению всех символов в блоке за один раз.

6. Ядро может поместить блок с символами в конец символьного списка.

Символьные списки позволяют создать несложный механизм буферизации, полезный при небольшом объеме передаваемых данных, типичном для медленных устройств, таких как терминалы. Они дают возможность манипулировать с данными с каждым символом в отдельности и с группой символьных блоков. Например, Рисунок 10.11 иллюстрирует удаление символов из символьного списка; ядро удаляет по одному символу из первого блока в списке (Рисунок 10.11а-в) до тех пор, пока в блоке не останется ни одного символа (Рисунок 10.11 г); затем оно устанавливает указатель списка на следующий блок, который становится первым блоком в списке. Подобно этому на Рисунке 10.12 показано, как ядро включает символы в символьный список; при этом предполагается, что в одном блоке помещается до 8 символов и что ядро размещает новый блок в конце списка (Рисунок 10.12 г).

Рисунок 10.11. Удаление символов из символьного списка

Рисунок 10.12. Включение символов в символьный список

Оглавление книги