⏰ Пример у реалном времену
Тешко је објаснити шта је то “програмирање у реалном времену” и како га извести. Уместо објашњавања, даћемо пример обичног кода и како да се исти “претвори” у код за рад у реалном времену. Како ћемо да видимо, не, није довољно просто избегавати динамичко заузимање меморије - штавише, то није неопходно.
Шта је то реално време?
Постоји неколико мање-више популарних дефиниција. Ниједна није баш сјајна, искрено говорећи. Чак и је сам назив проблематичан. Наиме, ако је неко пргорамирање у “реалном времен”, какво је друго? У “нереалном времену”? Управо, много правилније је рећи “програми за рад у реалном времену”, али, сем што је напорно за изговорити, има исти проблем - за шта су други програми, за рад у “нереалном времену”?
Укратко, програм за рад у реалном времену се бави неким стварним догађајима (који би се десили и да програма нема) и мора да произведе резултат (одговор) у неком дефинисаном времену (најкасније). При томе, и протек времена је “стварни догађај”.
Узмимо за пример управљање лифтом. Одговарајућа програмска подршка обрађује притисак разних дугмета као и отварање/затварање врата, при чему мора да заустави лифт на време да не би промашили спрат.
Шта је толико посебно у програмима за рад у реалном времену?
Прво, очигледно нам треба скраћеница! :) Нека буде ПЗУРВ.
Сем тога:
- ПЗУРВ не сме да се “спуца” или на неки други начин прекине да извршава своје основне функције (дакле, свирање музике у лифту још и може да се прекине, али управљање пократњем и заустављањем лифта не сме)
- Перформансе, пре свега брзина, не смеју да, услед било ког утицаја, падну испод задатих граница.
- Углавном ради стално, без престанка, осим у току одржавања (које не сме да траје предуго)
- Обично се такође ради о “угњежденом” програму, односно, са ограниченим ресурсима (меморија, процеорска моћ…)
- Често не постоје “резерве”, а када их има, преузима функција од стране “резервног” процесора не утиче на постављене границе исправног рада. Наравно, постоје посебни случајеви када су неке границе “мало лабавије”, али су ретки и углавном “не помажу много” - рецимо, пошто већина људи спава око 04:00, онда је то пригодно време да се пређе на резервни процесор док се главни ажурира. Наша драга комшиница која се у то доба враћа са журке сасвим може да сачека који минут пре него што јој лифт по позиву дође (или, још боље, почне да доноси боље одлуке о свом животу).
Како се ово разликује од “Веб опслуживача”?
Иако има сличности (јер се углавном извршавају “стално”), на Вебу је главно питање обраде велике количине података. Наравно, што брже то боље, али, пре свега да се ништа не спуца, али, ако касни или пријављује неке (чудне) грешке, то “може да прође”. Такође, обично има много резерве, тако да откази нису озбиљан проблем.
Рецимо, Фејсбук врши унапређења тако што нову верзију пусти на неком подскупу свих опслуживача. Како их има на хиљаде, сасвим је мало приметно да пусти нову верзију на пар стотина. Онда се прати да ли исти пријављују неке грешке или се можда и “спуцавају”. Ако се примети икакав проблем (што је чест случај), на тих пар стотина се врати стара верзија и бубе отклањају. Ово се ради скоро сваки дан, а опет, већина људи није доживела икакав проблем у раду се Фејсбуком због тога. Очигледно, овако нешто није могуће у лифту.
Како се пише ПЗУРВ?
Да почнемо са нашим примерон. Узећемо “обично” парче кода, Ц функцију за брисање директоријума, која није “у реалном времену” и превести је у реално време.
Брисање директоријума у нереалном времену
Претпоставимо да је брисање директоријума функција која мора да се дешава у реалном времену. Очигледно, то неће бити случај у лифут, али, лифт није једини систем у реалном времену, већ само онај који волимо да злоупотребљавамо, јер је већина читалаца бар једном била у непријатној ситуацији у неком лифту.
Ево “нереалног” кода, који користи ПОСИЏ АПИ за рад са директоријумима (већина кода је писана у Ц-у, тако да је ово врло добар избор):
int delete_dir(char const* dirname)
{
int rslt = -1;
DIR* dir = opendir(dirstack);
if (NULL == dir) {
return -1;
}
do {
char f[MAX_PATH + 1];
struct stat statbuf;
struct dirent* entry = readdir(dir);
if (NULL == entry) {
break;
}
if (!strcmp(entry->d_name, ".")
|| !strcmp(entry->d_name, "..")) {
continue;
}
snprintf(
f, sizeof f, "%s/%s", dirname, entry->d_name);
rslt = stat(f, &statbuf);
if (0 == rslt) {
if (S_ISDIR(statbuf.st_mode)) {
rslt = delete_dir(f);
}
else {
rslt = remove(f);
}
}
} while (0 == rslt);
closedir(dir);
remove(dirname);
return rslt;
}
Овде се грешка баш и не обрађују, код би био нешто дужи, али, хтели смо да се види “главна ствар”, а да се не изгубимо у детаљима.
Овде је занимљиво што смо корстили (аутоматско) заузимање меморије са
стека за f (име датотеке) уместо динамичког заузимаа (malloc()), што
је једна од првих асоцијација кад се помене ПЗУРВ. Довољно је занимљиав
да заслужује кратак осврт.
Динамичко заузимање меморије и ПЗУРВ
Можда сте чули да “у ПЗУРВ динамичко заузимање меморије није дозвољено”. То је мање-више тачно, али, зависи од вашег “заузимача меморије” и за шта се иста користи.
Постоје заузимачи меморије који су употреби у ПЗУРВ. Рецимо, “стек заузима” је управо такав. Такође, неки напреднији “битмап” заузимачи су такође употребљиви (имају горњу границу времена извршавања).
Ако употребљавате такве заузимаче и ако постоји исправан начин рада за случај да заузимач не успе да заузме меморију, онда је све у реду.
Дакле, ако за свирање у лифту у неком тренутку не успете да заузмете меморију и због тога музика мало “кврцне”, то је у реду. Али, за потребе података на основу којих се управља кретањем лифта, динамичко заузимање меморије није дозвољено.
Хајмо редом - избацивање рекурзије
Слично као и динамичко заузимање меморије, ни рекурзија (функција) није потпуно забрањена. Забрањена је само неограничена рекурзија. Дакле, ако може да се докаже да рекурзија никада неће бити дубља од Н нивоа и да имате довољно меморије (у сваком случају) за дотичних Н нивоа, онда је све у реду.
Рецимо, ако правите неку врсту “крос-бар” повезивања, ниво рекурзије је ограничен бројем “шипки” који можете да повежете, јер, једном када се спојите на једну шипку, нема смисла да то урадите поново. Дакле, алгоритам који рекурзивно тражи начин да споји две тачке путем крос-бар система је прихватљив, под условом да је количина меморије која се заузме за сваки ниво рекрузије довољно мала да се стек за рекурзију не “истроши”.
Ипак, посебно у данашње време, стабло директоријума може да буде
веома дубоко, па, иако постоји неко Н, оно је толико велико
да сигурно немамо толико меморије на располагању.
Дакле, у нашем случају, морамо да избацимо рекурзију.
Основна идеја избацивања рекрузије се састоји у томе да “будемо сами свој рекурзивни стек”. Онда можемо да водимо рачуна о томе колико се меморије троши на исти. У нашем случају, ради се о стеку (под-)директоријума за брисање.
Начелно, користили би листу или низ за дотични стек. Листа би узимала чланове из неког базена (који је низ). У оба случаја, морали би да знамо који је максимално прихватљив ниво дубине стека (у нашем случају, стабла директоријума). У неким случајевима, то је познато (као у случају “крос-бар” повезивња). У нашем случају, практично, није познато, јер је основни смисао да се диреторијуми могу да “надовезују”.
Али, може да се примети да овај “стек директоријума” има познат
начин приказа - dir/subdir/subdir..... Дакле, уместо да чувамо
стек стрингова може да чувамо само један стринг. Почевши од:
dir
онда имамо:
dir/subdir
па:
dir/subdir/subdir
а када се обрада тога заврши, враћамо се на:
dir/subdir
што практично занчи да само додајемо и избацујемо “најновији” директоријум на крај стринга, одржавајући стек директоријума у самом стрингу.
Овде може да се примети да, на већини система, постоји неко разумно
ограничење броја знакова у путањи до датотеке. Свакако, махом смо сви
у неком тренутку псовали неки програм који не може да се избори са путањом
дужом од 260 знакова, а које често настају при радом са резервним копијама.
Али, тако нешто се јако ретко дешава у ПЗУРВ, посебно ако је то путања
коју корисник уноси. Посебно, у нашем “нереалном коду”, већ се користи
MAX_PATH .
Дакле, можемо овако да прекодирамо:
int delete_dir(char const* dirname)
{
char dirstack[MAX_PATH + 1];
int rslt = 0;
snprintf(dirstack, sizeof dirstack, "%s", dirname);
while ((0 == rslt) && (dirstack[0] != '\0')) {
bool pushed = false;
DIR* dir = opendir(dirstack);
if (NULL == dir) {
rslt = -1;
break;
}
do {
char f[MAX_PATH + 1];
struct stat statbuf;
struct dirent* entry = readdir(dir);
if (NULL == entry) {
break;
}
if (!strcmp(entry->d_name, ".")
|| !strcmp(entry->d_name, "..")) {
continue;
}
snprintf(f,
sizeof f,
"%s/%s",
dirstack,
entry->d_name);
rslt = stat(f, &statbuf);
if (0 == rslt) {
if (S_ISDIR(statbuf.st_mode)) {
strcpy(dirstack, f);
pushed = true;
break;
}
else {
rslt = remove(f);
}
}
} while (0 == rslt);
closedir(dir);
if (!pushed && (rslt == 0)) {
rslt = remove(dirstack);
pop(dirstack);
}
}
return rslt;
}
Ако нисте приметили, направили смо помоћну функцију:
static void pop(char* dirstack)
{
char* s = strrchr(dirstack, '/');
if (s != NULL) {
*s = '\0';
}
else {
*dirstack = '\0';
}
}
Овај код је значајно сложенији и тежи за разумевање од “редовног” кода.
Али, решили смо проблем рекурзије и не користимо динамичко заузимање
меморије. Наравно, opendir() можда динамички заузима меморију, али
претпоставимо да се ради у неком ПОСИЏу за рад у реалном времену.
Нажалост, то није све.
Стан’ Станимире!
Није проблем само у ограниченој меморији. Проблем је и у ограниченом времену извршавања, пре свега више ствари одједном.
Тако, у лифту, музика свира за време док се мери позиција и брзина и смер кретања лифта и задаје брзине и смер мотора који лифт покрећу и примењују кочнице. Све се то ради “у исто време”. Наравно, један процесор не може то заиста све да ради у исто време, него ради “мало једно, мало друго”. Већина ствари може да се обради “у целости” у тренутку када је то потребно. Али, неко брисање дубоког стабла директоријума може да потраје толико дуго да није могуће урадити га “у цугу”.
Стога морамо да одрадимо још једну уобичајену ствар у ПЗУРВ: “растави дуге обраде”. Одредимо неко време колико радимо, застанемо кад оно истекне, да би касније наставили где смо стали, тако све док коначно не завршимо цео посао.
Наравно, ово само у случају да ова обрада може да траје толико дуго а да то није проблем. Још једном, тако нешто не можемо да учинимо за обраду која одређује када да се на лифту примене кочнице.
Ово подразумева чување стања “где смо стали”, обично у виду неког Аутомата с Коначним Бројем Стања. У нашем случају, можемо то да избегнемо. Наиме, систем датотека већ чува стање какво нам одговара!
Колико времена можемо да одвојимо зависи од конкретног уређаја/система, па за сврхе примера, прихватимо то као параметар:
int delete_dir(char const* dirname, int ms_limit)
{
char dirstack[MAX_PATH + 1];
struct timespec tend;
int rslt = clock_gettime(CLOCK_MONOTONIC, &tend);
if (0 == rslt) {
tend.tv_nsec =
(tend.tv_nsec + ms_limit * NANO_IN_MILLI)
% NANO_IN_UNIT;
tend.tv_sec +=
(tend.tv_nsec + ms_limit * NANO_IN_MILLI)
/ NANO_IN_UNIT;
}
snprintf(dirstack, sizeof dirstack, "%s", dirname);
while ((0 == rslt) && (dirstack[0] != '\0')) {
bool pushed = false;
DIR* dir = opendir(dirstack);
if (NULL == dir) {
rslt = -1;
break;
}
do {
char f[MAX_PATH + 1];
struct stat statbuf;
struct dirent* entry;
if (are_we_there_yet(&tend)) {
rslt = +1;
break;
}
entry = readdir(dir);
if (NULL == entry) {
break;
}
if (!strcmp(entry->d_name, ".")
|| !strcmp(entry->d_name, "..")) {
continue;
}
snprintf(f,
sizeof f,
"%s/%s",
dirstack,
entry->d_name);
rslt = stat(f, &statbuf);
if (0 == rslt) {
if (S_ISDIR(statbuf.st_mode)) {
strcpy(dirstack, f);
pushed = true;
break;
}
else {
rslt = remove(f);
}
}
} while (0 == rslt);
closedir(dir);
if (!pushed && (rslt == 0)) {
rslt = remove(dirstack);
pop(dirstack);
}
}
return rslt;
}
Добили смо још једну помоћну функцију:
static bool are_we_there_yet(struct timespec* there)
{
struct timespec t;
int rslt = clock_gettime(CLOCK_MONOTONIC, &t);
if (rslt != 0) {
return true;
}
return (t.tv_sec > there->tv_sec)
|| ((t.tv_sec == there->tv_sec)
&& (t.tv_nsec > there->tv_nsec));
}
и неколико константи:
#define NANO_IN_MILLI (1000*1000)
#define MILLI_IN_UNIT 1000
#define NANO_IN_UNIT (NANO_IN_MILLI * MILLI_IN_UNIT)
Користимо clock_gettime(CLOCK_MONOTONIC,...) за праћење протока
времена, чисто да би “остали у оквиру ПОСИЏ”. За дати случај, користила
би се можда нека друга функција.
Ово је свакако још сложеније него што је било и још теже за употребу. Имамо додатни параметар који некако треба одредити, и морамо да обрађујемо да функција може да врати “није готово, зовиме ме поново касније”.
Чек, а шта са нитима/задацима?
Кад се помиње ПЗУРВ, често се помисли на Оперативни Систем за Рад у Реалном Времену (ОСЗУРВ), односно RTOS на енглеском. Са ОСЗУРВ-ом, могли би просто да пустимо брисање директоријума у засебну нит или задатак и пустимо ОСЗУРВ да се петља са тим, зар не?
Ствари нису баш тако једноставне. Прво, многи ПЗУРВ немају ОСЗУРВ, или исти “није довољно добар”.
Много важније, употреба нити/задатака практично подразумева неку “сарадњу” између истих, што често доводи до употребе брава. Браве лако доводе до “загрљаја смрти” или замене приоритета и сличних “дивних ствари”. Позната је прича о Марс Патфајндер Лендер програму који се спуцао на површини Марса управо из тих разлога (прича каже да је буба удаљено исправљена и да је сонда неко време радила на Марсу) - узгред, ово не треба бркати саа Марс Полар Лендер сондом која се физички слупала, из непознатих разлога.
Чак иако избегнемо браве, морамо да користимо некакве “атомске променљиве”, које, уз непажљиву потребу често доводе до значајног пада перформанси, отежавају разумевања “најгорег случаја”, као и уопште исправности алгоритама.
Стога, “трпање дугачких обрада у нити” није уобичајени приступ у ПЗУРВ. Управо, углавном се користе да апстрахују прекиде и учине да управљање истим буде јасније (прекиди за временске контроле, промене стања улаза/излаза и слично).
Наравно, то што није уобичајен, не значи да је забрањен и управо у неком случају може да буде сасвим прикладно да се брисање директоријума ради “линеарно” у некој нити, олакшавајући посао програмеру.
Наравоученије
Програми за рад у реалном времену се теже развијају просто зато што је потребно водити рачуна о више ствари него код развоја “обичних” програма, чак и оних који су “мање обични од других”, попут Веб/Интернет опслуживача.
Али, лепо је што често може да се пође од “обичног кода”, па онда са мање-више познатим “трансформацијама”, систематски, дође до “реално временског кода”. Чак иако коначни код не личи на почетни, бар начин стизања до истог не мора да буде “црна магија”.