OSDev

для всех
Текущее время: 22 май 2024, 06:12

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




Начать новую тему Ответить на тему  [ Сообщений: 102 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 11  След.
Автор Сообщение
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 13:26 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1206
SII писал(а):
Если не секрет, откуда вы позаимствовали столь страшные навороты (саму идею)? Или самостоятельная придумка?
Что именно? Если в общем, то естественно Linux, Windows, но стараюсь не копировать, а адаптировать заинтересовавшие меня элементы. До описания реальных наворотов пока дело не дошло. Все, что сказано, это достаточно простые и поверхностные вещи.

418ImATeapot писал(а):
Кстати, рас уж такая тусовка...
Хранить регистры (т. е. Task state) в стеке юзерского потока = BAD IDEA?!!
В стеке ядра прикладного потока = GOOD IDEA!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 13:39 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1418
418ImATeapot писал(а):
Кстати, рас уж такая тусовка...
Хранить регистры (т. е. Task state) в стеке юзерского потока = BAD IDEA?!!


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

Но вот если

phantom-84 писал(а):
В стеке ядра прикладного потока = GOOD IDEA!


то это не плохая, а отвратительная идея, как и сами стеки потоков режима ядра (и как потоки режима ядра тоже, кстати говоря).

phantom-84 писал(а):
Что именно? Если в общем, то естественно Linux, Windows, но стараюсь не копировать, а адаптировать заинтересовавшие меня элементы. До описания реальных наворотов пока дело не дошло. Все, что сказано, это достаточно простые и поверхностные вещи.


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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 14:07 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1206
SII писал(а):
...не плохая, а отвратительная идея, как и сами стеки потоков режима ядра (и как потоки режима ядра тоже, кстати говоря).
Не нравится, озвучь вразумительную альтернативу. Не переключать контекст, пока поток работает в режиме ядра, это не альтернатива, а полное непонимание того, как работают монолитные ядра.

Цитата:
А ввод-вывод, небось, только синхронный? Т.е. если поток пользователя запросил чтение или запись, то до окончания этой операции он "зависает" где-то в недрах системы?
Примерно так. Хочешь асинхронный ввод-вывод, пиши многопоточное приложение и сам занимайся синхронизацией.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 14:37 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1418
phantom-84 писал(а):
SII писал(а):
...не плохая, а отвратительная идея, как и сами стеки потоков режима ядра (и как потоки режима ядра тоже, кстати говоря).
Не нравится, озвучь вразумительную альтернативу. Не переключать контекст, пока поток работает в режиме ядра, это не альтернатива, а полное непонимание того, как работают монолитные ядра.


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

Цитата:
Цитата:
А ввод-вывод, небось, только синхронный? Т.е. если поток пользователя запросил чтение или запись, то до окончания этой операции он "зависает" где-то в недрах системы?
Примерно так. Хочешь асинхронный ввод-вывод, пиши многопоточное приложение и сам занимайся синхронизацией.


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

1) поток запрашивает у ядра запуск операции ввода-вывода;
2) ядро проверяет запрос и ставит его в очередь к устройству;
3) если в данный момент устройство свободно, ядро вызывает драйвер, и тот начинает ввод-вывод (выдаёт соответствующие команды устройству);
4) ядро возобновляет работу потока, возвращая ему код успешного выполнения операции запуска ввода-вывода (но не самой операции ввода-вывода -- она ещё не выполнена);
5) когда операция ввода-вывода выполнена, драйвер и ядро обрабатывают эту ситуацию, устанавливая предусмотренное потоком для этого случая событие и/или выдавая потоку сигнал (в терминах унихоподобных систем; в терминах Винды это будет асинхронный вызов процедуры);
6) если потоку до окончания ввода-вывода делать нечего, он просто обращается к ядру с запросом ожидания наступления события, связанного с этой операцией ввода-вывода.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 16:04 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1206
SII писал(а):
Тоже порочный путь. Ввод-вывод по своей природе является асинхронным, и безусловно правильным была бы иная организация ввода-вывода:

1) поток запрашивает у ядра запуск операции ввода-вывода;
2) ядро проверяет запрос и ставит его в очередь к устройству;
3) если в данный момент устройство свободно, ядро вызывает драйвер, и тот начинает ввод-вывод (выдаёт соответствующие команды устройству);
4) ядро возобновляет работу потока, возвращая ему код успешного выполнения операции запуска ввода-вывода (но не самой операции ввода-вывода -- она ещё не выполнена);
5) когда операция ввода-вывода выполнена, драйвер и ядро обрабатывают эту ситуацию, устанавливая предусмотренное потоком для этого случая событие и/или выдавая потоку сигнал (в терминах унихоподобных систем; в терминах Винды это будет асинхронный вызов процедуры);
6) если потоку до окончания ввода-вывода делать нечего, он просто обращается к ядру с запросом ожидания наступления события, связанного с этой операцией ввода-вывода.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 16:38 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1418
phantom-84 писал(а):
У меня примерно так и происходит, только обычно в недрах драйвера (в функциях виртуальных устройств), а не на более высоком уровне и тем более не в прикладном коде: драйвер делает запрос на фиксацию сигнала, потом посылает команду физическому устройству и, возможно, делает какую-то дополнительную работу, после чего уходит на ожидание; если сигнал к этому моменту уже успел прийти, то возобновляет выполнение немедленно. Вполне даже синхронный механизм, только низкоуровневый.


Так в том-то и дело, что ввод-вывод должен быть асинхронным, причём и на прикладном уровне. Из асинхронного ввода-вывода синхронный делается элементарно (как я описал выше: поток просто связывает с операцией ввода-вывода некое событие и после запуска операции ввода-вывода переходит в ожидание этого события), а вот из синхронного сделать асинхронный невозможно в принципе. Конечно, процессор при этом может не простаивать, но для этого нужно создавать дополнительные потоки и т.д. и т.п., то есть излише усложнять уже не только систему (которая вынуждена заниматься принудительной "синхронизацией" операций), но ещё и прикладную задачу (которая не может по-человечески воспользоваться природной асинхронностью ввода-вывода из-за того, что ОС ей навязывает исключительно синхронную модель). В общем, это как раз тот случай, когда выбрасывание части кода из ОС не только упростит саму систему, но и упростит жизнь прикладным программам.

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


Не понял, что за проблема и какие такие "фазы"? Если можно, поподробнее.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 17:27 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1206
SII писал(а):
Так в том-то и дело, что ввод-вывод должен быть асинхронным, причём и на прикладном уровне. Из асинхронного ввода-вывода синхронный делается элементарно (как я описал выше: поток просто связывает с операцией ввода-вывода некое событие и после запуска операции ввода-вывода переходит в ожидание этого события), а вот из синхронного сделать асинхронный невозможно в принципе. Конечно, процессор при этом может не простаивать, но для этого нужно создавать дополнительные потоки и т.д. и т.п., то есть излише усложнять уже не только систему (которая вынуждена заниматься принудительной "синхронизацией" операций), но ещё и прикладную задачу (которая не может по-человечески воспользоваться природной асинхронностью ввода-вывода из-за того, что ОС ей навязывает исключительно синхронную модель). В общем, это как раз тот случай, когда выбрасывание части кода из ОС не только упростит саму систему, но и упростит жизнь прикладным программам.
Мне кажется, что асинхронный ввод-вывод сам по себе сложнее (требует гораздо большей усидчивости при написании программ), в добавок приложениям потребуется самостоятельно выполнять синхронизацию, когда это необходимо (а это необходимо практически всегда). Короче сложно. Может, опишешь модель работы приложения, использующего асинхронный ввод-вывод, в сравнении, скажем, с двухпоточным приложением, где один поток занимается файловыми операциями, а другой консольными операциями.

Цитата:
Не понял, что за проблема и какие такие "фазы"? Если можно, поподробнее.
Ну например функцию чтения сектора можно разделить на две функции в соответствии с фазами данной операции - подачей команды на чтение и приемом результатов.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 18:07 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1418
phantom-84 писал(а):
Мне кажется, что асинхронный ввод-вывод сам по себе сложнее (требует гораздо большей усидчивости при написании программ), в добавок приложениям потребуется самостоятельно выполнять синхронизацию, когда это необходимо (а это необходимо практически всегда). Короче сложно.


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

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

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

В результате поток сразу после запуска ввода-вывода "засыпает" до тех пор, пока ввод-вывод не будет завершён, т.е. для него эта операция ввода-вывода выполняется синхронно.

Более того, вместо двух вызовов системы можно сделать объединённый вызов, который сначала запускает ввод-вывод, а затем сразу же переводит поток в ожидание события, связанного с завершением ввода-вывода. Так сделано, например, в RSX-11 и VAX/VMS, где имеется два практически одинаковых системных сервиса QIO$ и QIOW$ с полностью идентичным набором параметров. Разница только в том, что QIOW$ сразу переведёт задачу (в тамошней терминологии) в ожидание завершения ввода-вывода, ну а QIO$ позволит ей работать дальше одновременно с выполнением ввода-вывода и "затормозить" только тогда, когда это реально необходимо, применив один из сервисов ожидания.

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

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


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

Цитата:
Ну например функцию чтения сектора можно разделить на две функции в соответствии с фазами данной операции - подачей команды на чтение и приемом результатов.


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

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

Собственно, именно так и работает система ввода-вывода в Винде, поскольку она туда перекочевала из VAX/VMS, куда, свою очередь, попала из RSX-11. Правда, с каждым "перебазированием" этот механизм всё раздувался, усложнялся и дополнялся, причём не всегда обоснованно ("хотели как лучше..."), но всё равно сам по себе остался быстрым и эффективным, намного превосходя любые унихи (собсно, одна из причин катастрофического отставания унихов по производительности от RSX-11 и VAX/VMS крылась именно в переусложнённом ядре с синхронным вводом-выводом, хотя, конечно, свою лепту внесли и другие причины -- использование Си вместо ассемблера, например). Другое дело, что Винда была сильно "усовершенствована" в других моментах, из-за чего в целом превратилась в неповоротливого монстра, но к идеологии ввода-вывода это прямого отношения не имеет...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 18:30 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1418
А вот, кстати, пришёл в голову такой пример.

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

Простейшее решение, базирующееся на синхронном вводе-выводе, выглядит следующим образом:

1. Считывается порция входного файла.
2. Считанное обрабатывается.
3. Обработанное записывается.
4. Если входной файл не закончился, то идём на п. 1.

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

Теперь альтернативное решение, базирующееся на асинхронном вводе-выводе.

1. Выделяется два или большее число буферов входных буферов и некоторое число выходных буферов. Для простоты предположим, что их всего по 2. Изначально все буферы пусты и свободны.
2. Запускается асинхронная операция считывания входного файла в первый буфер.
3. Запускается асинхронная операция считывания входного файла во второй буфер. Реальное её выполнение начнётся лишь после окончания первой операции, поскольку ввод-вывод сам по себе осуществляется последовательно.
4. Поток дожидается завершения операции считывания в первый входной буфер.
5. Поток поверяет, свободен ли первый выходной буфер. Если нет, он переходит в ожидание операции записи из первого выходного буфера. При первом проходе по циклу буфер будет, естественно, свободен.
6. Поток обрабатывает данные, считанные в первый входной буфер, и помещает результат в первый выходной буфер.
7. Поток запускает асинхронную операцию записи из первого выходного буфера. Буфер будет оставаться занятым до тех пор, пока запись не окончится.
8. Поток запускает асинхронную операцию считывания в первый входной буфер, если файл ещё не кончился. Если кончился, то здесь он уже ничего не делает.
9. Поток ожидает завершения операции считывания во второй входной буфер.
10. Поток поверяет, свободен ли второй выходной буфер. Если нет, он переходит в ожидание операции записи из второго выходного буфера. При первом проходе по циклу буфер будет, естественно, свободен.
11. Поток обрабатывает данные, считанные во второй входной буфер, и помещает результат во второй выходной буфер.
12. Поток запускает асинхронную операцию записи из второго выходного буфера.
13. Поток запускает асинхронную операцию считывания во второй входной буфер, если файл ещё не кончился. Если кончился -- ничего не делает.
14. Если файл ещё не кончился, поток переходит на п. 4.
15. Поскольку файл кончился, поток ожидает завершения асинхронной записи из обоих выходных буферов и завершает работу.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 11 июл 2011, 19:10 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1206
К предпоследнему посту...

У меня такое ощущение, что ты описываешь нечто похожее на механизм сообщений Linux/Windows. У меня подобным образом работает консольная подсистема. При вводе используются системные вызовы GetEvent и WaitEvent. Первый проверяет наличие пакетов в событийной очереди и если их нет, то сразу выполняет возврат. Второй уходит на ожидание, если очередь пуста. К сожалению так работает только консольная подсистема, но не файловая. Там, где присутствует "активная фаза" команды (подача команды), приложение практически всегда должно дождаться завершения этой команды.

К последнему посту...

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 102 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 11  След.

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


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

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


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

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