Вытесняющая многозадачность (диспетчер mzkernel)

[Barmaley_m]

Здравствуйте, друзья.

Предлагаю вашему вниманию диспетчер для организации на ZX Spectrum вытесняющей многозадачной среды.

Описание его архитектуры и работы - на Хабре (http://habrahabr.ru/post/228049/).

Текущая версия исходника - на GitHub (https://github.com/mborisov1/mzkernel)

На данный момент реализация минимальная. Фиксированное количество потоков (threads), фиксированный приоритет потоков, из объектов ожидания присутствует только два типа Events. Этого уже достаточно для того, чтобы можно было говорить о многозадачности, но мало для настоящей ОС. Можно использовать только в рамках отдельной прикладной программы, где заранее известно, сколько надо потоков.

Я старался оптимизировать код; если был выбор между размером кода и быстродействием - выбирал быстродействие. Одна важная возможность оптимизации пока не использована. В диспетчере широко применяется индексная адресация, а она у Z80 жутко тормозная. В перспективе можно будет от нее отказаться, но для этого надо, чтобы устоялись структуры данных. Иначе любое изменение в них приведет к необходимости изменений большого количества кода.

Приглашаю к обсуждению и внесению предложений по усовершенствованию, оптимизации. Сам планирую на досуге вносить усовершенствования, в первую очередь, следующего плана:
1) динамический приоритет потоков
2) объекты ожидания типа Mutex
3) пуск новых и завершение старых потоков реализовано 21.07.2014

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

Обновления:
21.07.2014 - небольшие оптимизации, добавлена возможность пуска новых и завершения старых потоков

[alone]

Может быть, поможет такой проект ядра с поддержкой страничной адресации и сообщений (рассчитан на ассемблер ALASM), автор sman:



STRUCT app
BYTE priority ;приоритет (0=конец списка)
BYTE flags ;флаги (factive, ftimeslice, fusetimer)
factive=0 ;есть сообщения: SET при добавлении сообщения, RES при взятии последнего сообщения
ftimeslice=1
fusetimer=2
;ftimer=3
;fcritical=4 (чтобы не портить hl)
WORD id ;номер задачи
WORD mainpg ;главная страница задачи (там очередь сообщений)
WORD curmsg ;адрес текущего сообщения этой задаче
WORD endmsg ;адрес конца очереди сообщений этой задаче
WORD curpg ;текущая страница
WORD sp ;текущий адрес стека (можно хранить в ТЕКУЩЕЙ (не главной) странице, но это бессмысленно)
WORD next ;указатель на следущую задачу (следующая за выполняемой внутри того же приоритета)
;[номер задачи, которая ждёт готовности этой задачи]
ENDSTRUCT

STRUCT msg
WORD type ;тип сообщения (2 б)
WORD sender ;автор сообщения (2 б)
WORD par0
WORD par1
WORD par2
WORD par3
WORD par4
WORD par5
ENDSTRUCT
;16 байт (делитель числа 256)

WORD Os_curapp ;()=Os_Tapp
WORD Os_nextapp ;()=Os_Tapp
WORD Isr_SP
WORD Os_frames
BYTE Os_critical
WORD Os_targetid
ARRAY Os_msg1,SIZEOF_msg
ARRAY Os_msg2,SIZEOF_msg
Os_TIMERSENDER=55555

MACRO STARTCRITICAL
ld hl,Os_critical
inc (hl) ;с этого момента уже не задача, а шедулер
ENDM

MACRO ENDCRITICAL
ld hl,Os_critical
dec (hl) ;выключение+проверка прерванности ОДНОВРЕМЕННО
CALL NZ,IsrEndCritical ;переход на IsrEndCritical не прервется, т.к. в этом случае di
;тут уже можно считать, что выполняется задача
ENDM

;выход из контекста задачи
MACRO RELEASECONTEXT
ld ix,(Os_curapp)
ld hl,(curpg)
PUTWORD app_curpg,HL
ld hl,0
add hl,sp
PUTWORD app_sp,HL
ld sp,lowmem
ENDM

;вход в контекст задачи
MACRO GETCONTEXT
GETWORD HL,app_sp
push bc,hl
GETWORD HL,app_curpg
SETPG
pop hl,bc
ld sp,hl
ENDM

MACRO SETFLAG
SET \0,(IX+app_flags)
ENDM

MACRO RESFLAG
RES \0,(IX+app_flags)
ENDM

MACRO TESTFLAG
BIT \0,(IX+app_flags)
ENDM


;шлет событие клавиатуре, гую, мыши, плееру (всем, кто подписан на таймер)
;подписанность на таймер - флажок fusetimer (как программа его установит?)
;страница на выходе должна должна остаться прежней!
;просто поставить флаг ftimer
;[вариант:вызвать обработчик таймера у конкретного потока (если задан адрес)]
Timer
ld ix,Os_Tapp-SIZEOF_app
ld de,SIZEOF_app
Timer0
add ix,de
ld a,(ix+app_priority)
or a
ret z
TESTFLAG fusetimer
jz Timer0
SETFLAG ftimer
jr Timer0



;делает то же, что таймслайс
Sleep
STARTCRITICAL
ld ix,(Os_curapp)
SETFLAG ftimeslice ;в контексте задачи
call Sched ;переключить задачу (стек и т.п.)
ld ix,(Os_curapp)
RESFLAG ftimeslice ;в контексте задачи
ENDCRITICAL
;выход из таймслайса
ret

IsrEndCritical
;прерывания отключены
;можно портить только AF,HL
dec (hl) ;1-1=0
push ...
call Isr
pop ...
;прерывания включены
ret

Isr
;регистры можно портить, но страница должна быть включена та же
ld (Isr_SP),sp
ld sp,lowmem
;определяем тип прерывания и работаем с ним (портит списки задач и сообщений)
;Если не определилось RS232, то экранное.
;Если определилось RS232, читать ВЕСЬ буфер (т.к. могло потеряться прерывание от RS232).
;Если RS232 произошло чуть позже экранного, то оно теряется.
;Если экранное произошло чуть позже RS232, то оно теряется (с этим ничего не поделать)
;fcritical=0, т.е. можно вызывать SENDMSG (но нельзя DOMSG)
call Timer
;
ld sp,(Isr_SP)
ei
ret

;случай прерванной критической секции
;сразу возврат, а перед выходом из критической секции вызвать IsrEndCritical
CriticalInt
;прерывания выключены
inc a ;=2
ld (Os_critical),a
;pop hl
pop af
ret ;в шедулер

OnInt
push af
;push hl
;todo внутри timer
;ld hl,(Os_frames)
;inc hl
;ld (Os_frames),hl
ld a,(Os_critical)
or a
jnz CriticalInt
push ...
CALL Isr ;делает ei
;включен контекст задачи, ее стек и ее страница, т.е. якобы она выполняется
call Sleep
pop ...
;pop hl
pop af
ret

GetMsg
STARTCRITICAL
call Sched
;exx
;todo при вызове Sched регистры класть сюда, а брать их на выходе (а не здесь)?
ld bc,(Os_msg1+msg_par3)
ld de,(Os_msg1+msg_par4)
ld hl,(Os_msg1+msg_par5)
exx
ld bc,(Os_msg1+msg_par0)
ld de,(Os_msg1+msg_par1)
ld iy,(Os_msg1+msg_par2)
;парамеры сообщения в hl',de',bc',iy,de,bc
ld hl,(Os_msg1+msg_type) ;обязательно в критической секции!
ld ix,(Os_msg1+msg_sender) ;
push hl
ENDCRITICAL
pop hl
ret

;парамеры сообщения взять в bc,de,iy,bc',de',hl'
MsgGetPars
GETWORD HL,app_mainpg
SETPG
GETWORD HL,app_curmsg
ld de,Os_msg1
ld bc,15
ldir
ld a,(hl)
ld (de),a
inc l
PUTWORD app_curmsg,HL
GETWORD DE,app_endmsg
or a
sbc hl,de
ret nz ;не последнее сообщение в очереди
RESFLAG factive ;последнее
ret

;ищем первую активную/таймслайсную задачу от начала списка задач
;активная - либо в таймслайсе, либо есть сообщения, либо таймер
SchedFind
LOCAL
ld ix,Os_Tapp-SIZEOF_app
ld de,(Os_nextapp) ;"следующая внутри приоритета"
ld bc,SIZEOF_app
_next
add ix,bc
ld a,(ix+app_flags)
and factive|ftimeslice|ftimer
jz _next ;имеет тот же приоритет, что "следующая внутри приоритета", но расположена раньше - пропускаем
ld a,(de) ;приоритет текущей/следующей внутри приоритета
cp (ix+app_priority)
jnz _ok
push ix
pop hl
;or a ;CY=0
sbc hl,de
jc _next ;расположена раньше внутри приоритета - пропускаем
_ok
GETWORD HL,app_next
ld (Os_nextapp),hl ;"следующая внутри приоритета"
ENDL
ret

;переход на задачу с ID=bc
CallTask
STARTCRITICAL
RELEASECONTEXT ;портит hl,ix
ld ix,(Os_curapp)
SETFLAG ftimeslice ;в критической секции, а то вдруг до STARTCRITICAL выпадет прерывание, которое завалит задачу в таймслайс и на следующем входе в неё СНИМЕТ этот флаг
;поиск задачи (если нету такой, то любую)
ld ix,Os_Tapp-SIZEOF_app
ld de,SIZEOF_app
SchedGivenSearch
add ix,de
ld a,(ix+app_priority)
or a
jz SchedSearch ;нету такой задачи - переходим на любую
GETWORD HL,app_id
;CY=0
sbc hl,bc
jnz SchedGivenSearch
;не следует искать Os_nextapp, т.к. мы рвём последовательность выполнения задач только для одного вызова
jr SchedFound

Sched
RELEASECONTEXT ;портит hl,ix
SchedSearch
call SchedFind ;выбираем задачу - результат в ix
SchedFound
TESTFLAG ftimeslice
jnz SchedOk ;таймслайс - просто переходим на задачу
TESTFLAG ftimer
jz SchedGetPars ;если таймер был, обслуживаем его в первую очередь
RESFLAG ftimer
ld hl,Os_TIMERSENDER
ld (Os_msg1+msg_sender),hl ;псевдосообщение, важен только sender
jr SchedOk
SchedGetPars
call MsgGetPars
SchedOk
ld (Os_curapp),ix
GETCONTEXT ;портит hl,нужен ix
ret ;задача


;CY=адресат не найден
SendMsg
;ix - ID адресата
;hl - тип сообщения
;bc,de,iy,bc',de',hl' - параметры
;Если при посылке сообщения очередь превысила лимит, то ставим текущую задачу в таймслайс и переход на задачу, которой шлём (если она не в таймслайсе)
;а если она в таймслайсе - крутимся, пока не будет готова, или до таймаута
push hl
STARTCRITICAL
pop hl
;обязательно в критической секции!
ld (Os_targetid),ix ;ID адресата
ld (Os_msg2+msg_type),hl
GETWORD HL,app_id
ld (Os_msg2+msg_sender),hl
ld (Os_msg2+msg_par0),bc
ld (Os_msg2+msg_par1),de
ld (Os_msg2+msg_par2),iy
exx
ld (Os_msg2+msg_par3),bc
ld (Os_msg2+msg_par4),de
ld (Os_msg2+msg_par5),hl
;exx
RELEASECONTEXT ;портит hl,ix
;поиск адресата (если нету, то выход)
ld bc,(Os_targetid) ;ID адресата
ld ix,Os_Tapp-SIZEOF_app
ld de,SIZEOF_app
SendMsgSearch
add ix,de
ld a,(ix+app_priority)
or a
jz SendMsgError ;конец списка задач - не найдена нужная
GETWORD HL,app_id
;CY=0
sbc hl,bc
jnz SendMsgSearch
;включаем главную страницу адресата
GETWORD HL,app_mainpg
SETPG
SendMsgLoop
;есть место в очереди?
GETWORD HL,app_curmsg
GETWORD DE,app_endmsg
or a
sbc hl,de
jz SendMsgNoRoom
;есть место {
;шлем сообщение
ld hl,Os_msg2
ld bc,15
ldir
ld a,(hl)
ld (de),a
inc e
PUTWORD app_endmsg,DE
ld ix,(Os_curapp)
GETCONTEXT
ENDCRITICAL
or a ;CY=0
ret ;отправитель
SendMsgError
ld ix,(Os_curapp)
GETCONTEXT
ENDCRITICAL
scf ;CY=1
ret ;отправитель
;}
SendMsgNoRoom
;de=curmsg=endmsg
;нет места {
TESTBIT ftimeslice ;адресат в таймслайсе?
jnz SendMsgTimeSlice
;не в таймслайсе {
;берем первое сообщение
push de
exd
ld de,Os_msg1
ld bc,15
ldir
ld a,(hl)
ld (de),a
inc l
PUTWORD app_curmsg,HL
;кладём наше сообщение
pop de
ld hl,Os_msg2
ld bc,15
ldir
ld a,(hl)
ld (de),a
inc e
PUTWORD app_endmsg,DE
;переход на адресат:
ld (Os_curapp),ix
;ищем "следующую внутри приоритета", запоминаем ее
GETWORD HL,app_next
ld (Os_nextapp),hl
;exx
ld bc,(Os_msg1+msg_par3)
ld de,(Os_msg1+msg_par4)
ld hl,(Os_msg1+msg_par5)
exx
ld bc,(Os_msg1+msg_par0)
ld de,(Os_msg1+msg_par1)
ld iy,(Os_msg1+msg_par2)
GETCONTEXT ;портит hl,нужен ix
ld hl,(Os_msg1+msg_type) ;обязательно в критической секции!
ld ix,(Os_msg1+msg_sender) ;
push hl
ENDCRITICAL
pop hl
ret ;адресат
;}
SendMsgTimeSlice
;в таймслайсе {
;берем контекст отправителя и входные регистры
;exx
ld bc,(Os_msg2+msg_par3)
ld de,(Os_msg2+msg_par4)
ld hl,(Os_msg2+msg_par5)
exx
ld bc,(Os_msg2+msg_par0)
ld de,(Os_msg2+msg_par1)
ld iy,(Os_msg2+msg_par2)
ld ix,(Os_curapp)
GETCONTEXT ;портит hl,нужен ix
ld hl,(Os_msg2+msg_type) ;обязательно в критической секции!
ld ix,(Os_targetid) ;
push hl
ENDCRITICAL
pop hl
;переключаем задачу
;желательно включить адресат
;иначе если адресат имеет приоритет ниже приоритета отправителя, то эта задача всегда будет включена снова раньше, чем хоть раз вызовется адресат - будет вечный цикл
;повиснет, если адресат сам ждет задачу, приоритет которой ниже, чем приоритет отправителя!!!
;поднять приоритет адресата до уровня отправителя?
push af
push hl
push ...
push ix
pop bc ;ID адресата
call CallTask ;переключиться на адресат (если не существует, то на любую задачу)
;выход из таймслайса
pop ...
pop hl
pop af
jp SendMsg ;новая попытка
;}
;}

[Shadow Maker]

Помню еще такой вот проект: http://zx-pk.ru/showthread.php?t=21281

[Vitamin]

В перспективе можно будет от нее отказаться, но для этого надо, чтобы устоялись структуры данных.
Ну для этого можно
а) использовать средства компилятора для организации структур (а не хардкодить оффсеты)
б) использовать что-то типа assert'ов для контроля смещений (если их нет, надо добавить:) )


;somewhere in defines
STRUCT THREAD
FLAGS BYTE
INDEX BYTE
ENDS

;somewhere in kernel
;hl- thread addr
KiUnwaitThread:
ASSERT(THREAD.FLAGS = 0)
ASSERT(THREAD.INDEX = 1)
ASSERT(THREAD = 2)
; Set the thread's state to Ready
set THREAD_FLAG_READY,(hl)
; Check if the thread's priority is higher than of any other requesters
inc hl
ld a,(request_thread)
cp (hl)
ret c
ld a,(hl)
ld (request_thread),a ;the new thread has a higher priority
ld (request_thread_ptr),hl
ret

[NovaStorm]

В диспетчере широко применяется индексная адресация, а она у Z80 жутко тормозная. В перспективе можно будет от нее отказаться

Несмотря на тормоза с индексами, это на Z80 таки быстрейший способ _произвольного_ доступа к структурам на стеке, а писать с ними удобнее.

[SfS]

Автор - молодец! Буду глядеть.

[Barmaley_m]

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

[Alex/AT]

Здравствуйте, друзья.
1) динамический приоритет потоков
2) объекты ожидания типа Mutex
3) пуск новых и завершение старых потоков
На самом деле - не проще взять на развитие мой scheduler_g2? ( http://zx-pk.ru/showthread.php?t=21281 ) Там уже есть и кооперативная многозадачность, и вытесняющая, пуск потоков, и удаление, и блокировки, и синхронизация по тактам, и возможность вешать хуки сохранения/восстановления контекста (например страницу окна 3). Плюс он достаточно оптимизирован. И приоритет можно менять на ходу, если очень хочется (хотя нафиг это в рамках ZX нужно). Если хочется из него сделать полностью вытесняющий вариант без синхронизации - достаточно просто не вызывать функции отдачи таймслайса, и всё.

[shurik-ua]

Описание его архитектуры и работы - на Хабре.
Там в каментах что-то про файберы говорится - мол с ними совсем другой коленкор - есть инфа на русском про эти самые файберы ?

[alone]

Сйдя по википедии, файберы - это системная реализация сопроцедур. Что-то подобное было в моей статье тут: http://nedopc.org/nedopc/journal/NedoPC_5.pdf
Более сложный вариант: http://pastebin.ru/L2KulLbB

Вообще статьи о разработках такого плана приветствуются в нашем журнале.

[Alex/AT]

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

Если строго, то в моём scheduler_g2 - гибрид тредов и файберов, модель там кооперативно-вытесняющая. :) Но по сути на ZX реально применимы только файберы - частота единственно имеющегося прерывания от таймера для вытесняющей модели крайне мала :), а большинству задач надо успеть в один и тот же экран выполниться.

[Barmaley_m]

есть инфа на русском про эти самые файберы ?
Файберы (Fiber) - это нечто, похожее на потоки (Threads), но в некоторых ОС, таких как Win32, допускается исполнение (неодновременное) нескольких файберов в одном потоке. Отсюда происходит и термин. Thread - нить, а Fiber - волокно, т.е. боле мелкая, составляющая часть нити.

Каждый файбер имеет свой стек, как и поток. Но переключение между файберами происходит только вручную. Есть функция, например Win32 SwitchToFiber(HANDLE), которая переключает исполнение на заданный файбер. При этом состояние текущего файбера (стек) сохраняется. Когда другой файбер сам вызовет SwitchToFiber() на исходный файбер - то исполнение первого файбера будет продолжено.

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

... code ...
... call some_function ...
... code ...

При этом функция some_function где-то внутри себя вызывает SwitchToFiber, переключая исполнение на другой файбер, и когда другой файбер отдаст управление назад - функция some_function делает какие-то завершающие действия и возвращается.

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

---------- Post added at 19:19 ---------- Previous post was at 19:05 ----------


На самом деле - не проще взять на развитие мой scheduler_g2? ( http://zx-pk.ru/showthread.php?t=21281 )
Спасибо, я поизучаю твой проект. Не знал о его существовании. Ну и в любом случае я делал бы свой, т.к. хотелось поупражняться в этом деле :)

---------- Post added at 19:24 ---------- Previous post was at 19:19 ----------


Треды - вытесняющая модель, файберы - кооперативная.
С этим согласен полностью.

Но по сути на ZX реально применимы только файберы - частота единственно имеющегося прерывания от таймера для вытесняющей модели крайне мала :), а большинству задач надо успеть в один и тот же экран выполниться.
А вот с этим категорически не согласен. При чем тут вообще прерывания от таймера к модели многозадачности? Вытесняющую многозадачность можно реализовать и вовсе без прерываний. Я думаю, дело в том, что многие заблуждаются насчет вытесняющей многозадачности в том, что будто бы ее основная идея - быстрое переключение между потоками (Round Robin), чтобы обеспечить их псевдопараллельное исполнение. Нет, на самом деле это тоже можно сделать, но вытесняющая многозадачность - это более широкое понятие, чем Round-Robin.

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

[Alex/AT]

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

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

Конечно, сделать вытесняющую многозадачность можно и с вытеснением раз в 1/50 секунды, но смысла в этом большого реально нет. Основное применение шедулера на ZX, как мне видится, это возможность в фоне считать "длинные" и вспомогательные задачи, параллельно исполняя основные, которые отрисовывают результат.


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

Почему настоятельно советую попробовать взять мой планировщик - собственно по двум причинам: а) он сильно оптимизирован; б) он умеет то, что жизненно необходимо ZX - хотя бы приблизительную синхронизацию с экраном. При условии, конечно, что задачи сообщают адекватное время выполнения в кооперативной модели. Как это работает - можно посмотреть в примерах. Он под GPLv2, поэтому можно смело выкладывать в GIT, если будут идеи - я присоединюсь к доработке, времени 100% мейнтейнить, к сожалению, нет. Да, код самого планировщика получился к сожалению достаточно сложным, оптимизация требует жертв. Там очень много комментариев, которые помогут разобраться.

[Barmaley_m]

Извини, но это бред.
Прошу заметить, я тебя не оскорблял.

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

Несмотря на то, что без вытеснения по прерываниям работа системы будет в некоторой степени детерминированной (наподобие кооперативной многозадачности), отсутствие знаний о работе хотя бы одного из потоков превращает работу такой системы в недетерминированную, когда каждый конкретный поток не знает, когда у него заберут процессорное время. Например, в моем диспетчере поток, устанавливая объект "Event", не знает, будет ли он при этом вытеснен. Это зависит от того, ожидает ли сигнализации этого объекта другой поток с более высоким приоритетом.

Ну и да, в моем диспетчере поддерживается вытеснение и по прерываниям, если в процедуре их обработки будут вызываться функции вида "SetEvent".

Даже если мы будем "вытеснять" задачу сами в пределах ядра при вызовах функций ядра - всё равно это будет де факто кооперативная многозадачность, просто кооперативность будет обеспечиваться ядром,
Ошибка именно здесь. Если обеспечивается ядром - значит уже не кооперативность.

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

"Настоящие" современные ОС тоже не переключают контекст потоков без необходимости. Это дорогая операция. Зачем жечь время процессора зря? Даже переключение по таймслайсам для реализации Round-Robin псевдопараллельного исполнения использует интервалы времени, сравнимые или превышающие 1/50с.

Основное применение шедулера на ZX, как мне видится, это возможность в фоне считать "длинные" и вспомогательные задачи, параллельно исполняя основные, которые отрисовывают результат.
В этом смысл многозадачности вообще, а не только на ZX. Длительная работа в режиме Round-Robin - это плохая ситуация даже на современных "больших" ОС, так как каждая задача при этом работает медленнее, чем хотелось бы.

Никто, опять же, не мешает запихать принудительную кооперативность в некие системные вызовы ядра - и получим примерно то, что сделано в твоём планировщике
Нет, получим не то, что сделано в моем планировщике, а Windows 3.11. Это там была "принудительная кооперативность" при вызове функции GetMessage или PeekMessage, а в других ситуациях контекст не переключался.

То, что сделано у меня - это переключение контекста по событиям, которые, по принятому принципу работы, являются основаниями для смены контекста. Быстро и максимально отдать время процессора приоритетным (важным) потокам; когда они чего-то ждут, например, нажатия клавиши - отдать время остальным.

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

Точно так же сделано в реальных больших ОС. Я разрабатывал диспетчер после долгого и подробного курения исходников ReactOS (аналог Windows). Там, конечно, реализовано больше, чем у меня - но не в один день Москва строилась; и не все из этого нужно на ZX.

Почему настоятельно советую попробовать взять мой планировщик - собственно по двум причинам: а) он сильно оптимизирован; б) он умеет то, что жизненно необходимо ZX - хотя бы приблизительную синхронизацию с экраном.
Хорошо, спасибо. Обязательно поизучаю!

[Vitamin]

Даже переключение по таймслайсам для реализации Round-Robin псевдопараллельного исполнения использует интервалы времени, сравнимые или превышающие 1/50с.
ЕМНИП, частота вызова шедулера в том же linux может измеряться килогерцами. Как подсказывает Кэп и опыт, это хорошо сказывается на интерактивности системы, но крайне плохо на общей производительности.

[Alex/AT]

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

Из фактического куда есть смысл смотреть: на ZX нет в целом смысла ждать прерывания для вытеснения потока - основное применение планировщика - распараллеливание действий типа отрисовки экрана, фонового обсчёта данных, обработки клавомыши, etc. А значит нормально подойдёт только кооперативная модель. Во многих демах и игрушках, кстати, можно найти свои суб-планировщики, и основная идея лично у меня была унифицировать подобный механизм так, чтобы практически любую процедуру можно было запихать под планировщик без принципиальных переделок. В том, что получилось - достаточно приблизительно посчитать такты, и расставить вызовы Slice/Idle.

[Barmaley_m]

ЕМНИП, частота вызова шедулера в том же linux может измеряться килогерцами.
Не следует путать частоту вызова планировщика с длительностью time slice. Потоки могут делать сколько угодно системных вызовов, и некоторые из них прямо или косвенно вызывают планировщик и приводят к смене контекста. time slice - это интервал переключения ядром потоков с одинаковым приоритетом в режиме Round-Robin при условии, что эти потоки не делают вызовов ядра, приводящих к перепланировке. Только что погуглил - в линуксе этот интервал составляет 100мс, а в винде - около 20мс, причем в случае винды серверная и клиентская версии используют разные значения. В серверной винде time slice дольше.

Как подсказывает Кэп и опыт, это хорошо сказывается на интерактивности системы,
Интерактивность системы обеспечивается правильным распределением задач по потокам и правильным присвоением их приоритета. Если придерживаться правила иметь более высокий приоритет у потоков, осуществляющих взаимодействие с пользователем - то и получится высокая интерактивность. Помню, у нас в универе была машина на RSX-11 с терминалами. Один комп на 15 студентов. Бывало, человек 10 одновременно запускало компиляцию. Компилировалось жутко медленно, минут по 5 даже для коротких программ. Но при этом редактор у всех работал без задержек. Потому что его приоритет был выше, чем у компилятора.

---------- Post added at 03:34 ---------- Previous post was at 03:26 ----------


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

[Vitamin]

Не следует путать частоту вызова планировщика с длительностью time slice.
Чот попутал, да. Давненько не брал в руки шашек:)
А если не RR алгоритм, то там как?

[Barmaley_m]

А если не RR алгоритм, то там как?
RR-алгоритм применяется только когда в системе имеется несколько потоков с одинаковым приоритетом в состоянии готовности.

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

Вот цитата из MSDN, Windows SDK
"Threads are scheduled to run based on their scheduling priority. Each thread is assigned a scheduling priority. The priority levels range from zero (lowest priority) to 31 (highest priority). Only the zero-page thread can have a priority of zero. (The zero-page thread is a system thread responsible for zeroing any free pages when there are no other threads that need to run.)

The system treats all threads with the same priority as equal. The system assigns time slices in a round-robin fashion to all threads with the highest priority. If none of these threads are ready to run, the system assigns time slices in a round-robin fashion to all threads with the next highest priority. If a higher-priority thread becomes available to run, the system ceases to execute the lower-priority thread (without allowing it to finish using its time slice), and assigns a full time slice to the higher-priority thread. For more information, see Context Switches."

[SfS]

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

Может. Но стандартный системный таймер - 10мс, что как бы 100Гц. Оттуда вызывется планировщик.

Кроме того - он вызывается из системных вызовов. Ну, скажем, вызвал ты select() или блокирующий read() - если данных нет, то управление будет отдано другим задачам-потокам.

"хорошо сказывается на интерактивности системы" то, что для всяких мышек есть аппаратное прерывание.

[Barmaley_m]

Выпустил обновление. Из изменений: небольшая оптимизация при сохранении контекста при прерываниях. Добавлена возможность пуска новых и завершения старых потоков. Для этого используются две новых функции: KeStartThread и KeExitThread.

Перед пуском нового потока необходимо инициализировать в памяти структуру состояния потока, указать адрес стека потока и разместить на его верхушке точку входа. Адрес структуры нового потока передается функции KeStartThread в регистре IY. Новые потоки находятся в состоянии готовности. Функцию KeStartThread можно вызывать только на IRQL=PASSIVE из какого-нибудь потока. При этом, если приоритет нового потока выше, чем у текущего - то текущий поток будет сразу вытеснен, а управление - отдано новому потоку.

Поток может завершиться, вызвав функцию KeExitThread по Call или Jp, эта функция не возвращается. Управление передается следующему по приоритету потоку, находящемуся в состоянии готовности. Последний поток с самым низким приоритетом (system idle thread) не должен завершаться или входить в режим ожидания, иначе происходит сбой.

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

Я не делал любимую многими функцию "TerminateThread" - прибитие одного потока из другого, по той причине, что если прибиваемый поток находится в состоянии ожидания - то его необходимо удалить из списка потоков, ожидающих некий объект. Но поскольку список этот односвязный - то удалить из него элемент невозможно. Надо или хранить в структуре потока указатель на начало списка, или делать двусвязный список. И то, и другое затратно по памяти и по быстродействию операций ожидания и выхода из ожидания, а толку от TerminateThread без защиты памяти мало. Чтобы снять заглючившую задачу, недостаточно прибить поток. Надо еще освободить его ресурсы, а если он перепахал память - то пиши пропало.

Следующий шаг - динамический приоритет потоков. Здесь опять потребуется изменять структуры данных системы. Чтобы изменить приоритет потока, нужно изменить его положение в списке потоков, отсортированном по приоритетам. Во-первых для списков такое перемещение само по себе затратное - O(n), а с односвязным списком вообще все печально. Фактически придется как бы прибить поток и запустить его заново, и это будет очень тормозно. Возможно, вместе с динамическим приоритетом потоков я добавлю возможность иметь потоки с одинаковым приоритетом и Round-Robin. Для этого придется радикально поменять формат "базы данных" диспетчера, сделав его более похожим на то, что используется в Windows NT.

Ну а с динамическим приоритетом станут возможными, наконец, мутексы.

---------- Post added at 04:25 ---------- Previous post was at 04:16 ----------


Может. Но стандартный системный таймер - 10мс, что как бы 100Гц. Оттуда вызывется планировщик.
Планировщик-то вызывается, но потоки не переключаются каждое прерывание. Quantum для Round-Robin может составлять величину, превышающую интервал между прерываниями.

Кроме того - он вызывается из системных вызовов. Ну, скажем, вызвал ты select() или блокирующий read() - если данных нет, то управление будет отдано другим задачам-потокам.
Внутри системы это приводит к вызову WaitForObject. Все это реализовано в моем диспетчере.

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

[CodeMaster]

Вытесняющая многозадачность отличается от кооперативной тем, что решение о смене контекста принимается не задачей, а диспетчером.

А как управление вернётся в диспетчер если задача не стала его отдавать (глюк, проблемы с железом)? Т.е. эта модель работает, до тех пор когда в системе нет проблем.


"Фоновый инициатор вытеснения" - это возможность, но не необходимость.

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

[shurik-ua]

А как управление вернётся в диспетчер если задача не стала его отдавать (глюк, проблемы с железом)?

Вспомнился старый анекдот:
- Пап, а правда что Windows-98 многозадачная ?
- Да, сынок.
- А покажи как это.
- Щас, дискету доформатирую. ))

[Vslav]

Просмотрел тему здесь и на Хабре, и увидел очередное изобретение велосипеда. Ни в коем случае не осуждаю и не высмеиваю топикстартера - сам грешил подобным "велосипедостроением" :), поэтому, надеюсь, мой пост не будет совсем уж бесполезным.
Существуют uC/OS, FreeRTOS, ScmRTOS, TNKernel + еще десятки подобных мелких RTOS (по факту это просто вытесняющие диспетчеры), и они не упоминаются в обсуждениях (по-крайней мере я не увидел), вместо этого имеются ссылки на Windows и ReactOS, которые достаточно сложны и, имхо, не совсем соответствуют микроконтроллерной проблематике. Также существует классическая "библия велосипедостроителей" - Jean J. Labrosse "μC/OS, The Real-Time Kernel" - там очень подробно расписаны все нюансы работы мелких RTOS и ряд интересных проблем типа инверсии приоритетов и способы борьбы с ними.
P.S. Лично мой выбор "велосипеда" c 2006 года - tnkernel.com, открыто, бесплатно, просто, быстро и мощно. Каюсь, в свое время тоже чуток поучаствовал в улучшении этого "велосипеда", теперь там часть кода за моим авторством. Также, весьма вероятно, из озорства, напишу ретро-порт TNKernel для PDP-11 :)

[Barmaley_m]

А как управление вернётся в диспетчер если задача не стала его отдавать (глюк, проблемы с железом)? Т.е. эта модель работает, до тех пор когда в системе нет проблем.
Выше уже рассматривался этот вопрос. Многозадачность и защита от неправильного поведения задач - это разные вещи. На голом Z80 без аппаратных примочек реализовать защиту невозможно. Если же подразумевать, что все задачи работают корректно - то управление вернется в диспетчер ровно тогда, когда нужно.

Это необходимая часть RealTime ОС
Многозадачная ОС и RealTime ОС - это где-то пересекающиеся, но не совпадающие множества. Для RealTime ОС гарантируется время реакции на событие. В моем диспетчере, как и во многих других, в том числе Windows и Linux, это не гарантируется. Так что они не являются RealTime ОС.

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

---------- Post added at 13:42 ---------- Previous post was at 13:34 ----------


Просмотрел тему здесь и на Хабре, и увидел очередное изобретение велосипеда.
Спасибо за обзор альтернатив! В этой теме уже довольно много альтернатив упоминалось, так что она превращается в единое место на форуме, куда сходится информация о реализациях многозадачности на ZX. Это тоже хорошо.

tnkernel.com, открыто, бесплатно, просто, быстро и мощно.
Мой диспетчер тоже открытый, бесплатный и простой. Не скажу, что тормозной - старался оптимизировать. Насчет мощности - планы на реализацию дополнительных важных функций тоже имеются!

---------- Post added at 13:47 ---------- Previous post was at 13:42 ----------


- Щас, дискету доформатирую. ))
Вот этот абсурд стал возможен из-за того, что в Win95/98 драйвер дисковода слишком часто и надолго переводит систему в состояние, когда многозадачность как бы отключена. Ну типа запрет прерываний, долгая работа на IRQL=DISPATCH_LEVEL и т.п. В Windows NT драйвер дисковода был чуть лучше, но все равно там было много таких мест, убивающих многозадачность. Я изучал его исходники. Драйвер параллельного порта был еще хуже. Сканнеры, подключаемые через параллельный порт, блокировали во время работы все задачи даже на Win2000/XP. Когда появился HyperThreading - то он даже рекламировался тем способом, что "ваша система больше не будет виснуть во время работы сканнера". Так как хоть один логический процессор виснет, остается еще второй, на котором система может как-то ковылять.

Дрова этому виной, одним словом.

[Valen]

Лично мой выбор "велосипеда" c 2006 года - tnkernel.com,
А в списке портов там z80 не вижу.
Вы tnkernel именно на z80 юзали ?

[Vslav]

А в списке портов там z80 не вижу.
Вы tnkernel именно на z80 юзали ?
Нет, официального порта под Z80 нет, но основная официальная ветка писалась универсальным образом и существуют рабочие порты под разные 8/16-битные процессоры. То есть, особых препятствий к портированию на Z80 нет. К тому же сегодня посмотрел - у Z80 есть возможность программно получить значение флага разрешения прерываний (копирование во флаг четности при ld A,I) поэтому все нормально. А вот на 580ВМ80 уже пришлось бы извращаться с отдельной внешней переменной.

Сам же использую свою отдельную ветку, специально оптимизированную под 32-битники (там используется особенность что операции чтения и сохранения указателей являются атомарными относительно прерываний ну и еще кучка оптимизаций) под Windows (эмуляция поверх Win32 API), ARM7, ARM9, Cortex-M0/M3/М4 и PowerPC e300.

В-общем, это было бы хорошее и интересное дело - написать порт TNKernel для Z80. Но насколько реально полезное - я не знаю, RTOS дает преимущества при разработке сложного софта - сетевых стеков, стеков USB, файловых систем и прочего. А в 64К адресного пространства это все уже не влезает никак, поэтому целесообразность практического (не для хобби) использования RTOS на 8/16-битниках с моей точки зрения сомнительна. Ну, можно, да. Но нонешние цены на 32-битники вытеснили 8/16-битники совсем уж в нижний сегмент простых проектов. Мои последние мелкие 8-битные проекты на STM8 были без RTOS, только bare hardware.

PS. Под FreeRTOS нагугливается неофициальный порт под Z80, можно и на него посмотреть, принципы те же самые.

[Bolt]

... RTOS дает преимущества при разработке сложного софта - сетевых стеков, стеков USB, файловых систем и прочего. А в 64К адресного пространства это все уже не влезает никак ...
Можете назвать конкретные цифры для нескольких проектов, например "PIC18, прошивка с поддержкой того, сего, и ещё вот этого занимает вот столько килобайт"? Я такое не собирал, мне чтобы ориентироваться.

[vladk]

Просмотрел тему здесь и на Хабре, и увидел очередное изобретение велосипеда.
...
Существуют uC/OS, FreeRTOS, ScmRTOS, TNKernel + еще десятки подобных мелких RTOS
...
Также существует классическая "библия велосипедостроителей" - Jean J. Labrosse "μC/OS, The Real-Time Kernel" - там очень подробно расписаны все нюансы работы мелких RTOS и ряд интересных проблем типа инверсии приоритетов и способы борьбы с ними.
...
P.S. Лично мой выбор "велосипеда" c 2006 года - tnkernel.com, открыто, бесплатно, просто, быстро и мощно. Каюсь, в свое время тоже чуток поучаствовал в улучшении этого "велосипеда", теперь там часть кода за моим авторством. Также, весьма вероятно, из озорства, напишу ретро-порт TNKernel для PDP-11 :)

Вот здесь http://dfrank.bitbucket.org/tneokernel_api/latest/html/why_reimplement.html расписано, почему и как TNKernel глючный.

[Vslav]

Вот здесь http://dfrank.bitbucket.org/tneokernel_api/latest/html/why_reimplement.html расписано, почему и как TNKernel глючный.
Эта тема довольно давно обсуждалась на Электрониксе. Человек просто взял TNKernel, поработал с ним, увидел что можно улучшить для своих целей и написал на его основе бранч, который назвал TNeo. Имхо, у этого товарища замечания, по большей части, к стилистике, хотя, надо признать, есть и пара реальных ошибок/опечаток. Кстати, я в свое время поступил точно так же - взял оригинальный TNKernel и произвел полный рефакторинг (у меня был свой список замечаний, побольше и посерьезней), итоговыми исходниками я с автором поделился, но в основную ветку он внес только часть предложенных мной изменений (их там нормально было предложено - время переключения контекста сократилось в пару раз). Ну и ладно, человек в своем праве, хотя на мой взгляд тут есть некоторый излишний консерватизм, но то такое. А вообще подход у автора достаточно основательный, при разработке RTOS архитектурные решения принимались на основе изучения достаточно серьезных статей (были у нас небольшие дискуссии, по мутексам в частности), так что на мелочи типа сколько операторов return в функции обращать внимания не стоит - это всегда недолго и переписать под свой вкус, лицензия позволяет.