SI Wiki - Кориснички доприноси [sr]

ПРС/Формуле

2025-09-29T09:28:46Z

MihailoM342: Zamenjen redosled za otvorene mreze i interaktivne sisteme jer tim redom ide u materijalima

{{tocright}}

== Оперативна меморија ==
=== Основни појмови ===
* У реду за чекање увек има послова.
* <math>S</math>: величина посла за учитавање у меморију
* <math>t</math>: време задржавања програма у меморији
* <math>U</math>: искоришћење меморије
** <math>\overline{U} = \frac{\sum_{i = 0}^n t_i \cdot S_i}{\sum_{i = 0}^n t_i}</math>
* Модели величина послова:
** Модел једнаких величина: сви послови имају једнаке величине
** Модел једнаковероватних величина: имамо минималну и максималну величину посла, и иста је вероватноћа да се било која величина од њих појави
** Експоненцијална расподела величина: више има мањих послова или обрнуто
* Модели времена задржавања у меморији:
** Константно време задржавања
** Функција од величине програма
* Монопрограмски систем: само један програм је учитан у меморију
* Статичке партиције: у сваку партицију оперативне меморије може бити учитан један програм

=== Модел статичких партиција ===
* Величине веће и мање партиције означавамо са <math>x_b</math> и <math>x_s</math>.
* Нормализујемо по величини веће партиције: <math>x_b = 1</math>
* Мали програми могу да стану у мању партицију, велики не могу.
* Ознаке стања:
** <math>E</math>: празне партиције
** <math>BS</math>: програми учитани и у велику и у малу партицију
** <math>BE</math>: велики програм учитан у велику партицију
** <math>SE</math>: мали програм учитан у велику партицију
*** Ако је време задржавања у меморији константно, ово стање не постоји!
** <math>SS</math>: мали програми учитани у обе партиције
** <math>ES</math> није могуће стање!
* Искоришћење рачунамо на основу величине просечног програма.
* Статичке вероватноће стања: вероватноћа да се налазимо у неком стању
* Просечно искоришћење: <math>\overline{U} = \overline{U_{BS}} \cdot p_{BS} + U_{SS} \cdot p_{SS} + ...</math>
* Рекурентно време стања: <math>\frac{1}{1 - p}</math> где је <math>p</math> вероватноћа да се остаје у стању (извођење преко математичког очекивања и потенцијалног реда)

=== Кнутов модел ===
* Равнотежно стање: једнака вероватноћа алокације и деалокације меморије
* Четири сценарија ослобађања блока: HBH, HBB, BBH, BBB
** Број случајева HBB једнак је броју случајева BBH (један се налази на почетку секвенце блокова а други на крају)
** У HBH имамо две рупе, у HBB и BBH једну, па на основу тога можемо изразити укупан број рупа.
* Вероватноћа ''perfect fit'' тежи нули.
* Кнутов закон: број рупа тежи половини броја блокова.
* Однос величине рупа и блокова: <math>c = \frac{\overline{H}}{\overline{S}}</math>
** Мора бити <math>c < 1</math> јер је ред послова бесконачан.
* Искоришћење меморије: <math>U = \frac{2}{2 + c}</math>

=== Бетериџов модел ===
* Меморија подељена на <math>M</math> блокова, програми величине 1, 2, 3... блока, а релокација није дозвољена.
* Све величине програма су једнако вероватне, и при прелазима између стања је увек завршио тачно један програм.
* Могућа стања за систем са величином меморије 2: SS, B, SE, ES.
** Број стања расте експоненцијално са величином меморије.
* Модел статичких страница: програми више не морају да буду тачне величине у блоковима, постоји интерна фрагментација.
** Одбачени део меморије: <math>W = \frac{n_{avr}}{2}</math> блокова, где је <math>n_{avr}</math> просечан степен мултипрограмирања.

=== Виртуелна меморија ===
* <math>x</math>: величина једне странице
* <math>k</math>: величина улаза у PMT
* <math>N</math>: број страница
* <math>M_{PMT}</math>: количина меморије која оде на PMT
** <math>M_{PMT} = \frac{M}{x} \cdot k</math>
* Одбачени део меморије: <math>W = M_{PMT} + \frac{n_{avr} \cdot x}{2}</math>
* Оптимална величина странице: <math>x_{opt} = \sqrt{\frac{2Mk}{n_{avr}}}</math>
* <math>\frac{1}{R}</math>: вероватноћа да је последња страница програма у меморији
** Уколико је дата, онда <math>W = M_{PMT} + \frac{n_{avr} \cdot x}{2} \cdot \frac{1}{R}</math>

== Дискови ==
* <math>T</math>: време за пренос записа у меморију.
** <math>T = T_{am} + T_{rd} + T_{dt}</math>
** <math>T_{am} = \frac{1}{n_{c_1} n_{c_2}} \int_{c_1}^{c_1 + n_{c_1}} \int_{c_2}^{c_2 + n_{c_2}} t(z - x) dx dz</math>
*** <math>T_{am}</math>: ''access motion'' време
*** <math>n_{c_1}</math>: број цилиндара првог диска
*** <math>c_1</math>: први цилиндар првог диска
*** <math>t(z - x)</math>: колико диску треба времена да пређе од цилиндра <math>x</math> до цилиндра <math>z</math>
*** Уколико се иде са цилиндра једне датотеке на исту датотеку: <math>T_{am} = \frac{2}{n_c^2} \int_0^{n_c} (n_c - x) t(x) dx</math>
** <math>T_{rev} = \frac{1}{v_{rot}}</math>
*** <math>T_{rev}</math>: време обртања диска
*** <math>v_{rot}</math>: брзина обртања диска
** <math>T_{rd} = \frac{T_{rev}}{2}</math>
** <math>T_{dt} = c \cdot T_{rev}</math>
*** <math>T_{dt}</math>: ''data transfer'' време
*** <math>c</math>: који део стазе заузима један запис
*** Уколико се само врши приступ, а не и трансфер података, онда је <math>T_{dt} = 0</math>.

== Поасонов процес ==
=== Основни термини ===
* <math>\bar{s}</math> - Средње време обраде посла
** Понекад означено и као <math>s, S_p</math>
* <math>\bar{a}</math> - Средње време/Очекивано време између два пристизања послова
* <math>\mu</math> - Брзина/интензитет обраде посла
* <math>\lambda</math> - Брзина/интензитет пристизања послова
* <math>\lambda = \frac{1}{\bar{a}}</math>
* <math>\mu = \frac{1}{\bar{s}}</math>

=== Стања система ===
* Стања система обележавамо бројевима који уједно означавају колико има послова у систему.
* Број стања = Број процесора који могу да раде посао + Број места у реду за чекање
* Уколико је ред за чекање неограничен/бесконачан, постоји бесконачан број стања.
* Свако стање има статичку вероватноћу, ознака <math>p_i</math>, где је <math>i</math> број стања.
* <math>\sum_{i = 0}^n p_i = 1</math> - Једначина преклапања. Збир свих стања у систему мора бити 1.
* Статичке вероватноће одређују се из балансних једначина.
* У системима са бесконачним бројем стања (неограниченим редом за чекање) јављају се редови:
** <math>1 + \rho + \rho^2 + ... = \sum_{i = 0}^{\infty} \rho^i = \frac{1}{1 - \rho}</math> - Геометријски ред. Конвергира само ако <math>\rho < 1</math> и то је неопходно проверити - иначе ред дивергира и анализа није применљива.
** <math>1 + 2\rho + 3\rho^2 + ... = \sum_{i = 0}^{\infty} (i + 1)\rho^i = \frac{1}{\left(1 - \rho\right)^2}</math> - Потенцијални ред. Конвергира само ако <math>\rho < 1</math> и то је неопходно проверити - иначе ред дивергира и анализа није применљива.
* За непознат али коначан број стања јавља се и геометријски низ (који има коначан број чланова): <math>1 + \rho + \rho^2 + ... \rho^n = \sum_{i = 0}^{n} \rho^i = \frac{1 - \rho^{n+1}}{1 - \rho}</math>
** Пазити на случај где <math>\rho = 1</math>. Тада је вредност низа <math>n\rho</math>.

=== Карактеристике система ===
* <math>T</math> - Просечно/очекивано време обраде послова/време одзива у систему
* <math>T_q</math> - Просечно/очекивано време обраде послова/време одзива у реду за чекање
** Веза: <math>T = T_q + \bar{s}</math>
* <math>J</math> - Просечан/очекивани број послова у систему
** <math>J = \sum_{i = 0}^n ip_i</math> - где се <math>i</math> слаже са бројем послова у систему.
* <math>J_q</math> - Просечан/очекивани број послова у реду за чекање
** Важи иста формула као за J, само што се вероватноће множе са бројем послова у реду за чекање.
* <math>X</math> - Проток кроз систем
** Уједно и проток кроз ред за чекање
** Уколико је ред за чекање бесконачан нема одбијања послова, што значи да је проток исти као и интензитет пристизања послова. <math>X = \lambda</math>
** Иначе, проток је <math>X = (1 - p_{MAX})\lambda</math>, где је <math>p_{MAX}</math> последње стање у ком нема места у реду за чекање.
* <math>X' = p_{MAX}\lambda</math> - Проток одбијених послова
* <math>T = \frac{J}{X}</math> - Литлова формула. Важи за '''цео систем'''.
** Могуће је посматрати само ред за чекање и ту важи: <math>T_q = \frac{J_q}{X}</math>
** Веза: <math>T = T_q + \bar{s} \iff \frac{J}{X} = \frac{J_q}{X} + \bar{s} \iff J - J_q = \bar{s}X</math>
* <math>U = \sum_{i = 0}^n U_i p_i</math> - Искоришћеност система. Искоришћеност неког дела <math>U_i</math> се дефинише као број послова подељен са капацитетом.
** Важи <math>U = 1 - </math> неискоришћени део система.
== Циклични модел мултипрограмирања ==
* Проток кроз систем је свуда исти.
* Ово значи да време проведено у процесорском делу система и диск делу система има исти проток, па важи: <math>T_{CPU} = \frac{J_{CPU}}{X}</math>, <math>T_{disk} = \frac{J_{disk}}{X}</math>
* <math>J_{CPU} + J_{disk} = n</math>
* <math>R = T_{CPU} + T_{disk} = \frac{n}{X}</math> - ''Round trip time'' - време проласка једног посла кроз цео систем.
* Пошто је проток у целом систему исти, код гранања еквивалентних паралелних сервера важи:
** <math>X = nX_p = mX_d</math>, <math>n</math> број процесора, <math>m</math> број дискова.
* Закон искоришћења једног сервера/диска: <math>U_p = X_pS_p</math>
** Пошто је проток свуда исти: <math>\frac{U_p}{U_d} = \frac{X_pS_p}{X_dS_d}</math>

== Гордон-Њуелов метод ==
* Гордон-Њуелов метод дефинише <math>x_i</math> као потражњу сервера <math>i</math>. Овај фактор је релативан и обично се узима да је потражња првог сервера (процесора) <math>x_1 = 1</math>.
* ГЊ систем једначина се формира овако:
** Сваки систем има своју једначину, где са леве стране једнакости стоје <math>\mu_ix_i</math>, а са десне, за сваку грану која улази у систем (тј. његов ред за чекање) <math>p_i\mu_ix_i</math>.
** <math>p_i</math> је вероватноћа уласка у грану.
* <math>G(n)</math> - константа система која зависи од броја послова у систему. Најлакше се одређује Бјузеновим методом.
* <math>P[n_j(N) \geq k] = x_j^k \frac{G(N-k)}{G(N)}</math> - Вероватноћа да у неком систему има више од <math>k</math> процеса.
** <math>N</math> је укупан број послова у систему.
** <math>j</math> је редни број система.
** <math>x_j</math> је његов фактор потражње.
* <math>P[n_j(N) = k] = P[n_j(N) \geq k] - P[n_j(N) \geq k + 1] = x_j^k \frac{G(N-k)}{G(N)} - x_j^{k+1} \frac{G(N-k + 1)}{G(N)}</math> - Вероватноћа да систем има тачно <math>k</math> послова.
* <math>U_j = P[n_j(N) \geq 1] = x_j \frac{G(N-1)}{G(N)}</math> - Искоришћеност сервера
** Сервер који има највећу искоришћеност је '''уско грло'''.
* <math>J_i = x_i^1 \frac{G(N-1)}{G(N)} + x_i^2 \frac{G(N-2)}{G(N)} + x_i^3 \frac{G(N-3)}{G(N)} + ... + x_i^n \frac{G(0)}{G(N)} </math> - Просечан/очекивани број послова на серверу.
* <math>P_{j_1j_2j_3...j_n} = \frac{x_1^{j_1}x_2^{j_2} ... x_n^{j_n}}{G(N)}</math> - Вероватноћа да у систему са <math>n</math> сервера и <math>N</math> послова сваки појединачни сервер има <math>j_i</math> послова.

== Отворене мреже ==
* Џексонова теорема: можемо посматрати сервисне центре као да су независни М/М/1 сервери.
** Време одзива појединачног сервера добијамо као: <math> R_i = \frac{1}{\mu_i - X_i} </math> (примена Литлове формуле за М/М/1 систем)
** Вероватноће стања укупног система се добијају као производи појединачних стања система.
** За М/М/1 важи: <math>p_0 = 1 - \rho</math>, <math>p_i = \rho^i p_0</math>, <math>J = \frac{\rho}{1 - \rho}</math>
* Једначина отворене мреже са централним сервером: <math>1 = \frac{V_1}{V_0} + \frac{V_2}{V_0} + ... + \frac{V_k}{V_0} + \frac{1}{V_0}</math>
** Сабирци су редом једнаки: <math>p_1, p_2, ..., p_k, p_0</math>
** <math>V_0, V_1, ..., V_k</math>: просечан број посета сваком од сервисних центара (<math>V_0</math> је централни сервер, у задацима, узети да је <math>V_0 = 1</math>)

== Интерактивни системи ==
* <math>\overline{\theta}</math>: време размишљања (време током ког се корисник одлучује шта да упише на терминал)
* <math>\overline{w}</math>: време проведено у реду за чекање
* <math>\overline{r}</math>: време одзива процесора
** <math>\overline{r} = \overline{w} + \overline{s}</math>
* <math>T_c</math>: време циклуса на процесору
** <math>T_c = \overline{w} + \overline{s} + \overline{\theta} = \overline{r} + \overline{\theta}</math>
** Примењена Литлова формула: <math>T_c = \frac{n}{X}</math>
* <math>n^*</math>: критичан број терминала (колико максимално терминала можемо да имамо у систему тако да остане <math>\overline{w} = 0</math>)
** <math>n^* = \left\lfloor 1 + \frac{\overline{\theta}}{\overline{s}} \right\rfloor</math>
* Искоришћење у интерактивном систему (опет добијено из Литлове формуле): <math>U = \frac{n \overline{s}}{T_c}</math>
** За <math>\overline{w} = 0</math> важи <math>U(n) = \frac{n \cdot \overline{s}}{\overline{s} + \overline{\theta}}</math>
** За систем у засићењу важи: <math>1 = \frac{n \cdot \overline{s}}{\overline{r}(n) + \overline{\theta}}</math>
* Рекурентна формула за рачунање вероватноћа стања система ('''важи само за систем са једним процесором'''): <math>\frac{1}{p_0(n)} = 1 + n\rho \frac{1}{p_0(n-1)}</math>

== МВА анализа ==
* Улазни параметри:
** <math>n</math>: укупан број послова у систему
** <math>Z</math>: средње време размишљања терминала, ако систем није интерактиван онда је 0
** <math>S_j</math>: време опслуживања једног посла на сервисном центру <math>j</math>
** <math>V_j</math>: просечан број посета сервисном центру <math>j</math>
** <math>D_j</math>: потражња сервисног центра <math>j</math>
*** Користи се у другој варијанти алгоритма, и добија се као <math>S_j \cdot V_j</math>.
* Променљиве:
** <math>Q_j(n)</math>: број послова у сервисном центру <math>j</math>
** <math>r_j(n)</math>: задржавање у сервисном центру <math>j</math>
** <math>R(i)</math>: време задржавања посла у систему (време одзива)
** <math>R_j(i)</math>: време задржавања посла у сервисном центру <math>j</math>
** <math>X(i)</math>: проток кроз систем
** <math>X_j(i)</math>: проток кроз сервисни центар <math>j</math>
** <math>U_j(i)</math>: искоришћење сервисног центра <math>j</math>

[[Категорија:ПРС]]
[[Категорија:Водичи]]

Микропроцесорски системи/Јануар 2022

2025-08-26T19:56:38Z

MihailoM342: main.c i usart1

{{tocright}}
'''Јануарски рок 2022. године''' нема поставку доступну са странице предмета. Није много познато о овом року, осим задатка наведеног испод.

== Задатак ==
=== Поставка ===
[[Датотека:MIPS januar 2022 referentna šema.svg|thumb|Референтна шема у задатку.<ref>На датој шеми ''LCD'' дисплеј није повезан на исти начин као на вежбама - код је одговарајуће модификован да се овоме прилагоди. На правом испиту је шема највероватније била као што је рађено на вежбама.</ref>]]
# <del>У систему постоји један микроконтролер који контролише вентилатор у складу са тренутном вредношћу температуре. У симулатору ''Proteus'' направити пројекат и инстанцирати микроконтролер ''STM32F103R6'' (''CM3_STM32''). Направити пројекат у алату ''CubeMX'' који ће служити за конфигурисање микроконтролера.</del>
# <del>У симулатору ''Proteus'' додати следеће компоненте</del> <u>строго према датој референтној шеми</u>:
#* аналогни мултиплексер ''74HC4051'' (''74HC'') чији је излазни пин повезан на канал 7 аналогно-дигиталног конвертора микроконтролера; селекција излаза аналогног мултиплексера се врши преко његових пинова ''CBA'' где пин ''A'' има најмању тежину,
#* <del>температурни сензор ''LM35'' (''NATDAC'') чији је излазни пин повезан</del> на нулти улаз (''X0'') мултилексера <del>(аналогна вредност напона на излазном пину сензора је линеарно пропорционална вредности температуре односно ради добијања вредност температуре напон треба помножити са вредношћу 100),</del>
#* анемометар ''ANEMOMETER'' (''ACTIVE'') повезан у складу са референтном шемом на канале 1 и 2 тајмера 1;<ref>На референтној шеми са викија повезан је само на један канал, јер је само један канал и потребан.</ref> излазни сигнал анемометра је периодична правоугаона поворка чија се фреквенција линеарно повећава са повећањем брзине ветра (брзина ветра једнака је производу фреквенције излазног сигнала анемометра и реалне константе 2.4),
#* ветроказ ''WINDVANE'' (''ACTIVE'') чији је излазни пин повезан у складу са референтном шемом (обратити пажњу на постојање отпорника) на први улаз (''X1'') мултиплексера; аналогна вредност напона на излазном пину ветроказа представља азимут односно правац ветра (функција за пресликавање вредности напона у азимут дата је у прилогу),<ref>Овај прилог не постоји на викију, али можете ископирати функцију <code>adcToWindvane</code> из решења.</ref>
#* <del>виртуелни терминал повезан на периферију ''USART1'' микроконтролера</del> преко пинова ''PB6'' и ''PB7'',
#* ''LCD'' дисплеј ''LM041L'' (''DISPLAY'') са четири линије, којима редом одговарају почетне адресе <code>0x00</code>, <code>0x40</code>, <code>0x90</code> и <code>0xD0</code> у ''DDRAM'' меморији контролера ''HD44780'', <del>повезан на пинове ''PC0''-''PC6'' микроконтролера и</del>
#* црвена ''LED-RED'' (''ACTIVE'') повезана на ''PA13''.
# Обезбедити приказ поруке '''''Temper: <t>''''' у трећем реду ''LCD'' дисплеја, где ''<t>'' представља тренутну вредност температуре изражено у степенима Целзијуса у опсегу [0, 60] <u>очитану са температурног сензора</u>. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.
# Обезбедити приказ поруке '''''Azimut: <a>''''' у првом реду ''LCD'' дисплеја, где ''<a>'' представља тренутну вредност азимута ветра <u>очитану са ветроказа</u>. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.
# Обезбедити приказ поруке '''''Brzina: <b>''''' у другом реду ''LCD'' дисплеја, где ''<b>'' представља тренутну вредност брзине ветра <u>очитану са анемометра</u>. Освежавање поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности.
# Обезбедити треперење црвене ''LED'' са периодом од једне секунде (пола секунде светли, пола секунде не светли) уколико је брзина ветра једнака или већа од 50 километара на сат. Уколико је брзина ветра мања од 50 километара на сат црвена ''LED'' не светли.
# Обезбедити приказ порука '''''<a>/<b>/<t>''''' на виртуелном терминалу, где је ''<a>'' тренутна вредност азимута ветра, ''<b>'' тренутна вредност брзине ветра и ''<t>'' тренутна вредност температуре изражено у степенима Целзијуса у опсегу [0, 60]. За величине чије вредности нису успешно израчунате исписати ? (знак питања). Уколико је ипак за неку од ставки (3), (4) или (5) вредност успешно израчуната онда та вредност мора бити приказана на виртуелном терминалу да би за ставку (7) били признати поени. Освежавање описане поруке вршити периодично на сваких 200 милисекунди уколико је дошло до промене вредности. Приликом освежавања поруке променити тренутне вредности у постојећој поруци уместо додавања нове поруке на виртуелном терминалу.

=== Решење ===
Цело решење може се преузети [[Медиј:MIPS januar 2022 projekat.zip|одавде]]. Разлика решења у односу на поставку јесте што је редослед исписа на ''LCD'' дисплеју температура, азимут, брзина уместо азимут, брзина, температура.

Сви релевантни измењени фајлови са кодом налазе се у <code>cubemx/code/Core/Src</code> и <code>cubemx/code/Core/Inc</code> директоријумима.

==== ''CubeMX'' ====
У алату ''CubeMX'' направљене су следеће измене:
* Омогућени су прекиди од ADC, TIM1 и USART1.
* Као ''Timebase Source'' подешен је TIM2.
* Омогућен је IN7 улаз ADC1.
* У TIM1 је канал 1 подешен за ''Input Capture''.
* У USART1 је режим подешен на ''Asynchronous'', ''Baud Rate'' је 9600Bits/s.
* У ''FreeRTOS'' је интерфејс подешен на CMSIS_V2.
* У ''Code Generator'' табу је подешено да се генеришу одвојени фајлови за сваку периферију.
* Пинови PC<sub>6..0</sub>, PA<sub>13</sub> и PB<sub>0</sub> су подешени као GPIO_Output.
Након генерисања, линија 310 у <code>Middlewares/Third_Party/FreeRTOS/Source/portable/GCC/ARM_CM3/port.c</code> је закоментарисана.

==== ''Makefile'' ====
У ''Makefile'' су додати фајлови <code>uart.c</code>, <code>lcd.c</code>, <code>sensors.c</code> и <code>exam.c</code> у <code>C_SOURCES</code>, следећи блок:
<syntaxhighlight lang="makefile">
ifeq ($(DEBUG), 1)
CFLAGS += -g -gdwarf-2
endif

# Generate dependency information
CFLAGS += -MMD -MP -MF"$(@:%.o=%.d)"
</syntaxhighlight>
је промењен на:
<syntaxhighlight lang="makefile">
ifeq ($(DEBUG), 1)
CFLAGS += -g -gdwarf-2 -fdebug-prefix-map==../
endif

# Generate dependency information
CFLAGS += -MMD -MP -MF"$(@:%.o=%.d)"

CFLAGS += -mlong-calls
CFLAGS += -Wall -Wextra
</syntaxhighlight>
и <code>startup_stm32f103x6.s</code> је промењено на <code>Core/Src/startup_stm32f103x6.s</code> унутар <code>ASM_SOURCES</code>.

==== <code>lcd.h</code> ====
<syntaxhighlight lang="c">
#ifndef CORE_INC_LCD_H_
#define CORE_INC_LCD_H_

#include <stdint.h>

#include "FreeRTOS.h"
#include "task.h"
#include "queue.h"

#define CLEAR_DISPLAY_INSTRUCTION 0x01

#define RETURN_HOME_INSTRUCTION 0x02

#define ENTRY_MODE_INSTRUCTION 0x04
#define ENTRY_MODE_INC_CURSOR 0x02

#define DISPLAY_INSTRUCTION 0x08
#define DISPLAY_ON 0x04
#define DISPLAY_CURSOR_ON 0x02
#define DISPLAY_BLINK_ON 0x01

#define SHIFT_INSTRUCTION 0x10
#define SHIFT_DISPLAY 0x08
#define SHIFT_RIGHT 0x04

#define FUNCTION_INSTRUCTION 0x20
#define FUNCTION_2_LINES 0x08
#define FUNCTION_5x10_DOTS 0x04

#define SET_CGRAM_ADDRESS_INSTRUCTION 0x40

#define SET_DDRAM_ADDRESS_INSTRUCTION 0x80

typedef enum {
LCD_INSTRUCTION, LCD_DATA
} LCD_Register;

typedef struct {
LCD_Register reg;
uint8_t data;
} LCD_Command;

void LCD_Init();
void LCD_Enqueue(LCD_Register reg, uint8_t data);

#endif
</syntaxhighlight>

==== <code>uart.h</code> ====
<syntaxhighlight lang="c">
#ifndef CORE_INC_UART_H_
#define CORE_INC_UART_H_

#include <stdint.h>

#include "FreeRTOS.h"
#include "task.h"
#include "queue.h"

void UART_Transmit(uint8_t byte);
void UART_Init();

#endif
</syntaxhighlight>

==== <code>sensors.h</code> ====
<syntaxhighlight lang="c">
#ifndef CORE_INC_SENSORS_H_
#define CORE_INC_SENSORS_H_

extern float temperatureSensor;
extern float anemometerSensor;
extern float windvaneSensor;

void Sensors_Init();

#endif
</syntaxhighlight>

==== <code>exam.h</code> ====
<syntaxhighlight lang="c">
#ifndef CORE_INC_EXAM_H_
#define CORE_INC_EXAM_H_

extern unsigned overflowCounter;

void examInit();

#endif
</syntaxhighlight>

==== <code>lcd.c</code> ====
<syntaxhighlight lang="c">
#include "lcd.h"
#include "gpio.h"

// Napomena: referentna šema se razlikuje od one date na vežbama.
#define LCD_ENABLE_BIT 0x04

QueueHandle_t LCD_QueueHandle;
LCD_Command cmd;

void LCD_Write(LCD_Register reg, uint8_t data) {
// Napomena: referentna šema se razlikuje od one date na vežbama.
GPIOC->ODR = (data << 3) | reg;
GPIOC->ODR |= LCD_ENABLE_BIT;
GPIOC->ODR &= ~LCD_ENABLE_BIT;
}

void LCD_WriteCommand(LCD_Register reg, uint8_t data) {
LCD_Write(reg, data >> 4);
LCD_Write(reg, data);
vTaskDelay(pdMS_TO_TICKS(2));
}

void LCD_Task(void *parameters) {
UNUSED(parameters);
LCD_Write(LCD_INSTRUCTION, (FUNCTION_INSTRUCTION) >> 4);
vTaskDelay(pdMS_TO_TICKS(2));
LCD_WriteCommand(LCD_INSTRUCTION, FUNCTION_INSTRUCTION | FUNCTION_2_LINES);
LCD_WriteCommand(LCD_INSTRUCTION, DISPLAY_INSTRUCTION | DISPLAY_ON);
LCD_WriteCommand(LCD_INSTRUCTION,
ENTRY_MODE_INSTRUCTION | ENTRY_MODE_INC_CURSOR);
LCD_WriteCommand(LCD_INSTRUCTION, RETURN_HOME_INSTRUCTION);
while (1) {
xQueueReceive(LCD_QueueHandle, &cmd, portMAX_DELAY);
LCD_WriteCommand(cmd.reg, cmd.data);
}
}

void LCD_Enqueue(LCD_Register reg, uint8_t data) {
cmd.reg = reg;
cmd.data = data;
xQueueSendToBack(LCD_QueueHandle, &cmd, portMAX_DELAY);
}

void LCD_Init() {
xTaskCreate(LCD_Task, "LCD_Task", 128, NULL, 5, NULL);
LCD_QueueHandle = xQueueCreate(64, sizeof(LCD_Command));
}
</syntaxhighlight>

==== <code>uart.c</code> ====
<syntaxhighlight lang="c">
#include "uart.h"
#include "usart.h"

QueueHandle_t UART_QueueHandle;
TaskHandle_t UART_TaskHandle;

void UART_Task(void *parameters) {
UNUSED(parameters);
uint8_t byte;
while (1) {
xQueueReceive(UART_QueueHandle, &byte, portMAX_DELAY);
HAL_UART_Transmit_IT(&huart1, &byte, sizeof(uint8_t));
ulTaskNotifyTake(pdTRUE, portMAX_DELAY);
}
}

void HAL_UART_TxCpltCallback(UART_HandleTypeDef *huart) {
if (huart->Instance != huart1.Instance) {
return;
}
BaseType_t wokenTask = pdFALSE;
vTaskNotifyGiveFromISR(UART_TaskHandle, &wokenTask);
portYIELD_FROM_ISR(wokenTask);
}

void UART_Transmit(uint8_t byte) {
xQueueSendToBack(UART_QueueHandle, &byte, portMAX_DELAY);
}

void UART_Init() {
xTaskCreate(UART_Task, "UART_Task", 128, NULL, 5, &UART_TaskHandle);
UART_QueueHandle = xQueueCreate(64, sizeof(uint8_t));
}
</syntaxhighlight>

==== <code>sensors.c</code> ====
<syntaxhighlight lang="c">
#include "sensors.h"

#include "FreeRTOS.h"
#include "task.h"

#include "adc.h"
#include "gpio.h"
#include "tim.h"

#define MAX_VOLTAGE 5.0
#define MAX_RESOLUTION 4096

float temperatureSensor = 0.0;
float anemometerSensor = 0.0;
float windvaneSensor = 0.0;
int fetchingTemperature;
unsigned overflowCounter = 0;
int previousTicks = 0;

TaskHandle_t Sensors_TaskHandle;

void Sensors_Task(void *parameters) {
UNUSED(parameters);
while (1) {
fetchingTemperature = 1;
HAL_GPIO_WritePin(GPIOB, GPIO_PIN_0, GPIO_PIN_RESET);
HAL_ADC_Start_IT(&hadc1);
ulTaskNotifyTake(pdTRUE, portMAX_DELAY);

fetchingTemperature = 0;
HAL_GPIO_WritePin(GPIOB, GPIO_PIN_0, GPIO_PIN_SET);
HAL_ADC_Start_IT(&hadc1);
ulTaskNotifyTake(pdTRUE, portMAX_DELAY);

vTaskDelay(pdMS_TO_TICKS(100));
}
}

float adcToWindvane(int adcValue) {
switch (adcValue) {
case 952:
return 0.0;
case 2471:
return 22.5;
case 2250:
return 45.0;
case 3760:
return 67.5;
case 3723:
return 90.0;
case 3831:
return 112.5;
case 3356:
return 135.0;
case 3589:
return 157.5;
case 2946:
return 180.0;
case 3116:
return 202.5;
case 1575:
return 225.0;
case 1698:
return 247.5;
case 315:
return 270.0;
case 786:
return 292.5;
case 547:
return 315.0;
case 1285:
return 337.5;
default:
return 0.0;
}
}

void HAL_ADC_ConvCpltCallback(ADC_HandleTypeDef *hadc) {
if (hadc->Instance != hadc1.Instance) {
return;
}
uint32_t value = HAL_ADC_GetValue(hadc);
if (fetchingTemperature) {
temperatureSensor =
((float) value) * MAX_VOLTAGE * 100 / MAX_RESOLUTION;
} else {
windvaneSensor = adcToWindvane(value);
}
xTaskNotifyGive(Sensors_TaskHandle);
}

void HAL_TIM_IC_CaptureCallback(TIM_HandleTypeDef *htim) {
if (htim->Instance != htim1.Instance) {
return;
}
float ticks = htim->Instance->CCR1 + overflowCounter * 65536
- previousTicks;
previousTicks = htim->Instance->CCR1;
overflowCounter = 0;
anemometerSensor = 8000000.0 / ticks * 2.4;
}

void Sensors_Init() {
HAL_TIM_Base_Start_IT(&htim1);
HAL_TIM_IC_Start_IT(&htim1, TIM_CHANNEL_1);
xTaskCreate(Sensors_Task, "Sensors_Task", 128, NULL, 5,
&Sensors_TaskHandle);
}
</syntaxhighlight>

==== <code>exam.c</code> ====
<syntaxhighlight lang="c">
#include "exam.h"
#include "lcd.h"
#include "uart.h"
#include "sensors.h"

#include "FreeRTOS.h"
#include "task.h"
#include "timers.h"

#include "gpio.h"
#include <string.h>

void writeLCD(unsigned addr, const char *str) {
LCD_Enqueue(LCD_INSTRUCTION, SET_DDRAM_ADDRESS_INSTRUCTION | addr);
for (size_t i = 0; i < strlen(str); ++i) {
LCD_Enqueue(LCD_DATA, str[i]);
}
}

void writeUART(char *str) {
for (size_t i = 0; i < strlen(str); ++i) {
UART_Transmit(str[i]);
}
}

void intToStr(int num, char *str, int maxLen) {
for (int i = 0; i < maxLen; ++i) {
str[i] = ' ';
}
int index = maxLen - 1;
if (num == 0) {
str[maxLen - 1] = '0';
}
while (num > 0 && index >= 0) {
str[index--] = '0' + (num % 10);
num /= 10;
}
str[maxLen] = '\0';
}

float prevTemperatureSensor;
float prevWindvaneSensor;
float prevAnemometerSensor;

void examTask(void *parameters) {
UNUSED(parameters);
// Ekvivalentne adrese: 0x80, 0xC0, 0x90
// Kontroleru se ne mogu poslati adrese sa preko 7 bita
// Napomena: redosled ispisa je ispravljen ovde, ali nije u projektu.
writeLCD(0x10, "Temper: ");
writeLCD(0x00, "Azimut: ");
writeLCD(0x40, "Brzina: ");
while (1) {
if (((int) prevTemperatureSensor) != ((int) temperatureSensor)
|| ((int) prevWindvaneSensor) != ((int) windvaneSensor)
|| ((int) prevAnemometerSensor) != ((int) anemometerSensor)) {
prevTemperatureSensor = temperatureSensor;
prevWindvaneSensor = windvaneSensor;
prevAnemometerSensor = anemometerSensor;
char temper[4];
char azimut[4];
char brzina[4];
intToStr((int) temperatureSensor, temper, 3);
intToStr((int) windvaneSensor, azimut, 3);
intToStr((int) anemometerSensor, brzina, 3);
// Napomena: redosled ispisa je ispravljen ovde, ali nije u projektu.
writeLCD(0x18, temper);
writeLCD(0x08, azimut);
writeLCD(0x48, brzina);
writeUART("\b\b\b\b\b\b\b\b\b\b\b");
writeUART(azimut);
writeUART("/");
writeUART(brzina);
writeUART("/");
writeUART(temper);
}
vTaskDelay(pdMS_TO_TICKS(200));
}
}

void ledTimer(TimerHandle_t xTimer) {
UNUSED(xTimer);
if (anemometerSensor < 50) {
HAL_GPIO_WritePin(GPIOA, GPIO_PIN_13, GPIO_PIN_RESET);
} else {
HAL_GPIO_TogglePin(GPIOA, GPIO_PIN_13);
}
}

void examInit() {
LCD_Init();
UART_Init();
Sensors_Init();
xTaskCreate(examTask, "examTask", 128, NULL, 2, NULL);
TimerHandle_t timer = xTimerCreate("ledTimer", pdMS_TO_TICKS(500), pdTRUE,
NULL, ledTimer);
xTimerStart(timer, portMAX_DELAY);
}
</syntaxhighlight>

==== <code>main.c</code> ====
Унутар <code>HAL_TIM_PeriodElapsedCallback</code>, додат је блок кода:
<syntaxhighlight lang="c">
/* USER CODE BEGIN Callback 1 */
if (htim->Instance == TIM1) {
++overflowCounter;
}
/* USER CODE END Callback 1 */
</syntaxhighlight>

Такође додати:
<syntaxhighlight lang="c">
/* USER CODE BEGIN Includes */
#include "exam.h"
/* USER CODE END Includes */

/* USER CODE BEGIN 2 */
examInit();
/* USER CODE END 2 */
</syntaxhighlight>

== Напомене ==
<references />

[[Категорија:Рокови]]
[[Категорија:Микропроцесорски системи]]

Системски софтвер/К2 2022

2024-08-27T16:58:27Z

MihailoM342: /* Решење */

{{tocright}}
'''Други колоквијум 2022.''' одржан је 14. маја. Колоквијум је трајао 90 минута и радио се у вежбанкама. Оба задатка су вредела 10 поена.

== 1. задатак ==
=== Поставка ===
Дати код на асемблеру за ''amd64'' преводи се двопролазним асемблером. Резултат превођења је предмети програм по ''ELF'' формату. Приказати садржај:
# табеле симбола
# релокационих записа као и
# садржај секција.
Користити школски формат наведен у наставку:
{| class="wikitable"
|+ ТАБЕЛА СИМБОЛА
|-
! Num !! Value !! Size !! Type !! Bind !! Ndx !! Name
|}
{| class="wikitable"
|+ РЕЛОКАЦИОНИ ЗАПИСИ
|-
! Offset !! Type !! Symbol !! Addend
|}
При решавању усвојити следеће (хексадецималне вредности унутар заграда након податка о величини инструкције јесу први бајтови инструкције који представљају њен операциони код):
* Инструкција <code>call</code> користи ''PC'' релативно адресирање. Величина инструкције је шест бајтова (<code>0xff 0x15</code>).
* Инструкција <code>mov</code> користи апсолутно адресирање. Величина инструкције је осам бајтова (<code>0x48 0x8b 0x04 0x25</code>).
* Инструкција <code>jz</code> користи ''PC'' релативно адресирање. Величина инструкције је два бајта (<code>0x74</code>) или шест бајтова (<code>0x0f 0x84</code>) зависно од величине помераја.
<syntaxhighlight lang="asm">
.intel_syntax noprefix
.extern a
.global f
.equ f, b-c

.text
call a[rip]
e: mov rax, c
jz e
jz c
d: mov rax, b - f
.long e

.data
.skip 6
c: .long b + 0xe
b:
.end
</syntaxhighlight>

=== Решење ===
{| class="wikitable"
|+ <code>.symtab</code>
|-
! Num !! Value [hex] !! Size !! Type !! Bind !! Ndx !! Name
|-
| 0 || 0 || 0 || NOTYP || LOC || UND ||
|-
| 1 || 0 || 0 || SCTN || LOC || 1 || .text
|-
| 2 || 0 || 0 || SCTN || LOC || 2 || .data
|-
| 3 || 4 || 0 || NOTYP || GLOB || *ABS* || f
|-
| 4 || 0 || 0 || NOTYP || GLOB || UND || a
|-
| 5 || A || 0 || NOTYP || LOC || 2 || b
|-
| 6 || 6 || 0 || NOTYP || LOC || 2 || c
|-
| 7 || 16 || 0 || NOTYP || LOC || 1 || d
|-
| 8 || 6 || 0 || NOTYP || LOC || 1 || e
|}
{| class="wikitable"
|+ <code>.rela.text</code>
! Offset !! Type !! Symbol !! Addend
|-
| 2 || PC32 || a || -4
|-
| A || 32 || .data || 6
|-
| 12 || PC32 || .data || 2
|-
| 1A || 32 || .data || 6
|-
| 1E || 32 || .text || 6
|}
{| class="wikitable"
|+ <code>.rela.data</code>
! Offset !! Type !! Symbol !! Addend
|-
| 6 || 32 || .data || 18
|}
{| class="wikitable"
|+ <code>.text</code>
! Offset
! colspan="8" | Content
! Instruction
|-
| 0000 || FF || 15 || 00 || 00 || 00 || 00 || || || <syntaxhighlight lang="asm" inline>call a[rip]</syntaxhighlight>
|-
| 0006 || 48 || 8B || 04 || 25 || 00 || 00 || 00 || 00 || <syntaxhighlight lang="asm" inline>mov rax, c</syntaxhighlight>
|-
| 000E || 74 || F6 || || || || || || || <syntaxhighlight lang="asm" inline>jz e</syntaxhighlight>
|-
| 0010 || 0F || 84 || 00 || 00 || 00 || 00 || || || <syntaxhighlight lang="asm" inline>jz c</syntaxhighlight>
|-
| 0016 || 48 || 8B || 04 || 25 || 00 || 00 || 00 || 00 || <syntaxhighlight lang="asm" inline>mov rax, b - f</syntaxhighlight>
|-
| 001D || 00 || 00 || 00 || 00 || || || || || <syntaxhighlight lang="asm" inline>.long e</syntaxhighlight>
|}
{| class="wikitable"
|+ <code>.data</code>
! Offset
! colspan="8" | Content
! Instruction
|-
| 0000 || 00 || 00 || 00 || 00 || 00 || 00 || || || <syntaxhighlight lang="asm" inline>.skip 6</syntaxhighlight>
|-
| 0006 || 00 || 00 || 00 || 00 || || || || || <syntaxhighlight lang="asm" inline>.long b + 0xe</syntaxhighlight>
|}

== 2. задатак ==
=== Поставка ===
Одредити вредност при обради од стране асемблера за хипотетичку машину (уколико вредност није позната написати знак питања) и индекс класификације за сваки израз у оквиру изворног асемблерског кода датог у наставку.
<syntaxhighlight lang="asm">
BEG
USE LAB1
ORG 0x64
SCT DAT
LAB2 DC LAB1
DC 7 + LAB2
SCT TXT
LAB3 LDA LAB2 - 1
ADX * - LAB3
OTI
HLT
END
</syntaxhighlight>
=== Решење ===
{| class="wikitable"
|-
! Наредба
! Индекс класификације
! Вредност
|-
| <code>DC LAB1</code>
| 1.unique()
| ?
|-
| <code>DC 7 + LAB2</code>
| 0 + 1.DAT = 1.DAT
| 0x6b
|-
| <code>LDA LAB2 - 1</code>
| 1.DAT - 0 = 1.DAT
| 0x63
|-
| <code>ADX * - LAB3</code>
| 1.TXT - 1.TXT = 0
| 0x2
|}

[[Категорија:Системски софтвер]]
[[Категорија:Рокови]]

Системски софтвер/Септембар 2022

2024-08-17T17:56:23Z

MihailoM342: /* Решење */

{{tocright}}
'''Испит из септембарског рока 2022.''' одржан је 14.09.
== 1. задатак ==
: Исти задатак се нашао на [[Системски софтвер/Јун 2022#1. задатак|јунском року 2022. године]]
=== Поставка ===
Посматра се процес асемблирања датог ивзорног асемблерског кода за ''amd64'' архитектуру. Резултат асемблирања је предметни програм по ''ELF'' формату. Приказати садржај (1) табеле симбола и (2) релокационих записа <u>строго поштујући школски формат и обавезно у складу са задатом нумерацијом симбола</u>.
<syntaxhighlight lang="asm">
.intel_syntax noprefix
.section .text
.global min, la1
min: enter 0, 0 # 0x00
mov rbx, la1 # 0x04
cmp rbx, [rbp]+0x12 # 0x0c
call var[rip] # 0x10
jle la1 # 0x16
mov rax, [rbp]+0x12 # 0x18
jmp la2 # 0x1c
la1: mov rax, rbx # 0x1e
la2: leave # 0x21
ret # 0x22

.data
.global var
.type var, @object
var:
.quad la1, la2-4
.end
</syntaxhighlight>

Напомена: хексадецимални бројеви наведени у коментару изворног асемблерског кода представљају померај до почетка инструкције у том реду гледано од почетка секције којој инструкција припада. Такође, усвојити претпоставку да је величина операционог кода:
* 2B за инструкцију <code>call</code> за ''PC'' релативно адресирање,
* 4B за инструкцију <code>mov</code> за апсолутно адресирање и
* 1B за инструкције <code>jle</code> и <code>jmp</code> за ''PC'' релативно адресирање.
=== Решење ===
Видети [[Системски софтвер/Јун 2022#1. задатак|овде]].
== 2. задатак ==
=== Поставка ===
Посматра се макро процесор са угњежденим макро дефиницијама, без угњеждених макро експанзија.
<div class="abc-list">
# Шта је резултат макро експанзије задатог текста?
# Приказати операције над стеком параматера према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
# Приказати операције над стеком аргумената према редоследу њиховог извођења користећи нотације ''PUSH(...)'' и ''POP(...)'' при чему уместо три тачкице треба навести листу вредности које се смештају или скидају са стека.
</div>
MCDEFN
M1 A, B, C D
M2 A, B, C
MCDEFN
M2 C, D, F
A, B, C, D, E
MCEND
M2 C, D, F
MCEND
M2 1, 2, 3
M1 4, 5, 6, 7
M1 4, 5, 6, 7
M2 1, 2, 3
=== Решење ===
a)

M2 1, 2, 3
M2 4, 5, 6
M2 6, 7, F
M2 4, 5, 6
M2 6, 7, F
4, 5, 1, 2, E

b)

PUSH(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))
PUSH(((2,0),C), ((2,1),D), ((2,2),F))
POP(((2,0),C), ((2,1),D), ((2,2),F))
POP(((1,0),A), ((1,1),B), ((1,2),C), ((1,3),D))

c)

PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,4), (1,5), (2,6), (3,7))
POP((0,4), (1,5), (2,6), (3,7))
PUSH((0,1), (1,2), (2,3))
POP((0,1), (1,2), (2,3))

== 3. задатак ==
=== Поставка ===
Посматрају се два објектна програма <code>levi.o</code> и <code>desni.o</code> добијена помоћу ''GNU'' асемблера.
{| class="wikitable"
|
#shdr
Num Address Size Type Flags Name
1: 0000000 0052 PROGBITS AX .text
3: 0000000 0000 PROGBITS WA .data
4: 0000000 0012 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000013 0000 FUNC GLOB 1 a
5: 0000010 0000 NOTYP GLOB 4 d
6: 0000000 0000 NOTYP GLOB UND c
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 4 (a) 0
000000b R_X86_64_PC32 6 (c) -4
||
#shdr
Num Address Size Type Flags Name
1: 0000000 000a PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
5: 0000000 0016 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 5 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 0000008 0000 OBJCT GLOB 5 c
6: 0000000 0000 NOTYP GLOB UND a
#.rela.text
Offset Type Symbol Addend
0000003 R_X86_64_PC32 6 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 0
|}

Приказати излаз линкера <code>izlaz.o</code> тако да буде испоштовано све што је наведено у наставку:
* <u>строго поштујући школски формат и обавезно са нумерацијом у табели симбола према следећем редоследу</u>: <code>UND, .text, .data, .bss, b, c, d, a </code>
* повезивање се иницира следећом командом <code>ld --relocatable -o izlaz.o -T script.ld levi.o desni.o</code>
* линкерска скрипта <code>script.ld</code> има следећи садржај:
SECTIONS
{
.text : { *(.text) }
.data : { *(.data) }
.bss : { *.(bss) }
}
=== Решење ===

#shdr
Num Address Size Type Flags Name
1: 0000000 005c PROGBITS AX .text
3: 0000000 0008 PROGBITS WA .data
4: 0000000 0028 NOBITS WA .bss
#.symtab
Num Value Size Type Bind Ndx Name
0: 0000000 0000 NOTYP LOC UND
1: 0000000 0000 SCTN LOC 1 .text
2: 0000000 0000 SCTN LOC 3 .data
3: 0000000 0000 SCTN LOC 4 .bss
4: 0000004 0000 NOTYP LOC 3 b
5: 000001a 0000 OBJCT GLOB 4 c
6: 0000010 0000 NOTYP GLOB 4 d
7: 0000013 0000 FUNC GLOB 1 a
#.rela.text
Offset Type Symbol Addend
0000004 R_X86_64_32S 7 (a) 0
000000b R_X86_64_PC32 5 (c) -4
0000055 R_X86_64_PC32 7 (a) -4
#.rela.data
Offset Type Symbol Addend
0000002 R_X86_64_32 3 (.bss) 12

== 4. задатак ==
: Исти задатак се нашао на [[Системски софтвер/Јун 2022#4. задатак|јунском року 2022. године]]
=== Поставка ===
Посматра се ''JIT'' емулатор и емулирање следећег програма.
<div class="abc-list">
# Означити све блокове који ће у току рада емулатора бити преведени. За сваки преведени блок навести јединствену идентификацију у облику <code>'''B'''''<n>(<x>-<y>)</code> (<code><n></code> је <u>редни број блока у погледу тренутка његовог превођења при чему нумерација почиње од броја један</u>, <x> је редни број прве а <y> редни број последње линије изворног кода блока).
# Навести секвенцу извршавања. У секвенци извршавања могу се нађи само <code>GP</code> (сваки пут када се емулатор врати у главну петљу), <code>BH</code> (сваки пут када се позове функција која помаже у разрешавању скокова) и <code>'''B'''''<n></code> (сваки пут када се изврши дати блок у складу са ознакама из претходне тачке).
</div>

<syntaxhighlight lang="asm">
BEG ; line 1
LDI 2 ; line 2 ( PZ) A <= <V>
L1 SUB B ; line 3 (CPZ) A <= A - mem[<V>]
L2 ADD C ; line 4 (CPZ) A <= A + mem[<V>]
BNG L2 ; line 5 if (!flags[P]) PC <= <V>
BZE L3 ; line 6 if ( flags[Z]) PC <= <V>
SBI 2 ; line 7 (CPZ) A <= A - <V>
BNZ L1 ; line 8 if (!flags[Z]) PC <= <V>
L3 HLT ; line 9 stop execution
B DC 9 ; line 10
C DC 2 ; line 11
END ; line 12
</syntaxhighlight>
=== Решење ===
Видети [[Системски софтвер/Јун 2022#4. задатак|овде]].

[[Категорија:Рокови]]
[[Категорија:Системски софтвер]]

Системски софтвер/Август 2022

2024-08-13T15:07:04Z

MihailoM342: /* Решење */

{{tocright}}
'''Испит у августовском року 2022. године''' одржан је 24. августа. Сваки задатак вреди укупно 10 поена. Испит траје 2 сата.

== 1. задатак ==
=== Поставка ===
Одредити вредност при обради од стране асемблера за хипотетичку машину (уколико вредност није позната написати знак питања) и индекс класификације за сваки израз у оквиру изворног асемблерског кода датог у наставку.
<syntaxhighlight lang="asm">
BEG
USE LAB1
ORG 0x60
SCT DAT
LAB2 DC LAB1
DC 7 + LAB2
SCT TXT
LAB3 LDA LAB2 - 1
ADX * - LAB3
END
</syntaxhighlight>
=== Решење ===
{| class="wikitable"
|-
! Наредба
! Индекс класификације
! Вредност
|-
| <code>DC LAB1</code>
| 1.unique()
| ?
|-
| <code>DC 7 + LAB2</code>
| 0 + 1.DAT = 1.DAT
| 0x67
|-
| <code>LDA LAB2 - 1</code>
| 1.DAT - 0 = 1.DAT
| 0x5f
|-
| <code>ADX * - LAB3</code>
| 1.TXT - 1.TXT = 0
| 0x2
|}
== 2. задатак ==
=== Поставка ===
Навести шта је резултат експанзије следећег кода од стране C претпроцесора и објаснити како је добијен.
<syntaxhighlight lang="c">
#define M1(x1) M2(x1)
#define M2(x1) M3(x1,A)
#define M3(x1,x2) x2 M3(x1,x2) M1(x1)
M3(M1(C), B)
</syntaxhighlight>
=== Решење ===
Појављивање неког макроа у својој дефиницији се не сматра макропозивом. Видети [https://gcc.gnu.org/onlinedocs/cpp/Self-Referential-Macros.html 3.10.5 Self-Referential Macros] из документације C претпроцесора.
<syntaxhighlight lang="c">
B M3(A M3(C, A) M1(C), B) M3(A M3(C,A) M1(C), A)

</syntaxhighlight>

== 3. задатак ==
=== Поставка ===
За неки емулатор потребно је написати функцију <code>void write(unsigned addr, unsigned data)</code> за упис у меморију. Адресни простор је величине 4 GB, а адресабилна јединица је бајт. Сматрати да је приступ речи увек поравнат на адресу дељиву са 4.
На располагању су функције <code>unsigned rphy(unsigned addr)</code>, која дохвата реч са дате физичке адресе и <code>void wphy(unsigned addr, unsigned data)</code>, која уписује задату реч на задату физичку адресу.
Емулирана машина поседује виртуелну меморију организовану странично. Величина странице је 16 KB. Регистар ''PMTP'' (који се емулира истоименом глобалном променљивом) садржи адресу табеле за пресликавање страница.
Сваки улаз у табели је 32 бита, при чему су највиша два бита ''V'' и ''D'' битови.
Уколико је ''V'' бит једнак 0, у најнижих 30 битова је записана адреса на диску, док је у случају да је бит ''V'' једнак 1, у најнижим битовима улаза записан редни број блока у који је смештена страница. У случају да страница није у меморији, учитава се у меморију позивом функције <code>void load(unsigned hddaddr)</code>, која у позадини генерише ''page fault'' и блокира позивајућу нит док страница не буде учитана са диска. Једини аргумент функције представља адресу којој се приступа.
=== Решење ===
Адресни простор је 4 GB, што значи да је адреса 32-битна.
Ако је величина странице 16 KB, најнижих 14 бита виртуелне адресе је померај у страници, а виших 18 је број улаза. Пошто је свака реч поравната са 4, улаз у табелу не мора да садржи два најнижа бита јер су она увек 0. Улаз у табелу пресликавања страница и виртуеална адреса изгледају овако:

''VA(32): PageNumber(18), Offset(14)''

''PMT(32): V(1), D(1), PhyAddress/BlockNumber(30)''
<syntaxhighlight lang="c">
void write(unsigned addr, unsigned data) {
unsigned offset = addr & 0x3FFF;
unsigned blk_no = addr >> 14;
// Проверавамо присутност блока у меморији
if (PMTP[blk_no] & 0x8000_0000) {
// Блок се налази у меморији
unsigned phy_addr = PMT[blk_no] << 2;
wphy(phy_addr + offset, data);

// Постављање dirty бита није било стриктно тражено на испиту
PMTP[blk_no] |= 0x4000_0000;
} else {
// Блок се мора довући са диска
unsigned block_no = PMT[blk_no] & 0x3FFF_FFFF;
load(block_no);
// Рекурзивни позив упада у горњу грану if-а.
write(addr, data);
}
}
</syntaxhighlight>

== 4. задатак ==
=== Поставка ===
Посматра се процес покренут над програмом ''run'' добијеним повезивањем са дељеном библиотеком ''libfoo.so''. Дељена библиотека ''libfoo.so'' садржи функције <code>bar</code> и <code>baz</code> чије су адресе унутар ''libfoo.so'' <code>0x1218</code> и <code>0x12C4</code> респективно, а сама дељена библиотека ''libfoo.so'' мапирана је почев од адресе <code>0x4FFF0000</code> унутар адресног простора посматраног процеса.

Програм ''run'', који представња ''PIC shared object ELF'' датотеку, мапиран је почев од адресе <code>0x7EEE0000</code> унутар адресног простора посматраног процеса. Програм ''run'' од дељених библиотека користи искључиво ''libfoo.so'' и позива њене две функције <code>bar</code> и <code>baz</code> користећи лењо повезивање. Уколико је познат део <code>.plt</code> секције програма ''run'', наведен у наставку, потребно је урадити следеће.

<div class="abc-list">
# '''[2]''' Одредити на којој адреси се налази <code>.got.plt</code> секција програма ''run''.
# '''[4]''' Попунити <code>.plt</code> секцију (заменити свако појављивање знакова питања одговарајућом вредношћу) уколико је познато да се улаз за функцију <code>bar</code> унутар <code>.plt</code> секције налази испред улаза за функцију <code>baz</code> унутар <code>.plt</code> секције.
# '''[2]''' Навести вредности које се налазе у улазима <code>.got.plt</code> секције, који одговарају симболима <code>bar</code> и <code>baz</code>, у тренутку пре него што је посматрани процес извршио први позив било које функције из дељене библиотеке ''libfoo.so''.
# '''[2]''' Навести вредности које се налазе у улазима <code>.got.plt</code> секције, који одговарају симболима <code>bar</code> и <code>baz</code>, у тренутку након што је посматрани процес извршио позив функције <code>bar</code>, а пре позива функције <code>baz</code>.
</div>

Disassembly of section .plt:
0000000000001060 <.plt>:
1060: ff 35 a2 42 00 00 push QWORD PTR [rip + 0x42a2]
1066: ff 25 a4 42 00 00 jmp QWORD PTR [rip + 0x42a4]
106c: 0f 1f 40 00 nop DWORD PTR [rax + 0x00]
1070: ff 25 ?? ?? ?? ?? jmp QWORD PTR [rip + ??]
1076: 68 00 00 00 00 push 0x00
107b: e9 ?? ?? ?? ?? jmp ??
1080: ff 25 ?? ?? ?? ?? jmp QWORD PTR [rip + ??]
1086: 68 01 00 00 00 push 0x01
108b: e9 ?? ?? ?? ?? jmp ??
=== Решење ===
Адресу <code>.got.plt</code> секције може се наћи разрешавањем помераја у нултом улазу <code>.plt</code> секције. Инструкција <code>push</code> на 0x1060 као операнд има први улаз у ''GOT'' табели. Величина улаза у ''GOT'' табели је 8 бајта. Одатле:
GOT[1] = rip + 0x42a2
GOT[1] = 0x1066 + 0x42a2
GOT[1] = 0x5308
GOT[0] = GOT[1] - 1 * 8 = 0x5308 - 8 = 0x5300
Исти резултат се добија коришћењем операнда <code>jmp</code> инструкције на 0x1066, која указује на други улаз:
GOT[2] = rip + 0x42a4
GOT[2] = 0x106c + 0x42a4
GOT[2] = 0x5310
GOT[0] = GOT[2] - 2 * 8 = 0x5310 - 0x10 = 0x5300

Структура ''GOT'' табеле:
{| class="wikitable"
|-
! Адреса
! Улаз
! Садржај
|-
| 0x5300<br />
| 0
| .dynamic
|-
| 0x5308
| 1
| .rel.dyn
|-
| 0x5310
| 2
| динамички линкер
|-
| 0x5318
| 3
| bar()<br />
|-
| 0x5320
| 4
| baz()<br />
|}

Први улаз ''PLT''-а припада функцији <code>bar</code>. Инструкција <code>jmp</code> на 0x1070 треба да скаче на трећи улаз у ''GOT'', а <code>jmp</code> на 0x107b на нулти улаз ''PLT''-а:
0x5318 - 0x1076 = 0x42a2
0x1060 - 0x1080 = 0xffffffe0
Други улаз ''PLT''-а припада функцији <code>baz</code>. Инструкција <code>jmp</code> на 0x1080 треба да скаче на четврти улаз у ''GOT'', а <code>jmp</code> на 0x108b на нулти улаз ''PLT''-а:
0x5320 - 0x1086 = 0x429a
0x1060 - 0x1090 = 0xffffffd0

Садржај <code>.plt</code> секције:
Disassembly of section .plt:
0000000000001060 <.plt>:
1060: ff 35 a2 42 00 00 push QWORD PTR [rip + 0x42a2]
1066: ff 25 a4 42 00 00 jmp QWORD PTR [rip + 0x42a4]
106c: 0f 1f 40 00 nop DWORD PTR [rax + 0x00]
1070: ff 25 a2 42 00 00 jmp QWORD PTR [rip + 0x42a2]
1076: 68 00 00 00 00 push 0x00
107b: e9 e0 ff ff ff jmp 1060
1080: ff 25 9a 42 00 00 jmp QWORD PTR [rip + 0x429a]
1086: 68 01 00 00 00 push 0x01
108b: e9 d0 ff ff ff jmp 1060

Садржај ''GOT'' табеле пре позивања било које функције из ''libfoo.so'':
5318: 76 10 ee 7e 00 00 00 00
5320: 86 10 ee 7e 00 00 00 00

Садржај ''GOT'' табеле након што је посматрани процес извршио позив функције <code>bar</code>, а пре позива функције <code>baz</code>:
5318: 18 12 ff 4f 00 00 00 00
5320: 86 10 ee 7e 00 00 00 00

[[Категорија:Рокови]]
[[Категорија:Системски софтвер]]

Заштита података/Јун 2022

2024-07-09T16:45:39Z

MihailoM342: /* 5. zadatak */

{{tocright}}
'''Ispit u junskom ispitnom roku 2022. godine''' održan je 7. juna.
{{rešenja}}

== 1. zadatak ==
Ana je kreirala poruku ''M'' koju je poslala Branku dva puta.

Uz poruku je oba puta poslala El Gamalov digitalni potpis poruke ''M''. Branko je oba puta dobio poruku i digitalne potpise. Prvi put je vrednost digitalnog potpisa koju je dobio Branko bila: <math>(S_1=110, S_2=791)</math>, a drugi put <math>(S_1=1760, S_2=640)</math>.

Branko je izračunao hash dobijene poruke ''M'' i oba puta dobio vrednost <math>m=3769</math>.

Javni elementi digitalnog potpisa su broj <math>q=5003</math> i njegov primitivni koren <math>\alpha=4999</math>.

Anin javni ključ <math>Y_a</math> je 1682. Provera El Gamalovog digitalnog potpisa se obavlja korišćenjem sledećih formula:
* <math>V_1=\alpha^m \bmod q</math>
* <math>V_2=Y_a^{S_1}S_1^{S_2}\bmod q</math>
Odrediti:
<div class="abc-list">
<ol>
<li>'''(3 poena)''' Vrednost <math>V_2</math> za prvi digitalni potpis: <span class="spoiler" data-solution="text">4890</span></li>
<li>'''(1 poen)''' Vrednost <math>V_2</math> za drugi digitalni potpis: <span class="spoiler" data-solution="text">2419</span></li>
<li>'''(4 poena)''' Na osnovu vrednosti V1 i izračunatih vrednosti u tačkama a) i b), Branko može da zaključi:
<div data-solution="single">
* Oba digitalna potpisa su ispravna, poruka ''M'' u oba slučaja nije menjana tokom prenosa i oba puta ju je potpisala Ana
* Ni jedan digitalni potpis nije ispravan i ne može da se utvrdi da je Ana potpisala tu poruku i da li je menjana tokom prenosa.
* Samo drugi digitalni potpis je ispravan i samo druga poruka nije menjana tokom prenosa i nju je potpisala Ana
* <span class="solution">Samo prvi digitalni potpis je ispravan i samo prva poruka nije menjana tokom prenosa i nju je potpisala Ana</span>
</div>
</li>
</div>

== 2. zadatak ==
Na slici je dat digitalni sertifikat (sa skraćenim prikazom RSA modula i digitalnog potpisa zbog prostora).
<pre>
Version: 3 (0x02)
Serial number: 20045315772003125868899357870856421858 (0x0f14965f202069994fd5c7ac788941e2)
Algorithm ID: SHA256withRSA
Validity
Not Before: 21/07/2020 23:00:00 (dd-mm-yyyy hh:mm:ss) (200721230000Z)
Not After: 08/10/2024 07:00:00 (dd-mm-yyyy hh:mm:ss) (241008070000Z)
Issuer
C = IE
O = Baltimore
OU = CyberTrust
CN = Baltimore CyberTrust Root
Subject
C = US
O = Microsoft Corporation
CN = Microsoft RSA TLS CA 01
Public Key
Algorithm: RSA
Length: 4096 bits
Modulus: aa:62:77:cf:9a:63:b2:06:84:f3:90:36:f4:99:f3:14:
...
1c:dd:30:8b:Od:4a:14:60:f9:d5:64:4f:43:44:a1:ed
Exponent: 65537 (0x10001)
Certificate Signature
Algorithm: SHA256withRSA
Signature: 9f:2b:be:92:67:5b:da:7b:Ba:ad:e8:ff:9d:4d:05:0e:
...
47:45:5e:79:54:c5:f9:dd:eb:fa:3f:78:51:75:d2:5b

Extensions
subjectKeyIdentifier :
b5760c3011cec792424d4cc75c2cc8a90ce80b64
authorityKeyldentifier :
kid=e59d5930824758ccacfa085436867b3ab5044df0
keyUsage CRITICAL:
digitalSignature,keyCertSign,cRLSign
extKeyUsage :
serverAuth, clientAuth
basicConstraints CRITICAL:
cA=true, pathLen=0
authorityInfoAccess :
ocsp: http://ocsp.digicert.com
cRLDistributionPoints :
http://crl3.digicert.com/Omniroot2025.crl
certificatePolicies :
policy oid: 2.23.140.1.2.1
policy oid: 2.23.140.1.2.2
policy oid: 1.3.6.1.4.1.311.42.1
</pre>
Taj digitalni sertifikat je izdala firma:
<div data-solution="single">
* Microsoft Corporation
* <span class="solution">Baltimore CyberTrust</span>
* Digicert
* Ne može da se odredi
</div>
Da bi se proverila validnost ovog sertifikata potrebno je:
<div data-solution="multiple">
* Proveriti CRL listu koju hostuje Microsoft Corporation
* Proveriti CRL listu koju hostuje Baltimore CyberTrust
* <span class="solution">Proveriti CRL listu koju hostuje Digicert</span>
* <span class="solution">Preuzeti i proveriti digitalni sertifikat firme Baltimore CyberTrust</span>
* Preuzeti i proveriti digitalni sertifikat firme Microsoft Corporation
* Preuzeti i proveriti digitalni sertifikat firme Digicert
</div>

== 3. zadatak ==
Sledeći algoritmi omogućavaju dobijanje različitih kriptografskih ključeva u svakoj TLS razmeni i to takvih da je moguća verifikacija porekla ključeva.
<div class="abc-list" data-solution="multiple">
# <span class="solution">RSA</span>
# <span class="solution">Ephemeral Diffie Hellman</span>
# Anonymous Diffie Hellman
# Fixed Diffie Hellman
</div>

Ovom porukom se potvrđuju kriptografski algoritmi koji će biti korišćeni u toku TLS sesije:
<div class="abc-list" data-solution="single">
# <span class="solution">Server Hello</span>
# Server Hello Done
# Client Hello Done
# Certificate Verify
# Certificate Request
# Finished
# Client Key Exchange
# Client Hello
# Change Cipher Specification
</div>

== 4. zadatak ==
Na slici je prikazan SAML deo poruke tokom autentikacije u okviru federacije identiteta:
<syntaxhighlight lang="xml">
<ds:Signature xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
<ds:SignedInfo>
<ds:CanonicalizationMethod Algoritm="http://www.w3.org/2001/10/xml-exc-c14n#" />
<ds:SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#rsa-sha1" />
<ds:Reference URI="...">
<ds:Transforms>
<ds:Transform Algorithm="http://www.w3.org/2000/09/xmldsig#enveloped-signature" />
<ds:Transform Algorithm="http://www.w3.org/2001/10/xml-exc-c14n#" />
</ds:Transforms>
<ds:DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1" />
<ds:DigestValue>...</ds:DigestValue>
</ds:Reference>
</ds:SignedInfo>
<ds:SignatureValue>...</ds:SignatureValue>
<ds:KeyInfo>
<ds:X509Data>
</syntaxhighlight>
Za ovu poruku je tačno sledeće:
<div class="abc-list" data-solution="single">
# šalje je klijent direktno ka pružaocu identiteta
# šalje je klijent direktno ka pružaocu usluge
# šalje je klijent ka pružaocu usluge preko pružaoca identiteta
# šalje je klijent ka pružaocu identiteta preko pružaoca usluge
# šalje je pružalac identiteta direktno ka klijentu
# šalje je pružalac identiteta direktno ka pružaocu usluge
# šalje je pružalac identiteta ka klijentu preko pružaoca usluge
# <span class="solution">šalje je pružalac identiteta ka pružaocu usluge preko klijenta</span>
# šalje je pružalac usluge direktno ka klijentu
# šalje je pružalac usluge direktno ka pružaocu identiteta
# šalje je pružalac usluge ka pružaocu identiteta preko klijenta
# šalje je pružalac usluge ka klijentu preko pružaoca identiteta
</div>

== 5. zadatak ==
Za IKE razmenu ključeva je tačno sledeće:
<div class="abc-list" data-solution="multiple">
# <span class="solution">Prvo se vrši razmena ključeva pa provera identiteta</span>
# Prvo se vrši provera identiteta pa razmena ključeva
# Ključ dobijen u prvoj fazi IKE razmene se češće menja od ključa dobijenog u drugoj fazi
# U prvoj i drugoj fazi razmene ključeva moraju da se koriste isti kriptografski algoritmi
# <span class="solution">U prvoj i drugoj fazi razmene ključeva mogu da se koriste različiti kriptografski algoritmi</span>
# <span class="solution">Ključ dobijen u drugoj fazi IKE razmene se češće menja od ključa dobijenog u prvoj fazi</span>
</div>

== 6. zadatak ==
Kada korisnik A prebacuje X bitcoin-a korisniku B, korisnik A mora da uradi sledeće:
<div class="abc-list" data-solution="single">
# da enkriptuje blok u kojem je ova transakcija
# da odredi nonce za potvrdu bloka u blockchainu
# <span class="solution">da digitalno potpiše ovu transakciju DSA algoritmom</span>
# da izračuna Merkleovo stablo transakcija
# da enkriptuje ovu transakciju RSA algoritmom
# da enkriptuje ovu transakciju AES algoritmom
</div>

== 7. zadatak ==
Odrediti optimalni poredak operacija u procesu prijema PGP poruke, ukoliko su svi servisi u upotrebi:
<div data-solution="select" data-options="Restauriranje poruke prema originalnom poretku, Skidanje email kompatibilnosti, Dešifrovanje poruke, Obezbeđivanje dekompresije, Provera autentikacije">
# operacija <span class="spoiler">Restauriranje poruke prema originalnom poretku</span>
# operacija <span class="spoiler">Skidanje email kompatibilnosti</span>
# operacija <span class="spoiler">Dešifrovanje poruke</span>
# operacija <span class="spoiler">Obezbeđivanje dekompresije</span>
# operacija <span class="spoiler">Provera autentikacije</span>
</div>
Na slici je data šema PGP upravljanja ključem uz korišćenje poverenja. U korenu hijerarhije se nalazi korisnički čvor. Čvorovi označeni crvenom bojom su čvorovi kojima se u potpunosti veruje da potpisuju druge ključeve, dok su plavom bojom označeni čvorovi kojima se delimično veruje da potpisuju druge ključeve. Konfigurabilni parametri su <code>X = 1</code> i <code>Y = 3</code>.
[[Датотека:ZP jun 2022 zadatak 7 PGP šema.svg|PGP šema uz sedmi zadatak.|frame|center|class=transparent-svg]]

Označiti sve čvorove koji su legitimni.
<div class="abc-list" data-solution="multiple">
# <span class="solution">A</span>
# <span class="solution">B</span>
# <span class="solution">C</span>
# <span class="solution">D</span>
# E
# <span class="solution">F</span>
# <span class="solution">G</span>
# <span class="solution">H</span>
# I
</div>

== 8. zadatak ==
Peđa želi da šifruje poruku '''0246813579BD'''h. Poruka se šifruje primenom CCM moda funkcionisanja. Algoritam enkripcije koje se koristi u šifrovanju radi tako što permutuje heksa cifre ulaznog podatka prema priloženoj permutaciji:
{| class="wikitable"
|+ Permutacija iz osmog zadatka.
| 3 || 5 || 7 || 4 || 6 || 0 || 1 || 2
|}
Blokovi ulaznih podataka koji se koriste za šifrovanje kreirani su po standardnoj šemi. Bajt flegova koji se čuvaju u blokovima ima vrednost '''8B'''h. Nonce ima vrednost '''C0D0'''h. Veličina bloka algoritma enkripcije je 4 bajta. MAC ima vrednost '''E159'''h.

Brojači koji se koriste u šemi kreću od 0.

Odgovoriti na sledeća pitanja. Odgovore davati u heksadecimalnom obliku bez oznake.
<div class="abc-list">
# Koji osnovni mod funkcionisanja se koristi za šifrovanje poruke? (Tačan odgovor nosi 1 poen, netačan odgovor nosi -1 poen, a odgovor "Ne znam" nosi 0 poena) <span class="spoiler" data-solution="text">CTR</span>
# Dati vrednost ulaznog bloka koji se kombinuje sa MAC-om <span class="spoiler" data-solution="text">8BC0D000</span>
# Dati vrednost ulaznih blokova za šifrovanje razdvojenih blanko znakom <span class="spoiler" data-solution="text">8BC0D001 8BC0D002</span>
# Dati vrednost koja se kombinuje sa MAC-om <span class="spoiler" data-solution="text">000D</span>
# Dati vrednost koja se kombinuje sa plaintext-om <span class="spoiler" data-solution="text">001D08BC002D</span>
# Dati vrednost šifrovane poruke <span class="spoiler" data-solution="text">025B89897990</span>
# Dati vrednost celokupne poruke koja se šalje <span class="spoiler" data-solution="text">025B89897990E154</span>
</div>

== 9. zadatak ==
: ''Oblast ovog zadatka se od 2023. godine ne predaje na predmetu i kao takav nije rešen.''
Malina Vojvodić iz Topolske 18 želi da napravi nalog na društvenoj mreži da se poveže sa Feđom da bi ga pozvala na svoj 50. rođendan. Odabrati dobre lozinke za Malinu imajući u vidu da Malina loše pamti i teške lozinke zapisuje na papir:
<div data-solution="multiple">
# maki1972
# ha03AMd"k
# prEduzEtnica44
# 123456
# topolskadama
# _Visnja_011
# m@lin@v
</div>
Na slici je prikazan IBM-ov digitalni imuni sistem. Za svaki od navedenih koraka odrediti akciju koja se u tom koraku sprovodi.
[[Датотека:ZP jun 2022 zadatak 9 digitalni imuni sistem.svg|frame|center|Digitalni imuni sistem iz devetog zadatka.]]
* 3A. korak: <span class="spoiler" data-solution="text">nerešeno</span>
* 3B. korak: <span class="spoiler" data-solution="text">nerešeno</span>
* 3C. korak: <span class="spoiler" data-solution="text">nerešeno</span>
* 6. korak: <span class="spoiler" data-solution="text">nerešeno</span>

== 10. zadatak ==
Za svaki od sledećih scenarija, odrediti o kom malicioznom softveru je reč.
<div class="abc-list" data-solution="select" data-options="logička bomba,zadnja vrata,zombi,keylogger,spamer,flooder,downloader,adware,ransomware">
* Marija je preuzela igricu na svoj računar i odigrala je nekoliko partija. Marijini mejl kontakti su odjednom krenuli da primaju veliku količinu elektronske pošte. Preuzeta igrica predstavlja trojanskog konja koji u sebi sadrži maliciozan softver <span class="spoiler">spamer</span>.
* Petar želi da organizuje DDOS napad i zbog toga je preuzeo kontrolu nad zombi računarima odakle šalje veliku količinu podataka ka određenom servisu na mreži. Maliciozni softver koji šalje ove podatke je <span class="spoiler">flooder</span>.
* Vlada je otvorio mejl i preuzeo priloženu izvršnu datoteku koja je prilikom pokretanja prouzrokovala konekciju na udaljeni server sa kojeg je preuzela i instalirala dodatne zlonamerne programe. Koji softver predstavlja ova izvršna datoteka? <span class="spoiler">downloader</span>.
</div>

[[Категорија:Рокови]]
[[Категорија:Заштита података]]

Системски софтвер

2024-03-16T13:20:58Z

MihailoM342: /* Пројекат */

{{Предмет
| шифра = 13С113СС, 13Е113СС
| семестар = 6, 8 (СИ)
| статус = изборни (СИ), обавезни (РТИ)
| страница = [https://rti.etf.bg.ac.rs/rti/ir3ss/ rti.etf.rs/rti/ir3ss]
| одсек = СИ, РТИ
}}
У овом снимку ћемо се упознати са '''Системским софтвером''', изборним предметом у шестом семестру на СИ, и обавезним на РТИ.

== Корисне везе ==
* [http://si3ss.etf.bg.ac.rs/ Стара страница предмета] (рокови)
* [https://godbolt.org/ ''Compiler Explorer''] (користан алат при вежбању задатака из декомпилације за први колоквијум)
* [https://drive.google.com/open?id=19796xkLX-qDMEAh9-4a5yi-8cdX_9t3G ETF SI] (рокови, белешке)
* [https://app.box.com/s/0r50je333z1qyypz0h3rm0iqb9s0d64f/folder/17683025696 ETF Materijali (Box)] (рокови, наставни материјал, белешке)

== Настава ==
Највећи део градива се обрађује на вежбама и на испите и колоквијуме/лабораторијску вежбу долазе задаци са вежби. Самим тим, предавања нису нарочитно битна, осим у првом делу када се обрађује архитектура ''x86''. На предавањима се обрађују:
* Асемблер, репрезентација типова, врсте ''x86'' асемблерских инструкција, кодови услова, сет инструкције, програмски скокови, петље, позивање потпрограма и стек оквири.
* ГНУ алати, развој програма уз помоћ ''GDB'' дебагера.
* Конструкција асемблера, двопролазни и једнопролазни асемблер.
* Линкери, релокације, статичке библиотеке, ''ELF'' формат, пуниоци, дељене библиотеке, ''PIE''.
* Емулатори, интерпретативни емулатори, статичка и динамичка рекомпилација, ''JIT'' превођење.
* Макропроцесори, ''C'' претпроцесор.
Предавања се претходних пар година нису одржавала уживо и самим тим распоред градива се не слаже са вежбама и колоквијумима.

== Пројекат ==
Пројекат из Системског софтвера је обавезан и састоји се од 3 програма који чине заједнички скуп алата за развој софтвера на апстрактном рачунарском систему. Програми су редом асемблер, линкер и емулатор. Оцењивање се дели на 3 нивоа:
* Ниво А који носи 30 поена
* Ниво Б који носи 35 поена и
* Ниво Ц који носи 40 поена.
У сваком нивоу је неопходно развити сва 3 програма и нивои изнад А садрже додатне функционалности. Поставка се објављује на ''Moodle'' платформи.

Тражени језик за развој пројекта је C/C++. Препоручено окружење за развој је ''Visual Studio Code'' на ''Ubuntu'' виртуелној машини која је доступна на ''Moodle'' платформи. За контролу генерисања кода препоручен је ''GNU make''. Дозвољено је користити спољашње библиотеке које не имплементирају срж пројекта (генерисање кода, повезивање, релоцирање, емулација и сл.), али није препоручено јер је можда неопходно инсталирати њих на вирутелну машину за одбрану, а то захтева дозволу предметног асистента на самој одбрани.

Пројекат се тестира помоћу јавних тестова (доступни на ''Moodle'' курсу предмета), који се покрећу за жељени ниво и све ниже нивое (могуће је уз одобрење асистента спустити ниво на одбрани). Поред покретања јавних тестова, одбрану чини и модификација која се тестира тајним тестовима. Потребно је да сви тестови раде како би одбрана пројекта била успешна.

== Лабораторијске вежбе ==
Лабораторијска вежба се одржава само на РТИ одсеку, и еквивалентна је првом колоквијуму на СИ одсеку.

== Испитни рокови ==
Стари испитни рокови могу се пронаћи на старој страници предмета, у [[#Корисне везе|одељку за корисне везе]]. Нови испитни рокови нису доступни са странице предмета, али се могу наћи на неком од драјвова у истом том одељку. Званична решења се не објављују.

Пре првог колоквијума обично изађу пробни тестови за теорију и задатак. Тренутно су доступни [[Системски софтвер/Пробни тестови 2022|пробни тестови 2022. године]].

Следећи рокови су сакупљени на {{SITENAME}}:
{{#dpl:
| category = Системски софтвер
| category = Рокови
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦19¦-1}²]],,
| noresultsheader = Тренутно нема рокова.
}}
Уколико желите да додате рок, посетите '''[[Project:Направи|страницу за прављење рока]]'''.

== Начин оцењивања ==
* <math>K_1</math> — бодови са првог колоквијума, има један термин за надокнаду или поправку (0-20)
* <math>K_2</math> — бодови са другог колоквијума, надокнађује се у оквиру испита (0-20)
* <math>Pr</math> — бодови са пројектног задатка (0-40)
* <math>I</math> — бодови са испита, услов за излазак је преко 30 бодова на пројектном задатку и првом колоквијуму
* Коначни бодови: <math>P = K_1 + Pr + max\left(K_2 + \frac{I}{2}, I\right)</math>
{| class="wikitable"
! Бодови
| <math>P \leq 50</math> || <math>50 < P \leq 60</math> || <math>60 < P \leq 70</math> || <math>70 < P \leq 80</math> || <math>80 < P \leq 90</math> || <math>90 < P</math>
|-
! Оцена
| 5 || 6 || 7 || 8 || 9 || 10
|}

== Потребна помоћ ==
* {{задаци|postavke}}
* {{задаци|rešenja}}
* Од користи би био водич за први колоквијум, са објашњењима како се одређене структуре у C могу пресликати у асемблер.

КДП/Фебруар 2024

2024-02-12T19:59:08Z

MihailoM342: /* Решење */

{{tocright}}
{{нерешено}}

== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објаснити ''Test and set'' решење за критичну секцију (''coarse grain'' и ''fine grain''). Дати решење за смањење инвалидације кеш меморија у том случају.
=== Решење ===

== {{категорија|2. задатак|Региони}} ==
=== Поставка ===
Користећи условне критичне регионе написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Није потребно оптимизовати пут лифта и путника.
=== Решење ===

== {{категорија|3. задатак|Активни_монитори}} ==
=== Поставка ===
Решити проблем читалаца и писаца (''Readers-Writers problem'') користећи активне мониторе. Обезбедити да процес који је пре упутио захтев за приступ ресурсу пре треба да буде опслужен.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N = ...; //broj citalaca + broj pisaca
chan s(int, int); //id, op
chan r[N](int, int);

// 0 - start read
// 1 - end read
// 2 - start write
// 3 - end write

void reader(int id) {
bool status;
while(true) {
send s(id, 0);
receive r[id](status);
//read
send s(id, 1);
receive r[id](status);
}
}

void writer(int id) {
bool status;
while(true) {
send s(id, 2);
receive r[id](status);
//write
send s(id, 3);
receive r[id](status);
}
}

void monitor() {
int id, op, numR = 0;
queue buffer(int, int);

while(true) {
if(buffer.isNotEmpty()) id, op = buffer.get();
else receive s(id, op);

if(op == 0) {
numR++;
send r[id](true);
} else if(op == 1) {
numR--;
send r[id](true);
} else if(op == 2) {
int id2, op2;
while(numR > 0) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 1) {
numR--;
send r[id2](true);
}
}
send r[id](true);
while(true) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 3) {
send r[id2](true);
break;
}
}
}
}
}
</syntaxhighlight>

== {{категорија|4. задатак|CSP}} ==
=== Поставка ===
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.
=== Решење ===



[[Категорија:Рокови]]
[[Категорија:КДП]]

КДП/Фебруар 2024

2024-02-12T19:58:16Z

MihailoM342: /* {{категорија|3. задатак|Активни_монитори}} */

{{tocright}}
{{нерешено}}

== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објаснити ''Test and set'' решење за критичну секцију (''coarse grain'' и ''fine grain''). Дати решење за смањење инвалидације кеш меморија у том случају.
=== Решење ===

== {{категорија|2. задатак|Региони}} ==
=== Поставка ===
Користећи условне критичне регионе написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Није потребно оптимизовати пут лифта и путника.
=== Решење ===

== {{категорија|3. задатак|Активни_монитори}} ==
=== Поставка ===
Решити проблем читалаца и писаца (''Readers-Writers problem'') користећи активне мониторе. Обезбедити да процес који је пре упутио захтев за приступ ресурсу пре треба да буде опслужен.

=== Решење ===
const int N = ...; //broj citalaca + broj pisaca
chan s(int, int); //id, op
chan r[N](int, int);

// 0 - start read
// 1 - end read
// 2 - start write
// 3 - end write

void reader(int id) {
bool status;
while(true) {
send s(id, 0);
receive r[id](status);
//read
send s(id, 1);
receive r[id](status);
}
}

void writer(int id) {
bool status;
while(true) {
send s(id, 2);
receive r[id](status);
//write
send s(id, 3);
receive r[id](status);
}
}

void monitor() {
int id, op, numR = 0;
queue buffer(int, int);

while(true) {
if(buffer.isNotEmpty()) id, op = buffer.get();
else receive s(id, op);

if(op == 0) {
numR++;
send r[id](true);
} else if(op == 1) {
numR--;
send r[id](true);
} else if(op == 2) {
int id2, op2;
while(numR > 0) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 1) {
numR--;
send r[id2](true);
}
}
send r[id](true);
while(true) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 3) {
send r[id2](true);
break;
}
}
}
}
}

== {{категорија|4. задатак|CSP}} ==
=== Поставка ===
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.
=== Решење ===



[[Категорија:Рокови]]
[[Категорија:КДП]]

КДП/Фебруар 2024

2024-02-12T19:57:10Z

MihailoM342: /* Решење */

{{tocright}}
{{нерешено}}

== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објаснити ''Test and set'' решење за критичну секцију (''coarse grain'' и ''fine grain''). Дати решење за смањење инвалидације кеш меморија у том случају.
=== Решење ===

== {{категорија|2. задатак|Региони}} ==
=== Поставка ===
Користећи условне критичне регионе написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Није потребно оптимизовати пут лифта и путника.
=== Решење ===

== {{категорија|3. задатак|Активни_монитори}} ==
=== Поставка ===
Решити проблем читалаца и писаца (''Readers-Writers problem'') користећи активне мониторе. Обезбедити да процес који је пре упутио захтев за приступ ресурсу пре треба да буде опслужен.
const int N = ...; //broj citalaca + broj pisaca
chan s(int, int); //id, op
chan r[N](int, int);

// 0 - start read
// 1 - end read
// 2 - start write
// 3 - end write

void reader(int id) {
bool status;
while(true) {
send s(id, 0);
receive r[id](status);
//read
send s(id, 1);
receive r[id](status);
}
}

void writer(int id) {
bool status;
while(true) {
send s(id, 2);
receive r[id](status);
//write
send s(id, 3);
receive r[id](status);
}
}

void monitor() {
int id, op, numR = 0;
queue buffer(int, int);

while(true) {
if(buffer.isNotEmpty()) id, op = buffer.get();
else receive s(id, op);

if(op == 0) {
numR++;
send r[id](true);
} else if(op == 1) {
numR--;
send r[id](true);
} else if(op == 2) {
int id2, op2;
while(numR > 0) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 1) {
numR--;
send r[id2](true);
}
}
send r[id](true);
while(true) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 3) {
send r[id2](true);
break;
}
}
}
}
}

== {{категорија|4. задатак|CSP}} ==
=== Поставка ===
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.
=== Решење ===



[[Категорија:Рокови]]
[[Категорија:КДП]]

КДП/Фебруар 2024

2024-02-12T19:55:01Z

MihailoM342: /* Решење */

{{tocright}}
{{нерешено}}

== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објаснити ''Test and set'' решење за критичну секцију (''coarse grain'' и ''fine grain''). Дати решење за смањење инвалидације кеш меморија у том случају.
=== Решење ===

== {{категорија|2. задатак|Региони}} ==
=== Поставка ===
Користећи условне критичне регионе написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Није потребно оптимизовати пут лифта и путника.
=== Решење ===

== {{категорија|3. задатак|Активни_монитори}} ==
=== Поставка ===
Решити проблем читалаца и писаца (''Readers-Writers problem'') користећи активне мониторе. Обезбедити да процес који је пре упутио захтев за приступ ресурсу пре треба да буде опслужен.
=== Решење ===
const int N = ...; //broj citalaca + broj pisaca
chan s(int, int); //id, op
chan r[N](int, int);

// 0 - start read
// 1 - end read
// 2 - start write
// 3 - end write

void reader(int id) {
bool status;
while(true) {
send s(id, 0);
receive r[id](status);
//read
send s(id, 1);
receive r[id](status);
}
}

void writer(int id) {
bool status;
while(true) {
send s(id, 2);
receive r[id](status);
//write
send s(id, 3);
receive r[id](status);
}
}

void monitor() {
int id, op, numR = 0;
queue buffer(int, int);

while(true) {
if(buffer.isNotEmpty()) id, op = buffer.get();
else receive s(id, op);

if(op == 0) {
numR++;
send r[id](true);
} else if(op == 1) {
numR--;
send r[id](true);
} else if(op == 2) {
int id2, op2;
while(numR > 0) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 1) {
numR--;
send r[id2](true);
}
}
send r[id](true);
while(true) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 3) {
send r[id2](true);
break;
}
}
}
}
}

== {{категорија|4. задатак|CSP}} ==
=== Поставка ===
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.
=== Решење ===



[[Категорија:Рокови]]
[[Категорија:КДП]]