Для создания параллельных программ существуют две основные концепции: синхронизация и взаимное исключение. Мы увидим, как эти два типа блокировок (семафоры в общем случае являются своего рода механизмом блокировки) помогают нам добиться синхронизации и взаимного исключения.
Семафор - это программная конструкция, которая помогает нам достичь параллелизма за счет реализации как синхронизации, так и взаимного исключения. Семафоры бывают двух типов: двоичные и счетные.
Семафор состоит из двух частей: счетчика и списка задач, ожидающих доступа к определенному ресурсу. Семафор выполняет две операции: wait (P) [это похоже на получение блокировки] и release (V) [аналогично освобождению блокировки] - это единственные две операции, которые можно выполнить с семафором. В двоичном семафоре счетчик логически переходит от 0 до 1. Вы можете думать, что он похож на блокировку с двумя значениями: открыт / закрыт. Счетный семафор имеет несколько значений для счетчика.
Что важно понять, так это то, что счетчик семафоров отслеживает количество задач, которые не нужно блокировать, то есть они могут прогрессировать. Задачи блокируются и добавляются в список семафоров только тогда, когда счетчик равен нулю. Следовательно, задача добавляется в список в процедуре P (), если она не может быть выполнена, и «освобождается» с помощью процедуры V ().
Теперь совершенно очевидно, как использовать двоичные семафоры для решения задач синхронизации и взаимоисключения - по сути, это блокировки.
ех. Синхронизация:
thread A{
semaphore &s; //locks/semaphores are passed by reference! think about why this is so.
A(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
;// some block of code B2
...
}
//thread B{
semaphore &s;
B(semaphore &s): s(s){} //constructor
foo(){
...
...
// some block of code B1
s.V();
..
}
main(){
semaphore s(0); // we start the semaphore at 0 (closed)
A a(s);
B b(s);
}
В приведенном выше примере B2 может выполняться только после того, как B1 завершил выполнение. Допустим, поток A выполняется первым, выполняет - получает sem.P () и ждет, так как счетчик равен 0 (закрыт). Появляется поток B, заканчивает B1, а затем освобождает поток A, который затем завершает B2. Таким образом, мы достигаем синхронизации.
Теперь давайте рассмотрим взаимное исключение с помощью двоичного семафора:
thread mutual_ex{
semaphore &s;
mutual_ex(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
//critical section
s.V();
...
...
s.P();
//critical section
s.V();
...
}
main(){
semaphore s(1);
mutual_ex m1(s);
mutual_ex m2(s);
}
Взаимное исключение также довольно просто - m1 и m2 не могут одновременно войти в критическую секцию. Таким образом, каждый поток использует один и тот же семафор, чтобы обеспечить взаимное исключение для его двух критических секций. Теперь возможно ли иметь больший параллелизм? Зависит от критических разделов. (Подумайте, как еще можно использовать семафоры для достижения взаимного исключения. Подсказка: мне обязательно нужно использовать только один семафор?)
Подсчет семафора: семафор с более чем одним значением. Давайте посмотрим, что это означает - блокировка с более чем одним значением? Так открыто, закрыто и ... хм. Какая польза от многоступенчатой блокировки во взаимном исключении или синхронизации?
Давайте возьмем самое простое из двух:
Синхронизация с использованием счетного семафора. Допустим, у вас есть 3 задачи - № 1 и 2, которые вы хотите выполнить после 3. Как бы вы разработали синхронизацию?
thread t1{
...
s.P();
//block of code B1
thread t2{
...
s.P();
//block of code B2
thread t3{
...
//block of code B3
s.V();
s.V();
}
Таким образом, если ваш семафор начинается закрытым, вы гарантируете, что блоки t1 и t2 будут добавлены в список семафоров. Затем приходит все важное t3, заканчивает свою деятельность и освобождает t1 и t2. В каком порядке они освобождены? Зависит от реализации списка семафоров. Может быть FIFO, может основываться на каком-то конкретном приоритете и т. Д. (Примечание: подумайте, как бы вы расположили свои P и V; если вы хотите, чтобы t1 и t2 выполнялись в определенном порядке, и если вы не знали о реализации семафора)
(Узнайте: что произойдет, если число V больше, чем число P?)
Взаимное исключение Использование счетных семафоров: я бы хотел, чтобы вы создали для этого свой собственный псевдокод (помогает вам лучше понимать вещи!), Но фундаментальная концепция такова: счетный семафор counter = N позволяет N задачам войти критический раздел свободно. Это означает, что у вас есть N задач (или потоков, если хотите), попадающих в критическую секцию, но N + 1-я задача блокируется (попадает в наш любимый список заблокированных задач) и пропускается только тогда, когда кто-то V семафор Хотя бы один раз. Таким образом, счетчик семафоров вместо того, чтобы колебаться между 0 и 1, теперь переходит от 0 до N, позволяя N задачам свободно входить и выходить, не блокируя никого!
Теперь, черт возьми, зачем тебе такая глупость? Разве не весь смысл взаимного исключения, чтобы не позволить больше чем одному парню получить доступ к ресурсу ?? (Подсказка Подсказка ... У вас не всегда есть только один диск на вашем компьютере, не так ли? ...)
Подумайте над : достигается ли взаимное исключение только с помощью счетного семафора? Что если у вас есть 10 экземпляров ресурса и 10 потоков входят (через счетный семафор) и пытаются использовать первый экземпляр?