OSDev

для всех
Текущее время: 15 дек 2018, 07:36

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
СообщениеДобавлено: 05 ноя 2018, 16:19 

Зарегистрирован: 05 ноя 2018, 14:34
Сообщения: 3
Добрый день.
В книгах по устройству операционных систем больше освещаются теоретические вопросы, много различных абстракций
скрывающих реализацию на нижнем уровне, даже если все понятно в теории, то приступая к написанию кода встает много вопросов как это правильно и эффективно реализовать

давно уже во мне тлело желание написать небольшую операционную систему, использую ассемблер, выбор пал на микроконтроллер с ядром cortex m4

под ядро операционной системы я выделил участок ОЗУ объемом в 64 Кбайта.

Предположим ОС будет многозадачной, вытесняющая многозадачность. задачам назначаются приоритеты из диапазона 0-32. Сначала была мысль создать 32 статических массива под задачи в состоянии готовности, и 32 массива под блокированные задачи. 1 массив состоит из 32 8байтных элементов, итого 256 байт на 1 очередь с определенным приоритетом, 256 х 32 очереди = 8 Кбайт на 1 структуру, а структур две, активных и блокированных задач.
Итого 16 Кбайт. а под ядро отведено всего 64 Кбайта.

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

Возникает вопрос как были организованы операционные системы 70-80х годов с ограниченными ресурсами
Динамически выделяли память?
или как это устроено например во FreeRTOS, у нее если не изменяет память 256 приоритетов

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

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

как же выделялась память внутри операционных систем 70-80х годов с ограниченными ресурсами, какие там были алгоритмы
вопросы видимо идиотские для большинства, но хотелось бы разобраться.
заранее спасибо


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 05 ноя 2018, 19:41 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1357
Откуда: Зеленоград
Цитата:
Возникает вопрос как были организованы операционные системы 70-80х годов с ограниченными ресурсами
Динамически выделяли память?


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

Алгоритмы были более чем традиционные -- как, в общем-то, и сейчас. Все фундаментальные вещи изобрели в 50-60, маскимум -- 70-х годах, и в плане системного программирования с тех пор ничего сколько-нибудь принципиально не изменилось (понятно, что в последующие времена появилась куча новых вещей типа шифрования или там обработки видео, но к ядрам осей это отношения не имеет). Так что, если Вирта читали и поняли, этого вполне достаточно.

А почему, кстати, так жёстко себя в памяти ограничиваете? У процов с этим ядром обычно куча флэша (вплоть до нескольких мегабайт), да и встроенного ОЗУ прилично (плюс часто внешнее имеется).

И, кстати говоря, компактность древних осей объяснялась отчасти ещё и тем, что системы команд были получше. Хотя главное, конечно, -- разумное ограничение функционала плюс довольно качественное ручное кодирование на ассемблере. Но временами и извращаться приходилось. Например, OS/360, скоммунизженная у нас как ОС ЕС (первая "большая" ОС в истории, кстати) занимала в сумме... ну, может, пару мегабайт, если говорить по чисто системные компоненты, однако благополучно работала на машинах с объёмом памяти от 128 килобайт и выше. Для этого её ядро было весьма небольшим, и большая часть тяжеловесных или не шибко часто используемых вещей грузилась с диска по мере необходимости. Работало всё жутко медленно и печально, но работало ж (а если памяти было много -- скажем, пара мегабайт, то изрядную часть модулей ОС можно было прописать для загрузки как резидентных, что самым благотворным образом сказывалось на её производительности).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 06 ноя 2018, 14:41 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 949
Откуда: Дагоба
SLD писал(а):
Сначала была мысль создать 32 статических массива под задачи в состоянии готовности, и 32 массива под блокированные задачи. 1 массив состоит из 32 8байтных элементов, итого 256 байт на 1 очередь с определенным приоритетом...

Зачем заводить 32 разных массива, когда можно обойтись двумя (или даже одним) связным списком?
Если у вас не система жёсткого реального времени, то без динамического выделения памяти не обойтись. В этом случае у вас глобально есть две альтернативы: либо выделять память целыми страницами, либо писать полноценный аллокатор, который может выделить кусок памяти произвольного размера. Правда надо отметить, что выделение страниц вам в любом случае понадобится по двум причинам. Во-первых, выделение страниц лежит в основе любого другого аллокатора, поскольку виртуальную память и защиту доступа можно организовать только на уровне страниц. Во-вторых, приложения также потребуют динамически выделяемую им память и приложениям она отдаётся постранично (аллокатор приложения реализуется в виде рантайм-библиотек самого приложения).
Полноценный аллокатор, очевидно, имеет бОльшие накладные расходы по сравнению со страничным, поэтому в ядре желательно обходится без него, там, где есть такая возможность. Например, в ядре ОС Линукс часто используется тайловое (tile - плитка, черепица) выделение, суть которого состоит в том, что под объекты одного рода выделяется целая страница, которая делится на равные части и имеет битмап свободных элементов. Сходный механизм вы можете использовать и для очереди задач.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 06 ноя 2018, 15:48 

Зарегистрирован: 05 ноя 2018, 14:34
Сообщения: 3
SII писал(а):

А почему, кстати, так жёстко себя в памяти ограничиваете? У процов с этим ядром обычно куча флэша (вплоть до нескольких мегабайт), да и встроенного ОЗУ прилично (плюс часто внешнее имеется).


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

Yoda писал(а):
Зачем заводить 32 разных массива, когда можно обойтись двумя (или даже одним) связным списком?


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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 06 ноя 2018, 16:19 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1357
Откуда: Зеленоград
SLD писал(а):
Да, нет, особо себя не ограничиваю, просто хочется сделать по уму, на сколько хватит понимания предмета, чтобы ядро работало быстро и занимало объем небольшой. Знаний не достаточно, пока, или в некоторых вещах не ясно какую стратегию предпочесть


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

Что же касается небольшого объёма, то, как я уже говорил, это сильно зависит от целевого железа. Архитектура ARM, хотя далеко ушла от того, что было "настоящим" RISC, сохранила главный недостаток любой RISC-архитектуры -- выполнение операций только и исключительно в регистрах процессора, из-за чего постоянно требуется выполнять загрузку-сохранение. Ну а в системном программировании редко когда требуется проводить длинные вычисления, где большинство операндов лежит в регистрах и доступы к памяти выполняются относительно нечасто, поэтому код оси на ARMе будет... ну, наполовину, наверное состоять из команд загрузки и сохранения -- что, понятно, не добавляет ему компактности. Противоположным примером являются старые архитектуры PDP-11 и VAX-11 (16- и 32-разрядные мини-машины, жутко популярные в своё время и скопированные у нас под вывеской СМ ЭВМ): там почти все операции можно выполнять вообще без использования регистров. Нужно тебе, скажем, увеличить счётчик использования некоего управляющего блока -- в PDP/VAX это одна команда, а в ARM -- целых три. Так что особо за объёмом не гонитесь :)

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

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


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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 09 ноя 2018, 07:45 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1092
В ограниченных ресурсах жили с ограниченными алгоритмами. Для примера в DOS можно было открыть не более 40 файлов одновременно. Задача была 1.
Что касается процессов. То у юникса 1.0 как и у доса задача была ограничена в размерах.
У первого юнекса под задачу отводилось 8 кб. В dos 64 кб. Механизма страничной защиты небыло в процах.
Юникс для расширения колличество процессов использовал дисковую память.
Процессы динамически создавались. Хотя ему это и ненужно было так как количество одновременно работающих процессов не превышала 10 до 90-тых годов.
Приоритетов в юниксе небыло. Так как универсальный планировщик был изобретён только 80 тых годах.
Был только три состояния ожидание, перекур и работа. Вместо планирования было понятие рандеву(свидания).

А вот память умели выделялась динамически. Но из-за ограниченности ресурсов обычно использовали статическое распределение. Во вторых алгоритмы динамического выделения памяти были не оптимальными. Heap allocator был изобретён в 70-тых годах.

Использовали буферы да массивы. Списки не использовали, вернее использовали, но крайне редко.

Изоляции избегали ресурсы были общими, виртуализации был минимум.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 09 ноя 2018, 12:04 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1357
Откуда: Зеленоград
pavia писал(а):
В ограниченных ресурсах жили с ограниченными алгоритмами. Для примера в DOS можно было открыть не более 40 файлов одновременно. Задача была 1.


MS DOS -- пример не шибко удачный, ибо накладывает миллион ограничений там, где системы, работавшие на ещё более ограниченных ресурсах, таких ограничений не имели. Тот же MS DOS, даже имея 640 Кбайт оперативной памяти и изрядную часть поддержки ввода-вывода в BIOS, лежащем в ПЗУ (т.е. не расходуя на это ОЗУ), был однозадачной системой с крайне ограниченным функционалом. Уже упоминавшаяся мной OS/360 или, например, RSX-11M были многозадачными системами, причём поддерживали многозадачность и всё из этого вытекающее даже на 128 Кбайтах ОЗУ (RSX-11M в полном варианте вообще 96 Кбайт хватало, а в максимально кастрированном -- 32 Кбайт, хотя уже не всякая задача могла работатать -- Фортрану хватало, например, ну а компилятор Паскаля или Кобола не лез).

Цитата:
Что касается процессов. То у юникса 1.0 как и у доса задача была ограничена в размерах.


В MS DOS ограничения как такового не было -- можно было использовать всю память, кроме занятой под саму ДОС. Что до ранних Юниксов, то ограниченность объяснялась железом: адресное пространство не более 64 Кбайт. Хотя RSX-11M, работающая на том же самом железе (PDP-11), позволяла создавать задачи, имеющие большее адресное пространство -- хотя в любой конкретный момент времени задача могла адресовать лишь 64 Кбайта.

Цитата:
Механизма страничной защиты небыло в процах.


Не было в 8086/8088. Но был (вместе с поддержкой виртуальной памяти) во многих PDP-11; защита была практически во всех мэйнфреймах, хотя виртуальная память появилась позже, в районе 1970 года (вместе с Системой 370, хотя впервые она появилась несколько раньше на паре моделей, формально относившихся к Системе 360).

Цитата:
Юникс для расширения колличество процессов использовал дисковую память.


Все системы с виртуальной памятью этим могут пользоваться. И многие без неё (например, RSX-11M для системы без т.н. диспетчера памяти -- т.е. MMU, или OS/360 в режиме MVT с поддержкой свёртки-развёртки).

Цитата:
Процессы динамически создавались. Хотя ему это и ненужно было так как количество одновременно работающих процессов не превышала 10 до 90-тых годов.


Как в Юниксе -- не знаю. В OS/360 MFT и MVT (т.е. в системах без виртуальной памяти) число, выражаясь современным языком, процессов пользователя было ограничено 15-ю (это аппаратное ограничение, связанное с механизмом защиты памяти), однако одновременно могло выполняться до нескольких десятков системных процессов (главный планировщик, задачи системного ввода и вывода, ещё что-то там). Кроме того, каждый процесс мог иметь несколько потоков (ограничивалось больше объёмом памяти под управляющие блоки, сама ОС ограничивала, если память не изменяет, 255 потоками на процесс).

Цитата:
Приоритетов в юниксе небыло. Так как универсальный планировщик был изобретён только 80 тых годах.


В IBM этого не знали, поэтому в OS/360 MVT (ещё 1960-е годы) приоритеты уже были.

Цитата:
Был только три состояния ожидание, перекур и работа. Вместо планирования было понятие рандеву(свидания).


То же самое.

Цитата:
А вот память умели выделялась динамически. Но из-за ограниченности ресурсов обычно использовали статическое распределение. Во вторых алгоритмы динамического выделения памяти были не оптимальными. Heap allocator был изобретён в 70-тых годах.


То же самое.

Цитата:
Использовали буферы да массивы. Списки не использовали, вернее использовали, но крайне редко.


То же самое. Внутренние структуры данных ядра OS/360 -- сплошь списки (очереди), даже область динамической памяти называлась областью системных очередей (SQA).

Цитата:
Изоляции избегали ресурсы были общими, виртуализации был минимум.


Первая система виртуальных машин -- VM/370, работавшая на Системе 370 и доступная как коммерческий продукт с 1970 года. До сих пор IBM по виртуализации так никто и не превзошёл (VM/370 плавно эволюционировала в современную z/VM, работающую на мэйнфреймах z/Architecture -- дальних потомках Системы 360).

В общем, "всё украдено изобретено до нас".


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 10 ноя 2018, 01:54 

Зарегистрирован: 05 ноя 2018, 14:34
Сообщения: 3
Все эти подробности о операционных системах 30-40 летней давности весьма интересны для меня.

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

пишу аллокатор на основе алгоритма из этой книги. тема эта зацепила

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

фиксированными блоками не хочется память выделять


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 10 ноя 2018, 10:47 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1357
Откуда: Зеленоград
Изображение

Фотка трёх сохранившихся у меня книжек по осям.

1. П. Кейлингерт. "Элементы операционных систем". // М., "Мир", 1985; буржуйский оригинал вышел в 1982. Предназначена не для программистов, а для тогдашних пользователей, поэтому глубин осей не касаются, но достаточно хорошо расписывают, как тогдашние оси работали на верхнем уровне (например, как OS/360 управляла памятью, выделяемой для разделов задач, и т.п.), какие проблемы могут возникать и т.д. В общем, взгляд "стратегический" и иногда "оперативный", но не "тактический". С современной точки зрения -- неплохое введение для тех, кто вообще с осями не знаком или только начинает знакомиться (включая программистов-прикладников; реальная квалификация тогдашних пользователей была зачастую выше, чем нынешних программистов).

2. У. Девис. "Операционные системы". // М., "Мир", 1980; буржуйский оригинал вышел в 1977 г. Более подробная книга, где освещены по верхам аппаратные средства, на которые опирается работа осей (в частности, работа MMU) и приведена "стратегическая" и "оперативная" информация по работе осей -- главным образом DOS/360 и OS/360. Опять-таки нет "тактического" уровня, т.е. конкретных низкоуровневых алгоритмов здесь не увидишь, но для тех, кто использовал означенные оси, сия книжка в изрядной степени заменяет документацию, если человек хочет разобраться, как система работает

3. С. Кейслер. "Проектирование операционных систем для малых ЭВМ". // М., "Мир", 1986; буржуйский оригинал -- 1983 г. Вот здесь уже полно "тактики" с примерами алголо-(или, если угодно, паскале-)-подобного псевдокода. Наш редактор перевода там упомниает Unix -- но в ругательном смысле: "Были попытки представить операционную систему UNIX в качестве такой стандартной операционной системы для всех ЭВМ, но они не увенчались успехом в основном из-за очень больших накладных расходов, присущих этой системе" (попросту говоря, там, где штатные оси летали, Unix еле шевелился -- при этом пожирая дофига памяти).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 12 ноя 2018, 09:34 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1092
Аллокатор описан у Кнута.
4.2 глава Д.В. Иртегов Введение в операционные системы. 2-е издание (2008)
9 глава у Бах Морис-Архитектура операционной системы UNIX-Prentice-Hall (1996)
8 глава Вирт Н., Гуткнехт Ю.-Разработка операционной системы и компилятора. Проект Оберон-ДМК Пресс (2012)

За идеями лучше всего. в Бар Р., Багатурова У.С. (пер.)-Язык Ада в проектировании систем (1988)
И в качестве беллетристики А.С.Деревянко, М.Н.Солощук Операционные системы (2002)

Знаю что следующий вопрос будет про на обработку процессов. Боюсь ссылка затеряется:
https://habr.com/post/267573/


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB