2,5 слова + 36 картинок.Вопросы интервью операционной системы печени слишком классные!

задняя часть Операционная система
2,5 слова + 36 картинок.Вопросы интервью операционной системы печени слишком классные!

Приглашаю всех посетить мой гитхаб и попросить звездуbestJavaer

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

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

Без дальнейших церемоний, давайте перейдем непосредственно к вопросам интервью.

Введение в операционные системы

Объясните, что такое операционная система.

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

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

Основные функции операционной системы

Вообще говоря, современные операционные системы в основном предоставляют следующие функции

  • 进程管理: Основная функция управления процессами — планирование задач.При одноядерном процессоре операционная система будет назначать задачу каждому процессу, и работа по управлению процессами очень проста, а при многоядерном процессоре операционная система необходимо не только назначать задачи процессам Кроме того, необходимо решать проблемы планирования, распределения и утилизации процессоров.
  • 内存管理: Управление памятью в основном заключается в том, что операционная система отвечает за управление выделением и перезапуском памяти, выделением памяти, когда она требуется процессу, и освобождением памяти после завершения процесса, координацией ресурсов памяти и обменом страницами в разумных пределах. алгоритм замены страницы
  • 设备管理: Выделите устройство в соответствии с определенным принципом распределения устройств, чтобы устройство и хост могли работать параллельно и предоставить пользователям хороший интерфейс устройства.
  • 文件管理: эффективно управлять пространством для хранения файлов, разумно организовывать и управлять файловой системой, а также предоставлять более эффективные методы и средства для доступа к файлам и защиты файлов.
  • 提供用户接口: операционная система предоставляет интерфейс для доступа к приложениям и оборудованию, позволяя пользователям инициировать системные вызовы через приложение, чтобы манипулировать оборудованием для достижения желаемых функций.

Несколько способов для программного обеспечения получить доступ к оборудованию

Программный доступ к оборудованию на самом деле является операцией ввода-вывода.

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

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

(1) Скорость передачи данных достаточно высока, чтобы удовлетворить потребности пользователей без потери данных;

(2) Накладные расходы системы невелики, а требуемых программ управления обработкой немного;

(3) Он может в полной мере использовать возможности аппаратных ресурсов, сделать устройство ввода-вывода максимально загруженным и максимально сократить время ожидания ЦП.

В соответствии с приведенными выше принципами управления операции ввода-вывода можно разделить на четыре категории.

  • 直接访问: Прямой доступ Пользовательский процесс напрямую управляет основной памятью или передачей информации между ЦП и периферийными устройствами. Режим прямого управления программой также называется режимом занятости/ожидания.
  • 中断驱动: Для уменьшения времени ожидания ЦП в режиме прямого управления программой и повышения степени параллелизма системы в системе введен механизм прерывания. После введения механизма прерывания периферийное устройство отправляет запрос на прерывание ЦП только тогда, когда операция завершается нормально или аварийно. В процессе ввода каждых данных устройством ввода-вывода в определенной степени реализуется параллельная работа ЦП и устройства ввода-вывода, поскольку нет необходимости во вмешательстве ЦП.

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

  • DMA 直接内存访问: Чтобы еще больше уменьшить вмешательство ЦП в операции ввода-вывода и предотвратить задержку ЦП для обработки из-за слишком большого количества параллельно работающих устройств или потери данных из-за несоответствия скорости, вводится метод управления DMA.
  • 通道控制方式: Канал, процессор, который не зависит от ЦП и отвечает за управление вводом и выводом, управляет прямым обменом данными между устройством и памятью. Имеет свои собственные канальные инструкции, которые инициируются ЦП и сигнализируют о прерывании ЦП, когда операция заканчивается.

Объясните, каково основное назначение операционной системы.

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

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

Какие существуют типы операционных систем

Операционная система обычно предварительно устанавливается перед покупкой компьютера. Большинство пользователей будут использовать операционную систему по умолчанию, но вы также можете обновить или даже изменить операционную систему. Но распространенных операционных систем всего три:Windows, macOS и Linux.

Почему приложения в системе Linux не могут работать непосредственно в Windows

Это общий вопрос, и вот конкретный ответ.

Один из них заключается в том, что формат системы Linux и системы Windows отличается,формат это протокол, что является значимыми данными в фиксированном месте. Формат исполняемого файла программы в Linux:elf,можно использоватьreadelfКоманда для просмотра заголовка файла elf.

И исполняемая программа под Windows естьPEформат, который является переносимым исполняемым файлом.

Другой момент заключается в том, что система Linux и система WindowsAPIДругое дело, что этот API относится к API операционной системы, а API в Linux называется系统调用, черезint 0x80Это мягкое прерывание реализовано. API в Windows помещается в файл библиотеки динамической компоновки, как его называют разработчики Windows.DLL, которая представляет собой библиотеку, содержащую код и данные. Исполняемые программы в Linux не получают системные ресурсы так же, как в Windows, поэтому, очевидно, они не могут работать в Windows.

Структура операционной системы

Монолитная система

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

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

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

Многие операционные системы поддерживают дополнительные расширения в дополнение к основной операционной системе, которая загружается при первом запуске компьютера. Например, драйверы устройств ввода-вывода и файловые системы. Эти части могут быть загружены по запросу. в UNIX они называются共享库(shared library), в винде это называется动态链接库(Dynamic Link Library,DLL). их расширение.dll,существуетC:\Windows\system32В каталоге более 1000 файлов DLL, поэтому не удаляйте файлы диска C легко, иначе он может взорваться.

многоуровневая система

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

микроядро

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

MINIX 3Это репрезентативная работа микроядра, и его конкретная структура выглядит следующим образом.

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

клиент-серверная модель

Стратегия микроядерного мышления заключается в разделении процессов на две категории:服务器, каждый сервер используется для предоставления услуг;客户端, воспользуйтесь этими услугами. Этот режим называется客户-服务器модель.

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

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

Почему это называется застрявшим в ядре?

Если структура программного обеспечения описывается слоями, то она должна быть такой: самый внешний слой — это прикладная программа, а внутренний слой — ядро ​​операционной системы.

Приложение находится на уровне привилегий 3, а ядро ​​ОС — на уровне привилегий 0. Если пользовательская программа захочет получить доступ к ресурсам операционной системы, она инициирует системный вызов и попадет в ядро, чтобы ЦП перешел в состояние ядра и выполнил код ядра. Что касается того, почему он тонет, давайте посмотрим на картинку.Внутреннее ядро ​​представляет собой вогнутую структуру, и оно кажется тонущим, поэтому это называется тонущим.

Что такое пользовательский режим и режим ядра

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

  • 内核态: ЦП в состоянии ядра может получить доступ к любым данным, включая периферийные устройства, такие как сетевые карты, жесткие диски и т. д. ЦП в состоянии ядра может переключаться с одной программы на другую и занимать ЦП без вытеснения, как правило, в привилегированный уровень Состояние 0 называется состоянием ядра.

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

Итак, почему есть пользовательский режим и режим ядра?

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

Как переключаться между режимом пользователя и режимом ядра?

Все пользовательские процессы выполняются в пользовательском режиме, но, как мы упоминали выше, пользовательские программы имеют ограниченные возможности доступа.Некоторые наиболее важные операции, такие как чтение данных с жесткого диска и клавиатуры, могут выполняться только в режиме ядра. данные очень важны для пользовательской программы. Таким образом, он включает преобразование в двух режимах, а именноПользовательский режим -> Режим ядра -> Пользовательский режим, и единственное, что может делать эти операции, это系统调用, и единственными, кто может выполнять системные вызовы, являются操作系统.

Общий пользовательский режим -> преобразование режима ядра, мы называем это ловушкой в ​​​​ядре, также известной как陷阱指令(trap instruction).

Их рабочий процесс выглядит следующим образом:

  • Сначала пользовательская программа вызоветglibcБиблиотеки, glibc — это стандартная библиотека и набор основных библиотек. В библиотеке определены многие ключевые API.
  • Библиотека glibc умеет обращаться к разным архитектурам.系统调用Правильный способ подготовить системный вызов — установить параметры, передаваемые пользовательским процессом, в соответствии с двоичным интерфейсом приложения архитектуры.
  • Затем библиотека glibc вызывает软件中断指令(SWI), эта инструкция обновленаCPSRзарегистрируйтесь, чтобы изменить режим на режим супервизора, затем перейдите к адресу0x08место.
  • Пока что весь процесс все еще находится в пользовательском режиме, после выполнения инструкции SWI процессу разрешено выполнять код ядра, а MMU теперь разрешает доступ к виртуальной памяти ядра.
  • Начиная с адреса 0x08, процесс выполняет загрузку и переходит к обработчику прерывания, который являетсяvector_swi().
  • В vector_swi() извлеките номер системного вызова SCNO из инструкции SWI, затем используйте SCNO в качестве таблицы системных вызовов.sys_call_tableИндекс вызова функции системного вызова.
  • После завершения выполнения системного вызова регистры пользовательского режима восстанавливаются перед выполнением в пользовательском режиме.

что такое ядро

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

Здесь нужно знать, чтоboot loader.

Загрузчик также известен как загрузчик, который может поместить операционную систему компьютера в память. При включении питания или перезагрузке компьютера BIOS выполнит некоторые начальные тесты, а затем передаст управление загрузчику.主引导记录(MBR).

Что такое система реального времени

Операционные системы реального времени предъявляют строгие требования ко времени, а операционные системы реального времени делятся на два типа:Жесткий режим реального времени и мягкий режим реального времени

硬实时操作系统Оговаривается, что определенное действие должно быть завершено или выполнено в течение определенного времени.Например, в цеху по производству автомобилей сварочный аппарат должен завершить сварку в течение определенного времени.Слишком ранняя или слишком поздняя сварка приведет к необратимому повреждению машина.

软实时操作系统Хотя время от времени нарушать окончательный лимит времени нежелательно, это все же допустимо. и не нанесет необратимого ущерба. Например, цифровое аудио, мультимедиа и мобильные телефоны — все это программные операционные системы реального времени.

Вы можете просто понять два показателя жесткого реального времени и мягкого реального времени:Должна ли она быть завершена вовремя и нанесен ли серьезный ущерб.

Процесс загрузки операционной системы Linux

Когда компьютер включен,BIOSбудет осуществляться开机自检(Power-On-Self-Test, POST), чтобы обнаружить и инициализировать оборудование. Потому что при запуске операционной системы будут использоваться диск, экран, клавиатура, мышь и другие устройства. Затем первый раздел на диске, также известный какMBR(Master Boot Record)Основная загрузочная запись, которая считывается в фиксированную область памяти и выполняется. В этом разделе очень маленькая программа, всего 512 байт. Программа вызывает загрузочную независимую программу с диска, и загрузочная программа копирует себя в память старшего адреса, чтобы освободить память младшего адреса для операционной системы.

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

Используется код запуска ядра汇编语言Завершено, в основном включая создание стека ядра, идентификацию типа ЦП, вычисление памяти, отключение прерываний, запуск модуля управления памятью и т. д., а затем вызов основной функции языка C для выполнения части операционной системы.

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

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

После того, как все оборудование сконфигурировано, следующее, что нужно сделать, — тщательно обработать процесс 0 вручную, настроить его стек, затем запустить его, выполнить инициализацию, настроить часы и смонтировать файловую систему. Создайтеinit 进程(进程 1 )и守护进程(进程 2).

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

Затем процесс /etc/rc считывает данные из /etc/ttys, в которых перечислены все терминалы и атрибуты. Для каждого включенного терминала процесс вызывает функцию fork для создания своей копии, выполняет внутреннюю обработку и запускаетgettyпрограмма о.

Программа getty наберет на терминале

login:

Ожидание ввода пользователем имени пользователя, после ввода имени пользователя программа getty завершается, и программа входа в систему/bin/loginначать операцию. Программа входа требует пароль и хранится с/etc/passwdПароли сравниваются, и, если они введены правильно, программа входа в систему заменяет себя программой оболочки пользователя и ожидает первой команды. Если оно неверно, программа входа запрашивает другое имя пользователя.

Весь процесс запуска системы выглядит следующим образом

Процессы и потоки

Преимущества многопроцессорных систем

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

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

Что такое процесс и таблица процессов

进程Это экземпляр исполняемой программы, например, веб-программа — это процесс, оболочка — это процесс, типора редактора статей — тоже процесс.

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

Чтобы отслеживать состояние активности каждого процесса, операционная система поддерживает进程表. Внутри таблицы процессов перечислены статус каждого процесса и ресурсы, используемые каждым процессом.

Что такое поток, разница между потоком и процессом

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

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

Вот разница между потоком и процессом, удерживающим ресурсы

Потоки не так независимы, как процессы, и данные будут совместно использоваться потоками.

Накладные расходы на создание потока намного меньше, чем на процесс, потому что для создания потока требуется только堆栈指针и程序计数器Вот и все, а создание процесса требует от операционной системы выделения нового адресного пространства, ресурсов данных и т. д., что относительно дорого.

что такое переключение контекста

Для одноразового однорепенного процессора одноретики можно выполнить только одну инструкцию CPU. Контекстный переключательМеханизм для выделения ресурсов ЦП из одного процесса к другому. С точки зрения пользователя, компьютер способен выполнять несколько процессов параллельно именно благодаря быстрому переключению контекста операционной системы. В процессе переключения операционной системе необходимо сначала сохранить состояние текущего процесса (включая указатель пространства памяти, исполняемые в данный момент инструкции и т. д.), а затем прочитать состояние следующего процесса, после чего выполнить процесс.

Каковы преимущества использования многопоточности

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

  • Возможность улучшить порядок ответов пользователям
  • Разделение ресурсов в процессах
  • более экономичный
  • Умение иметь четкое представление о многопоточных архитектурах

Как завершается процесс

прекращение процесса

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

  • 正常退出(自愿的)
  • 错误退出(自愿的)
  • 严重错误(非自愿的)
  • 被其他进程杀死(非自愿的)

Выйти нормально

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

ошибка выхода

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

cc foo.c	

Чтобы иметь возможность скомпилировать foo.c, но файл не существует, компилятор выдает объявление и завершает работу. Интерактивные процессы, обращенные к экрану, обычно не завершаются напрямую, когда задан неправильный аргумент, потому что это не имеет смысла с точки зрения пользователя, пользователь должен знать, что произошло, и хочет повторить попытку, поэтому приложение обычно всплывает диалоговое окно, информирующее пользователя о том, что произошла системная ошибка и необходимо повторить попытку или выйти.

Серьезная ошибка

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

убит другим процессом

Четвертая причина завершения процесса заключается в том, что процесс выполняет системный вызов, который сообщает операционной системе завершить процесс. В UNIX этим системным вызовом является kill. Соответствующая функция в Win32 естьTerminateProcess(обратите внимание, что это не системный вызов).

связь между процессами

Способов связи между процессами много, прежде всего нужно понимать следующие понятия

  • Состояние гонки: то есть, когда два или более потока изменяют общие данные одновременно, что влияет на правильность программы, это называется竞态条件(race condition).

  • Критический раздел: не только共享资源Это вызовет состояние гонки. На самом деле, общие файлы и общая память также вызовут состояние гонки. Так как же их избежать? Может быть, одно предложение может резюмировать это:Предотвратить одновременное чтение и запись общих ресурсов (включая общую память, общие файлы и т. д.) одним или несколькими процессами.. Другими словами, нам нужен互斥(mutual exclusion)Условный, то есть, если процесс использует общие переменные и файлы определенным образом, другим процессам, кроме процесса, запрещается делать такие вещи (доступ к унифицированным ресурсам).

    Хорошее решение должно содержать следующие четыре условия

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

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

Связь между процессами выражается в профессиональных терминах какInter Process Communication,IPC, он в основном имеет следующие 7. способ общения

  • 消息传递: Передача сообщений — это механизм для реализации связи и синхронного ожидания между процессами.При использовании передачи сообщений связь между процессами не требует общих переменных, и связь может осуществляться напрямую; передача сообщений делится на отправителя и получателя.
  • 先进先出队列: Очередь FIFO относится к связи между двумя несвязанными процессами. Два процесса могут взаимодействовать друг с другом. Это полнодуплексный метод связи.
  • 管道: Каналы используются для связи между двумя связанными процессами.Это полудуплексный метод связи.Если требуется полный дуплекс, требуется еще один канал.
  • 直接通信: В этом методе связи между процессами существует только одна связь между процессами, и имена двух взаимодействующих сторон должны быть четко определены между процессами.
  • 间接通信: Непрямое общение означает, что две взаимодействующие стороны не устанавливают соединение напрямую, а находят посредника, который может быть объектом и т. д., где процесс может размещать сообщения и удалять сообщения из него, чтобы достичь цели межпроцессного взаимодействия. - процесс коммуникации.
  • 消息队列: Очередь сообщений — это связанный список сообщений, хранящихся в ядре, который идентифицируется идентификатором очереди сообщений, который может обеспечить полнодуплексное коммуникационное соединение между различными процессами.
  • 共享内存: Общая память — это использование памяти между всеми процессами для установления соединения, этот тип должен синхронизировать доступ процессов для защиты друг друга.

модель межпроцессного состояния

модель процесса с тремя состояниями

Когда процесс запускается, он может пройти через следующие состояния

На рисунке присутствуют три состояния

  1. 运行态: Состояние выполнения относится к времени, когда процесс фактически занимает квант времени ЦП для выполнения.
  2. 就绪态: Состояние готовности означает работоспособность, но в состоянии готовности, поскольку другие процессы запущены.
  3. 阻塞态: Состояние блокировки также известно как состояние сна, что означает, что процесс не имеет условий выполнения и ожидает планирования со стороны ЦП.

Логически, рабочее состояние и состояние готовности очень похожи. В обоих случаях это означает процесс可运行, но во втором случае кванты процессорного времени не получаются. Третье состояние отличается от первых двух тем, что процесс не может работать, а также не может работать, когда ЦП простаивает.

Три государства будут включать переключение между четырьмя состояниями, когда операционная система не может продолжаться с процессом обнаружения, будет происходить状态1по циклу, в некоторых системах процесс выполняет системные вызовы, такие какpause, чтобы получить заблокированное состояние. В других системах, включая UNIX, процесс автоматически завершается, когда нет доступных входных данных для чтения из канала или специального файла (например, терминала).

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

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

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

Модель процесса с пятью состояниями

На основе модели с тремя состояниями добавляются два состояния, а именно新建и终止государство.

  • Новое состояние: новое состояние процесса — это когда процесс только что создан.

Создание процесса требует двух шагов: выделение необходимых ресурсов и пространства для нового процесса, перевод процесса в состояние готовности и ожидание запланированного выполнения.

  • Состояние завершения: Состояние завершения процесса означает, что процесс завершил свое выполнение, достиг конечной точки или должен прервать процесс из-за ошибки.

Завершение процесса требует двух шагов:

  1. Сначала подождите, пока операционная система или связанные с ней процессы позаботятся об этом.

  2. Занятые ресурсы затем восстанавливаются и удаляются системой.

Какие есть алгоритмы планирования

Алгоритмы планирования делятся на три категории: планирование в пакетной обработке, планирование в интерактивных системах и планирование в системах реального времени.

Планирование партиями

Первый пришел первый обслужен

Это как первый пришел первый обслужен. . . Вероятно, простейшая конструкция алгоритма планирования без вытеснения такова.先来先服务(first-come,first-serverd). Используя этот алгоритм, процессоры выделяются процессам в порядке запросов. По сути, это будет ожидающая очередь готовых процессов. Когда первая задача входит в систему извне, она сразу же запускается и может выполняться в течение любого промежутка времени. Он не ломается, потому что он слишком долго работает. Когда поступают другие задания, они помещаются в конец очереди готовности. Когда работающий процесс блокируется, запускается первый процесс в очереди ожидания. Когда заблокированный процесс возвращается в состояние готовности, он будет похож на вновь поступившую задачу и будет поставлен в очередь в конце очереди, то есть в конце всех процессов.

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

Однако у принципа «первым пришел - первым обслужен» есть и недостаток, то есть нет отношения приоритетов.Представьте, если в очереди стоят 100 процессов ввода-вывода, а 101-й процесс интенсивно использует ЦП, разве ему не нужно ждать? for 100 Процесс ввода-вывода будет ожидать только запуска процесса, интенсивно использующего ЦП, после запуска, что на практике невозможно, поэтому необходимо появление приоритетных или вытесняющих процессов, чтобы определить приоритет важных процессов для запуска.

сначала самая короткая работа

В пакетной обработке используется второй алгоритм планирования.最短作业优先(Shortest Job First), будем считать, что время работы известно. Например, страховая компания, поскольку подобная работа выполняется каждый день, можно довольно точно предсказать, сколько времени потребуется для обработки пакета из 1000 требований. Когда во входной очереди запускается несколько одинаково важных заданий, планировщик должен использовать алгоритм поиска кратчайшего первого задания.

Как показано на рисунке а выше, имеется 4 задания A, B, C, D со временем выполнения 8, 4, 4 и 4 минуты соответственно. Работая в порядке, показанном на диаграмме, время оборота для A составляет 8 минут, B — 12 минут, C — 16 минут, D — 20 минут, а среднее время — 14 минут.

Теперь рассмотрим запуск 4 заданий с использованием алгоритма «Сначала самое короткое задание», как показано на рис. b выше. Текущее время обработки составляет 4, 8, 12, 20, а среднее значение составляет 11 минут, что может доказать, что самое короткое задание сначала является оптимальным. Рассмотрим случай 4 заданий со временем выполнения a, b, c, d. Первая работа заканчивается в момент времени а, вторая — в момент времени а + b и так далее. Среднее время оборота составляет (4a + 3b + 2c + d) / 4 . Очевидно, что a оказывает наибольшее влияние на среднее значение, поэтому a должна быть самой короткой первой работой, за которой следует b, затем c и, наконец, d. Это может повлиять только на собственное время выполнения.

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

Кратчайшее оставшееся время сначала

Упреждающая версия кратчайшего задания сначала называется最短剩余时间优先(Shortest Remaining Time Next)алгоритм. Используя этот алгоритм, планировщик всегда выбирает процесс с наименьшим оставшимся временем выполнения для запуска. Когда поступает новое задание, все его время сравнивается с оставшимся временем текущего процесса. Если новый процесс занимает меньше времени, чем текущий процесс, текущий процесс приостанавливается и запускается новый процесс. Таким образом, краткосрочные рабочие места могут быть хорошо обслужены.

Планирование в интерактивных системах

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

круговое планирование

Один из старейших, простейших, честных и широко используемых алгоритмов —轮询算法(round-robin). Каждому процессу назначается период времени, называемый时间片(quantum), процесс может выполняться в течение этого интервала времени. Если процесс все еще выполняется в конце временного интервала, ЦП вытесняется и назначается другому процессу. Если процесс блокируется или завершается до окончания кванта времени, процессор немедленно переключается. Алгоритм опроса относительно прост в реализации. Что делает планировщик, так это поддерживает список запущенных процессов, как на рисунке ниже, и когда у процесса заканчиваются кванты времени, он перемещается в конец очереди, как b на рисунке ниже.

приоритетное планирование

Дело в том, что не все процессы имеют одинаковый приоритет. Например, иерархия в университете начинается с деканов, затем профессоров, секретарей, вспомогательного персонала и, наконец, студентов. Это достигается за счет учета внешней ситуации.优先级调度(priority scheduling)

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

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

сначала самый короткий процесс

Для пакетных систем, поскольку самая короткая задача сначала имеет самое короткое время отклика, один из способов состоит в том, чтобы строить догадки на основе прошлого поведения процесса и выполнять ту, которая имеет наименьшее предполагаемое время выполнения. Предположим, что расчетное время выполнения каждой команды на каждом терминале равноT0, теперь предположим, что время его следующего выполнения измеряется какT1, расчетное время может быть улучшено путем взвешивания двух значений, т.е.aT0+ (1- 1)T1. Выбирая значение a, вы можете решить, следует ли как можно быстрее забыть о старых средах выполнения или помнить о них в течение длительного периода времени. Когда a = 1/2, можно получить следующую последовательность

Видно, что после трех раундов доля T0 в новой оценке снизилась до 1/8.

Этот метод получения следующей оценки путем взятия средневзвешенного значения текущего измерения и предыдущей оценки иногда называют老化(aging). Этот метод использует много случаев, когда прогнозируемое значение основано на текущем значении.

расписание лотереи

Существует алгоритм, который может не только давать результаты предсказания, но и иметь относительно простую реализацию, т.彩票调度(lottery scheduling)алгоритм. Его основная идея обеспечивает различные системные ресурсы для процесса.彩票. Когда принято решение о планировании, лотерейный билет вытягивается случайным образом, и процесс с лотерейным билетом получает ресурс. Например, когда ЦП запланирован, система может проводить 50 лотерейных розыгрышей в секунду, и каждый выигрышный процесс будет вознагражден дополнительным временем выполнения.

Лотерейный билет можно понимать как бафф, этот бафф с вероятностью 15% позволяет сгенерировать速度之靴Эффект.

Справедливое распределение по расписанию

Если пользователь 1 запускает 9 процессов, а пользователь 2 запускает процесс, используя циклический алгоритм или алгоритм планирования с равным приоритетом, то пользователь 1 получит 90% процессорного времени, а пользователь 2 получит 10% процессорного времени.

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

Какие показатели влияют на планировщик

Существует несколько факторов, определяющих качество планировщика.

  • Использование процессора:

Процент времени, в течение которого ЦП выполняет задачи (то есть не простаивает).

  • время ожидания

Это время, когда процессы выполняются по очереди, то есть время, когда процесс переключается

  • пропускная способность

Количество завершенных процессов в единицу времени

  • Время отклика

Это время, прошедшее с момента отправки процесса до получения полезных результатов.

  • Время оборота

Время, прошедшее с момента отправки процесса до завершения процесса.

Что такое алгоритм планирования RR

RR(round-robin)Алгоритм планирования в основном нацелен на систему с разделением времени.Алгоритм планирования RR будет циклически выделять одну и ту же часть кванта времени каждому процессу.Алгоритм планирования RR не имеет концепции приоритета. Реализация этого алгоритма относительно проста, и каждый поток занимает квант времени, поэтому проблема нехватки потока отсутствует.

Управление памятью

Что такое пейджинг по запросу

В операционной системе процессы загружаются в память единицами страниц, а пейджинг по запросу — это虚拟内存метод управления. В системах, использующих пейджинг по запросу, это происходит только при попытке доступа к диску, на котором находится страница, и эта страница еще не находится в памяти.缺页异常, операционная система копирует страницы диска в память.

что такое виртуальная память

虚拟内存Это схема выделения памяти и механизм, который можно использовать для облегчения выделения памяти. Мы знаем, что приложения загружаются в память страницами. Но не все страницы загружаются в память, а аппаратное и программное обеспечение в компьютере восполняет нехватку памяти за счет временного переноса данных из ОЗУ на диск. Если виртуальной памяти нет, как только вы заполните память компьютера, компьютер скажет вам

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

Как реализована виртуальная память

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

  • Запрос управления страничным хранилищем.
  • Запросить управление сегментированным хранилищем.
  • Запросить управление хранилищем сегментированных страниц.

В любом случае требуется некоторая аппаратная поддержка. Требуется общая поддержка в следующих областях:

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

Почему память сегментирована?

Память — это устройство с произвольным доступом, для памяти не нужно искать с нуля, просто дайте адрес напрямую. Сегментация памяти происходит от8086 CPUВ начале ЦП 8086 по-прежнему имеет ширину 16-битного регистра. Диапазон чисел, которые могут быть сохранены в 16-битном регистре, составляет 2 в 16-й степени, то есть 64 КБ.虚拟地址, только физический адрес, то есть, если две одинаковые программы скомпилированы с одним и тем же адресом, то две программы не могут работать одновременно. Чтобы решить эту проблему, разработчики операционной системы предложили использовать ЦП.段基址 + 段内偏移способ доступа к произвольной памяти. Преимущество этого в том, что программа может重定位,Это также первая причина, по которой память сегментируется..

Так что же такое переезд?

Проще говоря, это изменить адрес инструкции в программе на другой адрес, а содержимое, хранящееся по этому адресу, остается прежним.

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

Любовь, любовь, этот регистр немного интересен

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

ЦП 8086 имеет 20 адресных шин, максимальная адресная емкость составляет 1 МБ, а ширина регистра, в котором находится базовый адрес сегмента, составляет всего 16 бит, а максимальная адресная емкость составляет 64 КБ. Очевидно, что 64 КБ не могут соответствовать максимальному диапазону адресации. 1 МБ., поэтому необходимо сегментировать память. Максимальная адресная способность каждого сегмента составляет 64 КБ, но она все еще не может достичь максимальной адресной способности 1 МБ, поэтому в это время необходимо偏移地址Адрес смещения также хранится в регистре, и возможность адресации также составляет 64 КБ.На данный момент он все еще не может соответствовать адресации 1 МБ, поэтому разработчик ЦП переместил адресную единицу и переместил базовый адрес сегмента в слева на 4 бита, а затем добавить к 16-битному адресу смещения сегмента, чтобы получить возможность адресации 1 МБ.Таким образом, вторая цель сегментации памяти — получить доступ ко всей памяти..

Разница между физическим адресом, логическим адресом, эффективным адресом, линейным адресом и виртуальным адресом

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

существует实模式Затем базовый адрес сегмента + смещение сегмента обрабатывается сумматором адреса, передается по адресной шине и, наконец, преобразуется в物理地址.

Но когда保护模式Далее вызывается базовый адрес сегмента + смещение внутри сегмента线性地址, но базовый адрес сегмента в это время не может называться реальным адресом, а будет называться选择子Селектор представляет собой индекс, который эквивалентен нижнему индексу массива.По этому индексу можно найти соответствующий дескриптор сегмента в GDT.Дескриптор сегмента записываетначало сегмента, размер сегментаДождитесь информации, чтобы получить базовый адрес. Если в это время функция подкачки памяти не включена, то этот линейный адрес можно использовать непосредственно как физический адрес для прямого доступа к памяти. Если функция пейджинга включена, то этот линейный адрес имеет другое имя, т.е.虚拟地址.

Будь то в реальном режиме или в защищенном режиме, адрес смещения внутри сегмента вызывается有效地址. Эффективные бойкоты также являются логическими адресами.

Линейные адреса можно рассматривать как虚拟地址, виртуальные адреса не являются реальными физическими адресами, но в конечном итоге виртуальные адреса будут сопоставлены с физическими адресами. Ниже приведено сопоставление виртуального адреса -> физического адреса.

Как управляется свободная память

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

Управление с помощью растровых изображений

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

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

Размер единицы выделения — важный фактор дизайна: чем меньше единица выделения, тем больше растровое изображение. Однако даже при 4-байтовой единице распределения 32-битной памяти требуется только 1 бит в растровом изображении.32nДля бита памяти требуется растровое изображение из n битов, поэтому1 растровое изображение занимает только 1/32 памяти. Если вы выберете больший блок памяти, растровое изображение должно быть меньше. Если размер процесса не является целым числом, кратным единице выделения памяти, то в последней единице выделения памяти тратится много памяти.

位图Предоставляет простой способ отслеживания использования памяти в памяти фиксированного размера, посколькуРазмер растрового изображения зависит от размера памяти и блока распределения.. Есть проблема с этим подходом, когда решение состоит в том, чтобы поместить процесс с k единицами распределения в память,内容管理器(memory manager)В растровом изображении необходимо искать строку, способную содержать k последовательных нулевых битов. Поиск непрерывной строки из нулей заданной длины в растровом изображении занимает очень много времени, что является недостатком растровых изображений. (Это можно просто понять как поиск длинного списка свободных ячеек массива в беспорядочном массиве)

использовать бесплатный список

Еще один способ отслеживать использование памяти — поддерживать связанный список выделенных и свободных сегментов памяти, который может содержать свободные области для процесса или двух процессов. Доступно Рисунок c вышедля представления использования памяти. Каждый элемент в связанном списке может представлять空闲区(H)или进程(P)Начальный флаг, длина и позиция следующего элемента связанного списка.

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

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

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

Каковы алгоритмы замены страницы?

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

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

  • 最优算法Заменяет последнюю страницу, к которой нужно получить доступ, на текущей странице. К сожалению, нет возможности определить, какая страница была посещена последней,因此实际上该算法不能使用. Однако его можно использовать в качестве эталона, по которому оцениваются другие алгоритмы.
  • NRUАлгоритм классифицирует атмосферу страницы по четырем категориям в соответствии с состоянием бита R и бита M. Страница выбирается случайным образом из категории с наименьшим номером. Алгоритм NRU прост в реализации, но его производительность не очень высока. Существуют лучшие алгоритмы.
  • FIFOПорядок, в котором страницы загружаются в память, отслеживается, и страницы помещаются в связанный список. Можно удалить самые старые страницы, которые все еще используются, поэтому этот алгоритм также не является хорошим выбором.
  • 第二次机会Алгоритм представляет собой модификацию FIFO, которая проверяет, используется ли страница, прежде чем удалить ее. Если страница используется, она зарезервирована. Это улучшение значительно повышает производительность.
  • 时钟Алгоритмы — это еще одна форма реализации алгоритмов второго шанса.Алгоритм часов имеет производительность, аналогичную алгоритму второго шанса, но для его выполнения требуется меньше времени.
  • LRUАлгоритм очень хороший алгоритм, но не特殊的硬件(TLB)сложно осознать. Без аппаратного обеспечения алгоритм LRU не может быть использован.
  • NFUАлгоритм является приближением к LRU, и его производительность не очень высока.
  • 老化Алгоритм представляет собой реализацию, которая ближе к алгоритму LRU и может быть реализована лучше, поэтому это хороший выбор.
  • Оба последних алгоритма используют алгоритм рабочего множества. Алгоритм рабочего набора обеспечивает разумную нагрузку на производительность, но его реализация сложна.WSClock— еще один вариант, который не только обеспечивает хорошую производительность, но и может быть эффективно реализован.

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

Файловая система

Способы повышения производительности файловой системы

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

Так что оптимизация диска очень нужна, и ниже мы обсудим несколько методов оптимизации.

тайник

Самый распространенный способ уменьшить количество обращений к диску — использовать块高速缓存(block cache)или缓冲区高速缓存(buffer cache). Кэш относится к серии блоков, которые логически принадлежат диску, но фактически хранятся в памяти из соображений производительности.

Существуют разные алгоритмы управления кешем, общий алгоритм такой: проверить все запросы на чтение, чтобы увидеть, есть ли блок в кеше. Если он присутствует, операции чтения могут выполняться без доступа к диску. Если контрольного блока больше нет в кэше, он сначала считывается в кэш, а затем копируется туда, где это необходимо. После этого все запросы к тому же блоку проходят高速缓存Что нужно сделать.

Работа кэша показана на следующем рисунке

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

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

блокировать опережающее чтение

Второй значительно улучшенной производительностью файловой системы являетсяПовысьте частоту попаданий, пытаясь записать блоки в кеш заранее, до того, как они потребуются.. Многие файлы顺序读取. Если к файловой системе поступает запрос на создание блока k в файле, файловая система выполняет соответствующую операцию и по завершении проверяет кэш, чтобы определить, кэширован ли уже блок k + 1. Если нет, файловая система планирует упреждающее чтение для k + 1, поскольку ожидается, что файл сможет читать непосредственно из кэша, когда используется блок.

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

Уменьшите движение рычага диска

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

Однако даже с бесплатными списками вы можете использовать块簇Технологии. То есть дисковое хранилище отслеживается не по блокам, а по смежным кластерам блоков. Если размер сектора составляет 512 байт, возможно, система использует блоки по 1 КБ (2 сектора), но выделяет дисковое пространство в единицах по 2 блока (4 сектора). Это не то же самое, что блоки диска размером 2 КБ, поскольку в кэше по-прежнему используются блоки размером 1 КБ, а передача данных между диском и памятью также выполняется в 1 КБ, но в бездействующей системе файлы считываются последовательно. количество операций поиска может быть сокращено вдвое, что значительно повысит производительность файловой системы. Варианты этого подхода доступны, если рассматривается ротационное позиционирование. При размещении блоков система пытается хранить последовательные блоки в файле на одном и том же цилиндре.

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

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

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

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

Дефрагментация диска

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

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

Дефрагментация диска хорошо работает с файловой системой. Файловые системы Linux (особенно ext2 и ext3), как правило, не так сложны для дефрагментации, как Windows, из-за того, как они выбирают блоки диска, поэтому ручная дефрагментация диска требуется редко. Более того, на SSD не влияет фрагментация диска.На самом деле дефрагментация на SSD лишняя.Не только не повышает производительность,но и изнашивает SSD. Таким образом, дефрагментация только сократит срок службы SSD.

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

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

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

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

Если драйвер диска получает по одному запросу за раз и выполняет запросы в том порядке, в котором они были получены, этот метод обработки先来先服务(First-Come, First-served, FCFS), таким образом сложно оптимизировать время поиска. Поскольку каждый раз будет обрабатываться по порядку, независимо от порядка, возможно, что после этого чтения вам нужно будет подождать, пока диск повернется в течение одной недели, прежде чем продолжить чтение, в то время как другие цилиндры могут быть прочитаны немедленно. в этом случае каждый запрос также будет поставлен в очередь.

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

Улучшение алгоритма «первым пришел – первым обслужено» заключается в использовании最短路径优先(SSF)алгоритм, который описан ниже.

Если мы обращаемся к дорожке № 6, запросы на 11, 2, 4, 14, 8, 15, 3 происходят одновременно, если мы принимаем принцип «первым пришел — первым обслужен», как показано на следующем рисунке.

Мы можем рассчитать количество дисков, охватываемых плечом диска, как 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51, что эквивалентно охвату дисков 51. Если мы сначала используем кратчайший путь, давайте вычислим составные диски.

Количество объединенных дисков равно 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17, что экономит вдвое больше времени по сравнению с 51.

Однако алгоритм поиска кратчайшего пути не идеален, и с этим алгоритмом все еще есть проблемы, т.е.优先级проблема,

Вот прототип для справки, которым является лифт в нашей повседневной жизни.电梯算法(elevator algorithm)выполнять планирование для достижения противоречивых целей эффективности координации и справедливости. Лифт, как правило, продолжает двигаться в одном направлении до тех пор, пока в этом направлении не будет запроса, а затем меняет направление.

Алгоритм лифта должен поддерживать二进制位, который является текущим битом направления:UP(向上)илиDOWN(向下). Когда запрос обрабатывается, драйвер диска или лифта проверяет этот бит, и, если бит находится в состоянии UP, рычаг диска или модуль лифта переходит к следующему более высокому или незавершенному запросу. Если в старших битах нет невыполненных запросов, выбирается противоположное направление. Когда бит направленияDOWN , также есть запрос младшего разряда, и рычаг диска поворачивается в эту точку. Если его нет, то он просто останавливается и ждет.

Давайте возьмем пример для описания алгоритма лифта, Например, порядок, в котором обслуживается каждый цилиндр, 4, 7, 10, 14, 9, 6, 3, 1, тогда его блок-схема выглядит следующим образом.

Таким образом, количество досок, которые должен пересечь алгоритм лифта, равно 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22.

Алгоритм лифта обычно уступает алгоритму SSF.

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

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

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

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

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

Различные уровни RAID

RAID называется磁盘冗余阵列, именуемый磁盘阵列. Использование технологии виртуализации для объединения нескольких жестких дисков в одну или несколько групп массивов дисков позволяет повысить производительность или избыточность данных.

RAID имеет разные уровни

  • RAID 0 — чередующийся дисковый массив без отказоустойчивости
  • RAID 1 — зеркалирование и дуплекс
  • RAID 2 — код исправления ошибок в памяти
  • RAID 3 — четность с чередованием битов
  • RAID 4 — контроль четности с чередованием блоков
  • RAID 5 — распределенная четность с чередованием блоков
  • RAID 6 — резервирование P+Q

статьи ИО

Что такое часы в операционной системе

时钟(Clocks)также называется定时器(timers), часы/таймеры необходимы для любой системы программирования. Часы отвечают за поддержание времени, предотвращение того, чтобы процесс занимал процессорное время в течение длительного времени, и другие функции.时钟软件(clock software)Это также подход, управляемый устройством. Затем мы представим часы. Обычно сначала мы обсуждаем аппаратное обеспечение, а затем представляем программное обеспечение. Подход снизу вверх используется, чтобы сказать вам, что нижний уровень является наиболее важным.

аппаратные часы

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

  • Часы более простого типа подключаются к сети 110 В или 220 В так, чтобы каждый电压周期Будет сгенерировано прерывание, около 50 - 60 Гц. Эти часы доминировали в прошлом.
  • Другие часы состоят из кварцевого генератора, счетчика и регистра, как показано на принципиальной схеме ниже.

Эти часы называются可编程时钟, программируемые часы имеют два режима, один一键式(one-shot mode), когда часы запускаются, значение из памяти копируется в счетчик, а затем каждый импульс кварцевого генератора приводит счетчик к -1. Когда счетчик становится равным 0, генерируется прерывание и прекращается работа до тех пор, пока программа снова не покажет начало. Когда есть другой режим方波(square-wave mode)В этом режиме, когда счетчик становится равным 0 и генерируется прерывание, значение регистра хранения автоматически копируется в счетчик, и это периодическое прерывание называется тактовым циклом.

Основные функции контроллера устройства

Контроллер устройства представляет собой可编址Когда он управляет только одним устройством, он имеет только один уникальный адрес устройства; если контроллер устройства управляет несколькими подключаемыми устройствами, он должен содержать несколько адресов устройств, и каждый адрес устройства соответствует устройству.

Существует два основных типа контроллеров устройств: символьные устройства и блочные устройства.

Основные функции контроллера устройства следующие:

  • Получение и распознавание команд: Контроллер устройства может принимать команды от ЦП и распознавать их. Внутри контроллера устройства также будут регистры для хранения инструкций и параметров.
  • Обмен данными: происходит обмен данными между ЦП, контроллером и устройством, ЦП отправляет инструкции контроллеру по шине или параллельно считывает данные с контроллера, контроллер записывает данные в указанное устройство.
  • Распознавание адресов: каждое аппаратное устройство имеет свой собственный адрес, и контроллер устройства может распознавать эти разные адреса для достижения цели управления аппаратным обеспечением. be Имеет уникальный адрес.
  • Обнаружение ошибок: Контроллер устройства также имеет функцию обнаружения данных, передаваемых устройством.

прерывание обработки

Существует много видов схем обработки прерываний, ниже приведены "Руководство разработчика системы ARM

Designing and Optimizing System Software》 Некоторые из перечисленных программ

  • 非嵌套Обработчик прерывания обрабатывает каждое прерывание по порядку, а невложенный обработчик прерывания также является простейшим обработчиком прерывания.
  • 嵌套Обработчик прерываний для нескольких прерываний без назначения приоритетов
  • 可重入Обработчик прерывания может использовать приоритет для обработки нескольких прерываний.
  • 简单优先级Обработчики прерываний обрабатывают простые прерывания
  • 标准优先级Обработчики прерываний могут обрабатывать прерывания с более высоким приоритетом за меньшее время, чем обработчики прерываний с более низким приоритетом.
  • 高优先级Обработчики прерываний могут обрабатывать задачи с более высоким приоритетом в течение короткого периода времени и переходить непосредственно к определенным процедурам обслуживания.
  • 优先级分组Обработчики прерываний могут обрабатывать задачи прерывания с разными уровнями приоритета.

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

  • Сохранить все регистры, не сохраненные аппаратным прерыванием
  • Установите контекст для процедуры обслуживания прерывания, возможно, включая установкуTLB,MMUи таблица страниц, если вы плохо знаете эти три понятия, обратитесь к другой статье
  • Настройка стека для процедуры обслуживания прерывания
  • Отвечать на контроллер прерываний и продолжать реагировать на прерывания, если нет централизованного контроллера прерываний.
  • скопируйте регистр, откуда он был сохранен, в таблицу процессов
  • Запускает процедуру обслуживания прерывания, которая извлекает информацию из регистров контроллера устройства, выдавшего прерывание.
  • Операционная система выберет соответствующий процесс для запуска. Если прерывание приводит к готовности некоторых процессов с более высоким приоритетом, выберите запуск этих процессов с более высоким приоритетом.
  • Установите контекст MMU для процесса, а также может потребоваться TLB, в зависимости от реальной ситуации.
  • Загрузите регистры процесса, включая регистр PSW.
  • начать новый процесс

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

Что такое драйвер устройства

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

Что такое ДМА

Китайское название DMA直接内存访问, что означает, что ЦП предоставляет модулю ввода-вывода разрешение на чтение или запись в память без участия ЦП. То есть DMA может не требовать участия CPU. Этим процессом управляет микросхема, называемая DMA Controller (DMAC). Поскольку устройства DMA могут передавать данные непосредственно между памятью, а не использовать ЦП в качестве посредника, это может уменьшить перегрузку шины. DMA улучшает параллелизм системы, позволяя ЦП выполнять задачи, в то время как система DMA передает данные по системной шине и шине памяти.

Особенности прямого доступа к памяти

Метод DMA имеет следующие характеристики:

  • Передача данных основана на блоках данных

  • Передаваемые данные отправляются непосредственно с устройства в основную память или напрямую выводятся из основной памяти на устройство.

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

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

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

Тупиковые статьи

Что такое зомби-процесс

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

Причина взаимоблокировки

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

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

Взаимная блокировка ресурсов может возникать в основном в следующих ситуациях.

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

восстановление тупиковой ситуации

Следовательно, для обнаруженного тупика нам необходимо его восстановить.Далее мы обсудим несколько методов восстановления тупика.

Восстановление путем вытеснения

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

Восстановление путем отката

Если проектировщики системы и операторы машин знают, что возможны тупиковые ситуации, процесс можно регулярно проверять. Контрольная точка процесса означает, что состояние процесса может быть записано в файл для последующего восстановления. Точка обнаружения содержит не только存储映像(memory image), также содержит资源状态(resource state). Более эффективное решение — не перезаписывать исходную контрольную точку, а записывать ее в файл каждый раз, когда возникает контрольная точка, чтобы при выполнении процесса накапливалась серия файлов контрольных точек.

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

убить процесс восстановления

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

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

Как выйти из тупика

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

нарушить взаимоисключающее условие

Наше первое соображениенарушить взаимоисключающее условие использования. Если ресурс не монополизирован процессом, то взаимной блокировки точно не будет. Если два принтера используют ресурс одновременно, это может вызвать путаницу, решение для принтеров — использовать假脱机打印机(spooling printer), метод, который позволяет нескольким процессам производить вывод одновременно, в этой модели единственным процессом, который фактически запрашивает принтер, является демон принтера, также известный как фоновый процесс. Фоновые процессы не запрашивают другие ресурсы. Мы можем устранить взаимоблокировку принтера.

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

Поэтому старайтесь, чтобы как можно меньше процессов запрашивали ресурсы.

сломать условие, которое заставляет ждать

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

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

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

нарушить неупреждающее условие

Также возможно нарушить невытесняющее условие. в состоянии пройти虚拟化способ избежать этого.

Разорвать условие ожидания цикла

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

Другой способ — единообразно пронумеровать все ресурсы, как показано на следующем рисунке.

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

тип тупика

двухступенчатая блокировка

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

Одним из решений является использование两阶段提交(two-phase locking). Как следует из названия, есть две фазы, на одной из которых процесс пытается заблокировать сразу все необходимые записи. В случае успеха начнется второй этап, второй этап заключается в выполнении обновления и снятии блокировки. Первый этап не делает действительно значимой работы.

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

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

коммуникационный тупик

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

Несмотря на то, что тупик возникает, это не тупик ресурсов, потому что A не занимает ресурсы B. На самом деле полностью видимых ресурсов для коммуникационных взаимоблокировок не существует. Согласно определению взаимоблокировки: каждый процесс блокируется, поскольку он ожидает событий, вызванных другими процессами, что является своего рода взаимоблокировкой. По сравнению с наиболее распространенным коммуникационным тупиком мы называем описанную выше ситуацию通信死锁(communication deadlock).

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

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

Когда пакет входит в маршрутизатор от хоста, он помещается в буфер, затем передается другому маршрутизатору, еще одному и так далее до пункта назначения. Буферы — это ресурсы, и их количество ограничено. Как показано на изображении ниже, каждый маршрутизатор имеет 10 буферов (на самом деле их много).

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

живой замок

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

Теперь представьте пару параллельных процессов, использующих два ресурса. После того, как их соответствующие попытки получить другую блокировку потерпят неудачу, оба процесса снимут удерживаемые ими блокировки, попытаются снова, и процесс повторится. Очевидно, что в этом процессе нет блокировки процесса, но процесс все равно не выполняется вниз, мы называем эту ситуацию活锁(livelock).

голод

Очень похожая проблема с deadlock и livelock饥饿(starvvation). Представьте, когда вы будете голодны? Чувствуете ли вы голод, если не едите какое-то время? Для процессов самое главное — это ресурсы.Если ресурсы не будут получены в течение определенного периода времени, процессы будут голодать, и эти процессы никогда не будут обслуживаться.

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

постскриптум

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

Если вы считаете, что эта статья неплохая, я надеюсь, что вы можете поставить лайк, посмотреть, переслать, оставить сообщение, добро пожаловать, чтобы обратить внимание на мой публичный аккаунт [Programmer cxuan], в этом аккаунте слишком много галантереи.

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

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

Я сам переписал шесть PDF-файлов. После того, как WeChat искал «Programmer cxuan» и следил за официальной учетной записью, я ответил cxuan в фоновом режиме и получил все PDF-файлы.Эти PDF-файлы следующие:

Шесть ссылок в формате PDF