Exam notes

TE 3 - Algos.md

Vocabulaire

• Graphe connexe pas d'éléments non-reliés
• Graphe acyclique sans cycle
• Graphe complet tous les arcs possibles
• Graphe bipartite 2 sous-graphes non-reliés entre eux
• Arc avant, arrière arc qui remont/redescent
• Arc transversal qui va à un autre arbre
• Ensemble de sommets fortement connexe si il y a tous les arcs possible
• DAG graphe dirigé acyclique
• Condensation DAG obtenu après avoir contracté les composantes fortements connexes
• Tournoi chaque paire de somment relié par un seul arc
• Suite de score d'un tournoi est la liste triée du nombre d'arcs sortant de chaque sommet
• Chemin eurélien visite chaque arc une seul fois
• Chemin amiltonien visite chaque noeud une seul fois
• k-clique sous-ensemble de sommets tous reliés entre eux
• Independent set sous-ensemble de sommet sans arrêtes en commun
• Matching sous-ensemble d'arrêtes sans somments en commun
• Graphe résiduel graphe de base soustrait au graphe de flux
• Graphe de flux on y met les chemins trouvés grâce au graphe résiduel

TE 3 - Systèmes embarqués.md

Intefaçage C

Le passage de paramètres se fait par les registres r0-r3 puis à l'aide de la pile.

Rappel :

• R0-R12, variable register
• R13, SP
• R14, LR
• R15, PC

Pour passer des paramètres à l'aide de la pile :

main: sub sp, #4 @réserve l’espace sur la pile
      ldr r0,=val
      str r0,[sp, #0] @place le paramètre sur la pile
      bl subroutine
      add sp, #4 @restaure la pile
subroutine: 
      ...
      ldr r0, [sp, #0] @prend la valeur du paramètre
      ...
      bx lr

Avant d'utiliser les registres, une sous-routine doit en sauvegarder l'état :

stmfd sp!,{r4-r8,lr}  // sauvegarde ! push {r4-r8,lr}
ldmfd sp!,{r4-r8,pc}^ // restauration ! pop {r4-r8,pc} 

Pour les processeurs ARM, les 5e et suivantes variables sont placées dans la pile de la dernière à la première :

• var5 <- new SP
• var6
• var7
• var8
• [some stuf] <- old SP

Si on utilise le FP (alias frame pointer), celui-ci pointera sur le lr :

• registres sauvegardés <- SP
• fp
• lr <- FP
• paramètres passés au sous-programme

Pour qu'une routine soit réentrante :

• Ne doit pas utiliser de données statiques (globales) non-constantes
• Ne doit retourner l’adresse de données statiques (globales) non-constantes
• Ne doit traiter que des données fournies par le programme appelant
• Ne doit pas reposer sur des verrous de ressources singleton
• Ne doit pas modifier son propre code
• Ne doit pas appeler des sous-programmes non-réentrants

Déclarer les routines assembleur (en C):

extern long fonction0(long,long);
extern long fonction1(long);
extern long fonction2(long, long, long);

En assembleur :

.global fonction0
.global fonction1
.global fonction2

fonction0:
      nop
      swi #0
      bx lr
fonction1:
      nop
      swi #1
      bx lr
fonction2:
      nop
      swi #2
      bx lr
      
swi_handler:
      stmfd SP!, {r0-12,lr}
      ldr r0, [lr, #-4]  # charge la valeure du swi
      add r0, 0x00ffffff # clear les 8 premiers bits
      cmp r0, #0
      beq fonction0
      cmp r0, #1
      beq fonction1
      cmp r0, #2
      beq fonction2
      ldmfd SP!, {r0-12,PC}^

Interruptions

Séquence d'interruption.
Depuis le GPIO, si une interruption logicielle arrive :

• le GPIO détermine sa provenance et la transmet à l'AITC
• si l'interruption est assez prioritaire l'AITC va transmettre l'interruption via IRQ au µp
• le µp va ensuite appeler la routine attachée au vecteur de l'interruption donnée
• l'isr de l'AITC check la provenace et appel l'isr du GPIO
• le GPIO check l'origine de l'interruption et appel la routine IRQ du périphérique

Types d'interruptions

• logicielle (swi, sofware interrupt)
• matérielle
• exception

Tables de vecteurs
Pour trouver la routine associée à une interruption, le µp ARM a :

• en mémoire, un endroit fixe qui renvoie à une case mémoire écrivable
• dans cet endroit, on inscrit l'adresse d'une routine
• lors d'une interruption, le µp ira appelé la routine grâce à son adresse qu'on aura rentré

Changer de mode

Pour désactiver les IRQ/FIQ

• Changer dans le PSR les 2 flag qui permettent de spécifier si à 1 FIQ/IRQ désactivé

Identifier l'état du processeur et de la pile lors du traitement d'une interruption
L'état du processeur est donné par le CPSR

Utiliser correctement les pointeurs de pile dans les différents modes
Il faut changer de mode pour accéder aux différents registres spécifiques.

Commutation de context, gigue
Commutation de context : Sauvegarde et rétablissement des registres du µp afin que ceux-ci ne soient pas altérés par l'écexution d'une autre série d'instruction
Lantence : temps entre le déclenchement d'une interruption et l'execution de sa routine
Gigue : variation de la latence

Système d'interruption des processeurs ARM, i.MX27

• µp : interruptions vectorisées grâce aux 2 ligne IRQ/FIQ, elles sont priorisée donc
• AITC : interruption vectorisée et priorisées (64)
• GPIO : détection par polling (192)

Activation/désactivation des interruptions matériels

Niveaux de priorités des interruptions

Procédure de reconnaisance d'interruptions multiples

• Polling
• priority
• Vectors

Entrées/Sorties

Concept général

Mode et techniques pour piloter des IO
Mode par scrutation :

• le µp check périodiquement
• si le buffer d'émission n'est pas plein on écrir
• si le buffer de réception n'est pas vide, on lit

Mode avec interruption :

• le périphérique génère une interruption quand il envoie des données ou est prêt à en recevoir
• le µp écrit ou lit si une interruption est levée

Calculer la taille des tampons d'émission et de réception

Système d'exploitation

Types de systèmes multitâche

• coopératif, chaque doit donner la main à une autre tâche
• préemptif, le processeur signal au système d'exploitation de commuter le processus en cours pour un autre

Composantes d'un noyau (7)

• Processus/thread
• Scheduler
• Timer
• Interruption
• Gestionnaire mémoire
• Mécanisme de synchro (sémaphore)
• Mécanisme d'échange d'informations

Eléments et structures nécessaire à la gestion d'un thread
Il est surtout important d'avoir la pile spécifique du thread, son TCB (thread control block)

Commutation de context entre 2 threads

• Sauvegarde le thread actuel dans son TCB (thread control block)
• Switch du TCP actuel au TCP du prochain thread
• Restaure le context du thread à partir du tcb

Algorithme de transfert de context entre 2 thread

// r0 current tcb
// r1 psr
// r2 new tcb
kernel_transfer:
      nop
      stmia r0, {r0­r12,sp,lr} // Sauve les registres
      str r1, [r0, #15*4]     // Sauve le PSR du thread
      ldr r1, [r2, #15*4]     // Charge le new PSR
      msr spsr_cxsf, r1       // Restaure le PSR
      ldmia r2, {r0­r12,sp,pc}^ // Restaure les reg

Initialisation du context d'un thread
Pour initialiser un thread, il faut mettre dans son TCB :

• r0, paramètre du thread
• r1, adresse de la routine du thread
• r2-12, initialisé à 0
• r13 SP, le fond de la pile
• r14 LR, la routine d'initialisation des threads
• r15 PC ???? on pourrait pas mettre directement l'adress du thread
• PSR, selon le mode de fonctionnement nécessaire