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

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

Модератор: xdsl

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

Сообщение Gemini 23 фев 2010, 14:57

Код: Выделить всё
Лабораторная работа №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
- не могу понять, по какому признаку должна выводиться ошибка. Поясните пожалуйста.
Не относитесь к этой жизни слишком серьезно,господа.Все равно вам из неё живым не выбраться.
Gemini
 
Сообщения: 90
Зарегистрирован: 13 янв 2009, 12:42
Откуда: Сейчас в Ша
Полное имя: Плешков Сергей Александрович

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

Сообщение xdsl 23 фев 2010, 21:28

Процесс С стартовать не смог в течении 50 единиц времени
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение Gemini 24 фев 2010, 07:47

дошло.
Не относитесь к этой жизни слишком серьезно,господа.Все равно вам из неё живым не выбраться.
Gemini
 
Сообщения: 90
Зарегистрирован: 13 янв 2009, 12:42
Откуда: Сейчас в Ша
Полное имя: Плешков Сергей Александрович

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

Сообщение Gemini 27 фев 2010, 08:06

Еще вопрос - если процесс не закончил работу до начала своего следующего периода - это ошибка?

Впрочем.глупый вопрос.конечно,это ошибка.
Не относитесь к этой жизни слишком серьезно,господа.Все равно вам из неё живым не выбраться.
Gemini
 
Сообщения: 90
Зарегистрирован: 13 янв 2009, 12:42
Откуда: Сейчас в Ша
Полное имя: Плешков Сергей Александрович

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

Сообщение Rei 21 дек 2010, 15:33

Не стал создавать новую тему, поскольку название для нее было бы идентичным названию этой темы :) тоже вопрос по предмету СРВ и тоже лабораторная работа 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?
Вложения
lab 3.zip
весь проект
(212.46 Кб) Скачиваний: 182
Демократия есть одурачивание народа при помощи народа ради блага народа. (Оскар Уайльд)
Аватара пользователя
Rei
Elite
 
Сообщения: 52
Зарегистрирован: 21 дек 2008, 20:45
Откуда: Шадринск
Полное имя: Кононцев Павел Викторович

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

Сообщение xdsl 22 дек 2010, 09:32

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

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

Сообщение Rei 22 дек 2010, 13:15

Классический пузырек ставит максимальный элемент в конец массива, после первого пробега. У меня получается пузырек наоборот :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;
Демократия есть одурачивание народа при помощи народа ради блага народа. (Оскар Уайльд)
Аватара пользователя
Rei
Elite
 
Сообщения: 52
Зарегистрирован: 21 дек 2008, 20:45
Откуда: Шадринск
Полное имя: Кононцев Павел Викторович

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

Сообщение xdsl 23 дек 2010, 10:28

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

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

Посмотрел еще раз на Ваш алгоритм, теперь вижу, что это не классический "пузырек", а авторский "камушек" ;).
Тем не менее, предлагаю завести счетчик, который увеличивать на 1 непосредственно перед if A[i]>A[j] then ... Полученные значения сравнить. Т.е. на сортировку без прерываний и сортировку с прерываниями. Если эти два счетчика окажутся различными, будет ясно, что алгоритм с прерываниями не эквивалентен алгоритму без прерываний. Меня не оставляют подозрения, что именно в алгоритме проблема. Буду рад, если окажусь неправ.
xdsl
 
Сообщения: 1228
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение Rei 23 дек 2010, 12:44

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, т.е. мы не должны наблюдать разницу во времени выполнения.
Демократия есть одурачивание народа при помощи народа ради блага народа. (Оскар Уайльд)
Аватара пользователя
Rei
Elite
 
Сообщения: 52
Зарегистрирован: 21 дек 2008, 20:45
Откуда: Шадринск
Полное имя: Кононцев Павел Викторович


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

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

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

cron