Семафоры

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

Семафоры

Сообщение xdsl 09 окт 2011, 23:19

Есть у меня один студент, активно прогуливавший дисциплину "Параллельное программирование". Как результат - ничего не знает из теории и не ориентируется в практике. Зато работает у одного из наших городских провайдеров, немного понимает в C#, в веб-программировании, в ИТ под виндой. На основе всего этого считает, что достоин как минимум трояка по моему предмету. Вот только одна беда - лично я считаю, что даже трояк у меня должен быть заработан, а не поставлен за красивые глазки или некие сторонние достижения. Результат: на экзамене студент получает 2 за незнание предмета. На пересдаче получает 2 за незнание предмета. На комиссии получает 2 за незнание предмета. Заметьте - именно за незнание предмета. Т.е. человек сдает практически пустой листочек и молчит в ответ на вопросы. Ну, думаю, ладно, может он просто базовых положений сформулировать не может, а вот создать набор параллельно-функционирующих и взаимодействующих приложений сумеет. Правда, опыт показывает, что с решением задач, если они не элементарны, у студента тоже все плохо (две недели решал задание одной лабораторной работы). На самой распоследней пересдаче, после очередного пустого листочка в ответ на экзаменационный вопрос, дал ему задачу:

Дано число X. Создать две программы. Запущенные в произвольном кол-ве экземпляры первой программы циклически ожидают ввода строки, в которой подсчитывают кол-во единиц. Экземпляр второй программы ожидает, пока суммарное количество введенных единиц во всех экземплярах первой программы не достигнет или не превысит значения X. После чего сигнализирует об этом факте. Коммуникация программ друг с другом - только с помощью системных семафоров или событий. Во время работы пользовательский ввод программ не блокируется. Порядок запуска программ - произвольный.

Язык и ОС разрешил использовать любой. Студент выбрал C# и Windows. Отвел ему на решение одну пару. Не решил. Дал еще две пары. Не решил. Разрешил решать до конца дня. Не решил. Ну, думаю, ладно - детский сад штаны на лямках, отпущу до понедельника (дело было в пятницу), может ему кто поможет. Сегодня пришло в голову - может сложную задачку дал? Попробовал решить сам. Оказалось не сложно, но интересно. 15 минут на решение, 30 на отладку (подзабыл о персистентости именованных posix-семафоров). Вот что вышло:
Число X содержится в текстовом файле x.txt
Первая программа:
Подсветка синтаксиса: (sm1.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
{$mode objfpc}

uses libc;
var t:text; x:integer;
    s:string;
    curr_set:integer=0;
var sem:psem_t;

procedure am(cnt:integer);
 var value,res:longint;
begin
 sem_getvalue(sem,@value);
 writeln('Захватываем семафорчик в кол-ве ',cnt,' блокировок. На семафоре осталось ~ ',value);
 while cnt<>0 do begin
  res:=sem_trywait(sem);
  if res<>0 then begin
   sem_getvalue(sem,@value);
   writeln('Не срослось захватить все, конкуренты помешали.');
   writeln('Незахватилось ' ,cnt,' блокировок. На семафоре осталось ~ ',value);
   break;
  end;
  inc(curr_set);
  dec(cnt);
 end;
 sem_getvalue(sem,@value);
 writeln('Захватили семафорчик в кол-ве ',curr_set,' блокировок. На семафоре осталось ~ ',value);
end;

procedure tfu();
 var value:longint;
begin
 sem_getvalue(sem,@value);
 writeln('Отдаем блокировки в кол-ве ',curr_set,' блокировок. На семафоре сейчас ~ ',value);
 while curr_set<>0 do begin
  sem_post(sem);
  dec(curr_set);
 end;
 sem_getvalue(sem,@value);
 writeln('Отдали блокировки. На семафоре осталось ~ ',value);
end;

function cnt(s:string):integer;
  var i:integer;
 begin result:=0; for i:=1 to length(s) do if s[i]='1' then inc(result); end;

begin
 assign(t,'x.txt');reset(t);readln(t,x);close(t);
 sem:=sem_open('test',O_CREAT,511,x);
 while true do begin
  readln(s); if s='' then break;
  tfu();
  am(cnt(s));
 end;
 tfu();
 sem_close(sem);
 //sem_unlink('test');
end.
 

Вторая программа:
Подсветка синтаксиса: (sm2.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
{$mode objfpc}

uses cthreads,sysutils,libc,classes;

type
tsemthread=class(tthread)
 procedure execute; override;
end;

procedure tsemthread.execute;
var sem:psem_t;
    value:longint;
begin

 repeat
  if terminated then exit;
  sem:=sem_open('test',0,511,1);
  sleep(1);
 until sem<>nil;

 while true do begin
  if terminated then break;
  sem_getvalue(sem,@value);
  if value=0 then write('YES!!!!');
  sleep(1);
 end;
 sem_close(sem);
end;

var
    t:tsemthread;
    s:string;
begin
 t:=tsemthread.create(false);
 while true do begin
   readln(s); if s='' then break;  
   writeln(s);
 end;
 t.terminate;
 t.waitfor;
 t.destroy;
end.
 

В случае аварийного останова первой программы захваченный семафор не освобождается, что, естественно, скажется на корректности работы. В принципе, устойчивости к аварийным ситуациям от программы не требовалось, однако для подчистки "хвостов" можно использовать, например, следующую программу:
Подсветка синтаксиса: (smclear.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
{$mode objfpc}
uses libc;
begin
 sem_unlink('test');
end.
 

Другой вариант заключается в организации реакции на сигналы завершения, но было уже лень это делать, ибо сути программы обработка сигналов не изменит, да и спать уже хочется ;). Посмотрим, что мне завтра (т.е. уже сегодня) принесет студент. Подозреваю, что отговорки, но как знать...
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Семафоры

Сообщение xdsl 10 окт 2011, 08:10

Студент пришел, программы принес. Обнаружилось, что вторая программа по внешним признакам - в заблокированном состоянии (не отзывается на ввод). Указал студенту на эту проблему. Программу он разблокировал, но она перестала работать. Полчаса попыток исправить ситуацию к результату не привели. Отправил решать до конца рабочего дня. Принесет рабочую версию - поставлю положительную оценку и выложу его код здесь, для сравнения и анализа.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Семафоры

Сообщение xdsl 10 окт 2011, 23:25

Через два часа студент принес исправления. Вот этот код.
Первая программа:

Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка csharp
using System;
using System.Threading;

public class Program
{
    public static void Main()
    {
        int aCount = 0;
        Semaphore sem1 = new Semaphore(0, 3000, "Semaphore1");
        Semaphore sem2 = new Semaphore(0, 3000, "Semaphore2");

        bool sch = false;
        while (sch == false)
        {
            string str = Console.ReadLine();
            //Console.WriteLine(str);
            int Count = 0;
            if ((Int32)aCount != 0) sem2.Release((Int32)aCount);
            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] == '1')
                {
                    Count++;
                }
                aCount = Count;
            }
            if (Count > 0) sem1.Release(Count);
        }
    }
}


Вторая программа:

Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка csharp
using System;
using System.Threading;

public class Program2
{
    // static int t = 15;
    static int n = 10;
    static int Count = 0;

    static ManualResetEvent evnt = new ManualResetEvent(true);

    public static void Main()
    {
        Semaphore sem1 = new Semaphore(0, 0, "Semaphore1");
        Semaphore sem2 = new Semaphore(0, 0, "Semaphore2");

        Thread t1 = new Thread(new ParameterizedThreadStart(Worker1));
        t1.Start(sem1);

        Thread t2 = new Thread(new ParameterizedThreadStart(Worker2));
        t2.Start(sem2);

        Thread t3 = new Thread(new ParameterizedThreadStart(RL));
        t3.Start();
    }

    static void Output(object s)
    {
        evnt.WaitOne();
        evnt.Reset();
        Console.Clear();
        Console.WriteLine(s);
        evnt.Set();
    }

    private static void Worker1(object obj)
    {
        Semaphore sem = (Semaphore)obj;
        while (sem.WaitOne())
        {
            Interlocked.Increment(ref Count);
            if (Count >= n) Output(Count);
            else Output("waiting.....");
        }
    }

    private static void Worker2(object obj)
    {
        Semaphore sem = (Semaphore)obj;
        while (sem.WaitOne())
        {
            Interlocked.Decrement(ref Count);
            if (Count >= n) Output(Count);
            else Output("waiting.....");
        }
    }

    private static void RL(object obj)
    {
        while (1 == 1)
        {
            Console.ReadLine();
        }
    }
}
 


Сходу обратил внимание студента на строки
Semaphore sem1 = new Semaphore(0, 3000, "Semaphore1");
Semaphore sem2 = new Semaphore(0, 3000, "Semaphore2");
Константная верхняя граница мне сильно не понравилась - типичнейший студенческий костыль, источник эксплуатационных багов. Отправил переделывать на динамический вариант, отметая наивные предложения студента довести верхнюю границу до двух миллиардов...

День шел, студент решал, решал и ... ненарешал. В конце рабочего дня, после долгих раздумий, я понял, что надо либо ставить окончательную двойку и отправлять его на отчисление, либо зачесть работу в том виде, каком есть. Выбрал второй вариант, хотя, наверное, зря. Наверное, надо было дать студенту шанс перевестись на другую специальность или в другой вуз, где попроще.

Приглашаю всех желающих поискать баги в решениях задачи, а также предложить более эффективные решения.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.


Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0

cron