OSDev

для всех
Текущее время: 24 авг 2025, 02:40

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




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

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


Оба содержащихся здесь утверждения неверны. Начну с конца, поскольку там проще :)

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


В моём алгоритме ожидание происходит только в случае, если не были вовремя прочитаны исходные данные или записаны выходные. И в том, и в другом случае многопоточность ровным счётом ничего не даёт, поскольку она также завязана на ввод-вывод: если данные ещё не поступили, то и обрабатывать нечего, а если поступили, но не завершена запись предыдущих результатов, то обрабатывать опять-таки нельзя, поскольку некуда помещать данные.

Цитата:
Думаю, многопоточный мог быть и проще.


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

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

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

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

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

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

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

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

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

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


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

Зарегистрирован: 20 апр 2011, 10:54
Сообщения: 145
phantom-84 писал(а):
418ImATeapot писал(а):
Кстати, рас уж такая тусовка...
Хранить регистры (т. е. Task state) в стеке юзерского потока = BAD IDEA?!!
В стеке ядра прикладного потока = GOOD IDEA!

Это как "в стеке ядра прикладного потока"? Либо ядра либо прикладного!

_________________
Found a CPU. LAPIC ID: 00


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

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1449
418ImATeapot писал(а):
Это как "в стеке ядра прикладного потока"? Либо ядра либо прикладного!


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

Ну а в случае местных осеписателей, думаю, дело в том, что, достаточно хорошо разобравшись с устройством и работой Линуха (что само по себе, естественно, похвально), они решили и у себя делать примерно то же самое. Это вполне естественно; я, например, долго пытался прикостылить идеологию ввода-вывода RSX-11 в свою недосистему на ЕС ЭВМ (советский аналог IBM System/360 и 370), но ничего, кроме костылей, не выходило. Лишь когда я взял на себя труд подробно изучить работу ОС ЕС (которая "в девичестве" OS/360), то у меня всё получилось нормально, хотя в целом моя система была куда ближе к RSX-11 (которая, прямо скажем, намного лучше, чем означенная OS/360, хотя и несколько менее функциональна -- всё ж для мини-ЭВМ была предназначена, а не для мэйнфреймов). Возможно, так и здесь: кругозора банально не хватает (что человек может сейчас изучить на глубоком уровне, кроме Линуха?), вот и используют уже знакомые идеи, хотя они на самом деле крайне неудачны...

Пы.Сы. Просьба никому не обижаться, тут ничего личного :)


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

Зарегистрирован: 20 апр 2011, 10:54
Сообщения: 145
Вот, кстати, виновник трепа (просьба от смеха не помирать и автора сильно не бить!)
Код:
use32

include 'tokamak.inc'


 ;Планировщик
OnTimer:
  pushad    ;сохранить все регистры
  push ds
  push es
  push fs
  push gs

  mov ax,TOKAMAK_SEGMENT_SYSTEM ;настроить сегментные регистры
  mov ds,ax
  mov ax,TOKAMAK_SEGMENT_PROCESS
  mov es,ax

  mov si,[TOKAMAK_CURRENT] ;сохранить SP текущего потока
  mov eax,esp
  mov [es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_ESP],eax

  inc dword [TOKAMAK_SYSTEM_TIME];Настроить время
  jnz .TimeOk
  inc dword [TOKAMAK_SYSTEM_TIME+4]
  .TimeOk:

  ; 1, 2, 3, 4, 5 ...
  mov edi,[TOKAMAK_SYSTEM_TIME];В edi у нас время
  mov si,TOKAMAK_MAX_PROCESS ;В si - номер потока, с которым мы сейчас работаем
  xor cx,cx ; В cx - номер потока с максимальным priority*sleep_time
  xor ebx,ebx ;В ebx - его priority*sleep_time


  .process_find:; Я иду искать!
    mov al,[es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_TYPE]; Спит?
    test al,al
    jnz .next;Нет!

    mov eax,[es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_RUN];Будильник?
    test eax,eax
    jz @f;Нет!
    cmp eax,edi
    jna .next;Спи, спи... Еще время есть.
     mov dword [es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_RUN],0
     mov cx,si
     jmp .found;Вставай, проклятьем заклеймленный!

    @@:
    mov eax,[es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_LAST] ;Ты когда последний раз варенье ел?
    sub eax,edi
    mul byte [es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_PRIORITY];И какой у тебя приоритет?
    cmp eax,ebx
    jna .next ;Не то...
     mov cx,si;Возьмем тебя на заметку!
     mov ebx,eax

  .next:
    dec si
    jnz .process_find ;Всех перебрали!

  .found:  ;Нашел!
    test cx,cx
    jz .halt

    ;Загружаем поток
    mov cx,si
    mov dword [es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_LAST],0
    LLDT [es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_LDT]
    mov ax,[es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_STACK]
    mov ss,ax
    mov eax,[es:si*TOKAMAK_PROCESS_STRUCTURE_SIZE+TOKAMAK_PROCESS_STRUCTURE_ESP]
    mov esp,eax
    pop gs
    pop fs
    pop es
    pop ds
    popad
    iretd

  .halt:;Все спят... Спите, спите... Дети...
    mov ax,TOKAMAK_SEGMENT_STACK
    mov ss,ax
    mov esp,0FFh
    sti
    hlt

Найди 1024 ошибки в 196 байтах!

_________________
Found a CPU. LAPIC ID: 00


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

Зарегистрирован: 20 апр 2011, 10:54
Сообщения: 145
Не надо было мне лезть... Сразу тема заглохла... Я думал мне хоть ткнут носом в упущения... Или это традиция такая - кода на форум (особенно неопробованного) не вывешивать?

_________________
Found a CPU. LAPIC ID: 00


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

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1449
Ну, лично я терпеть не могу ковыряться в чужом коде. Вообще, ИМХО, единственная цель подобных форумов -- подтолкнуть человека в правильном направлении: сказать, что можно почитать, как можно решить проблему альтернативными способами и т.п. Ну а ковыряние в чужом коде -- это как бы выполнение работы за другого :)

Что касается самого кода, то лично я считаю вообще неправильным приводить его вместо словесного описания принятых решений (если, конечно, речь идёт не о тонкостях собственно реализации, например, нестандартного применения какой-то инструкции процессора). Главная причина: неудобочитаемость любого кода по сравнению с нормальным русским, английским и т.п. языком. Сейчас вот, например, я разбираюсь с системной архитектурой ARMv7-M (Cortex-M), так там половина важных вещей дана в виде псевдокода, причём явно быдлокодерского производства (например, для сброса нескольких младших битов используют получение остатка от деления и вычитание вместо логического И). В результате два часа тратишь на то, что при чтении обычного текстового описания становится понятным за пять минут.


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

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1209
418ImATeapot писал(а):
Не надо было мне лезть... Сразу тема заглохла... Я думал мне хоть ткнут носом в упущения... Или это традиция такая - кода на форум (особенно неопробованного) не вывешивать?
Не вывешивать более "семи" строчек кода ))) А если серьезно, со временем надоедает копаться в чужом коде - неблагодарное занятие. Когда я вижу нечто вроде: "Что тут не так... и далее много кода", я обычно отвечаю: "Перефразируйте". Какое-то время назад опять перемалывали нечто подобное. Может, пригодится (только это традиционный вариант - со стеками ядра ;) ).
http://wasm.ru/forum/viewtopic.php?id=41401

SII писал(а):
Что касается самого кода, то лично я считаю вообще неправильным приводить его вместо словесного описания принятых решений (если, конечно, речь идёт не о тонкостях собственно реализации, например, нестандартного применения какой-то инструкции процессора).
+1


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

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 977
Откуда: Дагоба
SII писал(а):
Раньше в Линухе для каждого прикладного потока был не только стек режима пользователя (которым, собственно, поток и пользовался), но и "параллельный" стек режима ядра объёмом 8 Кбайт. Его использовала система, когда обслуживала запросы этого потока. Решение абсолютно идиотское...

Честно говоря, не понимаю, в чём собс-но идиотизм? На мой взгляд - хорошее решение, действительно изолирующее задачу и систему друг от друга.

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

<<< OS Boot Tools. >>>


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

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1449
Лишний расход памяти и кэша без всякой на то реальной нужды: если активно 100 пользовательских потоков, то только на этих стеках впустую улетает 800 килобайт (ну, хорошо, пускай несколько меньше: какая-то небольшая часть каждого стека хранит некую информацию о потоке, которую всё равно придётся где-то хранить, но основная-то часть каждого 8-килобайтного стека не используется вообще либо используется только в тот момент, когда ядро занято обслуживанием запроса этого конкретного потока). К защите же ядра от кода пользовательского режима эти стеки никакого отношения не имеют и не способны её ни улучшить, ни ухудшить.

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


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

Зарегистрирован: 18 апр 2010, 15:59
Сообщения: 155
мне кажется, что каждый поток носит стек ядра, для того чтобы обеспечить реентерабельность. При такой архитектуре, управление может быть передано высокоприоритетному потоку сразу же как только ожидаемый им ресурс будет освобожден. То есть, в не зависимости от того что и в каком режиме, освободивший ресурс поток собирается делать дальше. Архитектура с единым стеком ядра предпологает, что переключение между потоками может проходить только в одной точке.

Итого:
в первом случае присутствет как горизонтальная так и вертикальная реентерабельность
во вотором - только вертикальная.


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

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


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

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


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

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