Процессы и потоки, написанные для занятых людей

задняя часть Операционная система

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

процесс

Основная концепция операционной системы заключается в следующем.进程, процесс — это абстракция работающей программы. Все остальное в операционной системе вращается вокруг процессов. Процессы — одна из старейших и наиболее важных концепций, предоставляемых операционными системами. Они поддерживают, даже если доступен только один ЦП（伪）并发работать. Они абстрагируют один ЦП на ЦП нескольких виртуальных машин. Можно сказать: без абстрагирования процессов современная операционная система перестала бы существовать.

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

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

Во многих многопрограммных системах ЦП будет进程Быстро переключайтесь между программами, заставляя каждую программу работать десятки или сотни миллисекунд. Однако, строго говоря, в определенный момент ЦП может запускать только один процесс, но если мы определяем время в пределах 1 секунды, он может запускать несколько процессов. Это даст нам并行иллюзия. иногда люди говорят伪并行(pseudoparallelism)Это тот случай, когда нужно различать многопроцессорные системы (системы, в которых два или более ЦП совместно используют одну и ту же физическую память).

Давайте подробно объясним псевдопараллель:伪并行Относится к одноядерному или многоядерному процессору, выполняющему несколько процессов одновременно, что делает программу быстрее. Благодаря быстрому переключению ЦП между программами через очень ограниченные промежутки времени создается ощущение параллелизма. Недостатком является то, что процессорное время может быть выделено или не выделено следующему процессу.

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

модель процесса

В модели процесса все программное обеспечение, работающее на компьютере, часто включая операционную систему, организовано как ряд顺序进程(sequential processes), Упоминается как进程(process). Процесс — это экземпляр исполняемой программы, а также процесс включает в себя текущие значения счетчика программ, регистров и переменных. Концептуально каждый процесс имеет свой собственный виртуальный ЦП, но на самом деле ЦП переключается между процессами.

Как показано на рисунке выше, это многопроцессорная программа с 4 программами, и счетчик программ меняется по-разному, так как процессы постоянно переключаются.

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

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

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

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

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

Ключевая идея здесь в том, что认识到一个进程所需的条件, процесс представляет собой сумму определенного вида деятельности, у него есть процедуры, вход и выход, состояние. Один процессор может совместно использоваться несколькими процессами, и он использует некоторый алгоритм планирования, чтобы решить, когда остановить работу одного процесса и перейти к обслуживанию другого процесса. Следует также отметить, что если процесс выполняется дважды, он считается двумя процессами. Итак, после того, как мы поняли модель процесса, как создается процесс?

создание процесса

Операционная система нуждается в каком-то способе создания процессов. Вот несколько способов создать процесс

  • Инициализация системы (init)
  • Работающая программа выполняет системный вызов, который создает процесс (например, fork).
  • Запросы пользователей на создание нового процесса
  • Инициализировать пакетное задание

инициализация системы

При запуске операционной системы обычно создается несколько процессов. Некоторые из них前台进程(numerous processes), то есть процессы, которые взаимодействуют с пользователями и работают на них. Некоторые работают в фоновом режиме и не взаимодействуют с конкретным пользователем. Например, спроектируйте процесс для получения входящих электронных писем. Этот процесс большую часть времени спит, но просыпается каждый раз, когда приходит электронное письмо. Вы также можете разработать процесс для получения входящих запросов на веб-страницы на этом компьютере и запускаться при поступлении запроса для обработки входящих запросов на веб-страницы. Процессы, которые выполняются в фоновом режиме для обработки таких действий, как электронная почта, веб-страницы, новости, печать и т. д., называются守护进程(daemons). Большие системы будут иметь много демонов. В UNIX,psПрограммы могут отображать запущенные процессы, а в Windows вы можете использовать диспетчер задач.

создание системного вызова

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

Запрос пользователя на создание

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

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

пакетное создание

Последний случай создания процесса будет в大型机的批处理系统приложение в. Пользователи отправляют пакетные задания в такой системе. Когда ОС решает, что у нее есть ресурсы для выполнения другой задачи, она создает новый процесс и запускает в нем следующее задание из входной очереди.

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

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

В Windows все наоборот, простой вызов функции Win32CreateProcess，会处理流程创建并将正确的程序加载到新的进程中。这个调用会有 10 个参数，包括了需要执行的程序、输入给程序的命令行参数、各种安全属性、有关打开的文件是否继承控制位、优先级信息、进程所需要创建的窗口规格以及指向一个结构的指针，在该结构中新创建进程的信息被返回给调用者。 КромеCreateProcessВ Win 32 есть около 100 других функций, которые управляют процессами, синхронизацией и соответствующими транзакциями. Ниже приведено сравнение системных вызовов операционной системы UNIX и операционной системы Windows.

UNIX Win32 инструкция
fork CreateProcess создать новый процесс
waitpid WaitForSingleObject дождаться завершения процесса
execve none CraeteProcess = fork + servvice
exit ExitProcess прекратить выполнение
open CreateFile Создайте файл или откройте существующий файл
close CloseHandle закрыть файл
read ReadFile Чтение данных из одного файла
write WriteFile записать данные в один файл
lseek SetFilePointer Переместите указатель файла
stat GetFileAttributesEx получить разные атрибуты файла
mkdir CreateDirectory Создать новый каталог
rmdir RemoveDirectory удалить пустой каталог
link none Win32 не поддерживает ссылку
unlink DeleteFile уничтожить существующий файл
mount none Win32 не поддерживает монтирование
umount none Win32 не поддерживает монтирование, поэтому и не поддерживает монтирование
chdir SetCurrentDirectory Изменить текущий рабочий каталог
chmod none Win32 не поддерживает безопасность
kill none Win32 не поддерживает сигналы
time GetLocalTime получить текущее время

В UNIX и Windows после создания процесса родительский и дочерний процессы имеют отдельные адресные пространства. Если один из процессов изменяет слово в своем адресном пространстве, это изменение не будет видно другому процессу. В UNIX адресное пространство дочернего процесса является копией родительского процесса, но это два разных адресных пространства; недоступные для записи области памяти являются общими. Некоторые реализации UNIX полностью разделены между ними, потому что их нельзя изменить. В качестве альтернативы дочерний процесс разделяет всю память родительского процесса, но в этом случае память передается через写时复制(copy-on-write)Общая, что означает, что когда один из двух хочет изменить часть памяти, эта память сначала явно копируется, чтобы гарантировать, что изменение происходит в частной области памяти. еще раз подчеркнуть,Записываемая память не может быть разделена. Однако вновь созданный процесс действительно может совместно использовать ресурсы создателя, такие как открытые файлы, которые можно использовать совместно.В Windows адресное пространство родительского процесса и адресное пространство дочернего процесса отличаются с самого начала.

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

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

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

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

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

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

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

cc foo.c

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

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

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

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

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

иерархия процессов

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

Система процессов UNIX

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

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

Архитектура процесса Windows

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

статус процесса

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

cat chapter1 chapter2 chapter3 | grep tree

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

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

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

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

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

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

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

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

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

Следующая модель представлена ​​с вышеуказанной точки зрения

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

реализация процесса

Для выполнения переключения между процессами операционная система поддерживает таблицу, которая进程表(process table). Каждый процесс занимает одну запись в таблице процессов. Эта запись содержит важную информацию о состоянии процесса, включая счетчик программ, указатель стека, состояние выделения памяти, состояние открытых файлов, информацию об учетной записи и расписании, а также другую информацию, которая должна использоваться при переходе процесса из состояния выполнения в состояние готовности или блокировки. Сохранение информации, что гарантирует возможность повторного запуска процесса позже, как если бы он никогда не прерывался.

Ключевые поля в типичной системе показаны ниже

Содержимое первого столбца такое же, как进程管理связаны, содержание второго столбца связано с存储管理связаны, содержание третьего столбца связано с文件管理Связанный.

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

Язык ассемблера с твердыми базовыми знаниями, которые необходимо знать программистам (полностью)

Теперь, когда у нас есть общее представление о таблице процессов, мы можем больше рассказать об иллюзии того, как несколько последовательных процессов выполняются на одном процессоре. С каждым классом ввода/вывода связан中断向量(interrupt vector)местоположение (фиксированная область в нижней части памяти). Он содержит адрес входа процедуры обслуживания прерывания. Предполагая, что пользовательский процесс 3 выполняется, когда происходит прерывание диска, аппаратное обеспечение прерывания помещает в стек счетчик программ, слово состояния программы, а иногда и один или несколько регистров, и компьютер переходит к адресу, указанному вектором прерывания. Это то, что делает оборудование. Затем программное обеспечение берет на себя все остальное.

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

  1. аппаратный счетчик программ push-стека и т. д.

  2. Аппаратное обеспечение загружает новый программный счетчик из вектора прерывания

  3. Процедура языка ассемблера сохраняет значение регистра

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

  5. C прерывает работу сервера (типичное чтение и кэшированная запись)

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

  7. Процедура C возвращается к ассемблерному коду

  8. Процесс языка ассемблера запускает новый текущий процесс

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

нить

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

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

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

  • Возможность совместного использования одного и того же адресного пространства и всех доступных данных между несколькими потоками, чего нет у процессов
  • Потоки лучше, чем процессы更轻量级, так как потоки легче, их легче создавать и легче отменять, чем процессы. Во многих системах создание потока выполняется в 10-100 раз быстрее, чем создание процесса.
  • Третьей причиной может быть обсуждение производительности.Если несколько потоков сильно загружают ЦП, то повышения производительности получить нельзя, но если имеется много вычислений и много операций ввода-вывода, наличие нескольких потоков.Эти действия могут перекрываться. друг друга, что ускорит выполнение приложения

Многопоточное решение

Теперь рассмотрим пример использования потока: веб-сервер, запросы страниц отправляются на сервер, а запрошенные страницы отправляются обратно клиенту. На большинстве веб-сайтов одни страницы посещают больше, чем другие. Например, домашняя страница Sony имеет больше посещений, чем любая отдельная страница сведений о камере, а веб-сервер может хранить набор часто посещаемых страниц в памяти и избегать загрузки этих страниц на диск, тем самым повышая производительность. Набор таких страниц называется高速缓存(cache), кеш также используется во многих случаях, например, кеш процессора.

Выше показано, как организован веб-сервер, веб-сервер, называемый调度线程(dispatcher thread)Поток, который читает рабочий запрос из сети, после того, как поток планирования проверил запрос, выбирает бездействующий (заблокированный) рабочий поток для обработки запроса, обычно путем записи указателя на сообщение в специальное слово, связанное с каждым потоком. середина. Затем поток планирования разбудит спящий рабочий поток и изменит состояние рабочего потока с заблокированного на готовое.

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

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

Ниже приведен код для планирования потоков и рабочих потоков, предполагая, что TRUE — это константа 1, а buf и page — соответствующие структуры, содержащие рабочие запросы и веб-страницы соответственно.

Общая логика планирования потоков

while(TRUE){
  get_next_request(&buf);
  handoff_work(&buf);
}

Грубая логика рабочего потока

while(TRUE){
  wait_for_work(&buf);
  look_for_page_in_cache(&buf,&page);
  if(page_not_in_cache(&page)){
    read_page_from_disk(&buf,&page);
  }
  return _page(&page);
}

однопоточное решение

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

Решения для конечного автомата

Пока у нас есть два решения, однопоточное решение и многопоточное решение, на самом деле есть еще одно решение, которое状态机解决方案, его процесс выглядит следующим образом

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

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

Каждый раз, когда сервер переключается из состояния, в котором запрашивается работа, в другое состояние, соответствующее вычислительное состояние должно быть явно сохранено или перезагружено. Здесь у каждого вычисления есть сохраненное состояние, и есть набор событий, которые произойдут и вызовут изменение связанного состояния.Мы называем этот тип дизайна有限状态机(finite-state machine)чашка конечного автомата широко используется в информатике.

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

Модель характеристика
один поток Отсутствие параллелизма, низкая производительность, блокировка системных вызовов
Многопоточность Имеет параллелизм, блокирует системные вызовы
Конечный автомат Параллелизм, неблокирующие системные вызовы, прерывания

Классическая резьбовая модель

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

Другая концепция заключается в том, что у процесса есть поток выполнения, обычно обозначаемый аббревиатурой线程(thread). Поток будет иметь программный счетчик, который используется для записи следующей команды для выполнения; у потока также есть регистр, который используется для хранения переменных, которые поток использует в данный момент; у потока также есть стек, который используется для записи пути выполнения программы. Хотя поток должен выполняться в процессе, процесс и поток — это две совершенно разные концепции, и их можно обрабатывать отдельно. Процессы используются для объединения ресурсов, а потоки — это объекты, которые планируют выполнение на ЦП.

Потоки добавляют контент в модель процесса, то есть внутри одного процесса они допускают большую независимость друг от друга и не мешают друг другу. Параллельное выполнение нескольких потоков внутри процесса аналогично запуску нескольких процессов на одном компьютере. В нескольких потоках каждый поток использует одно и то же адресное пространство и другие ресурсы. Среди нескольких процессов процессы совместно используют физическую память, диски, принтеры и другие ресурсы. Поскольку поток содержит некоторые свойства процесса, поток вызывается轻量的进程(lightweight processes).多线程(multithreading)Этот термин также используется для описания нескольких потоков в одном и том же процессе.

Ниже мы видим три традиционных процесса, каждый со своим адресным пространством и одним потоком управления. Каждый поток работает в другом адресном пространстве

На рисунке ниже мы видим, что есть процесс с тремя потоками. Каждый поток работает в одном и том же адресном пространстве.

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

Левая часть рисунка выше находится в том же процессе每个线程共享Содержание изображения выше справа每个线程содержание в . Другими словами, список слева — это атрибут процесса, а список справа — это атрибут потока.

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

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

системный вызов потока

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

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

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

POSIX-потоки

Чтобы сделать возможным писать переносимые многопоточные программы, IEEE определяет стандарт многопоточности в стандарте IEEE 1003.1c. Пакет потоков определяется какPthreads. Большинство систем UNIX поддерживают его. Этот стандарт определяет более 60 вызовов функций. Нецелесообразно перечислять их все. Вот некоторые наиболее часто используемые системные вызовы.

POSIX-потоки(часто называютpthreads) — это независимая от языка модель выполнения, а также модель параллельного выполнения. Это позволяет программе управлять несколькими различными рабочими процессами, которые перекрываются во времени. Каждый рабочий процесс называется потоком, и эти процессы можно создавать и контролировать, вызывая API потоков POSIX. Его можно понимать как стандарт для потоков.

Реализации потоков POSIX доступны во многих аналогичных и совместимых с POSIX операционных системах, например.FreeBSD, NetBSD, OpenBSD, Linux, macOS, Android, Solaris, реализованный поверх существующего Windows API.pthread.

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

вызов потока описывать
pthread_create создать новую тему
pthread_exit завершить вызывающий поток
pthread_join дождитесь выхода определенного потока
pthread_yield Освободить ЦП для запуска другого потока
pthread_attr_init Создание и инициализация структуры свойств потока
pthread_attr_destory удалить структуру атрибутов потока

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

Новая нить пройдетpthread_createCreate, в качестве значения функции возвращается идентификатор вновь созданного потока. Этот вызов очень похож на UNIX.forkсистемные вызовы (помимо аргументов), где играет идентификатор потокаPIDЦель этого состоит в том, чтобы отличить его от других потоков.

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

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

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

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

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

Чтобы лучше понять, как работают pthreads, рассмотрим следующий пример.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define NUMBER_OF_THREADS 10

void *print_hello_world(vvoid *tid){
  /* 输出线程的标识符，然后退出 */
  printf("Hello World. Greetings from thread %d\n",tid);
  pthread_exit(NULL);
}

int main(int argc,char *argv[]){
  /* 主程序创建 10 个线程，然后退出 */
  pthread_t threads[NUMBER_OF_THREADS];
  int status,i;
 	
  for(int i = 0;i < NUMBER_OF_THREADS;i++){
    printf("Main here. Creating thread %d\n",i);
    status = pthread_create(&threads[i], NULL, print_hello_world, (void *)i);
    
    if(status != 0){
      printf("Oops. pthread_create returned error code %d\n",status);
      exit(-1);
    }
  }
  exit(NULL);
}

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

реализация потока

Существует три основных способа реализации

  • Реализовать потоки в пользовательском пространстве;
  • Реализовать потоки в пространстве ядра;
  • Смешанная реализация потоков в пространстве пользователя и ядра.

давайте обсудим отдельно

Реализация потоков в пользовательском пространстве

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

Потоки выполняются поверх системы выполнения, которая представляет собой набор процессов, управляющих потоками, включая четыре упомянутых ранее: pthread_create, pthread_exit, pthread_join и pthread_yield.

运行时系统(Runtime System)Также называемая средой выполнения, система выполнения обеспечивает среду, в которой выполняются программы. Эта среда может решить многие проблемы, в том числе структуру памяти приложения, способ доступа программы к переменным, механизм передачи параметров между процедурами, интерфейс с операционной системой и многое другое. Компилятор делает предположения для создания правильного кода на основе конкретной системы времени выполнения. Как правило, система выполнения отвечает за настройку и управление стеком и включает в себя такие вещи, как сборка мусора, многопоточность или другие динамические функции, встроенные в язык.

При управлении потоками в пользовательском пространстве каждый процесс должен иметь свой собственный выделенный поток.线程表(thread table), используемый для отслеживания потоков в процессе. Эти таблицы аналогичны таблицам процессов в ядре, но в них записываются только свойства отдельных потоков, такие как программный счетчик каждого потока, указатель стека, регистры и состояние. Метка резьбы единообразно управляется системой выполнения. Когда поток переходит в состояние готовности или блокировки, вся информация для перезапуска потока сохраняется в таблице потоков точно так же, как информация, хранящаяся ядром в таблице процессов.

Преимущества реализации потоков в пользовательском пространстве

Реализация потоков в пространстве пользователя имеет следующие преимущества по сравнению с реализацией потоков в пространстве ядра: подумайте, завершается ли поток или когда вызовpthread_yieldПри необходимости поток процесса будет переключаться, а затем информация о потоке будет сохранена в таблице потоков, предоставленной средой выполнения, а затем планировщик потоков выберет другой поток для запуска. Сохранение состояния потока и планировщика本地过程,Поэтому их запуск более эффективен, чем вызов ядра. Следовательно, нет необходимости переключаться на ядро, нет необходимости в переключении контекста и нет необходимости обновлять кеш памяти, потому что планирование потоков очень удобно, поэтому эффективность относительно высока..

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

Недостатки реализации потоков в пользовательском пространстве

Хотя реализация потоков в пользовательском пространстве будет иметь определенные преимущества в производительности, недостатки по-прежнему очевидны.阻塞系统调用Шерстяная ткань? Предполагая, что поток считывает клавиатуру до того, как будет выполнен какой-либо ввод с клавиатуры, невозможно заставить поток выполнять системный вызов, потому что это остановит все потоки. так,Одна из целей использования потоков — иметь возможность выполнять блокирующие вызовы из потоков и избегать влияния блокирующих потоков на другие потоки..

Аналогичная проблема с блокировкой звонков есть缺页中断Проблема, собственно, в том, что компьютер не помещает все программы в память одновременно.Если в программе происходит вызов функции или инструкция перехода к инструкции, которой нет в памяти, то произойдет ошибка страницы, и операционная система восстановит потерянную инструкцию с диска, которая называется缺页故障. Когда требуемые инструкции будут прочитаны и выполнены, соответствующий процесс будет заблокирован. Если только один поток вызывает страничную ошибку, ядро, поскольку оно даже не знает о существовании потока, обычно блокирует весь процесс до тех пор, пока дисковый ввод-вывод не завершится, даже если другие потоки могут работать.

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

Реализовать потоки в ядре

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

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

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

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

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

Гибридная реализация

Сочетая преимущества пользовательского пространства и пространства ядра, разработчики приняли内核级线程метод, а затем мультиплексировать потоки пользовательского уровня с некоторыми или всеми потоками ядра.

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

межпроцессного взаимодействия

Процессы должны часто взаимодействовать с другими процессами. Например, в канале оболочки выходные данные первого процесса должны быть переданы второму процессу и так далее по каналу. Следовательно, если процессам необходимо взаимодействовать, они должны использовать хорошую структуру данных, чтобы их нельзя было прервать. Ниже мы поговорим о进程间通信(Inter Process Communication, IPC)Проблема.

Вот три вопроса о межпроцессном взаимодействии

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

Обратите внимание, что последние два из этих трех вопросов также относятся к темам.

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

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

состояние гонки

В некоторых операционных системах взаимодействующие процессы могут совместно использовать некоторые общие ресурсы, которые могут читать и записывать друг для друга. Общие ресурсы могут находиться в памяти или в общем файле. Чтобы было понятно, как взаимодействуют процессы, приведем пример: спулер. Когда процессу необходимо напечатать файл, он помещает имя файла в специальный后台目录(spooler directory)середина. другой процесс打印后台进程(printer daemon)Периодически проверяет, нужно ли распечатать файл, и если да, печатает и удаляет имя файла из каталога.

Предположим, что в нашем фоновом каталоге много槽位(slot), числа 0, 1, 2, ..., каждый слот хранит имя файла. Также предположим, что есть две общие переменные:out, указывает на следующий файл для печати;in, который указывает на следующий свободный слот в каталоге. Эти два файла могут храниться в файле, доступном для всех процессов и состоящем из двух слов. В какой-то момент слоты с 0 по 3 пусты, а слоты с 4 по 6 заняты. В тот же момент и процесс A, и процесс B решают поставить файл в очередь на печать следующим образом.

墨菲法则(Murphy)В книге сказано, что все, что может пойти не так, в конечном итоге пойдет не так.Когда это предложение вступит в силу, могут произойти следующие вещи.

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

Теперь процесс B продолжает работать, он записывает имя файла печати в слот 7, затем изменяет указатель in на 8, и процесс B уходит, чтобы заняться другими делами.

Теперь процесс А начинает возобновлять работу, так как процесс А проходит проверкуnext_free_slotТакже обнаружено, что слот слота 7 пуст, поэтому имя файла печати сохраняется в слоте 7, а затем значение in обновляется до 8. Поскольку в слоте 7 уже есть значение, записанное процессом B, процесс A Имя файла печати перезапишет файл процесса B. Поскольку невозможно узнать, какой процесс обновляется внутри принтера, его функции относительно ограничены, поэтому процесс B никогда не может распечатать вывод в это время, как в этом случае,То есть, когда два или более потока изменяют общие данные одновременно, что влияет на корректность программы, это называется состоянием гонки.. Отладка условий гонки — очень сложная работа, потому что большую часть времени программа работает нормально, но в редких случаях случаются какие-то необъяснимые странности.

критическая секция

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

Условия предотвращения проблем с гонками можно описать абстрактно. Большую часть времени процесс занят внутренними вычислениями и другими вычислениями, которые не вызывают состояния гонки. Однако иногда процесс обращается к общей памяти или файлам или делает что-то, что может вызвать состояние гонки. Мы называем программный сегмент, который обращается к разделяемой памяти,临界区域(critical region)или临界区(critical section). Если мы сможем сделать это так, чтобы два разных процесса не могли одновременно находиться в критической секции, мы сможем избежать состояния гонки, что также является с точки зрения проектирования операционной системы.

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

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

С абстрактной точки зрения мы обычно хотим, чтобы процесс вел себя так, как показано на рисунке выше, в момент времени t1 процесс A входит в критическую секцию, а в момент времени t2 процесс B пытается войти в критическую секцию, потому что процесс A находится в критической секции в это время, поэтому процесс B будет заблокирован до тех пор, пока процесс A не покинет критическую секцию в момент времени t3, когда процесс B сможет войти в критическую секцию. Наконец, в момент времени t4 процесс B покидает критическую секцию, и система возвращается в исходное состояние без процессов.

мьютекс с ожиданием занятости

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

прерывание по маске

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

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

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

переменная блокировки

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

Эта конструкция правильная? Есть ли недостатки? Предположим, процесс считывает значение переменной блокировки и обнаруживает, что оно равно 0, и непосредственно перед тем, как установить его в 1, другой процесс планирует запуск, считывает переменную блокировки как 0 и устанавливает переменную блокировки в 1. Затем запускается первый поток и снова устанавливает значение переменной блокировки в 1. В этот момент в критической секции будут одновременно выполняться два процесса.

Может быть, некоторые читатели могут так подумать, проверьте это один раз, прежде чем войти, и проверьте еще раз в ключевой области, чтобы выйти, не будет ли это решено? На самом деле, эта ситуация бесполезна, потому что другие потоки все еще могут изменить значение переменной блокировки во время второй проверки, другими словами, такого родаset-before-checkне вид原子性операции, поэтому также возникает состояние гонки.

строгий опрос

Третий способ взаимного исключения сначала выбрасывает кусок кода.Программа здесь написана на языке C. Причина использования C заключается в том, что операционная система в основном написана на C (иногда на C++), а Java в принципе не используется , В таких языках, как Modula3 или Pascal, родное ключевое слово в Java также является исходным кодом, написанным на C или C++. C — мощный, эффективный, предсказуемый и характерный язык для написания операционной системы, в то время как для Java он непредсказуем, потому что ему не хватает памяти в критические моменты и нехватка памяти в неподходящий момент. Когда для освобождения памяти вызывается механизм сборки мусора . В языке C такой ситуации не происходит, и язык C не вызывает активно сборку мусора для освобождения памяти. Для сравнения C, C++, Java и четырех других языков вы можете обратиться кСсылка на сайт

код для процесса 0

while(TRUE){
  while(turn != 0){
    /* 进入关键区域 */
    critical_region();
    turn = 1;
    /* 离开关键区域 */
    noncritical_region();
  }
}

Процесс кода 1

while(TRUE){
  while(turn != 1){
    critical_region();
    turn = 0;
    noncritical_region();
  }
}

В приведенном выше коде переменнаяturn, начальное значение равно 0 и используется для записи того, какая очередь процесса входит в критическую секцию, а также для проверки или обновления общей памяти. Вначале процесс 0 проверяет поворот, находит, что его значение равно 0, и входит в критическую секцию. Процесс 1 также обнаруживает, что его значение равно 0, поэтому он продолжает тестировать очередь в цикле ожидания, чтобы увидеть, когда его значение станет равным 1. Непрерывная проверка переменной до тех пор, пока не произойдет определенное значение, этот метод вызывается忙等待(busywaiting). Поскольку этот метод тратит впустую процессорное время, этого метода обычно следует избегать. Ожидание занятости следует использовать только тогда, когда есть основания полагать, что время ожидания очень короткое. Замок для занятых ожиданий, называемый自旋锁(spinlock).

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

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

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

Решение Петерсона

Голландский математик Т. Деккер впервые предложил программный алгоритм взаимного исключения, не требующий строгой ротации, путем объединения переменных блокировки с переменными предупреждения.Алгоритм Деккера см.Ссылка на сайт

Позже G.L.PEPTERSON обнаружил гораздо более простой взаимный алгоритм исключения, который выглядит следующим образом

#define FALSE 0
#define TRUE  1
/* 进程数量 */
#define N     2													

/* 现在轮到谁 */
int turn;					

/* 所有值初始化为 0 (FALSE) */
int interested[N];											

/* 进程是 0 或 1 */
void enter_region(int process){					
  
  /* 另一个进程号 */
  int other;														
  
  /* 另一个进程 */
  other = 1 - process;				
  
  /* 表示愿意进入临界区 */
  interested[process] = TRUE;						
  turn = process;
  
  /* 空循环 */
  while(turn == process 
        && interested[other] == true){} 
  
}

void leave_region(int process){
  
  /* 表示离开临界区 */
  interested[process] == FALSE;				 
}

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

Теперь посмотрим, как работает этот метод. В начале в критической секции нет ни одного процесса, теперь процесс 0 вызововenter_region. Он сигнализирует, что хочет войти в критическую секцию, устанавливая элемент массива и устанавливая поворот на 0. Поскольку процесс 1 не хочет входить в критическую область, enter_region быстро возвращается. Если процесс сейчас вызовет enter_region, процесс 1 зависнет здесь до тех пор, покаinterested[0]становится FALSE, в этом случае, только если процесс 0 вызываетleave_regionВозникает только при выходе из критической секции.

Далее рассмотрен случай последовательного входа, а теперь рассмотрим ситуацию, когда два процесса вызываются одновременно.enter_regionСлучай. Все они по очереди сохраняют свой собственный процесс, но действителен только последний сохраненный номер процесса, а номер предыдущего процесса теряется из-за перезаписи. Если процесс 1 является последним депозитом, очередь равна 1. Когда оба процесса запускаютсяwhile, процесс 0 не будет зацикливаться и не войдет в критическую секцию, в то время как процесс 1 будет бесконечно зацикливаться и не войдет в критическую секцию, пока процесс 0 не выйдет.

TSL-инструкция

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

TSL RX,LOCK

называется测试并加锁(test and set lock), который считывает блокировку слова памяти в регистрRX, а затем сохраните ненулевое значение по этому адресу памяти. Инструкции чтения и записи гарантированно интегрированы, неразделимы и выполняются вместе. Никакому другому процессору не разрешен доступ к памяти, пока эта инструкция не будет завершена. ЦП, выполняющий инструкцию TSL, блокирует шину памяти, предотвращая доступ других ЦП к памяти до тех пор, пока инструкция не завершится.

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

Чтобы использовать инструкции TSL, используется блокировка общей переменной для координации доступа к общей памяти. Когда блокировка равна 0, любой процесс может использовать инструкцию TSL, чтобы установить ее в 1 и читать и записывать в разделяемую память. Когда операция завершается, процесс используетmoveИнструкция сбрасывает значение блокировки на 0 .

Как эта инструкция предотвращает одновременный вход двух процессов в критическую секцию? Ниже приведено решение

enter_region:
			| 复制锁到寄存器并将锁设为1
			TSL REGISTER,LOCK              
			| 锁是 0 吗？
  		CMP REGISTER,#0						 		
  		| 若不是零，说明锁已被设置，所以循环
  		JNE enter_region					 		
  		| 返回调用者，进入临界区
  		RET												 
       
leave_region:

			| 在锁中存入 0
			MOVE LOCK,#0			      
      | 返回调用者
  		RET

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

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

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

enter_region:
		| 把 1 放在内存器中
		MOVE REGISTER,#1	
    | 交换寄存器和锁变量的内容
		XCHG REGISTER,LOCK			
    | 锁是 0 吗？
		CMP REGISTER,#0		
    | 若不是 0 ，锁已被设置，进行循环
		JNE enter_region					
    | 返回调用者，进入临界区
		RET														
	
leave_region:				
		| 在锁中存入 0 
		MOVE LOCK,#0	
    | 返回调用者
		RET

XCHG — это, по сути, то же решение, что и TSL. Все процессоры Intel x86 используют инструкцию XCHG для низкоуровневой синхронизации.

спать и просыпаться

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

Это не только пустая трата процессорного времени, но и может привести к неожиданным результатам. Рассмотрим два процесса на компьютере с разными приоритетами,Hэто процесс с более высоким приоритетом.LЭто процесс с более низким приоритетом. Правило планирования процессов заключается в том, чтобы запускать выполнение всякий раз, когда процесс H находится в состоянии готовности H. В какой-то момент, когда L находится в критической секции, H становится готовым к запуску (например, конец операции ввода-вывода). Теперь H начнет активно ждать, но поскольку L не будет планироваться, когда H будет готов, у L никогда не будет шанса покинуть критическую область, поэтому H станет бесконечным циклом, который иногда называют优先级反转问题(priority inversion problem).

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

Проблема производитель-потребитель

В качестве примера этих частных примитивов рассмотрим生产者-消费者(producer-consumer)проблема, также известная как有界缓冲区(bounded-buffer)проблема. Два процесса совместно используют общий буфер фиксированного размера. Один из них является生产者(producer), поместите информацию в буфер, другой消费者(consumer), будет взято из буфера. Эту проблему также можно обобщить на проблему m производителей и n потребителей, но мы обсуждаем здесь только случай одного производителя и одного потребителя, что может упростить реализацию.

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

Эта логика звучит относительно просто, и для этого метода также требуется метод, называемый监听Эта переменная используется для мониторинга данных в буфере. Мы предварительно устанавливаем ее как счетчик. Если в буфере хранится не более N элементов данных, производитель будет судить, достигает ли счетчик N каждый раз, в противном случае производитель поместит данные в buffer.item и увеличить значение count. Логика потребителя также очень похожа: сначала проверьте, равно ли значение count 0, если оно равно 0, потребитель спит и блокируется, иначе он будет извлекать данные из буфера и уменьшать число count. Каждый процесс также проверяет, следует ли разбудить другие потоки, и, если да, пробуждает поток. Ниже приведен код производителя-потребителя.

/* 缓冲区 slot 槽的数量 */
#define N 100						
/* 缓冲区数据的数量 */
int count = 0										
  
// 生产者
void producer(void){
  int item;
  
  /* 无限循环 */
  while(TRUE){				
    /* 生成下一项数据 */
    item = produce_item()				
    /* 如果缓存区是满的，就会阻塞 */
    if(count == N){
      sleep();									
    }
    
    /* 把当前数据放在缓冲区中 */
    insert_item(item);
    /* 增加缓冲区 count 的数量 */
    count = count + 1;					
    if(count == 1){
      /* 缓冲区是否为空？ */
      wakeup(consumer);					
    }
  }
}

// 消费者
void consumer(void){
  
  int item;
  
  /* 无限循环 */
  while(TRUE){
    /* 如果缓冲区是空的，就会进行阻塞 */
  	if(count == 0){							
      sleep();
    }
    /* 从缓冲区中取出一个数据 */
   	item = remove_item();			
    /* 将缓冲区的 count 数量减一 */
    count = count - 1
    /* 缓冲区满嘛？ */
    if(count == N - 1){					
      wakeup(producer);		
    }
    /* 打印数据项 */
    consumer_item(item);				
  }
  
}

Чтобы описать на языке C что-то вродеsleepиwakeupсистемные вызовы, которые мы будем представлять в виде вызовов библиотечных функций. Они не являются частью стандартной библиотеки C, но могут использоваться практически в любой системе, в которой есть эти системные вызовы. не реализовано в кодеinsert_itemиremove_itemИспользуется для записи помещения элементов данных в буфер и извлечения данных из буфера и т. д.

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

Суть вышеуказанной проблемы состоит в том, чтоПробуждение процесса, который еще не спит, приводит к потерянному пробуждению.. Если не пропало, то все в порядке. Быстрый способ решить указанную выше проблему — добавить唤醒等待位(wakeup waiting bit). Этот бит устанавливается в 1 после отправки сигнала пробуждения процессу, который еще не активен. Позже, когда процесс пытается заснуть, если бит ожидания пробуждения равен 1, этот бит сбрасывается, и процесс остается активным.

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

сигнал

Семафор — это метод, предложенный Э. У. Дейкстрой в 1965 году, в котором используется целочисленная переменная для накопления количества пробуждений для последующего использования. По его мнению, существует новый тип переменных, называемый信号量(semaphore). Значением семафора может быть 0 или любое положительное число. 0 означает, что пробуждений не требуется, а любое положительное число означает количество пробуждений.

Дейкстра предположил, что семафор имеет две операции, которые сейчас широко используются.downиup(представлены сном и пробуждением соответственно). Операция инструкции down проверяет, больше ли значение 0 . Если оно больше 0, уменьшите значение на 1; если значение равно 0, процесс перейдет в спящий режим, а операция отключения продолжится. Проверка значений, изменение значений переменных и, возможно, спящий режим — все это находится в одном неделимом原子操作(atomic action)Заканчивать. Это гарантирует, что после начала операции с семафором ни один другой процесс не сможет получить доступ к семафору, пока операция не завершится или не будет заблокирована. Эта атомарность абсолютно необходима для решения проблем синхронизации и предотвращения гонок.

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

Операция up увеличивает значение семафора на 1. Если один или несколько процессов находятся в спящем режиме на семафоре и не могут завершить предыдущую операцию отключения, система выбирает один из них и позволяет этому процессу завершить операцию отключения. Таким образом, после операции up на семафоре, на котором находится спящий процесс, значение семафора по-прежнему равно 0 , но на один спящий процесс на нем меньше. Увеличение значения семафора на 1 и пробуждение процесса также неразделимы. Ни один процесс не будет заблокирован при выполнении up, так же как ни один процесс не будет заблокирован при выполнении wakeup в предыдущей модели.

Решение проблемы производитель-потребитель с семафорами

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

/* 定义缓冲区槽的数量 */
#define N 100
/* 信号量是一种特殊的 int */
typedef int semaphore;
/* 控制关键区域的访问 */
semaphore mutex = 1;
/* 统计 buffer 空槽的数量 */
semaphore empty = N;
/* 统计 buffer 满槽的数量 */
semaphore full = 0;												

void producer(void){ 
  
  int item;  
  
  /* TRUE 的常量是 1 */
  while(TRUE){			
    /* 产生放在缓冲区的一些数据 */
    item = producer_item();		
    /* 将空槽数量减 1  */
    down(&empty);	
    /* 进入关键区域  */
    down(&mutex);	
    /* 把数据放入缓冲区中 */
    insert_item(item);
    /* 离开临界区 */
    up(&mutex);	
    /* 将 buffer 满槽数量 + 1 */
    up(&full);														
  }
}

void consumer(void){
  
  int item;
  
  /* 无限循环 */
  while(TRUE){
    /* 缓存区满槽数量 - 1 */
    down(&full);
    /* 进入缓冲区 */	
    down(&mutex);
    /* 从缓冲区取出数据 */
    item = remove_item();	
    /* 离开临界区 */
    up(&mutex);	
    /* 将空槽数目 + 1 */
    up(&empty);	
    /* 处理数据 */
    consume_item(item);											
  }
  
}

Чтобы убедиться, что семафор работает правильно, самое главное реализовать его неделимым образом. Обычно вверх и вниз реализуются как системные вызовы. И ОС нужно только временно маскировать все прерывания, когда:Проверить наличие семафоров, обновить, при необходимости перевести процесс в спящий режим. Поскольку для этих операций требуется очень мало инструкций, прерывания не имеют значения. Если используется несколько процессоров, семафор должен быть защищен замком. Используйте инструкции TSL или XCHG, чтобы убедиться, что с семафором одновременно работает только один ЦП.

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

В приведенном выше решении используются три семафора: один, называемый полным, который записывает количество полных слотов буфера, один, называемый пустым, который записывает количество пустых слотов буфера, и один, называемый мьютексом, который используется для гарантии того, что производители и потребители не будут входить буфер одновременно.Fullинициализируется значением 0, empty инициализируется числом слотов в буфере, а мьютекс инициализируется значением 1. Семафор инициализируется значением 1 и используется двумя или более процессами, чтобы гарантировать, что только один из них может одновременно войти в критическую область.二进制信号量(binary semaphores).如果每个进程都在进入关键区域之前执行 down 操作，而在离开关键区域之后执行 up 操作，则可以确保相互互斥。

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

  1. аппаратный счетчик программ push-стека и т. д.

  2. Аппаратное обеспечение загружает новый программный счетчик из вектора прерывания

  3. Процедура языка ассемблера сохраняет значение регистра

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

  5. C прерывает работу сервера (типичное чтение и кэшированная запись)

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

  7. Процедура C возвращается к ассемблерному коду

  8. Процесс языка ассемблера запускает новый текущий процесс

в настоящее время использует信号量, естественный способ скрыть прерывания — оборудовать каждое устройство ввода-вывода семафором, изначально установленным в 0. Сразу после запуска устройства ввода-вывода обработчик прерывания выполняетdownоперация, процесс немедленно блокируется. При поступлении прерывания обработчик прерывания выполняетupоперация для возобновления заблокированного процесса. В приведенных выше шагах обработки прерывания шаг 5 изC 中断服务器运行Просто операция up, выполняемая обработчиком прерывания на семафоре, поэтому на шаге 6 операционная система может выполнить драйвер устройства. Конечно, если несколько процессов уже находятся в состоянии готовности, планировщик может выбрать запуск более важного процесса следующим, а алгоритм планирования мы обсудим позже.

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

Другой семафор о同步(synchronization)из.fullиemptyСемафоры используются для обеспечения того, чтобы события происходили или не происходили. В этом случае они гарантируют, что производитель остановится, когда буфер будет заполнен, а потребитель остановится, когда буфер станет пустым. Эти два семафора используются иначе, чем мьютекс.

Мьютекс

Если вам не нужны возможности подсчета семафора, простая версия семафора называетсяmutex(互斥量). Преимущество мьютексов состоит в том, чтобы поддерживать взаимное исключение между некоторыми общими ресурсами и фрагментом кода. Поскольку реализация мьютексов проста и эффективна, это делает мьютексы очень полезными при реализации пакетов потоков в пользовательском пространстве.

Мьютекс — это общая переменная, которая находится в одном из двух состояний:解锁(unlocked)и加锁(locked). Таким образом, для его представления требуется только один двоичный бит, но в целом整形(integer)Представлять. 0 означает разблокировку, все остальные значения означают блокировку, а значение больше 1 означает количество раз блокировки.

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

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

Поскольку мьютексы-мьютексы очень просты, их можно легко реализовать в пользовательском пространстве, если есть инструкции TSL или XCHG. для пакетов потоков на уровне пользователяmutex_lockиmutex_unlockКод следующий, и суть XCHG та же.

mutex_lock:
			| 将互斥信号量复制到寄存器，并将互斥信号量置为1
			TSL REGISTER,MUTEX
      | 互斥信号量是 0 吗？
			CMP REGISTER,#0	
      | 如果互斥信号量为0，它被解锁，所以返回
			JZE ok	
      | 互斥信号正在使用；调度其他线程
			CALL thread_yield	
      | 再试一次
			JMP mutex_lock	
      | 返回调用者，进入临界区
ok: 	RET														

mutex_unlcok:
			| 将 mutex 置为 0 
			MOVE MUTEX,#0	
      | 返回调用者
			RET

Код mutex_lock очень похож на код enter_region выше, мы можем сравнить его

Вы видите самую большую разницу в коде выше?

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

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

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

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

Futexes

По мере увеличения параллелизма эффективность同步(synchronization)и锁定(locking)Это очень важно для производительности. Если время ожидания процесса короткое, то自旋锁(Spin lock)очень эффективен, но если время ожидания велико, то это тратит впустую циклы процессора. Если процессов много, более эффективно заблокировать процесс и позволить ядру разблокировать его только после снятия блокировки. К сожалению, этот подход также приводит к другой проблеме: он может хорошо работать при большом количестве конфликтов процессов, но может быть очень дорого переключать ядра, когда конкуренция не очень сильна, и труднее предсказать количество блокировок. конкуренции еще сложнее.

Интересное решение состоит в том, чтобы объединить преимущества обоих и предложить новую идею под названиемfutex,или快速用户空间互斥(fast user space mutex), разве это не звучит интересно?

фьютексLinuxФункции в реализации базовой блокировки (во многом похожей на мьютексы) и избегают попадания в ловушку ядра, что может значительно повысить производительность, поскольку переключение ядра обходится дорого. Фьютекс состоит из двух частей:Службы ядра и пользовательские библиотеки. Службы ядра предоставляют等待队列(wait queue)Позволяет несколько процессов в очередь на замке. Они не будут бежать, если ядро ​​явно не разблокирует их.

Помещение процесса в очередь ожидания требует дорогостоящего системного вызова, которого следует избегать. Без конфликтов фьютекс может работать непосредственно в пользовательском пространстве. Эти процессы совместно используют 32-битную整数(integer)как общедоступная переменная блокировки. Предполагая, что инициализация блокировки равна 1, мы считаем, что в это время блокировка снята. Потоки выполняют атомарные операции,减少并测试(decrement and test)захватить замок. Декремент и установка — это атомарные функции в Linux, состоящие из встроенной сборки, обернутой в функцию C и определенной в заголовочном файле. Затем поток проверяет результат, чтобы увидеть, снята ли блокировка. Если блокировка сейчас не заблокирована, то бывает, что наш поток может успешно вытеснить блокировку. Однако, если блокировка удерживается другим потоком, поток, вытеснивший блокировку, должен ждать. В этом случае библиотека фьютекса не будет自旋, но использует системный вызов для помещения потока в очередь ожидания в ядре. Таким образом, накладные расходы на переключение на ядро ​​уже оправданы, поскольку потоки могут заблокироваться в любой момент. Когда поток завершает работу над блокировкой, он использует атомарный增加并测试(increment and test)Снимите блокировку и проверьте результаты, чтобы увидеть, не заблокированы ли еще какие-либо процессы в очереди ожидания ядра. Если они есть, он уведомляет ядро ​​о том, что один или несколько процессов в очереди ожидания могут быть разблокированы. Если нет конфликта блокировок, ядру не нужно конкурировать.

Мьютексы в Pthreads

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

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

Как мы и предполагали, мьютекс можно создавать и уничтожать, а обе роли выполняетPhread_mutex_initиPthread_mutex_destroy. мьютекс также может быть переданPthread_mutex_lockЧтобы заблокировать, если мьютекс уже заблокирован, он заблокирует вызывающую сторону. еще один звонокPthread_mutex_trylockИспользуется для попытки заблокировать поток, когда мьютекс уже заблокирован, возвращает код ошибки вместо блокировки вызывающего. Этот вызов позволяет потоку эффективно ожидать занятости. Наконец,Pthread_mutex_unlockРазблокирует мьютекс и освобождает ожидающий поток.

За исключением мьютексов,PthreadsТакже предусмотрен второй механизм синхронизации:条件变量(condition variables). Мьютекс отлично подходит для разрешения или блокировки доступа к критическим областям. Переменные условия позволяют блокировать поток, потому что какое-то условие не выполняется. В подавляющем большинстве случаев эти два метода используются вместе. Давайте подробнее изучим связь между потоками, мьютексами и условными переменными.

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

Вот некоторые из наиболее важных вызовов pthread, связанных с условными переменными.

Некоторые вызовы для создания и уничтожения условных переменных приведены в таблице выше. Основное свойство условной переменной:Pthread_cond_waitиPthread_cond_signal. Первый блокирует вызывающий поток до тех пор, пока другой поток не просигнализирует (используя последний вызов). Заблокированному потоку обычно необходимо дождаться сигнала пробуждения, чтобы освободить ресурсы или выполнить какое-либо другое действие. Только после этого заблокированные потоки могут продолжать работу. Переменные условия позволяют атомарно ожидать и блокировать процессы.Pthread_cond_broadcastИспользуется для пробуждения нескольких заблокированных потоков, которым необходимо дождаться сигнала для пробуждения.

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

Вот пример использования мьютексов и условных переменных

#include <stdio.h>
#include <pthread.h>

/* 需要生产的数量 */
#define MAX 1000000000										
pthread_mutex_t the_mutex;
/* 使用信号量 */
pthread_cond_t condc,condp;								
int buffer = 0;

/* 生产数据 */
void *producer(void *ptr){								
  
  int i;
  
  for(int i = 0;i <= MAX;i++){
    /* 缓冲区独占访问，也就是使用 mutex 获取锁 */
    pthread_mutex_lock(&the_mutex);				
    while(buffer != 0){
      pthread_cond_wait(&condp,&the_mutex);
    }
    /* 把他们放在缓冲区中 */
    buffer = i;			
    /* 唤醒消费者 */
    pthread_cond_signal(&condc);	
    /* 释放缓冲区 */
    pthread_mutex_unlock(&the_mutex);			
  }
  pthread_exit(0);
  
}

/* 消费数据 */
void *consumer(void *ptr){								
  
  int i;
  
  for(int i = 0;i <= MAX;i++){
    /* 缓冲区独占访问，也就是使用 mutex 获取锁 */
    pthread_mutex_lock(&the_mutex);				
    while(buffer == 0){
      pthread_cond_wait(&condc,&the_mutex);
    }
    /* 把他们从缓冲区中取出 */
    buffer = 0;	
    /* 唤醒生产者 */
    pthread_cond_signal(&condp);
    /* 释放缓冲区 */
    pthread_mutex_unlock(&the_mutex);			
  }
  pthread_exit(0);
  
}

монитор

Чтобы иметь возможность писать более точные программы, Бринч Хансен и Хоар предложили более продвинутый примитив синхронизации, названный管程(monitor). У них немного разные предложения, как вы можете понять из описаний ниже. Монитор — это набор программ, переменных и структур данных, образующих специальный модуль или пакет. Процессы могут вызывать программы в мониторе, когда захотят, но они не могут получить доступ к структурам данных и программам из-за пределов монитора. Ниже показан абстрактный, лаконичный монитор, аналогичный показанному в Pascal. Его нельзя описать на языке C, потому что мониторы — это языковые концепции, а язык C не поддерживает мониторы.

monitor example
	integer i;
	condition c;
	
	procedure producer();
  ...
	end;	
	
	procedure consumer();
	.
	end;
end monitor;

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

За мьютексы в монитор отвечает компилятор, но общепринятой практикой является использование互斥量(mutex)и二进制信号量(binary semaphore). Поскольку работает компилятор, а не программист, вероятность ошибки значительно снижается. В любой момент программисту, пишущему монитор, не нужно заботиться о том, как компилятор его обрабатывает. Ему нужно только знать, чтобы преобразовать все критические разделы в процедуры мониторинга. Никогда не может быть двух процессов, выполняющих код в критической секции одновременно.

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

Решение состоит в том, чтобы представить条件变量(condition variables)и связанные две операцииwaitиsignal. Когда монитор обнаруживает, что он не может работать (например, производитель обнаруживает, что буфер заполнен), он выполняется с некоторой условной переменной (например, заполненной).waitработать. Эта операция блокирует вызывающий процесс, а также вызывает в монитор другой процесс, который ранее ожидал вне монитора. Ранее мы обсуждали детали реализации условных переменных в pthreads. Другой процесс, такой как потребитель, может выполнятьсяsignalчтобы разбудить заблокированный вызывающий процесс.

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

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

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

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

Вот использованиеPascalРешение проблемы производитель-потребитель, реализованное языком через монитор

monitor ProducerConsumer
		condition full,empty;
		integer count;
		
		procedure insert(item:integer);
		begin
				if count = N then wait(full);
				insert_item(item);
				count := count + 1;
				if count = 1 then signal(empty);
		end;
		
		function remove:integer;
		begin
				if count = 0 then wait(empty);
				remove = remove_item;
				count := count - 1;
				if count = N - 1 then signal(full);
		end;
		
		count := 0;
end monitor;

procedure producer;
begin
			while true do
      begin 
      			item = produce_item;
      			ProducerConsumer.insert(item);
      end
end;

procedure consumer;
begin 
			while true do
			begin
						item = ProducerConsumer.remove;
						consume_item(item);
			end
end;

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

Хоть Pascal-подобный и является воображаемым языком, но поддерживаются некоторые реальные языки программирования, такие как Java (наконец-то настала очередь большой Java), Java может поддерживать мониторы, это своего рода面向对象Язык, который поддерживает потоки пользовательского уровня, а также позволяет разделять методы на классы. Просто введите ключевое словоsynchronizedКлючевое слово может быть добавлено к методу. Java гарантирует, что после того, как поток выполнит метод, никакому другому потоку не будет разрешено выполнять какие-либо синхронизированные методы для объекта. Без ключевого слова synchronized нет гарантии, что не будет перекрестного выполнения.

Ниже приведена проблема производителя-потребителя, решаемая Java с использованием монитора.

public class ProducerConsumer {
  // 定义缓冲区大小的长度
  static final int N = 100;
  // 初始化一个新的生产者线程
  static Producer p = new Producer();
  // 初始化一个新的消费者线程
  static Consumer c = new Consumer();		
  // 初始化一个管程
  static Our_monitor mon = new Our_monitor(); 
  
  // run 包含了线程代码
  static class Producer extends Thread{
    public void run(){												
      int item;
      // 生产者循环
      while(true){														
        item = produce_item();
        mon.insert(item);
      }
    }
    // 生产代码
    private int produce_item(){...}						
  }
  
  // run 包含了线程代码
  static class consumer extends Thread {
    public void run( ) {											
   		int item;
      while(true){
        item = mon.remove();
				consume_item(item);
      }
    }
    // 消费代码
    private int produce_item(){...}						
  }
  
  // 这是管程
  static class Our_monitor {									
    private int buffer[] = new int[N];
    // 计数器和索引
    private int count = 0,lo = 0,hi = 0;			
    
    private synchronized void insert(int val){
      if(count == N){
        // 如果缓冲区是满的，则进入休眠
        go_to_sleep();												
      }
      // 向缓冲区插入内容
			buffer[hi] = val;					
      // 找到下一个槽的为止
      hi = (hi + 1) % N; 				
      // 缓冲区中的数目自增 1 
      count = count + 1;											
      if(count == 1){
        // 如果消费者睡眠，则唤醒
        notify();															
      }
    }
    
    private synchronized void remove(int val){
      int val;
      if(count == 0){
        // 缓冲区是空的，进入休眠
        go_to_sleep();												
      }
      // 从缓冲区取出数据
      val = buffer[lo];				
      // 设置待取出数据项的槽
      lo = (lo + 1) % N;					
      // 缓冲区中的数据项数目减 1 
      count = count - 1;											
      if(count = N - 1){
        // 如果生产者睡眠，唤醒它
        notify();															
      }
      return val;
    }
    
    private void go_to_sleep() {
      try{
        wait( );
      }catch(Interr uptedExceptionexc) {};
    }
  }
      
}

Приведенный выше код в основном проектирует четыре класса,外部类(outer class)ProducerConsumer создает и запускает два потока, p и c. второй класс и третий классProducerиConsumerСодержит код производителя и потребителя соответственно. Наконец,Our_monitorэто монитор, который имеет два синхронизированных потока для вставки и удаления данных из общего буфера.

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

Самое интересное в программе то, чтоOur_monitor, который содержит буферы, управляемые переменные и два метода синхронизации. Пока производитель активен внутри вставки, он гарантирует, что потребитель не сможет работать в методе удаления, тем самым гарантируя безопасность обновления переменных и буферов, не беспокоясь о состоянии гонки. Переменная count записывает количество данных в буфере. Переменнаяlo- порядковый номер слота буфера, указывающий, какой следующий элемент данных будет извлечен. Так же,hiпорядковый номер следующего элемента данных, который будет помещен в буфер. lo = hi допускается, что означает наличие 0 или N данных в буфере.

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

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

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

обмен сообщениями

Другими упомянутыми выше методами являются消息传递(messaage passing). Этот метод межпроцессного взаимодействия использует два примитиваsendиreceive, они похожи на семафоры, а не на мониторы, и являются системными вызовами, а не уровнем языка. Примеры следующие

send(destination, &message);

receive(source, &message);

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

Основы проектирования системы обмена сообщениями

Системы обмена сообщениями в настоящее время сталкиваются со многими проблемами и трудностями проектирования, которые не решаются семафорами и мониторами, особенно при обмене данными между различными машинами в сети. Например, сообщения могут быть потеряны в сети. Чтобы предотвратить потерю сообщения, отправитель и получатель могут договориться: как только сообщение получено, получатель немедленно отправляет обратно специальный确认(acknowledgement)Информация. Если отправитель не получает подтверждение в течение определенного интервала, сообщение отправляется повторно.

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

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

Система обмена сообщениями также должна иметь дело с тем, как назвать процесс, чтобы его можно было четко идентифицировать в вызове отправки или получения.身份验证(authentication)Также вопрос, например, как клиент узнает, что он разговаривает с реальным файловым сервером, и что информация от отправителя к получателю может быть изменена человеком посередине.

Решение проблемы производитель-потребитель с передачей сообщений

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

/* buffer 中槽的数量 */
#define N 100													

void producer(void){
  
  int item;
  /* buffer 中槽的数量 */
  message m;													
  
  while(TRUE){
    /* 生成放入缓冲区的数据 */
    item = produce_item();						
    /* 等待消费者发送空缓冲区 */
    receive(consumer,&m);							
    /* 建立一个待发送的消息 */
    build_message(&m,item);						
    /* 发送给消费者 */
    send(consumer,&m);								
  }
  
}

void consumer(void){
  
  int item,i;
  message m;
  
  /* 循环N次 */
  for(int i = 0;i < N;i++){						
    /* 发送N个缓冲区 */
    send(producer,&m);								
  }
  while(TRUE){
    /* 接受包含数据的消息 */
    receive(producer,&m);							
    /* 将数据从消息中提取出来 */
  	item = extract_item(&m);					
    /* 将空缓冲区发送回生产者 */
    send(producer,&m);								
    /* 处理数据 */
    consume_item(item);								
  }
  
}

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

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

Существует множество вариантов передачи сообщений, и ниже описано, как编址.

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

барьер

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

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

Избегайте блокировок: чтение-копирование-обновление

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

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

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

На диаграмме выше мы удаляем B и D. Сначала наведите левый дочерний указатель A на C . Все операции чтения, первоначально выполненные в A, будут выполняться до узла C и никогда не будут читаться в узлах B и D. То есть они будут читать только новую версию данных. Аналогично, все текущие чтения в B и D будут продолжать следовать указателям исходной структуры данных и читать устаревшие данные. Все работает правильно и нам не нужно ничего блокировать. Основная причина возможности удаления B и D без блокировки данных заключается в том, что读-复制-更新(Ready-Copy-Update,RCU), который разделяет процессы удаления и повторного распространения в процессе обновления.

расписание

Когда компьютер представляет собой мультипрограммную систему, часто существует множество процессов или потоков, конкурирующих за квоты процессорного времени в одно и то же время. Это происходит, когда два или более процессов/потоков находятся в состоянии готовности. Если доступен только один ЦП, то он должен выбрать, какой процесс/поток может выполняться следующим. Есть операционная система под названием调度程序(scheduler)Роль существует, она делает это, алгоритм, используемый программой, называется调度算法(scheduling algorithm).

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

Введение в планирование

Давайте вернемся к ранним временам пакетных систем с картами на ленте в качестве входных данных, когда алгоритм планирования был очень простым: запускать каждое задание на ленте по очереди. Для мультипрограммных систем это немного сложнее, потому что обычно есть несколько пользователей, ожидающих обслуживания. Некоторые мейнфреймы по-прежнему批处理и分时服务При совместном использовании планировщик должен решить, будет ли следующим запущено пакетное задание или пользователь на терминале. Поскольку ЦП является дефицитным ресурсом на этих машинах, хороший планировщик может иметь большое значение для повышения производительности и удовлетворенности пользователей.

поведение процесса

Почти все процессы (дисковые или сетевые) запросы ввода-вывода и вычисления выполняются попеременно.

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

Выше a показан процесс с интенсивным использованием ЦП; b — процесс с интенсивным вводом-выводом, a потому что для его вычисления требуется больше времени, поэтому он называется计算密集型(compute-bound)илиCPU 密集型(CPU-bound), b вызывается, потому что частота ввода-вывода вышеI/O 密集型(I/O-bound).计算密集型进程有较长的 CPU 集中使用和较小频度的 I/O 等待。 I/O 密集型进程有较短的 CPU 使用时间和较频繁的 I/O 等待。注意到上面两种进程的区分关键在于 CPU 的时间占用而不是 I/O 的时间占用。 I/O 密集型的原因是因为它们没有在 I/O 之间花费更多的计算、而不是 I/O 请求时间特别长。无论数据到达后需要花费多少时间，它们都需要花费相同的时间来发出读取磁盘块的硬件请求。

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

Когда запланировать

Первая проблема связана с планированием и何时进行调度决策.存在着需要调度处理的各种情形。首先，在创建一个新进程后，需要决定是运行父进程还是子进程。因为二者的进程都处于就绪态下，这是正常的调度决策，可以任意选择，也就是说，调度程序可以任意的选择子进程或父进程开始运行。

Во-вторых, решения о планировании должны приниматься по завершении процесса. Поскольку этот процесс больше не выполняется (поскольку он больше не будет существовать), необходимо выбрать другие процессы для запуска из готовых процессов. Если ни один процесс не находится в состоянии готовности, система предоставляет空闲进程обычно работает

Что такое бездействующий процесс

空闲进程(system-supplied idle process)Это системный процесс с операционной системой Microsoft Windows.Процесс представляет собой отдельный поток, работающий на каждом процессоре.Его единственная задача - занимать процессорное время, когда система не обрабатывает другие потоки. System Idle Process — это не настоящий процесс, а核心虚拟Нет, многозадачные операционные системы существуют. Когда нет доступного процесса, система находится в состоянии простоя, в это время выполняется процесс простоя системы. Вы можете просто понять, что это представляет собой состояние простоя ЦП.Чем больше значение, тем больше простаивает процессор.Вы можете просмотреть использование ЦП в Windows через диспетчер задач Windows.

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

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

Если аппаратные часы обеспечивают периодические прерывания на частоте 50 или 60 Гц или на других частотах, решения по планированию могут приниматься при каждом прерывании часов или при k-м прерывании часов. Алгоритмы планирования можно разделить на две категории в зависимости от того, как обрабатываются прерывания часов.非抢占式(nonpreemptive)Алгоритм планирования выбирает процесс и позволяет этому процессу работать до тех пор, пока он не будет заблокирован (заблокирован ввод-вывод или ожидание другого процесса) или пока процесс автоматически не освободит ЦП. Даже после того, как процесс проработает несколько часов, его нельзя будет принудительно приостановить. Это предотвращает планирование, когда происходит прерывание часов. После обработки прерывания часов, если нет ожидающих процессов с более высоким приоритетом, прерванный процесс продолжает выполнение.

Другой случай抢占式Алгоритм планирования, который выбирает процесс и заставляет его работать в течение максимально фиксированного времени. Если он все еще работает после интервала, процесс будет приостановлен, и планировщик выберет другой процесс для запуска (при условии, что есть готовый процесс). Упреждающее планирование требует прерывания часов в конце интервала, чтобы вернуть управление ЦП планировщику. Если часы недоступны, единственным вариантом является невытесняющий.

Классификация алгоритмов планирования

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

  • 批处理(Batch)
  • 交互式(Interactive)
  • 实时(Real time)

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

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

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

Цель алгоритма планирования

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

Все системы

В любом случае,公平очень важно. Предоставление одному процессу большего количества процессорного времени, чем другим эквивалентным процессам, несправедливо по отношению к другим процессам. Конечно, разные типы процессов можно обрабатывать по-разному.

Справедливость — это система强制执行,Что это обозначает? Если система выплаты заработной платы в компании запланирована на 15 число этого месяца, то перед лицом эпидемии всем будет очень плохо, в это время начальник сказал, что зарплата будет выплачена вечером 14 числа, затем планировщик должен заставить процесс выполнить платеж вечером 14. Стратегия зарплаты.

Еще одна общая цель - сохранить систему所有部分尽可能的忙碌. Если бы центральный процессор и все устройства ввода-вывода работали все время, в секунду можно было бы выполнять больше работы, чем если бы что-то простаивало. Например, в пакетной системе планировщик определяет, какие задания загружаются в память для выполнения. Иметь в памяти некоторые процессы, интенсивно использующие ЦП, и некоторые процессы, интенсивно использующие ввод-вывод, — это лучшая идея, чем сначала вызывать и запускать все задания, интенсивно использующие ЦП, а затем вызывать и запускать их после их завершения. Практика для всех операций ввода-вывода. интенсивные работы. Использование последнего метода приведет к тому, что процессы с интенсивным использованием ЦП начнут конкурировать за ЦП, пока диск простаивает, а когда запустятся процессы с интенсивным вводом-выводом, они будут конкурировать за диск, а ЦП будет простаивать. . . . . . Очевидно, что за счет сочетания интенсивного ввода-вывода и интенсивного использования процессора вся система может работать более плавно и эффективно.

пакетная система

Обычно есть три индикатора для измерения рабочего состояния системы:Пропускная способность, время обработки и загрузка ЦП,吞吐量(throughout)количество заданий, выполняемых системой в час. Учитывая все обстоятельства, 50 заданий в час лучше, чем 40 заданий в час.周转时间(Turnaround time)— это среднее время, которое относится к среднему времени от отправки пакета до момента завершения задания. Эти данные измеряют среднее время ожидания пользователями результатов. Чем меньше время оборота, тем лучше.

CPU 利用率(CPU utilization)Часто используются в качестве индикаторов периодической системы. Тем не менее, загрузка ЦП не является хорошей метрикой, реальное значение — это мера того, сколько работы может быть выполнено системой (пропускная способность) в час, а также сколько времени требуется для завершения работы (время выполнения). Использование ЦП в качестве показателей, например, сколько раз в час вращается двигатель для сравнения производительности автомобиля, одинаково. И знайте, когда загрузка ЦП близка к 100% лучше, чем когда требования увеличивают вычислительную мощность.

интерактивная система

Для интерактивных систем существуют разные метрики. Самое главное попробовать减少响应时间. Это время относится ко времени от выполнения инструкции до результата. На персональных компьютерах с запущенными фоновыми процессами (например, чтение и сохранение файлов электронной почты из сети) запрос пользователя на запуск программы или открытие файла должен иметь приоритет над фоновой работой. Хороший сервис первым делом запускает все интерактивные запросы.

Связанный с этим вопрос均衡性(proportionality)Пользователи всегда имеют фиксированную (хотя часто неверный) вид на то, сколько времени нужно что-то делать. Когда запрос считается сложным и занимает много времени, пользователь подумает, что это нормально и приемлемо, но очень простая программа занимает много времени, и пользователь будет очень раздражен. Возьмите цветную печать и копирование как простой пример, цветная печать может занять 1 минуту, но пользователь находит его сложным и готов подождать минуту, наоборот, копирование простую и всего 5 секунд, но копир занимает 1 минуту И не заканчивает операцию копирования, пользователь будет очень тревожен.

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

Системы в реальном времени имеют разные соображения интерактивных систем, поэтому существуют различные цели планирования. Система в реальном времени характеризуется必须满足最后的截止时间. Например, если компьютер управляет устройством с фиксированной скоростью для генерации данных, то несвоевременный запуск может привести к потере данных. Поэтому к системе реального времени наиболее важным требованием является соответствие всему (или большинству) периоду времени.

В некоторых практических системах, особенно связанных с мультимедиа,可预测性很重要. Иногда несоблюдение окончательного срока не имеет значения, но если аудио-мультимедиа работает нестабильно, качество звука будет продолжать ухудшаться. Видео тоже может вызывать проблемы, но уши гораздо чувствительнее глаз. Чтобы избежать этих проблем, планирование процессов должно быть очень предсказуемым и регулярным.

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

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

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

Это как первый пришел первый обслужен. . . Вероятно, простейшая конструкция алгоритма планирования без вытеснения такова.先来先服务(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 на рисунке ниже.

Единственным интересным аспектом циклического планирования временных интервалов является длина временного интервала. Переключение с одного процесса на другой требует некоторого времени на административную обработку, включая сохранение значений регистров и карт памяти, обновление различных таблиц и списков, очистку и перезагрузку кэшей памяти и так далее. Этот переключатель называется进程间切换(process switch)и上下文切换(context switch). Если время переключения между процессами занимает 1 мс, включая отображение памяти, очистку и перезагрузку и т. д., и при условии, что квант времени установлен на 4 мс, то ЦП потратит 1 мс после того, как ЦП выполнил 4 мс полезной работы. . Следовательно, квант времени ЦП будет тратить 20% своего времени на управление. Дорого.

Для повышения эффективности процессора мы установили квант времени на 100 мс. Потери времени теперь составляют всего 1%. Но рассмотрим следующую ситуацию: что произойдет, если 50 запросов поступят за очень короткий промежуток времени и будут иметь разные требования к ЦП? Все 50 процессов помещаются в список запущенных процессов. Если ЦП бездействует, первый процесс начнет выполняться немедленно, второй запустится только через 100 мс и так далее. К сожалению, последний процесс должен ждать 5 секунд, чтобы получить возможность выполниться. Большинство пользователей обнаружат, что выполнение короткой команды в течение 5 секунд — это медленно. Это очень плохой дизайн, если для выполнения некоторых запросов в конце очереди требуется всего несколько секунд.

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

Вывод можно сформулировать так: установка слишком короткого времени переключения контекста вызовет избыточное переключение процессов и снизит эффективность процессора, а слишком длинное приведет к тому, что короткий запрос будет долго оставаться без ответа. Лучшее время переключения устанавливается между 20 - 50 мс.

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

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

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

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

Процессам можно назначать приоритеты статически или динамически. На военном компьютере можно установить приоритет процессов, запускаемых генералами, равным 100, полковникам 90, майорам 80, капитанам 70, лейтенантам 60 и так далее. В UNIX есть команда дляnice, который позволяет пользователям добровольно понизить приоритет своих собственных процессов, чтобы позаботиться о других, но обычно не используется.

Приоритет также может динамически назначаться системой для достижения определенной цели. Например, некоторые процессы требуют интенсивного ввода-вывода и большую часть времени тратят на ожидание завершения ввода-вывода. Когда такому процессу требуется ЦП, ЦП должен быть немедленно выделен для инициирования следующего запроса ввода-вывода, чтобы операция ввода-вывода могла выполняться, пока другой процесс выполняет вычисления. Такой процесс с интенсивным вводом-выводом, ожидающий ЦП в течение длительного времени, приведет только к тому, что он будет занимать память в течение длительного времени. Простой алгоритм улучшения обслуживания процессов с интенсивным вводом-выводом состоит в том, чтобы установить для них приоритет1/f, f — часть процесса в предыдущем интервале времени. Процесс, который использует только 1 мс в 50-мс квант времени, получит приоритет 50, в то время как процесс, который использует 25 мс до блокировки, будет иметь приоритет 2, а процесс, который использует весь квант времени, получит приоритет 1.

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

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

многоуровневая очередь

Самые ранние системы для использования приоритетных планировщиков былиCTSS(Compatible TimeSharing System). CTSS — совместимая система с разделением времени, у нее проблема в том, что переключение процессов происходит слишком медленно, причина в том, что память IBM 7094 может вместиться только в один процесс.

IBM был компьютером в Компьютерном центре Колумбийского университета с 1964 по 1968 год.

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

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

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

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

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

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

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

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

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

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

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

George OrwellоВсе процессы равны, но некоторые процессы могут быть более равными. Некоторые важные процессы могут дать им дополнительные лотерейные билеты, чтобы увеличить их шансы на выигрыш. Если продано 100 билетов и процесс содержит 20 из них, шанс выиграть в лотерею составляет 20%. В длинных прогонах он получает 20% ЦП. И наоборот, с планировщиком приоритетов трудно сказать, что именно означает наличие приоритета 40, здесь ясно правило, что процесс с f долей в лотерее получает примерно f долей системных ресурсов.

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

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

Планирование справедливого распределения

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

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

Планирование в системах реального времени

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

Системы в реальном времени могут быть разделены на две категории,硬实时(hard real time)и软实时(soft real time)Система, первое означает, что должен быть соблюден абсолютный крайний срок; второе означает, что, хотя случайный срок не может быть пропущен, с ним можно мириться. В обоих случаях режим реального времени достигается за счет разделения программы на набор процессов, где поведение каждого процесса предсказуемо и известно заранее. Эти процессы, как правило, недолговечны и очень быстро завершаются. При обнаружении внешнего сигнала задача планировщика состоит в том, чтобы запланировать процессы так, чтобы уложиться во все сроки.

События в системе реального времени можно дополнительно классифицировать на周期性(以规则的时间间隔发生)событие или非周期性(发生时间不可预知)событие. Системе может потребоваться реагировать на несколько периодических потоков событий, и в зависимости от того, сколько времени требуется для обработки каждого события, она может быть даже не в состоянии обработать их все. Например, если есть m периодических событий, событие i происходит в период Pi и требует Ci секунд процессорного времени для обработки одного события, то нагрузка может быть обработана, если

Только системы реального времени, которые удовлетворяют этому условию, называются可调度的, что означает, что это действительно может быть реализовано. Процесс, не прошедший этот тест, не может быть запланирован, поскольку сумма времени ЦП, требуемого этими процессами, больше, чем время, которое может предоставить ЦП.

В качестве примера учитывайте мягкую систему в реальном времени с тремя периодическими событиями с периодами 100 мс, 200 м и 500 мс. Если эти события требуют 50 мс, 30 мс и 100 мс времени ЦП, соответственно, система планируется, потому что 0,5 + 0,15 + 0,2

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

Политики и механизмы планирования

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

Решение проблемы заключается в调度机制(scheduling mechanism)и调度策略(scheduling policy)Отдельно, это долгосрочный последовательный принцип. Это также означает, что алгоритм планирования каким-то образом параметризован, но параметры могут быть заполнены пользовательским процессом. Давайте сначала рассмотрим пример с базой данных. Предположим, что ядро ​​использует алгоритм планирования приоритетов и предоставляет системный вызов, позволяющий процессам устанавливать приоритеты. Таким образом, хотя сам родительский процесс не участвует в планировании, он может управлять деталями планирования дочерних процессов. Механизм планирования находится в ядре, а политика планирования определяется пользовательским процессом.Разделение политики планирования и механизма является ключевой идеей.

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

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

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

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

Теперь рассмотрим случай, когда у потока A меньше работы на вычисление ЦП, например: 5 мс вычислений работают за 50-мс квант времени. Таким образом, каждый поток работает какое-то время, а затем возвращает ЦП планировщику потоков. Таким образом, прежде чем ядро ​​переключится на процесс B, будет последовательность A1,A2,A3,A1,A2,A3,A1,A2,A3,A1 . Следующее

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

现在考虑使用内核线程的情况，内核选择一个特定的线程运行。它不用考虑线程属于哪个进程，不过如果有必要的话，也可以这么做。对被选择的线程赋予一个时间片，而且如果超过了时间片，就会强制挂起该线程。一个线程在 50 ms 的时间片内，5 ms 之后被阻塞，在 30 ms 的时间片中，线程的顺序会是 A1,B1,A2,B2,A3,B3。 Как показано ниже

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

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

Ссылка на статью:

«Современные операционные системы».

《Современная операционная система》четвертое издание

woohoo.encyclopedia.com/computing/you…

Просто 00, как .ve Series Rogue.org/sys звонит / в тот день ...

woohoo.bottom upparameters.com/process_or т.е...

En. Wikipedia.org/wiki/run Тим…

Итак, Wikipedia.org/wiki/exe вырезать…

Знайте. Baidu.com/question/11…

Baike.baidu.com/item/wait queue / 9 ...

Woohoo.columbia.amount / Ground / com Путин ...

baike.baidu.com/item/interrupt-vector/4…

Категории