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

Это является относительно алгоритмом планирования планирования. Пару вопросов, по-видимому, поначалу сложно, но на самом деле не (Сигнал / ждать и местом кэша). Я объясню методы, а затем дайте какой-нибудь код, который я написал, чтобы проиллюстрировать концепции, а затем дать некоторые окончательные заметки на тюнинг.

Алгоритмы использования

Обработка сигнала / ждать эффективно, поначалу кажется сложно, но на самом деле оказывается чрезвычайно легким. Поскольку пары сигнала / ожидания не могут гнездиться или перекрываться, действительно могут быть только два удовлетворены, и в любое время ждали время. Просто указывая указатель «CurrentGignal» на самый последний неудовлетворенный сигнал, это все, что необходимо сделать для бухгалтерии.

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

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

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

Структуры данных

Вот основные структуры данных, которые вам понадобится:

class Scheduler
{
  LinkedList<JobList>[] Ready; // Indexed by number of cores working on list
  LinkedList<JobList> Blocked;
  int ReadyCount;
  bool Exit;

  public:
    void AddList(JobList* joblist);
    void DoWork();

  internal:
    void UpdateQueues(JobList* joblist);

    void NotifyBlockedCores();
    void WaitForNotifyBlockedCores();
}

class JobList
{
  Scheduler Scheduler;
  LinkedList<JobList> CurrentQueue;

  LinkedList<Job> Jobs;            // All jobs in the job list
  LinkedList<SignalPoint> Signals; // All signal/wait pairs in the job list,
                                      plus a dummy

  Job* NextJob;                    // The next job to schedule, if any
  int NextJobIndex;                // The index of NextJob

  SignalPoint* CurrentSignal;      // First signal not fully satisfied

  int WorkerCount;                 // # of cores executing in this list

  public:
    void AddJob(Job* job);
    void AddSignal();
    void AddWait();

  internal:
    void Ready { get; }
    void GetNextReadyJob(Job& job, int& jobIndex);
    void MarkJobCompleted(Job job, int jobIndex);
}
class SignalPoint
{
  int SignalJobIndex = int.MaxValue;
  int WaitJobIndex = int.MaxValue;
  int IncompleteCount = 0;
}

Обратите внимание, что точки сигнала для данного доступа, наиболее удобно хранятся отдельно от фактического списка рабочих мест.

Реализация планировщика

Планировщик сохраняет отслеживание списков заданий, назначает их к ядрам и выполняет задания из списков заданий.

addList добавляет задание на планировщик. Он должен быть помещен на готовую или заблокированную очередь в зависимости от того, есть ли она какая-либо работа (т. Е. Независимо от того, были ли какие-либо работы были добавлены к нему еще), поэтому просто вызовите Usersqueues.

void Scheduler.AddList(JobList* joblist)
{
  joblist.Scheduler = this;
  UpdateQueues(joblist);
}

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

void Scheduler.UpdateQueues(JobList* joblist)
{
  lock(this)
  {
    // Remove from prior queue, if any
    if(joblist.CurrentQueue!=null)
    {
      if(joblist.CurrentQueue!=Blocked) ReadyCount--;
      joblist.CurrentQueue.Remove(joblist);
    }

    // Select new queue
    joblist.CurrentQueue = joblist.Ready ? Ready[joblist.WorkerCount] : Blocked;

    // Add to new queue
    joblist.CurrentQueue.Add(joblist);
    if(joblist.CurrentQueue!=Blocked)
      if(++ReadyCount==1) NotifyBlockedCores();
  }
}

Dowork является нормальной работой планировщика, за исключением случаев: 1. Это выбирает Joblist с наименьшим количеством работников, 2. Работает рабочие места от Данный срок, пока он не может больше не может, и 3. Он хранит Jobindex, а также работу, поэтому Joblist может легко обновить состояние завершения (деталь реализации).

void Scheduler.DoWork()
{
  while(!Exit)
  {
    // Get a job list to work on
    JobList *list = null;
    lock(this)
    {
      for(int i=0; i<Ready.Length; i++)
        if(!Ready[i].Empty)
        {
          list = Ready[i].First;
          break;
        }
      if(list==null)  // No work to do
      {
        WaitForNotifyBlockedCores();
        continue;
      }
      list.WorkerCount++;
      UpdateQueues(list);
    }

    // Execute jobs in the list as long as possible
    while(true)
    {
      int jobIndex;
      Job job;
      if(!GetNextReadyJob(&job, &jobIndex)) break;

      job.Execute();

      list.MarkJobCompleted(job, jobIndex);
    }

    // Release the job list
    lock(this)
    {
      list.WorkerCount--;
      UpdateQueues(list);
    }
  }
}

Драйверная реализация

Дрогатор отслеживает, как сигнал / ожидания перемежаются с заданиями и отслеживают, какие пары сигнала / ожидания уже завершили все до их сигнала.

Конструктор создает пункт фиктивного сигнала, чтобы добавить задания. Эта точка сигнала становится реальной сигнальной точкой (и добавляется новый манекен) всякий раз, когда добавляется новый «сигнал».

JobList.JobList()
{
  // Always have a dummy signal point at the end
  Signals.Add(CurrentSignal = new SignalPoint());
}

AddJob добавляет задание в список. Это помечено как неполное на точке сигнализации. Когда работа на самом деле выполняется, неполноцентом одинаковой сигнализации уменьшается. Также необходимо сказать планировцу, что может быть изменено, поскольку новая работа может быть немедленно исполняемой. Обратите внимание, что планировщик вызывается после того, как блокировка на «это» выпущено, чтобы избежать тупика.

void JobList.AddJob(Job job)
{
  lock(this)
  {
    Jobs.Add(job);
    Signals.Last.IncompleteCount++;
    if(NextJob == null)
      NextJob = job;
  }
  if(Scheduler!=null)
    Scheduler.UpdateQueues(this);
}

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

void JobList.AddSignal()
{
  lock(this)
  {
    Signals.Last.SignalJobIndex = Jobs.Count;  // Reify dummy signal point
    Signals.Add(new SignalPoint());            // Create new dummy signal point
  }
}


void JobList.AddWait()
{
  lock(this)
  {
    Signals.Last.Previous.WaitJobIndex = Jobs.Count;
  }
}

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

bool JobList.Ready
{
  get
  {
    lock(this)
    {
      return NextJob!=null &&
        (CurrentSignal==Signals.Last ||
         NextJobIndex < CurrentSignal.WaitJobIndex);
    }
  }
}

getnextreadyjob очень прост: если мы будем готовы, просто верните следующую работу в списке.

void JobList.GetNextReadyJob(Job& job, int& jobIndex)
{
  lock(this)
  {
    if(!Ready) return false;
    jobIndex = list.NextJobIndex++;
    job = list.NextJob; list.NextJob = job.Next;
    return true;

  }
}

MarkJobCompleted, вероятно, самый интересный из всех. Из-за структуры сигналов и ожидания текущая задача представляет собой либо перед CurrentGignal, либо между CurrentSignal и CurrentGignal.Next (если оно после последнего фактического сигнала, он будет учитываться как между CurrentSignal и фиктивной точкой в ​​конце ). Нам нужно уменьшить количество неполных рабочих мест. Мы также можем понадобиться перейти к следующему сигналу, если этот счет идет до нуля. Конечно, мы никогда не проходим фиктивную сигнальную точку в конце.

Обратите внимание, что этот код не имеет звонка для планирования .updateQueue, потому что мы знаем, что планировщик будет вызывать GetNextreadyJob всего за секунду, и если он возвращает FALSE, он будет позвонить в любом случае.

void JobList.MarkJobCompleted(Job job, int jobIndex)
{
  lock(this)
  {
    if(jobIndex >= CurrentSignal.SignalJobIndex)
      CurrentSignal.Next.IncompleteCount--;
    else
    {
      CurrentSignal.IncompleteCount--;
      if(CurrentSignal.IncompleteCount==0)
        if(CurrentSignal.WaitJobIndex < int.MaxValue)
          CurrentSignal = CurrentSignal.Next;
    }
  }
}

Настройка на основе длины списка, оценки длины рабочих мест и т. Д.

Код выше не уделяет никакого внимания к тому, как длились списки рабочих мест,Поэтому, если есть сто крошечных списков рабочих мест и один огромный один, можно принимать отдельный крошечный список работы, а затем все собираются на огромное, что привело к неэффективности. Это можно решить, сделав готовый [] массив очередей приоритетов, приоритетных на (Joblist.jobs.Count - Joblist.nextjobindex) , но при приоритете фактически обновляется только в обычных ситуациях обновления для эффективности.

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

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

Окончательные заметки

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

1. Это сумасшедшая смесь синтаксиса C ++ и C #. Я первоначально начал писать в C #, затем изменил кучу синтаксиса в стиль C ++, поскольку я подумал, что это было более вероятным, что вы будете использовать для такого проекта. Но я оставил в довольно нескольких C # мозмах. К счастью, нет LINQ ;-).

2. Детали LinkedList имеют размахивание рук. Я предполагаю, что список может сделать первое, последнее, добавить и удалять, и что элементы в списке могут делать предыдущие и дальше. Но я не использовал фактическую API для любого настоящего класса связанного списка, о котором я знаю.

3. Я не скомпилировался и не проверил. Я гарантирую, что там есть ошибка или два.

Нижняя строка: Вам следует обрабатывать код выше как псевдокод, даже если он выглядит как настоящая Маккой.

Наслаждайтесь!