Реализация модели системы кеширования ОЗУ (Мини-учебник с ejudge = Чернокнижка)

Учебные материалы для 2 курсаГлавная страницаЗанятия по языку СиЗанятия попрограммированию вUnixМатериалы длядополнительного чтенияКонспекты занятий поязыку Си++Опции компилятора насервере (C)Опции компилятора насервере (C++)Стиль форматированияпрограммО вещественных числахО рекурсивном спускеО написании MakefileЗадание намоделирование кешаДокументация по STLСсылкиПамятка по работе в UnixЛекции по ОС для КазФМГУЗадание: реализация модели системыкеширования ОЗУВ данном задании необходимо реализовать программу,моделирующую работу кеш­памяти процессора (далеесимулятор кеша). Модель кеша должна поддерживатьследующие стратегии кеширования:полноассоциативный кеш и кеш прямого отображения;стратегии замещения: случайная ;стратегии записи: сквозная, отложенная.Параметры моделируемого кеша задаются вконфигурационном файле. В аргументах командной строкизадаются опции для симулятора кеша и имяконфигурационного файла. Трасса обращений к памятипоступает на стандартном потоке ввода.Симулятор кеша должен вывести на стандартный поток выводарезультаты моделирования в соответствии с опциями,переданными ему в командной строке.Параметры командной строкиСкомпилированная программа симулятора кеша должнаназываться cachesim. Должны поддерживаться опции: --dumpmemory, --statistics, --disable-cache, --print-config.Если указана опция --print-config, симулятор долженвывести на стандартный поток вывода параметры, заданные вконфигурационном файле, и завершить работу с кодомзавершения 0 (см. задачу c01).Если указана опция --dump-memory, симулятор долженраспечатать содержимое памяти после выполнения трассы.Если указана опция --statistics, должна выводитьсястатистика работы кеш­памяти.Если указана опция --disable-cache, кешированиеотключается, и модель кеширования не создается.Если указано несколько параметров командной строки,результаты работы выводятся в порядке --dump-memory, -statistics. Обязательным параметром командной строкиявляется путь к конфигурационному файлу. Примерыкомандной строки:cachesim --dump-memory trace.cfgcachesim --dump-memory --statistics trace.cfgcachesim trace.cfgКонфигурационный файлКонфигурационный файл — это текстовый файл. В текстовомфайле из байтов с кодами, меньшими ' ' допускаются толькобайты \r, \n, \t. Длина строки конфигурационного файла непревышает 1000 байт (с учетом символов­завершителей строки\r, \n). Комментарии в файле начинаются с символа '#' и идут доконца строки. После отбрасывания комментариев пробельныесимволы в конце строки игнорируются. Пустые строки вконфигурационном файле игнорируются.Непустые строки в конфигурационном файле имеютследующий вид:NAME=VALUEПеред NAME, между NAME и =, = и VALUE может находитьсяпроизвольное количество пробельных символов. NAME – этонепустая последовательность заглавных и строчных латинскихбукв, цифр и знаков '_' или '­', которая начинается с буквы или'_'. VALUE – это произвольная (возможно пустая)последовательность символов (включая пробел) до концастроки.Файл трассыФайл трассы — текстовый файл. В текстовом файле из байтов скодами, меньшими ' ' допускаются только байты \r, \n, \t. Длинастроки файла трассы не превышает 1000 байт (с учетомсимволов­завершителей строки \r, \n). Комментарии в файленачинаются с символа '#' и идут до конца строки. Послеотбрасывания комментариев пробельные символы в концестроки игнорируются. Пустые строки в файле игнорируются.Непустые строки в файле определяют трассу либо в кратком,либо в полном формате.Строка трассы в кратком формате имеет вид:OM ADDRГде O – это операция — символ 'R' или 'W', M – тип памяти –символ 'D' или 'I'. ADDR – это адрес в памяти, задаваемый вшестнадцатеричном виде и представимый как неотрицательноечисло в 32­битном целом типе.Строка трассы в полном формате имеет вид:OM ADDR SIZE VALUEГде дополнительно SIZE – это размер операции с памятью (1, 2,4 или 8), VALUE – знаковое целое число (в десятичном виде)соответствующего размера.Если для выполнения моделирования требуется трасса вполном формате, но на вход подается трасса в краткомформате, размер данных предполагается равным 1 байту, азначение — 0.Оперативная памятьРазмер оперативной памяти задается параметром memory_size.Размер оперативной памяти памяти не больше гигабайта ивыражается целым количеством килобайт. Например,memory_size = 65536задает размер памяти 64 килобайта.Параметр memory_read_time определяет количество тактов, закоторое выполняется чтение из ОЗУ. Параметрmemory_write_time определяет количество тактов, за котороевыполняется запись в ОЗУ. Параметр memory_width определяетмаксимальное количество байт, пересылаемых в/из ОЗУ заодну операцию и за указанное время. Если из памятисчитывается/в память записывается больше байт, чем значениепараметра memory_width, то чтение/запись будет требоватьпропорционально больше времени.Начальное значение памяти неизвестно. Целые числа хранятсяв памяти в порядке big­endian.КешПараметр cache_size задает общий размер кеш­памяти в байтах.Параметр block_size задает размер одного блока в байтах иможет принимать значения 16, 32, 64. Общий размер кешакратен размеру одного блока. Параметр associativity задает типассоциативности кеша и может принимать значения full дляполноассоциативного кеша и direct для кеша прямогоотображения.Для полноассоциативного кеша параметр replacement_strategyопределяет стратегию замещения и может принимать значенияrandom для случайного замещения, lfu для стратегии leastfrequently used, lru для стратегии least recently used. Стратегияlru заключается в замещении блока кеша, находящегося напоследнем месте в списке занятых блоков.При использовании стратегии lfu должны обрабатыватьсяследующие конфигурационные параметры: lfu_count_size –размер счетчика использований (в битах), счетчик работает снасыщением; lfu_init_value – начальное значение счетчикаиспользований при загрузке блока из ОЗУ; lfu_aging_interval –число операций чтения, после которого выполняется операция«старения»; lfu_aging_shift – количество бит, на которыесдвигается вправо значение счетчика при выполненииоперации «старения». При замещении наименее редкоиспользуемого блока кеша из блоков с минимальнымзначением счетчика использований выбирается случайное.Параметр write_strategy задает стратегию записи. Параметрможет принимать два значение: write­through для сквознойзаписи и write­back для отложенной записи. В случаеотложенной записи в ОЗУ записывается блок целиком.Параметр cache_read_time задает время выполнения чтения изкеша. Это время добавляется каждый раз при выполненииоперации чтения из кеша и в случае попадания, и в случаепромаха. В случае промаха, однако, добавляется еще и времячтения из нижележащей памяти.Параметр cache_write_time задает время выполнения записи вкеш. Это время добавляется каждый раз при выполненииоперации записи. В случае сквозной записи отдельнодобавляется время записи в память. В случае отложеннойзаписи время записи в память добавляется при выталкиваниигрязного блока из кеша.Для кеша со сквозной записью если при записи ячейка ненаходится в кеше, то блок не загружается из памяти в кеш. Длякеша с отложенной записью если при записи ячейка ненаходится в кеше, то блок загружается из памяти в кеш (сучетом времени загрузки из памяти).Случайные числаДля получения псевдослучайных чисел должны использоватьсяфункции srand и rand стандартной библиотеки. Параметр seedконфигурационного файла задает начальное значение длягенератора псевдослучайных чисел. Для получения целогопсевдослучайного числа, равномерно распределенного намножестве {0, 1, …, N – 1} должна использоваться формулаr = (int) (rand()/(RAND_MAX + 1.0) * N);Псевдослучайные числа, равномерно распределенные надругих множеств получаются отображением изпсевдослучайных чисел на указанном выше множестве.Вывод дампа памятиЕсли в командной строке указана опция ­­dump­memory, настандартный поток вывода должен быть напечатан дамппамяти в формате, показанном ниже.Первый столбец (8 шестнадцатеричных цифр ­ это адрес).Далее идут 16 столбцов ­ байты в шестнадцатеричном виде.Если значение байта не известно, выводится ??. В качествешестнадцатеричных цифр используйте заглавные буквы.Столбцы разделяются одним символом пробела.00000000 ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??00000010 00 00 00 C8 FF F0 ?? ?? ?? ?? ?? ?? ?? ?? ?? ??00000020 ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??00000030 ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??Вывод статистики выполнения трассыЕсли в командной строке указана опция ­­statistics, настандартный поток вывода должна быть напечатана статистикавыполнения трассы как показано ниже:clock count: CLOCK_COUNTreads: READSwrites: WRITESread hits: READ_HITScache block writes: CBWГде CLOCK_COUNT – общее количество тактов, которыепотребовались для выполнения операций с памятью в даннойтрассе. READS – общее количество операций чтения в даннойтрассе. WRITES – общее количество операций записи в даннойтрассе. READ_HITS – количество попаданий в кеш привыполнении операций чтения (только если кеш включен). CBW– количество операций записи блоков кеша в ОЗУ (только есликеш включен и для write­back кеша).Организация исходных файловИсходные файлы проекта должны находиться в каталогеcachesim. Архив этого каталога в формате .tar.gz сдается напроверку.Следование стилю оформления программ обязательно.В каталоге должен находится Makefile, оформленный всоответствии с требованиями, изложенными в методическомпособии.Общая структура проекта и заготовки некоторых файловдоступны в виде документации (сгенерировано Doxygen) иисходных файлов.Выбор между всеми возможными стратегиями реализациикеша (ассоциативность, стратегия замещения, стратегиязаписи) должен происходить на этапе создания объекта кеша вфункциях cache_create_* с помощью подстановоксоответствующих указателей на функции в структуруопераций. В реализациях операций не должны пристутствоватьусловные операторы и выражения, проверяющие стратегииреализации кеша. Для этого может потребоваться определитьдополнительную структуру CacheOps с указателями нафункции, которые настраиваются в зависимости от стратегииреализации кеша.Главный файл должен называться cachesim.c.Сообщения об ошибкахВсе сообщения об ошибках выводятся на стандартный потокошибок. Программа прекращает выполнение послеобнаружения первой ошибки.В случае, если аргументы командной строки не удовлетворяютспецификации должно выводиться сообщениеInvalid argumentsОшибки разбора конфигурационного файлаВ случае, если конфигурационный файл не может быть открытна чтение должна выводиться следующая ошибка. FILEзаменяется на имя файла, указанное в командной строке.Failed to open FILE for readingВ случае, если в строке LINE конфигурационного файла FILEбыла обнаружена ошибка разбора файла должно выводитьсяследующее сообщение. Строки в файле нумеруются с 1.Syntax error in line LINE of FILEВ случае, если конфигурационный параметр NAME ужеопределен должно выводиться следующее сообщениеDuplicate parameter NAME in FILELast modified: Friday, 21­Jun­2013 16:47:51 MSK Alexander Chernov.