Язык программирования Си Брайан Керниган, Деннис Ритчи 3е издание Версия 1 Table of Contents
 Скачать 2.33 Mb.
|
|
Упражнение 8.5. Модифицируйте fsize таким образом, чтобы можно было печатать остальную информацию, содержащуюся в узле inode. 8.7. Пример. Распределитель памяти В главе 5 был описан простой распределитель памяти, основанный на принципе стека. Версия, которую мы напишем здесь, не имеет ограничений: вызовы malloc и free могут выполняться в любом порядке; malloc делает запрос в операционную систему на выделение памяти тогда, когда она требуется. Эти программы иллюстрируют приемы, позволяющие получать машинно-зависимый код сравнительно машинно- независимым способом, и, кроме того, они могут служить примером применения таких средств языка, как структуры, объединения и typedef Никакого ранее скомпилированного массива фиксированного размера, из которого выделяются куски памяти, не будет. Функция malloc запрашивает память у операционной системы по мере надобности. Поскольку и другие действия программы могут вызывать запросы памяти, которые удовлетворяются независимо от этого распределителя памяти, пространство, которым заведует malloc , не обязательно представляет собой связный кусок памяти. Поэтому свободная память хранится в виде списка блоков. Каждый блок содержит размер, указатель на следующий блок и само пространство. Блоки в списке хранятся в порядке возрастания адресов памяти, при этом последний блок (с самым большим адресом) указывает на первый. При возникновении запроса на память просматривается список свободных блоков, пока не обнаружится достаточно большой блок. Такой алгоритм называется "поиском первого подходящего" в отличие от алгоритма "поиска наилучшего подходящего", который ищет наименьший блок из числа удовлетворяющих запросу. Если размер блока в точности соответствует требованиям, то такой блок исключается из списка и отдается в пользование. Если размер блока больше, чем требуется, от него отрезается нужная часть — она отдается пользователю, а ненужная оставляется в списке свободных блоков. Если блока достаточного размера не оказалось, то у операционной системы запрашивается еще один большой кусок памяти, который присоединяется к списку свободных блоков. Процедура освобождения сопряжена с прохождением по списку свободных блоков, поскольку нужно найти подходящее место для освобождаемого блока. Если подлежащий освобождению блок примыкает с какой-то стороны к одному из свободных блоков, то он объединяется с ним в один блок большего размера, чтобы по возможности уменьшить раздробленность (фрагментацию) памяти. Выполнение проверки, примыкают ли блоки друг к другу, не составляет труда, поскольку список свободных блоков всегда упорядочен по возрастанию адресов. Существует проблема, о которой мы уже упоминали в главе 5, состоящая в том, что память, выдаваемая функцией malloc , должна быть соответствующим образом выровнена с учетом объектов, которые будут в ней храниться. Хотя машины и отличаются друг от друга, но для каждой из них существует тип, предъявляющий самые большие требования на выравнивание, и, если по некоему адресу допускается размещение объекта этого типа, то по нему можно разместить и объекты всех других типов. На некоторых машинах таким самым "требовательным" типом является double , на других это может быть int или long Свободный блок содержит указатель на следующий блок в списке, свой размер и собственно свободное пространство. Указатель и размер представляют собой управляющую информацию и образуют так называемый "заголовок". Чтобы упростить выравнивание, все блоки создаются кратными размеру заголовка, а заголовок соответствующим образом выравнивается. Этого можно достичь, сконструировав объединение, которое будет содержать соответствующую заголовку структуру и самый требовательный в отношении выравнивания тип. Для конкретности мы выбрали тип long typedef long Align; /* для выравнивания по границе long */ union header { /* заголовок блока: */ struct { union header *ptr; /* след. блок в списке свободных */ unsigned size; /* размер этого блока */ } s; Align x; /* принудительное выравнивание блока */ }; typedef union header Header; Поле Align нигде не используется; оно необходимо только для того, чтобы каждый заголовок был выровнен по самому "худшему" варианту границы. Затребованное число символов округляется в malloc до целого числа единиц памяти размером в заголовок (именно это число и записывается в поле size (размер) в заголовке); кроме того, в блок входит еще одна единица памяти — сам заголовок. Указатель, возвращаемый функцией malloc , указывает на свободное пространство, а не на заголовок. Со свободным пространством пользователь может делать что угодно, но, если он будет писать что-либо за его пределами, то, вероятно, список разрушится. Поскольку память, управляемая функцией malloc , не обладает связностью, размеры блоков нельзя вычислить по указателям, и поэтому без поля, хранящего размер, нам не обойтись. Для организации начала работы используется переменная base. Если freep есть NULL (как это бывает при первом обращении к malloc ), создается "вырожденный" список свободного пространства; он содержит один блок нулевого размера с указателем на самого себя. Поиск свободного блока подходящего размера начинается с этого указателя ( freep ), т. е. с последнего найденного блока; такая стратегия помогает поддерживать список однородным. Если найденный блок окажется слишком большим, пользователю будет отдана его хвостовая часть; при этом потребуется только уточнить его размер в заголовке найденного свободного блока. В любом случае возвращаемый пользователю указатель является адресом свободного пространства, размещающегося в блоке непосредственно за заголовком. static Header base; /* пустой список для нач. запуска */ static Header *freep = NULL; /* начало в списке своб. блоков */ /* malloc: универсальный распределитель памяти */ void *malloc(unsigned nbytes) { Header *p, *prevp; Header *morecore(unsigned); unsigned nunits; nunits = (nbytes + sizeof (Header) - 1) / sizeof (Header) + 1; if ((prevp = freep) == NULL) { /* списка своб. памяти еще нет */ base.s.ptr = freep = prevp = &base; base.s.size = 0; } for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) { if (p->s.size >= nunits) { /* достаточно большой */ if (p->s.size == nunits) /* точно нужного размера */ prevp->s.ptr = p->s.ptr; else { /* отрезаем хвостовую часть */ p->s.size -= nunits; p += p->s.size; p->s.size = nunits; } freep = prevp; return (void *)(p+1); } if (p == freep) /* прошли полный цикл по списку */ if ((p = morecore(nunits)) == NULL) return NULL; /* больше памяти нет */ } } Функция morecore получает память от операционной системы. Детали того, как это делается, могут не совпадать в различных системах. Так как запрос памяти у системы — сравнительно дорогая операция, мы бы не хотели для этого каждый раз обращаться к malloc . Поэтому используется функция morecore, которая запрашивает не менее NALLOC единиц памяти; этот больший кусок памяти будет "нарезаться" потом по мере надобности. После установки в поле размера соответствующего значения функция morecore вызывает функцию free и тем самым включает полученный кусок в список свободных областей памяти. #define NALLOC 1024 /* миним. число единиц памяти для запроса */ /* morecore: запрашивает у системы дополнительную память */ static Header * morecore( unsigned nu) { char *cp, *sbrk(int); Header *up; if (nu < NALLOC) nu = NALLOC; ср = sbrk(nu * sizeof(Header)); if (cp == (char *) -1) /* больше памяти нет */ return NULL; up = (Header *) cp; up->s.size = nu; free((void *)(up+1)); return freep; } Системный вызов sbrk(n) в UNIXe возвращает указатель на n байт памяти или -1, если требуемого пространства не оказалось, хотя было бы лучше, если бы в последнем случае он возвращал NULL . Константу - 1 необходимо привести к типу char * , чтобы ее можно было сравнить с возвращаемым значением. Это еще один пример того, как операция приведения типа делает функцию относительно независимой от конкретного представления указателей на различных машинах. Есть, однако, одна "некорректность", состоящая в том, что сравниваются указатели на различные блоки, выдаваемые функцией sbrk . Такое сравнение не гарантировано стандартом, который позволяет сравнивать указатели лишь в пределах одного и того же массива. Таким образом, эта версия malloc верна только на тех машинах, в которых допускается сравнение любых указателей. В заключение рассмотрим функцию free . Она просматривает список свободной памяти, начиная с freep , чтобы подыскать место для вставляемого блока. Искомое место может оказаться или между блоками, или в начале списка, или в его конце. В любом случае, если подлежащий освобождению блок примыкает к соседнему блоку, он объединяется с ним в один блок. О чем еще осталось позаботиться, — так это о том, чтобы указатели указывали в нужные места и размеры блоков были правильными. /* free: включает блок в список свободной памяти */ void free(void *ap) { Header *bp, *p; bp = (Header *)ap -1; /* указатель на заголовок блока */ for (p=freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) break; /* освобождаем блок в начале или в конце */ if (bp + bp->s.size == p->s.ptr) { /* слить с верхним */ bp->s.size += p->s.ptr->s.size; /* соседом */ bp->s.ptr = p->s.ptr->s.ptr; } else bp->s.ptr = p->s.ptr; if (p + p->s.size == bp) { /* слить с нижним соседом */ p->s.size += bp->s.size; p->s.ptr = bp->s.ptr; } else p->s.ptr = bp; freep = p; } Хотя выделение памяти по своей сути — машинно-зависимая проблема, с ней можно справиться, что и иллюстрирует приведенная программа, в которой машинная зависимость упрятана в очень маленькой ее части. Что касается проблемы выравнивания, то мы разрешили ее с помощью typedef и union (предполагается, что sbrk дает подходящий в смысле выравнивания указатель). Операции приведения типов позволяют нам сделать явными преобразования типов и даже справиться с плохо спроектированным интерфейсом системы. Несмотря на то, что наши рассуждения касались распределения памяти, этот общий подход применим и в других ситуациях. Упражнение 8.6. Стандартная функция calloc(n, size) возвращает указатель на n элементов памяти размера size , заполненных нулями. Напишите свой вариант callос , пользуясь функцией malloc или модифицируя последнюю. Упражнение 8.7. Функция malloc допускает любой размер, никак не проверяя его на правдоподобие; free предполагает, что размер освобождаемого блока — правильный. Усовершенствуйте эти программы таким образом, чтобы они более тщательно контролировали ошибки. Упражнение 8.8. Напишите программу bfree(p, n) , освобождающую произвольный блок р , состоящий из n символов, путем включения его в список свободной памяти, поддерживаемый функциями malloc и free С помощью bfree пользователь должен иметь возможность в любое время добавить в список свободной памяти статический или внешний массив. А. Справочное руководство А 1. Введение Данное руководство описывает язык программирования Си, определенный 31 октября 1989 г. в соответствии с проектом, утвержденным в ANSI в качестве Американского национального стандарта для информационных систем: Язык программирования Си, Х3.159-1989 ("American National Standard for Information Systems — Programming Language C, X3.159-1989"). Это описание — лишь один из вариантов предлагаемого стандарта, а не сам стандарт, однако мы специально заботились о том, чтобы сделать его надежным руководством по языку. Настоящий документ в основном следует общей схеме описания, принятой в стандарте (публикация которого в свою очередь основывалась на первом издании этой книги), однако в организационном плане есть различия. Если не считать отклонений в названиях нескольких продуктов и отсутствия формальных определений лексем и препроцессора, грамматика языка здесь и грамматика в стандарте эквивалентны. Далее примечания (как и это) набираются с отступом от левого края страницы. В основном эти примечания касаются отличий стандарта от версии языка, описанной в первом издании этой книги, и от последующих нововведений в различных компиляторах. А 2. Соглашения о лексике Программа состоит из одной или нескольких единиц трансляции, хранящихся в виде файлов. Каждая такая единица проходит несколько фаз трансляции, описанных в А12. Начальные фазы осуществляют лексические преобразования нижнего уровня, выполняют директивы, заданные в программе строками, начинающимися со знака # , обрабатывают макроопределения и производят макрорасширения. По завершении работы препроцессора (А12) программа представляется в виде последовательности лексем. А 2.1. Лексемы (tokens) Существуют шесть классов лексем (или токенов): идентификаторы, ключевые слова, константы, строковые литералы, операторы и прочие разделители. Пробелы, горизонтальные и вертикальные табуляции, новые строки, переводы страницы и комментарии (имеющие общее название символы-разделители) рассматриваются компилятором только как разделители лексем и в остальном на результат трансляции влияния не оказывают. Любой из символов-разделителей годится, чтобы отделить друг от друга соседние идентификаторы, ключевые слова и константы. Если входной поток уже до некоторого символа разбит на лексемы, то следующей лексемой будет самая длинная строка, которая может быть лексемой. А 2.2. Комментарий Символы /* открывают комментарий, а символы */ закрывают его. Комментарии нельзя вкладывать друг в друга, их нельзя помещать внутрь строк или текстовых литералов. А 2.3. Идентификаторы Идентификатор — это последовательность букв и цифр. Первым символом должна быть буква; знак подчеркивания _ считается буквой. Буквы нижнего и верхнего регистров различаются. Идентификаторы могут иметь любую длину; для внутренних идентификаторов значимыми являются первые 31 символ; в некоторых реализациях принято большее число значимых символов. К внутренним идентификаторам относятся имена макросов и все другие имена, не имеющие внешних связей (А11.2). На идентификаторы с внешними связями могут накладываться большие ограничения: иногда воспринимаются не более шести первых символов и могут не различаться буквы верхнего и нижнего регистров. А 2.4. Ключевые слова Следующие идентификаторы зарезервированы в качестве ключевых слов и в другом смысле использоваться не могут: auto double int struct break else long switch case enum register typedef char extern return union const float short unsigned continue for signed void default goto sizeof volatile do if static while В некоторых реализациях резервируются также слова fortran и asm Ключевые слова const , signed и volatile впервые появились в стандарте ANSI; enum и void — новые по отношению к первому изданию книги, но уже использовались; ранее зарезервированное entry нигде не использовалось и поэтому более не резервируется. А 2.5. Константы Существует несколько видов констант. Каждая имеет свой тип данных; базовые типы рассматриваются в А4.2. константа: целая-канстанта символьная-константа константа-с-плавающей-точкой константа-перечисление А 2.5.1. Целые константы Целая константа, состоящая из последовательности цифр, воспринимается как восьмеричная, если она начинается с 0 (цифры нуль), и как десятичная в противном случае. Восьмеричная константа не содержит цифр 8 и 9 . Последовательность цифр, перед которой стоят 0х или 0Х , рассматривается как шестнадцатеричное целое. В шестнадцатеричные цифры включены буквы от а (или А ) до f (или F ) со значениями от 10 до 15. Целая константа может быть записана с буквой-суффиксом u (или U ) для спецификации ее как беззнаковой константы. Она также может быть с буквой-суффиксом l (или L ) для указания, что она имеет тип long Тип целой константы зависит от ее вида, значения и суффикса (о типах см. А4). Если константа — десятичная и не имеет суффикса, то она принимает первый из следующих типов, который годится для представления ее значения: int , long int , unsigned long int . Восьмеричная или шестнадцатеричная константа без суффикса принимает первый возможный из типов: int , unsigned int , long int , unsigned long int . Если константа имеет суффикс u или U , то она принимает первый возможный из типов: unsigned int , unsigned long int . Если константа имеет суффикс l или L ,то она принимает первый возможный из типов: long int , unsigned long int . Если константа имеет суффикс ul или UL , то она принимает тип unsigned long int Типы целых констант получили существенное развитие в сравнении с первой редакцией языка, в которой большие целые имели просто тип long . Суффиксы U и u введены впервые. А 2.5.2. Символьные константы Символьная константа — это последовательность из одной или нескольких символов, заключенная в одиночные кавычки (например 'х' ). Если внутри одиночных кавычек расположен один символ, значением константы является числовое значение этого символа в кодировке, принятой на данной машине. Значение константы с несколькими символами зависит от реализации. Символьная константа не может содержать в себе одиночную кавычку ' или символ новой строки; чтобы изобразить их и некоторые другие символы, могут быть использованы эскейп-последовательности: новая строка (newline, linefeed) NL (LF) \n горизонтальная табуляция (horisontal tab) HT \t вертикальная табуляция (vertical tab) VT \v возврат на шаг (backspace) BS \b возврат каретки (carriage return) CR \r перевод страницы (formfeed) FF \f сигнал звонок (audible alert, bell) BEL \a обратная наклонная черта (backslash) \ \\ знак вопроса (question mark) ? \? одиночная кавычка (single quote) \' двойная кавычка (double quote) \" восьмеричный код (octal number) ooo \ooo шестнадцатеричный код (hex number) hh \xhh Эскейп-последовательность \ооо состоит из обратной наклонной черты, за которой следуют одна, две или три восьмеричные цифры, специфицирующие значение желаемого символа. Наиболее частым примером такой конструкции является \0 (за которой не следует цифра); она специфицирует NULL -символ. Эскейп- последовательность \xhh состоит из обратной наклонной черты с буквой х , за которыми следуют шестнадцатеричные цифры, специфицирующие значение желаемого символа. На количество цифр нет ограничений, но результат будет не определен, если значение полученного символа превысит значение самого "большого" из допустимых символов. Если в данной реализации тип char трактуется как число со знаком, то значение и в восьмеричной, и в шестнадцатеричнои эскейп-последовательности получается с помощью "распространения знака", как если бы выполнялась операция приведения к типу char . Если за \ не следует ни один из перечисленных выше символов, результат не определен. В некоторых реализациях имеется расширенный набор символов, который не может быть охвачен типом char . Константа для такого набора пишется с буквой L впереди (например, L'х' ) и называется расширенной символьной константой. Такая константа имеет тип wchar_t (целочисленный тип, определенный в стандартном заголовочном файле ). Как и в случае обычных символьных констант, здесь также возможны восьмеричные и шестнадцатеричные эскейп-последовательности; если специфицированное значение превысит тип wchar_t , результат будет не определен. Некоторые из приведенных эскейп-последовательностей новые (шестнадцатеричные в частности). Новым является и расширенный тип для символов. Наборам символов, обычно используемым в |