Ответы к экзамену (1124580), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Вытесняющая многозадачность

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

• Преимущества: возможность полной реализации многозадачного ввода-вывода в ядре ОС, когда ожидание завершения ввода-вывода одной программой позволяет процессору тем временем исполнять другую программу. Сильное повышение надежности системы в целом, в сочетании с использованием защиты памяти — идеал в виде «ни одна программа пользовательского режима не может нарушить работу ОС в целом» становится достижимым хотя бы теоретически, вне вытесняющей многозадачности он не достижим даже в теории. Возможность полного использования многопроцессорных и многоядерных систем.

• Недостатки: необходимость особой дисциплины при написании кода, особые требования к его реентрантности, к защите всех разделяемых и глобальных данных объектами типа критических секций и mutex’ов.

Алгоритмы планирования.

1. First-Come, First-Served (FCFS - первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на него. Очередь подобного типа имеет в программировании специальное наименование – FIFO, сокращение от First In, First Out (первым вошел, первым вышел).

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

2. Round Robin (RR). Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели). По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 – 100 миллисекунд. Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

3. Приоритетное планирование. При приоритетном планировании каждому процессу присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS.

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

4. Алгоритм SJF (Shortest-Job-First) представляет собой частный случай приоритетного планирования. Для алгоритма SJF в качестве приоритета выступает оценка продолжительности выполнения процесса. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс.

5. Многоуровневые очереди (Multilevel Queue). Для систем, в которых процессы могут быть легко рассортированы по разным группам, был разработан другой класс алгоритмов планирования. Для каждой группы процессов создается своя очередь процессов, находящихся в состоянии готовность. Этим очередям приписываются фиксированные приоритеты. Например, приоритет очереди системных процессов устанавливается выше, чем приоритет очередей пользовательских процессов. Внутри этих очередей для планирования могут применяться самые разные алгоритмы. Так, например, для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов – алгоритм RR.

5.) Обработка вложенных прерываний в x86. Средства синхронизации, состояние гонок, взаимные блокировки. Запрет прерываний, спинлоки, мьютексы, семафоры. Read-Copy-Update.

Вложенные исключения и прерывания

Процессор может принимать исключения и прерывания, находясь как в режиме ядра, так и в пользовательском режиме. Однако только при входе в режим ядра ​​из пользовательского режима процессор x86 автоматически переключает стеки перед записью старого состояния регистров в стек и вызовом соответствующего обработчика исключения через IDT. Если процессор уже находится в режиме ядра, когда происходит прерывание или исключение (нижние 2 бита регистра CS уже равны нулю), то процессор только записывает дополнительные значения в том же стеке ядра. В этом случае ядро ​​может корректно обработать вложенные исключения, вызванные кодом внутри самого ядра. Эта возможность является важным инструментом в реализации защиты, как мы увидим далее в разделе о системных вызовах.

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

+---------------------+ <---- старый ESP

| старый EFLAGS | " - 4

| 0x00000 | старый CS | " - 8

| старый EIP | " - 12

+---------------------+

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

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

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

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

Файл, Сигнал, Сокет, Канал, Именованный канал, Семафор, Разделяемая память,

Обмен сообщениями, Проецируемый в память файл, Очередь сообщений, Почтовый ящик

Состоя́ние го́нки (англ. race condition) — ошибка проектирования многопоточной системы или приложения, при которой работа системы или приложения зависит от того, в каком порядке выполняются части кода.

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

Запрет прерываний

Это можно сделать командой CLI. Ее нужно поместить в начало критической последовательности команд, а в конце расположить команду STI, разрешающую процессору воспринимать прерывания. Команда CLI запрещает только маскируемые прерывания, немаскируемые всегда обрабатываются процессором. Для маскирования определенных аппаратных прерываний нужно просто послать требуемую цепочку битов в порт с адресом 21H, который соответствует регистру маски прерываний (IMR).

Спинлок (англ. Spinlock — циклическая блокировка) — низкоуровневый примитив синхронизации, применяемый в многопроцессорных системах для реализации взаимного исключения.

Физически спинлок представляет собой переменную в памяти и реализуется на атомарных операциях, которые должны присутствовать в системе команд процессора. Каждый процессор, желающий получить доступ к разделяемому ресурсу, атомарно записывает условное значение «занято» в эту переменную, используя аналог операции swap (в архитектуре x86 — xchg). Если предыдущее значение переменной (возвращаемое командой) было «свободно» то считается, что данный процессор получил доступ к ресурсу, в противном случае, процессор возвращается к операции swap и крутится в цикле ожидая, пока спинлок будет освобождён. После работы с разделяемым ресурсом процессор-владелец спинлока должен записать в него условное значение «свободно».

Мью́текс (англ. mutex, от mutual exclusion — «взаимное исключение») — одноместный семафор, служащий в программировании для синхронизации одновременно выполняющихся потоков.

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

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

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

V-операция над семафором представляет инкремент значения семафора на 1. Если при этом имеются процессы, задержанные на выполнении P-операции на данном семафоре, один из этих процессов выходит из состояния ожидания и может выполнить свою P-операцию.

Read – Copy Update (RCU) – техника синхронизации, предназначенная для «почти read-only», то есть редко изменяемых, структур данных.

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

6.) Виртуальная память. Модели организации оперативной памяти. Сегментная и страничная трансляция x86. Таблицы трансляции.

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

При использовании виртуальной памяти упрощается программирование, так как программисту больше не нужно учитывать ограниченность памяти, или согласовывать использование памяти с другими приложениями. Для программы выглядит доступным и непрерывным все допустимое адресное пространство, вне зависимости от наличия в ЭВМ соответствующего объёма ОЗУ.

Одиночное непрерывное распределение

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

Распределение неперемещаемыми разделами

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

Характеристики

Список файлов ответов (шпаргалок)