вторник, 15 мая 2012 г.

Часть 3. Гонки и тупики

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

Для начала, давайте разберемся вот с какой вещью. Если мы напишем программу с одним потоком, вычислений в этом потоке будет много, они будут требовать всех ресурсов 1 из процессоров/ядер, то в операционной системе Windows эта задача будет выполняться на одном процессоре или не нескольких? Как вы считаете? На самом деле, несмотря на то. Что поток будет один, процессорное время будет браться с разных ядер. Это связано с тем, что Windows операционная система с разделением времени. Помните, мы обсуждали кванты? Так вот, эти кванты нашему потоку будут даваться в общей очереди всех процессов. Но если остальные будут от своего времени отказываться, о наш, тестовый процесс, будет использовать его на 100%. Только эти 100% будут скакать я процессора на процессор. Для демонстрации этого эффекта давайте возьмем вот такой тестовый пример:
class Program
{
    static void Main(string[] args)
    {
        int a = 0;
        for (int j = 0; j < int.MaxValue; j++)
        {
            for (int i = 0; i < int.MaxValue; i++)
            {
                a = a + 1;
            }
        }
           
    }
}
Выполняться он будет очень долго, вычисления нагружают процессор хорошо, но запустив этот пример, мы как и ожидалось, увидим не загрузку 1 процессора на 100%, а разных процессоров по очереди:
На этом рисунке очень хорошо видно, на каких ядрах давалось процессорное время. Кстати, видно и то, что операционная система старалась давать кванты последовательно на одном и том же процессоре, но если на нем квант получал другой процесс, то наш перекидывался.
Из-за такой «прерывистой» работы процессов и начинаются проблемы. Первой и наиболее часто встречающейся проблемой являются гонки. Чтобы понять что это такое, давайте рассмотрим вот такой пример:
class Program
{
    static int value = 0;

    static void Inc()
    {
        for (int i = 0; i < 1000000; i++)
        {
            value = value + 1;
        }
    }

    static void Dec()
    {
        for (int i = 0; i < 1000000; i++)
        {
            value = value - 1;
        }
    }

    static void Main(string[] args)
    {
        Thread inc = new Thread(new ThreadStart(Inc));
        Thread dec = new Thread(new ThreadStart(Dec));
        inc.Start();
        dec.Start();
        inc.Join();
        dec.Join();
        Console.WriteLine(value);
        Console.ReadKey();
    }
}
Как видим, ничего сложного. 1 переменная. Два метода: один миллион раз прибавляет к переменной 1, второй ровно столько же раз отнимает от переменной 1. Запустив программу, на консоли мы должны увидеть 0? Так? А вот и не так. Я запускал программу несколько раз, вот что она мне возвращала:
Почему же такое происходит. А это и есть гонки. Давайте попробуем посмотреть по шагам, как этакая ситуация возникает.
Допустим у нас в переменной храниться 0 (ноль). Первый поток, пытается выполнить команду:
value = value + 1;
Но это здесь кажется, что тут простое действие, на самом деле, процессор должен загрузить в регистр старое значение переменной value, потом к этому регистру прибавить константу 1, и только потом из регистра результат выгрузить в память. А что произойдет, если в регистр из памяти загрузка произошла, а вот добавить единицу и выгрузить, процессор не успел? У него отняли его квант времени? Давайте посмотрим вот  на такой схеме:

Т.е. у нас первый процесс копирует из памяти в регистр число 0, у него отнимают процессор (в связи с окончанием кванта) и передают его второму процессу. Второй процесс берет из памяти 0 (в памяти же у нас ничего не менялось) и отняв от него 1, получившееся значение -1 записывает в память. В это время, первый процесс получает управление назад. В его регистре храниться 0, он прибавляет к нему 1 и записывает в память 1. Т.е. добавив к нулю единицу и отняв единицу, в переменной мы получили 1. Вот такие «незапланированные» переключения и получили названия гонки.
Как же сказать операционной системе, что пока процесс выполняет операцию, в рамках которой нельзя прервать ее выполнение? Для этого есть достаточно большое количество механизмов. Мы, в следующей части их все обсудим, а пока я покажу только один способ: критические секции.
Для создания критической секции используется ключевое слово C#: lock. Оно используется по следующему синтаксису:
lock (<объектная переменная к которой привязана секция>)
{
<полезная работа >
}
Если есть два потока, первый зашел в критическую секцию, а второй только пытается зайти, то пока первый поток не закончит работу, второй будет заблокирован:

Давайте модифицируем предыдущий пример, применив критические секции:
class Program
{
    static int value = 0;

    // т.к. при приведении int к object работает упаковка,
    // для критической секции заведем отдельную переменную
    static object mySection = new object();

    static void Inc()
    {
        for (int i = 0; i < 1000000; i++)
        {
            lock (mySection)
            {
                value = value + 1;
            }
        }
    }

    static void Dec()
    {
        for (int i = 0; i < 1000000; i++)
        {
            lock (mySection)
            {
                value = value - 1;
            }
        }
    }

    static void Main(string[] args)
    {
        Thread inc = new Thread(new ThreadStart(Inc));
        Thread dec = new Thread(new ThreadStart(Dec));
        inc.Start();
        dec.Start();
        inc.Join();
        dec.Join();
        Console.WriteLine(value);
        Console.ReadKey();
    }
}
Как видно, изменений всего два: добавлена дополнительная переменная для идентификации критической секции и операции сложения/вычитания взяты в блок lock.
Теперь, сколько бы мы раз не запускали наше приложение, оно всегда будет выводить 0:

С гонками разобрались. Давайте перейдем к тупикам (взаимным блокировкам, «смертельным объятиям»). Для того, чтобы продемонстрировать в чем проблема, давайте у нас будет ни одна переменная а две. Каждый поток будет одну из них увеличивать, вторую уменьшать:
class Program
{
    static int valueA = 0;
    static int valueB = 0;
    static object mySectionA = new object();
    static object mySectionB = new object();
    static void Inc()
    {
        for (int i = 0; i < 1000000; i++)
        {
            lock (mySectionA)
            {
                valueA = valueA + 1;
                lock (mySectionB)
                {
                    valueB = valueB - 1;
                }
            }                
        }
    }

    static void Dec()
    {
        for (int i = 0; i < 1000000; i++)
        {
            lock (mySectionB)
            {
                valueB = valueB + 1;
                lock (mySectionA)
                {
                    valueA = valueA - 1;
                }
            }
               
        }
    }

    static void Main(string[] args)
    {
        Thread inc = new Thread(new ThreadStart(Inc));
        Thread dec = new Thread(new ThreadStart(Dec));
        inc.Start();
        dec.Start();
        inc.Join();
        dec.Join();
        Console.WriteLine(valueA);
        Console.WriteLine(valueB);     
        Console.ReadKey();
    }
}
Как видим, у нас просто добавилась еще одна критическая секция, и мы одну секцию поместили в другую.
Запустив приложение и ожидая увидеть два нуля, мы будем долго ждать, но на консоль так ничего и не выведеться.
Это происходит из-за тупиков. Смотрим на схему:

Как видим, процессы будут ждать до бесконечности. Как не допустить такого развития событий. Если у нас есть возможность блокировать секции по очереди, то этим и надо воспользоваться:
static void Inc()
{
    for (int i = 0; i < 1000000; i++)
    {
        lock (mySectionA)
        {
            valueA = valueA + 1;                   
        }
        lock (mySectionB)
        {
            valueB = valueB - 1;
        }
    }
}

static void Dec()
{
    for (int i = 0; i < 1000000; i++)
    {
        lock (mySectionB)
        {
            valueB = valueB + 1;                   
        }
        lock (mySectionA)
        {
            valueA = valueA - 1;
        }

    }
}
Если такой возможности нет, то надо секции во всех методах захватывать в одном и том же порядке:
static void Inc()
{
    for (int i = 0; i < 1000000; i++)
    {
        lock (mySectionA)
        {
            valueA = valueA + 1;
            lock (mySectionB)
            {
                valueB = valueB - 1;
            }
        }
    }
}

static void Dec()
{
    for (int i = 0; i < 1000000; i++)
    {
        lock (mySectionA)
        {
            valueB = valueB + 1;
            lock (mySectionB)
            {
                valueA = valueA - 1;
            }
        }

    }
}
Если с первым решением все понятно, то по второму схема:

Основная проблема гонок и тупиков, что в отличии от этих, специально разработанных примеров, они происходят в реальных программах время от времени. Запустили два потока – нормально, три – нормально, четыре – все упало. А в другой раз все упало уже на 2-х потоках. Или отработало 4 часа и все нормально.
Ладно, раз обещал, в следующий раз будем смотреть подробно объекты синхронизации.


Комментариев нет:

Отправить комментарий