Что такое прогресс и ограниченное ожидание в критическом разделе?

Ответ 1

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

// Some arbitrary code (such as initialization).

EnterCriticalSection(cs);

// The code that constitutes the CS.
// Only one process can be executing this code at the same time. 

LeaveCriticalSection(cs);

// Some arbitrary code. This is called the remainder section.

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

Чтобы убедиться, что выполнение критических разделов работает правильно, необходимо выполнить три условия. Вы упомянули о двух из них (о чем я расскажу ниже). Третье - взаимное исключение, которое, очевидно, жизненно важно. Стоит отметить, что взаимное исключение относится только к КС и разделу отпуска. Однако остальные три раздела не являются эксклюзивными.

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

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

Познайте это предложение определения предложением.

Если ни один процесс не выполняется в его критическом разделе

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

и некоторые процессы хотят войти в их критические разделы

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

то только те процессы, которые не выполняются в их оставшейся части

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

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

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

и этот отбор не может быть отложен на неопределенный срок.

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

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

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

Поймите это предложение определения предложением, начиная с последнего.

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

Другими словами, если есть процесс, который запросил ввести его CS, но еще не ввел его. Позвольте называть этот процесс P.

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

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

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

Ответ 2

Взаимное исключение

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

Изображение для прогресса:

Прогресс

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

Ограниченное ожидание

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

Примечание
Никакое предположение не связано с H/W или скоростью обработки.

Ответ 3

В целом, решение проблемы критического сечения должно удовлетворять трем условиям:

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

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

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