Линейщина -> Параллельщина

Я хочу внутри неё сделать треды, т.е. сделать так, чтобы внутри неё было несколько потоков выполнения, которые выполняются по очереди.

по очереди

Боюсь даже представить, зачем. Ну да ладно.

Варианты на погуглить:

• OpenMP
• pthreads
• Boost threads

http://www.threadingbuildingblocks.org/

Intel® Threading Building Blocks (Intel TBB) offers a rich and complete approach to expressing parallelism in a C++ program. It is a library that helps you take advantage of multi-core processor performance without having to be a threading expert. Intel TBB is not just a threads-replacement library. It represents a higher-level, task-based parallelism that abstracts platform details and threading mechanisms for scalability and performance.

>по очереди
что тебя удивило? синхроназация так и происходит

> Боюсь даже представить, зачем. Ну да ладно.

Исключительно для удовлетворения любопытства.

Ну а точнее? Плясать надо от конкретной задачи, некоторые алгоритмы параллелятся влёгкую, некоторые — вообще не.

Читай — QNX/UNIX: Анатомия параллелизма.

Книжка тонкая, про pthreads. На QNX в названии не обращай внимания, просто несколько частей про риалтайм идет.

> > по очереди

что тебя удивило? синхроназация так и происходит

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

Всё верно?

Вас интересует алгоритмическая сторона вопроса (какие алгоритмы распараллеливаются, как их разделять и пр.) или практическая (программирование)? Если практическая, то какой язык программирования, есть ли ограничения по используемым библиотекам/средствам и пр.?

> Ну а точнее? Плясать надо от конкретной задачи, некоторые алгоритмы параллелятся влёгкую, некоторые — вообще не.

При чём здесь алгоритмы? Я хочу треды.

Если абстрактные треды в вакууме, то google: posix threads

> Вас интересует алгоритмическая сторона вопроса (какие алгоритмы распараллеливаются, как их разделять и пр.) или практическая (программирование)?

Нет, меня интересует именно реализация.

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

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

например, джабо-машине все равно сколько ядер, поочередно

> Читай — QNX/UNIX: Анатомия параллелизма.

Спасибо, гуглю.

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

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

Мммм... можно гуглить qnx microkernel на предмет архитектуры ядра. И читать её исходники, они вроде как открыты. Как совсем извращенный вариант, можно почитать что-нибудь по архитектуре NT и покурить исходники ReactOS.

Можно глянуть сорцы микроядра HelenOS. Очень грамотная «академическая» реализация и переносимость на чертову уйму платформ - такой код заслуживает изучения.

Самое простое:
Обработчик сигналов может получать контекст прерванного процесса. Дальше есть setcontext, swapcontext и др. Сделаешь свою псевдомногопоточность

>Я хочу внутри неё сделать треды

Лучше курни и сделай дреды

что тебя удивило?

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

да он что-то странное хочет вообще

> Обработчик сигналов может получать контекст прерванного процесса. Дальше есть setcontext, swapcontext и др. Сделаешь свою псевдомногопоточность.

Можно подробнее?

Какой обработчик сигналов?

>я хочу сделать свои threads

Вы разрабатываете ядро ОС, хотите сделать некое подобие тредов в userspace или просто хотите научиться писать многопоточные приложения?

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

возможно товарищ не так выразился

> Вы разрабатываете ядро ОС, хотите сделать некое подобие тредов в userspace или просто хотите научиться писать многопоточные приложения?

подобие тредов в userspace

Вот оно.

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

Не должны. Я просто не вижу другого варианта.

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

Тоже интересно, но это сложнее. Поэтому позже.

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

Не должны. Я просто не вижу другого варианта.

Вы бы поподробнее описали, что вам надо, чтобы народ не напрягал свой gcc линковкой с libastral.so

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

Можешь глянуть GNU Portable Threads. Это как раз «треды в userspace».

Предположим я пишу свой Python или Ruby (С виртуальной машиной), как мне сделать потоки?

Как я понял, если множество инструментов предоставляемых ОС. Но я хотел бы понять как это сделать без них. Это возможно?

Но если я не волнуюсь по поводу производительности и мной движет только академический интерес, как сделать?

man signal, man alarm. Каждому своему потоку выделять квант времени, по сигаларм попадает в твой хендлер сигаларма. Там сохраняешь контекст прерванного потока и делаешь свапконтекс, потока который хочешь поставить на выполнение

Ну и кстати как вариант можно найти книжку «Введение в операционные системы» Иртегова (второе издание) и там начиная со страницы 431 прочитать (глава 8). Сразу все станет понятнее.

Ну нафига вам «писать свой питон или руби», если вы только начали учить ЯП? Начните с чего-нибудь простенького.

>qnx microkernel на предмет архитектуры ядра. И читать её исходники, они вроде как открыты

Не совсем: скачивавшие исходники ядра программеры ограничены подпиской о неразглашении (или как оно там называется). Потому в «открытом доступе» их до сих пор нет.

Зато их можно найти в emule.

Бери континьюэйшоны и читай Грэма, получится смешно, но почти то, что ты хочешь.

Это верно, но легче воспринимать потоки как выполняющиеся параллельно, и не заморачиваться тем, как оно там внутри реальзовано.

>Предположим я пишу свой Python или Ruby (С виртуальной машиной), как мне сделать потоки?

Лучше сначала придумай как сделать нормальный GC.

Green threads.

Т.е. нити уровня VM (виртуальной машины). Такие когда-то были в Java, но потом их заменили на нативные нити (уровня ОС). Вообще, в императивных языках у лёгких нитей уровня VM нет особых преимуществ (но есть проблемы с блокирующим I/O), преимущества могут быть в функциональных языках. Вот в Erlang как были «лёгкие процессы» уровня VM, так и есть. Что интересно, в контексте RTS Erlang-а они даже более эффективны чем нити ядра ОС, например, можно создать до миллиона фиктивных нитей за микросекунды, и сотни тысяч реально работающих нитей (см. Yaws).

Если у вас язык чистый (без побочных эффектов) вы можете после каждой редукции сохранять текущий указатель кода и делать jump на sheduler, при этом важна целостность кучи и стека, которые должны быть индивидуальны для каждой из этих нитей уровня VM. В шедулере просто переключаете номер нити (+1, если достигнут номер максимальной (на данный момент) нити, то <- 0), достаёте из хэша адрес возврата этой следующей нити и прыгаете туда. Так получается осуществлять редукции последовательно, переключаясь между нитями (имеются ввиду функциональные редукции, которые превращаются в код какой-либо стеково-регистровой машины, при компиляции возможно ставить эти прыжки, тем самым «разрезая» поток выполнения).

При этом (также как в Erlang-е) получается невозможным блокирующее I/O и обычное FFI (если где-то что-то остановится из-за IO или внешней «грязной» процедуры - остановятся все эти миллионы нитей), вместо этого нужно выделить для I/O отдельную нить и осуществлять его путём посылки/приёма асинхронных сообщений к/от этой нити из других нитей. Точно также общение между нитями можно осуществлять только посредством асинхронных сообщений, без всякой shared memory. Ну и к FFI там более строгий подход («драйверы»), гарантирующий отсутствие deadlock-ов.

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

Какие слова гуглить? Какие сорцы смотреть?

Можете посмотреть на Haskell :) Там Control.Concurrent в GHC реализован так - в RTS есть scheduler с нитями уровня VM в том числе.

Спасибо за ценный коментарий. Узнал много нового.

pthreads

pthread_join()