Наименьший объем компьютерной памяти, необходимый для хранения одного из двух символов 0 и 1

Обновлено: 02.07.2024

В этом лабораторном занятии вы изучите, как различные виды информации представлены на компьютере.

На этой странице вы узнаете об битах, основных единицах данных в вычислениях.

Бит — это отдельная единица данных, которая может иметь только одно из двух значений. Обычно мы представляем эти два значения как 0 (выключено) и 1 (включено).

Как вы, наверное, знаете, информация передается по проводам внутри компьютера, и каждый провод либо включен, либо выключен, промежуточные состояния не допускаются. Этот небольшой фрагмент информации называется битом, наименьшей возможной единицей информации в цифровой области.

Ложь и правда
Выкл. и Вкл., имитируя выключатель света.
Красный и зеленый, имитирующие светофор.

Но что, если светофору также нужно желтое значение? Заманчиво сказать, что, например, 0 вольт на проводе означает красный цвет, 1 вольт — желтый, а 2 вольта — зеленый. Давным-давно были компьютеры, которые работали таким образом, но есть веские причины придерживаться двух возможных значений для каждого провода.

Какие веские причины?

< бр />

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

Это приблизительный график фактического поведения входа-выхода транзистора. Не беспокойтесь о деталях; просто обратите внимание на две синие плоские части графика. В области «отсечки» небольшие изменения входного напряжения вообще не меняют выходное напряжение; на выходе всегда ноль вольт. Точно так же в области «насыщения» небольшие изменения входного сигнала не влияют на выходное напряжение; этот вывод интерпретируется как единица. Именно так транзисторы используются в качестве переключателей в компьютере. Если бы на кривой было три плоских участка, возможно, у нас было бы три возможных значения для каждого провода.

Транзисторы — это универсальные устройства. При использовании в средней линейной (розовой) части графика они являются усилителями; небольшое изменение входного напряжения приводит к большому изменению выходного напряжения. Именно так они используются для воспроизведения музыки в стереосистеме.

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

второй бит	значение
0	0	красный
0	1	желтый
1	0	зеленый
1	1	(не используется)

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

Убедите себя, что больше не существует комбинаций двух битов.
Запишите все возможные комбинации трех битов. Сколько их?
Сколько существует комбинаций четырех битов?

Каждый добавленный бит удваивает количество значений, которые вы можете представить. Это означает, что представление сложных ситуаций не требует больших затрат оборудования; десяти бит достаточно для представления более 1000 различных значений.

Сколько именно значений может быть представлено десятью битами?
Сколько битов нужно для представления дней недели?
Сколько бит требуется для представления одной десятичной цифры (то есть для указания цифры от 0 до 9)?

В байте восемь бит.

Слово — это последовательность из любого количества битов, обрабатываемых ЦП за раз. По состоянию на 2017 год слова имеют длину 32 или 64 бита.

Биты стоят не дорого, но дорого — это схема, позволяющая программисту использовать наименьшее количество битов для конкретной задачи.

Можем ли мы вырезать этот закомментированный текст? --MF, 31.08.19
Я думаю, нам следует подумать о переносе его на U6, но не сегодня. -бч

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

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

Вместо этого современные компьютеры обычно позволяют выделять память только в двух размерах: байт, который стандартизирован на восьми битах, и слово, которое определяется как последовательность битов, которые ЦП обрабатывает за раз. По состоянию на 2017 год слова могут иметь ширину 32 бита или 64 бита, хотя большинство новых моделей компьютеров используют 64 бита.

Сколько различных значений может быть представлено 32 битами? Вам не нужно запоминать ответ, потому что вы можете быстро приблизить его, используя тот факт, что 2 10 = 1024, что примерно равно 1000. Это означает, что каждые десять битов ширины умножают количество значений это может быть представлено примерно 1000. Таким образом, 10 битов позволяют получить около тысячи значений, 20 битов — около миллиона значений, 30 битов — около миллиарда, а 32 бита — более четырех миллиардов значений (потому что мы удваиваем миллиард еще два раза). за разницу между 30 и 32).

Этот прием может оказаться полезным на экзамене AP.

Кажется, четырех миллиардов значений должно быть достаточно, но это не так, если вы астроном или банкир (или Google или Facebook). Вот почему у нас теперь есть 64-битные компьютеры, которые с 2019 года являются стандартом. (Apple только что удалила поддержку 32-разрядных программ в MacOS.)

Примерно сколько различных значений может быть представлено в 64-битном слове? (Не используйте калькулятор, используйте хитрость!)

Байты и символы

Восьмибитные байты в основном используются для представления символов текста.

Сколько битов нужно для представления 26 букв английского языка и десяти цифр от 0 до 9?

Широкое использование восьмибитного кода ASCII – основная историческая причина, по которой восьмибитный байт стал стандартом. (Еще одна причина заключается в том, что компьютерные схемы могут легче всего работать с шириной, равной степени двойки.)

В течение многих лет компьютеры использовали шестибитные коды символов, но для того, чтобы иметь как ВЕРХНИЙ РЕГИСТР, так и строчный буквы и знаки препинания, требуется семь битов. Первой официально признанной кодировкой был семибитный набор символов ASCII (американский стандартный код для обмена информацией). Он включал необязательный восьмой бит для обнаружения ошибок, который был использован для включения символов с диакритическими знаками в испанском, французском, немецком и некоторых других европейских языках. Например, в имени главного разработчика Snap!, немца Йенса Мёнига, есть символ с ударением. (Ближайший английский звук — это «u» в слове «lunch».)

По мере распространения компьютеров и Интернета по всему миру люди хотели иметь возможность писать на китайском, японском, арабском, кабильском, русском, тамильском и т. д. Набор символов Unicode поддерживает около 1900 языков, использующих 32 современных алфавита и 107 исторических алфавитов, которые больше не используются. Полный набор символов Unicode включает 136 755 символов.

Какое минимальное количество битов необходимо для представления любого символа Unicode?

фактическое компьютерное представление Юникода сложно.

В наиболее простом представлении Unicode используется одно 32-битное слово на символ, чего более чем достаточно. Но разработчики программ считают, что это неэффективное использование компьютерной памяти, а также то, что многие старые программы, которые до сих пор используются, были написаны, когда восемь бит на символ были стандартом. Таким образом, символы Unicode обычно представляются в многобайтовом представлении, в котором исходные 128 символов ASCII занимают один байт, а для других символов может потребоваться до четырех байтов. (Можно также использовать многобайтовую последовательность, чтобы указать программе обработки текстов, что вы хотите использовать однобайтовые или двухбайтовые коды для представления определенного нелатинского алфавита.)

Этот контент был заархивирован и больше не поддерживается Университетом Индианы. Информация здесь может быть неточной, а ссылки могут быть недоступны или ненадежны.

Примечание. Следующая информация частично предоставлена проектом Extreme Science and Engineering Discovery Environment ( XSEDE ) Национального научного фонда (NSF), который предоставляет исследователям передовые цифровые ресурсы и услуги, облегчающие научные открытия. Дополнительную информацию см. на веб-сайте XSEDE.

Бит — это двоичная цифра, наименьший приращение данных на компьютере.Бит может содержать только одно из двух значений: 0 или 1, что соответствует электрическим значениям выключено или включено соответственно.

Поскольку биты очень малы, вы редко работаете с информацией по одному биту за раз. Биты обычно собираются в группу из восьми, чтобы сформировать байт. Байт содержит достаточно информации для хранения одного символа ASCII, например "h".

Килобайт (КБ) — это 1 024 байта, а не тысяча байтов, как можно было бы ожидать, потому что компьютеры используют двоичную систему (с основанием два) вместо десятичной (с основанием десять).

Хранилище и память компьютера часто измеряются в мегабайтах (МБ) и гигабайтах (ГБ). Роман среднего размера содержит около 1 МБ информации. 1 МБ – это 1 024 килобайта, или 1 048 576 (1024 x 1024) байт, а не миллион байт.

Точно так же один 1 ГБ равен 1024 МБ или 1 073 741 824 (1024 x 1024 x 1024) байт. Терабайт (ТБ) равен 1024 ГБ; 1 ТБ — это примерно такой же объем информации, как и все книги в большой библиотеке, или примерно 1610 компакт-дисков с данными. Петабайт (ПБ) равен 1024 ТБ. 1 ПБ данных, записанных на DVD, создаст примерно 223 100 DVD, т. е. стопку высотой около 878 футов или стопку компакт-дисков высотой в милю. Университет Индианы в настоящее время создает системы хранения, способные хранить петабайты данных. Эксабайт (ЭБ) равен 1024 ПБ. Зеттабайт (ZB) равен 1024 ЭБ. Наконец, йоттабайт (YB) равен 1024 ZB.

Многие производители жестких дисков используют десятичную систему счисления для определения объема дискового пространства. В результате 1 МБ определяется как один миллион байтов, 1 ГБ определяется как один миллиард байтов и так далее. Поскольку ваш компьютер использует двоичную систему, как указано выше, вы можете заметить несоответствие между опубликованной емкостью вашего жесткого диска и емкостью, подтвержденной вашим компьютером. Например, жесткий диск, который, как говорят, содержит 10 ГБ дискового пространства с использованием десятичной системы счисления, на самом деле способен хранить 10 000 000 000 байтов. Однако в двоичной системе 10 ГБ составляют 10 737 418 240 байт. В результате вместо подтверждения 10 ГБ ваш компьютер подтвердит 9,31 ГБ. Это не неисправность, а вопрос разных определений.

Мы считаем по основанию 10 по степеням 10:

Компьютеры считают по основанию 2:

Итак, на компьютерном жаргоне используются следующие единицы:

< /th> < td>1 048 576 байт

Примечание. Названия и сокращения для количества байтов легко спутать с обозначениями для битов. В сокращениях для количества битов используется строчная буква «b» вместо прописной «B». Поскольку один байт состоит из восьми битов, эта разница может быть значительной. Например, если рекламируется широкополосное подключение к Интернету со скоростью загрузки 3,0 Мбит/с, его скорость составляет 3,0 мегабита в секунду или 0,375 мегабайта в секунду (сокращенно 0,375 Мбит/с). Биты и скорости передачи данных (биты во времени, например, в битах в секунду [бит/с]) чаще всего используются для описания скорости соединения, поэтому уделяйте особое внимание при сравнении поставщиков и услуг подключения к Интернету.

Этот документ был разработан при поддержке грантов Национального научного фонда (NSF) 1053575 и 1548562. Любые мнения, выводы, выводы или рекомендации, выраженные в этом материале, принадлежат авторам и не обязательно отражают точку зрения НФС.

Вся информация, хранящаяся в компьютере, должна быть каким-то образом закодирована в виде последовательности нулей и единиц, поскольку все устройства хранения состоят из набора ячеек, которые могут находиться в одном из двух возможных состояний. Одно состояние представляет 0, другое состояние представляет 1. Например, на компакт-диске или DVD есть миллиарды мест, где либо маленькая ямка была создана лазерным лучом (представляющая 1), либо ямка не существует (представляющая 0). Старая магнитная лента (например, аудиокассета или видеокассета VHS) состояла из последовательности мест, которые могли быть намагничены с восходящей или нисходящей поляризацией, представляющей 0 или 1.

В одном месте хранения хранится один бит (двоичная цифра) информации. Набор из 8 бит — это байт, и это, как правило, наименьшая единица информации, с которой имеет дело компьютер. В байте могут храниться $2^8 = 256$ разные шаблоны нулей и единиц, и эти разные шаблоны могут представлять разные вещи, в зависимости от контекста.

Целые числа¶

Если мы хотим сохранить целое число, то имеет смысл хранить двоичное представление целого числа, а в одном байте мы можем хранить любые числа от 0 до 255 с обычным двоичным представлением:

Конечно, многие практические задачи связаны с целыми числами больше 256 и, возможно, с положительными и отрицательными целыми числами. Таким образом, на практике одно целое число обычно хранится с использованием более 1 байта. По умолчанию для большинства компьютерных языков используется 4 байта для целого числа, что составляет 32 бита. Один бит используется для указания того, является ли число положительным или отрицательным, оставляя 31 бит для представления значений от 0 до $2^ = 2147483648$, а также отрицательных значений этих значений. На самом деле это немного сложнее (без каламбура), поскольку только что описанная схема позволяет хранить как +0, так и -0, а более сложная система позволяет хранить еще одно целое число, и на практике используется представление с дополнением до двух, как описано в [wikipedia ], в которой показана таблица того, как числа от -128 до 127 на самом деле будут представлены в одном байте.

Вещественные числа¶

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

Обратите внимание, что дроби могут быть представлены в двоичном формате с использованием обратных степеней 2. Например, десятичное число 5,625 может быть выражено как $4+1+\frac 1 2 + \frac 1 8$ , то есть:

и, следовательно, как 101.101 в двоичном формате.

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

Десятичное число 5,625 можно записать как $0,5625 \times 10^1$ в нормализованной форме с мантиссом 0,5625 и показателем степени 1.

Аналогично двоичное число 101.101 в форме с плавающей запятой имеет мантисса 0,101101 и показатель степени 10 (число 2 в двоичном формате, поскольку мантисса должна быть умножена на $2^2 = 4$, чтобы сдвинуть двоичную точку на два пробела. ).

До 1980 года разные производители компьютеров придумывали собственные способы хранения действительных чисел, что часто плохо справлялось с компьютерной арифметикой и приводило к серьезным проблемам с переносимостью компьютерных кодов между машинами. Стандарты IEEE в значительной степени решили эту проблему. Дополнительную информацию см. в [википедии].

Если мы сохраняем текст, например слова, которые вы сейчас читаете, символы также должны быть закодированы как строки из 0 и 1. Поскольку один байт может представлять 256 различных вещей, текст обычно кодируется с использованием одного байта для каждого символа. В английском языке нам нужно 52 различных шаблона для представления всех возможных букв (по одному шаблону для каждой буквы нижнего регистра и отдельный шаблон для соответствующей буквы верхнего регистра). Нам также нужно 10 шаблонов для цифр и достаточно большое количество других шаблонов для представления друг друга символов (например, знаков пунктуации, знаков доллара и т. д.), которые можно использовать.

См. Перфокарты, где приведен пример представления символов ASCII на перфокартах — ранней форме компьютерной памяти.

Очевидно, что для правильной интерпретации байта, хранящегося в компьютере, например 01001011, компьютеру необходимо знать, представляет ли он символ UTF-8, однобайтовое целое число или что-то еще.

Цвета¶

Еще одна вещь, которую может представлять строка из 0 и 1, — это цвет, например, один пиксель в отображаемом изображении. Каждый пиксель представляет собой одну точку света, и для указания того, какого цвета должен быть каждый пиксель, должна использоваться строка из 0 и 1. Существуют различные возможные способы задания цвета. Один из часто используемых способов заключается в указании тройки RGB, трех целых чисел, которые указывают количество красного, зеленого и синего в желаемом цвете. Часто каждое значение может находиться в диапазоне от 0 (не указывает на отсутствие) до 255 (максимальное количество). Все эти значения могут храниться в 1 байте данных, поэтому в этой системе 3 байта (24 бита) используются для хранения цвета одного пикселя. Красный цвет, например, имеет максимальные R и 0 для G и B и, следовательно, имеет первый байт 256 и следующие два байта 0 и 0. Вот красный и несколько других цветов в их RGB и двоичном представлении:

Цвета в html-документах и в других местах часто задаются путем точного написания того, какие значения должен иметь каждый из байтов. Записывать биты, как указано выше, обычно неудобно для людей, поэтому вместо этого графические языки, такие как Matlab или Matplotlib в Python, обычно позволяют вам указывать тройку RGB с точки зрения дробей от 0 до 1 (разделите приведенные выше значения RGB на 255, чтобы получить дроби). ):

Другой способ распространен в html-документах (а также разрешен в Matplotlib), где красный цвет обозначается строкой:

Последние два цвета можно увидеть в заголовке этой веб-страницы.

Чтобы найти шестнадцатеричную строку для нужного цвета или просмотреть цвет для заданной строки, попробуйте демо-версию farbtastic. См. также [wikipedia-web-colors] или эту страницу цветов, показывающую триплеты RGB и шестнадцатеричные коды.

Шестнадцатеричные числа¶

Шестнадцатеричное число имеет основание 16, например. шестнадцатеричное число 345 означает:

что равно 837 в десятичной системе счисления. Каждая шестнадцатеричная цифра может принимать одно из 16 значений, поэтому в дополнение к цифрам 0, 1, . 9 нам нужны символы для обозначения 10, 11, 12, 13, 14 и 15. Для них используются буквы a,b,c,d,e,f, например:

что равно 2638 в десятичном представлении.

Шестнадцатеричная нотация – удобный способ представления двоичных чисел, поскольку существует очень простой способ преобразования между шестнадцатеричными и двоичными числами. Например, чтобы преобразовать шестнадцатеричное число a4e в двоичное, просто переведите каждую шестнадцатеричную цифру отдельно в двоичную, a = 1010, 4 = 0100, e = 1110, а затем соедините их вместе, так что:

в двоичном формате. И наоборот, чтобы преобразовать двоичное число, такое как 100101101, в шестнадцатеричное, сгруппируйте биты в группы по 4 (начиная справа, при необходимости добавляя 0 слева) и преобразуйте каждую группу в шестнадцатеричное число:

Машинные инструкции¶

В дополнение к хранению данных (чисел, текста, цветов и т. д.) в виде строк битов мы также должны хранить компьютерные инструкции, составляющие компьютерную программу, в виде строки битов. Сейчас это может показаться очевидным, но на самом деле это была революционная идея, когда она впервые была предложена выдающимся математиком (и одним из первых «ученых-компьютерщиков») Джоном фон Нейманом. Идея «машины фон Неймана», в которой компьютерная программа хранится так же, как и данные, и может быть изменена по желанию, чтобы заставить компьютер выполнять разные действия, возникла в 1930-х и 40-х годах благодаря работам фон Неймана. Тьюринг и Цузе (см. [википедию]). До этого компьютеры были предназначены для выполнения одного определенного набора операций, выполнения одного алгоритма, и можно было легко изменить только данные. Чтобы «перепрограммировать» компьютер на что-то другое, требовалось физически перемонтировать схемы.

Современные компьютеры хранят последовательность инструкций для выполнения в виде двоичных строк. Эти строки отличаются от строк, которые могут представлять инструкции, когда удобочитаемая программа преобразуется в ASCII для сохранения в виде текстового файла.

В одном месте хранения хранится один бит (двоичная цифра) информации. Набор из 8 бит — это байт, и это, как правило, наименьшая единица информации, с которой имеет дело компьютер. Байт может хранить 2 ^ 8 = 256 различных шаблонов нулей и единиц, и эти разные шаблоны могут представлять разные вещи, в зависимости от контекста.

Целые числа¶

Конечно, многие практические задачи связаны с целыми числами больше 256 и, возможно, с положительными и отрицательными целыми числами. Таким образом, на практике одно целое число обычно хранится с использованием более 1 байта. По умолчанию для большинства компьютерных языков используется 4 байта для целого числа, что составляет 32 бита. Один бит используется для указания того, является ли число положительным или отрицательным, оставляя 31 бит для представления значений от 0 до $2^31 = 2147483648$, а также отрицательных значений этих значений. На самом деле это немного сложнее (без каламбура), поскольку только что описанная схема позволяет хранить как +0, так и -0, а более сложная система позволяет хранить еще одно целое число, и на практике используется представление с дополнением до двух, как описано в [wikipedia ], в которой показана таблица того, как числа от -128 до 127 на самом деле будут представлены в одном байте.

Вещественные числа¶

Если мы сохраняем текст, например слова, которые вы сейчас читаете, символы также должны быть закодированы как строки из 0 и 1. Поскольку один байт может представлять 256 различных вещей, текст обычно кодируется с использованием одного байта для каждого символа. В английском языке нам нужно 52 различных шаблона для представления всех возможных букв (по одному шаблону для каждой буквы нижнего регистра и отдельный шаблон для соответствующей буквы верхнего регистра). Нам также нужно 10 паттернов для цифр и довольно большое количество других паттернов для представления друг друга (например,знаки препинания, знаки доллара и т. д.), которые могут использоваться.

Цвета¶

Последние два цвета можно увидеть в заголовке этой веб-страницы.

Шестнадцатеричные числа¶

Шестнадцатеричное число имеет основание 16, например. шестнадцатеричное число 345 означает:

что равно 2638 в десятичном представлении.

Машинные инструкции¶

Проблема 2

Сколько страниц находится в виртуальном адресном пространстве?
Каков максимальный размер адресуемой физической памяти в этой системе?
Если средний размер процесса составляет 8 ГБ, вы бы использовали одноуровневую, двухуровневую или трехуровневую таблицу страниц? Почему?
Вычислите средний размер таблицы страниц в ответе на вопрос 3 выше.

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

Пейджинг 1 уровня
Поскольку у нас есть 2^23 страницы в каждом виртуальном адресном пространстве, и мы используем 4 байта на запись в таблице страниц, размер таблицы страниц будет 2^23 * 2^2 = 2 ^ 25. Это 1/256 собственного пространства памяти процесса, так что это довольно дорого. (32 МБ)

Пейджинг 2 уровня
Адрес будет разделен на 12 | 11 | 13, так как мы хотим, чтобы страницы таблицы страниц умещались на одной странице, и мы также хотим разделить биты примерно поровну.

Поскольку размер процесса составляет 8 ГБ = 2^33 Б, я предполагаю, что это означает, что общий размер всех отдельных страниц, к которым обращается процесс, составляет 2^33 Б. Следовательно, этот процесс обращается к 2^33 / 2^13 = 2^20 страниц. Нижний уровень таблицы страниц содержит 2^20 ссылок. Мы знаем, что размер каждого фрагмента нижнего уровня таблицы страниц составляет 2 ^ 11 записей. Таким образом, нам нужно 2^20 / 2^11 = 2^9 фрагментов нижнего уровня.

Тогда общий размер таблицы страниц равен:

Единица	Эквивалент
1 килобайт (КБ)	1024 байта
1 мегабайт (МБ)
1 гигабайт (ГБ)	1 073 741 824 байта
1 терабайт (ТБ) )	1 099 511 627 776 байт
1 петабайт (ПБ)	1 125 899 906 842 624 байт

//размер внешней таблицы страниц	//общий размер внутренних страниц< /td>
1 * 2^12 * 4	+ 2^9 * 2^11 * 4	= 2^20 * ( 2^-6 + 4) ~4 МБ

3 уровня пейджинга
Для 3 уровня пейджинга мы можем разделить адрес следующим образом:
8 | 8 | 7 | 13

Опять же, используя те же рассуждения, что и выше, нам нужно 2 ^ 20/2 ^ 7 = 2 ^ 13 фрагментов таблицы страниц уровня 3. Каждый фрагмент таблицы страниц уровня 2 ссылается на 2^8 фрагментов таблицы страниц уровня 3. Итак, нам нужно 2^13/2^8 = 2^5 таблиц уровня 2. И, конечно же, одна таблица уровня 1.

Общий размер таблицы страниц равен:

//размер внешней таблицы страниц	//общий размер таблиц уровня 2	//общий размер самых внутренних таблиц
1 * 2^8 * 4	2^5 * 2^8 *4	2^13 * 2^7 * 4	~4MB

Как легко заметить, двухуровневая и трехуровневая подкачка требуют гораздо меньше места, чем подкачка уровня 1. схема. И поскольку наше адресное пространство недостаточно велико, 3-уровневая подкачка работает не лучше, чем 2-уровневая подкачка. Из-за стоимости доступа к памяти гораздо логичнее выбрать двухуровневую схему подкачки для этого процесса.

Проблема 3

Каков размер страницы в такой системе? Объясните свой ответ (число без обоснования не будет засчитано).

Поскольку физические адреса имеют длину 44 бита, а размер страницы — 4 КБ, номер кадра страницы занимает 32 бита. Принимая во внимание 4 защитных бита, каждая запись таблицы страниц уровня 3 занимает (32+4) = 36 бит. Округление для выравнивания записей по байтам (словам) приведет к тому, что каждая запись будет потреблять 40 (64) бит или 5 (8) байтов. Для таблицы из 256 записей нам потребуется 1280 (2048) байт.

Таблица страниц верхнего уровня не должна предполагать, что таблицы страниц 2-го уровня выровнены по страницам. Итак, мы храним там полные физические адреса. К счастью, нам не нужны управляющие биты. Таким образом, каждая запись занимает не менее 44 бит (6 байтов для выравнивания по байтам, 8 байтов для выравнивания по словам). Таким образом, каждая таблица страниц верхнего уровня имеет размер 256*6 = 1536 байт (256 * 8 = 2048 байт).

Попытка воспользоваться выравниванием по 256 элементам для уменьшения размера элемента, вероятно, не стоит усилий. Сделать это было бы сложно; вам нужно будет написать новый распределитель памяти, который гарантирует такое выравнивание. Кроме того, мы не можем полностью уместить таблицу в выровненную область размером 1024 байта (44-10 = 34 бита на адрес, что потребовало бы более 4 байтов на запись), и округление размера до следующей степени двойки не спасло бы использовать любой размер, а не просто хранить указатели и использовать обычный распределитель.

Аналогично каждая запись в таблице страниц 2-го уровня представляет собой 44-битный физический указатель, 6 байтов (8 байтов) при выравнивании по байтам (словам). Таким образом, таблица с 16 элементами занимает 96 (128) байт. Таким образом, требуемое пространство составляет 1536 (2048) байт для таблицы страниц верхнего уровня + 96 (128) байт для одной таблицы страниц второго уровня + 1280 (2048) байт для одной таблицы страниц третьего уровня = 2912 (4224) байт. Поскольку процесс может уместиться ровно на 16 страницах, внутренняя фрагментация не тратит память впустую.

Таким образом, требуемое пространство составляет 1536 (2048) байт для таблицы страниц верхнего уровня + 3 * 96 (3 * 128) байт для 3 таблиц страниц второго уровня + 3 * 1280 (3 * 2048) для 3 таблиц третьего уровня. таблица страниц = 5664 (8576) байт.

Проблема 4

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

Решение:
Нужно решение.

Проблема 5

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

Решение:
Нужно решение.

Проблема 6

Рассмотрите следующий фрагмент кода, который умножает две матрицы: Предположим, что двоичный файл для выполнения этой функции помещается на одной странице, и стек также помещается на одной странице. Предположим далее, что для хранения целого числа требуется 4 байта. Вычислите количество промахов TLB, если размер страницы равен 4096, а TLB имеет 8 записей с замещающей политикой, состоящей из LRU.

Решение:
1024*(2+1024*1024) = 1073743872
Двоичный файл и стек умещаются на одной странице, поэтому каждый занимает одну запись в TLB. Пока функция работает, она постоянно обращается к двоичной странице и странице стека. Таким образом, две записи TLB для этих двух страниц будут все время находиться в TLB, а данные могут занимать только оставшиеся 6 записей TLB.

Мы предполагаем, что две записи уже находятся в TLB, когда функция начинает выполняться. Затем нам нужно рассмотреть только эти страницы данных.

Поскольку для хранения целого числа требуется 4 байта, а размер страницы составляет 4096 байт, для каждого массива требуется 1024 страницы. Предположим, что каждая строка массива хранится на одной странице. Тогда эти страницы можно представить в виде a[0..1023], b[0..1023], c[0..1023]: Страница a[0] содержит элементы a[0][0..1023], страница a[1] содержит элементы a[1][0..1023] и т. д.

Для фиксированного значения i, скажем, 0, функция выполняет цикл по j и k, у нас есть следующая ссылочная строка:

Для ссылочной строки (всего 1024 строки) a[0], c[0] приведут к двум промахам TLB. Поскольку доступ к a[0] и b[0] будет осуществляться через каждые четыре обращения к памяти, эти две страницы не будут заменены алгоритмом LRU. Для каждой страницы в b[0..1023] каждый раз при доступе к ней будет происходить один промах TLB. Таким образом, количество промахов TLB для второго внутреннего цикла равно
2+1024*1024 = 1048578.

Читайте также: