OVERLAYS! оверлеи линковщики своп

[bigral]

Всем имеющим хоть какой-то практический опыт "обхода" ограничений накладываемых адресуемым пространством просьба высказать свои мысли, опыт, наработки, советы, впечатления в этой теме.

Для тех кто "в танке" - суть проблемы тут http://en.wikipedia.org/wiki/Overlay_%28programming%29

[Barmaley_m]

Я в 1996г создавал программу управления программатором ПЗУ. Имея 256К ОЗУ на ZX, приходилось работать с двумя буферами образа ПЗУ по 64Кб каждый, применяя страничную адресацию.

Буфера были размещены по границам страниц. Были подпрограммы чтения и записи байта в буфер по 16-битному адресу внутри буфера. Работали они очень медленно, ведь для чтения или записи каждого байта приходилось вычислять адрес, переключать страницы, а потом переключать их назад. В результате скорость работы программатора определялась не скоростью работы микросхем ПЗУ или самого программатора, а скоростью доступа в буфер. Одним словом, тормозно было.

Особенно большие тормоза наблюдались при чтении и записи содержимого буферов на диск. Ведь если подготовка данных занимает слишком большое время - то головка проскакивает над нужным сектором, и приходится ждать следующего оборота диска. Поэтому для целей чтения и записи на диск пришлось сделать блочный доступ к буферам в памяти. То есть с дискеты считывалось несколько секторов (как правило, дорожка целиком) в промежуточный буфер, после чего из промежуточного буфера данные уже помещались в основной, тоже побайтно. Тоже тормоза, но чуть меньше.

Тем не менее, благодаря тому, что я не вылизывал эти частные моменты, программа "Omniprog" управления программатором была создана в рекордно короткие сроки и имела множество полезных функций и красивый интерфейс пользователя. А тормоза - дело относительное. Несмотря на неэффективный доступ к памяти, Omniprog работал быстрее, чем другие доступные на то время программаторы, в том числе те, которые работали на PC.

Если бы я все это дело разрабатывал сейчас - то сразу реализовал бы блочный доступ к основным буферам, т.е. извлекал оттуда или помещал туда сразу блоки, а не отдельные байты. Думаю, в этом случае основные тормоза были бы побеждены.

Но блочный доступ реализовать сложнее, чем побайтный. Например, для пересылки блока произвольной длины с произвольного виртуального адреса нужно учитывать ситуации, когда этот блок переходит через границу страницы. Также блочный доступ сложнее использовать в подпрограммах высокого уровня. Например, функция поиска строки в буфере тривиально реализуется в случае побайтного доступа. А в случае блочного - нужно разбить весь процесс на отдельные блоки и как-то отрабатывать переходы через их границы.

[SfS]

ИМХО.

Нужен манагер памяти, который умеет:

1. Создавать многостраничную кучу.
2. malloc() free() - выделение и освобождение памяти в куче.

3. memcpy() - копировать блок (без перекрытия)
4. memmove() - копировать блок (с перекрытием)
5. LongJump() - межстраничный переход
6. LongCall() - межстраничный вызов.

... Функции поиска и копирования массивов

Все адреса (указатели) - виртуальные, в формате 32 бита.
Так их проще на стеке сохранять. В незначащих битах можно хранить доп.информацию.

Для тех спеков, что умеют любую страницу в любое окно - реализация довольно проста.

Скажем:
0-3FFF - ПЗУ (может замещаться озу при копировании из страницы в страницу)
4000 - 7FFF - озу, где расположен менеджер памяти и другие неудаляемые вещи.
8000 - BFFF - 1я страница программы-библиотеки-оверлея-данных
С000 - FFFF - 2я страница данных (скажем, экран)

Таким образом, максимальный объём одного программного модуля 16К. Весьма немало.

[Vadim]

Работали они очень медленно, ведь для чтения или записи каждого байта приходилось вычислять адрес, переключать страницы, а потом переключать их назад.
А почему бы не работать с 16К блоками? Или хотя бы 256 байт, явно быстрее было бы

[Barmaley_m]

А почему бы не работать с 16К блоками? Или хотя бы 256 байт, явно быстрее было бы
Разумеется, быстрее. Но представь себе, стоит задача: найти по адресам 24F7-48A2 строку "abcde". Если использовать непосредственный доступ к памяти или подпрограмму чтения байта по логическому адресу - то такой поиск пишется легко. А если блоками - то это надо отрабатывать кучу граничных условий, размер программы разрастается, и ее становится трудно отлаживать.

В остальных ситуациях все было точно так же. Нужно было что-то делать с участком буфера ПЗУ по каким-то логическим адресам. Например, считать из микросхемы, прошить в микросхему, считать с диска, записать на диск и т.д.

Даже имея сегодняшний опыт, на ассемблере писать все эти процедуры с блочным доступом было бы значительно сложнее, в том числе с точки зрения отладки, чем с побайтовым. И заняло бы дольше времени. Как минимум день бы лишний на это ушел. А программа писалась в сжатые строки, на одном дыхании. Поэтому на оптимизацию доступа времени не нашлось. Зато все отлично работало и без глюков.

Я вовсе не говорю, что побайтовый доступ - хорошая идея. Наоборот, очевидно, что она обречена на медленность. Но зато код пишется легко. А блочный доступ конечно быстрее.

[Hacker VBI]

SfS, в tsconf имеем маппинг рам в 0, 4000, 8000, с000.
Для таких прикладных задач особо удобно.
Да,экран отдельно, в страницах

[Barmaley_m]

Вот что реально помогло бы - это выработать паттерны программирования для написания блочно-ориентированных алгоритмов.

Эта проблема до сих пор не решена для всех и каждого. По-хорошему, следовало бы преподавать такие паттерны в институтах, чтобы студенты сразу знали, как это делается. А то сейчас, с ростом памяти компьютеров, все обленились и даже при обработке аудио-, видео- и прочих больших файлов норовят загружать весь файл в память, чтобы удобнее было с ним работать.

А вот я уже давно выработал следующий паттерн для блочной обработки потоков:



#define BUFFER_SIZE 1024
void process_file_in_blocks(FILE* input_file, long file_size)
{
long bytes_remain = file_size;
int bytes_proc;
while(bytes_remain)
{
if(bytes_remain > BUFFER_SIZE)
bytes_proc = BUFFER_SIZE;
else
bytes_proc = bytes_remain;
process_block(input_file,bytes_proc);
bytes_remain -= bytes_proc;
}
}
Выглядит вроде просто, но если у вас такого еще нет - пользуйтесь на здоровье!

[alone]

Для тех спеков, что умеют любую страницу в любое окно - реализация довольно проста.

Скажем:
0-3FFF - ПЗУ (может замещаться озу при копировании из страницы в страницу)
4000 - 7FFF - озу, где расположен менеджер памяти и другие неудаляемые вещи.
8000 - BFFF - 1я страница программы-библиотеки-оверлея-данных
С000 - FFFF - 2я страница данных (скажем, экран)
К сожалению, для полного разделения сегментов 4 окон ATM (и т.п.) мало. Там лучшее решение такое:
0000-3FFF - керналь системы и стек (непереключаемый для данной задачи)
4000-7FFF - сегмент кода (переключаемый)
8000-BFFF - сегмент данных (непереключаемый для данной задачи), там же (или в нулевом окне) подпрограммы far-вызовов
C000-FFFF - окно работы с большими данными (в т.ч. с экраном) (переключаемое)

Код может быть расшарен между экземплярами одной задачи.

То есть даже нет места, чтобы сделать отдельный защищённый от записи непереключаемый сегмент кода для far-вызовов и защищённый от записи керналь (впрочем, можно специальной доработкой перехватывать команды RST и сразу переключать страницы или без керналя вручную делать NMI через порт, как на ZX Evo baseconf).

[Barmaley_m]

Я думаю, что установка фиксированных сегментов кода или данных накладывает неоправданные ограничения на приложения. Все-таки некоторые программы имеют большой код и маленькие данные, или наоборот.

Из удачных решений архитектуры ОС я могу отметить ASC CP/M. Там все, что можно (в том числе экран), было вынесено за пределы адресного пространства. Это дало 62K TPA, в которых могли размещаться пользовательские программы. В этих же 62k размещалось ядро CP/M (BDOS и CCP), но в CP/M приложениям разрешается затирать и то, и другое. По завершении приложения просто происходит перезагрузка обоих этих компонентов. Приложение, затершее BDOS, не может больше пользоваться функциями BDOS (файловая система), но при этом BIOS остается доступным (низкоуровневый ввод-вывод).

Если бы разрабатывал ось, я бы вынес ее ядро и экран за пределы адресного пространства приложений. Для доступа к расширенной памяти ввел бы в ядро функции блочного чтения и записи в "невидимое" ОЗУ по виртуальным адресам. Также, возможно, системный ввод-вывод не в адресное пространство приложения, а по виртуальным адресам в расширенную память. Чтобы лишний раз данные не гонять туда-сюда. Доступ к экрану тоже осуществлялся бы через ядро. Хотя это ограничило бы применимость такой оси. Демки и игры на ней делать не имело бы смысла.

[jerri]

Barmaley_m, а где можно пощупать ASC CP/M?

[bigral]

Интересно выходит,

1) "плоский" режим не что иное как упрощение реальной жизни, т.е. в каждом CPU адресное пространство ограниченно, а значит можно себе представить что потребуются overlays (а иначе можно было бы загрузить все проги вселенной в "резиновую" память);

2) для поддержки overlays компилятору и компоновщику нужно различать как минимум 2 типа памяти (общая и подменяемая), а так же знать максимальный размер и количество кусков таких типов (это чтоб контроллировать выход за рамки возможного);

3) у компилятора с поддержкой overlays кроме обычных операций jmp() call() есть так же jmp_far() и call_far() которые перед самой передачей управления изменят конфигурацию памяти на нужную (рассчитанную компоновщиком, который тоже должен знать про overlays);

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

[Barmaley_m]

Barmaley_m, а где можно пощупать ASC CP/M?

Я в этой теме (http://zx.pk.ru/showthread.php?t=6107&page=13) выкладывал свои архивы (стр. 13). В моих архивах есть дискета "sp_basic.trd". На ней в виде бейсик-файла находится запускаемый образ ASC CP/M. Для запуска необходимо иметь Спектрум с минимум 144Кб ОЗУ, из которых "лишние" 16К подключаются по адресам 0000-3FFF. Также должны быть открыты порты TR-DOS, то есть доступ к ним должен быть возможен не только из TR-DOS, а из любого места без ограничений. Подключение доп. страницы по адресам 0000-3FFF выполняется по команде OUT 123,2.

Также в моих выложенных архивах имеются файлы, запускаемые под CP/M. К сожалению, перед запуском их необходимо сначала записать на дискету в формате ASC CP/M, а это нетривиальная задача.

Я когда-то модифицировал эмулятор Unreal, чтобы он поддерживал все вышеупомянутые режимы. До конца дело не довел, поэтому в общий доступ не выкладывал пока. Возможно, имело бы смысл довести до конца этот проект эмулятора и подготовить образы дискет, чтобы можно было беспрепятственно запускать ASC CP/M. Просто до сих пор никто не проявлял особого интереса к этой теме, поэтому и мотивации не было. Возможно, имеет смысл создать отдельную тему по этой ОС и туда все выкладывать.

[jerri]

Barmaley_m, т.е компутер у Сендецкого был еще тем монстром.

[alone]

Как у многих в ту эпоху :) У Rst7 тоже был интересный агрегат - Пентагон 512K с IDE по схеме ATM Turbo 2, а что там ещё было привинчено - история не сохранила.

---------- Post added at 16:00 ---------- Previous post was at 15:55 ----------


3) у компилятора с поддержкой overlays кроме обычных операций jmp() call() есть так же jmp_far() и call_far() которые перед самой передачей управления изменят конфигурацию памяти на нужную (рассчитанную компоновщиком, который тоже должен знать про overlays);

call_far должны делаться через вызываторы, которые лежат в нижней памяти и никогда оттуда не исчезают.
Примерно такие:
proc_far
ld a,page
call set_page
jp proc

Или, если вызов из одного дальнего модуля в другой дальний модуль:
proc_far
ld a,page1
call set_page
call proc
ld a,page2
jp set_page

Иначе будет тормоз (включать контекст системы, сохранять регистры, включать контекст юзера, восстанавливать регистры, переходить, а на ret_far ещё раз).

[Barmaley_m]

Barmaley_m, а где можно пощупать ASC CP/M?
Только что выложил файлы, с помощью которых можно как следует пощупать эту систему, в этой теме (http://zx.pk.ru/showthread.php?t=23565).