сколькими способами можно представить физический адрес 0x7c00 в виде сегмента и смещения
Поиск и вывод строки по заданному шаблону (с использованием симоволов «?», «*», «+»)
Добрый день Имею такое задание: необходимо написать программу, которая сможет найти в файле.
«Задача на поиск чего-либо в массиве»
Представим ситуацию, что надо, например, проверить массив на наличие в нем, например, цифры 5.
Типичная задача по теорверу «Стрелок стреляет.»
Доброго времени суток вам, товарищи математики. Собственно я глупый студент, пытающийся разобраться.
Подскажите алгоритм. Задача «Водолей»
Задача Водолей. Даны три емкости А, В, С, содержащие разный объем жидкости. Необходимо получить.
Задача «Отожги мирных ферзей!»
Не могу решить задачу с олимпа: http://www.e-olymp.com/ru/problems/2764 Сам решаю.
Задача «Игра», динамическое программирование
Задаётся натуральное число n. Двое играющих называют по очереди числа, меньшие 107, по следующим.
Олимпиадная задача «Интересный прямоугольник»
Решение сразу показалась не очень-то и сложным. Но теперь зашёл в тупик. Задача на геометрию.
Задача «Радость информатика»
Здравствуйте господа! Помогите решить данную задачу. Сам попытался но у меня какие-то проблемы с.
Сколькими способами можно представить физический адрес 0x7c00 в виде сегмента и смещения
Нужно было быстро посчитать формулу в цикле. Запустил Python в интерактивном режиме. Быстро ввел код по типу:
count = 0
for i in range(10000):
if formula(i):
count += 1
Показать полностью.
Python хвалят за свою способность быстро на коленке что-то сделать. Но в тот момент у меня не получилось это сделать, и я в нем очень сильно разочаровался
Если интересно, могу специально для Вас найти что это была за формула такая
upd: поправил скрин
upd2: правки по кодстайлу для кода на js
И вот такие алгоритмы в одну строчку на каком-нибудь stepik’е или codewars куча
Пишем свою ОС: Выпуск 2
Здравствуйте. Это снова мы, iley и pehat, с долгожданной второй статьёй из цикла «Пишем свою ОС» (первая статья здесь). Извиняемся за большую паузу после первой статьи, нам понадобилось некоторое время, чтобы определить дальнейшее направление нашей работы. В этом выпуске мы кратко рассмотрим защищённый режим 32-битных процессоров Intel. Ещё раз подчеркнём, что мы не ставим себе целью дать исчерпывающие теоретические данные.
Давайте на минуту вспомним нашу программу из предыдущего выпуска. Она запускалась вместо операционной системы и выводила сообщение «Hello world». Программа была написана на 16-битном ассемблере и работала в так называемом реальном режиме. Как вы наверняка знаете, при адресации в реальном режиме физический адрес формируется с помощью сегмента и смещения и имеет размерность 20 бит. Несложная математика подсказывает нам, что таким образом можно обращаться всего к мегабайту оперативной памяти.
Небольшой объём доступной памяти — это не единственная проблема реального режима. Представьте себе ситуацию, когда в памяти одновременно находится операционная система и несколько прикладных программ. В реальном режиме ничто не мешает любой из прикладных программ обратиться по адресу, принадлежащему другой программе или даже операционной системе. Таким образом, ошибка в одной программе может привести к краху всей системы.
Чтобы решить эти две проблемы, Intel в своё время разработали новый, значительно более сложный способ адресации оперативной памяти. Точнее, Intel разработали даже несколько способов адресации, и все они известны под собирательным названием защищённый режим.
Итак, адресация в защищённом режиме может происходить в одном из трёх режимов (извините за тавтологию) — в сегментном, страничном и сегментно-страничном. В этом выпуске мы рассмотрим только сегментный режим.
В сегментном режиме в памяти выделяются, как ни странно, сегменты. Эти сегменты значительно отличаются от простых и знакомых нам сегментов реального режима. В данном случае сегмент — это непрерывная область памяти, которая характеризуется базой, лимитом (т.е. грубо говоря, размером) и некими дополнительными атрибутами. База — это, грубо говоря, физический адрес, с которого начинается сегмент (на самом деле, это не физический адрес, а так называемый линейный, но об этом позже). Важно заметить, что, в отличие от сегментов реального режима, наши сегменты могут иметь произвольный размер. База, размер и атрибуты каждого сегмента хранятся в дескрипторе. Дескрипторы хранятся в специальных таблицах, а для выбора конкретного дескриптора из таблицы используются селекторы. Не пугайтесь такой кучи новых страшных слов, мы сейчас всё разложим по полочкам.
Итак, при каждом обращении к памяти процессор берёт из регистра (например, CS), селектор, находит по нему нужный дескриптор в таблице, извлекает из дескриптора адрес начала сегмента, прибавляет к адресу начала смещение и получает линейный адрес (обратите внимание, что линейный адрес и физический адрес — это разные вещи, но на данном этапе можно полагать, что это одно и то же). Кроме того, процессор проверяет, не вышел ли полученный адрес за границу сегмента и допускают ли атрибуты сегмента доступ к нему в данный момент. Схема вычисления линейного адреса выглядит примерно так:
Итак, как мы уже говорили, в дескрипторе хранится база (base address), размер (segment limit) и всякие дополнительные атрибуты сегмента. Давайте взглянем на схему дескриптора.
Обратите внимание, что под базу выделено 32 бита, а под лимит всего 20. Как же так, — спросите вы — разве нельзя создать сегмент, размер которого будет больше мегабайта? Можно. Для этого используется несложный трюк. Если бит G установлен в единицу, то лимит считается не в байтах, а в блоках по 4 Кбайт. Надо заметить, что лимит содержит размер сегмента минус один в единицах гранулярности, т.е. если лимит равен 0, то сегмент имеет размер 1 байт или 4 Кбайт. Кроме того, как вы видите, дескриптор включает ещё несколько полей. Их подробное описание можно найти, например, здесь.
Как упоминалось, дескрипторы хранятся в специальных таблицах. Таблиц может быть несколько, но в любом случае в памяти обязана присутствовать GDT — глобальная таблица дескрипторов. Она одна на всю операционную систему. В свою очередь, у каждой задачи, то есть процесса может быть ноль, одна или несколько LDT — локальных таблиц дескрипторов. Адрес и размер GDT хранится в регистре GDTR, текущей LDT — в регистре LDTR. Пока нам LDT не понадобится. Кроме того, бывают еще IDT — таблицы дескрипторов прерываний, но их рассмотрение отложим до следующего выпуска.
Для выбора дескриптора из таблицы используется структура данных, называемая селектором. Вот как он выглядит:
Селектор содержит в себе бит, указывающий, в какой таблице искать дескриптор, локальной или глобальной (L/G) и собственно номер дескриптора (descriptor number). Кроме того, у селектора есть поле RPL, но оно нас пока не интересует.
Итак, давайте перейдём к делу!
;Загрузить в CS:EIP точку входа в защищенный режим
O32 jmp 00001000b : pm_entry
Теперь немного поясним код.
После загрузки адреса и лимита глобальной таблицы дескрипторов в регистр GDTR идет поголовный запрет на прерывания. Объясняется это тем, что все обработчики прерываний работают в реальном режиме, и в защищенном режиме начнутся проблемы с адресацией. Так что пока строго-настрого запрещаем прерывания.
Для запуска программы нужно проделать манипуляции, полностью совпадающие с описанными в первой статье. Там же вы найдете список литературы на случай, если захотите узнать о защищенном режиме подробнее.
Нам не хватило фантазии на что-нибудь, демонстрирующее реальные возможности защищенного режима, поэтому мы снова выводим “Hello, World!”, но уже пользуясь прямым доступом к видеопамяти. Чтобы сделать что-нибудь красивое, было бы удобно воспользоваться прерываниями. Тому, как использовать их в защищенном режиме, будет посвящена следующая статья нашего цикла. А вторая статья на этом заканчивается. Будем рады увидеть ваши отзывы и пожелания.
Адреса памяти: физические, виртуальные, логические, линейные, эффективные, гостевые
Мне периодически приходится объяснять разным людям некоторые аспекты архитектуры Intel® IA-32, в том числе замысловатость системы адресации данных в памяти, которая, похоже, реализовала почти все когда-то придуманные идеи. Я решил оформить развёрнутый ответ в этой статье. Надеюсь, что он будет полезен ещё кому-нибудь.
При исполнении машинных инструкций считываются и записываются данные, которые могут находиться в нескольких местах: в регистрах самого процессора, в виде констант, закодированных в инструкции, а также в оперативной памяти. Если данные находятся в памяти, то их положение определяется некоторым числом — адресом. По ряду причин, которые, я надеюсь, станут понятными в процессе чтения этой статьи, исходный адрес, закодированный в инструкции, проходит через несколько преобразований.
На рисунке — сегментация и страничное преобразование адреса, как они выглядели 27 лет назад. Иллюстрация из Intel 80386 Programmers’s Reference Manual 1986 года. Забавно, что в описании рисунка есть аж две опечатки: «80306 Addressing Machanism». В наше время адрес подвергается более сложным преобразованиям, а иллюстрации больше не делают в псевдографике.
Начнём немного с конца — с цели всей цепочки преобразований.
Физический адрес
Эффективный адрес
Эффективный адрес — это начало пути. Он задаётся в аргументах индивидуальной машинной инструкции, и вычисляется из значений регистров, смещений и масштабирующих коэффициентов, заданных в ней явно или неявно.
Например, для инструкции (ассемблер в AT&T-нотации)
addl %eax, 0x11(%ebp, %edx, 8)
эффективный адрес операнда-назначения будет вычислен по формуле:
eff_addr = EBP + EDX * 8 + 0x11
Логический адрес
Здесь обычно у тех, кто столкнулся с этими понятиями впервые, голова начинает идти кругом. Несколько упростить (или усложнить) ситуацию помогает тот факт, что почти всегда выбор селектора (и связанного с ним сегмента) делается исходя из «смысла» доступа. По умолчанию, если в кодировке машинной инструкции не сказано иного, для получения адресов кода используются логические адреса с селектором CS, для данных — с DS, для стека — с SS.
Линейный адрес
Эффективный адрес — это смещение от начала сегмента — его базы. Если сложить базу и эффективный адрес, то получим число, называемое линейным адресом:
lin_addr = segment.base + eff_addr
Преобразование логический → линейный не всегда может быть успешным, так как при его исполнении проверяется несколько условий на свойства сегмента, записанных в полях его дескриптора. Например, проверяется выход за границы сегмента и права доступа.
Сегментация была модной на некотором этапе развития вычислительной техники. В настоящее она почти всюду была заменена другими механизмами, и используется только для специфических задач. Так, в режиме IA-32e (64-битном) только два сегмента могут иметь ненулевую базу. Для остальных четырёх в этом режиме всегда линейный адрес == эффективный.
Что такое виртуальный адрес?
В литературе и в документации других архитектур встречается ещё один термин — виртуальный адрес. Он не используется в документации Intel на IA-32, однако встречается, например, в описании Intel® Itanium, в котором сегментация не используется. Можно смело считать, что для IA-32 виртуальный == линейный.
В советской литературе по вычислительной технике этот вид адресов также именовался математическим.
Страничное преобразование
Однако общая идея всегда одна и та же: линейный адрес разбивается на несколько частей, каждая из которых служит индексом в одной из системных таблиц, хранящихся в памяти. Записи в таблицах — это адреса начала таблицы следующего уровня или, для последнего уровня — искомая информация о физическом адресе страницы в памяти и её свойствах. Самые младшие биты не преобразуются, а используются для адресации внутри найденной страницы. Например, для режима PAE с размером страниц 4 кбайт преобразование выглядит так:
В разных режимах процессора различается число и ёмкость этих таблиц. Преобразование может завершиться неудачей, если очередная таблица не содержит валидных данных, или права доступа, хранящиеся в последней из них, запрещают доступ к странице; например, при записи в регионы, помеченные как «только для чтения», или попытке чтения памяти ядра из непривилегированного процесса.
Гостевой физический
До введения возможностей аппаратной виртуализации в процессорах Intel страничное преобразование было последним в цепочке. Когда же на одной системе работают несколько виртуальных машин, то физические адреса, получаемые в каждой из них, приходится транслировать ещё один раз. Это можно делать программным образом, или же аппаратно, если процессор поддерживает функциональность EPT (англ. Extended Page Table). Адрес, раньше называвшийся физическим, был переименован в гостевой физический для того, чтобы отличать его от настоящего физического. Они связаны с помощью EPT-преобразования. Алгоритм последнего схож с ранее описанным страничным преобразованием: набор связанных таблиц с общим корнем, последний уровень которых определяет, существует ли физическая страница для указанной гостевой физической.
Полная картина
Я попытался собрать все преобразования адреса в одну иллюстрацию. В ней преобразования обозначены стрелками, типы адресов обведены в рамки.
Как уже было сказано выше, каждое из преобразований может вернуть ошибку для адресов, не имеющих представления в следующем по цепочке виде. Устранение подобных проблем — это задача операционных систем и мониторов виртуальных машин, реализующих абстракцию виртуальной памяти.
Заключение
Организация памяти
За последнюю неделю дважды объяснял людям как организована работа с памятью в х86, с целью чтобы не объяснять в третий раз написал эту статью.
И так, чтобы понять организацию памяти от вас потребуется знания некоторых базовых понятий, таких как регистры, стек и тд. Я по ходу попробую объяснить и это на пальцах, но очень кратко потому что это не тема для этой статьи. Итак начнем.
Как известно программист, когда пишет программы работает не с физическим адресом, а только с логическим. И то если он программирует на ассемблере. В том же Си ячейки памяти от программиста уже скрыты указателями, для его же удобства, но если грубо говорить указатель это другое представление логического адреса памяти, а в Java и указателей нет, совсем плохой язык. Однако грамотному программисту не помешают знания о том как организована память хотя бы на общем уровне. Меня вообще очень огорчают программисты, которые не знают как работает машина, обычно это программисты Java и прочие php-парни, с квалификацией ниже плинтуса.
Так ладно, хватит о печальном, переходим к делу.
Рассмотрим адресное пространство программного режима 32 битного процессора (для 64 бит все по аналогии)
Адресное пространство этого режима будет состоять из 2^32 ячеек памяти пронумерованных от 0 и до 2^32-1.
Программист работает с этой памятью, если ему нужно определить переменную, он просто говорит ячейка памяти с адресом таким-то будет содержать такой-то тип данных, при этом сам програмист может и не знать какой номер у этой ячейки он просто напишет что-то вроде:
int data = 10;
компьютер поймет это так: нужно взять какую-то ячейку с номером стопицот и поместить в нее цело число 10. При том про адрес ячейки 18894 вы и не узнаете, он от вас будет скрыт.
Все бы хорошо, но возникает вопрос, а как компьютер ищет эту ячейку памяти, ведь память у нас может быть разная:
3 уровень кэша
2 уровень кэша
1 уровень кэша
основная память
жесткий диск
Это все разные памяти, но компьютер легко находит в какой из них лежит наша переменная int data.
Этот вопрос решается операционной системой совместно с процессором.
Вся дальнейшая статья будет посвящена разбору этого метода.
Архитектура х86 поддерживает стек.
Стек это непрерывная область оперативной памяти организованная по принципу стопки тарелок, вы не можете брать тарелки из середины стопки, можете только брать верхнюю и класть тарелку вы тоже можете только на верх стопки.
В процессоре для работы со стеком организованны специальные машинные коды, ассемблерные мнемоники которых выглядят так:
push operand
помещает операнд в стек
pop operand
изымает из вершины стека значение и помещает его в свой операнд
Стек в памяти растет сверху вниз, это значит что при добавлении значения в него адрес вершины стека уменьшается, а когда вы извлекаете из него, то адрес вершины стека увеличивается.
Теперь кратко рассмотрим что такое регистры.
Это ячейки памяти в самом процессоре. Это самый быстрый и самый дорогой тип памяти, когда процессор совершает какие-то операции со значением или с памятью, он берет эти значения непосредственно из регистров.
В процессоре есть несколько наборов логик, каждая из которых имеет свои машинные коды и свои наборы регистров.
Basic program registers (Основные программные регистры) Эти регистры используются всеми программами с их помощью выполняется обработка целочисленных данных.
Floating Point Unit registers (FPU) Эти регистры работают с данными представленными в формате с плавающей точкой.
Еще есть MMX и XMM registers эти регистры используются тогда, когда вам надо выполнить одну инструкцию над большим количеством операндов.
Рассмотрим подробнее основные программные регистры. К ним относятся восемь 32 битных регистров общего назначения: EAX, EBX, ECX, EDX, EBP, ESI, EDI, ESP
Для того чтобы поместить в регистр данные, или для того чтобы изъять из регистра в ячейку памяти данные используется команда mov:
mov eax, 10
загружает число 10 в регистр eax.
mov data, ebx
копирует число, содержащееся в регистре ebx в ячейку памяти data.
Регистр ESP содержит адрес вершины стека.
Кроме регистров общего назначения, к основным программным регистрам относят шесть 16битных сегментных регистров: CS, DS, SS, ES, FS, GS, EFLAGS, EIP
EFLAGS показывает биты, так называемые флаги, которые отражают состояние процессора или характеризуют ход выполнения предыдущих команд.
В регистре EIP содержится адрес следующей команды, которая будет выполнятся процессором.
Я не буду расписывать регистры FPU, так как они нам не понадобятся. Итак наше небольшое отступление про регистры и стек закончилось переходим обратно к организации памяти.
Как вы помните целью статьи является рассказ про преобразование логической памяти в физическую, на самом деле есть еще промежуточный этап и полная цепочка выглядит так:
линейный адрес=Базовый адрес сегмента(на картинке это начало сегмента) + смещение
Сегмент кода
Сегмент данных
Сегмент стека
Используемый сегмент стека задается значением регистра SS.
Смещение внутри этого сегмента представлено регистром ESP, который указывает на вершину стека, как вы помните.
Сегменты в памяти могут друг друга перекрывать, мало того базовый адрес всех сегментов может совпадать например в нуле. Такой вырожденный случай называется линейным представлением памяти. В современных системах, память как правило так организована.
Теперь рассмотрим определение базовых адресов сегмента, я писал что они содержаться в регистрах SS, DS, CS, но это не совсем так, в них содержится некий 16 битный селектор, который указывает на некий дескриптор сегментов, в котором уже хранится необходимый адрес. 
Так выглядит селектор, в тринадцати его битах содержится индекс дескриптора в таблице дескрипторов. Не хитро посчитать будет что 2^13 = 8192 это максимальное количество дескрипторов в таблице.
Вообще дескрипторных таблиц бывает два вида GDT и LDT Первая называется глобальная таблица дескрипторов, она в системе всегда только одна, ее начальный адрес, точнее адрес ее нулевого дескриптора хранится в 48 битном системном регистре GDTR. И с момента старта системы не меняется и в свопе не принимает участия.
А вот значения дескрипторов могут меняться. Если в селекторе бит TI равен нулю, тогда процессор просто идет в GDT ищет по индексу нужный дескриптор с помощью которого осуществляет доступ к этому сегменту.
Пока все просто было, но если TI равен 1 тогда это означает что использоваться будет LDT. Таблиц этих много, но использоваться в данный момент будет та селектор которой загружен в системный регистр LDTR, который в отличии от GDTR может меняться.
Индекс селектора указывает на дескриптор, который указывает уже не на базовый адрес сегмента, а на память в котором хранится локальная таблица дескрипторов, точнее ее нулевой элемент. Ну а дальше все так же как и с GDT. Таким образом во время работы локальные таблицы могут создаваться и уничтожаться по мере необходимости. LDT не могут содержать дескрипторы на другие LDT.
Итак мы знаем как процессор добирается до дескриптора, а что содержится в этом дескрипторе посмотрим на картинке: 
Дескрипторы состоит из 8 байт.
Биты с 15-39 и 56-63 содержат линейный базовый адрес описываемым данным дескриптором сегмента. Напомню нашу формулу для нахождения линейного адреса:
линейный адрес = базовый адрес + смещение
[база; база+предел)
(база+предел; вершина]
Кстати интересно почему база и предел так рвано располагаются в дескрипторе. Дело в том что процессоры х86 развивались эволюционно и во времена 286х дескрипторы были по 8 бит всего, при этом старшие 2 байта были зарезервированы, ну а в последующих моделях процессоров с увеличением разрядности дескрипторы тоже выросли, но для сохранения обратной совместимости пришлось оставить структуру как есть.
Значение адреса «вершина» зависит от 54го D бита, если он равен 0, тогда вершина равна 0xFFF(64кб-1), если D бит равен 1, тогда вершина равна 0xFFFFFFFF (4Гб-1)
С 41-43 бит кодируется тип сегмента.
000 — сегмент данных, только считывание
001 — сегмент данных, считывание и запись
010 — сегмент стека, только считывание
011 — сегмент стека, считывание и запись
100 — сегмент кода, только выполнение
101- сегмент кода, считывание и выполнение
110 — подчиненный сегмент кода, только выполнение
111 — подчиненный сегмент кода, только выполнение и считывание
44 S бит если равен 1 тогда дескриптор описывает реальный сегмент оперативной памяти, иначе значение S бита равно 0.
Самым важным битом является 47-й P бит присутствия. Если бит равен 1 значит, что сегмент или локальная таблица дескрипторов загружена в оперативку, если этот бит равен 0, тогда это означает что данного сегмента в оперативке нет, он находится на жестком диске, случается прерывание, особый случай работы процессора запускается обработчик особого случая, который загружает нужный сегмент с жесткого диска в память, если P бит равен 0, тогда все поля дескриптора теряют смысл, и становятся свободными для сохранения в них служебной информации. После завершения работы обработчика, P бит устанавливается в значение 1, и производится повторное обращение к дескриптору, сегмент которого находится уже в памяти.
На этом заканчивается преобразование логического адреса в линейный, и я думаю на этом стоит прерваться. В следующий раз я расскажу вторую часть преобразования из линейного в физический.
А так же думаю стоит немного поговорить о передачи аргументов функции, и о размещении переменных в памяти, чтобы была какая-то связь с реальностью, потому размещение переменных в памяти это уже непосредственно, то с чем вам приходится сталкиваться в работе, а не просто какие-то теоретические измышления для системного программиста. Но без понимания, как устроена память невозможно понять как эти самые переменные хранятся в памяти.
В общем надеюсь было интересно и до новых встреч.