Что такое стек процесса
Стек — что это такое и как он устроен? Какие виды стеков бывают
Здравствуйте, уважаемые читатели блога KtoNaNovenkogo.ru. Продолжаю объяснять сложные компьютерные термины простыми словами. Сегодня расскажу, что такое стек в программировании, как он устроен и каких видов бывает.
Это будет полезно для тех, кто в будущем планирует серьезно работать в сфере IT, ведь это одна из основополагающих концепций программирования, влияющих на качество кода, но не касающихся конкретного языка.
Что такое стек простыми словами
По традиции рассказ начну с определения. Термин пришел из английского языка: слово stack переводится как «пробка».
Стек — это один из способов организации и хранения информации в программировании. Если говорить профессиональным языком, это одна из структур данных.
Википедия дает определение стеку как абстрактному типу данных, представленному в виде организованного по принципу LIFO списка элементов. В свою очередь, аббревиатура LIFO расшифровывается как last in — first out, то есть « пришел последним, а вышел первым».
Термин появился в середине XX века благодаря Алану Тьюрингу. В таких языках программирования как Python и Lisp стеком называют любой список, потому что для них доступны операции выталкивания (pop на английском) и проталкивания (push). Для стека характерна еще одна операция — чтение головного элемента (по-английски — peek).
Как устроен стек
Программисты часто сравнивают стек со стопкой одинаковых тарелок, ведь он работает по схожему принципу: поставленная позже всех тарелка будет использоваться первой. Вряд ли кто-то будет пытаться вытягивать тарелку из середины или низа стопки. А чтобы взять вторую тарелку сверху, нужно в обязательном порядке сначала снять первую.
В стеке важна последовательность данных и здесь применима линейная связь:
Данные следуют друг за другом, брать их из произвольного места нельзя.
Добавление или проталкивание (на английском — push) элемента возможно только в вершину стека. Как только элемент стека использован, он удаляется (процесс называется выталкиванием, или pop на английском), а верхним элементом (top) становится следующий.
Исходя из вышесказанного, выделю главный принцип работы стека: данные, которые попали последними, используются первыми. А если информация попала первой, то она должна использоваться последней.
Похожим образом реализована другая структура данных — очередь (queue на английском). Но разница лишь в том, что в очереди первым используется раньше всех попавший в нее элемент, а последним — тот, что позже всех. Для наглядности представьте очередь на кассе супермаркета: кто первым занял место, тот первым и расплатился. Все, как и в реальной жизни.
Виды стеков
Различают две разновидности стеков:
Расскажу подробнее о каждом из них.
Стек вызовов
Стек вызовов — это область памяти, в которой хранится информация о точках перехода между фрагментами программного кода.
Этот вид используется, когда в программе есть подпрограммы и компьютеру нужно запомнить место, где программный код прерывался для выполнения подпрограммы, чтобы потом вернуться к выполнению основного кода. Если подпрограмма вдобавок вернула определенную информацию, компьютер должен запомнить и ее, а потом еще и передать в код основной программы.
Стек практически всегда хранится в оперативной памяти. Так как каждый стек занимает в ОЗУ определенное место, в случае слишком большого количества подобных элементов может случиться такая ситуация как переполнение. Почему это плохо? Потому что в этом случае данные могут попасть в область памяти другого элемента и перезаписать себя вместо той информации, которая там должна быть.
Это чревато следующими проблемами:
Стек данных
Стек данных очень схож со стеком вызовов и работает с ним по тому же принципу: первым используется последний добавленный в него элемент, а последним — тот элемент, который попал туда раньше других.
Стек данных обычно используется для работы со сложными типами информации:
Вот и все, дорогие друзья. Теперь вы имеете представление о таком понятии, как стек, как он устроен и каковы его разновидности существуют. Надеюсь, что вам все было понятно и после прочтения статьи вопросы отпадут сами собой. Если нет, то спускайтесь в комментарии к публикации, спрашивайте, что было непонятно, а другие читатели блога KtoNaNovenkogo.ru помогут найти ответы.
Я вернусь к вам с новой статьей уже совсем скоро. Не забудьте также посмотреть полезное видео по теме, которое вы найдете под этой статьей.
Удачи вам! До скорых встреч на страницах блога KtoNaNovenkogo.ru
Эта статья относится к рубрикам:
Комментарии и отзывы (1)
Дмитрий, к какой рубрики относиться данная статья. Заранее благодарю!
Основные принципы программирования: стек и куча
Мы используем всё более продвинутые языки программирования, которые позволяют нам писать меньше кода и получать отличные результаты. За это приходится платить. Поскольку мы всё реже занимаемся низкоуровневыми вещами, нормальным становится то, что многие из нас не вполне понимают, что такое стек и куча, как на самом деле происходит компиляция, в чём разница между статической и динамической типизацией, и т.д. Я не говорю, что все программисты не знают об этих понятиях — я лишь считаю, что порой стоит возвращаться к таким олдскульным вещам.
Сегодня мы поговорим лишь об одной теме: стек и куча. И стек, и куча относятся к различным местоположениям, где происходит управление памятью, но стратегия этого управления кардинально отличается.
Стек — это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out), то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.
Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека — это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.
В итоге стек позволяет управлять памятью наиболее эффективным образом — но если вам нужно использовать динамические структуры данных или глобальные переменные, то стоит обратить внимание на кучу.
Куча — это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.
27–29 декабря, Онлайн, Беcплатно
Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.
В сравнении со стеком, куча работает медленнее, поскольку переменные разбросаны по памяти, а не сидят на верхушке стека. Некорректное управление памятью в куче приводит к замедлению её работы; тем не менее, это не уменьшает её важности — если вам нужно работать с динамическими или глобальными переменными, пользуйтесь кучей.
Заключение
Вот вы и познакомились с понятиями стека и кучи. Вкратце, стек — это очень быстрое хранилище памяти, работающее по принципу LIFO и управляемое процессором. Но эти преимущества приводят к ограниченному размеру стека и специальному способу получения значений. Для того, чтобы избежать этих ограничений, можно пользоваться кучей — она позволяет создавать динамические и глобальные переменные — но управлять памятью должен либо сборщик мусора, либо сам программист, да и работает куча медленнее.
Русские Блоги
Стек ядра процесса, стек пользователя
1. Стек процессов
Когда ядро создает процесс, коллеги, которые создают task_struct, создают соответствующий стек для процесса. Каждый процесс будет иметь два стека: пользовательский стек, который существует в пользовательском пространстве, и стек ядра, который существует в пространстве ядра. Когда процесс выполняется в пространстве пользователя, содержимым регистра указателя стека процессора является адрес стека пользователя, и используется стек пользователя; когда процесс находится в пространстве ядра, содержимое регистра указателя стека процессора является адресом пространства стека ядра, и используется стек ядра.
2. Переключение между пользовательским стеком процесса и стеком ядра.
Когда процесс переходит в режим ядра из-за прерывания или системного вызова, стек, используемый процессом, также необходимо передать из пользовательского стека в стек ядра.
После перехода процесса в режим ядра сначала сохраните адрес стека пользовательского режима в стеке ядра, а затем установите содержимое регистра указателя стека на адрес стека ядра, таким образом завершив преобразование из пользовательского стека в стек ядра; когда процесс переходит из режима ядра При восстановлении в пользовательский режим в конце режима ядра адрес пользовательского стека, хранящийся в стеке ядра, восстанавливается в регистр указателя стека. Таким образом реализуется взаимное преобразование между стеком ядра и пользовательским стеком.
Затем мы знаем, что адрес стека пользователя сохраняется в стеке ядра, когда он захватывается ядром, когда он передается из ядра в пользовательский режим, но как мы узнаем адрес стека ядра, когда он захвачен ядром?
Ключевым моментом является то, что когда процесс переходит из пользовательского режима в режим ядра, стек ядра процесса всегда пуст. Это связано с тем, что когда процесс выполняется в пользовательском режиме, используется пользовательский стек. Когда процесс переходит в режим ядра, стек ядра сохраняет уверенность в том, что процесс работает в режиме ядра, но как только процесс возвращается в пользовательский режим, стек ядра Сохраненная информация недействительна и будет полностью восстановлена, поэтому стек ядра, получаемый каждый раз, когда процесс попадает в ядро из пользовательского режима, пуст. Следовательно, когда процесс находится в ловушке ядра, достаточно напрямую передать верхний адрес стека ядра в регистр указателя стека.
3. Реализация стека ядра
Среди них размер INIT_STACK_SIZE может быть только 8 КБ.
Когда ядро выделяет структуру task_struct для каждого процесса, оно фактически выделяет две последовательные физические страницы, нижняя часть которых используется как структура task_struct, а верхняя часть структуры используется как стек. Используйте макрос current () для доступа к дескриптору текущего запущенного процесса.
Примечание. В настоящее время структура task_struct находится в стеке ядра, а фактический полезный размер стека ядра составляет около 7 КБ.
Реализация стека ядра в ядре-2.6 (ядро-2.6.32):
Размер THREAD_SIZE может составлять 4 КБ или 8 КБ, а thread_info занимает 52 байта.
Конкретная структура показана на рисунке: 
Когда размер стека ядра равен 8 КБ, Thread_info находится в начальном адресе этой памяти, а стек ядра растет вниз от конца стека. Итак, в настоящее время необходимо изменить текущий макрос в ядре 2.6. Чтобы получить задачу, связанную с thread_info, через поле task_struct в структуре thread_info. Дополнительные сведения см. В реализации соответствующего текущего макроса.
Примечание. В настоящее время структура task_struct больше не находится в пространстве стека ядра.
Структура реального стека ядра показана на рисунке ниже. Поскольку стек всегда простирается от высоких адресов к младшим адресам, нижняя часть стека находится в конце комплекса thread_union, а структура thread_info расположена в начале комплекса thread_union и занимает меньше места. Пока нет крайнего случая, когда стек ядра особенно велик, стек и thread_info не могут мешать друг другу. На рисунке представлена схематическая диаграмма адресного пространства ядра. 
Пользовательский стек
Когда пользовательская программа вызывает функцию уровень за уровнем, пользовательский стек расширяется от верхнего адреса к низкому адресу, добавляя каждый раз кадр стека. Кадр стека хранит параметры функции, адрес возврата и локальные переменные, поэтому длина кадра стека Не уверен.
Нижняя часть пользовательского стека находится близко к верхнему краю пространства процесса, но, как правило, не просто выровнена по краю. В целях безопасности между нижней частью стека и верхним краем процесса вставляется область изоляции произвольного размера. Таким образом, расположение стека меняется каждый раз при запуске программы, поэтому хакерам непросто использовать уязвимости безопасности на основе стека для проведения атак.
Масштабирование пользовательского стека прозрачно для приложения, и приложению не нужно управлять стеком само по себе, что является функцией, предоставляемой операционной системой. Когда приложение только что запущено (новый процесс копируется системным вызовом fork ()), новый процесс фактически не занимает места в стеке. Когда функция вызывается в приложении и ее необходимо поместить в стек, будет вызвана ошибка страницы. Ядро обнаружит, что процессу требуется новое пространство стека при обработке этого исключения, поэтому оно создает новую VMA и отображает память в пользовательский стек. 
Разница между стеком ядра и стеком пользователя:
Процессор Intel разделен на четыре рабочих уровня: ring0
Ядро создает процесс, создает блок управления процессом при создании процесса и создает свой собственный стек.
У процесса есть два стека: пользовательский стек и системный стек.
Пространство пользовательского стека указывает на адресное пространство пользователя, а пространство стека ядра указывает на адресное пространство ядра.
Есть регистр указателя стека ЦП, состояние запущенного процесса имеет пользовательский режим и режим ядра, когда процесс выполняется в пользовательском режиме. Регистр указателя стека ЦП указывает на адрес стека пользователя, и используется стек пользователя; когда процесс работает в режиме ядра, регистр указателя стека ЦП указывает на адрес стека ядра, который использует стек ядра.
1. Переключение стека
Когда система переключается в привилегированный режим работы из-за системного вызова (мягкое прерывание) или аппаратного прерывания, процесс переходит в режим ядра, и стек, используемый процессом, также изменяется из пользовательского стека в системный стек.
Переход из пользовательского режима в режим ядра осуществляется в два этапа: сначала необходимо сохранить адрес пользовательского стека в стеке ядра, а затем указать регистр указателя стека ЦП на стек ядра.
При переходе из режима ядра в режим пользователя первым шагом является восстановление адреса стека пользователя в стеке ядра в регистр указателя стека ЦП.
2. Разница между стеком ядра и стеком пользователя
Каждая Windows имеет 4 г пространства процесса, системный стек использует часть пространства процесса, а пользовательский стек является частью верхнего уровня.Если пользователь хочет получить прямой доступ к части системного стека, требуется особый способ.
Зачем создавать два разных стека?
Код и данные ядра используются всеми процессами.Если соответствующий стек ядра не установлен для каждого процесса, то разные процессы не могут быть реализованы для выполнения разных кодов.
Если стек только один, то пользователи могут изменять содержимое стека, чтобы нарушить защиту безопасности ядра.
Для чего нужны стеки?
Jul 3, 2019 · 4 min read
Когда я узнал, что такое стек, мне стало интересно его практическое применение. Оказалось, что чаще всего эта структура используется для имплементации операции “Отмена” ( то есть, ⌘+ Z или Ctrl+ Z).
Чтобы понять, как это работает, разберемся с определением стека.
Что такое стек?
Стек — список элементов, который может быть изменён лишь с одной стороны, называющейся вершиной стека.
Представьте приспособление для раздачи тарелок, в котором тарелки стоят в стопке. Новые тарелки можно добавлять только поверх уже имеющихся, а брать можно лишь сверху. Таким образом, чем позже тарелку положат в стопку, тем раньше её оттуда возьмут. В рамках структур данных это называется LIFO-принципом (последним пришёл — первым ушёл).
Если использовать терминологию, то стек поддерживает операции добавления ( push) и удаления ( pop) элементов на его вершине.
Зачем использовать стек для отмены?
Потому что обычно мы хотим отменить последнее действие.
Стек позволяет добавлять элементы к его вершине и удалять тот элемент, который был последним.
Что произойдёт, если ни одно действие не будет отменено? Стек ведь станет огромным!
Верно. Если не удалять элементы из стека отмены, то есть не использовать операцию отмены, то он станет очень большим. Именно поэтому такие приложения, как Adobe Photoshop, с увеличением времени работы над файлом используют всё больше и больше оперативной памяти. Стек отмены хранит все действия, произведённые над файлом, в памяти до тех пор, пока вы не сохраните и не закроете файл.
Имплементация стека
Стек можно реализовать, используя либо связные списки, либо массивы. Я приведу пример реализации стека на обеих структурах на Python и расскажу о плюсах и минусах каждой.
Стек на связном списке:
Стек на массиве:
Что лучше?
В коде я указал сложность каждой из операций, используя “О” большое. Как видите, имплементации мало чем отличаются.
Однако есть некоторые нюансы, которые стоит учесть.
Массив
Это непрерывный блок памяти. Из-за этого при маленьком размере стека массив будет занимать лишнее место. Ещё один недостаток в том, что каждый раз при увеличении размера массива придётся копировать все уже существующие элементы в новую ячейку памяти.
Связный список
Он состоит из отдельных блоков в памяти и может увеличиваться бесконечно. Поэтому, с одной стороны, имплементация стека с использованием этой структуры немного лучше с точки зрения сложности алгоритма. С другой стороны, каждый элемент должен хранить адреса предыдущего и следующего элемента, что требует больше памяти.
Заключение
Так как динамический массив увеличивается в два раза при заполнении очереди, необходимость выделить дополнительную память будет возникать всё реже и реже. Кроме того, так как указатели не занимают много места, дополнительные данные в связных списках не критичны.
Как видим, между этими двумя реализациями стека практически нет различий — используйте ту, что нравится вам.
Принципы программирования: стек и куча: что это такое?
С каждым годом мы применяем для программирования всё более продвинутые языки, позволяющие писать меньше кода, но получать нужные нам результаты. Однако всё это не проходит даром для разработчиков. Так как программисты всё реже занимаются низкоуровневыми вещами, уже никого не удивляет ситуация, когда разработчик не вполне понимает, что означают такие понятия, как куча и стек. Что это такое, как происходит компиляция на самом деле, в чём разница между динамической и статической типизацией.
К сожалению, некоторые программисты, даже будучи «джуниорами» и работая на реальных проектах, не совсем чётко ориентируются в таких, казалось бы, олдскульных вещах. Именно поэтому в нашей сегодняшней статье мы вспомним, что же это такое — стек и куча, для чего они нужны и где применяются. Несмотря на то, что и стек, и куча связаны с управлением памятью, стратегия и принципы управления кардинально различаются.
Стек — что это такое?
Большое число задач, связанных с обработкой информации, поддаются типизированному решению. В результате совсем неудивительно, что многие из них решаются с помощью специально придуманных методов, терминов и описаний. Среди них нередко можно услышать и такое слово, как стек (стэк). Хоть и звучит этот термин, на первый взгляд, странно и даже сложно, всё намного проще, чем кажется.
Стек и простой жизненный пример
Представьте, что на столе в коробке лежит стопка бумажных листов. Чтобы получить доступ к самому нижнему листу, вам нужно достать самый первый лист, потом второй и так далее, пока не доберётесь до последнего. По схожему принципу и устроен стек: чтобы последний элемент стека стал верхним, нужно сначала вытащить все остальные. 
Стек и особенности его работы
Перейдя к компьютерной терминологии, скажем, что стек — это область оперативной памяти, создаваемая для каждого потока. И последний добавленный в стек кусочек памяти и будет первым в очереди, то есть первым на вывод из стека. И каждый раз, когда функцией объявляется переменная, она, прежде всего, добавляется в стек. А когда данная переменная пропадает из нашей области видимости (к примеру, функция заканчивается), эта самая переменная автоматически удаляется из стека. При этом если стековая переменная освобождается, то и область памяти, в свою очередь, становится доступной и свободной для других стековых переменных.
Благодаря природе, которую имеет стек, управление памятью становится весьма простым и логичным для выполнения на центральном процессоре. Это повышает скорость и быстродействие ЦП, и в особенности такое происходит потому, что время цикла обновления байта весьма незначительно (данный байт, скорее всего, привязан к кэшу центрального процессора).
Тем не менее у данной довольно строгой формы управления имеются и свои недостатки. Например, размер стека — это величина фиксированная, в результате чего при превышении лимита памяти, выделенной на стеке, произойдёт переполнение стека. Как правило, размер задаётся во время создания потока, плюс у каждой переменной имеется максимальный размер, который зависит от типа данных. Всё это позволяет ограничивать размеры некоторых переменных (допустим, целочисленных).
Кроме того, это вынуждает объявлять размер более сложных типов данных (к примеру, массивов) заранее, так как стек не позволит потом изменить его. Вдобавок ко всему, переменные, которые расположены на стеке, являются всегда локальными.
Для чего нужен стек?
Главное предназначение стека — решение типовых задач, предусматривающих поддержку последовательности состояний или связанных с инверсионным представлением данных. В компьютерной отрасли стек применяется в аппаратных устройствах (например, в центральном процессоре, как уже было упомянуто выше).
Практически каждый, кто занимался программированием, знает, что без стека невозможна рекурсия, так как при любом повторном входе в функцию требуется сохранение текущего состояния на вершине, причём при каждом выходе из функции, нужно быстро восстанавливать это состояние (как раз наша последовательность LIFO).
Если же копнуть глубже, то можно сказать, что, по сути, весь подход к запуску и выполнению приложений устроен на принципах стека. Не секрет, что прежде чем каждая следующая программа, запущенная из основной, будет выполняться, состояние предыдущей занесётся в стек, чтобы, когда следующая запущенная подпрограмма закончит выполняться, предыдущее приложение продолжило работу с места остановки.
Стеки и операции стека
Если говорить об основных операциях, то стек имеет таковых две: 1. Push — ни что иное, как добавление элемента непосредственно в вершину стека. 2. Pop — извлечение из стека верхнего элемента.
Также, используя стек, иногда выполняют чтение верхнего элемента, не выполняя его извлечение. Для этого предназначена операция peek.
Как организуется стек?
Когда программисты организуют или реализуют стек, они применяют два варианта: 1. Используя массив и переменную, указывающую на ячейку вершины стека. 2. Используя связанные списки.
У этих двух вариантов реализации стека есть и плюсы, и минусы. К примеру, связанные списки считаются более безопасными в плане применения, ведь каждый добавляемый элемент располагается в динамически созданной структуре (раз нет проблем с числом элементов, значит, отсутствуют дырки в безопасности, позволяющие свободно перемещаться в памяти программного приложения). Однако с точки зрения хранения и скорости применения связанные списки не столь эффективны, так как, во-первых, требуют дополнительного места для хранения указателей, во-вторых, разбросаны в памяти и не расположены друг за другом, если сравнивать с массивами.
Подытожим: стек позволяет управлять памятью более эффективно. Однако помните, что если вам потребуется использовать глобальные переменные либо динамические структуры данных, то лучше обратить своё внимание на кучу.
Стек и куча
Куча — хранилище памяти, расположенное в ОЗУ. Оно допускает динамическое выделение памяти и работает не так, как стек. По сути, речь идёт о простом складе для ваших переменных. Когда вы выделяете здесь участок памяти для хранения, к ней можно обращаться как в потоке, так и во всём приложении в целом (именно так и определяются переменные глобального типа). По завершении работы приложения все выделенные участки освобождаются.
Размер кучи задаётся во время запуска приложения, однако, в отличие от того, как работает стек, в куче размер ограничен только физически, что позволяет создавать переменные динамического типа.
Если сравнивать, опять же, с тем, как работает стек, то куча функционирует медленнее, т. к. переменные разбросаны по памяти, а не находятся вверху стека. Тем не менее данный факт не уменьшает важности кучи, и если вам надо работать с глобальными либо динамическими переменными, она больше подходит. Однако управлять памятью тогда должен программист либо сборщик мусора.
Итак, теперь вы знаете и что такое стек, и что такое куча. Это довольно простые знания, больше подходящие для новичков. Если же вас интересуют более серьёзные профессиональные навыки, выбирайте нужный вам курс по программированию в OTUS!