\thumb

\sectionnn{Architecture matérielle}

\begin{qcm}{Sur les SoCs}{5}
\label{exo:08-soc1}
\enlargethispage*{\baselineskip}
Pour chacune des questions suivantes, plusieurs propositions de réponses sont faites dont une seule est réellement pertinente. Laquelle ?

\begin{questions}
\item Un Soc est:

\choix Une puce électronique;

\choix Une sorte de micro-ordinateur sur une puce électronique;

\choix Un système d'exploitation sur une puce électronique;

\choix Une mémoire intégrée à une puce électronique.


%%%

\item La fluidité d'une vidéo sur un appareil à SoC dépend avant tout:\resetchoix

\choix de la mémoire embarquée dans le SoC;

\choix du nombre de c\oe urs du CPU;

\choix de la puce graphique (GPU);

\choix des ISP (Image Signal Processor).


%@TODO rajouter éventuellement une troisième question ?
\end{questions}
\end{qcm}

\begin{corrige}
\begin{questions}
\item Réponse \choix[b]. Un SoC est un système intégré sur une puce qui regroupe l'essentiel d'un ordinateur : processeurs, mémoire, périphériques d'interface, etc.

\item Réponse \choix[c]. En effet, les performances graphiques dépendent avant tout de la puce graphique. C'est elle qui gère les calculs des images donc il est nécessaire d'avoir un bon GPU pour que les calculs se fassent rapidement.
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%

\sectionnn{Processus et ressources partagées}

%%% NEW 2025

\begin{exo}{Processus et Linux}{Lycée Richelieu, Rueil-Malmaison}{2}{15}
\begin{questions}
\item Quelle est l'utilité de la commande \texttt{ps} ?
\item À quoi sert la commande \texttt{kill} ?
\item Avec une ligne de commande dans un terminal, on obtient l'affichage suivant :

\Par

\texttt{smt@DEBVM-B3iS-VP0: \$ ps o user,pid,ppid,tty,stat,command}

\begin{tabular}{*6{l}}
\texttt{USER} & \texttt{PID} & \texttt{PPID} & \texttt{TT} & \texttt{STAT} & \texttt{COMMAND} \\
smt & 4073 & 4070 & pts/0 & S & /bin/bash --login \\
smt & 4114 & 4073 & pts/0 & S+ & vi monitor.py \\
smt & 4133 & 4070 & pts/1 & S & /bin/bash --login \\
smt & 4152 & 4133 & pts/1 & S+ & python3 monitor.py \\
smt & 4156 & 4070 & pts/2 & S & /bin/bash --login \\
smt & 5298 & 4156 & pts/2 & R+ & ps -o user, pid, ppid,tty,stat, command \\
\end{tabular}

\Par

Voici un bref résumé de certaines caractéristiques des colonnes affichées :\enlargethispage*{5em}\vspace*{-0.5em}
\begin{itemize}
    \item \texttt{USER} : nom d'utilisateur
    \item \texttt{TT} : numéro de terminal
    \item \texttt{STAT} : état du processus (S : interruptible sleep, R : running). Le signe + indique un processus exécuté en premier plan.
\end{itemize}

\newpage

\begin{questions}
    \item Quel est le PID du processus parent de la commande \texttt{vi monitor.py} ?
    \item Le script \texttt{monitor.py} contient le code suivant :

    \begin{verbatim}
    name = input('Saisir votre nom :')
    print('Bonjour', name, '!')
    \end{verbatim}

    Quel est le PID correspondant à l'exécution de ce script Python ?
    
    \item Après avoir lancé ce programme, l'utilisateur \texttt{smt} a saisi son prénom mais n'a pas encore validé. Justifier le statut indiqué par la commande \texttt{ps} pour ce processus.
    
    \item Selon vous, quelles seront les conséquences visibles de l'exécution de la commande suivante ?

    \begin{verbatim}
    $ kill 4070
    \end{verbatim}
\end{questions}
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item La commande \texttt{ps} permet d’afficher la liste des processus en cours d'exécution (sans option, elle n'affiche que les processus lancés par l'utilisateur courant depuis le terminal courant). 

\item La commande \texttt{kill} permet de terminer l'exécution d'un processus.

\item
\begin{questions}
\item Le PID du processus parent de \texttt{vi monitor.py} est son PPID : 4073.

\item Le script Python \texttt{monitor.py} est exécuté par la commande \linebreak \texttt{python3 monitor.py}, son PID est donc 4152.

\item Le processus est en attente d’une saisie de l’utilisateur, il n’est donc plus en cours d’exécution mais \og en attente \fg.

\item La commande \texttt{kill 4070} va terminer le processus parent des trois terminaux (interpréteur de commandes bash), qui sont eux-mêmes les processus parents des trois autres commandes listées \linebreak(\texttt{vi monitor.py}, \texttt{python3 monitor.py} et \texttt{ps}).

Par conséquent, les trois terminaux se fermeront.
\end{questions}
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Processus et ressources}{Lycée Fresnel, Caen}{2}{10}
% d'après bac 2022 amérique du sud J1 ex 4
Une machine exécute de manière concurrente quatre processus notés P1, P2, P3 et P4.

Le tableau ci-dessous donne l'état à un instant donné des différents processus qui peuvent soit mobiliser (M) des ressources (notées R1, R2, R3, R4 et R5), soit être en attente (A) des ressources, soit ne pas les solliciter (-).

Une ressource ne peut être mobilisée que par un seul processus à la fois. Si un autre processus demande une ressource déjà mobilisée, il passe en attente.

\begin{center}
\begin{tabular}{|C|c|c|c|c|c|}
\hline\tabulartitle
 & R1 & R2 & R3 & R4 & R5 \\
\hline
P1 & M & - & - & A & - \\
\hline
P2 & - & - & - & M & A \\
\hline
P3 & - & M & A & & - \\
\hline
P4 & A & - & M & - & M \\
\hline
\end{tabular}
\end{center}

\begin{questions}
\item À partir du tableau ci-dessus, démontrer que, à cet instant, les processus s'attendent mutuellement.
\item Comment s'appelle cette situation ?
\item On suppose que le processus P1 libère la ressource R1. Donner un ordre possible d'exécution des processus.
\end{questions}
\end{exo}


\begin{corrige}
\begin{questions}
\item Chacun des processus est en attente d'une ressource (donnée) qui est déjà mobilisée par un autre processus : P1 est en attente de R4, or R4 est déjà mobilisée par P2. P2 est en attente de R5 qui est mobilisée par P4, etc.
\item Cette situation où chaque processus est en attente d'une ressource mobilisée par un autre processus est appelée interblocage.
\item Lorsque R1 est libérée, P4 passe en exécution. S'il libère ensuite R3 et R5, alors P3 et P2 s'exécutent ensuite. Enfin, P1 attendait R4 qui est libérée par P2. D'où un ordre possible : P4 P3 P2 P1.
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\sectionnn{Ordonnancement}

\enlargethispage*{3em}
%%% NEW 2025
\begin{exo}{Ordonnancement de processus}{Lycée Richelieu, Rueil-Malmaison}{2}{15}
On considère cinq processus à ordonnancer, notés A, B, C, D et E. Les durées d'exécution et leurs dates d'arrivée respectives sont données dans le tableau ci-dessous. Les durées et dates sont exprimées en unités de temps (multiples de cycles d'horloge), une unité étant assimilable à un quantum de temps.

\begin{center}
\begin{tabular}{|c|c|c|}
\hline\tabulartitle
Processus & Durée d'exécution & Date d'arrivée \\
\hline
A & 3 & 0 \\\hline
B & 6 & 1 \\\hline
C & 4 & 4 \\\hline
D & 2 & 6 \\\hline
E & 1 & 7 \\\hline
\end{tabular}
\end{center}

\begin{questions}
    \item Quelle est la durée totale, en unités de temps, nécessaire pour l'exécution de ces cinq processus ?
    \item Décrire en quelques lignes la différence entre les algorithmes Shortest Job First (SJF) et Shortest Remaining Time (SRT).
    \item Donner le schéma d'exécution des algorithmes d'ordonnancement suivants :
    \begin{itemize}
        \item First-Come First-Served (FCFS) ;
        \item Shortest Job First (SJF) ;
        \item Shortest Remaining Time (SRT) ;
        \item Round Robin (RR) avec un quantum de 2.
    \end{itemize}
    \item Quelle est la différence entre le temps d'attente et le temps de séjour d'un processus ?
    \item Calculer le temps d'attente moyen pour chacun de ces quatre algorithmes. Pour cette question et la suivante, il peut être intéressant de présenter au moins une partie des calculs faits. Un résultat juste dont le calcul n'est pas fourni n'entraîne pas de perte de points.
    \item Calculer le temps de séjour moyen pour chacun de ces quatre algorithmes.
    \item Quelle politique d'ordonnancement donne le meilleur résultat, c'est-à-dire celui correspondant à la durée minimale d'attente moyenne par processus ?
\end{questions}

\end{exo}

\begin{corrige}
\begin{questions}
\item L'exécution de ces cinq processus nécessite au total $3+6+4+2+1=16$ cycles CPU.

    \item La différence essentielle entre ces deux algorithmes est que SRT est préemptif, contrairement à SJF. L'avantage d'un algorithme préemptif est qu'il peut reprendre la main après unité de temps pour modifier le processus à exécuter.

    \item Pour ces questions, en l'absence d'une spécification plus précise des algorithmes SRT et RR dans ce cours, il peut exister plusieurs schémas d'exécution possibles pour SRT entre les dates 6 et 10 (incluse) et pour RR à partir de la date 4. Ce corrigé présente une possibilité parmi plusieurs valides.
\Par
{
    \small
    \begin{tabular}{|C|*{13}{c|}}
    \hline
    Date & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\\hline
    FCFS & A & A & A & B & B & B & B & B & B & C & C & C & C  \\\hline
    SJF & A & A & A & B & B & B & B & B & B & E & D & D & C \\\hline
    SRT & A & A & A & B & C &C& C& C& E& D& D& B& B \\\hline
    RR & A& A& B& B& A& B& B& C& C& B& B& C& C \\\hline
    \end{tabular}
    
    \Par
    
    \begin{tabular}{|C|*{5}{c|}}
    \hline
    Date & 13 & 14 & 15 & $<t_{A}>$ & $<t_{S}>$ \\\hline
    FCFS &  D & D & E & 4,4 & 7,6 \\\hline
    SJF & C&C&C& 3,2 & 6,4 \\\hline
    SRT & B& B& B& 1,2 & 5,8   \\\hline
    RR & D& D& E & 3,8 & 8,4 \\\hline
    \end{tabular}
    
}

    \item Le temps de séjour correspond au temps d'attente (durée écoulée entre la date d'arrivée et la date d'exécution) additionné du temps d'exécution (durée écoulée entre la date de début de l'exécution et la date de fin d'exécution).

    \item On a le tableau suivant:
    \begin{center}
    \begin{tabular}{|C|c|c|c|c|c|c|c|}
    \hline\tabulartitle
    Algorithme & $t_{A}(A)$ & $t_{A}(B)$ & $t_{A}(C)$ & $t_{A}(D)$ & $t_{A}(E)$ & $<t_{A}>$ \\
    \hline
    FCFS & 0 & 2 & 5 & 7 & 8 & 4,4 \\
    SJF & 0 & 2 & 8 & 4 & 2 & 3,2 \\
    SRT & 0 & 2 & 0 & 3 & 1 & 1,2 \\
    RR & 0 & 1 & 3 & 7 & 8 & 3,8 \\
    \hline
    Algorithme & $t_{S}(A)$ & $t_{S}(B)$ & $t_{S}(C)$ & $t_{S}(D)$ & $t_{S}(E)$ & $<t_{S}>$ \\
    \hline
    FCFS & 3 & 8 & 9 & 9 & 9 & 7,6 \\
    SJF & 3 & 8 & 12 & 6 & 3 & 6,4 \\
    SRT & 3 & 15 & 4 & 5 & 2 & 5,8 \\
    RR & 5 & 10 & 9 & 9 & 9 & 8,4 \\
    \hline
    \end{tabular}
    \end{center}

    \item L'ordonnancement pour lequel le temps d'attente moyen est minimal est l'algorithme préemptif SRT.
\end{questions}
\end{corrige}

% NEW 2025

\newpage

\begin{exo}{Algorithme d'ordonnancement}{Lycée Fresnel, Caen}{3}{30}

On donne dans le tableau ci-dessous quatre processus qui doivent être exécutés par un processeur. Chaque processus a un instant d'arrivée et une durée, donnés en unités de temps.

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline\tabulartitle
Processus & P1 & P2 & P3 & P4 \\
\hline
Instant d'arrivée & 0 & 2 & 3 & 7 \\
\hline
Durée & 8 & 6 & 2 & 2 \\
\hline
\end{tabular}
\end{center}


Les processus sont placés dans une liste d'attente en fonction de leur instant d'arrivée.
On se propose d'ordonnancer ces quatre processus avec la méthode suivante :
\begin{itemize}
\item Parmi les processus présents en liste d'attente, l'ordonnanceur choisit celui dont la durée restante est la plus courte ;
\item Le processeur exécute le processus élu durant une unité de temps puis l'ordonnanceur désigne de nouveau le processus dont la durée restante est la plus courte ;
\item En cas d'égalité de temps restant entre plusieurs processus, celui choisi sera celui dont l'instant d'arrivée est le plus ancien ;
\item Tout ceci jusqu'à épuisement des processus en liste d'attente.
\end{itemize}


\begin{questions}
\item Quelle est la durée totale, en unité de temps, nécessaire à l'exécution des quatre processus.
\item En suivant l'algorithme ci-dessus, déterminer l'ordonnancement des 4 processus de l'exemple précédent.

\item On définit le temps d'exécution d'un processus comme la différence entre son instant de terminaison et son instant d'arrivée. Calculer la moyenne des temps d'exécution des quatre processus.

On se propose de modifier l'ordonnancement des processus. L'algorithme reste identique à celui présenté précédemment mais au lieu de s'exécuter durant une seule unité de temps, le processeur exécutera à chaque fois le processus choisi durant deux unités de temps. En cas d'égalité de temps restant, l'ordonnanceur départagera toujours en fonction de l'instant d'arrivée.

\item Recopier et compléter le schéma ci-dessous donnant le nouvel ordonnancement des quatre processus.

\includegraphics{280_ch8-ordo2.eps}

\item Calculer la nouvelle moyenne des temps d'exécution des 4 processus et indiquer si cet ordonnancement est plus performant que le précédent.
\enlargethispage*{2em}

On se propose de programmer l'algorithme du premier ordonnanceur. Chaque processus sera représenté par une liste comportant autant d'éléments que de durées (en unités de temps). 

Pour simuler la date de création de chaque processus, on ajoutera en fin de liste de chaque processus autant de chaînes de caractères vides que la valeur de leur date de création.

\begin{listing}[language=Python]{}{08-ordo1.py}
\end{listing}

La fonction \texttt{choix\_processus} est chargée de sélectionner le processus dont le temps restant d'exécution est le plus court parmi les processus en liste d'attente.

\item Quel est le contenu de la liste d'attente à $t=10$ (premier algorithme) ?

\item Recopier et compléter la fonction \texttt{choix\_processus} ci-dessous. Le code peut contenir plusieurs lignes.

\begin{listing}[language=Python]{}{08-ordo2.py}
\end{listing}

Une fonction \texttt{scrutation} (non étudiée) est chargée de parcourir la liste \texttt{liste\_proc} de tous les processus et de renvoyer la liste d'attente des processus en fonction de leur arrivée. À chaque exécution de \linebreak \texttt{scrutation}, les processus présents (sans chaînes de caractères vides en fin de liste) sont ajoutés à la liste d'attente. La fonction supprime pour les autres un élément de chaîne de caractères vides.

\item Recopier et compléter les différentes instructions de la fonction \linebreak \texttt{ordonnancement} pour réaliser le fonctionnement désiré.\enlargethispage*{5em}

\begin{listing}[language=Python]{}{08-ordo3.py}
\end{listing}
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item On additionne les quatre durées, il faut donc $\Delta t = 8 + 6 + 2 + 2 = 18$ unités de temps.
\item À $t=0$, seul P1 est arrivé, il est donc exécuté. À $t=2$, P1 et P2 sont dans la liste et leur durée restante est la même. C'est P1 qui est élu car le plus ancien. À $t=3$, P3 arrive avec une durée restante plus courte que les deux autres, il est donc exécuté durant deux unités de temps. À $t=5$, P1 a la durée restante la plus courte. Il est exécuté jusqu'à $t=7$ où P4 arrive et est exécuté. À $t=10$, il reste P1 (durée restante : 5) et P2 (durée restante 6). P1 est donc exécuté jusqu'à ce qu'il termine et enfin P2 est exécuté. On en déduit le chronogramme suivant :

\includegraphics{284_ch8-ordo1.eps}
\item 

\begin{tabular}{|c|c|c|c|c|}
\hline\tabulartitle
Processus & P1 & P2 & P3 & P4 \\
\hline
Instant d'arrivée & 0 & 2 & 3 & 7 \\
\hline
Instant de terminaison & 12 & 18 & 5 & 9 \\
\hline
Temps d'exécution & 12 & 16 & 2 & 2 \\
\hline
\end{tabular}

D'où un temps d'exécution moyen :
$$\Delta t_{moy} = \frac{12+16+2+2}{4} = 8	$$

\item \includegraphics{284_ch8-ordo3.eps}

\item 

\begin{tabular}{|c|c|c|c|c|}
\hline\tabulartitle
Processus & P1 & P2 & P3 & P4 \\
\hline
Instant d'arrivée & 0 & 2 & 3 & 7 \\
\hline
Instant de terminaison & 10 & 18 & 6 & 12 \\
\hline
Temps d'exécution & 10 & 16 & 3 & 5 \\
\hline
\end{tabular}

D'où le nouveau temps d'exécution moyen :
$$\Delta t_{moy} = \frac{10+16+3+5}{4} = 8,5$$

Cet algorithme d'ordonnancement est donc moins performant que le précédent.

\item La liste d'attente contient uniquement les processus arrivés et non encore terminés. À $t=10$, il reste P1 et P2, d'où :
\begin{verbatim}
>>> liste_attente
[
 ['1.8','1.7'], 
 ['2.6','2.5','2.4','2.3','2.2','2.1']
]
\end{verbatim}

\item ~\par\vspace*{-2.2em}

\begin{listing}[language=Python]{}{08-ordo2c.py}
\end{listing}

\Par


\item ~\par\vspace*{-2.2em}
\begin{listing}[language=Python]{}{08-ordo3c.py}
\end{listing}
\end{questions}
\end{corrige}


\thumb
\AfficheCorrige
