OberonCore
https://forum.oberoncore.ru/

Хоаровский Monitor
https://forum.oberoncore.ru/viewtopic.php?f=31&t=665
Страница 1 из 1

Автор:  Сергей Губанов [ Среда, 26 Сентябрь, 2007 21:06 ]
Заголовок сообщения:  Хоаровский Monitor

Я тут Монитор написал. В удачном случае (т.е. когда не надо ожидать) вход+выход выполняется примерно за 16 машинных инструкций. В дотнете Монитор в удачном случае срабатывает примерно за 5 инструкций, но там видимо компилятор инлайнит код.

Код:
MODULE Monitor;

  IMPORT WinApi;
 
  TYPE
    Handle* = POINTER TO LIMITED RECORD
      count: INTEGER;
      enter, pulse: WinApi.HANDLE
    END;

  PROCEDURE New* (): Handle;
    VAR h: Handle;
  BEGIN NEW(h);
    h.enter := WinApi.CreateEvent(NIL, WinApi.FALSE, WinApi.TRUE, NIL);
    h.pulse := WinApi.CreateEvent(NIL, WinApi.TRUE, WinApi.FALSE, NIL);
    RETURN h
  END New;

  PROCEDURE Enter* (h: Handle);
    VAR res: INTEGER;
  BEGIN
    IF WinApi.InterlockedIncrement(h.count) # 1 THEN
      res := WinApi.WaitForSingleObject(h.enter, WinApi.INFINITE)
    END
  END Enter;

  PROCEDURE Exit* (h: Handle);
    VAR ok: WinApi.BOOL;
  BEGIN
    IF WinApi.InterlockedDecrement(h.count) # 0 THEN
      ok := WinApi.SetEvent(h.enter)
    END
  END Exit;

  PROCEDURE Wait* (h: Handle);
    VAR res: INTEGER;
  BEGIN   
    res := WinApi.SignalObjectAndWait(h.enter, h.pulse, WinApi.INFINITE, WinApi.FALSE);
    res := WinApi.InterlockedDecrement(h.count);
    Enter(h)
  END Wait;

  PROCEDURE Pulse* (h: Handle);
    VAR ok: WinApi.BOOL;
  BEGIN ok := WinApi.PulseEvent(h.pulse)
  END Pulse;

  PROCEDURE (h: Handle) FINALIZE-;
    VAR ok: WinApi.BOOL;
  BEGIN
    ok := WinApi.CloseHandle(h.pulse);
    ok := WinApi.CloseHandle(h.enter)
  END FINALIZE;

END Monitor.


Пример использования:
Код:
  IMPORT Monitor;

  TYPE
    Element* = INTEGER;

    Queue* = POINTER TO LIMITED RECORD
      synchRoot: Monitor.Handle;
      buffer: ARRAY 3 OF Element;
      begin, end, count, enqueued, dequeued: INTEGER;
    END;

  PROCEDURE NewQueue* (): Queue;
    VAR q: Queue;
  BEGIN NEW(q);
    q.synchRoot := Monitor.New();
    RETURN q
  END NewQueue;

  PROCEDURE (q: Queue) Enqueue* (e: Element), NEW;
  BEGIN
    Monitor.Enter(q.synchRoot);
    WHILE q.count >= LEN(q.buffer) DO Monitor.Wait(q.synchRoot) END;
    INC(q.count);
    INC(q.enqueued);
    q.buffer[q.end] := e;
    q.end := (q.end + 1) MOD LEN(q.buffer);
    Monitor.Pulse(q.synchRoot);
    Monitor.Exit(q.synchRoot)
  END Enqueue;

  PROCEDURE (q: Queue) Dequeue* (OUT e: Element), NEW;
  BEGIN
    Monitor.Enter(q.synchRoot);
    WHILE q.count < 1 DO Monitor.Wait(q.synchRoot) END;
    DEC(q.count);
    INC(q.dequeued);
    e := q.buffer[q.begin];
    q.begin := (q.begin + 1) MOD LEN(q.buffer);
    Monitor.Pulse(q.synchRoot);
    Monitor.Exit(q.synchRoot)
  END Dequeue;

Автор:  Wlad [ Среда, 26 Сентябрь, 2007 22:47 ]
Заголовок сообщения:  Re: Хоаровский Monitor

Сергей Губанов писал(а):
Я тут Монитор написал.

Любо! :о)
Сергей, а вот посмотрите: думаю не только в вашей демонстрашке, но и в остальных "жизненных примерах" методы Pulse и Exit будут "ходить друг с другом". По-моему, имеет смысл их "слить" в один - Exit...

Автор:  Илья Ермаков [ Четверг, 27 Сентябрь, 2007 10:35 ]
Заголовок сообщения:  Re: Хоаровский Monitor

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

Автор:  Сергей Губанов [ Пятница, 28 Сентябрь, 2007 10:27 ]
Заголовок сообщения:  Re: Хоаровский Monitor

Владимир Лось писал(а):
Сергей Губанов писал(а):
Я тут Монитор написал.

Любо! :о)
Сергей, а вот посмотрите: думаю не только в вашей демонстрашке, но и в остальных "жизненных примерах" методы Pulse и Exit будут "ходить друг с другом". По-моему, имеет смысл их "слить" в один - Exit...


Да, можно вместо Pulse ввести PulseAndExit, но просто голый Exit тоже надо оставить, он иногда нужен сам по себе.

В приведённом примере Wait & Pulse используются и в Enqueue и в Dequeue потому что размер буфера фиксирован (сигналы посылаются в "оба конца"). Если разрешить размер буфера динамически увеличивать, то Pulse понадобится только в Enqueue (а Wait только в Dequeue; сигналы -- только в одну сторону). Вызов системных функций в Windows очень медленный, так что если есть возможность их не вызывать, то надо этой возможностью обязательно воспользоваться.

Автор:  Сергей Губанов [ Пятница, 28 Сентябрь, 2007 17:05 ]
Заголовок сообщения:  Re: Хоаровский Monitor

Сергей Губанов писал(а):
...вход+выход выполняется примерно за 16 машинных инструкций...

Прошу прощения если ввёл кого-то в заблуждение этой фразой. Под "машинными инструкциями" я здесь имел ввиду не совсем то что общепринято (измерил в попугаях :D ).

Я имел ввиду, что скорости выполнения следующих циклов одинаковы:
Код:
FOR i := 1 TO N DO
  Monitor.Enter(h);
  Monitor.Exit(h)
END;

и
Код:
FOR i := 1 TO N DO
  INC(s); INC(s); INC(s); INC(s); INC(s);
  INC(s); INC(s); INC(s); INC(s); INC(s)
END;

В теле второго цикла написано 10 инкрементов, именно столько нужно их вставить для уравнения скоростей исполнения на процессоре AMD Sempron 3000+.

А те 16 - это я дома на старом Celeron померил.

Автор:  Сергей Губанов [ Воскресенье, 30 Сентябрь, 2007 00:17 ]
Заголовок сообщения:  Более близкий к оригиналу Хоаровский Monitor

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

Сначала интерфейс:
Код:
DEFINITION Hoare;

  TYPE
    Monitor = POINTER TO LIMITED RECORD
      (m: Monitor) Enter, NEW;
      (m: Monitor) Exit, NEW;
      (m: Monitor) FINALIZE-
    END;

    Condition = POINTER TO LIMITED RECORD
      (c: Condition) Signal, NEW;
      (c: Condition) Wait, NEW;
      (c: Condition) FINALIZE-
    END;

  PROCEDURE NewMonitor (): Monitor;
  PROCEDURE NewCondition (m: Monitor): Condition;

END Hoare.


Пример использования:
Код:
  IMPORT Hoare;

  TYPE
    Element* = INTEGER;

    Queue* = POINTER TO LIMITED RECORD
      monitor: Hoare.Monitor;
      nonEmpty, nonFull: Hoare.Condition;
      buffer: ARRAY 3 OF Element;
      begin, end, count, enqueued, dequeued: INTEGER;
    END;

  PROCEDURE NewQueue* (): Queue;
    VAR q: Queue;
  BEGIN NEW(q);
    q.monitor := Hoare.NewMonitor();
    q.nonEmpty := Hoare.NewCondition(q.monitor);
    q.nonFull := Hoare.NewCondition(q.monitor);
    RETURN q
  END NewQueue;

  PROCEDURE (q: Queue) Enqueue* (e: Element), NEW;
  BEGIN
    q.monitor.Enter;
    WHILE q.count >= LEN(q.buffer) DO q.nonFull.Wait END;
    INC(q.count);
    INC(q.enqueued);
    q.buffer[q.end] := e;
    q.end := (q.end + 1) MOD LEN(q.buffer);
    q.nonEmpty.Signal;
    q.monitor.Exit
  END Enqueue;

  PROCEDURE (q: Queue) Dequeue* (OUT e: Element), NEW;
  BEGIN
    q.monitor.Enter;
    WHILE q.count < 1 DO q.nonEmpty.Wait END;
    DEC(q.count);
    INC(q.dequeued);
    e := q.buffer[q.begin];
    q.begin := (q.begin + 1) MOD LEN(q.buffer);
    q.nonFull.Signal;
    q.monitor.Exit
  END Dequeue;

Вообще, в оригинале Хоар предполагал при Wait использование не WHILE, а IF. Но в его мониторе было требование чтобы процессы ожидавшие по Wait впускались первыми и будились по очереди, здесь же немного не так (будятся все), так что нужен WHILE.

Реализация:
Код:
MODULE Hoare;

  IMPORT WinApi;
 
  TYPE
    Monitor* = POINTER TO LIMITED RECORD
      n: INTEGER;
      h: WinApi.HANDLE
    END;

    Condition* = POINTER TO LIMITED RECORD
      m: Monitor;
      h: WinApi.HANDLE
    END;

  PROCEDURE NewMonitor* (): Monitor;
    VAR m: Monitor;
  BEGIN NEW(m);
    m.h := WinApi.CreateEvent(NIL, WinApi.FALSE, WinApi.TRUE, NIL);
    RETURN m
  END NewMonitor;

  PROCEDURE NewCondition* (m: Monitor): Condition;
    VAR c: Condition;
  BEGIN ASSERT(m # NIL, 20);
    NEW(c);
    c.m := m;
    c.h := WinApi.CreateEvent(NIL, WinApi.TRUE, WinApi.FALSE, NIL);
    RETURN c
  END NewCondition;

  PROCEDURE (m: Monitor) Enter*, NEW;
    VAR res: INTEGER;
  BEGIN
    IF WinApi.InterlockedIncrement(m.n) # 1 THEN
      res := WinApi.WaitForSingleObject(m.h, WinApi.INFINITE)
    END
  END Enter;

  PROCEDURE (m: Monitor) Exit*, NEW;
    VAR ok: WinApi.BOOL;
  BEGIN
    IF WinApi.InterlockedDecrement(m.n) # 0 THEN
      ok := WinApi.SetEvent(m.h)
    END
  END Exit;

  PROCEDURE (c: Condition) Wait*, NEW;
    VAR res: INTEGER;
  BEGIN   
    res := WinApi.SignalObjectAndWait(c.m.h, c.h, WinApi.INFINITE, WinApi.FALSE);
    res := WinApi.InterlockedDecrement(c.m.n);
    c.m.Enter
  END Wait;

  PROCEDURE (c: Condition) Signal*, NEW;
    VAR ok: WinApi.BOOL;
  BEGIN ok := WinApi.PulseEvent(c.h)
  END Signal;

  PROCEDURE (m: Monitor) FINALIZE-;
    VAR ok: WinApi.BOOL;
  BEGIN
    (* ok := WinApi.CloseHandle(h.pulse); *)
    ok := WinApi.CloseHandle(m.h)
  END FINALIZE;

  PROCEDURE (c: Condition) FINALIZE-;
    VAR ok: WinApi.BOOL;
  BEGIN
    ok := WinApi.CloseHandle(c.h)
  END FINALIZE;

END Hoare.

Автор:  Wlad [ Воскресенье, 30 Сентябрь, 2007 09:30 ]
Заголовок сообщения:  Re: Более близкий к оригиналу Хоаровский Monitor

Сергей Губанов писал(а):
Более близкий к оригиналу Хоаровский Монитор с явно выделенными условиями ожидания ...

Вандерфульно.

Автор:  Илья Ермаков [ Воскресенье, 30 Сентябрь, 2007 10:25 ]
Заголовок сообщения:  Re: Хоаровский Monitor

Сергей, а попробуйте вместо Event мои семафоры из SP4, модуль Synch-HostSynch - я предполагаю, что при большой нагрузке на монитор (т.е. в условиях конкурирования за ресурс) эффективность повысится весьма....

Автор:  Сергей Губанов [ Понедельник, 01 Октябрь, 2007 13:17 ]
Заголовок сообщения:  Re: Хоаровский Monitor

Илья Ермаков писал(а):
Сергей, а попробуйте вместо Event мои семафоры из SP4...


Это вот на них:
Код:
Semaphore = POINTER TO ABSTRACT RECORD
  (sem: Semaphore) POST (n: INTEGER), NEW, ABSTRACT;
  (sem: Semaphore) WAIT, NEW, ABSTRACT
END;
?

Мне кажется, что их функциональности недостаточно.
1) Нужна возможность атомарно вызвать POST(1) одного семафора затем WAIT другого: PostAndWait(postSem, 1, waitSem).
2) Что-то я никак не соображу как можно разбудить все потоки заснувшие на WAIT, ведь я не знаю их количества. Вроде нужна PostAll - будит всех.

Автор:  Илья Ермаков [ Понедельник, 01 Октябрь, 2007 14:17 ]
Заголовок сообщения:  Re: Хоаровский Monitor

Мда, забыл уже, долго соображал...

Вроде как при реализации монитора на базе семафоров обычно делают очередь ждущих объектов - и каждому выделяется свой семафор. Иначе ждущие будут пробуждаться в произвольном порядке, а не в том, в котором стали на ожидание. Я в соседней ветке выкладывал исходник модуля Ao. Там Ao.Monitor - это монитор, донавороченный до аналогии с Активным обероном viewtopic.php?p=4863#p4863

Автор:  Сергей Губанов [ Понедельник, 01 Октябрь, 2007 15:42 ]
Заголовок сообщения:  Re: Хоаровский Monitor

Илья Ермаков писал(а):
Вроде как при реализации монитора на базе семафоров обычно делают очередь ждущих объектов - и каждому выделяется свой семафор. Иначе ждущие будут пробуждаться в произвольном порядке, а не в том, в котором стали на ожидание. Я в соседней ветке выкладывал исходник модуля Ao. Там Ao.Monitor - это монитор, донавороченный до аналогии с Активным обероном viewtopic.php?p=4863#p4863

Там какая-то чёрная магия. Я её не понимаю.

Даже если делать очередь вручную (не перекладывая это на плечи ОС), всё равно нужно уметь как-то атомарным образом покидать эксклюзивный блок и незамедлительно засыпать на ожидании условного сигнала (т.е. выполнять аналог SignalAndWait). Как без этого?

Автор:  Сергей Губанов [ Понедельник, 01 Октябрь, 2007 16:10 ]
Заголовок сообщения:  Re: Хоаровский Monitor

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

Автор:  Сергей Губанов [ Четверг, 04 Октябрь, 2007 10:45 ]
Заголовок сообщения:  Хоаровский Monitor реализованный на пользовательских APC

Разобрался с APC и реализовал монитор через них напрямую без "семафорной прослойки".

Сравнил скорости работы двух реализаций мониторов: на ядерных Event-ах и на пользовательских APC. Скорость измерял в количестве операций с очередью - поставить/изъять (её код см. выше) в миллисекунду.

AMD Sempron 3000+
Max enqueue (or dequeue) rate per millisecond
2+2=4 threads:
Event --> 332
APC --> 385

50+50=100 threads:
Event --> 266
APC --> 367

APC-шная реализация хоаровского монитора:
Код:
MODULE Hoare;

   IMPORT WinApi;

   TYPE
      Monitor* = POINTER TO LIMITED RECORD
         cs: WinApi.CRITICAL_SECTION
      END;

      Condition* = POINTER TO LIMITED RECORD
         monitor: Monitor;
         n: INTEGER;
         list: ARRAY 256 OF WinApi.HANDLE
      END;

   PROCEDURE NewMonitor* (): Monitor;
      VAR m: Monitor;
   BEGIN NEW(m);
      WinApi.InitializeCriticalSection(m.cs);
      RETURN m
   END NewMonitor;

   PROCEDURE NewCondition* (m: Monitor): Condition;
      VAR c: Condition;
   BEGIN ASSERT(m # NIL, 20);
      NEW(c); c.monitor := m;
      RETURN c
   END NewCondition;

   PROCEDURE (m: Monitor) Enter*, NEW;
   BEGIN WinApi.EnterCriticalSection(m.cs)
   END Enter;

   PROCEDURE (m: Monitor) Exit*, NEW;
   BEGIN WinApi.LeaveCriticalSection(m.cs)
   END Exit;

   PROCEDURE APCEmpty (param: INTEGER);
   END APCEmpty;

   PROCEDURE (c: Condition) Signal*, NEW;
      VAR i, res: INTEGER;
   BEGIN
      IF c.n > 0 THEN
         FOR i := 0 TO c.n - 1 DO
            res := WinApi.QueueUserAPC(APCEmpty, c.list[i], 0);
            res := WinApi.CloseHandle(c.list[i])
         END;
         c.n := 0
      END
   END Signal;

   PROCEDURE (c: Condition) Wait*, NEW;
      CONST access = {0, 1, 3, 4, 16..19}; opt = {};
      VAR res: INTEGER; p: WinApi.HANDLE;
   BEGIN
      IF c.n < LEN(c.list) THEN
         p := WinApi.GetCurrentProcess();
         res := WinApi.DuplicateHandle(p, WinApi.GetCurrentThread(), p, c.list[c.n], access, 0, opt);
         INC(c.n);
         WinApi.LeaveCriticalSection(c.monitor.cs);
         res := WinApi.SleepEx(WinApi.INFINITE, WinApi.TRUE);
         WinApi.EnterCriticalSection(c.monitor.cs)
      ELSE
         WinApi.LeaveCriticalSection(c.monitor.cs);
         WinApi.Sleep(20);
         WinApi.EnterCriticalSection(c.monitor.cs)
      END
   END Wait;

   PROCEDURE (m: Monitor) FINALIZE-;
   BEGIN WinApi.DeleteCriticalSection(m.cs)
   END FINALIZE;

END Hoare.

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/