Алгоритм булочной – еще один подход к решению проблемы критических секций. Использует присвоение уникального номера в очереди (приоритета) каждому процессу.

Алгоритмы синхронизации более просты, если они используют аппаратную поддержку атомарных операций – проверка и установка ( test-and-set) и перестановка значений двух переменных ( swap). Приведена реализация синхронизации процессов с использованием обеих операций.

Общий семафор ( по Э. Дейкстре) – синхронизирующий примитив: целая переменная, над которой определены семафорные операцииwait и signal. Приведено решение проблемы критических секций с помощью семафоров. Семафор реализуется в виде структуры из двух полей: счетчик и ссылка на список ждущих процессов. Для реализации операций над семафором достаточно двух примитивов: block – блокировка текущего процесса, wakeup(P) – разблокировка процесса P.

Семафоры могут использоваться как общее средство синхронизации по ресурсам и по событиям.

Используются две разновидности семафоров – общие (с целым значением) и двоичные (значениями могут быть только 0 и 1). Общий семафор может быть реализован с помощью двоичных семафоров.

В системе "Эльбрус" имеется вариант операции ожидания жуж (жужжать на процессоре) для системных процессов – без прерывания, с удержанием процессора до момента разблокировки.

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

НЕ нашли? Не то? Что вы ищете?

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

Монитор ( по Ч. Хоару) – высокоуровневая конструкция для синхронизации: многовходовый модуль, содержащий описание общих данных и операций над ними в виде процедур. Обеспечивается взаимное исключение исполнения мониторных операций. Мониторможет также содержать условные переменные, для которых определены операции wait и signal для организации дополнительных очередей процессов. Рассмотрено решение задачи "обедающие философы" с использованием монитора. Описана реализация монитора и условных переменных с помощью семафоров.

Семафор Дейкстры представляет собой целочисленную переменную, с которой ассоциирована очередь ожидающих нитей. Пытаясь пройти через сема-Фор, нить пытается вычесть из значения переменной 1. Если значение переменной больше или равно 1, нить проходит сквозь семафор успешно (семафор открыт). Если переменная равна нулю (семафор закрыт), нить останавливается и ставится в очередь.

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

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

емафоры общего вида могут принимать любые неотрицательные значения. В современной литературе такие семафоры называют семафорами-счетчиками (counting semaphore). Это соответствует случаю, когда несколько нитей могут работать с объектом одновременно, или когда объект состоит из нескольких независимых, но равноценных частей – например, несколько одинаковых принтеров. При работе с такими семафорами часто разрешают процессам вычитать и добавлять к флаговой переменной значения, большие единицы. Это соответствует захвату/освобождению нескольких частей ресурса.

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

Во многих современных книгах и операционных системах семафорами называются только семафоры общего вида, двоичные же семафоры носят более краткое и выразительное имя мутекс (mutex – от MUTual EXclusion, взаимное исключение). Проследить генезис этого названия автору не удалось, но можно с уверенностью сказать, что оно вошло в широкое употребление не ранее конца 80-х. Так, в разрабатывавшейся в середине 80-х годов OS/2 1.0, двоичные семафоры еще называются семафорами, а в Win32, разработка которой происходила в начале 90-х, уже появляется название mutex. Операции над мутексом называются захватом (acquire) (соответствует входу в критическую секцию) и освобождением (release) (соответствует выходу из нее).

Многие ОС предоставляют для синхронизации семафоры Дейкстры или похожие на них механизмы.

21. Основные схемы управления оперативной памятью. Понятие «виртуальная память»

Функции ОС по управлению памятью

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

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

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

Функциями ОС по управлению памятью в мультипрограммной системе являются:

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


22. Методы выделения и разделения внешних устройств между программными процессами в операционной системе.

23. Основные методы организации записей в файл. Понятие прямого и последовательного метода доступа.

организация файлов и доступ к ним

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

Файл прямого доступа

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

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

Естественно, что в этом случае для доступа к середине файла просмотр всего файла с самого начала не обязателен. Для специфицирования места, с которого надо начинать чтение, используются два способа: с начала или с текущей позиции, которую дает операция seek.

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

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

Подобную логическую структуру имеют файлы во многих файловых системах, например в файловых системах ОС Unix и MS-DOS. ОС не осуществляет никакой интерпретации содержимого файла. Эта схема обеспечивает максимальную гибкость и универсальность. С помощью базовых системных вызовов (или функций библиотеки ввода/вывода) пользователи могут как угодно структурировать файлы. В частности, многие СУБД хранят свои базы данных в обычных файлах.

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

Выделяют три основных группы методов доступа к данным: последовательные, индексные, произвольные методы доступа. Последовательные методы используются при поиске большого числа записей (от 10 до 100%), индексные для получения одной или нескольких записей, произвольные для получения отдельных записей.

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

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

Индекс - структура данных, которая помогает СУБД быстрее обнаружить отдельные записи в файле и сократить время выполнения запросов пользователей.

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

Хотя индексы, строго говоря, не являются обязательным компонентом СУБД, они могут существенным образом повысить ее производительность. Как и в случае с предметным указателем книги, читатель может найти определение интересующего его понятия, просмотрев всю книгу, но это потребует слишком много времени. А предметный указатель, ключевые слова в котором расположены в алфавитном порядке, позволяют сразу же перейти на нужную страницу.

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

25. Основные методы ведения диалога «человек – ЭВМ». Диалог типа «меню» и «командная строка».

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

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

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



Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4