# Lista 4

###### tags: `sju21` `ćwiczenia`

<small>**Uwaga!** Zadanie 5 jest za 2 punkty.</small>

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie w trakcie dyskusji (co najwyżej jedno!) oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 4-1 | 4-2 | 4-3 | 4-4 |4-5(2)|
| ---------------------:| --- | --- | --- | --- | --- |
| Jacek Bizub | X | X | X | X |==X==| 6
| Wojciech Jasiński | X | X | X | X | | 4
| Artur Juraszek | | X | | | X | 3
| Michał Myczkowski | X | | | |==X==| 3
| Michał Odorczuk |==X==| X | X | X | X | 6
| Damian Ratajski | | | | | | 0
| Łukasz Siudek | | | | | | 0
| Błażej Sowa | X | X | | X. |==X==| 5
| Andrzej Turko | X |==X==| | X | X | 5
| Maksymilian Zawartko | X | X | X | X | | 4
:::

## Zadanie 4-1

:::success
Autor: Michał Odorczuk
:::

Na podstawie strony [Memory Management](https://freertos.org/a00111.html) wyjaśnij ogranicznia poszczególnych manadżerów pamięci sterty systemu FreeRTOS.

* heap_1 - the very simplest, does not permit memory to be freed.
* heap_2 - permits memory to be freed, but does not coalescence adjacent free blocks.
* heap_3 - simply wraps the standard malloc() and free() for thread safety.
* heap_4 - coalescences adjacent free blocks to avoid fragmentation. Includes absolute address placement option.
* heap_5 - as per heap_4, with the ability to span the heap across multiple non-adjacent memory areas.

Czemu autorzy dokumentacji odnoszą się z rezerwą do dynamicznego zarządzania pamięci w systemach czasu rzeczywistego?

* they are not always available on embedded systems,
* they take up valuable code space,
* they are not thread safe, and
* they are not deterministic (the amount of time taken to execute the function will differ from call to call)!!!

Podaj scenariusze użycia dynamicznego przydziału pamięci uzasadniające wybór dostępny wybór algorytmów zaimplementowanych w plikach «heap_?.c».

* heap_1.c - brak zwalniania pamięci, wymagana oszczędność kodu lub wymagana szybko alokacja w deterministycznym czasie
* heap_2.c - zwolnienia pamięci, ale pamięć realokowana jest tego samego rozmiaru, nie powodując defragmentacji
* heap_3.c - jeżeli malloc i free są już podlinkowane/ nie boli nas podlinkowanie ich - zwiększenie rozmiaru kodu jądra, nie mamy potrzeby ograniczenia sterty
* heap_4.c - dowolny przypadek, kiedy dochodzi do alokacji i zwolnień obszarów o różnych rozmiarach, ale wszystko mieści się w jednym bloku pamięci, a nie ma potrzeby oszczędzania na kodzie
* heap_5.c - programy wymagające wielkich obszarów pamięci, mające małe szanse na zmieszczenie się w jednym, ciągłym bloku

>[name=Michał Myczkowski - pytanie]
:::spoiler
Czy heap_3.c jest wrapperem [tej implementacji](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/libc/stdlib/malloc.c?r=b1dad820)?
:::

## Zadanie 4-2

:::info
Autor: Artur Juraszek
:::

[xTaskNofifyWait](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/tasks.c?r=9f4d3da8#4703)

if( pxCurrentTCB->ucNotifyState != taskNOTIFICATION_RECEIVED )

^Możliwe, że na zadanie czeka już pewne nieodebrane powiadomienie.
W takim przypadku odbieramy je od razu, bez zbędnego blokowania.

W przeciwnym wypadku:

Zgodnie z przekazanym w argumencie wywołania życzeniem zerujemy odpowiednie
bity w 32-bitowym słowie przechowującym wartość powiadomienia...:

pxCurrentTCB->ulNotifiedValue &= ~ulBitsToClearOnEntry;

...oraz oznaczamy zadanie jako oczekujące na zostanie powiadomionym:

pxCurrentTCB->ucNotifyState = taskWAITING_NOTIFICATION;

Jeśli w wywołaniu określono jakiś czas oczekiwania, to blokujemy zadanie i zmieniamy kontekst:

prvAddCurrentTaskToDelayedList( xTicksToWait, pdTRUE );
...
portYIELD_WITHIN_API();

Jeśli nie, to trudno - może będziemy mieli szczęście i powiadomienie nadejdzie akurat wtedy, gdy na chwilę odblokujemy przerwania:

taskEXIT_CRITICAL();

taskENTER_CRITICAL();

Po odblokowaniu (o ile zablokowanie miało miejsce) zadania, czy to na skutek timeoutu, czy nadejścia powiadomienia umieszczamy jego wartość niekoniecznie różną od początkowej) pod przekazanym w argumencie adresem:

*pulNotificationValue = pxCurrentTCB->ulNotifiedValue;

Następnie, w zależności od tego czy powiadomienie nastąpiło (zarówno w czasie zablokowania zadania jak i przed wywołaniem tej funkcji) ustawiamy zwracaną przez funkcję wartość.
Bity w słowie określającym wartość powiadomienia zerujemy jedynie wtedy, gdy faktycznie miało ono miejsce!

if( pxCurrentTCB->ucNotifyState != taskNOTIFICATION_RECEIVED )
{
	xReturn = pdFALSE;
}
else
{
	pxCurrentTCB->ulNotifiedValue &= ~ulBitsToClearOnExit;
	xReturn = pdTRUE;
}

Na koniec wyłączamy stan oczekiwania na powiadomienie:

pxCurrentTCB->ucNotifyState = taskNOT_WAITING_NOTIFICATION;

[xTaskGenericNotify](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/tasks.c?r=9f4d3da8#4783)

Upewniamy się, czy task nie próbuje powiadomić samego siebie:

configASSERT( xTaskToNotify );

Do przekazanego w wywołaniu adresu zapisujemy poprzednią wartość powiadomienia zadania-adresata:

*pulPreviousNotificationValue = pxTCB->ulNotifiedValue;

Zostawiamy adresatowi awizo:

pxTCB->ucNotifyState = taskNOTIFICATION_RECEIVED;

[Wykonujemy odpowiednią akcję na wartości powiadomienia](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/tasks.c?r=9f4d3da8#4803)

Jeśli adresat jest obecnie zablokowany i czeka na nadejście powiadomienia budzimy go, t.j. umieszczamy na liście zadań w stanie Ready:

https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/tasks.c?r=9f4d3da8#4847

Jeśli priorytet przypisany odbiorcy jest wyższy niż zadania-nadawcy, to dokonujemy wywłaszczenia:

https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/tasks.c?r=9f4d3da8#4871

## Zadanie 4-3

:::info
Autor: Wojciech Jasiński
:::
* Przedstaw uczestnikom zajęć proces tworzenia kolejki przy pomocy [xQueueCreate](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/include/queue.h#xQueueCreate). Wyjaśnij znaczenie poszczególnych pól struktury [QueueDefinition](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c#QueueDefinition).
- `xQueueCreate`
- 379..390: alokujemy pamięć (`pvPortMalloc`)
- [408](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#408): [prvInitialiseNewQueue](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#prvInitialiseNewQueue): inicjalizujemy podstawowe pola
- [446](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#446): [xQueueGenericReset](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#xQueueGenericReset)
- inicjalizujemy pozostałe pola
- 270: (przypadek kiedy nie kolejka nie jest świeżo utworzona)
- 293: (kiedy kolejka jest nowa)
- inicjalizujemy listy `xTasksWaitingToSend`, `xTasksWaitingToReceive`
* Zaprezentuj działanie procedur [xQueueSend](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/include/queue.h#xQueueSend) i [xQueueReceive](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c#xQueueReceive) w optymistycznym scenariuszu, tj. mamy odpowiednio co najmniej jedno wolne / używane miejce w kolejce.
- `xQueueSend`
- sekcja krytyczna:
- [767](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#767): sprawdzamy, że jest miejsce (albo nadpisujemy)
- 771..830: obsługa dla `configUSE_QUEUE_SETS`
- [833](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#833): [prvCopyDataToQueue](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#prvCopyDataToQueue): kopiujemy element gdzie trzeba
- 837..850: jeśli wątek czeka na kolejce, to odblokowujemy go (i potencjalnie oddajemy sterowanie)
- `xQueueReceive`
- sekcja krytyczna:
- [1309](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#1309): sprawdzamy, że jest jakiś komunikat do odebrania
- 1312: kopiujemy komunikat
- aktualizujemy liczniki kolejki
- wybudź potencjalne wątki czekające na zapis do kolejki (`xTasksWaitingToSend`)
* Następnie w obu przypadkach przejdź przez wariant blokujący, tj. `xTicksToWait` jest niezerowe i odpowiednio mamy pełną / pustą kolejkę
- `xQueueSend`
- 759: pętlimy się:
- 761: w sekcji krytycznej sprawdzamy miejsce w kolejce i zapisujemy czas
- 902: wyłączamy scheduler, blokujemy kolejkę
- 906: sprawdzamy, czy czas oczekiwania już minął
- TAK: odblokuj wszystko, zwróć błąd
- NIE: sprawdź, czy kolejka jest pełna:
- NIE: wracamy do początku pętli 759
- TAK:
- zapisujemy się na `pxQueue->xTasksWaitingToSend`
- odblokowujemy kolejkę
- wznawiamy scheduler
- `xQueueReceive`
- 1301: pętlimy się
- w sekcji krytycznej sprawdzamy, czy jest komunikat i zapisujemy aktualny czas
- 1367: wyłączamy scheduler, blokujemy kolejkę
- sprawdzamy, czy czas oczekiwania już minął
- TAK: odblokuj, wyjdź z błędem
- NIE: sprawdzamy, czy kolejka jest niepusta:
- TAK: wróć do początku pętli
- NIE:
- zapisz się na `xTasksWaitingToReceive`
- odblokuj rzeczy
- oddaj sterowanie
* Jaką rolę pełni funkcja [prvUnlockQueue](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#prvUnlockQueue)?
W trakcie operacji na kolejce może odezwać się przerwanie i także operować na tej samej kolejce. Jeśli kolejka jest zablokowana, to znaczy, że jakieś zadanie mogło się dobierać do list zadań czekających na kolejkę. Z ISR (interrupt service routine) nie możemy wtedy ich modyfikować - dlatego tylko modyfikujemy liczniki, a listy poprawimy w `prvUnlockQueue` w zadaniu, które (kiedyś) odblokuje kolejkę.

## Zadanie 4-4

:::info
Autor: Andrzej Turko
:::

**muteks** -- prymityw synchronizacyjny służący do obsługi zasobu, z którego może korzystać tylko jeden wątek/proces.
Podobne zastosowanie ma **semafor binarny**, ale on nie ma **dziedziczenia priorytetów**, czyli proces będący w sekcji krytycznej nie odziedziczy wyższego priorytetu po procesie uczekującym na to, aż ten pierwszy opuści sekcję krytyczną. Wobec tego semafor nie pamięta też, kto jest w sekcji krytycznej, podczas gdy mutex tak.

[xSemaphoreCreateMutex](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#496)
1. Tworzymy kolejkę o długości 1 i rozmiarze elementu 0
2. Ustawiamy wskaźnik na właściciela na NULL.
3. Dodajemy jeden element na kolejkę (mutex jest "otwarty")

[xSemaphoreCreateBinary](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/include/semphr.h?r=f635f9c7#162)
1. Tworzymy kolejkę długości 1 i rozmiarze elementu 0 -- zwracamy handle pustego (zajętego) semafora.

[xQueueSemaphoreTake](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#1418)
Jeżeli jest wolny:
1. Bierzemy mutex i zapisujemy się jako mutex holder
2. Wracamy z procedury
Jeżeli mutex jest zajęty:
1. Jeśli timeout == 0, wracamy z błędem
2. Niech właściciel mutexa odziedziczy priorytet.
3. Jeżeli jeszcze nie minał nasz czas blokowania: usypiamy zadanie w oczekiwaniu na mutex (ew. timeout).
4. Jeżeli minął, a mutex holder odziedziczył priorytet, wydziedziczamy go.

[xSemaphoreGive](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/include/semphr.h?r=f635f9c7#xSemaphoreGive)
Dodawanie elementu do kolejki: [xQueueGenericSend](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#833)
1. Dodajemy element do kolejki [prvCopyDataToQueue](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/queue.c?r=9f4d3da8#2074):
* Wydziedziczamy zadanie, które trzyma mutex (obecne).
* Ustawiamy mutex holder na NULL
2. Jeśli jakieś zadanie o wyższym piorytecie zablokowało się na kolejce, oddajemy sterowanie.

Dziedziczenie priorytetów:
* [xTaskPriorityInherit](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/tasks.c?r=9f4d3da8&fi=xTaskPriorityInherit#xTaskPriorityInherit): przekaż priorytet obecnego zadania mutex holderowi. Jeśli obecny priorytet mutex holdera jest mniejszy niż obecnego zadania:
1. Zmieniamy pozycje mutex holdera na listach eventów i ready.
2. Zmieniamy jego priorytet
* [xTaskPriorityDisinherit](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/FreeRTOS/tasks.c?r=9f4d3da8&fi=xTaskPriorityDisinherit#xTaskPriorityDisinherit): jeśli zadanie nie trzyma już żadnych muteksów:
1. zmnieniamy (zmniejszamy) jego priorytet
2. uaktualniamy miejsce w kolejce ready
3. zgłaszamy konieczność oddania sterowania

## Zadanie 4-5

:::info
Autor: Błażej Sowa
:::

static void vRtcTask(__unused void *data) {
  TickType_t xWakeTime;
  xTaskNotifyWait(0, 0, &xWakeTime, portMAX_DELAY);
  // W xWakeTime dostaliśmy numer pierwszego taktu zegara systemowego, w którym
  // zauważyliśmy zmianę wartości sekund zegara RTC

  klog("First time received at %d ticks\n", xWakeTime);

  for (;;) {
    // Pobieramy aktualny czas z RTC
    taskENTER_CRITICAL();
    const struct msm6242b currentTime = msm6242b;
    taskEXIT_CRITICAL();

    // Wypisujemy sformatowany czas
    klog("%d%d-%d%d-%d%d %d%d-%d%d-%d%d\n", currentTime.day1, currentTime.day2,
         currentTime.month1, currentTime.month2, currentTime.year1 % 10,
         currentTime.year2, currentTime.hour1, currentTime.hour2,
         currentTime.minute1, currentTime.minute2, currentTime.second1,
         currentTime.second2);

    // Usypiamy zadanie aż do taktu zegara systemowego
    // o numerze xWakeTime + "liczba taktów zegara na sekundę"
    vTaskDelayUntil(&xWakeTime, configTICK_RATE_HZ);
    // Funkcja zmieni wartość xWakeTime na takt zegara, w którym zadanie zostało
    // miało być wybudzone
  }
}

static xTaskHandle rtcTaskHandle;
static bool firstTimeReceived = false;
static bool initialTimeReceived = false;
static struct msm6242b initialTime;

static void SystemClockTickHandler(__unused void *data) {
  /* Increment the system timer value and possibly preempt. */
  uint32_t ulSavedInterruptMask = portSET_INTERRUPT_MASK_FROM_ISR();
  xNeedRescheduleTask = xTaskIncrementTick();

  if (!firstTimeReceived) {
    if (!initialTimeReceived) {
      initialTime = msm6242b;
      initialTimeReceived = true;
    } else {
      const struct msm6242b newTime = msm6242b;

      // Sprawdzamy czy czas zmienil się od odstatniego taktu
      // Wystarczy sprawdzić tylko cyfry jedności sekund
      if (initialTime.second2 != newTime.second2) {
        // Wysyłamy powiadomienie do zadania, przekazując w NotifyValue aktualny
        // numer taktu zegara
        BaseType_t higherPriorityTaskWoken;
        xTaskNotifyFromISR(rtcTaskHandle, xTaskGetTickCountFromISR(),
                           eSetValueWithOverwrite, &higherPriorityTaskWoken);
        firstTimeReceived = true;

        // Jeśli powiadomienie wybudziło zadanie o najwyższym priorytecie,
        // chcemy zmienić kontekst
        if (higherPriorityTaskWoken == pdTRUE) {
          xNeedRescheduleTask = pdTRUE;
        }
      }
    }
  }

  portCLEAR_INTERRUPT_MASK_FROM_ISR(ulSavedInterruptMask);
}

INTSERVER_DEFINE(SystemClockTick, 10, SystemClockTickHandler, NULL);

int main(void) {
  portNOP();

  AddIntServer(VertBlankChain, SystemClockTick);
  xTaskCreate(vRtcTask, "rtctask", configMINIMAL_STACK_SIZE, NULL, 3,
              &rtcTaskHandle);
  vTaskStartScheduler();
  return 0;
}