Страница 1 из 1

Вопрос по предмету СРВ lab3

СообщениеДобавлено: 23 фев 2010, 14:57
Gemini
Код: Выделить всё
Лабораторная работа №3.
Задание
Разработать планировщик периодических процессов по алгоритму RMS (см. лекции). На входе программы - файл input.txt следующей структуры:
рассчетное_время
название_процесса1 периодичность_запуска1 время_работы1
название_процесса2 периодичность_запуска2 время_работы2
...
название_процессаN периодичность_запускаN время_работыN
На выходе программы - файл output.txt следующей структуры:
Название_первого_запускаемого_процесса номер_периода время_запуска время_прерывания оставшееся_время_работы
Название_второго_запускаемого_процесса номер_периода время_запуска время_прерывания оставшееся_время_работы
...
Время прерывания последнего процесса должно быть равно рассчетному времени.
Если планирование по алгоритму RMS невозможно в принципе, файл output.txt должен содержать только фразу "Planning error".
Если планирование по алгоритму RMS завершилось неудачей, то файл должен содержать план работы процессов до неудачного момента и завершаться словом "Error".


Вопрос собственно по вот этому
Код: Выделить всё
Если планирование по алгоритму RMS завершилось неудачей, то файл должен содержать план работы процессов до неудачного момента и завершаться словом "Error"


Например в приведенной таблице - данные условия
Код: Выделить всё
110
a 30 15
b 40 15
c 50 5
должны прерываться таким образом
Код: Выделить всё
a 1 0 15 0
b 1 15 30 0
a 2 30 45 0
b 2 45 60 0
Error
- не могу понять, по какому признаку должна выводиться ошибка. Поясните пожалуйста.

Re: Вопрос по предмету СРВ lab3

СообщениеДобавлено: 23 фев 2010, 21:28
xdsl
Процесс С стартовать не смог в течении 50 единиц времени

Re: Вопрос по предмету СРВ lab3

СообщениеДобавлено: 24 фев 2010, 07:47
Gemini
дошло.

Re: Вопрос по предмету СРВ lab3

СообщениеДобавлено: 27 фев 2010, 08:06
Gemini
Еще вопрос - если процесс не закончил работу до начала своего следующего периода - это ошибка?

Впрочем.глупый вопрос.конечно,это ошибка.

Re: Вопрос по предмету СРВ lab3

СообщениеДобавлено: 21 дек 2010, 15:33
Rei
Не стал создавать новую тему, поскольку название для нее было бы идентичным названию этой темы :) тоже вопрос по предмету СРВ и тоже лабораторная работа 3 :)
Напомню:
Преамбула
В системах реального времени применяются разнообразные планировшики задач. Одним из первых был использован планировщих round robin, достоинством которого является детерминированность, а недостатком - небходимость специальной подготовки каждой задачи для выполнения работы с использованием данного планировщика. Для СРВ подготовка задачи заключается в возможности прерывания ее работы через четко определенные промежутки времени, возврат управления планировщику и возможность возобновления прерванной работы при последующем обращении.
Задание
1. Создать класс, предназначенный для сортировки массива детерминированным методом пузырька (см. пред. л.р.) и возможностью применения в СРВ при использовании планировщика round robin:

type
PArray=array[1..10000] of integer;
TSort=class
private
{внутренние поля}
public
constructor Create(PA:PArray; Count:integer); // PA - массив, который будет отсортирован Count - количество элементов в массиве
function Sort(time:longint):boolean;
// функция сортировки. Начинает или продолжает сортировку массива. Возвр. значение - true, если сортировка завершена, false - если время вышло
// time - максимальное время работы функции.
end;
Проверить работоспособность экземпляров класса.

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

Входные данные: 10 массивов (10 потоков), 10 000 элементов в каждом массиве, время прерывания сортировки: каждые 100 мс.
Массивы заполнены вещественными числами от 10 000 до 1 последовательно, сортируем методом пузырька. Фактически так мы должны получить максимальное время выполнения программы Tmax.
Код: Выделить всё
на компьютере с процессором AMD (ОС Windows XP):
Время выполнения задачи с прерываем:
  Tmax = 6127 мс
Результат задачи без прерывания:
  Tmax = 3258 мс

на компьютере с процессором Intel (ОС Windows XP):
Время выполнения задачи с прерываем:
  Tmax = 2289 мс
Результат задачи без прерывания:
  Tmax = 2292 мс

---------------------------------------------------------------------------
код функции сортировки:
...
function Tsrv.Sortirovka(ctime:double):boolean;
var i,j: integer;
     buf: real;
     tml: double;

begin
  Result:=False; i:=ic; j:=jc;  tml:=time;
  for i:=ic to n-1 do
   for j:=jc to n do
    begin
     if A[i]>A[j] then
      begin
       buf:=A[i];
       A[i]:=A[j];
       A[j]:=buf;
      end;

{начало проблемного кусочка кода}
     if (j mod 1000)=0 then              //каждые 1000 итераций внутреннего цикла проверяем
      if millisecondsbetween(tml,time)>=ctime then       //пора ли завершать работу
       begin
        ic:=i; jc:=j; exit;  //если пора то запоминаем где остановились и выходим из сортировки
       end;
{конец проблемного кусочка кода}

     jc:=i+2;
    end;

  ic:=i; jc:=j;
  if (ic=n)and(jc=n+1) then   //проверяем закончилась сортировка или нет.
   begin
    Result:=true; exit;
   end;
...

В итоге, что мы имеем.
В первом случае, с процессором AMD, эффективность сортировки упала на 100%. Во втором - с процессором Intel, все прекрасно.
Чем обусловлено такое поведение программы? И как же нам быть с такой бедой?
Прикрепил весь проект, на всякий случай. Тестировал первоначально у себя дома на Windows 7, процессор Intel и все оказалось замечательно. Протестировал в институте на Windows XP, процессор Intel - все прекрасно, пришел в 219 где стоят компьютеры с AMD и Windows XP - и снова увидел разницу во времени.
Для тестирование использовались два скомпилированный .exe файла.
1. с проблемным кусочком кода.
2. без такового (не закомментированным, при компиляции, а полностью удаленным из кода).

P.S.: Решение далеко не оптимальное, но все же почему такая разница во времени выполнения на AMD и почему ее нет на Intel?

Re: Вопрос по предмету СРВ lab3

СообщениеДобавлено: 22 дек 2010, 09:32
xdsl
А давайте с другого конца. Вы уверены, что у Вас все в порядке с алгоритмом сортировки? Ведь что такое пузырек - это когда первый раз производится пробег по всему массиву со "всплытием" максимального элемента на самый верх. Во второй раз - пробег по массиву без последнего элемента, который на предыдущей итерации уже стал максимальным, со "всплытием" максимального из оставшихся прямо под последний, гарантированно максимальный, элемент. Третий раз - пробег уже без двух последних элементов и т.д. Закончиться все это может и по причине отсутствия смены элементов во время пробега, и по банальному уменьшению счетчика обрабатываемых элементов массива до нуля. Заметьте, количество перебираемых элементов каждый раз уменьшается, но перебор всегда начинается с первого элемента. А что у Вас?

Re: Вопрос по предмету СРВ lab3

СообщениеДобавлено: 22 дек 2010, 13:15
Rei
Классический пузырек ставит максимальный элемент в конец массива, после первого пробега. У меня получается пузырек наоборот :lol: он ставит минимальный в начало. Почему наоборот? Мне так проще реализовать продолжение сортировки с места прерывания.

У меня первый проход начинается с i=1 и j=2 как и должно быть, т.к. первый элемент с самим собой сравнивать не имеет смысла. В результате этого прохода в начало массива "всплывает" минимальный элемент.
Второй пробег начинается с i=2 и j=3 потому как в результате первого пробега гарантированно в начало массива "всплыл" минимальный элемент массива.
В третий раз соответственно i=3 и j=4 и т.д.

Я выводил в файл все результаты чтобы убедиться в корректности работы сортировки, в проекте есть закомментированный код вывода в файл.
Еще я думаю что если бы из-за прерываний сортировки была проблема "лишних" пробегов то результаты выполнения на разных компьютерах одного и того же исполняемого файла дали бы приблизительно одинаковые результаты. Они бы показали что сортировка с прерываниями малоэффективна и разница во времени выполнения на компьютере с Intel была бы такой же, т.е. больше на 100% положенного в случае с прерыванием. Или все таки такие странные результаты могли быть?

Код: Выделить всё
...

constructor Tsrv.Create(_k,_id,_m:integer);
var i: integer;
    z: real;
begin
  inherited Create(true);
  k:=_k; id:=_id; m:=_m; ic:=1; jc:=ic+1;
  n:=StrToInt(Form1.Edit2.Text);
  case k of
  0: begin  {прямой порядок заполнения}
      z:=1; for i:=1 to n do begin A[i]:=z; z:=z+1; end;
     end;
  1: begin  {обратный порядок заполнения}
      z:=n; for i:=1 to n do begin A[i]:=z; z:=z-1; end;
     end;
  2: begin  {случайное заполнение}
      for i:=1 to n do begin z:=random(10000); A[i]:=z; end;
     end;
  end;
end;

...

procedure Tsrv.Execute;
var f:text; i:integer;
begin
  case m of
  0: begin
      tm[id]:=time;
      repeat until Sortirovka(tproc)=true;
      t[id]:=millisecondsbetween(tm[id],time);
      tms[id]:=t[id];
     end;

  1: begin
      tm[id]:=time;
      repeat until Sortirovka(tproc)=true;
      t[id]:=millisecondsbetween(tm[id],time);
      if t[id]<tmax then sleep(trunc(tmax-t[id]));
      tms[id]:=millisecondsbetween(tm[id],time);
     end;
  end;
end;

...

procedure TForm1.Button2Click(Sender: TObject);
var z,i,a:integer;
begin
randomize;
z:=StrToInt(Edit1.Text); // количество массивов
tproc:=StrToInt(Edit3.Text);  // время выполнения

for i:=0 to z-1 do
  begin
   thmax[i]:=Tsrv.Create(1,i,0);  // создаем нужное количество потоков с массивом заполненным в обратном порядке,
                  // 0 - значит без засыпания после окончания сортировки, чтобы приблизить время выполнения к Tmax.
   thmax[i].Resume;
  end;
for i:=0 to z-1 do thmax[i].WaitFor;
for Count:=0 to z-1 do
  if tmax<tms[Count] then tmax:=tms[Count];
Memo1.Lines.Add('Tmax: '+FloatToStr(tmax)); Memo1.Lines.Add(' ');
end;

Re: Вопрос по предмету СРВ lab3

СообщениеДобавлено: 23 дек 2010, 10:28
xdsl
Rei писал(а):Классический пузырек ставит максимальный элемент в конец массива, после первого пробега. У меня получается пузырек наоборот :lol: он ставит минимальный в начало. Почему наоборот? Мне так проще реализовать продолжение сортировки с места прерывания.

У меня первый проход начинается с i=1 и j=2 как и должно быть, т.к. первый элемент с самим собой сравнивать не имеет смысла. В результате этого прохода в начало массива "всплывает" минимальный элемент.
Второй пробег начинается с i=2 и j=3 потому как в результате первого пробега гарантированно в начало массива "всплыл" минимальный элемент массива.
В третий раз соответственно i=3 и j=4 и т.д.

Посмотрел еще раз на Ваш алгоритм, теперь вижу, что это не классический "пузырек", а авторский "камушек" ;).
Тем не менее, предлагаю завести счетчик, который увеличивать на 1 непосредственно перед if A[i]>A[j] then ... Полученные значения сравнить. Т.е. на сортировку без прерываний и сортировку с прерываниями. Если эти два счетчика окажутся различными, будет ясно, что алгоритм с прерываниями не эквивалентен алгоритму без прерываний. Меня не оставляют подозрения, что именно в алгоритме проблема. Буду рад, если окажусь неправ.

Re: Вопрос по предмету СРВ lab3

СообщениеДобавлено: 23 дек 2010, 12:44
Rei
xdsl писал(а):Посмотрел еще раз на Ваш алгоритм, теперь вижу, что это не классический "пузырек", а авторский "камушек" ;).
Тем не менее, предлагаю завести счетчик, который увеличивать на 1 непосредственно перед if A[i]>A[j] then ... Полученные значения сравнить. Т.е. на сортировку без прерываний и сортировку с прерываниями. Если эти два счетчика окажутся различными, будет ясно, что алгоритм с прерываниями не эквивалентен алгоритму без прерываний. Меня не оставляют подозрения, что именно в алгоритме проблема. Буду рад, если окажусь неправ.


Сделал счетчик, изменил входные данные немного. Запускал на домашнем компьютере. Процессор Intel время будет в пределах должного.
Код: Выделить всё
Входные данные: кол-во элементов: 10000; Поток: 1; Время прерывания: 100 мс.

С прерыванием:
Tmax: 470;  Counter: 49995004
Без прерывания:
Tmax: 446;  Counter: 49995000
--------------------------------------
Входные данные: кол-во элементов: 15000; Поток: 1; Время прерывания: 100 мс.

С прерыванием:
Tmax: 976;  Counter: 112492510
Без прерывания
Tmax: 983;  Counter: 112492500
--------------------------------------
Входные данные: кол-во элементов: 10000; Поток: 1; Время прерывания: 300 мс.

С прерыванием:
Tmax: 473;  Counter: 49995001
Без прерывания:
Tmax: 437;  Counter: 49995000

Как я уже и говорил решение не идеальное, где-то 4 лишних проверки проскакивает. Результаты стабильны при повторных запусках. Для большей уверенности запускал по 10 раз каждый вариант задачи.

Изменения в коде:
Код: Выделить всё
....
for i:=ic to n-1 do
   for j:=jc to n do
    begin
     count:=count+1; {счетчик в функции сортировки, count поле класса Tsrv типа integer, в конструкторе count:=0}
     if A[i]>A[j] then
      begin
       buf:=A[i];
       A[i]:=A[j];
       A[j]:=buf;
      end;

....

procedure Tsrv.Execute;
var f:text; i:integer;
begin
  case m of
  0: begin
      tm[id]:=time;
      repeat until Sortirovka(tproc)=true;
      t[id]:=millisecondsbetween(tm[id],time);
      tms[id]:=t[id];         
      CC:=count;    {Присваиваем значение счетчика count глобальной переменной CC}
     end;

...
{Вывод значения счетчика после вывода времени выполнения}
  Memo1.Lines.Add('Counter: '+IntToStr(CC));
...

P.S.: определенные проблемы конечно наблюдаются, но даже 40 или 100 лишних проверок займут время которое гораздо меньше времени погрешности ОС Windows, т.е. мы не должны наблюдать разницу во времени выполнения.