Понятие многослойности ядра

Понятие многослойности ядра

Ядро может состоять из следующих слоев: § Средства аппаратной поддержки ОС. До сих пор об операционной системе… § Машинно-зависимые компоненты ОС. Этот слой образуют программные модули, в которых отражается специфика аппаратной…

Аппаратная зависимость и переносимость ОС. Типовые средства аппаратной поддержки ОС.

Четкой границы между программной и аппаратной реализацией функций ОС не существует — решение о том, какие функции ОС будут выполняться программно, а… § средства поддержки привилегированного режима; § средства трансляции адресов;

Понятие микроядерной структуры

Микроядерная архитектура является альтернативой классическому способу построения операционной системы. Под классической архитектурой в данном случае… Суть микроядерной архитектуры состоит в следующем. В привилегированном режиме…

Понятие мультипрограммирования. Мультипрограммирование в системах пакетной обработки.

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

Понятие мультипрограммирования. Мультипрограммирование в системах разделения времени

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

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

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

Ясно, что системы разделения времени обладают меньшей пропускной способностью, чем системы пакетной обработки, так как на выполнение принимается каждая запущенная пользователем задача, а не та, которая «выгодна» системе. Кроме того, производительность системы снижается из-за возросших накладных расходов вычислительной мощности на более частое переключение процессора с задачи на задачу. Это вполне соответствует тому, что критерием эффективности систем разделения времени является не максимальная пропускная способность, а удобство и эффективность работы пользователя. Вместе с тем мультипрограммное выполнение интерактивных приложений повышает и пропускную способность компьютера (пусть и не в такой степени, как пакетные системы). Аппаратура загружается лучше, поскольку в то время, пока одно приложение ждет сообщения пользователя, другие приложения могут обрабатываться процессором.

Понятие мультипрограммирования. Мультипрограммирование в системах реального времени

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

Планирование процессов и потоков. Вытесняющие и невытесняющие алгоритмы планирования

Переход от выполнения одного потока к другому осуществляется в результате планирования и диспетчеризации. Работа по определению того, в какой момент… Планирование потоков, по существу, включает в себя решение двух задач: § определение момента времени для смены текущего активного потока;

Состояния процессов. Состояние потоков

§ выполнение — активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором; … § ожидание — пассивное состояние потока, находясь в котором, поток… § готовность — также пассивное состояние потока, но в этом случае поток заблокирован в связи с внешним по отношению к…

Проблема взаимного исключения процессов

Процессы можно разделить на: · Независимые процессы: борются за использование ресурсов, поскольку процессы… · Связанные процессы: работают совместно и общаются между собой посредством идентификатора процесса (ID). Процессы…

Понятие критической секции

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

Алгоритм Петерсона

Принцип работы Перед тем как начать исполнение критической секции кода (то есть кода,… Код enterRegion и leaveRegion на языке C++

Понятие тупика

В мультипрограммных вычислительных машинах одной из главных функций операционной системы является распределение ресурсов. Когда ресурсы разделяются…

Простой пример тупика при распределении ресурсов

В операционных системах тупики в большинстве случаев возни­кают в результате обычной конкуренции за обладание выделяе­мыми, или закрепляемыми ресурсами (т. е. ресурсами, которые в каждый момент времени отводятся только одному пользователю и которые поэтому иногда называются ресурсами последовательного использования}. На рис. 6.2 показан простой пример тупика подобного рода. На этом графе распределения ресурсов представлены два процесса (в виде прямоугольников) и два ресурса (в виде окружно­стей). Стрелка, направленная от ресурса к процессу, показывает, что данный ресурс принадлежит или был выделен данному процессу. Стрелка, направленная от процесса к ресурсу, показывает, что дан­ный процесс требует, но пока еще не получил в свое распоряжение данный ресурс. На рисунке изображена система в состоянии тупика; процесс А удерживает в своем распоряжении ресурс 1, а для про­должения выполнения ему необходим ресурс 2. Процесс В удер­живает ресурс 2, а для продолжения работы ему нужен ресурс 1. Каждый процесс ждет, чтобы другой процесс освободил нужный ему ресурс, причем каждый не освобождает свой ресурс до тех пор, пока другой не освободит свой ресурс, и т. д. Такое состояние кру­гового ожидания характерно для систем в тупиковом состоянии.

Рис. 6.2 Простая тупиковая ситуация.

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

Четыре необходимых условия возникновения тупика

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

Понятие семафора

Для реализации взаимного исключения, например, предотвращения возможности одновременного изменения двумя или более процессами общих данных,…  

Понятие монитора

Монитор — в языках программирования, высокоуровневый механизм взаимодействия и синхронизации процессов, обеспечивающий доступ к неразделяемым… Пер Бринч Хансен был первым, кто описал и реализовал мониторы, основывая их на… При многозадачности, основанной на мониторах, компилятор или интерпретатор прозрачно для программиста вставляет код…

Классические проблемы взаимодействия процессов. Проблема читателей и писателей

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

 

Проблема обедающих философов

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

Проблема читателей и писателей

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

Листинг. Решение проблемы читателей и писателей

typedef int semaphore: /* Воспользуйтесь своим воображением */

Semaphore mutex =1: /* Контроль доступа к гс */

Semaphore db = 1; /* Контроль доступа к базе данных */

int гс = 0: /* Количество процессов, читающих или желающих читать */

void reader(void)

{

while (true)

{

down(&mutex);

гс = rc+1;

if (rc == 1)

{

down(&db);

up(&mutex);

read_data_base();

down(&mutex);

rc - rc-1;

}

if (rc == 0)

{

up(&db);

up(&mutex);

use_data_read();

}

}

}

void writer(void)

{

while (true)

{

think_up_data();

down(&db);

write_data_base();

up(&db):

}

}

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

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

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

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

Проблема спящего брадобрея

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

 

Базовые механизмы распределения памяти. Однозадачная система без подкачки и замещения. Многозадачная система с фиксированными разделами.

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

Рис. 6.5. Классификация методов распределения памяти

 

Однозадачная система без подкачки на диск

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

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

Три варианта такой схемы. Операционная система может находиться в нижней части памяти, то есть в ОЗУ или же операционная система может располагаться в самой верхней части памя­ти—в ПЗУ, и третий спо­соб: драйверы устройств могут находиться наверху в ПЗУ, а остальная часть сис­темы — в ОЗУ. Первая модель раньше применялась на мэйнфреймах и мини-компьютерах, но в настоящее время практически не употребляется. Вторая схема сейчас используется на некоторых карманных компьютерах и встроенных системах, а третья модель устанавливалась на ранних персональных компьютерах (например, работающих с MS-DOS), при этом часть системы в ПЗУ носила название BIOS (Basic Input Output System — базовая система ввода-вывода).

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

Многозадачность с фиксированными разделами

Самый простой способ достижения многозадачности — разбиение памяти на n разделов. Такое разбиение можно выполнить либо при запуске системы, либо при ее написании.

Очередная задача, поступившая на выполнение, помещается либо в общую очередь (рисунок 2.9,а), либо в очередь к некоторому разделу (рисунок 2.9,б).

Рис. 2.9. Распределение памяти фиксированными разделами:
а - с общей очередью; б - с отдельными очередями

Подсистема управления памятью в этом случае выполняет следующие задачи:

• сравнивая размер программы, поступившей на выполнение, и свободных разделов, выбирает подходящий раздел,
• осуществляет загрузку программы и настройку адресов.

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

Сегментно-страничное распределение памяти

Рис. 2.15. Схема преобразования виртуального адреса в физический для …  

Цели и задачи файловой системы

Основные функции любой файловой системы нацелены на решение следующих задач: · именование файлов; · программный интерфейс работы с файлами для приложений;

Физическая организация файловой системы. Диски, разделы, сектора, кластеры. Непрерывное размещение, связанный список кластеров.

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

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

На каждой стороне каждой пластины размечены тонкие концентрические кольца — дорожки (traks), на которых хранятся данные.

Рис. 7.8. Схема устройства жесткого диска

 

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

Операционная система при работе с диском использует, как правило, собственную единицу дискового пространства, называемую кластером (cluster). При создании файла место на диске ему выделяется кластерами. Например, если файл имеет размер 2560 байт, а размер кластера в файловой системе определен в 1024 байта, то файлу будет выделено на диске 3 кластера.

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

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

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

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

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

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

 

Физическая организация файловой системы FAT.

· Загрузочный сектор содержит программу начальной загрузки операционной системы. Вид этой программы зависит от тана операционной системы, которая… · Основная копия FA Т содержит информацию о размещении файлов и каталогов на… · Резервная копия FAT.

Физическая организация файловых систем s5 и ufs.

Основной особенностью физической организации файловой системы s5 является… Каждый индексный дескриптор имеет номер, который одновременно является уникальным именем файла. Индексные дескрипторы…

Физическая организация файловой системы NTFS

Структура тома NTFS

Все файлы на томе NTFS идентифицируются номером файла, который определяется позицией файла в MFT. Этот способ идентификации файла близок к способу,… Весь том NTFS состоит из последовательности кластеров, что отличает эту… Базовая единица распределения дискового пространства для файловой системы NTFS — непрерывная область кластеров,…

Понятие прерывания (классификация, механизм, активное ожидание)

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

В зависимости от источника возникновения сигнала прерывания делятся на:

· асинхронные, или внешние (аппаратные) — события, которые исходят от внешних источников (например, периферийных устройств) и могут произойти в любой произвольный момент: сигнал от таймера, сетевой карты или дискового накопителя, нажатие клавиш клавиатуры, движение мыши. Факт возникновения в системе такого прерывания трактуется как запрос на прерывание (англ. Interrupt request, IRQ);

· синхронные, или внутренние — события в самом процессоре как результат нарушения каких-то условий при исполнении машинного кода: деление на ноль или переполнение, обращение к недопустимым адресам или недопустимый код операции;

· программные (частный случай внутреннего прерывания) — инициируются исполнением специальной инструкции в коде программы. Программные прерывания, как правило, используются для обращения к функциям встроенного программного обеспечения (firmware), драйверов и операционной системы.

Программное прерывание — синхронное прерывание, которое может осуществить программа с помощью специальной инструкции.

В процессорах архитектуры x86 для явного вызова синхронного прерывания имеется инструкция Int, аргументом которой является номер прерывания (от 0 до 255). В IBM PC-совместимых компьютерах обработку некоторых прерываний осуществляют подпрограммы BIOS, хранящиеся в ПЗУ, и это служит интерфейсом для доступа к сервису, предоставляемому BIOS. Также, обслуживание прерываний могут взять на себя BIOS карт расширений (например, сетевых или видеокарт), операционная система и даже обычные (прикладные) программы, которые постоянно находятся в памяти во время работы других программ (т. н. резидентные программы). В отличие от реального режима, в защищённом режиме x86-процессоров обычные программы не могут обслуживать прерывания, эта функция доступна только системному коду (операционной системе).

Постоянная проверка значения переменной в ожидании некоторого значения называется активным ожиданием. Данный способ является бесцельной тратой времени процессора.

Активное ожидание используется только в случае, когда есть уверенность в небольшом времени ожидания.

Блокировка, использующая активное ожидание, называется спин-блокировкой.

 

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

Активное ожидание используется как база для построения высокоуровневых механизмов.

Существуют ситуации, когда активное ожидание оправдано.

 

Обработчики прерываний, драйверы устройств

  Обработчик прерываний — это низкоуровневый эквивалент обработчика событий. Эти… На современных ПК обработчики основных аппаратных и программных прерываний находятся в памяти BIOS. Современная…