рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Алгоритмы динамического управления памятью

Алгоритмы динамического управления памятью - раздел История, История операционных систем При Динамическом Выделении Памяти Запросы На Выделение Памяти Формирую...

При динамическом выделении памяти запросы на выделение памяти формируются во время исполнения задачи. Динамическое выделение, таким образом, противопоставляется статическому, когда запросы формируют­ся на этапе компиляции программы. В конечном итоге, и те, и другие запросы нередко обрабатываются одним и тем же алгоритмом выделения памяти в ядре ОС. Но во многих случаях статическое выделение можно реализовать намного более простыми способами, чем динамическое. Главная сложность здесь в том, что при статическом выделении кажется неестественной — и поэтому редко требуется — возможность отказаться от ранее выделенной памяти. При динамическом же распределении час­то требуется предоставить возможность отказываться от запрошенных блоков так, чтобы освобожденная память могла использоваться для удов­летворения последующих запросов. Таким образом, динамический рас­пределитель вместо простой границы между занятой и свободной памя­тью (которой достаточно в простых случаях статического распределения) вынужден хранить список возможно несвязных областей свободной па­мяти, называемый пулом или кучей.

Многие последовательности запросов памяти и отказов от нее могут привести к тому, что вся доступная память будет разбита на блоки ма­ленького размера, и попытка выделения большого блока завершится не­удачей, даже если сумма длин доступных маленьких блоков намного больше требуемой. Это явление называется фрагментацией памяти. Иногда используют более точный термин — внешняя фрагмен­тация (что такое внутренняя фрагментация будет рассказано далее). Кроме того, большое количество блоков требует длительного поиска. Существует также много мелких трудностей разного рода. К счастью, человечество занимается проблемой распределения памяти уже давно, и найдено много хороших или приемлемых решений.

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

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

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

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

Впрочем, случайные запросы — далеко не худший вариант. Даже не зная Деталей стратегии управления кучей, довольно легко построить програм­му, которая "испортит жизнь" многим распространенным алгоритмам.

Приведенный пример построен на том предположении, что система выделяет нам блоки памяти, размер которых соответствует запрошенному с точности до байта. Если же минимальная единица выделения равна 32 байтам, ника­кой внешней фрагментации наш пример не вызовет: на каждый запрос бу­дет выделяться один блок. Но при этом мы столкнемся с обратной пробле­мой, которая называется внутренней фрагментацией: если система умеет выделять только блоки, кратные 32 байтам, а нам реально нужно 15 или 47 байт, то 17 байт на блок окажутся, потеряны.

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

1 Ns

ной будет------, где N— количество выделенных блоков, s — размер еди-

2 N1

ницы выделения, а 7 — средний размер блока. Упростив эту формулу, мы получим выражение для величины потерь: ^J , т. е. потери линейно растут с увеличением размера единицы выделения.

Если средний размер блока сравним с единицей выделения, наша формула теряет точность, но все равно дает хорошую оценку порядка величины потерь. Так, если s = 7, наша формула дает 50% потерь, что вполне согласуется со здравым смыслом: если запрашиваемый блок чуть короче минимально возможного, теряется только это "чуть"; зато если он чуть длиннее, то для него отводится два минимальных блока, один из которых теряется почти весь. Точная величина потерь определяется распределением запрашиваемых блоков по длине, но мы предпочитаем оставить вывод точной формулы лю­бопытному читателю.

Варианты алгоритмов распределения памяти исследовались еще в 50-е годы. I Итоги многолетнего изучения этой проблемы приведены в [Кнут 2000] и многих других учебниках.

Обычно все свободные блоки памяти объединяются в двунаправленный свя­занный список. Список должен быть двунаправленным для того, чтобы из него в любой момент можно было извлечь любой блок. Впрочем, если все действия по извлечению блока производятся после поиска, то можно слегка , усложнить процедуру поиска и всегда сохранять указатель на предыдущий блок. Это решает проблему извлечения и можно ограничиться однонаправ­ленным списком. Беда только в том, что многие алгоритмы при объедине­нии свободных блоков извлекают их из списка в соответствии с адресом, поэтому для таких алгоритмов двунаправленный список остро необходим. Поиск в списке может вестись тремя способами: до нахождения первого подходящего (first fit) блока, до блока, размер которого ближе всего к заданному - наиболее подходящего (best fit), и, наконец, до нахождения самого большого блока, наименее подходящего (worst fit).

Использование стратегии worst fit имеет смысл разве что в сочетании с сортировкой списка по убыванию размера. Это может ускорить выделение па­мяти (всегда берется первый блок, а если он недостаточно велик, мы с чистой совестью можем сообщить, что свободной памяти нет), но создает проблемы при освобождении блоков: время вставки в отсортированный список пропорционально О (л), где п — размер списка.

Помещать блоки в отсортированный массив еще хуже — время вставки ста­новится О (л + log(fl)) и появляется ограничение на количество блоков. Ис­пользование хэш-таблиц или двоичных деревьев требует накладных расходов и усложнений программы, которые себя в итоге не оправдывают. На прак­тике стратегия worst fit используется при размещении пространства в фай­ловых системах, например в HPFS, но ни одного примера ее использования для распределения оперативной памяти автору неизвестно. Чаще всего применяют несортированный список. Для нахождения наиболее подходящего мы обязаны просматривать весь список, в то время как первый подходящий может оказаться в любом месте, и среднее время поиска будет меньше. Насколько меньше — зависит от отношения количества подходя­щих блоков к общему количеству. (Читатели, знакомые с теорией вероятно­сти, могут самостоятельно вычислить эту зависимость.) В общем случае best fit увеличивает фрагментацию памяти. Действительно, если мы нашли блок с размером больше заданного, мы должны отделить "хвост" и пометить его как новый свободный блок. Понятно, что в случае best fit средний размер этого "хвоста" будет маленьким, и мы в итоге полу­чим большое количество мелких блоков, которые невозможно объединить, так как пространство между ними занято.

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

При использовании first fit с линейным двунаправленным списком воз­никает специфическая проблема. Если каждый раз просматривать спи­сок с одного и того же места, то большие блоки, расположенные ближе к началу, будут чаще удаляться. Соответственно, мелкие блоки будут скапливаться в начале списка, что увеличит среднее время поиска. Простой способ борьбы с этим явлением состоит в том, чтобы просматривать список то в одном направлении, то в другом. Более ради­кальный и еще более простой метод заключается в следующем: список делается кольцевым, и каждый поиск начинается с того места, где мы остановились в прошлый раз. В это же место добавляются освободив­шиеся блоки. В результате список очень эффективно перемешивается и никакой "антисортировки" не возникает.

Разработчик программы динамического распределения памяти обязан ре­шить еще одну важную проблему, а именно — объединение свободных бло­ков. Действительно, обидно, если мы имеем сто свободных блоков по одному килобайту и не можем сделать из них один блок в 100 килобайт. Но если все эти блоки расположены в памяти один за другим, а мы не можем их при этом объединить — это просто унизительно.

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

Представим себе для начала, что все, что мы знаем о блоке, — это его начальный адрес и размер. Легко понять, что это очень плохая ситуация. Действительно, для объединения блока с соседями мы должны найти их в списке свободных, или же убедиться, что там их нет. Для этого мы должны просмотреть весь список. Как одну из идей мозгового штурма можно выдвинуть предложение сортировать список свободных блоков по адресу.

Гораздо проще запоминать в дескрипторе блока указатели на дескрипторы соседних блоков. Немного развив эту идею, мы приходим к методу, который называется алгоритмом парных меток и состоит в том, мы добавляем к каждому блоку по два слова памяти. Именно слова не байта. Дело в том, что требуется добавить достаточно места, что хранить в нем размер блока в байтах или словах. Обычно такое число занимает столько же места, сколько и адрес, а размер слова обычно равен размеру адреса. На х86 в реальном режиме это не так, но это вообще довольно странный процессор.

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

Представим, что мы освобождаем блок с адресом addr. Считаем, addr имеет тип word *, и при добавлении к нему целых чисел результирующий адрес будет отсчитываться в словах, как в языке С. Для то чтобы проверить, свободен ли сосед перед ним, мы должны посмотреть слово с адресом addr - 2. Если оно отрицательно, то сосед занят, и мы должны оставить его в покое. Если же оно положительно, то мы можем легко определить адрес начала этого блока как addr - addr [-2].

Определив адрес начала блока, мы можем легко объединить этот блок: блоком addr, нам нужно только сложить значения меток-дескрипторов записать их в дескрипторы нового большого блока. Нам даже не нужно будет добавлять освобождаемый блок в список и извлекать оттуда его соседа!

Похожим образом присоединяется и сосед, стоящий после него. Единствен­ное отличие состоит в том, что этого соседа все-таки нужно извлекать из списка свободных блоков.

Фактически, парные метки можно рассматривать как способ реализации решения, предложенного нами как одна из идей мозгового штурма: двунаправленного списка, включающего в себя как занятые, так и свободные и, и отсортированного по адресу. Дополнительное преимущество при­веденного алгоритма состоит в том, что мы можем отслеживать такие ошибки, как многократное освобождение одного блока, запись в память за границей блока и иногда даже обращение к уже освобожденному блоку. Действительно, мы в любой момент можем проверить всю цепочку блоков памяти и убедиться в том, что все свободные блоки стоят в списке, что в нем стоят только свободные блоки, что сами цепочка и список не испорчены, и т. д.

Итак, наилучшим из известных универсальных алгоритмов динамического распределения памяти является алгоритм парных меток с объединением свободных блоков в двунаправленный кольцевой список и поиском по принципу first fit. Этот алгоритм обеспечивает приемлемую производитель­ность почти для всех стратегий распределения памяти, используемых в при­кладных программах.

Алгоритм парных меток был предложен Дональдом Кнутом в начале 60-х. В третьем издании классической книги [Кнут, 2000], этот алгоритм приво­дится под названием "освобождения с дескрипторами границ". В современ­ных системах используются и более сложные структуры дескрипторов, но всегда ставится задача обеспечить поиск соседей блока по адресному про­странству за фиксированное время. В этом смысле, практически все современные подпрограммы динамического выделения памяти (в частности, реализации стандартной библиотеки языка С) используют аналоги алгоритма парных меток. Другие известные подходы либо просто хуже, чем этот, либо проявляют свои преимущества только в специальных случаях.

реализация malloc в библиотеке GNU LibC (реализация стандартной библиотеки языка С в рамках freeware проекта GNU Not Unix) (пример 4.3) использует смешанную стратегию: блоки размером более 4096 байт выделяются стратегией first fit из двусвязного кольцевого списка с использованием циклического просмотра, а освобождаются при помощи метода, который в указанном ранее смысле похож на алгоритм парных меток. Все выделяемые таким образом блоки будут иметь размер, кратный 4096 байтам. Блоки меньшего размера объединяются в очереди с размерами, пропорцио­нальными степеням двойки, как в описанном далее алгоритме близнецов. Элементы этих очередей называются фрагментами. В отличие от алгоритма близнецов, мы не объединяем при освобождении парные фраг­менты. Вместо этого, мы разбиваем 4-килобайтовый блок на фрагменты одинакового размера. Если, например, наша программа сделает запросы на 514 и 296 байт памяти, ей будут переданы фрагменты в 1024 и 512 байт со­ответственно. Под эти фрагменты будут выделены полные блоки в 4 кило­байта, и внутри них будет выделено по одному фрагменту. При последую­щих запросах на фрагменты такого же размера будут использоваться свободные фрагменты этих блоков. Пока хотя бы один фрагмент блока за­нят, весь блок считается занятым. Когда же освобождается последний фраг­мент, блок возвращается в пул.

Описатели блоков хранятся не вместе с самими блоками, а в отдельном ди­намическом массиве _heapinfо. Описатель заводится не на непрерывную последовательность свободных байтов, а на каждые 4096 байт памяти (в примере 4.3 именно это значение принимает константа blocksize). Бла­годаря этому мы можем вычислить индекс описателя в _heapinfо, просто разделив на 4096 смещение освобождаемого блока от начала пула. Для нефрагментированных блоков описатель хранит состояние (занят-свободен) и размер непрерывного участка, к которому принадлежит блок. Благодаря этому, как и в алгоритме парных меток, мы легко можем найти соседей освобождаемого участка памяти и объединить их в большой непре­рывный участок.

Для фрагментированных блоков описатель хранит размер фрагмента, счет­чик занятых фрагментов и список свободных. Кроме того, все свободные Фрагменты одного размера объединены в общий список — заголовки этих списков собраны в массив _fraghead.

Используемая структура данных занимает больше места, чем применяемая в Классическом алгоритме парных меток, но сокращает объем списка свобод­ах блоков и поэтому имеет более высокую производительность. Средний о6ъем блока, выделяемого современными программами для ОС общего назначения, измеряется многими килобайтами, поэтому в большинстве случаев повышение накладных расходов памяти оказывается терпимо.

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

Проще всего решить эту задачу, если нам требуются блоки нескольких фик­сированных размеров. Мы объединяем блоки каждого размера в свой список. Если в списке блоков требуемого размера ничего нет, мы смотрим в список блоков большего размера. Если там что-то есть, мы разре­заем этот блок на части, одну отдаем запрашивающей программе, а вторую... Правда, если размеры требуемых блоков не кратны друг другу, что мы будем делать с остатком?

Для решения этой проблемы нам необходимо ввести какое-либо ограниче­ние на размеры выделяемых блоков. Например, можно потребовать, чтобы эти размеры равнялись числам Фибоначчи (последовательность целых чисел, в которой Fi+1 = Ft + Fi-1). В этом случае, если нам нужно Ft байт, а в наличии есть только блок размера Fi+1, мы легко можем получить два блока - один требуемого размера, а другой — Fi-1 который тоже не пропадет. Да, любое ограничение на размер приведет к внутренней фрагментации, но так ли велика эта плата за гарантированное время поиска блока?

На практике, числа Фибоначчи не используются. Одной из причин, по-видимому, является относительная сложность вычисления такого Ft , которое меньше требуемого размера блока. Другая причина — сложность объединения свободных блоков со смежными адресами в блок большего размера. Зато широкое применение нашел алгоритм, который ограничивает последовательные размеры блоков более простой зависимостью — степенями числа 2: 512 байт, 1 Кбайт, 2 Кбайт и т. д. Такая стратегия называется алгоритмом близнецов.

Одно из преимуществ этого метода состоит в простоте объединения блоков при их освобождении. Адрес блока-близнеца получается простым инвертированием соответствующего бита в адресе нашего блока. Нужно только проверить, свободен ли этот близнец. Если он свободен, то мы объединяем братьев в блок вдвое большего размера, и т. д. Даже в наихудшем случае время поиска не превышает О (log(Smax)-log(Smjn)), где Sтах и Smin обозначают, соответственно, максимальный и минимальный размеры используемых блоков. Это делает алгоритм близнецов трудно заменимым для ситуаций, в которых необходимо гарантированное время реакции — например, для задач реального времени. Часто этот алгоритм или его варианты использу­ется для выделения памяти внутри ядра ОС.

Существуют и более сложные варианты применения описанного выше под­хода. Например, пул свободной памяти Novell Netware состоит из 4 очере­дей с шагом 16 байт (для блоков размерами 16, 32, 48, 64 байта), 3 очередей с шагом 64 байта (для блоков размерами 128, 192, 256 байт) и пятнадцати очередей с шагом 256 байт (от 512 байт до 4 Кбайт). При запросах большего размера выделяется целиком страница. Любопытно, что возможности рабо­ты в режиме реального времени, присущие этой изощренной стратегии, в Netware практически не используются.

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

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

– Конец работы –

Эта тема принадлежит разделу:

История операционных систем

По тому какие из вышеперечисленных функций реализованы и каким было уделено больше внимания а каким меньше системы можно разделить на несколько... General Purpose Operating Systems ОС общего назначения... Real Time Systems ОС реального времени...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритмы динамического управления памятью

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

Онтогенез повторяет филогенез
  После опубликования книги Чарльза Дарвина «Происхождение видов» немецкий зоолог Эрнст Хэккель (Ernst Haeckel) сформулировал правило: «Онтогенез повторяет филогенез». Сказав это, он

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

ДОС (Дисковые Операционные Системы)
Это системы, берущие на себя выполнение только первых четырех функций. Как правило, они представляют собой некий резидентный набор подпро­грамм, не более того. ДОС загружает пользовательскую програ

ОС общего назначения
К этому классу относятся системы, берущие на себя выполнение всех вы­шеперечисленных функций. Разделение на ОС и ДОС идет, по-видимому, от систем IBM DOS/360 и OS/360 для больших компьютеров этой ф

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

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

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

Системы промежуточных типов
Существуют системы, которые нельзя отнести к одному из вышеперечис­ленных классов. Такова, например, система RT-11, которая, по сути своей, является ДОС, но позволяет одновременное исполнение неско

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

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

Проблема
Организация имеет двенадцать велосипедов. Стоит задача: перевезти рояль. Что делать? Грузовик не предлагать... Основная проблема MS Windows состоит вовсе не в том, что это не "насто­я

Открытые системы
Альтернативой закрытым решениям является концепция открытых систем. Идея открытых систем исходит из того, что для разных задач необходимы разные системы — как специализированные, так и системы обще

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

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

Представление изображений
Все известные форматы представления изображений (как неподвижных, так и движущихся) можно разделить на растровые и векторные. В векторном формате изображ

Представление звуков
Два основных подхода к хранению звуковых файлов можно сопоставить с векторным и растровым способами хранения изображений: это MIDI и по­добные ему форматы, и оцифрованный звук.

Упаковка данных
Данные многих форматов имеют значительный объем, поэтому их хра­нение и передача зачастую требуют значительных ресурсов. Одним из способов решения этой проблемы является повышение емкости запоми­на

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

Загрузка программ
Выяснив, что представляет собой программа, давайте рассмотрим процедуру ее загрузки в оперативную память компьютера (многие из обсуждаемых да­лее концепций, впрочем, в известной мере применимы и к

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

Абсолютная загрузка
Первый, самый простой, вариант состоит в том, что мы всегда будем загружать программу с одного и того же адреса. Это возможно в следующих случаях. □ Система может предоставить каждом

Формат загрузочного модуля a.out
В системе UNIX на 32-разрядных машинах также используется абсолютная за­грузка. Загружаемый файл формата a.out (современные версии Unix использу­ют более сложный формат загружаемого модуля и более

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

Оверлеи (перекрытия)
Смысл оверлея состоит в том, чтобы не загружать программу в память целиком, а разбить ее на несколько модулей и поме­щать их в память по мере необходимости. При этом на одни и те же адреса

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

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

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

Сборка в момент загрузки
Как мы видели в предыдущем разделе, объектные модули и библиотеки со­держат достаточно информации, чтобы собирать программу не только зара­нее, но и непосредственно в момент загрузки. Этот способ,

Программные модули в N9000
В этих архитектурах каждый объектный модуль соответствует одному модулю в смысле языка высокого уровня Oberon (или NIL— N9000 Instrumental Language). Далее мы будем описывать архитектуру системы N9

Динамические библиотеки
В Windows и OS/2 используется именно такой способ загрузки. Исполняе­мый модуль в этих системах содержит ссылки на другие модули, называе­мые DLL (Dynamically Loadable Library, динамически загружае

Загрузка самой ОС
При загрузке самой ОС возникает специфическая проблема: в пустой м шине, скорее всего, нет программы, которая могла бы это сделать. В системах, в которых программа находится в ПЗУ (или другой энерг

Загрузка Sun Solaris
Полный цикл загрузки Solaris (версия Unix System V Release 4, поставляющаяся фирмой Sun) на компьютерах х86 происходит в шесть этапов. Первые три эта­па стандартны для всех ОС, работающих на IBM PC

Управление оперативной памятью
Основной ресурс системы, распределением которого занимается ОС — это оперативная память. Поэтому организация памяти оказывает большое влияние на структуру и возможности ОС. В настоящее время сложил

Открытая память
Самый простой вариант управления памятью — отсутствие диспетчера па­мяти и возможность загружать в системе только один процесс. Именно так работают СР/М и RT-11 SJ (Single-Job, однозадачная). В эти

Сборка мусора
Явное освобождение динамически выделенной памяти применяется во многих системах программирования и потому привычно для большинства программистов, но оно имеет серьезный недостаток: если программист

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

Управление памятью в MS DOS
Так, например, процедура управления памятью MS DOS рассчитана на случай, когда программы выгружаются из памяти только в порядке, обратном тому, в каком они туда загружались (на практике, они могут

Управление памятью в MacOS и Win16
В этих системах предполагается, что пользовательские программы не сохра­няют указателей на динамически выделенные блоки памяти. Вместо этого каждый такой блок идентифицируется целочисленным дескрип

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

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

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

Централизованный контроллер, устанавливаемый на системной плате и способный работать с несколькими различными устройствами.
В качестве альтернативы ПДП можно предложить снабжение устройство буфером, который работает с частотой системной шины. Центральный про­цессор передает данные в буфер, и лишь когда

Прерывания
Альтернатива опросу, применяемая практически во всех современных процессорах, называется прерываниями (interrupt), и состоит в значительном усложнении логики обработк

ИСКЛЮЧЕНИЯ
Многие процессоры используют механизм, родственный прерываниям, для обработки не только внешних, но и внутренних событий (исключительные ситуации – отсутствие страницы, ошибки дост

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

Порядок доступа к памяти в SPARC
Современные процессоры предоставляют возможность управлять порядком доступа команд к памяти. Например, у микропроцессоров SPARCv9 определены три режима работы с памятью (модели памя­ти), переключае

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги