|
Вид на жительство
Регистрация: 07.01.2007
Адрес: Ленинградская обл
Сообщений: 428
Сказал спасибо: 147
Сказали Спасибо 71 раз(а) в 56 сообщении(ях)
|
Учебник по программированию - новая редакция
Сокращенная.
Учебник по программированию
Фрагменты будут необычно короткими. Это "выжимка" из состояния дел. Буду добавлять каждый день, пока не надоест или пока не кончится предмет программирования.
А кончится он быстро.
Память
Бывает, что количество обьектов заранее неизвестно. Тогда Вы выделяете память по мере создания новых обьектов. Вы освобождаете память обьекта, когда он больше не нужен.
Рассмотрим случай, когда обьекты имеют разные размеры. Допустим, нужно создать обьект (массив) большого размера. Может не оказаться непрерывного участка памяти нужного размера, хотя в сумме размер свободных (ранее освобождённых) участков может быть достаточен. Это происходит, когда Вы запрашиваете\освобождаете память для обьектов меньшего размера. Те области памяти, которые занимались\освобождались ими, могли располагаться не подряд.
Это называется фрагментацией памяти.
Для устранения фрагментации предложены следующие методы:
1) "Сборка мусора". Этот метод можно найти в старых книжках. Не рекомендуется. Состоит в периодической сдвижке занятых областей в одно место,например, в начало, при этом свободные области обьединяются в конце.
При этом процессам, работающим с памятью, нужно сообщить, что всё переехало на другое место.
2) Грамотный метод. Программист заранее смотрит, области памяти примерно каких размеров нужны в программе. Близкие размеры считаются за один стандартный, и память всегда запрашивается с округлением до одного из стандартных размеров в большую сторону. Память запрашивается не из общей кучи, а из определённого пула памяти. Пулы организуются заранее. При создании пула указывается, обьекты какого размера будут распределяться в этом пуле и сколько максимально их можно будет запросить.
После создания пулов память под обьекты запрашивается\освобождается в соответствующем пуле. Так организована файловая система FAT.
3) Эффективный метод. Прикладная программа строится так, чтобы исключить фрагментацию.
Если в выделении памяти Вы всё же полагаетесь на операционную среду, Вы должны чётко знать, как именно операционная среда борется с фрагментацией. Обычно никак. В этом случае при достаточно долгой работе Вашей программы Вы столкнётесь с нехваткой или "утечкой" памяти.
Мультизадачность
Здесь про такую мультизадачность:
1) Одна машина выполняет несколько программ;
2) Каждая программируется так, как будто машина выполняет только её одну.
В этой ситуации управление переключается между программами. Как это делается?
1. Прямая отдача управления. Программа всё-таки учитывает, что она не одна, но самым минимальным образом. А именно, она время от времени, например, в циклах, делает специальный вызов диспетчера - с тем, чтобы диспетчер решил, возвращать управление назад, или настал момент отдать управление другой программе.
2. Внешнее прерывание. При возникновении опред. события управление принудительно аппаратно передаётся в точку, заранее сопоставленную этому событию. В этой точке доступна информация о том, где управление было раньше. Дальнейшее решает всё тот же диспетчер.
Функция (1) есть к примеру в виндоус; также виндоус реагирует на некоторые аппаратные прерывания. Заметьте, что я не сказал: "корректно обрабатывает все прерывания", а сказал: «реагирует на некоторые».
Вы можете испытать Вашу операционную среду программой:
A JMP A
с тем, чтобы увидеть, виснет ли она (в какой мере задействованы прерывания), и какие именно манипуляции выведут её из зависания.
Всегда думайте: нужна ли здесь мультизадачность?
Может быть, лучше обойтись без мультизадачности в смысле (1)(2), то есть
- выполнять разные задачи на разных процессорах
или
- писать программы для каждой задачи с учётом того, как это работает в целом.
Виртуальная память
Виртуальная память - это ещё одна мечта программистов 50-х годов. Хотелось писать программу, не задумываясь о том, хватит ли памяти.
Исполняют мечту так:
- программе назначается диапазон адресов памяти, к которым она имеет право обращаться. При обращении к адресу, не принадлежащему программе, аппаратно генерируется внешнее прерывание. Обработчик прерывания размещает где-то в реальной оперативной памяти данные, к которым идёт обращение по требуемому программой адресу. Прежде, чем вернуть управление программе, включается аппаратная переадресация с "запрещённых" адресов на те реальные адреса, где размещены требуемые данные.
Для этого частично программно, частично аппаратно поддерживаются следующие служебные данные:
1. Таблицы адресов (вообще говоря, некоторых операций), разрешённых той или иной программе. Они заполняются программно. Действия программ проверяются на допустимость аппаратно.
2. Таблицы переадресации. Указывается, какие логические (например, большие) адреса где размещены в физической памяти. Заполняются программно, сама переадресация делается аппаратно.
При подгрузке областей виртуальной памяти в реальную там, в реальной, все места могут быть заняты. Надо что-то выгружать на внешнюю память. Это называется страничным обменом.
Если кроме диапазонов памяти "охраняются" также команды доступа к портам ввода-вывода, просто команды, несуществующие команды и т.п., то теоретически возможно организовать виртуальную машину.
Эти возможности были полностью реализованы в системах 60-70-х годов, но оказались не нужны. В самом деле, много ли найдётся таких задач, ради которых стоит городить этот огород?
Чтобы проверить, хорошо ли работает "охрана" команд (и изоляция приложений друг от друга) в Вашей операционной среде, поиграйте с такими программами:
- с программой, которая пишет по памяти всё дальше и дальше либо всё ближе к нулевому адресу;
- c программой, которая напрямую работает с портами ввода-вывода
При программировании лучше не надеяться на общесистемные волшебные средства, а при нехватке ОП организовывать хранение данных в файлах самому и лучше обдумывать решение. Например, метод Гаусса для ленточных матриц может быть реализован без "лобового" применения массивов большого размера, в небольшой оперативной памяти.
Ресурсы
Процесс может умереть, не освободив ресурс.
При доступе Lock - Unlock для захвата и освобождения ресурса применяются всякие флаги и счётчики занятости. Иногда их пишут даже в файлы – и лучше ничего этого не делать.
Сценарий зависания:
Первая задача владеет ресурсом и ждёт другой ресурс. Этим другим владеет задача, которая ждёт ресурса, занятого первой задачей, лишь потом освободит свой.Чтобы этого не было, все задачи должны захватывать и освобождать ресурсы согласно их сквозной нумерации.
МЕЖДУ проверкой флага и его установкой в состояние "занято" может возникнуть прерывание, управление получит другая задача, и она может при этой проверке решить, что ресурс свободен. Предлагали ввести аппаратно неразрывную команду "lock-and-test". Решение состоит в том, что захватом и освобождением ресурсов управляет только диспетчер, который отвергает повторный вход в себя.
Для программирования важно, что считать ресурсами (событиями,состояниями), особенно если они связаны с состоянием данных, а не с устройствами.
Опасность от совместного доступа к данным, как правило, преувеличена, либо устранима хорошим алгоритмом решения конкретной задачи.
Транзакции
Можно услышать и про очереди к ресурсам.
Уж если появляются очереди, пусть лучше это будут очереди транзакций (запросов).
Чем отличается транзакция от обычного запроса на обслуживание, отправляемого программе или устройству?
1. Транзакция должна быть выполнена полностью. Частичное выполнение нежелательно.
2. Транзакция не должна быть прервана выполнением определённых операций (например, похожей транзакцией)
Можно придумать такие транзакции, для которых можно восстановить данные, испорченные разрушенной транзакцией. Если очередь транзакций сохранилась, невыполненные транзакции после отката возможно выполнить повторно.
В отличие от мультипрограммирования, прерываний и виртуальности, транзакции реально возможно использовать в оборудовании.
От работы над организацией памяти (здесь - для очередей) Вы всё равно не отвертитесь.
Как правило, транзакции естественным образом возникают в работе с базами данных.
Базы данных
От транзакций естественным образом переходим к базам данных.
В наше время уже можно эффективно использовать поиск подстроки (контекстный поиск) по всей базе. Вы должны знать соответствующий быстрый алгоритм.
Самый эффективный из универсальных приёмов - это хэш-доступ. Делается так:
1) по ключу вычисляется хэш-функция. Она вычисляет место для прямого позиционирования;
2) от этого места производится последовательное чтение, пока не будет найден искомый ключ.
Последовательное хранение здесь не обязательно делается в порядке сортировки ключей.
Конечно же, последовательное чтение может осуществляться не физически последовательно, а по списку. Легко перестараться. Для развлечения сравнивайте время поиска в Вашей БД и время полного форматирования жёсткого диска.
Для самой сортировки оптимальным является метод "пузырька".
Жёсткие диски применяются всё меньше.
Для решения конкретной задачи Ваш собственный набор файлов наверняка будет лучше "взрослой" СУБД. Но чтобы он действительно был лучше, Вам всё же необходимо знать про избыточность, непротиворечивость и нормализацию данных.
В наше время данные можно хранить даже в CSV.
Искусственный интеллект, экспертные системы
Если Вам встретилась задача распознавания или что-то в этом роде, похожее на традиционные задачи "искусственного интеллекта", помните, что работающий подход к решению - это применение нейронных сетей.
Почему они хорошо работают? Каковы математические основы их работы?
Как ни крути, а нейроны вычисляют суммы произведений уровней сигналов на подбираемые при обучении коэффициенты. Формулу пишу словами :) Фактически нейронная сеть выдаёт координаты входной функции в пр-ве некоторых базисных функций вроде гармоник при разложении в ряд Фурье. Притом интересно, что и значения координат (гармоники) (интегралы) и выражение вектора в координатах (ряд Фурье) считаются по одинаковым формулам. Именно такие формулы отрабатываются нейронами.
На выходе набор координат воспринимаемого обьекта в некотором базисе. Базисные вектора определяются обучением сети, и самому конструктору они не известны.
Это делается внутри сети неоднократно. Поэтому там формируется не один набор базисных функций и, если угодно, несколько стадий и вариантов "понимания". Сеть подбирает способ хоть какого-нибудь, но понимания в терминах требуемых действий.
Это было неформальное описание (попытка понимания:)
Есть смысл при идентификации зависимостей сперва разложить их по каким-либо "стандартным" функциям из справочника. Помогает.
Интересный впечатляющий пример из моей практики. Была задача идентификации симптомов по кардиограмме. Кардиограммы записывались носимым кардиорегистратором. Болезнь только начинается, поэтому за несколько часов регистрации симптом появляется единично. Программа должна была точно выводить врача именно к картинке симптома. Мой эвристический метод давал неполное распознавание действительно зарегистрированных симптомов, и ложное срабатывание по артефактам регистрации. А.Любашевский подошёл к задаче грамотно. Он стал пробовать разложения по различным базисным функциям прямо из справочника. Оказалось, что подходят стандартные ортогональные полиномы (не помню, какие именно, но с первых же страниц справочника). Форма зубцов, интересующая врача, полностью определена всего ШЕСТЬЮ гармониками, притом не подряд идущими. То есть сердце работает по этим полиномам. Построенный Любашевским распознаватель работает со 100% точностью.
Есть типовые алгоритмы автоматического сведения многочисленных фактов, применяемые в анализе разведданных и в экспертных системах вроде диагностики неотложных состояний в медицине.
Алгоритмы (формулы) фильтрации также впечатляюще эффективны.
Но продолжим именно про программирование.
Свойства микромашин
Например:
1. Что-то выглядит как память, но на самом деле это типа «регистр устройства на шине». С виду память, а работает по-другому.
"p++" не прокатывает.
Такие места дальше будем называть "портами".
2. Если мы что-то записали в порт, это не значит, что оно сразу прочитано
3. Записанные данные могут измениться от самого чтения
4. Если устройство записало в порт информацию состояния, это не значит, что она так и будет храниться там до чтения или обновления.
5. (Естественно!) если что-то Вы пишете в порт устройству, этого может быть недостаточно, надо ещё записать куда-то «стробирующую» информацию. То же для чтения.
6. Устройства отвечают (в т ч на стробирование) не сразу.
7. В том числе после операции считывания состояния они могут продолжить свою работу не сразу.
8. Устройство может, наоборот, "застрять" до тех пор, пока Вы не прочитаете квитанцию.
9. Устройство может "застрять" до тех пор, пока Вы не ПОШЛЁТЕ квитанцию.
... и т д и т п
N). Любая операция: запись\чтение порта, прерывание - может поломать работу чего угодно где угодно. Пример: сигнал от клавиатуры в x86 по отношению к защищённому режиму.
Вы спросите: как же тут работать? Должен же где-то быть абсолют. Нас приучили, что оборудование безгрешно, а если программа работает неверно, виноват всегда программист.
Это верно.
Программист должен ПРЕДУСМАТРИВАТЬ именно такое поведение оборудования.
Способы управления памятью, описанные в начале, в мире микромашин, как правило, неприменимы (кроме последнего способа – писать программу так, чтобы этого совсем не было:). К примеру, где в этом DSP взять однородную память, достаточно длинную для применения «общих» способов?
Опрос устройств и автоматы
Допустим, что прерывания не используются. В этом случае постоянное (циклическое) действие (например, опрос порта), как уже говорилось, может монополизировать машину.
От этого помогает следующая техника.
Заводим "главный цикл", в начале которого анализируется, по какой ветке идти в этот раз. Если нужен опрос порта, то под одну попытку опроса отводится одна ветка. Ни в какой ветке нет никаких внутренних циклов, т.е. каждая ветка гарантированно имеет выход в каждом её вызове.
Допустим, что при этом что-то должно делаться через точно заданные интервалы времени. При этом прерывание от таймера не используется (например, нет его). В этом случае все ветки программируются так, чтобы их выполнение при всех вариантах внутренних ветвлений занимало одинаковое время ("балансируются"). Время рассчитывается по известному времени выполнения команд процессора, например, в тактах. Ветка, которая отрабатывает действие, зависящее от времени, вызывается через нужное число (одинаковых по продолжительности) прохождений "главного цикла".
Этот приём был применён в разработке звукового микшера. Программа отрабатывала и управление от ручек\кнопок, и звуковые эффекты. При этом до применения описанной техники неравномерности в выполнении программы были слишком заметны на слух.
Техника "главного цикла" похожа на применение конечных автоматов или таблицы состояний и переходов. Похожее можно встретить в ПЛК.
При ДОСТАТОЧНО СЛОЖНОМ наборе функций программы начинает проявляться общий недостаток этих техник. А именно, действия в некоторых ветках для читателя программы выглядят слишком автономно, хотя на самом деле таковыми не являются. Из-за этого не видны алгоритмы. При попытке осмысленно именовать эти многочисленные маленькие ветки (варианты выбора)(состояния) появляется слишком много явно искусственных и неудобных названий. Ветка устанавливает флаг какого-то состояния, а что оно значит, этого не видно.
То есть не стоит пихать все задачи в один главный цикл (в один ПЛК), а лучше распределять их по разным машинам.
Технологии программирования
Два главных факта, выделенных в ходе специальных исследований:
1) Никому ещё не удавалось написать без ошибок больше 50 операторов (строк). Это не зависит от языка программирования.
2) Пользователь довольно спокойно относится к недостаточной (неполной), но известной ему надёжной устойчивой функциональности и даже к явным сбоям, но таким, которые проявляются всегда при одних и тех же условиях. Гораздо хуже непредсказуемость в поведении системы.
... и третий факт, замеченный мной:
3) Программы бывают досадно крепкими. После того, как нашли "хомут", удивляемся: как оно вообще могло работать?
|
