AVR. Учебный Курс. Архитектура Программ. Часть 4

Вытесняющий диспетчер
Давным-давно, когда я учился в школе, мне не давал покоя вопрос. Как работают параллельные операционки? Как тот же самый Windows умудряется переключать процессы, не терять регистры (да, я тогда уже начинал учить асму), как он определяет момент переключения, почему все это работает? Виртуальная память, проверка на ошибочный код — никто ничего этого не объяснял. Все твердили про какие-то там объекты, классы, и говорили очень виртуально. А мне мясо, мясо давай!

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

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

Немного теории
Думаю не секрет, что любая многозадачная операционка работает на прерываниях таймера. Даже на x86 архитектуре без него никуда.

При срабатывании прерывания процессор идет на обработчик, а там прописано примерно так:

  • 1) Сохранение регистров.
    • 1.1) Сохранение виртуальной памяти — в файл подкачки или еще куда-нибудь.
  • 2) Сохранение текущего адреса.
  • 3) Загрузка регистров след. процесса.
    • 3.1) Загрузка виртуальной памяти.
  • 4) Загрузка адреса возврата.
  • 5) Переход по этому адресу.

По сути — не так уж и много работы, если исключить пункты X.Y. Всего и делов — сохранить, загрузить и вернуться. Вот именно это я и реализовал — простейшее ядро операционки, БЕЗ проверок и т.д.

Структура моей операционки

Каждый процесс имеет собственную память — 64 байта (число взял от балды, просто чтобы красивое было): 35 байт — место для сохранения регистров и SP, остальные 29 — под стек.

Да, кстати: переключение процессов дополнительно нагружает стек на 3 байта. Поэтому больше 26ти байт лучше не использовать, или же выделять CLI/SEI.

В памяти находится очередь процессов — она начинается с нуля (нулевой, ущербный процесс), и заканчивается FF. Почему FF? А просто так удобнее отлаживать: проще найти очередь в памяти в эмуляторе. Это единственная причина, поэтому можно его убрать. С нулевым процессом нельзя проводить никакие махинации — никаких пауз и таймеров к нему не использовать, иначе это приведет к апокалипсису… Наверное. Не пробовал.

Каждому процессу соответствует свой таймер. Это двухбайтные числа, лежащие в массиве, устанавливаются при помощи «API» функции SetTimer.Используется, чтобы временно убрать процесс из очереди.

Работа диспетчера
Когда наступает прерывание переполнения таймера — включается диспетчер. Работает он на процессоре в 8МГЦ 58.5 микросекунд, так что не мешает ни передачам данных (если конечно скорость не запредельная), ни работе процессов. Диспетчер сохраняет все регистры текущего процесса, адрес возврата, пересчитывает таймеры, запускает новые процессы (если их таймер дотикал до нуля), после чего загружает регистры следующего процесса из очереди, достает его адрес возврата и прыгает туда.

Схематично можно изобразить так:

Код

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

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

.equ ProcDataSize = 64		; память процесса
.equ ProcNum = 8		; колчиество процессов
 
; Куча временных переменных, по большей части для перекидывания данных
TempProc:	.byte 1		; для распознания
SREGT:		.byte 1		; временная переменная под SREG
SPTL:		.byte 1		; под SPL
SPTH:		.byte 1		; под SPH
R16T:		.byte 1		; под R16 :)
ZLT:		.byte 1		; ZL
ZHT:		.byte 1		; ZH
ADDRL:		.byte 1		; адрес
ADDRH:		.byte 1
TCurp:		.byte 1		; временный CurProc (см. ниже)

Дальше переменные очереди:

  • TasqQueue — очередь процессов. В ней находятся номера процессов в определенном порядке.
  • LastItem — «указатель» на последний элемент очереди (именно поэтому FF в конце очереди не используется: через указатель намного удобнее работать).
  • CurProc — текущий номер процесса. Используется при переключении и в SuspendProcess.
  • TimerQueue — МАССИВ таймеров. Да-да, именно массив. Саначала я хотел делать очередь, но потом решил, что массив проще в реализации. А имя осталось старым.
  • Proctable — таблица процессов. В нее при старте заносятся адреса всех процессов, чтобы далее работать не с адресами, а с номерами, что значительно упрощает программу.
					; Очередь и все, что с ней связано
CurProc:	.byte 1				; Системная переменная, хранит номер процесса
LastItem:	.Byte 1				; Номер последнего элемента очереди (для удобства)
TaskQueue:	.byte ProcNum+1 		; Очередь процессов
TimerQueue: .byte ProcNum*2 ; Массив таймеров
 
Proctable: 	.dw 1			; Таблица адресов процессов
		.dw 1			; для наглядности - 8 процессов отдельно
		.dw 1
		.dw 1
		.dw 1
		.dw 1
		.dw 1
		.dw 1

И, пожалуй, самая важная часть операционки — место под данные процессов. То самое, что описано в теории.

; Самое важное: место под стек и регистры.
; Сколько процессов - столько и этих записей
ProcData:	.byte ProcDataSize
		.byte ProcDataSize
		.byte ProcDataSize
		.byte ProcDataSize
		.byte ProcDataSize
		.byte ProcDataSize
		.byte ProcDataSize
		.byte ProcDataSize

Диспетчер.

Код диспетчера, как ни странно, прост. К тому же я его прокомментировал достаточно подробно. Пробегись глазами.

TM0_OVF:
	STS R16T, R16			; Выковыриваем из стека адрес
	POP R16				; в переменные ADDRx
	STS ADDRL, R16			; предварительно сохранив регистр R16
	POP R16
	STS ADDRH, R16
	LDS R16, R16T
 
	SaveRegs CurProc		; Сейвим регистры
 
	SaveAddr CurProc		; Сохраняем адрес возврата
 
	DecTimers			; Декаем таймеры
 
	GetNextProc			; Берем следующуий процесс
 
	STS ADDRL, ZL			; Сейвим адрес в ADDRx
	STS ADDRH, ZH	
 
	loadRegs			; Грузим регистры
 
	STS ZLT, ZL			; сохраняем Z, лишний раз не грузим стек
	STS ZHT, ZH
	LDS ZL, ADDRL			; ADDRx в Z
	LDS ZH, ADDRH
	PUSH ZL				; Пишем в стек адрес возврата
	PUSH ZH
	LDS ZL, ZLT			; и респим регистры Z
	LDS ZH, ZHT
 
	STS R16T,R16			; сейвим R16
	LDS R16, SREGT			; восстанавливаем SREG. ДАЛЕЕ НИКАКОЙ МАТЕМАТИКИ!!!
	OUT SREG, R16			; а то испортим
	OUTI TCNT0, 0			; Обнуляем таймер
	OUTI TIFR, 1			; и его флаг прерывания
	LDS R16, R16T			; вернем многостарадальный R16
	RETI				; Валим нафиг

Первое, что я делаю — достаю из стека адрес возврата и сохраняю в переменные. Зачем? А затем, что после некоторых манипуляций стек переключится на другой процесс, а там будут уже совершенно другие данные. Сохранится он потом в ProcTable. Сейчас ВРОДЕ БЫ код написан так, что это не обязательно. Однако так надежнее, и, если что, проще дописать новые возможности.

Далее пресловутое сохранение регистров, адреса, пересчет таймеров, переход к следующей процедуре в очереди (доставание ее адреса), загрузка регистров нового процесса. Под конец пишем в стек НОВЫЙ адрес возврата, для другого процесса, и RETI прыгает туда.

Обрати внимание, что восстановление SREG из переменной идет в самом конце диспетчера. Иначе при первой же математической операции (будь то Add, Sub или даже INC) испортятся флаги. А я этого не хочу. Также в конце сбрасывается таймер — одному Богу известно, сколько он там натикал за время работы диспетчера, и сколько осталось до следующего вызова.

Чтож, настал час, когда я покажу тебе самое сложное для восприятия во всей операционке — макросы. Вкратце со смыслом каждого думаю ты ознакомился, прочитав комментарии к коду выше (или нет?).
3…2…1… Поехали!

; Макрос сохранения регистров процесса
	.macro SaveRegs
		STS  ZLT, ZL		; Спасаем регистры
		STS  ZHT, ZH		; стараемся как можно меньше использовать стек
		STS  R16T, R16
		IN	 R16, SREG
		STS  SREGT, R16
 
		LDS  R16, TempProc  		; Определяем, где этот макрос применен
		CPI	 R16, $FF		; В SuspendProcess или в переключении
		BRNE NoLoadNum
 
			LDI ZL, low(TaskQueue)	; Получаем номер процесса из очереди
			LDI ZH, High(TaskQueue)
			LDS R16, @0
			ADD ZL, R16
			LDI R16, 0
			ADC ZH, R16
			LD  R16, Z
 
		NoLoadNum:
		STS TCurP, R16			; И сохраняем в переменную			
 
		LDI ZL, low(Procdata)		; Получим адрес памяти процессора:
		LDI ZH, High(Procdata)
 
		Push R17			; Снова спасаем регитсры
		Push R0
		Push R1
		LDS R16, TCurP			; Получаем адрес памяти процесса
		LDI R17, ProcDataSize
		MUL R16, R17
		ADD ZL, R0
		ADC ZH, R1
		Pop R1				; Вернем регистры
		Pop R0
		Pop R17
		LDS R16, R16T
 
		ST	Z+,R0			; Долго и нудно их сейвим
		ST	Z+,R1
		ST	Z+,R2
		ST	Z+,R3
		ST	Z+,R4
		ST	Z+,R5
		ST	Z+,R6
		ST	Z+,R7
		ST	Z+,R8
		ST	Z+,R9
		ST	Z+,R10
		ST	Z+,R11
		ST	Z+,R12
		ST	Z+,R13
		ST	Z+,R14
		ST	Z+,R15
		ST	Z+,R16
		ST	Z+,R17
		ST	Z+,R18
		ST	Z+,R19
		ST	Z+,R20
		ST	Z+,R21
		ST	Z+,R22
		ST	Z+,R23
		ST	Z+,R24
		ST	Z+,R25
		ST	Z+,R26
		ST	Z+,R27
		ST	Z+,R28
		ST	Z+,R29
 
		MOV YL, ZL				; Перекидываем адрес в Y пару
		MOV YH, ZH
		LDS ZH, ZHT				; Достаем Z
		LDS ZL, ZLT
		ST  Y+, R30				; И сейвим его
		ST	Y+, R31
 
		LDS R16, SREGT				; Сейвим SREG
		ST  Y+, R16
		IN	R16, SPL			; и Stack Pointer
		ST	Y+, R16
		IN	R16, SPH
		ST	Y+, R16
	.endm

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

— Почему бы не использовать параметры макроса? — спросишь ты.
— А потому что переключение процессов иногда вызывается по прерыванию, а иногда — в функции SuspendProcess. Получается, что макрос вызывается из одного и того же места, но «это место» срабатывает по разным причинам:) и надо как-то это отслеживать. — отвечу я.
Если TempProc = $FF — значит вызывали переключение по прерыванию, тогда выполняется полный код: т.е. получаем номер процесса по текущему индексу элемента в очереди. Если же нет — то не надо загружать номер процесса. Это для SuspendProcess.

Сейвим регистры в стек — как раз те самые 3 байта. Здесь можно использовать и временные переменные, но все равно макрос загрузки регистров грузит стек на 3 байта. Можно и там использовать переменные, но код становится совсем нечитаем, даже относительно того, чтоо счас. К тому же это тоже остатки мусора.
Как получаю адрес памяти процесса — беру номер, умножаю на размер 1й ячейки (64 байта) и получаю смещение. Прибавляю адрес первой и получаю то, что надо.

И вот мы дошли до самого сохранения регистров. Я думаю, понятно, как оно происходит до R29 :) Чтобы сохранить Z пару, делаю просто: Y пару менять не страшно, ведь Y уже сохранен. Поэтому перекидываю туда адрес, лежащий в Z, и сохраняю Z. Достаю заготовленный в самом начале макроса SREG и пишу в память. И наконец сохраняю стек.

Процедура загрузки похожа на сохранение, только все с точностью до наоборот :)

; Макрос загрузки регистров процесса
 
	.macro LoadRegs
		LDI ZL, low(TaskQueue)			; Грузим номер процесса из очереди:
		LDI ZH, High(TaskQueue)			; В Z - адрес очереди процессов
		LDS R16, CurProc			; В R16 - номер текущего процесса в очереди
		ADD ZL, R16				; Прибавляем его к адресу
		CLR R16
		ADC ZH, R16				; и грузим реальный номер
		LD  R16, Z						
 
		LDI ZL, low(Procdata)			; Вычисляем адрес данных процесса
		LDI ZH, High(ProcData)
 
		LDI R17, ProcDataSize			; Address = ProcData + ProcDataSize*N
		MUL R16, R17				; где N = R16, только что грузили
		ADD ZL, R0
		ADC ZH, R1
 
		LD	R0, Z+				; Респим регистры
		LD	R1, Z+
		LD	R2, Z+
		LD	R3, Z+
		LD	R4, Z+
		LD	R5, Z+
		LD	R6, Z+
		LD	R7, Z+
		LD	R8, Z+
		LD	R9, Z+
		LD	R10, Z+
		LD	R11, Z+
		LD	R12, Z+
		LD	R13, Z+
		LD	R14, Z+
		LD	R15, Z+
		LD	R16, Z+
		LD	R17, Z+
		LD	R18, Z+
		LD	R19, Z+
		LD	R20, Z+
		LD	R21, Z+
		LD	R22, Z+
		LD	R23, Z+
		LD	R24, Z+
		LD	R25, Z+
		LD	R26, Z+
		LD	R27, Z+
		LD	R28, Z+
		LD	R29, Z+
 
		PUSH YL					; Сейвим Y пару
		PUSH YH
		MOV YL, ZL				; Перекидываем туды Z
		MOV YH, ZH
		LD	R30, Y+				; И восстанавливаем Z
		LD	R31, Y+
 
		PUSH R16				; Сейвим R16
		LD  R16, Y+
		STS SREGT, R16				; Грузим SREG
		LD	R16, Y+				; ВНИМАНИЕ, ИЗВРАТ!
							; (Ну почему изврат. Нормальные будни ассемблерщика прим. DI HALT)
		STS	SPTL, R16			; Сохраняем SP в переменные
		LD	R16, Y+				; это будет использоваться далее
		STS  SPTH, R16				; делается потому, что нельзя здесь
							; менять SP - в стеке наши регистры
 
		POP R16					; Откапываем в стеке сокровища
 
		POP YH
		POP YL
 
		STS R16T, R16				; Сейвим R16 в переменную
		LDS R16, SPTL
		OUT SPL, R16				; Из переменных для SP грузим SP
		LDS R16, SPTH
		OUT SPH, R16
		LDS R16, R16T				; И возвращаем R16
							; Всё, изврат закончился.
	.endm						; Итог: восстановили все регистры и SP

Здесь уже с предварительным сохранением регистров можно не париться. Мы же их все равно загружаем :) Начало то же самое, что и в сохранении после проверки TempProc. Загружаем все регистры, так же перекидываем Z в Y и т.д. А вот в конце интересная вещь: если загружать значения SP прямо по ходу, то получится, что Y положится в стек одного процесса, а вынется из стека другого! Естественно, это будет полный бред. Поэтому гружу значения SP в переменные, достаю Y и R16, и только потом переношу в SP.

Поздравляю, мы уже на пол пути :)

; Макрос сохранения адреса возврата в таблицу
	.macro SaveAddr
		LDS  R16, TempProc			; Определим, откуда вызвали
		CPI	 R16, $FF
		BRNE NoLoadNumA						
 
			LDS R16, @0							
 
			LDI ZL, low(taskQueue)		; берем номер процесса из очереди
			LDI ZH, High(taskQueue)
 
			ADD ZL, R16
			LDI R16, 0
			ADC ZH, R16	
 
			LD R16, Z
		NoLoadNumA:
 
		LDS YL, ADDRL				; грузим засейвенный адрес
		LDS YH, ADDRH
 
		LDI ZL, low(Proctable)			; И сейвим его!
		LDI ZH, High(ProcTable)
 
		LSL R16
		ADD ZL, R16
		LDI R16, 0
		ADC ZH, R16
 
		ST Z+, YH
		ST Z+, YL
	.endm

Все просто, только много кода. Если вызывается из диспетчера — то достаем номер процесса из очереди, идем в таблицу и пишем туда наш адрес из ADDRx. О SuspendProcess — позже.

Идем дальше:

; Макрос получения след. процесса по очереди-------------------
 
	.macro GetNextProc
		LDI R16, $FF
		STS TempProc, R16			; В TempProc пишем $FF
 
		LDS R16, CurProc			; Инькаем CurProc
		INC R16
 
		LDS R17, LastItem			; Сравниваем с последним
		INC R17
		CP  R16, R17
		BRCS NoDec				; Если больше - пишем 0
 
			LDI R16, 0
 
	NoDec:
		STS CurProc, R16			; сохраняем в CurProc
 
		LDI ZL, low(taskQueue)			; Грузим номер из очереди...
		LDI ZH, High(taskQueue)			; (было выше)
 
		ADD ZL, R16
		LDI R16, 0
		ADC ZH, R16
 
		LD  R16, Z
 
		LDI ZL, low(ProcTable)			; Берем из таблицы адрес процесса...
		LDI ZH, High(ProcTable)
 
		LSL R16
		ADD ZL, R16
		LDI R16, 0
		ADC ZH, R16
 
		LD R16, Z+
		LD R17, Z+
 
		MOV ZL, R16				; И пихаем его в Z!
		MOV ZH, R17
	.endm

Тут тоже все просто до жути. Увеличиваем CurProc, если ушло за конец очереди — пишем 0, вынимаем из очереди номер процесса, идем в таблицу, достаем адрес возврата и пишем его в Z пару.

И последний макрос:

; Макрос пересчета таймеров
	.macro DecTimers
		LDI ZL, Low(TimerQueue)		; Грузим начало очереди таймеров
		LDI ZH, High(TimerQueue)		
 
		LDI R16, 0
	Decrease:				; Цикл уменьшения таймеров
		LD  R17, Z+			; Таймеры 2х-байтные
		LD	R18, Z
		CPI R17, 0			; побайтово сравниваем
		BRNE Decr			; Если 0 - то не надо уменьшать
		CPI R18, 0
		BREQ NoDecrease
	Decr:
		 SUBI R17, 1			; уменьшаем на 1
		 SBCI R18, 0
		 LD R0, -Z			; и переписываем старые значения
		 ST Z+, R17
		 ST Z,  R18
  		 CPI R17, 0			; если стало равно нулю - надо
		 BRNE NoDecrease		; запускать процесс
		 CPI R18, 0
		 BRNE NoDecrease
 
		  MOV R17, R16			; в R17 номер процесса
		  RCALL StartProcess		; API StartProcess
 
	NoDecrease:
		LD R0, Z+			; переход к следующей ячейке
		INC R16				; Inc R16; если стал равен кол-ву
		CPI R16, ProcNum		; процессов - значит выход.
		BRNE Decrease
	.endm

Тут мы проходимся по всему массиву таймеров, уменьшаем все на 1 (если они не равны нулю конечно), и, если таймер достиг нуля, то запускаем соответствующий ему процесс. Алгоритм думаю достаточно прокомментирован.

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

Вот и вся операционка. Если вдуматься, ничего сложного тут нет. В скомпилированном виде вместе с АПИ (см. ниже) весит 1190 байт. Для вытесняющей операционки немного :)

Если ты до сих пор не устал, то сейчас я покажу тебе API.

Application Programming Interface (API) я сделал из 5ти функций. Просто чтобы было легко потом дописать загрузку процесса например из EEPROM или еще чего. Можно конечно использовать его в своих целях.

CreateProcess:
функция вызывается так:

	LDI R17, N
	RCALL CreateProcess

N — номер процесса в таблице Proctable (помни, адреса давно остались в прошлом, у нас номера:))
Сама функция такая:

;Создание нового процесса
 CreateProcess:		           ; R17 - номер процесса в таблице адресов
 	 LDS R16, LastItem	; Увеличим номер последнего элемента
	 INC R16
	 CPI R16, ProcNum	; Если больше размера очереди - выходим
	 BREQ Exit
	 STS LastItem, R16	; увеличим конец очереди
 
; Инициализация нового процесса
	 LDI YL, Low(ProcData)	; Начало области данных
	 LDI YH, High(ProcData)
 
	 INC R17
 	 LDI R16, ProcDataSize	; Получаем начало данных след. процесса
	 MUL R16, R17
	 ADD YL, R0
	 ADC YH, R1
	 DEC R17
	 LD  R16, -Y		; Уменьшим на 1 - конец данных нужного
	 			; В Y пару сохраняем этот адрес -
	 			; Это будет стек
 
	 LDI ZL, Low(ProcData)	; Начало области данных
	 LDI ZH, High(ProcData)
 
 	 LDI R16, ProcDataSize	; Получаем начало данных нужного процесса
	 MUL R16, R17
	 ADD ZL, R0
	 ADC ZH, R1
 
	 LDI R16, 33		; Очищаем место регистров - 32 регистра,
	 LDI R18, 0		; флаг состояния => пишем 33 нуля
 Clear:
 	 ST  Z+, R18
	 DEC R16
	 BRNE Clear
 
	 ST  Z+, YL		; Пишем адрес стека
	 ST	 Z+, YH
 
; Запуск процесса  - ставим в очередь
 
	 LDS R16, LastItem
	 LDI ZL, Low(TaskQueue)		; Загружаем  адрес в очереди
	 LDI ZH, High(TaskQueue)	; Исходя из номера последнего элемента
 
	 ADD ZL, R16
	 LDI R16, 0
	 ADC ZH, R16
 
	 ST Z+, R17		; И пишем туда наш номер процесса,
	 LDI R16, $FF		; потом FF
	 ST Z+, R16
Exit:
 	RET

Сначала увеличим указатель на последний элемент очереди. Дальше очищаем память процесса. Адрес начала стека — это адрес начала данных следующего процесса минус единица. Чистим 33 байта для регистров (чтоб при старте у процесса все регистры обнулились, включая SREG), и вписываем после 33х нулей адрес стека процесса. Вот и проинициализировали (слово-то какое!). Пишем в конец очереди наш номер процесса — и все готово. Как хорошо работать с номерами: так бы пришлось постоянно возиться с двубайтными адресами, переписывать их в очереди и т.д. Вообщем, была бы полная неразбериха.

Следующая АПИ-функция:

; Запуск процесса после паузы
; Используется системой, но, думаю, можно и самому попробовать :)
 StartProcess:				; R17 - номер процесса
	 PUSH ZL
	 PUSH ZH
     PUSH R16
 	 LDS R16, LastItem		; Увеличим номер последнего элемента
	 INC R16
	 CPI R16, ProcNum		; Если больше размера очереди - выходим
	 BREQ ExitS
 
	 Push R17
 
	 STS LastItem, R16
	 LDI ZL, Low(TaskQueue)		; Далее надо сдвинуть очередь
	 LDI ZH, High(TaskQueue)	; что мы и делаем
 
	 ADD ZL, R16			; получаем адрес конца очереди
	 CLR R17
	 ADC ZH, R17
 
	 MOV R17, R16			; сдвигать надо от конца и до текущего
 	 LDS R18, CurProc		; т.к. вставляем процесс после текущего
	 SUB R17, R18			; В R17 - количесво сдвигов
 ShellS:					; Сдвигаем (да, криво, я знаю)
	 	 LD R18, Z+
		 ST Z, R18
		 LD R0, -Z
		 LD R0, -Z
		 DEC R17
		 BRNE ShellS
 
	 LD R0, Z+			; и пишем в освободившееся место интересующий
	 POP R17			; номер процесса
	 ST  Z, R17
ExitS:
	POP R16
	POP ZH
	POP ZL
 	RET

Функция ставит уже созданный процесс в очередь после текущего. Как?

Увеличиваем указатель на последний элемент, как и в CreateProcess. Потом сдвигаем очередь — с текущего элемента и до конца, и пишем на освободившееся места нужный номер процеса. Надеюсь, это понятно.

Самая сложная функция: пауза процесса. Что для этого нужно?

Нужно убрать интересующий процесс из очереди. Вроде все просто. НО если мы убираем текущий процесс — надо немедленно перейти к следующему. А если другой — то ни в коем случае нельзя сохранять регистры. Это я и делаю:

;Поставить процесс на паузу
;Удаление - вечная пауза :)
 
; Внимание! Перед функцией ОБЯЗАТЕЛЬНО необходимо запретить прерывания,
; а после - разрешить. Иначе возможно будет плохо.
 
 SuspendProcess:			;R17 - номер процесса
	 LDI ZL, Low(TaskQueue)		; начало очереди
	 LDI ZH, High(TaskQueue)
 
	 LDI R16, 0
 Seek:					; Ищем процесс с таким номером в очереди
 		LD R18, Z+
		CP R18, R17
		BREQ EOSeek		; Нашли - идем дальше
		INC R16
		CPI R16, LastItem
		BRNE Seek
 
		RJMP NotFound		; А если нет такого - выходим
 EOSeek:
 
	 LDI R19, 0			; для распознания в макросе
	 STS TempProc, R17
	 MOV R17, R16			; Сохраняем номер в очереди
	 LDS R16, CurProc
	 CP	 R16, R17		; Если не равен текущему -
	 BRNE TNoSave			; то не сохраняем регистры
 TSave:
		 LDI R19, 1		; тоже для распознания в дальнейшем
		 RJMP NoDec		; первое, что пришло в голову :)
 
 TNoSave:
 		 CP R16, R17		; Если меньше текущего -
	 	 BRCS NoDec		; То уменьшаем номер текущего в очереди
		 	LDS R16, CurProc
		 	DEC R16
		 	STS CurProc, R16
 
 NoDec:
 	 LDI ZL, Low(TaskQueue)		; Далее надо сдвинуть очередь
	 LDI ZH, High(TaskQueue)	; что мы и делаем
 
     INC R17			; От текущего и до конца
	 ADD ZL, R17
	 LDI R16, 0
	 ADC ZH, R16
	 DEC R17
 
 	 LDS R16, LastItem
	 SUB R16, R17
	 INC R16
 Shell:				; Сдвигаем (да, криво, я знаю)
	 	 LD R18, Z
		 ST -Z, R18
		 LD R0, Z+
		 LD R0, Z+
		 DEC R16
		 BRNE Shell
 
	 LDS R16, LastItem	; уменьшаем номер последнего элемента
	 DEC R16
	 STS LastItem, R16
 
	 CPI R19, 0
	 BREQ NotFound		; и если стопим текущий процесс - то переключим
	   RJMP TM0_OVF
 
 NotFound:	 		; Иначе - с вещами на выход
	RET

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

Теперь рассмотрим таймеры:

;Поставить таймер 
 
/*
 Внимание! данная функция должна использоваться вместе с Suspend porcess
 Иначе через установленную задержку запустится второй экземпляр процесса,
 имеющий тот же адрес, ту же память и тот же стек, НО работающий парал -
 лельно первому, Соответственно их регистры будут мешаться друг с другом,
 указатель стека будет прыгать туда-сюда - вообщем, не очень приятно.
 
 делается так:
 ...
 CLI
  Rcall SetTimer
  Rcall Suspend process
 STI
 ...
*/
 SetTimer:				 ;R17 - номер процесса, R18(L), R19(H)-задержка
 	 PUSH R16
	 PUSH R17
	 LDI ZL, Low(TimerQueue)	; начало массива таймеров
	 LDI ZH, High(TimerQueue)	
 
	 LDI R16, 0
	 ROL R17			; умножим адрес на два - таймеры двухбайтные
	 ROL R16			; а вдруг кто-то 129 процессов замутит:)
	 ADD ZL, R17			; получаем адрес
	 ADC ZH, R16			 
 
	 ST	 Z+, R18		; Ставим таймер
	 ST  Z+, R19			; Ставим таймер
	 POP R17
	 POP R16
	RET				; выход

Функция проста — ищем нужный элемент в массиве и пишем туда значения таймера. ВСЕ! Остальное будет делать диспетчер.
А теперь подумай: раз таймер измеряется в количестве переключений, разве может он точно работать? Может. НО только в случае, если ты НИГДЕ больше не используешь CLI/STI, SuspendProcess и таймеры других процессов. Потому что в первом случае (cli/sti) просто диспетчер может запоздать, во втором — тоже диспетчер опоздает, но уже намного (т.к. большой кусок кода в CLI/SEI), а в третьем — если несколько таймеров дотикают до нуля одновременно, то процессы поставятся в очередь по возрастанию, и неизвестно, когда очередь дойдет до твоего процесса.

Я считал — вроде можно поставить двумя байтами задержку до 5.5 секунд. Думаю, этого достаточно. Если хочешь — можно переписать под 3х байтовые таймеры. Тогда будет до 1408 секунд.

И самая простая АПИ из всех, состоит из одной команды :D

; Процедура "Перейти к след. процессу" ------------------------------
/*
Usage:
  надо, чтобы следующим процессом в очереди стал такой-то?
  Ну просто позарез надо? Да еще чтоб запустился немедленно?
  Тогда эта функция для вас!
  Делаем так:
 
  ...
  LDI R18, 1		; Если задержка = 1 - процесс запустится
  LDI R19, 0		; при следущем переключении. Нам это и надо.
  CLI
  RCALL SetTimer	; Ставим таймер
  RCALL SuspendProcess	; Отключим тот процесс, который надо поставить - он уберется из очереди
  RCALL GoToNextProc	; А функция - типа API ^_^ при переключении таймер дотикает дло нуля
			; и поставит процеес следующим в очереди
  SEI			; чисто для приличия - RETI сам это сделает
*/
 GoToNextProc:
 	CLI		; Защита (на всякий)
	RJMP TM0_OVF	; Валим на прерывание таймера (не пашет? убери R)
 RET			; Сюда вернется процесс, поэтому RET нужен.

Гениальнейшая функция :)

Вот и все. Я детально описал всю свою операционку. Оптимизацией почти не занимался, это думаю видно.
Конечно, на каком-нибудь АТМЕГА8/16 использовать такое не особенно нужно. Однако, как я писал выше, основной целью написания этой операционки было ознакомление с механизмом переключения процессов. Искренне надеюсь, что ты понял все, что я писал.

На реальном девайсе я это ни разу не запускал, работал только с тремя процессами в эмуляторе. Там ничего не слетало. Однако совершенно не исключено, что там есть баги. Так что если кто все же надумает построить на этом девайс — поаккуратнее :)

Сам исходник лежит по ссылке. Предупреждаю — весь код в одном файле. Я очень не люблю структурность и раскидывание на много файлов :)

47 thoughts on “AVR. Учебный Курс. Архитектура Программ. Часть 4”

  1. На таком уровне действительно все не сложно. Интереснее начинается на реальной платформе, когда появляются приоритеты задач, и необходимость менеджить виртуальную и физическую память итп. В WinCE весь код OS доступен разработчикам кроме некоторых исключений. Одно из них — диспетчер задач (scheduler). Не с проста, надо думать :)

    1. На реальной платформе конечно же все сложнее, однако приоритеты ТУТ например сделать не трудно: поставить процессы в очередь по нескольку раз.

      1. Обычно в real-time системах сперва обрабатываются задачи с более высоким приоритетом, потом, когда они перестают требовать процессорное время (ждут ввода-вывода, события или просто остановлены) время отдается задачам с более низким приоритетам.

  2. >> Сохранение виртуальной памяти — в файл подкачки или еще куда-нибудь.
    >>3.1) Загрузка виртуальной памяти.
    >>3.2) Проверка следующего кода программы на правильность — нулевые указатели, неверные команды и т.д.

    Эти пункты выглядят как бред. Во-первых, виртуальная память и подкачка — хоть и смежные, но разные понятия. Виртуальная память может быть и вовсе БЕЗ подкачки.

    Ни одна известная ОС память не загружает и не сохраняет при переключении задач, потому что это было бы архинеэффективно. В x86, например, при переключении задачи (потока) есть два сценария: если новый поток принадлежит тому же процессу, что и старый поток, то ничего (связанного с ВП) не происходит, если же новый поток принадлежит другому процессу, то меняется значение регистра CR3/PDBR так, чтобы он указывал на новый каталог страниц (Page Directory), использующийся при трансляции линейного адреса в физический. Подкачка же выполняется при обращении к выгруженным страницам ФП. Процессор при этом инициирует прерывание #PF (page fault), а ОС его обрабатывает.

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

    1. Эти пункты я не знаю точно — я их домысливал. Однако, например, как даст о себе знать команда
      mov esi, 0
      mov [esi], 1
      ? По виндовской технологии присваивание в нулевые адреса запрещено. Хотя оно не порушит программу — первые 0..X (не помню сколько) адресов не используются вообще — там пусто. Так что не представляю себе, как такую ошибку отловить где-нить кроме вритуального процессора. Если поясните — буду признателен, я реально не знаю толком.

      1. Если нет знаний, не нужно выдумывать всякую фигню.

        >>Если поясните — буду признателен, я реально не знаю толком.
        Эта (mov [0], 1) команда выполнится, процессор сгенерирует прерывание (#GP или #PF), оно обработается ядром ОС. Дальше начнёт работу механизм исключений Windows. Будет выброшено исключение 0xc0000005 (STATUS_ACCESS_VIOLATION), обработчик пройдётся по цепочки зарегистрированных обработчиков исключений, начиная с регистрационной записи, адрес которой содержится по FS:[0], пока не найдётся обработчик, согласившийся обработать исключение.

        Если согласившийся обработчик не будет найден, в user-mode будет вызван обработчик UnhandledExceptionFilter, результатом которого будет завершение потока с окном «Отправить отчёт» (и вариантом аттача отладчика к процессу).

        В kernel-моде будет вызвана функция KeBugCheckEx, которая выведет BSOD.

            1. И еще такой вопрос: как тогда отловить например CLI?
              Ведь если в обычной программе я юзаю CLI (без дальнейшего STI), мне пишут ошибку «privileged instruction». отловить ее после выполнения нереально — она ж вырубает прерывания.

    2. А насчет виртуальной памяти — я же не написал, что ВСЕГДА сохраняется/загружается. Я написал о том, что в операционках часто приходится это делать. Может и не придется, если стоит 8ГБ оперативы, может иногда придется, а может и всегда, если пытаться запустить какой-нить Win7 на 256-512 мегов.

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

        Но виртуальная память отлично может быть без своппинга. Может быть Win7 с 256 мб оперативки и ВЫКЛЮЧЕННЫМ своппингом. Никаких загрузок/сохранений при этом не будет (с незначительной оговоркой, которой можно пренебречь).

        При включенном своппинге загрузка/выгрузка происходит.

        Но (и в этом вся соль!) выполнение сохранения/загрузки вообще никак не связано с переключением задач/потоков. Поводом к переключению является то, что пришло время переключить. Поводом к сохранению/загрузке является #PF (Page Fault).

  3. Только не посчитайте меня гундосом, но для чего многозадачность на контроллере c одним процессором? Вот в винде мне абсолютно ясно- это сделано, в первую очередь для того, что бы программы разных производителей не толкались друг с другом. А вот эпл пошел по другому пути- они сторонним разработчикам дали инструментарий, все работает в одном процессе, если не врут конечно.
    Мне просто интересно.

    1. Далеко не всегда удобно выполнять все различные задачи строго последовательно — пока не преслали данные кнопки не обрабатываются и т.п. Чистые прерывания не всегда подходят по ряду причин — вот и городит народ RTOS’ы, причём вполне успешно — при более-менее объёмной задаче как правило вырисовываются процессы/задачи, которые оптимально выполнять именно параллельно.

      1. Вот я таких задач, честно скажу не знаю. Когда я просто подпрыгивал от нетерпения, что бы распараллелить парочку процессов, всегда (а я уже программирую больше 15 лет и с чем только не сталкивался) чуть позднее находился простой путь обхода, в частности всегда выручал механизм событий, как в маздае, например.

        Так что вопрос остается в силе. Для чего все это? Опять же это любопытство, так как объяснения из серии «хочу чтоб так было,хочу понять, хочу научиться»- меня вполне устраивают.

        1. Тогда гуглите области применения RTOS — основные идеи станут понятны :) Событийная модель, система прерываний, RTOS — у всех свои применения.

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

            1. Там же в начале написано:
              >>Отмазки
              Сея программа не более чем учебный пример. Т.к. не тестировалась в серьезных условиях. Не использовалась в каких либо проектах, а гонялась только на эмуляторе. Смысл ее не дать готовое решение, а показать принцип и механизм работы диспетчера операционной системы с принудительным переключением задач. Да и AVR это не та платформа на которой имеет смысл городить вытесняющие диспетчеры.
              Так что тут она только как пример.
              А вот например уже на ARM такое вовсю используется — тот же WinCE :)

              1. Это мне абсолютно понятно, мало того ваша попытка, на сколько понимаю удачна, мало того, с моей точки зрения похвальна, уж простите за высокомерие:)
                Мое же любопытство имеет следующий характер, «а бывает в жизни так, чтоб на контроллере и без многозадачности ну вообще ни как». То есть меня интересуют случаи из программистского опыта.

                1. Бывает. Когда у тебя вечный цейтнот, когда в последний день приходит заказчик и говорит «а давайте добавим вот это…» И тогда понимаешь что без перекрута всего уже выверенного и отлаженного алгоритма это не сделать.

                  На RTOS развитие и модернизация идет куда быстрей и с меньшими мозговыми затратами.

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

                  1. Эта задача легко делается и без ОС. На обычном флаговом автомате или на конечных автоматах. С другой стороны на диспетчере это будет сделать в разы проще и быстрей.

                    1. Нехорошо себя цитировать, однако «Вот в винде мне абсолютно ясно- это сделано, в первую очередь для того, что бы программы разных производителей не толкались друг с другом» — это все из той же оперы, только чтоб собственные программы тоже не толкались друг с другом.

                      Другое, дело, что именно сегодня я размышлял над компоновкой контроллера для одной железки и вдруг меня накрыло, то что называется, вдогонку к дискуссии.

                      Очень хочется мне поиметь обработчик событий — клавиатуры и прочее.
                      То есть обрабатывается все то, что прямо внутри прерывания, допустим , обрабатывать не имеет смысла или вообще вредно. То есть пришло прерывание- положили сообщение в очередь и забыли.

                      У обработчика событий одна задача- опустошать очередь событий, по ходу дела вызывая для них соответствующие процедуры.

                      Допустим, очередь событий пуста, тогда обработчик сидит и ждет нового события.
                      Вот тут, очень хочется порешать какую-нибудь серьезную задачку, найти, например , обратную матрицу 10×10 -иногда надо. Так вот, без вытесняющей многозадачности, развязать обработчик событий и затратный вычислительный процесс я не понимаю как. Еще раз подчеркну- события я не хочу обрабатывать внутри прерывания.

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

                      Как это же сделать без переключения контекста? Чует мое сердце, что затупил, однако ваш диагноз?

                    2. Например, побить численное вычисление на куски и давать в нем обработчику клавиатуры глотнуть чистого воздуха.

                      Плюс что плохого в обработке событий внутри прерываний?

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

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

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

                      Короче резюме- вытесняющая многозадачность концептуально необходима исключительно для удобства разработки / эксплуатации и только для этого?

                    4. Концептуально да. Т.к. нельзя придумать случая со статичным кодом (т.е. зашил и забыл) когда нельзя обойтись без него. На практике же каждая задача — индивидуальная головоломка которую надо решать каждый раз заново.
                      Тогда как применение RTOS сводит все к тривиальным тупым алгоритмам разруливая все посредством диспетчера.

                      А вот если мы сидим на арме.. да можем (да хоть по уарту) грузить в память исполняемый код на лету. Вот тут фишки ос вылезают в полный рост :)

                    1. По идеи, думаю, без ОС можно сделать все. Можно впринципе скачать линукс и ради каждой новой фичи его перекомпилировать, и все будет в одном процессе :)Ну это я утрирую. Другое дело, насколько просто сделать без ОС. Как Ди говорит, если и так прога нафаршированная до отказа, то дописать туда новую фичу, возможно, будет весьма и весьма проблематично.

                      Можно еще использовать так:
                      Пишешь одну основу, делаешь загрузчик, пишущий все, что идет с USART’а в EEPROM, а основа при старте грузит все процессы, записанные в EEPROM. Получится простейший расширяемый функционал — воткнул плату в COM-порт, запустил утилитку, закачал на девайс новую фичу и все счастливы :D

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

    1. Это не просто механизм удобной работы с ОЗУ, это еще и пути возврата из функций и процедур. Представь, ушла у тебя задача во вложенные функции, зарылась в стек. Тут ее насильно переключили на другую задачу, та тоже насрала в стек, опять переключили, следлующая тоже испортила стек. Вернулись в первую задачу, она лезет доставать свои данные из стека… Сюрприз!!!

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

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

          1. А я стек и не таскаю :) я просто SP сохраняю тоже в память процесса. А стек лежит на месте. При загрузке — опять же грузится SP и все.

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

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

      1. Я тестил его на эмуляторе. Гонял довольно долго и много раз. Стоит 3 процесса, один юзает стек, другой — таймеры, третий ниче. Ну и в R16 для тестов каждый процесс пишет свое число.
        При таком раскладе все работает в эмуле. Багов пока не было. А на девайсе не запускал т.к. не было надобности.

  6. Интересная статья, спасибо! Но вот у меня есть один вопрос(мне к сожалению сложно его адекватно сформулировать …), мне он покоя не дает —
    если рассматривать допустим какой нибудь ARM7 допустим у меня есть подобие ОС под этот арм и есть несколько процедур(потоков/задач) которые запущены и работают. Но!!! мне вдруг захотелось, запустить процесс извне(ммс карты или еще откуда нибудь) что мне делать? Как мне скомпилить отдельный поток(процедуру)? В арме программу можно запихнуть в оперативку и запустить, но как быть с адресами переходов внутри процесса как их изменить. Что происходит при запуске(и компиляции) программы в тех же виндах или unix системах?
    Так много дурацких вопросов….. Подскажите пожалуйста.

    1. Если я правильно понимаю, при компиляции пишется смещение всех функций и переменных относительно начала проги. При загрузке в винде проге выделяется виртуальная память, и адреса как-то транслируются в физическую. Как именно — не знаю.
      Если сам пишешь — ну можно попробовать пройтись по машинному коду программы и приплюсовать ко всем адресам начало в реальной памяти :) Может быть можно использовать относительные переходы. С ними попроще будет.

      1. Спасибо за ответ :). Похоже нужен специфический компилятор ибо ко всем функциям смещение задавать плохо, возможен вариант использования допустим каких-либо одинаковых функций(printf например) в разных процессах. Для них смещение делать не надо(точнее оно для всех одно и то же), да и включать при компиляции такие функции надо один раз…. Относительные переходы … надо подумать. Где бы найти компилятор который может такое, Keil такое не умеет походу. Буду мучить мозг дальше, спасибо еще раз.

  7. Спасибо за базис, DI HALT!
    P. S. В институте у нашего препода «системного программирования» была кличка — Дебил.

Добавить комментарий

Ваш e-mail не будет опубликован.

Перед отправкой формы:
Human test by Not Captcha