namespace Test
{
  public sealed class MultiSemaphore
  {
    private readonly bool[] busyFlags;

    public MultiSemaphore (int count)
    {
      this.busyFlags = new bool[count];
    }

    private bool IsBusy (params int[] indexies)
    {
      foreach (int i in indexies) if (this.busyFlags[i]) return true;
      return false;
    }

    public void Enter (params int[] indexies)
    {
      lock (this)
      {
        while (this.IsBusy(indexies)) System.Threading.Monitor.Wait(this);
        foreach (int i in indexies) this.busyFlags[i] = true; // заняли
        System.Threading.Monitor.PulseAll(this);
      }
    }

    public void Exit (params int[] indexies)
    {
      lock (this)
      {
        foreach (int i in indexies) this.busyFlags[i] = false; // освободили
        System.Threading.Monitor.PulseAll(this);
      }
    }
  }
}

  MultiSemaphore sem = new MultiSemaphore(10000);

  // ...

  sem.Enter(26, 38, 17, 237, 266, 1001);
  // работа с объектами номер 26, 38, 17, 237, 266 и 1001
  sem.Exit(26, 38, 17, 237, 266, 1001);

class Something
{
private:
  mutable mutex guard_; // чтобы сделать Something монитором, нам нужно владеть мьютексом...
public:
  void foo()
  {
    mutex::scoped_lock exclusive(guard_); // ... и пользоваться им
    .....
  }

  // если любишь в жизни риск, форматируй жёсткий диск
  mutex& guard() const { return guard_; }
  void lock() const { guard_.lock(); }
  void unlock() const { guard_.unlock(); }
  // никто не заставляет отдавать ручки наружу - только добрая или злая воля автора
}

Тогда, пожалуй, что соглашусь — риск налететь на deadlock при таком подходе повышается. Но, повторюсь, дело здесь не в "нелокальности", а в том, что, фактически, у нас количество семафоров равно количеству объектов (+ N * количество_объектов_value-типов за счёт боксинга).

  System.Monitor.Enter(this);

public static void M()
{
    lock(_syncObj)
    {
        ...
    }
}

public sealed class MyClass
{
  private static Data data;

  public static void M ()
  {
    lock (typeof(MyClass))
    {
      //эксклюзивная работа с data
      ...
    }
  }
}

PROCEDURE DoSmth;
BEGIN {EXCLUSIVE}
  ...
END DoSmth;

Задача об очереди

Напишите реализацию методов Enqueue и Dequeue.

Указание
Для синхронизации потоков, где это нужно, используйте:
• lock (expression)
• System.Threading.Monitor.Wait (object obj);
• System.Threading.Monitor.PulseAll (object obj);

Время: 5 минут

namespace EmployeeTest
{
    public interface IQueue
    {
        void Enqueue (object element);
        object Dequeue ();
    }

    public sealed class MyQueue: IQueue
    {
        private sealed class Item
        {
            public object element;
            public Item next;
            public Item (object element)
            {
                this.element = element;
            }
        }

        private Item head;
        private Item tail;

        public void Enqueue (object element)
        {
            // Добавить элемент в хвост очереди.
            // Операция должна быть безопасна в условиях многопоточного использования.
        }

        public object Dequeue ()
        {
            // Если очередь пуста, то ждать (спать) до тех пор пока кто-то другой 
            // (из другого потока) добавит элемент в очередь.
            // Извлечь элемент из головы очереди и вернуть его из функции.
            // Операция должна быть безопасна в условиях многопоточного использования.
            return null;
        }
    }
}

Решение задачи об очереди

namespace EmployeeTest
{
    public interface IQueue
    {
        void Enqueue (object element);
        object Dequeue ();
    }

    public sealed class MyQueue: IQueue
    {
        private sealed class Item
        {
            public object element;
            public Item next;
            public Item (object element)
            {
                this.element = element;
            }
        }

        private Item head;
        private Item tail;

        public void Enqueue (object element)
        {
            lock (this)
            {
                Item a = new Item(element);
                if (this.tail != null) this.tail.next = a; else this.head = a;
                this.tail = a;
                System.Threading.Monitor.PulseAll(this);
            }
        }

        public object Dequeue ()
        {
            lock (this)
            {
                while (this.head == null) System.Threading.Monitor.Wait(this);
                object r = this.head.element;
                this.head = this.head.next;
                if (this.head == null) this.tail = null;
                System.Threading.Monitor.PulseAll(this);
                return r;
            }
        }
    }
}

public interface IQueue
{
  void Enqueue (object element);
  object Dequeue ();
  bool IsAvailable {get;} // не пуста ли очередь?
  bool BlockingMode {get; set;} // снять/установить/проверить блокирующий режим.
  // В случае если BlockingMode = false, то Dequeue должна выдавать исключение когда очередь пуста
  // В случае если BlockingMode = true, то Dequeue должна блокировать поток до тех пор пока очередь пуста
}

СГ>  System.Monitor.Enter(this);
СГ>

class MySyncClass
{
    object sync_obj = new object();
    public void foo()
    {
        lock (sync_obj)
        {
            // modify me
        }
    }
}

System.Threading.Monitor.Enter(obj)
try
{
  ...эксклюзивный блок кода
}
finally
{
  System.Threading.Monitor.Exit(obj);
}

        public object Dequeue ()
        {
            // перед этой командой потоки ставятся в очередь: внутрь вход по одному!
            lock (this)
            {
                // Проникнув внутрь эксклюзивного блока, поток проверяет очередь на непустоту,
                // если она пуста - засыпает. Как только он засыпает по Wait, то объект this становится
                // вновь доступен для других потоков. Раз так, то какой-то другой поток может вызвать
                // метод Enqueue и сделать очередь непустой. В конце метода Enqueue зовётся PulseAll.
                // Сработавший PulseAll будит уснувшие на этом объекте потоки. Разбуженные потоки вновь
                // впускаются внутрь эксклюзивного блока (по одному), 
                // из которого они были временно выведены на время своего сна
                while (this.head == null) System.Threading.Monitor.Wait(this);

                object r = this.head.element;
                this.head = this.head.next;
                if (this.head == null) this.tail = null;
                System.Threading.Monitor.PulseAll(this);
                return r;
            }
        }

MODULE Buffers;

CONST
  BufLen = 256;
  
TYPE
  (* Buffer- First-in first-out buffer *)

  Buffer* = OBJECT
    VAR
      data: ARRAY BufLen OF INTEGER;
      in, out: LONGINT;
      
    (* Put - insert element into the buffer *)
    
    PROCEDURE Put* (i: INTEGER);
    BEGIN {EXCLUSIVE}
      AWAIT ((in + 1) MOD BufLen # out);  (*AWAIT ~full *)
      data[in] := i;
      in := (in + 1) MOD BufLen
    END Put;
    
    (* Get - get element from the buffer *)
    
    PROCEDURE Get* (VAR i: INTEGER);
    BEGIN {EXCLUSIVE}
      AWAIT (in # out);  (*AWAIT ~empty *)
      i := data[out];
      out := (out + 1) MOD BufLen
    END Get;
    
    PROCEDURE & Init;
    BEGIN
      in := 0; out := 0;
    END Init;
  
  END Buffer;

END Buffers.

bool Dequeue (out object obj);

if (queue.Dequeue(out x))
{
  ...
}
else
{
  ... очередь оказалась пустой
}

System.Monitor.Enter(this);
  try
  {
  }
  finally
  {
    System.Monitor.PulseAll(this);
    System.Monitor.Exit(this);
  }

TYPE ClassA = CLASS
  ptrB: POINTER TO ClassB;
END;
TYPE ClassB = CLASS
  ptrA: POINTER TO ClassA;
END;


FUNCTION Construct(): POINTER TO ClassA;
BEGIN
  ptrA := NEW ClassA;
  ptrA.ptrB := NEW ClassB;
  ptrA.ptrB.ptrA := ptrA;
  Construct := ptrA;
END;


PROCEDURE ClassA.foo;
BEGIN {exclusive}
  .....
  this.ptrB.foo();
  .....
END;
PROCEDURE ClassB.foo;
BEGIN {exclusive}
  .....
END;


PROCEDURE ClassB.bar;
BEGIN {exclusive}
  .....
  this.ptrA.bar();
  .....
END;
PROCEDURE ClassA.bar;
BEGIN {exclusive}
  .....
END;

    public class A1
    {
        public Smth Smth
        {
            get { return new Smth("Smth from A1"); }
        }

        public void DoA1(A2 a2)
        {
            Smth s = a2.Smth;
            lock (this)
            {
                // некие операции с иполоьзованием this и s
            }
        }
    }

    public class A2
    {
        public Smth Smth
        {
            get { return new Smth("Smth from A2"); }
        }

        public void DoA2(A1 a1)
        {
            Smth s = a1.Smth;
            lock (this)
            {
                // некие операции с иполоьзованием this и s
            }
        }
        public void MethForA2()
        {
            lock (this)
            {
                // некие операции с иполоьзованием this
            }
        }
    }

    public class D
    {
        public void MethForA1A2(A1 a1, A2 a2)
        {
            // синхронизирует все операцию целиком, а не данные a1 и a2
            // если additionalProcessing нет, то просто переносим все либо в A1 либо в A2
            lock (this)
            {
                a1.DoA1(a2);
                additionalProcessing(a1,a2);
                a2.DoA2(a1);
            }
        }

        private void additionalProcessing(A1 a1, A2 a2)
        { }
    }

СГ>>object Dequeue();
СГ>>

СГ>>bool TryDequeue(out object obj);
СГ>>

object Dequeue();

PROCEDURE DoSmth;
BEGIN
  ...
  BEGIN {EXCLUSIVE} this.a := a1; this.b := b1 END; (* значения измененяются одной атомарной операцией *)
  ...
  BEGIN {EXCLUSIVE} this.a := a2; this.b := b2 END; (* значения измененяются одной атомарной операцией *)
  ...
END DoSmth;

System.Threading.Monitor.Enter(this);
try
{
  ...
  ...
  ...
  return x;
}
finally
{
  System.Threading.Monitor.PulseAll(this);
  System.Threading.Monitor.Exit(this);
}

lock (this)
{
  try
  {
    ...
    ...
    ...
    return x;
  } 
  finally
  {
    System.Threading.Monitor.PulseAll(this);
  }
}

Enter(a[i]);
...
Exit(a[i-1]);
...
Enter(a[i+1]);
...
Exit(a[i]);
...

TYPE
  Sem* = OBJECT  (* Binary Semaphore *)
      VAR  taken: BOOLEAN
      
      PROCEDURE P*;  (*enter semaphore*)
      BEGIN {EXCLUSIVE}
          AWAIT(~taken); taken := TRUE
      END P;
      
      PROCEDURE V*;  (*leave semaphore*)
      BEGIN {EXCLUSIVE}
          taken := FALSE
      END V;
      
      PROCEDURE & Init;
      BEGIN  taken := FALSE
      END Init;
  END Sem;

a[1].sem.p();
process(a[1].data);
                    a[2].sem.p();
                    process(a[2].data);
a[1].sem.v();
                                        a[3].sem.p();
                                        process(a[3].data);
                    a[2].sem.v();
                                        a[3].sem.v();

СГ>Лочиться только на самом себе логически следует из объединения ООП и многопоточности:
СГ>1) Все данные инкапсулированы внутри объектов.
СГ>2) Доступ к любым данным осуществляется только с помощью методов объекта.
СГ>3) Для синхронизированного (эксклюзивного) доступа к данным используются эксклюзивные методы (т.е такие методы, блоки кода в которых залочены на this).

Задача о множестве

Напишите реализацию методов IsExist, Include, Exclude.

Время: 10 минут

namespace EmployeeTest
{
    public interface ISet
    {
        void Include (object element);
        void Exclude (object element);
        bool IsExist (object element);
    }

    public sealed class MySet: ISet
    {
        private sealed class List
        {
            public object head;
            public List tail;
            public List (object head, List tail)
            {
                this.head = head; this.tail = tail;
            }
        }

        private List list;

        public bool IsExist (object element)
        {
            // Помещен ли указанный элемент в это множество?
        }

        public void Include (object element)
        {
            // Если указанного элемента в этом множестве нет, поместить его.
        }

        public void Exclude (object element)
        {
            // Исключить указанный элемент из этого множества, если он в нем есть.
        }
    }
}

Владимир Лось. Активные объекты в С++.
Предлагается библиотека libao* . Сделана попытка реализации активных объектов в духе разработок ETHZ (Active Oberon, Zonnon). Даётся описание принципов построения активных объектов и краткое введение в предлагаемую библиотеку. Рекомендуется сначала прочитать статью...

( гы-гы, если кто ещё не знает)

Semaphore s_a1;
Semaphore s_a2;
Semaphore s_a1_a2;
SomeClass a1;
SomeClass a2;

// Далее, исполняем политику, в которой сказано, что при работе с a1 и a2 сначала следует залочить s_a1_a2
void func_a1a2()
{
  Guard g(s_a1_a2);
  Guard g1(s_a1);
  Guard g1(s_a2);
  // Много-много чего-то.
}

void func_a1()
{
  Guard g1(s_a1);
  // Здесь будет что-то про a1
}

Semaphore s_a3;
Semaphore s_other_a3;
SomeClass a3;

void func_a123()
{
  Guard g123(s_other_a3);
  Guard g3(s_a3);
  Guard g12(s_a1_a2); // Условно говоря, это - наследование имеющейся политики блокировок.
  Guard g1(s_a1);
  Guard g2(s_a2);
  // Интенсивно юзаем a1, a2, a3
}

class MultiSemaphore : public LockableObject
{
    Semaphore s_my_;
    /* Список адресов остальных семафоров */ others_sems_;
  public:
    MultiSemaphore(Semaphore *p1, ...)
    {
      /*читаем в цикле через va_arg*/ other_sems_.add(other_ptr);
    }
    //
    void Lock()
    {
      s_my_.Lock();
      /* Крутим цикл по списку others_sems_, от начала в конец */
      others_sems_[i]->Lock();
    }
    void Unlock()
    {
      // NB! Действуем строго в обратном порядке по отношению к Lock()!
      /* Крутим цикл по списку others_sems_, из конца в начало */
      others_sems_[i]->Unlock();
      s_my_.Unlock();
    }
}

Semaphore s_a1;
Semaphore s_a2;
MultiSemaphore s_a1_a2(&s_a1, &s_a2, 0); // 0 - терминатор списка

void func_a1_a2()
{
  Guard g(&s_a1_a2); // гарантируем себе, что блокировка проведена правильно.
}

void func_a1()
{
  Guard g(&a1);
  // ...
}

Semaphore s_a3;
MultiSemaphore s_other_a3(&s_a3, &s_a1_a2, 0);

void func func_a123()
{
  Guard g(&s_other_a3);
  // Всё! В этой точке мы имеем корректно заблокированый контекст.
}

Разница в том, что залочится в C# можно на любом (чужом) объекте (быть может, на ровном месте неожиданно заработав deadlock), а в Active Oberon — только на самом себе (только на this).

Monitor.Enter
[...]
Invoking this member is identical to using the C# lock statement.

object MultiSemaphore;

  var busy: array 1000 of boolean;

  procedure IsBusy (s: array of integer): boolean;
    var i: integer;
  begin
    for i := 0 to len(s)-1 do
      if busy[s[i]] then return true end
    end;
    return false
  end IsBusy;

  procedure SetBusy (s: array of integer; val: boolean);
    var i: integer;
  begin
    for i := 0 to len(s)-1 do busy[s[i]] := val end
  end SetBusy;

  procedure {public} Enter (s: array of integer);
  begin {locked}
    await ~IsBusy(s);
    SetBusy(s, true)
  end Enter;

  procedure {public} Exit (s: array of integer);
  begin {locked}
    SetBusy(s, false)
  end Exit;

end MultiSemaphore.