Преобразование виртуального адреса в физический

[baldr]

Вот описание принципа...
http://www.intuit.ru/department/os/osintro/9/osintro_9.html
Собственно вопрос вот в чем: объясните подробнее механизм работы с инвертированной таблицей страниц?
Как я понимаю, в этой таблице у нас содержатся номера страниц, находящихся в соответствующих страницах физческой памяти. Зачем нам нужна здесь хэш-таблица? что в ней содержится и что будет ее ключом?
Сижу, туплю......
Срочно надо. Заранее спасибо.

[RXL]

Хеш, он и в Африке - хеш... Временные копии хранимых в основной памяти элементов таблиц. Ключем в ней будет часть виртуального адреса.

Я не стал читать сие - работу таблиц в x86 я и так знаю. Вот что я не понял: что есть "инвертированной таблицей страниц"? Что ты под этим понимаешь?

[baldr]

Цитирую: "В этой таблице содержится по одной записи на каждый страничный кадр физической памяти.". Может, она как-то по-другому в науке обзывается?
RXL, моя ICQ 164208732 - если ты не занят - объясни быстренько?

[RXL]

Прочел все-таки этот абзац. Пустышка - ноль слов.

В этой таблице содержится по одной записи на каждый страничный кадр физической памяти.

Непрошибаемая логика... Оно же так и есть в реальности. И что здесь инвертированого?

Существенно, что достаточно одной таблицы для всех процессов.

Ну, если сделать полное соответсвие физической и виртуальной для всех процессов, то получим или супер-dos, или, рано или поздно, не хватит и 64-х бит адреса для всех процессов.

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

Красиво излагает. Только последний параметер в не влияет на размер таблицы (при SMP). А что такое "размер ... процессоров"? Кул, блин!

"Интернет-Университет Информационных Технологий"... Мощно!

Если кто считает, что я тут в корне не прав, то пишите - обсудим.

[baldr]

Вот, нашел симпатичную ссылку
http://www.cne.gmu.edu/workbenches/vmsim/vm.html
Вроде понятнее стало...

[RXL]

Как я понял, в инвертированной таблице элементы упорядочены по номеру физической страницы, а поиск осуществляется по номеру виртуальной страницы (с учетом доп. информации: pid и т.д.). Искомая страница либо есть в таблице (а сооотв. и в памяти), либо ее нет (задача целиком ложмится на менеджер вирт. памяти).

[baldr]

Ну а как хэш-то выглядит??

[baldr]

Вот, нашел даже детальное описание...
http://www.cs.berkeley.edu/~kamil/sp04/040104.pdf
Вроде, понял что-то.....

[RXL]

Все равно там нет четкого и ясного описания алгоритма. Много вопросов остается именно по хешу.
Хеш-ф-ия выдает двоичную последовательность длиной N. В тексте указано, что эта последовательность напрямую адресует элемент таблицы страниц, которые, в свою очередь, связаны в однонаправленный список.
Т.к. между последовательностью и номер элемента нет никакой логической связи, то я делаю след. предположение, что менеджер вирт. памяти сам вычисляет ту же хеш-ф-ию и подставляет новую страницу в нужное место. Т.е., есть искуственная зависимость между результатом хеш-ф-ии и привязкой виртуальной страницы к физической (для первой страницы в цепочке). При N=16 первые 256кБ физ. памяти жестко привязаны к хеш-ф-ии, а длина цепочки может достичь 2^(разрядность_адреса - log2(hfpvth_cnhfybws) - N). Для 64бит адреса, 4к страницы и N == 16 получаем цепочку длиной 2^36 для 2^64 физической памяти. Для меньшего объема физ. памяти цепочка будет короче, но разброс адресов вирт. памяти будет неудобным.

[baldr]

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

[npak]

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

Это не хэш-таблица.  Это просто список пар, отсортированный по первому элементу пары.  В хэш-таблице другой принцип.

Хэш-функция вычисляет некоторый набор битов, причём для близких значений аргументов (например, последовательные сегменты виртуальной памяти) наборы битов далеко разнесены.  Полученный набор битов интерпретируется как индекс в массиве записей.  В большинстве практических применений размер значения хэш-функции меньше размера аргумента (например, номер страницы на 32-х битном процессоре содержит 20 бит, значение хэш-функции 10-12 бит).  По этой причине может случиться коллизия -- значения хэш-функции совпадают для двух разных значений аргументов.  Это не приятно, но не смертельно.

Как работает хэш-таблица.  Таблица конечного размера, значение, возвращаемое хэш-функцией, не выходит за границу таблицы.

1.  Добавление новой записи.  Взять ключ, вычислить индекс ( = значение хэш-функции для ключа).  Посмотреть, есть ли запись в таблице по этому индексу.  Если нет, то поместить запись по вычисленнуму индексу.  Если есть (то есть произошла коллизия -- для какого-то ещё ключа хэш-функция вычислила этот индекс), то дальнейшие операции зависят от реализации.  Это называется "стратегия разрешения коллизий".  В таблице, упомянутой в статье, используется такой приём.  Запись преобразуется в односвязный список, все записи, которые соответствуют индексу с коллизией, добавляются в список.  В статье говорится, что на практике длина списка редко превышает 2.  Если в таблице слишком много коллизий или есть длинные списки, то таблицу могут "перетряхнуть", то есть увеличить размер таблицы и перевычислить индексы для существующих записей.  После перетряхивания, как правило, получается другой набор коллизий, так как значение хэш-функции привязано к размеру таблицы.
2.  Поиск записи.  Взять ключ, вычислить индекс ( = значение хэш-функции для ключа).  по индексу найти, что хранится в таблице.  Если по индексу записи нет, значит для указанного ключа ничего нет.  Если по индексу есть запись, то вернуть запись.  Если по индексу находится список, то пробежать по списку и найти запись, которая соответствует ключу.

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

В твоём случае отсортированного списка число операций для поиска значения требует log(размер таблицы): если в таблице 1000 записей, то требуется в среднем 10 операций сравнения.  Для системы адресации это неприемлимо много. 

[RXL]

В доках хеш-таблица не описана. Только по первой ссылке упоминается.

[baldr]

То есть, вид хэш-функции зависит от размера таблицы?
У меня следующие условия:
* организация виртуальной памяти – страничная, с инвертированной таблицей страниц,
* разрядность виртуального адреса – 20,
* разрядность физической страницы – 10,
* количество физических страниц в таблице страниц – 4,
* объем оперативной памяти – 8 физических страниц.
Как же строится хэш-функция? Ключом будет адрес виртуальной страницы. А как по ней вычислить индекс?
Так как нужен, в основном, алгоритм, то последним решением может стать просто использование std::map , но мне это не нравится.

[npak]

То есть, вид хэш-функции зависит от размера таблицы?
У меня следующие условия:
* организация виртуальной памяти – страничная, с инвертированной таблицей страниц,
* разрядность виртуального адреса – 20,
* разрядность физической страницы – 10,
* количество физических страниц в таблице страниц – 4,
* объем оперативной памяти – 8 физических страниц.
Как же строится хэш-функция? Ключом будет адрес виртуальной страницы. А как по ней вычислить индекс?
Так как нужен, в основном, алгоритм, то последним решением может стать просто использование std::map , но мне это не нравится.

разрядность страницы 10 -- это 2^10 (1024) байт?   то есть размер ОЗУ 8 килобайт? 

Получается, что на каждый процесс нужна таблица из 8-ми записей, то есть 8*(10 + 3) = 104 бита.  10 бит на номер страницы виртуальной памяти, 3 бита на номер страницы физической памяти. 

Я думаю, что можно использовать отсортированный массив.  В случае обычного дихотомического поиска требуется три ( log 8 ) обращения к таблице, что терпимо.  Можно обойтись без хэш-таблицы, ты больше потеряешь на вычислении хэш-функции.

[baldr]

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

[npak]

Пример простой быстрой хэш-функции http://www.isthe.com/chongo/tech/comp/fnv/

Код:

#define FNV_prime ((unsigned int)16777619)
#define FNV_offset_basis ((unsigned int)2166136261)
#define STEP(state,octet)                       \
    state *= FNV_prime;                         \
    state ^= octet;                             \

#define FNV_HASH_10(result, val)                \
    {                                           \
        result = FNV_offset_basis;              \
        STEP(result, val & 0xff);               \
        STEP(result, (val >> 8) & 0xff);        \
    }                                           \

#define FOLD(val, table_size) val %= table_size

#define FNV_HASH_TABLE_INDEX_10(result, val, table_size)   \
    FNV_HASH_10(result, val)                            \
    FOLD(result, table_size)                            \

Реализовано через макросы для максимальной эффективности (дабы не тратить время на вызов функции).

Для 10-битного номера страницы индекс в таблице вычисляется так.

Код:

    unsigned int index;
    FNV_HASH_TABLE_INDEX_10(index, pagenum, table_size);

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

Код:

#include <stdio.h>

#define FNV_prime ((unsigned int)16777619)
#define FNV_offset_basis ((unsigned int)2166136261)
#define STEP(state,octet)                       \
    state *= FNV_prime;                         \
    state ^= octet;                             \

#define FNV_HASH_10(result, val)                \
    {                                           \
        result = FNV_offset_basis;              \
        STEP(result, val & 0xff);               \
        STEP(result, (val >> 8) & 0xff);        \
    }                                           \

#define FOLD(val, table_size) val %= table_size

#define FNV_HASH_TABLE_INDEX_10(result, val, table_size)   \
    FNV_HASH_10(result, val)                            \
    FOLD(result, table_size)                            \


#define TABLE_SIZE 13

int main()
{
    unsigned int hash;
    unsigned int i;
    int table[TABLE_SIZE];

    for (i = 0; i < TABLE_SIZE; i++)
    {
        table[i] = 0;
    }
    for ( i = 0; i < 1024; i++)
    {
        FNV_HASH_TABLE_INDEX_10(hash, i, TABLE_SIZE);
        ++ table[hash];
        printf("hash(%d) == %d\n", i, hash);
    }
    for (i = 0; i < TABLE_SIZE; i++)
    {
        printf("table[%d] = %d\n", i, table[i]);
    }
    return 0;
}

Размер таблицы подобран хорошо, если соседним страницам соответствуют разные хэш-коды, и значения индексов равномерно распределены.

[npak]

Всё то же самое, но на Си++

Код:

#include <iostream>

const unsigned int FNV_prime = ((unsigned int)16777619);
const unsigned int FNV_offset_basis = ((unsigned int)2166136261);

inline unsigned int STEP(unsigned int& state, unsigned char octet)
{
    state *= FNV_prime;
    state ^= octet;
}

inline unsigned int FNV_HASH_10(unsigned short val)
{                 
    unsigned int result = FNV_offset_basis;
    STEP(result, val & 0xff);
    STEP(result, (val >> 8) & 0xff);
    return result;
}

inline unsigned int FOLD(unsigned int val, unsigned int table_size)
{
    return val % table_size;
}

inline unsigned int FNV_HASH_TABLE_INDEX_10(unsigned short val, unsigned int table_size)
{
    return FOLD(FNV_HASH_10(val), table_size);
}


const unsigned int TABLE_SIZE  = 13;

int main()
{
    unsigned int hash;
    unsigned int i;
    int table[TABLE_SIZE];

    for (i = 0; i < TABLE_SIZE; i++)
    {
        table[i] = 0;
    }
    for ( i = 0; i < 1024; i++)
    {
        hash = FNV_HASH_TABLE_INDEX_10(i, TABLE_SIZE);
        ++ table[hash];
        std::cout << "hash(" << i << ") == " << hash << std::endl;
    }
    for (i = 0; i < TABLE_SIZE; i++)
    {
        std::cout << "table[" << i << "] == " << table[i] << std::endl;
    }
    return 0;
}

[RXL]

Мое видение.

Код:

#define ADDRESS_BITS  32

#define PAGE_BITS  20
#define PAGES  (1 << PAGE_BITS)

#define OFFSET_BITS (ADDRESS_BITS - PAGE_BITS)

#define HASH_BITS  8
#define HASH_SIZE  (1 << HASH_BITS)

// пример ф-ии
#define HASH_FUNC(vp) ((vp ^ (vp >> 8) ^ (vp >> 16)) & (HASH_SIZE - 1))

#define GET_OFFSET(a) (a & ((1 << OFFSET_BITS) - 1))
#define GET_PAGE(a) ((a >> OFFSET_BITS) & (PAGES - 1))


struct table
  {
    uint pid;
    uint virtual_page;
    uint next;
  };


uint hash_table[HASH_SIZE];

struct table inverted_table[PAGES];


uint get_phys_page(uint virt_addr, uint pid)
{
  uint vp = GET_PAGE(virt_addr);
  uint p;

  for (
    p = hash_table[HASH_FUNC(vp)]; /* получение первой страницы в списке */
    p != -1; /* условно - (-1) - неверный номер страницы */
    p = inverted_table[p].next /* новер следующей страницы */
    )
      if (inverted_table[p].virtual_page == vp && inverted_table[p].pid == pid) return p;
  return -1;
}

[baldr]

Нам все равно надо будет постоянно подгружать страницы...
Поскольку число страниц в памяти ( 8 ) все равно гораздо меньше числа возможных страниц (1024), то в случае коллизий можно загружать новую на место старой. Я прав? В таком случае next будет не нужен.
Хэш-таблицу тоже можно не строить, раз ее можно вычислить (а вообще если длина этой таблицы равна количеству виртуальных страниц - то это можно реализовать и обычным методом - получается это обычная таблица страниц  :? ).
---
Вот сейчас я подумал - зачем такие сложные вычисления, если можно сделать проще:
frame_number=VirtualPage % TABLE_SIZE;
Это тоже хэш-функция. Вероятность коллизии примерно=1- (TABLE_SIZE+1) / MAXVirtPages;
ХМ.

[RXL]

Нет! Хеш-таблица преобразует хеш-последовательность в номер первой страницы в цепочке, т.к. прямой связи тут нет - таблица то обратная и индексировать ее виртуальным адресом нет возможности. Т.е. это необходимый посредник. И число элементов в хеш-таблице не равно кол-ву вирт. страниц - для это существует хеш-ф-ия. Кстати, да бы сократить путаницу (hash!) лучше назвать хеш-таблицу ассоциативной.

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

[baldr]

Вот я еще тут не понимаю:
Для двух страниц имеется одинаковое значение хэш-функции...
То есть, для страницы A хэш-функция выдаст физ.страницу a. Но для страницы B она выдаст опять же a. Тогда мы, когда ищем страницу B в памяти, получаем адрес a, в котором уже записана страница A. Я правильно понимаю, что мы записываем страницу B в любое другое место b, но в a.next мы записываем b. Но b уже соответствует вирт.странице C, которую тоже приходится потом записывать в другое место...
Это ж накапливается! Что-то тут не так...

[Finch]

Давайте посмотрим как винда распределяет адресное простраство. Всего дается 4 гигабайта на один процесс в виртуальном адресном пространстве. Из них 2 нижних гигабайта для пользовательского приложения. 2 верхних гигабайта винда забирает себе. У Рихтера написано, что это соотношение можно поменять как 3+1. Все стандартные библиотеки садятся на строго отведенные адреса. Содержимое кодовых страниц нельзя менять в пользовательском режиме. Значит в принципе в физическом адресном пространстве код библиотек может хранится в единственном экземпляре, подставляться в каждый процесс как его единственная копия. Различия будут только у страниц в которых хранятся переменные библиотек для каждого процесса отдельно.
Если не делать специальных установок, то код программы начинается с адреса 0x00400000.
Я бы хэш функцию выбрал бы очень сильно зависяшию от ID процесса. Плюс зависяшию от номера модуля стандартных библиотек. Т.е. приходит на вход хэш функции виртуальных адрес. Смотрю к какой области он относится. Если область кода библиотек, то  хэш строится по ID модуля библиотеки. Иначе по ID процесса.

[baldr]

Я объясню смысл зачем мне это надо... Имеется задание:
------
Модель преобразования виртуального адреса в физический адрес.
Исходные данные:
* организация виртуальной памяти – страничная, с инвертированной таблицей страниц,
* разрядность виртуального адреса – 20,
* разрядность физической страницы – 10,
* количество физических страниц в таблице страниц – 4,
* объем оперативной памяти – 8 физических страниц,
* виртуальный адрес вводится с клавиатуры.
Результаты работы модели должны включать:
•   виртуальный адрес,
•   физический адрес,
•   содержимое хеш-таблицы и таблицы страниц.
---
После всего, что мы тут обсудили, я пришел к следующему:

Код:

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 8
#define MAX_ADDRESS 1048576

int table [TABLE_SIZE];

// Hash function
#define FNV_prime ((unsigned int)16777619)
#define FNV_offset_basis ((unsigned int)2166136261)
#define STEP(state,octet)                       \
    state *= FNV_prime;                         \
    state ^= octet;                             \

#define FNV_HASH_10(result, val)                \
    {                                           \
        result = FNV_offset_basis;              \
        STEP(result, val & 0xff);               \
        STEP(result, (val >> 8) & 0xff);        \
    }                                           \

#define FOLD(val, table_size) val %= table_size

#define FNV_HASH_TABLE_INDEX_10(result, val, table_size)   \
    FNV_HASH_10(result, val)                            \
    FOLD(result, table_size)                            \

// end of hash function

void main()
{
    long i;
     for (i=0; i<TABLE_SIZE; i++) table[i]=-1;
    int exiter=0;
    char st[100];
    unsigned int fn;
    printf("\n\n");
    while (exiter==0)
    {
        printf("Enter the virtual address from 0 to %.0f (decimal) (Enter to exit): ", float(MAX_ADDRESS));
        gets(st);
        if (exiter=(st[0]==0)) break;
        long addr=atol(st);
        if (addr<0||addr>MAX_ADDRESS) continue;
        int vp=addr>>10;
        int offset=addr&&1024;
        FNV_HASH_TABLE_INDEX_10(fn, vp, TABLE_SIZE);
        table[fn]=vp;
        addr=long(fn)<<10|offset;
        printf("Physical address is %.0f \n", float(addr));
    }
    printf("\nHash table:");
    for (i=0; i<1024; i++)
    {
        FNV_HASH_TABLE_INDEX_10(fn, i, TABLE_SIZE);
        printf("%d ", fn);
    }
    printf("\nInverted page table:\n");
    for (i=0; i<TABLE_SIZE; i++)
    {
        printf("%d ", table[i]);
    }
}

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

Что здесь неправильного?

[RXL]

Вот я еще тут не понимаю:
Для двух страниц имеется одинаковое значение хэш-функции...

Я вижу, ты так и не понял, что такое хеш-функция?
Я дам такое определение (возможно есть более точное): это ф-ия, которая, на одну и ту же входную последовательность бит, выдает один и тот же результат. Кроме того, результат, вне зависимости от входной последовательности, имеет постоянную длину в битах. Входная последовательность может быть как фиксированного, так и переменного размера - зависит от алгоритма. Востановить входную последовательность из результат нельзя.
Для входной последовательности фиксированного размера результат, как правило, короче.
Применяется как контрольный код (напр. CRC16, MD5), ключ для ассоциативного поиска (наш случай!) и, возможно, где-то еще.
Аппаратно вычисляемые хеш-ф-ии, обычно, используют простейшие, быстровыполняемые операции: xor, сдвиг, суммирование, реже - умножение. Деление, степени, логарифмы - слишком сложные и медленные ф-ии. Но, это уже лирика...

Отсюда: один и тот же результат может дать несколько различных входных последовательностей.

Результат используется не для указания конкретной страницы (первая страница в списке - частный случай), а указания цепочки, в которой поиск осуществляется последовательным перебором.

В модели с прямым табличным преобразованием (как в x86) возможно несколько виртуальных адресов в различных таблицах на одну и ту же физическую страницу.

При использовании модели с инвертированной таблицей страниц у физической страницы может быть только один виртуальный адрес. Как на таких процессорах реализуют совместное использование одной физ. страницы - я не знаю - надо читать доки. Кстати, что-нибудь знает PowerPC?

Что здесь неправильного?

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

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

Такое упрощение не вяжется с заданием.