Эта статья поможет вам понять принцип взаимодействия процессов и потоков.

задняя часть

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

Процессы должны часто взаимодействовать с другими процессами. Например, в канале оболочки выходные данные первого процесса должны быть переданы второму процессу и так далее по каналу. Следовательно, если процессам необходимо взаимодействовать, они должны использовать хорошую структуру данных, чтобы их нельзя было прервать. Ниже мы поговорим о进程间通信(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, его также нельзя использовать в качестве хорошего плана.

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

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

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

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

int turn;										/* 现在轮到谁 */
int interested[N];								/* 所有值初始化为 0 (FALSE) */

void enter_region(int process){					/* 进程是 0 或 1 */
  
  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:
		TSL REGISTER,LOCK             | 复制锁到寄存器并将锁设为1
  		CMP REGISTER,#0			      | 锁是 0 吗？
  		JNE enter_region			  | 若不是零，说明锁已被设置，所以循环
  		RET							  | 返回调用者，进入临界区
    
    
leave_region:
			MOVE LOCK,#0			  | 在锁中存入 0 
  		RET							  | 返回调用者

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

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

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

enter_region:
		MOVE REGISTER,#1						| 把 1 放在内存器中
		XCHG REGISTER,LOCK						| 交换寄存器和锁变量的内容
		CMP REGISTER,#0							| 锁是 0 吗？
		JNE enter_region						| 若不是 0 ，锁已被设置，进行循环
		RET										| 返回调用者，进入临界区
	
leave_region:										
		MOVE LOCK,#0							| 在锁中存入 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. Каждый процесс также проверяет, следует ли разбудить другие потоки, и, если да, пробуждает поток. Ниже приведен код производителя-потребителя.

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

// 消费者
void consumer(void){
  
  int item;
  
  while(TRUE){									     /* 无限循环 */
  	if(count == 0){							         /* 如果缓冲区是空的，就会进行阻塞 */
      sleep();
    }
   	item = remove_item();				              /* 从缓冲区中取出一个数据 */
    count = count - 1						         /* 将缓冲区的 count 数量减一 */
    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								/* 定义缓冲区槽的数量 */
typedef int semaphore;						/* 信号量是一种特殊的 int */
semaphore mutex = 1;						/* 控制关键区域的访问 */
semaphore empty = N;					    /* 统计 buffer 空槽的数量 */
semaphore full = 0;							/* 统计 buffer 满槽的数量 */

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

void consumer(void){
  
  int item;
  
  while(TRUE){								/* 无限循环 */
    down(&full);							/* 缓存区满槽数量 - 1 */
    down(&mutex);							/* 进入缓冲区 */	
    item = remove_item();					/* 从缓冲区取出数据 */
    up(&mutex);								/* 离开临界区 */
    up(&empty);								/* 将空槽数目 + 1 */
    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:
			TSL REGISTER,MUTEX			| 将互斥信号量复制到寄存器，并将互斥信号量置为1
			CMP REGISTER,#0				| 互斥信号量是 0 吗？
			JZE ok						| 如果互斥信号量为0，它被解锁，所以返回
			CALL thread_yield			| 互斥信号正在使用；调度其他线程
			JMP mutex_lock				| 再试一次
ok: 	RET								| 返回调用者，进入临界区

mutex_unlcok:
			MOVE MUTEX,#0				| 将 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++){
    pthread_mutex_lock(&the_mutex);		/* 缓冲区独占访问，也就是使用 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++){
    pthread_mutex_lock(&the_mutex);			/* 缓冲区独占访问，也就是使用 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();       // 初始化一个管程
  
  static class Producer extends Thread{
    public void run(){								// run 包含了线程代码
      int item;
      while(true){									// 生产者循环
        item = produce_item();
        mon.insert(item);
      }
    }
    private int produce_item(){...}					// 生产代码
  }
  
  static class consumer extends Thread {
    public void run( ) {							// 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; 							// 找到下一个槽的为止
      count = count + 1;							// 缓冲区中的数目自增 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;							// 设置待取出数据项的槽
      count = count - 1;							// 缓冲区中的数据项数目减 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)Также вопрос, например, как клиент узнает, что он разговаривает с реальным файловым сервером, и что информация от отправителя к получателю может быть изменена человеком посередине.

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

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

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

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

void consumer(void){
  
  int item,i;
  message m;
  
  for(int i = 0;i < N;i++){					/* 循环N次 */
    send(producer,&m);						/* 发送N个缓冲区 */
  }
  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), который разделяет процессы удаления и повторного распространения в процессе обновления.

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

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

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

woohoo.encyclopedia.com/computing/you…

Всего 00 лайков .VE series rogue.org/sys call/ в тот день…

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

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

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

Категории