Связное распределение памяти для одного пользователя, называемое также одиночным непрерывным распределением, применяется в ЭВМ, работающих в пакетном однопрограммном режиме под управлением простейшей ОС.
Вся основная часть ЭВМ, не занятая программами операционной системы, выделяется программе единственного на данном отрезке времени пользователя. Размер программы в этом случае ограничивается размером доступной основной памяти, однако существует возможность выполнения программ, размер которых превышает размер основной памяти, используя механизм оверлеев.
Организация памяти при связном распределении для одного пользователя показана на рис. 4.2. (слайд №6)
Функциями ОС в данном случае являются:
· выделение программе необходимого пространства памяти;
Функция выделения памяти сводится к предоставлению программе всей доступной памяти ЭВМ.
Защита памяти в однопрограммных системах заключается в установке защиты областей памяти, занятых операционной системой, от воздействия программ пользователя.
ФИЛЬМ ПОКОРИЛ МИР! ПАРТИЗАНСКАЯ СВЯЗНАЯ НАПРАВЛЯЕТСЯ К ПОДПОЛЬЩИКАМ! Свадебная ночь! Русские сериалы
При мультипрограммной обработке в памяти компьютера размещается сразу несколько заданий. Распределение памяти между заданиями в этом случае может быть выполнено следующими способами:
· распределение фиксированными разделами;
· распределение переменными разделами;
· распределение со свопингом.
Распределение фиксированными разделами
имеет две модификации:
а) с загрузкой программ в абсолютных адресах;
б) с загрузкой перемещаемых модулей.
При загрузке перемещаемых модулей вся оперативная память машины разбивается на некоторое количество разделов фиксированного размера. Размеры разделов могут не совпадать. В каждом разделе может быть размещено только одно задание.
В случае загрузки программ в абсолютных адресах при их подготовке указывается начальный адрес загрузки программ, совпадающий с начальным адресом раздела, в котором эта программа будет выполняться.
В случае загрузки перемещаемых модулей раздел, в котором будет размещено задание, либо автоматически определяется операционной системой в соответствии с реализованной в нем стратегией выбора раздела (“первый подходящий”, “самый подходящий”, “самый неподходящий”), либо указывается операционной системе специальными командами языка управления заданиями.
В обоих случаях задание монопольно владеет всем объемом оперативной памяти раздела, в который оно было помещено операционной системой.
Основным недостатком распределения памяти фиксированными разделами является неэффективное использование ресурсов вычислительной системы из-за возможного появления длинных очередей заданий, ожидающих освобождения конкретного раздела в то время, как остальные разделы пусты. Подобная ситуация изображена на рис. 4.3. Задания, ожидающие освобождения раздела С, могли бы разместиться и в разделах А или В, однако операционная система не позволяет им это сделать, т.к. в управляющей информации указан конкретный раздел, в котором эти задания должны выполняться — раздел С.
Опасные связи | Сезон 6 | Выпуск 44
Способ распределения памяти фиксированными разделами используется в операционных системах ОС ЕС и IBM/360 в режиме MFT, в котором загрузка программ выполняется перемещаемыми модулями.
В мультипрограммных системах с фиксированными разделами наблюдается явление фрагментации памяти.
Фрагментация памяти — появление в памяти вычислительной машины чередования занятых и незанятых (свободных) участков оперативной памяти.
При распределении фиксированными разделами появление фрагментации обусловлено тем, что либо задания пользователей не полностью занимают выделенные им разделы, либо часть разделов остается незанятой.
На рис.4.4. показано проявление фрагментации оперативной памяти.
Фрагментация памяти представляет собой нарушение односвязности пространства свободной памяти ЭВМ, что приводит к снижению эффективности использования памяти как одного из основных ресурсов вычислительной машины.
Распределение памяти переменными разделами
предназначено для повышения эффективности использования оперативной памяти ЭВМ. Суть способа распределения памяти переменными разделами состоит в том, что заданиям, когда они поступают, выделяется такой объем памяти, который им требуется, т.е. размер раздела оперативной памяти, выделяемой каждому заданию, в точности соответствует размеру этого задания. Поэтому “перерасхода” памяти, как это происходит при распределении фиксированными разделами, в данном способе не наблюдается.
Имеется две модификации способа распределения переменными разделами:
· распределение переменными неперемещаемыми разделами;
· распределение переменными перемещаемыми разделами.
При распределении памяти переменными неперемещаемыми разделами (динамическими разделами) операционная система создает две таблицы: таблицу учета распределенных областей памяти и таблицу учета свободных областей памяти (“дыр”).
При поступлении очередного задания память для него отводится на этапе долгосрочного планирования, причем выделение памяти осуществляется по информации из таблицы учета “дыр” в соответствии с принятой в ОС стратегией размещения (“первый подходящий”, “самый подходящий”. “самый неподходящий”). При успешном распределении ОС корректирует обе таблицы — распределенных и свободных областей.
После окончания какого-либо задания занимаемый им участок памяти освобождается, и операционная система корректирует таблицу распределенных областей, вычеркивая из нее информацию о закончившемся задании, а также заносит в таблицу свободных областей данные о вновь появившейся “дыре”.
(слайд №7)
Рассмотрим следующий пример. Пусть начальное распределение памяти переменными разделами выполнено так, как показано в табл.4.1, 4.2 и на рис. 4.5а. После размещения заданий А, В, С и Д осталась свободная область такого размера, что ни одна из программ, продолжающих стоять в очереди, в эту область не помещается.
Таблица 4.1. Таблица распределенных областей
| Номер раздела, ключ защиты | Имя раздела | Размер | Адрес | Состояние |
| А В С Д Е | 100К 200К 100К 400К 100К | 50К 150К 350К 450К 850К | Распределен Распределен Распределен Распределен Распределен |
Таблица 4.2. Таблица свободных областей
| Номер свободной области | Размер | Адрес | Состояние |
| 100К | 950К | Доступна |
Предположим, что через некоторое время закончились задания А и С (см. рис.4.5б). Таблицы областей приобретают вид, показанный в табл. 4.3 и 4.4.
Таблица 4.3. Таблица распределенных областей: закончилось задание А
| Номер раздела, ключ защиты | Имя раздела | Размер | Адрес | Состояние |
| — В — Д Е | — 200К — 400К 100К | — 150К — 450К 850К | Пусто Распределен Пусто Распределен Распределен |
Таблица 4.4. Таблица свободных областей: закончилось задание А
| Номер свободной области | Размер | Адрес | Состояние |
| 100К 100К 100К | 100К 350К 950К | Доступна Доступна Доступна |
Можно видеть, что несмотря на наличие 274К свободной памяти, достаточной для размещения задания Е, стоящего первым в очереди, ОС не имеет возможности это сделать, т.к. свободная память разбита на два фрагмента по 100К каждый, в которых разместить программы, стоящие в очереди, невозможно. Этот пример иллюстрирует главный недостаток способа распределения переменными неперемещаемыми разделами — склонность к фрагментации основной памяти, что снижает эффективность работы вычислительной системы.
При распределении памяти переменными перемещаемыми разделами операционная система осуществляет действия, называемые уплотнением памяти, состоящими в перемещении всех занятых участков к одному или другому краю основной памяти. Благодаря этому вместо большого количества небольших “дыр”, образующихся при использовании распределения переменными неперемещаемыми разделами, формируется единый (связный) участок свободной памяти. На рис.4.5в показан результат уплотнения, когда находящиеся в основной памяти программы В, Д и Е перемещены на свободные участки после окончания работы программ А и С. Свободная память теперь представляет собой непрерывную область размером 274К, в которую ОС может поместить стоящее в очереди задание F. Этот процесс называют также дефрагментацией памяти.
Дефрагментация памяти, применяемая при распределении перемещаемыми разделами, имеет свои недостатки:
· требуются дополнительные затраты времени;
· во время уплотнения памяти система должна прекращать (приостанавливать) все другие работы, что зачастую может оказаться неприемлемым;
· необходимость перемещения заданий в памяти требует хранения значительного объема информации, связанной с размещением программ в памяти, что увеличивает требования к памяти со стороны ОС;
· при интенсивном потоке коротких программ может возникнуть необходимость частой дефрагментации памяти, так что затачиваемые на эти цели системные ресурсы могут оказаться неоправданными получаемой выгодой.
Источник: studopedia.su
Ваша программа использует связный список? Платите лицензионные отчисления
Бюро по регистрации патентов и торговых марок США не перестаёт нас удивлять: в апреле 2006 года оно выдало компании LSI Logic Corporation патент на связный список. Связные списки используются практически в любой программе, а значит любая компания-разработчик в США теоретически оказывается под угрозой судебного иска. Впрочем, вряд ли компания сможет отстоять своё «изобретение» в суде, так как связные списки появились ещё в середине 50-х годов прошлого века.
На всякий случай напомню, что такое связный список. Связный список — структура данных, представляющая из себя набор элементов, каждый из которых состоит из двух частей: собственно данных и ссылки-указателя на следующий элемент. Это одна из простейших структур данных, она используется повсеместно, например, для реализации стека, очереди, хеша, списков с пропусками и т. п.
В патенте описана одна из разновидностей списка, а именно двусвязный список. Элементы двусвязного списка содержат два указателя: на следующий и предыдущий элементы. Благодаря этому список можно просматривать как вперёд, так и назад. Сравните с кратким описанием патента: «Компьютерный список снабжается вспомогательными указателями для обхода списка в разных направлениях.
Один или несколько вспомогательных указателей обеспечивают быстрый, последовательный обход списка с минимальными затратами вычислительного времени. Такие списки могут использовать в любых приложениях, в которых требуется различные сортировки списка для различных задач». Компании потребовалось целых четыре года, чтобы запатентовать свой алгоритм. Возможно, они просто искали в Бюро кого-то, кто не знает о связных списках?
- патенты
- структуры данных
Источник: habr.com
Реализация связных списков на С++
В данной своей статье я хотел бы рассмотреть такую интересную структуру данных, как связанный список или как его еще называют динамический список. Связный список — это динамическая структура данных, состоящая из узлов, которые содержат в себе в классическом варианте два значения: первое — это какое-либо данное (этим данным может быть что угодно: обычная переменная, объект класса и так далее), а второе — это указатель на следующий узел в списке (не зря же список является связанным).
Список связный потому что все узлы списка связаны между собой с помощью указателей, а динамический потому что динамически во время выполнения программы можно расширять данную структуру путем добавления новых узлов в список. В отличие от массива будь то статического, либо динамического, динамический список можно увеличивать во время работы программы. В этом то и есть его очень большой плюс. А вот давайте теперь и рассмотрим все это на рисунке:
На рисунке мы видим узлы, содержащие в себе два значения — данное и указатель. Указатель всегда указывает (содержит в себе адрес памяти) на следующий узел связанного списка. И самое важное — это то, что указатель последнего узла должен всегда выставляться в нуль (NULL, nullptr или просто 0). Этим он сообщает что является последним узлом связанного списка и что дальше указывать не на что.
Если нужно будет добавить новый узел в динамический список, то это значение NULL заменяется на адрес нахождения в памяти нового узла (как это делается мы рассмотрим ниже), а сам же указатель нового узла опять выставляется в NULL. По ходу работы программы мы можем сколь угодно создавать таких узлов нашего связанного списка, единственное ограничение накладывает размер свободной оперативной памяти компьютера (ее конечно же должно хватать). Логически мы видим, что все узлы расположены как бы по порядку, хотя на самом деле в памяти компьютера они могут располагаться где угодно. И найти его не составит никакого труда, т.к. у нас есть в узле поле-указатель, указывающий на нужную ячейку памяти.
Давайте теперь последовательно рассмотрим работу связанного списка. Итак, мы описали в своей программе структуру, представляющую собой узел динамического списка. Эта структура из двух полей — данное и указатель на структуру того же типа. Такие структуры еще называются самоссылающимися (или структуры с самоадресацией). Вот как это будет выглядеть
//стуктура, описывающая узел связанного списка struct Node < int data; Node *next; >;
А теперь нужно создать сам объект «связанный список», который и будет хранить эти самоссылающиеся узлы (Node — с англ. узел). Вот как мы это сделаем
//класс, описывающих объект «связанный список» class List < private: Node *head; //»голова» связанного списка public: List() //конструктор класса без параметров < head = NULL; //первого элемента пока нет >//метод, добавляющий новый узел в список void addNode(int d); //метод, выводящий связанный список на экран void printList(); >;
Изначально в конструкторе класса List переменной head выставляется значение в NULL , т.к. при создании объекта класса List связанный список еще пуст и узлов в нем нет, соответственно и указывать не на что. Складываем все вышеупомянутое и получаем рабочую программу, реализующую динамический список.
#include using namespace std; struct Node < int data; Node *next; >; class List < private: Node *head; //»голова» связанного списка public: List() //конструктор класса без параметров < head = NULL; //первого элемента пока нет >//метод, добавляющий новый узел в список void addNode(int d) < Node *nd = new Node; //динамически создаем новый узел nd->data = d; //задаем узлу данные nd->next = NULL; //новый узел в конце, поэтому NULL if(head == NULL) //если создаем первый узел head = nd; else //если узел уже не первый < Node *current = head; //ищем в цикле предшествующий последнему узел while(current->next != NULL) current = current->next; //предшествующий указывает на последний current->next = nd; > > //метод, выводящий связанный список на экран void printList() < Node *current = head; while(current != NULL) < cout data next; > > >; int main()
Результат работы программы будет выглядеть так:
Думаю, что метод, добавляющий новый узел в список ( addNode ) нужно рассмотреть подробнее — не всем и все здесь будет понятно сразу же:
Итак, первая строка кода
Node *nd = new Node;
динамически (new) создает новый объект типа Node , т.е. новый узел. Как вы знаете, после отработки данной строки, в указатель nd , при успешном создании объекта, записывается адрес созданного объекта в памяти (в неудачном случае будет записано NULL , т.е. объект не создан). Идем дальше…
nd->data = d; nd->next = NULL;
В этих двух строках кода мы уже обращаемся к полям созданного узла и присваиваем им необходимые значения: задаем данное — это данное метод addNode() принимает в качестве аргумента, выставляем указатель в NULL , т.к. вновь созданный узел всегда у нас будет последним (в данном варианте программы узлы добавляются в конец связанного списка — классический вариант). Далее…
if(head == NULL) head = nd; else
Следующая конструкция выбора служит для определения: создается первый узел в списке или он уже не первый. В случае, если создается только первый узел, то head будет в NULL и выполнится условие после if , т.е. head присвоится адрес первого узла в памяти. В последующих случаях, когда создаются 2, 3, 4, 5, . узлы будет срабатывать блок после else . Его рассмотрим подробнее…
Node *current = head; while(current->next != NULL) current = current->next; current->next = nd;
Создаем вспомагательную переменную типа Node и присваиваем ей указатель на начало списка. Далее в цикле мы последовательно проходимся по нашему связанному списку, пока не дойдем до узла, который был создан последним прошлый раз и присваиваем его указателю адрес нашего вновь созданного узла. Описанный процесс показан на рисунке:
Однонаправленный связнный список. Стек
Нами был рассмотрен классический вариант динамического списка, в котором новые узлы добавляются в конец, но есть еще вариант, когда узлы добаляются в начало, кстати, код такой программы немного меньше и проще. Его мы сейчас и рассмотрим.
#include using namespace std; struct Node < int data; Node *next; >; class List < private: Node *head; public: List() < head = NULL; >void addNode(int d) < Node *nd = new Node(); nd->data = d; nd->next = head; head = nd; > void printList() < Node *current = head; while(current) < cout data next; > > >; int main()
Рассмотрев код программы, видим, что изменился метод добавления нового узла в список. Теперь новый узел как бы вклинивается между «головой» списка и следующим после нее узлом. Соответственно, в результатах работы мы видим в какой последовательности выводятся значения, находящиеся в узлах. Если вам подходит такой вариант обратного вывода, то можете использовать этот код.
Двунаправленный связанный список. Дек
В однонаправленном мы могли перемещаться только в одно направление и не могли вернуться назад, т.к. любой из следующих узлов не содержал в себе указателя на предыдущий. Также я добавил в программу возможность добавлять узлы как в начало списка, так и в конец, удалять узлы можно по условию, задаваемому функциональным объектом:
#ifndef CONTAINER_H #define CONTAINER_H #include #include #include template class Container < public: Container() < m_start = m_end = nullptr; m_size = 0; >~Container() < clear(); >void push_front(const T if (m_start) < Node* new_node = new Node(); new_node->data = data; new_node->next = m_start; m_start->prev = new_node; m_start = new_node; > else < init(data); >m_size++; > void pop_front() < if (!m_start) return; if (m_start->next) < Node* next = m_start->next; next->prev = nullptr; delete m_start; m_start = next; > else < delete m_start; m_start = m_end = nullptr; >m_size—; > void push_back(const T if (m_end) < Node* new_node = new Node(); new_node->data = data; new_node->prev = m_end; m_end->next = new_node; m_end = new_node; > else < init(data); >m_size++; > void pop_back() < if (!m_end) return; if (m_end->prev) < Node* prev = m_end->prev; prev->next = nullptr; delete m_end; m_end = prev; > else < delete m_end; m_start = m_end = nullptr; >m_size—; > void sort(std::function cmp) < if (!m_start) return; Node* tmp = m_start; while (tmp) < Node* tmp_next = tmp->next; while (tmp_next) < if (cmp(tmp->data, tmp_next->data)) std::swap(tmp->data, tmp_next->data); tmp_next = tmp_next->next; > tmp = tmp->next; > > void remove_one(std::function cnd) < Node* tmp = m_start; while (tmp) < if (cnd(tmp->data)) < remove_node(tmp); return; >tmp = tmp->next; > > void remove_all(std::function cnd) < Node* tmp = m_start; while (tmp) < if (cnd(tmp->data)) < Node* bck = nullptr; if (tmp->prev) bck = tmp->prev; else if (tmp->next) bck = tmp->next; remove_node(tmp); if (!bck) return; tmp = bck; > else < tmp = tmp->next; > > > void clear() < if (!m_start) return; if (m_start == m_end) < delete m_start; >else < Node* tmp = m_start; while (tmp != m_end) < Node* next = tmp->next; delete tmp; tmp = next; > > m_size = 0; m_start = m_end = nullptr; > void for_each(std::function fun) < Node* tmp = m_start; while (tmp) < fun(tmp->data); tmp = tmp->next; > > inline size_t size() const noexcept < return m_size; >Container clear(); Node* tmp = other.m_start; while (tmp) < push_back(tmp->data); tmp = tmp->next; > other.clear(); return *this; > private: struct Node < Node() < next = nullptr; prev = nullptr; >~Node() = default; T data; Node* next; Node* prev; >; void init(const T m_start = new Node(); m_start->data = data; m_end = m_start; > void remove_node(Node* node) < Node* prev = node->prev; Node* next = node->next; if (prev != nullptr) prev->next = next; if (next != nullptr) next->prev = prev; if (node == m_start) m_start = next; if (node == m_end) m_end = prev; delete node; m_size—; > Node* m_start; Node* m_end; size_t m_size; >; #endif // CONTAINER_H
Источник: pro-prof.com