Комментарии 38
Считается, что во многом благодаря этой особенности Burroughs получила первые заказы на свою ЭВМ от Эйндховенского университета в Нидерландах.
Скорее, благодаря тому, что Дейкстра совмещал работу в этом университете и в Burroughs. Он вообще отметился в науке, кроме всего прочего, рубкой со страшной силой за интересы Burroughs.
Ну, в более поздних железяках, включая современные процы, стековой архитектуры как таковой есть: сам стек имеется, но как именно его использовать, во многом определяет программа -- в отличие от описанных в статье "истинно стековых" машин.
Кстати говоря, отсутствие стека в IBMовских мэйнфреймах, как по мне -- самый большой недостаток архитектуры. Конечно, без него вполне можно обойтись, но неудобно, да и скорость при вызове подпрограмм страдает, если не предпринимать заблаговременные и иногда весьма нетривиальные меры...
На тот момент это было неудобно, но в современных условиях аппаратный стек скорее, наоборот, вызывает проблемы с многопоточностью, переполнением и контролем прав доступа.
Так что мейнфреймы IBM, где память для вызываемого кода выделялась вызывающим кодом в виде области сохранения в своей статической памяти или в куче, можно сказать, опередили своё время.
Никаких проблем аппаратный стек сам по себе не вызывает. Т.е. вообще никаких. Нет проблемы в выделении стека каждому потоку, нет проблемы контролировать переполнение стека, нет проблемы контролировать права доступа -- и если ОС далеко не всегда всё это делают по-человечески, то это не из-за невозможности это сделать.
Ну а области сохранения... Те же самые проблемы, вид сбоку. Каждому потоку нужна своя цепочка областей сохранения, память может закончиться, а доступ к ним контролировать куда сложней: в отличие от стека, занимающего непрерывный кусок виртуального адресного пространства и поэтому потенциально пригодного для защиты обычными механизмами виртуальной памяти (таблицами переадресации), динамическая память общая для всего процесса, и области сохранения, относящиеся к разным потокам, вполне могут находиться по соседним виртуальным адресам, "переплетаясь" как угодно между собой.
Нет проблемы в выделении стека каждому потоку
Сколько именно стека вы предлагаете выделять каждому потоку?
Тут люди на семидесятом году развития программирования банальнейшей рекурсии боятся из-за возможного переполнения стека (причём те же самые люди, которые направо и налево выделяют динамическую память под объекты), а вы говорите – нет проблем.
Вот должен ли сегмент памяти под стек быть исполняемым, например?
Никакой проблемы с переполнением стека нет.
Если стек уперся в лимит (который к стаи проверяется элементарно), то выделяется больший сегмент памяти и существующий стек туда банально тушкой перекидывается.
Одно из преимуществ стека именно в том, что не имеет значения в каком месте (с какого адреса) он хранится прямо сейчас или будет храниться позже.
Одно из преимуществ стека именно в том, что не имеет значения в каком месте (с какого адреса) он хранится прямо сейчас или будет храниться позже.
Вот так новость. А как же должны работать указатели на объекты, размещённые в стеке?
А зачем ссылаться на объекты в стеке по абсолютным адресам?
Собственно ссылаться на объекты в стеке просто не хорошая практика.
В стеке могут хранится ссылки, на то что в куче. И от смены места хранения таких ссылок никаких сложностей не возникнет.
Собственно механизм что я описал используется например в рантайме golang.
Проблема в том, что ссылаться прямо, а не относительно указателя стека к памяти в стеке можно и, более того, такое происходит постоянно. Скажем, создали в стеке экземпляр некоего класса (локальную переменную функции) и вызвали какую-либо другую функцию, передав ей указатель на эту переменную (причём можно даже не знать, что передан указатель -- это может быть скрыто компилятором). В такой ситуации передан будет именно виртуальный адрес объекта в стеке, а не смещение относительно виртуального адреса вершины стека -- а соответственно, перемещать стек в этот момент нельзя.
Можно сколько угодно хаять языки, которые поступают именно так (хоть рукописный ассемблерный код, хоть выхлоп компиляторов це/це++, хоть ещё уйму других традиционно компилируемых языков), но взять и просто выкинуть всё написанное на них ПО в рамках существующих ОС невозможно. Реализовать новую ОС под новые языки?.. Ну, технически это возможно, конечно, только, боюсь, с ПО там будет негусто, ведь даже просто перекомпилировать исходники крупных проектов, созданных под Винду, для Линуха или наоборот может быть не очень просто, а тут простой перекомпиляцией явно не обойдёшься.
Ну почему только относительно указателя на вершину стека? Можно и относительно дна стека ссылку сделать. Если стек в отдельном сегменте то там вообще только относительная ссылка будет.
Но тут действительно не так просто взять в любом языке провернуть идею с переносом стека в более крупный сегмент памяти.
Я скорее про то, что такое в принципе возможно (при определенных условиях).
Я подозреваю, тут надо говорить чуть о другом. Есть подход под названием split stack. Если функция детектирует, что стек подходит к предельно возможной границе, она вызывает аллокацию большого блока в новом месте. (Реально каждая такая функция на входе безусловно вызывает какой-нибудь check_stack который всё это и делает.)
Он обычно не включён по умолчанию, но реализации есть почти везде.
выделяется больший сегмент памяти и существующий стек туда банально тушкой перекидывается
В каком смысле "перекидывается"? Насколько я помню книжку Рихтера в современных ОС вполне себе существует страничная память, и никуда ничего перекидывать не надо... Просто добавляем ещё страницу и работаем. Плюс физически в стеке есть набор зарезервированных страниц (на весь размер стека), но "коммитятся" они только при попытке к ним обратиться (потому что память виртуальная).
Ограничение -- размер заранее выделенного виртуального адресного пространства. Т.е. если у тебя под стек зарезервированы адреса от 1000 до 1FFF, ты не сможешь его расширить свыше этих пределов, поскольку адреса ниже 1000 и выше 1FFF, вполне вероятно, уже назначены для чего-то другого (скажем, стека другого потока). Но, по большому счёту, на 64-разрядной системе можно резервировать очень большие объёмы, хотя это потенциально, но не всегда влечёт определённые накладные расходы (на таблицы переадресации).
Просто добавляем ещё страницу и работаем.
Это механизм, принятый в Windows, и он работает только в том случае, когда мы заполняем данные в стеке не более чем по одной странице. Если я размещаю массив более 4 килобайт и не инициализирую его, это не срабатывает. Поэтому Windows расписывает вновь размещаемые на стеке объекты нулями, что может обходиться очень дорого, когда они имеют большие размеры и предназначены для размещения разреженных данных (например, хеш-таблицы).
Если у конкретной реализации есть конкретные недостатки, это не значит, что обязательно всегда и везде реализовывать именно так. Технических проблем расширить стек сразу на большую величину нет, если виртуальное адресное пространство было под это дело зарезервировано.
Техническая проблема в том, что для большого количества ниток стеков не напасёшься. Конечно, для 64-разрядной архитектуры проблема менее актуальна, но всё равно пухнет таблица страниц.
Объём таблиц переадресации зависит, вообще говоря, от объёма распределённого виртуального адресного пространства. А выделяется пространство под страницы стеков или страницы динамической памяти, используемой для областей сохранения -- это без разницы.
Области сохранения не обязаны образовывать непрерывный диапазон виртуальных адресов, в отличие от аппаратного стека. Поэтому сто ниток потребуют 100*maxstack виртуальной памяти в случае аппаратного стека и только фактически занятый объём в случае областей сохранения. Иными словами, аппаратный стек расходует виртуальное адресное пространство, даже не будучи заполненным.
Это да, про что я выше и говорил -- выделять заранее адресное пространство, основываясь на информации от компоновщика. Но само по себе оно память пожирает только при реальной необходимости, а что до таблиц переадресации, то нередко есть возможность выделять лишь необходимую часть. Скажем, ещё в Системе 370, где они были чисто двухуровневыми, на самом верхнем уровне (в управляющем регистре) задавался размер таблицы сегментов, а в каждом элементе таблицы сегментов -- размер соответствующей таблицы страниц. Соответственно, если полная таблица страниц позволяет адресовать, скажем, 64 Мбайта (цифры с потолка, чисто для иллюстрации), но тебе нужно лишь 4 Мбайта, а начало области выровнено на эти самые 64 Мбайта, делаешь укороченную таблицу страниц, да и всё: попытка обратиться к адресу, для которого нет элемента, вызывает прерывание, а дальше уже ОС смотрит, ошибка это или надо расширять таблицу.
Но, кстати говоря, можно попробовать сделать и "кусочный" стек, но это нужно заморачиваться в ОС. Идея в том, что при достижении выделенной границы хоть вниз, хоть вверх приложение попадает на страницу, которая никогда не выделяется, а соответственно, происходит прерывание -- и ОС вручную изменяет указатель стека, чтоб указывал на начало-конец следующего/предыдущего сегмента стека.
Тут проблема как раз в том, что новое обращение к стеку может прийтись не на guard page, а ещё дальше.
Да, Вы правы... Т.е. реализовать-то такое можно, но лишь при строгом соответствии кода прикладного уровня определённым требованиям. Хотя "юридически" это не проблема: выпускаешь официальную спецификацию на использование стека прикладными программами, и всё, а кто нарушил -- его проблемы. Но, как по мне, это излишнее усложнение, и лучше всё ж не делать сегментированный стек: его основное достоинство -- как раз простота использования и для приложения, и для системы. (Ну и, замечу, аппаратная поддержка стека отнюдь не мешает использовать области сохранения в стиле Системы 360, и тот же компилятор Фортрана, если в нём регулярно получаются такие конструкции, может именно области сохранения организовывать невидимым для пользователя образом, а не использовать стек -- или использовать, но ограниченно, для мелких переменных и адресов возврата)
По умолчанию я бы резервировал под стек порядка 256 килобайт адресного пространства; если нужно больше, то это, скорей всего, указывает на проблемы в архитектуре приложения (огромная глубина вызовов подпрограмм и огромное количество локальных переменных в них); естественно, фактически выделял бы по потребности -- добавляя новые страницы по мере необходимости. Однако технически нет проблем максимальную величину стека задавать в процессе сборки приложения компоновщиком, а также при запуске. Если реально есть такая потребность -- пожалуйста, укажи соответствующий параметр при сборке, и будет резервироваться, скажем, гигабайт (на 64-разр системе -- не проблема).
Защита от исполнения кода в области данных (и, в частности, в стеке), равно как и защита от модификации области кода, уже давным-давно обеспечивается MMU при должной настройке таблиц переадресации. Вот в Системе 370 такой защиты ещё не было, это да.
У меня, например, по умолчанию в компоновщике прописано 2 гигабайта стека. И я бы не назвал это проблемой в архитектуре. Один большой динамически размещаемый массив, например.
Защита от исполнения кода в области данных (и, в частности, в стеке), равно как и защита от модификации области кода, уже давным-давно обеспечивается MMU при должной настройке таблиц переадресации.
Только это подразумевает, что код в стеке не может появляться. А если может? Например, передаётся через стек динамически сгенерированный код. Да банальная фортрановская подпрограмма интегрирования вызывает предупреждение линкера о исполняемом коде в стеке, не говорю уж там о приложениях функционального программирования.
А если, например, уровень секретности у разных стековых фреймов должен быть разный?
Нет по сути никакого общего требования к стеку, потому что стек – это всего лишь порядок выделения памяти, а не какая-то определённая категория данных.
Для специфических случаев ничто не мешает использовать некие специфические механизмы. Однако для обычных вызовов обычных функций механизм стека и удобнее, и эффективнее, чем области сохранения.
Ну а насчёт гигантских массивов в стеке... Лично я бы так делать не стал, а выделил бы большой кусок динамически -- но, по сути, Вы сами указали, что эта проблема вполне решаемая прописыванием параметров компоновщика.
Вот я, допустим, простой учёный, программирующий на Фортране. И вы мне предлагаете вместо
read *, m, n
allocate a(m,n)мутить какие-то структуры данных с указателями, чтобы массив оказался вместо стека в куче. Это возможно, конечно, но неудобно в использовании и ухудшает читаемость и надёжность* кода.
* В таком случае и освобождать память придётся руками.
Кстати говоря, отсутствие стека в IBMовских мэйнфреймах, как по мне -- самый большой недостаток архитектуры. Конечно, без него вполне можно обойтись, но неудобно, да и скорость при вызове подпрограмм страдает, если не предпринимать заблаговременные и иногда весьма нетривиальные меры...
Это можно разобрать по пунктам:
1. Для userland, если вы не видели, для кода на C стек эмулируется доступом относительно регистра 15, то есть стек сделан элементом ABI. Линия S/360 не единственная такая: точно так же, например, в новейшем RISC-V и проблемы от этого не видят. Наоборот, требование явных push/pop, которые надо разбивать на микрооперации, для современных процессоров становится утяжеляющим.
2. Существенной проблемой в системах до S/390 в этом смысле было отсутствие в командах типа RX, RS отрицательных непосредственных смещений. Да, приходилось костылить. Например, тот же доступ к стеку получался в формате: например, аллоцировать 200 байт: LA 1, 200 // SR 15, 1 - и дальше уже неотрицательными смещениями. Но костыль откровенно минимальный.
Эта ошибка, да, не была повторена последующими реализациями, а начиная с S/390 дали команды с 20-битным смещением со знаком. То есть вместо такой пары LA + SR будет сразу, например, LAY 15, -200(15). И можно использовать отрицательные смещения, если хочется. Чуть проще, но разница минимальная.
3. Вызов одной подпрограммы в куче архитектур делается помещением адреса возврата не в стек, а в отдельный регистр. Кроме названных тут ещё все ARM (регистр X30 для AArch64). И тоже нет плача про это. Нужно ещё кого-то вызвать - сам сложил этот регистр в стек.
4. Для системного уровня стек там не нужен за счёт подхода с парами ячеек PSW - old PSW и возможностью временного использования "нулевой страницы". И опять же новые архитектуры, как RISC-V, это повторяют, с поправкой на мелкие детали. (Здесь я не в курсе предыдущих подходов типа MIPS.)
------
Ну то есть я реально тут со стороны именно железа не вижу проблем аж вообще. Оно не мешает - и этого достаточно.
Вот то, что стандартное ABI до какого-то момента это не предусматривало (если оно вообще было) и компиляторы были слабые - было более важно. Типовой компилятор сразу сбрасывал при входе все регистры в область сохранения, чем-то вроде STM 14,12,0(13) - и на выходе восстанавливал; это действительно долго, нудно и скорее бессмысленно.
Думать в стиле стека везде включая системный уровень - можно. Но не обязательно.
Всё перечисленное я знаю. Для Системы 370 (точней, советских ЕС ЭВМ Ряда 2) писал на ассемблере немало, на ARMах (микроконтроллерах, т.е. М-профиле, и на классических, из которых выросли A/R-профили) писал и пишу сейчас. В любом случае, при наличии аппаратного стека работать удобнее -- это как раз ARMовский случай, и да, LR действительно сохраняется в стеке вместе с другими регистрами, если в дальнейшем нужно вызывать подпрограмму. Но если стека нет -- изволь заморачиваться с выделением/освобождением областей сохранения, а это долго и нудно, особенно если подпрограммы должны быть повторно-входимыми (если повторная входимость не требуется -- кажется, именно так было в классическом Фортране, -- то область сохранения для каждой подпрограммы можно, в принципе, выделять статически, а для подпрограмм, никогда не выполняемых одновременно -- совмещать в памяти). Надо полагать, Вы в курсе, что в оригинальной OS/360 вообще предлагалось выделять память под область сохранения в начале выполнения подпрограммы путём вызова ОС (дёргать GETMAIN) -- но это ж кошмарно низкая скорость будет: при каждом вызове подпрограммы вызывать ОС для выделения памяти, а в конце выполнения подпрограммы -- для её освобождения.
Всё перечисленное я знаю.
Ну, я прокомментировал "для неопределённого круга читателей" (c) :)
В любом случае, при наличии аппаратного стека работать удобнее -- это как раз ARMовский случай, и да, LR действительно сохраняется в стеке вместе с другими регистрами, если в дальнейшем нужно вызывать подпрограмму. Но если стека нет -- изволь заморачиваться с выделением/освобождением областей сохранения,
Так в том и дело, что лучше сказать "при наличии стека работать удобнее" без акцента на его "аппаратность". Просто выделенный один регистр работает не хуже, если ему не мешать.
Варианты PDP-11, VAX, ARM, x86 и прочих отличаются тем, что стек используется на полностью контролируемых процессором операциях типа обработки прерываний. И вот тут начинается, что его надо при этом явно поддерживать раздельным для разных уровней привилегий - это есть во всех перечисленных архитектурах. А если его нет, то достаточно софтовой обработки. Может, она чуть медленнее, но процессор проще.
если повторная входимость не требуется -- кажется, именно так было в классическом Фортране, -- то область сохранения для каждой подпрограммы можно, в принципе, выделять статически, а для подпрограмм, никогда не выполняемых одновременно -- совмещать в памяти
Да, я помню эти проблемы.
Вы в курсе, что в оригинальной OS/360 вообще предлагалось выделять память под область сохранения в начале выполнения подпрограммы путём вызова ОС (дёргать GETMAIN)
А вот этого совсем не помню. Верю, но сам не помню :)
Зато в каком-то классическом полушуточном тексте 80-х утверждалось, что тот, кто принял решение исключить стек из S/360, был впоследствии "сослан во внутрифирменный аналог Сибири" (дословно). Впоследствии читал, что это чисто легенда. Но она отражает как раз проблемы бесстекового вызова.
книжка по теме Stack Computers: the new wave
перевод http://the-epic-file.com/text/bookz/sc/sc_contents.htm
Смотрел старый советский документальный фильм 70-х про московский ЗиЛ, так у них вся бухгалтерия, планово-экономическая часть и складское работали через терминалы с B5500 (возможно и с филиалами завода связь была). Почему не применили советский компьютер не понятно.
Могли внедрять всё это, когда ничего по-настоящему подходящего советского банально не было. ЕС ЭВМ появились, во многом, как раз из-за того, что у нас в конце 1960-х задумались о массовом АСУчивании ("цифровизации", выражаясь современным языком) народного хозяйства и внезапно выяснилось, что подходящих ЭВМ попросту нет: почти все советские разработки были ориентированы исключительно на научно-технические расчёты, а не на решение планово-экономических задач. Нет, понятно, что БЭСМ-6 могла считать зарплату -- но делала это куда менее эффективно, чем при решении научных задач.
Чего в статье не сказано - это как достигалась эффективность такой работы только со стеком. Память всегда была медленнее процессора.
Про Эльбрус-(1,2) я, например, слышал, что у них реально кэш вершины стека (сколько-то ячеек) в регистрах. Вики про B7700 и некоторые последующие говорит то же самое, но только через 10 лет после первой модели линейки. Раньше это не настолько было важно?
А ещё набор операций со стеком. Из Форта я помню DUP, DROP, SWAP, PICK, OVER, ROT - это минимальная группа, чтобы с этим можно было хоть сколько-то удобно работать.
Память всегда была медленнее процессора.
Не всегда. Например, в 6502 процессор значительно медленнее памяти. Да и в младших моделях ЕС ЭВМ регистры процессора размещались в памяти.
Спасибо за поправку, я таки слишком обобщил. Надо было сказать, что локальные регистры на триггерах всегда быстрее внешней памяти - вот на это я исключений не видел. Часто на порядки медленнее (как сейчас, и как массово было в 50-х, как раз когда Burroughs начинались). Случай 6502 это не медленность его схемотехники - у неё хватало времени - а следствие перекошенного общего дизайна.
Да и в младших моделях ЕС ЭВМ регистры процессора размещались в памяти.
Подозреваю, тут тоже были проблемы общего дизайна. Потому что единицы микросекунд на чтение-запись ферримагнетика по сравнению с десятками (или единицами на быстрых вариантах) наносекунд на триггерах - всё-таки сильно больше.
В принципе сделать отдельные регистры быстрее массовой памяти, конечно, всегда можно. Но соображения стоимости и надёжности, бывало, диктовали обратное, и это не проблема, а особенность. Тот же 6502 был одним из самых популярных и массовых процессоров своего времени, если не самым.
А кроме того, какой прок разгонять память, если АЛУ само по себе тормозное?
Почти-почти всегда память действительно была медленнее процессора. АЛУ ЕС-1020 успевало выполнить обработку за 250-300 нс -- но, поскольку регистры процессора были в обычном ферритовом ОЗУ, хотя и в невидимой для программиста области, -- машинный такт составлял 1000 нс, поскольку именно столько требовалось для выборки информации из ОЗУ (и потом ещё столько же требовалось для регенерации или записи обновлённой информации). В ЕС-1022 АЛУ технически осталось тем же самым, только расширенным с одного до двух байт, но локальную память разместили в микросхемах К155РУ1 (ёмкость каждой аж 16 бит) -- и это позволило отвязать цикл процессора от цикла ОЗУ и сократить его на треть (до 650 нс, если память не изменяет), причём за этот сокращённый цикл и АЛУ, и локальная память успевали отработать дважды, выполняя за одну микрокоманду обработку не одного, а до четырёх байтов, что и стало главной причиной резкого повышения производительности у ЕС-1022 по сравнению с ЕС-1020, хотя само ОЗУ на 1022 даже медленнее: полуцикл 1,2 мкс вместо 1,0 (ну а быстрей 500 нс я лично ферритовую память сколько-нибудь значительного объёма не встречал).
То же самое у IBM: в модели 360/30 регистры лежат в обычном ферритовом ОЗУ, а в 360/40 выполнены внутри процессора на какой-то другой памяти, и в результате модель 40 намного производительней, хотя тоже имеет однобайтовое АЛУ, как и 30.
И даже с 6502 и прочими ранними микропроцессорами не всё так однозначно. 6502 просто не форсировали по частоте за ненадобностью, но, скажем, 8080, выполненный в те же годы по примерно такой же технологии, работал не на 1 МГц, а на 2, 2,5, 3 в зависимости от конкретной разновидности, но не умел обращаться к памяти каждый свой такт (кажется, минимум 3 такта у него было на одно обращение к памяти) -- но это из-за особенностей внутреннего, весьма небыстрого устройства, в результате чего 6502 часто оказывался более высокопроизводительным, чем 8080, несмотря на в 2-3 раза меньшую частоту. Ну а цикл в 500 нс, соответствующий частоте 2 МГц, вполне сопоставим с циклом ранних динамических ОЗУ, современных этим микропроцессорам. Скажем, наша К565РУ1 (4 Кбита), содранная с кого-то из интелов, если память не изменяет, имела цикл 500-900 нс -- т.е., в общем-то, такой же, как у быстрой ферритовой памяти, а соответственно, если и была быстрей ранних микропроцессоров, то очень несильно -- да и то под вопросом (хотя бы потому, что, помимо времени на работу собственно микросхемы памяти, необходимо учитывать время на работу дешифраторов и прочих внешних схем, что ещё порядка 100 нс вполне добавляло).
Ну и, кроме того, не стоит забывать, что ранние микропроцессоры были очень медленными -- для средней и тем более высокой производительности использовались совсем другие машины, собранные на рассыпной логике и биполярных микропроцессорных секциях (скажем, PDP-11 и VAX-11 1970-х -- сплошь на ТТЛ/ТТЛШ, в роли АЛУ зачастую, хотя не всегда, -- SN74181 или SN74S181; у IBM вообще свои микросхемы, схемотехнически относящиеся к ЭСЛ, но, вроде бы, не совместимые с коммерческими микросхемами Моторолы, которые мы содрали как 100- и 500-ю серии и использовали в большинстве ЕСок). То есть "настоящие" процы были сильно быстрей любого доступного ОЗУ, и сопоставимую скорость имели лишь "игрушечные".
Burroughs B5000 — первый компьютер со стековой архитектурой