Рубрики

Примечания в последнюю минуту — Операционные системы

Смотрите «Горящие заметки» по всем предметам по всем предметам здесь

Операционные системы: это интерфейс между пользователем и компьютерным оборудованием.

Типы операционной системы (ОС):

  1. Пакетная ОС — набор похожих заданий хранится в основной памяти для выполнения. Задание присваивается ЦП только после завершения выполнения предыдущего задания.
  2. Мультипрограммная ОС — основная память состоит из заданий, ожидающих процессорного времени. ОС выбирает один из процессов и назначает его ЦПУ. Всякий раз, когда исполняющемуся процессу нужно ждать какой-либо другой операции (например, ввода-вывода), ОС выбирает другой процесс из очереди заданий и назначает его ЦПУ. Таким образом, ЦП никогда не остается бездействующим, и пользователь получает представление о выполнении нескольких задач одновременно.
  3. Многозадачная ОС — Многозадачная ОС сочетает в себе преимущества многозадачного программирования ОС и планирования ЦП для быстрого переключения между заданиями. Переключатель настолько быстр, что пользователь может взаимодействовать с каждой программой во время ее работы.
  4. ОС с разделением времени — системы с разделением времени требуют взаимодействия с пользователем, чтобы инструктировать ОС для выполнения различных задач. ОС отвечает выводом. Инструкции обычно передаются через устройство ввода, например клавиатуру.
  5. ОС реального времени — ОС реального времени, как правило, создаются для выделенных систем для выполнения определенного набора задач в установленные сроки.

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

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

Новый поток или дочерний процесс данного процесса может быть введен с помощью системного вызова fork (). Процесс с n системными вызовами fork () генерирует 2 n — 1 дочерних процессов.
Существует два типа потоков:

  • Пользовательские темы
  • Ядра

Поток Java, потоки POSIX. Пример: Окно Solaris.

User level threadKernel level thread
User threads are implemented by users.kernel threads are implemented by OS.
OS doesn’t recognize user level threads.Kernel threads are recognized by OS.
Implementation of User threads is easy.Implementation of Kernel thread is complicated.
Context switch time is less.Context switch time is more.
Context switch requires no hardware support.Hardware support is needed.
If one user level thread performs blocking operation then entire process will be blocked.If one kernel thread performs blocking operation then another thread can continue execution.

Процесс:
Процесс — это исполняемая программа. Значение программного счетчика (ПК) указывает адрес следующей инструкции выполняемого процесса. Каждый процесс представлен блоком управления процессом (PCB).

Планирование процесса: Ниже приведены разные времена относительно процесса.

  1. Время прибытия — время, когда процесс прибывает в готовую очередь.
  2. Время завершения — время, в которое процесс завершает свое выполнение.
  3. Burst Time — Время, необходимое процессу для выполнения процессора.
  4. Время Поворота — Разница во времени между временем завершения и временем прибытия.
    Turn Around Time = Completion Time - Arrival Time 
  5. Время ожидания (WT) — Разница во времени между временем разворота и временем посылки.
    Waiting Time = Turn Around Time - Burst Time 

Зачем нам нужно планирование?
Типичный процесс включает в себя как время ввода-вывода, так и время процессора. В системе однопрограммирования, такой как MS-DOS, время, затрачиваемое на ожидание ввода / вывода, тратится впустую, и CPU в это время освобождается. В многопрограммных системах один процесс может использовать процессор, а другой ожидает ввода-вывода. Это возможно только при планировании процесса.

Задачи алгоритма планирования процессов:

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

Различные алгоритмы планирования:

  1. First Come First Serve (FCFS) : Самый простой алгоритм планирования, который планирует согласно времени прибытия процессов.
  2. Сначала самое короткое задание (SJF) : Процесс, который имеет самое короткое время пакета, запланирован первым.
  3. Сначала самое короткое оставшееся время (SRTF) . Это преимущественный режим алгоритма SJF, в котором задания планируются в соответствии с самым коротким оставшимся временем.
  4. Планирование циклического перебора (RR) : каждому процессу назначается фиксированное время циклическим способом.
  5. Планирование на основе приоритетов (не вытесняющее) : в этом планировании процессы планируются в соответствии с их приоритетами, то есть процесс с наивысшим приоритетом выполняется в первую очередь по расписанию. Если приоритеты двух процессов совпадают, то планирование осуществляется в соответствии с временем прибытия.
  6. Наивысший коэффициент отклика (HRRN) : в этом планировании запланированы процессы с наивысшим коэффициентом отклика. Этот алгоритм позволяет избежать голодания.
    Response Ratio = (Waiting Time + Burst time) / Burst time
  7. Планирование многоуровневой очереди (MLQ) : в соответствии с приоритетом процесса процессы помещаются в разные очереди. Обычно процессы с высоким приоритетом помещаются в очередь верхнего уровня. Только после завершения процессов из очереди верхнего уровня, запланированные процессы нижнего уровня запланированы.
  8. Планирование многоуровневой очереди обратной связи (MLFQ) : позволяет процессу перемещаться между очередями. Идея состоит в том, чтобы разделить процессы в соответствии с характеристиками их процессорных всплесков. Если процесс использует слишком много процессорного времени, он перемещается в очередь с более низким приоритетом.

Некоторые полезные факты о алгоритмах планирования:

  1. FCFS может вызывать длительное время ожидания, особенно когда первое задание занимает слишком много процессорного времени.
  2. И SJF, и алгоритмы с кратчайшим оставшимся временем могут вызвать голодание. Рассмотрим ситуацию, когда в готовой очереди находится длинный процесс, а более короткие процессы продолжают поступать.
  3. Если квант времени для планирования Round Robin очень велик, то он ведет себя так же, как планирование FCFS.
  4. SJF является оптимальным с точки зрения среднего времени ожидания для данного набора процессов. SJF дает минимальное среднее время ожидания, но проблема с SJF заключается в том, как узнать / предсказать время следующей работы.

Проблема критической секции:

  1. Критический раздел — часть кода в программе, где общие переменные доступны и / или обновлены.
  2. Раздел «Остаток» — оставшаяся часть программы, за исключением критического раздела.
  3. Обход условий — Окончательный вывод кода зависит от порядка доступа к переменным. Это называется гонкой вокруг состояния.

Решение проблемы критического сечения должно удовлетворять следующим трем условиям:

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

Инструменты синхронизации:
Семафор — это целочисленная переменная, доступ к которой осуществляется только через две атомарные операции: wait () и signal (). Элементарная операция выполняется в одном временном интервале ЦП без каких-либо преимуществ. Семафоры бывают двух типов:

  1. Подсчет семафора . Подсчет семафора — это целочисленная переменная, значение которой может находиться в неограниченной области.
  2. Mutex — бинарные семафоры называются Mutex. Они могут иметь только два значения: 0 или 1. Операции wait () и signal () работают с ними аналогичным образом.

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

  1. Взаимное исключение — один или несколько ресурсов не доступны для совместного использования (одновременно может использоваться только один процесс).
  2. Hold and Wait — процесс удерживает хотя бы один ресурс и ожидает ресурсов.
  3. No Preemption — ресурс не может быть взят из процесса, если процесс не освобождает ресурс.
  4. Циклическое ожидание набор процессов ожидает друг друга в круговой форме.

Методы обработки тупиковых ситуаций. Существует три способа устранения тупиковых ситуаций.

  1. Предотвращение или предотвращение тупиковых ситуаций. Идея состоит в том, чтобы не переводить систему в тупиковое состояние.
  2. Обнаружение и восстановление тупиковых ситуаций. Пусть возникнет взаимоблокировка, а затем выполните упреждающее действие для ее устранения.
  3. Проигнорируйте проблему все вместе — : если взаимоблокировка очень редка, то дайте ей случиться и перезагрузите систему. Это подход, который используют как Windows, так и UNIX.

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

Управление памятью:
Эти методы позволяют распределять память между несколькими процессами.

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

Методы управления памятью:

(а) Схемы распределения с одним разделом —
Память делится на две части. Одна часть предназначена для использования ОС, а другая — для использования пользователями.

(б) Схемы с несколькими разделами —

  1. Фиксированный раздел — память делится на разделы фиксированного размера.
  2. Переменный раздел — память делится на разделы переменного размера.

Схемы распределения разделов:

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

Замечания:

  • Наилучшее соответствие не обязательно дает наилучшие результаты для распределения памяти.
  • Причиной внешней фрагментации является условие в Фиксированном и Временном разделениях, согласно которому весь процесс должен быть размещен в смежной области памяти. Поэтому используется пейджинг .
  1. Пейджинг —
    Физическая память делится на кадры одинакового размера. Основная память делится на страницы фиксированного размера. Размер кадра физической памяти равен размеру кадра виртуальной памяти.
  2. Сегментация —
    Сегментация реализована, чтобы дать пользователям представление о памяти. Логическое адресное пространство представляет собой набор сегментов. Сегментация может быть реализована с использованием или без использования подкачки.

Ошибка страницы:

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

Алгоритмы замены страницы:

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

    Например, рассмотрим строку ссылки на страницу 1, 3, 0, 3, 5, 6 и 3 слота страницы. Изначально все слоты пусты, поэтому, когда пришли 1, 3, 0, они распределяются по пустым слотам -> 3 Page Faults. Когда приходит 3, он уже находится в памяти, поэтому -> 0 Page Faults. Затем приходит 5, он не доступен в памяти, поэтому он заменяет самый старый слот страницы, т.е. 1. -> 1 Page Fault. Наконец, 6, он также не доступен в памяти, поэтому он заменяет самый старый слот страницы, то есть 3 -> 1 Page Fault.

    Аномалия Белады:
    Аномалия Белади доказывает, что возможно увеличение количества сбоев страниц при увеличении количества кадров при использовании алгоритма замены страниц «первым пришел — первым обслужен» (FIFO). Например, если мы рассмотрим эталонную строку 3 2 1 0 3 2 4 3 2 1 0 4 и 3 слота, мы получим всего 9 ошибок страницы, но если мы увеличим количество слотов до 4, мы получим 10 ошибок страницы.

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

    Рассмотрим ссылочную строку страницы 7 0 1 2 0 3 0 4 2 3 0 3 2 и 4 слота страницы. Изначально все слоты пусты, поэтому, когда 7 0 1 2 выделяются пустым слотам -> 4 страницы сбоев. 0 уже есть, так что -> 0 Ошибка страницы. Когда пришло 3, оно заменит 7, потому что оно не будет использоваться в течение самого длительного промежутка времени в будущем. 0 уже есть, так что -> 0 Ошибка страницы. 4 будет иметь место 1 -> 1 Page Fault. Теперь для дальнейшей ссылки на страницу -> 0 Ошибка страницы, потому что они уже доступны в памяти.

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

  3. Наименее недавно использованные (LRU) —
    В этом алгоритме будет заменена страница, которая используется не так давно.

    Допустим, справочная строка страницы 7 0 1 2 0 3 0 4 2 3 0 3 2. Изначально у нас пустые 4-страничные слоты. Изначально все слоты пусты, поэтому, когда 7 0 1 2 выделяются пустым слотам -> 4 страницы сбоев. 0 уже их так -> 0 страница ошибки. Когда пришло 3, оно заменит 7, потому что это наименее недавно использованное -> 1 страница. 0 уже находится в памяти, поэтому -> 0 Ошибка страницы. 4 будет иметь место 1 -> 1 Page Fault. Теперь для дальнейшей ссылки на страницу -> 0 Ошибка страницы, потому что они уже доступны в памяти.

    Файловая система : файл представляет собой набор связанной информации, которая записывается во вторичном хранилище. Или файл представляет собой набор логически связанных объектов.

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

    1. КАТАЛОГ ОДНОГО УРОВНЯ : В этом случае для всех пользователей поддерживается единый каталог
    2. КАТАЛОГ ДВУХУРОВНЕВОГО : Из-за двух уровней для каждого файла есть путь к файлу, чтобы найти этот файл.
    3. ДЕРЕВО СТРУКТУРНЫЙ СПРАВОЧНИК : Каталог поддерживается в виде дерева. Поиск эффективен, а также есть возможность группировки.

    Методы размещения файлов :

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

    Планирование диска :
    Планирование диска выполняется операционными системами для планирования запросов ввода-вывода, поступающих на диск. Планирование диска также известно как планирование ввода / вывода.

    1. Время поиска. Время поиска — это время, необходимое для определения положения диска на указанной дорожке, где данные должны быть считаны или записаны.
    2. Задержка вращения: Задержка вращения — это время, которое требуемый сектор диска поворачивает в положение, обеспечивающее доступ к головкам чтения / записи.
    3. Время передачи: время передачи — это время для передачи данных. Это зависит от скорости вращения диска и количества передаваемых байтов.
    4. Время доступа к диску: время поиска + задержка вращения + время передачи
    5. Время отклика диска. Время отклика — это среднее время, затраченное запросом, ожидающим выполнения операции ввода-вывода. Среднее время ответа — это время ответа на все запросы.

    Алгоритмы планирования диска :

    1. FCFS: FCFS — самый простой из всех алгоритмов планирования дисков. В FCFS запросы обрабатываются в порядке их поступления в очередь на диске.
    2. SSTF: в SSTF (сначала самое короткое время поиска) запросы, имеющие самое короткое время поиска, выполняются первыми. Таким образом, время поиска каждого запроса заранее рассчитывается в очереди, а затем они планируются в соответствии с их рассчитанным временем поиска. В результате, запрос рядом с кронштейном диска будет выполнен первым.
    3. SCAN: В алгоритме SCAN плечо диска перемещается в определенном направлении и обслуживает запросы, поступающие на его пути, и после достижения конца диска оно меняет направление и снова обслуживает запрос, поступающий на его пути. Таким образом, этот алгоритм работает как лифт и, следовательно, также известен как алгоритм лифта.
    4. CSCAN: В алгоритме SCAN рычаг диска снова сканирует путь, который был отсканирован, после изменения его направления. Таким образом, может случиться так, что слишком много запросов ожидает на другом конце или может быть ноль или несколько запросов, ожидающих в сканируемой области.
    5. СМОТРИТЕ: Это похоже на алгоритм планирования диска SCAN за исключением того, что плечо диска, несмотря на переход к концу диска, обращается только к последнему запросу на обслуживание перед головкой, а затем меняет свое направление оттуда только. Таким образом, это предотвращает дополнительную задержку, которая произошла из-за ненужного обхода конца диска.
    6. CLOOK: Так как LOOK похож на алгоритм SCAN, аналогичным образом, CLOOK похож на алгоритм планирования диска CSCAN. В CLOOK рычаг диска, несмотря на переход к концу, переходит только к последнему запросу, который должен быть обслужен перед головкой, а затем оттуда переходит к последнему запросу другого конца. Таким образом, это также предотвращает дополнительную задержку, которая произошла из-за ненужного обхода конца диска.

    Рекомендуемые посты:

    Примечания в последнюю минуту — Операционные системы

    0.00 (0%) 0 votes