Вытесняющая многозадачность на ассемблере Z80

  • Tutorial
Медленный процессор и маленький объем ОЗУ — это еще не значит, что на такой платформе нельзя реализовать вытесняющую многозадачность. Более того, главный смысл организации многозадачной среды — это эффективное использование процессорного времени, чтобы процессор не простаивал, пока одни программы ждут какого-либо события, а использовался другими программами. Даже на таких платформах, как ZX Spectrum (Z80 3.5МГц, 48-128кБ ОЗУ), или 8-битные микроконтроллеры AVR, организация вытесняющей многозадачности имеет большой смысл.

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

Архитектура реализованной многозадачной системы


Архитектура была навеяна концепциями ядра Windows NT при изучении мною исходников ReactOS [2]. Из этих концепций был реализован минимум, который дает необходимые черты многозадачности. Более полная реализация возможна, но начиная с некоторого момента дополнительные функции перестают себя оправдывать из-за их затратности на малых ЭВМ.

Потоки (Threads)

Потоки [1] являются основными единицами, которыми управляет диспетчер. Каждый поток имеет исполняемый код и собственный стек, которым можно пользоваться для хранения адресов возврата из подпрограмм и другой информации. Диспетчер переключает исполнение с одного потока на другой таким образом, чтобы по возможности все потоки исполнили столько кода, сколько желают.

Каждый поток может находиться в одном из трех состояний: ожидание (waiting), готовность к исполнению (ready) и исполнение (running). В состоянии ожидания диспетчер не дает коду потока исполняться до наступления события, которое ожидаетя потоком. Поток, находящийся в состоянии готовности, получит управление от диспетчера, как только это станет возможным. В состоянии исполнения может находиться только один поток, так как в системе имеется только один процессор. Его код исполняется процессором до тех пор, пока поток не перейдет в состояние ожидания, либо пока не произойдет вытеснение, т. е. диспетчер по собственной инициативе не передаст управление другому потоку.

Количество потоков в системе фиксировано. Новые потоки не запускаются, а старые — не завершаются. Для микроконтроллерного применения или в рамках отдельной прикладной программы это ограничение несущественно. Зато упрощается диспетчер и ускоряется его работа.

Каждому потоку соответствует приоритет. Если имеется несколько потоков в состоянии готовности — то диспетчер выбирает к исполнению тот из них, приоритет которого наивысший. В текущей версии диспетчера приоритет потока нельзя изменять в процессе работы. Динамический приоритет потоков затратен в реализации, хотя эта возможность необходима для решения проблемы инверсии приоритета [1].

Приоритет всех потоков в системе различный. Это значит, что диспетчер не организует псевдопараллельное исполнение кода с одинаковым приоритетом, быстро переключая процессор с одного потока на другой (“Round-Robin”). Но на самом деле это ограничение несущественно. Псевдопараллельное исполнение нескольких потоков дает замедление каждого из них. Учитывая ограниченные ресурсы памяти компьютера, лучше организовать последовательное исполнение таких программ. Главная польза от вытесняющей многозадачности состоит не в возможности псевдопараллельного исполнения, а в эффективном разделении процессора между кратковременными задачами обработки запросов от важных источников (например, реакция на нажатие пользователем клавиши на клавиатуре) и длительной работой программ, время завершения которых некритично (компиляция, архивация). Если назначить для потока, обрабатывающего нажатия клавиш, высокий приоритет, а для потока архивации — низкий, то с точки зрения пользователя, редактирующего текст, скорость работы редактора не упадет, но зато в фоновом режиме в качестве бонуса заархивируется файл.

Объекты ожидания (объекты синхронизации)

На их основе поток может перейти в состояние ожидания путем вызова соответствующей функции диспетчера. Объект ожидания может быть сигнализирован или несигнализирован. Если он сигнализирован — то функция ожидания возвращается немедленно, и поток продолжает исполнение. Если же объект несигнализирован — то поток переходит в состояние ожидания, а исполняться начинают другие потоки, которые находятся в состоянии готовности. Как только объект станет сигнализирован, ожидающий поток вернется в состояние готовности и при первой возможности получит управление от диспетчера. В операционных системах обычно имеются такие объекты ожидания, как события (events), семафоры (semaphores), мутексы (mutex) и др. В рассматриваемом диспетчере реализованы два типа Events: Notification Event (Manual Reset), и Synchronization Event (Auto-Reset).

IRQL

Состояние процессора. Аббревиатура в Windows NT расшифровывается как ”Interrupt Request Level” [3], хотя это не совсем точно отражает смысл понятия. В описываемом диспетчере существует три уровня IRQL. PASSIVE_LEVEL – это когда в данный момент процессор исполняет код одного из потоков. В это время может произойти вытеснение исполняемого потока другим потоком, либо процессор может начать обрабатывать аппаратное прерывание. DISPATCH_LEVEL — в этом состоянии находится процессор во время исполнения критического кода диспетчера. Например, переключение исполнения между потоками — операция, состоящая из множества действий. В это время нельзя сказать, что процессор исполняет тот или иной поток — он как бы находится «между ними». В связи с этим вытеснение кода, исполняемого в режиме DISPATCH_LEVEL, невозможно. Наконец, третий уровень — DIRQL — соответствует тому, что процессор в данный момент обрабатывает аппаратное прерывание.

В отличие от Windows NT, в моем диспетчере нет такого места, где бы хранился текущий уровень IRQL. Также нет функций, повышающих или понижающих его в явном виде. Но IRQL как концепция подразумевается в системе и объективно существует в ней, хоть и неявно.

Пользовательский код может исполняться либо в потоках (на PASSIVE_LEVEL), либо в пользовательской подпрограмме обработки прерываний (ISR) на DIRQL. Набор доступных функций диспетчера различен для разных IRQL. Нарушение требований по IRQL приводит к сбою системы.

Пользовательский код, исполняющийся в потоках, не должен запрещать прерывания. Код ISR исполняется с запрещенными прерываниями, и поэтому наоборот, их нельзя разрешать. Что касается DISPATCH_LEVEL — то в Windows NT в этом режиме прерывания не запрещены, а в моем диспетчере, для простоты, на DISPATCH_LEVEL прерывания запрещены.

Функции диспетчера


Приводится назначение функций и описание их работы. Подробности передачи параметров в эти функции приведены в комментариях к исходному коду и здесь не дублируются, чтобы не загромождать текст. Имена функций по возможности взяты идентично именам аналогичных функций ядра Windows NT [2,3].

KeResetEvent

Снять сигнализацию объекта ожидания типа Event. Можно вызывать на любом уровне IRQL.

KeSetNotifEvent

Сигнализировать объект ожидания типа Notification Event (Manual Reset). Все потоки, которые ожидали сигнализации этого объекта, перейдут в состояние готовности к исполнению. Если среди них окажется поток с более высоким приоритетом, чем текущий – то исполнение текущего потока будет вытеснено в пользу того, который имеет высший приоритет.

Объект останется сигнализирован до вызова KeResetEvent.

Функцию можно вызывать только на IRQL=PASSIVE_LEVEL.

KeSetNotifEventFromIsr

То же самое, но для вызова на IRQL>=DISPATCH_LEVEL. При вызове этой функции из ISR переключение потоков, если произойдет, то после завершения исполнения ISR.

KeSetSynchrEvent

Сигнализировать объект ожидания типа Synchronization Event (Auto Reset). Если у этого объекта были ожидающие потоки — то один из них перейдет в состояние готовности, а объект сразу вернется в несигнализированное состояние. Остальные потоки продолжат ожидание. Если ожидающих потоков не было — то объект останется сигнализирован до тех пор, пока какой-нибудь поток не вызовет на нем функцию ожидания, либо KeResetEvent.

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

Функцию можно вызывать только на IRQL=PASSIVE_LEVEL.

KeSetSynchrEventFromIsr

То же самое, но для вызова на IRQL>=DISPATCH_LEVEL. При вызове этой функции из ISR переключение потоков, если произойдет, то после завершения исполнения ISR.

KeWaitForObject

Ожидание сигнализации объекта (Event). Если на момент вызова этой функции объект был сигнализирован — то функция немедленно возвращается. При этом, в случае Synchronization Event, произойдет сброс объекта в несигнализированное состояние. Если же объект не был сигнализирован — то текущий поток перейдет в режим ожидания, и диспетчер станет исполнять код из других потоков, находящихся в состоянии готовности.

Функцию можно вызывать только на IRQL=PASSIVE_LEVEL.

User ISR

Под этим разумеется возможность исполнения пользовательской подпрограммы обработки прерываний. В виде функции не выделена, но в исходнике диспетчера предусмотрено место для ее вызова или вставки. Для взаимодействия с потоками эта подпрограмма может использовать функции KeSetNotifEventFromIsr и KeSetSynchrEventFromIsr и, таким образом, «разбудить» какой-нибудь поток и привести к вытеснению другого потока.

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

Остальные функции диспетчера не предназначены для вызова из пользовательских программ.

Настройка диспетчера под конкретный проект


Чтобы использовать диспетчер в каком-либо программном проекте, необходимо его настроить. В исходном тексте следует заполнить структуру данных threads для каждого потока. Пример заполнения приведен в исходнике. Главное, что следует заполнять — это адреса стеков потоков. Последние два байта стека каждого потока содержат адрес его точки входа. Также следует указать количество потоков путем задания константы NUM_THREADS. Максимальное количество потоков в системе — 255.

При старте системы все потоки должны находиться в состоянии готовности. Последний поток, имеющий самый низкий приоритет, не должен переходить в режим ожидания. Этот поток представляет из себя аналог System Idle Process и не решает какую-либо задачу, а предназначен для «сжигания» неиспользуемого времени процессора. В нем рекомендуется циклически исполнять команду HALT.

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

Выделение памяти под объекты ожидания, которых в принципе может быть неограниченное количество, оставлено на усмотрение пользователя. Можно хранить эти объекты в стеке, в глобальных статических переменных или подключить к проекту менеджер кучи (heap) и выделять память под указанные объекты в куче.

Проблемные ситуации


Для среды исполнения, реализуемой диспетчером, характерны ситуации, проблемные для систем вытесняющей многозадачности вообще [1]. К ним относятся: голодание (Starvation), гонки (Race Conditions) и инверсия приоритета (Priority Inversion). Первые две проблемы могут быть решены правильным проектированием системы, разумным распределением задач по потокам, разумного выбора их приоритета и использованием примитивов синхронизации (в первую очередь Auto-Reset Synchronization Events). Третья ситуация в моем диспетчере не разрешается, так как отсутствуют динамический приоритет потоков и объекты синхронизации типа Mutex. Поэтому, если эта ситуация возникает в конкретном проекте, ее следует учесть и при необходимости добавить в диспетчер вышеуказанные средства.

Исходный код


Исходный код диспетчера вместе с описанием структур данных, параметров функций и прочей информацией, можно скачать на GitHub.

Литература


1. Википедия. Статья «Многозадачность»
2. ReactOS. Исходный код, компонент «ntoskrnl”
3. Windows WDK Documentation. MSDN. Kernel-mode driver architecture
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 30

    +1
    М.м… А сколько % CPU уходит на переключение потока?
      +3
      Это зависит от того, каким событием вызвано переключение. Например, если это произошло вследствие вызова функции ожидания — то тратится время на перевод текущего потока в режим ожидания, поиск другого потока в состоянии готовности, перевод его в состояние исполнения, и восстановление его регистров. Считать такты лень, но я старался оптимизировать код диспетчера. Например, если поток был вытеснен при вызове им функции ожидания — то при последующем пробуждении этого потока состояние его регистров не восстанавливается. Считается, что функция ожидания может использовать все регистры, и если потоку нужно их сохранять — то он должен делать это сам. Если при этом сохранять только те регистры, которые используются потоком — то можно сэкономить на их сохранении/восстановлении.

      Вообще, поскольку в данном диспетчере не предусмотрено псевдопараллельное исполнение (Round-Robin) — то потоки переключаются настолько редко, насколько это возможно. А сколько это времени займет от общего времени процессора — зависит от решаемой задачи. Программист должен учитывать, что переключение потоков — относительно дорогая операция, и стараться поменьше к нему прибегать. Но это справедливо и для современных ОС. Например, в некоторых местах MSDN четко указано, что WaitForSingleObject — дорогая функция. В Windows она значительно затратнее, чем в моем диспетчере, так как там реализовано больше функций, плюс защита памяти, переключение адресных пространств процессов.
      0
      У меня под руками нет Z80, но я не вижу, как в нем реализовать именно вытесняющую многозадачность.

      Скажем, обычный код

      di
      m: jp m

      введет в ступор всю систему, ибо NMI (тут могу ошибаться, давно дело было) не позволяет баловаться с «чужими» запретами на прерывания.

      Может, все-таки корпоративная многозадачность получилась?
        +3
        Нет, вытесняющая. Смотрите статью Википедии по ссылке. Реализована многозадачность, а не защита. Это разные вещи. Потоки, исполняемые в моей системе, не должны запрещать прерывания. Если они их запрещают — то работа системы будет нарушена. Подобные ограничения присутствуют в AmigaOS, например, и это не мешает данной ОС по праву иметь вытесняющую многозадачность.

        Кроме того, в ряде ситуаций описанный вами запрет прерываний не приводит к нарушению работы системы. Если ISR не вызывает функций вида «KeSetEvent» — то само по себе прерывание не может привести к вытеснению потока. Если ваш поток получил управление — значит он имел на этот момент самый высокий приоритет в системе. И он будет исполняться до тех пор, пока не вызовет функцию ожидания или «KeSetEvent» независимо от того, запретил он прерывания или нет.
          +1
          Не обратил внимания на нюансы, да. Для меня многозадачность одновременно включает и защиту от неправильного поведения задач.

          И да, вопрос уже «на интерес»: а в промышленном применении сейчас это имеет смысл? или только как задачка «сделать, потому что никто не делал»?
            +1
            Имеет прямой смысл на микроконтроллерах. Разрабатывая алгоритмы их работы, я часто был вынужден реализовывать те или иные упрощенные формы многозадачности. Наличие универсального диспетчера позволяет применить единообразный подход и сократить время на разработку.

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

              Я именно про Z80. Ведь его вроде больше не выпускают и не используют?
                +2
                Выпускают и используют. Есть большая группа энтузиастов ZX Spectrum, в которой идет разработка новых программ под этот компьютер. Иногда удается привлечь открытия науки и техники, которые появились уже после ухода этого компьютера из мейнстрима. В результате на нем удается реализовать вещи, которые раньше были немыслимы для компьютеров такого класса.

                Пишутся новые игры, демонстрации, системные и прикладные программы. Разрабатываются компиляторы, языки программирования.

                Какой в этом смысл? А смысл в том, чтобы оттачивать мастерство. Ограниченность ресурсов вынуждает искать нетривиальные решения. Но зачастую им впоследствии находится применение уже далеко за пределами этого ретро-компьютера.
                  0
                  Как говорится, обалдеть. Глядишь, так и Радио-86РК к чему-нить полезному приспособить придумают :)
                    +1
                    «Радио-86РК» тоже живет и побеждает. Есть и у него группы энтузиастов, ведущих новые разработки. Но я этим не интересовался. Можно погуглить, если интересно.
        +2
        Про файберы вместо вытесняющей многозадачности не думали?
        Там цена переключения минимальна, что для контроллера — важнейший плюс.
          0
          Пока не думал. Спасибо что подсказали. Кстати, я давно уже задумывался на тему подходящих применений для файберов. Пока почти ничего не приходит на ум, кроме задач обработки avi-файлов и подобных им. Может быть у вас есть идеи?
            +2
            Первое и самоочевидное — итераторы, одинаково удобные и для реализации, и для использования.
            Второе, имеющее прямое отношение к микроконтроллерам — обработка ввода по событиям.
            Можно писать простой линейный код без разбиения на отдельную обработку каждого байтика, при этом все остальное тоже будет работать, причем прозрачно.
            Третье — работа в стиле «потоки данных», можно реализовать сложные алгоритмы в виде цепочек простых фильтров, работающих одновременно без промежуточных буферов.
            При этом процессор не простаивает, оверхед от переключений минимальный, а уровень абстракции высок.
            Еще можно обратить внимание на реализацию кооперативной многозадачности на базе форт-системы — там стоимость переключения можно вообще почти в ноль уронить.
              0
              Пожалуйста объясните подробнее про итераторы и обработку ввода по событиям, приведите примеры, а то я ничего не понял. Понял только про работу в стиле «потоки данных», но это я сам имел в виду под «обработкой avi-файлов».

              Я вообще когда-то хотел написать целый пост про применение файберов, но, как оказалось, я додумался лишь до одного их красивого применения. Вы, судя по всему, знаете больше. Пожалуйста, поделитесь вашим знанием!
                  0
                  Да это же конгениально! Спасибо большое. Я догадывался, что файберы — мощное средство, но до сих пор не видел, где и как его следует применять.

                  (примечание для Grammar Nazi: слово «конгениально» употреблено в шутку в неправильном значении намеренно ошибочно. Мне известно его правильное значение).
                    –1
                    добавили бы к «конгениально» просто [sic].
                      0
                      Ок, учту. Главное — чтобы Grammar Nazi тоже знали, что это означает!
                  +3
                  Про обработку ввода по событиям.
                  Допустим, мы грузим что-то по сети, при этом давая возможность пользователю вводить с клавиатуры.
                  Информация приходит маленькими кусочками и нам приходится дробить код на множество мелких операций, выглядящих как каша с постоянной проверкой состояния и переходами.
                  На файберах мы можем сделать так:
                  1. Файбер, проверяющий пришедшее по сети и кладущий результат (если есть) в файбер-канал 1 иначе отдающий управление фиберу-планировщику.
                  2. Файбер, проверяющий нажатие клавиши и кладущий результат (если есть) в файбер-канал 2 иначе отдающий управление фиберу-планировщику.
                  3. Файбер, читающий файбер-канал 1 и выполняющий пришедшие по сети команды
                  4. Файбер, читающий файбер-канал 2 и выполняющий пришедшие с клавиатуры команды
                  5. Файбер-планировщик (например, round robin)

                  Файбер-канал — вместо записи в буфер переключает на планировщик, а при чтении берет по оставленному при записи указателю сколько есть… и переключает на планировщик, если недостаточно.

                  В результате логика каждой функции проста и линейна, а параллельность обеспечивается ручным переключением на планировщик и каналами на файберах.
                    +1
                    Спасибо большое. Было бы хорошо иметь на Хабре пост о применениях файберов. Пишите!
                    0
                    Я как-то чисто в учебных целях написал на файберах сервер для Win32 без единого потока.
              0
              Делал подобное 20 лет назад:
              andyplekhanov.narod.ru/hard/hard.htm
                +2
                Иэх…
                Делал нечто подобное чуть более 20 лет назад.
                Точнее — не делал, а перепиливал некую ОСРВ РТ/ОС-11 (в написании сильно не уверен):
                * Не для Z80, а для 8080
                * зашиваемое в ПЗУ
                * для промышленных контроллеров КРВМ (для буровых, такие себе герметичные ящики, зарываются в землю лет на 15..20 (по документации)).
                Не понравилось «API» — дизасемблировал, почистил, выкинул дебагер, редактор — осталось только ядро (практически — планировщик).
                Вытесняющая (или вытесняюще-корпоративная?..) многозадачность — все потоки заканчивались nop (перед которым взводили таймер — когда их будить (опрос датчиков же)). Сам планировщик тоже заканчивается nop.
                Защиты памяти, еснно, нет (а кому она нужна в промконтроллерах?).
                PID'ы, мютексы (как это называется сейчас, оказывается) — всё на месте.

                200 байт.

                хорошее было время… Неторопливое.
                  0
                  200 байт и мутексы — очень впечатляющий результат. У меня получилось значительно больше байт (610 включая данные и стек трех потоков). Можете поделиться вашей разработкой?

                  Насчет ОСРВ — их было две. Первая — RT-11 (более ранняя и простая), вторая — RSX-11 (она же ОСРВ, более поздняя и развитая). Но это же на «мини-ЭВМ», которые занимали целую комнату! Там еще был процессор PDP-11. Это очень не похоже на 8080. Думаю, перепилить пришлось многое!
                    0
                    Транслирую из лички ответ TIEugene (он не может сам написать из-за слитой кармы):
                    * мютексы и вся остальная динамика были в ОЗУ, а все программы — в ПЗУ, поэтому расход памяти надо считать отдельно.
                    * вся алхимия сводится к:
                    — все задачи _перед_ nop ставят себя в очередь, заказывая — когда их разбудить (в тиках)
                    — раз в 1/50s подрывается NMI и подрывает ядро
                    — которое декрементирует счетчик тиков, и те задачи, которым пора
                    — удаляет из очереди
                    — вызывает
                    Всё
                    Задачи сами между собой разбираются. Ядру же — пофик.
                    * мютексы… ну как — мютексы… Например задвинуть задвижку — это запуск четырех задач:
                    — одна — быстро запускает движок (если выставлен флаг «запустить движок»), выставляет флаг «движок пошел» — и тикает
                    — вторая — вешается на прерывание от датчика концевика (или вешается на таймер опросить датчик — случаи разные бывают), быстро считывает, записывает куда-то данные, выставляет флаг «готово» — и тикает.
                    — третья — обрабатывает данные (если они есть)
                    — четвертая — следит, чтобы из п.1 дошло до п.2 хотя бы. Или вызывает пожарных.
                    Ну и т.д.
                    Да, приходится рисовать state machine и подсчитывать такты процессора для каждой задачи (min и max). А что делать?

                    Сырцы попробую найти — они есть, но (ессно) не комментированы, и кто из них ху — надо разбираться.
                      0
                      Судя по вашему ответу, архитектура вашей системы значительно отличалась от того, что реализовал я в своем проекте. Возможно даже, что ваша система не реализует концепцию потоков и другие вещи, которые на сегодняшний день типичны для многозадачных систем. Надо более подробно изучать доки или код, чтобы утверждать наверняка.
                    +2
                    многозадачность — все потоки заканчивались nop

                    Наверно всё-таки hlt они заканчивались, а не nop
                      +1
                      --некую ОСРВ РТ/ОС-11

                      RT11SJ наверное.

                      В Томском Политехе ее перепилили в многопроцессорную, многозадачную и перемещаемую еще в 1991-м.
                    0
                    Как-то делал подобное на 51 контроллере. В нем очень удобно реализовывать до 4 задач т.к. есть 4 банка регистров.
                      +3
                      Вспоминается, как загружаешь Dizzy, остаешься в интерпретаторе BASIC'е, запускаешь функцию старта прерывания IM2 (по которому идет обработка ввода клавиатуры/джойстика и движущихся объектов), идет выход назад в интерпретатор — а Dizzy начинается бегать прям по текстовым командам на экране, реагируя на джойстик — пока не добежит до области, где ничего не напечатано («нет земли») — и полетел кувыркаясь по диагонали =). При этом интерпретатор BASIC'а успешно работал одновременно с процедурой обработки джойстика и отрисовкой движения Dizzy.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое