[SyncLair 0]

хочу попробовать силы в написании небольшой ОС для микроконтроллеров, ну или хотя бы разобраться в том как они написаны

 

Во-первых есть некоторые вещи которые у меня не вызывают вопросов и сомнений:

1. ОС должна быть вытесняющей и реального времени (иначе неинтересно )

2. в ОС присутствуют потоки-задачи которые она перемешает из одного

списка в другой (блокированные-готовые), списки сделаны как двухсвязные списки

упорядоченные по приоритету.

3. В ОС помимо простых delay() есть примитивы синхронизации они же средства межпроцесного взаимодействия

 

Вот по поводу третьего пункта хотелось бы порассуждать, услышать Ваши мнения!

 

Их(средств) очень много типов: семафоры, двоичные семафоры, мьютексы, барьеры, очереди, какие-то mailbox-ы, условные переменные.

 

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

 

Вопрос состоит вот в чём!: Какой базовый примитив синхронизации может быть положен в основу реализации ну пусть семафоров, мьютексов и очередей?

Или какая базовая(ые) функция(и) нужны для того, чтобы реализовать функциональность всех этих примитивов????

 

Вот мои предварительные размышлизмы:

 

FreeRTOS:

изначально ориентирована на передачу сообщений, то есть потоки общаются только путём передачи асинхронных сообщений через буферы

однако после того как народ активно стал просить семафоры Ричард таки сделал семафор(N), как очередь из N элементов каждый размером в 0 байт,

а затем отдельно прописал реализацию мьютексов.

 

На лицо элегантное решение -- базовый примитив синхронизации в данном случае очередь сообщений!

 

есть у данного решения один минус -- память, если у меня куча двоичных семафоров что защищают ресурсы, то в простейшей реализации двоичный семафор это двухсвязный список + счётчик а во freeRTOS намешана ещё куча всего. В итоге ресурсов может быть много, но заранее не известно будет ли к ним доступ из нескольких потоков. Например UART-ом может пользоваться лишь одна задача. И поэтому ставить заранее на каждый общий ресурс большую структуру очереди freeRTOS не выгодно -- много ОЗУ кушается зря (второй список потоков, указатель на буфер и т. д.).

 

Связи с данными выкладками по RAM хочется спросить! А может в некоторых малых ОС за базовый примитив синхронизации выбран семафор?

 

minix:

тоже как и freeRTOS ориентирована на передачу сообщений, но не через очередь, а от процесса к процессу! и не асинхронно а синхронно!

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

буфер для того, же UART-а, городить отдельный поток который ``заведует'' буфером?

 

windows:

все объекты синхронизации при создании получают handle, а дальше используется waitforsingleobject или waitformultipleobjects, значит переводя на язык OOП -- есть базовый класс(базовая функция) от которого ``унаследованы'' все типы семафоров файлов и прочее -- хотелось бы увидеть этот класс и исходники на него, но этож мелкомягкие, правда есть reactOS, может кто подскажет где смотреть исходники на предмет реализации в ядре вот этих функций (а может это реализовано в бибилотеке? в UserSpace)

-- есть ещё пару НО! -- 1)ясно что при создании объекта происходит регистрация ресурса в ядре, что сразу даёт malloc и лишнюю косвенность, что для маленьких МК без MMU не очень хорошо, накладные расходы на один двоичный семафор наверно велики

2) windows вообще не РТОС и рядом со встраиваемыми системами не стояла (по миниатюрности и реалтизму)

 

linux:

насколько понимаю есть таблица сист вызовов и всё примерно тоже самое как и в windows

 

uOS:

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

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

 

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

 

chibiosRT и некоторые другие ОS:

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

 

P S: Надеюсь тут не будет холиваров по поводу операционных систем.

[_Pasha 0]

есть у данного решения один минус -- память, если у меня куча двоичных семафоров что защищают ресурсы, то в простейшей реализации двоичный семафор это двухсвязный список + счётчик а во freeRTOS намешана ещё куча всего. В итоге ресурсов может быть много, но заранее не известно будет ли к ним доступ из нескольких потоков. Например UART-ом может пользоваться лишь одна задача. И поэтому ставить заранее на каждый общий ресурс большую структуру очереди freeRTOS не выгодно -- много ОЗУ кушается зря (второй список потоков, указатель на буфер и т. д.).

А зачем, простите, защищать ресурсы осевыми средствами, если все признаки для определения занят/свободен уже есть в железе? Это во-первых.

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

 

[_Pasha 0]

есть у данного решения один минус -- память, если у меня куча двоичных семафоров что защищают ресурсы, то в простейшей реализации двоичный семафор это двухсвязный список + счётчик а во freeRTOS намешана ещё куча всего. В итоге ресурсов может быть много, но заранее не известно будет ли к ним доступ из нескольких потоков. Например UART-ом может пользоваться лишь одна задача. И поэтому ставить заранее на каждый общий ресурс большую структуру очереди freeRTOS не выгодно -- много ОЗУ кушается зря (второй список потоков, указатель на буфер и т. д.).

А зачем, простите, защищать ресурсы осевыми средствами, если все признаки для определения занят/свободен уже есть в железе? Это во-первых.

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

 

[SyncLair 0]

А зачем, простите, защищать ресурсы осевыми средствами, если все признаки для определения занят/свободен уже есть в железе? Это во-первых.

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

Сегодня эти десять.. сто переменных модифицирует один поток а завтра четыре. Сто семафоров на каждую не напасёшся.

 

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

Нууу в большинстве ОСей, что я видел используются именно двухсвязные списки чтобы перемешать задачу из списка блокированных в список готовых и наоборот. Если вы мне скажите как 10 задач-потоков, которые где-то в 100 файлах проекта половину которых я в глаза не видел объединить в один массив стандартными или полустандартными средствами, так чтобы это в нескольких компиляторах работало -- я буду очень рад :08: .

[_Pasha 0]

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

Сегодня эти десять.. сто переменных модифицирует один поток а завтра четыре. Сто семафоров на каждую не напасёшся.

 

 

Нууу в большинстве ОСей, что я видел используются именно двухсвязные списки чтобы перемешать задачу из списка блокированных в список готовых и наоборот. Если вы мне скажите как 10 задач-потоков, которые где-то в 100 файлах проекта половину которых я в глаза не видел объединить в один массив стандартными или полустандартными средствами, так чтобы это в нескольких компиляторах работало -- я буду очень рад :08: .

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

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

1.2. Много "слушателей" - это широковещательная передача, не требующая модели producer/consumer и синхронизации. РЕшается поллингом внутри потока. Т.е. у очереди есть один указатель на запись и много локальных указателей чтения. Такая вот очередь... И просыпаются они все разом.

1.3. Ваш вариант :)

 

2. Массивы указателей и массивы индексов для списков. Если копнуть всякие фокусы с операциями в поле Галуа, можно соорудить генератор, быстро выдающий нужный индекс. Но это так, пофантазировать.

Изменено 9 января, 2012 пользователем _Pasha

[Terminator 0]

А зачем, простите, защищать ресурсы осевыми средствами, если все признаки для определения занят/свободен уже есть в железе?

И ждать освобождения поллингом, да?

 

[DevL 0]

как то все перемешано, и теория и расписания по операционкам:

 

>примитивы синхронизации они же средства межпроцесного взаимодействия

не всегда и не везде

или имелось в виду: inter-process or task synchronization

 

>базовый примитив синхронизации в данном случае очередь сообщений!

тяжело назвать это базовым примитивом,

скорее просто - реализованно в виде очереди...

 

по большому счету, рекомендую сделать следующее , если убер-цель: написании небольшой ОС для микроконтроллеров

- посмотреть по сторонам и исходникам того что доступно и важно понять ( OS + разные frameworks , типа Intel TBB etc )

- набраться общей теории И правильной терминологии

- забыть за подход от общего к частному

- начинать писать свое, ориентируясь только на важные и главное - практичные случаи

- думать о том - что со временем много еще поменяется и перепишится, но всегда будет ведомым и от необходимости...

 

Тот же MS регулятно меняет и добавлят новые вещи в теме синхронизации и они ведомые...

[kikos 0]

А зачем, простите, защищать ресурсы осевыми средствами, если все признаки для определения занят/свободен уже есть в железе? Это во-первых.

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

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